Approaching a Stop Light

Proposed by Bouyack on 02/16/2008

I came up with this problem while driving to work one morning:

As you are driving you come around a bend in the road and see that the stoplight in front of you is red. What is the best strategy for approaching the red light if you want to minimize the time it takes you to get to your destination? You can assume there are no other cars on the road. You are not allowed to break the traffic laws (i.e. you cannot run the red light and you have to obey the speed limit). Also, at this particular intersection you cannot make a right turn on red. You are given the following constants:

The answer is given in the form of a function which indicates your acceleration, positive or negative, as you approach the light. The function can be in terms of either time or distance to the light.

Two additional questions:

Note that the answer may not be unique.

Discussion

I wasn't able to come up with a full equation yet (though I did write some stuff out like in the good ol' days… ah, memories), but at least I have some thoughts as to what it should look like. The ideal situation is to be going at v_max when you reach d, but since you're not allowed to break any laws and (in the first scenario anyway) you have no idea how much longer the light will remain red, you must err on the side of caution. Therefore, you will have to undergo maximum deceleration once you reach a certain distance from the light, which is a function of your speed: d_startbrake(v) = v2/2(b_max). Prior to reaching that point, you should accelerate as much as possible and as long as possible (until you hit v_max) in hopes that the light will change before you hit d_startbrake(v_max). Unfortunately since you have no information about the light you can't do probabilities or anything without risking breaking the law, so I think that's the best you can do. Additionally, I don't believe the actual magnitudes of these constants necessarily come into play unless you run into an unfortunate situation where d_startbrake(v0) > d (asleep at the wheel?), in which case there would be no way to stop in time.

I'm too lazy to write it out formally, but the acceleration function for this would be something wonky like "a_max (unless your velocity hits v_max, at which point 0) until you reach d_startbrake(v), at which point b_max".

Knowing the period of the light should change things (there would be a point in the d_startbrake function where you could start accelerating again, which I guess would turn it into d_startbrake(v,t)?), and knowing how long the light was red would probably also improve your time in the average case because you'd be able to assign a value to t, removing the variable and thus making the function dependent on just your velocity.

— Greg Strnad 2008/03/03 18:18

It is possible that your strategy is the optimal one but I wish that I could prove it. It's also possible that the optimal solution is some gradual slope (of the velocity) down to zero or something else. Unfortunately, even evaluating the value of a simple strategy runs into yucky algebra and triple integrals. The integrals aren't so terrible but keeping everything symbolic (as opposed to plugging in values for some of the variables) leads to rather lengthy expressions and working it out by hand is error prone. Proving the optimal strategy is even more difficult.

— Matt Bouyack 2008/03/16 20:46

I've actually made significant progress on simplifying the evaluation of strategies. I've taken some pictures of my work (since it would be rather disgusting to attempt to write out all the equations in text alone) and will post them shortly. I've introduced several new variables. x_max is the point at which, if you were forced to come to a complete stop at the intersection, you would reach v_max given that you accelerate at a_max. This is, effectively, the furthest point that matters. The optimal strategy will be the one that, on average, reaches x=x_max in the shortest time. I also use the variables t_star, v_star, and d_star. These are the time, velocity, and distance to the intersection that you were at when the light turned green. Here's an outline of my work: First I calculate t_total in terms of t_star, v_star, d_star and the five variables originally given. t_total is the total time it takes to reach x_max from the point you first see the stoplight. Next I calculate the average value of this expression by integrating from t=0 to t=T, where T is the period of the light, the maximum time you will ever have to wait. Though in the original problem the period is unknown (essentially infinite) this eliminates the need to deal will an integral that doesn't converge. Later, after such complications have been simplified away, one can just take the limit as T → infinity to arrive at the answer to the original problem. At this point in my calculations I introduce the variable phi, which is the strategy you are evaluating. With this comes v_phi(t), d_phi(t), and a_phi(t), the velocity, distance, and acceleration at time t based on the strategy phi. The last thing I do is make some major simplifications based on two observations. The first is that if cost(phi) is minimized by the strategy phi, than cost(phi)+k and cost(phi)*k are also minimized by phi. That is, I can add or multiply by any constant (for multiplying it has to be non-zero, non-negative) without changing the relative evaluation of a strategy. The second observation is that d_phi(0) = d_0 and d_phi(T)=0. The final result is:

— Matt Bouyack 2008/03/17 00:07