Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems CCS: Computing methodologies Artificial intelligence CCS: Human-centered computing Interactive systems and tools CCS: Theory of computation Timed and hybrid models

Mir Md Sajid Sarwar, Rajarshi Ray · 2025

Read Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems CCS: Computing methodologies Artificial intelligence CCS: Human-centered computing Interactive systems and tools CCS: Theory of computation Timed and hybrid models by Mir Md Sajid Sarwar, Rajarshi Ray (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15668.txt.

Introduction

Mir Md Sajid Sarwar and Rajarshi Ray tackled in 2025 how to explain why a planning problem has no solution. Explaining failed plans is an open problem in explainable AI planning, where most work explains successful plans instead. Their idea borrows the trick of splitting a task into sub-problems that lead toward the goal.

They define waypoints that every would-be plan must pass through, so an unreachable waypoint explains the failure. Finding these waypoints is cast as a longest common subsequence problem, a classic in computing. They then check which waypoint fails first using symbolic reachability. Tests on unsolvable problems in hybrid domains show the approach can produce clear explanations.

Catalog record

CREATORMir Md Sajid Sarwar, Rajarshi Ray
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15668

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems CCS: Computing methodologies Artificial intelligence CCS: Human-centered computing Interactive systems and tools CCS: Theory of computation Timed and hybrid models Mir Md Sajid Sarwar, Rajarshi Ray Abstract . Explaining unsolvability of planning problems is of significant research interest in Explainable AI Planning. A number of research efforts on generating explanations of solutions to planning problems have been reported in AI planning literature. However, explaining the unsolvability of planning problems remains a largely open and understudied problem. A widely practiced approach to plan generation and automated problem solving, in general, is to decompose tasks into sub-problems that help progressively converge towards the goal. In this paper, we propose to adopt the same philosophy of sub-problem identification as a mechanism for analyzing and explaining unsolvability of planning problems in hybrid systems. In particular, for a given unsolvable planning problem, we propose to identify common waypoints, which are universal obstacles to plan existence, in other words, they appear on every plan from the source to the planning goal. This work envisions such waypoints as sub-problems of the planning problem and the unreachability of any of these waypoints as an explanation for the unsolvability of the original planning problem. We propose a novel method of waypoint identification by casting the problem as an instance of the longest common subsequence problem, a widely popular problem in computer science, typically considered as an illustrative example for the dynamic programming paradigm. Once the waypoints are identified, we perform symbolic reachability analysis on them to identify the earliest unreachable waypoint and report it as the explanation of unsolvability. We present experimental results on unsolvable planning problems in hybrid domains. 1. Introduction In human-computer interaction (HCI), humans engage in trustworthy collaborations with autonomous agents, and one of the precursors of such collaborations is that an autonomous agent must explain the rationale behind its decision to the human. With the emergence of artificial intelligence (AI) and the multitude of application domains where AI planning is being envisioned to replace plans generated by humans, Explainable AI Planning (XAIP) ( DBLP:journals/corr/abs-1709-10256 ; DBLP:conf/rweb/HoffmannM19 ) has emerged as an important connection between HCI and AI for designing explainable systems that bridges the gap between theoretical and algorithmic planning and real-world applications ( ijcai2020p669 ) . While there has been a lot of research on generating explanations to planning problems, most of the earlier works in explanation generation have focused on explaining why a given plan or action was chosen ( DBLP:conf/ijcai/ChakrabortiSZK17 ; DBLP:conf/aips/ChakrabortiKSSK19 ; DBLP:journals/jair/KrarupKMLC021 ; DBLP:journals/tecs/SarwarRB23 ) . However, explaining the unsolvability of a given planning problem remains a largely open and understudied problem. The recent works that focus on explaining the unsolvability of planning problems have primarily concentrated on generating certificates or proofs of unsolvability ( DBLP:conf/aips/ErikssonRH17 ; DBLP:conf/aips/ErikssonRH18 ) , or on identifying counterfactual alterations to the original planning task to make it solvable, often referred to as “excuses” ( DBLP:conf/aips/GobelbeckerKEBN10 ) . These approaches, which are more oriented towards automatic verification, may fall short in adequately explaining unsolvability in complex planning domains. A well-known insight into human thinking and problem-solving is that humans tend to decompose a problem into sub-problems that help in progressively converging towards the goal. Many AI systems mimic this notion in the way they solve problems. For instance, the main feature of the pioneering automated theorem prover, logic theorist , is the use of problem-subproblem hierarchy ( LT-1956 ) . An innovative technique for identification of sub-problems relevant for explaining unsolvability of a planning problem in domains with discrete dynamics has been proposed in ( DBLP:conf/ijcai/SreedharanSSK19 ) . In this paper, we propose to adopt the same philosophy of sub-problem identification as an efficient mechanism for analyzing and explaining unsolvability of planning problems in hybrid domains, domains with a combination of discrete and continuous dynamics. In particular, for a given unsolvable planning problem, we propose to identify a sequence of waypoints, which are universal obstacles to plan existence, in other words, they appear on every path on every plan from the source to the planning goal. This work envisions such waypoints as sub-problems of the planning problem and the unreachability of any of these waypoints as an explanation for the unsolvability of the original problem at hand. We propose a novel method of waypoint identification by casting the problem as an instance of the longest common subsequence problem, a widely popular problem in computer science, typically considered as an illustrative example for the dynamic programming paradigm. Once the waypoints are identified, we perform symbolic reachability analysis on them to identify the earliest unreachable waypoint and report it as the explanation of unsolvability. We present experimental results on unsolvable planning problems in hybrid domains. In summary, the key contributions of this paper are: (a) A proposal for an artifact for explaining unsolvability of hybrid planning problem based on the identification of inevitable waypoints. (b) A method to generate the explanation artifact by casting it as an instance of the longest common subsequence problem, and subsequently using symbolic reachability analysis on the hybrid automaton. The rest of this paper is organized as follows. In Section 2 , we present a motivating example to demonstrate this work. Section 3 provides a background and problem overview. Section 4 illustrates our methodology and the framework of explanation. Section 5 discusses implementation and results. Section 6 presents related literature. Finally, Section 7 summarizes the contributions and the findings of this work and discusses possible future directions. 2. Motivating Example In this section, we present a motivating example in the context of a planning problem for a planetary rover that explores a planetary site and collects samples for experiments. The agent (autonomous battery powered rover) possesses knowledge about the topography of the exploration site as a planar grid. Figure 1 shows the topography as a 5 \times 5 grid of cells. The rover is initially positioned at cell 11 and there is a base-station at cell 25. The task of the rover is to collect soil and rock samples from designated sites, in cells 1 and 14 respectively and then reach the base-station. Mountainous regions and craters in the terrain are marked as impassable (cells 7, 12, etc). There are inclined areas in the terrain shown in Orange cells. The motion dynamics of the rover is interpreted as a hybrid system. The rover’s continuous motion and battery discharge dynamics can be different in each cell. For instance, the motion and battery depletion dynamics in an inclined region is different from the dynamics in flat-regions and regions where soil and rock samples are collected. When a rover makes a transition from one cell to another, it starts to follow the dynamics of the new cell instantaneously. The discrete dynamics here capture the connectivity of the cells in the presence of mountains and craters where the rover cannot move. The rover’s movement is restricted to one of its adjacent cells and movement to diagonal cells is prohibited. Figure 1 . Rover-domain is depicted. Initially, the rover is at cell 11. Mountains and craters are impassable regions of the terrain such as cells 7, 12, etc. The rover needs to collect soil samples from cell

Read the complete text