LCPPO: An Efficient Multi-agent Reinforcement Learning Algorithm on Complex Railway Network

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 16:38:25

Abstract: The complex railway network is a challenging real-world multi-agent system usually involving thousands of agents. Current planning methods heavily depend on expert knowledge to formulate solutions for specific cases and are therefore hardly generalized to new scenarios, on which Multi-agent Reinforcement Learning (MARL) draws significant attention. Despite some successful applications in multi-agent decision-making tasks, MARL is hard to be scaled to a large number of agents. This paper rethinks the curse of agents in the centralized-training-decentralized-execution paradigm and proposes a local-critic approach to address the issue. By combining the local critic with the PPO algorithm, we design a deep MARL algorithm denoted as Local Critic PPO (LCPPO). In experiments, we evaluate the effectiveness of LCPPO on a complex railway network benchmark, Flatland, with various numbers of agents. Noticeably, LCPPO shows prominent generalizability and robustness under the changes of environments.

Main paper: 
 introduction: 
 Multi-agent Reinforcement Learning (MARL) has drawn 20 significant attention in multi-agent decision-making tasks, e.g. continuous control on robots (Yan et al. 2023) , playing strategic video games (Wang et al. 2022b ), distributed voltage control on grid networks (Wang et al. 2022a ) and cooperation in autonomous driving (Keviczky et al. 2007) .Although MARL has sparked significant interest in the community, its successful applications are primarily concentrated in cases where the number of agents is limited (less than 10). Most existing MARL algorithms still suffer from increasing complexity with more agents in the system. This can partially explain why MARL is still unable to master the complex railway networks, where there exist at most thousands of agents. Flatland (Mohanty et al. 2020 ) is an opensource platform simulating traffic on complex railway networks. In this platform, MARL has not yet outperformed the traditional optimization approaches, which motivates us to specifically design a more efficient paradigm assisting MARL to address the real-world problem in this work.In this paper, we begin by investigating the reason why existing MARL algorithms would fail on complex railway networks. The training of the multi-agent systems is a non-stationary stochastic process from the single agent's perspective so that independent learning (Claus and Boutilier 1998) will receive an unstable training process. To address this issue, MARL algorithms heavily rely on the Centralized-Training-Decentralized-Execution (CTDE) (Oliehoek, Spaan, and Vlassis 2008) paradigm. Based on CTDE, each agent can gather information from other agents during training (i.e., coordinating and communicating with other agents). This information is encoded in agents' policies so that they can still perform harmoniously with local observations during execution. Figure 1 provides an intuitive example of independent learning and CTDE on actor-critic-based methods. Figure 1b visualizes the independent learning that each agent has an independent critic with its own observation and action as inputs, denoted "independent critic". Figure 1c concludes most popular CTDEbased methods (Lowe et al. 2020; Wang et al. 2020a; Sunehag et al. 2018) in the MARL society. There exists a global mixer gathering all other agents' actions and observations. The global information is then fed into the critic network (denoted "global critic") to produce a more consistent value prediction and eliminate the non-stationarity. Nevertheless, the complexity of the global critic grows along with the number of existing agents, which results in the global information being redundant so that the learning procedure would be unstable in practice (Yu et al. 2022) . On the other hand, both paradigms of forming critics do not utilize the physical information existing in the physical system (e.g. the group structure 1a from the railway network). In this work, we propose the local critic 1d paradigm by taking advantage of the provided group structure depicting the spatial relationship among agents to mitigate the above issue incurred by the global critic.Nevertheless, there exist several challenges to directly applying the local critic to MARL. First, the group structure (e.g. members, connections, size) is non-static and each agent may be involved in different groups throughout the whole process, which prompts the introduction of a novel mixing network to deal with variations of the group structure. The output of this mixing network usually has a practical implication as the group long-term value in previous works (Sunehag et al. 2018; Rashid et al. 2018) , which is difficult to track in this scenario when the group is formalized and unravelled temporarily. The second challenge is how to appropriately clarify the contribution of each agent to a certain group. When an agent had joined different groups along a trajectory, it would be non-trivial to study which past groups or group members its long-term rewards might be influenced by, which directly impacts the policy optimization.Our main contribution is to sweep away the practical issues of incorporating the local critic into multi-agent systems, namely dynamic group and agent coordination. Our method is easy to implement on actor-critic frameworks like PPO, leading to a practical MARL algorithm LCPPO. Furthermore, our approach demonstrates superior performance over other MARL baselines on a complex railway network simulator Flatland with various numbers of agents. Finally, our method shows additional generalizability and robustness regarding environmental changes in the network sys-100 tem, which reveals LCPPO to be a promising approach in real-life applications.Vehicle Planning Problem as modelled in the Flatland Environment has been an active research area within the op-105 erations research (OR) community dating back to decades (Bodin and Golden 1981; Ryan and Foster 1981) . To the Flatland challenge, the winning solution in 2020 (Laurent et al. 2021 ) was from the perspective of Multi-Agent Path Finding (MAPF) (Stern et al. 2019) combining it with other optimisation techniques. For example, to handle malfunctions, an improved version of Minimum Communication Policies (MCP) (Ma, Kumar, and Koenig 2016) was used to avoid the deadlocks by stopping some trains to maintain the order that each train visits each location. Overall, most mentioned OR methods heavily depend on expert knowledge to formulate solutions for specific cases and are therefore hardly generalized to new scenarios. Moreover, they all need global information for planning, which is inefficient and unstable for unforeseen situations.The ever-growing complexity of railway networks and a need for real-time rescheduling makes OR methods infeasible and has paved the way for MARL solutions owing to their success in optimisation problems. However, scalability to a large number of agents and efficient coordina-125 tion of individual agents remain major challenges. Currently, two parallel approaches are attempting to manage both challenges. The first approach is learning decentralized policies and adding communication between agents (Foerster et al. 2016; Sukhbaatar, Szlam, and Fergus 2016; Das et al. 2019) .These methods are sometimes bothered by the communica-tion bandwidth and latency and are not appropriate for railway systems where agents are far away. The other approach is centralized-training-decentralized-execution (CTDE) introduced in Background. To implicitly handle coordination during training, MARL methods usually require a global critic to gather all agents' information (Lowe et al. 2020) , or decompose a global critic into individual value functions (Sunehag et al. 2018; Rashid et al. 2018 Rashid et al. , 2020;; Wang et al. 2020b) . All of them suffer from large joint state-action space and cannot scale to the number of agents. This directly motivates the local critic approach proposed in this paper. Yang et al. (2018) have already investigated issues of large scalability in MARL, unfortunately, which simplifies agents based on static neighbouring information and is difficult to apply on dynamic railway network setups.Multi-agent reinforcement learning (MARL) is a domain that combines multi-agent learning and reinforcement learning to solve a game model depicting a realistic problem. In this work, we apply MARL as a basic learning framework to solve the complex railway network. Following the common setting in MARL, we model the multi-agent system (MAS) as a partially observable stochastic game (POSG) which can be expressed as the following 7-tuple (Kumar and Zilberstein 2009) such that ⟨N , S, A, O, {r i } i∈N , T, b 0 ⟩. More specifically, N = {1, 2, ...} is a set of agents existing in the MAS. S is a set of available states. O = × i∈N O i is a joint observation set, where O i is agent i's observation set; while A = × i∈N A i is a joint action set, where A i is agent i's action set.Each agent i is equipped with a reward function to evaluate its performance such that r i : S × A → R. Additionally, the transition function of the MAS can be described as follows: T : S × A → ∆(S × O), where ∆(X ) is the set of all probability distributions defined over a set X . b 0 ∈ ∆(S) is the initial state distribution. The objective of POSG is to maximize each agent's individual discounted cumulative rewards by a stationary policy πi : O i → A i such that max πi E[ ∞ t=0 γ t r i (s t , a t )],where γ ∈ (0, 1) is a discount factor, s t ∈ S and a t ∈ A. In MARL, the usual learning paradigm to solve POSG is called the multi-agent actorcritic framework, for which each agent individually applies the actor-critic framework to optimize its policy. Two of the most popular algorithms based on this paradigm are IPPO (de Witt et al. 2020) and MAPPO (Yu et al. 2022) , which extends the vanilla multi-agent actor-critic framework by incorporating the PPO algorithm (Schulman et al. 2017) . In this work, we propose Local Critic PPO based on MAPPO via formalizing the critic with GNNs to capture sufficient information from the complex railway network.MARL algorithms are applied either as fully centralised methods where a single policy with joint action is learned for all agents or in an independent agent learning setting -also called decentralised learning where agents are optimised separately. Nevertheless, the fully centralised method could lead to the curse of dimensionality to impede learning the optimal joint policy, while the independent learning (e.g. IPPO) may result in the non-stationary learning procedure (Hernandez-Leal, Kartal, and Taylor 2019). To trade off the benefits and drawbacks of these two paradigms, Centralised Training and Decentralized Execution (CTDE) (Oliehoek, Spaan, and Vlassis 2008 ) (e.g. MAPPO) was proposed to form each agent's critic by all other agents' information (e.g. observations and actions), still maintaining the decentralised policies to approximate the joint policy as used in independent learning paradigm to avoid the curse of dimensionality. Standing by the view of application, a limitation of CTDE is that it always collects the information of all agents to form a critic for an agent i, however, in physical scenarios some agents could not influence agent i. This would inevitably cause some unnecessary fluctuations on the approximate critic, leading to potential learning instability (Yu et al. 2022 ). To mitigate this issue, we propose the local critic to aggregate the sufficient agents' information, based on the existing physical information (e.g. a tree structure describing the spatial relationship among agents) provided by the complex railway network. This would directly filter out the information of irrelevant agents, to reduce the instability induced especially from the scenarios with a large number of agents. The outstanding performance of the proposed local critic sheds light on the necessity of incorporating known physical information into design when dealing with real-world problems.Learning (LCMARL) Figure 2 provides an overview of the overall approach of incorporating the local critic into the MARL framework, in particular actor-critic-styled algorithm.Suppose N agents in the system, and they receive their local observations o t = (o 1 t , o 2 t , . . . , o N t ) at each step t. Without loss of generality, we assume global state s t = o t . However, from the single agent's view, the system is still partially observable. The group structure g t is a graph represen-235 tation with N nodes and E edges, which can be naturally constructed in the railway system. In specific, two agents share an edge if they are on rails connected by less than one crossroad. For each agent i, the number of its neighbouring agents N t (i) is usually much less than N due to the sparsity 240 property in railway systems.All observations are further passed into the local-critic networkV (o t , g t ; ϕ) : O × G → R to predict agents' in- dividual values v t = (v 1 t , v 2 t , . . . , v N t ), where G is the space of group structure. The local-critic network is represented as 245 a neural network parameterized with ϕ, as illustrated in Fig- ure 2b . The network utilizes the group structure g t within the GNN (Scarselli et al. 2009 ) layer. For each agent i, it ensures its local information can only flow inside its neighbouring agents N t (i). If the neighbouring size is limited to G and 250 the number of agents N , the complexity of GNN is O(GN ) compared with O(N 2 ) of the global critic in Figure 1c , and thus easily speedup on hardware (Wang et al. 2023 ) when G ≪ N . In practice, the GNN structure is implemented with the transformer (Vaswani et al. 2017 ) architecture with the 255 mask mechanism.The biggest challenge in learning the local-critic network is the evolving group structure g t . For agent i, it's urgent to discover its influence on its neighbouring agents N t (i) in 260 several successive steps, but N t (i) can change at every step. To mitigate this issue, we propose a concept of the imaginary step t (red dashed frame in Figure 2a ). The imaginary step t utilizes the observations o t+1 but maintains the group structure g t . By passing through the local-critic network, we ob-265 tain virtual values ṽt+1 = V (o t+1 , g t ). Since values ṽt+1 and values v t (individual values at step t) are calculated with the same group structure g t , there exists an iterative relation with these values and rewards r t , which will be further introduced in the next section.With the introduction of the imaginary step, values at different steps are connected with the same group structure. In detail, assume the predicted values at step t are v t = V (o t , g t ; ϕ) for all agents, while the imaginary values at step t+ 1 are ṽt+1 = V (o t+1 , g t ; ϕ). These values repre-275 sent the same meaning: the discounted expected cumulative return agents can achieve under the static group structure g t . We denote the i-th output of V (o t , g t ; ϕ) as V i (o t , g t ; ϕ) for simplicity. According to the dynamic programming techniques (Sutton and Barto 2018) , the extended Bellman equa-280 tion for any i on value function V i can be derived:EQUATION)where γ is the discount factor to account for future steps.The expectation is concerning the next observations, actions and rewards. The complicated expectation computation is! ! ! + 1 % &'( ( % &'( ) % &'( * + , -'.. Equation 1 indicates that the value of agent i is only accounted for by the received individual reward r i t . It is imperfect since agents could reach a local sub-optimal solution as Prisoner's dilemma in Game Theory. Instead, we would like to encourage agents to find solutions better for global interest.Inspired by the VDN method by Sunehag et al. (2018) , they utilized the monotonicity of the addition calculation and summed all individual values V i as the global value, to encourage cooperative behaviours among agents. Similarly, we sum all individual values inside each agent i's neighbourhood to encourage agent coordination inside this local group, which requires much less computation compared with VDN on a global group. Moreover, with the evolution of the local group, agents will possibly have a chance to coordinate with different agents when necessary. The modified Bellman equation takes place on the local-group level instead of on the single-agent level:j∈Nt(i) V j (o t , g t ; ϕ) = E at,rt,o t+1 j∈Nt(i) r j t +γ j∈Nt(i) V j (o t+1 , g t ; ϕ) .(2) Intuitively, agent j learns to maximize its own value V j , which also contributes to the local group value.Equation 2 describes the recursive definition (Bellman Equation) of the value function with a local-critic perspective, which can be further used to in policy evaluation. For a complete RL algorithm, policy improvement is also required to learn a better policy. In this paper, we rely on the successful single-agent RL algorithm PPO (Schulman Algorithm 1: LCPPO 1: Input: initial parameters θ 0 for policy function π, initial parameters ϕ 0 for value function V 2: for k = 1, 2, • • • , K do 3: Set data buffer D k = ∅ 4: for j = 1, 2, • • • , J do 5: Collect trajectory τ j = {o 0 , a 0 , r 0 , g 0 , o 1 , • • • , }τ j ← τ j ∪ {v Nt(j) t , ÂNt(j) t , RNt(j) t } 13:end for 14:D k ← D k ∪ {τ j } 15:end for 16:Update value function's parameters ϕ with Adam optimizer (Kingma and Ba 2015) by fitting rewards-to-go:ϕ k+1 = arg min ϕ τ ∈Dk t=0 Nt(j) i∈Nt(j) V i (o t , g t ; ϕ)- RNt(j) t 2 17:Update policy function's parameters θ with Adam optimizer (Kingma and Ba 2015) by maximizing multiagent PPO objective:θ k+1 = arg max θ τ ∈Dk t=0 Nt(j) i∈Nt(j) c i t (θ) ÂNt(j) t , clip(r i t (θ), 1-ϵ, 1+ϵ) ÂNt(j) t where c i t (θ) = π(a i t |o i t ;θ) π(a i t |o i t ;θk)et al. 2017) as the backbone, and develop a novel MARL algorithm, denoted as Local-Critic PPO (LCPPO). The specific procedure is explained in Algorithm 1. We assume homogeneous agents and the policy function is π i (o i t ; θ) = π(o i t ; θ) for any agent i with parameters θ and value function is V (o t , g t ; ϕ) with parameters ϕ. Agent i's individual value function is denoted as V i (o t , g t ; ϕ), which is the ith output of V (o t , g; ϕ). LCPPO can be extended to heterogeneous agents in future work with individual policy and value functions. For each agent j's neighbouring group N t (j) derived from group structure g t , the group value is defined as the sum of group members' individual values: vNt(j) t = i∈Nt(j) V i (o t , g t ; ϕ).The key modification to PPO method is on Line 9 that the local group reward r Nt(j) t is modified with an additional correction term γ(ṽNt(j) t+1 -v Nt+1(j) t+1). This term is designed to compensate the calculations on advantages ÂNt(j) t so that it accounts for virtual values instead of real values to follow Equation 2.Task Description We evaluate the LCPPO on Flatland (Mohanty et al. 2020) , a simplified grid environment to simulate the railway networks with an easy-to-use machine learning interface. The goal is to control each vehicle with different routes to arrive safely and punctually. Figure 4 visualizes the running process in Flatland. We mainly follow the official environmental configurations 1 with 10/20/30 agents respectively. In particular, the map size is 30 × 30 with 3 cities (2 cities for 10 agents). The max rails between cities are 2 and there are 2 rail pairs in each city. The malfunction rate is 0 and the speed for the vehicle is 1.0 grid per step, and verified in later analysis.Regarding the MARL setup, we follow the previous setup (Jiang et al. 2022 ) that each agent i receives a local observation o i t at step t consisting of two parts: agent attributes X attr and tree-structured representation X tree . X attr describes the individual attributes of each agent with 83 dimensions, e.g. scheduled departure and arrival time. X tree represents the spatial information on the grid environment, which is encoded as the tree structure X tree = (node V v=1 , edge E e=1 ) includes V = 31 nodes with 12-dimensional node attributes node v and E = 30 edges with 3-dimensional attributes edge e indicating connected nodes. All the information is derived from the spanning tree, which is constructed by traversing from the agent's location and branch at each possible crossroad. Please refer to Jiang et al. (2022) for the detailed description of the spanning tree and attributes. The action space includes five discrete actions: do nothing, go forward, stop, turn left, and turn right. Regarding the group structure needed by LCPPO during training, it's defined as follows: for each agent, any other agents who appear in the first level of its spanning tree belong to the same group. The common group size is less than 5, which is much less than the total number and guarantees the efficiency of LCPPO.1 https://flatland.aicrowd.com/challenges/neurips2020/envconfig.html Evaluation Metric We adopt multiple objectives to evaluate the performance of different methods. Each agent re-370 ceives an individual reward signal at each step, consisting of the following items:• Arrival Reward: r a t = 1 if the agent reaches the target and r a t = 0 otherwise; • Deadlock Penalty: r l t = -1 if the agent immerses in 375 a deadlock and r l t = 0 otherwise. A deadlock happens when two trains step into a single trail from opposite directions. The deadlock quickly blocks the rails and catastrophically paralyzes the whole system, and thus should be penalized.• Environment Reward: To encourage the train to arrive on time, Flatland environment (Mohanty et al. 2020 ) provides an environmental reward defined asEQUATIONwhere B is the latest arrival time, T max is the system's maximum running steps and d is the shortest path Man-385 hattan distance between the train's position and its target at T max . The intuition of the reward is to punish the delays after the scheduled latest time. The final reward for agent i is the weighted sum of all terms above: r i t = c e r e t + c a r a t + c l r t l , where c e = 1.0, c a = 5.0 390 and c l = 2.5 follows previous work (Jiang et al. 2022) .• IPPO implements the structure as in Figure 1b . Each critic only relies on local observation during training. • MAPPO represents the structure as in Figure 1c and pre-395 vious work (Yu et al. 2022) . The critic network gathers all agents' observations as input and predicts the value. • LCPPO follows Algorithm 1 introduced in this paper.Theoretically, the critic network only utilizes observations from its neighbours. Practically, we use all agents' 400 observations and adopt a Transformer (Vaswani et al. 2017 ) layer with the mask mechanism to imitate the effects. For a fair comparison, all baselines share the same actor network structure of a 2-layer feedforward neural network 405 with 64 hidden units each. Notably, the parameter sharing technique (de Witt et al. 2020) is enabled among agents for efficient learning. The critic network has a hidden-layer structure as the actor network, and there is an additional transformer layer to group local information in LCPPO.Other hyperparameters are demonstrated in Table 1 .The main results of 10/20/30 agents are shown in Figure 3 . All experiments are carried out with 5 random seeds and the average performances are plotted with standard deviation 415 as shaded area. All evaluation metrics are averaged across participating agents. In terms of the arrival ratio and environmental reward, all experiments share a similar trend of LCPPO > IPPO > MAPPO, which is strong evidence that the local critic successfully guides the coordination of agents thus leading to more on-time arrivals. Notably, MAPPO can't learn anything with the increasing number of agents. This result complies with the curse of agent issues occurring in the MARL area as explained in the Introduction.Generalization (Kirk et al. 2023 ) is essential for learningbased methods since there might be mismatches between training and testing environments in practice, which also applies to the railway system. There are various malfunctions in real-world railway trails. Besides, it's common to add or reduce train routes, which all require rescheduling plans. In theory, LCPPO only utilizes local information to guide planning behaviours. When mismatches happen in the system, To demonstrate the generalization of LCPPO, we design the following experimental setups: we first utilize different algorithms to train planning policies on environments defined in the setups. Later on, certain components of the environment are modified to simulate the mismatch in the system and all policies are tested on newly changed environments without further tuning. Regarding the changing components, we consider the following scenarios: All experiments are carried out with 5 random seeds and we report the average arrival ratio and its standard devi-460 ation in Table 2 . Apparently, LCPPO is the most robust algorithm among all baselines. The global critic method (MAPPO) is the least favourite method under environmental mismatches. This proves our concerns about current stateof-the-art MARL methods. The number of agents is the most influential factor to all baselines, which calls theories from open team research (Rahman et al. 2021) .This paper focuses on the applications of MARL on complex network railway networks. The failure of state-of-the-470 art MARL methods in such a large-scale environment directly motivates this work. We proposed the local critic idea and achieved an efficient MARL algorithm LCPPO. LCPPO scales efficiently with the number of agents on the Flatland challenge and performs better and more robustly than other 475 baselines.Despite the advantages provided by the local critic, LCPPO still renders some deadlocks and unsuccessful plannings, which is non-negligible in real-world applications. It implies that the CTDE paradigm might not be enough to handle the coordination on agents (Zhou et al. 2023 ). Therefore, it would be beneficial to include communications among local groups or global information (graph structure, other agents' observations...) during execution for global optimal solutions. Besides, current updates on the value function rely on the sum of rewards in the local group, which treats all agents with identical importance. This assumption might be wrong for heterogeneous multi-agent systems. A more advanced credit assignment technique should be considered (Rashid et al. 2018; Wang et al. 2022b ) and extended 490 to dynamic group scenarios. 
 
 Appendix:  


Decision: he paper addresses an interesting application of MARL approach to solve a problem which has been well solved by the Operations Research community. 

After the rebuttal, the reviewers unanimously agree that there is merit in the paper, though the contribution is not (yet) major, as experimental results show that their MARL approach is still inferior compared with a traditional OR approach.  

We like the authors to include comparison with the winning OR solution of the Flatland Challenge in the final version of the paper (which they have included in the rebuttal). They might like also to revise the title of the paper to better reflect its focus.

Reviews: review: strength_weakness: strength_weakness: comparison to general CTDE methods, without any comparison to RL leader (7th place overall) of the 2020 challenge.

No comparison to the winner the challenge. That case is especially interesting both as it is a planning method and known and relevant to the ICAPS audience,  and second, even if the RL method proposed is inferior to it, the discussion and using it as the bar for RL is important, interesting to see how far RL still needs to go on that application.

It would have been interesting to see some ablation study on the component of LCPPO and not just the final results.

Minor: (de)centralised or (de)centralized - but variation appear in the paper, for consistency choose one.
questions: questions: Beyond the weaknesses, just a general concern: what is the relevance to the ICAPS community? unless I missed something, it seems as a pure RL paper, that can can more supportive audience in a learning venue.
strength_weakness: strength_weakness: The paper does not allow sufficient reproducibility in its current form. Insufficient information is provided on essential components, e.g. the GNN. 

Essentially, the novelty of the paper lies in the fact that not all agents are included, but only a so-called neighboring group. The authors are only partially successful in defining this neighboring group, and there is also a lack of in-depth analysis as to whether other generation rules are more suitable for creating the neighboring group. 

The state of the art is insufficiently elaborated. It is very narrowly defined, which is why other works that deal with local vs. global optimization are not taken into account. Further evaluations should have been carried out at this point.

Some of the statements, especially in the introduction, are without sources or a comprehensible explanation. The selection of sources (e.g. strategic video games) also seems arbitrary and does not take up the fundamental work in these areas.
questions: questions: 1. Please define the role of the GNN in your work more clearly.
2. Why did you define the neighboring group as you did? Did you evaluate other generation rules e.g. more than one crossroad.
3. To what extent would you agree that your approach is only an incremental development of MAPPO? 
4. With regard to generalization: To what extent are the implemented changes proof of generalization? The change in speed does not seem to play any role at all for generalization or learning, and the malfunctions also address a temporal aspect, which does not come into play in your state description, since an action evaluation takes place in the observation of the agent. Surely no assumptions are made about the future here? There is neither stacking nor any recurrent information flows.
strength_weakness: strength_weakness: Weaknesses are in above text box
questions: questions: Questions are in above text box