Python Warmup

What and Why

In this exercise we will express a map of the DC Metro in Python 3 so that we might solve certain pathfinding problems.

One of the principal challenges of designing autonomous agents that work in the real world is creating useful models of the real world. Recall that all models are wrong: a useful model is a model that we can solve problems “on” such that our solutions (on the model) suggestion actions (in the real world) that, when taken, result in outcomes1 that we want.

1 Everyone has them.

This exercise reviews objected-oriented Python programming (which you may have just learned) and tree search algorithms (prerequisite material).

The Solution

Here are the “questions” we would like to answer with our model:

  • What is the path between two metro stations?
  • What is the median travel time between two metro stations on a specific path?
  • What is the 90th percentile2 travel time between two metro stations on a specific path?
  • What is the 10th percentile travel time between any two metro stations on a specific path?

2 i.e., time that is longer than 90% of times for the same trip.

We would like for our model to account for transfers between train lines (and how much time those transfers take). We would also like for our model to account for wait time at the starting station before the arrival of the first relevant train.

The Problem

We don’t need to implement a solution method for this exercise. Rather, we’re going to express a model that could be used to solve the problem. What we’ll need:

Stations

Write a Python Station class that models a single station on the metro. The stations can be found on the WMATA Map; your class should be “generic” such that it can accommodate any station in the system. These stations:

  • Serve only a single line
  • Serve multiple lines that are parallel in both directions
  • Serve multiple lines that are divergent in both directions
  • Serve multiple lines that are parallel in one direction and divergent in others

Your class should include some way to connect stations in the model as they are connected in the real metro system. There is more than one way to accomplish this: you might implement a class the represents edges, but you don’t have to.

Your class(es) should also capture information about travel times between stations.3

3 This travel time isn’t present on the WMATA map. Let us assume it can be quantified.

Implement a getSuccessors method for your Station class that returns a tuple of adjacent stations.

Punishment gluttons are encouraged to implement the model for the NYC MTA system instead. The NYC subway has “local” and “express” trains that run on parallel tracks.

Don’t Solve The Problem

If you’ve completed the above, you’re warmed up and ready to start Homework One. The early parts of Homework One review search algorithms from CSCI 3212 and 6212. The latter parts rely on algorithms we’ll learn in lecture two.