Missionaries and Cannibals: Discussion, Part 1
Date: Mon, 12 Jul 1999
From: Vladimir Lifschitz
To: TAG
Here is a classical planning problem that we have never tried to
formalize in an action language and solve using dlv or smodels or
ccalc:
Three missionaries and three cannibals come to
a river and find a boat that holds two. If the
cannibals ever outnumber the missionaries on
either bank, the missionaries will be eaten.
How shall they cross?
Any ideas?
============
Date: Tue, 20 Jul 1999
From: Mary Heidt
To: TAG
Here is a solution using smodels for the missionaries and cannibals problem.
Comments are welcome.
-------
%Missionaries and Cannibals problem presented to smodels
%Three missionaries and three cannibals come to a river and find a boat that holds two.
%If the cannibals ever outnumber the missionaries on either bank, the missionaries will be
%be eaten. How can they cross?
agent(cannibal).
agent(missionary).
vehicle(boat).
time(0..15).
next(T,T1):- time(T), time(T1), T1 = T + 1.
const max = 3.
num(0..max).
%---------------------------------------------------------------------------------------
% FLUENTS
%---------------------------------------------------------------------------------------
%located(X,N) iff N number of type X are located on the first side of the river
%located(A,N):- agent(A), num(N).
%located(O,N):- object(O), num(N).
%--------------------------------------------------------------------------------------
% ACTIONS
%--------------------------------------------------------------------------------------
%cross(A,N) iff N agent(s)of the type A cross to the opposiste side of the river
%cross(A,N):- agent(A), num(N).
%return(A,N) iff N agent(s)of the type A return to the the original side
%return(A,N):- agent(A), num(N).
%--------------------------------------------------------------------------------------
% DYNAMIC CAUSAL LAWS
%--------------------------------------------------------------------------------------
%causes(located(A,N1-N),cross(A,N),[located(A,N1)])
holds(located(A,N1-N),T1):- agent(A),
num(N1),
num(N),
next(T,T1),
occurs(cross(A,N),T),
holds(located(A,N1),T).
ab(located(A,N1),T):- agent(A),
num(N),
num(N1),
time(T),
occurs(cross(A,N),T),
holds(located(A,N1),T).
holds(located(boat,0),T1):- next(T,T1),
agent(A),
num(N),
occurs(cross(A,N),T),
holds(located(boat,1),T).
ab(located(boat,N1),T):- time(T),
agent(A),
num(N),
num(N1),
occurs(cross(A,N),T),
holds(located(boat,1),T).
%causes(located(A,N1+N),return(A,N),[located(A,N1)])
holds(located(A,N1 + N),T1):- agent(A),
num(N),
num(N1),
next(T,T1),
occurs(return(A,N),T),
holds(located(A,N1),T).
ab(located(A,N1),T):- agent(A),
num(N),
num(N1),
time(T),
occurs(return(A,N),T),
holds(located(A,N1),T).
holds(located(boat,1),T1):- next(T,T1),
agent(A),
num(N),
occurs(return(A,N),T),
holds(located(boat,0),T).
ab(located(boat,N1),T):- time(T),
agent(A),
num(N),
num(N1),
occurs(return(A,N),T),
holds(located(boat,0),T).
%------------------------------------------------------------------------------------------
% INERTIA
%------------------------------------------------------------------------------------------
holds(located(A,N),T1):- agent(A),
num(N),
next(T,T1),
holds(located(A,N),T),
not ab(located(A,N),T).
holds(located(boat,N),T1):- num(N),
next(T,T1),
holds(located(boat,N),T),
not ab(located(boat,N),T).
%------------------------------------------------------------------------------------------
% CONSISTENCY
%------------------------------------------------------------------------------------------
:- time(T),
holds(located(boat,0),T),
holds(located(boat,1),T).
:- agent(A),
time(T),
num(N),
num(N1),
not eq(N,N1),
holds(located(A,N),T),
holds(located(A,N1),T).
%------------------------------------------------------------------------------------------
% CONSTRAINTS
%------------------------------------------------------------------------------------------
%it is impossible for more agents to cross than are on the first side
:- agent(A),
num(N),
num(N1),
time(T),
occurs(cross(A,N),T),
holds(located(A,N1),T),
gt(N,N1).
%it is impossible for more agents to return than are on the other side
:- agent(A),
num(N),
num(N1),
time(T),
occurs(return(A,N),T),
holds(located(A,N1),T),
gt(N + N1,max).
%cannibals cannot outnumber missionaries on either side
:- time(T),
num(N),
num(N1),
holds(located(cannibal,N),T),
holds(located(missionary,N1),T),
gt(N,N1),
gt(N1,0).
:- time(T),
num(N),
num(N1),
holds(located(cannibal,N),T),
holds(located(missionary,N1),T),
lt(N1,max),
lt(N,N1).
%agents cannot move if they are not on the same side with the boat
:- time(T),
num(N),
agent(A),
holds(located(boat,0),T),
occurs(cross(A,N),T).
:- time(T),
num(N),
agent(A),
holds(located(boat,1),T),
occurs(return(A,N),T).
%-------------------------------------------------------------------------------------------
% INITIAL CONDITIONS
%-------------------------------------------------------------------------------------------
holds(located(cannibal,3),0).
holds(located(missionary,3),0).
holds(located(boat,1),0).
%--------------------------------------------------------------------------------------------
% CONTROL MODULE
%--------------------------------------------------------------------------------------------
%An action must occur at each instance of time until goal is reached
%Possible actions are movement of missionaries only, movement of cannibals only, and
%movement of one cannibal and one missionary.
move(missionary,T):- time(T), not goal(T), not move(cannibal,T), not move(mixed,T).
move(cannibal,T):- time(T), not goal(T), not move(missionary,T), not move(mixed,T).
move(mixed,T):- time(T), not goal(T), not move(missionary,T), not move(cannibal,T).
occurs(cross(A,2),T) :- agent(A), time(T), move(A,T), not occurs(return(A,2),T), not
occurs(cross(A,1),T), not occurs(return(A,1),T).
occurs(return(A,2),T) :- agent(A), time(T), move(A,T), not occurs(cross(A,2),T), not
occurs(cross(A,1),T), not occurs(return(A,1),T).
occurs(cross(A,1),T) :- agent(A), time(T), move(A,T), not occurs(cross(A,2),T), not
occurs(return(A,2),T), not occurs(return(A,1),T).
occurs(return(A,1),T) :- agent(A), time(T), move(A,T), not occurs(cross(A,2),T), not
occurs(return(A,2),T), not occurs(cross(A,1),T).
occurs(cross(cannibal,1),T):- time(T), move(mixed,T), not occurs(return(cannibal,1),T), not
occurs(return(missionary,1),T).
occurs(cross(missionary,1),T):- time(T), move(mixed,T), not occurs(return(cannibal,1),T), not
occurs(return(missionary,1),T).
occurs(return(cannibal,1),T):- time(T), move(mixed,T), not occurs(cross(cannibal,1),T), not
occurs(cross(missionary,1),T).
occurs(return(missionary,1),T):- time(T), move(mixed,T), not occurs(cross(cannibal,1),T), not
occurs(cross(missionary,1),T).
%----------------------------------------------------------------------------------------------
% GOAL
%----------------------------------------------------------------------------------------------
goal(T):- time(T),
holds(located(missionary,0),T),
holds(located(cannibal,0),T).
:- not goal(11).
hide holds(X,Y).
hide ab(X,Y).
hide time(T).
hide num(N).
hide agent(A).
hide side(S).
hide opp(X,Y).
hide next(X,Y).
hide goal(X).
hide object(X).
============
Date: Tue, 20 Jul 1999
From: Vladimir Lifschitz
To: Mary Heidt
I found a formalization for the missionaries and cannibals problem too.
Instead of smodels, it uses ccalc, but it clearly has a lot in common with
yours. Let's compare the two formalizations carefully, and analyze the
differences.
-------
%%%%%%%%%%%%% Parameters %%%%%%%%%%%%
:- macros
maxInt -> 3; % largest integer needed
numTotal -> 3; % total number of missionaries, as well as cannibals
boatCapacity -> 2;
from -> 10; to -> 11. % range of plan lengths to be tried
%%%%%%%%%%%%% Definitions and Declarations %%%%%%%%%%%%
:- include 'C'. % standard file
:- macros
sum(#1,#2,#3) -> #1 is min((#2)+(#3),maxInt); % addition in range 0..maxInt
diff(#1,#2,#3) -> #1 is max((#2)-(#3),0); % subtraction in this range
outnumbered(#1,#2) -> (#2 > #1) && (#1 > 0). % #1 missionaries are
% outnumbered by #2 cannibals
:- sorts
number; bank.
:- variables
M,M1,C,C1 :: number;
B,B1 :: bank.
:- computed X. % variable to store results of calculations
:- constants
0..maxInt :: number;
b1,b2 :: bank;
numM(bank,number) :: inertialTrueFluent; % number of missionaries on a bank
numC(bank,number) :: inertialTrueFluent; % number of cannibals on a bank
boatAt(bank) :: inertialTrueFluent;
cross(number,number) :: action.
%%%%%%%%%%%%% Postulates %%%%%%%%%%%%%
% effects of crossing the river:
% the boat moves to the other bank
cross(M,C) causes boatAt(B) if -boatAt(B).
% numbers of missionaries on both banks change
cross(M,C) causes numM(B,X) if boatAt(B) && numM(B,M1) && diff(X,M1,M).
cross(M,C) causes numM(B,X) if -boatAt(B) && numM(B,M1) && sum(X,M1,M).
% and so do numbers of cannibals
cross(M,C) causes numC(B,X) if boatAt(B) && numC(B,C1) && diff(X,C1,C).
cross(M,C) causes numC(B,X) if -boatAt(B) && numC(B,C1) && sum(X,C1,C).
% preconditions for crossing the river:
% someone should be in the boat
nonexecutable cross(M,C) if M=0 && C=0.
% but not too many
nonexecutable cross(M,C) if M+C > boatCapacity.
% enough people should be available prior to departure
nonexecutable cross(M,C) if boatAt(B) && numM(B,M1) && M>M1.
nonexecutable cross(M,C) if boatAt(B) && numC(B,C1) && C>C1.
% missionaries should not be outnumbered in the boat
nonexecutable cross(M,C) if outnumbered(M,C).
% number of people on each bank and location of the boat are unique
always \/ M: numM(B,M).
always \/ C: numC(B,C).
always \/ B: boatAt(B).
caused -numM(B,M1) if numM(B,M) && -(M=M1).
caused -numC(B,C1) if numC(B,C) && -(C=C1).
caused -boatAt(B1) if boatAt(B) && -(B=B1).
% missionaries should not be outnumbered on either bank
always numM(B,M) && numC(B,C) ->> - outnumbered(M,C).
%%%%%%%%%%%%% Planning Problem %%%%%%%%%%%%
:- plan
facts ::
0: (numM(b1,numTotal) && numC(b1,numTotal)),
0: (numM(b2,0) && numC(b2,0)),
0: boatAt(b1);
goals ::
from..to: (numM(b1,0) && numC(b1,0)).
------------
Output of ccalc:
calling sato...
run time (seconds) 39.83
calling sato...
run time (seconds) 74.18
0. boatAt(b1) numC(b1,3) numC(b2,0) numM(b1,3) numM(b2,0)
ACTIONS: cross(1,1)
1. boatAt(b2) numC(b1,2) numC(b2,1) numM(b1,2) numM(b2,1)
ACTIONS: cross(1,0)
2. boatAt(b1) numC(b1,2) numC(b2,1) numM(b1,3) numM(b2,0)
ACTIONS: cross(0,2)
3. boatAt(b2) numC(b1,0) numC(b2,3) numM(b1,3) numM(b2,0)
ACTIONS: cross(0,1)
4. boatAt(b1) numC(b1,1) numC(b2,2) numM(b1,3) numM(b2,0)
ACTIONS: cross(2,0)
5. boatAt(b2) numC(b1,1) numC(b2,2) numM(b1,1) numM(b2,2)
ACTIONS: cross(1,1)
6. boatAt(b1) numC(b1,2) numC(b2,1) numM(b1,2) numM(b2,1)
ACTIONS: cross(2,0)
7. boatAt(b2) numC(b1,2) numC(b2,1) numM(b1,0) numM(b2,3)
ACTIONS: cross(0,1)
8. boatAt(b1) numC(b1,3) numC(b2,0) numM(b1,0) numM(b2,3)
ACTIONS: cross(0,2)
9. boatAt(b2) numC(b1,1) numC(b2,2) numM(b1,0) numM(b2,3)
ACTIONS: cross(1,0)
10. boatAt(b1) numC(b1,1) numC(b2,2) numM(b1,1) numM(b2,2)
ACTIONS: cross(1,1)
11. boatAt(b2) numC(b1,0) numC(b2,3) numM(b1,0) numM(b2,3)
===========
Date: Fri, 30 Jul 1999
From: Mary Heidt
To: Vladimir Lifschitz
I have tried to run your formalization of the missionaries and cannibals
problem on the version of ccalc we have and am unable to get the program
to run. We get an error message for the line with the rule
:- computed X.
I wanted to compare the run times between your ccalc version and my
smodels version. The version your sent on July 20 shows run times of
39.83 and 74.18 seconds. I have included the output from my formalization
for smodels below and as you can see the cpu time is 0.0.
I expected that there might be a difference because our control module
makes our program more specific and your program is more general. However,
I do not believe this can explain the rather large difference in the times.
The other differences I see in the programs are
1. The smodels formalization has two actions (cross and return), while the
ccalc formalization has only one action (cross).
2. The smodels formalization keeps track of the missionaries and cannibals
on only one side of the river, while the ccalc formalization keeps track of
missionaries and cannibals on both sides of the river.
Do you have any explanation for the difference in run times?
Regards,
Mary
-----
output from smodels
baboon% time fparse cannibals > out
0.0u 0.0s 0:00 0% 0+0k 0+0io 0pf+0w
baboon% time smodels 0 < out
smodels version 2.21. Reading...done
Answer: 1
Stable Model: occurs(cross(missionary,1),0) occurs(cross(missionary,2),4)
occurs(cross(missionary,2),6) occurs(cross(cannibal,1),0)
occurs(cross(cannibal,2),2) occurs(cross(cannibal,2),8)
occurs(cross(cannibal,2),10) occurs(return(missionary,1),1)
occurs(return(missionary,1),5) occurs(return(cannibal,1),3)
occurs(return(cannibal,1),5) occurs(return(cannibal,1),7)
occurs(return(cannibal,1),9) move(missionary,1) move(missionary,4)
move(missionary,6) move(cannibal,2) move(cannibal,3) move(cannibal,7)
move(cannibal,8) move(cannibal,9) move(cannibal,10) move(mixed,0)
move(mixed,5)
Answer: 2
Stable Model: occurs(cross(missionary,1),0) occurs(cross(missionary,1),10)
occurs(cross(missionary,2),4) occurs(cross(missionary,2),6)
occurs(cross(cannibal,1),0) occurs(cross(cannibal,1),10)
occurs(cross(cannibal,2),2) occurs(cross(cannibal,2),8)
occurs(return(missionary,1),1) occurs(return(missionary,1),5)
occurs(return(missionary,1),9) occurs(return(cannibal,1),3)
occurs(return(cannibal,1),5) occurs(return(cannibal,1),7)
move(missionary,1) move(missionary,4) move(missionary,6)
move(missionary,9) move(cannibal,2) move(cannibal,3) move(cannibal,7)
move(cannibal,8) move(mixed,0) move(mixed,5) move(mixed,10)
Answer: 3
Stable Model: occurs(cross(missionary,2),4) occurs(cross(missionary,2),6)
occurs(cross(cannibal,2),0) occurs(cross(cannibal,2),2)
occurs(cross(cannibal,2),8) occurs(cross(cannibal,2),10)
occurs(return(missionary,1),5) occurs(return(cannibal,1),1)
occurs(return(cannibal,1),3) occurs(return(cannibal,1),5)
occurs(return(cannibal,1),7) occurs(return(cannibal,1),9)
move(missionary,4) move(missionary,6) move(cannibal,0) move(cannibal,1)
move(cannibal,2) move(cannibal,3) move(cannibal,7) move(cannibal,8)
move(cannibal,9) move(cannibal,10) move(mixed,5)
Answer: 4
Stable Model: occurs(cross(missionary,1),10) occurs(cross(missionary,2),4)
occurs(cross(missionary,2),6) occurs(cross(cannibal,1),10)
occurs(cross(cannibal,2),0) occurs(cross(cannibal,2),2)
occurs(cross(cannibal,2),8) occurs(return(missionary,1),5)
occurs(return(missionary,1),9) occurs(return(cannibal,1),1)
occurs(return(cannibal,1),3) occurs(return(cannibal,1),5)
occurs(return(cannibal,1),7) move(missionary,4)
move(missionary,6) move(missionary,9) move(cannibal,0) move(cannibal,1)
move(cannibal,2) move(cannibal,3) move(cannibal,7) move(cannibal,8)
move(mixed,5) move(mixed,10)
False
Duration: 0.690
Number of choice points: 16
Number of wrong choices: 16
Number of atoms: 923
Number of rules: 4862
Number of picked atoms: 12376
Number of forced atoms: 749
Number of truth assignments: 131415
Size of searchspace (removed): 68 (85)
0.0u 0.0s 0:00 0% 0+0k 0+0io 0pf+0w
========
Date: Fri, 30 Jul 1999
From: Vladimir Lifschitz
To: Mary Heidt
> I have tried to run your formalization of the missionaries and cannibals
> problem on the version of ccalc we have and am unable to get the program
> to run. We get an error message for the line with the rule
>
> :- computed X.
This is a recently added feature, available in Version 1.22. You probably
have an earlier version. If this is so, please download the current
version from the ccalc homepage (see the TAG bibliography for the URL).
> I wanted to compare the run times between your ccalc version and my smodels
> version. The version your sent on July 20 shows run times of 39.83 and
> 74.18 seconds. I have included the output from my formalization for smodels
> below and as you can see the cpu time is 0.0.
That would be pretty hard to beat! We'll look into this and get back to you.
========
Date: Sun, 1 Aug 1999
From: Vladimir Lifschitz
To: Mary Heidt
I'd like to have a better understanding of the role of the control
module in your solution to the missionaries and cannibals problem.
Is it necessary to include that module in order to get a correct
answer, or would smodels produce a solution even without it, although
maybe it would take a bit more time?
===========
Date: Tue, 3 Aug 1999
From: Mary Heidt
To: Vladimir Lifschitz
Smodels will not produce a solution without a control module. The control
module(CM) specifies the set(S) of possible futures an agent should consider
in his plans. Given action description A, history H, goal F, the current
moment tn, length of plan k, under certain conditions, we will have that::
For a1...an in S, m <= k
H |= holds_after(f,[a1...an]) iff
A
occurs(a1,tn),
occurs(a2,t(n+1)),
.
.
occurs(am,t(m+n))
belong to a.s. of A + H + CM.
If we want to allow arbitrary actions we will use the folowing
occurs(ai,t) or occurs(-ai,t) <-- t >= tn, not goal(t).
If we only want sequential plans we can say
occurs(ai,t) or ... occurs(an,t) <-- t >= tn, not goal(t).
If we only want plans in which a1 is followed by a2 we can say
occurs(a2,t+1) <-- occurs(a1,t), t >= tn, not goal(t+1).
In the formalization of the missionaries and cannibals problem we use the
control module to specify two kinds of actions: one in which only one type
of agent crosses the river(the agent can be either one or two missionaries
or cannibals), or the second type of action in which one missionary and one
cannibal cross the river. We have a rule for each action that is allowed.
We believe that our control module improves program efficiency. In Ezra's
paper "Applications of Logic Programming to Planning: Computaitonal
Experiments" she used statements such as:
toggle(L,T) :- latch(L), time(T), not ntoggle(L,T).
so that an action or its negation would occur at every moment of time.
Instead, we are using statements in our control module that specify exactly
what choice of actions exist for an agent at each moment of time until the
goal is reached.
=========
Date: Wed, 11 Aug 1999
From: Vladimir Lifschitz
To: Mary Heidt
I asked you about the role of the control module in your solution to
the missionaries and cannibals problem, and I understood from your
answer that *some* control module is needed. The simplest control
module is apparently the one that says that all actions are allowed
as long as the goal is not achieved:
occurs(ai,t) or occurs(-ai,t) <-- t >= tn, not goal(t).
Let me put my question differently then: Is it true that smodels would
produce a correct answer even with this simplest control module? If so,
would this take noticeably more time?
The reason why I am interested in this is that I think of choosing a
control module other than the simplest possible as an optimization.
As with any optimization, it's important to evaluate its usefulness
by an experimental comparison.
===========
Date: Mon, 16 Aug 1999
From: Mary Heidt
To: Vladimir Lifschitz
Smodels will produce a correct answer with this control module. However,
with this control module it is possible to have moments of time where no
actions occur ( occurs(-ai,t)). This is not allowed with our control
module.
=========
Date: Tue, 17 Aug 1999
From: Vladimir Lifschitz
To: Mary Heidt
> Smodels will produce a correct answer with this control module. However,
> with this control module it is possible to have moments of time where no
> actions occur ( occurs(-ai,t)).
It seems to me that this would not actually happen because your program
includes the constraint
:- not goal(11).
and 11 is the length of the shortest possible solution. Is this right?
=========
Date: Tue, 24 Aug 1999
From: Monica Nogueira and Mary Heidt
To: Vladimir Lifschitz
Regarding your question to Mary Heidt
Vladimir:
> The simplest control module is apparently the one that says that
> all actions are allowed as long as the goal is not achieved:
>
> occurs(ai,t) or occurs(-ai,t) <-- t >= tn, not goal(t).
>
>Let me put my question differently then: Is it true that smodels would
>produce a correct answer even with this simplest control module? If so,
>would this take noticeably more time?
Mary:
>> Smodels will produce a correct answer with this control module. However,
>> with this control module it is possible to have moments of time where no
>> actions occur ( occurs(-ai,t)). I have not had a chance to compare the
>> times.
Vladimir:
> It seems to me that this would not actually happen because your program
> includes the constraint
> :- not goal(11).
> and 11 is the length of the shortest possible solution. Is this right?
we have the following comments:
a. You are right, since 11 is the length of the shortest solution, for all
moments of time at least one action must occur.
However, we can say that Mary chose goal(11) by "luck". She could have not
known the shortest solution would take 11 steps, and could have given goal(12)
instead, in which case the program with the simplest control module would
generate models with moments of time where no action occur.
b. Mary wrote a "simple" control module (which will be referred to as
Non-Optimized
Control Module, versus Optimized Control Module for the original program)
for the missionaries and cannibals example, and this program is attached.
Notice that besides the simpler control module, several new constraints were
added to control the number of passengers allowed to board the boat.
c. I ran some tests to allow us to compare efficiency of these programs. A
summary of these tests is given on the table below.
----------------------------------------------------------
Plan length Non-Optimized CM Optimized CM
#models time(s) #models time(s)
----------------------------------------------------------
11 1 9 1 0
4 9 4 0
----------------------------------------------------------
12 1 11 1 0
48 23 4 0
----------------------------------------------------------
13 1 11 1 0
368 60 60 1
----------------------------------------------------------
14 1 11 1 0
2,240 158 60 1
----------------------------------------------------------
15 1 11 1 0
11,836 434 556 6
----------------------------------------------------------
Obs:
On the table, for each given plan length, the top row shows the time taken to
compute only 1 model, while the second row shows the time taken to compute all
models, for both the non-optimized and the optimized control modules.
Program with the non-optimized controle module:
-----------------------------------------------------------
% Mary Heidt
% cannibals3
% Missionaries and Cannibals problem presented to smodels using
% the simplest control module.
% Three missionaries and three cannibals come to a river and find a boat that
% holds two. If the cannibals ever outnumber the missionaries on either bank,
% the missionaries will be eaten. How can they cross?
agent(cannibal).
agent(missionary).
vehicle(boat).
time(0..15).
next(T,T1):- time(T), time(T1), T1 = T + 1.
const max = 3.
num(0..max).
%-------------------------------------------------------------------------------
% FLUENTS
%-------------------------------------------------------------------------------
%located(X,N) iff N number of type X are located on the first side of the river
%located(A,N):- agent(A), num(N).
%located(O,N):- object(O), num(N).
%-------------------------------------------------------------------------------
% ACTIONS
%-------------------------------------------------------------------------------
%cross(A,N) iff N agent(s)of the type A cross to the opposiste side of the river
%cross(A,N):- agent(A), num(N).
%return(A,N) iff N agent(s)of the type A return to the the original side
%return(A,N):- agent(A), num(N).
%-------------------------------------------------------------------------------
% DYNAMIC CAUSAL LAWS
%-------------------------------------------------------------------------------
%causes(cross(A,N),located(A,N1-N),[located(A,N1)])
holds(located(A,N1-N),T1):- agent(A),
num(N1),
num(N),
next(T,T1),
occurs(cross(A,N),T),
holds(located(A,N1),T).
ab(located(A,N1),T):- agent(A),
num(N),
num(N1),
time(T),
occurs(cross(A,N),T),
holds(located(A,N1),T).
holds(located(boat,0),T1):- next(T,T1),
agent(A),
num(N),
occurs(cross(A,N),T),
holds(located(boat,1),T).
ab(located(boat,1),T):- time(T),
agent(A),
num(N),
num(N1),
occurs(cross(A,N),T),
holds(located(boat,1),T).
%causes(return(A,N),located(A,N1+N),[located(A,N1)])
holds(located(A,N1 + N),T1):- agent(A),
num(N),
num(N1),
next(T,T1),
occurs(return(A,N),T),
holds(located(A,N1),T).
ab(located(A,N1),T):- agent(A),
num(N),
num(N1),
time(T),
occurs(return(A,N),T),
holds(located(A,N1),T).
holds(located(boat,1),T1):- next(T,T1),
agent(A),
num(N),
occurs(return(A,N),T),
holds(located(boat,0),T).
ab(located(boat,0),T):- time(T),
agent(A),
num(N),
num(N1),
occurs(return(A,N),T),
holds(located(boat,0),T).
%-------------------------------------------------------------------------------
% INERTIA
%-------------------------------------------------------------------------------
holds(located(A,N),T1):- agent(A),
num(N),
next(T,T1),
holds(located(A,N),T),
not ab(located(A,N),T).
holds(located(boat,N),T1):- num(N),
next(T,T1),
holds(located(boat,N),T),
not ab(located(boat,N),T).
%-------------------------------------------------------------------------------
% CONSISTENCY
%-------------------------------------------------------------------------------
:- time(T),
holds(located(boat,0),T),
holds(located(boat,1),T).
:- agent(A),
time(T),
num(N),
num(N1),
not eq(N,N1),
holds(located(A,N),T),
holds(located(A,N1),T).
%-------------------------------------------------------------------------------
% CONSTRAINTS
%-------------------------------------------------------------------------------
%it is impossible for more agents to cross than are on the first side
:- agent(A),
num(N),
num(N1),
time(T),
occurs(cross(A,N),T),
holds(located(A,N1),T),
gt(N,N1).
%it is impossible for more agents to return than are on the other side
:- agent(A),
num(N),
num(N1),
time(T),
occurs(return(A,N),T),
holds(located(A,N1),T),
gt(N + N1,max).
%cannibals cannot outnumber missionaries on either side
:- time(T),
num(N),
num(N1),
holds(located(cannibal,N),T),
holds(located(missionary,N1),T),
gt(N,N1),
gt(N1,0).
:- time(T),
num(N),
num(N1),
holds(located(cannibal,N),T),
holds(located(missionary,N1),T),
lt(N1,max),
lt(N,N1).
%agents cannot move if they are not on the same side with the boat
:- time(T),
num(N),
agent(A),
holds(located(boat,0),T),
occurs(cross(A,N),T).
:- time(T),
num(N),
agent(A),
holds(located(boat,1),T),
occurs(return(A,N),T).
%no more than two agents can be in the boat
%this constraint is not in the cannibals program
:- time(T),
num(N),
num(N1),
occurs(cross(cannibal,N),T),
occurs(cross(missionary,N1),T),
gt(N+N1,2).
:- time(T),
num(N),
num(N1),
occurs(return(cannibal,N),T),
occurs(return(missionary,N1),T),
gt(N+N1,2).
:- time(T),
num(N),
occurs(cross(cannibal,N),T),
gt(N,2).
:- time(T),
num(N),
occurs(return(cannibal,N),T),
gt(N,2).
:- time(T),
num(N),
occurs(cross(missionary,N),T),
gt(N,2).
:- time(T),
num(N),
occurs(return(missionary,N),T),
gt(N,2).
%-------------------------------------------------------------------------------
% INITIAL CONDITIONS
%-------------------------------------------------------------------------------
holds(located(cannibal,3),0).
holds(located(missionary,3),0).
holds(located(boat,1),0).
%-------------------------------------------------------------------------------
% CONTROL MODULE
%-------------------------------------------------------------------------------
noccurs(cross(cannibal,N),T):- num(N),
time(T),
not occurs(cross(cannibal,N),T),
gt(N,0),
not goal(T).
occurs(cross(cannibal,N),T):- num(N),
time(T),
not noccurs(cross(cannibal,N),T),
gt(N,0),
not goal(T).
noccurs(return(cannibal,N),T):- num(N),
time(T),
not occurs(return(cannibal,N),T),
gt(N,0),
not goal(T).
occurs(return(cannibal,N),T):- num(N),
time(T),
not noccurs(return(cannibal,N),T),
gt(N,0),
not goal(T).
noccurs(cross(missionary,N),T):- num(N),
time(T),
not occurs(cross(missionary,N),T),
gt(N,0),
not goal(T).
occurs(cross(missionary,N),T):- num(N),
time(T),
not noccurs(cross(missionary,N),T),
gt(N,0),
not goal(T).
noccurs(return(missionary,N),T):- num(N),
time(T),
not occurs(return(missionary,N),T),
gt(N,0),
not goal(T).
occurs(return(missionary,N),T):- num(N),
time(T),
not noccurs(return(missionary,N),T),
gt(N,0),
not goal(T).
%-------------------------------------------------------------------------------
% GOAL
%-------------------------------------------------------------------------------
goal(T):- time(T),
holds(located(missionary,0),T),
holds(located(cannibal,0),T).
:- not goal(12).
hide holds(X,Y).
hide ab(X,Y).
hide time(T).
hide num(N).
hide agent(A).
hide next(X,Y).
hide goal(X).
hide vehicle(X).
hide noccurs(X,Y).