The Red Light Problem
In this blog post we derive the optimal way to slow down for a red light using variational calculus. We derive all of the results from first principles, and rely on analogies and intuition to illuminate the key ideas of variational calculus.
This post assumes no prior knowledge beside basic calculus and probability. We also mention Holder’s Inequality from Analysis.
The basic situation described is familiar to anyone who drives. You are in a hurry, your cruising around 40 mph. You see the stoplight ahead turn red. You start to tap the brake, but you don’t want to slow down too much. There is a chance that if you control your speed correctly, you won’t come to a full stop before the light turns green.
You slowly tap the break, and slow down to about 20 mph, suddenly the light turns and you speed past all the cars that had come to a full stop. All because of your optimal breaking given the red light, your distance to the light, and your belief about how long the light would last.
But how do you know how much to tap the break. Is there an optimal way to slow down? To answer this question we will need to create a mathematical model of the situation and agree on an objective.
Uniform Red Light Problem
A red light appears at distance \(D\) from your car. You know the red light will last at most \(T_{max}\) seconds before turning green.
Let \(v(t)\) be the speed of your car as a function of time, and let \(p(t)\) be a probability density function over time, dictating how likely the light will turn green in a given time period.
Your goal will be to be driving as fast as possible when the light turns green.
In other words your objective is to maximize \(E(v(t_{final})) = \int_0^{T_{max}} v(t)p(t)dt\).
Since you can’t drive through the light you have the following constraint: \(\int_0^{T_{max}} v dt \leq D\). This says that even if the light takes the full amount of time \(T_{max}\), we will not cross the stoplight.
We will assume a uniform distribution on the probability. This is a reasonable assumption but we will relax it later.
Therefore we have \(p(t) = \frac{1}{T_{max}}: 0 \leq t \leq T_{max}\)
Solution to Uniform Red Light Problem
So we wish to maximize \(E(v(t_{final})) = \int_0^{T_{max}} v(t)p(t)dt = \frac{1}{T_{max}}\int_0^{T_{max}} v(t)dt\)
Combining with our constraint \(\int_0^{T_{max}} v dt \leq D\) we get:
\[max_v E(v(t_{final})) \leq \frac{D}{T_{max}}\]This upper bound can be realized by simply driving at speed \(\frac{D}{T_{max}}\) until the light turns.
A lot of people would stop here. This is pretty intuitive, and the math works out very nicely. But we will venture further into the problem by relaxing our assumption that the probability is uniform.
Intuitively, we can maybe go faster by speeding up when we think the light is about to turn. This is only possible given non uniform probabilities.
The generalized problem looks like this:
Holder’s Red Light Problem (optional section)
Maximize: \(\int_0^{T_{max}} v(t)p(t)dt\)
Given: \(\int_0^{T_{max}} v dt = D\)
This statement immediately made me think of the Extremal Holder’s inequality.
This extremal equality states the following:
\[D \lVert p \rVert _{\infty}=sup(\int_0^{T_{max}} vpdt: \lVert v \rVert_1=D)\]So the top speed that we can travel should be \(D \lVert p \rVert _{\infty}\).
In the the case of uniform distribution we again get \(\frac {D}{T_{max}}\), so we can see the uniform case as a special case of the general problem.
There is an issue with the above solution. If one inspects the proof of Holder’s Inequality it is proved by essentially constructing a delta function. Let me explain:
In driving terms, the Holder’s Inequality strategy above would entail a driver waiting for the most probable moment for the light to turn green, and then speeding up to almost infinity. This is not a realistic way to approach a red light.
One way to solve for this non physical behavior is to put an explicit tax on acceleration in the problem statement, or adding speed limits. I decided instead to put a tax on the variance; let me explain.
I thought about my own driving behavior, why I didn’t accelerate very fast when I thought the light would turn?
I realized that for me it is risk aversion, though it feels great to accelerate as the light turns green, if you get it wrong your going to have to stop at the light.
The delta strategy is just to risky for me, I really don’t want to be caught at the light.
Therefore we should make our drivers have a tolerance for risk. In other words, let’s change the problem a bit:
Risk Averse Red Light Problem
Maximize: \(\int_0^{T_{max}} v(t)p(t)dt\)
Given: \(\int_0^{T_{max}} v dt = D\)
\[\int_0^{T_{max}} v(t)^2p(t)dt - \int_0^{T_{max}} v(t)p(t)dt^2 = Var_{max}\]Let’s transform this into an equivalent problem that is easier to solve.
Risk Averse Red Light Variational Problem
Maximize: \(\int_0^{T_{max}} v(t)p(t)dt\)
Given:\(\int_0^{T_{max}} v(t)^2p(t)dt = C\) \(\int_0^{T_{max}} v dt = D\)
Theorem
If \(v*\) solves the Risk Averse Red Light Problem the above than \(v*\) will also solve the variational problem with \(C = Var_{max} - E(v*)^2\):
Proof:
Say the above equation is solved by \(w*\). Then \(E(w*)\geq E(v*)\) and therefore \(Var(w*) = C - E(w*)^2 \leq C - E(v*)^2 = Var(v*)\). Therefore \(w*\) must also solve the non variational setup.
Penalty Problem
We have a well defined problem, but I am going to venture to guess that many don’t know how to solve the above variational problem.
We are going to take the approach of starting with a simpler problem and building up from there.
To ‘soften’ the constraints, let’s instead add a financial penalty for violating the constraints. The fine system will be denoted as \((\lambda_1, \lambda_2)\)
In this penalty problem, we seek to maximize the following:
\[\int_0^{T_{max}} v(t)p(t) - \lambda_1 \ (v(t)^2p(t)dt-C/T_{max}) -\lambda_2 (v-D/T_{max}) dt\]given the ability to change \(v(t)\).
This is if the driver was penalized for going through the red light or by exceeding variance threshold by an amount proportional to the violation.
Solution to the penalty problem
We will solve this by assuming the driver has stationary behavior around the light turning.
So let’s take the delta of the function. Say we had a solution \(v*\) to this optimization problem. If we perturb \(\int_0^{T_{max}} v(t)p(t) - \lambda_1 \ (v(t)^2p(t)-C/T_{max}) -\lambda_2 (v-D/T_{max}) dt\) by a small amount we get:
\[\int_0^{T_{max}} (v + \delta v) p - (\lambda_1) \ ((v+ \delta v)^2p-C/T_{max}) -(\lambda_2) (v + \delta v -D/T_{max}) dt\]Taking differences we get:
\[\int_0^{T_{max}} \delta v p - \lambda_1 \ 2v \delta vp -\lambda_2 (\delta v) dt =\int_0^{T_{max}} \delta v *(p - \lambda_1 \ 2v p -\lambda_2) dt\]By stationarity we get: \(p - \lambda_1 \ 2v p -\lambda_2 = 0\)
The driver’s behavior will have to satisfy this relationship given \((\lambda_1, \lambda_2)\)
Finally we get the speed:
\[v = \frac {\lambda_2 - p}{2 \lambda_1 p}\]The Competitive problem
We were able to find solutions the the above by finding stationary points given the fine system.
But what if we need to find stationary points given not only \(v\) changing, but also \((\lambda_1, \lambda_2)\).
In this penalty problem, we seek to maximize the following:
\[\int_0^{T_{max}} v(t)p(t) - \lambda_1 \ (v(t)^2p(t)dt-C/T_{max}) -\lambda_2 (v-D/T_{max}) dt\]given the ability to change \(v(t), (\lambda_1, \lambda_2)\).
You can think of this as a nash equilibrium for an adversarial game between a fine-setter and a driver.
Theorem:
A solution to the competitive problem is also a solution to the variational problem.
Proof: Any solution must satisfy the constraints, or else the penalty setter could make a driving strategy less profitable. Therefore The constraints are satisfied by any solution to the competitive problem.
Since the solutions are in the space of the constraints, the competitive problem collapses into the variational problem.
Solution to the competitive problem
We know that any solution must be stationary in \(v(t), (\lambda_1, \lambda_2)\).
We can look at delta’s in \((\lambda_1, \lambda_2)\) but that only gives our constraints back.
We can look at delta’s in \(v(t)\), and we get the following:
\(p - \lambda_1^* \ 2v^* p -\lambda_2^* = 0\).
This is identical for what we got solving the penalty problem, but we don’t know the prices this time.
Finding the prices
To simply notation, I am going to say we got it down to this point:
\[v = v_0 + \frac{c}{p}\]We will also call \(T_{max}\) as \(T\) and \(E(v)\) as \(E\) and \(i = \int_0^T \frac{1}{p}\)
We know that
\[E = \int_0^T (v_0 +\frac{c}{p})p dt = v_0 +c T\] \[D = \int_0^T v_0 +\frac{c}{p} dt = v_0 T +c \int_0^{T} \frac{1}{p}\]So:
\[E = v_0 + cT\] \[D = v_0T + ci\]Let’s set \(M =\frac{ET}{D}\), this represents how much faster we are going than the uniform distribution strategy. We are only interested in solutions where \(M \geq 1\).
Solving for \(c\) to isolate \(v_0\) we get:
\[v_0 = \frac{TD-iE}{T^2 - i} = \frac{D}{T}\frac{iM-T^2}{i-T^2}\]Also:
\[c = \frac{E - v_0}{T} = \frac{MD}{T^2}- \frac{D}{T^2}\frac{iM-T^2}{i-T^2} = \frac{D(1-M)}{i-T^2}\]Finally.
\[v(t) = \frac{D}{i-T^2}(\frac{iM - T^2}{T} + \frac{D(1-M)}{p(t)})\]\(p\): pdf of light turning green:
\(v\): velocity as a function of time.
\(M\): How much faster than benchmark
\(T\): maximum amount of time a light can last.
\(D\): Distance from light originally.
\[i= \int_0^T \frac{1}{p(t)}dt\]Let’s talk quickly about signs.
\(i-T^2\) will always be positive. \(T^2\) is the \(i\) of the uniform distribution and represents a minimum.
Therefore \(iM-T^2\) will also be positive since we assume that \(M > 1\)
\(\frac{D(1-M)}{p}\) is negative, which makes sense, for small p we reduce our speed.