search-practice.org

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.

Marker	Start	End	Distance (mi)
A	High & Goodale	Goodale parking lot	0.22
B	High & 5th	High & Goodale	0.93
C	I-71 5th offramp	High & 5th	1.07
D	I-71 11th offramp	I-71 5th offramp	0.52
E	I-71 17th offramp	I-71 11th offramp	0.47
F	US-23 & 17th	I-71 17th offramp	0.75
G	US-23 & 15th	US-23 & 17th	0.12
H	High & 15th	US-23 & 15th	0.49
I	High & Woodruff	High & 15th	0.26
J	Woodruff & Tuttle	High & Woodruff	0.46
K	Lane & Tuttle	Woodruff & Tuttle	0.17
L	SR-315 & Lane	Lane & Tuttle	0.74
M	SR-315 I-670 offramp	SR-315 & Lane	2.05
N	Park & Vine	SR-315 I-670 offramp	0.99
O	Park & Goodale	Park & Vine	0.15
P	Goodale parking lot	Park & Goodale	0.13
Q	US-23 & Goodale	US-23 & 15th	1.76
R	SR-315 & King	SR-315 & Lane	1.10
S	High & King	SR-315 & King	1.02
T	High & 11th	I-71 11th offramp	1.15
	US-23 & Goodale	Goodale parking lot	0.41
	High & 15th	High & 11th	0.37
	High & 11th	High & King	0.31
	High & King	High & 5th	0.21

Longitude / latitude information

Location	Lon	Lat
High & Goodale	-83.00286	39.97384
High & 5th	-83.00551	39.98710
I-71 5th offramp	-82.98526	39.98631
I-71 11th offramp	-82.98519	39.99394
I-71 17th offramp	-82.98443	40.00072
US-23 & 17th	-82.99865	40.00133
US-23 & 15th	-83.00118	39.99973
High & 15th	-83.00807	40.00007
High & Woodruff	-83.00888	40.00409
Woodruff & Tuttle	-83.01748	40.00400
Lane & Tuttle	-83.01683	40.00631
SR-315 & Lane	-83.03085	40.00646
SR-315 I-670 offramp	-83.02120	39.97749
Park & Vine	-83.00469	39.97147
Park & Goodale	-83.00453	39.97362
Goodale parking lot	-83.00649	39.97372
US-23 & Goodale	-82.99826	39.97423
SR-315 & King	-83.02511	39.99084
High & King	-83.00610	39.99019
High & 11th	-83.00712	39.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)

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.