Guidelines for Assignment 6:
 
The assignment is split into 3 parts:

1. The students are to do a statistical test on the 4 search
techniques listed in the book, i.e. Breadth-First Search, Depth First
Search, Iterative Deepening, and Best-First Search. The search space
will be a grid of 10 x 10 nodes. There will be 4 to 5 grids with
increasing difficulty (including obstacles and cul de sacs) for the
students to test out their algorithms. Each node in the search space
will have associated with it a parameter which indicates whether it is
occupied or not.

   Other points of interest
   I have determined two forms of representation.
   They may be found in /course/cs141/asgn/asgn6.
   -- We will provide the students with the grids in the form of 
	(setq grid '(((0 0) nil) ((0 1) nil) ((0 2) nil)
                     ((1 0) nil) ((1 1) nil) ((1 2) nil)
                     ((2 0) nil) ((2 1) t) ((2 2) nil)))
	So each element in the list contains a node in the list and
        there is no specific order in which they appear.

   -- Or we can provide them with something more similar to the
      examples in the book, i.e. give them a grid in the form
      ((start-node) (list of neightbouring nodes in order to search) 
	(other nodes))
      This will give them the ability to reuse the search routines
      spelled out in the book and only make slight changes to the
      state representation, goalp, next and compare routines. 
      Therefore, I would prefer this representation.
      In this case, we will have to make it compulsory that they use
      the exact functions that appear in the book.

   i. *The first coordinate in the grid representation is going to
      be the starting location of the search in both cases.
      *The grid representation need not necessarily be in any specific
      order.	
      *The search will NEVER start in an occupied node.


   ii. In this part of the problem, there will be only one goal.

   iii. The students have to come up with the following routines:
       	
       A routine to determine the next state given the current state.
       A routine to determine whether the current state is the goal
	state.
       A comparator function for sorting nodes using the Manhatten 
        distance.
       A way to check if the node has been traversed before.
       (I would suggest just removing it from the rest of nodes to traverse).
	
2. The students are to use Breadth-First Search in order to return a
path when asked to traverse through certain nodes. 

	(traverse grid goals)
	will return the list of nodes visited in order to visit all
        the goals
	     
	grid  - refers to the grids specified as in part 1.
	goals - refers to the sequence of goals to visit. It is not
	necessary to visit the goals in any specific order.
	
	It may be in the form
	((0 0) (3 5) (4 6) .......) where each pair specifies the
	nodes to visit in the grid.

3. Implement Hill-climbing search on the above search space as well.
Hill-Climbing search basically involves searching the search space
like a depth-first search but a comparison function is used to
determine which of the nodes to search first.
The student may use the comparator function used in part 1.

Extra Credit: Build a graph which contains the shortest path from each
node to every other node. (10%)



