Preprint: Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems

Unsolvability explanation is understudied but important: While AI planning research has focused extensively on explaining how to solve problems, explaining why problems cannot be solved remains largely unexplored—a gap this work addresses for responsible AI systems that need to communicate limitations to users.

"Inevitable waypoints" offer intuitive explanations: The paper proposes identifying universal obstacles (waypoints) that must be overcome to reach any goal; when these waypoints are unreachable, they provide clear, human-understandable reasons why a problem cannot be solved, rather than opaque technical failures.

Breaking down complex problems aids understanding: By decomposing unsolvable planning problems into sub-problems and analyzing which waypoints are blocked, the approach makes it easier for non-experts to understand why automated systems fail—supporting transparency in AI decision-making.

Method builds on established computer science techniques: The approach uses longest common subsequence analysis and symbolic reachability analysis, grounding the explanation method in well-understood algorithms rather than novel black-box techniques, which enhances trustworthiness.

Applicable to hybrid systems: The work specifically addresses hybrid planning problems (combining discrete and continuous elements), suggesting the explanation framework could help users understand failures in complex real-world AI systems that operate in mixed environments.