Time-Saving Tips for Problem Solving with Incomplete Information
Michael R. Genesereth\cr
Computer Science Department
Stanford University
Stanford CA 94305
Illah R. Nourbakhsh\cr
Computer Science Department
Stanford University
Stanford CA 94305
Abstract:
Problem solving with incomplete information is usually very
costly, since multiple alternatives must be taken into account in the planning
process. In this paper, we present some pruning rules that lead to substantial
cost savings. The rules are all based on the simple idea that, if goal
achievement is the sole criterion for performance, a planner need not consider
one ``branch'' in its search space when there is another ``branch''
characterized by equal or greater information. The idea is worked out for the
cases of sequential planning, conditional planning, and interleaved planning and
execution. The rules are of special value in this last case, as they provide a
way for the problem solver to terminate its search without planning all the way
to the goal and yet be assured that no important alternatives are overlooked.
Content Areas:
Planning, Interleaved Planning and Execution, Robotics
Introduction
In much of the early literature on robot problem solving, the problem solver is
assumed to have complete information about the initial state of the world. In
some cases, the information is provided to the robot by its programmer; in other
cases, the information is obtained through a period of exploration and
observation.
In fact, complete information is rarely available. In some cases, the models
used by our robots are quantitatively inaccurate (leading to errors in position,
velocity, etc.). In some cases, the incompleteness of information is more
qualitative (e.g. the robot does not know the room in which an essential tool is
located). In this paper, we concentrate on problem solving with incomplete
information of the latter sort.
There are, of course, multiple ways to deal with qualitatively incomplete
information. To illustrate some of the alternatives, consider a robot in a
machine shop. The robot's goal is to fabricate a part by boring a hole in a
piece of stock, and it decides to do this by using a drill press. The
complication is that there might or might not be some debris on the drill press
table.
In some cases, it may be possible to formulate a sequential plan that
solves the problem. One possibility is a sequential plan that
covers many states
by using powerful operators with the same effects in those states. In our
example, the robot might intend to use a workpiece fixture that fits into
position whether or not there is debris on the table. Another possibility is a
sequential plan that coerces many states into a single known state.
For example,
the robot could insert into its plan the action of sweeping the table. Whether
or not there is debris, this action will result in a state in which there is no
debris.
A second possibility is for the planner to insert a conditional into the
plan, so that the robot will examine the table before acting, in one case
(debris present) clearing the table, in the other case (table clear) proceeding
without delay.
A more interesting possibility is for the planner to interleave planning
and execution, deferring some planning effort until more information is
available. For example, the robot plans how to get its materials to the drill
press but then suspends further planning until after those steps are executed
and further information about the state of the table is available.
The difficulty with all of these approaches is that, in the absence of any good
pruning rules, the planning cost is extremely high. In the case of deferred
planning, the absence of good termination rules means that the problem solver
must plan all the way to the goal, thus eliminating the principal value of the
approach.
In this paper, we present some powerful pruning rules for planning in the face
of incomplete information. The rules are all based on the simple idea that, if
goal achievement is the sole criterion for performance, a planner need not
consider one ``branch'' in its search space when there is another ``branch''
characterized by equal or greater information.
Fikes introduced interleaved planning
and execution in the limited instance of plan modification during
execution {Fikes 1972}. Rosenschein's work on dynamic logic
formalized conditional planning but paid little attention to
computational aspects {Rosenschein 1981}. More
recent works do provide domain dependent
guidance, but have not uncovered methods that generalize
across domains
{Hsu 1990}, {Olawsky 1990}, {Etzioni 1992}.
In the next section, we give a formal definition for problem
solving. In section 3, we present a traditional approach to problem solving
with complete information. In sections 4-6, we present pruning rules for the
three approaches to problem solving mentioned above. Section 7 offers some
experimental results on the use of our rules. The final section summarizes the
main results of the paper and describes some limitations of this work.
Problem Solving
Our definition of problem solving assumes a division of the world into two
interacting parts -- an agent and its environment. The outputs of the agent
(its actions) are the inputs to the environment, and the outputs of the
environment are the inputs to the agent (its percepts).
Formally, we specify the behavior of our agent as a tuple
{P,B,A,int,ext,b_1}, where P is a set of input objects (the agent's
percepts), B is a set of internal states, A is a set of output
objects (the agent's actions), int is a function from P cross B into B
(the agent's state transition function), ext is a function from P cross B into
A (the agent's action function), and b_1 is a member of B (the agent's initial
internal state).
We characterize the behavior of an agent's environment as a
tuple {A,E,P,see,do,e_1}, where A is a finite set of
actions, E is a set of world states, P is a finite set of distinct
percepts, see is a function that maps each world state into its
corresponding percept, do is a function that maps an action and a state
into the state that results from the application of the given action in the
given state, and e_1 is an initial state of the world.
Note the strong similarity between our characterization of an agent's behavior
and that of its environment. There is only one asymmetry -- the see function
is a function only of the environment's state, whereas the
ext function of an agent is a function of both the percept and the internal
state. (For automata theorists, our agent is a Mealy machine, whereas our
environment is a Moore machine.) This asymmetry is of no real significance and
can, with a little care, be eliminated; it just simplifies the analysis.
The behavior of an agent in its environment is cyclical. At the outset, the
agent has a particular state b_1, and the environment is in a particular state
e_1. The environment presents the agent with a percept p_1 (based on
see), and the agent uses this percept and its internal state to select an
action a_1 to perform (based on the ext function). The agent then updates
its internal state to b_2 (in accordance with int), and the environment
changes to a new state e_2 (in accordance with do). The cycle then repeats.
In what follows, we define a goal to be a set of states of an environment.
We say that an agent achieves a goal G if and only if there is some time
step n on which the environment enters a state in the goal set:
There exists some n such that e_n is a member of G.
In problem solving with complete information, the agent has the advantage of
complete information about the environment and its goal. In problem solving
with incomplete information, some of this information is missing or incomplete.
The pruning rules presented here are fully general and apply equally well in
cases of uncertainty about initial state, percepts, and actions. However, for
the sake of presentational simplicity, we restrict our attention
to uncertainty about the robot's initial state. In our version, the robot's job
is to achieve a goal G, when started in an environment
{A,E,P,see,do,e}, where e is any member of a set of states
I that is a subset of E.
Problem Solving with Complete Information
The traditional approach to problem solving with complete information is
sequential planning and execution. An agent, given a description of an initial
state and a set of goal states, first produces a plan of operation, then
executes that plan.
In single state sequential planning, information about the behavior of
the agent's environment is represented in the form of a state graph, i.e. a
labelled, directed graph in which nodes denote states of the agent's
environment, node labels denote percepts, and arc labels denote actions. There
is an arc (s_1,s_2) in the graph if and only if the action
denoted by the label on the arc transforms the state denoted by s_1 into
the state denoted by s_2. By convention, all labelled arcs that
begin and end at the same state are omitted.
To find a plan, the robot searches the environment's state graph for a path
connecting its single initial state to a goal state. If such a path exists, it
forms a sequential plan from the labels on the arcs along the path.
Obviously, there are many ways to conduct this search --- forward, backward,
bidirectional, depth-first, breadth-first, iterative deepening, etc. If the
search is done in breadth-first fashion or with iterative deepening, the
shortest path will be found first.
As an illustration of this method, consider an application area known as
the Square World. The geography of this world consists of a set of 4 cells
laid out on a 2-by-2 square. The cells are labelled a,b,c,d in a clockwise
fashion, starting at the upper left cell. There is a robot in one of the cells
and some gold in another.
One state of the Square World is shown on the left below. The robot is in
cell a and the gold is in cell c. The figure on the right illustrates
another state. In this case, the robot is in cell b and
the gold is in cell d.
If we concentrate on the location of the robot and the gold only, then
there are 20 possible states. The robot can be in any one of 4 cells,
and the gold can be in any one of 4 cells or in the grasp of the robot
(5 possibilities in all).
Given our point of view, we can distinguish every one of these
states from every other state. By contrast, consider an agent with
a single sensor that determines whether the gold is in the grip of the
robot, in the same cell, or elsewhere. This sensory limitation induces a
partition of the Square World's 20 states into 3 subsets. The first subset
contains the 4 states in which the robot grasps the gold. The second
subset consists of the 4 states in which the gold and the robot are in the same
cell. The third subset consists of the 12 states in which
the gold and the robot are located in different cells.
The Square World has four possible actions. The agent has a single movement
action move, which moves the robot around the square in a clockwise direction
one cell at a time. In addition, the agent can grasp the gold if the gold is
occupying the same cell, and it can drop the gold if it is holding the gold,
leading to 2 more actions grab and drop. Finally, it can do nothing, i.e.
execute the noop action.
Our robot's objective in the Square World problem is to get itself and the gold
to the upper left cell. In this case, the goal G is a singleton
set consisting of just this one state.
The robot knows at the outset that it is in the upper left cell.
However, it does not know the whereabouts of the gold, other than
that it is not in its grasp or in its cell. Therefore, the initial state
set I consists of exactly three states -- in each, the robot is in the
upper left cell and the gold is in one of the other cells.
Figure sssp presents the state graph for the Square World. The labels inside
the nodes denote the states. The first letter of each label
denotes the location of the robot. The second letter
denotes the location of the gold using the same notation as for the robot,
with the
addition of i indicating that the gold is in the grip of the robot. The
structure of the graph clarifies the robot's three percepts. The four inner
states
indicate that the robot is holding the gold. The next four states indicate
that the
gold is in the same cell as the robot (aa,bb,cc,dd). The outermost twelve
states indicate that the robot and the gold are in different locations.
Looking at the graph in figure sssp, we see that there are multiple paths
connecting the Square World state ac to state aa. Consequently, there
are multiple plans for achieving aa from ac. It is a simple
matter for sssp to find these paths. If the search is done in breadth-first
fashion, the result will be the shortest path --- the sequence move, move,
grab, move, move, drop.
Sequential Planning with Incomplete Information
In problem solving with incomplete information, our robot knows that its initial
state is a member of a set I of possible states. How can this robot
reach the goal, given a state graph of the world and this set I? One
approach is to derive a sequential plan that is guaranteed to reach the goal
from every initial state in I. The robot can execute such a plan
with confidence.
A multiple state sequential planner finds a sequential
plan if a sequential solution exists using a state-set graph instead of
the state graph that sssp uses. In the state-set graph, a node is a
set of states. An action arc connects node n_1 to node n_2 if n_2 contains
exactly the states obtained by performing the corresponding action in the states
of n_1. Figure mssp illustrates a partial state-set graph for the
Square World. Note that actions can change the state-set size, both increasing
node size and coercing the world to decrease node size. The mssp
architecture begins with node $I$ and expands the state-set graph breadth-first
until it encounters a node that is a subset of the goal node. Msspa
expands nodes using Results(N), which returns all nodes that result from
the application of each a in A to node N. The following is a simple
version of such an algorithm. For a more thorough treatment of problem
solving search algorithms, see {Genesereth 1992}.
MSSPA Algorithm
1. graph = I, frontier = (I)
2. S = Pop(frontier)
3. If S s a subset of G go to 6.
4. frontier = Append(frontier,Results(S))
Expand graph by adding Results(S).
5. Go to 2.
6. Execute the actions of the path from I to S in graph.
One nice property of this approach is that it is guaranteed -- the robot will
achieve its goal if there is a guaranteed sequential plan.
Furthermore, it will find the plan of minimal length.
However, the cost of simple mssp is very high. Given i= |I|,
g= |G|, a = |A|, and search depth k , the cost cost_{mssp} of finding a
plan is proportional to iga^{k} .
Fortunately, many of the paths in the state-set graph can be ignored; these
are useless partial plans. Any path reaching a node that is identical
to some earlier node in that path is accomplishing nothing. Furthermore, any
path that leads to a state from which there is no escape is simply trapping the
robot. Finally, if we compare two paths and can show that one
path is always as good as the other path, we needn't bother
with the inferior path. We formally define useless in terms of any
partial plan that begins at any node in the graph. Therefore, note the
distinction
between the root node, the current node being expanded, and node I, the node
at which our solution plan must begin:
A partial plan q is useless with respect to root
(the current node) and result-node (q) (the resultant node of executing
plan q from root) if
(1) there is a node n on the path from I to root (inclusive)
such that n is a subset of result-node (q) ,
(2) there is a state s in result-node(q) that has no outgoing arcs in
the state graph, or (3) there is a plan r such that q is not a sub-plan of
r and result-node(r) is a proper subset of result-node(q).
Pruning Rule 1: Sequential Planning
Prune any branch of the state-set graph that leads only to useless plans.
{Theorem}{Pruning Rule 1 preserves completeness.}
Furthermore, we can guarantee the minimal solution by modifying condition (3)
to (3e): there is some plan r such that
length(r) <= length(q)
and result-node(r) is a proper subset of result-node(q) .
Note that once the planner
finds a useless partial plan, it can prune all extensions of that plan
since any solution from the result-node of a useless plan must work either
from an earlier node (1) or from some other plan's result-node (3).
This rule can lead to significant cost savings.
Recall that cost_{mssp} was iga^{k} . If the pruning
rule decreases the branching factor from a to a/b and
searches to depth d for case 3, the cost of
mssp including the cost of Pruning Rule 1 is proportional to ki^{2}
+ zi + a^{d}i^{2} + ig)a^{k}/b^{k}. This indeed grows more slowly than
cost_{mssp} as solution length increases. We have savings when:
{{new\; cost}\over{old\; cost}}=
{{ki + z + a^{d}i + g}\over{gb^{k}}} < 1
Conditional Planning
Sequential planning has a serious flaw: some
problems require perceptual input for success. In these
cases, a sequential planner would fail to find a solution although the system
can reach the goal if it consults its sensory input. We need
a planner that will find such solutions.
A multiple state conditional planner finds the minimal
conditional solution using a
conditional state-set graph. This graph alternates
perceptory and effectory nodes. An effectory node has
action arcs emanating from it and percept arcs leading to
it. A perceptory node has percept arcs emanating from it
and action arcs leading to it. Action arcs connect nodes exactly
as in state-set graphs. Percept arcs are labelled with
percept names and lead to nodes representing the subset of
the originating states that is consistent with the corresponding
percept. Figure mscp illustrates part of a conditional state-set graph.
Mscp begins with just the state set I and expands the conditional state-set
graph in a breadth-first (or iterative deepening) manner until it finds a
solution. The planner uses both Results and Sees, which expands
a perceptory node into a set of nodes, to accomplish the construction. Searching
this graph is much less trivial and often more costly than the state-set graph
search that mssp conducts. This is basically an and-or graph search
problem.
Mscp returns a conditional plan. This plan specifies a
sequence of actions for every possible sequence of inputs.
It is effectively a series of nested case statements that branch based
upon perceptual inputs. Mscpa
then executes the conditional plan by checking the robot's percepts against
case statements and executing the corresponding sub-plans. Below is a
greatly simplified version of the mscp algorithm.
MSCPA Algorithm
1. graph} = I (a perceptory node)
2. Expand every unexpanded perceptory node n using Sees(n).
3. If there is a sub-graph of graph that specifies all action arcs and
reaches a subset of G for every possible series of percept arcs, then go to 6.
4. Expand every unexpanded effectory node m using Results(m).
5. Go to 2.
6. Execute that sub-graph as a conditional plan.
Mscpa will reach the goal with a minimal action sequence
provided that there is a conditional solution.
Unfortunately, greater power has a price. At its worst, Cost_{mscp}
is even greater than cost_{mssp} because the space contains
perceptual branches: igp^{k}a^{k} . To extend Pruning Rule 1
to mscp,
remember that a sequential plan has a single ``result node'' while
a conditional
plan has many possible ``result nodes.'' We define the
result-nodes(q) to
be the set of possible resultant nodes (depending upon perceptory inputs) of
conditional plan q. Pruning Rule parts (1) and (2) require trivial changes
to take this into account. But part (3) now intends to compare two plans,
which amounts to comparing two sets of result-nodes.
We define domination such that if plan r dominates
plan q, then if there is a solution from result-nodes(q),
there must be a solution from result-nodes(r). Each
node in result-nodes(r) is dominating if it is a
proper subset of some node in result-nodes(q).
But ``result-nodes'' that maintain
goal-reachability and do not
introduce infinite loops are also acceptable. Therefore, we also state
that n
is dominating if it has reached the goal or even if it is a proper
subset of root. Below, we define domination and revisit useless in
terms of conditional plans:
Formally, conditional plan r dominates a conditional plan q if
and only if
(A) Forall (n_q in result-nodes(q)) there exists some
(n_r in result-nodes(r)) such that n_r is a proper subset of n_q, and
(B) Forall (n_r in result-nodes(r)) either
1.There exists (n_q in result-nodes(q)) s.t.
n_r is a proper subset of n_q, or
2.n_r is a subset of G, or
3.n_r is a subset of root.
A partial conditional plan q is useless with respect to root
and result-nodes(q) if:
(1) There is a node n on the path from I to root (inclusive)
and there is a node n_{q} in result-nodes(q) such that n is a
subset of n_{q}, or
(2) There is a node n_{q} in result-nodes(q) such that there is a
state
in n_{q} with no outgoing action arcs in the state graph, or
(3) There is a partial conditional plan r such that r dominates q.
Pruning Rule 2: Conditional Planning
Prune any branch of the conditional state-set graph that
leads only to useless plans.
{Theorem}{Pruning Rule 2 preserves completeness.}
Once again, we can reimpose the minimality guarantee by modifying condition
(3): (3e) There is a plan r such that length(r) <= length(q) and r
dominates q without use of case B3.
Cost analysis of mscp with Pruning Rule 2 yields
results identical to cost_{mssp} with the exception that all a^{k}
terms become a^{k}p^{k}. The pruning rule
again provides significant search space savings as solution length increases.
Interleaved Planning and Execution
Conditional planning is an excellent choice when the
planner can extract a solution in reasonable time. But this
is not an easy condition to meet. As the branching factor
and solution length increase mildly, conditional planning
becomes prohibitively expensive in short order. These are
cases in which conditional planning wastes much planning
energy by examining simply too much of the search space.
What if the system could cut its search short and
execute effective partial conditional plans? The system
could track its perceptual inputs during execution and
pinpoint its resultant fringe node at the end of execution.
The planner could continue planning from this particular
fringe node instead of planning for every possible fringe
node. This two-phase cycle would continue until the
system found itself at the goal.
DPA Algorithm
1. states = I.
2. if states is a subset of G exit (success!!!)
3. Invoke terminating mscp from states and return
the resultant conditional plan.
4. Execute the conditional plan, updating states
during execution.
5. Go to 2.
Dpa will reach the goal provided that there is a conditional solution and the
search termination rules preserve completeness.
Assume for the moment that our search termination
rules return sub-plans of the minimal conditional plan
from I to G. We can quantify the dramatic search space
savings of delayed planning in this case. Recall that the
cost of conditional planning is igp^{k}a^{k} . The cost of
delayed planning is the sum of the costs of each
conditional planning episode. If there are j such episodes,
then the total cost of delayed planning is jigp^{k/j}a^{k/j} .
Figure dpa demonstrates the savings, representing mscpa
with a large triangle and dpa by successive small triangles.
Note that if the system could terminate search at every
step, the search cost would simplify to a linear one: kigpa.
Let us return to the search termination problem: how
can the planner tell that a particular plan is worth
executing although it does not take the system to the goal?
The intuition is clear in situations where all our actions are
clearly inferior to one action: we might as well execute
that one action before planning further. For example,
suppose Sally the robot is trying to deliver a package. She
is facing the staircase and has two available actions: move
forward and turn right 90 degrees. The pruning rules
would realize that flying down the stairs is useless (deadly)
and the planner should immediately return the turn right
action. We can generalize this rule from single actions to
partial plans:
Termination Rule 1 (Forced Plan)
If there exists a plan r such that
for all plans q either q is useless or r is a sub-plan of q,
then return r as a forced plan.
{Theorem}
{Termination Rule 1 preserves completeness and provides a minimal solution.}
The forced plan rule has trivial cost when its
conditional planner is using Pruning Rule 2.
Unfortunately, the forced plan criterion can be difficult to
satisfy. This rule requires that every non-useless
solution from $root$ share at least a common first action.
This fails when there are two disparate solutions to the
same problem. Still, complete conditional planning to the
goal may be prohibitively expensive.
We need a termination rule with weaker criteria.
The viable plan rule will select a plan based upon its
own merit, never comparing two plans. The foremost
feature of any viable plan is reversibility. We want to
insure that the plan does not destroy the ability of the
system to reach the goal. This justifies the requirement
that each fringe node of a viable plan be a subset of root.
A viable plan must also guarantee some sort of
progress toward the goal. We guarantee such progress by
requiring every fringe node to be a proper subset of root.
Each viable plan will decrease uncertainty by decreasing
the root state set size. This can occur at most |I| - 1 times.
Termination Rule 2 (Viable Plan)
If there exists a plan r such that
for all nodes n_{r} in result-nodes(r): n_{r} is a proper subset of
root, then return r as a viable plan.
{Theorem}{Termination Rule 2 preserves completeness.}
The fact that the viable plan rule does not
preserve minimality introduces a new issue: how much of
the viable plan should the system execute before returning
to planning? Reasonable choices range from the first
action to the entire plan. We have implemented several
options. Experimental results indicate that this variable
allows a very mild tradeoff between planning time and
execution time.
Average-case cost analysis of dpa using the Viable
Plan Rule yields hopeful results. Recall that pure
conditional planning would cost igp^{k}a^{k}. Suppose a dpa
system executes n partial plans of depth j, resulting in
node I_{n} with size h. From I_{n}, there are no search
termination opportunities and the planner must plan
straight to the goal. Assume that there is some c such that i=ch. The cost
per node of the Viable Plan Rule is i^{2}.
For case 1, assume g>h. The cost from I to I_{n} is
n(i^{2} + ig)p^{j}a^{j}. The worst-case cost from
I_{n} to the goal is (h^{2} + hg)p^{k}a^{k} when I_{n} is no closer
to the goal than I. This can occur precisely when g>h and
coercion is
not necessary. When we divide the cost of dpa by the cost of mscp we
are left with savings when:
{{n(i+g)p^{j}a^{j}}\over{gp^{k}a^{k}}} +
{{h}\over{i}} +
{{h^{2}}\over{ig}} < 1
For case 2, assume g<=h. Then a number of coercive
actions occur along the way from I to G. If we assume
that these coercives are distributed evenly, then there are
(h-g)/2 coercives from I_{n} to the goal and k - (i-h)/2 total
steps from I_{n} to the goal. The total cost changes to
n(i^{2} + ig)p^{j}a^{j} + (h^{2} + hg)p^{k-(i-h)/2}a^{k-(i-h)/2} . The
third term, h^{2}/ig , which would otherwise become greater than one, is
h/(gp^{(i-h)/2}a^{(i-h)/2} ).
Experimental Results
We tested these architectures with six problems in
four worlds using property space representations. For
DPA, we implemented both termination criteria and
executed the first step of viable plans. MJH World is an
indoor navigation problem. Wumpus World is a
traditional hero, gold, and monster game. The Bay Area
Transit Problem {Hsu 1990} captures the high-level
issues of travelling from Berkeley to Stanford in spite of
traffic jams. The Tool Box Problem {Olawsky 1990}
describes two tool boxes that our robot must bolt. The
following chart shows p, a, i, and g for
each problem:
Worlds p a i g
MJH1 2 4 4 4
MJH2 2 4 6 6
MJH3 2 4 6 6
WUM1 4 6 24 4
WUM2 4 6 44 4
BAT 16 4 8172 8172
TBOX 3 14 4 4
Below are running times (in seconds) and plan
lengths, including average length in brackets, for all
architectures with and without pruning rules. The
DPA statistics were derived by running DPA on every
initial state and averaging the running times. The dash (-)
signifies no solution and the asterisk (*) indicates no solution
after 24 hours running time.
World SPA SPAh CPA CPAh DPA
MJH1 34.6 4.1 82.8 21.4 1.6
MJH2 - - 74.6 24.6 1.5
MJH3 - - * 623.6 2.4
WUM1 - - 877.7 104.5 1.3
WUM2 - - * 15111 1.7
BAT - - * * 3.6
TBOX - - * * 73.1
World Lenthdpa Lengthideal
MJH1 9-11[10] 7
MJH2 8-12[10] 6-10[8]
MJH3 8-16[11] 6-12[10]
WUM1 7-15[9.2] 7-11[8.5]
WUM2 7-20[10.8] 7-15[9.8]
BAT 5-12[6.5] 5-12
TBOX 10-13[11.7] 10-13
BAT introduces a huge initial state set and a
high branching factor. DPA time results for BAT are
based upon a random sampling of thirty actual initial
states. TBOX is the hardest problem because the action
branching factor is so high that even sequential
programming with complete information is impossible
without pruning. The TBOX running times are based
upon running DPA on every I possible in the Tool Box
World. Therefore, this is essentially the average of thirty-two separate
problems. Our DPA planner never issued an unbolt command in any TBOX
solution. Olawsky regards the use of unbolt as a failure and, using that
definition, our termination rules produced zero failures in TBOX. A
surprising result concerning both of these large domains is
that the execution lengths were extremely similar to the
ideal execution lengths.
Conclusion
This paper presents some powerful pruning rules for problem solving with
incomplete information. These rules are all domain-independent and lead to
substantial savings in planning cost, both in theoretical analysis and on
practical problems. The rules are of special importance in the case of
interleaved planning and execution in that they allow the planner to terminate
search without planning to the goal.
Although our analysis concentrates exclusively on uncertainty about initial
states, the rules are equally relevant to uncertainty about percepts and
actions. Although the analysis also assumes that state sets are represented
explicitly, the pruning rules apply equally well to planners based on explict
enumerations of property sets (e.g. Strips) and logic-based methods (e.g.
Green's method).
One substantial limitation of this work is our emphasis on state goals. We have
not considered the value of these methods or rules on problems involving
conditional goals or process goals. We have also not considered the
interactions of our rules with methods for coping with numerical uncertainty.
Further work is needed in both areas.
Acknowledgements
David Smith introduced the machine shop robot example. Sarah Morse
provided a helpful early critique of this paper. Tomas Uribe provided
useful late-night suggestions. Funding was provided by the Office of Naval
Research under contract number N00014-90-J-1533.
References
{Etzioni 1992} Etzioni, O., Hanks, S., Weld, D., ``An
Approach to Planning with Incomplete Information,'' {\it Proceedings
of the Third International Conference on Knowledge Representation and
Reasoning}, October, 1992.
{Fikes 1972} Fikes, R. E., Hart, P.E., and Nilsson, N.
J., ``Learning and Executing Generalized Robot Plans,'' {\it Artificial
Intelligence}, 3(4): 251--288, 1972.
{Genesereth 1992} Genesereth, M. R., {\it Discrete
Systems}. Course notes for {\it CS 222}. Stanford, CA: Stanford University,
1992.
{Hsu 1990} Hsu, J., ``Partial Planning with Incomplete
Information,'' {\it AAAI Spring Symposium on Planning in Uncertain,
Unpredictable, or Changing Environments}. Menlo Park, CA: AAAI Press,
1990.
{Olawsky 1990} Olawsky, D., and Gini, M., ``Deferred
Planning and Sensor Use,'' {\it Proceedings of the DARPA Workshop on
Innovative Approaches to Planning, Scheduling, and Control}. Los
Altos, CA: Morgan Kaufmann, 1990.
{Rosenschein 1981} Rosenschein, S.J., ``Plan Synthesis:
A Logical Perspective,'' {\it Proceedings of the Seventh International
Conference on Artificial Intelligence}. Vancouver, British Columbia,
Canada, August 1981.