This assignment will make you familiar with modelling, simulation, and performance analysis in DEVS.
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.
Note how the modelling view we will take is called active resource (as opposed to the active entity or agent-based view). In the active resource view, it is the resources for which there is competition (and as a result, queueing), the road segments, which are modelled as dynamic entities. In contrast, the cars moving around will be modelled as passive entities, passed around as (structured/parametrized) events between active resources. This is an antropomorphic view as road segments are obviously not active, and do not make any decisions. It is however a convenient abstraction/view which is commonly used when modelling queueing systems.
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 (and its driver). 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 (and hence slower reaction time), 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 and the particular route taken by the car.
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.
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 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 quality of 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:
Caveat: it may be useful to add an ID attribute to Query and QueryAck classes. This ID is set to the car's ID the moment a query is sent. When an acknowledgement is received, it is ignored if its ID does not equal the current car's ID. This covers the pathological case where the car which sent the query has already left the road segment, and a new car has already entered by the time the acknowledgement is received. Note that this can only happen for (unrealistically) very fast cars, short road segments, and long observation delays. It is an artifact of the high level of abstraction at which we build our model.
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[.
Every time a Car instance is generated, it is passed
a value for v_pref by the Generator.
This value is sampled from a uniform distribution over the range
[v_pref_min, v_pref_max[.
v_pref is a strictly positive real number as are
the lower and upper bounds.
For sampling from a uniform distribution, you should use Python's
random module which implements pseudo-random number
generators for various distributions.
A generator thus has the following parameters:
Tthe basic behaviour of a generator is:
keep output-ing cars, with IAT sampled from a distribution.
The problem with this is that it is very likely
that at the moment of car departure, there is still
a car in the first road segment, which will lead to
a collision. Given that in our simple model, collided
cars (velocity 0) never get removed, this will lead
to more collisions. After
a collision occurs, no more cars will ever make it to
the collector.
So, the generator should more accurately reflect what happens in the real world. You might have "scheduled" to drive away from home at a certain time, but the moment you want to leave, you first look ahead. If there is no car in front of you, you will leave, otherwise you will wait until the road in front is clear. This is what we need to model. It may make sense to draw a small state automaton to visualize the following logic.
The solution is for a Generator to have a Q_send output port and a Q_rack input port exactly like a RoadSegment. A Generator should, like a RoadSegment, look forward at the road segment ahead. If a collision could occur, the generator will delay producing the next car's arrival. Note how this strategy is similar to that used in a GPSS GENERATE block.
In the case of moving from road segment to road segment, we have some time to adapt our speed, based on the time it takes for the car in the road segment ahead to clear that segment. Here, as the car leaves the generator immediately the IAT is over, we should not leave when we find out there is a car in the first road segment.
This implies that we need to not produce a car output when the IAT elapses, but rather need to go into another mode in which we immediately (after time delay 0) produce a query output to check if there is a car in the first road segment. If we were to use a non-zero time-delay, that would bias our IAT distribution which does not reflect reality. The fact that it will take a while to receive an acknowledgement to the query is reasonable. This delay is the observation delay. Note that after we output the query, we keep waiting (until we receive an acknowledgement) for a duration INFINITY as we really need to know what lies ahead. In the (pathological) case of direct connection of a generator to a connector, the generator will never receive an acknowledgement and will wait forever. You may assume such a model is syntactically incorrect and will never be used.
When the reply received indicates there is no car ahead, we can output the car immediately. Note that receiving an acknowledgement triggers the external transition function. It is however only at the time of an internal transition that an output can be generated. So, we need to add another zero time delay after which a car should be output and a transition is made to the original mode, where we will stay for IAT time.
When the reply received indicates there is a car ahead, we need to wait. As for a regular road segment, we will schedule our departure after a time given by the t_until_dep attribute of the reply received.
A special case of car(s) ahead is when the acknowledgement received holds INFINITY. This means the() car(s) ahead is(are) stopped. The above logic will from then on never send cars. In case the car ahead was only temporarily stopped, this is not realistic. We will however ignore this case for the assignment.
In addition to the above, it is the Generator's responsibility to:
The Collector models the road system's "environment" accepting Cars leaving the system. Its main purpose is to collect statistics. In this case, we are interested in two performance metrics:
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, 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 there are no cars present however (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 2 in two examples.
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 3 in two examples.
The special case where t_until_dep is INFINITY is discussed 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, INFINITY 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 reasonable number of 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. In particular, make the behaviour deterministic, for some extreme cases, so it is possible to analytically determine the performance metrics.
Discuss your results !
You will use the pydevs (Python DEVS) simulator found on the MSDL DEVS page. You are strongly advised to first study the Queue example (presented in class) in the examples directory before starting on this assignment.
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.
Maintained by Hans Vangheluwe. | Last Modified: 2008/09/09 15:13:19. |