mob@mit-amt.MIT.EDU (Mario O. Bourgoin) (08/13/86)
First, I would like to thank all the persons who answered my request for
help. Your advice and suggestions were most useful in making this
exercise a learning experience for me.
Thanks to:
- Dave Broderick. He was the first to send me a solution to the
farmer problem. His program modeled the state as composed of
left and right riverbank lists and the problem as finding a
sequence of sequential addition/deletions from these lists to
reach the goal. As an example:
Start state: river(farmer+[fox,goose,grain],[]).
Goal state: river([],farmer+[fox,goose,grain]).
- Chrisj@basser.oz. He was the last to send me a solution to the
farmer problem. I got it just as I was writing this article
and haven't had time to try it out yet. His answer is to the
Australian version of the problem, involving a Koala,
Eucalyptus leaves, a Dingo and of course a Farmer.
- Maarten van Emden mhvanemden. His reply was to send me a
problem set which included questions about moving from node to
node through a graph which was where my head space was at at
the time. This covered two methods to prevent program
looping: the depth-bound approach and the path record
approach. The problem set also included many questions which
brought home other points that were essential in cleaning up
my model of Prolog's behavior. This reply was without doubt
the most useful one.
- Ed Windes. He pointed out the problem of the path/2 procedure
being left-recursive and also mentioned the need for keeping a
record of visited states to prevent looping while walking
through the problem state graph.
- Wayne Cook and Suzanne Dietrich. Both made the suggestion that
already seen states be asserted and looked up as a means of
controlling looping. I had already used the technique in a
small classification expert system as a means of avoiding
solving for already discovered facts.
Truth Maintenance Systems (TMS) accomplish this caching in an
efficient way that allows easy checking of which facts are or
are not applicable to a situation. TMSs also replace
chronological backtracking with dependency directed
backtracking for greater search efficiency. Johan de Kleer
(Artificial Intelligence, Vol. 28, No. 1, 1986) of Xerox PARC
has designed an assumption based TMS which eliminates most
backtracking of all types. Maybe such systems will be
included in future versions of Prolog.
- Chuck Restivo. For being the moderator to this newsgroup and
sending my request for help to places that may not have been
reached otherwise.
------------------------------------------------------------------------
On to the problem itself. There were three problems that prevented the
original program from finding _a_ solution to the farmer problem:
- There was a typo in the statement of the linked/2 procedure.
- The path/2 procedure was left recursive. While the solution
statement was logically correct, the left recursion caused
much unnecessary searching to find a solution. This was fixed
by replacing the left call to a call to linked/2.
- The path/2 procedure did not restrict alternate linked states
to those not yet encountered. This was fixed by adding a Path
variable to the input(?) list of the path/2 predicate making
it into a path/3 predicate.
While the last two fixes are not in theory essential to the finding of a
solution, not fixing them results in stack overflow before a solution
can be found. If Prolog refused to solve for goals already encountered,
this problem would not exist. A hash table of calls would provide an
efficient solution to the problem of whether a state has been met
already given a consistent encoding of variable names. Can someone
provide me with a reason other than efficiency for why this is not done?
Ed Windes and Suzanne Dietrich pointed out that the linked/2 procedure
did not produce all of correct linked states for the state(1,1,1,1)
input. This was due only to the typo in the third and clause of the
predicate. With this fixed, the predicate is able to generate all of the
linked states, albeit with much redundancy.
There are two answers to the Farmer Puzzle. While with the above fixes
my program would manage to produce a correct solution, resolution for
alternate answers would repeat many of the already encountered
solutions. The number of repetitions has an upper bound of 2^58 as near
as I can calculate. The 58 was obtained by counting the number of legal
second states produced by Prolog using linked/2 and subtracting the
total number of legal states from the result. Can someone substantiate
this answer?
The problem is that both legal/1 and linked/2 are loose
characterizations of what they claim to represent so that they reproduce
previously given answers upon resolution. legal/1 for example will
produce 16 legal states while there are only 10 legal ones. 16 was
obtained through figuring out the number of states that legal/1 can
produce. Can someone give me an explanation or a pointer to an
explanation as to how to calculate the number of repeated resolutions to
linked/2 or similar predicates?
Another problem of efficiency was that my statement of the problem did
not take advantage of Prolog's unification procedure for stating
similarity between elements of states. Taking advantage of this feature
eliminates the same(yes,_,_) predicate and associated matching. This
results in up to 2.5 times! fewer procedure calls. This statistic was
gathered by hand. Can someone point me to tools that allow me to get
statistics from Prolog? I use C-Prolog. Better yet, can someone point me
to theory that would allow me to calculate the expected number of calls
a particular problem statement will require to generate all solutions?
------------------------------------------------------------------------
Here is the final solution:
/* The problem solver keeps track of the current state as a predicate
of the form:
state(Farmer,Fox,Goose,Grain).
Where Farmer is abbreviated F, Fox is X, Goose is G and Grain is A.
Each place can take on a value of either 1 or 2, each number
representing a side of the river.
*/
/* Test for membership of an element in a list */
member(E,[E|_]).
member(E,[_|T]) :- member(E,T).
/* Define sides 1 and 2 as being opposite */
opposite(1,2).
opposite(2,1).
/* A legal state is one where either the farmer is on the same side as
the goose or is on the same side as both the fox and the grain. In
the latter case, the condition that the farmer be on the opposite
side from the goose is necessary to prevent resolutions that repeat
states already covered by the first legal/1 definition.
*/
legal(state(F,_,F,_)).
legal(state(F,F,G,F)) :- opposite(F,G).
/* There are four cases for linked states:
Only the farmer changes sides */
linked(state(F1,X,G,A),state(F2,X,G,A)) :-
opposite(F1,F2),
legal(state(F2,X,G,A)).
/* The farmer and the fox change sides */
linked(state(F1,F1,G,A),state(F2,F2,G,A)) :-
opposite(F1,F2),
legal(state(F2,F2,G,A)).
/* The farmer and the goose change sides */
linked(state(F1,X,F1,A),state(F2,X,F2,A)) :-
opposite(F1,F2),
legal(state(F2,X,F2,A)).
/* The farmer and the grain change sides */
linked(state(F1,X,G,F1),state(F2,X,G,F2)) :-
opposite(F1,F2),
legal(state(F2,X,G,F2)).
/* This is the top level predicate whose purpose is to establish
whether there is a non-circular path from the Start state to the
Goal state. Solution is that path. path/3 calls path/4 with a list
of the Start state as the germ of the already seen states list.
*/
path(Start,Goal,Solution) :-
path(Start,[Start],Goal,Solution).
/* A path from State to Goal exists if State is linked with Goal.
Path is the list of states encountered up to now. Solution is Path
prepended with Goal.
*/
path(State,Path,Goal,[Goal|Path]) :-
linked(State,Goal).
/* A path from State1 to Goal exists if there exists a State2 which
has not yet been encountered, which is linked with State1 and for
which a path exists to Goal. State2 is part of the list of states
encountered up to now and Solution is the list of states leading
from the original state to Goal.
*/
path(State1,Path,Goal,Solution) :-
linked(State1,State2),
not(member(State2,Path)),
path(State2,[State2|Path],Goal,Solution).
--Mario O. Bourgoin