traffic lights, part one

24 January 2008

I spend a lot of time in traffic. Compared to many other commuters, that statement is a total lie, but for me 25 minutes stuck in a car is about 25 minutes too many.

And I thought the 101 was bad. (context)

I figure that if I'm stuck in traffic, I might as well not be paying for it. Recently, I upgraded to a hybrid to enhance my MPG (tax credit + gas prices == economic win), but still, I know that behaviorally there are ways to eke more distance out of gas. An easy way to save on gas (even if nominally) is to accelerate as little as possible; seeing as most of my acceleration is out from red lights, this raises the question of how do you maximize your speed through a red light, thereby reducing the amount of acceleration required to attain your desired speed?

This is an economic conundrum if ever one there was, so it makes sense to tackle it with a good measure of game theory. To make the analysis simpler, we'll start with assuming that we know when the light is going to change, and that there are no other cars in the way; in part two, when it happens, we'll look at what happens when knowledge of light-changing times follows a known probability distribution (a much more accurate model). If there is a part three, it'll examine what happens when other cars are already waiting at the light. For now, let's also assume that we're moving fast enough to run the red light in absence of acceleration (deceleration).

To start, let's issue a few definitions. Let \( t \) be the time elapsed since \( t_0=0 \); let \( x(t) \) be the distance to the the stopping point at time \( t \); let \( v(t)\geq 0 \) and \( 0\geq a(t)\geq a_{min} \) be velocity and acceleration at time \( t \), respectively (naturally, \( v(t)=v(0)+\int_0^ta(t)dt \); let \( t_f \) be the known time at which the light is going to change. Our problem is then stated as follows: what function \( a(t) \) maximizes \( v(t_f) \) subject to \( \int_0^{t_f}v(t)dt\leq x(0) \)? That is, what acceleration function maximizes final velocity, subject to not running the light?

THEOREM: The optimal acceleration function slows as rapidly as possible to a constant \( v(t_i) \), such that \( (t_f-t_i)v(t_i)=x(0)-\int_0^{t_i}v(t)dt \). In other words, the optimal strategy is to immediately apply maxiumum braking pressure until you reach the speed which will perfectly cover the distance to the light at the time the light changes. To show this, we'll need a few tools on our belt.

LEMMA: Any optimal acceleration function must be such that \( \int_0^{t_f}v(t)dt=x(0) \). Here we declare that any velocity-maximizing acceleration function has the car crossing the line (covering distance \( x(0) \)) at the moment the light changes (\( t_f \)). Suppose we have an acceleration function \( a_1(t) \) — deriving velocity function \( v_1(t)=v_1(0)+\int_0^ta_1(t) \) — such that \( \int_0^{t_f}v_1(t)dt<x(0) \). Let the derived position function be \( x_1(t) \).

By our assumption that we are initially moving fast enough to run the red light, we know there is some \( 0\leq t_i<t_f \) such that \( (t_f-t_i)v_1(t_i)=x(t_i) \), or that at some point we are moving exactly the right speed to cross the line as the light changes. We also know that there is some \( t_j \) such that \( v_1(t)<v_1(t_i) \forall t\in[t_j,t_f] \); otherwise, \( v_1(t)=v_1(t_i) \forall t\in[t_i,t_f] \), and thus we find that \( \int_{t_i}^{t_f}v_1(t)dt=(t_f-t_i)v_1(t_i)=x(t_i) \), where we cross the line as the light changes, a contradiction.

Let's use our given acceleration function \( a_1(t) \) to derive a new acceleration function \( a_2(t) \):

\[ a_2(t)=\begin{cases} a_1(t)&\text{if } 0\leq t\leq t_i\\ 0&\text{if } t_i<t\leq t_f \end{cases} \]

Then \( a_2(t)\geq a_1(t) \forall t\in[t_i,t_f] \) (given our constraint that acceleration is negative), and more importantly \( v_2(t)> v_1(t) \forall t\in[t_j,t_f] \). Knowing that acceleration function \( a_2(t) \) has been constructed so that we cross the line at exactly the time the light changes, and specifically that \( v_2(t_f)>v_1(t_f) \), we see that from any acceleration function \( a_1(t) \) such that \( \int_0^{t_f}v_1(t)dt<x(0) \) we may derive a new acceleration function \( a_2(t) \) such that \( \int_0^{t_f}v_2(t)dt=x(0) \) and \( v_2(t_f)>v_1(t_f) \), proving our lemma. \( \square \)

Back to the theorem at hand...

Suppose we have an acceleration function \( a_1(t) \) such that \( \int_0^{t_f}v(t)dt=x(0) \) (we'll call this criterion lemma-possibly optimal, in recognition of the above lemma), and an acceleration function \( a_2(t) \) where for \( t_i \) such that \( (t_f-t_i)v_2(t_i)=x_2(t_i) \)

\[ a_2(t)=\begin{cases} a_{max}&\text{if }0\leq t\leq t_i\\ 0&\text{if }t_i<t\leq t_f \end{cases} \]

Thus \( \int_0^{t_f}v_2(t)dt=x(0) \). Furthermore, we may see that \( \exists t_1, t_2: a_1(t)\neq a_2(t) \forall t\in(t_1,t_2) \); that is, \( a_1(t) \) and \( a_2(t) \) differ over some open interval.

By definition of \( a_2(t) \), this means that for some \( t_1,t_2>t_i \) we have \( a_1(t)<0 \forall t \in (t_1,t_2) \). If not, then we know that for some \( t_1,t_2\leq t_i \) we have \( a_1(t)>a_{max} \forall t\in(t_1,t_2) \) (otherwise, \( a_1(t)=a_2(t) \forall t\in [0,t_f] \), a contradiction). Then \( a_1(t)\geq a_2(t) \forall t\in[0,t_f] \) and so \( v_1(t)\geq v_2(t) \forall t\in[0,t_f] \), with \( v_1(t)>v_2(t) \forall t\in(t_j,t_f] \) for some \( t_j \). Then we know that \( \int_0^{t_f}v_1(t)dt>\int_0^{t_f}v_2(t)dt \), or that \( \int_0^{t_f}v_1(t)dt>x(0) \), a contradiction.

Finding a suitable \( t_1,t_2 \) as above, we see `(1), \( \int_{t_1}^{t_f}v_1(t)dt<\int_{t_1}^{t_f}v_2(t)dt \); separating the lemma-possibly optimal definition integral, this implies that \( \int_0^{t_1}v_1(t)dt>\int_0^{t_1}v_2(t)dt \). Knowing that \( v_1(0)=v_2(0) \) and that \( v_1(t), v_2(t) \) are nonincreasing (by definition of the acceleration functions), we see that \( v_1(t_1)>v_2(t_1) \). By definition of \( v_2(t) \), we can use (1) to see (2), \( \int_{t_1}^{t_f}v_1(t)dt<(t_f-t_1)v_2(t_i) \). Suppose that \( v_1(t_f)\geq v_2(t_f) \), then since \( v_1(t) \) is nonincreasing, we know that \( \int_{t_1}^{t_f}v_1(t)dt\geq (t_f-t_1)v_1(t_f)\geq (t_f-t_1)v_2(t_f) \), a contradiction of (2).

Thus we see that for any lemma-possibly optimal acceleration function \( a_1(t)\neq a_2(t) \), \( v_1(t_f)<v_2(t_f) \). Combining this with our lemma, we have proved the theorem. \( \square \)


To maximize your speed through an unblocked traffic light for which you know the change time without touching the gas pedal, slow down as quickly as possible and hold the constant intercept speed once you reach it.

Way too much math to show that little fact. Sometime soon, I'll work on deriving a similar proof for unknown change times following a probability distribution. Then we'll be cooking with gas.

Included \(\LaTeX\) graphics are generated at LaTeX to png or by MathJax.

contemporary entries


there are no comments on this post