QUBOによるスケーラブルなマルチロボット経路計画
Scalable Multi-Robot Path Planning via Quadratic Unconstrained Binary Optimization
マルチエージェント経路探索をQUBOで定式化し、BFS前処理と適応的ペナルティ、時間窓分解で最大4台のロボットの準最適経路を効率的に求めた。
分類: cs.RO, quant-ph
原文アブストラクト
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.