Site Search
Computer Science


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

Performance Evaluation of Competing Data Structures in Pathfinding

Add this event into your calendar using the iCAL format
  • Mon, 06/04/2018 - 11:00am - 1:00pm

Performance Evaluation of Competing Data Structures in Pathfinding

MSc Thesis Proposal by:

Mohsen Tavakoli

Date:  Monday, June 4th, 2018
Time:  11: 00 am – 1:00 pm
Location: 3105, Lambton Tower

Abstract: Pathfinding is an essential part of many applications, including video games and robot navigation. A pathfinding algorithm usually finds a path from the given starting point to the endpoint. One of the most well known and used of these algorithms is A*.

The classic A* algorithm can guarantee the minimum weight path to the desired destination which was introduced in 1968 by Hart, Nilsson, and Raphael. A* is widely used in the game industry to solve the shortest path problem. The A* algorithm utilizes two data structures to maintain its function. A* explores the nodes in the graph from the start position one by one and assigns them a value of “F” which is the sum of G cost and H cost.

The G cost is the actual cost of exploring the node from the starting position to the current node and the H cost is the estimate of the cost of from the current node to the goal node. The Open List will keep all of the nodes which are not explored at each iteration of the algorithm. In each iteration, the algorithm will remove the node with the least value of F cost. If the node is not the goal, then it will be added to the closed list. Interactions with the open list which are insert (current node) and remove Min are the costliest part of the algorithm. It is well known that using a priority queue will increase the performance of this algorithm. A number of priority queues have been used to implement A* and improve the performance of this algorithm. We propose to use a two-level binary heap, which initially was introduced for Dijkstra’s algorithm, and we will evaluate its performance. We expect it will outperform other binary heaps due to the decreased size of current open list.

Thesis Committee:
Internal Reader: Dr. Mehdi Kargar
External Reader: Dr. Myron Hlynka
Advisor: Dr. Scott Goodwin

See More: