Subdimensional Expansion

The algorithm starts by planning an optimal path for each agent independently, ignoring all other agents. This is performed in each agent's individual state space, which is exponentially smaller than the full joint state space. The initial solution is the set of these independent, conflict-prone paths.

• Key Benefit: Avoids the curse of dimensionality from the outset.
• Method: Typically uses A* or similar single-agent planners.
• Result: A fast baseline solution that is often optimal if no conflicts exist.

The core innovation is the dynamic expansion of the search space. The planner checks the set of independent paths for conflicts (e.g., two agents occupying the same vertex at the same time). Only when a conflict is detected between a subset of agents does the algorithm merge their state spaces, creating a new, higher-dimensional joint state space for that specific group.

• Process: A conflict between agents A and B triggers the creation of a 2D joint space (A x B).
• Efficiency: The global joint space (A x B x C x ...) is never fully constructed, saving immense memory and computation.

The algorithm operates in a loop: detect conflict, expand subspace, replan within it, and integrate the new joint plan. This creates a hierarchy of coupled groups. A new conflict between an agent in a coupled group and a third agent may lead to that group being merged with the third agent's space.

• Example: Agents 1 & 2 are coupled. If agent 3 now conflicts with the joint plan for (1,2), the subspace expands to (1,2,3).
• Outcome: The search dimensionality grows only as needed to resolve the specific interdependencies present in the problem instance.

When using an optimal single-agent planner (like A*) for the initial paths and for replanning within expanded subspaces, Subdimensional Expansion can guarantee optimality with respect to the sum of individual costs (SOC). This is because the algorithm systematically explores the necessary joint configurations to resolve conflicts without increasing cost unnecessarily.

• Proof: The search is equivalent to a systematic exploration of the relevant regions of the full joint state space.
• Bound: The solution cost is provably equal to the cost found by a full joint-space A* search, but found much more efficiently.

This technique provides massive scalability improvements over monolithic joint-space searches like Multi-Agent A (MAA)**. The primary savings are:

• Memory: Storing and searching many small subspaces versus one enormous joint space.
• Computation: Pruning vast regions of the joint space that correspond to irrelevant agent combinations.
• Practical Impact: Allows optimal solutions for problems with dozens of agents where MAA* would be intractable, often achieving performance closer to that of suboptimal algorithms.

Subdimensional Expansion is a foundational concept that bridges decoupled and coupled planning. It is the underlying principle of the prominent Conflict-Based Search (CBS) algorithm. In CBS, the high-level search tree manages constraints, and the low-level searches are instances of single-agent planning—this is a concrete implementation of the subdimensional expansion philosophy.

• CBS Analogy: Each high-level node defines a set of constraints that effectively decouples agents; expanding the tree is akin to expanding the search dimensions.
• Contrast with MAA*: MAA* is always fully coupled. Contrast with Priority Planning, which is always fully decoupled with a fixed hierarchy.

Subdimensional Expansion is critical for coordinating fleets of Autonomous Mobile Robots (AMRs) and Automated Guided Vehicles (AGVs) in distribution centers. It enables:

• Dynamic task assignment for order picking and put-away.
• Real-time collision avoidance in narrow aisles and at intersections.
• Integration with manual forklifts by treating them as dynamic obstacles with predictable paths. The algorithm's efficiency allows for the continuous replanning required when new orders are injected into the system, minimizing makespan and maximizing throughput.

In baggage handling systems, Subdimensional Expansion coordinates hundreds of independent carrier vehicles moving along a fixed track network. Key applications include:

• Merging and sorting at high-speed junctions without deadlocks.
• Priority routing for transfer bags with tight connection windows.
• Fault tolerance by dynamically replanning around disabled vehicles or blocked lanes. The method's ability to resolve cardinal conflicts optimally ensures system-wide efficiency is maintained even during peak operational loads.

For teams of Unmanned Ground Vehicles (UGVs) exploring disaster sites, Subdimensional Expansion facilitates cooperative coverage and mapping.

• Exploration of partitioned areas where robots operate independently until their paths converge.
• Efficient rendezvous planning for data exchange or resource transfer.
• Avoidance of dynamic hazards (e.g., aftershocks, fire spread) by treating them as expanding obstacle zones. The lazy expansion of the joint state space conserves computational resources on edge hardware, allowing for longer mission durations.

This technique manages the movement of customer vehicles and service robots in fully automated parking garages.

• Bidirectional traffic flow in aisles, requiring precise resolution of edge conflicts.
• Staging and queuing for electric vehicle charging stations.
• Integration with elevator systems for multi-story facilities, modeled as shared resources with temporal constraints. Subdimensional Expansion's conflict-driven approach is ideal for this environment, where most vehicles are independent until they compete for the same ramp or parking spot.

In cleanroom environments, overhead hoist transport systems and AGVs move wafer cassettes between processing tools. Subdimensional Expansion is applied for:

• Precision scheduling to meet strict cycle time requirements and tool readiness.
• Vibration-minimizing trajectories to protect delicate wafers, often modeled as kinodynamic constraints.
• Contamination zone avoidance by enforcing strict spatial separation rules. The algorithm's optimality guarantees help minimize the sum-of-costs (SOC), directly reducing production cycle times and increasing fab yield.

Beyond physical robotics, Subdimensional Expansion algorithms simulate realistic crowd movement for games and architectural planning.

• Large-scale battle scenes with hundreds of NPC units navigating to strategic positions.
• Pedestrian flow simulation in urban environments or emergency egress studies.
• Formation keeping for groups of units moving as a cohesive squad. The bounded suboptimal variants of these algorithms (e.g., Windowed Hierarchical Cooperative A*) provide the real-time performance required for 60 FPS gameplay while producing visually convincing, collision-free group movement.

Multi-Agent Path Finding (MAPF) is the foundational computational problem of finding collision-free paths for multiple agents from their start locations to their goal locations in a shared environment. It is the core problem that Subdimensional Expansion and other algorithms aim to solve.

• Centralized vs. Decoupled: Algorithms are categorized by whether they plan in the joint state space of all agents (centralized, like MAA*) or plan for agents separately while managing interactions (decoupled, like Priority Planning).
• Optimality Criteria: Solutions are typically evaluated by Makespan (total completion time) or Sum of Costs (SOC) (total distance traveled by all agents).
• Applications: Extends beyond robotics to video game character AI, warehouse automation, and airport ground traffic control.

Conflict-Based Search (CBS) is a two-level, optimal search algorithm for MAPF that represents a major alternative paradigm to Subdimensional Expansion. It operates by:

• High-Level Constraint Tree: Searching a tree where each node contains a set of constraints (e.g., "Agent A cannot be at vertex V at time T") and a solution that satisfies them.
• Low-Level Path Planner: For each agent, a single-agent planner (like A*) finds the shortest path that obeys the current set of constraints.
• Conflict Resolution: When a Vertex Conflict or Edge Conflict is found in the current solution, the algorithm branches by adding a new constraint for one of the involved agents to resolve it.

CBS explores the space of constraints rather than the full joint state space, making it highly effective for optimal solutions in moderately-sized problems.

Multi-Agent A (MAA)** is a centralized, optimal search algorithm that serves as a baseline for understanding the complexity Subdimensional Expansion avoids. It applies the classic A* algorithm directly to the joint state space of all agents.

• State Explosion: The joint state space size grows exponentially with the number of agents (O(b^n), where b is branching factor, n is agent count). This makes MAA* intractable for large fleets.
• Heuristic Design: Requires an admissible heuristic for the entire fleet, often the sum of individual agent heuristics (like Manhattan distance).
• Contrast with Subdimensional Expansion: While MAA* searches the full high-dimensional space from the start, Subdimensional Expansion begins in individual, low-dimensional spaces and expands dimensionality only as needed to resolve conflicts, offering a more scalable search strategy.

A Multi-Value Decision Diagram (MDD) is a compact data structure critical for representing an agent's possible paths within a cost bound, and it is often used within algorithms like CBS and Subdimensional Expansion.

• Structure: An MDD for a single agent is a directed, acyclic graph that encodes all possible paths the agent can take from start to goal that have exactly the same optimal cost (or within a bounded cost).
• Efficiency: It compresses the exponential number of possible paths into a manageable graph by merging nodes that represent the same (location, time) pair.
• Use in Conflict Detection: MDDs allow for extremely fast identification of potential Cardinal Conflicts. By comparing the MDDs of two agents, an algorithm can determine if all optimal paths for both agents inevitably lead to a conflict at a specific time and location.

Increasing Cost Tree Search (ICTS) is another optimal MAPF algorithm that takes a cost-based approach, contrasting with the state-space search of Subdimensional Expansion.

• Two-Level Search:
  1. High-Level: Searches a "Cost Tree" where each node represents a vector of individual path costs for all agents (e.g., Agent1=5, Agent2=7). The tree is explored by incrementally increasing the sum of costs.
  2. Low-Level: For a given cost vector, a solver checks if there exists a set of individual paths meeting those exact costs that are also conflict-free.
• Pruning: Branches of the cost tree are pruned if it's impossible for an agent to reach its goal within its allocated cost (often verified using an MDD).
• Philosophical Difference: While Subdimensional Expansion dynamically adds dimensions (agents) to the search, ICTS dynamically increases the allowed cost budget in a structured way.

These are specific types of agent interactions that advanced MAPF algorithms like CBS and Subdimensional Expansion must classify and resolve efficiently.

• Cardinal Conflict: The most severe conflict type. It occurs when two agents conflict, and resolving it by making either agent wait unavoidably increases the sum of their path costs (SOC). Detecting these often requires analyzing MDDs.
• Bypass Conflict: A favorable type of conflict. It occurs when an agent's path can be locally modified to "go around" another agent without increasing its own path cost. Resolving a bypass conflict is cost-neutral.
• Semi-Cardinal Conflict: A conflict that is cardinal for one agent but not the other.
• Algorithmic Impact: Efficiently identifying conflict types allows algorithms to make smarter branching decisions. Prioritizing the resolution of cardinal conflicts often leads to faster solution times.