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.
Space-Time Conflict Spheres for Constrained Multi-Agent Motion Planning
2023-06-04
2887859 byte
Conference paper
Electronic Resource
English
Trajectory Planning for Time-Constrained Agent Synchronization
TIBKAT | 2020
|Trajectory Planning for Time-Constrained Agent Synchronization
Springer Verlag | 2019
|Vehicle motion planning method based on risk field in multi-vehicle conflict scene
European Patent Office | 2023
|