Practice with searching


Routing from Dreese Labs to Goodale Park

In this example, our goal is to find a route between Woodruff & Tuttle and the Goodale parking lot. The graph on the right shows how various road intersections connect to each other, and the distance between intersections (in miles).

Initial state
Woodruff & Tuttle
Possible actions
Every action is the same: drive to another intersection.
Transition model
Shown in the graph and the table; each intersection can access the other intersections which are linked in the graph.
Goal criteria
Our destination is Goodale parking lot
Path cost
Shown in the graph and the table; distance (in miles) to the next intersection.

Map data

This map data is encoded in Java and Python source code if you would like to use it in a program.

Goodale parking lot routes


MarkerStartEndDistance (mi)
AHigh & GoodaleGoodale parking lot0.22
BHigh & 5thHigh & Goodale0.93
CI-71 5th offrampHigh & 5th1.07
DI-71 11th offrampI-71 5th offramp0.52
EI-71 17th offrampI-71 11th offramp0.47
FUS-23 & 17thI-71 17th offramp0.75
GUS-23 & 15thUS-23 & 17th0.12
HHigh & 15thUS-23 & 15th0.49
IHigh & WoodruffHigh & 15th0.26
JWoodruff & TuttleHigh & Woodruff0.46
KLane & TuttleWoodruff & Tuttle0.17
LSR-315 & LaneLane & Tuttle0.74
MSR-315 I-670 offrampSR-315 & Lane2.05
NPark & VineSR-315 I-670 offramp0.99
OPark & GoodalePark & Vine0.15
PGoodale parking lotPark & Goodale0.13
QUS-23 & GoodaleUS-23 & 15th1.76
RSR-315 & KingSR-315 & Lane1.10
SHigh & KingSR-315 & King1.02
THigh & 11thI-71 11th offramp1.15
US-23 & GoodaleGoodale parking lot0.41
High & 15thHigh & 11th0.37
High & 11thHigh & King0.31
High & KingHigh & 5th0.21

Longitude / latitude information

LocationLon (W°)Lat (N°)
High & Goodale-83.0028639.97384
High & 5th-83.0055139.98710
I-71 5th offramp-82.9852639.98631
I-71 11th offramp-82.9851939.99394
I-71 17th offramp-82.9844340.00072
US-23 & 17th-82.9986540.00133
US-23 & 15th-83.0011839.99973
High & 15th-83.0080740.00007
High & Woodruff-83.0088840.00409
Woodruff & Tuttle-83.0174840.00400
Lane & Tuttle-83.0168340.00631
SR-315 & Lane-83.0308540.00646
SR-315 I-670 offramp-83.0212039.97749
Park & Vine-83.0046939.97147
Park & Goodale-83.0045339.97362
Goodale parking lot-83.0064939.97372
US-23 & Goodale-82.9982639.97423
SR-315 & King-83.0251139.99084
High & King-83.0061039.99019
High & 11th-83.0071239.99528

The distance (as the crow flies) from each location to each other is collected in the goodale-distances.txt file.

Here is some Python code for converting two long/lat coordinates into a measure of miles between them:

# from: http://www.johndcook.com/python_longitude_latitude.html
import math
def dist((long1, lat1), (long2, lat2)):
    # Convert latitude and longitude to 
    # spherical coordinates in radians.
    degrees_to_radians = math.pi/180.0

    # phi = 90 - latitude
    phi1 = (90.0 - lat1)*degrees_to_radians
    phi2 = (90.0 - lat2)*degrees_to_radians

    # theta = longitude
    theta1 = long1*degrees_to_radians
    theta2 = long2*degrees_to_radians

    # Compute spherical distance from spherical coordinates.

    # For two locations in spherical coordinates 
    # (1, theta, phi) and (1, theta, phi)
    # cosine( arc length ) = 
    #    sin phi sin phi' cos(theta-theta') + cos phi cos phi'
    # distance = rho * arc length

    cos = (math.sin(phi1)*math.sin(phi2)*math.cos(theta1 - theta2) + 
    arc = math.acos( cos )

    # Remember to multiply arc by the radius of the earth 
    # in your favorite set of units to get length.
    return (arc * 3960.0)

Comparison of searches

Number of checked states (time)


Maximum number of states in memory


Length of path (goodness of solutions)


Let’s introduce an anomaly

Suppose we change the distance from High & 15th to High & 11th to 37 miles (originally was 0.37 miles). This modification is a proxy for a traffic jam between these two intersections or some other similar unplanned situation. A* will account for this change because its heuristic is the composite heuristic \(f(s) = g(s) + h(s)\), which means that \(f\) accounts for both the estimated distance \(h\) between High & 15th and High & 11th (“as the crow flies”), and the cost \(g\) of traveling that distance (the traffic jam is accounted for here).

Best-first search, on the other hand (and hill-climbing for that matter) do not take into account \(g\), so they do not plan for the traffic jam; they only plan for the “as the crow flies” distance. Thus, best-first and hill-climbing will travel across this jammed route and their solution cost will suffer as a result.


AI Su13 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.