POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding

W1: We believe that achieving strong performance in decentralized settings, or even matching the scores of centralized methods, represents a significant breakthrough. The benchmark highlights this challenge and provides a platform to address it. Additionally, many MARL approaches underperform compared to learnable MAPF methods, even when using preprocessing tecniques from learnble MAPF (e.g. from Follower). This indicates that POGEMA presents a compelling challenge for large-scale MARL training setups, especially for the CTDE (centralized training decentralized execution) paradigm.

We also want to emphasize several promising research directions in decision-making that can be explored using our benchmark:

1. Large-scale imitation learning: POGEMA provides a fast environment and efficient centralized baselines that can be used to generate high-quality data for training. This is particularly useful for foundation models, as the procedural generation of maps allows for an unlimited supply of expert data.
2. Communication learning: POGEMA’s large maps inherently require agents to rely on local communication, making it an ideal testbed for MARL approaches focusing on communication. While communication has been extensively studied in MARL, its application in large-scale settings remains underexplored, and POGEMA provides a platform for advancing this field.
3. Memory-efficient methods: Most existing approaches (except for Switcher) rely on global guidance to reach goals in POGEMA, which poses significant challenges in multi-agent scenarios requiring memory. The sharp drop in performance compared to methods, which uses target guidance, highlights the need for memory-efficient strategies, making this an important area for further exploration.
4. Heterogeneous policies and opponent / ally modelling Currently, no centralized approaches can effectively handle scenarios with multiple policies. Learnable methods have the potential to close this gap, enabling agents to coordinate effectively in heterogeneous settings. This also opens an exciting avenue for studying how different algorithms can be trained concurrently in the same environment, fostering advancements in collaborative and adversarial multi-agent interactions.

W2: The primary challenge in any multi-agent navigation problem is coordinating the move/wait actions of agents to balance safety (avoiding collisions) with efficiency (minimizing the time to reach goals). While it is true that practical scenarios often include additional complexities, such as uncertainties in observations or execution, even under the simplified assumptions of perfect sensing and execution, the problem remains extremely difficult—especially when dealing with large groups of agents and complex map topologies.

Studying such “idealized” problems allows researchers to focus on the core challenges of coordination and cooperation without the confounding effects of noise or uncertainty. Insights gained from solving these problems can then be extended to more realistic scenarios, thereby advancing the field.

W3: Even in idealized, fully observable, discretized, and fully synchronized setups, obtaining an optimal solution to multi-agent pathfinding is an NP-hard problem. Much of the research in this field focuses on striking the right balance between the solver’s speed and the quality of the solution—a task that remains far from simple. This trade-off is crucial for practical applications and continues to drive progress in the field.

One promising approach to achieving this balance lies in decentralized, learnable methods, which POGEMA is specifically designed to support. By focusing on tasks with minimalistic representations, researchers can isolate and address fundamental challenges, enabling progress that can later extend to more complex and realistic scenarios. Thus, we believe that focusing on tasks with minimalistic representation one can actually push the frontiers forward.

Overall, we believe that POGEMA does not sweep under the carpet important real-world limitations (despite not considering them) but rather allows researchers and practitioners to focus their attention to the core task of any multi-agent navigation problem, i.e. to safe coordination of actions between the agents. In the same way, the other MARL navigation environments/benchmarks inherit the similar limitations, actually. For example, in the MAgent environment the actions are also discrete. In Flatland the agents are also confined to graphs, representing the railroad networks. In Nocturne the agents are confined to roads/lanes and the time horizon is very limited (9s). We believe that introducing such limitations is a reasonable trade-off between the real-world implications and the ability for the researchers to concentrate on the core problem of multi-agent navigation, i.e. coordination and cooperation between the agents.

[Hönig et al., 2016] Hönig, W., Kumar, T.K., Cohen, L., Ma, H., Xu, H., Ayanian, N. and Koenig, S. Multi-agent path finding with kinematic constraints. ICAPS 2016. p. 477-485.

[Ma et al., 2019] Ma, H., Hönig, W., Kumar, T.S., Ayanian, N. and Koenig, S. Lifelong path planning with kinematic constraints for multi-agent pickup and delivery. AAAI 2019. p. 7651-7658.

[Okumura et. al, 2022] Okumura, K., Machida, M., Défago, X. and Tamura, Y. Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence, 310, 2022. P.103752.

W2: Thank you for your feedback. We have revised and rewritten the introduction to make it more concise.

Q1: Thank you for pointing that out. We have corrected this typo in the revised version of the paper.

Q2: Thank you for catching this error. It should indeed be “NP-Hard.”

Q3: First, we agree that our definitions may lack rigor, but they capture the essence of the categorization. Your remarks are valid and insightful:

• Regarding “the rewards of agents might not sum up to a fixed value but could have a relationship akin to being inversely proportional” — this aligns with our definition, as both describe the same principle: a joint strategy that benefits one player necessarily disadvantages others. We will refine our definition to clarify this point.
• Regarding “in cooperative behaviors, agents do not necessarily share rewards, but they are working towards the same task” — working towards the same task implies a shared goal, which can be mathematically expressed as a “shared reward function.” We will include a remark to make this connection clearer.

We sincerely thank the reviewer for their time and expertise.

W1: First, we want to emphasize that our primary contribution is POGEMA as a benchmark, not just as an environment. There are two main problems in MARL: reproducible evaluation and the generalization problem. The POGEMA benchmark addresses these by providing an evaluation protocol and tools, metrics, along with well-prepared baselines, including centralized MAPF solvers. Additionally, it includes procedural generation tools, which require agents to learn generalized policies that are then tested on unseen scenarios in a hold-out set during training.

We thank the reviewer for pointing out papers [1][2], and we have included a comparison with them in Table 1. Let’s now review these environments.

In comparison to Gigastep, we highlight several key distinctions:

• POGEMA supports procedural generation of scenarios, which is essential for testing generalization. In contrast, Gigastep primarily uses empty maps or simple, hand-designed obstacles that do not challenge the diversity of algorithmic capabilities.
• A vital characteristic of a benchmark is a well-defined evaluation protocol for assessing and comparing solutions. Gigastep lacks this, as it only compares PPO with hand-designed bots.
• While GPU acceleration is a key feature of Gigastep, we argue it may be unnecessary. Once environments can process a sufficient number of steps per second across parallel environments, the bottleneck often shifts from simulation to neural network computation. In contrast, POGEMA’s approach—avoiding reliance on GPUs or TPUs for simulation—keeps these resources available for training. Additionally, we extended the Speed Performance Evaluation section in the Appendix, where we compared POGEMA to JaXMARL. POGEMA also outperforms Gigastep in reported throughput, generating a maximum of 3.1M observations per second on CPU.
• Gigastep’s GitHub repository has not been actively maintained since 2022, with several unresolved issues, raising concerns about its long-term reproducibility. In contrast, POGEMA is actively maintained. We provided version updates history to anonymized code to support this claim.

Magent is a well-recognized environment within the community, though less widely used than SMAC. However, it lacks procedural generation capabilities, essential for testing agent generalization. The benchmark consists of six static scenarios, none of which scale to more than 1,000 agents, with the largest agent population observed in the “Gather” scenario, supporting up to 495 agents.

Both Gigastep and Magent require knowledge of JAX or C++ for modification, which can hinder their adaptability. In contrast, POGEMA is implemented in pure Python, making it more accessible and easier to modify.

Next, we wish to elaborate on the need to address real-world complications in a multi-agent navigation environment. We agree with the reviewer that real-world multi-agent problems impose numerous challenges (continuous workspace and time, non-syncronized time, communication and observation issues, perception limitations etc.). Still, the core challenge of any multi-agent navigation problem is the coordination of actions between the agents in a way that minimises the risk of collisions and optimises a given cost objective. This aspect is the crux of any multi-agent navigation scenario and that is why we opted to distil this problem and focus on it in POGEMA. It is known that even the discretized version of the considered multi-agent pathfinding (MAPF) problem is NP-Hard to solve optimally. On the other hand, numerous practically important applications mimic the discrete nature of MAPF and actively use MAPF solutions in real world. The most prominent example being the automated warehouses where, indeed, robots move synchronously utilizing cardinal moves. Moreover, it is described in numerous works, e.g. [Hönig et al., 2016], [Ma et al., 2019], [Okumura et. al, 2022] how solutions of the ‘discertized idealized’ MAPF can be applied in practice and transferred to the real robots.

Q1: First, partial observability is conceptually applicable to any learnable MAPF approach because an agent’s policy typically relies only on its local observation. While it is possible to provide the policy with the full state in some simple setups (due to limited size of network input), doing so is unnecessary and diminishes many of the advantages of the partially observable case. Partial observability promotes scalability, decentralization, and robustness, which are critical in dynamic and multi-agent environments.

Second, while it is true that maps are often known a priori in industrial settings like warehouses, this assumption limits adaptability. Traditional heuristic approaches used in these domains are tailored for static environments and may struggle with dynamic changes, such as temporary obstacles or blocked paths. In contrast, learnable decentralized algorithms can adapt to such changes. Exploring these types of approaches could broaden their applicability to more dynamic and uncertain settings beyond traditional use cases.

Third, regarding map availability, most learnable MAPF approaches assume the map is already known (e.g. Follower, DCC, SCRIMP etc).. However, there are algorithms, such as the “Switcher” approaches in the benchmark, that can construct or update the map during inference. If the map is assumed to be known beforehand, many approaches use guidance, such as providing the algorithm with partial information about local shortest paths to the goal, which significantly improves their performance. Even with access to this information, these approaches lack of global knowledge of other agents’ positions or their target locations. This limitation aligns with the decentralized, partially observable paradigm, fostering robustness and generalization to scenarios where global information is unavailable or unreliable.

Thank you for the question. Dense rewards can make the learning process easier for RL algorithms, especially when they face exploration challenges in environments with long planning horizons. For POGEMA, we chose to use a sparse reward of +1 at the end of the episode as the default. However, for benchmarking and training MARL algorithms, we used reward structures inspired by Follower to facilitate learning and improve performance.

Your question, while seemingly simple, touches on a deeper issue. Dense rewards can introduce bias, as agents may exploit the reward signal or solve unintended tasks without optimizing the main objective. This can be seen in many RL approaches for learnable MAPF, where reward shaping schemes are often introduced to guide the agent’s behavior.

When we move beyond centralized training to consider decentralized settings, the reward function becomes even more critical. In multi-agent scenarios, tasks can become adversarial—optimizing one agent’s objective may reduce rewards for others. Designing reward functions in these cases is particularly challenging. For centralized training, the issue shifts to scalability. As the agent population grows, so do the state spaces, and with many agents influencing the global reward, this greatly complicates training.

W6: Regarding the inclusion of all multi-agent benchmarks, the intention behind Table 1 is not to claim that the listed issues are the only challenges in MARL or multi-agent systems. Instead, the table highlights key problems addressed by the presented approach and contextualizes POGEMA within the broader landscape of MARL benchmarks. Many of these issues are indeed important and require further exploration.

On the topic of GPU parallelization, we acknowledge that it was not explicitly addressed in the table. However, we have included a proxy column reflecting how quickly environments can generate samples, which provides an indirect measure of computational efficiency. While GPU parallelization is an important factor, CPU parallelization is equally relevant for many applications, and our focus on this aspect reflects the flexibility of POGEMA. We will clarify this in the manuscript to ensure a balanced representation of parallelization methods.

Finally, regarding the detailed explanations in the related work section, we aimed to provide a comprehensive discussion of the components and context for POGEMA. However, we agree that some parts could be condensed for clarity and brevity. We will revise the related work section to reduce redundancy and streamline the descriptions, ensuring the focus remains on the most relevant comparisons and contributions.

W7-Q3: Thank you for pointing this out. Here are several future research directions that we would like to emphasize and include in the paper:

1. Large scale MARL: Many MARL approaches underperform compared to learnable MAPF methods, even when using preprocessing techniques from second (e.g., from Follower). This suggests that POGEMA presents a compelling challenge for large-scale MARL training setups, particularly for the CTDE (Centralized Training, Decentralized Execution) paradigm. Popular methods like QMIX and MAMBA struggle to scale to large numbers of agents in such setups. In our experiments, we were unable to train these methods on the same maps and with the same number of agents as in Follower (which uses independent PPO), where the authors trained agents in environments with up to 256 agents.
2. Large-scale imitation learning: POGEMA provides a fast environment and efficient centralized baselines that can be used to generate high-quality data for training. This is particularly useful for foundation models, as the procedural generation of maps allows for an unlimited supply of expert data.
3. Communication learning: POGEMA’s large maps inherently require agents to rely on local communication, making it an ideal testbed for MARL approaches focusing on communication. While communication has been extensively studied in MARL, its application in large-scale settings remains underexplored, and POGEMA provides a platform for advancing this field.
4. Memory-efficient methods: Most existing approaches (except for Switcher) rely on global guidance to reach goals in POGEMA, which poses significant challenges in multi-agent scenarios requiring memory. The sharp drop in performance compared to methods, which uses target guidance, highlights the need for memory-efficient strategies, making this an important area for further exploration.
5. Heterogeneous policies (opponent / ally modelling) Currently, no centralized approaches can effectively handle scenarios with multiple policies. Learnable methods have the potential to close this gap, enabling agents to coordinate effectively in heterogeneous settings. This also opens an exciting avenue for studying how different algorithms can be trained concurrently in the same environment, fostering advancements in collaborative and adversarial multi-agent interactions.

W1: From the MAPF perspective POGEMA is indeed centered around what is called Classical MAPF [Stern et al., 2019] . This is a challenging problem which is known to be NP-Hard to solve optimally. Therefore, a large volume of research is focused on finding the best trade-off between the speed of obtaining a solution and the quality of this solution. Moreover, in one of the most important practical applications that drives the field, i.e. in automated warehouses, the assumption of ‘discretized grid with simplified setting’ holds. That justifies the value of concentrating on this setup. The core challenge of any multi-agent navigation problem, i.e. the need to coordinate the movements of the agents, is existent in the considered setup. Moreover, such an ‘idealized’ setup helps the researchers to better concentrate on the coordination/cooperation challenge. Still, we agree with the reviewer that some phrasings in the abstract/title/introduction may be altered.

[Stern et al., 2019] Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., Kumar, T.K. and Barták, R.. Multi-agent pathfinding: Definitions, variants, and benchmarks. In SoCS 2019.

W2: We appreciate the reviewer’s feedback and agree that providing training code for DCC and SCRIMP would enhance reproducibility. In our work, we used pre-trained weights provided by the authors of these approaches, as their training relied on custom frameworks and environments not compatible with POGEMA. For instance, SCRIMP approach has a collision-resolution technique integrated with its environment, which is not supported by POGEMA, and we would like to avoid implementing such ad-hoc techniques on the level of the environment that violate decentralized decision-making. While we acknowledge the value of comparing training performance in a unified setting, we opted for a different evaluation approach: allowing training on diverse scenarios and evaluating on a hold-out dataset.

W3: We thank the reviewer for highlighting this concern. While we did not include experiments scaling to >1000 agents in the initial submission—primarily because many communication-based approaches cannot handle such numbers within feasible time—it is straightforward to test scalability with faster algorithms, such as Follower.

To address this issue, we will expand the POGEMA Speed Performance Evaluation section to include steps-per-second comparisons for setups with more than 1000 agents. This will illustrate how processing time changes as the number of agents increases. We will update the manuscript accordingly during the discussion period.

As an intermediate response, we have provided an animation here showing Follower running 1024 agents in a single environment of size 128×128.

W4: In our code, we used the latest version at the time or writing, i.e. LaCAM-v3. Thank you for bringing this to our attention; we have updated the references to include this citation as well. Additionally, we have revised the appendix, extending the Evaluation Setup Details section to include links to the GitHub repositories of the code used.

W5: Indeed, lacking JAX support and GPU-based parallelization tools is a limitation. However, while many new environments are specifically designed for GPU acceleration, we argue that this may not always be necessary. Once an environment can process a sufficient number of steps per second across parallel simulations, the bottleneck often shifts from simulation to neural network computation. By avoiding reliance on GPUs or TPUs for simulation, POGEMA keeps these resources fully available for training. Additionally, we extended the Speed Performance Evaluation section in the Appendix, where we compared POGEMA to JaXMARL. Notably, POGEMA outperforms Gigastep (another environment, suggested by reviewer iVSi) in reported throughput, achieving a maximum of 3.1 million observations per second on CPU.

Regarding the Robot Warehouse environment (referred to as RWARE in Table 1) suggested by the reviewer, it is already included in our comparison. After analyzing its implementation in JAX, we identified challenges in adapting it to a rich (L)MAPF setting. The primary issue lies in procedural generation. The current implementation assumes a warehouse pattern with a single connected component, allowing targets to be placed at any available slot. However, in (L)MAPF, there may be multiple independent components, and it is critical to ensure that each target and agent belong to the same connected component. This typically requires BFS-based preprocessing, which is difficult to parallelize efficiently on GPUs. Furthermore, almost all learnable MAPF approaches use target guidance, which is often constructed using the A* algorithm or precomputed cost-to-go values. These computations are also difficult to parallelize efficiently on GPUs.

Following discussions with Reviewers Jpm1 and iVSi, we have significantly revised the introduction to make it more focused and streamlined (please see the revised pdf). Additionally, we have made slight adjustments to the wording of the title and abstract. We agree with the reviewers’ observation that our work focuses on a specific variant of the multi-agent navigation problem, namely the one that employs discretized atomic actions and known as multi-agent pathfinding in the literature. However, we emphasize that the core challenge of any multi-agent navigation problem, the need to coordinate actions to avoid conflicts, remains central to the formulation we study. We are pleased to note that the reviewers do not appear to dispute this argument.

Finally, we confirm that all updates we committed to during the discussion period have been implemented.