kyle woodward :: current

30 April 2013

Half a decade ago, I wrote a blog post describing the optimal deceleration pattern, to maximize your velocity through a traffic light just as it turns green. It is practically illegible. Since I've been applying the calculus of variations to some ongoing research projects, redoing the math seems like some good practice.

setup

You are driving a car towards a red light, and what do you see? An empty lane! You merge over, eagerly anticipating zooming off and laughing maniacally at the chumps who haven't even lifted their chumpy feet off of the gas pedal, you having perfectly timed the light. In a world where you know when the light will change, and your only available option is to brake before the light — no fair braking to a stop, then goosing the throttle as the light is about to turn — how should you manage your brake pedal so as to maximize the speed at which you coast through the intersection?

We have the following primitives:

There is time \( T \) until the light changes.
You are currently traveling at speed \( v_0 \).
Your available braking power \( \dot{v} \) is constrained by \( -\alpha \leq \dot{v}\leq0 \).
There is distance \( \Delta \) between your vehicle and the stop line.

the objective

From this setup, the mathematical objective is expressed as

\[ \max_v \int_0^T \dot{v}(t) dt,\text{ s.t. } v(0)=v_0,\; \int_0^T v(t) dt \leq \Delta,\; -\alpha\leq\dot{v}(t)\leq 0 \]

The calculus of variations (for an excellent reference, see Intriligator, 1971) gives us a [pointwise] Lagrangian of

\[ \mathcal{L}=\dot{v}+\lambda_1 \left( \Delta - v\right) +\lambda_2 \left(\dot{v}+\alpha\right) -\lambda_3 \dot{v} \]

Since the Lagrangian is \( t \)-free, the solution may be expressed as

\[ \mathcal{L}-\left(\frac{d\mathcal{L}}{d\dot{v}}\right)\dot{v} = C \]

In particular, we have

\[ \lambda_1 \left(\Delta - v\right) + \lambda_2 \alpha = C \]

It is worth noting that \( \lambda_1 \) is a constant, as it is the multiplier on an integral constraint, while \( \lambda_2 \) is a function.

analysis

As is usual in Lagrangian analysis, we look at cases.

\( \bf{\lambda_1=0}. \) Then the integral constraint is irrelevant. It is easy to see that the solution is \( \dot{v}(t)=0 \).

\( \bf{\lambda_1>0}. \) We can see that \( \lambda_1 \dot{v} = \dot{\lambda}_2 \alpha \). Hence if \( \dot{v}\neq 0 \), it must be that \( \dot{v}=-\alpha \).

In either case, the optimal deceleration pattern is given by

\[ \dot{v}(t) = \begin{cases} -\alpha & \text{ if } t \leq \bar{T}, \\ 0 &\text{ otherwise.} \end{cases} \]

The question then reduces to solving for \( \bar{T} \); however, at this point we have already solved as much as the previous post: the optimal strategy is to brake as hard as possible, for as long as necessary to just meet the light at the no-more-braking speed. From the above analysis, we know that \( \bar{T} = 0 \) when \( v_0 T\leq \Delta \).

In all other cases, we know that \( \bar{T} \) solves

\[ \int_0^{\bar{T}} v(t)dt + \int_{\bar{T}}^T v\left(\bar{T}\right)dt=\Delta \;\;\; \implies\;\;\;v_0T + \frac{1}{2} \alpha \bar{T}^2 - \alpha T \bar{T} =\Delta \]

It follows that when \( v_0 T>\Delta \), we have

\[ \bar{T} = T - \frac{1}{\alpha} \sqrt{ \alpha^2 T^2 - 2 \alpha \left( v_0 T - \Delta \right)} = T - \sqrt{ T^2 - \frac{2 \left( v_0 T - \Delta \right)}{\alpha}}. \]

alternative characterization

Rather than using the '\( t \)-free' shortcut, we can appeal directly to the Euler equation,

\[ \frac{\partial\mathcal{L}}{\partial v}-\frac{d}{dt}\left(\frac{\partial \mathcal{L}}{\partial \dot{v}}\right) = 0 \]

In this case,

\[ -\lambda_1 + \left( \dot{\lambda}_3 - \dot{\lambda}_2 \right) = 0 \]

It is worth noting that, at almost every point, \( \dot{\lambda}_3 \neq 0 \) implies \( \dot{\lambda}_2=0 \), and vice-versa. Hence if \( \lambda_1 = 0 \), it must be that \( \dot{\lambda}_3 = 0 \) and \( \dot{\lambda}_2=0 \) (otherwise, we can integrate both \( \lambda_2 \) and \( \lambda_3 \) slightly to positive values, implying that both constraints bind). This implies that one constraint or the other will bind throughout.

In the more interesting case, \( \lambda_1>0 \). This implies that either \( \dot{\lambda}_3>0 \) or \( \dot{\lambda}_2<0 \); since the equation is set equal to \( 0 \), these are mutually exclusive. Remembering that each of \( \lambda_2,\lambda_3 \) must be positive, the only solution here consistent with continuous \( \lambda_2,\lambda_3 \) is to have \( \dot{\lambda}_2<0 \) on a range \( t\in[0,\bar{T}] \) and \( \dot{\lambda}_3>0 \) on a range \( t\in[\bar{T},T] \). By the nature of the constraints binding over different regions, this implies the same solution as above.

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