## Explaining traffic jams February 7, 2008

Posted by dorigo in mathematics, news, science.

I just finished browsing a paper by Gabor Orosz and Gabor Stepan, researchers respectively in nonlinear mathematics and applied mechanics. The pdf file had rest on the virtual desktop of my laptop computer for a while now, begging to be read like a hundred more, but advantaged by having not been thrown to the darkness of my “papers to read” folder with all the others. And today, with some time to spend before the arrival of the next train to Venice, I just ventured to read it.

After my quick read I am left with mixed feelings. The paper is not the kind of science that fits George Bernard Shaw’s definition, which I learned from Jeff a week ago: “Science is always wrong! It never solves a problem without creating ten more“. In fact, it does answer the question of how traffic jams are created from a uniform flow. The problem in this case is that the answer was already rather well known. Nonetheless, just thinking at the elegant math which is the ultimate cause of your anguish at the wheel when stuck on a highway makes it easier to accept the situation, and this is enough justification for the article. But the study is indeed some breakthrough in modeling traffic jams.

Orosz and Stepan consider an idealized highway such as the one pictured on the right: vehicles are the points at coordinates $x_i$ along a circumference, all moving in the same direction. They then analyze the nonlinearities that arise in a model of traffic flow in their toy highway when one introduces a realistic time delay in the response of drivers to the detection of an impact threat with the car preceding them. They find that the time delay is crucial in allowing to model, with quite complicated formulas, the onset of backward-traveling “stop-and-go” waves, which interrupt the unstable solution of a well-behaved uniform flow of vehicles.

Apparently, the duality between uniform flow and “stop-and-go” waves has a name: it is an instance of a Hopf bifurcation. Now, since I had never heard of Hopf bifurcations before (or maybe I have, and have forgotten about them – oblivion is the privilege of a cultured man), I am not the best person to explain it here.
So you can read about it on wikipedia if you can not stand your own ignorance (I have accepted mine long ago). If you have lost your mouse and cannot click above, here is a quote:

In bifurcation theory a Hopf or Andronov-Hopf bifurcation is a local bifurcation in which a fixed point of a dynamical system loses stability as a pair of complex conjugate eigenvalues of the linearization around the fixed point cross the imaginary axis of the complex plane.

Everything is clear now, huh ? Well, the math is really not for everybody, not even in the simplest case. And it turns out that the time delay introduced by Orosz and Stepan changes the description of the system from one with ordinary differential equations in a finite-dimensional dynamical space to one modeled by delay differential equations and infinite-dimensional phase spaces. Hugh.

In any case, however complex the main body of the paper is, its conclusions are quite readable. Basically, the model of Orosz and Stepan demonstrates the onset of backward-traveling waves of traffic jams, and shows how a highway is basically a bistable system, with the linear flow easily affected by large enough “perturbations” -.such as a truck changing lane – which cause the onset of stop-and-go waves. All things we knew, but the formulas in the model do allow some planning: just a little decrease in the speed of cars approaching a backward-moving wave could significantly dampen it. Something we knew qualitatively, but we can now compute. A step in the right direction, towards the fulfilment of my highway dream.

I dream of highways where you enter with your car, and then leave the wheel and the gas pedal and read a book. An electronic wireless system controls the speed of your car and its steering, and you get to destination in the smallest possible time available given the number of vehicles on the road. This is not science fiction: we have owned the technology to do this since maybe ten years ago. Just imagine the amount of time saved to human beings, the decrease in pollution, and in the amount of stress… I know these systems are being studied, and I am rooting for those guys.

1. Amara - February 8, 2008

The Physics of Traffic Flows is a fantastic interdisciplinary science problem. Here is my take on it 11 years ago.
http://www.amara.com/ftpstuff/traffic.txt

2. Doug - February 8, 2008

Hi Tommaso,

1 – This paper seems related to Euler’s Konigsberg’s Bridges Problem?

2 – There may also be a relation to Basar and Olsder, ‘Dynamic Noncooperative Game Theory’ [SIAM classic] section 4.7 Braess paradox?

3 – There likely is a relation within the Tropical Algebras such as Max Plus Algebras used by many engineers?

3. carlbrannen - February 8, 2008

One of the problems with wikipedia is that it tends to provide explanations that are self referential. There must be some social reason for this. It’s not at all complicated. Read the following link, especially the part with the <a href=beautiful graph of Ricker’s equation:
<a href=”http://www.scholarpedia.org/article/Predator-prey_model”scholarpedia.org/Predator_prey_model.

When I was a grad student in plasma physics, I built a Hopf bifurcation device that generated that image on an oscilloscope. It was quite a hit, but very simple to do, consisting of a a clock, a sample and hold amplifier, and the analog multiplers and adders to do the equation. But an easier way is by programming the equation.

What happens is that there is a parameter that changes the equation. When the parameter is “small”, the equation iterates to a constant, that is, it converges. As one slowly increases the parameter, the character of the iterates changes. They eventually become unstable and oscillate up and down between two values. Then these typically split and the iterates run through a cycle of length 4, then 8, then 16, etc.

After various chaotic regimes, one can find parameter values where the iteration does all sorts of interesting things. Look carefully at the graph to see some of the cool stuff. But to really appreciate it, you have to have an applet that you can tune the dynamics on. I’d type one up in Java, but there has to be some already out on the web.

I was interested in nonlinear dynamics. I guess I’m still interested in nonlinear equations, except now its in the applications to elementary particles of bilinear equations. I wonder if chaos theory has applications to elementary particles…

4. carlbrannen - February 8, 2008

Ooops, here’s the link. The fact that WordPress doesn’t have the ability to review our comments before publishing, and as well doesn’t give us the ability to edit them, is quite annoying. They have excuses for this misbehavior but they are very thin.

5. Phil Warnell - February 8, 2008

Hi T,

“An electronic wireless system controls the speed of your car and its steering, and you get to destination in the smallest possible time available given the number of vehicles on the road.”

I certainly share your hopes and dreams in this regard. With the advent of GPS and Blue Tooth it has eliminated the need for wires under the road and what not, which were part of earlier conceptions the idea. I think one of the things that might be holding it back is guaranteeing the required level of reliability in relation to safety. That is any failure in this case could lend a whole new meaning to having the system crash :-)

Regards,

Phil

6. Phil Warnell - February 8, 2008

Hi Amara,

“Shock waves in real traffic are very dangerous. Drivers have finite reaction times, so sudden changes in traffic density can cause accidents. In this traffic model, the local density determines the traffic velocity. Fortunately under normal visibility conditions, rivers adjust their speed by judging the global traffic conditions (i.e., they look at more than just the car in front of them). This fact introduces a diffusion term into the model that smooths the discontinuous shock fronts.”

I find this quote you made of Vemeer very interesting and also noticeably true in another related circumstance and that is when driving in a snow storm. What I’ve observed is that when snow initially starts to fall that this is when you have most of the crashes and resultant traffic jambs. However, after the storm has persisted for a few hours and despite road conditions declining that even with traffic volumes are high (rush hour) there are less stoppages, although average speeds are considerably reduced. This in my experience results in decreased travel time over the period when the snow started at first. I believe this then also demonstrates the validity of this hypothesis.

Regards,

Phil

7. dorigo - February 8, 2008

Dear Doug,

the answer to the first two questions is no – I do not see any connection to the problem of bridges (which is basically simple topology) and to the Braess paradox, which is also a static problem with a simple algebraic solution. I nonetheless thank you for the second link, which I found enjoyable.
As for the third question, I cannot answer it… But I think the answer is also no, by induction ;-)

Cheers,
T.

8. dorigo - February 8, 2008

Hi Carl,

thank you – your comments are always appreciated. In this case, your explanation of the instability is very useful. I will visit your link when I have time to do it… I am kind of in a rush right now.

Cheers,
T.

9. dorigo - February 8, 2008

Hi Phil,

agreed – safety is all-important in this case. But think of air travel, and put everything in perspective: we already rely on automated systems heavily there.
I see no real reason to doubt on our ability to design foul-proof highway automation systems.

Cheers,
T.

10. Charles Tye - February 8, 2008

Hi Tommaso,

I remember Hopf bifurcations from my undergraduate days. If I remember correctly, a good way to visualise a Hopf bifurcation is in phase space. A fixed point attractor for a system suddenly stops being a fixed point and the attractor expands into a limit cycle when a parameter goes through a critical value – i.e oscillatory behaviour appears “out of nowhere” from a previously stable system. This is very plausible for a model of traffic flow.

In his book “Five More Golden Rules”, which has a whole chapter on bifurcation theory, John Casti gives a nice physical example of a Hopf bifurcation. Consder a small sphere, say a ball-bearing, inside a large hollow sphere, say a basketball. If you start the basketball rotating and perturb the ball-bearing, for a small angular velocity it will return to the bottom of the basketball. Above a critical angular velocity which will depend on the friction, the ball-bearing, when perturbed will move up the side of the sphere and there will be a stable circle of invariant points that will depend on the angular velocity.

11. Amara - February 9, 2008

Phil Warnell:
I find this quote you made of Vemeer

No, that quote came from Alejandro Garcia, my former MS Physics thesis advisor and author of the text: Numerical Methods for Physics:
http://www.algarcia.org/nummeth/nummeth.html

Alex developed the traffic problem in great detail (20 pages including Matlab and Fortran code) in my first edition of his textbook because it is a good example of the generalized inviscid Burger’s equation, a relatively simple nonlinear PDE with wave solutions. His graphics showing how the shock wave develops under particular conditions seem intuitively right, but I thought I understood Montroll’s approach better.

Professor Montroll was one of my physics professors many years earlier at UC Irvine. Montroll taught a elective class called Physics of Technology where he spent about a couple of lectures on the traffic flow problem. What I like most about Montroll’s treatment is how he managed to tie in sociological interactions into his physics models. For example, I will always remember Montroll’s “rule of thumb” demonstrated by the traffic flow problem:

“One rule-of-thumb in responding to any stimulus that one does not want to become unstable is: the longer one waits in response to a stimulus, the strength of that response should be exponentially less with respect to that time.”

12. dorigo - February 9, 2008

Hi Charles,

yes, after reading the comments – particularly the text by Amara and your comment – I remember I did happen to study the basics during my undergrad courses.

Amara, the last sentence is indeed useful, and interdisciplinary in nature. It also applies to email exchanges and flames in threads :)

Cheers,
T.

13. Phil Warnell - February 9, 2008

Hi Amara,

“One rule-of-thumb in responding to any stimulus that one does not want to become unstable is: the longer one waits in response to a stimulus, the strength of that response should be exponentially less with respect to that time.”

This has me somewhat confused as I understand the meaning. This would suggest that if I see brake lights in front of me that the longer I take to respond the less heavily I should press the brake when I actually do react. Is this what is meant or am I missing something?

Regards,

Phil

14. Amara - February 9, 2008

Dear Phil, Did you read what I wrote about Montroll’s Lagrangian model? http://www.amara.com/ftpstuff/traffic.txt His statement stems from his derived solutions and stability criteria.

If the stability criteria was violated (lambda*delta < (1/2)), small low frequency disturbances cause the line of traffic to act as an amplifier. So if the time lag between an input fluctuation and a response is long, and your response is very strong, you may be responding too strongly to a situation that has passed. The response might then be in phase with the fluctuation, further deteriorating the control. The best way to stabilize this flow problem is to make small responses to small fluctuations soon after they occur.

15. Phil Warnell - February 9, 2008

Hi Amara,

“Did you read what I wrote about Montroll’s Lagrangian model? http://www.amara.com/ftpstuff/traffic.txt His statement stems from his derived solutions and stability criteria.”

First, let me say I appreciate both your insight and response and yes I did review what you had written, although I must confess not in extreme detail. My point was that as stated (in the rule of thimb) it seemed to imply that a delayed response could be compensated for by decreased action. This as you clearly indicate is not the case. In terms of least action it really implies the sooner (time) and as little (required action) the better. The limit then to sooner is instantaneous and the least is none (no action). To contemplate this then would suggest that predetermined (planned) is the combined resultant limit. This is of course (at least for me) is logically unavoidable. Thanks once again for the clarification.

“A stitch in time saves nine”

Regards,

Phil

16. Stefan - March 21, 2008

A timely post ;-)

Did you see this wonderful experimental realization of the emergence of traffic jam on a circular road, and the backward-travelling stop-and-go wave? Check out the movies!

Cheers, Stefan

17. dorigo - March 21, 2008

Hi Stefan,

thank you for the notice! That is really neat… For people like me, who work in particle physics, “scaled down” systems that allow one to check a numerical simulation are a real luxury!

Cheers,
T.

Sorry comments are closed for this entry