# Synthesizing Robust Plans Under Incomplete Domain Models

Tuan A. Nguyen ∗and **Subbarao Kambhampati** ∗and **Minh B. Do** †
* Dept. of Computer Science & Engineering, Arizona State University. Email: {natuan,rao}@asu.edu
† Embedded Reasoning Area, Palo Alto Research Center. Email: minh.do@parc.com

## Abstract

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task.

While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In such cases, the goal should be to generate plans that are robust with respect to any known incompleteness of the domain. In this paper, we first introduce annotations expressing the knowledge of the domain incompleteness, and formalize the notion of plan robustness with respect to an incomplete domain model. We then propose an approach to compiling the problem of finding robust plans to the conformant probabilistic planning problem. We present experimental results with Probabilistic-FF, a state-ofthe-art planner, showing the promise of our approach.

## 1. Introduction

Lesh (2002), we shall assume that although the domain modelers cannot provide complete models, often they are able to provide annotations on the partial model circumscribing the places where it is incomplete. In our framework, these annotations consist of allowing actions to have *possible* preconditions and effects (in addition to the standard necessary preconditions and effects).

As an example, consider a variation of the *Gripper* domain, a well-known planning benchmark domain. The robot has one gripper that can be used to pick up balls, which are of two types light and heavy, from one room and move them to another room. The modeler suspects that the gripper may have an internal problem, but this cannot be confirmed until the robot actually executes the plan. If it actually has the problem, the execution of the *pick-up* action succeeds only with balls that are not heavy, but if it has no problem, it can always pickup all types of balls. The modeler can express this partial knowledge about the domain by annotating the action with a statement representing the possible precondition that balls should be light.

Incomplete domain models with such possible preconditions/effects implicitly define an exponential set of complete domain models, with the semantics that the real domain model is guaranteed to be one of these. The robustness of a plan can now be formalized in terms of the cumulative probability mass of the complete domain models under which it succeeds. We propose an approach that compiles the problem of finding robust plans into the conformant probabilistic planning problem. We present experimental results showing scenarios where the approach works well, and also discuss aspects of the compilation that cause scalability issues.

In the past several years, significant strides have been made in scaling up plan synthesis techniques. We now have technology to routinely generate plans with hundreds of actions. All this work, however, makes a crucial assumption–that a complete model of the domain is specified in advance. While there are domains where knowledge-engineering such detailed models is necessary and feasible (e.g., mission planning domains in NASA and factory-floor planning), it is increasingly recognized (c.f. (Hoffmann, Weber, and Kraft 2010; Kambhampati 2007)) that there are also many scenarios where insistence on correct and complete models renders the current planning technology unusable. What we need to handle such cases is a planning technology that can get by with partially specified domain models, and yet generate plans that are "robust" in the sense that they are likely to execute successfully in the real world.

This paper addresses the problem of formalizing the notion of plan robustness with respect to an incomplete domain model, and connects the problem of generating a robust plan under such model to *conformant probabilistic planning* (Kushmerick, Hanks, and Weld 1995; Hyafil and Bacchus 2003; Bryce, Kambhampati, and Smith 2006; Domshlak and Hoffmann 2007). Following Garland &
2. Related Work Although there has been some work on reducing the "faults" in plan execution (e.g. the work on *k-fault* plans for nondeterministic planning (Jensen, Veloso, and Bryant 2004)),
it is based in the context of stochastic/non-deterministic actions rather than incompletely specified ones. The semantics of the possible preconditions/effects in our incomplete domain models differ fundamentally from non-deterministic and stochastic effects. Executing different instances of the same pick-up action in the *Gripper* example above would either all fail or all succeed, since there is no uncertainty but the information is unknown at the time the model is built. In