Critically Constrained Planning via Partial Delete Relaxation

通过部分删除松弛进行严格约束规划

• 批准号: 252282745
• 负责人: Professor Dr. Jörg Hoffmann
• 金额: --
• 依托单位: Lehrstuhl für Grundlagen der Künstlichen Intelligenz
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2018-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/252282745?language=en
• 关键词: Critically; Constrained; Planning; via; Partial

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.

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