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:

   #lang racket

   (require "problem.rkt")

   (require "node.rkt")

   (require "8puzzle.rkt")

    

   ;; 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: Lights out representation

1. Make sure the lights-out procedures are available, define a 3×3 version of the problem, and a do-nothing heuristic.

   (require "lightsout.rkt")

   (define lights-out (lights-out-problem 3))

   (define zero-fun (lambda (x) 0))
2. Generate a random state for your 3×3 lights out problem involving only a single move.

   (define lights-out-state (random-lights-out-state 3 1))
3. Inspect the value of lights-out-state.
   You should find a list of 10 elements. The first element indicates the side length (3 in this case), and the remaining elements indicate the light status (zero for off, one for on) of all 3² lights. The elements are ordered by moving along the rows. Thus, the squares on the board below have the indicated indices in the state list

   1	2	3
   4	5	6
   7	8	9

   The following command may help you visualize the state:

   (lights-out-state-board-list lights-out-state)

   1. Which light switch was toggled (from the all-off state) to produce the state you see?
   2. Which light switch would you toggle for your next move?
4. Create a node for your lights out state and generate its successors, just as you did for the eight-puzzle above, but using the uninformed heuristic zero-fun.

   (define lights-out-start-node _________)

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

   > (map node-action lights-out-successors)

   What do you suppose these actions mean? Confirm your intuition with the instructor.
6. Inspect the state of the first successor.

   > (lights-out-state-board-list (node-state (car lights-out-successors)))

   Some light values in the resulting states may not be strictly 0 or 1.
   1. Can you figure out why and what these non-binary values mean? (Compare the state to the starting state and consider the action it corresponds to.)
   2. Once you have a hypothesis, read the documentation section "Details" in lightsout.rkt to confirm it.
   3. Ask the instructor if you have any remaining questions about the lights out state representation.
7. Which one of the successors is a goal state? Verify your answer by writing an expression using the procedure returned by

   (problem-goal? lights-out)

Lab Assignment