CIS 587: Spring 96: Homework 1(*)

Instructions

This assignment involves three different search strategies and two search problems. The search strategies are breadth-first search, iterative deepening, and Best-First search. The two problems are the water-jug problem and the 8-puzzle problem. Thus in total you will have six cases. We require the same problem representation for both problems. This representation must be acceptable to the three search strategies.

Your solution of the water-jug problem must allow any water-jug problem of the form:

You are given two jugs of capacity m and n.
You can empty a jug, fill a jug, transfer the content of a jug to the other jug until the former empties or the latter fills.
Produce a jug with capacity p.

Your solution of the 8-puzzle problem must allow any initial configuration. The goal, of course, is the usual one with, circularly, from top-left and around the border 1, 2, 3, 4, 5, 6, 7, 8. [Remember that the goal configuration is not accessible from all initial configurations.]

Make a single file containing:

Your Lisp code
One instance of each problem as a global variable, say, *jug-example-1*, *eight-puzzle-1*

Please send this file to

	ingargio@yoda.cis.temple.edu

and include in the Subject line "cis587 HMW1".

The homework is given January 23, 1996 and is due by 4:00pm, Tuesday February 13, 1996.

Representation of a problem

We assume that a search problem is represented as a list

  ( initial-stat   ; Representation of the initial state.
    next-state-ops ; A list of operators. Each operator is a
  		   ; lisp function that, given a state, returns
		   ; two values: a next state, or nil, and the
                   ; the cost of the transition or 0.
    goalp	   ; A lisp function that, applied to a state,
		   ; returns true iff that state is a goal state.
    heuristic	   ; It is either nil or a lisp function. In the
		   ; latter case, given a state s, returns h(s).
  )

Representation of a state

It is up to you, but I suggest that it is a list and that this list's first element be available to the search algorithm (for example, to keep information about the predecessor of the current state, the current g value, etc).

Breadth First Search and Iterative Deepening Search

Write two lisp functions


   (bfs problem maxdepth maxnodes), 
   (ids problem maxdepth maxnodes) and

that start with a given state and solve the problem using breadth-first-search and iterative-deepening-search. Your program must not exceed the maximum depth or maximum number of nodes limits passed as the second and third argument. Your program must not make any assumptions about the structure of a state except for what stated above.

Your program must print the following information:

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

Heuristic Search

Write a best-first (BF*) search routine

   (best-first problem maxdepth maxnodes)

that implements BF*.

For a simple heuristic, try adding the number of squares that are in the final location. Try at least one other heuristic function. Indicate if these heuristic functions are or not admissible or monotonic. Compare the path length and number of nodes searched for breadth-first search, depth-first search, and best-first with your two heuristics.

(*) This assignment is derived from Assignment 1 in the course 15-381, Introduction to Artificial Intelligence, taught at Carnegie-Mellon by Dr.Mauldin and Dr.Nyberg.

ingargiola@cis.temple.edu