[PDF version of this document]| [HV Home]
DEVS assignment

DEVS assignment


General Information

The problem

The purpose of this assignment is to model the behaviour of car traffic on a straight stretch of road. This road is made up of a sequence of small road segments. Each road segment can hold only one car and is hence quite short (typically 10m as we assume trucks are not allowed on this stretch of road). If more than one car is present in a road segment, a collision occurs.
The model will consist of a Coupled DEVS model named RoadStretch. This model is made up of of a concatenation of one Generator Atomic DEVS, followed by a series of RoadSegment Atomic DEVS, and terminated by a Collector Atomic DEVS as depicted in Figure 1.
Figure 1: The Road Stretch
The following is a detailed description of the three different Atomic DEVS as well as of the Car, Query and QueryAck entities sent (as events) between the Atomic DEVS building blocks.


Cars are instances of the Car class and are generated by the Generator Atomic DEVS, passed through the sequence of RoadSegment Atomic DEVS, and finally end up at the Collector Atomic DEVS.
The Car class is a container for all the relevant information pertaining to a car. A car has the following attributes set at instantiation time: Note how, to keep things simple, dv_pos_max and dv_neg_max are not sampled from a distribution and will be the same for all cars. You are free to extend this and use random values.
Note that if one wished to model the car driver's quality of vision, one should add a parameter to the Car class encoding this.
We give the Car class an attribute distance_travelled which changes during the course of the simulation to reflect its changing state. The attribute distance_travelled is initialized (at instantiation time) to 0. Each time a Car object leaves a road segment, distance_travelled is incremented with L, the length of that road segment (not all road segments need to have the same length - note that in this assignment, all road segments do have the same length of 10m so it would be possible to just count the number of road segments traversed though that would not be very general). Thus, at each point in simulated time, distance_travelled will reflect the distance the car has travelled, irrespective of the traffic system's topology.
A Car attribute v will keep track of the car's current speed.
As shown in Figure 1, a Car instance is output through a Generator's car_out output port. It enters a RoadSegment through that Atomic DEVS' car_in input port and leaves again through that model's car_out output port. Finally, the Car instance enters the Collector Atomic DEVS through that model's car_in input port.

Query and QueryAck

The moment a car enters a new road segment, a Query message (an instance of the Query class) is sent to the next road segment through the sender road segment's Q_send output port. The receiver road segment will receive the query through its Q_recv input port.
This query is used to model, at a discrete event level of abstraction, the driver's observation of the next road segment for the presence of a car. In this discrete event model, where the road segments are the "active" components (the road segments are modelled as DEVS', not the cars, which are "passive"), the next road segment will, after some observation delay observ_delay, reply with a QueryAck message (an instance of the QueryAck class) through its Q_sack "query send acknowledgement" output port. The QueryAck message is received by the Query's sender on the latter's Q_rack "query receive acknowledgement" input port.
The Query class has no attributes. If the car driver's vision were modelled, it might carry that information though.
The QueryAck class carries information back about the presence of a car in the next road segment. It contains the single attribute t_until_dep. This value indicates how long it will take for the car (if present) to leave the next road segment. The following values can be returned:


A Generator generates Car instances on its car_out output port. The Inter Arrival Time (IAT) of cars is uniformly distributed over the interval [IAT_min, IAT_max].
A generator thus has the following parameters:
Note how a Generator has a Q_send output port and a Q_rack input port exactly like a RoadSegment. You may ignore this in your implementation. In a more elaborate model however, the Generator would, like a RoadSegment, look forward at the road segment ahead. If a collision could occur (a car is present in the next segment and the IAT is shorter than the time for that car to leave the next segment), the generator will delay producing the next car's arrival. Note how this strategy is also implemented in a GPSS GENERATE block.
It is the Generator's responsibility to:


The Collector is where Cars leave the system. Its main purpose is to collect statistics. In this case, we are interested in two performance metrics:
  1. The transit_time of each car: the time between departure from a Generator till the arrival in the Collector. To be able to compute the transit_time of each car, the Collector will take the difference between the arrival time and the departure_time stored as an attribute in the Car object. Note how a DEVS model has no access to a "global" time (only the DEVS simulator keeps track of this). This global time is needed to know the arrival time of a car in the Collector. You must thus add a state variable global_time to the Collector and keep it properly updated (in the external transition function, using the elapsed time).

  2. avg_v_pref_dev, the amount the average speed of each car deviates from that car's preferred speed. Each car's preferred speed is available as an attribute of that car object. The average speed of a car is computed by dividing the car's attribute distance_travelled by the car's transit_time.

Ideally, we would like as much insight as possible in the distribution of the above performance metrics. For simplicity, you should however not collect the distribution in a table (as requested in class), but only the average of these metrics.
Note how unlike a RoadSegment, a Collector does not have a Q_recv input port nor a Q_sack output port. This means that Query messages sent from the last RoadSegment will not go anywhere and hence that last RoadSegment will never receive a QueryAck. This is reasonable as a Collector has an infinite capacity for collecting cars. The fact that the last RoadSegment will never receive a QueryAck is not a problem. A car entering that last road segment will just continue at the v_old velocity at which it entered the segment. It is thus scheduled to leave that segment after L / v_old.


A road segment has the following parameters:
The RoadSegment Atomic DEVS will have a list cars_present as part of its state to keep track of the cars currently in that road segment. cars_present is initialized to [].
The moment a car enters a road segment (at velocity v_old, found in the car's attribute v), that road segment will first check if there are already cars present. If there are, the arriving car will be added to the cars_present list, and all cars' velocities v will be set to 0, denoting a collision.
If however, there are no cars present (the list of present cars is empty), the RoadSegment immediately sends a Query message to the model downstream, via the ouput port Q_send.
It also schedules a departure of the car at time L / v_old.
Note how there may only be one downstream model as otherwise there would be a choice of where to go. This should be modelled explicitly in a choice model.
Some elapsed time later, a QueryAck is received interrupting the scheduled departure. During that time, the car will have travelled a distance xi = elapsed * v_old. There still remains a distance remaining_x = L - xi to be travelled to leave the road segment.
Usually, the delay (due to observation time of the next road segment) is very short. If the road segment is connected to a Collector however, a QueryAck will never be received and the car will leave the road segment after the scheduled time L / v_old.
When a QueryAck is received, the road segment's external transition will handle it. It will update the distance still to be travelled, and retrieve from the QueryAck object, the t_until_dep of the car in the next road segment. This time will be used locally as t_no_coll, the minimum time the car must stay in the current road segment to not collide with the car in the next road segment when leaving. Note how collision may still occur as (1) the t_until_dep received in the QueryAck is only an approximation and (2) the car may not be able to slow down sufficiently within the remaining distance in the current road segment.
Let's first consider the case where there is no car in the next road segment and the t_until_dep received in the QueryAck is thus 0. This case is depicted in Figure reffig:noCarBefore in two examples.
Figure 2: Adapting speed, no car in road segment ahead
As there are no restrictions on the speed imposed by the next road segment, the car will want to update its speed to its v_pref. However, the car should not exceed the current road segment's speed limit v_max. The new target speed is thus min(v_pref, v_max). It may not be possible to attain this target speed due to the maximum velocity changes dv_pos_max and dv_neg_max. The final new speed v_new will take this into account. A departure is scheduled after t_until_dep = remaining_x / v_new.
Let's now consider the case where there is a car in the next road segment and the t_until_dep received in the QueryAck is thus a positive number. This case is depicted in Figure reffig:carBefore in two examples.
Figure 3: Adapting speed, car in road segment ahead
The special case of a negative number denoting plus infinity is considered later.
Now, we cannot just set the target speed to min(v_pref, v_max) as that might bring us to the next road segment too early (i.e., before the car in that segment has left). The time until departure must thus be the maximum of t_no_coll (obtained from the QueryAck's t_until_dep) and the time it would take to leave at the intended target speed remaining_x / min(v_pref, v_max). This will require an updated speed of remaining_x / max(t_no_coll, remaining_x / min(v_pref, v_max)). It may not be possible to reach this speed however due to the maximum velocity changes dv_pos_max and dv_neg_max. The final new speed v_new will take this into account. A departure is scheduled after t_until_dep = remaining_x / v_new.
If the car(s) in the next segment is/are standing still, as is the case after a collision, or due to a v_max = 0, a negative number (-1) will be returned as t_until_dep in the QueryAck. This means that the target speed is 0. dv_neg_max will determine whether it is possible to attain this speed. Note how there is nothing special about this case (compared to the one where the t_until_dep returned is a positive number).
Note how at any point during the t_until_dep, the model might be interrupted by a Query from the previous road segment (or generator) enquiring about the time until departure of the car currently present (if any). You must make sure to appropriately update t_until_dep (remember how an external transition forgets about the remaining time). You may either return in a QueryAck, a conservative dead reckoning estimate L / v or a more accurate estimate based on the updated t_until_dep.


Perform a few simulation experiments. Always choose the simulation duration sufficiently long enough to get statistically relevant measurements.
Choose some meaningful values for the various parameters to demonstrate the correctness of your model. For example, make the behaviour deterministic so it is possible to analytically determine the performance metrics.
Discuss your results !

Practical issues

You will use the PythonDEVS simulator found on the MSDL DEVS page.
You need DEVS.py and Simulator.py. Queue.py demonstrates how to model a cascade of processors (of jobs) in PythonDEVS.
An older version of this example is given in a report. The report gives background information on the implementation of the DEVS simulator.
Note that in PythonDEVS, when an external transition is triggered, this means that some external input has arrived on one or more of the ports. Using peek, you can check each of the ports for the presence as in p = self.peek(self.IN1) in an external transition function with a subsequent check if p == None: to determine whether the received external input arrived on port self.IN1.