Event Flow Chart and Avoiding Jams

I have drawn up three diagrams to explain some of my the topics covered in my last post better.

This is a diagram of two intersection nodes. Suppose a car needed to get from intersection 2 to the intersection that is west of intersection 1; we will also suppose that the number of time steps required to get from the end of an incoming queue to the center of an intersection and the number of time steps required to get from the center of the intersection to the front of the outgoing queue, is 5. The car would exit the west outgoing queue of intersection 2 and enter the incoming queue of intersection 1 which would schedule a choose direction event for 5 time steps in the future. When the car got to the center of intersection 1 (this is represented by the execution of the choose direction event), it would realize that there was no room to enter the west outgoing queue, or any other queue for that matter, so the car would schedule a departure event to go east for 5 time steps in the future, which would put the car in the east outgoing queue of intersection 1. It would also schedule an arrival event for intersection 2 for the 5 time steps in the future. This cycle may go on once or twice in hopes that one of the jams in intersection 2 will subside. However, if the jams do not subside, the car will have to choose a different direction to avoid the jams. 

This is a diagram of many intersection nodes all in a configuration and how the previously described algorithm can be used to avoid a jam, as well as how to avoid a livelock for the entire model. The car will begin by attempting to go south the east, after a few tries it will go either west or north (west in this case) and then go south. The car will then try to go east again when it is nearest to its destination, and when it realizes that it cant, it will go south again, then east and then north. A car's final destination is determined by the total number of spaces north or south and east or west, it has remaining to move. Therefore the algorithm to determine where the car should move from a particular intersection becomes very simple, the car should either towards its destination in the vertical or horizontal directions. If neither of these two options are available, the car must pick a different direction at random and move there in an attempt to avoid the jam.

The flow chart above describes the events that are scheduled in order to accomplish the algorithm aforementioned. The colors indicate which intersection to the particular event is scheduled for, and the arrows indicate which event (and intersection) the even was scheduled by. Starting at the event indicated "start", the arrival event schedules a direction choice which schedules a departure. An arrival is then scheduled on the blue intersection which goes through the same process as the red intersection and sends the car back. This may happen a few times before the red intersection schedules an event to send the car to a different intersection. 

I hope to have this coded up by next week, and if all goes well I should have some performance results within the next two weeks.

-J

This weekend I will be...

Over the past couple of weeks I have done a lot of work on ROSS Vehicular Traffic Model, one of the problems I am having is putting my work into a format that is easily sharable with the rest of the world because a lot of the work I have so far consists of diagrams and flow charts that I have drawn in my notebook.  This weekend I will be uploading all of the diagrams and flow charts I have made that describe how my model works and explain what problems I ran into.

I have also spent the past few weeks learning how to use ROSS and how to write a model in code.  Unfortunately there is not as much documentation as I would have liked on ROSS and it is hard to find people really know how it works.  Professor Carothers and Thomas "TJ" Reale have been a great resource in helping me understand how ROSS works and how constructing a model works.  Here is a link to a basic ROSS model with some instructions on how it works.  http://odin.cs.rpi.edu/ross/index.php/Constructing_the_Model

Today I committed code that I wrote about a week and a half ago (so you can get an idea of what it will look like) before I realized that I needed to go back and redo some parts of my model (which I will explain in a blog post later this weekend).  Also thanks to Peter Hajas for helping me with git hub.

The rest of this blog post will be dedicated to describing some restrictions when using optimistic simulation and ROSS that have been challenges.

• ROSS is an event based simulator, thus every action that you wish to perform must be modeled in this way.  An event consists of a set of code that will be run and usually consists of the following: some form of statistical record keeping, a manipulation of local data, and the scheduling of a future event.  For example, if a car arrives at an intersection the node will execute an ARRIVAL event: a counter for the total amount of cars at that intersection will be incremented, a car object will be entered into the incoming road queue, and a DEPARTURE event with a time stamp of some time in the future when we think the care will be able to depart.  This limits how a model can be constructed, and this will become evident in future blog posts.
• As I have described in my presentation, my traffic model will essentially be a set of intersections, each intersection being its own node.  When using ROSS, it is impossible for nodes to share information, thus they must send information to each other in the form of an event.  This is a huge problem in regards to a DEPARTURE event because it is impossible to instantly check if the roadway of a neighboring intersection is clear (there are few enough cars on that road so that there is enough space for the car of interest to enter it).  My initial solution was to have neighboring intersections schedule events for the intersection of interest telling it when it becomes free and when it becomes jammed.  This solution however would cause huge problem with the optimistic part of the simulation because the time stamp on that event would have to be 0 (instant).  This is a problem because by the time the intersection processes that event, the time simulation would have already passed that event's time stamp which would cause a rollback which is very inefficient.  My new solution to this problem (which will work) is as follows.  All intersections will have two (well, more than two but more on that later) queues in all four cardinal directions, one for incoming traffic and one for outgoing traffic.  When there is an ARRIVAL event, a car will be pushed into the incoming queue and will progressively make its way to the center of the intersection.  When it gets there it will attempt to join the outgoing queue in whatever direction it desires to go (more on how that works later too).  If that queue is full, the car will go into the outgoing queue in the direction it came.  Because of this, a DEPARTURE event will not have to check to see if the roadway is clear because no matter what, a car will be popped off the front of the incoming queue (if there are any cars in the incoming queue) making room for any cars coming from other intersections.  This solution does however present ways for my model to "livelock" which I have also found a good solution for which I will explain in a later post.

This project has been very interesting to work on so far because the fact that most of the code (ROSS) has already been written and most of the focus is on the design of the model.  I expect that once I have the final details of my model ironed out, coding up the model shouldn't take more than a few days.

If you have any questions for me or would like me to explain anything better in my post, feel free to contact me at schnej7@rpi.edu .

-J

Progress on Model Construction

I have been working on my model construction over the past few weeks.  It has proven to be much more difficult that I initially anticipated due to the lack of documentation and the unique and specific format of the model.  I have code to push, but I am currently having trouble with github which I hope will be fixed later today. I still need to iron out some of my events before I begin testing my model, but I think I am close to having a testable version.

-J