easy(?) probability/diff eq. question

Question

I've been wondering about this ever since I was a little kid and I used to ride in the back of the car and my mom would speed like hell towards a green light, only to slam on the brakes when she realized she wasn't going to make it.

Here is my question, loosely phrased: Given that we want to make it across the intersection before the light is up, what should be our position function? To make things precise, we could specify some initial conditions, put a cap on the car's acceleration/deceleration (or its speed or its jerk or whatever), fix a probability distribution on when the light will change, and assign some point values to our happiness if we make the light vs. don't make the light vs. end up entering the intersection after the light has changed and get a ticket for it. And then of course we could throw in the extra curveball of a yellow light warning you that it's about to turn red...

A similar question arises if you're approaching a red light but you think it might turn green soon. Ideally you'd like to enter the intersection at the highest possible speed just after the light has turned green, but then again you don't want to enter when it's still red.

I'm sure a computer could solve such problems easily, but it seems like there should be some better way to think about this than just asking a machine to do it for me. For the first question, it seems like the answer will just be either "hit the gas and go for it" or "cruise to a stop and don't plan on going through", depending on the parameters. (Of course, there might be something in the "go just fast enough that you can slow down and not enter on a red" plan if the cost of a ticket is high enough.) On the other hand, the second question seems to admit much more interplay between probability and differential equations. The real issue here is that I know almost nothing about either of these two fields. Any ideas?

Answer 1

I think there's potentially an interesting set of problems here - I thought about it myself some time ago, and I'm not the only one (if you're too lazy to follow the link, this is Tim Gowers posing exactly this question on Terry Tao's blog). I would classify them as "Operations Research" rather than probability or DE; the latter could be tools to be used here, but it's unlikely that there are significant theoretical challenges here once the problem is clearly posed. Of course, one of the challenges here is posing the right problem.

For example, it's not hard to see that if you're at rest at a certain known distance from the light, and your acceleration is limited to some value A, and you know when the light is about to turn green, then your best strategy is to stand still until the correct (easily calculated) time, and then slam the gas pedal and speed so as to make it to the light just in time.

In other instances such as if your initial speed is too high to make it before the light turns green, you may be better off breaking first and then accelerating. In general, it is typical of such problems that the strategy is "extremal" in the sense that the action at each time is either full deceleration or full acceleration; it may be hard to find a problem where the strategy is more subtle. Still, determining the optimal timings etc. could be an interesting challenge. I did not yet spend any time trying to find a good definition of the problem, but it's a worthwhile thing to think about.

Answer 2

The general type of extremal' that Amit talks about has a name within the field of optimal control.Most' control strategies tend to be `bang-bang'. For a control (here an acceleration) to bebang-bang' means that you operate at the max (of A above) or min (as in slamming on the brakes). The whole problem boils down to figuring out the `switching times' : when to switch from one strategy to the other.

There is a LARGE mathematical and engineering literature on this type of problem, some of the most useful works having been done by Pontrjagin,Gamkrelidze, and Boltjanskii and going under the name `Maximum principle'. LC Young wrote a beautiful book on it.

The general set-up for the maximum principle is an ODE $\dot x = f(x,u, t)$ where $u$ is called the control'. The simplest version of the optimal control problem is to choose $u = u(t)$ tosteer' the vector or scalar $x(t)$ from $x_0$ to $x_1$. The constraints are of the form $a < u < A$ (if $u$ is vector-valued , then $u$ varies over some convex set). The thing to maximize might be the time the steering takes (`optimal time') or some integral $\int L (x, u, t) dt$.

If instead one looks for $u = u(x)$ one is talking about ``optimal feedback control''.

Answer 3

Yor Naim left this at Tao's blog as a possibly relevant paper to this question:

J. I. Katz How to Approach a Traffic Light Mathematics Magazine, v63 n4 226-230 Oct 1990.

Answer 4

This is completely irrelevant to the mathematics, but on a recent trip to China I was surprised to see that the traffic lights there have a countdown so that you know exactly how long before the lights are due to turn green or red.