Multi-Agent Pathfinding (MAPF) Algorithms
Multi-Robot Planning and Coordination
Carnegie Mellon University
Pittsburgh, PA
January 2024 - April 2024
Multi-Agent Path Finding (MAPF) is a computational problem focused on finding collision-free paths for multiple agents, such as robots or vehicles, in a shared environment. The goal is to ensure that each agent reaches its designated destination without colliding with others while minimizing overall path lengths or time. MAPF is highly relevant for many scenarios, such as automated warehouses, drone fleets, and multi-robot systems, where coordinated movement is crucial for efficiency, safety, and task completion. It addresses the challenges of dynamic and complex environments, making it essential for optimizing operations in various industries.
A picture of an Amazon robotic order-fulfilment center, where MAPF algorithms are crucial to avoid congestions and deadlocks
For this project, I implemented a single-agent solver and four Multi-Agent Path Finding (MAPF) solvers to explore their capabilities in navigating complex environments. I conducted a comprehensive analysis of each solver, identifying their strengths, limitations, and the specific scenarios where they struggle. Additionally, I compared their performances across various map configurations, highlighting how different environments impact their efficiency and effectiveness. This project not only deepened my understanding of pathfinding algorithms but also provided valuable insights into optimizing agent coordination in multi-agent systems.
Joint-State A*
Description:
Joint-State A* treats the combined positions of all agents as a single "joint state" and searches for a solution using A* across this joint state space. The algorithm ensures that all agents move without collisions by considering their interactions during the search.​
Drawbacks:
Joint-State A* has a very high branching factor. With n agents, each capable of moving in m directions, we get a branching factor of m^n. This means that the search process slows down exponentially with an increase in number of agents
Prioritized Planning
Description:
Prioritized planning works by planning a path for each agent sequentially, with the paths of previously planned agents as obstacles. This method is neither optimal nor complete, but finds solutions much faster than Joint-State A*.
Drawbacks:
Prioritized planning suffers from two primary shortcomings: the order of agent paths to be planned and the greedy nature of the algorithm itself, which can lead to suboptimality and/or incompleteness.
Prioritized Planning fails to find a solution in this example, due to algorithmic shortcomings
Conflict Based Search (CBS)
Description:
CBS constructs a conflict tree to resolve path conflicts between agents. Initially, individual paths are computed for each agent. When conflicts (e.g., collisions) arise among these paths, CBS adds nodes to the conflict tree, each representing a sub-problem where one conflict is avoided. The algorithm recursively explores the tree until it finds a set of conflict-free paths for all agents. CBS is both optimal and complete.
Drawbacks:
Although CBS manages scaling with respect to the number of agents more effectively than Joint State A*, it remains computationally intensive. This is because CBS, despite its more efficient approach to handling multiple agents, still requires significant resources as the number of agents increases. The complexity of resolving conflicts and maintaining optimality adds to the computational burden, making it challenging to scale in large or highly congested environments.
Priority Based Search (PBS)
Description:
PBS resolves path conflicts between agents using a different approach than CBS. Initially, individual paths are computed for each agent. When conflicts (e.g., collisions) arise, instead of constructing a conflict tree, PBS assigns priorities to agents to determine which agent's path takes precedence in a conflict. The algorithm iteratively adjusts these priorities and recomputes the paths of lower-priority agents to avoid conflicts. PBS is generally faster than CBS because it avoids the recursive exploration of conflict trees.
PBS is able to solve instances that CBS struggles on, for a given time constraint