CS 3304 Project #3
The Farmer/Fox/Chicken/Grain Problem You have probably heard this simple logic puzzle before:
A farmer is returning to his farm a!er a long day of working in the fields. He has with him a fox, a chicken, and some grain. He must cross a small stream on his way back to the barn. At the stream, there is a canoe, in which he can transport at most one item across at a “me. However, he cannot leave the fox alone with the chicken, or the fox will eat the chicken. Similarly, he cannot leave the chicken alone with the grain because the chicken will eat the grain. Devise a plan (sequence of ac”ons) that the farmer can take to safely bring all of his possessions across the stream and con”nue on his way home.
The farmer/fox/chicken/grain problem (FFCGP) is a classic planning problem. A planning problem is one where, given the current state of the world (i.e., the farmer and all three items on this side of the stream and nothing on the other side of the stream), you must devise a plan—a series of ac!ons that can be carried out in order—to get to a desired goal situa!on (i.e., nothing on this side of the stream and the farmer and all three items on the other side). Further, in order for your plan to work, it must sa!sfy a set of constraints. In this case, at no !me during the sequence of ac!ons can the fox be le” alone with the chicken, or the chicken be le” alone with the grain.
You job is to build a simple planning engine which can solve the FFCG problem and similar problems of the same nature. A similar planning problem you may have also run across is the explorers and dinosaurs problem (EDP):
Three explorers and three dinosaurs come to a river and find a boat that holds two. If the dinosaurs ever outnumber the explorers on either bank, the explorers will be eaten. How shall they cross?
Implementa!on Language and Guidelines
The implementa!on language for this project is Prolog. You will be programming in a logical programming style, as described in Chapter 16 of your textbook. Since this program must be wri#en in Prolog, appropriate use of logic and declara”ve language features is expected. Your implementa!on must adhere to the tenets of logic and declara!ve programming. In addi!on, your program must u!lize recursion and to the fullest extent. You may not use any versions of assert , retract , record , erase , flag , or any of the other database features of Prolog. You may use the predicates we used and developed in class.
As with prior programs, your solu!on must adhere to good programming style, including correct use of parameter passing, iden!fier naming, predicate length, commen!ng, and headers for each predicate.
Input and Output Format
Write your program as a Prolog predicate called plan_transport which matches the following signature:
plan_transport( Initial_State,
Goal_State,
Set_of_Invalid_Combinations,
Drivers,
Max_Plan_Length,
Plan ) :-
/* your definition goes here */.
This predicate defines acceptable plans for transpor!ng a given set of objects (the farmer and his items, a set of dinosaurs and explorers, or a collec!on of space colonists and their supplies) from one loca!on to another using a vehicle (boat, space ship, airplane). Without loss of generality, let’s call the two loca!ons the “le”” loca!on and the “right” loca!on. Then the Initial_State is a two-item list which describes the set of objects at the le” loca!on and the set of objects at the right loca!on. For the FFCGP where all items start on the le” side and nothing is on the right, we can describe the ini!al state as:
[ [ farmer, fox, chicken, grain ], [] ]
Note that order does not ma!er in lis!ng the items on either side. We can also leave one or more por!ons of the ini!al state or goal state unbound, either to see what is “reachable” from a given start state or to see where we “might have come from” if the goal state is specified. At a minimum, however, all known objects must be listed in the union of both sides of both the ini!al and goal states. Similarly, the Goal_State defines the final configura!on at which we wish to arrive (with everything moved to the right):
[ [], [ farmer, fox, chicken, grain ] ]
The Set_of_Invalid_Combinations is a list, each element of which is a set of items that cannot be le” together. For example:
[ [ fox, chicken ],
[ chicken, grain ],
[ chicken, fox, grain ] ]
Again, order does not ma!er in an invalid combina!on. Lis!ng [fox, chicken] as an invalid combina!on precludes any situa!on throughout the whole plan where either loca!on contains exactly those two items (in either order, if lists are used to record the items on each side). The Set_of_Invalid_Combinations is a required parameter, and must not be unbound.
The Drivers parameter is also required to be bound. It is a simple list of objects (atoms). Every !me the transport vehicle moves from one loca!on to another, at least one of the objects in this list must be in it (i.e., there must be a legi!mate Driver from this list to pilot the transport vehicle).
The Max_Plan_Length is also required to be bound and must be a non-nega!ve integer. Any legi!mate Plan must contain Max_Plan_Length moves or fewer.
If plan_transport is called with an unbound variable provided for the Plan , then a sa!sfactory plan will be generated. Through backtracking, all possible legal plans should be generated. If a bound value is provided for the Plan , then the predicate will succeed if the given plan sa!sfies the constraints (including Max_Plan_Length ) and fail otherwise.
To put the pieces of the FFCGP example together, your planner might be called as follows:
?- plan_transport( [ [ farmer, fox, chicken, grain ], [] ],
[ [], [ farmer, fox, chicken, grain ] ],
[ [ fox, chicken ],
[ chicken, grain ],
[ chicken, fox, grain ] ],
[ farmer ],
10,
Plan ).
Then a legal plan follows this syntax (white space added for readability and lets use Prolog canonical ordering):
Plan = [ [ go_right, farmer, chicken ],
[ go_left, farmer ],
[ go_right, farmer, fox ],
[ go_left, farmer, chicken ],
[ go_right, farmer, grain ],
[ go_left, farmer ],
[ go_right, farmer, chicken ] ]
Plan = [ [ go_right, chicken, farmer ],
[ go_left, farmer ],
[ go_right, farmer, fox ],
[ go_left, chicken, farmer ],
[ go_right, farmer, grain ],
[ go_left, farmer ],
[ go_right, chicken, farmer ] ]
A plan is a list of moves. Each move is itself a list star!ng with go_right or go_left and followed by one or two items being transported. Without loss of generality, at the start of the plan the transport vehicle always starts at the le# loca”on. Further, every move must include at least one Driver (from the Drivers list) and at most one other object. The plan shown above is one 7-move plan which sa!sfies the problem. It is not the only solu!on sa!sfying the constraints.
Framing the EDP in this style is le” as an exercise for your tes!ng.
Note that your solu!on need not write any results. You are simply wri!ng a predicate which will succeed or fail, and that may bind
its parameters (e.g., the Plan ) as a byproduct.
Also, your solu!on need not find the shortest plan first, or generate plans in any specific order. However, your solu!on must be able to generate all possible unique plans which sa!sfy the constraints through backtracking. In other words, it must be complete. There is a 1-minute !me limit on the execu!on of your program against our test data on Web-CAT.
Also, your predicate can simply fail for logically inconsistent inputs (e.g., the same atom is listed on both sides in the ini!al state or on both sides in the goal state, atoms appearing in one state are not present in the other, a bound non-nega!ve value is not provided for Max_Plan_Length , a bound value is not provided for the set of invalid combina!ons, no plan sa!sfying the constraints exists, etc.).
Tes!ng and Submi$ng Your Program
Recall that you can ¡°read¡± in Prolog predicates from a file, by typing ¡°[filename].¡± inside the SWI-Prolog session; You can then test the loaded predicates. Alterna!vely you can create a separate Prolog program to load your program file and run a series of test cases in one stroke. For example, consider a file named triple.pl containing the Prolog predicate triple/2 . In order to streamline tes!ng this predicate, one may create the following file, named tests.pl .
[triple].
triple([1], X).
triple([1,2], X).
triple([1,2,3], X).
triple([1,2,3,4], X).
triple([1,2,3,5], X).
…
…
Now to run the several test cases contained in tests.pl in batch, you can enter ¡°swipl < tests.pl¡± at the UNIX command prompt.
Your Prolog program is to be organized and submi!ed electronically as a single file through the Canvas. All documenta!on and iden!fying informa!on should be placed in comments within the single source file. The comments at the beginning of the file should iden!fy the assignment and give your full name. Every Prolog predicate should be preceded by comments explaining its purpose, the meaning of each parameter, and the general strategy of its implementa!on if applicable. 80% of the score comes from correct implementa!on and execu!on; 20% of the score comes from (logical and declara!ve) programming style, sound design, and good coding principles (comments, readability). All work on this project is to be your own. There are no group projects in this course.
FAQ
Q: Are we allowed to use built-in Prolog predicates?
A: You bet, as long as they do not mimic impera!ve programming constructs. There is a complete list of built-in predicates in Sec!ons E.1 and E.2 of the SWI-Prolog reference manual (linked under our project spec) You may find the following list of allowable, built-in predicates par!cularly useful.
var/1 -- Type check for unbound variable
nonvar/1 -- Type check for bound term
ground/1 -- Verify term holds no unbound variables
free_variables/2 -- Find unbound variables in a term
setof/3 -- Find all unique solutions to a goal
@.
the answer P is thus bound inside
just change it to:
plan_transport(…, …, …, …, …, SP) :-