You have probably heard this simple logic puzzle before:
A farmer is returning to his farm after 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 time. 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 actions) that the farmer can take to safely bring all of his possessions across the stream and continue 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 actions that can be carried out in order--to get to a desired goal situation (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 satisfy a set of constraints. In this case, at no time during the sequence of actions can the fox be left alone with the chicken, or the chicken be left alone with the grain.
You job is to build a simple planning engine that can solve the FFCG problem and similar problems of the same nature. A similar planning problem you may have also run across is the missionaries and cannibals problem (MCP):
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?
For this assignment,
the implementation language is Prolog. You will be programming
in a logical programming style, as described in Chapter 16 of the text
book. Since this program must be written in Prolog, appropriate use of
logic language features is expected. In particular, you
may not use any versions of assert, retract,
record, erase, flag, or any
of the other database features of Prolog.
As with prior programs, your solution must adhere to good programming style, including correct use of parameter passing, identifier naming, predicate length, commenting, headers for each predicate, etc.
As you work through this assignment, you may find the following resources useful:
Write your program as a Prolog predicate called
plan_transport
that 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 transporting a given
set of objects (the farmer and his items, a set of
cannibals and missionaries, a collection of space colonists and
their supplies, etc.) from one location to another using a
vehicle (boat, space ship, airplane, etc.).
Without loss of
generality, let's call the two locations the "left" location and
the "right" location.
Then the Initial_State is a two-item list that
describes the set of objects at the left location and the set
of objects at the right location. For the FFCGP where all items
start on the left side and nothing is on the right, we can describe the
initial state as:
[ [ farmer, fox, chicken, grain ], [] ]
Note that
order does not matter in listing the items on either side.
We can also leave one or more portions of the initial 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 initial and goal states.
Similarly, the Goal_State defines the final configuration
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 left together. For example:
[ [ fox, chicken ],
[ chicken, grain ],
[ chicken, fox, grain ] ]
Again,
order does not matter in an invalid combination. Listing
[fox, chicken] as an invalid combination precludes
any situation throughout the whole plan where either location
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 time the transport
vehicle moves from one location to another, at least one of the
objects in this list must be in it (i.e., there must be a legitimate
Driver from this list to pilot the transport vehicle).
The
Max_Plan_Length is also required to be bound
and must be a non-negative integer.
Any legitimate Plan must contain Max_Plan_Length
moves or fewer.
If plan_transport is called with an
unbound variable provided for the Plan, then a satisfactory
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
satisfies 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):
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 ] ]
A plan is a list of moves. Each move is itself a list starting
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 left location. 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 that satisfies the problem. It is not the only
solution satisfying the constraints.
Framing the MCP in this style is left as an exercise for your testing.
Note that your solution need not write any results.
As with the Scheme function in Program Assignment #2, you are simply
writing a predicate that will succeed or fail, and that may bind
its parameters (e.g., the Plan) as a byproduct.
Also, your solution need not find the shortest plan first, or generate plans in any specific order. However, your solution must be able to generate all possible unique plans that satisfy the constraints through backtracking. There is a 1-minute time limit on the execution of your program against your own test data on the Curator.
Also, your predicate can simply fail for logically inconsistent inputs (e.g., the same atom is listed on both sides in the initial state or on both sides in the goal state, atoms appearing in one state are not present in the other, a bound non-negative value is not provided for Max_Plan_Length, a bound value is not provided for the set of invalid combinations, no plan satisfying the constraints exists, etc.).
In addition to writing your program, you will also need to write a set of test cases that demonstrate that your program works correctly. The Curator-assessed portion of your program grade will depend on all three of these factors:
The correctness of your test cases (each test case must have the right expected output)
The thoroughness of your test cases (together, they must exercise all behaviors required by this assignment)
The correctness of your program (it must pass all your test cases)
Review the test case input guidelines to see the format for your test cases. The FFCGP example for plans of length up to 7 could be phrased as a test case like this:
//==
plan_transport( [ [ farmer, fox, chicken, grain ], [] ],
[ [], [ farmer, fox, chicken, grain ] ],
[ [ fox, chicken ],
[ chicken, grain ],
[ chicken, fox, grain ] ],
[ farmer ],
7,
Plan )
//--
[ 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, farmer, chicken ],
[ go_left, farmer ],
[ go_right, farmer, grain ],
[ go_left, farmer, chicken ],
[ go_right, farmer, fox ],
[ go_left, farmer ],
[ go_right, farmer, chicken ] ]
]
Here, the input section of the test case is the Prolog goal to
satisfy.
The output section contains a list of one or more solutions separated
by commas.
Each solution is a list of Variable = Value pairs giving
the value for each unbound variable listed in the Prolog goal.
Not that neither the order of the solutions in the output section
nor the order of the variables within a solution (if the goal contains more
than one unbound variable) matter in the comparison.
If the goal has no solution, simply list fail
as the expected output. If the goal contains no unbound variables but
should still succeed, list true as the
expected output. An empty output section will be interpreted the same
as fail.
Combine all of your test cases into a single ASCII file to submit to the Curator along with your program. In addition, you can use the tddplg.pl tool to run test cases on your own machine.
Your Prolog implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Prolog predicate should be preceded by a comment block explaining its purpose, the meaning of each parameter, and the general strategy of its implementation if applicable.
In addition to your Prolog source file, you will also need to submit a plain ASCII file containing your test cases.
Your program and test case file will be both be submitted electronically through the Web-CAT Curator for automatic grading. The Web-CAT Curator will grade one half of your program score (50 points), as well as assess any deductions based on the late policy described in the syllabus. The TA will assess the remaining 50 points based on the program grading criteria. There is no need to print or turn in a hard copy version of your program; the TA will mark up a PDF version of your program and e-mail it back to you.