Next: Protecting links
Up: Omnipotence Without Omniscience: Efficient
Previous: LCW Updates
In this section we explain how XII utilizes LCW to satisfy universally
quantified goals. Traditionally, planners that have dealt with goals of
the form ``Forall 
of type t make 
true'' have done so
by expanding the goal into a universally-ground, conjunctive goal called
the universal base. The universal base of
such a sentence equals the
conjunction 
in which the
s correspond to each possible interpretation of under
the universe of discourse, 
, i.e. the possible
objects of type t [][p. 10]genesereth-text. In each
, all references to have been replaced with the constant
. For example, suppose that pf denotes the type corresponding to the files in the
directory /papers and that there are two such files: 
and 
. Then the universal base of ``Forall 
of type pf make printed() true'' is printed(a.dvi)
printed(b.dvi).
A classical planner can satisfy 
goals by subgoaling to
achieve the universal base, but this strategy relies on the closed
world assumption. Only by assuming that all members of the universe
of discourse are known (i.e., represented in the model) can one be
confident that the universal base is equivalent to the goal.
Since the presence of incomplete information invalidates the closed
world assumption, the XII planner uses two new mechanisms for
satisfying goals:
- Sometimes it is possible to directly support a goal with a
effect, without expanding the universal base. For example, given
the goal of having all files in a directory group readable, XII can
simply execute chmod g+r *; it doesn't need to know which files (if
any) are in the directory. Section 3.1 elaborates this option.
-
Alternatively, XII can subgoal
on obtaining LCW on the type
of each universal variable 
in the goal. Once XII
has LCW(
), the universe of discourse for is completely
represented in its world model. At this point XII generates the
universal base and subgoals on achieving it. Note that this strategy
differs from the classical case since it involves interleaved planning
and execution. Given the goal of printing all files in /papers,
would plan and execute an ls command, then plan to print each
file it found, and then execute that plan. Section 3.2 describes
this option in detail.
For completeness, XII also considers combinations of these mechanisms to
solve a single goal; see [8] for
details.
In the remainder of this section we explain these two
techniques in more detail.
Next: Protecting links
Up: Omnipotence Without Omniscience: Efficient
Previous: LCW Updates