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 and display it.

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

   (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 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?

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.

   (load "lightsout.scm")

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

   (define zero-fun (lambda (x) 0))
2. Generate and inspect the lights-out goal state for a 3×3 board.

   (lights-out-goal-state 3)

   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

   0	1	2
   3	4	5
   6	7	8
3. 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))
4. Inspect the value of lights-out-state.
   1. Which light switch was toggled to produce it?
   2. Which light switch would you toggle for your next move?
5. 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 successors _________)
6. 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