Push and Swap

Push and Swap is formally proven to be complete for any solvable MAPF instance on a graph, meaning it is guaranteed to find a solution if one exists. This distinguishes it from many heuristic or sampling-based approaches that may fail to find a solution even when one is present. Its completeness relies on a structured set of local operations that can systematically rearrange agents in strongly connected graphs, even in highly congested scenarios.

The algorithm is built around two fundamental, local operations:

• Push: Moves a chain of agents along a path to create an empty vertex (a "hole"). This is the primary method for repositioning agents.
• Swap: Exchanges the positions of two adjacent agents. This is the essential operation for resolving deadlocks where agents are mutually blocking each other's goals. These maneuvers are applied iteratively according to a set of priority rules to guide each agent toward its destination without creating unsolvable gridlock.

A defining strength of Push and Swap is its effectiveness in densely packed environments where the ratio of agents to free space is high. Unlike algorithms that require significant free space for maneuvering, Push and Swap uses the agents themselves as movable obstacles to create temporary pathways. It is particularly well-suited for warehouse rack aisles or factory floor grids where agents start very close to their target locations but are interleaved.

The algorithm's guarantees hold under specific topological conditions:

• Graph must be biconnected: The environment must remain connected even if any single vertex is removed. This ensures the "hole" created by a Push operation can always be moved.
• At least one empty vertex: The algorithm requires at least one unoccupied starting location (a "hole") to initiate the Push maneuver. These requirements make it ideal for well-connected grid or lattice workspaces but less suitable for environments with narrow corridors or choke points that violate biconnectivity.

While often analyzed as a centralized algorithm, the rule-based nature of Push and Swap allows for decentralized or distributed implementations. Each agent can execute the Push and Swap rules based on local observations of its immediate neighbors and a shared priority ordering. This aligns with modern multi-agent system principles where agents operate with limited communication, making it relevant for scalable fleet orchestration where central coordination is a bottleneck.

Push and Swap occupies a unique niche within the MAPF taxonomy:

• *Vs. Search-based (CBS, MAA)**: It is rule-based, not search-based, avoiding exponential growth in joint state space. It provides completeness but not optimality guarantees on metrics like Sum of Costs.
• Vs. Reactive (ORCA): It is a planned, deterministic algorithm, not a reactive collision avoidance scheme. It solves the full problem from start to goal, not just instantaneous velocity selection.
• Vs. Prioritized Planning: It does not assign a fixed, global priority. Priorities are dynamic and local, derived from the rule set, allowing more complex interactions than simple sequential planning.

In automated storage and retrieval systems (AS/RS), robots must frequently access pallets stored in dense grid racks. Push and Swap is directly applicable for retrieving a target pallet blocked by others. The algorithm systematically executes push maneuvers to create temporary space and swap maneuvers to reposition blocking agents, enabling the retrieval robot to reach its goal without requiring empty slots. This minimizes the need for large, inefficient buffer zones within the racking system.

Port container yards are classic examples of tightly packed grid environments. Transfer cranes (the agents) must navigate to specific containers, which are often buried behind others. Push and Swap provides a complete method for planning the sequence of moves where containers (modeled as agents) are temporarily relocated. The swap operation is crucial here, allowing two adjacent containers to exchange positions, a common requirement for creating access lanes in extremely congested layouts without predefined empty slots.

For fully automated valet parking systems, a fleet of autonomous mobile robots (AMRs) must park and retrieve customer vehicles in a structured, grid-like garage. Push and Swap algorithms plan the coordinated movements to extract a target vehicle blocked by others. The local push and swap maneuvers correspond to the precise, low-speed movements required to shuffle vehicles within the confined space of a parking bay, ensuring all vehicles remain accessible.

In circuit board assembly, components are placed by robots on panels that move through stations. If a panel must be reworked, it may need to be routed back through the line, requiring other panels to be temporarily moved. Modeling panels as agents on a linear or grid-like track, Push and Swap can plan the deadlock-free reshuffling in buffer zones to prioritize the rework panel without halting the entire production flow, utilizing the limited buffer space efficiently.

Beyond physical robotics, Push and Swap provides the foundational logic for a class of video game puzzles and Sokoban-like problems. The algorithm guarantees a solution exists for any solvable configuration of movable blocks (agents) and empty spaces (holes) on a graph. Game engines can use it to:

• Verify level solvability during design.
• Generate hint systems by computing the next optimal push/swap move.
• Power AI-controlled characters in games requiring cooperative block-pushing puzzles.

Systems composed of identical modular robots that can connect and disconnect to form structures must often rearrange themselves. Push and Swap offers a planning framework for modules moving on the surface of a structure. A module can push a line of connected modules (like a train) and swap positions with an adjacent module. This enables complex self-reconfiguration tasks, such as changing the shape of a robotic swarm or repairing a structure by replacing a faulty module from within.

The foundational computational problem that Push and Swap solves. MAPF seeks collision-free paths for multiple agents from start to goal locations in a shared graph or grid environment. Core challenges include:

• Optimality: Minimizing metrics like Makespan or Sum of Costs (SOC).
• Completeness: Guaranteeing a solution will be found if one exists.
• Scalability: Managing the exponential growth of the joint state space as agent count increases.

A leading optimal algorithm often contrasted with Push and Swap. CBS is a two-level search:

• High-level: Searches a constraint tree, where each node imposes constraints (e.g., "Agent A cannot be at vertex V at time T") to resolve conflicts.
• Low-level: Plans individual paths for each agent using a fast single-agent solver like A*, respecting the current constraints. It guarantees optimality but can be computationally heavy in dense, highly coupled environments where Push and Swap's local maneuvers excel.

The most severe type of conflict in MAPF, central to understanding algorithmic complexity. A Cardinal Conflict occurs between two agents where any resolution (e.g., making one agent wait) unavoidably increases the Sum of Costs. This represents an irreducible cost addition. Algorithms like CBS must branch on these conflicts. Push and Swap's completeness relies on its ability to perform non-cost-preserving swaps and pushes to resolve such deadlocks in dense packing scenarios.

The two primary optimality criteria for evaluating MAPF solutions like those from Push and Swap.

• Makespan: The total time until the last agent reaches its goal. Minimizing makespan focuses on overall throughput.
• Sum of Costs (SOC): The sum of each agent's individual path length or travel time. Minimizing SOC focuses on total fleet effort or energy use. Push and Swap is complete (finds a solution if one exists) but is not designed for optimality under these metrics, prioritizing solvability in dense, complex graphs.

A scalable, suboptimal algorithm used in large-scale or lifelong MAPF settings. WHCA* operates by:

• Planning paths for each agent within a short, fixed-duration time window.
• Using a reservation table to avoid collisions within that window.
• Replanning periodically as agents move. It contrasts with Push and Swap's approach: WHCA* is decentralized and fast for open spaces but can deadlock in tightly packed scenarios where Push and Swap's systematic swaps guarantee progress.

A compact data structure used to reason about agent paths in optimal MAPF algorithms. An MDD for a single agent encodes all possible optimal paths from start to goal within a given cost bound (e.g., shortest path length).

• Each layer of the MDD corresponds to a timestep.
• Nodes represent possible locations at that time. Algorithms like CBS and ICTS use MDDs for efficient conflict detection and reasoning. While not directly used in Push and Swap, understanding MDDs highlights the structured search space that Push and Swap navigates through local operations.