Wednesday, January 22, 2020 - 15:00 to 17:00
SCHOOL OF COMPUTER SCIENCE
The School of Computer Science is pleased to present…
MSc Thesis Defense by: Shrijan Karmacharya
Date: Wednesday January 22, 2020
Time: 3:00PM – 5:00 PM
Location: LT 3105
Abstract:
Pathfinding is an essential part of navigation systems, often used in video games, route planning and robotic navigation. A* search has been one of the most well-known and frequently used algorithms for pathfinding. A* uses an and a to keep track of all nodes generated and expanded. The size and performance of these data structures are major drawbacks of A*. Lookahead is used to investigate future outcomes and improve the quality of available choices. Lookaheads are done on a DFS manner from the frontier of A* search. This combination of A* and DFS lookahead has been shown to save space when working with puzzles. We leverage this concept with grid-based pathfinding in video games to save the amount of space consumed. However, because grids contain redundant paths, the DFS lookaheads end up being an overhead as they do not maintain a list of nodes visited or expanded. By using a domain-specific pruning technique, we significantly improve the time taken by the algorithm and further improve upon the space consumed. A combination of lookahead and A* search with this pruning technique is, therefore, able to achieve improvement in both space-consumed and time-taken over the standard A* search algorithm for grid-based pathfinding.
Thesis Committee:
Internal Reader: Dr. Sherif Saad Ahmed
External Reader: Dr. Myron Hlynka
Advisor: Dr. Scott Goodwin
Chair: TBA
MSc Thesis Defense Announcement
5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca