<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta>
      <journal-title-group>
        <journal-title>Workshop Agents in Trafic and Transportation, July</journal-title>
      </journal-title-group>
    </journal-meta>
    <article-meta>
      <title-group>
        <article-title>Multiagent Reinforcement Learning for Trafic Signal Control: a k-Nearest Neighbors Based Approach</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Vicente N. de Almeida</string-name>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Ana L. C . Bazzan</string-name>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Monireh Abdoos</string-name>
          <xref ref-type="aff" rid="aff1">1</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Computer Science, Universidade Federal do Rio Grande do Sul (UFRGS)</institution>
          ,
          <addr-line>Porto Alegre, RS</addr-line>
          ,
          <country country="BR">Brazil</country>
        </aff>
        <aff id="aff1">
          <label>1</label>
          <institution>Faculty of Computer Science and Engineering, Shahid Beheshti University</institution>
          ,
          <addr-line>Tehran</addr-line>
          ,
          <country country="IR">Iran</country>
        </aff>
      </contrib-group>
      <pub-date>
        <year>2022</year>
      </pub-date>
      <volume>25</volume>
      <issue>2022</issue>
      <fpage>0000</fpage>
      <lpage>0002</lpage>
      <abstract>
        <p>The increasing demand for mobility in our society poses various challenges to trafic engineering, computer science in general, and artificial intelligence in particular. As it is often the case, it is not possible to increase the capacity of road networks, therefore a more eficient use of the available transportation infrastructure is required. This relates closely to multiagent systems and to multiagent reinforcement learning, as many problems in trafic management and control are inherently distributed. However, one of the main challenges of this domain is that the state space is large and continuous, which makes it dificult to properly discretize states and also causes many RL algorithms to converge more slowly. To address these issues, a multiagent system with agents learning independently via a temporal diference learning algorithm based on k-nearest neighbors is presented as an option to control trafic signals in real-time. Our results show that the proposed method is both efective (reduces the average waiting time of vehicles in a trafic network) and eficient (the learning task is significantly accelerated), when compared to a baseline reported in the literature.</p>
      </abstract>
      <kwd-group>
        <kwd>eol&gt;multiagent reinforcement learning</kwd>
        <kwd>k-nearest neighbors</kwd>
        <kwd>trafic signal control</kwd>
      </kwd-group>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>1. Introduction</title>
      <p>Trafic congestion is a phenomenon caused by too many vehicles trying to use the same
infrastructure at the same time. The consequences are well-known: air pollution, decrease in
speed, delays, opportunity costs, etc. The increase in transportation demand can be met by
providing additional capacity. However, this might not be economically or socially attainable or
feasible. Thus, optimizing the use of the existing infrastructure is key. One way to accomplish
this is by control techniques, notably the adaptive control of trafic signal controllers. A major
challenge of optimizing such a controller is that the problem is very constrained, since minimum
and maximum green times need to be observed, and the control policy needs to be fair to all
trafic directions, even the side ones (in order to deal with starvation).</p>
      <p>Several approaches to adaptive control exist (see, e.g., [1]). However, those more
sophisticated ones can be applied only to a handful of intersections. Therefore, approaches based
on reinforcement learning (RL) are gaining popularity. In these approaches, learning agents
are normally in charge of controlling the signals at a single intersection, in a distributed and
decentralized way. We remark that for centralized approaches, where there is a single controller
in charge of computing optimal actions for the whole set of intersections, deep learning is more
popular. However, due to robustness issues (central point of failure, communication failures),
it is desirable to avoid centralized solutions. Besides, centralized approaches assume a central
entity in charge of the control, which needs to collect all information from all intersections,
and needs to determine an action for each controller at the intersections, thus violating the
autonomy of the individual controllers. That being the case, in this paper we deal with multiple
agents (signal controllers) learning in a distributed way.</p>
      <p>One important aspect of such learning task is that trafic signal control is a highly non-local
phenomenon, i.e., it is afected by actions of other agents. This is what makes multiagent
RL much more challenging than single agent RL. Another challenge is the fact that the state
space is very large (thus RL algorithms like Q-learning converge more slowly) and continuous
(appropriately discretizing continuous states is a dificult problem).</p>
      <p>That being said, alternatives to tackle these matters, like function approximation, come with
some drawbacks. They make the learning harder to comprehend, and generally require that
the agents gather a large amount of data to be able to successfully generalize and apply their
collected experiences.</p>
      <p>To tackle large continuous state spaces in an eficient way, this paper proposes the use of a
method that avoids both the need for state discretization and the usage of function approximation,
by using a temporal diference learning algorithm based on k-nearest neighbors (k-NN) [ 2, 3].
This algorithm estimates Q-values by calculating a weighted average of the Q-values of the
 closest previously visited states. It is applied to trafic signal control using a multiagent
approach, in which each trafic controller (one per intersection) learns independently.</p>
      <p>To our best knowledge, a temporal diference learning approach based on k-nearest neighbors
has not been used for trafic signal control. Also, in our experiments, we deal with changes in
trafic flows, which has rarely been discussed in the trafic signal control with RL literature.</p>
      <p>The reader can find details of the proposed method and of how it is applied to trafic signal
control in Section 4. In Section 3 we present the related literature, and in Section 2 we discuss
the underlying concepts such as RL and trafic signal control. Our results are presented and
discussed in Section 5, followed by a conclusion and a discussion on future research lines.</p>
    </sec>
    <sec id="sec-2">
      <title>2. Background</title>
      <p>This section briefly presents underlying concepts on RL and on trafic signal control.</p>
      <sec id="sec-2-1">
        <title>2.1. Reinforcement Learning</title>
        <p>In RL, an agent learns how to act in an environment interacting and receiving a feedback signal
(reward) that measures how its action has afected the environment. The agent does not a
priori know how its actions afect the environment, hence it has to learn this by trial and error
(in an exploration phase). However, the agent should not only explore; in order to maximize
the rewards of its action, it also has to exploit the gained knowledge. Thus, there must be an
exploration-exploitation strategy that is to be followed by the agent. One of these strategies
is -greedy, where an action is randomly chosen (exploration) with a probability , or, with
probability 1-, the best known action is chosen, i.e., the one with the highest Q-value so far
(exploitation). In the exploitation phase, at each interaction, it is assumed that the agent has
sensors to determine its current state and can then decide on an action. The reward is then
used to update its policy, i.e., a mapping from states to actions. This policy can be generated or
computed in several ways.</p>
        <p>For the sake of the present discussion, we concentrate on a model-free, of-policy algorithm
called Q-learning [4], which estimates so-called Q-values using a table to store the experienced
values of performing a given action when in a given state. Hence Q-learning is a tabular method,
where the state space and the action space need to be discretized.</p>
        <p>In RL, the learning task is usually formulated as a Markov decision process (MDP), composed
by the sets of states and actions, a transition function, and a reward function. Since the transition
and the reward functions are unknown to the agent, its task is exactly to learn them, or at least
a model for them.</p>
        <p>
          The value of a state  and action  at time  is updated based on Eq. (
          <xref ref-type="bibr" rid="ref1">1</xref>
          ), where  ∈ [0, 1]
is the learning rate,  ∈ [0, 1] is the discount factor, +1 is the next state and  is the reward
received when the agent moves from  to +1 after selecting action  in state .
(, ) ←
(, ) +  ( +  max((+1, )) − (, ))

(
          <xref ref-type="bibr" rid="ref1">1</xref>
          )
        </p>
        <p>When there are multiple agents interacting in a common environment, the RL task (thus,
multiagent RL) is inherently more complex than that regarding single-agent RL, because agents’
actions are highly coupled and agents are trying to adapt to other agents that are also learning.
Besides, several convergence guarantees no longer hold. However, in many real-world problems,
where the control is decentralized, there is no way to avoid a multiagent RL formulation, as for
instance the scenario we deal with in the present paper, namely control of trafic signals, whose
basic concepts we briefly review next.</p>
      </sec>
      <sec id="sec-2-2">
        <title>2.2. RL-Based Trafic Signal Control</title>
        <p>Besides safety and other issues, one aim of a trafic signal controller is to decide on a split of
green times among the various phases that were designed to deal with geometry and flow issues
at an intersection. This can be done in several ways (for more details, please see a textbook
such as [5]). In this paper, the controller is given a set of phases and has to decide which one
will receive right of way (green light).</p>
        <p>A phase is defined as a group of non-conflicting movements (e.g., flow in two opposite trafic
directions) that can have a green light at the same time without conflict.</p>
        <p>In its simplest form, the control is based on fixed times, whose split of the green time among
the various phases can be computed based on historical data on trafic flow, if available. The
problem with this approach is that it cannot adapt to changes in the trafic demand. This may
lead to an increase in the waiting time. To mitigate this problem, it is possible to use an adaptive
scheme and thus give priority to lanes with longer queues (or other measures of performance).
Adaptive approaches based on RL were developed, as we discuss at the beginning of the next
section.</p>
      </sec>
    </sec>
    <sec id="sec-3">
      <title>3. Related Work</title>
      <p>In the last two decades there has been a large body of work that proposes the use of RL for
trafic signal control. Given the extension and diversity of such a body of work, it is outside the
scope of the present paper to review them. Readers are directed to surveys such as [6, 7, 8, 9].
In any case, those surveys show that there has already been a significant contribution of RL
techniques to control trafic signals. However, issues of scalability and performance remain
open, especially if tabular methods are used, such as the aforementioned Q-learning. Tabular
methods require discretization of the state space. The finer such discretization is, the poorer
the computational performance of the learning task, since agents need to visit an increasing
number of states.</p>
      <p>Therefore, the remaining of this section discusses alternative ways to tackle these issues.</p>
      <p>A first line of research does use tabular methods, with various levels of discretization of the
state space, thus depicting diferent levels of performance of the learning task. In this class,
well-known works include [10, 11, 12, 13], among others.</p>
      <p>A second class of works avoids using tabular methods such as Q-learning. Rather, they propose
the use of function approximation. For instance, [14] uses tile coding. Recently, many studies
have used deep neural networks to approximate the -function (e.g., DQN [15]). However,
non-linear function approximation is known to diverge in multiple cases [16, 17]. In order to
address these shortcomings, [18] proposed the use of linear function approximation, which has
guaranteed convergence and error bounds.</p>
      <p>A third research line employs clustering methods together with some sort of RL aproach in
order to tackle the large or continuous state space. However, to the best of our knowledge, there
has been no attempt to employ clustering-based methods to trafic signal control. Applications
span over obstacle avoidance [19]; games such as Atari [20]; and for partitioning the state space
in general [21]. Also worth mentioning are works that employ hierarchical clustering and/or
hierarchical RL for state abstraction or experience generalization, such as [22, 23, 24, 25, 26, 27,
28, 29, 30]. Again, these works cover applications other than trafic signal control and deal with
single agent scenarios.</p>
      <p>Finally, another way to tackle the issues that arise from large and continuous state spaces
appeared in [2, 3], in which a temporal diference learning algorithm based on k-nearest neighbors
was presented. RL approaches based on this technique have been used in diferent domains,
like robot motion control [31] and video streaming [32]. However, to our best knowledge, its
application in trafic signal control, as we do here, is novel. Moreover, as we tackle a network of
signal controllers, our work deals with multiagent reinforcement learning. Even if the agents
learn independently, because a multiagent setting is ineherently non-stationary, this makes the
learning task much more challenging. More details about these challenges are discussed in [6].</p>
      <p>In a nutshell, our paper intends to help fill a gap in the trafic signal control by means of RL.
We accomplish this by applying a method that avoids the need of discretizing continuous states,
and also without requiring a function approximation technique (which makes the learning
potentially more dificult to manage and understand [17]).</p>
    </sec>
    <sec id="sec-4">
      <title>4. Materials and Methods</title>
      <p>In many real world problems, the state space that is associated with an RL task is large and
continuous. For example, this is the case when the task is to control a trafic signal, where the
state refers to queue length, density of vehicles, or a combination of both (please refer to [8] for
a discussion about popular formulations of the state space for this particular domain). Therefore,
the quality of the learning task depends on how the state is discretized. Also, learning agents
must be able to efectively adapt to a changing environment.</p>
      <p>This section explains the approach we employ in order to address the just mentioned issues
related to how to deal with a continuous state space. Also, we discuss how the method was
applied to controlling a network of trafic signals.</p>
      <sec id="sec-4-1">
        <title>4.1. Temporal Diference Learning Based on k-Nearest Neighbors</title>
        <p>Essentially, the method estimates the Q-values of the current state by calculating the weighted
average of the Q-value estimates of the  nearest states, based on the euclidean distance metric.
The closer a neighbor state is, the greater the impact its Q-value estimates have on the Q-values
of the current state. It then selects an action based on an exploration strategy like -greedy,
transitions to a new state and receives a reward. Subsequently, it calculates a temporal diference
(TD) error based on the reward and the expected value of the last and new state, and uses this
error to update the Q-value estimates of all the  nearest states that contributed to estimate the
Q-values of the previous state.</p>
        <sec id="sec-4-1-1">
          <title>4.1.1. Estimating Q-Values</title>
          <p>
            Each dimension of the state space could be of a diferent order of magnitude. When measuring
the Euclidean distance between two states, dimensions of a greater order of magnitude could
introduce a selection bias, and impact more heavily the value of the distance than dimensions
of a smaller order of magnitude. To prevent this bias, when a state  is observed at time step ,
it is normalized, according to Eq. (
            <xref ref-type="bibr" rid="ref2">2</xref>
            ), where  and  denote the lower and upper bounds of
the state space, respectively.
          </p>
          <p>^ = 2 · ( − −  ) − 1</p>
          <p>
            The agent keeps a record of each visited state and an estimate of the Q-values for each of
these states. After normalizing the observed state , the  nearest previously visited states
according to the euclidean distance metric are selected, in order to determine the k-nearest
neighbors set. A weight is then calculated for each state in the set, according to Eq. (
            <xref ref-type="bibr" rid="ref3">3</xref>
            ), where
 and  represent the weight of the ℎ nearest state and the euclidean distance between 
and the ℎ nearest state, respectively, and  represents the k-nearest neighbors set.
          </p>
          <p>
            1
 = 1 + 2 , ∀ ∈ 
(
            <xref ref-type="bibr" rid="ref2">2</xref>
            )
(
            <xref ref-type="bibr" rid="ref3">3</xref>
            )
          </p>
          <p>
            The Q-value of a state-action pair is determined by the estimate of an expected value, in which
the probabilities of each state in the  set are given by Eq. (
            <xref ref-type="bibr" rid="ref4">4</xref>
            ), where () is the probability of
the ℎ nearest state in the  set.
          </p>
          <p>() = ∑︀∈  , ∀ ∈ 
(, ) = ∑︁ ()(, )</p>
          <p>
            For each action , the Q-value of the state-action pair (, ) is then determined according to
an estimate of expected value using the probabilities and the current estimates of the Q-values
of each state in the k-nearest neighbors set, according to Eq. (
            <xref ref-type="bibr" rid="ref5">5</xref>
            ).
          </p>
          <p>∈</p>
          <p>This way, the method avoids both state discretization and function approximation, as it
estimates the Q-values of the current state by calculating the weighted average of the Q-values
of the nearest previously visited states.</p>
        </sec>
        <sec id="sec-4-1-2">
          <title>4.1.2. Action Selection and Updating Q-Values</title>
          <p>
            Having the expected value of each action for the current state , an exploration strategy, such
as -greedy, is used to select an action . After taking the selected action, the agent transitions
to a new state +1 and receives a reward . In order for learning to occur, the agent estimates
the expected value of taking each possible action in the next state, +1, via the k-NN approach
explained in Section 4.1.1 (using Eq. (
            <xref ref-type="bibr" rid="ref2">2</xref>
            ), Eq. (
            <xref ref-type="bibr" rid="ref3">3</xref>
            ), Eq. (
            <xref ref-type="bibr" rid="ref4">4</xref>
            ) and Eq. (
            <xref ref-type="bibr" rid="ref5">5</xref>
            ) on +1), and calculates the
TD error  (which is the basic update rule of a TD learning method, obtained by measuring
the diference between the estimated value of a state or a state-action pair, and the improved
estimate obtained after gaining more experience), using Eq. (
            <xref ref-type="bibr" rid="ref6">6</xref>
            ).
          </p>
          <p>
            =  +  max((+1, )) − (, )

(
            <xref ref-type="bibr" rid="ref6">6</xref>
            )
          </p>
          <p>
            The Q-value estimate for taking the action  in each state in the k-nearest neighbors set is
then updated using Eq. (
            <xref ref-type="bibr" rid="ref7">7</xref>
            ).
          </p>
          <p>
            (, ) ←
(, ) +  () , ∀ ∈ 
(
            <xref ref-type="bibr" rid="ref7">7</xref>
            )
          </p>
          <p>A pseudocode for the algorithm is presented in Algorithm 1.</p>
        </sec>
      </sec>
      <sec id="sec-4-2">
        <title>4.2. Scenario and Formulation of the RL task</title>
        <p>As aforementioned, our goal is to present a multiagent RL approach based on k-nearest neighbors
as an alternative to deal with large and continuous state spaces in trafic signal control. To
measure the performance of our approach, we use a scenario that contains a network of trafic
signal controllers (or agents), introduced in [33]. Each of these agents independently acts and
learns using the k-NN method.</p>
        <p>
          The scenario selected is especially interesting and non-trivial because, besides containing
a network of intersections, it considers changes in the environment, i.e., changes in trafic
(
          <xref ref-type="bibr" rid="ref4">4</xref>
          )
(
          <xref ref-type="bibr" rid="ref5">5</xref>
          )
contexts. We stress that such changes are rarely addressed in RL-based methods for signal
control. Further, we compare our results to those reported in [33], in which a tabular method
(Q-learning) with a fixed discretization scheme was used, which included diferent features.
        </p>
        <p>In short, while [33] has reported results that outperformed other baselines in a non-trivial
environment (trafic situation changes), our aim here is to show that a better way of treating
the continuous state space may pay of.</p>
        <p>Our experiments were performed using a microscopic trafic simulator, namely SUMO [ 34]
(Simulation of Urban MObility). The scenario is a 4x4 trafic signal grid, with 16 trafic signal
controllers (one in each intersection), which are the learning agents. In this scenario, agents are
homogeneous, i.e., they have the same set of available actions.</p>
        <p>Figure 1 shows the trafic grid network’s topology. We defer the details about the trip demands;
these are discussed in Section 4.3, where we show how the various flows of vehicles change
along the simulation time.</p>
        <p>Every link has 150 m in length, two lanes and is one-way. There are four vertical (B1 → B6,
C1 → C6, D1 → D6, E1 → E6) and four horizontal (A2 → F2, A3 → F3, A4 → F4, A5 → F5)
Origin-Destination (OD) pairs. A vehicle is inserted in an origin node, and is removed from
the simulation in a destination node. Vehicles go in the North-South (N-S) direction in vertical
links, and in the West-East (W-E) direction in horizontal links.</p>
        <p>Trafic signals in our scenario have a minimum and maximum time they must remain green.
They are referred to as minGreenTime and maxGreenTime, respectively.</p>
        <p>We compare our RL method to a baseline (from [33]). As is often with RL problems, we use a
multiagent MDP (MMDP) to formalize our trafic signal control problem. Thus, besides the set
of agents, we need to define the other sets and functions that compose the MDP. In the next
sections we define the state space, the action space, and the reward function.</p>
        <sec id="sec-4-2-1">
          <title>4.2.1. State Space</title>
          <p>
            At each time step  (which corresponds to five seconds of real-life trafic dynamics), each agent
observes a vector , which describes the current state of the respective intersection. We use the
default state definition in [ 35], shown in Eq. (
            <xref ref-type="bibr" rid="ref8">8</xref>
            ), where  1 ∈ {0, 1} and  2 ∈ {0, 1} are binary
variables that indicate the current active green phase (see Section 2.2 for a description about
phases).  ∈ {0, 1} is a binary variable that indicates whether or not the current green phase
has been active for more than minGreenTime. L is the set of all incoming lanes. The density
Δ ∈ [0, 1] is defined as the number of vehicles in the incoming lane  ∈  divided by the total
capacity of the lane.  ∈ [0, 1] is defined as the number of queued vehicles in the incoming
lane  ∈  divided by the total capacity of the lane. A vehicle is considered to be queued if its
speed is below 0.1 m/s.
          </p>
          <p>
            = [ 1,  2, , Δ1, ..., Δ||, 1, ..., []]
(
            <xref ref-type="bibr" rid="ref8">8</xref>
            )
          </p>
          <p>Note that although it is common in the literature that only one feature be used (i.e., either
density or queue), here we employ both as this was the case in [33], which we use as a baseline
for comparison.</p>
        </sec>
        <sec id="sec-4-2-2">
          <title>4.2.2. Action Space</title>
          <p>Each learning agent chooses a discrete action  at each time step . For our scenario, since all
intersections have two incoming links, there are two phases, so each agent has only two actions:
keep and change. The former keeps the current green signal active, while the latter switches
the current green light to another phase. The agents can only choose keep if the current green
phase has been active for less than maxGreenTime, and can only choose change if the current
green phase has been active for more than minGreenTime.</p>
        </sec>
        <sec id="sec-4-2-3">
          <title>4.2.3. Reward Function</title>
          <p>
            As with the state space, we also use the default reward function given in [33], which is the
cumulative vehicle delay, shown in Eq. (
            <xref ref-type="bibr" rid="ref9">9</xref>
            ), where  is the cumulative vehicle delay at the
intersection at time step .
          </p>
          <p>
            We define the cumulative vehicle delay at time step , , as being the sum of the waiting time
of all of the vehicles (a vehicle is waiting if its speed is less than 0.1 m/s) that are approaching
the intersection. This is calculated as in Eq. (
            <xref ref-type="bibr" rid="ref10">10</xref>
            ), where  is the set of incoming vehicles, and
 is the delay of vehicle  at time .
          </p>
          <p>=  − +1
 = ∑︁</p>
          <p>∈</p>
        </sec>
      </sec>
      <sec id="sec-4-3">
        <title>4.3. Changing the Demand Along the Simulation Horizon</title>
        <p>As mentioned, a particular challenge in the present work is that the demand changes during the
simulation time, i.e., the amount of vehicles traveling from a given origin to a given destination
changes from time to time. Following [33], we also denote these diferent situations by trafic
contexts or simply context, and refer to the grid depicted in Figure 1. There are two diferent
trafic contexts, which correspond to two diferent vehicle flow rates:
• Context 1 (NS = WE): one vehicle is inserted in all 8 Origin-Destination pairs every 3
seconds.
• Context 2 (NS &lt; WE): one vehicle is inserted every 6 seconds in the 4 OD pairs in the
North-South direction and one vehicle is inserted every 2 seconds in the 4 OD pairs in
the West-East direction.</p>
        <p>Each simulation runs for 80,000 seconds and switches contexts every 20,000 seconds; thus
there are three changes in context (Context 1 → Context 2 → Context 1 → Context 2).</p>
      </sec>
      <sec id="sec-4-4">
        <title>4.4. Signal Control and Learning Parameters</title>
        <p>The value used for minGreenTime was 10 seconds, and 50 seconds for maxGreenTime. Also,
as aforementioned, one simulation time step corresponds to five seconds of real-life trafic
dynamics, as in [33].</p>
        <p>We also kept the same parameter values that were used in that paper. Thus:  = 0.1,  = 0.99
and  = 0.05. Regarding the k-NN method,  = 200 was used. Several values for  were tested,
and 200 was selected because this brought the best results.</p>
        <p>
          (
          <xref ref-type="bibr" rid="ref9">9</xref>
          )
(
          <xref ref-type="bibr" rid="ref10">10</xref>
          )
        </p>
      </sec>
    </sec>
    <sec id="sec-5">
      <title>5. Results and Discussion</title>
      <p>Next we discuss the simulation results of our proposed method. To evaluate our approach,
we calculate the average waiting time of all vehicles, which is a metric commonly used in the
literature. As mentioned previously, a vehicle whose speed is less than 0.1 m/s is considered to
be waiting. Reducing the average waiting time of vehicles is an important objective for trafic
signal control, as it reduces vehicle queue sizes and improves trafic flow.</p>
      <p>Figure 2 shows the average waiting time (over all vehicles) for our method and the baseline,
over 20 repetitions, along the 80,000 seconds of simulated real-world trafic dynamics, which
represent 16,000 actions taken (since the agent takes an action every 5 seconds). The vehicle
lfow also changed at 20,000 seconds, 40,000 seconds and 60,000 seconds (as aforementioned,
the trafic contexts changed in the following manner: Context 1 → Context 2 → Context 1 →
Context 2).</p>
      <p>Comparing the proposed method with the baseline in [33], it is clear that our approach
outperforms the baseline, converging sooner. The first time the agents explore each of the two
contexts (from 0 to 20,000 seconds for Context 1, and from 20,000 seconds to 40,000 seconds for
Context 2), in both of them, the proposed method converged much faster than the baseline.</p>
      <p>In Context 1, the proposed method quickly finds an approximate best solution requiring
very little exploration, while the baseline takes a considerably greater amount of steps before
converging. This is the simplest context, since a vehicle is inserted every 3 seconds in all OD
pairs, so there is a symmetry to the trafic flow. The results for this context indicate that for
simpler scenarios, the approach based on k-NN is vastly superior, since it is able to rapidly
detect patterns within the agent’s dataset of experiences.</p>
      <p>Context 2 involves a more dificult vehicular flow, since vehicles are inserted unevenly (one
vehicle is inserted every 2 seconds in the 4 West-East OD pairs, and one vehicle is inserted
every 6 seconds in the 4 North-South OD pairs). Because more vehicles flow in the West-East
direction, larger queues are formed in that direction and the trafic controllers must adapt to
this new situation. As can be seen, both the baseline and the proposed method have a decline
in performance, as they are dealing with a context they never saw before, but our proposed
method quickly reduces the average waiting time, taking around 8,000 seconds (1,600 time
steps) in this new context to do so, while the baseline only reaches this level the second time
the context changes to Context 2.</p>
      <p>For the second half of the simulation (from 40,000 seconds to 80,000 seconds), the context
changes back to Context 1, and then changes back to Context 2. As can be seen, both methods
at this point have already approximately converged, and are operating at a similar level of
performance in terms of waiting time. However, an advantage of our method is that it shows
significantly less standard deviation in comparison to Q-learning.</p>
    </sec>
    <sec id="sec-6">
      <title>6. Conclusion and Future Work</title>
      <p>In this paper, a multiagent system with agents learning via a temporal diference learning
algorithm based on k-nearest neighbors was presented as an option to control trafic signals in
real-time. This approach seeks to solve the issues that arise when the state space is continuous
and thus, a poor discretization leads to poor performance. Or, rather, when the discretization is
ifne, but then leads to scalability issues. The goal here was to employ a method that could deal
with a continuous state space and still be eficient.</p>
      <p>By simultaneously avoiding the need for state discretization and the usage of function
approximation, the approach is able to somewhat circumvent significant issues that arise in
the application of RL for trafic signal control. This was shown by simulating the method in a
complex scenario that involved not only many trafic signals, but also changes in the flow of
vehicles (trafic contexts).</p>
      <p>In this scenario, a tabular method that includes more than one feature was used as a baseline
for comparison. Our results showed that our method outperformed the baseline; specifically, it
converges earlier to a situation in which the waiting time of vehicles is lower.</p>
      <p>To our best knowledge, this is the first time that a RL approach combined with k-nearest
neighbors was used for trafic signal control. Also, the scenario used involved changes in trafic
contexts, which has been rarely discussed in the literature.</p>
      <p>As a next step, the proposed method will be combined with an approach that incrementally
clusters the agent’s experiences and uses cluster fusion to share knowledge among agents in
order to improve even more the performance of the trafic signal controllers. As for extension
of the experiments, we intend to use scenarios in which agents are heterogeneous with regard
to having a diferent set of actions or phases.</p>
    </sec>
    <sec id="sec-7">
      <title>Acknowledgments</title>
      <p>This work is partially supported by FAPESP and MCTI/CGI (grants number 2020/05165-1 and
2021/05093-3), and by a FAPERGS grant (Vicente N. de Almeida). Ana Bazzan is partially
supported by CNPq under grant number 304932/2021-3, and by the German Federal Ministry of
Education and Research (BMBF), Käte Hamburger Kolleg Cultures des Forschens/ Cultures of
Research.
[13] H. Wei, G. Zheng, H. Yao, Z. Li, Intellilight: A reinforcement learning approach for
intelligent trafic light control, in: Proceedings of the 24th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, KDD ’18, Association for
Computing Machinery, New York, NY, USA, 2018, p. 2496–2505. doi:10.1145/3219819.3220096.
[14] M. Abdoos, N. Mozayani, A. L. Bazzan, Hierarchical control of trafic signals using
Qlearning with tile coding, Appl. Intell. 40 (2014) 201–213.
doi:10.1007/s10489-0130455-3.
[15] E. Van Der Pol, Deep Reinforcement Learning for Coordination in Trafic Light Control,</p>
      <p>Ph.D. thesis, University of Amsterdam, 2016.
[16] L. Baird, Residual algorithms: Reinforcement learning with function approximation, in:
In Proceedings of the Twelfth International Conference on Machine Learning, Morgan
Kaufmann, 1995, pp. 30–37.
[17] R. S. Sutton, A. G. Barto, Reinforcement learning: An introduction, second ed., The MIT</p>
      <p>Press, 2018.
[18] L. N. Alegre, T. Ziemke, A. L. C. Bazzan, Using reinforcement learning to control
trafifc signals in a real-world scenario: an approach based on linear function
approximation, IEEE Transactions on Intelligent Transportation Systems (2021). doi:10.1109/
TITS.2021.3091014.
[19] A. Matt, G. Regensburger, An adaptive clustering method for model-free reinforcement
learning, in: Proceedings of INMIC 2004, IEEE, 2004, pp. 362–367.
[20] X. Ma, S.-Y. Zhao, W.-J. Li, Clustered reinforcement learning, 2019. ArXiv preprint
arXiv:1906.02457.
[21] S. Mannor, I. Menache, A. Hoze, U. Klein, Dynamic abstraction in reinforcement learning
via clustering, in: Proceedings of the twenty-first international conference on Machine
learning (ICML), ACM Press, New York, NY, USA, 2004, pp. 71–79.
[22] R. Akrour, F. Veiga, J. Peters, G. Neumann, Regularizing reinforcement learning with state
abstraction, in: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems
(IROS), IEEE, 2018, pp. 534–539.
[23] A. Dereventsov, R. Vatsavai, C. G. Webster, On the unreasonable eficiency of state space
clustering in personalization tasks, in: 2021 International Conference on Data Mining
Workshops (ICDMW), IEEE, 2021, pp. 742–749.
[24] N. Entezari, M. E. Shiri, P. Moradi, A local graph clustering algorithm for discovering
subgoals in reinforcement learning, in: Communication and Networking, Springer Berlin
Heidelberg, 2010, pp. 41–50. doi:10.1007/978-3-642-17604-3_5.
[25] X. Guo, Y. Zhai, K-means clustering based reinforcement learning algorithm for automatic
control in robots, International Journal of Simulation Systems, Science and Technology 17
(2016). doi:10.5013/IJSSST.a.17.24.06.
[26] M. Hashemzadeh, R. Hosseini, M. N. Ahmadabadi, Clustering subspace generalization to
obtain faster reinforcement learning, Evolving Systems 11 (2020) 89–103.
[27] G. Kheradmandian, M. Rahmati, Automatic abstraction in reinforcement learning
using data mining techniques, Robotics and Autonomous Systems 57 (2009) 1119–1128.
doi:10.1016/j.robot.2009.07.002.
[28] L. Lehnert, M. L. Littman, Transfer with model features in reinforcement learning, 2018.</p>
      <p>ArXiv preprint arXiv:1807.01736.
[29] A. I. Panov, A. Skrynnik, Automatic formation of the structure of abstract machines
in hierarchical reinforcement learning with state clustering, 2018. ArXiv preprint
arXiv:1806.05292.
[30] A. Srinivas, R. Krishnamurthy, P. Kumar, B. Ravindran, Option discovery in
hierarchical reinforcement learning using spatio-temporal clustering, 2016. ArXiv preprint
arXiv:1605.05359.
[31] F. Han, L. Jin, Y. Yang, Z. Cao, T. Zhang, Research on robot motion control based on
local weighted kNN-TD reinforcement learning, in: Proceedings of the 10th World
Congress on Intelligent Control and Automation, 2012, pp. 3648–3651. doi:10.1109/
WCICA.2012.6359080.
[32] H. Lin, Z. Shen, H. Zhou, X. Liu, L. Zhang, G. Xiao, Z. Cheng, KNN-Q learning
algorithm of bitrate adaptation for video streaming over HTTP, in: 2020
Information Communication Technologies Conference (ICTC), 2020, pp. 302–306. doi:10.1109/
ICTC49638.2020.9123312.
[33] L. N. Alegre, A. L. C. Bazzan, B. C. da Silva, Quantifying the impact of non-stationarity in
reinforcement learning-based trafic signal control, PeerJ Computer Science 7 (2021) e575.</p>
      <p>URL: http://dx.doi.org/10.7717/peerj-cs.575. doi:10.7717/peerj-cs.575.
[34] P. A. Lopez, M. Behrisch, L. Bieker-Walz, J. Erdmann, Y.-P. Flötteröd, R. Hilbrich, L. Lücken,
J. Rummel, P. Wagner, E. Wießner, Microscopic trafic simulation using SUMO, in: The
21st IEEE International Conference on Intelligent Transportation Systems, 2018.
[35] L. N. Alegre, SUMO-RL, https://github.com/LucasAlegre/sumo-rl, 2019.</p>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          [1]
          <string-name>
            <given-names>M.</given-names>
            <surname>Papageorgiou</surname>
          </string-name>
          , Trafic control, in: R. W. Hall (Ed.),
          <source>Handbook of Transportation Science</source>
          , Kluwer Academic Pub,
          <year>2003</year>
          , pp.
          <fpage>243</fpage>
          -
          <lpage>277</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          [2]
          <string-name>
            <given-names>J. A. Martín H.</given-names>
            ,
            <surname>J. de Lope</surname>
          </string-name>
          ,
          <article-title>A k-NN based perception scheme for reinforcement learning</article-title>
          , in: R. M.
          <string-name>
            <surname>Díaz</surname>
            ,
            <given-names>F.</given-names>
          </string-name>
          <string-name>
            <surname>Pichler</surname>
            ,
            <given-names>A. Q.</given-names>
          </string-name>
          <string-name>
            <surname>Arencibia</surname>
          </string-name>
          (Eds.),
          <source>Computer Aided Systems Theory - EUROCAST</source>
          <year>2007</year>
          , volume
          <volume>4739</volume>
          of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg,
          <year>2007</year>
          , pp.
          <fpage>138</fpage>
          -
          <lpage>145</lpage>
          . doi:
          <volume>10</volume>
          .1007/978-3-
          <fpage>540</fpage>
          -75867-9_
          <fpage>18</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          [3]
          <string-name>
            <surname>J. A. Martín H.</surname>
          </string-name>
          , J. de Lope,
          <string-name>
            <given-names>D.</given-names>
            <surname>Maravall</surname>
          </string-name>
          ,
          <article-title>The kNN-TD reinforcement learning algorithm</article-title>
          , in: J.
          <string-name>
            <surname>Mira</surname>
            ,
            <given-names>J. M.</given-names>
          </string-name>
          <string-name>
            <surname>Ferrández</surname>
            ,
            <given-names>J. R.</given-names>
          </string-name>
          <string-name>
            <surname>Álvarez</surname>
            , F. de la Paz,
            <given-names>F. J.</given-names>
          </string-name>
          <string-name>
            <surname>Toledo</surname>
          </string-name>
          (Eds.),
          <source>Methods and Models in Artificial and Natural Computation. A Homage to Professor Mira's Scientific Legacy</source>
          , Springer, Berlin, Heidelberg,
          <year>2009</year>
          , pp.
          <fpage>305</fpage>
          -
          <lpage>314</lpage>
          . doi:
          <volume>10</volume>
          .1007/978-3-
          <fpage>642</fpage>
          -02264-7_
          <fpage>32</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          [4]
          <string-name>
            <given-names>C.</given-names>
            <surname>Watkins</surname>
          </string-name>
          , Learning from Delayed Rewards,
          <source>Ph.D. thesis</source>
          , University of Cambridge,
          <year>1989</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          [5]
          <string-name>
            <given-names>R. P.</given-names>
            <surname>Roess</surname>
          </string-name>
          ,
          <string-name>
            <given-names>E. S.</given-names>
            <surname>Prassas</surname>
          </string-name>
          ,
          <string-name>
            <given-names>W. R.</given-names>
            <surname>McShane</surname>
          </string-name>
          , Trafic Engineering, 3rd ed.,
          <source>Prentice Hall</source>
          ,
          <year>2004</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          [6]
          <string-name>
            <given-names>A. L. C.</given-names>
            <surname>Bazzan</surname>
          </string-name>
          ,
          <article-title>Opportunities for multiagent systems and multiagent reinforcement learning in trafic control</article-title>
          ,
          <source>Autonomous Agents and Multiagent Systems</source>
          <volume>18</volume>
          (
          <year>2009</year>
          )
          <fpage>342</fpage>
          -
          <lpage>375</lpage>
          . doi:
          <volume>10</volume>
          .1007/s10458-008-9062-9.
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          [7]
          <string-name>
            <surname>K.-L. A. Yau</surname>
            ,
            <given-names>J.</given-names>
          </string-name>
          <string-name>
            <surname>Qadir</surname>
            ,
            <given-names>H. L.</given-names>
          </string-name>
          <string-name>
            <surname>Khoo</surname>
            ,
            <given-names>M. H.</given-names>
          </string-name>
          <string-name>
            <surname>Ling</surname>
            ,
            <given-names>P.</given-names>
          </string-name>
          <string-name>
            <surname>Komisarczuk</surname>
          </string-name>
          ,
          <article-title>A survey on reinforcement learning models and algorithms for trafic signal control</article-title>
          ,
          <source>ACM Comput. Surv</source>
          .
          <volume>50</volume>
          (
          <year>2017</year>
          ). doi:
          <volume>10</volume>
          .1145/3068287.
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          [8]
          <string-name>
            <given-names>H.</given-names>
            <surname>Wei</surname>
          </string-name>
          ,
          <string-name>
            <given-names>G.</given-names>
            <surname>Zheng</surname>
          </string-name>
          ,
          <string-name>
            <given-names>V. V.</given-names>
            <surname>Gayah</surname>
          </string-name>
          ,
          <string-name>
            <given-names>Z.</given-names>
            <surname>Li</surname>
          </string-name>
          ,
          <article-title>A survey on trafic signal control methods</article-title>
          ,
          <year>2020</year>
          . URL: http://arxiv.org/abs/
          <year>1904</year>
          .08117,
          <string-name>
            <surname>preprint</surname>
            <given-names>arXiv</given-names>
          </string-name>
          :
          <year>1904</year>
          .08117.
        </mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation>
          [9]
          <string-name>
            <given-names>M.</given-names>
            <surname>Noaeen</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Naik</surname>
          </string-name>
          ,
          <string-name>
            <given-names>L.</given-names>
            <surname>Goodman</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Crebo</surname>
          </string-name>
          ,
          <string-name>
            <given-names>T.</given-names>
            <surname>Abrar</surname>
          </string-name>
          ,
          <string-name>
            <given-names>B.</given-names>
            <surname>Far</surname>
          </string-name>
          ,
          <string-name>
            <given-names>Z. S. H.</given-names>
            <surname>Abad</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A. L. C.</given-names>
            <surname>Bazzan</surname>
          </string-name>
          ,
          <article-title>Reinforcement learning in urban network trafic signal control: A systematic literature review</article-title>
          ,
          <year>2021</year>
          . URL: engrxiv.org/ewxrj. doi:
          <volume>10</volume>
          .31224/osf.io/ewxrj.
        </mixed-citation>
      </ref>
      <ref id="ref10">
        <mixed-citation>
          [10]
          <string-name>
            <given-names>M.</given-names>
            <surname>Aslani</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M. S.</given-names>
            <surname>Mesgari</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Wiering</surname>
          </string-name>
          ,
          <article-title>Adaptive trafic signal control with actorcritic methods in a real-world trafic network with diferent trafic disruption events</article-title>
          ,
          <source>Transportation Research Part C: Emerging Technologies</source>
          <volume>85</volume>
          (
          <year>2017</year>
          )
          <fpage>732</fpage>
          -
          <lpage>752</lpage>
          . doi:https: //doi.org/10.1016/j.trc.
          <year>2017</year>
          .
          <volume>09</volume>
          .020.
        </mixed-citation>
      </ref>
      <ref id="ref11">
        <mixed-citation>
          [11]
          <string-name>
            <given-names>P.</given-names>
            <surname>Balaji</surname>
          </string-name>
          ,
          <string-name>
            <given-names>X.</given-names>
            <surname>German</surname>
          </string-name>
          ,
          <string-name>
            <given-names>D.</given-names>
            <surname>Srinivasan</surname>
          </string-name>
          ,
          <article-title>Urban trafic signal control using reinforcement learning agents</article-title>
          ,
          <source>IET Intelligent Transportation Systems</source>
          <volume>4</volume>
          (
          <year>2010</year>
          )
          <fpage>177</fpage>
          -
          <lpage>188</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref12">
        <mixed-citation>
          [12]
          <string-name>
            <given-names>S.</given-names>
            <surname>El-Tantawy</surname>
          </string-name>
          ,
          <string-name>
            <given-names>B.</given-names>
            <surname>Abdulhai</surname>
          </string-name>
          ,
          <string-name>
            <given-names>H.</given-names>
            <surname>Abdelgawad</surname>
          </string-name>
          ,
          <article-title>Multiagent reinforcement learning for integrated network of adaptive trafic signal controllers (marlin-atsc): Methodology and large-scale application on downtown toronto, Intelligent Transportation Systems</article-title>
          , IEEE Transactions on
          <volume>14</volume>
          (
          <year>2013</year>
          )
          <fpage>1140</fpage>
          -
          <lpage>1150</lpage>
          . doi:
          <volume>10</volume>
          .1109/TITS.
          <year>2013</year>
          .
          <volume>2255286</volume>
          .
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>