The problem is MAPF on a graph with a start vertex and a goal vertex for every agent. At each discrete time step an agent may move along a legal edge or wait, but agents must not occupy the same vertex at the same time or traverse the same edge in opposite directions simultaneously. The principal objective studied is sum of costs, defined as the sum, over all agents, of the number of time steps needed to reach their goals. The paper notes that other global objectives, such as makespan, are possible, but the supplied excerpt does not establish results for those alternatives.
The main contribution is Increasing Cost Tree Search, a two-level formulation that differs conceptually from applying traditional single-agent A* variants to the joint state space. At the high level, ICTS searches vectors of individual path costs, beginning with each agent's shortest-path cost when other agents are ignored and increasing components in increasing total-cost order. At the low level, it tests whether the selected individual costs can be realized by a set of paths without conflicts, using multi-value decision diagrams. The paper also develops pruning mechanisms, including pairwise consistency tests and Enhanced Pairwise Pruning, to reduce low-level work. Beyond proving optimality, it explicitly characterizes cases in which A*-based approaches are better than ICTS.
An ICT node is a vector containing one individual path cost for each agent, and its node cost is the sum of those components. The high-level tree starts at the vector of independent shortest-path costs and generates cost-increasing alternatives, so the first ICT node whose costs admit a valid joint solution has minimum possible total cost. For a selected cost, the low-level phase builds an MDD for each agent; the MDD contains the agent's possible paths from its start to its goal with exactly that cost, represented as a layered directed acyclic structure. The algorithm searches the implicit Cartesian product of the MDDs rather than materializing the entire product in memory, rejecting combinations with vertex conflicts or opposite edge traversals. Pairwise MDD checks can first determine whether two agents have compatible paths, allowing an ICT node to be discarded before a more expensive multi-agent search is performed.
The evaluation covers open four-connected grids, grids with randomly scattered obstacles, and benchmark game maps from Sturtevant's pathfinding database. It also includes a large 257 by 257 map from Dragon Age: Origins. For the grid experiments, the authors randomized 100 problem instances for each relevant agent count and report averages over instances solved by all compared variants. Comparisons include regular A*, A* with Operator Decomposition, basic ICTS, and ICTS with additional pruning or enhanced variants. Reported measures include generated or visited nodes, runtime, the number of instances solved within a time limit, and success rate. The excerpt does not provide every implementation detail, complete parameter setting, or full table, so all experimental conditions cannot be reconstructed from the supplied evidence alone.
ICTS is attractive when the set of relevant individual cost vectors is smaller than the joint state expansion generated by A*. Its advantage depends not only on the number of agents but also on map topology, the ratio of agents to vertices, conflict density, and the amount by which agents must increase their individual costs to pass one another. In some cases ICTS generates fewer nodes but still takes longer because its per-node constant overhead is larger. Conversely, pruning can make ICTS dramatically faster on instances where many cost combinations or MDD branches can be rejected early. The paper presents dense small grids and a corridor in which two agents must travel far to swap order as pathological cases for ICTS. Future work proposed in the excerpt includes viewing low-level search as a constraint satisfaction problem, understanding the influence of instance parameters, and extending ICTS to weighted graphs and abstract goals.
Independent shortest paths are not sufficient for MAPF because paths that are individually optimal can collide when executed simultaneously. Earlier optimal approaches described in the paper extend A* to search combinations of agent states, while other decoupled approaches use macro-operators but do not generally provide both optimality and completeness. The resulting challenge is to preserve an optimality guarantee without exploring every combination of all agents' positions at every time step. ICTS addresses this challenge by separating the question of individual path costs from the question of whether paths with those costs can coexist.
The input consists of a graph and a start and goal vertex for each of the agents. A solution is a collection of paths that reaches every goal while respecting vertex and opposite-edge collision constraints. The optimization target is the minimum sum of individual arrival costs, denoted in the paper by the optimal solution cost. The supplied evidence does not establish the behavior of the method for weighted edges, abstract or set-valued goals, or objectives other than sum of costs; these are presented as extensions or alternatives rather than fully evaluated settings.
The high-level root is the vector of independent shortest-path costs, and each ICT node is ordered by the sum of its vector components. An MDD stores only locations and transitions that can participate in a path of one specified cost, with layers corresponding to time steps. Low-level search traverses the implicit product of the individual MDDs and enforces both same-vertex and opposite-edge conflict rules. The paper's theoretical argument shows that every high-level node visited has total cost no greater than the optimal solution cost and that low-level states are similarly bounded under the relevant admissible-cost reasoning. This bound explains why ICTS can avoid some surplus states generated by a full-state A* search.
The experiments include an 8 by 8 open grid, a 3 by 3 grid, 32 by 32 grids with different percentages of random obstacles, and large game maps. Some grid experiments use a coupling mechanism to generate hard instances and do not activate the ID framework, whereas the game-map experiments activate it; these experiment types are distinguished in the supplied text. The DAO evaluation reports runtime and success-rate behavior as the number of agents changes, and the grid evaluations report node and time comparisons as well. The excerpt does not establish the complete set of map names, all tested agent counts, or all implementation choices.
On the 8 by 8 open grid, ICTS generated fewer nodes than the A* variants and required the same or slightly less time in a lower-agent regime. As the number of agents increased, the comparison shifted: for one reported threshold, A* variants became faster even when ICTS still generated slightly fewer nodes, and with more agents the A* variants clearly outperformed ICTS in both nodes and time. The corridor example illustrates the opposite extreme: A* solved the stated instance in 51 milliseconds, while basic ICTS required 36,688 milliseconds because the relevant cost-vector increase was very large. In other experiments, especially with enhanced pruning, ICTS was faster than basic ICTS and was reported to outperform A* with Operator Decomposition by almost three orders of magnitude on an 8 by 8 setting. DAO results also contain many cases where ICTS or ICTS with enhanced pruning was faster, but the evidence does not support a claim of universal dominance.
ICTS provides an optimal MAPF search framework by decomposing the problem into selecting individual path costs and checking whether those costs support a collision-free collection of paths. Because high-level nodes are explored in nondecreasing total-cost order and the low-level test is exhaustive over the relevant MDD space, the first feasible ICT node represents an optimal solution. The experiments support the theoretical claim that performance is governed by structural properties of the instance rather than by a universally best algorithm. ICTS and A*-based methods therefore occupy complementary parts of the optimal-MAPF design space.
ICTS can suffer from an exponential search over individual cost vectors, while A*-based approaches can suffer from exponential growth in the number of agents in the joint state space. If only a few agents are present but they must incur a large cost increase to resolve a conflict, the ICT tree can become very large. Dense environments can create many conflicts and large MDD products, and pairwise pruning itself adds computation. The supplied excerpt does not establish worst-case practical performance beyond the discussed examples, nor does it show that the proposed variants are complete or optimal for all MAPF variants.
The paper is important because it introduces a structural alternative to joint-state A* for optimal MAPF. Its use of cost vectors and MDDs turns the relationship between individual shortest paths and global feasibility into an explicit search problem. The analysis also gives a useful methodological lesson: node counts, runtime, and solvability can favor different algorithms, and the best method depends on agent density, topology, and conflict structure. The pruning ideas provide a foundation for later work on cost-based and constraint-based optimal MAPF search.
This paper is recommended for researchers studying optimal MAPF, search decomposition, multi-value decision diagrams, and the practical trade-offs between ICTS and A*-based solvers. It is especially useful for readers who want both an optimality argument and empirical evidence showing why algorithm rankings change across instance families. It also serves as a starting point for understanding pruning strategies and the later research directions suggested by the ICTS framework.