MSc Thesis Defense Announcement by Sheeba Mohanraj: "Performance of Buckets versus Min-Heap in A* Search Algorithm"

Tuesday, September 17, 2019 - 12:30 to 14:30

SCHOOL OF COMPUTER SCIENCE

 

  The School of Computer Science at the University of Windsor is pleased to present …

 

MSc Thesis Defense by:

Sheeba Mohanraj
 
Date:  Tuesday, September 17, 2019
Time:  12:30 pm – 2:30 pm
Location: 3105, Lambton Tower

 

Abstract: 

Pathfinding is the search for the least cost route between two points on a map. Given a map with a start node and a goal node, the pathfinding algorithm begins from the start node and searches through the map exploring its neighbours until it finds a path to the goal node. A* is the most popular pathfinding algorithm which uses heuristics for finding the least cost path from the start node to the goal node. The A* algorithm uses two parameters g cost(the actual cost of reaching the current node from the start node) and the h cost(the estimated cost of reaching the goal node from the current node). F cost is the sum of the g cost and the h cost. At each iteration, the A* algorithm chooses the node with the lowest f cost from the open list to be expanded. This node will be removed from the open list and added to the closed list. This process is repeated until reaching the final node. The A* algorithm for pathfinding is affected by its data structures, particularly by the frequent insertions and deletions in the open list. Min-Heap is the commonly used data structure for implementing the open list for A* algorithm, which takes O(log n) for insertion and deletion. Since this is very expensive, we explored the idea of implementing the open list with Buckets, which was initially introduced for improving the performance of Dijkstra's algorithm. We found that the bucket data structure produces better results as it takes O(1) for inserting a node into the open list and O(bucketsize) for deletion. We compared the performance of both the algorithm under various factors to determine which was performing better.

 

Thesis Committee:

Internal Reader:   Dr. Yuan
External Reader:  Dr. Myron Hlynka
Advisor:                Dr. Goodwin
Chair: Dr.              TBD
 

Thesis Defense Announcement

 
5113 Lambton Tower, 401 Sunset Avenue, Windsor ON, N9B 3P4, (519)253-3000 Ext. 3716 csgradinfo@uwindsor.ca
(519)253-3000