cs.ROFeb 16, 2026

Scalable Multi-Robot Path Planning via Quadratic Unconstrained Binary Optimization

Authors: Javier González Villasmil

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Multi-Agent Path Finding (MAPF) remains a fundamental challenge in robotics, where classical centralized approaches exhibit exponential growth in joint-state complexity as the number of agents increases. This paper investigates Quadratic Unconstrained Binary Optimization (QUBO) as a structurally scalable alternative for simultaneous multi-robot path planning. This approach is a robotics-oriented QUBO formulation incorporating BFS-based logical pre-processing (achieving over 95% variable reduction), adaptive penalty design for collision and constraint enforcement, and a time-windowed decomposition strategy that enables execution within current hardware limitations. An experimental evaluation in grid environments with up to four robots demonstrated near-optimal solutions in dense scenarios and favorable scaling behavior compared to sequential classical planning. These results establish a practical and reproducible baseline for future quantum and quantum-inspired multi-robot coordinations.

Figures & tables

Figure 1
Figure 3: Example QAOA circuit for a small pathfinding problem with 2 qubits (after pre-processing). The circuit alternates between cost and mixer Hamiltonians for p=2 layers.
Figure 3
Figure 4
Figure 5
ProblemGridRobotsClassicalQUBOPath (C/Q)VariablesReduction
   Time (s)Time (s)(steps)(orig/red)(%)
5×5 Single5×51<< 0.0010.0039/9300 →\to 1296%
5×5 Multi5×520.0010.05118/18500 →\to 1696.8%
10×10 Multi10×1020.0030.56376/809600 →\to 0100%
Table 1: Performance comparison of Classical MAPF vs QUBO-based approach

Explore similar work

CardsList

  1. Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding

    Mar 11, 2026Fernando Salanova, Eduardo Montijano, Cristian MahuleaMulti-Agent PlanningMulti-Agent Path Finding

    Dept. of Systems Engineering and Computer Science, University of Zaragoza, Zaragoza, Spain

  2. The Cost of Classical Multi-Agent Path Finding

    Oct 7, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianMulti-Agent Path FindingGraph-Based Planning

    Chalmers University of Technology Gothenburg, Sweden

  3. Multi-Agent Route Planning as a QUBO Problem

    Feb 8, 2026Renáta Rusnáková, Martin Chovanec, Juraj GazdaMulti-Objective Optimization

    Department of Computers and Informatics, Faculty of Electrical Engineering and Informatics, Technical University of Košice, Letná 9, 042 00 Košice