Expected Path Degradation when Searching over a Sparse Grid Hierarchy
Submitted by bekris on Mon, 04/06/2015  17:02
Title  Expected Path Degradation when Searching over a Sparse Grid Hierarchy 
Publication Type  Conference Paper 
Year of Publication  2015 
Authors  Kolchmeyer, R, Dobson, A, Bekris, KE 
Conference Name  Symposium on Combinatorial Search (SoCS) 
Date Published  06/2015 
Conference Location  Ein Gedi, Dead Sea, Israel 
Abstract  A traditional direction for more efficient gridbased 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 pathfinding 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
obstaclefree case and that a significant reduction in the size of the
search space can be achieved.

URL  http://www.cs.rutgers.edu/~kb572/pubs/Kolchmeyer_SoCS2015_Sparse_Grid.pdf 