电子学报 ›› 2019, Vol. 47 ›› Issue (10): 2166-2176.DOI: 10.3969/j.issn.0372-2112.2019.10.019

• 学术论文 • 上一篇    下一篇

基于双层蚁群算法和动态环境的机器人路径规划方法

许凯波1,2, 鲁海燕1, 黄洋1, 胡士娟1   

  1. 1. 江南大学理学院, 江苏无锡 214122;
    2. 无锡市玉祁高级中学, 江苏无锡 214183
  • 收稿日期:2017-12-20 修回日期:2019-02-13 出版日期:2019-10-25 发布日期:2019-10-25
  • 作者简介:许凯波 男.1992年6月出生,山西晋城人.硕士,2018年毕业于江南大学理学院应用数学专业,主要研究方向为最优化与控制.E-mail:2587073839@qq.com;鲁海燕 女.1970年出生,山东淄博人.副教授,硕士生导师,分别于1996年和2007年在浙江大学获得硕士学位和博士学位,现为江南大学理学院信息与计算科学系党支部书记,主要从事组合优化;网络优化;计算智能和机器学习及其在组合优化、计算流体力学、生物信息学中的应用等方面的研究.E-mail:luhaiyan@jiangnan.edu.cn
  • 基金资助:
    国家自然科学基金(No.61772013,No.61402201);中央高校基本科研业务费专项资金(No.114205020513526)

Robot Path Planning Based on Double-Layer Ant Colony Optimization Algorithm and Dynamic Environment

XU Kai-bo1,2, LU Hai-yan1, HUANG Yang1, HU Shi-juan1   

  1. 1. School of Science, Jiangnan University, Wuxi, Jiangsu 214122, China;
    2. Wuxi Yuqi Senior High School, Wuxi, Jiangsu 214183, China
  • Received:2017-12-20 Revised:2019-02-13 Online:2019-10-25 Published:2019-10-25

摘要: 针对动态环境未知时变的特点,提出一种机器人路径规划新方法.在该方法中,首先对栅格法建立的环境模型进行凸化处理,以避免机器人沿规划路径移动时陷入U型陷阱,从而加快路径规划的速度;其次,提出双层蚁群算法(DACO),在每次迭代中先用外层蚁群算法寻找一条路径,然后以该路径为基础构造一个小环境,接着在该环境下用内层蚁群算法重新寻优,若寻得的路径质量更高,则更新路径并执行本文给出的一种新型信息素二次更新策略;最后,针对环境中不同动态障碍物的体积和速度,提出三种避障策略.动态环境下,机器人先由DACO算法规划一条静态环境下从起点到终点的全局最优路径,然后从当前起点开始,通过自带传感器获取动态环境信息,并根据需要执行等待、正碰或追尾避障策略,到达新的起点.仿真实验表明,该方法可以在动态环境下实时地为移动机器人规划出一条安全且最短的路径,是求解移动机器人路径规划问题的一种切实有效的方法.

关键词: 动态障碍物, 移动机器人, 路径规划, 蚁群算法, 栅格法

Abstract: For the characteristics of being unknown and time-varying of dynamic environment,a new method for mobile robot path planning is proposed in this paper.Firstly,in this method the environment model established by the grid method is convexized in order for the robot to avoid falling into U-shaped traps when moving along the planned path and thus to speed up the path planning.Secondly,a double-layer ant colony optimization(DACO)algorithm is proposed.In each iteration of DACO algorithm,a path is found firstly by the outer ACO algorithm,then on basis of which a small environment is constructed,and then the robot re-plans path by the inner ACO algorithm in the small environment; if the newly obtained path is better,then the global optimal path is updated and a new pheromone secondary update strategy proposed in this paper is executed.At last,three kinds of obstacle avoidance strategies are put forward according to the volume and speed of different dynamic obstacles in the environment.In the dynamic environment,the robot plans a global optimal path from the starting point to the destination with respect to the static environment via the DACO algorithm,then from the current starting point,the robot acquires the dynamic environment's information by its embedded sensor and implements waiting-for-obstacle avoidance strategy,collision avoidance strategy or rear-end collision avoidance strategy when necessary,and then the robot moves to next position as a new starting point.Simulation results show that the proposed can plan a safe and shortest path for mobile robot in real time under dynamic environment and is a practical and effective method for mobile robot path planning.

Key words: dynamic obstacles, mobile robot, path planning, ant colony optimization, grid method

中图分类号: