Date of Award
Goodwin, Dr. Scott
CC BY-NC-ND 4.0
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.
Renukamurthy, Sanjay, "Improving Spatially Distributed Multiagent Pathfinding Using Cooperative JPS" (2016). Electronic Theses and Dissertations. 5663.