Home    

Practice with searching

TOC

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

./images/goodale-route-map.png

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) + 
           math.cos(phi1)*math.cos(phi2))
    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)

./images/goodale-checked.png

Maximum number of states in memory

./images/goodale-memory.png

Length of path (goodness of solutions)

./images/goodale-path.png

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.

./images/goodale-anomaly-path.png

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.