====== 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:

  * **v0** - velocity when you noticed the light was red
  * **d** - distance from intersection
  * **v_max** - the speed limit
  * **a_max** - maximum acceleration possible for your car
  * **b_max** - maximum braking (deceleration) possible for you car

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:

  * Does the answer change at all if you know the period of the light?
  * What if you also know how long the light has been red?

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) = v<sup>2</sup>/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(v<sub>0</sub>) > 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.

 --- //[[gerf@thegerf.net|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. 

 --- //[[mjb40@case.edu|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:

     ***cost(phi) = integral(0,T,t,v_phi(t)*v_phi(t)/2 + d_phi(t)*a_max)**

{{thinktank:stoplight.jpg?300|}}

 --- //[[mjb40@case.edu|Matt Bouyack]] 2008/03/17 00:07//