Font Size:

A Suboptimality Bound for 2

^{k}Grid Path PlanningLast modified: 2018-07-02

#### Abstract

The 2

^{k}neighborhood has been recently proposed as an alternative to optimal any-angle path planning over grids. Even though it has been observed empirically that the quality of solutions approaches the cost of an optimal any-angle path as*k*is increased, no theoretical bounds were known. In this paper we study the ratio between the solutions obtained by an any-angle path and the optimal path in the 2^{k}k, that generalizes previously known bounds for the 4- and 8-connected grids. We analyze two cases: when vertices of the search graph are placed (1) at the corners of grid cells, and (2) when they are located at their centers. For case (1) we obtain a suboptimality bound of 1 + 1/8*k*^{2}+*O*(1/*k*^{3}), which is tight; for (2), however, worst-case suboptimality is a fixed value, for every*k*≤ 3. Our results strongly suggests that vertices need to be placed in corners in order to obtain near-optimal solutions. In an empirical analysis, we compare theoretical and experimental suboptimality.
Full Text:
PDF