Multi-Agent Path Finding (MAPF) is a well-known problem in the field of Artificial Intelligence (AI) that involves finding a set of collision-free paths for a group of agents in a shared environment. We briefly discuss the scope of the project, the current progress and results below. A detailed report can be found here.
Conrtibutors: Shiva Surya Lolla, Dheeraj Bhogisetty and Siyuan Huang
- Abstract
- Problem Description
- Current Progress
- How to run the code
- Results
- References
This project explores the problem of Multi-Agent Path Finding (MAPF) on a 2D grid map. The MAPF problem is to plan optimal collision-free paths for a large number of agents given their start and goal locations. MAPF has many potential real-world applications such as automated warehouse systems, office robots, autonomous aircraft towing vehicles, and game characters in video games, etc. However, the solution to this problem is NP-hard and designing practical systems to find high-quality collision-free paths in real-time for such agents is extremely challenging. We plan to explore and implement three optimal MAPF planners - Conflict-Based Search, Symmetry Breaking, and Mutex Propagation. The robot agents are simulated in a Pygame environment, and the performance of the algorithms is evaluated against various benchmarks. The objective of this study is to compare and analyze the effectiveness of the three algorithms and provide insights into the challenges of solving the MAPF problem.
The Classical MAPF problem in its simplest form can be described as follows: On a 2-dimensional grid, there are ‘n’ robots and some of the cells are blocked (obstacles). The positions of blocked cells and starting cells of ‘n’ robots are known. A different unblocked cell is assigned to each of the n robots as its goal cell. The problem is to move the robots from their starting cells to their goal cells in discrete time steps and let the robots wait at their goal position until all the robots have reached their goal. The optimization objective is to minimize the number of time steps until all robots are at their goal cells, i.e., the simulation time which is called the makespan. During each time step, each robot can wait in its current cell or move to a free neighbouring cell in one of the four main compass directions – North, East, West, or South. Robots are not allowed to collide. Two robots collide if and only if, during the same time step, they both move to the same cell or both move to the current cell of another robot.
This paper gives an exhaustive overview on the MAPF problem, its variants and different classes of solution.
We developed a custom PyGame environment to create an interactive simulator to configure custom maps and agents’ start and goal configurations. Through the PyGame environment, users can easily change the size of the map, place or remove obstacles, and add or remove agent start and goal pairs. Once the user has finished setting up the environment, one can simply press a key to run the underlying MAPF algorithms which return the path of each agent if a collision-free solution can be found. Given the paths, the PyGame simulator can then animate the movement of each agent over each time step.
Conflict-Based search [2] is implemented in two-level: highlevel and low-level. The pseudo-code for the algorithm is shown in Fig. 3. At first, the low-level planner is invoked to find initial paths for the agents. The low-level planner uses A* to find paths for each individual agent exclusively. The highlevel planner maintains a conflict tree and the initial solution is added as the root node to this tree. The obtained paths are checked for conflicts and if found a constraint is added as a node to the tree. The planner iteratively searches for a solution by resolving constraints at each level of the tree until all of them are resolved, if possible. The low level is called again in each iteration to update the paths of the agents to be consistent with the imposed constraints. CBS returns an optimal solution if one exists.
Reference paper: Conflict-Based Search
We visualized the agents’ paths generated by CBS using the Pygame interface. We started by simulating two agents in a 2-D grid and were able to successfully plan optimal paths for upto ten agents. We experimented with different configurations of agent start and goal positions. Few results are shown below.
[Grid with 2 agents](https://u[MAPF4.webm](https://user-images.githubusercontent.com/81319659/222927674-06a6fc38-09ea-4250-b07d-7c932f2e1c2d.webm)