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.


    Access

    Download


    Export, share and cite



    Title :

    Improving Spatially Distributed Multiagent Pathfinding Using Cooperative JPS


    Contributors:

    Publication date :

    2016-01-12


    Remarks:

    Electronic Theses and Dissertations


    Type of media :

    Theses


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629




    Improving Lookahead search for grid-based pathfinding

    Karmacharya, Shrijan | BASE | 2020

    Free access

    Distributed Multiagent Systems

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



    Cooperative Monitoring to Diagnose Multiagent Plans

    Roberto Micalizio / Pietro Torasso | BASE | 2014

    Free access

    PATHFINDING SYSTEM, METHOD AND PROGRAM

    MUTSUGA KATSUHIKO / MOCHIZUKI ATSUSHI | European Patent Office | 2016

    Free access