# Multi Agent Path Finding using Evolutionary Game Theory

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 45 references that are in the map.
- First posted on arXiv 5 Dec 2022.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments](https://mlsanity.com/paper/2007.15724/) (2020)
- [Collective eXplainable AI: Explaining Cooperative Strategies and Agent Contribution in Multiagent Reinforcement Learning with Shapley Values](https://mlsanity.com/paper/2110.01307/) (2021)
- [Heterogeneous Multi-Agent Reinforcement Learning for Unknown Environment Mapping](https://mlsanity.com/paper/2010.02663/) (2020)
- [Stable and Efficient Shapley Value-Based Reward Reallocation for Multi-Agent Reinforcement Learning of Autonomous Vehicles](https://mlsanity.com/paper/2203.06333/) (2022)
- [Learning to Collaborate in Multi-Module Recommendation via Multi-Agent Reinforcement Learning without Communication](https://mlsanity.com/paper/2008.09369/) (2020)
- [Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks](https://mlsanity.com/paper/2110.08802/) (2021)
- [Multi-Objective Vehicle Rebalancing for Ridehailing System using a Reinforcement Learning Approach](https://mlsanity.com/paper/2007.06801/) (2020)

## Built on by (most cited first, 3 of 3)

- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks](https://mlsanity.com/paper/2309.10275/) (2023)
- [Survival of the Fittest: Evolutionary Adaptation of Policies for Environmental Shifts](https://mlsanity.com/paper/2410.19852/) (2024)

## Abstract (arXiv)

In this paper, we consider the problem of path finding for a set of homogeneous and autonomous agents navigating a previously unknown stochastic environment. In our problem setting, each agent attempts to maximize a given utility function while respecting safety properties. Our solution is based on ideas from evolutionary game theory, namely replicating policies that perform well and diminishing ones that do not. We do a comprehensive comparison with related multiagent planning methods, and show that our technique beats state of the art RL algorithms in minimizing path length by nearly 30% in large spaces. We show that our algorithm is computationally faster than deep RL methods by at least an order of magnitude. We also show that it scales better with an increase in the number of agents as compared to other methods, path planning methods in particular. Lastly, we empirically prove that the policies that we learn are evolutionarily stable and thus impervious to invasion by any other policy.