The Multiagent Pathfinding problem (MAPF) applies in fields such as video games, robotics, warehouse management, etc. MAPF is mainly concerned with routing units while avoiding collision. A recent approach by Wilt et al. to MAPF for maps with narrow corridors spatially partitions maps into High Contention (HCA) and Low Contention areas (LCA). A modified Cooperative A* is used in LCA. In our approach we introduce a new algorithm by combining “Cooperative” and “Jump Point Search” (JPS) to traverse through the LCA. JPS is modified to handle the multiagent environment by incorporating a new stopping rule to identify between HCA and LCA called “forced selection”. As JPS jumps from node to node, we introduce a “backtracking mechanism” to avoid collision. We evaluate our algorithm against Wilt et al.’s algorithm on real video game maps and demonstrate significate improvements in terms of makespan, solution time and failure-rate.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Improving Spatially Distributed Multiagent Pathfinding Using Cooperative JPS


    Beteiligte:

    Erscheinungsdatum :

    12.01.2016


    Anmerkungen:

    Electronic Theses and Dissertations


    Medientyp :

    Hochschulschrift


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629




    Improving Lookahead search for grid-based pathfinding

    Karmacharya, Shrijan | BASE | 2020

    Freier Zugriff

    Distributed Multiagent Systems

    Mahmoud, MagdiSadek / Karaki, Bilal J. | Springer Verlag | 2022


    Distributed Cooperative Control of Autonomous Vehicle Chassis Based on Multiagent Theory

    Li, Yuxing / Cai, Yingfeng / Sun, Xiaoqiang et al. | IEEE | 2025



    Cooperative Monitoring to Diagnose Multiagent Plans

    Roberto Micalizio / Pietro Torasso | BASE | 2014

    Freier Zugriff