Shared Memory for Multi-agent Lifelong Pathfinding

Authors: Alsu Sagirova, Yuri Kuratov, Mikhail Burtsev
Primary area: reinforcement learning
Keywords: shared memory, transformers, multi-agent pathfinding

Abstract:
Multi-agent reinforcement learning (MARL) demonstrates significant progress in solving cooperative and competitive multi-agent problems in various environments. One of the main challenges in MARL is the need to explicitly predict other agents' behavior to achieve cooperation. As a solution to this problem, we propose the Shared Recurrent Memory Transformer (SRMT), which extends memory transformers to multi-agent settings by pooling and globally broadcasting individual working memories, enabling agents to implicitly exchange information and coordinate actions. We evaluate SRMT on the Partially Observable Multi-Agent Path Finding problem, both in a toy bottleneck navigation task requiring agents to pass through a narrow corridor and on a set of mazes from the POGEMA benchmark. In the bottleneck task, SRMT consistently outperforms a range of reinforcement learning baselines, especially under sparse rewards, and generalizes effectively to longer corridors than those seen during training. On POGEMA maps,  including Mazes, Random, and Warehouses, SRMT is competitive with a variety of recent MARL, hybrid, and planning-based algorithms. These results suggest that incorporating shared memory into transformer-based architectures can enhance coordination in decentralized multi-agent systems.

Decision: reject
Reviewer scores: 3, 8, 5

Reviews and discussion:
<thread>
creation date:
1730097246738

thread_type:
official_review

<thread_object>
creator: reviewer_r4zr

<content>
summary:
The paper proposes a global shared recurrent memory transformer (SRMT) mechanism for multiagent reinforcement learning to address the multiagent pathing finding problem. Specifically, SRMT uses self-attention to aggregate agent memory and observation history while utilizing cross-attention to aggregate the shared memory from other agents to help coordination. Results on a toy bottleneck navigation task and a set of maze environments from the POGEMA benchmark show that SRMT outperforms various baselines.

strengths:
1.	The motivation for using a global shared memory to help coordination and the idea of using the transformer to implement it are clear.
2.	The background is clearly explained and the related works are well discussed.

weaknesses:
1.	It seems that a lot baselines are missing. For example, in the Bottleneck Task, only some basic memory mechanisms from single-agent RL are compared while more advanced memory mechanisms such as relational memory [1] and AMRL [2] from the single-agent RL domain are not compared.
2.	At the same time, although some works about MARL memory such as RATE and ATM are discussed in Section 2.2, they are not compared in the experiments.
3.	The ablation study to validate each component of the proposed SRMT is not given.
4.	There are some typos. In Line 36, “MAPF” is not defined.

References

[1] Adam Santoro, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski, Théophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy Lillicrap. Relational Recurrent Neural Networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.

[2] Jacob Beck, Kamil Ciosek, Sam Devlin, Sebastian Tschiatschek, Cheng Zhang, and Katja Hofmann. Amrl: Aggregated memory for reinforcement learning. In International Conference on Learning Representations, 2020.

questions:
1.	Could the authors give the number of network parameters of each method? As SRMT uses transformers and ResNet, it may obtain advantages by more network parameters.
2.	Could SRMT scale well with the number of agents? If the number of agents increases, will the training time become much longer?
3.	Why does MAMBA with discrete communication protocol outperform SRMT in some scenarios? Does it mean that the global shared memory is not always the best choice? If yes, how could we choose the right method for the multiagent path-finding problem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691351921

thread_type:
official_review

<thread_object>
creator: reviewer_fa5a

<content>
summary:
This paper introduces the Shared Recurrent Memory Transformer (SRMT), a novel model in multi-agent reinforcement learning designed for multi-agent lifelong pathfinding tasks. SRMT extends memory transformers to decentralized multi-agent environments by pooling individual agent memories into a shared memory space, allowing agents to indirectly share information and coordinate. The model is tested in various pathfinding tasks, including bottleneck navigation and complex environments from the POGEMA benchmark. SRMT demonstrates superior performance in coordination and generalization, particularly in high-density and partially observable environments.

strengths:
1. The SRMT model is an adaptation of memory transformers to multi-agent settings, facilitating indirect communication among agents through a shared memory. This approach addresses a significant challenge in decentralized coordination by leveraging shared recurrent memory, which is unique compared to conventional communication strategies.
2. The paper provides a rigorous evaluation of SRMT on multiple benchmark tasks, including POGEMA and bottleneck navigation. The use of diverse reward settings (e.g., sparse, directional) further strengthens the experimental framework, revealing SRMT’s adaptability in various coordination scenarios.
3. The architecture and methods are clearly explained, supported by diagrams and flowcharts that help clarify SRMT’s working mechanism. The comparisons with baselines and the explanation of the multi-agent Markov decision process formulation are presented in a straightforward and understandable manner.
4. SRMT’s ability to handle decentralized pathfinding without explicit communication protocols has considerable implications for real-world applications, particularly in settings where communication might be unreliable or costly. Its effectiveness across different maps and scenarios demonstrates potential for scalability in complex, large-scale environments.

weaknesses:
1. While SRMT performs well on small to medium-sized environments, its scalability to very large maps or highly dense environments remains uncertain. The evaluation could be extended to more challenging settings, particularly with greater agent populations or larger obstacles, to fully assess SRMT’s scalability.
2. While SRMT is designed for decentralized systems, it would be beneficial to see comparisons with centralized approaches on key metrics to understand the trade-offs better, particularly in environments that demand high coordination.
3. While the paper claims that shared memory improves coordination, additional analysis on how shared memory influences individual agent behavior would provide a deeper understanding. An ablation study removing the shared memory aspect could further validate its impact on SRMT’s performance.
4. The model's performance varied across different reward structures, and while this is discussed, a more detailed exploration of how reward shaping influences learning would strengthen the analysis. This would help in tailoring SRMT to tasks where only sparse rewards are available.

Missing references (MARL with local information). I believe these are quite recent papers and work in a similar setting as mentioned in the related works section.

[1]: Hu, Y., Fu, J., & Wen, G. (2023). Graph soft actor–critic reinforcement learning for large-scale distributed multirobot coordination. *IEEE transactions on neural networks and learning systems*.

[2]: Nayak, S., Choi, K., Ding, W., Dolan, S., Gopalakrishnan, K., & Balakrishnan, H. (2023, July). Scalable multi-agent reinforcement learning through intelligent information aggregation. In *International Conference on Machine Learning* (pp. 25817-25833). PMLR.

questions:
1. How well does SRMT scale with an increased number of agents or more complex map structures? Additional experiments in larger environments could help evaluate its robustness in real-world applications.
2. Would SRMT benefit from combining shared memory with limited explicit communication for certain high-density environments?
3. How does shared memory impact the decision-making process for individual agents? Further analysis on memory usage patterns and shared memory dynamics could provide insights into SRMT’s internal coordination mechanisms.
4. Does SRMT allow for integration with hierarchical pathfinding methods, such as combining local and global pathfinding strategies?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694044183

thread_type:
official_review

<thread_object>
creator: reviewer_766h

<content>
summary:
This work considers the application of a shared memory mechanism to the MAPF setting.

strengths:
- The writing is generally clear and polished. 
- The approach is well-grounded in prior literature, and the algorithmic details are well-explained.  
- Figure 1 is a useful complement to the written algorithmic details, and makes it easy to understand the method at a glance. 
- Figure 10 analysis is nice.

weaknesses:
* It is hard to get a relative sense of the competitiveness of this approach. The baselines did not feel particularly well-motivated, and MARL communication works, which I'd argue share a similar goal, were not used as baselines (e.g. \[1\])
* More generally, I am left not knowing exactly what I should take away from the results—Figure 5 seems to show that SRMT and variants achieve modest results compared to baselines (and the baselines used are not motivated or described in sufficient detail).
* \[2\] I consider this a necessary work to acknowledge, given it is one of the first works discussing the use of attention in MARL
* Nitpicks: 
	* I cannot interpret the error bars in Figure 4—it is too muddled.
	* Despite the writing overall being clear, the language could be tightened somewhat; e.g. L043: "has to reach its goal" is quite colloquial; also contraction in L497. I recommend combing through the paper and essentially asking each word/phrase to justify itself—and to be as specific as possible, avoiding colloquialisms. 

\[1\] Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), *Advances in Neural Information Processing Systems, volume 29*. Curran Associates, Inc., 2016. URL https://proceedings.neurips.cc/paper_ files/paper/2016/file/c7635bfd99248a2cdef8249ef7bfbef4-Paper.pdf.

\[2\] Iqbal, S. &amp; Sha, F.. (2019). Actor-Attention-Critic for Multi-Agent Reinforcement Learning. <i>Proceedings of the 36th International Conference on Machine Learning</i>, in <i>Proceedings of Machine Learning Research</i> 97:2961-2970 Available from https://proceedings.mlr.press/v97/iqbal19a.html.

questions:
- Following up on a weakness above: Why was this approach not evaluated against any MARL baselines that implement communication channels between agents?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732566839989

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to thank the reviewers for their thoughtful feedback and for recognizing several strengths of our work. All reviewers found an idea and proposed method to be well-explained. Reviewers (766H, r4zr) specifically note that the background and related work are well-discussed. Reviewer fa5a highlights the importance of the challenge and uniqueness of the shared memory approach compared to other communication strategies, mentions that evaluation is rigorous and highlights the potential of SRMT for real-world scenarios in decentralized settings without explicit communication protocols. Reviewer 766H acknowledged that the provided analysis of shared memory is “nice”.

We have carefully considered the reviewers’ questions and comments and have made every effort to address them comprehensively. This involved conducting additional experiments and extending the paper to provide deeper insights. We are confident that these revisions have strengthened the paper and improved its overall quality. Below is a summary of our responses.

**On baselines**

We compare SRMT with MAPF methods that employ different strategies on POGEMA benchmark: centralized with search-based planner (RHCR), without communication (Follower, MATS-LP), cooperative MARL with communication (MAMBA, QPLEX). Follower, MATS-LP, and RHCR are very competitive methods as they are three top-performing from the POGEMA benchmark.
As suggested by reviewers we extended our evaluations with three MARL approaches that employ memory mechanisms (RATE [1], RRNN [2], ATM [3]). On bottleneck environments we found that SRMT overperforms these methods and included results to the revised version of the manuscript.

_Reviewer 766H suggested evaluating RIAL-DIAL, unfortunately this method cannot be directly applied as it relies on sequential decision making, but in the case of MAPF all agents perform actions simultaneously._

**On ablation study**

The bottleneck task results include an ablation study to isolate and demonstrate the role of the proposed shared memory mechanism. In particular, RMT agents (SRMT w\o shared memory) use their individual memory representations locally without sharing them. In the Attention core method (SRMT w\o shared memory and w\o individual memory), the memory is completely removed from the core part of the policy model to test the memoryless architecture. In the Empty core method, the core network is completely removed from the policy model with direct connection of spatial encoder to actor-critic action decoder. The results of these ablation methods are in Figure 3 and show that shared memory is a key component of SRMT, especially in the sparse rewarding scenario, where the task is harder for agents to learn.

------------------------------------
We thank the reviewers for their valuable feedback and the opportunity to update our manuscript. In particular, we have emphasized the results of the ablation study to improve clarity and highlight its significance, and we have incorporated evaluations and discussion of the suggested baselines to provide a more comprehensive comparison.



[1] Cherepanov et al. Recurrent action transformer with memory, 2024. Arxiv:2306.09459.

[2] Santoro et al. Relational Recurrent Neural Networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.

[3] Yang et al. Transformer-based working memory for multiagent reinforcement learning with action parsing. Advances in Neural Information Processing Systems, 35:34874–34886, 2022.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes the Shared Recurrent Memory Transformer (SRMT) for improved coordination in decentralized multi-agent pathfinding (MAPF). The core claim is that by pooling and globally broadcasting individual working memories, agents can implicitly exchange information and coordinate actions more effectively without explicit communication protocols. SRMT is evaluated on a bottleneck task and the POGEMA benchmark, where it outperforms various baselines, particularly in sparse reward settings and generalizes well.

The main strengths of the paper are clarity of the presentation, and a comprehensive evaluation including the ablations and memory analysis. The main remaining weaknesses are about novelty, polish and scalability.

Overall, the paper presents a novel approach with promising results. The authors have successfully addressed many of the initial concerns. The revised manuscript has improved the paper, but the original concerns may not be completely addressed.