Project 4

Due Thursday, August 9 at 6 p.m.

IMPORTANT: No work will be accepted after 5 p.m. on Friday, August 10. Unlike previous assignments, you will only have one extra late day in which to submit the assignment.

Remember to consult the programming guides on the Assignments page and the examples directory ~hsc/classes/270/examples/C++ on CDF.

For the final project of the class, you will implement and play with a traffic simulator. The simulator will attempt to model rush hour traffic. Most of the simulator is written for you so your job is to think of changes we can make in the real world to reduce the gridlock at rushhour, modify the simulator to model those changes, and then test the new simulator to see how your changes affected the traffic behavior. In the end, you will write a short report summarizing your results. The main goal is to have a little fun with your coding.

1. Traffic Simulation, Implementation (50%)

First I will discuss how the simulator is implemented. A basic simulator is provided for you. To complete the implementation, you will have to add in the queue and graph datatypes and the shortest path algorithm which you have previously implemented. If you were unsuccessful in implementing any of these programs, object code and header files for these modules will be provided after Project 3 is due, and you can compile these into the simulator. However, I think it will be nicer if you use your own implementations.

The simulator inputs a street network. The street network will be represented as a graph in which the vertices are intersections and the edges are street segments, and we will have cars drive the street network. Each car will depart from its source intersection at a specified time and will navigate the network until it comes to its destination intersection.

The other interesting feature of the simulator is that we will have traffic lights at each intersection to control the flow of traffic.

• Entities: Our simulation will have the following entities:
  • cars: A car is the basic entity of the simulator. Each car will have a starting intersection, a destination intersection and a departure time. The car will leave its starting point at the proper time and navigate the network to the destination.
  • street segments: A street represents the piece of road between two intersections. A street will have a length which indicates how long it will take a car to traverse it, a capacity indicating the maximum number of cars it can hold, and a speed which indicates the number of cars that may flow through at each given interval. We will implement a street with a queue.
  • intersections: An intersection is a node in the graph.
  • traffic lights: Each intersection will include a traffic light. The traffic light will have to include information on the period of its cycle and which streets may move during a green light state.
  • clock: We will need an internal clock to keep track of time.
• Events: We will need to consider the following types of events:
  • The simulation starts.
  • A car begins its trip.
  • A car arrives at an intersection.
  • A traffic light changes state.
  • A car arrives at its destination.
  • A status report is made.
  • The simulation ends.
  Depending on your simulation, there may be other types of events.
• Groupings: Each intersection will have to be grouped with its appropriate street segments and traffic lights, and all the intersections will need to be grouped into an entire network.
• Relationships: An obvious relationship is that a car may be in the network.
• Random Variables: We will use probibalistic distributions to determine the source and destination intersections of a car as well as its departure time.
• Strategies: These are up to you. It will be interesting to see how the traffic patterns change as you change parameters of the system.
• Measurements: You will need to come up with ways of measuring how the system is performing.

Implementation Details

Each street segment will include a queue to hold the cars. The simulator provided assumes that you implemented the queue to hold only int, in which case the index of the car is stored on the queue. If you implemented the queue to hold any datatype, you may store the actual Car object on the queue.

When a car is placed on a queue, it is given a time at which it may be taken off of the queue. This corresponds to the length of time it takes to travel a stretch of road. If the car is at the head of the queue, if the light is green, and if there is room on the next desired street queue, the car is removed from the queue it is on and placed on the next queue. If there is no room on the next street, the car and all cars behind it cannot move and we have a traffic jam.

To read in the network, the first value is the number of intersections in the network. After that, there is one line per street, and the data is in the form from intersection (the street runs from this vertex), to intersection (the street runs to this vertex), length (how many clock ticks after a car is added before it may be removed), capacity (the maximum number of cars that will fit), and speed (the maximum number of cars that may be removed from the queue in one clock tick). The street data is terminated by a negative value.

Next comes one line for each intersection in the network. The first value is the intersection number, the next four values indicate the north, east, south, and west streets. These numbers correspond to the intersection that each street comes from. A -1 indicates there is no incoming street in this direction. The directions are important because we want north and south streets to have a green light at the same time while east and west have a red. The last two values are probabilities. The first is the probability that the intersection will be a source intersection for a car, and the second is the probability that the intersection will be a destination for a car.

A sample network:

5
0 1 20 50 4
1 0 20 50 4
1 2 30 50 2
2 1 30 50 2
2 3 30 40 2
3 2 30 40 2
3 0 20 50 4
0 3 20 50 4
0 4 40 20 1
4 0 40 20 1
1 4 30 15 1
4 1 30 15 1
2 4 30 10 1
4 2 30 10 1
3 4 50 15 1
4 3 50 15 1
-1
0 3 4 1 -1 .24 .15
1 4 2 -1 0 .24 .15
2 3 -1 1 4 .24 .15
3 -1 2 4 0 .24 .15
4 3 2 1 0 .04 .40

The basic simulator provided is a time-driven, probabilistic simulator. The simulator will be controlled by command line arguments. The initial simulator will have the following arguments: -cars c sets the number of cars in the simulation, -start s sets the initial value on the simulator clock (this may be any positive integer) and the earliest that a car may depart, and -end e which is the latest that a car may depart.

For example, the command:

trafficsim -cars 1000 -start 1000 -end 2000

To make your life easier, you may save the network description given above into a file and pipe this into the program.

trafficsim -cars 1000 -start 1000 -end 2000 < city_map

Makefiles

The simulator will involve compiling together many different files. To make your life easier, you will use a makefile to handle the compilation. The makefile is a script in which you indicate how the code is to be compiled. When you type make or make trafficsim, the script will examine the timestamp on your source code, determine which files need to be recompiled, and recompile the necessary ones. This is very nice when dealing with projects that contain hundreds of files because you do not want to recompile each of the files everytime you make a minor change. You will be provided with a makefile for the simulator. Take a look at the file so you understand how it works, and for each new module you add to the simulator, you will need to update the makefile.

Programming Tasks

1. Your first task is to add in the necessary modules to get your program to run. You will have to search for places that I places lots of "*"s. There I indicate what is needed.
2. The simulator uses a uniform probability distribution to determine when in the simulation interval a car departs. This is not very realistic because we know that rush our traffic is anything but uniform. Try coming up with a different distribution to model the departure times. For example, you may use a normal distribution in which the mean is the midpoint of the start, end range and set the standard deviation to be about 1/6 of the range. This will mean 2/3 of the cars will depart during the middle third of your range and 95% will depart during the middle 2/3 of your range. You may experiment with these parameters or come up with a different distribution that better models rush hour traffic.

Now you should play with the simulator. Modify some parameters to see what happens. Then, come up with ideas on how you can change the simulator to affect the way the traffic flows. It will be interesting to see whether you can make changes which reduce gridlock. Here are some ideas, but you are free to try whatever you want:

• Currently, the each car performs a shortest path calculation to determine the path from the source to the destination, but this path does not take into account possible traffic delays. Try modifying the simulator so that, when a car is about to depart, it estimates the shortest path based on the road conditions. You will have to add some sort of parameter which estimates the load on each street edge.
• Maybe you can do better and have a dynamic shortest path algorithm. For example, you may assume that we have "traffic reports" periodically, and each car uses the traffic report and finds the shortest path from its current location to its goal.
• Try changing the cycles of the traffic lights. For example, you may make the lights have sensors. A light will not change its state until a car is at the intersection on one of the streets with a red light.
• Perhaps you can make the lights more intelligenct. A formula called Webster's formula may be used to determine the average delay of a car at a light. The formula is estimated by

       delay = 9/10[(c(1-m)^2)/(2(1-mx)) + (x^2)/(2q(1-x))]
   

  where c is the cycle time of the light, q is the average number of vehicles per clock tick that pass through the intersection, m = g/c where g is the length of the green light - 2 ticks (for acceleration), and x = q/ms where s is the maximum number of cars per clock tick which may pass through.
  What if each intersection can periodically recalculate the proper time of its green light for each side (g in the above equation) to minimize the delay? This will involve finding the root of a polynomial, but you can plug in the code from Project 1.
• Do something else.

These suggestions are just a few possible choices, but you can try your own ideas. You may modify the simulator code and the code of your other modules (queues and graph) as you wish. Depending on the tests you run, you will probably want to change the data currently output by the simulator. Right now, it measures the difference between when a car actually arrives and when it would have arrived if there was no traffic and no lights.

You are to submit electronically your makefile all files that are needed to compile and run your code. We will test your code by running make to compile it and then we will run various tests on it.

Please remember that style is still important so be certain to comment your code, and please break your code into functions and separate files depending on its functionality.

Here is the code for the simulator.

• Makefile
• trafficsim.cpp
• network.cpp
• cars.cpp
• random_numbers.cpp
• network.h
• cars.h
• random_numbers.h

2. Traffic Simulation, Analysis (50%)

In this part, you will analyze the results of your simulations from part 1. You should write a short report (1 or 2 pages) which discusses what you decided to simulate and what results you obtained.

Your grade will depend on the simulations you decided to do, how well you implemented the simulations, the tests you performed, and how you present your results. As a result, you should spend a little time to decide how to best present the output of your simulator. For example, you should summarize your output and present the important details instead of simply reproducing the voluminous output of your programs! Also use the statistical techniques discussed in class to analyze your results.

If you are unable to do many tests because you had troubles with the implemention, report on the data that you do have, describe the simulation you were trying to implement, and discuss what further tests you would like to make, if you had additional time.

For each of the tests summarized in your report, you must list the command line arguments you used on the simulator to run the test. It is important that your report matches the simulator you submit. If the grader does not feel that your program is capable of running the tests and producing the output you claim, you will receive an extremely poor mark!

Try to have some fun with this project. Rather than figuring out what would give you a good grade, choose a test which you want to try, modify the simulator and run some simulations. Perhaps the results of those simulations will give you another idea to test, and then write a report comparing and evaluating your different tests and their results. The end result will be a nice final project.

Place your written report in the class drop box.