Multi-agent path finding is one of the key problems in the topic of multi-agent system. While some inevitable execution delays resulting from the realistic factors, such as robot faults or avoiding human etc., may make the path plan invalid. Our aim is to effectively find paths with robustness to k-delays for all agents, i.e., each agent can get a k-step margin in its paths without breaking the whole plan, especially for the large-scale systems. We propose a priority-based hierarchical framework for k-robust multi-agent path finding, where the pattern of searching path while avoiding conflict is profit to reduce the burden of conflict handling in k-robust planning. Then, the classification and generation rules of robust constraints are designed to guarantee global k-robustness of prioritized planning. Finally, for the new challenge of k-robust starting predicament, a multi-level key-agent guided priority adjustment mechanism is proposed to improve solution success rate. Experimental results show that the proposed algorithm can effectively reduce the runtime, and averagely maintain a success rate of over 95%. Especially for large-scale problems with hundreds of agents, the runtime can be reduced to a few seconds. In addition, the runtime does not increase dramatically as the k-value grows from 0 to 7.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Priority-Based Hierarchical Framework for k-Robust Multi-Agent Path Finding


    Contributors:
    Zhang, Kaixiang (author) / Mao, Jianlin (author) / Zhang, Shufan (author) / Wang, Ning (author)

    Published in:

    Publication date :

    2024-09-01


    Size :

    3068211 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Multi-Agent Path Finding with Priority for Cooperative Automated Valet Parking

    Okoso, Ayano / Otaki, Keisuke / Nishi, Tomoki | IEEE | 2019


    Decentralized Multi-Agent Path Finding for UAV Traffic Management

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


    Hierarchical path-finding for Navigation Meshes (HNA*)

    Pelechano Gómez, Núria / Fuentes, Carlos | BASE | 2016

    Free access

    High Density Automated Valet Parking via Multi-agent Path Finding

    Okoso, Ayano / Otaki, Keisuke / Koide, Satoshi et al. | IEEE | 2022


    Finding a Path in the Hierarchical Road Networks

    Park, C. K. / Sung, K. / Doh, S. et al. | British Library Conference Proceedings | 2001