改进蚁群算法的移动机器人路径规划

doi:10.3778/j.issn.1002-8331.2108-0211

摘要/Abstract

摘要： 针对传统蚁群算法在路径规划中存在易陷入局部最优与收敛速度慢等问题，提出一种改进的蚁群算法。采用初始信息素差异化分布策略，增强目标点导向区的初始信息素浓度；基于回退策略与禁忌搜索结合分块优化，利用叉积运算进行局部折点优化；引入信息素自调节加强因子，改进信息素浓度更新公式；引入随机状态转移参数，增强全局搜索能力；将改进算法在多种地图环境下与传统蚁群算法、樽海鞘群算法进行比较，仿真结果证明了改进算法拥有较好的收敛性与稳定性。

关键词: 蚁群算法, 路径规划, 差异化分布策略, 叉积运算, 自调节加强因子, 随机状态转移参数

Abstract: An improved ant colony algorithm is proposed to address the problems of the traditional ant colony algorithm in path planning, such as the tendency to fall into local optimum and slow convergence speed. The initial pheromone concentration in the target point guidance area is enhanced by adopting the initial pheromone differential distribution strategy. The local fold optimization is carried out by using the fork product operation based on the backoff strategy and taboo search combined with chunking optimization. The pheromone self-adjustment enhancement factor is introduced to improve the pheromone concentration update formula. The random state transfer parameter is introduced to enhance the global search capability. The improved algorithm is compared with the traditional ant colony algorithm and the salp swarm algorithm in a variety of map environments. The simulation results prove that the improved algorithm has better convergence and stability in path planning.

Key words: ant colony algorithm, path planning, differential distribution strategy, fork product operation, self-adjustment enhancement factor, random state transfer parameter

唐旭晖, 辛绍杰. 改进蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2022, 58(5): 287-295.

TANG Xuhui, XIN Shaojie. Improved Ant Colony Algorithm for Mobile Robot Path Planning[J]. Computer Engineering and Applications, 2022, 58(5): 287-295.

参考文献

[1] JIANG J R，HUANG H W，LIAO J H，et al.Extending Dijkstra’s shortest path algorithm for software defined networking[C]//2014 16th Asia-Pacific Network Operations and Management Symposium（APNOMS），2014.
[2] JU C，LUO Q，YAN X.Path planning using an improved a-star algorithm[C]//2020 11th International Conference on Prognostics and System Health Management（PHM-2020 Jinan），2020.
[3] WANG Y，HUANG Y.Mobile robot path planning algorithm based on rapidly-exploring random tree[C]//International Conferences on Ubiquitous Computing & Communications；Data Science and Computational Intelligence；Smart Computing，Networking and Services，2009.
[4] ZHANG J H，YONG Z，YONG Z.Path planning of mobile robot based on hybrid multi-objective bare bones particle swarm optimization with differential evolution[J].IEEE Access，2018，6：44542-44555.
[5] ZHANG D，YOU X，LIU S，et al.Dynamic multi-role adaptive collaborative ant colony optimization for robot path planning[J].IEEE Access，2020，8：129958-129974.
[6] JARRAY R，BOUALLEGUE S.Paths planning of unmanned aerial vehicles based on grey wolf optimizer[C]//2020 4th International Conference on Advanced Systems and Emergent Technologies（IC_ASET），2020.
[7] 徐菱，付文浩，江文辉，等.基于16方向24邻域改进蚁群算法的移动机器人路径规划[J].控制与决策，2021，36（5）：1137-1146.
XU L，FU W H，JIANG W H，et al.Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm[J].Control and Decision，2021，36（5）：1137-1146.
[8] 封声飞，雷琦，吴文烈，等.自适应蚁群算法的移动机器人路径规划[J].计算机工程与应用，2019，55（17）：35-43.
FENG S F，LEI Q，WU W L，et al.Mobile robot path planning based on adaptive ant colony algorithm[J].Computer Engineering and Applications，2019，55（17）：35-43.
[9] 张强，陈兵奎，刘小雍，等.基于改进势场蚁群算法的移动机器人最优路径规划[J].农业机械学报，2019，50（5）：23-32.
ZHANG Q，CHEN B K，LIU X Y，et al.Ant colony optimization with improved potential field heuristic for robot path planning[J].Transactions of the Chinese Society for Agricultural Machinery，2019，50（5）：23-32.
[10] 汪贵庆，袁杰，沈庆宏.基于精英蚁群算法的交通最优路径研究[J].南京大学学报（自然科学），2019，55（5）：709-717.
WANG G Q，YUAN J，SHEN Q H.Research on traffic optimal path based on elitist ant system[J].Journal of Nanjing University（Natural Science），2019，55（5）：709-717.
[11] 张毅，权浩，文家富.基于独狼蚁群混合算法的移动机器人路径规划[J].华中科技大学学报（自然科学版），2020，48（1）：127-132.
ZHANG Y，QUAN H，WEN J F.Mobile robot path planning based on the wolf ant colony hybrid algorithm[J].Journal of Huazhong University of Science and Technology（Natural Science Edition），2020，48（1）：127-132.
[12] 江明，王飞，葛愿，等.基于改进蚁群算法的移动机器人路径规划研究[J].仪器仪表学报，2019，40（2）：113-121.
JIANG M，WANG F，GE Y，et al.Research on path planning of mobile robot based on improved ant colony algorithm[J].Chinese Journal of Scientific Instrument，2019，40（2）：113-121.
[13] 张成，凌有铸，陈孟元.改进蚁群算法求解移动机器人路径规划[J].电子测量与仪器学报，2016，30（11）：1758-1764.
ZHANG C，LING Y Z，CHEN M Y.Path planning of mobile robot based on an improved ant colony algorithm[J].Journal of Electronic Measurement and Instrumentation，2016，30（11）：1758-1764.
[14] TAO Y，GAO H，REN F，et al.A mobile service robot global path planning method based on ant colony optimization and fuzzy control[J].Applied Sciences，2021，11（8）：3605.
[15] 李志锟，黄宜庆，徐玉琼.改进变步长蚁群算法的移动机器人路径规划[J].电子测量与仪器学报，2020，34（8）：15-21.
LI Z K，HUANG Y Q，XU Y Q.Path planning of mobile robot based on improved variable step size ant colony algorithm[J].Journal of Electronic Measurement and Instrumentation，2020，34（8）：15-21.
[16] 梁凯，毛剑琳.基于改进蚁群算法的室内移动机器人路径规划[J].电子测量技术，2019，42（11）：65-69.
LIANG K，MAO J L.Path planning of indoor mobile robot based on improved ant colony algorithm[J].Electronic Measurement Technology，2019，42（11）：65-69.
[17] 游晓明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（3）：552-556.
YOU X M，LIU S，LV J Q.Ant colony algorithm based on dynamic search strategy and its application on path planning of robot[J].Control and Decision，2017，32（3）：552-556.
[18] WANG R，LI Y，FAN J，et al.A novel pure pursuit algorithm for autonomous vehicles based on salp swarm algorithm and velocity controller[J].IEEE Access，2020，8：166525-166540.