21
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of What braking strategy is most fuel-efficient? $\endgroup$ – Anton Geraschenko Oct 22 '17 at 17:31
  • 1
    $\begingroup$ @AntonGeraschenko : I see some differences: here we also have parameters $a$ and $L$. Also, the distribution $\mu$ here is not necessarily uniform. $\endgroup$ – Iosif Pinelis Oct 22 '17 at 17:39
  • 3
    $\begingroup$ Whoa! MO autogenerates a comment from me when I try to tag duplicates. I meant to point to mathoverflow.net/questions/33312/… and mathoverflow.net/questions/1108/…, and comment about how it's easy to get confused about what you're optimizing (stacky.net/wiki/…). I now notice that the goal in this question is actually pretty different from those. This question aims to optimize ETA, rather than wasted energy. $\endgroup$ – Anton Geraschenko Oct 22 '17 at 17:48
  • 2
    $\begingroup$ I think one must specify rules about allowability of passing the light before it turns green. E.g., to be absolutely sure to not do so is a severe constraint... $\endgroup$ – paul garrett Oct 22 '17 at 19:17
  • 2
    $\begingroup$ @paul Since we have perfect brake, it doesn't sound that severe. To think of it, even without that, after all this is a real-life inspired question and I do want to be absolutely sure not to go when it's red. $\endgroup$ – domotorp Oct 22 '17 at 19:33
7
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't know enough variation calculus to be sure, but this looks quite convincing. At the end of the uniform distribution, I think the RHS should be $L-a(t-\alpha-\lambda)$. Also, the constants seem to be easy to determine: we need to set them so that we stop at the light at time $\alpha$, so $\lambda=-\frac La$. Btw, in the first para what is $v'$? Shouldn't it be $v$? And when discussing the constraints in the third para, I think some $\ge d$ should be $\le d$. $\endgroup$ – domotorp Dec 22 '17 at 20:04
  • 1
    $\begingroup$ Thanks for the proof reading. I use $v'$ instead of $v$ because the actual velocify function is no longer $v$ once the light turns - according to the strategy I give at the start it switches to "accelerate at $a$ until you reach $L$". So $v$ is the velocity function that would be followed if the light never turns green, and $v'$ is the actual velocity function which veers away from $v$ when the light turns. $\endgroup$ – Mario Carneiro Dec 23 '17 at 1:12
  • 1
    $\begingroup$ I think the solution for $\lambda$ is more complicated than that. We don't need to stop at time $\alpha$, we need to stop at the light, i.e. at position $d$. In fact, we have a parabola $d(t)=(L+a\beta)t-at^2/2$, and we want $\beta:=\alpha+\lambda$ to be maximal such that $d(t)\le d$ for all $t\le \alpha$. There are two cases depending on whether the parabola "hits its head or gets poked in the side": the parabola has maximum when $v(t)=0$, i.e. $t^*=L/a+\beta$, with value $d(t^*)=\frac{(L+a\beta)^2}{2a}$. ... $\endgroup$ – Mario Carneiro Dec 23 '17 at 2:44
  • 1
    $\begingroup$ ... If $\alpha$ is large enough, we want this to be equal to $d$, so $\beta=\frac{\sqrt{2ad}-L}{a}$, in which case we have $t^*=\sqrt{2d/a}$, meaning that this solution is valid when $\alpha\ge t^*$, i.e. $d\le a\alpha^2/2$. Otherwise, we want to solve for $d(\alpha)=d$, so $\lambda=\frac{d}{a\alpha}-\frac{L}a-\frac\alpha2$. $\endgroup$ – Mario Carneiro Dec 23 '17 at 2:51
  • $\begingroup$ I had this exact same question, so great to see an answer! Since I only took math up to calculus 2, this math looks a bit too foreign to me, is there any way to visualize the velocity curve? $\endgroup$ – Ryan Jan 30 at 19:58
1
$\begingroup$

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)$.

$\endgroup$
  • 6
    $\begingroup$ It is clear that then the problem reduces to the maximization of the expected speed at the time moment when you pass the light. Why? The dependence of the ETA on that speed is not linear! $\endgroup$ – fedja Oct 22 '17 at 17:52
  • 6
    $\begingroup$ ETA doesn't look like a function of expected speed when you pass the light. To maximize expected speed when you pass the light, a reasonable strategy (assuming $a$ and $d$ are not too small) is to immediately come to a complete stop, and accelerate as much as possible once the light turns green. $\endgroup$ – Anton Geraschenko Oct 22 '17 at 17:57
  • $\begingroup$ Indeed, I didn't properly consider the time before the light. This should now be corrected. $\endgroup$ – Iosif Pinelis Oct 22 '17 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.