Reinforcement Learning (RL) has been extensively used in Urban Tra c Control (UTC) optimization due its capability to learn the dynamics of complex problems from interactions with the environment. Recent advances in Deep Reinforcement Learning (DRL) have opened up the possibilities for extending this work to more complex situations due to it overcoming the curse of dimensionality resulting from the exponential growth of the state and action spaces when incorporating ne-grained information. DRL has been shown to work very well for UTC on a single intersection, however, due to large training times, multi-junction implementations have been limited to training a single agent and replicating behaviour to other junctions, assuming homogeneity of all agents. This study proposes the usage of Independent Deep Q-Network (IDQN) to train multiple heterogeneous agents, which is a more realistic scenario given heterogeneity of junction layouts in the city. We use Dueling Double Deep Q-Networks (DDDQNs) with prioritized experience replay to train each individual agent separately for its own conditions. We enrich this approach with ngerprinting to disambiguate the age of the data sampled from the replay memory to mitigate non-stationarity e ects resulting from other agents a ecting the environment. Our IDQN approach is evaluated on three connected heterogeneous junctions in low and high tra c conditions, implementing di erent combinations of standard and prioritized experience replay and ngerprinting. Results show that IDQN is suitable approach to optimization in heterogeneous UTC with the best performance achieved by the combination of IDQN with prioritized experience replay but without ngerprinting.
Tra c congestion is often caused by an ine cient control of tra c lights on
intersections, i.e., settings not su ciently adapted to particular set of conditions.
In recent years several AI-based approaches have been investigated in order
to optimize tra c ow in junctions. The most promising technique has been
Reinforcement Learning (RL) due to its capacity to learn the dynamics of
complex problems without any human intervention. Di erent RL implementations
have been applied in Urban Tra c Control (UTC) [
This paper proposes a solution for heterogeneous multi-junction UTC scenario. Our approach is based on the Independent Deep Q-Network (IDQN) to achieve learning on multiple agents, with each agent using Dueling Double Deep Q-Network (DDDQN) enriched with ngerprinting to mitigate non-stationarity present in multi-agent environment. We evaluate the approach in widely used open source tra c simulator SUMO, and show it can successfully optimize the tra c ows on three heterogeneous junctions.
The rest of this paper is organized as follows: Section 2 reviews other work in DRL in UTC. Chapter 3 presents the techniques our approach is based on as well as the design speci cs of our proposed IDQN technique. Chapter 4 presents the simulation environment, experiment design, results and their analysis, while Section 5 concludes the paper discussing avenues for future work. 2
RL has been extensively applied in UTC [
This paper proposes the usage of DRL to deal with the curse of dimensionality, that traditional RL approaches encounter, by using Neural Networks. To train multiple heterogeneous agents, it uses Independent Q-Learning (IQL), where each agent learns independently and simultaneously its own policy, treating other agents as part of the environment. However, the environment becomes nonstationary from the point of view of each agent, as it involves the interaction with other agents who are themselves learning at the same time, ruling out any convergence guarantees. The technique we used is Dueling Double Deep Q-Networks (DDDQN), which relies in a component called experience replay memory in order to stabilize and improve the learning. (We have used Dueling Networks, Double DQN and Prioritized Experience Replay to improve the training over standard DQN). However, experience replay technique is incompatible with non-stationary environments. In order to combine the experience replay memory and IQL, we used a technique of ngerprinting which stabilizes the memory against the non-stationarity. This ngerprint disambiguates the age of the data sampled from the replay memory.
In this section we describe all the techniques underlying our approach. We then detail all RL components in our implementation, namely the design of the state space, action space, reward function, and deep neural network architecture. 3.1
Reinforcement learning (RL) learns optimal actions for speci c environment
conditions by trial-and-error learning to maximize the long term reward signal [
At each time step t, the agent perceives a state st in state space S from
which it selects an action at in the action space A by following a policy . The
agent receives a reward rt when it transitions to the state st+1 according to the
environment dynamics, the reward function R(st, at, st+1) and the transition
function T(st, at, st+1). Discount factor 2 [
RL can be either model-based or model-free (where the transition and the reward functions are unknown). The most common model-free technique is QLearning, where RL agents learn Q-values which are functions of state-action pair that returns a real value: Q: S x A ! R. Thus, the policy is represented as: (1) (2) (s) = arg max Q(s; a)
a2A
where the Q-value can be learned by using Q-learning updates [
In situations with a large state and action spaces it is unfeasible to learn
Q value estimates for each state and action pair independently as in standard
tabular Q-Learning. Therefore, DRL models the components of RL with deep
neural networks. There are multiple variations and extensions of the basic DRL
model, so in the following subsections we describe the methods our approach
utilizes to develop DRL algorithm applicable in heterogeneous UTC scenarios.
Deep Q Networks [
DQN parameterizes an approximate value function Q(s, a; i) using Convolutional Neural Networks, where i are the weights of the network at iteration i. The experience replay stores the agent's experiences et = (st, at, rt, st+1) at each time step t in a dataset Dt = e1,,et pooled over many episodes into a replay memory. Then, mini batches of experience drawn uniformly at random from the dataset (s, a, r, s) U(D) are applied as Q-updates during the training. The Q-learning update at iteration i follows the loss function:
Li( i) = E(s;a;r;s) U(D) r + max Q s0; a0; i a0
Q (s; a; i)
2
(3)
(4)
(5)
where i are the Q-network parameters at iteration i and i are the target
network parameters. The target network parameters are updated with the
Qnetwork parameters every C steps and are held xed between individual updates.
Double DQN The max operator in standard Q-learning and DQN uses the
same values both to select and to evaluate an action, which produces likely
to select overestimated values, resulting in overoptimistic value estimates. To
prevent this, Double Q-learning decouples the selection and the evaluation [
For DQN architectures is not desired to fully decouple the target as in [
Q(st+1; arg max Q(st+1; a; t); i )
a
Prioritized Experience Replay [
Rt+1 + t+1 max Q s0; a0; i a0
Q (s; a; i) !
Where ! is a hyper-parameter that determines the pattern of the distribution. New transitions are pushed into the replay bu er memory with maximum priority, providing a bias towards recent transitions.
Dueling Network A dueling network is a technique proposed by [
Q(s; a; ; ; ) = V (s; ; ) +
A (s; a; ; ) 1
X A (s; a; ; )
jAj a0
!
(6)
Multi-agent learning: Independent DQN In a multi-agent setting, multiple
agents can collaborate directly by exchanging Q-values or jointly deciding on
actions, or can operate independently in the shared environment, such as in
the case of Independent Q-Learning (IQL) [
Fingerprinting in IQL A key component of DQN is the experience replay
memory. Unfortunately, the combination of experience replay with IQL is
problematic because the non-stationarity introduced by IQL results in data in
experience replay memory no longer indicating the current dynamics in which the
agent is learning. To address this issue, [
In our approach, the state is a image-like representation of the current state
of the simulator environment (Figure 1a), similar to the concept used in [
The locations are calculated by mapping the continuous space of the simulated environment into a discretized environment by creating a grid with cells of size C. The matrix P is a binary matrix where one indicates the presence of a vehicle and zero the absence of a vehicle (Figure 1b). The matrix S indicates the (a) Simulation Environment State speed of the vehicle in the same cell position where a vehicle was calculated to be located in the matrix P (Figure 1c). The speed is represented as a percentage of the maximum allowed speed that it is computed by dividing the current vehicle's speed by the maximum allowed speed.
Additionally, a ngerprint is de ned as: Let -a be the other agents of agent a, such that we can include the importance weights of the prioritized experience replay and the TD-Errors vectors sampled from the other agents into the observation function as a and TD a respectively. Given that, the new observation function is O'(s) = f O(s), a, TD a g. They are included in a matrix F. The action space varies depending of the structure of the intersection. For example, in a four road intersection the action space is de ned as A = fNS, EW, NST; EWTg where NS stands for turning green North-South roads, EW stands for turning green East-West roads, NST stands for turning green North-South right turning, and EWT stands for turning green East-West right turning.
The duration of each phase is 1 time step, but at each time step the phase can be extended. Additional yellow phase is added during a xed period of 3 time steps when the previous action is di erent than the current chosen action. This middle yellow phase reduces the risk of collisions. Let wi;t be the ith vehicle's waiting time at time step t, and Wt the total cumulative waiting time for all the vehicles in the observation scope of the road network at time step t as shows in equation 7. The reward function is formulated in equation 8. Agent receives a positive reward from a range (0.0, 1.0] where the agent's reward loses are proportional to the cumulative waiting time at time step t. Thus, the agent must keep short waiting time in order to receive higher scores.
Wt =
X wi;t i (7) rt = ( W1:0t ; if cummulative waiting time Wt is greater than 0 1:0; otherwise (8)
The Figure 2 illustrates the Deep Neural Network which is the same as used
in [
In this section we present an evaluation of IDQN as a proposed solution for
multi-agent DRL for heterogeneous agents in tra c light control using the tra c
simulator SUMO [
We run the test in the network layout shown in Figure 3, which consists of three heterogeneous junctions.
Table 1 lists the hyper-parameters used. Every episode corresponds to 1 hour
of simulation time which is 3600 time steps, where every time step is 1 simulated
second. The values were rst chosen from a combination of [
We select two metrics that have been used in several DRL studies for UTC. Every metric is taken per episode. Cumulative Reward is the sum of rewards rt taken on every time step t until the episode is nished. The Average Waiting Time is the sum of all Wt divided by the number of time steps in the episode. SUMO de nes the waiting time for a vehicle as the time (in seconds) spent with a speed below 0.1 m/s since the last time it was faster than 0.1 m/s.
We implement and evaluate the following combinations of IDQN, experience replay, and ngerprinting, to assess impact of each component on the performance: { IDQN without experience replay (PEMR Disabled), therefore the agent cannot store experiences. { IDQN with prioritized experience replay (PEMR). { IDQN with prioritized experience replay and ngerprint (PEMR + FP). This is the proposed IDQN technique with the ngerprint to disambiguate the age of experience replays.
We evaluate the approach against the xed time (FT) baseline, in which order of the phases is xed and precon gured; phases are actuated in a round robin manner.
Every technique is tested in two tra c conditions. A low tra c load which consists of 1300 to 1600 cars per episode. With e cient tra c control the scenario is expected to result in smooth tra c ow, but any control ine ciencies will result in longer queues. And a high tra c load which consists of 1900 to 2500 cars per episode. This scenario represents the tra c load in peak times. 4.2
The Figure 4 presents the results of the experiments executed in low and high tra c load respectively.
(a) Low Tra c: Cumulative Rewards
(b) Low Tra c: Average Waiting Time (c) High Tra c: Cumulative Rewards
(d) High Tra c: Average Waiting Time
As can be seen from the Figure 4a, in low tra c conditions, FT gets a constant reward range that varies extremely low around 50 due to it not adapting its performance to the tra c conditions. PEMR Disabled also gets very low rewards, even worse than the FT, as it never successfully learns to adapt. Therefore, disabling the experience replay is not useful for our problem. Finally, PEMR and PEMR + FP, show identical performance, getting 400% bigger rewards than FT. They both learn very well in spite of the non-stationarity, increasing the rewards from around 25-100 in the exploration phase up to around 200-250 in the exploitation phase. They reach their optimal point at 300 episodes, where they get to keep a stable rewarding. Based on this similarity of results, we deduce that the ngerprint in low tra c loads is not helping. As illustrated in gure 4c, in high tra c conditions, FT actually performs well in terms of the reward, and in line with PEMR, with both outperforming PEMR Disabled and PEMR + FP by around 25%. We conclude that the extra layer of the ngerprint reduces the performance of the technique under intense tra c loads. Moreover, none of the DRL technique learn su ciently over the episodes. These results indicate that the agents need longer training time for such a high load.
The Figure 4b presents the waiting time for low tra c. FT waiting time follows the same pattern as its rewards. PEMR Disabled produces extremely high waiting times. Similarly to their performance with respect to rewards, PEMR and PEMR + FP get similar performance, with very low waiting times which are approximately 300% less than FT. From these results we can con rm that the ngerprinting is not helping, as observed when analyzing the rewards. In high tra c load, the results for waiting time follow the same pattern as for the rewards in high load: PEMR + FP slightly outperforms PEMR. Overall, no DRL approach learns a good performance for high load in the amount of time given for the training.
To further analyse the results, we have looked into unexpectedly bad performance of ngerprinting. One possibility is that the ngerprint might not be able to improve the performance as prioritized experience replay is already good enough to deal with the non-stationarity without adding ngerprints. To test this hypothesis, we run an experiment using only normal experience replay (EMR). The gure 5 shows this additional experiment which compares EMR against PEMR + FP. Both techniques learn well, but PEMR + FP obtains higher rewards outperforming ERM by around 45% in the highest point of PEMR + FP. Figure 5b illustrates how they get a similar performance in waiting time, but EMR is more stable than PEMR + FP by not producing peeks. We conclude the Prioritized Experience Replay helps to deal with the non-stationarity by getting bigger rewards, which indicates that PEMR has better performance than EMR. These results prove that PEMR can be good enough to deal with the non-stationarity. Potentially PEMR + FP could be improved by selecting a better ngerprint, but we leave this for future work. (a) Cumulative Rewards per Episode
(b) Average Waiting Time per Episode
Fig. 5: Low Tra c IDQN Experiments with Standard ERM
This paper presented IDQN as the rst approach in literature to addresses heterogeneous multi-agent DRL in UTC. We evaluated IDQN's performance with di erent con gurations in low and high tra c loads. Our experiments showed that IDQN is a suitable techniques for heterogeneous multi-agent UTC environments which can deal with the non-stationarity. The best results were obtained in the low tra c load. The high tra c load requires further investigation, by either ne-tuning hyper-parameters or allowing for the longer training time. We demonstrated that the experience replay is mandatory to learn e ciently, but that the ngerprint we chose did not enhance the prioritized experience replay. Therefore, further investigation is needed to evaluate if di erent ngerprints could improve the performance. Further, our technique should be evaluated against standard RL approaches, to investigate if more ne-grained sensor data enabled by the use of DRL approaches improves the performance over standard approaches. 6
This publication has emanated from research supported in part by a research grant from Science Foundation Ireland (SFI) under Grant Number 13/RC/2077 and 16/SP/3804