Scalable Multi-Robot Path Planning via Quadratic Unconstrained Binary Optimization

1. Problem Statement

The paper addresses Multi-Agent Path Finding (MAPF), the challenge of computing collision-free paths for multiple robots in a shared environment while optimizing metrics like travel time or distance.

• The Core Issue: Classical centralized MAPF algorithms (e.g., Conflict-Based Search, Time-Expanded Graphs) suffer from exponential growth in joint-state complexity as the number of agents increases. This makes them computationally prohibitive for large swarms.
• The Gap: While Quadratic Unconstrained Binary Optimization (QUBO) has been applied to combinatorial problems (e.g., TSP, Max-Cut), existing formulations lack the specific structural adaptations required for dynamic, grid-based multi-robot coordination, such as comprehensive collision avoidance, variable reduction, and handling current hardware limitations (qubit counts).

2. Methodology

The authors propose a robotics-oriented QUBO framework that encodes all agents into a single global optimization problem. The methodology relies on four key pillars:

A. QUBO Formulation for MAPF

The path planning problem is modeled as minimizing a cost function $C(x) = x^T Q x$, where binary variables $x$ represent robot positions at specific time steps.

• Encoding: Uses a linear encoding where variables are mapped as $x_{i,j,t}$ (robot at grid cell $(i,j)$ at time $t$).
• Penalty Design: The cost function incorporates specific penalties to enforce constraints:
  • One-Hotness: Ensures a robot occupies only one cell per time step.
  • Adjacency: Ensures continuous movement (no teleportation) based on 4-connectivity.
  • Start/End Conditions: Enforces correct initial and final positions.
  • Obstacle Avoidance: Structurally enforced by removing obstacle nodes from adjacency lists rather than explicit penalties.
  • Multi-Agent Collision: Penalizes two robots occupying the same cell at the same time.
• Normalization: The authors empirically determined that normalization scales (e.g., 1.0 vs. 2.0) significantly impact solver performance, with different scales optimal for different problem sizes and solvers (QAOA vs. Quantum Annealing).

B. Logical Pre-Processing (BFS-Based)

To address the variable explosion inherent in QUBO, the authors introduce a Breadth-First Search (BFS) based pre-processing strategy:

• Variable Reduction: By analyzing reachability and connectivity, the system identifies and fixes variables that must be 0 (e.g., obstacles, unreachable cells) or 1 (start positions) before the solver runs.
• Impact: This achieves >95% variable reduction, drastically shrinking the QUBO matrix size and making the problem tractable for current hardware.

C. Time-Windowed Decomposition

Instead of solving the entire path horizon (e.g., 100 steps) in one massive QUBO, the problem is broken into overlapping or sequential time windows (e.g., 5–10 steps).

• Mechanism: Each window is solved independently but maintains continuity with the previous window's path.
• Approximation Penalty: For non-final windows, the "Goal Penalty" is replaced with an "Approximation Penalty" that encourages moving closer to the goal (reducing Manhattan distance) without forcing immediate arrival, preventing the solver from getting stuck in local minima or teleporting.
• Benefit: This allows the system to solve large-scale problems on hardware with limited qubits and supports dynamic replanning (e.g., adding obstacles mid-flight).

D. Multi-Agent Adaptation

• Global Clock: A centralized global time index is used to synchronize agents, allowing for relative start times.
• Linear Scaling: Unlike classical methods where complexity grows exponentially with agent count, the QUBO variable count grows linearly with the number of agents ($O(M \times N \times T \times R)$).
• Synergy: Counter-intuitively, adding more robots can sometimes reduce total variable usage because the pre-processing logic can prune more of the shared state space.

3. Key Contributions

1. Unified QUBO Framework: A novel formulation that treats multi-robot path planning as a single global optimization problem, shifting the complexity burden from exponential joint states to linear variable growth.
2. BFS-Based Pre-Processing: A logical reduction technique that eliminates >95% of variables, making the approach viable for current quantum and quantum-inspired hardware.
3. Time-Windowed Decomposition: A strategy to bypass hardware qubit limits by solving the problem in incremental steps while maintaining path continuity.
4. Adaptive Penalty System: A robust penalty design (including backtracking and teleportation prevention) tailored specifically for grid-based robotics, moving beyond generic routing formulations.
5. Empirical Baseline: The first honest comparison establishing performance baselines for QUBO-based MAPF against classical algorithms (A*, Dijkstra) in terms of solution quality and scaling behavior.

4. Results and Performance

The study was evaluated on grid environments (5×5 and 10×10) with up to 4 robots using simulated QAOA (PennyLane) and D-Wave simulated annealing.

• Single-Agent Performance: Classical algorithms (A*) remain significantly faster (0.001s vs. 0.003s). QUBO is not yet superior for single-robot tasks.
• Multi-Agent Scaling:
  • In dense 10×10 scenarios with 4 robots, QUBO achieved near-optimal solutions (5.3% path length penalty compared to optimal).
  • While still slower in absolute time (0.563s vs. 0.003s for classical), QUBO demonstrated more favorable scaling properties. As the number of agents increases, the gap narrows because classical sequential planning struggles with combinatorial explosion, whereas QUBO's linear variable growth remains manageable.
• Variable Reduction: The BFS pre-processing reduced variable counts from thousands to dozens (e.g., 300 $\to$ 12 variables in a 5×5 single-robot case, a 96% reduction).
• Failure Modes: The system occasionally gets stuck in local minima (staying near the goal) or requires window restarts to resolve invalid moves, but these are rare with proper penalty tuning.

5. Significance and Future Work

• Practical Baseline: The paper does not claim immediate "quantum advantage" but establishes a reproducible, scalable baseline for future quantum-ready robotics. It bridges the gap between classical robotics and emerging quantum optimization.
• Scalability: The linear scaling of variables with respect to agent count suggests that QUBO could outperform classical methods in large-scale swarm scenarios where classical search spaces become prohibitive.
• Limitations:
  • Centralization: The current approach relies on a single solver, which conflicts with the distributed nature of swarm robotics.
  • Swap Collisions: Handling "swap" collisions (robots swapping places) requires quartic terms, which are difficult to encode in standard QUBO.
  • Hardware Noise: Current quantum hardware (qubit counts ~100-150) is prone to noise, requiring redundancy or error mitigation.
• Future Directions: The authors propose exploring distributed QUBO formulations, binary encoding to reduce qubit requirements, and integration with Variational Quantum Eigensolvers (VQE).

Conclusion: This work demonstrates that while current hardware cannot yet beat classical planners in speed, the structural scalability of the QUBO approach offers a promising pathway for future large-scale multi-robot coordination as quantum hardware matures.