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).