A multi-agent path planning algorithm based on game theory and reinforcement learning
Wenbo Xiong, Lei Guo, Tongyu JIAO · JOURNAL OF SHENZHEN UNIVERSITY SCIENCE AND ENGINEERING · 2024
This study addresses the issue of slow speed and low efficiency in path planning algorithms for multi-agents on a plane. We formulate the multi-agent path planning problem as a non-zero-sum stochastic game and employ the multi-agent reinforcement learning algorithm, win or learn fast - policy hill-climbing (WoLF-PHC), to obtain a Nash equilibrium strategy to make conflict free optimal path decisions for each agent. Additionally, we propose a fast adaptive WoLF-PHC (FA-WoLF-PHC) algorithm to improve the WoLF-PHC algorithm by constructing an objective function and using gradient descent method to adaptively update the learning rate. FA-WoLF-PHC is applied in two game scenarios: coin flipping and custom payoff matrix, and compared with policy hill-climbing (PHC) and WoLF-PHC algorithms. The experimental data show that the FA-WoLF-PHC algorithm improves the learning speed compared to the WoLF-PHC and effectively reduces oscillations in the learning process of WoLF-PHC and PHC algorithms. In the multi-agent path planning problems, the FA-WoLF-PHC algorithm improves the learning speed by 16.01% compared to WoLF-PHC algorithm. When the environmental grid map is expanded to 6 × 6 and the number of agents is increased to 3, the average times required for the FA-WoLF-PHC, WoLF-PSP and PP-AP Sarsa (Physarum Polycephalum-Artificial Potential Sarsa) algorithms are 16.30, 20.59, and 17.72 seconds, respectively, to learn the final strategies over 10 experiments. The results show that the FA-WoLF-PHC algorithm can obtain Nash equilibrium strategies for each agent, and it effectively improves learning speed compared to the WoLF-PSP and PP-AP Sarsa algorithms. The FA-WoLF-PHC algorithm can quickly learn Nash strategies in common game scenarios and generate conflict-free optimal paths for each agent in multi-agent path planning problems, showing significant improvement in learning speed compared with other algorithms.