Critically Constrained Planning via Partial Delete Relaxation

规划是人工智能的基本子领域之一。它的技术允许解决任何可以通过在大型转换系统中寻找路径来建模的问题，并且可以极大地简化问题的解决：编写/维护10行模型代码，而不是1000行程序代码。由于删除-松弛启发式函数带来的显著的可扩展性进步，这一想法在2000年左右实现了工业规模的应用。这些方法通过解决一个忽略行动的负面影响的宽松规划任务，得出目标距离的估计。这种技术的变体今天被广泛使用，无论是在竞争获胜的研究原型中还是在应用中。尽管取得了这样的成功，但“删除-放松”有严重的缺点。计划的许多应用都是受限制的，因为我们需要在限制不受欢迎的副作用（如燃料消耗）的情况下实现目标。删除放松无法解释这一点，因为它假装不会发生任何坏事。在围绕可解性阈值的严格约束问题中，结果是戏剧性的，在这些问题中，所有已知的方法都失败了，计划者求助于穷举搜索。我们的目标是提高这些问题的性能，特别是在先前研究不足的无法解决的方面。为此，我们将采用允许在完全放松的计划（完全没有删除）和不放松的计划（所有删除）之间平滑插入的技术。十多年来，这种部分删除松弛一直是一个研究目标，并最终在导致该项目的两条工作线中实现：连词编译扩展输入任务，明确表示选定的连词子集C。红黑计划只放松状态变量的一个子集。在项目之前，这两种方法都产生了巨大的改进，但只在少数领域；他们在严格约束计划上的行为是有希望的，但不令人满意。该项目旨在充分发挥这些技术的潜力。在第一个资助阶段，我们对连词编译有了更好的理解；在线c学习方法在可解性阈值两侧都非常成功；证明不可解性的红黑规划方法；与概率规划中的死角检测有关。建议的项目更新将：(1)通过变量合并完成对基本方法的研究，以及对红黑规划、痕迹记忆变量松弛的强有力的新概括。（ii）开发以重近似代替启发式函数为模板的稀疏搜索方法，并通过智能混合重轻量级近似来反驳计划存在。（iii）在超额认购计划和目标概率分析方面，发展我们的技术在传统规划之外的应用。

Planning is one of the fundamental sub-areas of AI. Its technology allows to solve any problem that can be modeled in terms of finding paths in large transition systems, and can drastically simplify problem solving: instead of 1000s of lines of program code, one writes/maintains 10s of lines of model code. The industrial-scale use of this idea became realistic around the year 2000, thanks to dramatic scalability advances brought about by delete-relaxation heuristic functions. These derive an estimate of goal distance by solving a relaxed planning task in which the negative effects of actions are ignored. Variants of this technique are in wide-spread use today, both in competition-winning research prototypes and in applications.Despite this success, the delete-relaxation has serious shortcomings. Many applications of planning are constrained in the sense that we need to achieve the goal subject to limiting undesirable side effects, like fuel consumption. The delete relaxation is unable to account for that, as it pretends that nothing bad can ever happen. The consequences are dramatic in critically constrained problems around the solvability threshold, where all known methods fail and planners resort to exhaustive search. Our objective is to improve performance on such problems, especially on the unsolvable side for which there is scant prior research. To this end, we will employ techniques that allow to smoothly interpolate between fully-relaxed planning (no deletes at all) and unrelaxed planning (all deletes).Such partial delete relaxation has been a research aim since more than a decade, and was finally achieved in the two lines of work leading up to this project: Conjuncts compilation extends the input task with an explicit representation of a selected subset C of conjunctions. Red-black planning relaxes only a subset of the state variables. Prior to the project, both methods yielded dramatic improvements, but only in few domains; their behavior on critically constrained planning was promising but unsatisfactory. The project aims at realizing the techniques' full potential. During the first funding phase, we established a better understanding of conjuncts compilation; online C-learning methods highly successful on both sides of the solvability threshold; red-black planning methods for proving unsolvability; and a connection to dead-end detection in probabilistic planning. The proposed project renewal will: (i) Complete the investigation of basic methods through variable merging as well as a powerful new generalization of red-black planning, trace-memory variable relaxation. (ii) Develop sparse search methods using heavy approximations as templates instead of heuristic functions, and refuting plan existence by intelligently mixing heavy and light-weight approximations. (iii) Develop applications of our technology beyond classical planning, in over-subscription planning and goal probability analysis.