Interleaving search and heuristic improvement

Santiago Franco, Álvaro Torralba

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)

Abstract

Abstraction heuristics are a leading approach for deriving admissible estimates in cost-optimal planning. However, a drawback with respect to other families of heuristics is that they require a preprocessing phase for choosing the abstraction, computing the abstract distances, and/or suitable cost-partitionings. Typically, this is performed in advance by a fixed amount of time, even though some instances could be solved much faster with little or no preprocessing. We interleave the computation of abstraction heuristics with search, avoiding a long precomputation phase and allowing information from the search to be used for guiding the abstraction selection. To evaluate our ideas, we implement them on a planner that uses a single symbolic PDB. Our results show that delaying the preprocessing is not harmful in general even when an important amount of preprocessing is required to obtain good performance.

Original languageEnglish
Title of host publicationProceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019
EditorsPavel Surynek, William Yeoh
Number of pages5
PublisherAAAI Press
Publication date2019
Pages130-134
ISBN (Electronic)9781577358084
Publication statusPublished - 2019
Externally publishedYes
Event12th International Symposium on Combinatorial Search, SoCS 2019 - Napa, United States
Duration: 16 Jul 201917 Jul 2019

Conference

Conference12th International Symposium on Combinatorial Search, SoCS 2019
Country/TerritoryUnited States
CityNapa
Period16/07/201917/07/2019
SeriesProceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019

Keywords

  • Artificial Intelligence (AI)
  • Planning and scheduling
  • Heuristic search

Fingerprint

Dive into the research topics of 'Interleaving search and heuristic improvement'. Together they form a unique fingerprint.

Cite this