Multi-agent motion planning (MAMP) is a critical challenge in applications such as connected autonomous vehicles and multi-robot systems. In this paper, we propose a space-time conflict resolution approach for MAMP. We formulate the problem using a novel, flexible sphere-based discretization for trajectories. Our approach leverages a depth-first conflict search strategy to provide the scalability of decoupled approaches while maintaining the computational guarantees of coupled approaches. We compose procedures for evading discretization error and adhering to kinematic constraints in generated solutions. Theoretically, we prove the continuous-time feasibility and formulation-space completeness of our algorithm. Experimentally, we demonstrate that our algorithm matches the performance of the current state of the art with respect to both runtime and solution quality, while expanding upon the abilities of current work through accommodation for both static and dynamic obstacles. We evaluate our algorithm in various unsignalized traffic intersection scenarios using CARLA, an open-source vehicle simulator. Results show significant success rate improvement in spatially constrained settings, involving both connected and non-connected vehicles. Furthermore, we maintain a reasonable suboptimality ratio that scales well among increasingly complex scenarios.
翻译:多试剂运动规划(MAMP)是连接自主车辆和多机器人系统等应用中的一个关键挑战。在本文件中,我们为MAMP提出一个空间时间冲突解决方法。我们用一种新型的、灵活的、基于球体的分解方法来为轨迹设计问题。我们的方法利用一种深度的第一冲突搜索战略来提供分解方法的可缩放性,同时保持对组合方法的计算保证。我们形成了回避离散错误和坚持对生成解决方案的动态限制的程序。理论上,我们证明了我们的算法的持续时间可行性和配制空间的完整性。我们实验性地表明,我们的算法在运行时间和解决方案质量方面都与目前艺术状态的性能相匹配,同时通过固定和动态障碍的便利扩大当前工作的能力。我们利用开放源车辆模拟器CARLA评估了我们各种未信号化交通交叉情景的算法。结果显示,空间限制环境在相互连接和非连接的车辆之间都取得了显著的成功率改进。此外,我们保持一种合理的亚性亚性比例。