Enhancements to Hierarchical Pathfinding Algorithms

<p>In this thesis we study the problem of pathfinding in static grid-based maps. We apply the approach of abstraction and refinement. We abstract the grid map into a graph representation, and use the classic A* algorithm to search for a path in the abstract space, and then refine it into low-level path.</p> <p>We started with a 2013 entry program to the Grid-based Path Planning Competition, and implemented several enhancements to experiment with the tradeoff between memory usage and search speed. Our program returns the refined low-level path incrementally, therefore reduces the first-move lag in large maps. We cache the low-level edge paths during runtime to avoid repeatedly refining the same abstract edge. In the precomputation step we calculate the low-level paths for all of the edges in the abstraction and directly access the data during online search. We also applied the weighted A* algorithm for online abstract pathfinding and show that the search speed can be further increased by sacrificing path optimality.</p> <p>We ran our program with 132 maps and 1,739,340 queries. Results show that caching edge paths increases the search speed by a factor of 4.20 in comparison to returning the path incrementally but without caching. With precomputation, the search speed increases by a factor of 1.00 in comparison to caching edge paths. We show that online pathfinding speed can be increased by using more memory and/or offline storage.</p>

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters Thesis

Year dc:date.available

2016

Author dc:creator

• Li, Xin

Contributors dc:contributor

• Nathan R. Sturtevant, Ph.D.
• Scott Leutenegger
• Rafael Fajardo

• Abstraction and refinement
• GPPC
• Grid-based path planning competition
• Pathfinding
• Single agent search
• Computer Sciences
• Theory and Algorithms

Statement dc:rights

• <p>Copyright is held by the author. User is responsible for all copyright compliance.</p>

Language dc:language

en

Repository record dc:identifier

https://digitalcommons.du.edu/etd/1209

OAI identifier oai:identifier

oai:digitalcommons.du.edu:etd-2209