HCAStar

class w9_pathfinding.mapf.HCAStar

Hierarchical Cooperative A* (HCA*) algorithm for multi-agent pathfinding.

HCA* plans paths for each agent individually using SpaceTimeAStar, while avoiding collisions with previously planned agents by reserving their space-time paths.

This algorithm is neither optimal nor complete, but it is fast and often works well in practice.

Parameters:

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

References

Silver, D. 2005. Cooperative pathfinding. In AIIDE, 117-122.

mapf(starts, goals, max_length=100, 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.

  • 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.