Information Technology Reference
In-Depth Information
a.
Write the initial state clauses for the fluent
located_on
for the initial situation
in figure 9.15. (As you test your program with different initial situations, you
will need to vary these clauses.)
b.
Write the successor state clauses for the fluent
located_on
. You need to
decide for each action
a
how
located_on
(
depends on
a
and what
holds in situation
s
. Show that your
located_on
works properly by testing it
on a variety of situations.
[
|
])
b
,
l
,
a
s
c.
Write a clause for the goal state in figure 9.15. (As you test your program
with different goals, you will need to vary this clause.)
d.
Define the
poss
predicate for your
move
action, using
located_on
.
e.
Show that the planning problem in figure 9.15 can be solved with
plan
.
f.
Show that your program works on other small problems of your choosing.
8.
As noted in section 9.3.2, the
reachable
predicate defined in figure 9.3 allows
for
loops
, where a sequence of moves passes through a state and later returns to
exactly the same state. For example, in the monkey and bananas problem where
the monkey starts at location 2, a sequence of
go
moves that ends with
go(loc2)
returns the monkey to the initial state. The presence of such loops can only slow
down the process of searching for a reachable goal state.
Write clauses to define a new predicate
reachable_uniq
(
s
,
l
,
s
)
that is just like
reachable
except that the moves in
l
do not pass through the same state twice.
Hint:
Define an auxiliary predicate
reachable_list
(
s
,
l
,
x
,
s
)
that holds when
l
[
m
1
,
...
,
m
n
]
+
is a list
of
n
moves (as before), and
x
is a list of
n
1
states in reverse
s
0
,
s
=
order
[
s
n
,
...
,
s
0
]
=
s
n
, and for every
i
from 1 to
n
, there is a legal move
m
i
from state
s
i
−
1
to state
s
i
.
with no repetitions, such that
s
9.
Consider the following, called the jealous husband problem:
Three married couples find themselves on one bank of a river wanting to
get to the other side using a boat that can only hold two people at a time.
However, each husband insists on being with his wife whenever there are
other men present.
The shortest solution involves eleven boat crossings, too many to solve com-
fortably using the
reachable
predicate. Use
reachable_uniq
from exercise 8 to
solve it. (Not to take this example too seriously or anything, but we might prefer
a solution where the jealous husbands all end up on one side of the river without
a boat, and the women have all gone off to find better husbands!)
