Improving Domain-Independent Heuristic State-Space Planning via plan cost predictions

Francesco Percassi, Alfonso Emilio Gerevini, Enrico Scala, Ivan Serina, Mauro Vallati

Research output: Contribution to journalArticlepeer-review


Automated planning is a prominent Artificial Intelligence (AI) challenge that has been extensively studied for decades, which has led to the development of powerful domain-independent planning systems. The performance of domain-independent planning systems are strongly affected by the structure of the search space, that is dependent on the application domain and on its encoding.

This paper proposes and investigates a novel way of combining machine learning and heuristic search to improve domain-independent planning. On the learning side, we use learning to predict the plan cost of a good solution for a given instance. On the planning side, we propose a bound-sensitive heuristic function that exploits such a prediction in a state-space planner. Our function combines the input prediction (derived inductively) with some pieces of information gathered during search (derived deductively). As the prediction can sometimes be grossly inaccurate, the function also provides means to recognise when the provided information is actually misguiding the search. Our experimental analysis demonstrates the usefulness of the proposed approach in a standard heuristic best-first search schema.
Original languageEnglish
Pages (from-to)849-875
Number of pages27
JournalJournal of Experimental and Theoretical Artificial Intelligence
Issue number6
Early online date31 Oct 2021
Publication statusPublished - 1 Nov 2023


Dive into the research topics of 'Improving Domain-Independent Heuristic State-Space Planning via plan cost predictions'. Together they form a unique fingerprint.

Cite this