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

占伟 屈军锁 芦鑫 侯磊超

关键词： 仿生优化; 蚁群算法; 栅格法; 移动机器人; 路径规划; 启发因子; 信息素更新策略

中图分类号： TN929.5?34; TP242                 文献标识码： A                  文章编号： 1004?373X（2018）24?0170?04

Global path planning based on improved ant colony algorithm for mobile robot

ZHAN Wei， QU Junsuo， LU Xin， HOU Leichao

（School of Communications and Information Engineering， Xian University of Posts & Telecommunications， Xian 710121， China）

Abstract： The ant colony algorithm is an intelligent bionic optimization algorithm， whose self?organization and intelligence is of guiding significance to the study of global path planning. Based on this， an improved ant colony algorithm is proposed. The environment model is established by using the grid method. The traditional ant colony algorithm is improved by studying and improving the inspiring factor and pheromone updating strategy of the algorithm. The simulation results show that the improved ant colony algorithm has the characteristics of rapid convergence speed and good optimization performance in comparison with the traditional ant colony algorithm.

Keywords： bionic optimization; ant colony algorithm; grid method; mobile robot; path planning; inspiring factor; pheromone updating strategy

0  引  言

随着人工智能领域的高速发展，机器人路径规划问题已成为时代热点之一。全局路径规划问题的研究是研究机器人动态路径规划方法的重要基础。近年来，国内外学者相继提出遗传算法、神经网络算法、人工势场法和蚁群算法等算法[1?2]用于该问题。遗传算法应用性广但存在进化速度下降快，迭代次数冗余等问题[3];人工势场法具有高效性的特点但也存在易陷入陷阱区等问题[4];神经网络算法计算量大且结构复杂[5]。

蚁群算法作为一个智能模式，其具有较强的适应性和协作性，适应性主要表现在通过信息素的积累不断优化结构达到最优目标，没有外界作用力的情况下系统熵动态增加[6]保证系统朝着最优解的方向进行。而机器人路径规划问题是典型的组合优化问题，该问题可模拟成蚂蚁寻找最优路径觅食的群体行为[7]，传统的蚁群算法虽然具有发现最优解的能力，但存在一定的缺陷：收敛速度慢，易陷入局部最优解[7]。现拟提出一种改进的蚁群算法，通过改进的蚁群算法搜索到最优路径，根据信息素的数量大小参照概率自主选择路径，通过调整启发因子函数提高算法收敛速度。

1  基于蚁群算法的移动机器人全局路径规划

1.1  问题描述与模型建立

当移动机器人协作完成某任务时，对于移动机器人而言，首先要做的是获取周边环境信息，建立环境模型，按照自身算法进行定位和避障，最后获得一条最优路径，因此路径规划是完成这一系列工作的首要前提。例如多机器人机场搬运货物问题，货物地点随机分布，机器人如何进行最优路径的选择而高效地进行货物的搬运。本文研究的全局路径规划问题的条件是：

1） 已知全局环境条件，即障碍物的所有位置已知;

2） 机器人与障碍物之间无碰撞，机器人相互之间的碰撞不考虑;

3） 机器人起始位置和目标位置已知。多移动机器人路径规劃需达到的效果是：最优结果，即各移动机器人需找到从出发位置到目的位置的最优（最短）路径。

为了便于研究与分析，本文采用栅格法进行环境建模，即将机器人二维环境信息通过提取与分析转换成可理解的数学空间模型，便于机器人的研究与分析。假定全局环境的空间范围为[S]，[S]为有限工作空间，栅格地图如图1所示。图中白色方块表示可行域，黑色方块表示障碍物域。机器人可到达的位置为以其向周围扩展的8个方位，每个栅格图代表一定比例的大小。

从左下方位开始进行编号，各栅格点对应的坐标数学关系如下：

[xi=mod（i-1，Nx）+0.5yi=fix（i-1）Ny+0.5]    （1）

式中：[mod]表示取余;[fix]表示取整;[xi，yi]表示每个栅格的坐标位置;[Nx，Ny]分别表示每行、每列的栅格数目。

1.2  基于传统蚁群算法的多机器人路径规划问题

蚂蚁在寻找食物源的过程中会留下信息素，蚂蚁根据信息素的数量大小参照概率自主选择路径，因此蚂蚁可以找到从住巢到食物地之間的最优路径即最短路径[8?9]。蚂蚁行走示意图如图2所示。

初始状态，设定每条路径上的信息素含量相等，蚂蚁[k]从栅格[i]转移到栅格[j]的状态转移概率[p（k）ij（t）]由信息素量[τij]、启发函数[ηij（t）]、信息启发因子[α]以及期望启发式因子[β]决定[10]。

（2）

式中：[τij]表示t时刻栅格点[ni，nj]之间的信息素含量;[Aa]表示禁忌表之外的蚂蚁允许走的节点。在完成一次循环对路径上的信息素上进行更新，假定完成一次周游所需时间为[Δt]，[t+Δt]时刻路径[i，j]上的信息素[11]为：

[τijt+Δt=1-ρ?τijt+Δτijt] （3）

[Δτij（t）=k=1mΔτkij（t）] （4）

[Δτkij（t）=QLk，蚂蚁k经过（i，j）0]  （5）

[ηij（t）=1dij]   （6）

式中：[ρ]表示信息素挥发系数，[ρ∈0，1];[Q]表示信息素强度其值为常数;[dij]表示栅格[i]到栅格[j]的距离;[Lk]表示在本次循环结束时蚂蚁所走路径的长度。

2  基于改进蚁群算法的多机器人路径规划

改进的蚁群算法流程图如图3所示。

步骤1：建模和环境描述，利用栅格法进行建模，设置算法参数;

步骤2：将[m]只蚂蚁放在初始位置;

步骤3：根据概率矩阵选择路径，并且将已走过的路径添加至禁忌表，同时对下一步需走的路径依照算法进行选择;

步骤4：死锁防止，若蚂蚁搜索出现死锁现象，终止搜索并设置当前路径长度为无穷大;

步骤5：找出此次迭代最小路径[dbest]、最长路径[dworse]以及之前迭代的最小路径，并判定其与[dbest]的大小;

步骤6：更新信息素;

步骤7：重复步骤3～步骤6，直至迭代次数=设定的迭代次数，得到最短路径;对传统算法进行了如下改进。

2.1  启发因子

算法中，启发因子为[ηij（t）]与节点之间的距离成反比，蚁群算法作为自组织结构存在搜索时间长的缺陷，而算法对时间度要求较高。本文对搜索因子即启发因子做出了改进：根据所求空间的具体特征（两个节点之间的距离），给定蚁群算法一个初步引导方向，改进的蚁群算法的启发因子[ηij（t）]，[ηij（t）=1d2ij]，跟距离平方成反比，大大增加算法的时间有效性，能够减小算法收敛的时间，同时保证最短路径的搜索方向向着最短目标最优方向进行。

2.2  信息素的更新策略

传统蚁群算法信息素的更新方式使得搜索结果易陷入局部最优解，导致出现“死锁”现象，越来越多的蚂蚁选择同一条路径而忽略其他路径，很难寻得最优解。基于此，本文改进信息素的更新策略，通过关系使信息素不仅进行全局搜索，而且保证信息每次迭代过程中将本次迭代中的最短路径和最长路径运用到信息素的更新方式上。全局搜索和局部搜索相结合使得解不会因收敛过快而陷入局部最优解，同时又保持快速发现最优解的能力。

[τijt+Δt=1-ρ?τijt+Δτijt+dbestdworse]

（7）

式中：[dbest]表示迭代过程中的最短路径;[dworse]表示迭代过程中的最长路径。

正负反馈的结合保证系统以最优的状态寻得最短路径。正反馈使得系统始终朝着最优解的方向进行，算法实现的过程中采用概率搜索，缩小解的范围;负反馈使得算法不会过早收敛，在两者的共同作用下，使机器人花费最少的时间代价而寻找一条最优路径。

3  结果及分析

本文采用Matlab作为仿真工具，实验过程分别选取39，52，80，100蚂蚁数目（[m]值）进行设定，仿真参数：最大迭代次数设定为400，[α=0.9]，[β=6.8]，[Q=125]，[ρ=0.75]，传统蚁群与改进蚁群算法选取的蚂蚁数目相同。

3.1  传统蚁群算法

图4为传统机器人的最短路径收敛图。

由仿真结果图看出，算法在迭代240次后得到一个最优解值为680，从而其最佳优化指标为：

[c1=c0-c*c*=680-c*c*]           （8）

式中：[c*]表示理论上该问题的最优解;[c0]表示采用传统的蚁群算法得到的最优解，时间性能指标为：

[t1=E1TE=240TE] （9）

式中：[E1]表示终止条件时迭代的次数;[E]为给定的迭代次数;[T]为迭代一次所需的时间。

3.2  改进的蚁群算法

图5为最优路径搜索图（其中每个栅格代表一定比例的路径大小）。图6为改进蚁群算法的机器人最短路径收敛图。

由图6得，算法在迭代115次后得到一个最优解值455，从而得其最佳优化指标：[c2=c0-c*c*=455-c*c*]，时间性能指标[t2=E1TE=115TE]。

3.3  结果分析

选取蚂蚁数目的不同，将改进的蚁群算法与传统的蚁群算法进行对比，对比表格如表1所示。

其中[c]代表最短路径，[E]代表迭代次数，最佳优化性能指标表示算法解决问题的优化程度（找到最短路径），针对该问题，其值越小表示算法的解越优，根据点数不同得到的实验结果分析：[c1>c2]，因此改进的蚁群算法相对传统的蚁群算法优化性能更好。时间性能指标与算法搜索的快慢程度有关，其值的大小与收敛的快慢程度成反比，其值越小收敛越快，值越大收敛越慢。[t1>t2]，因此改进的蚁群算法收敛更快。综合分析，随着点数的增加，研究问题的复杂度的增加，改进的蚁群算法在最佳优化指标和时间优化指标的优势越来越明显。

4  结  语

移动机器人全局路径规划问题是一个典型的智能优化问题，建立环境模型抽象成数学坐标，在分析传统蚁群算法的基础上，对传统蚁群算法进行了改进：主要从启发因子和信息素更新策略两方面。改进的蚁群算法较传统的蚁群算法具有良好的优化性能，且改进的蚁群算法收敛速度更快。

参考文献

[1] 史恩秀，陈敏敏，李俊，等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报，2014，45（6）：53?57.

SHI Enxiu， CHEN Minmin， LI Jun， 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.

[2] 屈鸿，黄利伟，柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报，2015，44（2）：260?265.

QU Hong， HUANG Liwei， KE Xing. Research of improved ant colony based robot path planning under dynamic environment [J]. Journal of University of Electronic Science and Technology of China， 2015， 44（2）： 260?265.

[3] YU J， LAVALLE S M. Optimal multi?robot path planning on graphs： structure and computational complexity [J/OL]. [2015?07?12]. https：//arxiv.org/pdf/1507.03289.pdf.

[4] LI J， DONG T， LI Y. Research on task allocation in multiple logistics robots based on an improved ant colony algorithm [C]// Proceedings of International Conference on Robotics and Automation Engineering. Jeju： IEEE， 2016： 17?20.

[5] LIU J， YANG J， LIU H， et al. An improved ant colony algorithm for robot path planning [J]. Soft computing， 2017， 21（19）： 5829?5839.

[6] 张成，凌有铸，陈孟元.改进蚁群算法求解移动机器人路径规划[J].电子测量与仪器学报，2016，30（11）：1758?1764.

ZHANG Cheng， LING Youzhu， CHEN Mengyuan. Path planning of mobile robot based on an improved ant colony algorithm [J]. Journal of electronic measurement and instrumentation， 2016， 30（11）： 1758?1764.

[7] 牛治永，李炎，李晓岚.基于改进蚁群算法的机器人路径规划[J].自动化技术与应用，2011，30（7）：1?4.

NIU Zhiyong， LI Yan， LI Xiaolan. Path planning of detecting robot based on improved ant colony algorithm [J]. Techniques of automation and applications， 2011， 30（7）： 1?4.

[8] 肖国宝，严宣辉.一种新型协作多机器人路径规划算法[J].计算机科学，2013，40（4）：217?220.

XIAO Guobao， YAN Xuanhui. New cooperative multi?robot path planning algorithm [J]. Computer science， 2013， 40（4）： 217?220.

[9] 邱莉莉，郑建立.基于改进蚁群算法的机器人路径规划[J].信息技术，2015（6）：150?152.

QIU Lili， ZHENG Jianli. Based on improved ant colony algorithm for robot path planning [J]. Information technology， 2015（6）： 150?152.

[10] 王忠民，曹栋.基于蚁群算法的行为识别特征优选方法[J].西安邮电大学学报，2014，19（1）：73?77.

WANG Zhongmin， CAO Dong. A feature selection method for behavior recognition based on ant colony algorithm [J]. Journal of Xian University of Posts and Telecommunications， 2014， 19（1）： 73?77.

[11] 游晓明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（3）：552?556.

YOU Xiaoming， LIU Sheng， L? Jinqiu. 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.