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 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, Travis / Casbeer, David / Mercker, Travis et al. | AIAA | 2010


    Path Planning for a Multi-robot System with Decentralized Control Architecture

    Metoui, Fethi / Boussaid, Boumedyen / Abdelkrim, Mohamed Naceur | Springer Verlag | 2020


    Path Planning for a Dubins Agent with Resource Constraints and Dynamic Obstacles

    Cortez, Alan C. / Ford, Bryce T. / Nayak, Indranil et al. | AIAA | 2023