Date of Award
1-12-2016
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Supervisor
Goodwin, Dr. Scott
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
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.
Recommended Citation
Renukamurthy, Sanjay, "Improving Spatially Distributed Multiagent Pathfinding Using Cooperative JPS" (2016). Electronic Theses and Dissertations. 5663.
https://scholar.uwindsor.ca/etd/5663