arXiv:2504.15668v1 宣布类型: 新 摘要: 在可解释AI规划中，解释规划问题的不可解性是一项重要的研究兴趣。AI规划文献中报道了生成规划问题解的解释的多项研究努力。然而，解释规划问题的不可解性仍然是一个未解决且研究不足的问题。一种广泛采用的计划生成和自动化问题解决方法是将任务分解为有助于逐步接近目标的子问题。在本文中，我们提出采用同样的子问题识别哲学作为分析和解释混合系统中规划问题不可解性的机制。特别是，对于给定的不可解规划问题，我们建议识别常见的关键点，即普遍的障碍，这些障碍阻止计划的存在；换句话说，它们出现在从起点到规划目标的每一条计划路径上。本文设想这些关键点作为规划问题的子问题，而任何这些关键点不可达作为原始规划问题不可解性的解释。我们提出了一种新颖的子点识别方法，将其问题形式化为计算机科学中广泛流行的最长公共子序列问题的一个实例，通常作为动态规划范式的示例问题。一旦识别出关键点，我们对其执行符号可达性分析以找出最早不可达的关键点，并将其报告为不可解性的解释。我们展示了在混合域中不可解规划问题的实验结果。