15-381: Task I - Problem Spaces and Search

Version date: 8-sep-94 9:25am

Instructions

For each part, write the appropriate Lisp code, run it on your computer, and make a single file containing:

1. Your Lisp code for problem 1
2. An output log from problem 1, not more than one page or 60 lines of trace and results for each run.
3. Your Lisp code for problem 2
4. An output log from problem 2, not more than one page or 60 lines of trace and results for each run.
5. Your Lisp code for problem 3
6. An output log from problem 3, not more than one page or 60 lines of trace and results for each run.

Handing it in

	/afs/andrew/scs/cs/15-381/handin/userid

If you do not have an andrew account, please send the file by email to

	dredish@cs.cmu.edu

The homework is due by 10:30am, Thursday September 22, 1994.

1. Depth First and Breadth First Search (5pts of 15)

(dfs state maxdepth maxnodes) and
(bfs state maxdepth maxnodes),

(new-states state) and
(goalp state),

Your program must print the following information:

1. Either a path of states from the start state to a goal state, or a statement that no path was found.
2. The maximum depth searched.
3. The total number of nodes searched.
4. The average branching factor for the problem.

;;; One problem space representation for the water jug problem

(setq *start* '(0 0))

(defun first-jug (state) (car state))
(defun second-jug (state) (cadr state))
(defun mk-state (f s) (list f s))

(defun goalp (state)
    (eq (first-jug state) 2))

(defun new-states (state)
    (remove-null
	(list
	    (fill-first state)
	    (fill-second state)
	    (pour-first-second state)
	    (pour-second-first state)
	    (empty-first state)
	    (empty-second state))))

(defun remove-null (x)
    (cond
	((null x) nil)
	((null (car x)) (remove-null (cdr x)))
	((cons (car x) (remove-null (cdr x))))))

(defun fill-first (state)
    (cond
	((< (first-jug state) 4) (mk-state 4 (second-jug state))))))

(defun fill-second (state)
    (cond
	((< (second-jug state) 3) (mk-state (first-jug state) 3))))


(defun pour-first-second (state)
    (let (   (f (first-jug state))
	     (s (second-jug state)))
	(cond
	    ((zerop f) nil)		; Cant pour nothing
	    ((= s 3) nil)		; Second full
	    ((<= (+ f s) 3)		; Empty first into second
		(mk-state 0 (+ f s)))
	    (t				; Fill second from first
		(mk-state (- (+ f s) 3) 3)))))

(defun pour-second-first (state)
    (let (   (f (first-jug state))
	     (s (second-jug state)))
	(cond
	    ((zerop s) nil)		; Cant pour nothing
	    ((= f 4) nil)		; First full	    
	    ((<= (+ f s) 4)		; Empty second into first
		(mk-state (+ f s) 0))	    
	    (t				; Fill first from second
		(mk-state 4 (- (+ f s) 4))))))

(defun empty-first (state)
    (cond
	((> (first-jug state) 0) (mk-state 0 (second-jug state)))))

(defun empty-second (state)
    (cond
	((> (second-jug state) 0) (mk-state (first-jug state) 0))))

2. Problem Spaces (5pts of 15)

(new-states state) and
(goalp state),

You and a friend are at the entrance to a fabulous ball room with a large party going on. Although neither of you has brought formal wear, upon entering the Foyer (and seeing a tastefully engraved sign that the main party is in the Checkered Room), you are told politely but firmly that you may not enter the main rooms without a jacket and tie, but that the establishment will loan you each ties and jackets during your visit. There is one white jacket, one white tie, one black jacket, and one black tie (four pieces of clothing altogether). The rooms are layed out as follows:

Either player may make the following moves in this game:

1. You may pick up and put on a jacket, if you are not already wearing one.
2. You may take off and drop a jacket, if you are wearing it.
3. You may pick up and put on a tie, if you are not already wearing one.
4. You may take off and drop a tie, if you are wearing it.
5. You may move from the current room along the gray arrows into an adjacent room, if you meet the dress code for that room.

Items dropped in a room stay in that room, and may be picked up by the other player.

Your goal is to produce a series of moves that get one player into the checkered room where the main party is in full swing.

Using the lisp functions new-states and goalp, along with your DFS and BFS functions, solve the problem and note the solution lengths and nodes visited in each case.

3. Heuristic Search (5pts of 15)

(new-states state) and
(goalp state), (heur-value state)

Also write a best-first search routine

(best-first state maxdepth maxnodes)

Use all of your search functions to transform the initial state

		|	|
	    1	|   2   |   3
		|	|
	--------+-------+--------
		|	|
	    4	|   5   |   6
		|	|
	--------+-------+--------
		|	|
	    7	|   8   |   
		|	|

into the goal state:

		|	|
	    1	|   8   |   7
		|	|
	--------+-------+--------
		|	|
	    2	|       |   6
		|	|
	--------+-------+--------
		|	|
	    3	|   4   |   5
		|	|

For a simple heuristic, try adding the number of squares that are in the final location. Try at least one other heuristic function, and compare the path length and number of nodes searched for breadth-first search, depth-first search, and best-first with your two heuristics.

Notes

Watch the class bboard, academic.cs.15-381, for any clarifications, hints or modifications to the assignment. These will also show up on the class Web Home Page, 15-381.html