Multi Agent Path Finding using Evolutionary Game Theory
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Agent Path FindingSimilar Papers 제목 키워드 기반
Multi-agent Path Finding for Timed Tasks using Evolutionary Games
Autonomous multi-agent systems such as hospital robots and package delivery drones often operate in highly uncertain environments and are expected to achieve complex temporal task objectives while ensuring safety. While …
Multi-Agent Path FindingReinforcement Learning (RL)Learning in Multiagent Systems: An Introduction from a Game-Theoretic Perspective
We introduce the topic of learning in multiagent systems. We first provide a quick introduction to the field of game theory, focusing on the equilibrium concepts of iterated dominance, and Nash equilibrium. We show some …
The path integral formula for the stochastic evolutionary game dynamics in the Moran process
The Moran process is one of an basic mathematical structure in the evolutionary game theory. In this work, we introduce the formulation of the path integral approach for evolutionary game theory based on the Moran proces…
Ranking Joint Policies in Dynamic Games using Evolutionary Dynamics
Game-theoretic solution concepts, such as the Nash equilibrium, have been key to finding stable joint actions in multi-player games. However, it has been shown that the dynamics of agents' interactions, even in simple tw…
DescriptiveA Fast Evolutionary adaptation for MCTS in Pommerman
Artificial Intelligence, when amalgamated with games makes the ideal structure for research and advancing the field. Multi-agent games have multiple controls for each agent which generates huge amounts of data while incr…