CS&E logo University of Washington Computer Science & Engineering
 The XII Planner
  CSE Home   AI Home  About CSE    Search    Contact Info 

Project faculty
 Oren Etzioni
 Dan Weld
Project students
 Keith Golden
   

The XII Planner

Overview

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.

Publications

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.



CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to bug-ucpop at cs.washington.edu]