Multi Agent Path Finding

Overview

This is a project that I had to do for my csci-360 class Introduction to Artificial Intelligence. This project uses time-space A* to implement two different solvers: Prioritized Planning and ConflictBased Search (CBS).

Just as a note when attempting to find the paths using the Prioritized Planner, sometimes an optimal path may not be found. This is because the goal state of a higher priority agent may block a lower priority agent from reaching it's own goal state.

Example:
@ @ @ @ @ @ @ @ @ @ @
@ A0 A1 . . . . . . . . G1 G0 @
@ @ @ @ @ . . @ @ @ @ @
@ @ @ @ @ @ @ @ @ @ @

As you can see if Agent A1 has the highest priority it will prevent agent A0 from ever reaching its goal state. However if A0 is the higher prioity agent it will force A1 to move out of the way into the little divit in the middle as the lower priority agent, A1, cannot be on a collision path with the higher priority agent, A0.

Preparation:

Before running the code please make sure that you have Python 3 with matplotlib as well as numpy packages installed.

Compiling and Running the Code:

To compile the code first navigate into either the PrioritizedPlanner or ConflictBasedSearch directories.

• Prioritized Planner
  • ../code/PrioritizedPlanner/
• CBS
  • ../code/ConflictBasedSearch/

To compile:

cmake .
make

To execute the code after making the executable:

./PrioritizedPlanner exp0.txt exp0_paths.txt

Here, file exp0.txt is the input file that contains the information of the map and the start and goal locations of the agents. File exp0 paths.txt is the output file that contains the paths.

*Note*: You can change the input file name to any valid input file and the output file can be whatever you desire as long as it ends in .txt.

To run code with a path in a different directory its the same process:

./ConflictBasedSearch ../test/test_1.txt test_1_CBS_paths.txt

To use the python visualizer make sure that you pass in the paths for the same map.

To run the python visualizer:

python3 ../visualize.py exp0.txt exp0_paths.txt

And thats it, you should be able to compile and run the programs, as well as use the visualization tool.

If you would like to continue reading, I will go into more detail about the A* search algorithm as well as both the Conflict Based Search and Prioritized Planning algorithms.

Important Note

If you plan on cloning the repo then you have to remove the files that cmake generates otherwise you will get an error. In both the /PrioritizedPlanner and /ConflictBasedSearch directories remove all files that aren't: (.cpp or .h ; CMakeLists.txt)

The exp_..txt files are test cases and you don't need to keep them. There are more test cases in the /test directory.

A* Search

A* is an informed variation of Dijkstra. And it can be considered a 'best first search' as it greedily chooses which vertex to explore next based off the value function: f(v) = h(v) + g(v)