Search papers, labs, and topics across Lattice.
This paper introduces a QUBO-based approach to multi-robot path planning, addressing the scalability limitations of classical centralized methods. The authors formulate MAPF as a QUBO problem, incorporating BFS-based pre-processing for variable reduction and adaptive penalty design for constraint satisfaction. Experimental results in grid environments with up to four robots show near-optimal solutions and improved scaling compared to sequential planning, suggesting a viable baseline for quantum and quantum-inspired algorithms.
Forget A*, QUBO offers a surprisingly scalable alternative for multi-robot path planning, achieving near-optimal solutions even in dense scenarios.
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.
