Part A - State Space Search using LISP

This part of the assignment requires you to solve the following problem using the LISP computer programming language:

A merchant has a beaker containing 24 ounces of a precious fluid. He also has empty 5-ounce, 11- ounce, and 13-ounce beakers. How can he divide the fluid into three equal portions?

For this part of the assignment you are required to solve this problem as a state space search problem using the A-star algorithm that has been described in lectures.

You have been supplied with LISP code for A-star search. The code is contained in the file a-star.lisp. You should not make any changes to the code in this file. All the problem-specific code you write should be contained in a file called precious.lisp.

The code in precious.lisp should contain only the following:

  Definition of a global variable *start-state* whose value represents the initial state.

  Definition of a global variable *operators* which lists the names of the operators.

  Definition of a predicate solution-state? that takes a state as argument and returns T if that state is a solution, and nil otherwise.

  Function definitions for each of the operators listed in *operators*.

  Definition of a function cost-of-applying-operator that takes a state and an operator as arguments, and returns the cost of applying the operator to that state. We will assume that all costs are equal, and hence this function should always return 1, irrespective of the state or the operator.

  Definition of a function estimated-distance-from-goal that takes a state as an argument, and returns an estimate of the number of steps required to get from this state to the goal. Note that this function will determine the number of states examined in the search-the fewer the better. You can, of course, write any number of helper functions which are called by the functions above.

Compare the performance of A-star search (using the heuristic you have defined) with the performance of breadth first search. You should compare the number of states examined, the length of the solution and the maximum depth of the search tree. You can obtain this information by examining the value of the variable *stats* after the search has completed.

Notes:
  Using A-star search with a heuristic that evaluates all states as 0 results in a breadth first search. In order to run breadth first search, all you need to do is replace the function estimateddistance- from-goal with the following:

(defun estimated-distance-from-goal (state) 0)

  Don't forget to reset the value of *stats* before running the search again.

Write a short report on your findings (approx. 150 words). The report should contain a table that compares the number of states examined, the length of the solution, and the maximum depth of the search tree.

Part B - State Space Search using Prolog

This part of the assignment requires you to solve the following problem using the Prolog computer programming language:

Ten cannibals and ten missionaries come to the left bank of a crocodile infested river, where there is a boat that can be used by one or two persons. There is an island in the middle of the river. If cannibals outnumber the missionaries at any time, the cannibals eat the missionaries. How can they use the boat to cross the river so that all missionaries survive? All trips must be either to or from the island; i.e., crossings directly from bank to bank are not allowed.

For this part of the assignment you are required to solve this problem as a state space search problem using the best-first-search algorithm.

You have been supplied with two Prolog files: adts.pl and bfs.pl. The file adts.pl contains Prolog code implementing various abstract data types. The file bfs.pl contains code that can be used to perform bestfirst- search in Prolog. Note that the file bfs.pl consults adts.pl.

For this task you are required to write Prolog code to solve the missionaries and cannibals problem. To assist you, two example files have been made available on the LMS: fwgc.pl and jugs.pl, which implement the farmer, wolf, goat and cabbage problem, and the water jugs problem, respectively. Note that these files contain all of the code in bfs.pl, in addition to the problem-specific operators, coded in a procedure move(Current_State, Next_State). It is suggested that you study the code in these files before commencing your solution to the missionaries and cannibals problem.

In addition to outputting the sequence of steps required to move from the start state to the goal state, your code should also show the total number of states examined (i.e., the sum of the number of states on the Open and Closed lists), the maximum depth of the search tree, and the length of the solution. All code (with the exception of code in the file adts.pl) should be contained in a file called mc.pl.
Procedures that you will need to include in mc.pl are:

  A procedure move(Current_State, Next_State) that described the problem solving operator for moving from Current_State to Next_State .

  A procedure heuristic(State, Goal, H) where state is the state being evaluated, Goal is the goal state, and H is the heuristic evaluation for state. (Note that bfs.pl contains the procedure heuristic(State, Goal, 0).

This assigns a H value of 0 to every state, and thus results in breadth first search. You should replace this with a procedure that implements your proposed heuristic).

  Procedures to find the the total number of states on the Open and Closed lists, the maximum depth of the search tree, and the length of the solution.

  Any helper procedures required. (For example, you may wish to write a procedure unsafe(State) that returns False if state State is unsafe (i.e., if the number of cannibals at any location outnumber the number of missionaries at that location).

Compare the performance of A-star search (using the heuristic you have defined) with the performance of breadth first search. You should compare the number of states examined, the length of the solution and the maximum depth of the search tree.

Write a short report on your findings. The report should contain a table that compares the number of states