Lab: Uninformed Search

CSC261 - Artificial Intelligence - Weinman

Summary:

We familiarize ourselves with the interface for search problems and nodes in preparation for implementing uninformed search algorithms.

Preparation

1. Copy the starter files to a directory for this lab.

   $ mkdir search

   $ cp ~weinman/courses/CSC261/code/search/*.scm search/

   $ cd search
2. Create a new Scheme file in your search directory called search-prep.scm and open it in your Scheme environment. For example,

   $ touch search-prep.scm

   $ drracket search-prep.scm &

   Add the remaining preparatory commands to that file.

Exercises

Eight puzzle, states, and successors

1. Load the relevant files

   (load "problem.scm")

   (load "node.scm")

   (load "8puzzle.scm")
2. Create an instance of a problem for the eight puzzle:

   (define eight-puzzle (eight-puzzle-problem))

   Note that eight-puzzle-problem is a procedure. It may seem silly to call this with no parameters, since it will always give the same result. However, other problems may be parameterized (requiring a procedure to generate the problem), so we've made this generator a procedure as well, for parallelism.
3. Because we won't be needing any heuristics for this assignment, let's define the always-zero function mentioned in the assignment

   (define zero-fun (lambda (x) 0))

   Despite the name, we hope you don't find this lab to be zero fun.
4. Create a random state for your eight puzzle problem involving only three moves

   (define eight-puzzle-state (random-eight-puzzle-state 3))
5. Display a visualization of this board, akin to that found in AIMA Figure 3.4 (p. 71).

   > (display (eight-puzzle-state-board-list eight-puzzle-state))

   Note that the three rows may be collapsed onto one line.
6. Can you determine the moves necessary to solve the puzzle?
7. Create a search node for this state. Note that node-init requires a heuristic procedure, which we can largely ignore for now by using the form given above

   (define eight-puzzle-start-node (node-init eight-puzzle-state zero-fun))
8. Generate the list of successors (resulting nodes) for your state.

   (define successors 

           (problem-expand-node eight-puzzle 

                                eight-puzzle-start-node

                                zero-fun))
9. Examine the list of actions corresponding to each successor.

   > (map node-action successors)

   These symbols indicate the direction the blank tile would be moved.
10. Examine the first resulting successor state. (Remember a node is distinct from a state!)

    > (display (eight-puzzle-state-board-list

               (node-state (car successors))))
11. Test whether the state of the first successor node is the goal state by applying the procedure returned by (problem-goal? eight-puzzle) to it. Note that problem-goal? returns a goal predicate for the given problem; it is not a predicate itself.
12. Write an expression using map and node-state to generate a list of all the successor states. You may create an anonymous procedure with lambda or use compose.

Search routines

1. Open search.scm and read the 6-P documentation for search. You will be implementing this procedure as a Scheme version of TREE-SEARCH as desribed in the lab. If you do not understand any of the 6-Ps, discuss them with your partner or the instructor.
2. Read the 6-P documentation for depth-first-search. Explain to your partner why the enqueing procedure

   (lambda (new-nodes frontier) (append new-nodes frontier))

   makes search behave in a depth-first fashion.
3. Read the 6-P documentation for uniform-cost-search. Study the enqueueing routine and convince yourself that the "POP" instruction of the search procedure will always produce the node in the frontier with the lowest path cost.

Lab Assignment