Back to search

University of Denver

Enhancements to Hierarchical Pathfinding Algorithms

Abstract

dc:description.abstract

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. 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. 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.

Degree

thesis:*
Name thesis:degree_name
M.S.
Level thesis:degree_level
Masters Thesis

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Xin
Contributors dc:contributor
  • Nathan R. Sturtevant, Ph.D.
  • Scott Leutenegger
  • Rafael Fajardo

Subjects

dc:subject × 7

Rights

dc:rights
Statement dc:rights
  • <p>Copyright is held by the author. User is responsible for all copyright compliance.</p>
  • Xin Li
Language dc:language
en

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.du.edu/etd/1209

Chain of custody

source
Harvested from
University of Denver
Base URL
digitalcommons.du.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Li, Xin. Enhancements to Hierarchical Pathfinding Algorithms. Masters Thesis thesis, https://digitalcommons.du.edu/etd/1209