Shared Recurrent Memory Improves Multi-agent Pathfinding

Authors: alsu  sagirova
yuri  kuratov
mikhail  burtsev
Venue: NeurIPS_cc_2024_Workshop_UniReps
Published: 2024-09-24 13:02:15

Abstract: Multi-agent systems are gaining attention in AI research due to their ability to solve complex problems in a distributed manner, but coordinating multiple agents remains challenging. Inspired by the global workspace theory, we introduce the Shared Recurrent Memory Transformer (SRMT). SRMT extends memory transformers to multi-agent settings by pooling and globally broadcasting individual working memories, enabling agents to implicitly exchange information and coordinate behavior. We evaluate SRMT on the Partially Observable Multi-Agent Path Finding in a bottleneck navigation task requiring agents to pass through a narrow corridor. SRMT consistently outperforms a range of reinforcement learning baselines, especially under challenging reward structures with sparse feedback. Our experiments also demonstrate that SRMT generalizes effectively to environments with significantly longer corridors than those seen during training, highlighting its scalability and robustness. These results suggest that incorporating shared memory structures into transformer-based architectures can enhance coordination in decentralized multi-agent systems.

Main paper: 
 introduction: 
 Multi-agent systems have significant potential to solve complex problems through distributed intelligence and collaboration. However, coordinating the interactions between multiple agents remains challenging, often requiring sophisticated communication protocols and decision-making mechanisms. We propose a novel approach to address this challenge by introducing a shared memory as a global workspace for agents to coordinate behavior. The global workspace theory [Baars, 1988] suggests that in the brain, there are independent functional modules that can cooperate by broadcasting information through a global workspace. Inspired by this theory, we consider the agents in MAPF as independent modules with shared memory and propose a Shared Recurrent Memory Transformer (SRMT) as a mechanism for exchanging information to improve coordination and avoid deadlocks. SRMT extends memory transformers [Burtsev et al., 2020 , Bulatov et al., 2022 , Yang et al., 2022 , Cherepanov et al., 2024] to multi-agent settings by pooling and globally broadcasting individual working memories.In this study, we test the shared memory approach on Partially Observable Multi-agent Path Finding (PO-MAPF) [Stern et al., 2019] , where each agent has to reach its goal while observing the state of the environment, including locations and actions of the other agents and/or static obstacles, only locally. Multi-agent pathfinding can be considered in the decentralized manner, where each agent independently collects rewards and makes decisions on its actions. There are many attempts to solve this problem: in robotics [ Van den Berg et al., 2008 , Zhu et al., 2022] , in machine and reinforcement learning field [Damani et al., 2021 , Ma et al., 2021b , Wang et al., 2023 , Sartoretti et al., 2019 , Riviere et al., 2020] . Such methods often involve manual reward-shaping and external demonstrations. Also, several works utilize the communication between agents to solve decentralized MAPF [Ma et al., 2021a , Li et al., 2022 , Wang et al., 2023 ]. Yet still, the resulting solutions are prone to deadlocks and poorly generalizable to the maps not used for training. In this work, we compare SRMT to a range of RL baselines and show that it consistently outperforms them in the bottleneck navigation task. 
shared recurrent memory transformer: 
 In SRMT, the input sequence for each agent at each time step is constructed by combining three key components: the agent's personal memory vector; the historical sequence of the agent's observations from the past h = 8 time steps; and the current step's observation. This sequence undergoes a full self-attention mechanism. Next, the output of the self-attention is passed through a cross-attention layer between current hidden representations and shared memory. The shared memory consists of a globally accessible, ordered sequence of all agents' memory vectors for the current time step. This interaction between personal and shared memory enables each agent to incorporate global context into its decision-making process. The resulting output is then passed through a memory head, which updates the agent's personal memory vector for the next time step. Simultaneously, the output is also fed into the decoder part of the policy model, which generates the agent's action (Fig. 1A ).We use POGEMA [Skrynnik et al., 2024a] framework for the experiments. In POGEMA the twodimensional environment is represented as a grid composed of obstacles and free cells. At each time step each agent can perform two types of actions: moving to an adjacent cell or remaining at their current position. Agents have limited observational capabilities, perceiving other agents only within a local 5 × 5 area centered on their current position. The episode ends when the predefined time step, episode length, is reached. The episode can also end before this time step if certain conditions are met, i.e. all agents reach their goal locations.As an initial test of our approach, we selected a simple two-agent coordination task where the agents must navigate through a narrow passage. The environment consists of two rooms connected by a one-cell-wide corridor, as illustrated in Fig. 1B . Each agent starts in one room, and their goal is located in the opposite room, requiring both agents to pass through the narrow corridor to complete the task. To train the model, we utilized 16 maps with corridor lengths uniformly selected between 3 and 30 cells.To evaluate the performance, we utilize three metrics: Cooperative Success Rate (CSR) -a binary measure indicating whether all agents reached their goals before the episode's end; Individual Success Rate (ISR) -the fraction of the agents that achieved their goals during the episode; and Sum-of-Costs (SoC) -the total number of time steps taken by all agents to reach their respective goals (the lower the value the better). The policy function is approximated with a deep neural network (see Appendix Fig. 4 ). The agents are assumed to be homogeneous, so the policy is shared between agents during training. To benchmark the effectiveness of SRMT, we compared it against several baselines: recurrent memory transformer without memory sharing (RMT), transformer without memory (Attention), direct connection of spatial encoder to actor-critic action decoder (Empty), GRU RNN (RNN). Among these baselines, RMT, Attention core and Empty core methods can be considered as ablations of SRMT architecture. We also trained and evaluated MAMBA [Egorov and Shpilman, 2022] and QPLEX [Wang et al., 2020] as baselines. Additional details regarding the training procedure can be found in Appendix A.1. 
results and discussion: 
 We first evaluated SRMT against the baseline models using three variations of the reward function: Directional, Moving Negative, and Sparse.2 In the Directional setting, the agent was rewarded for reaching the goal and for every step that brought it closer to the goal. In Moving Negative movements are slightly penalized for minimizing the path to the goal but no information about the goal location is provided. In contrast, the Sparse reward function only gives a reward when the agent successfully moves into the goal cell, offering no intermediate rewards. The comparison of evaluation scores, shown in Figure 2 , demonstrates that SRMT successfully solves the task under considered reward functions. In particular, SRMT consistently performed well, even in the challenging Moving Negative and Sparse reward scenarios where other methods struggled. Considering the Sparse reward, the difference between SRMT and RMT scores is statistically significant (Wilcoxon signed-rank test, p < 0.001). The ability to coordinate across agents via shared memory proved critical, especially when feedback from the environment was minimal.Among the non-memory sharing methods, RMT achieved the best performance, outperforming both the GRU-based RNN and the vanilla transformer models. This indicates that the combination of self-attention with recurrence in RMT offers distinct advantages in multi-agent coordination, particularly in tasks that require sequential decision-making over time. However, without the shared memory, RMT's performance in the Sparse reward setting was still limited compared to SRMT, highlighting the importance of global information exchange. To further assess the generalization capabilities of the trained policies, we evaluated them on bottleneck environments with corridor lengths significantly larger than those used during training, ranging from 5 to 1000 cells. The evaluation results3 for the Sparse and Moving Negative reward functions are shown in Figure 3 .The results indicate that trained with the Sparse reward function, the SRMT-based policy consistently outperforms the baseline methods regarding both the individual success rate (ISR) and the total time spent in the environment (SoC). Remarkably, SRMT scales effectively up to corridor lengths of 400 cells without any significant performance degradation. For corridor lengths beyond 400 steps, the Cooperative Success Rate (CSR) of SRMT drops from 1.0 to 0.8, which still surpasses the other models, except for RMT. RMT shows the highest stability across all tested corridor lengths, Figure 3 : SRMT agents generalize on corridor lengths up to 1000. After training on corridor sizes from 3 to 30 cells all methods were evaluated on longer passages up to 1000. All models show good scaling till 100 while memory-based transformers were able to scale beyond that. For the Sparse reward, SRMT leads up to 400 and then drops below RMT for collective performance. For the Moving Negative reward, SRMT shows the top-1 performance on all three metrics. The shaded area indicates 95% confidence intervals. maintaining a score of 0.9 for CSR across the board. For the Moving Negative reward function, resulting policies with SRMT show the top-1 scores for any corridor length up to 1000 (see Fig. 3 ). Evaluation scores for the other reward functions and analysis of memory representations can be found in Appendix A. 
conclusion: 
 In this paper, we introduced the Shared Recurrent Memory Transformer (SRMT) as a novel architecture for enhancing coordination in multi-agent systems. SRMT enables agents to exchange information implicitly and coordinate actions without explicit communication protocols. Our experimental results on the bottleneck navigation task demonstrate that SRMT consistently outperforms baseline models, especially in challenging scenarios with sparse rewards and extended corridor lengths. The shared memory mechanism allows agents to generalize their learned policies to environments with significantly longer corridors than those seen during training, demonstrating the scalability and robustness of our approach. These findings highlight the potential of incorporating shared memory structures in transformer-based architectures for multi-agent reinforcement learning. 
 
 Appendix: As in the majority of research related to Multi-Agent Path Finding (MAPF), in this work we assume that the agents have flawless localization and mapping abilities. Our primary focus is on the decisionmaking aspect of the problem. We also consider that the agents execute actions accurately and that their moves are synchronized. Additionally, we treat obstacles as fixed elements of the environment.Finally, it's important to note that our approach, like other prominent learnable methods designed for (PO)-MAPF -such as PRIMAL [Sartoretti et al., 2019] , PRIMAL2 [Damani et al., 2021] , DHC [Ma et al., 2021a] , and PICO [Li et al., 2022] -does not offer theoretical guarantees that agents will reach their destinations. However, extensive experimental evidence, both from our work and from the referenced studies, demonstrates that these learnable methods are practically powerful and scalable solutions for complex MAPF problems.https://github.com/Aloriosa/srmt Preprint.See Appendix A for details of rewards and extra results.For these evaluations, we adjusted the episode length to 2 • corridor_len + 100 to ensure that both agents had sufficient time to reach their goals within each episode. 


Decision: In light of the positive reviewers' feedback and relevancy of the submission, we are pleased to accept this paper for presentation at UniReps 2024. We kindly ask the authors to incorporate the reviewers' suggestions and feedback in the final camera-ready version of the manuscript.

Reviews: review: title: title: Sound methodology, SRMT offers minor improvements over RMT with situation-dependent performance, but may diverge from the workshop's focus.
main_review: main_review: This paper introduced a revision for the recurrent memory transformer (RMT). Here this Shared RMT aims to improve the multi-agent coordination. 

The methodology is sound, including solid task design for multi-agent coordination, policy learning architecture, nicely designed metrics. The reasons for the model selected are valid though the most proceeding architecture is not implemented. More clarification details will be better, such as the core part is replaced by various benchmarks to assess the SRMT performance.

Based on the results, there are the similarities in performance between SRMT and RMT, and that the improvement of SRMT over RMT may be minor and situation-dependent. In terms of performance, SRMT's results (CSR, ISR, SoC) are largely comparable to the original RMT, particularly in the directional and moving negative reward functions. SRMT may show an advantage in the sparse reward condition, but the statistical significance of this improvement is unclear. Regarding generalization, SRMT outperformed RMT in the extended corridor length scenario for multi-agent pathfinding. However, RMT still demonstrates strong and stable performance, outperforming other baseline models. Given the computing power required, the overall model performance, and the complexity of more realistic pathfinding scenarios (with corridor lengths under 100), RMT might be sufficient for most practical applications.

Additionally, while the paper introduces SRMT to enhance multi-agent coordination, its focus on task-specific performance improvements and pathfinding does not directly address the workshop's core theme of neural representation convergence.
title: title: Sensible extension to RMT for MAS, but weak performance justification
main_review: main_review: Incorporating shared memory in the cross attention block demonstrates the authors have an sound understanding and appreciation for the strengths and weaknesses of a transformer. As such, the paper reads as a natural extension of Recurrent Memory Transformers to multi-agent settings.

The baselines, although well known (Actor-critic,GRU), seem cherry picked.  Justification as to why they picked these baselines would alleviate this concern. Moreover, experiments are run on only one task : POGEMA. Running experiments on at least one other task would  demonstrate the utility of this architecture and alleviate any concerns of cherry picking tasks.

Currently, without the appendix, which the reviewer is not obligated to read, the paper seems a little misleading. For example, the SRMT performance drops below the RNNs for long corridor lengths but nothing is mentioned about it. Overall, the paper is easy to read and understand.

The reviewer recommends that the authors include settings and more baselines along with justifications for the same.
title: title: MARL with Shared Recurrent Memory Transformer architecture
main_review: main_review: Summary: This paper introduces the Shared Recurrent Memory Transformer (SRMT), a novel architecture for multi-agent coordination in partially observable environments. Inspired by the global workspace theory, SRMT extends memory transformers to multi-agent settings by pooling and broadcasting individual working memories. The authors evaluate SRMT on a bottleneck navigation task, demonstrating improved performance over several baselines, especially under challenging reward structures and when generalizing to longer corridors.

Minor Points: 
- The paper provides an abstract but clear motivation for the proposed approach, linking it to established theories in cognitive science. 
- The evaluation on different reward structures (directional, moving negative, and sparse) provides good support into the model's performance and robustness.

Major Points: 
- Although compared with reasonable baselines, the paper might lack comparisons with other methods in MARL, such as Centralized Critics with Decentralized Actors (CCDA) [1], and without these comparisons, it could be challenging to assess the true contribution of SRMT to the field.

Citation: [1] Lyu, X., Xiao, Y., Daley, B., & Amato, C. (2021). Contrasting centralized and decentralized critics in multi-agent reinforcement learning. arXiv preprint arXiv:2102.04402.
title: title: Review of Shared Recurrent Memory Improves Multi-agent Pathfinding
main_review: main_review: Quality:
The work introduces the Shared Recurrent Memory Transformer (SRMT) as a novel architecture for enhancing coordination in multi-agent system. It demonstrates high quality in terms of the research methodology, experimental design, and presentation of results. The authors have provided detailed information about the proposed Shared Recurrent Memory Transformer (SRMT) and its application in multi-agent systems.

Clarity:
The document is well-structured and clearly presents the proposed SRMT model, the experimental setup, and the results. The use of figures and tables generally aids in understanding the experimental outcomes. One potential improvement could be Figure 3 is a little messy and could be improved to increase clarity.

Originality:
The work introduces a novel approach, the Shared Recurrent Memory Transformer, which extends memory transformers to facilitate information exchange and coordination in multi-agent systems. This original contribution adds value to the field of multi-agent systems and reinforcement learning.

Significance:
The study is significant as it addresses the challenge of coordination in multi-agent systems, a critical area in robotics and artificial intelligence. The results demonstrate the effectiveness of SRMT in enhancing coordination and performance in decentralized multi-agent systems, which has practical implications for real-world applications.

Pros:

1. Introduction of a novel approach, SRMT, to enhance coordination in multi-agent systems.

2. Rigorous evaluation metrics and comparison with baseline models.


Cons:

1. Improve the visualization of experimental result

2. The limitations section could be expanded to provide a more comprehensive understanding of the constraints of the proposed approach.

Comments: title: Official Comment by Authors
comment: We would like to sincerely thank all the reviewers for their feedback and positive reviews. We have updated the paper with a few changes:
- We added the evaluation results for the two additional baseline methods: MAMBA and QPLEX.
- We specified the statistical significance of the difference in SRMT and RMT scores for the Sparse rewarding function.
- We added the explanation of the baseline methods choice.
- We updated the presentation of Figure 3.