Car, road, traffic-lights and an optimization problem.

Question

Suppose you are driving on a road at speed $V$, and then at a distance $D$ you see a traffic lights showing "red". You are familiar with that road and know that the light will stay "red" for a time $T$, but as you just came around the corner you don't know how long it is already showing "red".

What is the best strategy to approach the traffic light, when you want your speed to be as high as possible$^1$ at the moment when the lights are switching to "green"? Constraints:

1. You are not allowed to pass the lights as long as they show "red".

2. As long as the lights are "red", you must not speed up, i.e. $|v(t_2)|\leqslant |v(t_1)|$ if $t_2 > t_1$.

3. You are approaching the traffic lights, i.e. $V>0$, where positive speed is towards the lights (in the direction of the road).

4. There is an upper limit for the deceleration of $g=9.8\mathrm{m}/\mathrm{s}^2$, and you are driving at a reasonable[tm] speed: It is possible that you can come to a halt before crossing the lights, even if the lights are "red" for the maximal time $T$.

The last point constrains the initial speed to $V\leqslant gT$, and thus the distance must satisfy $D\geqslant\frac12gT^2$ so that

$$D\geqslant\frac12V\cdot T$$

If the distance is big enough, i.e. $D\geqslant V\cdot T$ then the solution is simply to keep on driving with $V$ because at the moment you will reach the lights they will have changed to "green".

So let's also assume $D < V\cdot T$ in the remainder.

One strategy is to keep on driving with $V$ and if the lights don't switch doing a full brake and come to a halt.

But there might be better strategies like braking gradually, which gains you some extra time in which the lights might turn "green". The speed $v(T)$ is then not as high as $V$ but that's definitely better than coming to a halt.

I have no idea how to even formalize this...

Even if we knew the best strategies for all remaining times $T^{*}$, how would you average / combine these $v_{T^{*}}(t)$ to get the best solution w.r.t expected speed at the time the lights are switching "green"?

Presumably a calculus of variations problem?

In addition to the constraints from above, the following clarifications / simplifications shall apply:

• The road is flat, i.e. no hills or (change in) potential energy.

• You must stay on the road, i.e. the car moves on a prescribed trajectory. The road is just a 1-dimensional smooth line$^2$ with the lights at distance $D$ ahead.

• The times when you come around the corner and see that the lights are "red" are evenly distributed during the "red"-phase, i.e. the average time until they switch "green" is $T/2$.

• There is no friction or drag etc.: Change in speed is only due to using the brake.

• There are no other cars etc. that would impede you.

• Speed of light is infinitely high.

---

$^1$This is the most energy-efficient way of driving provided braking just dissipates kinetic energy.

$^2$Without loss of generality we can assume the road is straight, because change in direction won't dissipate energy as the component of such acceleration is perpendicular to the direction of motion.

---

Hint:

The best $v(t)$ is constrained by:

• "Red" lights must not be crossed:

$$0 \leqslant \int_0^T v(t) dt \leqslant D $$

• No speed-up while "red":

$$-g \leqslant v'(t) \leqslant 0 $$

• Must not move backwards and no speed-up:

$$ 0 \leqslant v(t) \leqslant v(0) = V $$

If the switching time is known to be exactly $T^*$, then the optimal speed at time $T^*$ is given by

$$ v_{T^*} = V - gT^* + \sqrt{g(2D + g{T^*}^2 - 2VT^*)} $$

which follows from a simple geometric consideration. No Idea how to use that or if it's of any use at all...

Answer 1

Since the time at which the light turns green is uniformly distributed over $[0,T]$, your expected velocity at the moment the light turns green is: $$\int_{0}^{T}\frac{v(t)}{T} dt = \frac{1}{T} \int_{0}^{T}v(t) dt$$ This is simply the distance that would be traveled by time $T$ divided by $T$. Any path $\hat{v}$ that traverses the whole distance D, i.e. $$\int_{0}^{T}\hat{v}(t) dt = D$$ will have an average velocity of $D/T$ and be optimal. It does not matter how you decelerate (or even accelerate, go backwards, etc.) so long as you would traverse the whole distance D by time $T$.

---

How to compute fuel efficiency requires we define what fuel efficiency is. Minimizing how much you brake and accelerate: $$\int_{0}^{T} |v'(t)|dt$$ is equivalent to what maximizing your expected velocity at the moment the light turns green, as was previously answered.

Alternatively, maybe fuel efficiency is equivalent to minimizing the dissipation of kinetic energy? (There is then no reason to ever accelerate as it only makes you go further without increasing the objective function.) If the car does not accelerate, then the problem is equivalent to maximizing the kinetic energy that remains: $$\int_{0}^{T}\frac{v(t)^{2}}{T} dt$$ Intuitively, because kinetic energy is convex in velocity, this expectation will be maximized by staying at the initial velocity of $V$ for as long as possible, denote this path by $\tilde{v}$. Further, let $F_{v}(\hat{V})$ denote the cumulative density function of velocity, i.e. the probability that velocity is less than $\hat{V}$ when the light turns green. Note that since $v$ and $\tilde{v}$ are non-increasing (supposing no acceleration), $$F_{v}(x) = \Pr[v(t_\textrm{green}) \leq x] = \int_{v^{-1}(x)}^{T} \frac{1}{T} dt = \frac{T-v^{-1}(x)}{T}$$

Claim 1: For any $v(t)$, there exists a $t^{*}$ (not necessarily unique) such that for all $t < t^{*}$ we have $\tilde{v}(t) \geq v(t)$, and for all $t > t^{*}$ we have $\tilde{v}(t) \leq v(t)$.

Proof: Let $\tilde{t}$ be the time at which $\tilde{v}$ starts decelerating, then: $$t^{*} = \inf \{t\geq\hat{t}| \tilde{v}(t^{*}) \leq v(t^{*}) \}$$ By construction, for all $t < t^{*}$ we have $\tilde{v}(t) \geq v(t)$. Further, since $\tilde{v}$ decelerates as quickly as possible to zero after $\hat{t}$, and at $t^{*} > \hat{t}$ we have $\tilde{v}(t^{*}) \leq v(t^{*})$, it must be that for all $t > t^{*}$ we have $\tilde{v}(t) \leq v(t)$.

Corollary 1: For any $v(t)$, take the $t^{*}$ satisfying the previous claim and let velocity $x^{*} = \tilde{v}(t^{*})$, then for all $x < x^{*}$ we have $F_{\tilde{v}}(x) \geq F_{v}(x)$, and for all $x > x^{*}$ we have $F_{\tilde{v}}(x) \leq F_{v}(x)$.

Claim 2: Any $v(t)$ which doesn't go distance $D$ by time $T$ is not optimal since $\hat{v}(t) = v(t-\epsilon)$ where $\epsilon>0$ is chosen so that $\hat{v}$ goes distance $D$ in time $T$ results in higher expected kinetic energy by delaying any deceleration.

Claim 3: Take any $v(t)$ which goes distance $D$ by time $T$, then $F_{\tilde{v}}$ is a mean preserving spread of $F_{v}$.

Proof: Since both $v(t)$ and $\tilde{v}(t)$ go distance $D$ by time $T$, they have the same mean velocity, which implies that: $$\mathbb{E}[\tilde{v}(t)] = \int_{0}^{V} 1 - F_{\tilde{v}}(x)dx = \int_{0}^{V} 1 - F_{v}(x)dx = \mathbb{E}[v(t)] = D/T$$ $$\Longrightarrow \int_{0}^{V} F_{\tilde{v}}(x) - F_{v}(x)dx = 0$$ Define: $$A(\hat{x}) = \int_{0}^{\hat{x}} F_{\tilde{v}}(x) - F_{v}(x)dx$$ Then $A(0) = 0$ and $A(V) = 0$. By Corollary 1, $A$ is increasing for $\hat{x}<x^{*}$ and decreasing from $\hat{x}>x^{*}$. Thus, $A(\hat{x})\geq 0$ for all $x$, and strictly for some $x$ if $F_{\tilde{v}}$ and $F_{v}$ are different.

By Claims 2 and 3, $\tilde{v}(t)$ (strictly) maximizes the expectation of any (strictly) convex function of velocity.

---

In addition to $\tilde{v}$ being a solution to either of the previous optimization problems, notice that it also minimizes the expected distance between the car and the light when it turns green.

I don't believe frictions would really affect the analysis as they are just mandatory braking? We would have to define friction and fuel efficiency to actually show that though.

Other considerations could be considered, e.g. comfort and not damaging the brakes. The point is you can decelerate/accelerate however you like without affecting your expected velocity for when the light turns green as long as you go distance $D$ by time $T$. Or, if you want to maximize kinetic energy, you should wait as long as possible to slow down.