Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems
- URL: http://arxiv.org/abs/2504.15668v1
- Date: Tue, 22 Apr 2025 07:45:30 GMT
- Title: Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems
- Authors: Mir Md Sajid Sarwar, Rajarshi Ray,
- Abstract summary: Explaining unsolvability of planning problems is of significant research interest in Explainable AI Planning.<n>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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Explaining unsolvability of planning problems is of significant research interest in Explainable AI Planning. AI planning literature has reported several research efforts on generating explanations of solutions to planning problems. 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.
Related papers
- Introduction to AI Planning [0.0]
The notes begin by introducing the state model and move on to exploring classical planning.<n>The most extensive section is dedicated to Hierarchical Task Network (HTN) planning.<n>The lecture notes end with a bonus chapter on the Planning Domain Definition (PDDL) Language.
arXiv Detail & Related papers (2024-12-16T10:38:04Z) - Unified Task and Motion Planning using Object-centric Abstractions of
Motion Constraints [56.283944756315066]
We propose an alternative TAMP approach that unifies task and motion planning into a single search.
Our approach is based on an object-centric abstraction of motion constraints that permits leveraging the computational efficiency of off-the-shelf AI search to yield physically feasible plans.
arXiv Detail & Related papers (2023-12-29T14:00:20Z) - Automated Process Planning Based on a Semantic Capability Model and SMT [50.76251195257306]
In research of manufacturing systems and autonomous robots, the term capability is used for a machine-interpretable specification of a system function.
We present an approach that combines these two topics: starting from a semantic capability model, an AI planning problem is automatically generated.
arXiv Detail & Related papers (2023-12-14T10:37:34Z) - What Planning Problems Can A Relational Neural Network Solve? [91.53684831950612]
We present a circuit complexity analysis for relational neural networks representing policies for planning problems.
We show that there are three general classes of planning problems, in terms of the growth of circuit width and depth.
We also illustrate the utility of this analysis for designing neural networks for policy learning.
arXiv Detail & Related papers (2023-12-06T18:47:28Z) - Planning as In-Painting: A Diffusion-Based Embodied Task Planning
Framework for Environments under Uncertainty [56.30846158280031]
Task planning for embodied AI has been one of the most challenging problems.
We propose a task-agnostic method named 'planning as in-painting'
The proposed framework achieves promising performances in various embodied AI tasks.
arXiv Detail & Related papers (2023-12-02T10:07:17Z) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models.
TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one.
TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
arXiv Detail & Related papers (2023-10-06T01:40:09Z) - A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist
Scheduling Problems [11.66506213335498]
Hoist scheduling has become a bottleneck in electroplating industry applications with the development of autonomous devices.
We formulate the hoist scheduling problem as a new temporal planning problem in the form of adapted PDDL.
We provide a collection of real-life benchmark instances that can be used to evaluate solution methods for the problem.
arXiv Detail & Related papers (2022-12-11T05:30:44Z) - Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion
Planning [36.300564378022315]
We present a learning-enabled Task and Motion Planning (TAMP) algorithm for solving mobile manipulation problems in environments with many articulated and movable obstacles.
The core of our algorithm is PIGINet, a novel Transformer-based learning method that takes in a task plan, the goal, and the initial state, and predicts the probability of finding motion trajectories associated with the task plan.
arXiv Detail & Related papers (2022-11-03T04:12:04Z) - Temporal Planning with Incomplete Knowledge and Perceptual Information [0.0]
This paper presents a new planning approach that combines contingent plan construction within a temporal planning framework.
We propose a small extension to the Planning Domain Definition Language (PDDL) to model incomplete, (ii) knowledge sensing actions.
We also introduce a new set of planning domains to evaluate our solver, which has shown good performance on a variety of problems.
arXiv Detail & Related papers (2022-07-20T07:26:08Z) - Anytime Stochastic Task and Motion Policies [12.72186877599064]
We present a new approach for integrated task and motion planning in settings.
Our algorithm is probabilistically complete and can compute feasible solution policies in an anytime fashion.
arXiv Detail & Related papers (2021-08-28T00:23:39Z) - Multiple Plans are Better than One: Diverse Stochastic Planning [26.887796946596243]
In planning problems, it is often challenging to fully model the desired specifications.
In particular, in human-robot interaction, such difficulty may arise due to human's preferences that are either private or complex to model.
We formulate a problem, called diverse planning, that aims to generate a set of representative behaviors that are near-optimal.
arXiv Detail & Related papers (2020-12-31T07:29:11Z) - Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
We consider alternatives to an implicit sequential planning assumption.
We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan.
We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
arXiv Detail & Related papers (2020-04-23T18:08:58Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.