The University of Windsor has moved to an “essential service only” model. Learn More.

MSc Thesis Defense Announcement by Shrijan Karmacharya:"Improving Lookahead search for grid-based pathfinding"

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