Interleaving search and heuristic improvement

Santiago Franco, Álvaro Torralba

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

1 Citation (Scopus)


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
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


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


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


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

Cite this