This Riddler is about how to perfectly time a stoplight, something we’ve all had to deal with!
You are driving your car on a perfectly flat, straight road. You are the only one on the road and you can see anything ahead of you perfectly. At time t=0, you are at Point A, cruising along at a speed of 100 kilometers per hour, which is the speed limit for the whole road. You want to reach Point C, exactly 4 kilometers ahead, in the shortest time possible. But, at Point B, 2 kilometers ahead of you, there is a traffic light.
At time t=0, the light is green, but you don’t know how long it has been green. You do know that at the beginning of each second, there is a 1 percent chance that the light will turn yellow. Once it turns yellow, it remains yellow for 5 seconds and then turns red for 20 seconds. Your car can accelerate or decelerate at a maximum rate of 2 meters per second-squared. You must always drive at or below the speed limit. You can pass through the intersection when the traffic light is yellow, but not when it is red.
What is the best strategy to reach your destination as soon as possible?
Here is my solution:
[Show Solution]
Let’s give names to the variables so that the unit conversions don’t become cumbersome. Define:
\begin{align}
x_\text{light} &= \text{position of the traffic light (2 km)} \\
x_\text{end} &= \text{position of the finish line (4 km)} \\
v_\text{max} &= \text{speed limit (100 km/h)} \\
a_\text{max} &= \text{maximum acceleration (2 m/sec}^2\text{)} \\
\tau_y &= \text{time that a yellow light lasts (5 sec)} \\
\tau_r &= \text{time that a red light lasts (20 sec)}
\end{align}
It is implicitly assumed in the problem that we can never run a red light. So even though we don’t know when the light will turn yellow, we can’t take any chances; we must make sure that even the unlikeliest most ill-timed yellow light can never cause us to run a red.
There are many different approaches to solving this problem but since I’m currently teaching a class on optimization modeling, I figured I would go that route. The idea behind a modeling approach is to imagine that the position, velocity, and acceleration of the car are decision variables that must satisfy several constraints.
Basic variables and constraints
Let’s discretize the time interval and suppose we make decisions at every $\Delta t$ seconds. So if $\Delta t = 1$, we make decisions every second. Then, define the following decision variables:
\begin{align}
x_t & \ge 0 && \text{position at time }t\\
0 \le v_t &\le v_\text{max} && \text{speed at time }t\\
-a_\text{max} \le a_t &\le a_\text{max} && \text{acceleration at time }t
\end{align}where the time indices range over $t=0,1,\dots,T$ where $T$ is sufficiently large. Of course, we cannot choose positions and velocities arbitrarily; they must be consistent. By approximating the acceleration as constant over each $\Delta t$ step, we may write that:
\begin{align}
v_{t+1} &= v_t + a_t \Delta t && \text{(change in speed with constant accel.)}\\
x_{t+1} &= x_t + v_t\Delta t + \tfrac{1}{2}a_t \Delta t^2 && \text{(change in pos. with constant accel.)}
\end{align}We also have initial conditions for position and speed:
\[
x_0 = 0 \qquad\text{and}\qquad v_0 = v_\text{max}
\]Note that we constrained the speed to be nonnegative. It turns out this doesn’t matter and there is nothing to be gained by allowing backward movement. We get the same answer either way!
Contingency planning
Since we can never risk running a red light, we must ensure that at every instant, one of two things must happen. Either:
- We can reach $x_\text{light}$ within $\tau_y$ sec. (we run the yellow) or:
- We never pass $x_\text{light}$ within $\tau_y+\tau_r$ sec. (we can avoid running a red).
These constraints can be encoded algebraically. For each $t$, We’ll define a new set of positions, velocities, and accelerations that last for $\tau_y+\tau_r$ seconds. These are contingency variables that allow us to ensure nothing can go wrong if the light turns yellow at time $t$. So we define the variables:
\begin{align}
\hat x_{t,k} & \ge 0 && \text{(contingency position)}\\
0 \le \hat v_{t,k} &\le v_\text{max} && \text{(contingency velocity)}\\
-a_\text{max} \le \hat a_{t,k} &\le a_\text{max} && \text{(contingency acceleration)}
\end{align}These new contingency variables are defined over $0\le t \le T$ and $0 \le k \le \tau_y+\tau_r$. Just like the ordinary position and velocity, they must satisfy contingency constraints:
\begin{align}
\hat v_{t,k+1} &= \hat v_{t,k} + \hat a_{t,k} \Delta t && \text{(change in speed with const. accel.)}\\
\hat x_{t,k+1} &= \hat x_{t,k} + \hat v_{t,k} \Delta t + \tfrac{1}{2}\hat a_{t,k} \Delta t^2 && \text{(change in pos. with const. accel.)}
\end{align}We also have initial conditions for position and speed:
\[
\hat x_{t,0} = x_t \qquad\text{and}\qquad \hat v_{t,0} = v_t
\]Now that we have the contingency trajectories set up, we must encode our binary constraint. Either we can run the yellow, or we are safe from running the red. Let’s define binary variables:
\begin{align}
z^y_t \in \{0,1\} & \qquad \text{(can we run the yellow if light turns yellow at }t\text{?)}\\
z^r_t \in \{0,1\} & \qquad \text{(are we safe from running the red if light turns yellow at }t\text{?)}
\end{align}The constraints that we can run the yellow and not run a red are:
\begin{align}
\hat x_{t,\tau_y} &\ge x_\text{light} z^y_t &&\quad\text{for all }t\text{, and}\\
\hat x_{t,\tau_y+\tau_r} &\le x_\text{light} + (1-z^r_t)x_\text{end} &&\quad\text{for all }t\text{, respectively.}
\end{align}together with the logic constraint $z^y_t + z^r_t \ge 1$ for all $t$, which ensures that we can run the yellow OR we are safe from running the red. And that’s it!
Objective function
The work above describes the feasible set of position, velocity, and acceleration profiles that guarantee we never break the law. Among these profiles, we should choose the one that gets us to the finish line as fast as possible on average. I struggled to find a simple objective function that captures this notion precisely. As a compromise, I simply minimized the duration of the trip assuming the light never turns red. This should be a decent approximation to the true solution because yellow lights are relatively rare. Most of the time when the light turns yellow, it doesn’t actually affect us; it’s only a concern if the light turns yellow when we are close to it, which won’t happen all that often.
To characterize the finish time, I defined the binary variables:
\[
z^e_t \in \{0,1\} \qquad \text{(are we finished at time }t\text{?)}
\]together with the constraint:
\[
x_t \ge x_\text{end} z^e_t\qquad\text{for all }t.
\]Now, our binary variable will be $1$ whenever we have crossed the finish line. So by maximizing $\sum_{t=0}^T z^e_t$, we get to the end as soon as possible.
Solution
From a modeling standpoint, all our constraints are linear, which is nice. We do have some binary variables, which makes this a mixed-integer linear program (MILP). Nevertheless, the problem is relatively easy to solve using a standard solver. For this problem, I coded the model in Julia together with the JuMP package and the Gurobi solver. Some details:
- Solving with $\Delta t = 1$. After presolve, the problem had: 3492 constraints, 6216 continuous variables, and 108 binary variables. Solving took about 0.3 seconds on a laptop.
- Solving with $\Delta t = 0.5$. After presolve, the problem had: 15499 constraints, 29602 continuous variables, and 216 binary variables. Solving took about 1.3 seconds on a laptop.
- Solving with $\Delta t = 0.25$. After presolve, the problem had: 63925 constraints, 125250 continuous variables, and 436 binary variables. Solving took about 12 seconds on a laptop.
No matter the time discretization, all solutions looked the same. Here is a plot of the solution for $\Delta t = 0.25$, zoomed in near the point where the car approaches the traffic light.
The plot looks constant outside this range. So, the optimal thing to do is maintain a speed of 100 km/h for 65 seconds, then decelerate as hard as possible for 2.5 seconds, then accelerate as hard as possible for 2.5 seconds, and then continue on at 100 km/h. The reason for the dip in velocity is that we would otherwise be unable to stop in time if the light were to turn yellow, so we must be risk-averse. After 67.5 seconds, we can safely accelerate, knowing that if the light turns yellow we will make it within the next 5 seconds.
If you’re interested in seeing my code in full detail, you can view/download my notebook here.
I wish I could take your class!
I too just intuited that the probability is too small for any other strategy to be advisable, and I just directly calculated what you can do to get through the light going as fast as possible if it does turn yellow at various points. (https://www.sharelatex.com/project/588bc1336e5de4073270ebed) I’m curious about at what probability-per-second it starts to be preferable to ensure that you can hit the light at top speed as the red ends, but not curious enough to go through the drudgery of calculating the expectations.
I think backing up does make sense (if legal) where otherwise, with full deceleration to zero starting when you see the yellow and full acceleration to the hit the light as it turns green, you’d be sitting at rest for some period of time–you can use that time to back up and hit the light going faster than you would have.
Yes, backing up makes sense. All I did in my solution was compute the optimal trajectory assuming the light never turns yellow. Depending on when it does turn yellow, that affects how you should act.
I think the real way to solve this problem would be to solve a separate optimization for each possible instant where the light could turn yellow. This gets messy pretty quickly using my approach, so I abandoned the idea. I wish the posted solution on fivethirtyeight gave more insight rather than just stating the solution. i.e. I’m not convinced it’s even correct.