Assumption-Based Planning: Generating Plans and Explanations under Incomplete Knowledge

Abstract

Many practical planning problems necessitate the generationof a plan under incomplete information about the state of theworld. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which at-tempts to find a plan under all possible completions of theinitial state, an assumption-based plan supports the assertionof additional assumptions about the state of the world, oftenresulting in high quality plans where no conformant plan ex-ists. We are interested in this paradigm of planning for tworeasons: 1) it captures a compelling form of commonsenseplanning, and 2) it is of great utility in the generation of expla-nations, diagnoses, and counter-examples – tasks which sharea computational core with planning. We formalize the notionof assumption-based planning, establishing a relationship be-tween assumption-based and conformant planning, and proveproperties of such plans. We further provide for the scenariowhere some assumptions are more preferred than others. Ex-ploiting the correspondence with conformant planning, wepropose a means of computing assumption-based plans viaa translation to classical planning. Our translation is an ex-tension of the popular approach proposed by Palacios andGeffner and realized in their T0 planner. We have imple-mented our planner, A0, as a variant of T0 and tested it on anumber of expository domains drawn from the InternationalPlanning Competition. Our results illustrate the utility of thisnew planning paradigm.