MultiAgentAStar

class w9_pathfinding.mapf.MultiAgentAStar

Multi-Agent A* (MAA*) algorithm for multi-agent pathfinding.

This algorithm performs a joint search in the combined state space of all agents, treating the multi-agent configuration as a single search node.

It is optimal and complete — it is guaranteed to find a solution if one exists, and the solution will be optimal with respect to the Sum-of-Costs objective (i.e., the total cost across all agents’ paths).

This algorithm typically scales poorly due to the size of the joint state space. Can be suitable only for a small number of agents or simple environments.

Parameters:

env (Environment) – The environment in which to search for paths.

References

Standley, T.S.: Finding optimal solutions to cooperative pathfinding problems. In: AAAI Conference on Artificial Intelligence. pp. 173-178 (2010)

mapf(starts, goals, max_length=100, max_time=1.0, operator_decomposition=True, reservation_table=None)

Finds non-colliding paths for all agents from their respective start nodes to goal nodes. The result is a list of individual paths — one per agent.

Parameters:

  • starts (list[node]) – A list of start nodes, one per agent.

  • goals (list[node]) – A list of goal nodes, one per agent. Must be the same length as starts.

  • max_length (int, default=100) – The maximum allowed length of any individual agent’s path.

  • max_time (float, default=1.0) – The maximum amount of time (in seconds) allowed the solver to find a solution. If the time limit is exceeded, a RuntimeError is raised.

  • operator_decomposition (bool, default=True) – If True, enables Operator Decomposition to reduce branching in joint space.

  • reservation_table (ReservationTable, optional) – Dynamic obstacles.

Returns:

A list of paths, one per agent. If no collision-free paths are found, returns an empty list.

Return type:

list[list[node]]

Raises:

  • ValueError – If the number of starts and goals is different, or if any node is invalid.

  • RuntimeError – If no solution is found within the time constraint.