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

ABSTRACT

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.

KEYWORDS:

• Automated planning
• plan cost prediction
• heuristic search
• classical planning

Acknowledgments

We thank the anonymous reviewers for their useful comments. This work was supported by MIUR “Fondo Dipartimenti di Eccellenza 2018-2022” of the DII Department at the University of Brescia. Mauro Vallati was supported by a UKRI Future Leaders Fellowship [grant number MR/T041196/1].

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 The grounding of a planning task is a transformation of all operators in a set of action instances, one for each possible instantiate of its parameters. Powerful techniques to do this automatically and in a way to focus only on actually reachable actions is described by Helmert (2003).

2 This can be downloaded from the http://planning.domains/ website

3 The actual predicted costs and the model parameterisation can be found at https://bitbucket.org/maurovallati/icaps-2020/

Additional information

Funding

This work was supported by the UK Research and Innovation [MR/T041196/1]. Alfonso E. Gerevini, Enrico Scala and Ivan Serina have been supported by AIPlan4EU, a project funded by EU Horizon 2020 research and innovation programme under GA n. 101016442.