COSC 270 Project 2

COSC 270: Artificial Intelligence

Project 2
Spring 2015

Due: ~~Thu, Feb 12~~ Sun, Feb 15 @ 11:59 P.M.
7 points

Inspired by Berkeley's Pac-Man Projects, in this project, you'll implement four search algorithms for finding solutions in mazes.

Make sure your function load-maze-problem from p1 works on the following mazes:
For convenience, I've placed all of these mazes in a zip file. There is also a copy of this file on cs-class, which you can copy by executing
```
cs-class% cp ~maloofm/cosc270/mazes.zip ./
```
For the maze problem, implement the problem-specific functions
- successors problem state ⇒ ((successor action action-cost)* ),
- make-child node successor⇒ (state path path-cost),
- goal-test problem state ⇒ [ t | nil ],
- h node goal ⇒ Number, and
- f node goal ⇒ Number.
Recall that g node ≡ path-cost. Put these functions in a file named maze.lisp.
Use these functions to implement
1. breadth-first search as the function bfs,
2. uniform-cost search as the function ucs,
3. greedy best-first search as the function gbfs, and
4. A* as the function a*.
As we discussed in lecture, each search function should take a problem as its argument and return a pair consisting of the solution (i.e., a sequence of actions) and the solution's cost. Put these functions in a file named search.lisp
It is imperative that you name and implement these functions correctly. To grade your project, I will use my own functions to automatically call and evaluate your implementations. I will of course evaluate them on the mazes I've provided, but I'll also use additional mazes. I will also evaluate your implementations using a different search problem.
Clearly, if you haven't named or implemented these functions correctly, then my routines won't work with your code. You should think about other types of mazes I might use and the special cases your search routines might need to handle. As a simple example, how do your implementations handle the case that the goal state of a maze is not reachable from the initial state?
All variables must be either a function parameter or locally scoped in let or do forms. Your implementations must not rely on global variables and must not litter memory with global variables as they execute. If you use a global variable, it must be passed into functions, and your functions must not access these global variables directly.
For each algorithm, instrument a copy of the functions named function-stats (e.g., bfs-stats) and compute over the mazes:
1. the average number of nodes entered (i.e., explored)
2. the average number of nodes expanded (i.e., the total number of successors)
3. the average number of nodes maintained (i.e., stored)
4. the average number of times it found the optimum
Place these results in comments at the top of the file maze.lisp.

Instructions for Electronic Submission

In the header comments of the primary file, provide the following information:

;;;;
;;;; COSC 270 Project 2
;;;; Name
;;;; E-mail Address
;;;; Platform: Windows, Linux (cs-class), etc.
;;;; Lisp Environment: clisp, sbcl, cmucl, gcl
;;;;
;;;; In accordance with the class policies and Georgetown's Honor Code,
;;;; I certify that, with the exceptions of the course materials and those
;;;; items noted below, I have neither given nor received any assistance
;;;; on this project.
;;;;

Use Blackboard to submit your assignment. Put the files search.lisp and maze.lisp in a directory or folder with the same name as your Net ID. Zip up the folder, and upload the zip file for assignment p2 on Blackboard. If you need to include a message with your submission, use Blackboard's comment field.