Optimal Control of Autonomous Vehicles Approaching A Traffic Light
Xiangyu Meng Christos G. Cassandras




Optimal Control of Autonomous Vehicles Approaching A Traffic Light
    Xiangyu Meng, and Christos G. Cassandras This work was supported in
part by NSF under grants ECCS-1509084, IIP-1430145, and CNS-1645681, by AFOSR
under grant FA9550-12-1-0113, by DOE under grant DOE-46100, and by Bosch and
the MathWorks. The authors are with the Division of Systems
Engineering and Center for Information and Systems Engineering, Boston
University, Brookline, MA 02446 USA e-mail: {xymeng,cgc}@bu.edu.
    December 30, 2023
======================================================================================================================================================================================================================================================================================================================================================================================================================================




This paper devotes to the development of an optimal acceleration/speed profile
for autonomous vehicles approaching a traffic light. The design objective is
to achieve both short travel time and low energy consumption as well as avoid
idling at a red light. This is achieved by taking full advantage of the
traffic light information based on vehicle-to-infrastructure communication.
The problem is modeled as a mixed integer programming, which is equivalently
transformed into optimal control problems by relaxing the integer constraint.
Then the direct adjoining approach is used to solve both free and fixed
terminal time optimal control problems subject to state constraints. By an
elaborate analysis, we are able to produce a real-time online analytical
solution, distinguishing our method from most existing approaches based on
numerical calculations. Extensive simulations are executed to compare the
performance of autonomous vehicles under the proposed speed profile and human
driving vehicles. The results show quantitatively the advantages of the
proposed algorithm in terms of energy consumption and travel time.





§ INTRODUCTION


The alarming state of existing transportation systems has been well
documented. For instance, in 2014, congestion caused vehicles in urban areas
to spend 6.9 billion additional hours on the road at a cost of an extra 3.1
billion gallons of fuel, resulting in a total cost estimated at $160 billion
<cit.>. From a control and optimization standpoint, the
challenges stem from requirements for increased safety, increased efficiency
in energy consumption, and lower congestion both in highway and urban
traffic.

Connected and automated vehicles (CAVs), commonly known as self-driving or
autonomous vehicles, provide an intriguing opportunity for enabling users to
better monitor transportation network conditions and to improve traffic flow.
Their proliferation has rapidly grown, largely as a result of Vehicle-to-X (or
V2X) technology <cit.> which refers to an intelligent
transportation system where all vehicles and infrastructure components are
interconnected with each other. Such connectivity provides precise knowledge
of the traffic situation across the entire road network, which in turn helps
optimize traffic flows, enhance safety, reduce congestion, and minimize
emissions. Controlling a vehicle to improve energy consumption has been
studied extensively, e.g., see <cit.>. By utilizing road topography information,
an energy-optimal control algorithm for heavy diesel trucks is developed in
<cit.>. Based on Vehicle-to-Vehicle (V2V) communication, a
minimum energy control strategy is investigated in car-following scenarios in
<cit.>. Another important line of research focuses on
coordinating vehicles at intersections to increase traffic flow while also
reducing energy consumption. Depending on the control objectives, work in this
area can be classified as dynamically controlling traffic lights
<cit.> and  as coordinating vehicles
<cit.>,<cit.>
,<cit.>,<cit.>. More recently, an optimal
control framework is proposed in <cit.> for CAVs to cross one
or two adjacent intersections in an urban area. The state of art and current
trends in the coordination of CAVs is provided in <cit.>.

Our focus in this paper is on an optimal control approach for a single
autonomous vehicle approaching an intersection in terms of energy consumption
and taking advantage of traffic light information. The term “ECO-AND” short for “Economical Arrival and
Departure”) is often used to refer to this problem. Its
solution is made possible by vehicle-to-infrastructure (V2I) communication,
which enables a vehicle to automatically receive signals from upcoming traffic
lights before they appear in its visual range. For example, such a V2I
communication system has been launched in Audi cars in Las Vegas by offering a
traffic light timer on their dashboards: as the car approaches an
intersection, a red traffic light symbol and a “time-to-go” countdown appear in the digital display and
reads how long it will be before the traffic light ahead turns green
<cit.>. Clearly, an autonomous vehicle can take advantage of such
information in order to go beyond current “stop-and-go” to achieve “stop-free” driving. Along these lines, the problem of
avoiding red traffic lights is investigated in  <cit.>. The purpose in
<cit.> is to track a target speed profile, which is
generated based on the feasibility of avoiding a sequence of red lights. The
approach uses model predictive control based on a receding horizon. The
authors in <cit.> studied an energy-efficient driving strategy
on roads with varying traffic lights and signals at intersections. with the
goal of avoiding a red light instead of following the host vehicle driven by a
human. Avoiding red lights with probabilistic information at multiple
intersections was considered in <cit.>, where the time
horizon is discretized and deterministic dynamic programming is utilized to
numerically compute the optimal control input. The work in
<cit.> devises the optimal speed profile given the feasible
target time, which is within some green light interval. A velocity pruning algorithm is proposed in <cit.> to identify feasible green windows, and a velocity profile is calculated numerically in terms of energy consumption.

Here, we investigate the optimal control problem of autonomous vehicles
approaching a traffic light where the objective function is a weighted sum of
both travel time and energy consumption. The problem is challenging due to the
following reasons. First, finding a feasible green light interval leads to a
Mixed Integer Programming (MIP) problem formulation. In general, solving MIP
problems requires a significant amount of computation, and the optimality of
the solution is not guaranteed due to the non-convexity of the problem
involved with integer variables. The second reason comes from state
constraints related to speed limits. The inclusion of bounds on state
variables poses a significant challenge for most optimization methods. To
overcome the above difficulties, we devise a two-step method. Specifically, we
first address the problem without the traffic light constraint, which means
that the terminal time is free, and the mixed integer constraints are removed.
If the terminal time obtained from the free terminal time optimal control
problem is within some green light interval, then the problem is solved.
However, if the terminal time falls within some red light interval, then the
optimal terminal time could be either the end of the previous green light
interval or the beginning of the next green light interval by using the
monotonicity property of the objective function. Then, we transform the
original problem into a fixed terminal time optimal control problem. We solve
the fixed terminal time optimal control problem with two different terminal
times, and comparing the corresponding performances leads to the optimal
solution of the original problem. All related optimal control problems with
state constraints are solved by using the direct adjoining approach
<cit.>. The main contributions of our paper are:



  * Instead of solving this problem numerically as in
<cit.> and <cit.>, an analytical
solution is obtained.


  * For the free terminal time optimal control problem, it is easy to
characterize the type of the optimal acceleration profile.





  * Due to the on-line and real-time nature of the algorithm, the optimal
control profile can be re-calculated as needed, for example when the optimal
trajectory is interrupted by other road users due to safety constraints.


The remainder of this paper is organized as follows. The problem is formulated
in Section <ref>. In Section <ref>, we present the methodology to solve
the formulated problem, where the solution to the free terminal time optimal
control problem is described in Subsection <ref>, and the solution to the
fixed terminal time optimal control problem is presented in
Subsection <ref>. Simulation results illustrating the use of the
proposed algorithm are presented in Section <ref>. Section <ref>
summarizes our findings, concludes the paper and provides directions for
future work.



§ PROBLEM FORMULATION


 The dynamics of the vehicle are modeled by a double integrator

    ẋ(  t)        =v(  t)  ,
    v̇(  t)        =u(  t)  ,

where x(  t)  , v(  t), and u(  t)
are the position, velocity, and acceleration of the vehicle, respectively. At
time t_0, the initial position and velocity are given as x(
t_0)  =0 and v(  t_0)  =v_0 respectively. Let us use
l to denote the distance to the traffic light, and t_p the intersection
crossing time of the vehicle. The traffic light switches between green and red
at an intersection are dictated by a rectangular pulse signal f(
t) with a period T:

    f(  t)  ={[                       1       for kT≤ t≤ kT+DT,;                       0 for kT+DT<t<(  k+1)  T, ].

where f(  t)  =1 indicates that the traffic light is green, and
f(  t)  =0 indicates that the traffic light is red as shown in
Fig. <ref>. The parameter 0<D<1 is the fraction of the time period
T during which the traffic light is green, and k∈ℤ_≥0 is a
non-negative integer. 

Our objective is to make the vehicle cross an intersection without stopping
with the aid of traffic light information (TLI) as well as to minimize both
travel time and energy consumption. Thus, we formulate the following problem:


 ECO-AND Problem

    min_u(  t)    ρ_t(  t_p-t_0)  +ρ
    _u∫_t_0^t_pu^2(  t)  dt

subject to

    (<ref>) and (<ref>),
         x(  t_p)  =l,
         v_min≤ v(  t)  ≤ v_max
         u_min≤ u(  t)  ≤ u_max

and

    kT≤ t_p≤ kT+DT,

for some k∈ℤ_≥0.




In (<ref>), the term J^t=t_p-t_0 is the travel time while
J^u=∫_t_0^t_pu^2(  t)  dt captures the energy
consumption; see <cit.>.


In order to normalize these two terms for the purpose of a well-defined
optimization problem, first note that the maximum possible value of J^t is
l/v_min. Depending on the relationship between v_min, v_max,
u_max and l, there are two different cases for the maximum possible
value of J^u. The first case is when the road length is long enough so
that the vehicle can accelerate from v_min to v_max by using the
maximum acceleration u_max, i.e., when l≥ v_minv_max-v_min/u_max+1/2(  v_max-v_min)  ^2
/u_max. In this case,

    J^u=∫_t_0^t_pu_max^2dt=v_max-v_min/u_max
    u_max^2=(  v_max-v_min)  u_max.

The second case is when the road length is not long enough for the vehicle to
accelerate to the maximum speed. According to the dynamics (<ref>) and
(<ref>), we have

    v_min(t_p-t_0)+1/2u_max(t_p-t_0)^2=l.

By solving the above quadratic equation, we are able to get

    t_p-t_0=√(v_min^2+2u_maxl)-v_min/u_max.

Therefore, in this case:

    J^u=∫_t_0^t_pu_max^2dt=(  √(v_min^2+2u_maxl)-v_min)  u_max.

We can now specify the two weighting parameters ρ_t and ρ_u as
follows:  ρ_t=ρv_min/l and

    ρ_u={[                                       1-ρ/(  v_max-v_min)  u_max [  if l≥ v_minv_max-v_min/u_max; +1/2(  v_max-v_min)  ^2/u_max ];                          1-ρ/(  √(v_min^2+2u_maxl)-v_min)  u_max                                                        otherwise ].

capturing the normalized trade-off between the travel time and energy
consumption by setting 0≤ρ≤1. When ρ=0, the problem reduces to
minimizing the energy consumption only; when ρ=1, we seek to minimize the
travel time only.

In (<ref>)-(<ref>), the parameters v_min≥0 and v_max>0 are the minimum and maximum allowable speeds for road vehicles,
respectively, while the parameters u_min and u_max are the maximum
allowable deceleration and acceleration, respectively. Note that hen u<0,
the vehicle decelerates due to braking and when u>0 the vehicle accelerates.
Finally, the integer constraint (<ref>) reflects the requirement that
t_p belongs to an interval when the light is green (see Fig.
<ref>).



§ MAIN RESULTS


 Problem <ref> is a Mixed Integer Programming (MIP) problem.
Existing approaches to such problems turn out to be computationally very
demanding for off-line computation, not to mention obtaining analytical
solutions in a real-time on-line context. We propose a two-step approach,
which allows us to efficiently obtain an analytical solution on-line. The
first step is to solve Problem <ref> without the integer constraint
(<ref>). If the optimal arrival time t_p^∗ is within some green
light interval, then the problem is solved. However, if

    kT+DT<t_p^∗<kT+T,

for some k, then we solve Problem <ref> twice with the constraint
(<ref>) replaced by t_p=kD+DT and t_p=kT+T, respectively. We
compare the performance obtained with different terminal times, and the
solution produced by the one with better performance naturally yields the
optimal solution.

Let us first introduce a lemma, which will be used frequently throughout the
following analysis.


 Consider the vehicle's dynamics (<ref>) and (<ref>) with
the initial conditions x_0 and v_0. If the control input u(
t)  =u is constant during the time interval [  t_0
,t_1], then

    v(  t_1)       =v_0+u(  t_1-t_0)  ,
    
    x(  t_1)       =x_0+v_0(  t_1-t_0)  +1/2u(  t_1-t_0)  ^2,
    
    J^u    =u^2(  t_1-t_0)  ;

If the control input u(  t)  =u(  t_1-t) with a
constant u, then

    v(  t_1)       =v_0+1/2u(  t_1-t_0)
    ^2,
    
    x(  t_1)       =x_0+v_0(  t_1-t_0)  +1/3u(  t_1-t_0)  ^3,
    
    J^u    =1/3u^2(  t_1-t_0)  ^3.




The proof is given in Appendix <ref>.

In the following, we first seek the optimal solution to Problem <ref>
without the constraint (<ref>), which is termed “free terminal time
optimal control problem”.



 §.§ Free Terminal Time Optimal Control Problem


 The free terminal time optimal control problem is given below.


 Free Terminal Time Optimal Control Problem

    min_u(  t)  ρ_t(  t_p-t_0)  +ρ_u
    ∫_t_0^t_pu^2(  t)  dt

subject to

    (<ref>) and (<ref>),
        x(  t_p)  =l ,
        v_min≤ v(  t)  ≤ v_max,
        u_min≤ u(  t)  ≤ u_max,

where ρ_t and ρ_u are given in Section <ref>.


From the objective function (<ref>), it can be seen that a minimum energy
consumption solution should avoid braking, that is, u(  t)  ≥0
for t∈[  t_0,t_p]. We will show this fact in the
following lemma.


 The optimal solution u^*(t) to Problem <ref> satisfies
u^∗(  t)  ≥0 for all t∈[  t_0,t_p^*].


The proof is given in Appendix <ref>.

In addition, it follows from this lemma that whenever v(  τ)
=v_max (which may not be possible in some cases), we must have u(
t)  =0 for all t∈[  τ,t_p]. Based on these
observations, we can derive necessary conditions for the solution to Problem
<ref>, which are summarized in the following theorem.


Let x^∗(  t), v^∗(  t),
u^∗(  t), t_p^∗ be an optimal solution to Problem
<ref> and assume that ρ_t≠0 and ρ_u≠0. Then, the
optimal control u^∗(  t) satisfies

    u^∗(  t)  =min_0≤ u(  t)  ≤ u_max
    ρ_uu^2+ρ_t/v^∗(  t_p^∗)  (
    t-τ)  u,

where τ is the first time on the optimal path when v(  τ)
=v_max if τ<t_p; τ=t_p^∗ otherwise.



Here we use the direct adjoining approach in <cit.> to
obtain necessary conditions for the optimal solution u^∗(
t) and t_p^∗. The Hamiltonian H( v,u,λ) and
Lagrangian L( v,u,λ ,μ ,η) are defined as

    H( v,u,λ) =ρ _uu^2+ρ _t+λ
    _1v+λ _2u

and

    L( v,u,λ ,μ ,η) =   H( v,u,λ)
    +μ( u-u_max)  
       +η _1( v_min-v) +η _2( v-v_max) ,

respectively, where λ(t)=[λ_1(t)λ_2(t)]^T and
η(t)=[η_1(t)η_2(t)]^T,

    μ( t) ≥ 0, μ( t) [ u^∗( t) -u_max] =0,  
       η _1( t) ≥ 0,η _2( t) ≥ 0,
    
       η _1( t) [ v_min-v^∗( t) ]
    +η _2( t) [ v^∗( t) -v_max]
    =0.

Note that we did not include the constraint u( t) ≥ u_min
since we have already established that the optimal control u^∗(
t) ≥ 0 in the free terminal time optimal control problem in Lemma <ref>.
Let us temporarily assume that both ρ _t≠ 0 and ρ
_u≠ 0. According to Pontryagin's minimum principle, the optimal
control u^∗( t) must satisfy

    u^∗( t) =min_0≤ u( t) ≤ u_maxH( v^∗( t) ,u(t),λ( t) ) ,

which allows us to express u^∗( t) in terms of the
costate λ( t), resulting in

    u^∗( t) =min{ u_max,-λ _2(
    t) /2ρ _u},

with λ _2( t) ≤ 0 due to Lemma <ref>. The Lagrange multiplier μ( t) is such that

    . ∂ L^∗/∂ u| _u=u^∗(
    t) =2ρ _uu^∗( t) +λ _2(
    t) +μ( t) =0.

Since we can always find μ( t) ≥ 0 to make (<ref>) and (<ref>) hold under the minimum principle (<ref>),
(<ref>) and (<ref>) can be considered as redundant conditions.
For the costate λ _1( t), we have

    λ̇_1( t) =-∂ L^∗( t) /
    ∂ x=0,

which means λ _1(t)=λ _1 is a constant. The costate λ _2(
t) satisfies

    λ̇_2( t) =-∂ L^∗( t) /
    ∂ v=-λ _1+η _1( t) -η _2( t) .

First, let us use a proof by contradiction to show that if v^*( t)
=v_min, then t=t_0. Assume that v^*( t) =v_min for t≠
t_0. Then, we must have v^*( t) =v_min for all t∈[
t_0,t_p^∗]. This is because acceleration always precedes cruising at constant speed in the
optimal control profile. If not, the vehicle would travel a longer time for the same trip using the same amount of energy.
According to the system dynamics in (<ref>), u( t) =0 for all t∈[ t_0,t_p^∗].
Based on the minimum principle (<ref>), λ _2( t) =0
for all t∈[ t_0,t_p^∗]. From (<ref>), we know
that η _2( t) =0 for all t∈[
t_0,t_p^∗]. Since the terminal time t_p is
unspecified, there is a necessary transversality condition for t_p^∗ to be optimal, namely, H( v^*(t_p^∗),u^*(t_p^*),λ(t_p^∗)) =0, that
is,

    ρ _uu^*( t_p^∗) ^2+ρ _t+λ _1v^∗( t_p^∗) +λ _2( t_p^∗)
    u( t_p^∗) =0.

Since u^*( t_p^∗) =0, we must have λ _1<0
according to (<ref>). Then, we obtain λ̇_2( t) > 0
from (<ref>), which contradicts λ _2( t) =0 for t∈[ t_0,t_p^∗]. We have thus established that  if v^*( t)
=v_min, then t=t_0.
Next, we will show that λ _2( t) has no
discontinuities. Since it is impossible that v( t) =v_min for t≠ t_0, the costate trajectory λ _2( t) may jump
only at some time τ when v( τ) =v_max. The condition

    H^∗( τ ^-) =H^∗( τ ^+) ,

can be written as

    ρ _uu^∗( τ ^-) ^2+λ _2( τ
    ^-) u^∗( τ ^-)  
               =ρ _uu^∗( τ ^+) ^2+λ _2(
    τ ^+) u^∗( τ ^+) ,

where τ ^+ and τ ^- denote the left-hand side and the
right-hand side limits, respectively. We know from Lemma <ref>
that u^∗( t) =0, for t∈[ τ ,t_p^∗
]. Therefore, from (<ref>), we obtain

    ρ _uu^∗( τ ^-) ^2+λ _2( τ
    ^-) u^∗( τ ^-) =0.

According to (<ref>), we either have u^∗( τ ^-)
=-λ _2( τ ^-) /2ρ _u or u^∗( τ ^-) =u_max. When u^∗( τ ^-)
=-λ _2( τ ^-) /2ρ _u, (<ref>)
becomes

    -ρ _uu^∗( τ ^-) ^2=0,

which implies u^∗( τ ^-) =λ _2( τ
^-) =0. When u^∗( τ ^-) =u_max, (<ref>) becomes

    u_max=-λ _2( τ ^-) /ρ _u,

which contradicts the condition (<ref>) where u_max=-λ
_2( τ ^-) /2ρ _u. Therefore, only the case u^∗( τ ^-) =λ _2( τ ^-) =0 is
possible. In other words, the costate trajectory λ _2(
t) has no discontinuities, and the following jump conditions:

    λ _2( τ ^-) =λ _2( τ ^+)
    -ζ _1( τ) +ζ _2( τ) ,

and

    ζ _1( τ) ≥ 0,ζ _2( τ) ≥ 0,
    
       ζ _1( τ) [ v_min-v^∗( τ) 
    ] +ζ _2( τ) [ v^∗( τ)
    -v_max] =0,

are always satisfied with ζ _1( τ) =ζ _2(
τ) =0.
Next, we will show that λ _2( t_p^∗) =0. At the
terminal time t_p^*, the following transversality conditions hold:

    λ _2( t_p^∗ -)     =   γ _1. 
    ∂/∂ v[ v_min-v] | _v=v^∗( t_p^∗) 
          +γ _2. ∂/∂ v[ v-v_max]
    | _v=v^∗( t_p^∗)

that is,

    λ _2( t_p^*-) =-γ _1+γ _2,

where

    γ _1≥ 0,γ _2≥ 0,  
          γ _1[ v_min-v^∗( t_p^*) ] +γ
    _2[ v^∗( t_p^*) -v_max] =0.

If v_min<v^*( t_p^∗) <v_max, then γ
_1=γ _2=0, which leads to λ _2( t_p^∗)
=0 by the continuity of λ _2( t). When v^*(
t_p^∗) =v_max, then u^*( t_p^∗) =0,
which results in λ _2( t_p^∗) =0 according to (
<ref>).
Last, we will show that η _1( t) =0, and

    η _2( t) ={[                 0    for t∈[ t_0,τ);             -λ _1 for t∈[ τ ,t_p^∗] ]
    .

Since H( v,u,λ) is not an explicit function of time t, it follows that

    dH^∗( t) /dt=0,

that is,

    [ 2ρ _uu^∗( t) +λ _2(
    t) ] u̇^∗( t) +[ η _1( t) -η _2( t) ] u^∗(
    t) =0.

The first term [ 2ρ _uu^∗( t) +λ
_2( t) ] u̇^∗( t) is
always zero since when u^∗( t) ≠ u_max, 2ρ
_uu^∗( t) +λ _2^∗( t) =0
according to (<ref>), and when u^∗( t) =u_max, u̇^∗( t) =0. The condition (<ref>) can thus be
reduced to

    [ η _1( t) -η _2( t) 
    ] u^∗( t) =0.

When v_0=v_min, we have η _2( t_0) =0 from the fact that if v^*( t)
=v_min, then t=t_0 shown earlier and from (<ref>). Condition (<ref>) then implies

    η _1( t_0) u^∗( t_0) =0.

Since u^∗( t_0) >0, we can get η _1(
t_0) =0. For t≠ t_0, η _1( t) =0 since v(t)> v_min for t≠ t_0.
Therefore, for any v_0, we have η _1( t) =0.
It is easy to get from (<ref>) that η _2( t) =0
for t∈[ t_0,τ). For t∈[ τ ,t_p^∗
], η _2( t) =-λ _1 satisfies the
condition (<ref>) and λ̇_2( t) =0 in (<ref>
).
Based on the above observations, the differential equation (<ref>)
becomes

    λ̇_2( t) =-λ _1

for t∈[ t_0,τ). From (<ref>), we have -λ
_1=ρ _t/v^∗( t_p^∗) since u^∗( t_p^∗) =0. Solving the differential equation (<ref>), we have

    λ _2( t) =ρ _t/v^∗( t_p^∗) ( t-τ)

for t∈[ t_0 τ] . In the case that v^∗(
t_p^∗) < v_max, we simply let τ =t_p^∗ in (
<ref>). The proof is completed by substituting (<ref>) for λ _2( t) in (<ref>).


Recall that the theorem was proved under the assumption that ρ_t≠0
and ρ_u≠0. The special cases when either ρ_t=0 or ρ
_u=0 are considered in the following two corollaries.


Let x^∗(  t), v^∗(  t), u^∗(  t), t_p^∗ be an optimal solution to Problem
<ref> when ρ_t=0. Then, the optimal control u^∗(
t) satisfies

    u^∗(  t)  =0,

for all t∈ t_0,t_p^∗].



Let x^∗(  t), v^∗(  t), u^∗(  t), t_p^∗ be an optimal solution to Problem
<ref> when ρ_u=0. Then, the optimal control u^∗(
t) satisfies

    u^∗(  t)  ={[                u_max   for t∈[  t_0,τ)  ,;                    0 for t∈[  τ,t_p^∗]  , ].

where τ is the first time on the optimal path when v^∗
(τ)=v_max.


The proofs of the above two corollaries are straightforward by setting
ρ_t=0 and ρ_u=0, respectively, in (<ref>) in Theorem
<ref>.

Based on the vehicle dynamics (<ref>) and (<ref>), the initial
conditions x(  t_0)  =0 and v(  t_0)  =v_0,
and the terminal condition x^∗(  t_p^∗)  =l, the
optimal control law (<ref>) and the optimal time t_p^∗ can be
uniquely determined. In the following, we will classify the results into
different cases dependent on the values of the model parameters. In order to
do so, we define two functions:

    f(  v_0)        =l-v_max^2-v_0^2/2u_max
    -u_maxv_max^2ρ_u/ρ_t+1/6u_max^3v_max^2ρ_u^2/ρ_t^2,
    
    g(  v_0)        = l-2v_0√((  v_max-v_0)
    v_maxρ_u/ρ_t)
        -4/3(  v_max-v_0)  √((  v_max
    -v_0)  v_maxρ_u/ρ_t).

Depending on the signs of these two functions, the optimal solution consisting
of u^∗(  t) and t_p^∗ can be classified as shown
in Table <ref> with all detailed calculations provided in
Appendix <ref>. Referring to this table, the optimal control is
parameterized by the following function

    Φ(  t|a,b,c)  ={[      u_max  when t≤ a;     c(t-b) when a<t<b;          0  when t≥ b ].

The parameters shown in Table <ref> are defined as follows:

    t_1     =t_0+(  1-u_max^2ρ_u/ρ_t)
    v_max-v_0/u_max,t_3=t_0+v_1-v_0/u_max,
    
    t_2     =t_1+2u_maxv_maxρ_u/ρ_t,t_4
    =t_0+2√((  v_max-v_0)  v_maxρ_u/ρ_t
    ),

where

    v_1=√(2u_maxl+v_0^2/1+4u_max^2/1-ρ_u/ρ_tu_max^2ρ_u/ρ_t+8/3
    u_max^4/(  1-ρ_u/ρ_tu_max^2)
    ^2ρ_u^2/ρ_t^2)

and v_2 is the solution of the following equation:

    l=2/3(  v_0+2v_2)  √((  v_2-v_0)
    v_2ρ_u/ρ_t).

The parameters δ_1,δ_2,δ_3,δ_4 specifying in
Table <ref> the optimal time t_p^∗ when the vehicle arrives at
the traffic light  in each of the four possible cases are given below:

    δ_1     =t_2+f(  v_0)  /v_max,
    δ_2     =t_3+2u_maxv_1/1-ρ_u/ρ_tu_max^2ρ_u/ρ_t,
    δ_3     =t_4+g(v_0)/v_max,
    δ_4     =t_0+2√((  v_2-v_0)  v_2ρ_u
    /ρ_t).




This remark pertains to the underlying criteria for the optimal solution
classification in Table <ref>. The first row determines whether or not the
maximum acceleration u_max will be used for a given initial speed v_0. The optimality conditions tell us that the vehicle starts with the maximum
acceleration when the initial speed is relatively slow. The second row
determines if the road length l is large enough for a vehicle to reach its
maximum speed for a given initial speed v_0. In general, the optimal
control contains three phases: full acceleration, linearly decreasing
acceleration, and no acceleration. The first column specifies the case where
all three phases are included with switches defined by t_1, t_2. The
second column corresponds to the case of low initial speeds and short-length
roads. Under optimal control in this case, the vehicle starts with full
acceleration, but the road length is so short that the maximum speed cannot be
reached. Therefore, the optimal control contains only the first two phases.
The third column corresponds to the case of large initial speeds and
long-length roads. The vehicle starts with linearly decreasing acceleration,
and then proceeds with no acceleration when the speed reaches the limit
v_max. Here, the optimal control contains only the last two phases. The
last column corresponds to the case of large initial speeds and short-length
roads. Therefore, the vehicle uses only linearly decreasing acceleration.




 §.§ Fixed Terminal Time Optimal Control Problem




In this section, we consider the case where the optimal time t_p^∗
obtained in the free terminal time optimal control problem <ref> is within
some red light interval, that is,

    kT+DT<t_p^∗<kT+T,

In this case, the candidate optimal arrival time t_p^∗ in
Problem <ref> is either kT+DT or kT+T. Therefore, we can compare the
performance obtained under either one of these two terminal times, and select
the one with better performance to determine the optimal arrival time for
Problem <ref>. In both cases, the travel time is now fixed, hence the only
objective is to minimize the energy consumption. Thus, we have the following
problem formulation:


Fixed Terminal Time Optimal Control Problem

    min_u(  t)  ∫_t_0^t_pu^2(  t)
    dt

subject to

    (<ref>)  and  (<ref>)
        x(  t_p)  =l
        t_p =kT+DT or kT+T
        v_min≤ v(  t)  ≤ v_max
        u_min≤ u(  t)  ≤ u_max






  §.§.§ Arrival Time t_p=kT+DT


In this case, it is clear that that the vehicle must use less time than the
one specified by t_p^∗ in Problem <ref> and higher acceleration.
Define a function

    h(  v_0)  ={[                 v_0t_p+1/2u_maxt_p^2-l                for t_p≤v_max-v_0/u_max; v_maxt_p-1/2(  v_max-v_0)  ^2/u_max
    -l                for t_p>v_max-v_0/u_max ].

Observe that the terminal time t_p=kT+DT is possible if and only if
h(  v_0)  ≥0. The main result for this case is given in the
following theorem.


Let x^∗(  t), v^∗(  t), u^∗(  t) be an optimal solution to Problem <ref> with
t_p=kT+DT. Then, the optimal control u^∗(  t)
satisfies

    u^∗(  t)  =min_0≤ u(  t)  ≤ u_max
    u^2+u^∗(  t_0)  ^2(  t-τ)  u/v_0-v^∗(  t_p)  +(  τ-t_0)  u^∗(  t_0)  ,

where τ is the first time on the optimal path when v(  τ)
=v_max if τ<t_p; τ=t_p^∗ otherwise.



Similar to the proof of Theorem <ref>, we will use the direct adjoining approach <cit.> to solve the fixed terminal time optimal control problem.
The Hamiltonian H( v,u,λ) and
Lagrangian L( v,u,λ ,μ ,η) are defined as

    H(u,v,λ)=u^2+λ _1v+λ _2u,

and

    L(u,v,λ,μ,η)=    H+μ( u-u_max) 
       +η _1( v_min-v) +η
    _2( v-v_max) ,

respectively, where λ(t)=[λ_1(t)λ_2(t)]^T and
η(t)=[η_1(t)η_2(t)]^T, and 

    μ( t) ≥ 0,μ( t) [ u^∗(
    t) -u_max] =0,
       η _1( t) ≥ 0,η _2( t) ≥ 0,
       η
    _1( t) [ v_min-v^∗( t) ] +η
    _2( t) [ v^∗( t) -v_max] =0.

Note that, as in the the proof of Theorem <ref>, u^∗( t) ≥ 0 for all t,
therefore, the constraint u( t) ≥ u_min is relaxed, and

    u^∗( t) =min_0≤ u( t) ≤ u_maxu^2+λ _2u.

which implies that

    u^∗( t) =min{ u_max,-λ _2(
    t) /2},

and λ _2( t) ≤ 0.
From the proof of Theorem <ref>, we know that μ( t) is a redundant
variable, and λ _1 is a constant. Let us first assume that

    l>v_mint_p.

Note that the case of l=v_mint_p cannot occur when t_p=kT+DT (however, it may occur when t_p=kT+T and this case will be discussed later).
Again, we can prove the fact that v( t) =v_min happens only at t=t_0 but without using the transversality condition as we did in the free terminal time optimal control problem.
The property that λ _2( t) has no discontinuities also still holds. The costate λ_2(t) satisfies

    λ̇_2( t) =-λ _1+η _1(
    t) -η _2( t) .

Similarly, we
can show that η _1( t) =0, and (<ref>) reduces to

    λ̇_2( t) =-λ _1

for t∈[ t_0,τ) and λ _2( τ)
=0. By solving the differential equation (<ref>), we get

    λ _2( t) =-λ _1( t-τ) .

Again since the Hamiltonian is not an explicit function of time, by the condition

    H( t_0) =H( t_p) ,

we have

    u^∗( t_0) ^2+λ _1v^∗( t_0)
    -λ _1( t_0-τ) u^∗( t_0) =λ
    _1v^∗( t_p)

where the fact that λ_2(t_p)=u^*(t_p)=0 has been used. From (<ref>), we can obtain

    λ _1=u^∗( t_0) ^2/v^∗(
    t_p) +( t_0-τ) u^∗( t_p)
    -v^∗( t_0)

For t∈ [τ, t_p], we can just let η_2(t)=-λ_1.
If v^*(t_p)<v_max, then τ=t_p in (<ref>).
The proof is completed by substituting λ _1 in (<ref>) into (<ref>), and then λ _2 into
(<ref>).


Given the terminal time kT+DT and the road length l, the value of v_0
can be classified into one of five cases as shown in Table <ref>. Note
that if Case i is infeasible for some v_0 and the given parameters, we
can treat J_i^u as infinity. The performances associated with each case in Table <ref> as
well as the detailed calculations are given in Appendix <ref>. After
obtaining the performance for each cases with t_p=kT+DT, we select the one
with the smallest energy consumption, that is,

    J_u^kT+DT=min{  J_1^u,… J_5^u}  ,

with the corresponding optimal acceleration profile.



  §.§.§ Arrival Time t_p=kT+T


In this case, the vehicle must use less acceleration than in the free terminal
time case. Depending on the initial speed v_0, there are three cases to
consider. First, if

    l=v_0(  kT+T-t_0)  ,

then the vehicle can cruise through the intersection with the constant speed
v_0 without any acceleration (Case VI in Table <ref>). The energy
consumption in this case is

    J_6^u=0.

If, on the other hand,

    l>v_0(  kT+T-t_0)  ,

then the problem can be solved using the result of the case t_p=kT+DT
analyzed above. Finally, if

    l<v_0(  kT+T-t_0)  ,

then the vehicle must decelerate to reach the traffic light while in its green
state. Therefore, the control input is only subject to the constraint

    u_min≤ u(  t)  ≤0.

The main result in this case is given in the following theorem.


Let x^∗(  t), v^∗(  t), u^∗(  t) be an optimal solution to Problem <ref> with
t_p=KT+T. Then, the optimal solution u^∗(  t)
satisfies

    u^∗(  t)  =min_u_min≤ u(  t)  ≤
    0u^2+u^∗(  t_0)  ^2(  τ-t)
    u/v^∗(  t_p)  -v_0-(  τ-t_0)  u^∗(  t_0)  ,

where τ is the first time on the optimal path when v(  τ)
=v_max if τ<t_p; τ=t_p^∗ otherwise.



The Hamiltonian H(  u,v,λ) and the Lagrangian L(
u,v,λ,μ,η) are defined as

    H(  u,v,λ)  =u^2+λ_1v+λ_2u

and

    L(  u,v,λ,μ,η)        =H(  u,v,λ)
    +μ(  u_min-u)  
        +η_1(  v_min-v)  +η_2(  v-v_max)
    ,

respectively, where λ(t)=[  λ_1(t),λ_2(t)]
^T, η(t)=[  η_1(t),η_2(t)]  ^T, and

    μ(  t)  ≥0,μ(  t)  [  u_min-u^∗(  t)  ]  =0,
       η_1(  t)  ≥0,η_2(  t)  ≥0,
       η_1(  t)  [  v_min-v^∗(  t)
    ]  +η_2(  t)  [  v^∗(  t)
    -v_max]  =0.

As before, we do not include the constraint u(  t)  ≤ u_max
since we have already established in Lemma <ref> that u^∗(
t)  ≤0.

According to Pontryagin's minimum principle, the optimal control u^∗(  t) must satisfy

    u^∗(  t)  =min_u_min≤ u(  t)  ≤
    0H(  v^∗(  t)  ,u^∗(  t)  ,λ(  t)  )

which allows us to express u^∗(  t) in terms of the
costate λ(  t), that is,

    u^∗(  t)  =max{  u_min,-λ_2(
    t)  /2}

with λ_2(  t)  ≥0. The Lagrange multiplier μ(
t) is redundant as before. The costate λ_1 is a constant.
The co-state λ_2(  t) satisfies

    λ̇_2(  t)  =-∂ L^∗/∂
    v=-λ_1+η_1^∗(  t)  -η_2^∗(
    t)  .



First, it is easy to see that v_0≠ v_min. Let τ be the first
time that v(  τ)  =v_min, then

    u^∗(  t)  =0

for t≥τ. Again, since the Hamiltonian is not an explicit function of
time, by the condition

    H^∗(  τ^-)  =H^∗(  τ^+)  ,

we have

    u^∗(  τ^-)  ^2+λ_2(  τ^-)
    u^∗(  τ^-)  =0.

According to (<ref>), we either have u^∗(  τ^-)
=u_min or u^∗(  τ^-)  =-λ_2(
τ^-)  /2. When u^∗(  τ^-)  =u_min, the
above equality becomes

    u_min^2+λ_2(  τ^-)  u_min=0,

which contradicts the minimum principle (<ref>); when u^∗(
τ^-)  =-λ_2(  τ^-)  /2,
(<ref>) becomes

    u^2(  τ^-)  -2u^2(  τ^-)  =0.

Therefore, only λ_2(  τ^-)  =u^∗(  τ
^-)  =0 is possible, that is to say, λ_2 and u^∗
have no discontinuities at τ.

At the terminal time t_p, the following costate boundary condition holds:

    λ_2(  t_p^∗-)        =γ_1.  ∂/∂ v[  v_min-v]  | _v=v^∗(  t_p^∗)  
        +γ_2.  ∂/∂ v[  v-v_max]
    | _v=v^∗(  t_p^∗)

that is,

    λ_2(  t_p^-)  =-γ_1+γ_2

and

    γ_1≥0,γ_2≥0,γ_1[  v_min-v^∗(  t_p)  ]  +γ_2[  v^∗(
    t_p)  -v_max]  =0.

At t_p, we know that v^∗(  t_p)  ≠ v_max. Thus,
γ_2=0. Likewise, it is easy to obtain γ_1=0. Therefore, we
have

    λ_2(  t_p)  =0.



Since the Hamiltonian is not an explicit function of time, the condition

    dH^∗(  t)  /dt=0,

implies that

    [  2u^∗(  t)  +λ_2(  t)  ]
    u̇^∗(  t)  +[  η_1(  t)  -η
    _2(  t)  ]  u^∗(  t)  =0.

Since the first term is always zero as before, the above condition becomes

    [  η_1(  t)  -η_2(  t)  ]  u^∗(  t)  =0.

When v_0=v_max, we have η_1(  t_0)  =0, that is

    η_2(  t_0)  u^∗(  t_0)  =0.

Recall that

    λ̇_2(  t)  =-∂ L^∗/∂
    v=-λ_1+η_1(  t)  -η_2(  t)  .

Since λ_1>0, then λ_2(  t) must decrease.
Therefore, u^∗(  t_0)  <0, and η_2(  t)
=0 for all t. For t∈[  t_0,τ), η_1^∗(  t)  =0. Therefore,

    λ̇_2(  t)  =-λ_1

for t∈[  t_0,τ). For t∈[  τ,t_p)  ,

    λ̇_2(  t)  =-λ_1+η_1^∗(
    t)  =0.

Solving the above differential equation, we obtain

    λ_2(  t)  =λ_1(  τ-t)  ,

for t∈ t_0,τ). By the condition

    H(  t_0)  =H(  t_p)  ,

we have

    u^∗(  t_0)  ^2+λ_1v_0+λ_1(
    τ-t_0)  u^∗(  t_0)  =λ_1v^∗(
    t_p)  ,

that is,

    λ_1=u^∗(  t_0)  ^2/v^∗(
    t_p)  -v_0-(  τ-t_0)  u^∗(  t_0)
    .

The proof is completed by substituting λ_1 into (<ref>) and
then λ_2 into (<ref>).


The classification of all possible solutions with t_p=kT+T is
shown in Table <ref>. The performances associated with each case in this
table as well as the detailed calculations are given in Appendix <ref>.
After obtaining the energy consumption from J_6^u through J_10^u,
we can select

    J_u^kT+T=min{  J_6^u,…,J_10^u},

where J_i^u can be treated as infinity if Case i is infeasible.
Finally, we can compare the two performances obtained, that is,

    J^kT+DT    =ρ_t(  kT+DT)  +ρ_uJ_u^kT+DT
    
    J^kT+T    =ρ_t(  kT+T)  +ρ_uJ_u^kT+T

and determine the optimal performance to be the one with a smaller value.



§ NUMERICAL EXAMPLES


 We have simulated the system defined by the vehicle dynamics
(<ref>) and (<ref>) and associated constraints and optimal control
problem parameters with values given as follows. The minimum and maximum
speeds are 2.78 m/s and 22.22 m/s. The maximum acceleration and
deceleration are set to 2.5 m/s^2 and -2.9 m/s^2, respectively. The
weights in (<ref>) are set using ρ=0.9549, that is, ρ_t=0.0133,
and ρ_u=9.2798×10^-4. In this case, the values

    1-u_max^2ρ_u/ρ_t=0.5630,

and

    v_m+v_M/2v_M=0.5626,

are almost the same. Thus, if we randomly generate the initial speed v_0
from a uniform distribution on the interval [v_min,v_max], different
initial speeds fall roughly equally into the two different cases in the first
row in Table <ref>. The total cycle time for the traffic light is 60 s
with different patterns. We first test the optimal controller on a road of
length 200 m. Figure <ref> depicts the case when the initial speed is
relatively slow. The vehicle starts with full acceleration and, when the speed
limit is reached, it switches to no acceleration. The vehicle arrives at the
traffic light within the first green light cycle. When the initial speed is relatively large, the vehicle should not
start with full acceleration. This is the case shown in Fig. <ref>.


In the last two figures, the traffic light starts at a green state. The
following two figures show the case when the traffic light starts at a red
state. It can be inferred from the first two plots that the arrival time
obtained from the free terminal time optimal control problem should be within
the red light interval. Figure <ref> shows a case when the initial speed
is slow. The optimal arrival time obtained from the free terminal time optimal
control is 12.1860 seconds. However, the traffic light in the first 40 seconds
is red. The optimal time for the vehicle to arrive at the intersection is 40
seconds. The vehicle has adequate time to accelerate, therefore, it does not
start with full acceleration, and it is unnecessary to accelerate to the
maximum speed. 

Figure <ref> exhibits a different traffic light pattern, where the
traffic light in the first 20 seconds is red. Due to a relatively large
initial speed, the vehicle has to decelerate to cross the intersection when
the traffic light is green. 









In the following, we test the optimal controller on a road of length 2203 m.
Due to this length, the optimal arrival time usually does not fall within the
first green light cycle, and sometimes it is impossible for the vehicle to
arrive at the traffic light within this cycle. For the case in Fig. <ref>
, the optimal arrival time calculated from the free terminal time optimal
control problem is 102.3476 seconds. Unfortunately, this arrival time belongs
to a red light interval. Therefore, full acceleration is used to reach the
speed limit and cross the intersection at 100 seconds when the traffic light
is green. 

Figure <ref> shows the case when the vehicle has a relatively fast
initial speed compared to Fig. <ref>. Therefore, the vehicle does not
start with full acceleration to reach the speed limit and catch the green
light at 100 seconds. 

For the last case in Fig. <ref>, the initial speed is very large. The
best option is to decelerate the vehicle to cross the intersection at 120
seconds when the traffic light is green. 



Exploring the time-energy tradeoff. In order to compare the
performance between (i) autonomous vehicles under the optimal control
developed and (ii) a human driver, we arbitrarily define the following rules
as the driving behavior of a human driver:



  * Full acceleration when the traffic light is green;


  * No acceleration/deceleration when the traffic light is red.


We calculate the performance of both autonomous vehicles and human drivers for
the different scenarios encountered from Fig. <ref> to Fig. <ref>,
and summarize the results in Table <ref>. The improvement is more than
10% for the case in Fig. <ref>. The performance improvement is
calculated as the performance difference between the human driver and
autonomous vehicle divided by the performance of the human driver. It is
particularly challenging for a human driver to make a decision when he/she
faces a steady red traffic light. Also note that the weighting parameter ρ is chosen to be in
favor of travel time rather than energy efficiency. Therefore, the performance
improvement would be larger when we decrease the weighting parameter ρ,
which provides a trade-off between energy consumption and travel time.

Figure <ref> shows the travel time and the energy consumption when we
vary the parameter ρ from 0 to 1. The initial speed is chosen as
v_0=18.6182. By exploring the trade-off curve, one may select am
appropriate weight parameter ρ depending on a particular application of
interest. For instance, if energy efficiency is a major concern,
Fig. <ref> suggests to not select a large value for ρ since the
energy consumption grows rapidly as ρ approaches 1. On the other hand,
a small ρ is likely not a better option, since we can see that energy
consumption does not significantly increase with ρ increasing as long as
ρ<0.7 (approximately). In fact, when ρ increases from 0 to 0.7, the
travel time is significantly reduced by 42.84% whereas the energy
consumption increases by only 4.85%. It is noteworthy that both curves show
different trends around the circled area shown in Fig. <ref>: this is
mainly because the optimal control has included the full acceleration part
when the parameter ρ is large. 



§ CONCLUSIONS


 This paper provided the optimal acceleration/deceleration profile
for autonomous vehicles approaching an intersection based on the traffic light
information, which could be obtained from an intelligent infrastructure via
V2I communication. The solution for the above problem had the key feature of
avoiding idling at a red light. Comparing with similar problems solved by
numerical calculations, we provided a real-time analytical solution. The
proposed algorithm offered better efficiency in terms of travel time and
energy consumption, which has been verified through extensive simulations. The
simulation results showed that the algorithm achieved substantial performance
improvement compared with vehicles with heuristic human driver behavior.

There are a few avenues available for extending this work. In particular,
there is a need to consider a practical scenario where interferences from
other road users present. A possible way of doing this is to predict the
driving behavior of vehicles ahead. It is also desirable to develop a more
general algorithm by taking into account traffic light information at multiple intersections.






§ PROOF OF LEMMA <REF>


 Let us first consider the case of constant control input. By
solving the differential equation (<ref>), it is straightforward to get
the expression for v(  t_1). As a byproduct, we have
v(  t)  =v_0+(  t-t_0)  u. By solving the
differential equation (<ref>), it follows that

    x(  t_1)        =x_0+∫_t_0^t_1[  v_0+(
    t-t_0)  u]  dt
        =x_0+v_0(  t_1-t_0)  +1/2u(  t_1
    -t_0)  ^2.

The energy consumption J^u is then easy to obtain.

Next, let us consider the case that u(  t)  =u(
t_1-t) for t∈[  t_0,t_1]. Solving the
differential equation (<ref>), we obtain

    v(  t_1)        =v_0+∫_t_0^t_1[  u(
    t_1-t)  ]  dt
        =v_0+1/2u(  t_1-t_0)  ^2.

As a byproduct, we have v(  t)  =v_0+1/2u(
t-t_0)  ^2. Solving the differential equation (<ref>) yields

    x(  t_1)        =x_0+∫_t_0^t_1[  v_0+1/2u(  t-t_0)  ^2]  dt
        =x_0+v_0(  t_1-t_0)  +1/6u(  t_1
    -t_0)  ^3.

The energy consumption is then calculated as

    J^u=∫_t_0^t_1u^2(  t_1-t)  ^2dt=1/3
    u^2(  t_1-t_0)  ^3.





§ PROOF OF LEMMA <REF>


 We will prove the result by a contradiction argument. Let us assume
that u^∗(  t) and t_p^∗ are the optimal control
and the optimal arrival time of Problem <ref>, respectively. In addition,
we assume that there exists an interval [  t_1,t_2] such
that u^∗(t)<0. Next, we construct another control input u(
t) such that u(  t)  =u^∗(  t) for
t<t_1, and u(  t)  =0 for t∈[  t_1,t_2].
It is then straightforward to get

    v^∗(t_1)=v(t_1), and x^∗(t_1)=x(t_1).

We now invoke the comparison lemma <cit.> which compares
the solutions of the differential inequality v̇(t)≤ f(t,v) with the
solution of the differential equation u̇(t)=f(t,u) and asserts that If
v_0≤ u_0, then v(t)≤ u(t). By applying the comparison principle
to the dynamics of v(t), it follows that

    v^∗(t)<v(t)

for t>t_1 until v^∗(t)=v_max. By applying the comparison
principle again to the dynamics of x(t), it follows that x^∗(t)<x(t)
for t>t_1. Then, according to the terminal condition

    x^∗(t_p)<x(t_p)=l,

we conclude that t_p^∗>t_p, therefore we have

    t_p-t_0<t_p^∗-t_0.

Let τ be the time when v(τ)=v_max, and we assume that τ
>t_2 without loss of generality. The remaining control input of u(t) is
thus constructed as

    u(  t)  ={[               u^∗(  t) for t_2≤ t<min{τ
    ,t_p};                      0    for t≥min{τ,t_p}  . ].

By using the inequality (<ref>) at t=τ we have

    v^∗(τ)<v(τ)=v_max

Recalling that u^∗(t)<0, u(  t)  =0 for t∈[
t_1,t_2], it follows that

    ∫_t_0^t_pu^2(  t)  dt=    ∫_t_0^t_1
    u^2(  t)  dt+∫_t_2^min{τ,t_p}u^2(  t)  dt
    
    <    ∫_t_0^t_1u^∗(  t)  ^2dt+∫_t_1^t_2
    u^∗(  t)  ^2dt
         +∫_t_2^min{τ,t_p}u^∗(  t)
    ^2dt
    ≤   ∫_t_0^t_p^∗u^∗(  t)  ^2dt.

The above inequality together with (<ref>) contradicts the optimality of
u^∗(t) and t_p^∗ in (<ref>) and completes the proof by
contradiction. Therefore, we conclude tha u^∗(t)≥0 for all
t∈ t_0,t_p^∗].



§ CALCULATIONS FOR TABLE <REF>


 Let us assume that ρ_u≠0, and ρ_t≠0.



 §.§ Case I: v^*(  t_p^∗)  =v_max


Let us first find the time duration δ such that u(  t)
decreases from u_max to 0 while the speed increases from v to the
maximum speed v_max under the optimal control

    u̇(  t)  =-ρ_t/2ρ_uv_max.

Integrating (<ref>) on both sides yields

    0=u_max-ρ_t/2ρ_uv_maxδ

which can be simplified as

    δ=2u_maxv_maxρ_u/ρ_t.

According to Lemma <ref>, we know that

    v_max = v+u_max^2v_maxρ_u/ρ_t,

which can be written as

    v=(  1-u_max^2ρ_u/ρ_t)  v_max

with the assumption that

    (  1-u_max^2ρ_u/ρ_t)  v_max≥ v_min.

For the same amount of time, the distance that the vehicle travels is

    d =2u_maxv_max^2ρ_u/ρ_t-2/3u_max
    ^3v_max^2ρ_u^2/ρ_t^2.



According to Theorem <ref>, the optimal control can be parameterized in
terms of the speed v(t) as

    {[                                u^∗(  t)  =u_max          if v(  t)  ≤(
    1-u_max^2ρ_u/ρ_t)  v_max;                      u̇^∗(  t)  =-ρ_t/2ρ_uv_max if (  1-u_max^2ρ_u/ρ_t)  v_max≤
    v(  t)  ≤ v_max;                                    u^∗(  t)  =0                               if v(  t)  =v_max ].



There are different cases depending on the relationship between the initial
speed v_0 and the road length l. Remind that the analysis is under the
assumption that

    (  1-u_max^2ρ_u/ρ_t)  v_max≥ v_min.





  §.§.§ Case I.1 v_0≤(  1-u_max^2ρ_u/ρ_t)  v_max


(The first column in Table <ref>). In this case, the vehicle will first
accelerate to v(  t_1)  =(  1-u_max^2ρ_u
/ρ_t)  v_max using the maximum acceleration u_max. Then
it will travel a distance d to reach v_max. At time t_1, we have

    x(  t_1) =v_0(  t_1-t_0)  +1/2(
    t_1-t_0)  ^2u_max.

It is easy to figure out that

    t_1-t_0=(  1-u_max^2ρ_u/ρ_t)
    v_max-v_0/u_max.

To achieve the maximum speed v_max, the road length l must satisfy

    l     ≥ x(t_1)+d
        =v_max^2-v_0^2/2u_max+u_maxv_max^2ρ
    _u/ρ_t-1/6u_max^3v_max^2ρ_u^2/ρ_t^2.





  §.§.§ Case I.2 (  1-u_max^2ρ_u/ρ_t
)  v_max< v_0≤ v_max


(The third column in Table <ref>). In this case, the vehicle will not
start with full acceleration, and we have

    u^∗(  t)  =ρ_t/2ρ_uτ-t/v_max,

where τ is the time when v(  τ)  =v_max.

According to Lemma <ref>, we can obtain

    x(  τ)       =v_0(  τ-t_0)  +ρ_t
    /6ρ_uv_max(  τ-t_0)  ^3,

and

    v_max=v_0+ρ_t/4ρ_uv_max(  τ-t_0)
    ^2.



We can calculate from (<ref>) to get

    τ-t_0=2√((  v_max-v_0)  v_maxρ_u/ρ_t).

By using (<ref>), a necessary condition for v(  t) to reach
the maximum speed v_max is

    l     ≥2v_0√((  v_max-v_0)  v_maxρ_u
    /ρ_t)
        +4/3(  v_max-v_0)  √((  v_max
    -v_0)  v_maxρ_u/ρ_t).























 §.§ Case II: v^*(  t_p^∗)  <v_max




  §.§.§ Case II.1 v_0<(  1-u_max^2ρ_u/ρ
_t)  v_max


(The second column in Table <ref>). In this case, the road length

    l<v_max^2-v_0^2/2u_max+u_maxv_max^2ρ_u
    /ρ_t-1/6u_max^3v_max^2ρ_u^2/ρ
    _t^2

is not long enough for the vehicle to reach the maximum speed. Let us assume
that the speed when the acceleration starts to decrease at time t_1 is v. According to Lemma <ref>, it takes the time

    t _1-t_0=v-v_0/u_max

for the vehicle to reach the speed v by using the maximum acceleration, and

    x(  t_1) = v^2-v_0^2/2u_max.

The speed v increases to v^∗(  t_p^∗) by using a
linearly decreasing optimal control from u_max to 0. It is easy to get
that

    u̇(  t)  =-ρ_t/2ρ_uv^∗(
    t_p^∗)  .

Therefore, the time for u_max to decrease to 0 is

    δ_2=2u_maxv^∗(  t_p^∗)  ρ_u/ρ_t.

According to Lemma <ref>, we can obtain

    v^∗(  t_p^∗)       =v+u_max^2v^∗(
    t_p^∗)  ρ_u/ρ_t,

which is

    v^∗(  t_p^∗)  =v/1-ρ_u/ρ_t
    u_max^2.



By the road length constraint, we are able to calculate v from the equality

    l= v^2-v_0^2/2u_max+v^22u_max/1-ρ_u
    /ρ_tu_max^2ρ_u/ρ_t+4/3v^2ρ_u^2/ρ_t^2u_max^3/(  1-ρ_u/ρ_tu_max^2)  ^2,

that is,

    v=√(2u_maxl+v_0^2/1+4u_max^2/1-ρ_u
    /ρ_tu_max^2ρ_u/ρ_t+8/3u_max^4/(  1-ρ_u/ρ_tu_max^2)  ^2ρ_u^2/ρ_t^2)

















  §.§.§ Case II.2 v_0>(  1-u_max^2ρ_u/ρ
_t)  v_max


(The fourth column in Table <ref>). In this case, the road length

    l<     2v_0√((  v_max-v_0)  v_maxρ_u/ρ_t)
         +4/3(  v_max-v_0)  √((  v_max
    -v_0)  v_maxρ_u/ρ_t)

is not large enough for the vehicle to reach the speed limit, and the maximum
acceleration u_max will not be used either. According to Theorem <ref>
, the optimal control can be parameterized as

    u^∗(  t)  =ρ_t(  t_p^∗-t)
    /2ρ_uv^∗(  t_p^∗)  .

According to Lemma <ref>, we have

    v^∗(  t_p^∗)  =v_0+ρ_t(  t_p^∗-t_0)  ^2/4ρ_uv^∗(  t_p^∗)
    ,

and

    l=v_0(  t_p^∗-t_0)  +ρ_t/6ρ_uv^∗(  t_p^∗)  (  t_p^∗-t_0)
    ^3.

By solving the equation (<ref>), we can obtain

    v^*(t_p^*)=v_0+√(v_0^2+ρ_t/ρ_u(
    t_p^∗-t_0)  ^2)/2.

By substituting for v^*(t_p^*), we are able to obtain t_p^* from
(<ref>).



§ DETAILED CALCULATIONS FOR TABLE <REF>




There are different cases depending on the initial speed v_0, the time
duration kT+DT, and the road length l.



 §.§ Case I: u^*_0=u_max and u̇^*(  t)
=0


This case corresponds to h(v_0)=0. The vehicle accelerates fully until it
arrives at the traffic light or the maximum speed is reached. According to
Lemma 1, the vehicle reaches the maximum speed by spending time

    δ=v_max-v_0/u_max.

Depending on the values of kT+DT and δ, we have different energy
consumptions

    J_1^u={[         u_max(  v_max-v_0)  if v_max-v_0
    /u_max<kT+DT;       u_max^2(  kT+DT-t_0) if v_max-v_0
    /u_max≥ kT+DT ].



For all other cases, h(  v_0)  >0, and u̇(
t)  ≠0 for some t.



 §.§ Case II: u^∗(  t_0)  =u_max, and v^∗(  t_p)  =v_max


The time t_1 is when the acceleration starts to decrease, that is,

    1/2u_max^2(  τ-t_1)  /v_0-v_max+(  τ-t_0)  u_max=u_max.

From (<ref>), we can obtain

    τ=2v_max-v_0/u_max-t_1+2t_0.

According to Lemma <ref>,

    v(  t_1)       =v_0+u_max(  t_1-t_0) 
    
    x(  t_1)       =v_0(  t_1-t_0)  +1/2u_max(  t_1-t_0)  ^2

and

    x(  τ)  =x(  t_1)  +v(  t_1)  (
    τ-t_1)  +1/6u_max^2(  τ-t_1)
    ^3/v_0-v_max+(  τ-t_0)  u_max.

Therefore, we have

    l=(  t_p-τ)  v_max+x(  τ)  .

We can solve the equation (<ref>) to get t_1. The energy consumption
can be expressed as

    J_2^u=(  t_1-t_0)  u_max^2+1/12u_max^4(  τ-t_1)  ^3/[  v_0-v_max+(
    τ-t_0)  u_max]  ^2.





 §.§ Case III: u^∗(  t_0)  =u_max, and v^∗(  t_p)  <v_max


In this case, τ=t_p. First, we need to find the time t_1 such that
the acceleration starts to decrease, that is,

    1/2u_max^2(  t_p-t_1)  /v_0-v^∗(  t_p)  +(  t_p-t_0)  u_max=u_max.

By solving the above equation for v^∗(  t_p), we can
obtain

    v^∗(  t_p)  =v_0+t_p+t_1-2t_0/2u_max.



According to Lemma <ref>, the speed and the distance of the vehicle at
t_1 are

    v^*(  t_1)  =v_0+(  t_1-t_0)  u_max,

and

    x^*(  t_1)  =v_0(  t_1-t_0)  +1/2u_max(  t_1-t_0)  ^2,

respectively. From the road length constraint

    l=x^*(  t_1)  +v^*(  t_1)  (  t_p
    -t_1)  +1/3u_max(  t_p-t_1) ^2
    ,

we are able to calculate t_1. The energy consumption for this case can be
expressed as

    J_3^u=u_max^2(  t_p+2t_1-3t_0)  /3.





 §.§ Case IV u_0^∗<u_max and v^∗(  t_p)
=v_max


In this case, the vehicle reaches the maximum speed at τ. According to
Lemma <ref>, we have

    v_max=v_0+1/4u^∗(  t_0)  ^2(
    τ-t_0)  ^2/v_0-v_max+(  τ-t_0)  u^∗(  t_0)  ,

Solving the above equation for u^∗(  t_0) yields

    u^∗(  t_0)  =2v_max-v_0/τ-t_0.

With the expression of u^∗(  t_0) and Lemma <ref>, we
can obtain

    l=1/3(  v_0+2v_max)  (  τ-t_0)
    +(  t_p-τ)  v_max.

We can calculate τ from (<ref>) as

    τ=3l+(  2v_max+v_0)  t_0-3t_pv_max/v_0-v_max.

The energy consumption in this case is expressed as

    J_4^u=4/3(  v_max-v_0)  ^2/τ-t_0
    .





 §.§ Case V: u_0^∗<u_max and v^∗(  t_p)
<v_max


In this case, τ=t_f. According to Lemma <ref>, the final speed is

    v^∗(  t_p)  =v_0+1/4u^∗(
    t_0)  ^2(  t_p-t_0)  ^2/v_0-v^∗(
    t_p)  +(  t_p-t_0)  u^∗(  t_0)
    ,

From (<ref>), we can get

    u^∗(  t_0)  =2v^∗(  t_p)  -v_0
    /t_p-t_0.

Using the expression of u^∗(  t_0) and Lemma <ref>,
we can obtain

    l=v_0(  t_p-t_0)  +2/3(  v^∗(
    t_p)  -v_0)  (  t_p-t_0)  .

Solving the equation (<ref>), we have

    v^∗(  t_p)  =3/2l-v_0(  t_p
    -t_0)  /t_p-t_0+v_0.

The energy consumption in this case can be expressed as

    J_5^u=3[  l-v_0(  t_p-t_0)  ]  ^2
    /(  t_p-t_0)  ^3.





§ DETAILED CALCULATIONS FOR TABLE <REF>






 §.§ Case VII: u(  t_0)  =u_min and v(
t_p)  =v_min.


In this case, the vehicle starts with full deceleration u_min, and then
at time t_1, the deceleration linearly increases until it reaches zero at
t=τ. Therefore, at time t=t_1, we have

    u_min=1/2u_min^2(  τ-t_1)  /v_0+(  τ-t_0)  u_min-v_min,

that is,

    v_0-v_min=2t_0-τ-t_1/2u_min.



According to Lemma <ref>, the speed and travel distance of the vehicle at
time t_1 are

    v(  t_1)  =v_0+u_min(  t_1-t_0)  ,


and

    x(  t_1)  =v_0(  t_1-t_0)  +1/2u_min(  t_1-t_0)  ^2,

respectively. At time τ, we have

    x(  τ)  =x(  t_1)  +v(  t_1)  (
    τ-t_1)  +1/6u_min^2(  τ-t_1)
    ^3/v_0+(  τ-t_0)  u_min-v_min

To satisfy the road length constraint, we must have

    l=x(  τ)  +(  kT+T-τ)  v_min.

We can solve (<ref>) to obtain

    τ=2t_0-t_1+2v_min-v_0/u_min

and (<ref>) to get t_1. The energy consumption in this case can be
expressed as

    J_7^u=(  t_1-t_0)  u_min^2+1/12u_min^4(  τ-t_1)  ^3/[  v_0+(  τ-t_0)
    u_min-v_min]  ^2.





 §.§ Case VIII: u^∗(  t_0)  =u_min and v^∗(  t_p)  >v_min.


In this case, τ=t_f. The vehicle starts with full deceleration
u_min, and at time t_1, the deceleration starts to increase.
Similarly, we have

    v_0-v^∗(  t_p)  =2t_0-t_p-t_1/2u_min.

According to Lemma <ref>, we know that

    v^∗(  t_1)       =v_0+u_min(  t_1-t_0) ,
    
    x^∗(  t_1)       =v_0(  t_1-t_0)  +1/2u_min(  t_1-t_0)  ^2.

Solving (<ref>), we can get

    v^∗(  t_p)  =v_0+t_1+t_p-2t_0/2u_min.

Using the expression of v^∗(  t_p), we can obtain
t_1 by solving the following equation

    l=x^∗(  t_1)  +v^∗(  t_1)  (
    t_p-t_1)  +1/3u_min(  t_p-t_1)
    ^2.



The energy consumption in this case can be expressed as

    J_8^u=u_min^2(  t_p+2t_1-3t_0)  /3.





 §.§ Case IX: u^∗(  t_0)  <u_min, and v^∗(  t_p)  =v_min.


In this case, the vehicle starts with linearly increasing deceleration until
it reaches the minimum speed v_min.

According to Lemma <ref>, we have

    v_min=v_0+1/4u^∗(  t_0)  ^2(
    τ-t_0)  ^2/v_0+(  τ-t_0)  u^∗(
    t_0)  -v_min.

Solving u^∗(  t_0) in (<ref>) yields

    u^∗(  t_0)  =2v_min-v_0/τ-t_0.

According to Lemma <ref> and the expression of u^∗(
t_0), the distance of the vehicle at time τ is given as

    x(  τ)  =1/3(  2v_min+v_0)  (
    τ-t_0)  .

Then, we can solve τ from the following equation

    l=x(  τ)  +(  KT+T-τ)  v_min,

that is,

    τ=3l+(  2v_min+v_0)  t_0-3t_pv_min/v_0-v_min.

The energy consumption in this case can be expressed as

    J_9^u=4/3(  v_min-v_0)  ^2/τ-t_0.





 §.§ Case X: u^∗(  t_0)  <u_min, and v^∗(  t_p)  <v_min.


In this case, τ=t_p. The optimal control only contains the linear
increasing deceleration process. According to Lemma <ref>, we have

    v^∗(  t_p)  =v_0+1/4u^∗(
    t_0)  ^2(  t_p-t_0)  ^2/v_0+(  t_p
    -t_0)  u^∗(  t_0)  -v(  t_p)
    ,
        l =v_0(  t_p-t_0)  +1/6u^∗(
    t_0)  ^2(  t_p-t_0)  ^3/v_0+(  t_p
    -t_0)  u^∗(  t_0)  -v^∗(  t_p)
    .

We can solve u^∗(  t_0) and v^∗(
t_p) from (<ref>) and (<ref>) to obtain

    u^∗(  t_0)  =2v^∗(  t_p)  -v_0
    /t_p-v_0,

and

    v^∗(  t_p)  =3/2l-v_0(  t_p
    -t_0)  /t_p-t_0+v_0.

The energy consumption in this case is

    J_10^u=3[  l-v_0(  t_p-t_0)  ]  ^2
    /(  t_p-t_0)  ^3.

































































































































10

url@samestyle








schrank20152015
D. Schrank, B. Eisele, T. Lomax, and J. Bak, “2015 urban mobility scorecard,”
  Texas A&M Transportation Institute and INRIX, Tech. Rep., 2015.

li2014survey
L. Li, D. Wen, and D. Yao, “A survey of traffic control with vehicular
  communications,” IEEE Trans. Intell. Transport. Syst., vol. 15,
  no. 1, pp. 425–432, 2014.

gilbert1976vehicle
E. G. Gilbert, “Vehicle cruise: Improved fuel economy by periodic control,”
  Automatica, vol. 12, no. 2, pp. 159 – 166, 1976.

hooker1998optimal
J. Hooker, “Optimal driving for single-vehicle fuel economy,”
  Transportation Research Part A: General, vol. 22, no. 3, pp. 183 –
  201, 1988.

hellstrom2010design
E. Hellstrom, J. Aslund, and L. Nielsen, “Design of an efficient algorithm for
  fuel-optimal look-ahead control,” Control Engineering Practice,
  vol. 18, no. 11, pp. 1318 – 1327, 2010.

li2012minimum
S. E. Li, H. Peng, K. Li, and J. Wang, “Minimum fuel control strategy in
  automated car-following scenarios,” IEEE Transactions on Vehicular
  Technology, vol. 61, no. 3, pp. 998–1007, 2012.

fleck2016adaptive
J. L. Fleck, C. G. Cassandras, and Y. Geng, “Adaptive quasi-dynamic traffic
  light control,” IEEE Trans. Control Syst. Technol., vol. 24, no. 3,
  pp. 830–842, 2016.

milanes2010controller
V. Milanes, J. Perez, E. Onieva, and C. Gonzalez, “Controller for urban
  intersections based on wireless communications and fuzzy logic,” IEEE
  Trans. Intell. Transport. Syst., vol. 11, no. 1, pp. 243–248, 2010.

alonso2011autonomous
J. Alonso, V. Milans, J. Prez, E. Onieva, C. Gonzlez, and T. de Pedro,
  “Autonomous vehicle control systems for safe crossroads,”
  Transportation Research Part C: Emerging Technologies, vol. 19, no. 6,
  pp. 1095 – 1110, 2011.

huang2012assessing
S. Huang, A. W. Sadek, and Y. Zhao, “Assessing the mobility and environmental
  benefits of reservation-based intelligent intersections using an integrated
  simulator,” IEEE Trans. Intell. Transport. Syst., vol. 13, no. 3, pp.
  1201–1214, 2012.

kim2014mpc
K. D. Kim and P. R. Kumar, “An mpc-based approach to provable system-wide
  safety and liveness of autonomous ground traffic,” IEEE Trans. Autom.
  Control, vol. 59, no. 12, pp. 3341–3356, 2014.

zhang2016optimal
Y. J. Zhang, A. A. Malikopoulos, and C. G. Cassandras, “Optimal control and
  coordination of connected and automated vehicles at urban traffic
  intersections,” in Proc. of the 2016 American Control Conference,
  2016, pp. 6227–6232.

rios2017survey
J. Rios-Torres and A. A. Malikopoulos, “A survey on the coordination of
  connected and automated vehicles at intersections and merging at highway
  on-ramps,” IEEE Trans. Intell. Transport. Syst., vol. 18, no. 5, pp.
  1066–1077, 2017.

v2i
http://www.audi.com/en/innovation/connect/smart-city.html.

asadi2011predictive
B. Asadi and A. Vahidi, “Predictive cruise control: Utilizing upcoming traffic
  signal information for improving fuel economy and reducing trip time,”
  IEEE Trans. Control Syst. Technol., vol. 19, no. 3, pp. 707–714,
  2011.

kamal2013model
M. A. S. Kamal, M. Mukai, J. Murata, and T. Kawabe, “Model predictive control
  of vehicles on urban roads for improved fuel economy,” IEEE
  Transactions on Control Systems Technology, vol. 21, no. 3, pp. 831–841,
  2013.

mahler2014optimal
G. Mahler and A. Vahidi, “An optimal velocity-planning scheme for vehicle
  energy efficiency through probabilistic prediction of traffic-signal
  timing,” IEEE Trans. Intell. Transport. Syst., vol. 15, no. 6, pp.
  2516–2523, 2014.

wan2016optimal
N. Wan, A. Vahidi, and A. Luckow, “Optimal speed advisory for connected
  vehicles in arterial roads and the impact on mixed traffic,”
  Transportation Research Part C: Emerging Technologies, vol. 69, pp.
  548 – 563, 2016.

de2016eco
G. De Nunzio, C. Canudas de Wit, P. Moulin, and D. Di Domenico, “Eco-driving
  in urban traffic networks using traffic signals information,”
  International Journal of Robust and Nonlinear Control, vol. 26, no. 6,
  pp. 1307–1324, 2016.

hartl1995survey
R. F. Hartl, S. P. Sethi, and R. G. Vickson, “A survey of the maximum
  principles for optimal control problems with state constraints,” SIAM
  Review, vol. 37, no. 2, pp. 181–218, 1995.

malikopoulos2008real
A. Malikopoulos, “Real-Time, Self-Learning Identification and Stochastic
  Optimal Control of Advanced Powertrain Systems,” Ph.D. dissertation, The
  University of Michigan, 2008.

khalil2002nonlinear
H. K. Khalil, Nonlinear Systems, 3rd ed.1em plus 0.5em minus
  0.4emPrentice Hall, 2002.






