Why Can’t You Do That HAL? Explaining Unsolvability of Planning Tasks

Why Can’t You Do That HAL? Explaining Unsolvability of Planning Tasks

Sarath Sreedharan, Siddharth Srivastava, David Smith, Subbarao Kambhampati

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1422-1430. https://doi.org/10.24963/ijcai.2019/197

Explainable planning is widely accepted as a prerequisite for autonomous agents to successfully work with humans. While there has been a lot of research on generating explanations of solutions to planning problems, explaining the absence of solutions remains an open and under-studied problem, even though such situations can be the hardest to understand or debug. In this paper, we show that hierarchical abstractions can be used to efficiently generate reasons for unsolvability of planning problems. In contrast to related work on computing certificates of unsolvability, we show that these methods can generate compact, human-understandable reasons for unsolvability. Empirical analysis and user studies show the validity of our methods  as well as their computational efficacy on a number of benchmark planning domains.
Keywords:
Humans and AI: Human-AI Collaboration
Agent-based and Multi-agent Systems: Human-Agent Interaction