Reinforcement learning is an efficient, widely used machine learning technique that performs well when the state and action spaces are reasonable. This is rarely the case regarding controlrelated problems, as for instance controlling traffic signals. Here, the state space can be very large. In order to deal with the curse of dimensionality, a rough discretization of such space can be used but this is effective just up to a certain point. A way to mitigate this is to use techniques that generalize the state space such as function approximation. In this paper, a linear function approximation is used. Specifically, SARSA( ) with Fourier basis features is implemented to control traffic signals in the agent-based transport simulation MATSim. The results are compared not only to trivial controllers such as fixed-time, but also to state-of-the-art rule-based adaptive methods. It is concluded that SARSA( ) with Fourier basis features is able to outperform such methods, especially in scenarios with varying traffic demands.
Traffic signal control is a challenging real-world problem. Current
solutions to this problem, such as adaptive systems like SCOOT [
The use of RL is associated with challenging issues: the environment is dynamic (and thus agents must be highly adaptive), agents must react to changes in the environment at individual level while also causing an unpredictable collective pattern, as they act in a coupled environment. Therefore, traffic signal control poses many challenges for standard techniques of multiagent learning.
To understand these challenges, let us first discuss the single agent
case, where one agent performs an action once in a given state, and
learns by getting a signal (reward) from the environment. To put it
simply, RL techniques are based on estimates of values for
stateaction pairs (the so-called Q-values). These values may be
represented as a table with one entry for each state-action pair. This works
well in single agent problems and/or when the number of states and
actions is small. However, in [
An efficient representation of the states is a key factor that may limit the use of the standard RL algorithms in problems that involve several agents. Moreover, in scenarios in which the states are represented as continuous values, estimation of the state value by means of tabular Q-values may not be feasible. To deal with this problem, in this paper a true online SARSA( ) algorithm with Fourier Basis linear function approximation is used. As discussed ahead, this option is based on the fact that non-linear function approximation has several drawbacks.
The RL-based adaptive signal control algorithm was implemented
in the open-source agent-based transport simulation MATSim [
The remaining of this paper is organized as follows. The next section discusses background and related work. Sect. 3 describes the two adaptive signal control approaches used in this study: The rule-based signal control based on La¨mmer and the RL-based approach. Experiments and results are presented in Sect. 4, whereas Sect. 5 contains a discussion of the results and future work. 2 2.1
In contrast to fixed-time signals that cyclically repeat a given signal plan, traffic-responsive signals react to current traffic by adjusting signal states based on sensor-data (e.g., from upstream inducting loops or cameras). They can, therefore, react to changes in demand and reduce emissions and waiting times more efficiently.
A variety of traffic-responsive signal control algorithms have been
developed. An overview is given, e.g., by Friedrich [
Examples of traffic-responsive approaches from various
generations and technological basis are: SCOOT [
In RL, an agent’s goal is to learn an optimal control policy , which maps a given state to the best appropriate action by means of a value function. We can model RL as a Markov decision process (MDP) composed by a tuple (S; A; T ; R), where S is a set of states; A is a set of actions; T is the transition function that models the probability of the system moving from a state s 2 S to a state s0 2 S, upon performing action a 2 A; and R is the reward function that yields a real number associated with performing an action a 2 A when one is in state s 2 S. An experience tuple hs; a; s0; ri denotes the fact that the agent was in state s, performed action a and ended up in s0 with reward r. Let t denote the tth step in the policy . In an infinite horizon MDP, the cumulative reward in the future under policy is defined by the Q-function, Eq 1, where 2 [0; 1] is the discount factor for future rewards.
Q (s; a) = E hX1
RL methods can be divided into two categories: Model-based methods assume that the transition function T and the reward function R are available, or instead try to learn them. Model-free methods, on the other hand, do not require that the agent have access to information about how the environment works.
There are many studies that use RL to improve traffic signal
performance. Due to space restrictions, we refer the reader to some
survey papers (with different purposes): [
Using RL for traffic signal control is especially promising, as one
does not need a lot of domain knowledge (as opposed to, e.g.,
rulebased approaches); rather, the controller learns a policy by itself.
However, issues may arise with the aforementioned curse of
dimensionality. In fact, depending on the specific formulation (e.g., how
states and action spaces are defined), the search space can be very
high. For instance, consider an intersection with four incoming
approaches with three lanes per approach. If we define the state as the
queue length for each lane discretized in 10 levels, we would have
(4 3)10 distinct possible states. The reader is referred to [
In [
Since most of these works use QL, and thus approximate the Qfunction as a table, they may fall prey to the curse of dimensionality. This arises when one deals with realistic scenarios, as, e.g., those beyond 2-phase intersections that are common in the literature.
In order to address this, a few works used function approximation.
For instance, [
Recently, many studies have achieved impressive results using
deep neural networks to approximate the Q-function (e.g., DQN
[
As deployment, operations, and maintenance costs of trafficresponsive signals in general are high, transport simulation tools provide a perfect environment to systematically test and evaluate new signal control methods before applying them in the field.
The agent-based transport simulation MATSim [
In MATSim traffic is modeled by agents (i.e., persons) that follow a daily plan of activities and trips. Traffic flow is modelled mesoscopically by spatial first-in-first-out (FIFO) queues. Vehicles at the head of a queue can leave a link when the following criteria are fulfilled: (1) The link’s free-flow travel time has passed, (2) the flow capacity of the link is not exceeded in the given time step, and (3) there 4 An example on how to start a MATSim simulation using the RL signal control presented in this paper can be found at http://matsim.org/ javadoc ! signals ! RunSarsaLambdaSignalsExample.
(a) Graph structure of a link with multiple lanes.
(b) Multiple queues; spillback is captured correctly. is enough space on the next link. Despite this simplistic modeling approach, congestion as well as spillback can be modeled.
The traffic signal control module was developed by Grether as an
extension to MATSim [
Events of vehicles entering or leaving links and lanes are thrown on a second-by-second time resolution in the simulation. Sensors on links or lanes that detect single vehicles can be easily modeled by listening to these events. As in reality, the maximum forecast period of such sensors is limited – vehicles can only be detected when they have entered the link. If a link is short, forecasts might not be accurate. In the simulation, responsive signals use these sensor data to react dynamically to approaching vehicles. For every signalized intersection, the control unit is called every second to decide about current signal states. With that, also RL-based signal control approaches can be easily installed into the simulation framework.
In general, MATSim can model user reaction as route, mode or
departure time changes. But for this paper, only the traffic flow
simulation of MATSim is used. Readers interested in the evolutionary part
of MATSim – i.e., how agents adapt their plans and how long-term
effects can be analyzed – are referred to [
In this section, the two adaptive signal control approaches used in this study are presented: The rule-based signal control algorithm based on La¨mmer and the RL approach based on true online SARSA( ) with linear function approximation. 3.1
control algorithm
The idea of the self-controlled signals proposed by La¨mmer and
Helbing [
With this, the priority index is calculated as follows:
vehicles that are registered by sensors. Given a prediction of the
expected queue length n^i(t; ) at time > t and the maximum outflow
rate qimax for phase i, one can derive the expected required green
time g^i(t; ) for clearing the queue at time t using g^i(t; ) = n^qim(ta;x) .
i
i(t) =
8 n^i(t; )
><> i(tm)ax n^i0i(t;+i0g^)i(t; ) ; if i =
>> p(etn)(t) + i0 + g^i(t; i0) ; if i 6=
:
(t)
(t) :
(3)
Two cases are distinguished depending on whether the phase i is
already active or not. In either case, the equation basically divides the
number of vehicles by the time needed to clear the queue including
the (remaining) intergreen time. The priority index can, therefore, be
interpreted as a clearance efficiency rate. includes either the effect
of remaining intergreen time for the selected phase (when it has not
yet switched to green), or a lookahead beyond the end of the current
queue. It is bounded from below by the remaining intergreen time
i(t), since that time, if larger than zero, will be incurred before
traffic can flow, and from above by the full intergreen time i0, since
beyond that it is possible to just switch back from some other state. For
a non-active phase (i.e., i 6= (t)), the priority index is reduced by a
canceling penalty p(etn)(t). This prevents the optimizing regime from
frequently switching signal phases. The penalty can be interpreted
as the average additional waiting time for vehicles at the previously
served links that would occur upon cancellation. The priority index
as it is defined in Eq. 3 assumes that each signal phase only serves
one link – which is why phases and links are both denoted by i here.
The algorithm was further extended to be able to deal with realistic
traffic situations like lanes, phase combination with opposing
traffic, minimum green times, and overload. Since this extensions make
the equation less readable while the main method stays the same, the
authors refer to Thunig et. al [
An enclosing stabilizing strategy ensures that each link is at least served once during a specified minimal service interval to prevent spillbacks. Links that have to be stabilized are added to a stabilization queue. If the queue is non-empty, the phase corresponding to the first element of the queue is switched to green for a guaranteed green time gis depending on the average capacity utilization. If the stabilization queue is empty, the optimizing strategy takes over. La¨mmer’s control claims to provide intrinsic green waves and locally optimal service, which also results in system-wide optimal service.
An assumption of La¨mmer’s algorithm is the queuerepresentation of traffic flow: If a link i is served, vehicles can leave the link with a constant outflow rate qimax, which is assumed to be known. Additionally, queues are assumed to be non-spatially, i.e., the algorithm does not account for vehicles spilling back to upstream lanes or links. Demand is supposed to be manageable on average with the desired cycle time T to ensure stability.
Two sensors are used to predict the number of waiting vehicles
per link and time. One is positioned at the end of the link to detect
waiting and outflowing vehicles; the second one is located further
upstream to detect approaching vehicles. Assuming free flow
conditions at link i, one can estimate the length of the queue ni(t) at time
t and predict the expected queue length n^i(t; ) at a time > t.
While the estimation of queue lengths allows uncertainty, the mere
presence of a queue is definite.
The proposed RL traffic signal controller implements the true
online SARSA( ) algorithm [
When linear approximation is used, the Q-values Q(s; a) for each discrete action a are approximated as a weighted sum of a set of m basis functions 1; :::; m, as in Eq. 4, where is the vector of weights.
Q(s; a) =
m (s; a) = X i i(s; a) i=1
The Fourier series is one of the most commonly used continuous
function approximation methods, presenting solid theoretical
foundations. In [
When applying Fourier series to the RL setting, it is possible to drop the sin terms of the series5. Then, for a nth order Fourier approximation, each basis function i is defined as in Eq. 5, where ci = [c1; :::; ck] is a vector that attaches an integer coefficient c1 j k 2 [0; :::; n] to each feature in s, and k is the dimension of the state space.
i(s; a) =
0; (cos( ci s); if a = at if a 6= at The basis set of functions 1; :::; m is obtained by systematically varying these coefficients. Each coefficient determines the basis function’s frequency along its dimension. Furthermore, as we increase the order n of the approximation, more frequencies are used.
After the execution of action at, the weights are updated via gradient descent, following the true online SARSA( ) with linear function approximation update rule, as in Eq. 6, where = rt +
Q(st+1; at+1) Q(st; at) is the temporal difference error and Qold is a scalar temporary variable initialized with zero and set to Qold Q(st+1; at+1) after every step.
+ ( + Q
(Q
(6)
The eligibility traces vector e – which is used to address the credit assignment problem – is updated as in Eq. 7. Each weight update also takes into account previously visited states, which are credited accordingly to the values accumulated on the vector e. The parameter controls the decay of the eligibility traces at each time step. e e + (eT ) (7)
Given the base learning rate , each weight i is updated with the
scaled learning rate i = =jjcijj2, as proposed in [
In order to address the exploration–exploitation dilemma, the "greedy exploration strategy is used to choose actions: the action with the highest Q-value is selected with a probability of 1 " and a random action is selected with probability ".
Next we give the formulations that are specific to the domain of
signal control.
5 For detailed explanation, please see [
State Space In RL problems, the definition of state space strongly influences the agents’ behavior and performance. In traffic signal control, for instance, information related to the level of congestion in the approaching lanes is fundamental in order to appropriately choose the next active signal phase.
In the present setting, the agent observes a vector st 2 Rk at
each time step t. This vector partially represents the true state of the
controlled intersection and is defined as in Eq. 8, where E is the set of
all links of the intersection and L is the set of all approaching lanes,
i 2 f0; 1g is a binary feature active when i is the current selected
signal phase, 2 [0; 1] is the elapsed time of the current signal phase
divided by the maximal green time gmax, the density e 2 [0; 1] is
defined as the number of vehicles on link e 2 E divided by it’s
storage capacity and ql 2 [0; 1] is defined as the number of queued
vehicles on lane l 2 L divided by the storage capacity of the lane.
st = [ 1; :::; j j; ; q1; :::; qjLj; 1; :::;
jEj]
(8)
This state definition is inspired by [
As common in the literature, the proposed RL signal control is only called every three seconds. This means, that one time step for the traffic signal agent corresponds to three seconds of simulation. This reduces the complexity and the size of the state space, without significantly reducing the performance.
Action Space At each time step t (every three seconds), the traffic signal controller chooses a discrete action at 2 A. In our setting, the number of actions is equal to the number of possible signal phases, therefore, jAj = j j. There are two restrictions in the action selection: the agent can change the current active signal phase only if the elapsed time is greater or equal than the minimal green time gmin and keep it only if the elapsed time is less than the maximal green time gmax. These restrictions ensure the feasibility of the signal controller for real-world applications.
Reward After taking action at, the traffic signal controller
receives a scalar reward rt 2 R. As in [
On its turn, the cumulative vehicle delay D, for any time t, is computed as in Eq. 10, where Vt is the set of vehicles on incoming approaches and dtv is the delay of vehicle v at time t.
rt = Dat
Dat+1 Dt = X dtv v2Vt (9) (10) (4) (5)
This study focuses on a single intersection scenario with two set-ups,
each for a different demand level. In both, the RL control is compared
to a fixed-time signal control and rule-based traffic-responsive signal
control based on [
Traffic signals. The single intersection featured here (see Fig. 2) has four incoming approaches. In the horizontal direction, there is a dedicate left turning lane in each traffic approach, as well as three lanes for straight traffic. In the vertical direction, there are two lanes for straight traffic.
Traffic signals are grouped into three non-conflicting signal phases: Straight traffic in horizontal direction; left turning traffic in horizontal direction; vertical direction. While switching between two signal phases, there is an all red period of one second. The minimum green time for a signal phase is five seconds.
The fixed-time control that is used for comparison purposes is
optimized by Webster’s method [
In a second set-up, the demand is doubled during five time periods over the day of 2,000 seconds length each, in order to analyze the effect of fluctuating demand on the performance of the RL controller. To be more precise, in the time intervals [0, 2,000), [20,000, 22,000), [40,000, 42,000), [60,000, 62,000), and [80,000, 82,000) the average flow rates in horizontal direction are 3600 vehicles per hour going straight and 360 vehicles per hour going left per approach, whereas in vertical direction the average flow rate per approach is 1200 vehicles per hour. During the rest of the simulation, the average flow rates are the same as for the first scenario set-up.
In both set-ups, arrival rates are stochastic: vehicles are inserted as platoons with a platoon size that is exponentially distributed around an expected value of five. Also the time gap between vehicle platoons is exponentially distributed; its expected value is the platoon size divided by the average flow value. 4.2
The proposed method of the true online SARSA( ) with Fourier basis linear function approximation for signal control is applied to the single intersection scenario presented in the previous section and compared to RL signal control methods with other configurations (in Sect. 4.2.1, where our method is compared to a tabular variant), as well as to a fixed-time and a rule-based adaptive signal control approach (in Sect. 4.2.2).
Due to the stochastic arrival rates, results presented here are averaged over 20 runs with different random seeds, whereby the random seed influences the platoon structure of approaching vehicles (the average flow rate stays the same).
The shadowed area in the plots shown ahead depicted the standard deviation regarding average delay or total queue length, accordingly. The lines were smoothed with a moving average window of 300 seconds (i.e., 5 minutes) for better clarity. 4.2.1
Comparison with other RL signal control methods
Here we compare the proposed method with the traditional tabular
SARSA( ) [
Tabular vs. linear SARSA( ). In order to transform the continuous state space defined in Sect. 3.2 to a discrete state space for the tabular SARSA( ), the queue q and density attributes were discretized in equally distributed bins/intervals. The binary features i for each phase are already discrete and the feature has a finite number of possible values as the elapsed time increases in steps of five seconds; therefore, they did not need to be discretized.
In order to allow a fair comparison, the same discount factor, value of and exploration rate were used for both methods. The discount factor was set to = 0:95, = 0:1 and the exploration rate was set to " = 0:01 (this latter means that the agent is mostly taking the action with the highest Q-value, but still exploring with a fixed low chance). For the tabular SARSA( ), a learning rate of = 0:1 was used, while for true online SARSA( ) with linear function approximation, = 10 6 was used. These values are common in the literature and produced the best results for each method after extensive experimentation with different values.
As the state space in this case is large, and the number of Fourier basis functions grows exponentially on the number of dimensions of the state space, it is necessary to restrict the number of basis. We can meet this condition by placing constraints on the coefficient vectors ci. However, in this setting, adding coefficients with more than two non-zero elements did not improve the results. Thus, we further limited each coefficient vector ci to have at most two non-zero elements.
In Fig. 3 the average delay per vehicle at each second of the simulation is depicted for true online SARSA( ) with Fourier basis linear function approximation and for tabular SARSA( ) with 8 vs. 10 discretization bins of the q and features.
With 10 bins, the learning is very slow, as the number of discretization bins exponentially increases the size of the state space. Reducing the number of bins to 8 significantly speeds up the learning and reduces the delay. However, by reducing the number of bins, different states (in which different actions are optimal) are perceived as the same, thus leading to sub-optimal performance in the long run.
The usage of function approximation not only avoids the curse of dimensionality, but introduces generalization, i.e., when updating the 30 ) eh25 v / s (20 y a l e d15 e g re10 a v A 5 0
40000
Time of day (s)
Q-function after taking an action in a given state, similar states are also affected and have their Q-values changed. With that, the true online SARSA( ) with Fourier basis linear function approximation results in a much faster learning curve and overall lower delay values. Order of the Fourier basis approximation. Fig. 4 shows the impact that the value of the Fourier approximation order n has on the agent’s performance. As expected, the higher the value of n, the more accurate is the approximation of the Q-function. Changing the order from n = 3 to n = 9 results in a notable reduction on average delay; however, when n is sufficiently high (n = 7 and n = 9), there is no further improvement. For this reason, the Fourier approximation order is fixed to n = 7 for all following experiments.
State definition. Although the q (flow) features provide the traffic signal control agent with queue on each lane, the (density) features are also important, as they inform how many vehicles (that may be queued in the following seconds) there are on each link. Fig. 5 shows that, by removing the features from the state definition, the average delay increases. This difference might be even higher in scenarios with very high demand, where a high number of vehicles are moving and approaching the queues.
Reward definition. The definition of the reward function has a
high impact on the performance of the RL controller [
Time of day (s) 0 20000
40000 Time of day (s) 60000 80000 using change in cumulative delay as reward not only converges to a better performance, but produces a learning curve that decreases orders of magnitude faster. This result shows that the choice of which reward function to use is one of the most critical implementation decisions when designing a reinforcement learning controller. 4.2.2
Comparison with fixed-time and rule-based signals In this section, the true online SARSA( ) with Fourier basis linear function approximation is compared to fixed-time and rule-based adaptive signals in both set-ups of the single intersection scenario.
Fig. 7 shows the performance regarding average delay and total queue length for the first set-up (constant average flow rates). It can be seen that for this, somewhat homogeneous setup, RL and La¨mmer perform much better than Webster fixed-time control in terms of average delay and queue length. Also, they produce less variation in these measures, demonstrating robustness against traffic fluctuations. Note that for constant average flow rates, the fixed-time control used here (optimized by Webster’s method) is already quite good. RL is able to outperform the fixed scheme because it seems to be more stable regarding platoon variations. This can be seen in both plots in Fig 7, with the standard deviation (shown as the shadowed area in the plots) being lower for the RL.
Fig. 8 depicts the effects of more heterogeneous demand (second set-up), where the flow rates are doubled during five time periods over the day (see Sect. 4.1). The RL controller improves its performance from the second peak onwards, as in the first peak it was experiencing an overload situation for the first time. In this more difficult set-up, the difference in performance between RL and La¨mmer becomes less visible, with both presenting the same amount of queue length when there is low demand. Additionally, RL decreases the
20000
40000 Time of day (s) 60000 80000 (a) Average delay per vehicle during the simulation. 0 20000 60000
80000 40000
Time of day (s) (a) Average delay per vehicle during the simulation.
40000 Time of day (s) 60000 80000 (b) Total queue length during the simulation. queue lengths faster than La¨mmer after the peaks, which indicates that RL better adapts to different vehicle demands.
In summary, despite its slightly lower performance in the first setup, the RL control is able to handle overload situations and quickly reduces the queues afterwards. Recall that, contrarily to rule-based approaches, the RL control does not require domain knowledge. 5
In the present paper it was shown that specific techniques from RL can help to improve the performance of traffic signal control, and even outperform state-of-the-art rule-based adaptive signal control methods. It was argued that tabular RL methods may not be feasible due to the curse of dimensionality. When it is possible to employ them, it is often the case that they need long learning times before convergence in the case of realistic intersections with more than two signal phases and when a more complex definition of state is used. Recall that the results presented here show that including more features (i.e., not only queue but also density) played a significant role in the performance.
To address the curse of dimensionality, we used Fourier basis linear function approximation alongside the true online SARSA( ) algorithm, which to the authors best knowledge was not used for traffic signal control before. This method was implemented in MATSim and compared to optimal fixed-time and rule-based adaptive signal control in a single intersection scenario, in which the demand was varied. It could be seen that our approach outperforms the fixed-time controller and is competitive with the rule-based adaptive controller in terms of average delay and queue length. This kind of comparison
40000 Time of day (s) 60000 80000 (b) Total queue length during the simulation. with other than fixed-time approaches is rarely in the RL literature and is, therefore, a key feature of this work.
As a next step, the signal control based on true online SARSA( ) with Fourier basis linear function approximation will be applied to real-world scenarios using MATSim, and compared to the signal control approaches employed here. Given ongoing experimentation, the performance of the RL control looks very promising, which would emphasise its advantage in scenarios that are more challenging. On the one hand, with multiple intersections, one can assess the effects of the interaction of adjacent intersections as, e.g., when congestion spills back. On another perspective, this is a multiagent RL task that is known to be more challenging. Also, it will be investigated, whether the RL signal control can be further improved to handle situations of overload even better than the current implementation. Finally, since the issue of which reward scheme to use seems to be a key issue, a possible extension of this work could consider using the methods for designing a reward function that fits this domain best.
The authors thank Prof. Kai Nagel for his support and supervision during the internship of Lucas N. Alegre at TU Berlin. Thanks also to Dr. Ricardo Grunitzki for a previous version of the tabular Qlearning code. The authors are grateful to the Deutsche Forschungsgemeinschaft (DFG) for funding the project Optimization and network wide analysis of traffic signal control, as well as to the Brazilian Research Council (grant no. 307215/2017-2 for Ana Bazzan).