UNIVERSITY OF TEXAS AT ARLINGTON DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
4308/5360 ARTIFICIAL INTELLIGENCE I FALL 2018
PROGRAMMING ASSIGNMENT (100 POINTS) ASSIGNED: 10/30/2018 DUE: 11/27/2018
The programming assignment consists of the following problems:
- (50 points) Write Lisp code that solves the missionaries and cannibals problem assuming that you have one boat, 15 cannibals, and 15 missionaries. Assume that the boat can carry at most six people and there is a single boat available. You cannot have the boat moving with no one onboard. The cannibals should never outnumber the missionaries (either on the boat or at both sides of the river). You can write your own code or modify the code from the course textbook website to solve the problem. You need to print out the sequence of moves leading to a correct solution. Try the same problem with 20 cannibals and 20 missionaries. You should not hard-code your solution.
- (50 points) Implement the A* algorithm for searching trees in Lisp. Do not use the course textbook website code or other code from the Internet. Implement a counter that counts the number of nodes expanded and prints this number at the end of the search. Use your code to solve the 8-puzzle problem with the heuristic being the number of misplaced tiles and start state ((E, 1, 3), (4, 2, 5), (7, 8, 6)). The
goal state is: ((1, 2, 3), (4, 5, 6), (7, 8, E)). Print the number of nodes expanded. You only need to show the states generated during the search process. Your code should detect infeasible puzzles.
Sample Lisp code for the first problem can be found at https://github.com/aimacode/aima-lisp
The programs must be written in ANSI Common Lisp (see the class lecture slides on Lisp). The development of the programs can be done on the machine of your choice, however the source code must compile and run using CLISP. You should create a Lisp script that invokes the necessary functions to solve the problems and displays the output to the terminal.
You need to submit a .zip/.tgz file containing all the source code to run the programs along with a report. The report must contain the following items: a title page (including your name and student ID number), an implementation description of the programs, known bugs and deficiencies, a description of how to run the programs, and the terminal session script output. The weight distribution for the assignment is 80% for correctness and 20% for the report.
You should work on this assignment individually and not in groups. Finally, I suggest that you start the assignment as early as possible.
1