TY - GEN

T1 - A Suboptimality Bound for 2kGrid Path Planning

AU - Kramm, Benjamin

AU - Rivera, Nicolas

AU - Hernandez, Carlos

AU - Baier, Jorge A.

N1 - Funding Information:
We acknowledge support from Fondecyt via grants number 1161526.

PY - 2018

Y1 - 2018

N2 - The 2kneighborhood 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 2kneighborhood. We derive a suboptimality bound, as a function of 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/8k2+ O(1/k3), 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.

AB - The 2kneighborhood 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 2kneighborhood. We derive a suboptimality bound, as a function of 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/8k2+ O(1/k3), 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.

UR - http://www.scopus.com/inward/record.url?scp=85078941098&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85078941098

T3 - Proceedings of the 11th International Symposium on Combinatorial Search, SoCS 2018

SP - 63

EP - 71

BT - Proceedings of the 11th International Symposium on Combinatorial Search, SoCS 2018

A2 - Bulitko, Vadim

A2 - Storandt, Sabine

PB - AAAI press

T2 - 11th International Symposium on Combinatorial Search, SoCS 2018

Y2 - 14 July 2018 through 15 July 2018

ER -