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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Space-Time Conflict Spheres for Constrained Multi-Agent Motion Planning


    Contributors:
    Chari, Anirudh (author) / Chen, Rui (author) / Liu, Changliu (author)


    Publication date :

    2023-06-04


    Size :

    2887859 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Trajectory Planning for Time-Constrained Agent Synchronization

    Marchukov, Yaroslav / Montano, Luis | TIBKAT | 2020


    Trajectory Planning for Time-Constrained Agent Synchronization

    Marchukov, Yaroslav / Montano, Luis | Springer Verlag | 2019


    Multi-Agent Motion Planning using Deep Learning for Space Applications

    Yun, Kyongsik / Choi, Changrak / Alimo, Ryan et al. | AIAA | 2020



    Vehicle motion planning method based on risk field in multi-vehicle conflict scene

    LU GUANGQUAN / TANG RENJING / WANG ZHAOJIE | European Patent Office | 2023

    Free access