CS63 Fall 2002
Lab 3: Using A* Search
Due: Friday, September 27, by noon

CONTENTS

INTRODUCTION

This week we will implement the informed search method best-first search and test its two variants: greedy search and A* search. Best-first search shares the same basic structure as general search. The only differences are that it takes an additional parameter, an evaluation function, and that it uses a priority queue rather than a standard queue. We will again be focusing on the eight puzzle as our problem domain.

GETTING STARTED

Copy the scheme file provided in the directory below to your home directory. 

~meeden/Public/cs63/lab3-astar/
The file pq.ss implements a heap style priority queue. At the bottom of the file I have included some tests. Execute these tests and be sure you understand how the priority queue works.

LAB INSTRUCTIONS

Part A: Using the search.ss file as a model, create a bestfirst.ss file that implements best first search. The parameters to your best first search should be: 

initial-state goal-state operators expander displayer evaluator
Notice that there is a new parameter evaluator. This is a function that when given a current state and the goal state, will return the estimated goodness of the current state. Also note that we have dropped the queuer parameter from the basic search algorithm. We will be using the priority queue instead. The priority queue has an insert method for adding items to the queue, and a remove-min method for removing items from the queue.

You will also need to modify make-node so that it includes the estimated value of the state, and you will need to create a new accesser function to get this value out of a node.

In addition, you will need to make some modifications to your 8puzzle.ss code. Update the expander function so that it uses an evaluator function. Implement the two evaluators that we discussed in class: 1) number of tiles out of place; and 2) manhattan distance. Remember that an astar evaluator should include both the cost of getting from the start state to the current state as well as an estimate of the distance to the goal state.

Part B: Test your solution on the original starting states A-E from the last lab as well as these additional starting states F-H using the same goal each time. Again, each test is progressively harder. 

   
 1 2 3   2 6 3   7 3 4   7 4 5   
 8   4   4   5   6 1 5   6   3   
 7 6 5   1 8 7   8   2   8 1 2   
 goal      F       G       H
Using a priority queue of size 1000, make a table showing how many nodes are expanded by the astar search using h1, the number of tiles out of place, versus h2, the manhattan distance. If the search is unsuccessful record that as well. Since the h2 estimate is always greater than or equal to the h1 estimate, we would expect astar to expand fewer nodes when using h2. Do the your results support this?

Part C: Try greedy search on the same set of test cases A-H. Using a priority queue of size 1000, if the search finds a solution, record the number of steps and the number of nodes expanded. If not, record failure.

Extra credit: Implement a bi-directional A* search and show how it fares on the same set of test cases.

HAND IN

Use cs63handin to submit both your updated 8puzzle.ss file and your bestfirst.ss file. Your table of test results should be included in the 8puzzle.ss file as comments.