COMP90054 AI Planning for Autonomy

Since the purpose of assignments is to help you learn more, marks should not be assigned only on whether your code passes a few test cases but also on how much you have learnt.

Who knows better about whether you have learnt from this assignment other than yourself? We ask you to evaluate your work.

Each submission will contain a short self-reflection on what the student learnt, how they approached the tasks (including writing new tests) and will give the student a chance to argue that, even though they didn’t complete a task, they tried and learnt from it.

More generally, In the past we saw several people either not submitting a self evaluation or not really taking the time to reflect on their learning. In this assignment, we make the expectations clearer: students are not only marked based on the code performance, but also their self evaluation.

Your task contains programming excercises with increasing difficulty. This is where we give students control over how much assessment they want to complete or have the time to complete.

• Programming Code Performance (7 marks):
  • Practice
  • Part 0 (0 marks)
  • Part 1
  • Part 2
  • Part 3
• Self Evaluation Quality (3 marks)
• Submission Instruction

You must build and submit your solution using the sample code we provide you in this repository, which is different from the original UC Berkley code base.

• Please remember to complete the SELFEV.md file with your individual submission details (so we can identify you when it comes time to submit).

• You should only work and modify file search.py in doing your solution. Do not change the other Python files in this distribution.

• Your code must run error-free on Python 3.8. Staff will not debug/fix any code. Using a different version will risk your program not running with the Pacman infrastructure or autograder.

• Your code must not have any personal information, like your student number or your name. That info should go in the SELFEV.md file, as per instructions above. If you use an IDE that inserts your name, student number, or username, you should disable that.

• Assignment 1 FAQ is available to answer common questions you might have about Assignment 1 on ED

• Getting started on GitHub - the video below explains how to clone, git add, commit and push while developing your solution for this assignment:

• You can set up your local environment:

  • You can install Python 3.8 from the official site, or set up a Conda environment or an environment with PIP+virtualenv.
  • You need to install additional package (func_timeout) using: pip3 install func_timeout

• Alternatively, you can use docker:

  • You need to install docker from the official site
  • Please check Docker Run to run your code.

To familiarise yourself with basic search algorithms and the Pacman environment, it is a good start to implement the tasks at https://inst.eecs.berkeley.edu/~cs188/fa18/project1.html, especially the first four tasks; however, there is no requirement to do so.

You should code your implementations only at the locations in the template code indicated by ***YOUR CODE HERE*** in files search.py, please do not change code at any other locations or in any other files.

This is a great way to test that you understand the submission instructions correctly, and how to get feedback from our hidden test-cases as many times as you want. Here are the steps:

• Please tag your solution with test-submission. If you are not familiar with tag, please check tag hints
• We are going to run your code in our server. You can check your result from this link after a few minutes. This can test your code for part 1, 2 and 3.

Taking inspiration from what we have discussed in our lectures and workshops, implement a good heuristic function for A* algorithm (already implemented). Inserting your code into the template indicated by the comment *** YOUR CODE HERE FOR TASK 1 *** . You can view the code location at the following link: search.py#L129.

python pacman.py -l mediumMaze -p SearchAgent -a fn=astar,prob=FoodSearchProblem,heuristic=foodHeuristic

The autograder seeks an optimal solution length within the time budget (10 seconds) for each test case. The node expansion number will directly impact your result, please inspect the autograder for further thresholds information. In addition, please make sure your heuristic is admissible, otherwise you may not get full marks for this part due to not finding the optimal plan.

You will see in first person the balance between 1) how informed you make your heuristic (it should expand less nodes in general), and 2) the overall runtime. As you can see, sometimes it may be preferable to have a cheaper less informed heuristic, even if you end up expanding more nodes.

Other layouts are available in the layouts directory, and you can easily create you own.

We have been exposed to single-agent problems in lectures and tutorials, but in real-life situations, which are often more complex, we often need to consider more than one agent. This part involves solving a more complicated problem as if it were a single agent problem. You will be able to model this new type of problem following the instructions below.

Multi-Agent Pathfinding problems (MAPF) involve a set of agents, each with a start and goal location. The goal of the problem is to find paths for all the agents so that they can simultaneously travel along these paths without colliding with each other. Realistic applications of these problems include automated warehouses and autonomous vehicles driving. Check this video out to understand the real-world application of what you are about to solve.

This is similar to problem 7 (practice part) of the Berkeley Pacman framework. You need to model the state space of a problem with multiple agents. Each agent has a target food of its own in the maze. Our task is to control all agents to eat all their corresponding food (points) in the maze. In other words, all agents need to visit their corresponding target food position at least once, but they do not neeed to stay at that position after that.

In order to implement this, there is a new problem called MAPFProblem provided to you. Some of the variables are listed in the code comment blocks and the initialization for the functions. You will need to:

1. Make sure isGoalState recognises whether the current state is a goal state.
2. Implement your transition function in getSuccessors, which should return a list of tuples that contain (next_state, action_dict, cost). next_state and action_dict should follow the required format detailed below. The cost would just be 1. Intuitively, each tuple contains all the possible successors states, where each successor is defined by the next state after all pacmans move simultaneously through the actions specified by the action dictionary.

• A search_state in this problem is a tuple in the format of ( pacmanPositions, foodGrid ) where:

    pacmanPositions:  a dictionary {pacman_name: (x,y)} specifying Pacmans' positions
    foodGrid:         a Grid (see game.py) of either pacman_name or False, specifying the target food of each pacman.
  

• An action_dict is a dictionary {pacman_name: direction} specifying each pacman's move direction, where direction could be one of 5 possible directions in Directions (i.e. Direction.SOUTH, Direction.STOP etc)

For this part, you need to make sure these collisions are avoided:

1. Vertex Collision: agents attempt to access the same position at the same time.
2. Swapping Collision: agents attempt to swap their positions at the same time. In other word, agents would crash into each other.

You should insert your code into the template indicated by the comments *** YOUR CODE HERE FOR TASK 2 ***, you can view the locations at these links: search.py#L158 and search.py#L177.

Optional We encourage you to test your submission locally with your own layouts by editing test_cases_assignment1/part2/MAPF_test.test. And we enourage you to share new layouts publicly in this ED Megathread to enable other students to test their submissions on these layouts as well. You can start threads to discuss and compare performance with other students.

You should be able to test your program by running the localauto_grader or online server grader.

In this part we will help you prove to yourself that you have all the ingredients to pick up many new search algorithms, tapping into knowledge you acquired in the lectures and tutorials.

Solutions to multi-agent path planning problems can usually be categorized into two types: Coupled and Decoupled methods. The Coupled approach considers all agents together to find the best solution, as we did in part 2. A more detailed explanation can be found in the relavant video. However, the coupled approach taken in part 2 cannot scale to large size problems, this is why this part will introduce a new hybrid coupled and decoupled algorithm knwon as Conflict Based Search (CBS), which has revolutionised this field.

Conflict Based Search (CBS) is a two-level algorithm that consists of two parts: low-level search and high-level search. The algorithm first performs a low-level search, executing a search for each agent to find the corresponding optimal path to satisfy the constraints imposed by the high-level CT (Conflict Tree) node. Then, the algorithm moves onto the high-level search phase, which utilises the Conflict Tree to fix possible conflicts.

Conflict Tree is a tree structure constructed based on conflicts between individual agents' paths, where each node represents a set of constraints on the movement of an agent. These restrictions reflect the conflicts that may occur at a corresponding time if the pacman is at a certain location. The deeper level nodes of the conflict tree contain more constraints than the shallow nodes in the tree, as each successor may add a new constraint resulting from the new computed path if a conflict exists.

In many cases, CBS is able to improve the efficiency of the search by examining a smaller number of states than the A* algorithm while maintaining optimality.