Multi-Agent Pathfinding

Multi-Agent Pathfinding (MAPF) is the problem of finding collision-free paths for multiple agents moving simultaneously in a shared environment. Each agent has a unique start and goal location, and the goal is to plan a path for every agent such that they reach their goals without colliding with one another.

MAPF algorithms

Algorithm	Class	Optimal	Complete
Hierarchical Cooperative A*	HCAStar	False	False
Windowed Hierarchical Cooperative A*	WHCAStar	False	False
Conflict Based Search	CBS	True	True
Increasing Cost Tree Search	ICTS	True (only in an unweighted environment)	True
A* with Operator Decomposition	MultiAgentAStar	True	True

• ReservationTable
• SpaceTimeAStar
• HCAStar
• WHCAStar
• CBS
• ICTS
• MultiAgentAStar