What is the optimal speed to approach a red light?

Question

Suppose from distance $d$, while driving at speed $v_0$, I notice that there's a red traffic light in front of me. Suppose that there are no other vehicles, my vehicle has perfect brakes, my maximum acceleration is $a$ and the red light will turn green according to some $\mu$ distribution. My goal is to get to my final destination as soon as possible, i.e., to minimize my estimated time of arrival (ETA), and suppose that the rest of the road has some speed limit $L$.

With what speed should I approach the red light to minimize my ETA?

Of course, the answer will depend on the parameters; I'm interested in any non-trivial results. As essentially the same problem has been raised earlier here and here (thanks for the links!), but apparently without any solution, let me be more specific.

Is there any non-trivial set of parameters for which we know the solution?

ps. I'm not interested in reducing milage, but feel free to add comments in this direction, if you wish.

Answer 1

Similar to the linked variants on this problem, the optimal strategy takes the form of a function $v(t)$, which corresponds to the strategy in which you travel at velocity $v(t)$ until the light turns green, then you slam on the accelerator and accelerate at $a$ until you reach the speed limit $L$.

If $T$ is the time when the light turns green, we will be at $D=\int_0^Tdt\;v(t)$ traveling at $V=v(T)$, and the velocity function for $t\ge T$ is $v'(t)=\min(V+a(t-T),L)$. We want to maximize, for $t\gg T$:

$$K:=\int_0^tdt\; v'(t)=D-\frac{(L-V)^2}{2a}-LT+Lt$$

The leading term $Lt$ only depends on the chosen time $t$ to measure our distance, so we can ignore it, and similarly with $LT$ which depends only on $T$ which is not under our control. For the rest, we see a quadratic penalty to slowing below top speed.

The constraint of not running the red light is expressed as $P[\int_0^Tdt\;v(t)\le d]=1$, which amounts to just $\int_0^xdt\;v(t)\le d$ for all $x$ such that $\mu([x,\infty))>0$. In fact we can just go ahead and assume $\int_0^xdt\;v(t)\le d$ for all $x$ because the strategy is irrelevant once the light is green.

So we are looking at:

$$E[K]=E\left[\int_0^Tdt\;v(t)-\frac{(L-v(T))^2}{2a}\right]$$

where $T$ is drawn from the distribution $\mu$, and we wish to choose $v$ maximizing $E[K]$. I don't think much more can be done in this generality, so let me focus on the case $\mu$ uniform on $[0,\alpha]$.

In this case the expected value becomes (up to a factor $1/\alpha$ which doesn't affect the result)

$$\int_0^\alpha dT\left[\int_0^Tdt\;v(t)-\frac{(L-v(T))^2}{2a}\right]=$$ $$\int_0^\alpha dt\left[(\alpha-t)\;v(t)-\frac1{2a}(L-v(t))^2\right].$$

We can add in a Lagrange multiplier to account for the constraint (which will almost certainly turn out to be extremal) $\int_0^\alpha dt\; v(t)=d$, and solve this using calculus of variations:

$$\mathcal{L}(t,v,\lambda)=(\alpha-t)\;v-\frac1{2a}(L-v)^2+\lambda v$$

$$\frac{\partial\mathcal{L}}{\partial v}=0\implies v(t)=L+a(\alpha+\lambda)-at$$

Here $\lambda$ is a free constant which should be chosen to maintain the constraint $\int_0^\alpha dt\; v(t)\le d$, which I'll leave to you since the story is more interesting: This says you should decelerate at $a$ starting from an appropriate speed. (Here the appropriate speed is so that you come to a stop at the light, unless this puts the initial speed above $L$, in which case obviously you should drive at the speed limit until you get close enough.)

---

Let's try another simple and reasonable distribution: the exponential distribution with mean $\beta=\alpha^{-1}$. In this case the expectation works out to:

$$\int_0^\infty dT\;e^{-\alpha T}\left[\int_0^Tdt\;v(t)-\frac{(L-v(T))^2}{2a}\right]=$$ $$\int_0^\infty dt\;e^{-\alpha t}\left[\beta v(t)-\frac1{2a}(L-v(t))^2\right].$$

As with the uniform distribution case, we add a Lagrange multiplier and solve the Euler-Lagrange equation:

$$\mathcal{L}(t,v,\lambda)=e^{-\alpha t}\left[\beta v-\frac1{2a}(L-v)^2\right]+\lambda v$$

$$\frac{\partial\mathcal{L}}{\partial v}=0\implies v(t)=L+a(\beta+\lambda e^{\alpha t})$$

Unfortunately, this solution is formally problematic, since the integral of the velocity doesn't converge for large $t$. This solution is still correct before we hit the discontinuity, but we need to add the constraint in differently.

Let's explicitly consider a velocity curve that is zero after a certain fixed time, i.e. we approach the light and come to a stop. For a fixed chosen time $t^*$ to stop at, the functional is the same, and so the solution is the same: exponential deceleration away from the unreachable "steady state" velocity $L+a\beta$. But when we hit the light, we use our magic brakes to stop, and continue after the light from a full stop.

$$E[K]=\int_0^{t^*} dT\;e^{-\alpha T}\left[\int_0^Tdt\;v(t)-\frac{(L-v(T))^2}{2a}\right]+\underset{c(t^*)}{\underbrace{\int_{t^*}^\infty dT\;e^{-\alpha T}\left[d-\frac{L^2}{2a}\right]}}$$ $$=\int_0^{t^*} dt\left[\int_t^{t^*}dT\;e^{-\alpha T}\;v(t)-\frac{e^{-\alpha t}}{2a}(L-v(t))^2\right]+c(t^*).$$ $$=\int_0^{t^*} dt\left[\beta(e^{-\alpha t}-e^{-\alpha t^*})\;v(t)-\frac{e^{-\alpha t}}{2a}(L-v(t))^2\right]+c(t^*).$$

The parts that depend on $t^*$ don't affect the variational analysis:

$$\mathcal{L}(t,v,\lambda)=\beta(e^{-\alpha t}-e^{-\alpha t^*})\;v-\frac{e^{-\alpha t}}{2a}(L-v)^2+\lambda v$$

$$\frac{\partial\mathcal{L}}{\partial v}=0\implies v(t)=L+a(\beta(1-e^{\alpha(t-t^*)})+\lambda e^{\alpha t})$$

This time we should really solve for $\lambda$ since we need to ensure that $\int_0^{t^*}dt\;v(t)=d$. I'll spare the details as the algebra gets worse, but after putting $\lambda$ back in the equation, we have a one-dimensional optimization for $E[K]$ as a function of $t^*$, which can't be solved with elementary functions, but from numerical simulations it looks like the best option is still the extremal one: Wait until the last moment at the top speed, then execute the exponential deceleration maneuver $v(t)=L+a\beta(1-e^{\alpha t})$ and stop when $v(t)=0$, at $t=\beta\log(1+\frac L{a\beta})$.

PS: I don't recommend these maneuvers. They strike me as mildly suicidal.

Answer 2

This is just the first step in obtaining a possible answer: formalization. For simplicity, let us ignore the possibility that the light will change more than once before it is reached by the vehicle. Let $V$ and $D$ denote, respectively, the speed when you pass the light and the distance to cover after the light. Then the smallest possible time to travel after the light is $S_V^{-1}(D)$, where $S_V(t):=\int_0^t du\,[L\wedge(V+au)]$.

Assume you noticed the red light at time $0$ and it will turn green at a (random) time moment $t$. Let $v(u)$ denote your chosen speed at time $u$. Fix $v_0=v(0)$. Assuming your optimal behavior (that is, you accelerate as much as possible, to reach the light as soon as possible after it turned green -- if you did not reach it before it turned green), the speed when you pass the light will be
\begin{equation} V_s(t)=(L\wedge[v(t)+a\tau_s(t)])I\{s(t)\le d\}, \end{equation} where $I\{\cdot\}$ is the indicator function, $d$ is the distance to the light at time $0$, $s(t):=\int_0^t v(u)\,du$, and $\tau_s(t)$ is the nonnegative solution of the equation $s(t)+s'(t)\tau_s(t)+a\tau_s(t)^2/2=d$ assuming $s(t)\le d$.

The time to travel just past the light will then be $t+T_{s,t}^{-1}(d)I\{s(t)\le d\}$, where \begin{equation} T_{s,t}(r):=s(t)+\int_0^r du\,[L\wedge(s'(t)+au)]. \end{equation}

Hence, the total expected travel time will be $\int_0^\infty\mu(dt)\,t$ plus
\begin{equation} \int_0^\infty\mu(dt)\,[S_{V_s(t)}^{-1}(D)+T_{s,t}^{-1}(d)I\{s(t)\le d\}], \end{equation} which has to minimized over all smooth enough increasing positive functions $s$ on $[0,\infty)$ such that $s(0)=0$, $s'\le L$, $s'(0)=v_0$, $s''\le a$. This looks pretty complicated! A bit of good news is that the integrand $S_{V_s(t)}^{-1}(D)+T_{s,t}^{-1}(d)I\{s(t)\le d\}$ is a piecewise-algebraic function of $s(t)$ and $s'(t)$.