Heuristic Search: Route Finding

Due: Friday, September 28, 2007.

In this assignment, we will use A* and IDA* search to find routes for driving between cities.

Functions and data are provided in the file txcities.lsp for use with this assignment; these are described later.

1. Write a function (astar start goal hfn) that finds a driving route from the city start to the city goal, using the A* algorithm and the heuristic function hfn. You can call the heuristic function using (funcall hfn city goal) where city is the current city being examined; hfn will give an estimated distance to the goal. The astar function can use the citypath function described below. You do not need to implement the closed list, nor check for duplicates on the open list.

   Test your function by finding routes:

   1. austin to temple
   2. austin to dallas
   3. corsicana to muleshoe
   4. laredo to haskell
   5. dumas to houston

   Try the heuristic functions h0, h1, and h2 on each of the above routes. Print out the number of nodes removed from the open list each time. Print out the mileage of the route that is found. How does the number of nodes vary depending on the heuristic function? How do the routes vary? Are the routes good ones?

2. Write function(s) (citypath node) that reverses the sequence of cities starting with the node node, its parent, and so forth. node is the goal node; the result should be a list of city names, from the start to the goal.

3. Write function(s) (idastar start goal hfn) that finds a driving route from the city start to the city goal, using the IDA* algorithm. Test using the same routes and heuristic functions as above. Count the number of nodes examined; global variables *nodes*, *minover*, and *gvalue* are provided (you will need to initialize them).

Data and functions are provided by loading the file (load "/projects/cs343/txcities.lsp"):

1. (make-node city f g h parent) makes a new node data structure with the given values. The arguments are optional.
2. (city node), (f node), (g node), (h node), and (parent node) are access functions for the fields of a node. You can also use these with setf to set values: (setf (city node) 'austin)
3. (make-priq) will make a priority queue that can be used for the open list: (setq open (make-priq))
4. (priq-insert open new) insert the node new according to its f value.
5. (priq-extract open) extract the node with the lowest f value.
6. (links city) gives the road connections to other cities. Each element of the list links is a list (city miles).
7. (citydist city1 city2) gives the straight-line distance in miles between the cities. You will not need this function for the assignment, but it may be of interest.