Site Search
Computer Science


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

Exploiting Problem Structure in Pathfinding

Add this event into your calendar using the iCAL format
  • Wed, 05/09/2018 - 1:30pm - 3:30pm

Exploiting Problem Structure in Pathfinding

MSc Thesis Proposal by:

Qing Cao

Date:  Wednesday, May 9th, 2018
Time:  1: 30 pm – 3:30 pm
Location: 3105, Lambton Tower

Abstract: Pathfinding plays a fundamental role in many fields such as GPS, video games, robotics and crowded simulations and can be implemented in static, dynamic, and real-time environments. With a given map and a start and a goal position on the graph, a pathfinding algorithm usually searches on this graph from the start node and exploring its neighbor nodes until reaching the goal. It often is closely related to the shortest path problem.

A* is one of the best and most popular heuristic-guided algorithms used in pathfinding for video games. The algorithm always picks the node with smallest “f” value and process this node. The “f” value is the sum of two parameters “g” (the actual cost from the start node to the current node) and “h” (estimated cost from the current node to the goal). At each step of the algorithm, the node with lowest “f” will be removed from an open list and its neighbor nodes with their “f” values would be updated in this list. The main cost of this algorithm is the frequent insertion and deleteMin operations of the open list. Typically, implementation of A* uses a priority queue or min-heap to perform the open list, which usually takes O(log n) for the operations. But this is still expensive when using the algorithm in a large and complicated map with lots of nodes. We propose a new data structure called multi-stack heap for the open list based on the 2D grid map and Manhattan distance, which only costs O(1) for insertion and deleteMin. It could be very efficient especially when we have a considerable number of nodes to explore.

Thesis Committee:
Internal Reader: Dr. Mehdi Kargar
External Reader: Dr. James Gauld
Advisor: Dr. Scott Goodwin

See More: