 |
GOAL REGRESSION
|
Notes from: Richard
Waldinger, Achieving Several Goals Simultaneously. In E. Elcock
& D. Michie (Eds.), Machine Intelligence 8. Machine
Representations of Knowledge. Chichester: Ellis Horwood, 1977.
Pp. 94-136.
Suppose P is a relation
and F is an action of program instruction; if P is true and we
execute F, then there is no guarantee that P will still be true.
However, Given P, it is always possible to find a relation P'
such that achieving P' and then executing F guarantees that P
will be true afterwards.
For example,
in a simple blocks world if P is "block C is clear"
(meaning C has no blocks on top of it) and F is "Put block
A on block B," then P' is the relation "C is clear
or A is on C"; for if C is clear before putting A on B,
then C will still be clear afterwards, while if A is on C before
being put on B, then the action itself will clear the top of
C.
|
|
P' is taken as the
weakest relation that ensures the subsequent truth of P; in other
words, if P' is not true before executing F, P may not be true
afterwards, Otherwise, we could always take P' to be the relation
that is always false. P' is called the result of passing P back
over F, and this operation of passing P back is called "regression."
So the idea of goal regression
is linked to planning via plan modification...i.e. in order to
achieve P and Q, construct a plan F that achieves P, and then
modify F so that it achieves Q while still achieving P. The idea
is to protect P so that the choice of where to place the steps
for achieving Q is determined relative to the plan for P.
Assume that F is a linear sequence
of instructions (F1, ..., Fn). In order to achieve Q after executing
F, it suffices to achieve Q' immediately before executing Fn,
where Q' is the result of passing Q back over Fn. Similarly,
it suffices to achieve Q'' immediately before executing Fn-1,
where Q'' is the result of passing Q' back over Fn-1.
The idea is that a goal may be
difficult or impossible to achieve after F but may be easier
at some earlier point. Or if Achieving Q after executing F destroys
the truth of P, it is possible that planning to achieve Q' or
Q'' earlier will not disturb P at all.
How to do this:
- have explicit "regression
rules"
- if a relation is defined in
terms of other relations, it may be possible to pass back those
defining relations;
- if the plan step is defined
in terms of simpler component steps, then knowing how to pass
relations back over the components allows one to pass the relation
back over the original plan step
- if you don't know how to pass
it back, make the assumption that the plan step has absolutely
no effect on the relation. (Cf. frame problem).
A simple example is shown to
the right. The protect annotation indicates the goal regression
operation. By passing goals back over plan steps back-tracking
and reversing the order may be avoided. This technique will not
always prevent goal reordering.
|
 |
|
(The observation
that it is technically simpler to look at the "weakest preconditions"
of a relation (passing it back) instead of the "strongest
postconditions" (passing it forward), appears to be due
to Z. Manna (1968) Termination of Algorithms. PhD Thesis, Department
of Computer Science, Carnegie-Mellon University, Pittsburgh,
PA; C.A.R. Hoare (1969) An axiomatic basis for computer programming.
Communications of the ACM, 12, 10, 576-580, 583; and J.C. King
(1969) A Program Verifier. PhD Thesis, Department of Computer
Science, Carnegie-Mellon University, Pittsburgh, PA. The term
"weakest precondition" is Dijkstra's. ( E.W. Dijkstra
(1975) Guarded commands, non-determinacy in a calculus for the
derivation of programs. Proceedings, International Conference
on Reliable Software 2-2.13, Los Angeles, CA>
Notes from: Nils J.
Nilsson, Principles of Artificial Intelligence. Palo Alto, CA:
Tioga Publishing, 1980. Chapter 7.4.2 & Chapter 8.1
|
|
|