Increasing Cost Tree Search (ICTS)

ICTS does not search the joint state-space of all agents directly. Instead, it searches a Cost Tree where each node represents a vector of possible path costs for each agent. The root node contains the optimal individual path cost for each agent, ignoring others. The algorithm then explores increasing the sum of costs (SOC) budget, generating new cost vectors where one or more agents' costs are incremented. This high-level search identifies feasible cost combinations before verifying them with low-level pathfinding.

For each agent and a given cost bound, ICTS builds a Multi-Valued Decision Diagram (MDD). An MDD is a directed acyclic graph that compactly encodes all possible optimal paths for that single agent within the specified cost limit. Nodes represent locations, and edges represent moves across time steps.

• Key Property: An MDD for cost c contains all paths of length exactly c from start to goal.
• Function in ICTS: The MDD allows the algorithm to efficiently check if a set of cost-compatible paths (from the Cost Tree) can be combined into a joint, collision-free plan without searching all possible permutations.

ICTS uses a two-level search hierarchy to decouple cost optimization from collision checking.

• High-Level Search: Explores the Cost Tree. For each candidate cost vector, it passes the individual cost bounds to the low-level search.
• Low-Level Search: For each agent, it generates an MDD based on its assigned cost bound from the high level. It then performs a depth-first search over the Cartesian product of all agents' MDDs to find a non-conflicting combination of paths. If found, a solution exists for that cost vector. If not, the high-level search continues.

ICTS is an optimal MAPF algorithm for the Sum of Costs (SOC) objective. It guarantees finding the solution with the minimum possible total distance traveled by all agents, provided one exists.

Mechanism of Guarantee:

• The Cost Tree is explored in a best-first order based on the SOC of each cost vector.
• The first cost vector for which the low-level search finds a conflict-free joint plan is, by definition, the optimal SOC. The algorithm systematically proves that no lower-cost combination is feasible.

A core efficiency mechanism in ICTS is pruning the low-level search by detecting implicit conflicts through MDD analysis. Before a full depth-first search, the algorithm can perform pairwise checks:

• If the MDDs of two agents do not intersect in space-time for their given cost bounds, those agents cannot conflict, and their path combination is trivially valid.
• If MDDs intersect only at specific nodes/edges, the search can be constrained to avoid those conflicts early. This pruning prevents the exponential exploration of all path combinations within the MDDs.

ICTS and Conflict-Based Search (CBS) are sister algorithms, both providing optimal SOC solutions but with complementary approaches.

Key Contrasts:

• Search Space: ICTS searches in the space of cost combinations. CBS searches in the space of constraints on agent behavior.
• Data Structure: ICTS uses MDDs to encode path sets. CBS uses constraint trees and replans individual paths.
• Performance Profile: ICTS can be more efficient when many agents have similar, short optimal paths. CBS often excels when conflicts are sparse but complex. The choice between them is often problem-dependent.

Multi-Agent Path Finding (MAPF) is the foundational computational problem that ICTS solves. It involves finding collision-free paths for multiple agents from their start locations to their goal locations in a shared, typically discretized, environment. The core challenge is the combinatorial explosion of possible joint actions.

• Optimality Criteria: Solutions are evaluated on metrics like Sum of Costs (SOC) or Makespan.
• Centralized vs. Decoupled: Algorithms like ICTS and CBS are centralized, while methods like Priority Planning are decoupled.
• Core Constraints: Solutions must avoid Vertex Conflicts and Edge Conflicts.

Conflict-Based Search (CBS) is the primary alternative optimal algorithm to ICTS for solving MAPF. It employs a two-level search: a high-level constraint tree and low-level path planners for individual agents.

• Constraint Resolution: When a conflict (e.g., two agents occupying the same vertex at the same time) is detected, CBS branches by adding constraints that prevent the conflict, forcing one agent to avoid that space-time cell.
• Comparison to ICTS: While ICTS searches a tree of cost combinations, CBS searches a tree of constraints. CBS often has superior performance in practice due to more effective pruning.
• Bypass Conflict: A refinement where an agent's path is locally adjusted to go around another without increasing cost, avoiding a new constraint branch.

A Multi-Value Decision Diagram (MDD) is a compact, directed acyclic graph that encodes all possible optimal paths for a single agent from start to goal within a specific cost bound (e.g., length or time).

• Core ICTS Component: ICTS uses MDDs to represent the search space for each agent efficiently. The algorithm searches over combinations of MDD levels.
• Pruning Power: By intersecting MDDs, ICTS can quickly prune combinations of paths where agents would collide, as no compatible state exists at that time step.
• Structure: An MDD for cost C has C+1 layers, where each node represents a world state the agent can be in at that time step while staying optimal.

These are the two primary optimality criteria for evaluating MAPF solutions, which ICTS is designed to optimize.

• Sum of Costs (SOC): Also called Flowtime. Defined as the sum of the path lengths (or travel times) for all individual agents. ICTS directly minimizes SOC by searching cost combinations. Example: Three agents with path lengths 5, 7, and 9 have an SOC of 21.
• Makespan: The total time elapsed from the start until the last agent reaches its goal. This metric focuses on overall completion time rather than total effort. Algorithms can be tailored to optimize for one metric or the other.

A Cardinal Conflict is the most severe type of conflict in MAPF. It occurs between two agents where any feasible resolution (e.g., making one agent wait) unavoidably increases the sum of their path costs.

• Impact on Search: Identifying cardinal conflicts is crucial for efficient search. In algorithms like CBS, recognizing a conflict as cardinal allows the search to prune one of the two resulting branches immediately, as it cannot lead to a better solution.
• Relation to ICTS: In the ICTS framework, a cardinal conflict would manifest as a situation where, for a given cost budget, the MDDs of the two agents have no non-conflicting path combination, forcing the search to a higher cost tier.

Bounded Suboptimal Search refers to a class of algorithms that sacrifice guaranteed optimality for dramatic gains in speed, with a provable bound on solution quality (e.g., no more than 1.2x the optimal cost).

• Scalability Trade-off: Optimal algorithms like ICTS and CBS can be slow for large fleets. Bounded suboptimal variants (e.g., Enhanced CBS (ECBS)) use focal searches and cost heuristics to find good solutions quickly.
• Engineering Relevance: In many real-world logistics and warehousing applications, a provably good enough solution computed in milliseconds is more valuable than an optimal solution computed in minutes.