Consider the following well-known problem:
 

In his yard, a farmer has a fox, a hen, and a bushel of grain. The farmer must transfer all these things to a stall at the market, using only a cart which can carry at most one of them (plus himself) at a time. The problem is that if the farmer leaves the fox unattended with the hen, it will eat the hen. Similarly, if the hen is left unattended with the grain, it will eat the grain.

Is there a way for the farmer (without helpers) to transfer all three items to market without any of them getting eaten?

Use Prolog to solve this as a planning problem using the plan predicate. A state can be represented by a list with four elements, [fox, hen, grain, cart], where each of these elements is a location: either yard or market. (Assume that the farmer is always with the cart.) A move is either go_alone(loc) or go_with(item, loc) where loc is a location and item is one of fox, hen, or grain. A move should not be legal if something will get eaten in the resulting state.

a. Define a predicate safe_state(s) that holds whenever s is a state where nothing will be eaten. So [yard,yard,market,yard] is considered to be a safe state, but [yard,market,market,yard] is not because the hen is with the grain unattended.

b. Define the predicate legal_move using the safe_state predicate.

c. Define initial_state and goal_state, and use the plan predicate to find a seven-step solution.

The answer for the above question given below.. To the best of my knowledge..

Step-by-step explanation

Ans) The Farmer/Fox/Chicken/Grain Problem

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.

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 missionaries and cannibals problem (MCP):

Implementation Language and Guidelines

The implementation language for this project is Prolog. You will be programming in a logical programming style. Since this program must be written in Prolog, appropriate use of logic and declarative language features is expected. Your implementation must adhere to the tenets of logic and declarative programming. In addition, your program must utilize 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.

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 transporting a given set of objects (the farmer and his items, a set of cannibals and missionaries, or a collection of space colonists and their supplies) from one location to another using a vehicle (boat, space ship, airplane). 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 which 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 and lets use Prolog canonical ordering):

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

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 which satisfy the constraints through backtracking. In other words, it must be complete. There is a 1-minute time limit on the execution 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 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.).

Testing and Submitting 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. Alternatively 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 from homework #8. In order to streamline testing 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 "pl < tests.pl" at the UNIX command prompt.