Bounded suboptimal path planning with Compressed Path Databases

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

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


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.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth International Conference on Automated Planning and Scheduling
EditorsJ. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, Shirin Sohrabi
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Electronic)9781577358244
Publication statusPublished - 2020
EventInternational Conference on Automated Planning and Scheduling 2020 - Nancy, France
Duration: 26 Oct 202030 Oct 2020
Conference number: 30th (Proceedings) (Website)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherThe AAAI Press
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843


ConferenceInternational Conference on Automated Planning and Scheduling 2020
Abbreviated titleICAPS 2020
Internet address

Cite this