Proceedings

Learning Generalized Unsolvability Heuristics for Classical Planning

Simon Ståhlberg, Guillem Francès, Jendrik Seipp

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4175-4181.

https://doi.org/10.24963/ijcai.2021/574

Keywords

  • Planning and Scheduling: Planning and Scheduling

Abstract

Recent work in classical planning has introduced dedicated techniques for detecting unsolvable states, i.e., states from which no goal state can be reached. We approach the problem from a generalized planning perspective and learn first-order-like formulas that characterize unsolvability for entire planning domains. We show how to cast the problem as a self-supervised classification task. Our training data is automatically generated and labeled by exhaustive exploration of small instances of each domain, and candidate features are automatically computed from the predicates used to define the domain. We investigate three learning algorithms with different properties and compare them to heuristics from the literature. Our empirical results show that our approach often captures important classes of unsolvable states with high classification accuracy. Additionally, the logical form of our heuristics makes them easy to interpret and reason about, and can be used to show that the characterizations learned in some domains capture exactly all unsolvable states of the domain.

Simon Ståhlberg, Guillem Francès, and Jendrik Seipp. 2021. Learning Generalized Unsolvability Heuristics for Classical Planning. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4175–4181. https://doi.org/10.24963/ijcai.2021/574
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards