Bounded Suboptimal Path Planning with Compressed Path Databases

Shizhe Zhao, Mattia Chiari, Adi Botea, Alfonso E. Gerevini, Daniel Harabor, Alessandro Saetti, Peter J. Stuckey

 PosterID: 74
picture_as_pdf PDF
library_books Slides
library_books Poster
menu_book BibTeX
Compressed Path Databases (CPDs) are a state-of-the-art method for path planning. They record, for each start position, an optimal first move to reach any target position. Computing an optimal path with CPDs is extremely fast and requires no state-space search. The main disadvantages are overhead related: building a CPD usually involves an all- pairs precomputation, and storing the result often incurs prohibitive space overheads. Previous research has focused on reducing the size of CPDs and/or improving their online performance. In this paper, we consider a new type of CPD, which can also dramatically reduce preprocessing times. Our idea involves computing first-move data for only selected target nodes; chosen in such a way as to guarantee that the cost of any extracted path is within a fixed bound of the optimal solution. Empirical results demonstrate that our new bounded suboptimal CPDs improve preprocessing times by orders of magnitude. They further reduce storage costs and compute paths more quickly – all in exchange for only a small amount of suboptimality.

Session Aus4: Path Planning
Canb 10/29/2020, 11:00 – 12:00
10/30/2020, 20:00 – 21:00
Paris 10/29/2020, 01:00 – 02:00
10/30/2020, 10:00 – 11:00
NYC 10/28/2020, 20:00 – 21:00
10/30/2020, 05:00 – 06:00
LA 10/28/2020, 17:00 – 18:00
10/30/2020, 02:00 – 03:00
Contact: icaps20-support (at) googlegroups.com
Copyright ©2020 by ICAPS.