基于对角障碍检测和优化蚁群算法的路径规划

徐兴毅 付丽霞 张勇 毛剑琳 郭宁

引用本文:
Citation:

基于对角障碍检测和优化蚁群算法的路径规划

    作者简介: 徐兴毅(1995−),男,云南人,硕士生,研究方向为智能优化与控制. E-mail: 2550157276@qq.com;
    通讯作者: 付丽霞, 905771625@qq.com
  • 中图分类号: TP312

Path planning based on diagonal obstacle detection and optimized ant colony algorithm

    Corresponding author: FU Li-xia, 905771625@qq.com ;
  • CLC number: TP312

  • 摘要: 针对大部分算法在多对角障碍环境中求解最短路径时会穿过对角障碍形成实际不可行路径的问题,提出一种结合对角障碍检测的优化蚁群算法用于移动机器人路径规划. 首先采用对角障碍检测标记出条件障碍,然后使用三角选择法准确筛选出可通行和不可通行的条件障碍,最后提出自调整期望启发因子和信息素更新策略. 实验结果表明:该算法具有环境适应性强、收敛速度快和寻优能力强的特点,并能有效避免所规划路径穿过对角障碍.
  • 图 1  地图优化前后对比

    Figure 1.  Comparison before and after map optimization

    图 2  条件栅格的筛选

    Figure 2.  Selection of condition grid

    图 3  多对角障碍环境中不同算法结果对比

    Figure 3.  Comparison of algorithms under multi-diagonal obstacles

    图 4  无对角障碍环境中算法对比

    Figure 4.  Comparison of algorithms without diagonal barrier

    表 1  对角障碍环境下的实验结果对比

    Table 1.  Comparison of experimental results in multi-diagonal obstacle environment

    算法平均收敛迭代次数规划路径长度平均收敛时间/s算法平均总耗时/s
    传统蚁群 30 28.6274 2.965221 9.719562
    对角障碍检测 20 30.9706 1.959106 9.576410
    对角加条件障碍 17 28.2563 1.680547 9.660051
    本文算法 11 28.2563 1.054999 6.563211
    下载: 导出CSV

    表 2  无对角障碍环境中实验结果对比

    Table 2.  Comparison of experimental results in an environment without diagonal obstacles

    算法(栅格环境)收敛迭代
    次数(20×20)
    规划路径
    长度(20×20)
    收敛迭代
    次数(30×30)
    路径长度(30×30)
    文献[11]算法1928.043143.36
    本文算法1228.042543.36
    下载: 导出CSV
  • [1] Patle B K ,Ganesh B L , PandeyA, et al. A review: On path planning strategies for navigation of mobile robot[J]. Defence Technology, 2019, 15(4): 582-606. DOI:  10.1016/j.dt.2019.04.011.
    [2] 霍凤财, 迟金, 黄梓健, 等. 移动机器人路径规划算法综述[J]. 吉林大学学报: 信息科学版, 2018, 36(6): 639-647. Huo F C, Chi J, Huang Z J, et al. Review of path planning for mobile robots[J]. Journal of Jilin University: Information Science Edition, 2018, 36(6): 639-647.
    [3] 史恩秀, 陈敏敏, 李俊, 等. 基于蚁群算法的移动机器人全局路径规划方法研究[J]. 农业机械学报, 2014, 45(6): 53-57. DOI:  10.6041/j.issn.1000-1298.2014.06.009. Shi N X, Chen M M, Li J, et. al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6): 53-57.
    [4] 王晓燕, 杨乐, 张宇, 等. 基于改进势场蚁群算法的机器人路径规划[J]. 控制与决策, 2018, 33(10): 1 775-1 781. Wang X Y, Yang L, Zhang Y, et al. Robot path planning based on improved ant colony algorithm with potential field heuristic[J]. Control and Decision, 2018, 33(10): 1 775-1 781.
    [5] 王雷, 李明, 蔡劲草, 等. 改进遗传算法在移动机器人路径规划中的应用研究[J]. 机械科学与技术, 2017, 36(5): 711-716. Wang L, Li M, Cai J C, et al. Research on mobile robot path planning by using improved genetic algorithm[J]. Mechanical Science and Technology for Aerospace Engineering, 2017, 36(5): 711-716.
    [6] 贾会群, 魏仲慧, 何昕, 等. 基于改进粒子群算法的路径规划[J]. 农业机械学报, 2018, 49(12): 371-377. DOI:  10.6041/j.issn.1000-1298.2018.12.044. Jia H Q, Wei Z H, He X, et al. Path planning based on improved particle swarm optimization algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2018, 49(12): 371-377.
    [7] Bharadwaj H , Vinodh K E. Comparative study of neural networks in path planning for catering robots[J]. Procedia Computer Science, 2018, 133: 417-423. DOI:  10.1016/j.procs.2018.07.051.
    [8] Dorigo M, Gambardella L M . Ant colonies for the travelling salesman problem[J]. BioSystems, 1997, 43(2): 73-81. DOI:  10.1016/S0303-2647(97)01708-5.
    [9] 朱艳, 游晓明, 刘升. 基于启发式机制的改进蚁群算法[J]. 信息与控制, 2019, 48(3): 265-271. Zhu Y, You X M, Liu S. Improved ant colony algorithm based on Heuristic mechanism[J]. Information and Control, 2019, 48(3): 265-271.
    [10] 江明, 王飞, 葛愿, 等. 基于改进蚁群算法的移动机器人路径规划研究[J]. 仪器仪表学报, 2019, 40(2): 113-121. Wang 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.
    [11] 朱颢东, 孙振, 吴迪, 等. 基于改进蚁群算法的移动机器人路径规划[J]. 重庆邮电大学学报:自然科学版, 2016, 28(6): 849-855. Zhu H D, Sun Z, Wu D, et al. Path planning for mobile robot based on improved ant colony algorithm[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2016, 28(6): 849-855.
    [12] 刘新宇, 谭力铭, 杨春曦, 等. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857. DOI:  10.3778/j.issn.1673-9418.1811015. Liu X Y, Tan L M, Yang C X, et al. Self-adjustable dynamic path planning of unknown environment based on ant colony-clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(5): 846-857.
    [13] 刘梅. 基于栅格化视觉的机器人路径优化研究[J]. 计算机与数字工程, 2018, 46(8): 1 548-1 552. DOI:  10.3969/j.issn.1672-9722.2018.08.014. Liu M. Research on robot path optimization based on rasterized vision[J]. Computer & Digital Engineering, 2018, 46(8): 1 548-1 552.
    [14] 程向红, 祁艺. 基于栅格法的室内指示路径规划算法[J]. 中国惯性技术学报, 2018, 26(2): 236-240. Cheng X H, Qi Y. Indoor indicator path planning algorithm based on grid method[J]. Journal of Chinese Inertial Technology, 2018, 26(2): 236-240.
    [15] 朱庆保, 张玉兰. 基于栅格法的机器人路径规划蚁群算法[J]. 机器人, 2005(2): 132-136. DOI:  10.3321/j.issn:1002-0446.2005.02.008. Zhu Q B, Zhang Y L. An ant colony algorithm based on grid method for mobile robot path planning[J]. Robot, 2005(2): 132-136.
  • [1] 黄冰倩杜庆治龙华 . 面向WSN的移动锚节点路径规划算法. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20170249
    [2] 王康碧蒋作和晓萍周卫红 . 一种基于蚁群算法的电梯群节能调度算法. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.2013b5
    [3] 李祖欣张榆锋施心陵 . 基于论域自调整模糊规则切换的双模控制器. 云南大学学报(自然科学版),
    [4] 岳昆李维华苏茜刘惟一 . XML查询中的频繁路径选择. 云南大学学报(自然科学版),
    [5] 曾超李娜王维周曙白陈朝阳 . 群搜索算法与Powell法结合的医学图像配准. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20120464
    [6] 陈畅陈丽李佳李云德 . 玻色-爱因斯坦凝聚体中的三角涡旋格子. 云南大学学报(自然科学版),
    [7] 杜凡杜小浪罗柏青赫尚丽 . 濒危特有植物毛蕊三角车(Rinorea erianthera)在云南发现. 云南大学学报(自然科学版),
    [8] 石国姣王公正黄帅凤飞龙张保存 . 二维内质量结构三角形晶格声子晶体的带隙研究. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20180748
    [9] 杨子生 . 论土地生态规划设计. 云南大学学报(自然科学版),
    [10] . Excel Solver的线性规划模型. 云南大学学报(自然科学版),
    [11] 邹力鵾王丽珍何婧 . 基于图的空间例外检测算法研究. 云南大学学报(自然科学版),
    [12] 何树红董志伟李如兵 . 常利率影响下调整下限风险模型的破产概率. 云南大学学报(自然科学版),
    [13] 胡宗达吴兆录闫海忠周元清张志明 . 滇西南灯台树种植适宜区规划研究. 云南大学学报(自然科学版),
    [14] 周云松裴以建余江池宗琳 . 双足行走机器人步态轨迹规划. 云南大学学报(自然科学版),
    [15] 刘国志 . 基于信赖域技术的局部收缩的微粒群算法. 云南大学学报(自然科学版),
    [16] 赵柳颜光前吴俊罗华友孙亮舒若 . 基于ABUS冠状面图像的乳头位置自动检测算法. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20180318
    [17] 杨仁青柏正尧尹立国高皜张涛 . 基于分数傅里叶变换的数字图像复制-粘贴篡改检测算法. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20150058
    [18] 杨雨薇张亚萍 . 一种改进的SIFT图像检测与特征匹配算法. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20160731
    [19] 代志涛苏寒松刘高华张倩芳 . 基于改进非局部均值滤波算法的显著性区域检测*. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20170351
    [20] 独智序王晓峰 . 基于稳健关键点的图像Copy-Move篡改检测算法. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20170629
  • 加载中
图(4)表(2)
计量
  • 文章访问数:  542
  • HTML全文浏览量:  472
  • PDF下载量:  6
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-21
  • 录用日期:  2020-02-19
  • 网络出版日期:  2020-04-23

基于对角障碍检测和优化蚁群算法的路径规划

    作者简介:徐兴毅(1995−),男,云南人,硕士生,研究方向为智能优化与控制. E-mail: 2550157276@qq.com
    通讯作者: 付丽霞, 905771625@qq.com
  • 昆明理工大学 信息工程与自动化学院,云南 昆明 650500

摘要: 针对大部分算法在多对角障碍环境中求解最短路径时会穿过对角障碍形成实际不可行路径的问题,提出一种结合对角障碍检测的优化蚁群算法用于移动机器人路径规划. 首先采用对角障碍检测标记出条件障碍,然后使用三角选择法准确筛选出可通行和不可通行的条件障碍,最后提出自调整期望启发因子和信息素更新策略. 实验结果表明:该算法具有环境适应性强、收敛速度快和寻优能力强的特点,并能有效避免所规划路径穿过对角障碍.

English Abstract

  • 在移动机器人的研究领域当中,路径规划[1]一直是人们研究的热点问题,即移动机器人根据已知的环境信息或者自身携带的传感器感知外界环境,在复杂的环境中寻找一条无碰撞的路线,并完成指定任务. 随着国内外学者的深入研究,机器人路径规划不仅仅局限于准确找到一条无碰撞的路线,同时还要求根据多个综合指标来选出最优路线,比如充分考虑到能耗最低、路线最短和收敛速度快等问题[2]. 因此,大量的智能算法得到了很好的运用,如:蚁群算法[3-4]、遗传算法[5]、粒子群算法[6]和神经网络[7]等已运用于机器人的路径规划当中.

    蚁群算法最初是由意大利的学者Dorigo[8]等提出的一种模拟蚂蚁觅食行为,解决旅行商问题的算法. 由于其具有并发性、自组织性、强鲁棒性等特点,在路径规划中具有很大的优势,从而被广泛地用于机器人路径规划,但蚁群算法存在搜索效率较低、容易陷入局部最优解等缺点,一些学者针对这些问题进行了改进. 文献[9]引入了一种启发式机制的思想,在蚁群算法的基础上,通过候选节点到目标点的距离动态调整启发函数,提高收敛速度;文献[10]通过自适应调节信息素挥发因子和优化避障的策略,有效地解决了传统蚁群算法容易陷入局部最优解及收敛速度较慢等问题;文献[11]改进了节点间的状态转移规则,提出自适应调整启发函数,使不同复杂环境下的路径规划都具有良好的寻优能力;文献[12]通过生成虚拟障碍物,避免规划的路径穿过对角障碍,同时加入聚类算法,自适应地调整搜索半径,提升了蚁群算法的环境适应能力.

    在上述对蚁群算法改进的研究中,除文献[12]外,都没有考虑到实际环境中存在对角障碍的问题,导致这些改进蚁群算法在出现对角障碍的环境中规划出的路线会穿过对角障碍,使规划出的路线实际不可行. 文献[12]虽然采用生成虚拟障碍的方法避免了穿过对角障碍,但其中某些实际可通过的区域被作为虚拟障碍而不可通行,无形中增加了障碍物区域,使得规划出的路径并不是最短. 为此,本文提出了如下的改进:①基于文献[12]对角障碍检测的基础上,将地图中对角障碍附近的自由栅格标记为条件障碍,使得栅格地图得到进一步的简化,减少算法的计算时间;②采用三角选择法筛选出可穿越和不可穿越的条件障碍,提高地图的准确性,既保证规划的路径不穿过对角障碍物,又能缩短路径长度;③对蚁群算法中的期望启发因子β和信息素更新采用参数自调整策略,克服蚁群算法自身缺陷,获得最短路径,并提升算法的收敛速度.

    • 栅格法是目前路径规划中最常用的仿真环境建模方法[13],它能够将实际场景按照一定比例量化成若干个面积相等的栅格. 其中,不规则的障碍物通过腐蚀或膨胀处理,按照其在整个实际场景中的大小和位置,等比例划分为多个栅格,并标记为障碍栅格. 其余无障碍的地方所划分的栅格标记为自由栅格. 可用一个M×N的数组矩阵来表示栅格地图中障碍物的分布情况[14],如式(1)所示:

      $ G\left( {M,N} \right) = \left\{ {\begin{array}{*{20}{c}} 1\!\!\!\!\!\!&\!{,{\text{障碍栅格;}}}\\ 0\!\!\!\!\!\!&\!{,{\text{自由栅格,}}} \end{array}} \right. $

      式中,$ G\left( {M,N} \right) = 1$ 时表示栅格地图上MN列存在障碍物,不可通行;$ G\left( {M,N} \right) = 0$ 时表示栅格地图上MN列没有障碍物,可自由通行.

      为了方便在计算中能够迅速找到对应的栅格,对每一个栅格进行编号,建立一个直角坐标系,以x为横轴,y为纵轴,每个栅格对应的编号为i,每个栅格的中心点坐标为($ {x_i},{y_i}$),栅格编号与中心点坐标的对应关系为:

      $ \left\{ {\begin{array}{*{20}{l}} {{x_i} = a\left( {{\rm{mod}}\left( {i,M_{\max}} \right) - 0.5} \right),}\\ {{y_i} = a\left( {M_{\max} + 0.5 - {\rm{ceil}}\left( {\dfrac{i}{{M_{\max}}}} \right)} \right),} \end{array}} \right. $

      式中,a表示每个栅格的边长,Mmax表示栅格图中横纵轴栅格数的最大值,mod是求余符号,ceil是舍余求整符号.

    • 将实际环境转化为栅格地图,通常会出现大量的对角障碍,所谓对角障碍就是如图1(a)所示形成对角的障碍栅格B1B2,为机器人的安全考虑,应避免机器人穿越B1B2相交的对角点,在本文中叙述为避免机器人穿过对角障碍B1B2. 由此,本文针对栅格地图中出现多个对角障碍的问题提出了基于对角障碍检测的地图优化,目的是找到地图中的对角障碍,并将其附近的自由栅格标记为条件栅格,从而避免机器人穿越对角障碍,对角障碍检测的实现步骤如下,图1所示为栅格地图优化前后的对比.

      图  1  地图优化前后对比

      Figure 1.  Comparison before and after map optimization

      步骤 1 通过邻接矩阵寻找障碍栅格,并判断栅格编号ij之间的关系,找出对角障碍. 邻接矩阵表征每个栅格与其8个领域栅格的关系,通过创建一个i×j的二维方阵Dij为栅格的编号,$ D\left( {i,j} \right)$ 代表栅格i与栅格j之间的关系,其满足如下的关系:

      $ D\left({i,j} \right) = \left\{ {\begin{array}{*{20}{l}} 1\!\!\!&\!\!\!\!{,{\text{栅格}}{{i}}{\text{、}}\!\!\!\!{{j}}{\text{为障碍栅格且相邻}}};\\ {0}\!\!\!&\!\!\!\!{,{\text{其它}}}. \end{array}} \right. $

      式中,$ D\left( {i,j} \right) = 1$ 表示栅格ij为相邻的障碍栅格.

      根据对角障碍的特征,搜索矩阵D中值为1的元素所对应的ij的数值,记编号i的障碍栅格编号为B1,编号j的障碍栅格编号为B2,则满足式(4)的B1B2互为对角障碍.

      $ {B_2} - {B_1} = M \pm 1,\;\;\;\;\;\; {{B_1} < {B_2}}. $

      式中,M为栅格图中横向栅格最大值.

      步骤 2 在对角障碍附近标记条件障碍. 当判断栅格B1B2互为对角障碍后,将满足式(5)的自由栅格Cg1Cg2标记为条件障碍(也称为条件栅格).

      $ \left\{ {\begin{array}{*{20}{c}} {C{{\rm{g}}_1} = {B_1} + M},C{{\rm{g}}_1}{\text{为自由栅格}};\\ {C{{\rm{g}}_2} = {B_2} - M},C{\rm{g}}_2{\text{为自由栅格}}. \end{array}} \right. $

    • 通过对角障碍检测标记出条件障碍,文献[12]中将标记出的条件栅格全部虚拟为障碍栅格,虽然避免了规划出的路径穿越对角障碍,但是会使得部分实际可通行的条件栅格变为障碍,从而无形中增加了所规划出的路径长度. 例如:图2中当机器人从节点S1行进至节点S3时,如果条件栅格Cg1可穿越,则机器人行进的最短路径为S1Cg1S3,但用文献[12]的方法得到机器人行进的路径将是S1S4S3,显然不是最短路径. 为解决这一问题,本文对条件障碍采用三角选择法进行筛选,准确筛选出可通行和不可通行的条件栅格. 具体步骤如下:

      图  2  条件栅格的筛选

      Figure 2.  Selection of condition grid

      步骤 1 计算当前机器人所处位置到八邻域节点的距离,并用邻接矩阵G记录.

      创建一个M×M的邻接矩阵 $ {{G}}\left( {{S_1},{S_2}} \right)$,设机器人所处节点S1的坐标为 $ \left( {{x_1},{y_1}} \right)$,且栅格S1不为障碍栅格,下一邻接节点S2坐标为 $ \left( {{x_2},{y_2}} \right)$,则将S1S2的距离 $ G\left( {{S_1},{S_2}} \right)$ 按式(6)进行计算.

      $\begin{split} &G\left( {{S_1},{S_2}} \right) =\\ &\left\{ {\begin{array}{*{20}{c}} {\sqrt {{{\left| {{x_1} - {x_2}} \right|}^2} + {{\left| {{y_1} - {y_2}} \right|}^2}} } {,\;\;{S_2}{\text{为自由栅格}}};\\ {0.9} {,\;\;{S_2}{\text{为条件栅格}}};\\ 0 {,\;\;{S_2}{\text{为障碍栅格.}}} \end{array}} \right.\end{split} $

      表示式(6)中将机器人所处位置到条件障碍的距离范围设置为 $ \left( {0,1} \right)$,目的是使条件障碍能够更大概率地被选中,通过多次实验可得最优值为0.9.

      步骤 2 对条件栅格采用三角选择法进行筛选,将满足穿越条件的条件栅格加入到待选节点,其余不可穿越的条件栅格加入禁忌表.

      设机器人当前位于节点S1,选择与S1邻接的条件栅格Cg,通过式(7)计算得到S3,如S3为自由栅格,则根据式(8)进行条件障碍筛选分类,将不可穿越的条件栅格放入禁忌表,其它可穿越的条件障碍放入待选节点表. 如此,可使地图得到进一步优化.

      $ {S_3} = 2C{\rm{g}} - {S_1}, $

      $ \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} G\left( {{\rm{Cg}},{S_1}} \right) = 0.9{\text{或}}G\left( {{\rm{Cg}},{S_3}} \right) = 0.9{\text{或}}; \\ G\left( {{\rm{Cg}},{S_3}} \right) = 0,{\rm{Cg}}{\text{不可穿越表}}; \\ \end{array}\; \\ {{{\text{否则}},\;{\rm{Cg}}{\text{可穿越表}}}.} \end{array}} \right. $

      图2所示,机器人从S1移动到S3时,经步骤1的对角障碍检测后标记出的条件栅格Cg1Cg2,再经步骤2筛选出实际可穿越的Cg1作为待选节点,其规划路径为S1Cg1S3,则可得到S1S3的最短路径,既能避免机器人穿越对角障碍,又能获得最短路径.

    • 蚁群算法模拟了自然界中蚂蚁外出觅食的过程,每只蚂蚁在其通过的路径上会释放出信息素,使得一定范围内的蚂蚁能够察觉并影响他们以后的路径选择. 当路径上的蚂蚁越来越多时,该路径上的信息素强度将得到增强,蚂蚁选择该路径的概率增加[15],从而促使整个蚁群最终找到一条最短的路径.

    • 蚁群算法是一种正反馈机制,其实质是调整算法转移概率公式中信息素和启发信息在公式中的占比,使得最优解能够得到更大概率地被选择. 状态转移概率决定着被选为下一节点的可能性大小,蚂蚁由当前节点i选择下一节点j的转移概率为:

      $ P_{ij}^k\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^\beta }}}{{ \displaystyle\sum \nolimits_{j \in {a_k}} {{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^\beta }}}},j \in {a_k};\\ {0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\text{其它}}}. \end{array}} \right. $

      $ {\eta _{ij}}\left( t \right) = 1/{d_{je}}, $

      式中ak表示蚂蚁k可以到达的节点,α为信息素启发因子,β为期望启发因子,$ {\tau _{ij}}\left( t \right)$t时刻蚂蚁从ij的信息素浓度,$ {\eta _{ij}}\left( t \right)$t时刻蚂蚁从ij的启发信息,dje表示节点j到终点e的欧式距离.

      信息素更新策略影响各节点信息素的挥发和积累,引导蚂蚁群能找到一条最优的路径达到目标点,信息素更新公式为:

      $ {\tau _{ij}} = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + {\rm{\Delta }}{\tau _{ij}}\left( {t,t + 1} \right), $

      $ {\rm{\Delta }}{\tau _{ij}}\left( {t,t + 1} \right) = \left\{ {{\rm{}}\begin{array}{*{20}{l}} {\dfrac{Q}{{{L_k}}},\;\;\;{\text{蚂蚁本次迭代经过}}\left( {i,j} \right)};\\ {0,\;\;\;\;\;\;{\text{其它}}}. \end{array}} \right. $

      式中ρ为信息素挥发因子,$ \varDelta {\tau _{ij}}\left( {t,t + 1} \right)$ 表示本次蚂蚁在路径上的信息素增量,Q为信息素强度,Lk表示第k只蚂蚁所走的路径总长度.

    • 蚁群算法在初期的搜索中,信息素浓度较低,启发信息对下一节点的选择占主导作用;而后期随着迭代次数的增加,信息素浓度逐渐增强,启发信息的影响应该得到减弱,以提高算法收敛速度. 由此,本文提出了一种自调整策略动态更新期望启发因子,其基本思想是引入一个可自调整的期望启发因子,随着蚂蚁迭代次数的增加来减弱启发信息对节点选择的影响,将传统蚁群算法的式(9)改进为式(13)和式(14):

      $ P_{ij}^k\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^{\left[ {\beta '} \right]}}}}{{\displaystyle \sum \nolimits_{s \in {a_k}} {{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^{\left[ {\beta '} \right]}}}}\;\;\;,j \in {a_k}};\\ {0,{\text{其它}}}. \end{array}} \right. $

      $ \beta ' = \beta K - k + 1/K, $

      式中k为当前蚂蚁迭代次数,K为蚂蚁总的迭代次数.

      由(14)式可知,当前蚂蚁迭代次数k从0逐渐增加至总的迭代次数K,随着k的增加,期望启发因子 $ \beta '$ 逐渐变小,满足了对期望启发因子前期强、后期弱的自调整策略,使得启发信息逐渐削弱,间接促使信息素的作用得到增强,加快了蚁群算法的收敛速度.

    • 信息素更新的作用是为了减弱陷入死锁蚂蚁所通过路径上的信息素浓度,同时增强每次迭代后最优蚂蚁路径上的信息素浓度. 传统蚁群算法使用固定的信息素增量进行更新,虽然能够使得一些路径上的信息素迅速积累,得到较快的收敛速度,但导致算法搜索范围小,容易陷入到局部最优. 另外,使用2.2节的启发因子自调整策略,随迭代次数的增加会间接促使信息素作用增强,如果仍沿用传统蚁群算法的信息素更新策略,将导致信息素的作用过强. 针对这一问题,本文提出信息素自调整策略,使信息素随迭代次数缓慢增加,将传统蚁群算法的式(11)改进为式(15).

      $ {\tau _{ij}}\left( {t + 1} \right) = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + \frac{k}{K}\varDelta {\tau _{ij}}\left( {t,t + 1} \right), $

      $ \varDelta {\tau _{ij}}\left( {t,t + 1} \right) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{Q}{{{L_k}}},\;\;\;{\text{蚂蚁本次迭代经过}}\left( {i,j} \right)};\\ {0,\;\;\;\;\;\;{\text{其它}}}. \end{array}} \right. $

      式中k为当前蚂蚁迭代次数,K为蚂蚁总的迭代次数.

      改进后的蚁群算法前期 $ \dfrac{k}{K}$ 比较小,信息素增量小,保持了路径选择的多样性,使搜索范围扩大,不容易陷入局部最优;在算法后期,参数 $ \dfrac{k}{K}$ 增大,信息素增量大,最优路径的信息素浓度增大,且1.3节中期望启发因子β的减小进一步促使信息素对节点的选择占主导地位,使得算法的收敛速度得到提高.

    •   步骤 1 利用对角障碍检测将地图中对角障碍附近的自由栅格标记为条件栅格;

      步骤 2 初始化蚁群算法中的各个参数,即信息素启发因子α、期望启发因子β、信息素挥发系数ρ、蚂蚁迭代次数k和蚂蚁数M

      步骤 3 对机器人当前所处栅格的八邻域进行搜索,记录下自由栅格和条件栅格的编号并存入矩阵,作为下一步可选节点,将障碍栅格加入到禁忌表中;

      步骤 4 对下一步可选节点中的条件栅格采用本文1.3节的三角选择法进行筛选,根据式(8)筛选出可穿越的条件栅格并保留在待选节点表中,将不可穿越的条件栅格加入到禁忌表中;

      步骤 5 将待选节点逐一带入公式(13)中计算选择概率所占的比重,通过轮盘赌决定下一步可行进的栅格,并判断蚂蚁数量是否达到最大值,如达到则继续下一步,否返回步骤3继续搜索;

      步骤 6 所有蚂蚁完成一次搜索以后,找出本次迭代中的最优路径,根据公式(15)进行信息素更新,更新完成后将蚂蚁数清零,迭代次数加1;

      步骤 7 判断迭代次数是否达到最高次数Kmax,达到则输出蚂蚁的最优路径长度并绘制收敛曲线,否则跳转至步骤3继续进行搜索.

    • 在Matlab R2019a的软件中进行仿真实验,计算机为Windows10 64 bit的操作系统,CPU为Core i7-9750H,计算机内存为8.00 GB. 为了验证算法的环境适应性和优越性,在多对角障碍环境和无对角障碍环境中分别进行仿真实验.

    • 为了验证多对角障碍的环境中,本文所提出的算法能够有效地避免穿过对角障碍,同时得到最优路径. 仿真环境设置为存在多对角障碍的20×20栅格环境,进行4种不同策略下的规划路径结果比较,同时将收敛曲线、算法运行时间进行对比. 设置初始参数α值为1、β值为7、ρ值为0.5、蚂蚁数目m为50,最大迭代次数Kmax为100,共进行10次实验,取10次实验结果的平均值进行分析.

      图3(a)可以看出,传统蚁群算法在多对角障碍的环境中,虽然规划出了一条抵达目标点的路径,但是所规划的路径穿过了对角障碍,无法在实际场景中运用;图3(b)中采用加入对角障碍检测的传统蚁群算法,通过标记条件障碍,并将条件障碍全部虚拟为障碍栅格,标记后障碍栅格在地图中占比37.25%,比未标记前增加了15%,整个地图环境变得简洁,减少了计算量,同时规划出的路径能成功避免穿过地图中所有的对角障碍. 但可以看出在地图中一些拐角的地方,部分可通过的条件栅格被虚拟为障碍栅格而无法穿越,导致所规划的路径并不是最短;图3(c)中在图3(b)中算法的基础上加入了三角优化算法实现条件障碍的筛选,筛选出可穿越的条件障碍并将其加入待选节点表,比单纯采用对角障碍检测增加了搜索的范围,更有利于得到最优路径. 如此,既避免了穿过对角障碍,又克服了图3(b)中存在的缺陷,寻得了最优路径;图3(a)(b)(c)均采用传统蚁群算法,为解决传统蚁群算法存在的缺陷,图3(d)中对图3(c)中的传统蚁群算法进行了改进,加入参数自调整策略,动态调整期望启发因子和信息素更新机制,形成本文最终的算法,规划出的路径避免穿过对角障碍,且能寻得最优路径.图3(e)绘制了4种不同算法的收敛曲线,从图中可以清晰地看出本文算法在寻到最优路径时的迭代次数明显少于其它算法,并且收敛曲线较为平缓,表明本文算法收敛速度更快,且能稳定地收敛于最优解.

      图  3  多对角障碍环境中不同算法结果对比

      Figure 3.  Comparison of algorithms under multi-diagonal obstacles

      此外,从表1中的实验结果数据可以看出,本文算法中相比其它3种算法,在准确躲避对角障碍得到最优路径的同时,平均收敛迭代次数和收敛时间均为最少,说明了对条件障碍的筛选使地图得到简化,算法计算量减少,提高了算法的收敛速度,同时算法总耗时(即:算法达到最大迭代次数Kmax为100时的耗时)缩短.

      算法平均收敛迭代次数规划路径长度平均收敛时间/s算法平均总耗时/s
      传统蚁群 30 28.6274 2.965221 9.719562
      对角障碍检测 20 30.9706 1.959106 9.576410
      对角加条件障碍 17 28.2563 1.680547 9.660051
      本文算法 11 28.2563 1.054999 6.563211

      表 1  对角障碍环境下的实验结果对比

      Table 1.  Comparison of experimental results in multi-diagonal obstacle environment

      通过上面的实验数据分析,本文的改进算法用于多对角障碍环境中机器人路径规划,能够准确避免穿过对角障碍的同时寻得最优路径,且算法的效率有所提升.

    • 为不失一般性,证明本文的改进算法在无对角障碍的环境中也具有较好的性能,在与文献[11]相同的栅格地图环境中,将本文算法的仿真实验结果与文献[11]的仿真实验结果进行对比分析. 设置初始参数α值为1.3、β值为8、ρ值为0.4、蚂蚁数目m为50,最大迭代次数Kmax为100,在20×20和30×30的栅格地图中分别进行仿真实验.

      通过对比图4(a)4(b)可以看出在无对角障碍的环境中,两种算法在20×20和30×30的地图中都能够寻到一条最优路径,但结合表2的实验结果对比可知,本文算法加入参数自调整策略后,在相同的环境下收敛迭代次数少于文献[11],收敛速度更快. 如此,验证了本文所采用的算法在无对角障碍的环境下同样能获得最优路径,并具有较好的收敛性.

      算法(栅格环境)收敛迭代
      次数(20×20)
      规划路径
      长度(20×20)
      收敛迭代
      次数(30×30)
      路径长度(30×30)
      文献[11]算法1928.043143.36
      本文算法1228.042543.36

      表 2  无对角障碍环境中实验结果对比

      Table 2.  Comparison of experimental results in an environment without diagonal obstacles

      图  4  无对角障碍环境中算法对比

      Figure 4.  Comparison of algorithms without diagonal barrier

    • (1)大多数论文并没有在仿真环境中考虑到对角障碍的存在,而实际运用场景中往往会存在大量的对角障碍. 本文基于文献[12]对角障碍检测的基础上,提出通过三角选择法实现条件障碍的筛选,准确区分可穿越和不可穿越的条件障碍. 仿真结果表明使用加入了对角障碍检测和条件障碍筛选的蚁群算法能够简化地图,并提升地图的准确性,缩短算法运行时间,准确避免穿过对角障碍,并得到最优路径.

      (2)针对传统蚁群算法存在收敛速度慢、搜索范围小而易陷入局部最优等问题,本文提出了一种参数自调整策略,期望启发因子和信息素更新能够随迭代次数的增加得以动态调整,使算法前期扩大搜索范围,后期快速收敛,从而保证在全局搜索中算法的全局性和收敛性都能够得以兼顾,规划出的路线较快地收敛到全局最优路径.

      (3)在多对角障碍和无对角障碍的仿真环境中进行实验和算法对比,实验结果表明,本文算法具有环境适应性强、收敛速度快和寻优能力强的特点,有一定的优越性.

      论文中主要针对环境信息已知的静态路径规划,没有考虑动态环境下算法的适应性,这也是文章的不足之处和后续研究的重点.

参考文献 (15)

目录

    /

    返回文章
    返回