CSE2AIF – Artificial Intelligence Fundamentals 2019 Individual Assignment 1
Due Monday 2nd September 2019, 9:00am General Information
This assignment is to be done individually, and contributes 10% of your final mark for this subject. The submission date for the assignment is Monday 2nd September 9:00am. Submission is electronic. Details of what to submit are provided below. Make sure that you follow the directions carefully and that the files are named exactly as specified in the instructions.
The assignment is to be done individually. This means that answers to questions, and code that you write must be your own. You must not collude with other students in any way, and you must not outsource your work to any third party. For information on plagiarism, see the La Trobe University policy on academic misconduct at http://www.latrobe.edu.au/students/learning/academic-integrity. Plagiarism is treated very seriously. Penalties will be applied and are strictly imposed.
Solving the Missionaries and Cannibals Problem using State Space Search
The Missionaries and Cannibals problem is another classic river-crossing problem. One version of the problem goes as follows:
Three missionaries and three cannibals are on the east side of a river. They have a boat which is big enough to carry at most two people. For both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals, since the cannibals would eat the missionaries. The boat cannot cross the river by itself with no people on board. How can all missionaries and cannibals get to the other side alive?
Other versions of the problem vary the number of missionaries and cannibals, or the number of persons that the boat can hold. Some even put an island in the river. For this assignment, we will consider only the case of three missionaries and three cannibals, and a boat which can hold at most two persons.
Part 1 – Choosing an appropriate representation
As mentioned in lectures, how you choose to represent states can be critical in determining whether a solution to the problem can be found.
Consider the following two representation schemes: Scheme 1:
A state is represented as a list containing five elements. The first element represents the number of missionaries on the east bank; the second represents the number of cannibals on the east bank; the third represents the number of missionaries on the west bank; the fourth represents the number of cannibals on the west bank; the fifth represents the location of the boat, which can either be east or west. Under this representation the initial state would be represented as (3 3 0 0 east).
Note that we could obviously get away with a list of only three elements; e.g., number of missionaries on east bank, number of cannibals on east bank, and position of boat. This is because the number of missionaries and cannibals on the west bank could be determined from
this. While using a list of length five involves some redundancy, it could result in cleaner, more readable, code.
Scheme 2:
Another approach is to treat each of the actors individually, i.e., m1, m2, m3, c1, c2, c3, boat. Under this scheme, a state could be represented using a list of length seven, where the first element represents the position of the first missionary (east or west), the second element represents the position of the second missionary, and so on. The seventh element would represent the position of the boat.
Questions:
1. What is the smallest number of distinct operators required under Scheme 1? List these operators using meaningful names.
2. What is the smallest number of distinct operators required under Scheme 2? List these operators using meaningful names.
3. Why would Scheme 1 be preferred for this problem? (Don’t just say that Scheme 1 uses smaller lists – provide some sort of informal analysis of the search trees that would be expected to result from the two approaches, e.g., in terms of average branching factor).
4. Sketch the first four levels (i.e., root node plus next three levels) of the breadth-first-search search tree resulting from Scheme 1. Make sure that you indicate the state corresponding to each node, and the operators that have been applied to move from one state to another. Do not include illegal states, or states that have already been visited. Assume that operators are applied in the order in which you have listed them in Question 1 above.
Part 2 – Writing the code
Now write LISP code which uses the representation described above in Scheme 1 above to find a solution to the problem using breadth first search.
You have been supplied with LISP code for breadth first search. The code is contained in the file bfs.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 mc.lisp.
The code in mc.lisp must contain:
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*.
You can, and are encouraged to, write any number of helper functions which are called by the
functions above.
As well as correctly solving the problem, your code must display good programming style:
appropriate function and parameter naming;
appropriate use of local symbol definitions (i.e., let blocks);
appropriate use of state constructor and accessor functions;
appropriate use of helper functions;
appropriate and consistent documentation;
appropriate and consistent indentation that reflects logical structure of the code.
Use the slides in the file ‘State Space Search – Using the supplied LISP code.pdf’ as a guide to what is expected in terms of style.
Testing
You may wish to write a function which will load all required files, and then runs your program. You could do this as follows:
(defun test()
(load ‘bfs)
(load ‘mc)
(breadth-first-search *start-state* *operators*)
)
You would then simply evaluate the expression
[1]> (test)
Your code will be tested in this way, so make sure that it loads and runs correctly.
Marking Criteria
Your solution will be marked according to the following criteria:
Correct answers to questions from Part 1 (5 marks)
LISP code that finds correct solution (10 marks)
Programming style (5 marks)
Submission
Submission is electronic only, and must be submitted using the CSE2AIF LMS site. You must submit the following THREE files:
A word file named PartA.doc that contains answers to questions in Part A. (The file must contain your name and student number)
A file mc.lisp that contains LISP code for the following:
Definition of a global variable *start-state*
Definition of a predicate solution-state?
Definition of the global variable *operators*
Function definitions for each of the operators listed in *operators*
Definition of any helper functions used
The file MUST include your name and student number in the header documentation.
DO NOT make any changes to the file bfs.lisp, and DO NOT include any of the functions
from bfs.lisp in your submission.
A file mc-run.txt. This file should be a plain text file showing a run of your program. You can capture a run of the program using dribble (see instructions below). Edit the file to include your name and student number in the header documentation.
Directions for capturing a session using CLISP
The function dribble can be used to capture a session with the CLISP interpreter to a text file. To begin capture, call the function dribble with the double-quoted filename as an argument (if a file with that filename does not exist, it will be created; otherwise, the session will be appended to the end of it). For example, the following command
[1]> (dribble “sample.txt”)
will cause the session to be captured to the file sample.txt. When you want to stop dribbling, call the function dribble without any arguments.
[10]> (dribble)