# Cooperative Reward Shaping for Multi-Agent Pathfinding

arXiv: https://arxiv.org/abs/2407.10403 · HTML: https://mlsanity.com/paper/2407.10403/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 15 Jul 2024.

## Builds on (most cited first, 17 of 17)

- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Multiagent Cooperation and Competition with Deep Reinforcement Learning](https://mlsanity.com/paper/1511.08779/) (2015)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [Prosocial learning agents solve generalized Stag Hunts better than selfish ones](https://mlsanity.com/paper/1709.02865/) (2017)
- [Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00285/) (2021)
- [Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning](https://mlsanity.com/paper/2005.05420/) (2020)
- [Learning to Simulate Self-Driven Particles System with Coordinated Policy Optimization](https://mlsanity.com/paper/2110.13827/) (2021)
- [Distributed Heuristic Multi-Agent Path Finding with Communication](https://mlsanity.com/paper/2106.11365/) (2021)
- [Learning Selective Communication for Multi-Agent Path Finding](https://mlsanity.com/paper/2109.05413/) (2021)
- [MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments](https://mlsanity.com/paper/2007.15724/) (2020)
- [A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1903.06372/) (2019)
- [Stable and Efficient Shapley Value-Based Reward Reallocation for Multi-Agent Reinforcement Learning of Autonomous Vehicles](https://mlsanity.com/paper/2203.06333/) (2022)
- [STAS: Spatial-Temporal Return Decomposition for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2304.07520/) (2023)
- [Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time](https://mlsanity.com/paper/2201.08976/) (2022)

## Abstract (arXiv)

The primary objective of Multi-Agent Pathfinding (MAPF) is to plan efficient and conflict-free paths for all agents. Traditional multi-agent path planning algorithms struggle to achieve efficient distributed path planning for multiple agents. In contrast, Multi-Agent Reinforcement Learning (MARL) has been demonstrated as an effective approach to achieve this objective. By modeling the MAPF problem as a MARL problem, agents can achieve efficient path planning and collision avoidance through distributed strategies under partial observation. However, MARL strategies often lack cooperation among agents due to the absence of global information, which subsequently leads to reduced MAPF efficiency. To address this challenge, this letter introduces a unique reward shaping technique based on Independent Q-Learning (IQL). The aim of this method is to evaluate the influence of one agent on its neighbors and integrate such an interaction into the reward function, leading to active cooperation among agents. This reward shaping method facilitates cooperation among agents while operating in a distributed manner. The proposed approach has been evaluated through experiments across various scenarios with different scales and agent counts. The results are compared with those from other state-of-the-art (SOTA) planners. The evidence suggests that the approach proposed in this letter parallels other planners in numerous aspects, and outperforms them in scenarios featuring a large number of agents.