Expected Path Degradation when Searching over a Sparse Grid Hierarchy

Abstract

The traditional focus of combinatorial search research is to speed up the search algorithm. An alternative, however, is to create a sparser representation of the search space. This relates to the idea of spanners from graph theory. These are subgraphs which retain 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 focuses on grid path-finding to propose an algorithm that constructs a grid spanner, where 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.