Critically Constrained Planning via Partial Delete Relaxation

• Applicant: Professor Dr. Jörg Hoffmann
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2014 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 252282745

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.

• DFG Programme: Research Grants