Reducing Bus Bunching with Asynchronous Multi-Agent Reinforcement Learning

1 Introduction

Public transport has been considered the most critical component in sustainable urban transportation. Providing reliable and efficient services to meet the increasing transit demand has become a major challenge faced by public transit operators. However, in real-world operations, the great uncertainties in traffic conditions (e.g., congestion, incident, and signal control) and dwell time often make bus services unstable [Daganzo and Ouyang, 2019]. Bus bunching has become a common phenomenon in the operation of high-frequency bus services. For a bus service, vehicles essentially leave the departure terminal with a regular frequency/headway (e.g., every 10 min) based on the timetable. If a bus is slightly delayed on the route, it will likely encounter more waiting passengers at the next bus stop, and then the dwell time serving boarding/alighting passengers will also increase. As a result, the delayed bus will be further delayed, and the following bus will become faster due to fewer waiting passengers and shorter dwell time; eventually, two or even more buses will bunch together and travel as a group (e.g., see Fig. 1). Bus bunching has two major negative effects on rider experience: on the one hand, passengers will suffer from long waiting times and then see a group of vehicles arriving together; on the other hand, bus bunching also leads to imbalanced occupancy, since the leading bus in a group will take more passengers and the others will take less. Overall, bus bunching is an urgent issue that undermines the reliability and efficiency of transit services. In general, the severity of bus bunching increases with the service length, and downstream passengers often suffer more than upstream passengers.

∗Contact Author

Bus holding control is one of the most effective methods to reduce bus bunching. Recently advances in model-free reinforcement learning (RL) have shed new light on the sequential control problem, allowing us to develop efficient and effective control policies for a large system without building an explicit model. In particular, multi-agent reinforcement learning (MARL) provides a learning scheme to explore collaborative policy, which has been shown to be superior in a multi-agent system. The application of MARL in intelligent transportation systems (ITS) has attracted considerable attention in recent years, with a particular focus on traffic signal control (see e.g., [Chen et al., 2020]). Bus fleet operation is also a unique ITS application where MARL fits very well. On this track, Chen et al. [2016] and Alesiani and Gkiotsalitis [2018] proposed MARL models to develop holding control strategies to match a pre-specified headway; however, such a setting is often too restrictive to adapt to the great uncertainties in bus fleet operation. Instead of using a fixed headway, Wang and Sun [2020] proposed a reward function to promote headway equalization in the MARL model. Nevertheless, the models above overlook the fact that buses are not being controlled simultaneously since holding happens only when a bus arrives at a bus stop. In such an asynchronous setting, the default MARL cannot effectively take into account the impact from other agents. To deal with such asynchronicity, Menda et al. [2018] proposed an event-driven MARL by designing a reward function associated with macro-action; however, this approach still cannot distinguish the contributions from ego agent and other agents.

To better address the asynchronous issue in bus fleet control, in this paper we propose a new credit assignment framework for asynchronous control (CAAC) by integrating actions from other agents using inductive graph learning. Our main contribution is threefold:

• We establish an asynchronous multi-agent reinforcement learning (ASMR) framework to optimize holding control policy on a bus route to reduce bus bunching.
• To the best of our knowledge, this work is the first to consider the marginal contribution from uncertain events in MARL. This proposed CAAC also has potential to be generalized to other asynchronous control problems.
• We build a learning framework for bus operation in an asynchronous setting based on real-world transit operation data, and evaluate the proposed CAAC with extensive experiments.

2 RelatedWork

2.1 Holding Control to Avoid Bus Bunching

Bus holding control is a longstanding research topic in transit operation [Daganzo and Ouyang, 2019]. Traditional methods mainly focus on maintaining headway consistency by deriving suitable policies using optimization-based models. However, in practice, this approach has two major limitations. On the one hand, due to the lack of field data, scenarios and optimization models are often over-simplified in many existing studies (e.g., [Daganzo, 2009; Wang and Sun, 2020]). As a result, these models can hardly reproduce reality and scale to large real-world scenarios. On the other hand, these optimization-based models are essentially scenario-specific [Seman et al., 2019], and in practice they require careful design and training for each case. Therefore, these optimization-based models often fail to generalize the policy learned from the past to future and unseen scenarios.

2.2 Asynchronous Multi-agent Control

In this paper, we tackle the asynchronous multi-agent control problem by introducing a new credit assignment scheme.

Credit assignment aims to better estimate each agents' own contribution to the team's success for better policy update, and it has been a central research topic in designing reliable MARL algorithms [Chang et al., 2004]. For example, Foerster et al. [2018] proposed COMA-a multi-agent actorcritic algorithm with a counterfactual baseline to quantify the contribution from each agent. However, COMA only works for applications with a discrete action space. Recent studies have proposed credit assignments by designing different value decomposition schemes, which can accommodate both discrete and continuous action spaces. For example, Sunehag et al. [2018] proposed Value-Decomposition Network (VDN) to measure the impact of each agent on the observed joint reward. Rashid et al. [2018] developed QMIX, which improves VDN by adding restrictions on the relation between local and global Q-value. Furthermore, Son et al. [2019] developed QTran as a more generalized factorization scheme. These studies have made outstanding contributions to the general credit assignment problem. However, a major limitation is that they only consider local observation-action, which hinders the exploration of more effective cooperation policy. Notably, Wang et al. [2020] derived a similar credit assignment framework with Shapely Q-value to better quantify local contributions; however, the asynchronous issue with a varying number of activated agents is still overlooked. Lee et al. [2020] studied sequential decision problems involving multiple action variables whose control frequencies are different; still, the framework only considers a pre-specified frequency for each single agent.

3 Holding Control as an ASMR Task

In this paper, we define the forward headway for a specific bus at a certain time as the time duration for it to reach the current location of the preceding bus. Correspondingly, we define the backward headway as the forward headway of its follower. Holding control is a widely used strategy to maintain headway consistency and avoid bus bunching in daily operation [Wang and Sun, 2020]. The key idea of holding control is to let a bus stay longer (i.e., by adding a slack period) at stops in addition to the dwell time for passengers to board/alight. For instance, when a bus gets too close to the preceding vehicle, it can equalize/balance the forward headway and backward headway by holding at a bus stop. In this study, we model bus holding as a control policy in MARL with the goal of improving overall operation efficiency.

Fig. 2 shows the vehicle holding control framework on a bus route, in which we take all the buses running in the system/environment as agents. Note that we label all buses in a sequential order, where bus bi+1 follows bus bi. Bus holding control for a fleet {bi} is a typical application of asynchronous multi-agent control, as holding control is applied only when a bus arrives at a bus stop. We define the basic elements in this framework as follows:

State: Each agent has a local observation of the system. For bus bi arriving at stop kj at time t, we denote the state of bi by si,t, which includes the number of passengers onboard, the forward headway hi and the backward headway hi+1.

Action: Following Wang and Sun [2020], we model holding time as:

where ∆T is the maximum holding duration and ai,t ∈ [0, 1] is a strength parameter. We consider ai,t the action of bus bi when arriving at a bus stop at time t. Here, ∆T is used to limit the maximum holding duration and avoid over-intervention. We model ai,t as a continuous variable in order to explore the near-optimal policy in an adequate action space. Note that no holding control is implemented when ai,t = 0.

Reward: Despite that holding control can reduce the variance of bus headway and promote system stability, the slack/holding time will also impose additional penalties on both passengers (i.e., increasing travel time) and operators (i.e., increasing service operation hours). To balance system stability and operation efficiency, we design the reward function associated with bus bi at time t as:

where CV 2 = V ar[h] E2 [h] quantifies headway variability [Transportation Research Board, 2013] and w ∈ [0, 1] is a weight parameter. Essentially, E[h] is almost a constant given the schedule/timetable, and thus CV is mainly determined by V ar[h]: a small CV indicates consistent headway values on the bus route, and a large CV suggests heavy bus bunching. The second term in Eq. (2) penalizes holding duration and prevents the learning algorithm from making excessive control decisions. This term is introduced because any holding decisions will introduce additional slack time and reduce operation efficiency. Overall, the goal of this reward function is to effectively achieve system stability with as few interventions as possible, with w serving as a balancing parameter.

The agent implements an action (i.e., determining holding time) when it arrives at a stop, and then it will receive feedback upon arriving at the next stop. In previous studies [Wang and Sun, 2020; Chen et al., 2016], this dynamic process is considered a multi-agent extension of Markov decision processes (MDPs) [Littman, 1994] and referred to as Markov game G = (N, S,A,P,R, γ), where N denotes the number of agents, γ denotes the discount factor, S and A = {A1, . . . ,AN} denote the state space and the joint action space, respectively, and P : S ×A ↦→ S represents the state transition function. However, this definition becomes inaccurate in the bus control problem, since agents rarely implement actions at the same time. To address this asynchronous issue, we introduce a modified formulation in which each agent maintains its own transition: ˆ Pi : Si × ˆ A ↦→ Si, ˆ A ⊆ A, where Si is the observation of agent i. In this way, state transition observed by agent i does not necessarily depend on the actions from all the other agents at any particular time. The policy to choose an action is given by the conditional probability πθi = p (Ai | Si). Finally, the reward function for each agent can also be defined independently: R = {R1, . . . ,RN}. While the independence assumption simplifies the problem, it raises a new challenge-how to effectively consider the actions from other agents, which is to be addressed in the following section.

4 Methods

As mentioned previously, traditional multi-agent models, such as Independent Q-Learning (IQL) [Tan, 1993], MADDPG [Lowe et al., 2017] and QTran [Son et al., 2019], cannot address the aforementioned asynchronous issue. To solve this problem, in this section we introduce a Credit Assignment framework for Asynchronous Control (CAAC) with shared parameters.

4.1 Credit Assignment Framework for Asynchronous Control (CAAC)

Following previous work, we adopt the basic actor-critic architecture, in which the critic is used to evaluate the effect of action from a single agent. To achieve reliable and efficient credit assignment in an asynchronous setting, we design an inductive critic following the scheme shown in Fig. 3.

The proposed inductive critic consists of an ego critic and an event critic: the ego critic is to evaluate the actor's policy, and the event critic is to account for the contribution from the actions of other agents. With this architecture, we expect CAAC to better quantify the undetermined impact from other agents and provide a more accurate credit assignment scheme for policy evaluation. We next introduce CAAC and the learning algorithm in detail.

Approximate Marginal Contribution with Event Critic

Inspired by the idea of inductive graph learning [Hamilton et al., 2017], we propose to build a graph-based event critic to learn to approximate the marginal contribution from other agents. We first introduce the concept of event graph (EG) based on the spatiotemporal trajectory plot (see Fig. 4). We denote EG by G (V, E), where V and E are the vertex set and edge set, respectively. We define a vertex (i, t) as the event when a bus bi arrives at a bus stop at time t. Note that we ignore the index of bus stops when defining EG. We assume bus bi arrives at the next stop at time t + ∆i,t, and introduce incoming edges for (i, t) by linking all arriving events (j, t′ ) from other vehicles (i.e., j ̸= i) within the time window t < t′ ≤ t + ∆i,t. The left panel of Fig. 4 illustrates how EG is built based on the trajectory diagram. Each node in the panel represents an arrival event of a bus. Taking the event (i, t) as an example, there are three incoming edges from other events. We denote the set of neighbors of event (i, t) by Ni,t = {(j, t′ ) ∈ V : j ̸= i, t < t′ ≤ t +∆i,t}.

Given an ego agent, the formulation of EG presents a neat and dynamic tool to account for actions from other agents, which allows us to conduct inductive graph learning and build a flexible policy evaluation block for asynchronous control. Specifically, we adopt graph attention neural network (GAT) [Veliˇckovi´c et al., 2018] to inductively learn and approximate the undetermined impact from the actions of other agents. Considering the heterogeneous effects from upstream and downstream events, we introduce two separate GATs for upstream events and downstream events, respectively. In doing so, we divide Ni,t into two subsets: upstream event set N u i,t = {(j, t′ ) ∈ V : j > i, t < t′ ≤ t +∆i,t} and downstream event set N d i,t = {(j, t′ ) ∈ V : j < i, t < t′ ≤ t +∆i,t}. The right panel of Fig. 4 summarizes the inductive block, which we call event critic (EC).

We next introduce the details of EC. We first define ej,t′ = {e1j,t′ , e2j,t′ } , ∀ (j, t′ ) ∈ Ni,t to capture the augmented information for the event critic, where e1j,t′ denotes the number of bus stops separating the two controls and it is normalized by the total number of stops in the system, and e2j,t′ = |j - i| is the number of vehicles in between bi and bj . We then aggregate information from upstream and downstream, respectively. Given the upstream events N u i,t , the node features consist of two parts: (1) node features of other agents: hj,t′ = (sj,t′ , aj,t′ , ej,t′), where (sj,t′ , aj,t′) is the state-action pair of agent j at t′ ; (2) node feature of the ego agent hi,t = (si,t, ai,t, zeros like (ej,t′)), where we add zeros to ensure equal feature length. Since EG is undirected, the graph attention is actually based on the relation between the ego event and its upstream events. We can then perform graph attention:

where σ is non-linear activation function and || represents concatenation, W a is the trainable shared weight matrix, and f represents a single-layer neural network. Finally, we sum all the derived features as

The information aggregation M d i for downstream events N d i,t works the same way as the upstream. The summation of M u i and M d i is then fed to a feed-forward neural network to generate the final result of the event critic. Note that we omit self-attention and mask the aggregation output if there exist no upstream or downstream events for the ego agent (i.e., no contribution from other agents).

Deep Deterministic Policy Gradient with Inductive Critic A critical issue in MARL with Deep Deterministic Policy Gradient (DDPG) is that the critic is likely to have an ambiguous evaluation on the contribution of each agent. The problem becomes even worse in an asynchronous setting where even the number of activated agents varies in each decision step. To address this issue, we implement multi-agent DDPG with a more rational credit assignment by combining the ego critic and event critic (see Fig. 3).

As the first component of the inductive critic, the ego critic is responsible for evaluating the ego policy. Based on the evaluation, we can derive policy gradient to maximize the following objective function as in DDPG:

The second part of the inductive critic is the event critic, which is used to approximate the marginal contribution from other agents. Finally, we approximate the actual system return for agent i using the sum of the output from ego critic and event critic:

Based on the standard DQN loss [Mnih et al., 2015] following the Bellman equation, the proposed inductive critic can be trained by minimizing the following loss function:

where ri,t is the reward obtained by agent i given its action ai,t, Gtar i,t+∆i,t denotes the cumulative return from the next decision step t +∆i,t in the view of agent i, which is estimated through the target network [Mnih et al., 2015], and I(·) is an indicator function. Note that in the case where an event has no upstream/downstream events, we additionally impose L2 norm with hyperparameter β = 0.1. Thus, ∥∥M u i,t∥∥2 and ∥∥M d i,t∥∥2 regularize W a in the event critic block, which can facilitate inductive learning. In training, we sample from the interaction between agents and the system to approximate the expectation of above objective functions. In the execution phase, only local observations are used for actor network; thus, the overall CAAC is very flexible for real-world applications.

5 Evaluation

We evaluate the performance of the proposed method based on real-world data. Four bus routes (R1-R4) in an anonymous city are selected, with true passenger demand derived from smart card data. The four routes are all trunk services covering more than 15 km with over 40 bus stops along the route. Table 1 lists the basic statistics of the routes, including the number of services per day, the number of stops, route length, the mean and standard deviation (std) of headway at the departure terminal.

5.1 Simulator for Bus Route Operation

We first develop and calibrate the bus simulator to reproduce the patterns of real-world operation. In this simulation, the alighting and boarding times per passenger are set to ta = 1.8 s/pax and tb = 3.0 s/pax, respectively. To simulate the uncertainty of road conditions, buses are given a random speed v × U(0.6, 1.2) km/h when travelling between every two consecutive stops, where v is set to 30 km/h and U denotes a continuous uniform distribution. The capacity of the bus is set to 120 pax. Fig. 5 (a) and (b) show the simulated boarding time and actual boarding time from smart card (tapin for boarding and tap-out for alighting) data and the simulated journey time and actual journey time, respectively, for service R1. The Pearson correlations for these two plots are 0.999 and 0.983, respectively, suggesting that our simulator is consistent with the real-world operation.

5.2 Experimental Settings

We set hyper-parameter w = 0.2 in reward function Eq. (2) to place priority on system stability. We start our experiment by training the model on R1 for 250 episodes. In the execution phase, we test the performance of the tuned RL models on R1 and then evaluate the model transferability by applying R1's models on R2/R3/R4 directly without retraining. The proposed CAAC framework is compared with the following baseline models, including both traditional headwaybased control models and state-of-the-art MARL methods: i) No control (NC): NC is considered a naive baseline where no holding control is implemented. ii) Forward headwaybased holding control (FH) [Daganzo, 2009]: the holding time is d = max{0, d + g(H0 - h-)}, where H0 is the desired departure headway, h- is the forward headway of the arriving bus, d is the average delay at equilibrium, and g > 0 is a control parameter. We use the same parameters as in Daganzo [2009]. iii) Independent Actor-Critic (IAC) [Lillicrap et al., 2016]: we implement DDPG in the IAC setting to examine the performance where the agent completely overlooks the impact from other agents. IAC can be considered a special case of CAAC with no event critic. iv) MADDPG [Lowe et al., 2017]: we implement MADDPG as a state-ofthe-art baseline without special consideration for the asynchronous setting. In MADDPG, the ego bus considers all other buses when performing actions. In the implementation, we fill zeros for the actions from inactivated agents. Besides, to achieve transferability, both the critic network and the actor network are shared among all agents.

All models are implemented with python and PyTorch 1.7.0 on Ubuntu 18.04 LTS, and experiments are conducted on a server with 256GB RAM. We use the following indicators to evaluate model performance: i) Average holding time (AHT), which characterizes the degree of intervention; ii) Average waiting time (AWT), which evaluates the severity of bus bunching; iii) Average journey time (AJT), which quantifies the average journey duration from boarding to alighting for all trips; iv) Average travel time (ATT), which quantifies the average travel time for each bus from the departure terminal; and v) Average occupancy dispersion (AOD), which evaluates how balanced the occupancy is. Note the dispersion is computed as a variance-to-mean ratio of the number of onboard passengers. We expect to see a large AOD value when bus bunching happens, since the number of onboard passengers will be highly imbalanced in those situations.

5.3 Results

Execution Results on Trained Route (R1)

We first evaluate model performance on R1 on which all the MARL models are trained. Fig. 6 presents detailed stop-wise performance comparison. Overall, the result suggests that RL-based models perform better in reducing bus bunching at a lower cost than traditional headway-based control FH. We believe it is because of the long-term reward consideration and informative guidance from state definition in RL models, which are particularly beneficial to efficient transit control. In particular, the proposed CAAC performs the best in stabilizing the system: it shows the smallest AWT and AOD values, while imposing more control interventions than MADDPG. This is mainly due to the fact that MADDPG does not distinguish its own contribution from that of others. Consequently, the reward in MADDPG is mainly determined by the agent's own control actions, leading to biased strategies. IAC can be considered a special case of CAAC, with the event critic component removed. Our results show that IAC is also less effective than CAAC, since the impact from other agents is completely ignored in IAC and therefore it suffers from the uncertainty of the system dynamics.

Fig. 7 shows the trajectory plot colored by occupancy (i.e., number of onboard/capacity) under different control policies based on one random seed. As can be seen, the real-world operation provides a challenging scenario where it is hard to maintain headway regularity over the whole day without any intervention (i.e., NC). Notably, all MARL strategies seem to bring improvements at the upstream segment (i.e., 0-5 km). However, we see that CAAC clearly outperforms IAC and MADDPG in maintaining headway consistency over the downstream segment.

Execution on Untrained Routes (R2/R3/R4)

When applying RL in real-world applications, one critical challenge is to ensure model transferability. As we adopt inductive graph learning in designing the event critic, we expect that trained model on one service can be also applied/generalized to other unseen services. To examine the transferability, we apply the models trained on R1 directly on R2/R3/R4 without retraining. Note that the configurations of R2/R3/R4 in terms of bus stop location, number of stops, and number of buses (i.e., agents) are different from that of R1. In addition, the default timetable and the demand pattern on R2/R3/R4 also differ substantially from those of R1. Thus, this experiment presents an unseen/unfamiliar environment for those RL models trained on R1. To better compare the models, we randomly scale demand with multiple random seeds and runs the model 10 times for each random seed.

Table 2 summarizes the overall performance of different models. For IAC, agents are trained in the environment ignoring the impact from other agents on the system. When transferred to another scenario, the performance greatly deteriorates due to the variation in dynamics from other agents. For MADDPG, it only partially considers actions from other agents given the uncertainty in agent states (i.e., activated or not). As a result, MADDPG performs worse on R2/R3/R4 than on R1. In contrast, the proposed CAAC shows superior transferability when applied to R2/R3/R4 in terms of system stability, maintaining comparable performance to that of R1. The above transferability analysis reinforces the point that, in an asynchronous setting, the training process clearly benefits from taking those undetermined events into consideration. As an example, CAAC demonstrates remarkable inductive power and transferability to unseen scenarios.

6 Conclusion

In this paper, we develop an asynchronous multi-agent reinforcement learning model to improve dynamic bus control and reduce bus bunching. In particular, we propose CAACa credit assignment framework to address the asynchronous issue in multi-agent control problems, which is often overlooked in previous studies. To effectively consider the impact/contribution of other agents, we design an inductive critic by combining an ego critic and an event critic. This design can be easily embedded in the actor-critic framework, and it turns out to be efficient and effective in policy training. Overall, our results demonstrate that the proposed CAAC framework is simple but very effective in characterizing the marginal contribution from other agents in bus holding as an ASMR problem. The graph neural network-based inductive critic offers additional generalization and inductive power, which allows us to apply a well-trained model directly on a new bus route.

There are several directions for future research. While the current model trains the agents with randomly scaled demand, we suspect that the performance of agents can be further improved using more informative/reasonable demand patterns. Another future research direction is to incorporate more traffic entities (e.g., traffic signals) with the inductive architecture and develop a more comprehensive traffic control policy such as signal priority for buses. Finally, the method can be generalized to other applications with similar spatiotemporal asynchronous patterns.

Acknowledgments

This research is supported by the Fonds de Recherche du Qu´ebec - Soci´et´e et Culture (FRQSC) under the NSFCFRQSC Research Program on Smart Cities and Big Data, and the Canada Foundation for Innovation (CFI) John R. Evans Leaders Fund.