Link Search Menu Expand Document
CS372 - AI

AI Project 1: GPS Navigation

  1. What your program should do
    1. Debugging output
  2. General guidelines
  3. Part A: The A* algorithm
  4. Part B: GPS directions
  5. Calculating a compass bearing
  6. Determining GPS turning directions
  7. Testing
    1. Location IDs
    2. Example runs
  8. At the end of the project
  9. Grading
  10. Submission instructions
  11. Challenges

In this project, you will write a program that uses the A* algorithm to find the fastest route between two locations in Memphis. Your program will print out the route as a list of GPS-style navigation directions.

Optional starter code: priority queue classes (cpp/python/java)proj0 solutions (python/java)

What your program should do

  • Your program should read the memphis-medium.txt map and process it using the ideas from Project 0, though nothing needs to be printed.
  • Your program should ask the user for the starting and ending location IDs of the desired route. Your program should also ask whether the user wants to print debugging information; this is explained below.
  • Your program should use the A* algorithm to compute the fastest driving route between the two locations. As in Project 0, your program should use the speed limit for each road to determine the time it takes to travel that particular road segment. You may assume speed changes are instantaneous, and you don’t have to take traffic or stop lights (or other things which one would slow down for) into account.
  • Your program should print the fastest route found as a sequence of location IDs and street names (see below for details). In addition, the output should include:
    • The total number of nodes visited in the search tree.
    • The total time the route takes to drive, in seconds.
  • Your program should also print the route in a GPS navigation style, involving turn-by-turn directions (see below for more details).

Debugging output

To help you debug your program, and to help in grading, your program should also print some extra information while the A* search is running. However, because this information can become rather long, you will only print it if requested.

If asked to print debugging information, your program must print:

  • Information about every node removed from the frontier, as it is removed (we call this visiting a node). You should print the node’s state (a location ID), the node’s parent’s state (also a location ID), and the f(n), g(n), and h(n) values for the node.
  • Information about every child node that is generated as part of the expansion of a node. For each child node, you should print whether it is added to the frontier or not, along with the same five pieces of information as when a node is visited (state ID, parent’s state ID, f(n), g(n), and h(n)).

General guidelines

  • You may implement this project in Java, Python, or C++. Talk to me if you want to use another language.
  • All the basic guidelines from Project 0 about suggested data structures apply to Project 1 as well. You may choose to base this project off of your own code for Project 0, or you may start with my Project 0 code, available in Python or Java.

Part A: The A* algorithm

  • This part of the project is worth 85% of your grade. In other words, if you complete the A* algorithm, but do nothing in part B, your maximum grade is 85/100.
  • Please the A* pseudocode in the book or from the handouts in class. NEW: Pseudocode and implementation hints. While you may find online sources helpful in understanding the algorithm, you may encounter slight variations in different people’s versions of the algorithm that will make it difficult for me to test your code and help you debug it if necessary.
  • You should keep track of the number of vertices “visited,” which means the number of vertices popped off of the queue.
  • g(n) for a node n (a.k.a. the path-cost) is the total travel time, in seconds, from the initial state to the state of node n.
  • h(n) is the heuristic function. Remember that it is supposed to be an estimate of the total travel time remaining, from the state of node n to the goal state. There are lots of ways to estimate this, but in order for A* to be optimal, we must use a function that does not overestimate the true time to the goal. Therefore, we will use the straight-line travel time from n to the goal state, assuming you could drive from node n to the goal at 65 miles per hour. We can use 65mph because that’s the maximum speed limit of any Memphis road, so this h(n) will never overestimate the true travel time.
  • Data structure suggestions:
    • You can use a class for the states (like a Location class), but you can also just use the location ID (a string or some kind of number, depending on language). You probably want to make a Node class, but it’s possible to get away without one if you use maps to store the parent references, along with the f/g/h values for the nodes. I found it easiest to make a Node class that holds a state, a parent pointer, and the f/g/h values.
    • Frontier: I have written priority queue classes in Python, C++, and Java, which you may use if you want. I think they are easier to use than the ones built-in to those languages, but you may use whatever kind of priority queue structure you want.
    • Reached: Standard maps should work fine here. You can use a map from states to Nodes or since you really just need the f(n) value for a node, you can use a map from states to doubles and just store the f(n) value directly in the map.
  • When A* finishes, you end up with the final Node object that corresponds to a goal state. You can then follow the chain of parent pointers back to the initial state to get the sequence of locations/roads that you need.

Part B: GPS directions

  • This part of the project is worth the final 15% of your grade.
  • The GPS directions section has the following minimum requirements:
    • You must provide the initial direction you head (north, south, etc), and the name of the road.
    • You must provide the distance and time you should spend traveling on this road.
    • Every time the road changes names, you must state which direction you turn (left or right), and the distance and time you spend traveling on the new road.
  • Initial direction: This can be computed from the pseudocode given below to compute a compass bearing, given a pair of latitude-longitude coordinates. You only need to handle the eight directions: north, northeast, east, southeast, south, southwest, west, and northwest.
  • Turning direction: This can be computed by comparing the compass bearing of the road one is turning from against the road that one is turning onto. You only need to handle turning “left” or “right.” You may assume there is a turn every time the road changes names, even though this may not be true (you might be going straight, but you don’t have to handle this case; this is a challenge problem). You also don’t need to handle turns where the road doesn’t change names (this can also be done as a challenge).

Calculating a compass bearing

This pseudocode takes a starting latitude-longitude combination and an ending latitude-longitude and returns the compass bearing, that one would travel along a line between the two points. The bearing is returned as a value in degrees, between 0 and 359. 0=north, 90=east, 180=south, 270=west, as is illustrated here.

Pseudocode (adapted from this)

function getBearing(lat1, long1, lat2, long2) {
  // convert to radians first
  lat1 *= pi/180
  lat2 *= pi/180
  long1 *= pi/180
  long2 *= pi/180
  
  y = sin(long2-long1) * cos(lat2)
  x = cos(lat1) * sin(lat2) - sin(lat1) * cos(lat2) * cos(long2-long1)
  angle = atan2(y, x)  // arctangent function
  bearing = (angle * 180/pi + 360) % 360 // convert back to degrees
  return bearing

A compass bearing can be used to calculate a direction as a word, e.g., north or southwest. Your initial GPS instruction should contain one of these words, but you only need to account for eight directions (north/south/east/west and the four directions in between). 360 degrees divided into 8 pieces = 45 degrees, so each of the eight “directional words” corresponds to a slice of the compass 45 degrees wide. Each “slice” is centered on one of the eight main compass bearings, and includes 22.5 degrees on either side. For instance:

  • “East” corresponds to exactly 90 degrees. But it also should include any bearing between 90-22.5=67.5 degrees and 90+22.5=112.5 degrees.
  • “Northeast” corresponds to exactly 45 degrees. But it should also include any bearing between 45-22.5=22.5 degrees and 45+22.5=67.5 degrees. This pattern continues for the other “directional words,” and therefore any bearing, from 0-359, corresponds to one of those eight words.

Determining GPS turning directions

You determine if a GPS direction should be a “right turn” or a “left turn” by calculating the compass bearing for each of the road segments involved in the turn (that is, the bearing before the turn and the bearing after the turn). Then, examine the difference between the bearings and which bearing is larger. By calculating whether or not the difference between the bearings is greater or less than 180, and whether the first or second bearing is larger than the first, you should be able to determine whether the turn is towards the right or the left.

Example: Imagine your first bearing is 90 degrees (due east) and the second bearing is 70 degrees. The difference between these is 20 degrees, and the first is larger than the second, indicating a left turn. Note: This is obviously a very slight left turn, and one of the challenges is to modify the turning directions to incorporate more descriptive words like “bear slightly right” or “make a sharp left turn.”

Example 2: Imagine your first bearing is 330 degrees and the second bearing is 70 degrees. Like in example 1, the first bearing is larger than the second, but the difference is 260, which is larger than 180, so this is a right turn.

Testing

You should test your program thoroughly. I recommend using the debugging output to make sure you are examining nodes in the same order that my solution is. It is possible there may be slight variations in f/g/h values due to round-off errors differing between Python/C++/Java. However, these variations should be very small.

Location IDs

To test your program, I have collected the IDs for some Memphis landmarks, commonly-visited places, and some intersections near Rhodes.

Example runs

Here are four sample runs. Assuming the debugging flag is turned off, the first three all run in less than one second on my computer, and the last one takes less than five seconds.

At the end of the project

  • As you are preparing to submit the project, please prepare a text file (.txt, pdf, or Word doc is fine) answering the following questions:
    1. What bugs and conceptual difficulties did you encounter? How did you overcome them? What did you learn?
    2. Describe whatever help (if any) that you received. Don’t include readings, lectures, and exercises, but do include any help from other sources, such as websites or people (including classmates and friends) and attribute them by name.
    3. Describe any serious problems you encountered while writing the program.
    4. Did you do any of the challenges (see below)? If so, explain what you did.
    5. List any other feedback you have. Feel free to provide any feedback on how much you learned from doing the assignment, and whether you enjoyed doing it.
  • Please also add a comment at the top of your program stating your name and a pledge that you have followed the honor code and collaboration policy for this project. This can be as simple as writing “I have neither given nor received unauthorized aid on this program.” You can find the collaboration policy on the syllabus.

Grading

  • Your project will be graded on the correctness of your program, in particular:
    • whether your program produces the correct best route and correct best travel time in seconds,
    • whether the sequence and number of nodes visited and expanded is correct,
    • whether the GPS turn-by-turn navigation directions, including number of miles and seconds, is correct. Small variations in f/g/h values due to round-off errors are OK; and this may cause small variations in the sequence of nodes visited/expanded as well. It might also induce variations in the optimal route found, but it shouldn’t cause the best travel time to change much.
  • Your project will also be graded on the appropriateness and efficiency of the algorithms you choose, and on coding style.

Submission instructions

Through Canvas, upload all your source code files and your file with the answers to the questions above.

Challenges

The challenges for this assignment all involve making the GPS directions clearer.

  • Change the directions so any number of seconds greater than or equal to 60 is displayed as minutes and seconds.
  • Change the turning directions so that small changes in bearing are labeled as “slight” or “slightly” and larger changes are labeled as “sharp” or “sharply.” Turns close to 90 degrees shouldn’t have a label, but anything that is a big deviation from a 90 degree turn should get a “slight” or a “sharp.”
  • Change the turning directions to include “go straight” rather than a turning direction where it’s appropriate. Note that distinguishing when to label a turn, for example as “slight right” versus “go straight” might involve figuring out how many streets meet at an intersection.
  • There are many streets in the map with the name “NoName.” Most of these are ramps to and from highways and therefore don’t have true street names. Use the presence of “NoName” streets to change the driving directions to say things like “Turn/bear right onto the ramp to…” or “Merge onto…” rather than reporting “NoName” as the actual street name. Note that this will probably involve looking a few streets ahead after the NoName street to determine the name of the highway or street that the ramp is leading to.
  • Have your program draw a map of the route chosen.