Page 67 - Introduction to AI Robotics

50
2 The Hierarchical Paradigm
Reducing differences is a bit like a jigsaw puzzle where Strips tries differ-
ent substitutions to see if a particular operator will reduce the difference. In
REDUCING order to reduce the difference, Strips looks in the difference table, starting at
DIFFERENCES the top, under the add-list column for a match. It looks in the add-list rather
than a separate differences column because the add-list expresses what the
result of the operator is. If Strips finds an operator that produces the goal
state, then that operator eliminates the existing difference between the initial
and goal states.
The add-list in OP2: GOTHRUDOOR has a match on form. If rm=R2,then
the result of OP2 would be INROOM(IT, R2). This would eliminate the
difference, so OP2 is a candidate operator.
Before the OP2 can be applied, Strips must check the preconditions. To do
this, rm must be replaced with R2 in every predicate in the preconditions.
OP2 has two preconditions, only CONNECTS(dx, rk, rm) is affected. It
becomes CONNECTS(dx, rk, R2).Until dx and rk are bound, the pred-
icate doesn’t have a true or false value. Essentially dx, rk are wildcards,
CONNECTS(*, *, R2). To fill in values for these variables, Strips looks at
the current state of the world model to find a match. The predicate in the cur-
rent state of the world CONNECTS(D1, R1, R2) matches CONNECTS(*,
*, R2). D1 is now bound to dx and R1 is bound to rk.
Now Strips propagates the bindings to the next precondition on the list:
NEXTTO(IT, dx). NEXTTO(IT, D1) is FALSE because the predicate is
FAILED not in the current world state. NEXTTO(IT, D1) is referred to as a failed
PRECONDITIONS precondition. An informal interpretation is that GOTHRUDOOR(IT, D1) will
get the robot to the goal state, but before it can do that, IT has to be next to
D1.
RECURSION TO Rather than give up, STRIPS recurses (uses the programming technique of
RESOLVE DIFFERENCES recursion) to repeat the entire procedure. It marks the original goal state as
G0, pushes it on a stack, then it creates a new sub-goal state, G1.
The difference between NEXTTO(IT, D1) and the current world state is:

:NEXTTO(IT, D1)
Strips once again searches through the add-list in the difference table to
find an operator that would negate this. Indeed, OP1: GOTODOOR(IT,
dx) has a matchinthe add-list of NEXTTO(IT, dx). Strips has to start over
with reassigning values to the identifiers because the program has entered a
new programming scope, so dx=D1.