This paper presents a novel approach to address the challenge of planning paths for multi-agent systems subject to complex constraints. The technique, called the Decentralized Multi-Agent Rapidly-exploring Random Tree (DMA-RRT) algorithm, extends the Closed-loop RRT (CL-RRT) algorithm to handle multiple agents while retaining its ability to plan quickly. A core component of the DMA-RRT algorithm is a merit-based token passing coordination strategy that makes use of the tree of feasible trajectories grown in the CL-RRT algorithm to dynamically update the order in which agents replan. The reordering is based on a measure of each agent's incentive to change the plan and allows agents with a greater potential improvement to replan sooner, which is demonstrated to improve the team's overall performance compared to a traditional, scripted replan order. The main contribution of the work is a version of the algorithm, called Cooperative DMA-RRT, which introduces a cooperation strategy that allows an agent to modify its teammates' plans in order to select paths that reduce their combined cost. This modification further improves team performance and avoids certain common deadlock scenarios. The paths generated by both algorithms are proven to satisfy inter-agent constraints, such as collision avoidance, and numerous simulation and experimental results are presented to demonstrate their performance.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Decentralized path planning for multi-agent teams with complex constraints


    Beteiligte:

    Erschienen in:

    Autonomous Robots ; 32 , 4 ; 385-403


    Erscheinungsdatum :

    2012


    Format / Umfang :

    19 Seiten, 61 Quellen




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch




    Decentralized path planning for multi-agent teams with complex constraints

    Desaraju, V. R. | British Library Online Contents | 2012


    Decentralized abstractions for multi-agent systems under coupled constraints

    Boskos, Dimitris / Dimarogonas, Dimos V. | British Library Online Contents | 2019


    Decentralized Multi-Agent Path Finding for UAV Traffic Management

    Ho, Florence / Geraldes, Ruben / Goncalves, Artur et al. | IEEE | 2022


    Multi-Agent Decentralized Search of a Probability Map with Communication Constraints

    Millet, T. / Casbeer, D. / Mercker, T. et al. | British Library Conference Proceedings | 2010


    Multi-agent Decentralized Search of a Probability Map with Communication Constraints*

    Millet, Travis / Casbeer, David / Mercker, Travis et al. | AIAA | 2010