Date of Award

1-12-2016

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Goodwin, Dr. Scott

Rights

CC BY-NC-ND 4.0

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.

Share

COinS