mlsanityData to 7 Oct 2026

Multi Agent Path Finding using Evolutionary Game Theory

arXiv 2212.02010 ↗First posted 5 Dec 2022cs.MA cs.AI cs.GTcited by 3

Not on the map. Why?

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.

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

Builds on

13 of 45 references.

References · 13

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  3. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 903
  4. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  5. 2018PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learningcited by 89
  6. 2020Lifelong Multi-Agent Path Finding in Large-Scale Warehousescited by 79
  7. 2020MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environmentscited by 26
  8. 2021Collective eXplainable AI: Explaining Cooperative Strategies and Agent Contribution in Multiagent Reinforcement Learning with Shapley Valuescited by 24
  9. 2020Heterogeneous Multi-Agent Reinforcement Learning for Unknown Environment Mappingcited by 12
  10. 2022Stable and Efficient Shapley Value-Based Reward Reallocation for Multi-Agent Reinforcement Learning of Autonomous Vehiclescited by 11
  11. 2020Learning to Collaborate in Multi-Module Recommendation via Multi-Agent Reinforcement Learning without Communicationcited by 8
  12. 2021Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networkscited by 6
1 more
  1. 2020Multi-Objective Vehicle Rebalancing for Ridehailing System using a Reinforcement Learning Approachcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 1.

3 papers.

  1. 2025Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfindingcited by 3
  2. 2023Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networkscited by 0
  3. 2024Survival of the Fittest: Evolutionary Adaptation of Policies for Environmental Shiftscited by 0