WHCAStar

class w9_pathfinding.mapf.WHCAStar

Windowed Hierarchical Cooperative A* (WHCA*) for multi-agent pathfinding.

WHCA* improves upon HCA* by introducing a fixed time window for planning. Within this window, it plans paths for each agent individually using SpaceTimeAStar, while avoiding collisions with other agents.

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, window_size=16, 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.

  • window_size (int, default=16) – Time window size for path planning.

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