A Suboptimality Bound for 2kGrid Path Planning

Benjamin Kramm, Nicolas Rivera, Carlos Hernandez, Jorge A. Baier

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 11th International Symposium on Combinatorial Search, SoCS 2018
EditorsVadim Bulitko, Sabine Storandt
PublisherAAAI press
Pages63-71
Number of pages9
ISBN (Electronic)9781577358022
Publication statusPublished - 2018
Event11th International Symposium on Combinatorial Search, SoCS 2018 - Stockholm, Sweden
Duration: 14 Jul 201815 Jul 2018

Publication series

NameProceedings of the 11th International Symposium on Combinatorial Search, SoCS 2018

Conference

Conference11th International Symposium on Combinatorial Search, SoCS 2018
Country/TerritorySweden
CityStockholm
Period14/07/1815/07/18

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'A Suboptimality Bound for 2<sup>k</sup>Grid Path Planning'. Together they form a unique fingerprint.

Cite this