Site Search
Computer Science


Lambton TowerLambton Tower
Lambton Tower
Arunita Jaekel, Ph.D.Dr. Arunita Jaekel
Dr. Arunita Jaekel
Dr. Luis RuedaDr. Luis Rueda
Dr. Luis Rueda
Alioune Ngom, Ph.D.Dr. Alioune Ngom
Dr. Alioune Ngom
Jessica Chen, Ph.D.Dr. Jessica Chen
Dr. Jessica Chen
Dr. Robert KentDr. Robert Kent
Dr. Robert Kent
Xiaobu Yuan, Ph.D.Dr. Xiaobu Yuan
Dr. Xiaobu Yuan
Dr. Ziad Kobti lecturingDr. Ziad Kobti
Dr. Ziad Kobti
Windsor WaterfrontWindsor Waterfront Park
Windsor Waterfront Park
Imran Ahmad, Ph.D.Dr. Imran Ahmad
Dr. Imran Ahmad
Dr. Scott GoodwinDr. Scott Goodwin
Dr. Scott Goodwin
Robin Gras, Ph.D.Dr. Robin Gras
Dr. Robin Gras
Christie Ezeife, Ph.D.Dr. Christie Ezeife
Dr. Christie Ezeife

Improving Spatially Distributed Multiagent Pathfinding Using Cooperative JPS

Add this event into your calendar using the iCAL format
  • Tue, 01/05/2016 - 10:00am - 12:00pm


MSc Thesis Defense by:

Sanjay Renukamurthy

Date:  Tuesday, January 5, 2016
Time:  10:00 am – 12:00 pm
Location: 3105, Lambton Tower

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. (2014) 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 (2014) algorithm on real video game maps and demonstrate significate improvements in terms of makespan, solution time and failure-rate.

Thesis Committee:
Internal Reader:  Dr. Imran Ahmad  
External Reader: Dr. Myron Hlynka
Advisor:  Dr. Scott Goodwin
Chair:  Dr. Arunita Jaekel

See More: