Modified Dynamic Programming Algorithms for GLOSA Systems with Stochastic Signal Switching Times

A discrete-time stochastic optimal control problem was recently proposed to address the GLOSA (Green Light Optimal Speed Advisory) problem in cases where the next signal switching time is decided in real time and is therefore uncertain in advance. The corresponding numerical solution via SDP (Stochastic Dynamic Programming) calls for substantial computation time, which excludes problem solution in the vehicle's on-board computer in real time. To overcome the computation time bottleneck, as a first attempt, a modified version of Dynamic Programming, known as Discrete Differential Dynamic Programming (DDDP) was recently employed for the numerical solution of the stochastic optimal control problem. The DDDP algorithm was demonstrated to achieve results equivalent to those obtained with the ordinary SDP algorithm, albeit with significantly reduced computation times. The present work considers a different modified version of Dynamic Programming, known as Differential Dynamic Programming (DDP). For the stochastic GLOSA problem, it is demonstrated that DDP achieves quasi-instantaneous (extremely fast) solutions in terms of CPU times, which allows for the proposed approach to be readily executable online, in an MPC (Model Predictive Control) framework, in the vehicle's on-board computer. The approach is demonstrated by use of realistic examples. It should be noted that DDP does not require discretization of variables, hence the obtained solutions may be slightly superior to the standard SDP solutions.


Introduction
In an era of climate crisis, actions toward environment protection are due in Transportation systems, which have a significant impact on environmental pollution and energy resources shortage. Improved fuel efficiency in road vehicles implies reduced fuel consumption, emissions and expenses for the driver. Efficient intelligent transportation systems, including real-time traffic signals, contribute to this effort. Traffic lights were introduced, in the first place, as a measure to ensure safe crossing of antagonistic streams of vehicles, cyclists and pedestrians at urban junctions. However, enforcing safety via traffic lights affects the fuel consumption, as some vehicles are obliged to fully stop in front of a red light; and then accelerate, after the traffic light switching to green. To reduce the resulting vehicle delays and number of stops, several algorithms have been proposed and deployed over the past decades, aiming at optimizing the traffic signals operation (Hounsell and McDonald, 2001;Papageorgiou et al., 2003;Kosmatopoulos et al., 2006). In this context, fuel consumption is increasingly considered as an optimization or evaluation criterion, while developing and deploying signal control systems (Jamshidnejad et al., 2017).
Fixed-time signal plans are derived offline based on historical constant demands; and are applied without deviations. This implies that switching times of the traffic lights are known in advance. In contrast, real-time signal control strategies make use of real-time measurements to compute in real time suitable signal settings. Depending on the employed signal control strategy, the control update period may range from one second to one signal cycle. Clearly, for real-time signals, the next switching time is not known before the switching decision has been actually made.
A common dilemma, for a vehicle approaching a red traffic light, is whether it should slow down or maintain its speed at risk to stop if the traffic light has not switched to green at arrival. This dilemma may be addressed by appropriately designed on-board systems, which receive the current state and timing of the traffic signal and guide the driver (or an automated vehicle), while approaching the traffic light, by giving speed advice that ensures that the vehicle will cross the traffic signal at green and with minimum fuel consumption and emissions. Systems (or apps) optimizing the vehicle approach to traffic lights are often referred to as Green Light Optimal Speed Advisory (GLOSA) systems (Stahlmann et al., 2016).
In the case of fixed signals, and hence prior knowledge of the next switching time, a corresponding message is broadcasted by the signal controller well before switching. Under these conditions, the problem of how to optimize the approach to traffic signals has been addressed in different ways, including rule-based algorithms (Katsaros et al., 2011;Sanchez et al., 2006;Ma et al., 2018) and optimal control approaches, which consider explicitly the vehicle kinematics and are, by their nature, more efficient in producing fuel-optimal speed profiles (Lawitzky et al., 2013;Typaldos et al., 2020a). Some of these works take into consideration additional factors, such as the car waiting queue. In (Yang et al., 2016), an eco-CACC (Cooperative Adaptive Cruise Control) scheme was developed, where optimal speed trajectories were calculated by minimizing fuel-consumption and ensuring that the vehicles arrive at the intersection as soon as the last queued vehicle is discharged. An extension of this work for the case of multiple signalized intersections is presented in (Yang et al., 2020). In the literature, most existing GLOSA problems are focusing on developing strategies for a single vehicle, however, there are few works that approach the problem in case of platoons of vehicles in mixed traffic environment. In (Zhao et al., 2018), a model predictive control (MPC) approach was proposed that minimizes the fuelconsumption of a platoon of mixed vehicles (automated and human-driven vehicles) while crossing an intersection during the green phase.
On the other hand, the case of real-time signals with very short (e.g., second-by-second) control update periods is more complicated, as there is no exact prior knowledge of the next switching time. In this case, the best available knowledge can be presented as an estimate or as a probabilistic distribution for the next switching time within a shortterm future time-window. A comparison of several signal control methods with respect to traffic efficiency, plan stability and the resulting GLOSA performance is presented in (Blokpoel and Lu, 2017). In (Koukoumidis et al., 2011), a system called SignalGuru was developed, which detects and predicts the traffic signal timing using a collection of mobile phone data. Instead of a single estimate, Mahler and Vahidi (2012) produced a probability distribution for the next switching time based on past signal statistics. However, the available probability distribution is used heuristically (rather than optimally) to accordingly time-weigh the objective function within a deterministic optimal control problem that is solved via a dynamic programming (DP) algorithm. In (Sun et al., 2020), the uncertainty of traffic signal timing is considered as a data-driven chance-constrained robust optimization problem, where the red-light duration is defined as a random variable. A data-driven approach is adopted to formulate chance constraints, based on empirical sample data, and Dynamic Programming is employed to solve the optimization problem. In (Lawitzky et al., 2013), a stochastic optimal control problem was proposed, which uses a probabilistic distribution of the next signal switching time, and the problem is solved using a discrete stochastic dynamic programming (SDP) algorithm.
In (Typaldos et al., 2020a), the problem of producing fuel-optimal vehicle trajectories for a vehicle approaching a traffic signal was considered for both cases of known and stochastic switching times. For the first case, an optimal control problem was formulated and solved analytically via PMP (Pontryagin's Maximum Principle). Subsequently, the case of stochastic switching time with known probability distribution was also addressed in the format of a stochastic optimal control problem, which was solved numerically using SDP. The proposed SDP algorithm may take several minutes to execute, which implies that the solution is not real-time feasible and can therefore not be obtained on-board the vehicle, but must be executed offline, on the infrastructure side, and be communicated to approaching vehicles according to their current states. To substantially reduce the computation time and memory requirements for the solution of the stochastic GLOSA problem and enable its solution on-board the vehicle, Typaldos et al. (2021) employed a Discrete Differential Dynamic Programming (DDDP) algorithm (Heidari et al., 1971). DDDP is an iterative algorithm, each iteration receiving a feasible (but non-optimal) trajectory and transforming it to an enhanced one, to be used in the next iteration, and so forth, until convergence to the overall solution is achieved. Each iteration uses the conventional DP algorithm to solve the problem within a strongly reduced state domain around the received state trajectory of the previous iteration. The computational time required for each iteration is far lower compared to that of the one-shot full problem solution, due to the strongly reduced space domain considered. Thus, the problem may be solved by use of DDDP very fast (around 1 s CPU time or less) (Typaldos et al., 2021). It should be noted that, in contrast to deterministic optimal control problems, general stochastic optimal control problems do not feature a solution trajectory, even for given initial states, due to the uncertainty of system evolution created by the included stochastic variables. However, in the specific stochastic GLOSA problem, such a trajectory is indeed present in the problem solution, and this allows for application of the DDDP algorithm.
As an attempt to further reduce the computation time for the solution of the stochastic GLOSA problem and enable its solution on-board the vehicle, a Differential Dynamic Programming (DDP) algorithm is employed in the current Figure 1: A vehicle starting from a given initial state ( 0 , 0 ) aims to reach a fixed final state ( , ) in presence of a traffic signal at a given position 1 that switches to green at time 1 .
work. DDP was first introduced in (Jacobson and Mayne, 1970), while several extensions and applications were eventually conducted by Yakowitz (1979, 1984). DDP is also used in robotics (Tassa et al., 2014;Budhiraja et al., 2018) and unmanned aerial vehicles (UAV) (Xie et al., 2017). DDP is also an iterative algorithm, which starts with a user-defined feasible trajectory to be used in the first iteration. Each iteration produces an improved trajectory, to be used in the subsequent iteration; until convergence to the solution of the original optimal control problem is achieved. Each iteration solves, for each time-step separately, a quadratic-linear approximation of the stochastic recursive Bellman equation; the approximation being computed around the initial trajectory of the iteration. It should be noted that, in contrast to the standard DP and DDDP algorithms, DDP requires no discretization of the state and control spaces, hence it may result in better solutions compared with discretised-value formulations. Moreover, DDP is found to deliver solutions quasi-instantaneously, which enables the approach to be readily implementable in an MPC (model predictive control) framework online, on the vehicle's computer. Note that communication between vehicles and traffic signals (V2I) is crucial in GLOSA problems (Lu et al., 2020), however in this work we focus on the methodological part of such systems.
The remainder of the paper is organized as follows: in Section 2, the optimal control problems with known signal switching time and uncertain signal switching time, as proposed in (Typaldos et al., 2020a) are briefly presented for completeness. Section 3 presents the DDDP algorithm, along the lines of (Typaldos et al., 2021). Section 4 presents the DDP-based GLOSA problem algorithm, while demonstration results for the DDP algorithm's performance and comparison with the one-shot stochastic GLOSA and the DDDP results are presented in Section 5. Finally, Section 6 concludes this work, summarizing its contributions.

Optimal Control-Based GLOSA with Known or Unknown Signal Switching Time
This section outlines, for completeness, the deterministic and stochastic GLOSA optimal control problems, for the cases of known and unknown signal switching time, respectively, as well as the SDP solution algorithm for the latter, following (Typaldos et al., 2020a).

Known Signal Switching Time -Deterministic GLOSA
Consider a vehicle traveling from an initial state 0 = [ 0 , 0 ] , 0 being a given initial position and 0 a given initial speed, with the purpose to reach a fixed final state = [ , ] within a free (but weighted) time horizon . Between the initial and final positions, there is a traffic signal, and hence the additional restriction that the vehicle must not pass the signal position 1 before the known time 1 , when the traffic light turns green from red (see Fig.  1). The implicit assumption here is that a red light is active when the vehicle appears on the link (at time 0), but a generalisation, which includes the case where the vehicle appears when the traffic light is green, is given in (Typaldos et al., 2020a). The vehicle task is to appropriately adjust its acceleration (control variable), so as to minimize fuel consumption, while satisfying the initial and final conditions 0 and , as well as the intermediate (traffic signal) constraint.
The minimization problem outlined above is formulated as an optimal control problem, which accounts for the vehicle kinematics via the following state equations: where is the vehicle acceleration, which assumes the role of the control variable. The objective criterion to be minimized reads The utilized acceleration cost term 2 in the criterion was demonstrated to be an excellent proxy for deriving fuelminimizing vehicle trajectories (Typaldos et al., 2020b). The final time is free but penalized with the weight . For higher values of , the resulting will be lower and vice versa. This, consequently, affects the acceleration cost, which, depending on higher or lower value, will also have increased or decreased values (for more details, see (Typaldos et al., 2020a)). In addition, the green-light constraint, ≥ 1 , must be fulfilled, where is the time at which the vehicle crosses the signal position 1 , that is, ( ) = 1 . If necessary, upper and lower bounds may be applied to speed and acceleration .
The solution of this problem was addressed in (Typaldos et al., 2020a) and can be obtained analytically using symbolic differentiation tools. Thus, the numerical solution of the deterministic GLOSA problem, for a specific problem instance, takes only fractions of a second of computation time and can be executed in real time on-board for each approaching vehicle. Note that it may be reasonable to continuously update the vehicle trajectory (in a model predictive control (MPC) loop) to account for possible deviations from the first calculated vehicle trajectory, which may occur because of a variety of disturbances, including a slower vehicle ahead.
For a given junction, the final state is the same for any initial vehicle state 0 and any switching time 1 . Therefore, the optimal value of criterion (3) of the deterministic GLOSA solution depends only on the initial state and the switching time and is denoted * ( 0 , 1 ) for later use.

Uncertain Signal Switching Time Problem -Stochastic GLOSA
The traffic light switching time may be subject to short-term decisions in dependence of the prevailing traffic conditions in cases of real-time signals. In such cases, we typically have minimum and maximum admissible switching times; hence, based on statistics from past signal switching activity, we may derive a probability distribution of switching times within the admissible time-window of possible signal switching times. Thus, the problem can be cast in the format of a stochastic optimal control problem, which may be solved numerically using SDP techniques. To this end, the analytical solution of the deterministic GLOSA optimal control problem is used within the stochastic approach, as will be explained in this section (for more details, see (Typaldos et al., 2020a)).
For the stochastic optimal control problem and the SDP algorithm (Bertsekas, 2012), the discrete-time version of the vehicle kinematics, with time step , is considered, as follows: where ( ) and ( ) correspond to the vehicle position and speed, respectively, at discrete times = 0, 1, … (where = ), while the control variable ( ) reflects the acceleration that remains constant over each time period . The state and control variables are bounded within the following feasible regions with , and , being the lower and upper bounds of the states and acceleration, respectively. The traffic light's discrete switching time 1 is not known, but it is assumed that a known range ≤ 1 ≤ of possible switching times exists, and being the minimum and maximum possible switching times, respectively. For proper problem formulation, a virtual statẽ ( ) is introduced, that reflects formally the stochasticity of traffic light switching where ( ) is a binary stochastic variable defined as ( ) = 0 if traffic light switches at time + 1 1 else (9) with (8) and (9), the virtual statẽ ( ) is either equal to 1 if the traffic light has not yet switched until time − 1; or equal to 0 if switching occurred at time or earlier. The virtual statẽ is assumed measurable, which means that the system knows at each time if switching has taken place or not within the last time period [( − 1) , ]. The stochastic variable ( ) is independent of its previous values and takes values according to a time-dependent probability distribution ( | ). Based on the statistics of previous signal switching activity, availability of an a-priori discrete probability distribution ( ), ≤ 1 ≤ , is assumed, for signal switching within the time-window, where ∑ = ( ) = 1. Since no switching takes place for ≤ − 1, we have For ≥ , the probability distribution ( | ), is obtained by use of "crop-and-scale", meaning that the a-priori probabilities of previous time steps, where switching did not take place, are distributed analogously to increase the probabilities of the remaining discrete times within the time-window (Lawitzky et al., 2013). As shown in (Typaldos et al., 2020a), this update may be done by use of the following crop-and-scale formula that applies for ≤ ≤ − 1 and for any a-priori distribution ( ) The cost criterion of the stochastic problem is essentially the same as (3) in the deterministic case. However, in the stochastic case, the exact value of the criterion depends on the stochastic variable's realization, and therefore we consider minimisation of the expected value. As shown in (Typaldos et al., 2020a), the cost criterion in discrete time becomes where the expectation refers to the stochastic variable ( ), = 0, … , − 1. This criterion captures the quadratic acceleration cost up until the stochastic switching time 1 , when the vehicle is at state ( 1 ). After the signal switching, the problem instantly becomes a deterministic GLOSA problem (Section 2.1), and the corresponding optimal cost-togo is * [ ( 1 ), 1 ], which will be denoted as the "escape cost".
In this formulation, it has been assumed that the decision on the traffic light switching is taken within the last time period before the actual switching. The generalization to the case of taking a switching decision time periods in advance of the actual switching is easy and is mentioned in (Typaldos et al., 2020a).

Discrete SDP Numerical Solution Algorithm
For the numerical solution of the stochastic problem, using the SDP algorithm, the state and control variables must be discretised. As the discretization level has a significant impact on computational time and memory requirements, but also on the accuracy of the computed solution, an appropriate trade-off must be specified between reasonable computation requirements versus achievable solution quality. For the discretization, the discrete time interval is set equal to 1 s, which is a reasonable choice for the problem at hand. Then, a general discretization interval Δ for the problem variables is assumed, and the discretization interval of acceleration is set Δ = Δ. From (5), the discretization interval of speed assumes the same value (Δ = Δ = Δ). Likewise, in view of (4), the discretization interval for the position is Based on these settings, it was shown in (Typaldos et al., 2020a) that, if ( ), ( ), ( ) are discrete points, then ( + 1) and ( + 1) resulting from (4) and (5) are also discrete points.
It is now straightforward to apply the discrete SDP algorithm to obtain a globally optimal closed-loop control law * ( ) = [ ( ), ], which, for any given vehicle state ( ) ∈ and time , delivers the corresponding optimal acceleration * ( ). The SDP algorithmic steps are summarized below. Note that the algorithm needs to consider only the casẽ ( ) = 1, therefore any arguments pertaining tõ ( ) are suppressed for convenience.
The SDP algorithm is as follows: 1: As mentioned, this algorithm delivers a globally optimal control law * ( ) = [ ( ), ] for the full state domain . Note that general stochastic optimal control problems do not possess a solution trajectory for specific initial states 0 , because the state evolution is uncertain in presence of the stochastic variables. However, in the specific stochastic GLOSA problem addressed here, the evolution of the vehicle states (4) and (5) is not affected by the stochastic variable ( ), which concerns only the signal switching time. Thus, for a given initial state, i.e., vehicle position and speed at time 0, the optimal control law may be used to produce an optimal vehicle trajectory that the vehicle should pursue; until the signal switching actually occurs, in which case the vehicle must instantly behave according to the deterministic GLOSA solution.
Note that the SDP algorithm may take several minutes to execute in an ordinary PC, as will be reported in Section 5. This implies that the solution cannot be obtained on the vehicle side in real time.

Discrete Differential Dynamic Programming (DDDP)
In (Typaldos et al., 2021), a modified DP algorithm called DDDP was employed for the stochastic GLOSA problem in order to address the major disadvantage of the discrete (S)DP algorithm, which is the high computation time required for the numerical solution of the optimal control problem, which increases exponentially with the number of state and control variables (Papageorgiou et al., 2015). The DDDP algorithm was proposed in (Heidari et al., 1971) for deterministic optimal control problems. The method can nevertheless be applied here, because an optimal vehicle trajectory may be derived for the stochastic GLOSA problem, despite its stochastic character, as mentioned in the previous section. The DDDP approach to the stochastic GLOSA problem is presented in this paper in more detail and with more comprehensive testing and comparison results, compared to the conference article (Typaldos et al., 2021).
DDDP is an iterative algorithm, calling for a feasible starting state trajectory to be specified externally. Each iteration receives a feasible (but non-optimal) state trajectory ( −1) ( ), and transforms it to an enhanced one ( ) ( ), to be used in the next iteration. To this end, each iteration solves a discrete SDP problem by use of the standard SDP algorithm presented above. What changes at each iteration is the considered state domain which is a strongly reduced subdomain of the original state domain in (6). In other words, the discretized SDP problem is solved in each iteration within a corridor with width ( ) around the received state trajectory ( −1) ( ) of the previous iteration, to produce a solution trajectory ( ) ( ) for use in the next iteration. The corridor width ( ) , as well as the discretisation intervals Δ ( ) , Δ ( ) , can vary in each iteration, typically at a decreasing rate. The iterations stops when a termination criterion is satisfied.
In the proposed GLOSA application (Typaldos et al., 2021), the starting trajectory for the first iteration of DDDP is the optimal solution of the deterministic GLOSA problem, assuming the "pessimistic" case where the traffic light will switch from red to green at the latest possible time, that is, at 1 = , so as to cover the whole time range and be not too far from the stochastic optimal trajectory; see (Typaldos et al., 2020a). The discretisation intervals Δ ( ) , Δ ( ) for the first iteration are also given. The intervals are reduced by half, each time there is no solution improvement at two subsequent iterations. The corridor width is taken as where = [ , ] are constant given values specifying the state corridor width. Thus, the corridor's initial width is defined through the chosen values for and Δ ( ) . In the following iterations, whenever the discrete interval is reduced, there is an analogous reduction of the corridor width. Consequently, we have a constant number of feasible discrete points in all iterations, which facilitates the algorithm's fine-tuning, so as to improve its computational efficiency. Note that, and values may differ, as the magnitude of the two respective state variables differs. The admissible control region (see (7)) is kept the same at each iteration, although many related state transitions cannot be considered in view of the reduced state variables domain. The algorithm terminates whenever there is no improvement of the produced solution trajectory even after a reduction of the discretisation interval; or when the Δ ( ) value becomes less than 0.125, which was found in (Typaldos et al., 2020a) to lead to sufficiently accurate results.
It should be noted that there is no general guarantee that the DDDP iterations will actually converge to the fulldomain SDP solution. In particular, if the state sub-domains ( ) considered in the iterations are too small, the obtained DDDP solution may actually differ from the overall SDP solution. On the other hand, if the state sub-domains are selected large, the required number of iterations may decrease, but the computation time required to find the solution at each iteration increases accordingly. In conclusion, some fine-tuning regarding the size of sub-domains is necessary to ensure convergence to the overall SDP solution with minimum overall (all iterations) computation time.

Differential Dynamic Programming (DDP)
DDP is an iterative algorithm, which requires a given initial feasible trajectory (of states and controls) to be used in the first iteration. At each iteration and time step, a quadratic-linear approximation of the recursive Bellman equation (14), around the initial trajectory of the iteration, is solved, leading to an improved trajectory. The improved trajectory is then used as initial trajectory in the next iteration, and the procedure continues until convergence to the solution of the original optimal control problem is achieved. The method was developed for deterministic optimal control problems; and it is not applicable to general stochastic problems, which do not feature solution trajectories (Bertsekas, 2012). However, as explained earlier, the specific stochastic GLOSA problem admits feasible solution trajectories for specific initial states, hence DDP may be applied.

General Constrained DDP
The standard DDP method (Jacobson and Mayne, 1970) does not account for constraints, so, for the needs of the problem presented in this work, extensions of DDP, proposed by Murray and Yakowitz (1979) for linear constraints and by Yakowitz (1986) for nonlinear constraints, is utilized.
Consider a discrete-time optimal control problem with states and controls with the recursive Bellman equation ( ( ), ) = min{ ( , , )+ ( ( , , ), +1)}, for = −1, … , 0, where is the optimal cost function, is the objective function of the optimal control problem, is the right-hand side of the state equation, and the minimisation must be carried out for all feasible controls ( ) that satisfy any inequality constraints present. The DDP procedure undertakes, at each time step of each iteration, a quadratic approximation of the term to be minimized in the recursive Bellman equation, i.e., of ( , , ) + ( ( , , ), + 1). The quadratic approximation is taken around nominal trajectories (̄ ( ),̄ ( )), which are the initial trajectories of each iteration. Define = −̄ and = −̄ . The aim is to find the optimal control law for , which minimizes the quadratic approximation, subject to some inequality constraints. The procedure of the DDP algorithm for each iteration is described in brief as follows, see (Yakowitz, 1986;Murray and Yakowitz, 1979) for more details.
For = − 1, … , 0, the quadratic approximation ( , , ) of the term ( , , ) + ( ( , , ), + 1) around a nominal point (̄ ( ),̄ ( )), is required and can be expressed as follows (for simplicity, the indexes are omitted) where the zero-order constant term is omitted, as it does not influence the minimisation; and , , , , are matrices with appropriate dimensions and with elements that may depend on (̄ ( ),̄ ( )). Furthermore, we assume the general inequality constraints for the optimal control problem and we denote as̃ ( , ) its linear approximation around the nominal trajectories (̄ ,̄ ).
For the solution of the resulting Quadratic Programming (QP) problem, Fletcher's active set algorithm is used (Fletcher, 1971). The critical issue here is that the minimization in the recursive Bellman equation should be executed in a parametrized way, i.e., deliver as a function of , which is not compatible with a numerical solution procedure. Therefore, in the QP problem formulation, we replace with̄ (i.e. we set = 0) in (18) and̃ ( , ), and solve the following QP problem to obtain a numerical value for min (̄ ,̄ + ) s.t̃ After solving the QP problem, the index set of the active constraints, denoted as , leads to the linear system of equations and expressing (21) in matrix form, we have where has rank equal to the number of indexes in . This solution of the QP problem satisfies the necessary conditions of optimality for the Lagrangian (Fletcher, 1971) where is the Lagrange multiplier vector. These necessary conditions may be obtained by differentiating with respect to and , which yields the following linear system of equations In order to re-introduce , i.e. the variablity of state variables, we consider that the constraints that are active while we assumed =̄ , remain active for other , i.e.
which in matrix form reads Then, we may derive a control law, i.e. as a function of by solving analytically the accordingly extended version of (24), i.e.
Which must be stored for use at the next time step − 1 within the same iteration. Note that this approximate cost function is quadratic by construction, which facilitates the quadratic approximation in the Bellman equation at the next time step − 1. Given ( , ), from (28) where 0 < ≤ 1 is used to ensure the convergence of the algorithm. Specifically, values smaller than 1 may facilitate convergence if needed; but may decrease the convergence rate if selected too small. The algorithm terminates whenever the following convergence test is satisfied where 1 is a small positive number. In contrast to the SDP and DDDP algorithms, DDP does not apply any discrete DP procedures, hence no discretization of the state and control domains is necessary. As a result, the required computation time is independent of any discretization intervals, and the obtained solution trajectories are value-continuous, hence potentially better than those obtained by the other algorithms, even when using fine discretization.

Constrained DDP for the GLOSA Problem
To apply the DDP algorithm to the GLOSA stochastic optimal control problem described in Section 2.2, the quadratic approximation of the right-hand side of (14) around a nominal trajectory (̄ ( ),̄ ( )) is first required. Note that only the * term needs to be approximated, as the rest terms are already quadratic. For the approximation, the LOESS (locally estimated scatterplot smoothing) method was utilized (Cleveland et al., 2017). Specifically, a number of ( , ) points are specified around the nominal trajectory at each iteration, and the corresponding values of * ( ( ), ) are computed. It was found that some 4 such points per time step are sufficient for a good fit. Then, LOESS fits the following smooth function to the data set ( , ) = 1 2 + 2 2 + 3 + 4 + 5 + 6 (34) where 1 , … , 6 are the coefficients of fitting. The resulting fitted function (34), along with the other quadratic terms of (14), can be easily expressed in the form of (18). It was verified that the resulting quadratic function (18) is always convex, something that was expected from the physical background of the problem. The nominal trajectory of the first iteration is taken to be the optimal solution of the deterministic GLOSA problem, assuming the "pessimistic" case where the traffic light switches from red to green at the latest possible time, i.e., 1 = . For the state constraints (6), we may replace the state equations (4), (5) therein, hence, for the admissible region of the SDP (6) and (7), we have the equivalent constraints which can be written in terms of and as follows Having the quadratic approximation of the recursive Bellman equation and the linear inequality constraints (35), the resulting QP is as described in the previous subsection. In fact, the resulting QP problem for the stochastic GLOSA application is simpler than the general case of Section 4.1. After setting = 0 in (36), we have only one decision variable, , with constant upper and lower bounds. Thus, for the solution of the QP problem, it suffices to first compute analytically the value of that minimises the quadratic function. If this value does not violate any of the upper or lower bounds, then the QP solution is given by that value; else, the QP solution equals the activated bound. All further procedures are as explained in Section 4.1.

Demonstration Results and Comparison
In this section, the performance of the proposed approaches is tested, demonstrated and compared. Specifically, the DDDP and DDP algorithms are applied to realistic scenarios and evaluated regarding the quality of their solution compared to the standard SDP, as well as the computational time needed for each algorithm to converge to the optimal solution.

Scenarios Setup
For the evaluation, several scenarios have been considered in various situations, such as cases where the vehicle needs to accelerate or decelerate before or after the traffic signal; or cases where the vehicle is forced to fully stop and wait until the traffic light switches from red to green. For this paper, three scenarios have been chosen for demonstration with full illustration of state and control trajectories, according to Table 1. For consistency, the chosen scenarios are the same as in previous related works (Typaldos et al., 2020a(Typaldos et al., , 2021. All scenarios concern mixed accelerationdeceleration cases. However, in Scenario 1, the vehicle starts with low initial speed and needs to mostly accelerate in order to optimally pass the traffic signal. On the other hand, in Scenarios 2 and 3, the vehicle starts at higher speed, hence it needs to mostly decelerate to avoid a full stop at the traffic signal. Compared to Scenarios 1 and 2, in Scenario 3 the vehicle starts closer to the traffic light, which leads to a full stop for few time steps before the traffic signal switches from red to green. For all evaluated scenarios, the weight parameter in (3)   is 1 s and the switching time window for the traffic signal is [ , ] = [10, 30] s with uniform a-priori probability distribution. Regarding DDDP, for the initial discretization, Δ = Δ = 0.5 is used, which leads to Δ = 0.25 m according to (15); and the initial corridor width in (17) is set = [20, 4], i.e., we have = 5 ⋅ . The choice of the initial discretization and corridor width value will be justified later in this section. For the DDP algorithm, parameters in (30) and 1 in (33) are set equal to 1 and 10 −4 , respectively.

DDDP algorithm results
Fig. 2 (Scenario 1) and Figs. 6 and 7 (for Scenarios 2 and 3, respectively, see Appendix A) display the optimal state (speed) and control (acceleration) trajectories over each iteration of the DDDP algorithm. Note that, position trajectories are not included, as the differences in those trajectories, at each iteration, are small and barely visible. In each iteration, we consider a corridor Δ ( ) = [− ⋅ Δ ( ) , ⋅ Δ ( ) ] around the respective received state trajectories, which cannot of course extend out of the full state bounds.
In all Figs 2, 6 and 7, the dashed blue lines represent, for each iteration, the received trajectory, the solid orange lines represent the optimal trajectories derived, and the red dashed lines reflect the corresponding corridor bounds. For Scenario 1 (Fig. 2), it can be observed that, starting with the initial chosen discretization, the first DDDP iteration improves the initial trajectory, leading to a better solution, which is optimal within the considered sub-domain. In the second iteration, no further improvement can be achieved within the new sub-domain bounds, which means that, with the current discretization values, the best achievable solution has been reached. By reducing the discretization at the 3rd iteration, a reduction in the corridor width is observed, but the number of discrete points remains the same. This reduction enables further improvement of the solution, which remains the same in iteration 4; hence the discretisation is further reduced, leading to further improvement in iteration 5; and the procedure continues with iteration 6, where no further improvement is reached and the algorithm terminates, as the discretisation has reached the minimum required value. Similar behaviour is observed for Scenarios 2 and 3, where 10 iterations are required for convergence, and the respective Figs. 6 and 7 display a subset thereof. Table 2 contains the values of the objective function for each iteration of the DDDP algorithm for all scenarios, assuming Δ = 0.5 and = [20,4], where the choice of these values will be explained in the following.
The DDDP has been evaluated for different corridor and initial discretization Δ values, for the three investigated scenarios (see Table 4 in Appendix A). It can be seen that, for all presented initial discretization values, the obtained optimal solution at convergence reaches the same globally optimal solution, if the corridor width is sufficiently large, specifically for ≥ 4 (or lower, in some cases). This is because, for very small values of , DDDP does not have sufficient flexibility to improve the solution at each iteration due to the extremely limited state space, something that may lead to a local optimum of the overall problem at convergence. At the same time, a reduction of the number of DDDP iterations is obtained for larger corridors. This behaviour is expected, as the bigger corridors, i.e., bigger admissible sub-regions, lead to potentially better solutions at each iteration, and hence to fewer iterations to converge to the optimal solution. On the other hand, despite the decrease on the number of iterations, the overall computation time may increase due to the higher computation time required at each iteration, which in turn, is due to more feasible discrete state points included in each iteration's sub-region. Based on these observations, the selection of the values = [20, 4] and Δ = 0.5 seems to be a reasonable choice. The accuracy of the DDDP algorithm compared to the full one-shot SDP solution may be assessed by contrasting the optimal cost and the optimal states and control trajectories, obtained in the last respective DDDP iterations of the three scenarios, to the corresponding optimal trajectories derived from the full-range SDP with a discretisation of Δ = 0.125. As a matter of fact, DDDP manages, in all cases, to converge to the exact same optimal solution as the full-range SDP. The obtained optimal costs of both approaches, for the three scenarios, are 1.175, 3.906 and 6.3582, respectively, while the computation time differences are remarkable, as the one-shot SDP needs approximately 613 s to obtain the solution (same for all scenarios), while DDDP needs only 0.69, 1.24 and 1.12 s for the respective three scenarios. More importantly, this big reduction in computation time enables the DDDP algorithm to be executable in real time, even in an MPC mode, on the vehicle side, similarly to the deterministic GLOSA.

DDP algorithm results
Fig. 3 (Scenario 1) and Figs. 8 and 9 (for Scenarios 2 and 3, respectively, see Appendix A) illustrate the evolution of the state (speed) and control (acceleration) trajectories produced by the DDP algorithm at each iteration. In all figures, blue dashed lines represent the initial trajectories, and solid orange lines the derived trajectories of each iteration. From the figures, it can be seen that the DDP algorithm, starting from the pessimistic deterministic GLOSA solution, converges to the overall optimal solution. It can also be observed that, at each iteration, starting from the  initial (received) trajectory, the algorithm results in an improved one, which leads to an improved solution. The DDP algorithm is seen to converge very fast to the optimal solution, with the improvement being more profound at the first iterations, as the change between the nominal and the produced trajectories are more noticeable. On the other hand, in the last iterations, the improvement is smaller, as the algorithm is already very close to the optimal solution. As mentioned earlier, all intermediate DDP solutions at each iteration are continuous due to the nature of DDP, which is operating on a continuous-value basis for all involved variables. Fig. 4 demonstrates the accuracy of the DDP solutions compared to the one-shot discrete SDP solutions for the three scenarios. In this figure, the optimal state (speed) and control (acceleration) trajectories obtained from DDP algorithm at convergence are contrasted to those obtained from the full-range SDP algorithm with discretization Δ = 0.125 m/s 2 . The two solutions, in all scenarios, are quite close to each other, with a slight advantage for the DDP solution, which is not bound to a fine, but still visible value-discretization of the state and control, as it is the case for the one-shot discrete SDP algorithm.  Table 3 contains the summarized information of the number of iterations until convergence, CPU time and the optimal obtained cost of the one-shot SDP, the iterative DDDP and the iterative, but non-discrete DDP algorithms for Scenarios 1, 2 and 3. Based on the results reported in the table, it can be verified that DDP's optimal solution is slightly better compared to the other two approaches. However, the most striking difference of DDP is the computational time needed to solve the problem, which is extremely small.

Summarized results
In order to explore the robustness of the DDDP and DDP algorithms and to further emphasize their superiority compared to the one-shot (S)DP, in terms of computation times, a more excessive analysis was conducted and is presented in Fig. 5. Specifically, Fig. 5 illustrates the required CPU times until convergence for both proposed algorithms for a plethora of different initial conditions, i.e., initial speeds and positions (distance from the traffic signal) of a vehicle. From both Fig. 5a and Fig. 5b it can be seen that, for all evaluated initial conditions, the CPU times of both DDDP and DDP are similarly low as for the above three scenarios, with average times of 1.4 s and 0.001 s, respectively, the corresponding maximum and minimum times being 6.3 s and 0.2 s for DDDP and 0.006 s and 0.0005 s for DDP, respectively. These findings lead to the conclusion that, even though DDDP reduces the CPU time significantly compared to the one-shot SDP, the DDP algorithm achieves almost instantaneous solutions, which enables the DDP approach to be used, within an MPC framework, in the vehicle's on-board computer.

Conclusions
In recent works (Typaldos et al., 2020a(Typaldos et al., , 2021, a stochastic GLOSA methodology was developed, by optimizing, using SDP and DDDP techniques, respectively, the vehicle kinematic trajectories subject to the intermediate stochastic traffic signal switching constraint and with a fixed final state. As an extension to these works, an iterative Differential Dynamic Programming (DDP) algorithm was employed in this paper. Within each iteration, DDP solves, for each timestep separately, a quadratic-linear approximation of the recursive Bellman equation. Demonstration and comparison results indicate that the DDP algorithm strongly outperforms both the full-range SDP and the DDDP algorithms in terms of computation time; and even delivers a slightly better optimal solutions due to lack of discretisation. This enables the DDP algorithm to be readily executable within a model predictive control framework in real time on-board approaching vehicles.
Current and future work is focused on: • Generalization of the current GLOSA problem by considering uncertain switching times for both green and red phases.
• Testing of the approach performance in presence of multiple (equipped and not equipped) vehicles, while traversing multiple subsequent intersections.