ICTS

class w9_pathfinding.mapf.ICTS

Increasing Cost Tree Search (ICTS) algorithm for multi-agent pathfinding.

ICTS is a two-level search algorithm that explores combinations of path costs to find collision-free solutions.

  1. High-level search - Performs a top-down search over combinations of individual path costs, forming an Increasing Cost Tree (ICT). The root of the tree represents the minimal possible path costs for each agent.

  2. Low-level search - For each high-level node, attempts to build a valid joint plan using Multi-value Decision Diagrams (MDDs) to ensure that the agents’ paths do not conflict.

This algorithm is complete — it is guaranteed to find a solution if one exists. It is also optimal with respect to the Sum-of-Costs objective, but only in unweighted environments (i.e. where all edges have equal cost). In weighted environments, it may still find valid solutions, but they are not guaranteed to be optimal.

Parameters:

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

References

Sharon, G., Stern, R., Goldenberg, M., Felner, A.: The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence 195, 470-495 (2013)

mapf(starts, goals, max_length=100, max_time=1.0, ict_pruning=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 for the solver to find a solution. If the time limit is exceeded, a RuntimeError is raised.

  • ict_pruning (bool, default=True) – If True, enables enhanced pairwise pruning.

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

num_closed_nodes

Number of Constraint Tree (CT) nodes expanded (processed) during the last search.

num_generated_nodes

Total number of Increasing Cost Tree (ICT) nodes generated during the last search.