Using reinforcement learning to support agents in making decisions that consider more than one objective poses challenges. We formulate the problem of multiple agents learn to travel from A to B in a trafic network as a reinforcement learning task in which we take into account: non-stationarity, more than one objective, and a a stochastic game based model. To solve this task, we propose an adaptation of an existing algorithm (PQL), which deals with more than one objective. We have applied the proposed method to a scenario in which hundreds of agents have to learn how to travel from their origins to their destinations, aiming at minimizing their travel times, as well as the carbon monoxide vehicles emit. Results show that the adapted algorithm is able to find eficient routes for the agents.
http://www.inf.ufrgs.br/~bazzan (A. L. C. . Bazzan)
kind of problem, the work described in [
In contrast to the aforementioned works, in the present paper, each agent or driver not only performs its optimization process locally (in a decentralized way), by means of multi-objective RL (MORL), but also it builds its trip by making decisions at each intersection (that function as states). Hence, the underlying learning task is state-based. Other characteristics of the problem we deal with is that it involves many agents competing for resources. This also poses challenges to RL methods, even if only one objective is considered. Specifically, the fact that there are many agents learning simultaneously causes the environment to be non-stationary.
In short, a realistic, decentralized RL-based approach to routing involves the following issues: (i) agents learning simultaneously result in non-stationarity; (ii) there are potentially two or more objectives to be optimized; (iii) the underlying learning task is modeled as a stochastic game, where states are the intersections of the networks, where decisions about which link to take are made.
The remainder of this paper is organized as follows. The next section discusses the background concepts and gives an overview on the related work. Section 3 details the proposed method. Its evaluation in a proof-of-concept scenario is discussed in Section 4. Concluding remarks and future directions are given in Section 5.
In this section, we briefly introduce some relevant concepts on RL, as well as on trafic assignment, route choice, and routing (including multi-objective variants).
In RL, an agent learns how to act in an environment, by receiving a feedback (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, which characterizes an exploration phase. Such phase may be very noisy in multiagent scenarios, given that all agents are learning simultaneously and hence have to adapt to others’ exploration processes. However, agents should not only explore; in order to maximize the rewards of their actions, they also have to exploit the gained knowledge. Thus, there must be an exploration-exploitation strategy that is to be followed by the agents. 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 value so far (exploitation).
In the exploitation phase, at each interaction, it is assumed that an agent has sensors to
determine its current state and can then make an action. The reward perceived or received
from the environment is used to update its policy, i.e., a mapping from states to actions. This
policy can be generated or computed in several ways. For the sake of the present paper, we
concentrate on a model-free, of-policy algorithm called Q-learning or QL [
( , ) ← ( , ) + ( + max(( +1 , )) − ( , )) (1)
RL can be employed to compute how drivers learn how to go from A to B in a transportation network. The next section thus introduces this learning task.
In this section, we first discuss the diferences among the various terms that are related to this problem. Then, we introduce the concepts related to the definition of an urban network (topology), as well as the demand side. Finally, we discuss the need for multiobjective approaches.
Given a road network and the demand for its use (number of trips per unit of time), the task of finding out how each unit of such demand realizes its travel needs can be solved in diferent ways, although all seek to compute the so-called user equilibrium, i.e., the condition in which no user is better of by changing its route. We recall that, in the literature, demand can be expressed as trip, traveller, user, agent, or vehicle, depending on the community.
In the transportation community this problem is normally known as trafic assignment
problem (TAP), which is solved in a centralized fashion, mostly via a macroscopic approach
using a volume-delay function (VDF), which estimates the travel time as a function of the
volume of trips; see Chapter 10 of [
Regarding approaches that were already proposed to tackle this problem, in the literature,
there are various approaches to solve the TAP; here we refer only to those that address more
than one objective such as [
This said, next we briefly review the concept of transportation network and the demand that uses it. Formally, a trafic network can be modeled as a graph = ( , ) , where is the set of vertices or nodes that represent the intersections, and , the set of links that describe the segments connecting a pair of vertices. In the network, trips are distributed among a set of origin-destination (OD) pairs; each corresponding to a certain demand for trips. These then translates into flows on the various links.
In all methods it is assumed that agents (drivers) are rational, thus each selects the route or link with the least perceived individual cost, in order to travel from its origin to its destination. Several factors may influence this decision, such as travel time, distance, monetary cost (e.g., toll), fuel consumption, battery, emission of pollutants, etc.
Traditionally, multi-objective trafic assignment is modeled by using a linear combination of
the various objectives, as proposed, for instance, by Dial in [
Hence, it is necessary to have alternative solutions. One issue that arises is that, in a
multiobjective scenario, there is a set of eficient solutions instead of just one. Diferent solutions have
been proposed in the transportation and optimization communities; see for instance [
When employing RL to the problem of how agents should travel from A to B, there are two
possible approaches. The first one relates closely to the TAP in the sense that shortest routes
are computed for agents in each OD pair, although it is not centralized as it is the case with the
aforementioned methods. Examples of this approach are [
The second variant relax the assumption that each agent selects one of the shortest routes (and then travel on it, without deviating from the selected route). Rather, agents make choices en route, i.e., they decide which link to follow once they find themselves in each vertex. This is the approach followed in [16, 14] and also in the present paper.
In this section we discuss how to use QL when agents need to deal with more than one objective. Besides the discussion ahead, we refer readers to other approaches; see [17, 18].
In order to extend the aformentioned QL algorithm, [19] proposed Pareto Q-learning (PQL), which integrates the Pareto dominance relation into a MORL approach. PQL considers both the immediate reward vector and the set of expected future discounted reward vectors in order to compute the so-called Q-sets, which are composed of vectors. In PQL, the set of expected future discounted reward vectors relies on a function, called (from non-dominated), that finds those vectors that correspond to the possible future states, and which are not Pareto-dominated.
Eq. 2 shows how Q-sets are calculated. (,̄ ) denotes the immediate reward vector and (, ) is the set of non-dominated vectors in the next state , which is reached by performing action at time step . (,̄ ) is added to each element of (, ) . When is selected at , both terms are updated. (,̄ ) is updated according to Eq. 3, where ⃗ is the new reward vector and (, ) is the number of times action was selected in . (, ) is updated as shown in Eq. 4, using the non-dominated vectors in the ̃ of every action ′ in the next state ′. ̃ (, ) = (,̄ ) ⊕
(, ) (,̄ ) =
(,̄ ) + (, ) = (∪ ′ ̃ ( ′, ′)) ⃗− (,̄ ) (, ) (2) (3) (4)
PQL learns the entire Pareto front, finding multiple Pareto optimal solutions, provided that each state-action pair is suficiently sampled. This algorithm is not biased by the Pareto front shape (algorithms that find a single policy and use scalarization cannot sample the entire Pareto front if it is non-convex) or a weight vector (it guides the exploration to specific parts of the search space).
Note that PQL assumes that the environment is deterministic, hence it is not directly useful for environments in which the presence of multiple agents learning simultaneously cause non-stationarity, as for instance the route choice domain we use ahead.
Our contribution (called aPQL, detailed ahead) is an adaptation of PQL to deal with multiple objectives and with multiple agents (thus, a non-stationary environment).
Before presenting the details of the proposed method, some considerations to the Markov
decision process (MDP) underlying the learning task should be addressed. In an MDP, we define
a set of states , a set of actions , a reward function ∶ × → ℝ , and a probabilistic state
transition (, , ′) → [
In the routing learning task, each intersection within a trafic network is a state , and the actions are the links an agent might take when in (i.e., links that leave the intersection). In short, agents build their routes by making decisions about which link to follow, when finding themselves in a given intersection.
Regarding the environment, the transition model is implemented by a microscopic trafic simulator itself, which moves vehicles along the network. As for the rewards, since we deal with a multiobjective scenario, the rewards returned by the simulator are assembled in a vector; this way, the reward function definition is ∶ × → ℝ , where is the number of objectives to be optimized. As detailed in Section 3.3, in the present paper we deal with agents aiming at optimizing two objectives: travel time and carbon monoxide emission. However, the proposed method is general and can be used if more objectives are taken into account.
In a traditional RL environment, at each time step, each agent finds itself in state , chooses action , receives a reward and transitions to a state ′. In the learning task at hand, time steps are controlled by the microscopic simulator and correspond to an unit of time such as one second. This has important consequences. First, not all time steps count as decision-making steps; these only happen when an agent is at an intersection. The rest of the time steps are used (e.g., see plots ahead) just as clock units. Second, diferent agents find themselves either in decision-making states, or are moving along a link (thus, not updating their value functions), or have reached their destinations. In the latter case, an episode is finished for that particular agent. Since travel times and destinations are diferent for most of the agents, episodes are not synchronous. Therefore, in general, we do not refer to episodes; rather, we use the clock units or time steps of the simulator to depict time. To control the simulation time, we introduce a parameter called maximum number of steps, .
In this section we detailed how we deal with multiple objectives in the reward function.
In the exploration phase, due to uncoordinated action selection by the agents, congestion may occur, which impacts the reward of the agents, while also inserting a lot of noise in the learning process, which then leads to slow convergence. In order to speed up this process, and avoid agents wandering around the network performing experimentation, two hyper-parameters were introduced. The first one is a bonus that is added to the reward when an agent reaches its destination. The second is a penalty that is subtracted to the reward when an agent is in a dead-end node, i.e., a node from which it cannot reaches its destination at all.
Given that the reward accounts for more than one objective (and thus is represented by a vector of size , where is the number of objectives to optimize), both the bonus and the penalty are added (subtracted in the case of ) to the corresponding scalar value, as stated in Eq. 5 (for the bonus) and Eq. 6 (for the penalty).
⃗= ⃗+ ⋅ ⃗ 1 ⃗= ⃗− ⋅ 1⃗ (5) (6)
A further hyper-parameter of our model resembles a kind of toll on emissions of pollutants. It is designed based on the assumption that certain links of the network should be spared from high emission levels; this may be the case of links close to parks, hospitals, residential areas, etc. This parameter is the penalty ; it acts similarly to the aforementioned penalty , with the diference that is subtracted only to the element of the reward vector that refers to the emission. Let ̂ be an -th basis vector, where is the position of the emission element of the reward vector. Then the penalty is used to update the reward as in Eq. 7. Algorithm 1 summarizes how the reward is calculated.
⃗= ⃗− ⋅ ̂ (7) Algorithm 1: Compute Reward
Data: , , ,
Result: ⃗ 1 ⃗← −[. 2 ⃗← ⃗+ ⋅ 3 ⃗← ⃗− ⋅ 1⃗; 4 ⃗← ⃗− ⋅ ̂ ;
1⃗; _ _ _, . _ _] ;
Originally, in PQL (i.e., as proposed in [19]), every pair state-action (, ) is associated with a set of non-dominated points that represents the Pareto front. Q-sets are computed as in Eq. 2 and are used to compute a hypervolume of the Pareto front. This is then used to determine the best action. In our case, this was not efective given that the Q-sets tend to contain few points only, thus computations based on hypervolume tend to be inefective. Therefore, we had to modify the action selection strategy. Instead of using the hypervolume of the Pareto front to determine the best action, we let each agent select randomly (with uniform probability, at each decision point, and independently of one another) which objective is to be optimized at that given step. This seems to be a fair substitution for the hypervolume and avoids biasing towards one objective. Once a particular objective is randomly drawn, then an agent uses the -greedy strategy to select an action, given the Q-set. Note that the approach continues to be multiobjective, as all objectives have their values updated after a given action was selected.
Given this adaptation in the action selection part of the approach proposed in [19], henceforth we refer to ours as aPQL (adapted PQL). The remainder of aPQL follows basically the same procedures underlying PQL.
Algorithm 2 shows how our method works for each agent. The required parameters are: (maximum number of time steps); , and (bonus, the destination, and the emission penalty discussed in Section 3.3); the discount factor as well as the ( -greedy exploration strategy). Left4 Left3 Left2 Left1 Left0
Top0 Top1 Top2 Top3 Top4 A4 A3 A2 A1 A0
B4 B3 B2 B1 B0
C4 C3 C2 C1 C0
D4 D3 D2 D1 D0
E4 Right4 E3 Right3 E2 Right2 E1 Right1
E0 Right0 Bottom0 Bottom1 Bottom2 Bottom3 Bottom4
Bottom0|Top4 / Top4|Bottom0 Bottom1|Top3 / Top3|Bottom1 Bottom3|Top1 / Top1|Bottom3 Bottom4|Top0 / Top0|Bottom4
Left0|Right4 / Right4|Left0 Left1|Right3 / Right3|Left1 Left3|Right1 / Right1|Left3 Left4|Right0 / Right0|Left4 in a destination or in a dead-end node. Recall that a dead-end node is one from which it is not possible to reach a destination at all, an information provided by SUMO. In both cases, Algorithm 1 is used to compute the reward, as stated in Section 3.3: in the case of a destination node (line 12), a non-zero bonus is given; in the case of a dead-end (line 15), the reward includes a non-zero penalty.
The agent can then update its non-dominated policies for the last action using the Q-sets of possible next states, and the average rewards (line 17). After these updates, the agent (re)starts a new trip (an episode for this particular agent), thus it is reinserted at its origin node.
The else statement in lines 19 - 29 deals with the agent that reached a node that is not its destination (or a dead-end). In this case, the reward computation in line 20 neither a bonus nor a penalty apply. Thus both and are set to zero.
Both methods in lines 17 and 22, as well as the Q-set computation in line 21 are performed as proposed in the original PQL algorithm.
To test the approach, we used a 5 × 5 grid network depicted in Figure 1. The demand corresponding to the OD (origin-destination) matrix is shown in in Table 1. For each OD pair, the number of trips refers to both directions. For example, for the first line of the table, half of the vehicles travel from Bottom0 to Top4 and half from Top4 to Bottom0.
Each link shown in Figure 1 is two-way. The ticker links (in blue, connecting nodes A2 to E2) are the ones in which we want to have less emission. Thus, each agent using those links receive a penalty (as discussed in Section 3.3) once it travels through them.
The method proposed was compared against three others: dynamic user assignment (DUA), which is an iterative method for computing the user equilibrium provided by SUMO; the standard QL optimizing only the agents’ travel time (QLTT); and the standard QL optimizing only the CO emission (QLCO).
All parameters discussed in Section 3 were set as follows: maximum simulation steps =
50, 000; since we use normalized (ranging from [−1, 0]) values for the reward, all values regarding
reward computation were set as = 1 , = 1 and = 1, guaranteeing that the rewards values
received are always within [
Its is also worth mentioning that, due to the stochastic nature of all methods we used for comparison, each of them were repeated 30 times. In the plots ahead, we show the mean values (and their standard deviations, as shadows).
The comparison among the aforementioned methods was performed using values related to three diferent metrics: travel time (Figure 2a), CO emission (2b) and speed (2c). These values were collected from each link in the network. Plots in Figure 2 show a moving average (over a window of 600 steps) of the corresponding value, over all links.
In order to investigate performances for a part of the network only (those links indicated in blue in Figure 1), Figure 3 also depicts the three metrics, however values there are averaged only over those particular links (not for the entire network, as in Figure 2).
Results plotted in Figure 2 show a clear advantage of the aPQL method: it outperforms the others, showing lower travel time, lower CO emission, and higher speed (already after approximately 20,000 steps). These results seem to indicate that the aPQL method have a better usage of the links in the network. On a related note, one might assume that higher speeds would lead to higher CO emission. However, a more decisive factor is acceleration/deceleration. If the speed is constant, this seems to not afect emissions in a significant negative way.
Another issue is that one also observes a better distribution of vehicle in the network, which may be due to the fact that the aPQL takes the advantage of both the optimization of travel time and CO emission. The penalty imposed in the links A2 to E2 in Figure 1 causes both methods that optimize the objectives independently to behave in a diferent way. Optimizing travel time (QLTT) alone leads agents to a solution that can be seen in Figure 3(b), where no considerable reduction to CO emission is observed when we look at the red curve that represents QLTT. Conversely, optimizing only the CO emission causes the agents not to take the links in which they are penalized. In fact, since they completely stop selecting such links, it is possible to see that there are no data points for travel time and speed in Figure 3 regarding QLCO. One also notices that the average network travel time from QLCO (green curve in Figure 2(a)) is slightly higher than the one observed in QLTT. This happens due to the fact that, by avoiding several links within the network, the agents in QLCO have less available actions, and thus experience an increase in travel time.
By employing an approach that considers both objectives at the same time, aPQL makes the agents reach a compromise that seems to yield a better distribution of vehicles throughout the network: they mostly (but not entirely) avoid the links in which the CO emission is penalized (observed in the orange curves in Figure 3), using other parts of the network, taking advantage of the fact that those links are less occupied. This leads to a considerable increase in performance in relation to the other methods.
Lastly, it is worth noting that the values observed in travel time in the present paper are
considerably lower than what was seen in our previous works, when the same grid networks
was used ([
Using RL to support agents making decisions that consider more than one objective poses challenges. We formulate the problem of multiple agents learning to travel from A to B in a trafic network as an RL task in which: (i) agents learning simultaneously result in nonstationarity; (ii) there are potentially two or more objectives to be optimized; (iii) the underlying learning task is modeled as a stochastic game, where states are intermediary locations in the networks (such as intersections), in which decisions are made about which link to take.
To solve this task, we propose an adaptation in an existing algorithm, PQL [19]. This algorithm deals with more than one objective, but it was originally formulated for single-agent learning tasks, in which the environment is deterministic. In route choice neither of these apply. Thus our adaptation addresses them. We have applied the proposed method to a scenario in which hundreds of agents compete for a scarce resource (link usage), and have to learn how to travel from their origins to their destinations, aiming at minimizing their travel times, as well as the CO vehicles emit. Results show that the adapted algorithm is able to find routes that are more eficient then when either only travel time or only emissions are considered as rewards.
Future work is planned in the direction of considering communication between vehicles and infraestructure as in [14], given that this work was the basis of the present one; thus a revisiting of that case (now considering various objectives) is an open direction. In this regard, we also plan to include more objectives, such as other types of emissions.
This work is partially supported by FAPESP and MCTI/CGI (grants number 2020/05165-1 and 2021/05093-3). 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. [14] G. D. dos. Santos, A. L. C. Bazzan, Sharing diverse information gets driver agents to learn faster: an application in en route trip building, PeerJ Computer Science 7 (2021) e428. URL: https://doi.org/10.7717/peerj-cs.428. doi:10.7717/peerj-cs.428. [15] G. Dytz dos Santos, A. L. C. Bazzan, A. P. Baumgardt, Using car to infrastructure communication to accelerate learning in route choice, Journal of Information and Data Management 12 (2021). URL: https://sol.sbc.org.br/journals/index.php/jidm/article/view/1935. [16] A. L. C. Bazzan, R. Grunitzki, A multiagent reinforcement learning approach to en-route trip building, in: 2016 International Joint Conference on Neural Networks (IJCNN), 2016, pp. 5288–5295. doi:10.1109/IJCNN.2016.7727899. [17] R. Rǎdulescu, P. Mannion, D. Roijers, A. Nowé, Multi-objective multi-agent decision making: a utility-based analysis and survey, Autonomous Agents and Multi-Agent Systems 34 (2020). doi:10.1007/s10458-019-09433-x. [18] C. F. Hayes, R. Radulescu, E. Bargiacchi, J. Källström, M. Macfarlane, M. Reymond, T. Verstraeten, L. M. Zintgraf, R. Dazeley, F. Heintz, E. Howley, A. A. Irissappane, P. Mannion, A. Nowé, G. de Oliveira Ramos, M. Restelli, P. Vamplew, D. M. Roijers, A practical guide to multi-objective reinforcement learning and planning, CoRR abs/2103.09568 (2021). URL: https://arxiv.org/abs/2103.09568. arXiv:2103.09568. [19] K. Van Mofaert, A. Nowé, Multi-objective reinforcement learning using sets of pareto dominating policies, J. Mach. Learn. Res. 15 (2014) 3483–3512.