Expected Path Degradation when Searching over a Sparse Grid Hierarchy

TitleExpected Path Degradation when Searching over a Sparse Grid Hierarchy
Publication TypeConference Paper
Year of Publication2015
AuthorsKolchmeyer, R, Dobson, A, Bekris, KE
Conference NameSymposium on Combinatorial Search (SoCS)
Date Published06/2015
Conference LocationEin Gedi, Dead Sea, Israel

A traditional direction for more efficient grid-based pathfinding
is to speed up the search algorithm. An alternative, however, is to
create a sparser grid representation, which can also significantly
speed up searching for a path. This direction is related to the idea
of spanners from graph theory. These are subgraphs that allow the
computation of paths between any two vertices of the original graph
while guaranteeing a maximum stretch in path length. In practice, the
path degradation of graph spanners is significantly smaller than the
theoretical bound; even so, expected path degradation of graph
spanners is typically not studied. This work is inspired by this
observation and focuses on grid path-finding to propose an algorithm
that constructs a grid spanner. Theoretical analysis for the obstacle
free case shows that significant performance gains can be achieved
with a small decrease in expected path quality. This is an important
first step towards studying the expected performance of
spanners. Experiments on game maps show that expected path quality
with obstacles is only sometimes marginally lower than that in the
obstacle-free case and that a significant reduction in the size of the
search space can be achieved.