用量子优化方法解决多机器人路径规划，效率更高且可扩展。
Scalable Multi-Robot Path Planning via Quadratic Unconstrained Binary Optimization
- 将多机器人路径问题转为可并行求解的QUBO模型
- 在4个机器人的密集场景中接近最优，变量减少超95%
- 适合未来量子计算或硬件加速的多机协同研究
多智能体路径规划（MAPF）是机器人领域的基础挑战，传统集中式方法随智能体数量增加导致状态空间呈指数级增长。本文探索二次无约束二值优化（QUBO）作为可扩展的替代方案，提出面向机器人任务的QUBO建模：结合基于BFS的逻辑预处理（实现超过95%的变量压缩），自适应惩罚设计以确保无碰撞与约束满足，并采用时间窗分解策略，使算法可在现有硬件上运行。在网格环境中对最多4个机器人的实验表明，该方法在密集场景中获得近最优解，且相比传统顺序规划展现出更优的可扩展性。这些结果为未来量子及量子启发式多机器人协调提供了实用且可复现的基准。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。