Lab: Informed Search and Heuristics

CSC261 - Artificial Intelligence - Weinman

Summary:

We explore a heuristic for the eight-puzzle problem in preparation for implementing A^* and a new heuristic.

Preparation

1. Open your Scheme environment and create a new Scheme file in your definitions pane in the same directory as your prior search files.
2. Add the preparations from the prior lab to your file:

   ;; Load definitions

   (load "problem.scm")

   (load "node.scm")

   (load "8puzzle.scm")

    

   ;; Define the problem

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

Exercises

A: Eight puzzle heuristic

1. Let's create a more difficult problem with at most ten moves from the goal

   (define eight-puzzle-state (random-eight-puzzle-state 10))

   and display it.

   > (display (eight-puzzle-state-board-list eight-puzzle-state))
2. The function eight-puzzle-misplaced in the file 8puzzle.scm provides the simple heuristic h₁ of AIMA 3.6 (p. 103), which is the number of misplaced (out of position) tiles. Apply this heuristic to your state.

   > (eight-puzzle-misplaced eight-puzzle-state)
3. Create a search node for this state. Recall that node-init requires a heuristic procedure, which we can now take to be eight-puzzle-misplaced.

   (define eight-puzzle-start-node

     (node-init eight-puzzle-state

                eight-puzzle-misplaced))
4. Query the path cost and (estimated) total cost of this start node.

   > (node-path-cost eight-puzzle-start-node)

   > (node-total-cost eight-puzzle-start-node)

   Make sure these two numbers make sense to you before moving on.
5. Using this heuristic function, generate the successors to your state.

   (define successors 

     (problem-expand-node eight-puzzle 

                          eight-puzzle-start-node

                          eight-puzzle-misplaced))

   Which successor would depth-first search expand next? Make sure your partner(s) agree about why.
6. Inspect the (estimated) total cost of all the successors

   > (map node-total-cost successors)

   1. Which successor would uniform-cost-search expand next?
   2. Which successor would A^* search expand next?
   For both, make sure you and your partner(s) agree about why.

B: Jumping representation

1. Make sure the jump procedures are available, define a length 10 version of the problem, and a do-nothing heuristic.

   (load "jump.scm")

   (define jump (jump-problem 10))

   (define zero-fun (lambda (x) 0))
2. Read the "Details" section of the header in jump.scm to understand the Scheme-based state representation.
3. Define the following (arbitrary) state for the jumping problem, making sure you understand what it represents.

   (define jump-state (list 10 3 2))
4. Create a node for your jump state and generate its successors, just as you did for the eight-puzzle above (A.3), but using the uninformed heuristic zero-fun.

   (define jump-start-node _________)

   (define successors _________)
5. Inspect the actions corresponding to each successor.

   > (map node-action successors)

   What do you suppose these actions mean? Confirm your intuition with the instructor.

Lab Assignment