13. Events in the Road Network
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2015
|
We've been promising to create a simulation system that moves vehicles through a road network, but up to this point, we've concentrated only on the network itself. Here is the event code we've maintained up to this point:
class Event {
/** Events mark arrival of vehicles at Intersections.
* @see Intersection
* @see Vehicle
*/
float time; //when the vehicle arrives
Intersection place; //where vehicle arrives
// Bug: is this right? There may be many queues at intersection
// Bug: how do we know which queue the road leads to?
}
This code is useless! It is time to start rethinking it and building something that works. To work on this, we need to back off and think of what goes on in a real road network, and then reduce this to code. Consider a trip in a vehicle:
Roads: In the simplest case, assuming cars travel at the speed limit and there is no delay due to congestion, the travel time down the road is fixed by the length of the road and the speed limit. Call this time tr. Under these assumptions, we can predict that a vehicle entering a road at time t will arrive at the intersection at the far end of the road at time t+tr.
If we want to develop a model for congestion, the impact of congestion is a function of the road itself. In that case, the travel time for the road might increase as some function of the the population of the road. The population of the road clearly increases by one with the arrival of each vehicle and decreases by one each time a vehicle reaches an intersection. The key point, here, is that the travel time on any particular road will be a function of the state of that road and not of anything else.
Intersections: When a vehicle arrives at an intersection, its behavior depends on that intersection and the vehicle's travel plans. The travel plan determines just one thing, which outgoing road the vehicle selects. Everything else depends on the intersection. Intersections may have internal queues of vehicles waiting at stop signs or stop lights. They may have rules governing how long it takes a vehicle to traverse the intersection. These details can be quite complex, but we can draw some conclusions:
First, the arrival of a vehicle at an intersection at time t may predict the immediate departure of that vehicle. For example, when a car arrives at an uncontrolled intersection that is not currently occupied by another vehicle, it sails through. In this case, if ti is the time it takes to traverse the intersection, the car will enter its departing road at time t+tr.
Second, if an intersection is occupied, if there is a stop sign, or if there is a stop light, a vehicle arriving at an intersection will enter one or perhaps one of several queues of waiting vehicles . In that case, arrival does not predict the departure time of that vehicle. Rather, when a vehicle leaves the intersection at time t, if there are any waiting vehicles, one of them will be selected to leave the intersection at time t+tr.
From this, we conclude that there are at least the following types of events:
Note that entry to a road implies departure from the source intersection of that road, and departure from a road implies arrival at the destination intersection of that road. Therefore, we may simplify things a bit, but we still need to flesh out our road and interseciton classes to account for these events.
To see how this works, consider just class Road. We need to add a new method enter() to mark the fact that a car arrives at a road. This might look something like the following:
public void enter( Vehicle v, float t ) {
/** simulate v entering this road at time t.
*/
// report that v has left the source intersection
source.exit( v, t );
// BUG must schedule this.exit( v, t + travelTime )
}
public void exit( Vehicle v, float t ) {
/** Simulate v exiting this road at time t.
*/
// report that v will enter the destination intersection
destination.enter( v, t );
}
Note that this code is quite incomplete, but it establishes a framework on which we can build. For example, this code uses a constant travel time, but in a real road network, the travel time can depend on the number of vehicles on the road. Below some congestion threshold, the traffic tends to move at the speed limit, but once the number of cars reaches this threshold, the traffic generally slows rather abruptly. This is not the place to study the mathematics of congestion, but any model attempting to take congestion into account must track the number of cars on each segment of road. We can do this by adding a new field to each road, population. This is initially zero. Then, we update the enter() and exit() methods to manage the population:
class Road {
...
int population; //how many vehicles are here
...
public void enter( Vehicle v, float t ) {
/** simulate v entering this road at time t.
*/
// report that v has left the source intersection
source.exit( v, t );
// update the state of the road
population = population + 1;
// BUG must schedule this.exit( v, t + travelTime )
}
public void exit( Vehicle v, float t ) {
/** Simulate v exiting this road at time t.
*/
// update the state of the road
population = population - 1;
// report that v will enter the destination intersection
destination.enter( v, t );
}
Intersections are significantly more complex. The behavior of an intersection depends on the type of intersection, so first we need to worry about the abstract class:
abstract class Intersection {
...
// simulation methods for Intersection
public void enter( Vehicle v, float t );
/** Simulate v entering this intersection at time t.
*/
public void exit( Vehicle v, float t );
/** Simulate v entering this intersection at time t.
*/
...
}
Now, for each class of intersection, we need to add behavior. Our first-approximation model of an intersection is that only one vehicle at a time can enter the intersection. If the interseciton is occupied, the next vehicle must wait. Here, we'll concentrate on the simple uncontrolled intersection, adding two two new state variables to track the state of the intersection: A boolean to track whether the intersection is occupied and a queue of vehicles waiting to enter the intersection.
class NoStops{
...
boolean occupied = false; // intersection initially unoccupied
List queue = new List (); // empty queue
...
}
When a vehicle enters the intersection, its behavior depends on the state of the intersection. If the intersection is occupied, the vehicle goes onto the queue, while if the intersection is unoccupied, the vehicle zips through to the next road:
// simulation methods for uncontrolled Intersection
public void enter( Vehicle v, float t ){
/** Simulate v entering this intersection at time t.
*/
if (occupied) {
// Bug: queue vehicle v on queue
} else {
occupied = true;
Road d = v.pickRoad( outgoing );
// Bug: schedule d.enter( v, t + travelTime )
}
}
Of course we need to figure out how to use a linked list as a queue, but that can wait. First, we'll focus on what to do if the intersection is unoccupied: We occupy it, setting the state to occupied, and then we ask the vehicle to pick an outgoing road. How the vehicle picks an outgoing road is its business, so we'll have to add a method to vehicles to permit that.
Finally, having picked an outgoing road, we schedule the vehicle to enter that road after the time it takes to cross this intersection. The code already presented shows that entering the next road causes the vehicle to exit the intersection, so we finish the job in the exit method:
public void exit( Vehicle v, float t ){
/** Simulate v entering this intersection at time t.
*/
if ( /* Bug: queue empty */ ) {
occupied = false;
} else {
// Bug: Vehicle v = dequeue from queue
Road d = v.pickRoad( outgoing );
// Bug: schedule d.enter( v, t + travelTime )
}
}
Like the enter method, the exit method offers two different behaviors, but in this case, the difference depends on whether or not other vehicles are awaiting entry to the intersection. If none are waiting, we simply reset the occupied flag. If some are waiting, we grab a waiting vehicle and let it through.
In the above code, we've assumed that vehicles have a pickRoad() method. This method is given a list of roads and selects one of them as the next road the vehicle will follow. How does a vehicle pick a road? The stupidest algorithm is to select an outgoing road at random. More intelligent simulation models might use some kind of intelligent route finding algorithm, or they might incorporate a plan (from Park Road, turn onto Lee Street, and then onto River Street to Wolf Road, and from there, take Newton Road). For this example, let's stick with something simple. We'll pick an outgoing road at random. This requires that we have a random-number generation mechanism.
A quick web search reveals that Java offers several choices for generating random numbers. The most flexible is a utility package called Random. This is actually too general, but we'll use it and then criticize:
import java.util.Random;
class PRNG {
/** Pseudo-Random Number Generator for simulation model.
*/
private static Random r = new Random( 1 );
public static int randInt( int n ) {
/** Draw an integer in the range 0 <= i < n from the stream.
return r.nextInt( n );
}
}
A pseudo-random number generator is an algorithm that generates a sequence of values that appear random, except that each value in the sequence is entirely determined by the previous value. PRNGs are widely used in computing. Some are painfully obvious (for example, the values alternate even-odd-even-odd). Others are good enough to use in cryptography. For any pseudorandom number generator, if you start it from the same seed value, it will always generate the same sequence of values.
We are starting our generator from the seed value 1. (The initializer Random() takes the seed as its parameter. Starting with a fixed seed means that each time we run our simulation model, it will behave exactly the same as the previous time. This means that, if we find an error, we can run it again and again to try to debug the error. Had we changed the seed from run to run, we might never be able to recreate the error in order to debug it.
The Java random package offers an alternative initializer that creates random streams with a different seed each time you call it -- the details of this will vary from computer system to computer system, but imagine, for example, using the date and time as a seed, or using the number of seconds since the computer was rebooted, or some combination of these. In production, using a different seed each time you simulate the same model lets you see the extent which your results depend on luck and the extent to which they are repeatable.
Now to the criticism: Maintaining multiple streams of random values in an application is dangerous. If two streams are started from the same pseudo-random number generator and you draw numbers from one stream for one purpose and from another stream for another purpose, you run the risk that the numbers will be correlated with each other. Use the wrong seed values, for example, and you might find yourself drawing the same numbers from the two generators, with one stream simply offset from the other by a few steps. Therefore, the code given above creates a global static stream and draws numbers from it for whatever purpose we may have.
Given this, we can now create vehicles that make navigation decisions on a random basis:
class Vehicle {
/** Vehicles travel on roads through intersections
* @see Intersection
* @see Road
*/
// Bug: do I need my current location?
public Road pickRoad( List roadList ) {
/** Pick a road in a really stupid way.
* Clearly, later versions could use more
* intelligent algorithms here!!!
*/
return roadList.get( PRNG.randInt( roadList.size() ) );
}
}
This looks at the size of the road list in order to decide the range of random numbers to use, and then is uses the selected random number to pick one road from the list.
We could also use the same random number stream to perturb the travel times, for example, we could multiply each travel time by a random value between 0.9 and 1.1 in order to add realistic variation to the times, or even better, we could use a gaussian distribution
This looks at the size of the road list in order to decide the range of random numbers to use, and then is uses the selected random number to pick one road from the list.
We could also use the same random number stream to perturb the travel times, for example, we could multiply each travel time by a random value between 0.9 and 1.1 in order to add realistic variation to the times, or even better, we could use a gaussian distribution
This looks at the size of the road list in order to decide the range of random numbers to use, and then is uses the selected random number to pick one road from the list.
We could also use the same random number stream to perturb the travel times, for example, we could multiply each travel time by a random value between 0.9 and 1.1 in order to add realistic variation to the times, or even better, we could use a gaussian distribution. That, however, is a topic to put off until you have a statistics course under your belt.