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.
- 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:
- austin to temple
- austin to dallas
- corsicana to muleshoe
- laredo to haskell
- 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?
- 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.
- 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"):
- (make-node city f g h parent) makes a new node data structure
with the given values. The arguments are optional.
- (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)
- (make-priq) will make a priority queue that can be used
for the open list: (setq open (make-priq))
- (priq-insert open new) insert the node new
according to its f value.
- (priq-extract open) extract the node with the lowest
f value.
- (links city) gives the road connections to other cities.
Each element of the list links is a list (city miles).
- (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.
You may wish to compare your results with the results at
Mapquest and
Google Maps.