16. Building a Simulation

Where Are We

At the end of the last lecture, we presented this lambda-expression based simulation framework:

/** Framework for discrete event simulation.
 */
public class Simulator {

    public interface Action {
        // actions contain the specific code of each event
        void trigger( double time );
    }

    private static class Event {
        public double time; // the time of this event
        public Action act; // what to do at that time
    }

    private static PriorityQueue<Event> eventSet
        = new PriorityQueue<Event> (
            (Event e1, Event e2)-> Double.compare( e1.time, e2.time )
        );

    /** Call schedule to make act happen at time.
     *  Users typically pass the action as a lambda expression:
     *  <PRE>
     *  Simulator.schedule( t, ( double time )-> method( ... time ... ) )
     *  </PRE>
     */
    static void schedule( double time, Action act ) {
        Event e = new Event();
        e.time = time;
        e.act = act;
        eventSet.add( e );
    }

    /** run the simulation.
     *  Call run() after scheduling some initial events to run the simulation.
     */
    static void run() {
        while (!eventSet.isEmpty()) {
            Event e = eventSet.remove();
            e.act.trigger( e.time );
        }
    }
}

Using the Framework

Let's start with something simple (and pretty useless): Scheduling the end of time. Given that endTime is a variable set to the end of time, we could do this by adding the following to the initialization code in the main method or perhaps in buildModel:

Simulation.schedule( endTime, (Double t)-> System.exit( 0 ) );

Note that the lambda expression requires a parameter, the time, but that this parameter is not used in the body of the expression. This parameter is needed so that the Java compiler can match the lambda expression with the interface Simulator.Action.

Of course, we ought to provide some way to specify the end of time. It would make sense to allow a command in the model specification file to give the end of time, but it would also make sense to allow the end to be read as a command line argument, or even from both, ending the simulation with whatever comes first. The easiest way to do that would be to simply schedule the end of time if there is an end-time command line parameter, and also to schedule the end of time if there is an end command in the input file. With two end events in the pending event set, whichever comes first does the job.

Finally, it might be nice to allow users to be able to specify times in familiar units like days, hours, minutes and seconds, instead of just using dimensionless floating point numbers. A system of time units requires that, everywhere a time is read from any source, a time unit may follow. Typically, we would convert all times to some standard unit internally, perhaps days, or perhaps seconds, it hardly matters so long as times are also converted to human readable form in any simulation output.

A Simple cyclic series of events

In our road-network simulatioin, stop lights can have a very simple behavior: the light changes every p seconds, where p is the period of the stop light. In the real world, this models only the simplest of stoplights. Real stop lights may have different times for side roads than they have for arterial roads, and they may be reactive, waiting until they sense sensing waiting traffic on a side road before they offer a green light in that direction. We'll ignore that complexity here.

The first thing we must do to simulate stop lights is augment the StopLight class with an instance variable, the period of that stop light, and read this from the input line. We could use the following format in our road-network description file:

intersection N 1.4 stoplight 30

Assuming that times are given in seconds, this indicates an interesection named N where cars can cross the intersection in 1.4 seconds and where there is a stop light which changes every 30 seconds. It is pretty obvious that period should be an instance variable of each stop-light object, and it can be final, since for trivial stop lights, the period is a constant. In the constructor for stop-lights, we add this code:

period = sc.getNextFloat( 0.1F,
    ()-> super.toString() +": stoplight: expected period"
);
if (period <= 0) {
    Error.warn( this.toString() + ": negative period?" );
} else {
    Simulator.schedule(
        period, // BUG - Should we multiply by a random from 0.0 to 1.0?
        (double t)-> this.lightChange( t );
    )
}

One interesting puzzle in the above code involves the two error messages, one uses super.toString while the other uses this.toString. There is a compelling reason for this. These calls are from inside a constructor for an object. Within a constructor, every call to this.anyMethod needs to be thought about with great care. The reason is, this object is still under construction. Calls to methods after the object is fully constructed are safe, but before construction is complete, the methods called should never reference fields that have yet to be properly initialized.

In the case at hand, the call to super.toString is in the middle of code to initialize a final variable in the object, period. Furthermore, the toString method for stop lights needs to output the period as part of the description of this stop-light.

Within the constructor, it is safe to use super.toString because the very first line of the stop-light constructor is a call to the constructor for the superclass. After that is called, all fields in the superclass are properly initialized, so it should be safe to call super.toString or any other method of the superclass.

The above code is mostly about getting the period, but note that if a valid period is found, the code immediately schedules a lightChange event for this stop light. So, we must add an event to change the light:

private void lightChange( double time ) {
    Simulator.schedule(
        time + period,
        (double t)->> this.lightChange( t );
    )
    // BUG -- no concept of incoming roads getting unblocked on a green light
    // BUG -- no way to release waiting queue of vehicles
    
    System.out.println( this.toString() +": light change at t = "+ time );
    // BUG -- the above is just for debugging, to prove that it works
}

The above code has each light change schedule the next light change at a time that advances, and it includes a print statement for debugging only to show the time at which this light changes.

Adding Vehicle Behavior

We have a Java program that builds an internal representation of a road network on the computer, and we have a pending event set mechanism (actually two of them), so it's time to marry the two and create a simulation of a road network.

Of course, we need to add some things to our road network to do this:

• Vehicles: Where do they come from and where do they go?

• Behavior: How do vehicles behave as they traverse a road?

Vehicle Sources and Destinations

One way to add vehicles to a highway network is to add some new classes of intersection, vehicle sources and sinks. In the real world, these might model roads coming into the highway network from the outside world and roads leaving the highway network, or they might model parking lots.

In the simulated world, vehicle sources create new vehicles out of nothing and spit them out into the road network. Similarly, vehile sinks consume any vehicle that enters them, utterly and completely destroying those vehicles.

In our model, we'll keep things simple with the following two new intersection types:

• Vehicle sources: There could be several kinds of sources with different behaviors. For example, we could have sources that behave differently depending on the time of day. Here, we'll keep things simple, sources simply inject vehicles at random times, and they are characterized by just one parameter, the median interval between vehicles. The textual description of a source intersection will look very much like the textual description of a stop light:

  interseciton X source 3.5
  

• Vehicle sinks: If we were traffic engineers, we'd make the sink intersection accumulate some kind of statistics about the life history of each vehicle as it is destroyed, but since we're just building the simulation engine, we'll ignore that. Sinks could look like this in our textual language:

  interseciton Y sink
  

Adding source intersections to the program

We need to add parsing support for source intersections. Step 1 in this venture is to just parse the details of the source and store the parameter values. This is straightforward code that is no different from the code we've already given for stop lights. The two classes begin to diverge only when we get to the simulation methods. For a source intersection, as in a stop light, the constructor schedules an event that schedules an event that schedulesd an event, for ever until the end of time. In the case of the stop light, these events are strictly periodic. In the case of source intersections, the interval between successive cars arriving into the simulation model from the most basic type of source intersection should be random. So, the repeating event code looks like this:

private void produce( double time ) {
    Simulator.schedule(
        time + period, // BUG -- need to randomize time of next production
        (double t)-> this.produce( t )
    );
    // BUG -- produce a vehicle v
    // BUG -- what is the travel time of a source intersection?
    // BUG -- pick an outgoing road r
    // BUG -- r.enter( time, v );

    System.out.println( this.toString() +": produces at t ="+ time );
}

Here, aside from bug notices, this code is still the same as the code for the stop-light, but the bug notices hint at an entirely different direction for the development of this code:

• The interval between successive events will need to be randomized.
• We need to figure out how to produce vehicles. For that matter, we need to figure out if we even need to represent vehicles with any data structure at all.
• Two vehicles cannot leave the same intersection at the same time, so the travel time of a source intersection gives the minimum time between vehicle departures. How does this work?
• We need a mechanism to decide, for each vehicle, which outgoing road to take from the source intersection.

As we will see later, some of these problems apply to all intersections. We need to further develop the model to fully appreciate this.

In contrast, the Sink subclass of Intersection is relatively easy. We won't give the code here to parse vehicle sinks, and we note that sinks simply consume vehicles and discard them. In a fully developed model, the sink could also gather statistics, but we won't do that here.