• The due date is Wednesday 2 January, before 23:55.
  
  
• Submissions must be done via BlackBoard. Beware that BlackBoard's clock may differ slightly from yours. All results must be uploaded to BlackBoard and accessible from links in the main (index.html) file.
  
  
• The assignment must be made in groups of maximum 2 people. It is understood that all partners will understand the complete assignment (and will be able to answer questions about it). Clearly identify who did what.
  
  
• Grading will be done based on correctness and completeness of the solution. Do not forget to document your requirements, assumptions, design, implementation and modelling and simulation results in detail!
  
  
• To get feedback about the assignment workload, provide the number of hours you spent on this assignment.

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.

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.

Car

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:

• A unique car ID.
  
  
• v_pref: the car(driver)'s preferred speed. Whenever adjusting its speed, the car will try to attain this speed. This speed may not be attained in the current road segment due to a speed limitation (v_max) of a road segment or due to the inability to accelerate or decelerate too much in one road segment. The value of v_pref is, at instantiation time, passed to the car by the Generator.
  
  
• dv_pos_max: the car's maximum acceleration (velocity increase), over one road segment. A positive number.
  
  
• dv_neg_max: the car's maximum deceleration (velocity decrease), over one road segment. A positive number.
  
  
• departure_time: the time at which the car leaves the Generator. It is the Generator's responsibility to assign this value.
  
  

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.

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 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:

• 0 if there is no car present in the next road segment.
  
  
• A strictly positive number if there is a car present in the next road segment. This value gives the earliest time interval after which it is safe to enter the next road segment. It is safe to enter the next segment when that segment becomes empty. The value is thus calculated as the time it takes for the car in the next segment to leave that segment. This is calculated as the length of the next road segment divided by the speed of the car in that road segment at the time of the query. Note that this is only an approximation. This makes sense as a human observer can also only approximate the time it will take for the car in the next road segment to leave that segment. Such an approximation is called "dead reckoning": it is assumed that the car in the next segment will maintain the same speed as at the time of the observation. Note also how we are conservative and do not use the remaining distance to be travelled in the next road segment but rather the full length of the next road segment.
  
  
• INFINITY will be returned if the car in the next segment has velocity 0. This typically occurs when a collision has happened and multiple cars pile up, all with velocity 0.
  
  

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.

Generator

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:

• IAT_min: IAT lower bound.
  
  
• IAT_max: IAT upper bound.
  
  
• v_pref_min: lower bound on v_pref.
  
  
• v_pref_max: upper bound on v_pref.
  
  

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:

• Assign the car's v_pref by sampling from a uniform distribution over the range [v_pref_min, v_pref_max[.
  
  
• Assign the car's dv_pos_max.
  
  
• Assign the car's dv_neg_max.
  
  
• Assign the car's departure_time: the time at which the car leaves the Generator. 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 assign to departure_time. You must thus add a state variable global_time to the Generator and keep it properly updated (in the internal transition function, using the IAT -- beware of not sampling the IAT distribution twice !).
  
  
• Assign the car's initial velocity v. There are several choices possible depending on what kind of "environment" we are modelling in the generator. If the arrival is from the exit of a parking lot for example, it makes sense to give all cars initial velocity v=0. If the arrival is from an arbitrary traffic system, one may wish to sample the arrival velocity from some distribution. Another approximation is to let each car enter at its v_pref. Note how in the latter case, it will never be possible for a car to travel faster than its v_pref given the velocity adaptation scheme we use.
  
  

Collector

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:

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, 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.

RoadSegment

A road segment has the following parameters:

• L: the length of the road segment.
  
  
• v_max: the maximum allowed speed in the road segment. The maximum speed may be due to road conditions (potholes in Montréal roads for example) or due to speed limit road signs. We assume cars will (try to) avoid speeding.
  
  
• observ_delay: the time it takes before the road segment replies to a Q_send query message received on its Q_recv input port. A reply comes in the form of a QueryAck message through the road segment's Q_sack "query send acknowledgement" output port. The observ_delay models the observation delay and encodes factors such as the visibility in the observed road segment. Note that we are not modelling the quality of the car driver's vision here. observ_delay is purely a property of a road segment (and is not determined by a property of the car/driver). A reasonable choice for observ_delay in the context of this assignment is 0.1s.
  Overall driver reaction time depends on many factors and includes for example muscle movement time, and brake engagement time. These factors are nicely discussed in the article "How Long Does It Take To Stop?". These factors are not taken into account in our model.
  
  

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.

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 3 in two examples.

Figure 3: Adapting speed, car in road segment ahead

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 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 in the examples directory before starting on this assignment.

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.