找出规划问题中必然经过却无法抵达的障碍点,解释为何问题无解。
Preprint: Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems
- 将无解问题的共同必经点视为子问题,用最长公共子序列法识别
- 通过符号可达性分析定位首个无法到达的必经点,作为无解原因
- 适用于复杂混合系统规划,帮助理解为何任务无法完成
解释规划问题的无解性是可解释人工智能规划中的重要研究方向。尽管已有研究致力于生成可解问题的解释,但无解问题的解释仍属开放且研究不足。现有规划方法通常将任务分解为子问题以逐步逼近目标。本文借鉴此思想,提出通过识别所有可能路径中必然经过的通用障碍点(即必经点)来分析和解释混合系统中规划问题的无解性。这些必经点被视为原问题的子问题,若其中任一点不可达,则可作为原问题无解的解释。本文将该问题建模为最长公共子序列问题,并利用动态规划求解。随后对识别出的必经点进行符号可达性分析,确定最早不可达的点并作为无解原因报告。实验在混合领域中的无解规划问题上验证了方法的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。