This paper discusses the first steps towards the definition of novel statistics and metrics that characterize networks in terms of the complexity they pose to the traffic assignment problem. Here, we follow an approach in which the assignment emerges from routes selected by learning agents. Specifically, we deal with issues related to how routes are coupled. We first define and quantify route coupling, i.e., how much a given route is coupled with other routes that can be used by learning agents. The investigation of route coupling is important in multiagent reinforcement learning settings since it measures how a change in action selection by one agent interferes with the actions taken by other agents. Our preliminary empirical results indicate that using route coupling to bias the learning process of agents results in faster convergence in the traffic assignment problem.
Traffic networks can be represented as directed graphs G = (V, A), where V represents the set of nodes (street or road intersections, points of interest, or districts), and A the set of arcs (street or road segments). The topology of these graphs, as well as other characteristics such as how demand is distributed and how latency (cost) functions are defined, have a great influence on the traffic assignment problem (TAP), whose goal is to assign the traffic demand (number of trips, vehicles) onto the arcs of a network G.
Our objective is to characterize road networks by designing qualitative metrics and statistics. In particular, given a graph, an origin-destination matrix, and latency functions, we wish to design metrics that numerically represent the degree of difficulty posed to the assignment task. We study the TAP not under the traditional, centralized approach, but via an agentbased variant. Here, each agent (in this context, a driver or vehicle) learns to select a route taking it from its origin to its destination. Given that in such a process a decision made by an agent affects the outcome of other agents, this is a typical multiagent reinforcement learning problem (MARL).
A closely related issue to the one studied in this paper is that of how to characterize a traffic network in terms of how high the price of anarchy (PoA); [Koutsoupias and Papadimitriou, 1999; Roughgarden and Tardos, 2002]) is. The PoA measures the loss in performance caused by a situation in which each driver seeks to minimize its travel time independently. Some works refer to this as selfish routing. One of our goals is to investigate how the magnitude of the PoA affects the learning task. Knowing this, one could anticipate how complex the assignment will be. As the Braess paradox—a case in which the PoA can be very high—shows, the addition of arcs to a network may end up causing more congestion [Braess, 1968].
This paper discusses the first steps towards the definition of novel statistics and metrics to characterize networks in terms of the complexity they pose to the TAP. In particular, we propose a metric based on topological properties of the network, whose goal is to measure how coupled routes are. Coupling refers, intuitively, to how many points of interaction a route has with other routes, and how likely it is that agents might decide to switch routes. This serves as a way of estimating how strongly an agent on one route might be affected by other agents who might change their behavior. Measuring this effect is important since strong dependencies make learning in MARL settings harder. We describe a way of using coupling statistics to bias the learning process of agents in a way that empirically counteracts the negative effects of non-stationary in the learning process, and that is conducive to faster convergence to an equilibrium. We evaluate our methods in several road networks with different topologies and demands— both real-world networks and synthetic ones, such as those affected by the Braess paradox. In order to construct challenging networks that are affected by this paradox, we modify an existing method to extend Braess networks to arbitrary sizes.
This paper is organized as follows: Section 2 introduces the classical, optimization-based approach to the TAP, and an alternative MARL-based approach to compute a user equilibrium. Section 3 introduces our main methods and presents a few networks that we use to illustrate them. We present preliminary results in Section 4, related work in Section 5, and present concluding remarks in Section 6. 2
This section introduces a mathematical formulation for the traffic assignment problem and presents the notation that will be used throughout the paper. As previously mentioned, a transportation network can be represented as a directed graph G = (V, A). Each arc a ∈ A has a latency function which is a function of the traffic in that arc—it quantifies the effects of network usage, such as traffic congestion. This function depends on parameters of the arc such as the time τ to transverse it without congestion (this is also known as free flow time), and the nominal capacity ρ of the arc (e.g., in terms of number of vehicles).
In this work we denote the set of incoming arcs to node v ∈ V by IN (v), and the set of outgoing arcs from node v ∈ V by OUT (v). In addition, let C = {(o(1), d(1)), . . . , (o(|σ|), d(|σ|)} ⊆ V × V denote the set of commodities, i.e., a set of origin-destination (OD) pairs. Here, o(σ) and d(σ) represent, respectively, the origin and destination nodes for σ = 1, . . . , |C|. Each commodity σ has an associated demand rσ = ro(σ),d(σ); i.e., each OD pair (o(σ), d(σ)) has an associated demand rσ that emanates from node o(σ) and terminates in node d(σ).
Furthermore, each arc has a latency function that expresses how travel time depends on the traffic flow on that arc. If drivers were to selfishly select routes that minimize their individual travel times, they could simply select the shortest path that satisfies their desired origin and destination nodes. This strategy, however, makes several underlying assumptions which are often not met, or are unrealistic: for example, that the time taken to traverse an arc is constant and independent of other drivers. This is clearly not the case in real traffic networks, where the maximum flow allowed in an arc depends on which routes other drivers take and on how many drivers occupy an arc at a given time.
When simulating traffic conditions on a given network, a
designer needs to select a latency function that approximates
the real-life costs of navigating in that network. One of the
best-known and widely used latency function for real-world
networks, often referred to as the BPR function, was
introduced by the U. S. Bureau of Public Roads [
In the next section we introduce a mathematical model for assignment problem—this is a classical, optimization-based method to solve the TAP. We then describe an alternative way of solving a version of this problem, namely by searching for a user equilibrium via MARL techniques. 2.1
In this subsection we present mathematical models describing the two main principles that characterize the traffic assignment: the system optimum (SO) and user equilibrium (UE) Wardrop [1952]. The latter principle states that “under equilibrium conditions traffic arranges itself in congested networks such that all used routes have equal and minimum costs, while all those routes that were not used have greater or equal costs”. The former principle refers to the system as a whole and states that the average trip time is minimum.
Beckmann et al. [1956] were the first to propose and solve a mathematical model to compute both the SO and UE solutions. In what follows we present an arc-based mathematical model for SO and for the UE model. A path-based mathematical model may also be used to represent the respective assignment problems. Let xaσ be variables indicating the flow on arc a for the commodity σ; let fa be the total flow on arc a and Φa be the associated cost for the arc a. The SO model for a multi-commodity network can be written as: min Φ =
X Φa a∈A subject to:
xaσ = −dσ, if v = o(σ) dσ, if v = d(σ) 0,
otherwise ∀v ∈ V, σ ∈ C (1) (2) (3) (4) (5) (6)
Objective function (1) aims at finding a flow assignment for each arc that minimizes the total cost for the system— resulting in an assignment respecting the SO principle. Constraints (2) associate the cost of each arc a to the variable Φa; constraints (3) associate the total flow in arc a to variables fa; constraints (4) ensure flow conservation, and constraints (5) and (6) define the domain of variables. Note that this model has quadratic constraints, since it contains a product between flow variables in the constraints (2)—in particular, the product of latency costs and arc flows (i.e., (mafa + na) fa). The SO model can be extended to networks that consider the BPR latency function by changing constraints (2). This formulation uses a set of variables Φa and constraints (2) to define the latency cost on each arc; this is especially useful for the case where the latency function is a composition of linear functions (see Case 2, Section 3.1, for more details).
We now consider the UE model, whose objective is to minimize the function Φ =
X Z fa a∈A x¯a la(x)dx (7)
Since we assume that the latency function is la(x) = max + na, we can simplify this expression. For the case where na ≥ 0, x¯a = 0. For the case where na < 0, x¯a should be the max x such that la(x) = 0; i.e., x¯a = −na/ma. Since we also consider la(x) ≥ 0, the latency function becomes a composition of two line segments, thereby defining a piecewise linear function which is convex and strictly increasing. To completely define the UE model, we now only need to replace the constraints (2) with the following set of constraints: 1 2 1 2 mafa2 + nafa − max¯2a + nax¯a ≤ Φa.
If na ≥ 0, then x¯a = 0 and constraints (8) are reduced to 1 2
Solving the above-mentioned models involves assigning a traffic flow to each arc in order to obtain a global assignment that is consistent either with the SO or UE hypotheses. The models can be solved via mathematical programming using general-purpose solvers such as CPLEX and MOSEK. Mathematical programming-based methods like the ones previously mentioned may have difficulties if non-linear latency functions are used. Furthermore, these methods can typically only solve static assignments. Unlike optimization approaches that use mathematical models suitable only for static assignment with linear or convex latency functions, MARL can be used to compute traffic assignment solutions by considering each individual driver as an autonomous agent, in a microscopic fashion. This strategy can be used to tackle a wide range of problems, such as those involving static or dynamic assignment, and also ones that require the simulation of complex systems.
In this paper we assume that when using MARL to compute traffic assignment solutions, each agent learns to make decisions (i.e., to select routes) by using reinforcement learning. We use the Q-learning algorithm to update the value of each state-action pair of the agent; this value represents the expected long-term utility that the agent hopes to achieve by selecting a given action in a state, and following the current action-selection strategy thereafter. This update is performed based on an experience tuple hs, a, s′, rewi according to Equation 10, where α is the learning rate and γ is a discount rate applied for future rewards. Details of the use of Q-learning for the TAP are given in Section 4.
Q(s, a) ← Q(s, a)+α rew + γ max Q(s′, a′) − Q(s, a) a′ (10) 3
We are interested in characterizing traffic networks of
different types—for instance, synthetic (or pictorial) networks such
as those used to illustrate the Braess paradox; networks whose
demand distributions are closer to real-world cases (versus
symmetric-demand distributions such as those in Braess
paradox); single versus multicommodity cases; networks with
linear versus non-linear latency functions; etc. Hence, prior to
discussing the statistics we employ to measure the coupling
between routes, we introduce and discuss the nature of a few
selected networks: arbitrarily large Braess-paradox networks
(in Section 3.1), the OW network (Section 3.2), and the Sioux
Falls network (Section 3.3). We then introduce a metric for
characterizing some properties of these networks—the
coupling statistic (Section 3.4).
The Braess paradox occurs whenever adding resources to a
transportation network deteriorates the quality of a UE.
Using Beckmann’s mo
Roughgarden [2001] discusses the problem of designing networks so that the Braess paradox does not occur—more specifically, which edges should be removed from a network to obtain the best possible flow at Nash equilibrium. This author also discusses how to create arbitrarily large Braess graphs, whose sizes depend on a factor p; a few examples are shown in Figure 1. Although single-commodity, these networks are interesting since they are associated with a high PoA. Roughgarden’s method allows the investigation of the PoA in large graphs, rather than in simple ones like the network in Figure 1a. Being able to produce large networks with this property is useful in the context of our work because we aim at defining novel statistics and metrics to characterize networks (such as Braess networks of different sizes) in terms of the complexity they pose to the TAP—in particular in the context of using MARL algorithms to solve it. s s s v2 v3 v2 w1 v1 w2 v1 w3 (a) B1 (b) B2
v1 (c) B3 w1 w2 w1 t t t
Braess graphs of arbitrary size can be generated as follows: given a size parameter p, the p-th Braess graph Bp is constructed with a set V p = {s, v1, ..., vp, w1, ..., wp, t} of 2p + 2 vertices; and a set of arcs Ap defined by {(s, vi), (vi, wi), (wi, t) : 1 ≤ i ≤ p}∪{(vi, wi−1) : 2 ≤ i ≤ p} ∪ {v1, t)} ∪ {s, wp)}. Next, we describe how to associate latency functions with each of these arcs.
A key decision when designing arbitrarily large Braess networks is how to associate latency functions to the arcs. We extend the method described by Roughgarden [2001] in three ways: (i) we allow networks with arbitrary constant arc costs c, instead of unitary costs; (ii) we allow arbitrary demand values1 r instead of only fractions of a unitary demand; and (iii) we introduce simpler piecewise latency functions which, although resulting in lower PoA values, allow for solutions to be more easily obtained via standard commercial optimization packages.
In what follows, the demand for a given commodity (or origin–destination pair) σ ∈ C is indicated as rσ. Let c > 0 be the cost associated with constant-cost arcs, and r ∈ R∗+ be the total demand of the network. Roughgarden [2001] uses c = 1 and r = p; this constrains the networks that can be generated since p is typically much smaller than the demand. We modify this formulation so that r can be arbitrarily large. By default, we consider c = 10 and r = 4200.
We now define the latency function la(x) associated with each arc a. The value of i of each arc is the same as described in Section 3.1. We omit the subscript p in the latency function to simplify notation. The latency functions are defined as: • la(x) = 0 for arcs of form a = (vi, wi) ∀i ∈ {1, 2, . . . , p}; • la(x) = c for arcs of form a = (vi, wi−1) ∀i ∈ {2, . . . , p}, (s, wp) or (v1, t).
For the remaining arcs of the form a = (wi, t) or (s, vp−i+1) ∀i ∈ {1, 2, . . . , p}, the latency function is defined as a function of the flow in the arc. We use two strategies to define the latency of these arcs. The first strategy is to use a linear function with na = 0, and the second one is to use a piecewise function based on the latency function described by Roughgarden [2001]; these are henceforth referred to as Case 1 and Case 2 respectively.
Case 1 - Linear function with na = 0 In this case, the latency function la(x) = max + na is a r simple line segment satisfying la(0) = 0 and lap( p ) = ic, i.e.: ma = icp r na = 0. (11) (12)
In this case, the latency function la(x) = max + na is a composition of two line segments satisfying la(0) = 0, 1In this paper we use the term demand, rather than traffic rate, but keep the symbol r used by Roughgarden [2001]. s
c la(x) = 3rci x
i = 1 la(x) = 3rci x
i = 2 la(x) = 3rci x
i = 3
la( p +r1 ) = 0, and lap( pr ) = ic, i.e.,
Besides Braess-paradox networks, another network of
interest in this work is the OW network
The Sioux Falls (SF) network (Figure 5) is based on the realworld city of Sioux Falls, USA. It is frequently used as a testbed for traffic assignment approaches. The SF network uses as a latency function the BPR function (Eq. 15), where fa is the flow on arc a, τa is the free-flow travel time in a, and ρa is its nominal capacity. In this paper we use a˜ = 0.15 and ˜b = 4, as suggested in the literature.
la(fa) = τa 1 + a˜ fa ρ ˜b! (15) 3.4
In this section we introduce novel statistics and metrics to characterize networks in terms of the complexity they pose to the traffic assignment problem—in particular to multiagent reinforcement learning algorithms. We do so by measuring how coupled routes are. We first define and quantify route coupling, i.e., how much a given route is coupled with other routes that can be used by learning agents. The investigation of route coupling is important in multiagent reinforcement learning settings since it measures how changes in the actions of one agent interfere with the actions taken by other agents.
Assume a graph G and latency functions la ∈ R, as previously defined; suppose that we have a demand r resulting from drivers wishing to traverse this graph. Different drivers may have different origins and may wish to reach different destination nodes. Our goal is to have drivers select paths that allow for an overall cost function to be minimized. To this end, drivers may use a set R of routes, where each route Ri is defined as a sequence of nodes connecting the starting node oi of a route to a destination node di; i.e., Ri ≡ [oi, . . . , di]. Concretely, assume that there are |R| routes defined over the graph G. If drivers were to selfishly select paths that minimize their own travel time, measured with respect to the latency la of each arc in a route, we could simply compute the shortest path between oi and di. This strategy, however, makes assumptions that are often unrealistic: for example, that the time taken to traverse an arc is independent of other drivers. This is clearly not the case in real traffic networks.
Alternatively, we can minimize an overall cost function defined over G by using learning methods capable of identifying the optimal allocation of drivers to routes. In this case, one recurring problem is that of non-stationarity: if each driver independently observes the state of the network and makes a decision, the effects of that decision (e.g., its impact on total travel time) may seem to change with time in unpredictable ways. The reason for this is that choices made by other agents, and which the driver cannot always predict or observe, cause properties of the network to remain as unobservable variables in the learning problem. From each driver’s point of view, therefore, the overall learning problem seems to change with time: even if it always selects the same action when observing a same local state, the effective result of that action depends on a series of latent factors. If drivers learn to select routes in this manner, it may take a long time for the aggregate effects of other drivers’ decisions to be averaged out and for the learning algorithm to converge to an equilibrium.
We propose a way of analyzing topological properties of the network in order to estimate how likely it is that nonstationarity (caused by partial observation of other drivers’ decisions or intent) will negatively affect the learning process. On one one hand, networks with sparse and non-interacting routes will typically not be affected by non-stationarity; after all, each driver’s decisions will have almost no effect on the travel time of other agents, therefore resulting in a process in which drivers can independently optimize their route choices. Networks where important routes share many arcs with other routes, on the other hand, will be strongly affected by non-stationarity: if a group of agents decides to change their decisions and switch to a different route, this will directly affect the travel time of many other agents—even if they do not change their own decisions.
The metric that we propose is called coupling, and consists in a statistic computed based on topological properties of the network. Our goal with it is to estimate how strong the effect of non-stationarity might be and to describe a way of using it to bias the learning process, in a way that empirically counteracts the negative effects of non-stationary and is conducive to faster convergence to an equilibrium. Intuitively, the coupling statistic measures how many points of interaction a route has with other routes, and how likely it is that other agents might decide to switch to any given alternative route. If two routes share many arcs, for instance, the effective flow on both of them will be more strongly affected by agents deciding to travel on those routes or deciding to abandon them in favor of other options; these routes are, therefore, highly coupled.
We define the coupling Ψ(Ri) of a route Ri as the expected value of the interaction I(Ri, Rj ) of that route with other routes Rj in the system. This expectation is defined with respect to a probability distribution P over possible routes: routes that are more likely to be selected by agents (based on their individual preferences for reaching particular places in the network) have higher probability. Specifically, we define: (16) (17) Ψ(Ri)
EP I(Ri, ·) = = |R| j=1
X P (Rj )I(Ri, Rj ) where I(Ri, Rj ) is the normalized number of shared arcs between routes Ri and Rj :
I(Ri, Rj ) = 1 |Ri ∩ Rj | |R| |Ri|
Intuitively, I measures how much of the underlying structure and resources of the network are shared by two routes, and P reflects the agents’ demands for different routes at some point in time—defined according to their preferences for reaching different regions of the network2.
In our experiments, we refer to Ψ(Ri) as the mean coupling of a route Ri whenever P is assumed to be a uniform distribution. This corresponds to the case where we have no prior information about agents’ preferences for reaching particular nodes of the network. When we do have that information, we can encode it in P , which then represents the relative preferences of agents for choosing different routes.
To illustrate the use of the proposed coupling statistics, we start with a simple example—the Braess graph B1, depicted in Figure 1(a). This network has a single commodity: the entire demand of r = 4200 drivers travels from s to t. There are 3 possible routes they can select from: st1, st2, and st3, as shown in Table 1. These form the set R of routes, which was generated by using a k-shortest paths algorithm Yen [1971]. This algorithm returns k shortest paths (when analyzed under free flow) associated with a given commodity. The st1 path is the shortest one to satisfy the single demand in B1; st2 and st3 are the second and third shortest paths, respectively.
Table 2 shows the normalized number of shared arcs between any two routes, which is the second term in Equation 17. This table should be read row-wise: e.g., st1 shares 33% of its elements with st2. The coupling Ψ of each route (Equation 16) is shown in Table 3 for the case of uniform P . Under this distribution, it is equivalent to the average normalized number of shared arcs with other routes: Ψ(st2), for instance, 2Route coupling does not take into account interactions of a route with itself. We abuse notation in Equations 16 and 17. In reality, these are defined over the set R − {Ri}, not R. is 12 (50.00 + 0.00). Note that st1 has the highest coupling— but traditional MARL approaches ignore this information.
We propose to use the coupling statistic to bias the learning process of each agent. We report results that relate to a very simple type of biasing; namely, the Q-table of each agent is initialized with the negative of the coupling for each route. Continuing with our example (the B1 network), the Q-values associated with action st1 were initialized with −33.33, and the Q-values associated with actions st2 and st3 were initialized with −25.00. This means we are using information about route coupling to bias agents’ preferences in a way that leads more agents to prefer routes st2 or st3, rather than st1. Our hope is that this will successfully bias route selections, guiding agents in their exploration of which are the best actions to perform and accelerating convergence to an equilibrium.
sv1 → v1w1 → w1t sw1 → w1t sv1 → v1t In order to evaluate the use of the coupling Ψ as a biasing method in MARL we will use the OW network, since solving the traffic assignment problem in it has been shown to be a complex task. In our experiments, agents use Q-Learning, a standard reinforcement learning algorithm, to learn to select routes and reach a UE. Note that at this point we disregard the fact that the UE may be socially bad; see discussion in Section 5. In a traditional reinforcement learning setting, each agent keeps its own Q-table. Q-values are associated with each action—in this case, one of the k shortest routes available for an agent to travel from its origin to its destination. Note that this formulation resembles a repeated game, where there is just one state Claus and Boutilier [1998]. This means that Equation 10 can be simplified and does not require a discount rate. While this simplifies the learning problem, the large number of concurrently-learning agents in MARL makes the problem inherently more complex. Each agent selects actions according to an ǫ-greedy strategy: with probability 1 − ǫ, the action with highest Q-value is selected; with probability ǫ, a random action is selected. We initialize ǫ with a high value and decay it by (1 − δ)% at the end of each episode. This allows for high exploration at the beginning of the learning process. In our experiments, the reward is the negative of the individual travel time of an agent, α = 0.3, ǫ = 1.0 at the first episode, and δ = 0.9. These values were selected after extensive tests with different ranges of values.
The OW network, used in the following experiments, has |C| = 4 commodities, and we associate with it a total demand of r = 1700. We computed k = 5 shortest paths per commodity. Table 4 shows the coupling for each of the |C| × k = 20 shortest routes, computed via Equation 16.
In our experiments, we measure the average latency of the r agents in the system and plot it as a function of time (Figure 6). We do so under three distinct situations: (i) the Qtable of agents is initialized with zeros; (ii) the Q-table is initialized with the negative of the coupling statistic Ψ(Ri) associated with route Ri; (iii) the Q-table is initialized with a random value between 0 and the (negative) maximum value of Ψ. Note that an approximation of the UE for the OW network (which can be computed, e.g., via CPLEX) is of approximately 67 minutes of average latency. In Figure 6 we show that biasing the Q-values of agents with Ψ leads to a faster convergence to the UE.
In the future we plan to perform further experiments; first, one that starts with a lower value of ǫ so that agents can exploit the bias provided at the beginning of the learning process for longer periods of time. Due to lack of space, we omit a table that shows that, at the end of the learning process, the number of agents using each of the k paths is roughly correlated with Ψ of the corresponding path. This suggests that the coupling statistic does serve, indeed, as a proxy to how desirable different routes are—one that considers how agents selecting between them are (as a consequence of the concurrent learning aspect of MARL) negatively impacted by nonstationarity. 5
A number of techniques from transportation planning, economics, operations research, and computer science deal with the TAP. Due to lack of space, we omit classical approaches. The reader is referred to Ortu´zar and Willumsen [2001]. For
AL1 AL2 AL3 AL4 AL5 AM1 AM2 AM3 AM4 AM5 BL1 BL2 BL3 BL4 BL5 BM1 BM2 BM3 BM4 BM5
AC → CG → GJ → JI → IL AC → CG → GJ → JL AC → CF → FI → IL AC → CD → DG → GJ → JI → IL AC → CD → DG → GJ → JL AC → CD → DH → HK → KM AC → CG → GJ → JK → KM AC → CG → GH → HK → KM AD → DH → HK → KM AC → CG → GJ → JM BD → DG → GJ → JI → IL BD → DG → GJ → JL BA → AC → CG → GJ → JI → IL BA → AC → CG → GJ → JL BA → AC → CF → FI → IL BE → EH → HK → KM BD → DH → HK → KM BD → DE → EH → HK → KM BE → ED → DH → HK → KM BD → DG → GJ → JK → KM approaches that seek to balance the UE and the SO, we refer the reader to Bazzan and Chira [2015]. We focus on those that seek to approximate the UE by means of reinforcement learning or other agent-based approaches.
To the best of our knowledge, no attempts have been made to bias the learning of the UE by using similar statistics and metrics as the one we propose. Similar metrics such as the Path Size Logit model [Ben-Akiva and Bierlaire, 1999] and the C-Logit model [Cascetta et al., 1996] are used to select routes in a network in route choice models. However, these strategies differ in the formulation metrics since they are based on the length of arcs.
A natural way to tackle the problem of route choice is via agent-based simulation techniques. Examples are MATSim Balmer et al. [2004], Klu¨gl and Bazzan [2004] and Dia and Panwai [2014]. A learning-based approach to route choice was proposed by Tumer and Agogino [2006], where agents learn to select from pre-computed routes in a singlecommodity network.
Finally, another topic related to our objective is the study of performance degradation caused by the selfish behavior of individual road users—this remains an important research topic, as shown by Koutsoupias and Papadimitriou [1999] regarding the PoA problem. 6
Traffic assignment and route choice are difficult learning problems because the routes available for agents may be highly coupled. Furthermore, the price of anarchy might be strongly affected by issues such as the topology of the network, the demand distribution, and the nature of the latency functions, among other factors. In this paper we presented the first steps towards the definition of statistics and metrics that quantify how difficult the traffic assignment is, in general— and in particular how difficult the computation of an UE is.
In this work we assumed that agents trying to reach an UE learn to select routes independently. As a consequence, their learning processes can be negatively affected by the nonstationarity intrinsic to MARL settings. To counteract this effect, it might be beneficial to bias agents’ decisions in order to accelerate convergence towards less coupled routes. We have shown how to define and compute such a coupling metric and experimented with using the coupling statistics as initial Qvalues; our objective was to give agents initial incentives to select routes that are less coupled. Preliminary results show that this strategy can lead to faster convergence.
Ongoing work is being developed to improve the biasing strategy. We are also working towards evaluating the proposed approach in more complex networks, such as the Sioux Falls network and the Braess graphs with higher p values. Since the Sioux Falls network has 528 commodities, it may be time consuming to compute couplings for, say, all k = 4 routes for each of the commodities. We plan to use previous results from Chudak et al. [2007] to pre-select routes that contain the most congested arcs, and concentrate our analyzes on them. Finally, given that we do have prior information about agents’ preferences for reaching particular nodes of the network (i.e., we do know rσ for each commodity), we can also define a variant of the coupling statistic Ψ which is weighted by these preferences. We also plan to extend the learning process to a state-based one, such as that described in Bazzan and Grunitzki [2016], where agents learn to select an arc (action) at each node (state) of the network that is visited. This contrasts with our current model, where agents learn to select a complete pre-defined route among k options.
Fernando Stefanello was supported by CAPES/PNPD. Ana Bazzan is partially supported by CNPq.