The XII Planner

Classical planners presuppose correct and complete information about the world. Although recent work has sketched a number of algorithms for planning with incomplete information, 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 or UCPOP satisfy universally quantified goals by computing the set of ground instances of the goal. But how can a planner compute this set in the absence of complete information? Sometimes it may have to sense which widgets or which files are present before generating its plan.
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.

This paper reports on the fully-implemented XII planner (XII stands for ``eXecution and Incomplete Information'') 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, but XII interleaves planning and execution (following IPEM) and, unlike UCPOP, does not make the closed world assumption. XII uses closed world reasoning to avoid redundant information gathering and to solve universally quantified goals in the presence of incomplete information.

The folks behind XII: Dan Weld, Keith Golden, Oren Etzioni.

A short paper (to appear at AAAI-94) describing XII, (also available in html) and a a more theoretical paper (to appear at KR'94) describing local closed world information, a key contribution of this work.

Back to AI Home Page

Back to CSE Home Page

For more information, send mail to "bug-ucpop@cs.washington.edu".