Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (3): 681-687.DOI: 10.11772/j.issn.1001-9081.2018071601

Previous Articles     Next Articles

Multi-Agent path planning algorithm based on ant colony algorithm and game theory

ZHENG Yanbin1,2, WANG Linlin1, XI Pengxue1, FAN Wenxin1, HAN Mengyun1   

  1. 1. College of Computer and Information Engineering, Henan Normal University, Xinxiang Henan 453007, China;
    2. Henan Engineering Laboratory of Intellectual Business and Internet of Things Technologies(Henan Normal University), Xinxiang Henan 453007, China
  • Received:2018-08-02 Revised:2018-09-12 Online:2019-03-10 Published:2019-03-11
  • Contact: 王林林
  • Supported by:
    This work is partially supported by the Science and Technology Research Project of Henan Province (142300410349, 132102210538), the Soft Science Project of Henan Province (142400411001), the Youth Fund of Henan Normal University (2017QK20).

基于蚁群算法及博弈论的多Agent路径规划算法

郑延斌1,2, 王林林1, 席鹏雪1, 樊文鑫1, 韩梦云1   

  1. 1. 河南师范大学 计算机与信息工程学院, 河南 新乡 453007;
    2. 智慧商务与物联网技术河南省工程实验室(河南师范大学), 河南 新乡 453007
  • 作者简介:郑延斌(1964-),男,河南内乡人,教授,博士,CCF会员,主要研究方向:虚拟现实、多智能体系统、对策论;王林林(1993-),女,河南周口人,硕士研究生,主要研究方向:虚拟现实、多智能体系统;席鹏雪(1993-),女,河南新乡人,硕士研究生,主要研究方向:虚拟现实、多智能体系统;樊文鑫(1994-),男,河南郑州人,硕士研究生,主要研究方向:虚拟现实、多智能体系统;韩梦云(1993-),女,河南安阳人,硕士研究生,主要研究方向:虚拟现实、汉字识别。
  • 基金资助:
    河南省科技攻关项目(142300410349,132102210538);河南省软科学项目(142400411001);河南师范大学青年基金资助项目(2017QK20)。

Abstract: A two-stage path planning algorithm was proposed for multi-Agent path planning. Firstly, an improved ant colony algorithm was used to plan an optimal path for each Agent from the starting point to the target point without colliding with the static obstacles in the environment. The reverse learning method was introduced to an improved ant colony algorithm to initialize the ant positions and increase the global search ability of the algorithm. The adaptive inertia weighted factor in the particle swarm optimization algorithm was used to adjust the pheromone intensity Q value to make it adaptively change to avoid falling into local optimum. The pheromone volatilization factor ρ was adjusted to speed up the iteration of the algorithm. Then, if there were dynamic collisions between multiple Agents, the game theory was used to construct a dynamic obstacle avoidance model between them, and the virtual action method was used to solve the game and select multiple Nash equilibria, making each Agent quickly learn the optimal Nash equilibrium. The simulation results show that the improved ant colony algorithm has a significant improvement in search accuracy and search speed compared with the traditional ant colony algorithm. And compared with Mylvaganam's multi-Agent dynamic obstacle avoidance algorithm, the proposed algorithm reduces the total path length and improves the convergence speed.

Key words: multi-Agent, path planning, reverse learning, ant colony algorithm, game theory

摘要: 针对多Agent路径规划问题,提出了一个两阶段的路径规划算法。首先,利用改进的蚁群算法来为每个Agent规划出一条从起始点到目标点,不与环境中静态障碍物碰撞的最优路径。在蚁群算法的改进中引入反向学习方法来对蚂蚁位置进行初始化分布,提高了算法的全局搜索能力;利用粒子群算法中的自适应惯性权重因子来调节信息素强度Q值,使其自适应地变化,避免陷入局部最优;对信息素挥发因子ρ进行调节,提高算法的迭代速度。其次,若多Agent之间存在动态碰撞,利用博弈论构建多Agent之间的动态避障模型,并利用虚拟行动法来解决博弈的求解问题及多Nash均衡的选择问题,确保每个Agent能够快速学习到最优Nash均衡。仿真实验结果表明改进蚁群算法与传统蚁群算法相比在搜索精度与搜索速度上有明显的提高,与Mylvaganam的多Agent动态避障算法相比,所提算法减小了路径总长度并提高了收敛速度。

关键词: 多Agent, 路径规划, 反向学习, 蚁群算法, 博弈论

CLC Number: