Introduction

Classical planners (e.g., [2]) presuppose correct and complete information about the world. Although recent work has sketched a number of algorithms for planning with incomplete information (e.g., [7][4][15][9][12][1]), substantial problems remain before these planners can be applied to real-world domains. Since the presence of incomplete information invalidates the Closed World Assumption, an agent cannot deduce that a fact is false based on its absence from the agent's world model. This leads to two challenges:

• Satisfying Universally Quantified Goals: Goals of the form ``Move all widgets to the warehouse'' or ``Make all files in /tex write-protected'' are common in real world domains. Classical planners such as PRODIGY [11] or UCPOP [14] reduce universally quantified goals to the set of ground instances of the goal, and satisfy each instance in turn. But how can a planner compute this set in the absence of complete information? How can the planner be certain that it has moved all the widgets or protected all the relevant files?

• Avoiding Redundant Sensing: Should the planner insert a sensory action (e.g., scan with the camera, or the UNIX command ls) into its plan? Or is the action redundant, yielding information already known to the planner? Since satisfying the preconditions of a sensory action can require arbitrary planning, the cost of redundant sensing is potentially unbounded and quite large in practice (see section 5).

This paper reports on the fully-implemented XII planner which addresses these challenges. We allow incomplete information, but assume the information that is known is correct. XII's planning algorithm is based on UCPOP [14], but XII interleaves planning and execution (following IPEM [1]) and, unlike UCPOP, does not make the closed world assumption.

Section 2 introduces the central concept underlying XII's operation: local closed world information (LCW). In section 3 we describe how incorporating LCW in a planner enables it to solve universally quantified goals in the presence of incomplete information. We then (section 4) show how the same mechanism addresses the problem of redundant information gathering. Section 5 gives experimental results which demonstrate the advantages of eliminating redundant sensing. We conclude with a discussion of related and future work.