More realistic Strips example - 2

Reducing differences is a bit like a jigsaw puzzle where Strips tries different
substitutions to see if a particular operator will reduce the difference. In
order to reduce the difference, REDUCING 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 predicate
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 current
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 amatch in the 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.


Again, Strips examines the preconditions. This time rk=R1 and rm=R2
can be matched with CONNECTS(dx, rk, rm), and all preconditions are
satisfied (that is, they evaluate to true). Strips puts the operator OP1 on the
plan stack and applies the operator to the world model, changing the state.
(Note that this is the equivalent of a “mental operation”; the robot doesn’t
actually physically go to the door, it just changes the state to imagine what
would happen if it did.)
To recall, the initial state of the world model was:
initial state:
INROOM(IT, R1)
INROOM(B1,R2)
CONNECTS(D1, R1, R2)
CONNECTS(D1, R2, R1)
STATUS(D1,OPEN)
Applying the operator OP1 means making the changes on the add-list and
delete-list. There is only a predicate on the add-list and none on the deletelist.
After adding NEXTTO(IT, D1), the state of the world is:
state after OP1:
INROOM(IT, R1)
INROOM(B1,R2)
CONNECTS(D1, R1, R2)
CONNECTS(D1, R2, R1)
STATUS(D1,OPEN)
NEXTTO(IT, D1)
Strips then returns control back to the previous call. It resumes where it
left off in evaluating the preconditions for OP2 with dx=D1, rm=R2 and
rk=R1, only now the world model has changed. Both STATUS(D1, OPEN)
and INROOM(IT, R1) are true, so all the preconditions for OP2 are satisfied.
Strips puts OP2 on its plan stack and changes the world model by applying
the add-list and delete-list predicates. This results in what the state of the
world will be when the plan executes:


state after OP2:
INROOM(IT, R2)
INROOM(B1,R2)


CONNECTS(D1, R1, R2)
CONNECTS(D1, R2, R1)
STATUS(D1,OPEN)
NEXTTO(IT, D1)
Strips exits and the plan for the robot to physically execute (in reverse
order on the stack) is: GOTODOOR(IT, D1), GOTHRUDOOR(IT, D1).