In route planning, the objective is to find the best way to get from point A to point B (think Google Maps). In this homework, we will build on top of the classic shortest path problem to allow for more powerful queries. For example, not only will you be able to explicitly ask for the shortest path from the Gates Building to Coupa Cafe at Green Library, but you can ask for the shortest path from Gates back to your dorm, stopping by the package center, gym, and the dining hall (in any order!) along the way.

We will assume that we have a map of a city (e.g., Stanford) consisting of a set of locations. Each location has:

  1. a unique label (e.g., 6608996258),
  2. a (latitude, longitude) pair specifying where the location is (e.g., 37.4299866, -122.175519), and
  3. a set of tags which describes the type of location (e.g., amenity=food).

There are a set of connections between pairs of locations; each connection has a distance (in meters), and can be traversed in both directions (if the distance from A to B is 100 meters, then the distance from B to A is also 100 meters).

There are two city maps that you'll be working with: a grid map (createGridMap) and a map of Stanford (createStanfordMap), which is derived from Open Street Maps. We have also included instructions on how to create your own maps in README.md.

Important: for this assignment, please develop using Python 3.8.

Problem 0: Grid City

Consider an infinite city consisting of locations $(x,y)$ where $x, y$ are integers. From each location $(x,y)$, one can go east, west, north, or south. You start at $(0,0)$ and want to go to $(m, n)$, where $m, n \geq 0$. We can define the following search problem to capture this:

  1. What is the minimum cost of reaching location $(m,n)$ (note that $m,n \geq 0$) starting from location $(0,0)$ in the above city? Describe one possible path achieving the minimum cost. Is it unique (i.e., are there multiple paths that achieve the minimum cost)?
    Provide an expression for the minimum cost. In addition, using 1 - 2 sentences describe one possible minimum cost path and state whether it is unique.
  2. How will Uniform Cost Search (UCS) behave on this problem? Mark the following as true or false:
    1. UCS will never terminate because the number of states is infinite.
    2. UCS will return the minimum cost path and explore only locations between $(0,0)$ and $(m,n)$; that is, $(x,y)$ such that $0 \le x \le m$ and $0 \le y \le n$.
    3. UCS will return the minimum cost path and explore only locations whose past costs are less than the minimum cost from $(0,0)$ to $(m,n)$.
    T/F for each subpart.
  3. Now consider running UCS on an arbitrary graph. Mark the following as true or false:
    1. If you add a connection between two locations, the minimum distance cannot go up.
    2. If you make the cost of an action from some state small enough (possibly negative), that action will show up in the minimum cost path.
    3. If you increase the cost of each action by 1, the minimum cost path does not change (even though its cost does).
    T/F for each subpart.
Problem 1: Finding Shortest Paths

We first start out with the problem of finding the shortest path from a start location (e.g., the Gates Building) to some end location. In Google Maps, you can only specify a specific end location (e.g., Coupa Cafe at Green Library).

In this problem, we want to give the user the flexibility of specifying multiple possible end locations by specifying a set of "tags" (e.g., so you can say that you want to go to any place with food versus a specific location like Tressider).

  1. Implement ShortestPathProblem so that given a startLocation and endTag, the minimum cost path corresponds to the shortest path from startLocation to any location that has the endTag.

    In particular, you need to implement startState(), isEnd(state), successorsAndCosts(state).

    Recall the separation between search problem (modeling) and search algorithm (inference). You should focus on modeling (defining the ShortestPathProblem); the default search algorithm, UniformCostSearch (UCS), is implemented for you in util.py.

    An implementation of the ShortestPathProblem class.
  2. Run python mapUtil.py > readableStanfordMap.txt to write a (long-ish) file of the possible locations on the Stanford map along with their tags. Each tag is a [key]=[value]. Here are some examples of keys:

    Choose a starting location and end tag (perhaps that's relevant to your daily life) and implement getStanfordShortestPathProblem() to create a search problem. Then, run python grader.py 1b-custom to generate path.json. Once generated, run python visualization.py to visualize it (opens in browser). Try different start locations and end tags. Pick two settings corresponding to the following:

    You should feel free to add new landmarks and if you are not at Stanford, follow the instructions in the README.md to use your own map and landmarks.

    A screenshot of the visualization of your two solutions as well as i) one or more sentences describing something interesting you've learned about traveling (around campus, or elsewhere) and ii) something incorrect about either the map or modeling assumptions (such a landmark being out of place, etc.).
  3. Your system now allows anyone to find the shortest path between any pair of locations on campus. By shortening their travel distance, it promises to optimize travel efficiency.

    But now, what happens when a large fraction of the population start using your system to plan their routes? In particular, what negative externalities might result from this system being widely deployed (see these brief articles for inspiration: "Why Traffic Apps Make Congestion Worse," "The Perfect Selfishness of Mapping Apps" ).

    Discuss the impact of these externalities on users of your system and other people. Remember that problems often arise from the mismatch between the real world and one's model of it. How would you reduce this mismatch?

    Provide 3-5 sentences describing at least two externalities (one for users and one for other people), and what you could do to address these problems.
Problem 2: Finding Shortest Paths with Unordered Waypoints

Let's introduce an even more powerful feature: unordered waypoints! In Google Maps, you can specify an ordered sequence of waypoints that a path must go through – for example, going from point A to point X to point Y to point B, where [X, Y] are "waypoints" (such as a gas station or a friend's house).

However, we want to consider the case where the waypoints are unordered: {X, Y}, so that both A → X → Y → B and A → Y → X → B are allowed. Moreover, X, Y, and B are each specified by a tag like in Problem 1 (e.g., amenity=food).

This is a neat feature if you think about your day-to-day life; you might be on your way home after a long day, but need to stop by the package center, Tressider to grab a bite of food, and the bookstore to buy some notebooks. Having the ability to get a short, quick path that hits all these stops might be really convenient (rather than searching over the various waypoint orderings yourself).

  1. Implement WaypointsShortestPathProblem so that given a startLocation, set of waypointTags, and an endTag, the minimum cost path corresponds to the shortest path from startLocation to a location with the endTag, such that all of waypointTags are covered by some location in the path.
    Note that a single location can be used to satisfy multiple tags.

    Like in Problem 1, you need to implement startState(), isEnd(state), and successorsAndCosts(state).

    There are many ways to implement this search problem, so you should think carefully about how to design your State. We want to optimize for a compact state space so that search is as efficient as possible.

    An implementation of the WaypointsShortestPathProblem class. To get full credit, your implementation must have the right asymptotic dependence on the number of locations and waypoints. Note that your code will timeout if you do this incorrectly.
  2. If there are $n$ locations and $k$ waypoint tags, what is the maximum number of states that UCS could visit?
    A mathematical expression that depends on $n$ and $k$, with a brief explanation justifying it.
  3. Choose a starting location, set of waypoint tags, and an end tag (perhaps that captures an interesting route planning problem relevant to you), and implement getStanfordWaypointsShortestPathProblem() to create a search problem. Then, similar to Problem 1b, run python grader.py 2c-custom to generate path.json. Once generated, run python visualization.py to visualize it (opens in browser).
    A screenshot of the visualized path with a list of the waypoint tags you selected. In addition, provide one or more sentences describing unexpected or interesting features of the selected path. Does it match your expectations? What does this path fail to capture that might be important?
  4. Ride sharing companies use route finding systems similar to the one you built in this problem to route drivers. Such companies have been criticized for using behavioral nudges in their driver-facing applications; for example, a New York Times article reported how the app uses features such as “forward dispatch” (a feature that dispatches a new ride to a driver before the current one ends) to constantly keep drivers busy. This makes it more difficult for drivers to take breaks.

    How would you implement better labor practices for drivers, balancing company goals with the protection of driver interests? How could your new unordered waypoints feature help? What waypoints would you include from one drop-off location to the next pick-up location for drivers, and what information about drivers would you need to determine appropriate waypoints?

    Note that the unordered waypoints feature is an example of a dual use technology: what are some waypoints that a company might use to increase its profits at the expense of driver health?

    Provide 3-5 sentences describing waypoints to include, at least one dimension of drivers' identity that could inform selection of waypoints, and a potential use of the unordered waypoints feature that would not be beneficial for drivers.
Problem 3: Speeding up Search with A*

In this problem, we will explore how to speed up search by reducing the number of states that need to be expanded using various A* heuristics.

  1. In this problem, you will implement A* to speed up the search. Recall that in class, A* is just UCS with a different cost function (a new search problem), so we will implement A* via a reduction to UCS.

    In particular, you should implement aStarReduction() which takes a search problem and a heuristic as input and returns a new search problem.

    An implementation of the NewSearchProblem class in the aStarReduction(problem, heuristic) function. As in prior problems, you need to implement startState(), isEnd(state), and successorsAndCosts(state).
  2. We are now ready to speed up search by simply implementing various heuristics. First, implement StraightLineHeuristic for Problem 1, which returns the straight line distance from a state to any location with the end tag. Note: you might want to precompute some things so that evaluating the heuristic is fast.
    An implementation of the StraightLineHeuristic class.
  3. Next, implement NoWaypointsHeuristic for Problem 2, which returns the minimum cost path from a state to any location with the end tag but ignoring all the waypoints (essentially the solution to Problem 1, so you can reuse that if you'd like). Note: you might want to precompute some things so that evaluating the heuristic is fast. Helpful comments are provided in the code.
    An implementation of the NoWaypointsHeuristic class.
  4. Recall that heuristics are most effective when they are equal to the future cost. Consider a $n \times n$ grid map (createGridMap) where the start and end are at the opposite corners; for $n = 10$, we would have startLocation = "0,0", endTag = "label=9,9".

    Provide a concrete example of $n$ waypointTags so that running A* with the NoWaypointsHeuristic results in the same running time complexity as solving the relaxed shortest path problem.

    An example of $n$ waypointTags that satisfies the constraints of the question.
Submission

Submission is done on Gradescope.

Written: When submitting the written parts, make sure to select all the pages that contain part of your answer for that problem, or else you will not get credit. To double check after submission, you can click on each problem link on the right side, and it should show the pages that are selected for that problem.

Programming: After you submit, the autograder will take a few minutes to run. Check back after it runs to make sure that your submission succeeded. If your autograder crashes, you will receive a 0 on the programming part of the assignment. Note: the only file to be submitted to Gradescope is submission.py.

More details can be found in the Submission section on the course website.