Inductive Certificates of Unsolvability for Domain-Independent Planning
Abstract
If a planning system outputs a solution for a given problem, it is simple to verify that the solution is valid. However, if a planner claims that a task is unsolvable, we currently have no choice but to trust the planner blindly. We propose a sound and complete class of certificates of unsolvability which can be verified efficiently by an independent program. To highlight their practical use, we show how these certificates can be generated for a wide range of state-of-the-art planning techniques with only polynomial overhead for the planner.
Cite
Text
Eriksson et al. "Inductive Certificates of Unsolvability for Domain-Independent Planning." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/730Markdown
[Eriksson et al. "Inductive Certificates of Unsolvability for Domain-Independent Planning." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/eriksson2018ijcai-inductive/) doi:10.24963/IJCAI.2018/730BibTeX
@inproceedings{eriksson2018ijcai-inductive,
title = {{Inductive Certificates of Unsolvability for Domain-Independent Planning}},
author = {Eriksson, Salomé and Röger, Gabriele and Helmert, Malte},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {5244-5248},
doi = {10.24963/IJCAI.2018/730},
url = {https://mlanthology.org/ijcai/2018/eriksson2018ijcai-inductive/}
}