Modeling a Roundabout with DEVS

Files

All files can be found here.

Each atomic DEVS was implemented in its own module.

Files:
car.py - The class representing a car.
constant.py - Constants shared by several modules.
exit.py - The road segment taken when the car exits the roundabout.
generator.py - Generates the cars.
quadrant.py - A curved section of the roundabout.
roundabout.py - The coupled DEVS glueing all atomic DEVS together.
segment.py - A road segment between the generator and the roundabout.
state.py - State module from our project. Contains state variable classes to compute metrics.

Only the QueueVar and State classes from state.py were used in this assignment. A rough draft of the API documentation can be found here.

Model

We describe briefly our model and some design decisions below. Please refer to the source files for complete documentation on individual atomic DEVS.

Overall View

Our model is composed of 4 types of atomic DEVS. Four instance of each type is used. Below is a list of all atomic models instances, the A? is the ID used by the simulator in the output.

A1  => Generator North
A2  => Generator South
A3  => Generator West
A4  => Generator East

A5  => Segment North
A6  => Segment South
A7  => Segment West
A8  => Segment East

A9  => Quadrant NE
A10 => Quadrant SE
A11 => Quadrant NW
A12 => Quadrant SW

A13 => Exit N
A14 => Exit S
A15 => Exit W
A16 => Exit E

Select Function

In case of conflicts, the atomic DEVS with highest priority is chosen. If there are several DEVSs with the same highest priority then the first DEVS of that highest priority in the IMM list is chosen.

A Quadrant has a priority of 2, a Segment has a priority of 1 and all other DEVS a priority of 0.

Generator

Generates the cars using an uniform distribution. It is also possible to specify at what time the first car is generated. By default a car is generated at time 0 but it is possible to specify different starting time for different generators.

Segment

The segment maintains a list of cars currently on the segment with the time left before they reach the roundabout. A car with a time left of zero means that it has reached the intersection. Negative time lefts are to be interpreted as a positive waiting time i.e a time left of -10, means that car has been waiting for 10 seconds. When more than one car are waiting on some segment to go on the roundabout, the order they engage in the roundabout (when possible) is in FIFO order.

The state of the segment is a cross-product of three boolean variables: wait, empty and full.

• wait flag: Takes the value WAIT when there is at least one car waiting at the roundabout. At any other time, it has the NOWAIT value.
• empty flag: EMPTY if there are no cars in the left quadrant, NOTEMPTY if there is at least one car.
• full flag: FULL if the right quadrant is full of cars, NOTFULL otherwise.

Each segment instance maintains a QueueVar to compute metrics. The QueueVar automagically keeps track of the average queue length.

The queueing time of a car is set when the car is dequeued. It is simply -timelefts[0].

Quadrant

A quadrant is one curve section of the roundabout.

Each quadrant, like a segment, maintains a list of cars currently on the quadrant and the time left before they reach the end of the quadrant.

The quadrant state has 4 fields:

• First field: Number of cars in the quadrant.
• Second field: Indicates whether the quadrant is empty or not.
• Third field: Indicates whether the quadrant is full or not.
• Fourth field: Indicates whether an empty or full message was already sent.

The initial state is: [0,EMPTY,NOTFULL,MSGSENT].

The segment and the quadrant interact closely. When the quadrant gets full, it sends a FULL message to the segment connected at its beginning point. When a FULL quadrant has a car leaving (either via the quadrant's exit or to the next quadrant), it becomes not full and sends a NOTFULL to the segment connected at its beginning point. Similarly when the state second field changes from EMPTY to NOTEMPTY (or from NOTEMPTY to EMPTY), a NOTEMPTY (or EMPTY) message is sent to the quandrant at its end point. These output messages trigger an external transition in the segment and allow the segment to know the state of its two adjacent quadrants. The segment then knows if it is okay to let the cars go into the roundabout and when to stop sending cars and queue them.

Exit

This atomic represents an exit of the roundabout. Other that recording the cars that leaves the roundabout, it does not do much.

Results

Output: results.txt.gz

The results are for a simulation runned for 800 seconds.

Queue Performance Metrics

***************Performace Metrics**************************
The average queue length of north segment is  8.0325
The average queue length of south segment is  1.37
The average queue length of west segment is  5.315
The average queue length of east segment is  4.455

Avg queue time of cars in exit DEVS
North : avg is 64.4444444444
South : avg is 70.6136363636
West : avg is 63.5625
East : avg is 62.4390243902
Over all cars that exited 65.5625

We have plotted the queue time distribution of all queues combined.

Transit Time

The average transit time is computed over the cars that exited the roundabout.

Avg transit time
North : avg is 392.888888889
South : avg is 399.795454545
West : avg is 393.1875
East : avg is 393.170731707
Over all cars that exited 395.145833333

The first number is the car id, the second the transit time and the third the queue time.

The transition time of car that exiting to the north is: 
[(5, 336.0, 0.0), (7, 324.0, 0.0), (1, 348.0, 0.0), (18, 336.0, 12.0), (28, 343.
0, 7.0), (35, 335.0, 11.0), (38, 336.0, 0.0), (26, 367.0, 19.0), (53, 342.0, 18.
0), (64, 377.0, 65.0), (98, 355.0, 31.0), (77, 427.0, 91.0), (105, 383.0, 71.0),
 (120, 379.0, 67.0), (122, 378.0, 66.0), (127, 364.0, 40.0), (148, 355.0, 31.0),
 (65, 560.0, 212.0), (154, 356.0, 32.0), (69, 561.0, 213.0), (161, 354.0, 30.0),
 (144, 408.0, 96.0), (171, 351.0, 27.0), (78, 583.0, 235.0), (180, 348.0, 24.0),
 (87, 579.0, 231.0), (159, 423.0, 111.0)]
The transition time of car that exiting to the south is: 
[(4, 324.0, 0.0), (2, 336.0, 0.0), (9, 324.0, 0.0), (8, 336.0, 0.0), (31, 312.0,
 0.0), (15, 350.0, 2.0), (21, 359.0, 11.0), (13, 381.0, 45.0), (24, 368.0, 20.0)
, (17, 388.0, 52.0), (44, 343.0, 31.0), (32, 364.0, 40.0), (20, 402.0, 66.0), (4
3, 368.0, 20.0), (50, 356.0, 44.0), (49, 361.0, 13.0), (56, 363.0, 15.0), (72, 3
49.0, 1.0), (58, 403.0, 91.0), (62, 401.0, 89.0), (68, 402.0, 90.0), (70, 394.0,
 82.0), (71, 398.0, 62.0), (92, 379.0, 31.0), (96, 379.0, 31.0), (94, 396.0, 60.
0), (100, 386.0, 38.0), (93, 427.0, 115.0), (102, 401.0, 65.0), (108, 396.0, 48.
0), (95, 432.0, 120.0), (103, 428.0, 116.0), (106, 430.0, 118.0), (109, 428.0, 1
16.0), (66, 534.0, 210.0), (112, 436.0, 124.0), (114, 443.0, 131.0), (123, 435.0
, 123.0), (135, 403.0, 67.0), (73, 560.0, 236.0), (81, 557.0, 233.0), (141, 432.
0, 96.0), (174, 373.0, 25.0), (99, 554.0, 230.0)]
The transition time of car that exiting to the west is: 
[(11, 313.0, 1.0), (16, 314.0, 2.0), (6, 348.0, 0.0), (22, 323.0, 11.0), (10, 35
0.0, 14.0), (12, 349.0, 1.0), (14, 379.0, 55.0), (29, 355.0, 19.0), (45, 354.0, 
18.0), (34, 415.0, 91.0), (67, 345.0, 9.0), (47, 416.0, 92.0), (76, 352.0, 16.0)
, (48, 430.0, 118.0), (52, 428.0, 80.0), (82, 381.0, 57.0), (86, 369.0, 33.0), (
51, 491.0, 179.0), (57, 489.0, 177.0), (79, 442.0, 94.0), (61, 509.0, 197.0), (8
5, 458.0, 110.0), (115, 391.0, 67.0), (119, 380.0, 44.0), (88, 464.0, 116.0), (1
25, 397.0, 73.0), (137, 363.0, 27.0), (129, 393.0, 69.0), (139, 376.0, 40.0), (1
36, 420.0, 96.0), (155, 424.0, 100.0), (186, 364.0, 28.0)]
The transition time of car that exiting to the east is: 
[(3, 312.0, 0.0), (23, 325.0, 1.0), (19, 340.0, 4.0), (27, 324.0, 0.0), (40, 318
.0, 6.0), (41, 346.0, 22.0), (60, 326.0, 14.0), (63, 315.0, 3.0), (37, 378.0, 42
.0), (39, 378.0, 42.0), (25, 433.0, 85.0), (74, 318.0, 6.0), (46, 398.0, 62.0), 
(30, 441.0, 93.0), (33, 431.0, 83.0), (36, 437.0, 89.0), (83, 344.0, 32.0), (54,
 415.0, 91.0), (42, 445.0, 97.0), (55, 430.0, 82.0), (59, 427.0, 79.0), (75, 406
.0, 58.0), (80, 404.0, 56.0), (89, 403.0, 55.0), (90, 412.0, 64.0), (113, 358.0,
 46.0), (117, 355.0, 43.0), (101, 410.0, 62.0), (124, 361.0, 49.0), (131, 353.0,
 41.0), (111, 409.0, 61.0), (97, 453.0, 129.0), (146, 343.0, 31.0), (168, 330.0,
 18.0), (121, 438.0, 114.0), (134, 411.0, 63.0), (177, 336.0, 24.0), (84, 573.0,
 237.0), (128, 471.0, 147.0), (91, 572.0, 236.0), (151, 441.0, 93.0)]

Plots

We have plotted the transit time distribution. In this plot, we count only cars that have reached their destination.

Fig. 1 - Frequency vs transit time for all cars that exited.

Fig. 2 - Frequency vs transit time for cars with destination North

Fig. 3 - Frequency vs transit time for cars with destination South

Fig. 4 - Frequency vs transit time for cars with destination West

Fig. 5 - Frequency vs transit time for cars with destination East

Possible Problems with the Model

Events at same time could cause cars to occupy the same space physical space in a quadrant (i.e. same quadrant timeleft value).

Conclusion

We runned the simulation for longer times and we observed that the relative difference between the average queue length of different Exit blocks becomes smaller. This can be explained by the symmetry of the system.

We can see from the plots that the transit times are all around 310 to 450.

A steady state of the system is not reached. After a while, cars start accumulating in the segment queues. The longer the simulation is runned, the longer these queues get. This causes a longer queue time and transit time. Cars are produced faster than they are consumed.