基于HGM与TGSA的机器人路径规划算法研究

姚成信，王冠凌，陈孟元

(安徽工程大学 安徽省电气传动与控制重点实验室，安徽 芜湖 241000)

移动机器人路径规划问题就是在充满各种障碍物的环境中，机器人遵从一定的规则(如路径最短、耗时最短或安全度最高等)，从起点到终点独立搜索出一条与障碍物无碰撞的最优或者次优路径．因此，机器人路径规划问题的研究需要解决环境建模与最优路径搜索两大基本问题．为解决以上路径规划的两个问题，一是需要根据已知环境信息建立较为精确的环境地图模型；二是在规模较大、环境复杂的情况下，运用一种合适的建模方法和高效率的算法对路径进行规划[1]．

自然界一直给人们带来各种灵感与启发，人们一直在尝试利用来自于自然界中的种种现象来解决许多类似的实际问题，如人工神经网络，遗传算法，人工势场法，粒子群算法，蚁群算法，蜂群算法，人工鱼群算法等的提出和改进都为相关问题的解决提供了很好的思路．上述算法都是基于仿生原理或者模拟自然现象，但从生物进化角度来看，作为生长在生物底层的植物具有更简单和更有效的特征，模拟植物生长过程构建的路径规划算法可能会达到更好的效果．最早基于植物生长形态提出仿生计算算法是在1968年，荷兰Utrecht大学的生物学和植物学家，匈牙利裔的林登麦伊尔(Aristid Lindenmayer)等人提出利用计算机模拟植物生长系统(L-systems)，主要用于分形领域及计算机图形学的研究．土耳其Ali KARCI基于栽培和种植树苗的自然过程，提出了树苗生长算法(SGuA)．使用交配、分枝和接种三个阶段来对树苗的播种和成长过程进行抽样优化，并将所提出的方法应用于标准测试函数，结果表明该方法在寻找更好的解决方案和函数评估次数的情况下要优于遗传算法[2]．

国内最早对于以植物为对象的算法的研究，是由李彤[3]等在2005年提出的模拟植物生长算法(PGSA)，主要是将该算法运用于整数规划问题的求解，并取得了较为满意的效果．崔志华等人从植物的生长机制上对植物进行研究，模拟包括光合作用、向光性、顶端优势这三个生长机制，提出了标准的人工植物优化算法(APOA)，分析论证了人工植物算法的运行机理，建立起比较科学、完整的算法研究框架，并开始初步探讨了有关算法的收敛性、稳定性和计算复杂度等一系列理论问题[4-5]．郭改文[6]等提出模拟自然树生长的竞争算法(GCA)，并建立了自然树生长的竞争模型．该算法具有拟合精确度高、运行速度快、内存占用率低等优点，为优化设计和计算等问题的解决提供了一种新的思路．周尧明[7]等提出一种基于植物生长机制的生物启发计算算法(PGPP)，并描述其在路径规划中的应用．该算法具有良好的路径规划能力，并提供了一种新颖的路径规划方法．

文中通过采用一种既考虑到全局路径信息又考虑到行走安全性和有效性的蜂巢栅格法构建了机器人环境地图模型．针对利用传统算法求解机器人路径规划时全局搜索能力差，易陷入局部最小点的问题，用一种新的优化算法——生长树算法，对原机器人路径规划模型进行改进，寻找一条更优路径．

1 蜂巢栅格法环境建模

图1 移动机器人运行环境

在由蜂巢栅格组成的环境地图中，环境被等分为形状相同的六边形栅格，文中地图环境模型的构建建立在由40*50的蜂巢栅格组成的二维空间平面中，且空间内仅存在静态障碍物，同时赋予相应数值表示障碍物对应的位置．假设移动机器人运动区域中的起始位置为第一个蜂巢栅格B(xB,yB)、目标位置为T(xT,yT)，区域中静态障碍物位置及大小已知，根据区域环境地图中的起始位置、目标位置以及障碍物位置，以横轴为X轴，纵轴为Y轴，构建新的蜂巢栅格坐标系，如图1所示．在实际应用中根据地面机器人的尺寸，将移动机器人缩小为一个质点，机器人在栅格地图中的移动看作质点的移动.环境中将障碍物边界做相应的扩展及模糊化处理(黑色阴影)，空白栅格表示机器人能够自由通过的地方，图1a代表机器人路径的起始点位置，图1b代表目标点位置，这样就将空间中机器人路径规划问题转化为栅格图中的最短路径搜索问题，简化了问题求解的复杂性．

2 树生长模拟算法

2.1 算法的寻优原理

完整的大树包括树干和无数的分枝，它们的生长方向始终向着太阳，这个生长的过程可以类比无数条路径的组合；由于在阳光照射下，一些上层枝叶会对下层枝叶遮挡，产生的阴影可看作面积不同的障碍物；各分枝当中最优的向光生长过程就是最优的路径规划形式．树的顶端优势现象就是其中一条最理想的机器人路径规划，它描述的是从树根到树冠顶端的无障碍理想路径方式．

将树向光分枝生长的路径过程看作是机器人路径规划中的全局遍历式路径搜索寻优过程，决定其随机分枝生长所获得的光照强度看作一种适应值函数，即目标函数；光照强度最适宜的位置对应到算法中为适应值最优的位置，即局部最优解；最优位置处生长出的嫩芽看成算法中进行局部搜索的点；众多不断分枝出来的枝条看作搜索空间的路径；树木生长方式看作个体移动；树苗描述为路径规划的起点，太阳位置描述为目标点，树苗向着太阳方向不断生长的过程看作是一条规划起点到终点的最优过程[8-10]．其对应关系如表1所示．

表1树生长模拟算法与路径规划问题的对应表

路径规划问题的定义域[xmin,xmax]树的生长环境算法的迭代次数t树分枝的生长期局部最优解(xbest,ybest)光照强度适宜的位置目标函数I(i)光照强度算法中的一段路径i树的枝条机器人位置移动(xti,yti)枝条的生长所有路径条数m枝条的总数

2.2 寻找全局最优解的理论依据

(1)在树的生长过程中顶枝会不断地分化出侧枝，由于顶枝受光面积大，相比侧枝生长活跃，这样顶枝的相关性选择机制更多，从而使各顶枝能不断地进行局部寻优．

(2)生长素和光照的分布使得在枝干最优位置点附近区域局部搜索的可能性更加合理，从而在最优解周围搜索出更优解的可能性增大．

(3)光照的作用使得部分顶枝生长停止，侧枝替代其成为顶枝，并重新生成新的侧枝向光生长．这种方式能将当前局部搜索能力较强的位置(顶枝)加以屏蔽，从而能迅速改变树枝的生长方向，有效地跳出局部极值点进行全局寻优．树向光生长有3种典型的情况，如图2所示．图2a表示没有障碍物的情况，图2b、图2c表示具有一些障碍的情况；Bud处网格表示当前树芽，Target处网格表示当前增长的终点，黑色的是障碍，灰色的是树生长路径的过程．首先，采用倾斜方式生长，如图2a所示.树在生长过程中没有遇到障碍物，保持正常的向光生长；如果障碍物出现在生长方向上，则绕开障碍物朝目标方向继续生长，如图2b所示；如果生长过程中没有可行的方向，如图2c所示，树停止分枝生长，将不会进行任何进一步的计算．障碍处可能首先出现的分枝将首先生长．被障碍阻塞的其他分枝将决定是继续增长还是停止，这取决于障碍物在哪里．

图2 树向光生长的3种典型情况

3 树生长模拟算法在机器人路径规划中的研究应用

3.1 路径规划的数学模型

在标准生长树模型中，将光照强度分布在特定生长树的区域范围视为该生长树模型的定义域区间，树在生长过程中通过不断感知区域内不同的光照强度来进行分枝-生长，最终向最佳光照方向寻优出最优生长路径．生长树算法将优化问题的定义域视为树的生长环境，算法的迭代次数视为树的生长周期．在枝芽的光合作用进入向光性阶段时，树分别利用生长期优化规则进行寻优分枝点；最后进入生长寻优阶段，枝芽会在向光生长过程中根据寻优规则完成全局遍历式寻优．在生长树经历完整个生长周期后，算法收敛停止，找到最优生长路径．

图3 蜂巢栅格坐标图

(1)

式中，Nx为X轴上的最大序号数，Ny为Y轴上的最大序号数．

蜂巢栅格坐标(xi,yi)与序号i的关系可表示为：

(2)

式中,Nx1为第一奇数行最大序号数，Nx2为第一偶数行最大序号数．int表示取最大整数运算；mod表示求余运算．

(2)光合速率计算.首先在环境区域内遍寻各位置处的光照强度及对应的光合速率，即寻找目标函数，式(3)表示坐标上任意点(xi,yi)处枝条的光照强度，式(4)代表坐标(xi,yi)位置处枝条的光合速率．

(3)

式中，kl表示光照强度系数，(xD,yD)是目标点的位置，(xB,yB)是起始树芽的位置．

(4)

图4 生长素浓度与生长速率的关系

(3)随机分枝.生物学实验证明，决定枝芽细胞分裂和生长的生长素信息不是每个细胞与生俱来就被赋予的，而是细胞生长系统从其环境中接受到了分裂生长的位置信息，根据这种信息，表现出明显的向光性生长特点[12]．由于光照强度大的位置，树生长时进行光合速率快，生长速率快，此处生长素浓度往往处于最佳生长素点附近，如图4所示.由图4可知，芽的生长素浓度与生长速率的关系处于一个变化的过程，生长素浓度太高或者太低都会对芽的生长速率产生很大的影响，所以最佳芽生长素浓度位置附近最容易首先产生分枝，即规定光照强度最大位置对应光合速率最大位置，也是最佳生长素浓度处．这也是算法中的局部最优解处．

(5)

一旦新分枝发芽时，新枝和旧枝合二为一，均看作同一平面内的同一枝干．

(4)模拟环境下寻优生长.植物在生长过程中会受到许多影响，如自身顶端优势的影响、自然灾害(火灾、雷击等)及人工作用(人工剪枝等)，在此为了简单起见，一律将其分为没有障碍和具有一些障碍两种典型的情况．树在生长过程中没有遇到障碍物，保持正常的向光生长；如果障碍物出现在生长方向上，则另一个方向变为生长方向；如果生长过程中没有可用的方向，则树停止分枝生长，将不会进行任何进一步的计算．障碍可能是首先出现的分枝．首先出现的分枝将首先生长．被分枝阻塞的其他分枝将决定是继续增长还是停止，这取决于障碍物在哪里．其具体的规则如下：

式(6)表示枝条的顶芽(最优位置)在顶端优势作用下生长，看作是路径规划中没有遭遇障碍物模型．

(6)

式(7)表示由于上面的枝叶遮挡导致光合作用不足，在自然因素的作用下，树枝随机选择性转变生长方向，看作是路径规划中遭遇障碍物模型．

(7)

式(8)则表示侧枝在向光生长过程中由于光合作用不足，生长素浓度不足以提供枝叶生长所需的能量，导致枝条停止生长，看作是路径规划中陷入障碍物模型．

(8)

针对模拟环境下寻优生长的3种不同模型，对该算法下的最优路径规划设计目标函数为：

(9)

式中，μ1,μ2,μ3均为权值系数，用来调整寻找出一条最优路径．

3.2 基本算法流程

TGSA主要包括6个步骤，TGSA流程图如图5所示．

图5 TGSA流程图

4 仿真实验对比分析

4.1 两种不同环境地图下的算法对比

实验地图环境模型建立在由30*30的蜂巢栅格组成的二维空间平面中．地图中左下角处栅格为机器人的路径起点，地图中右上角处栅格为终点，黑色栅格为障碍物．算法仿真结果对比如图6、图7所示，普通栅格地图下的机器人路径如图6所示，蜂巢栅格地图下的机器人路径如图7所示．

在图6、图7中，地图环境区域分别设置为30*30的传统栅格和蜂巢栅格．障碍物全部扩展为圆形障碍物，两种地图中的障碍物圆心及半径已知，即地图中全部静态圆形障碍物位置已知，且全部位置对应相同，两种地图中的起始位置和目标位置均相同．

通过图6、图7中转弯处位置可以看出，蜂巢栅格遇到障碍物，每次移动方向改变的转角为60°，相比传统栅格法的90°转角，降低了运动过程中转弯带来的安全性问题，同时单次转弯走过的路径总长度与无障碍时通过的直线距离比传统策略更高，使得最后规划的路径长度要比传统路径短且安全性并不降低．同时可见，树生长模拟算法在两幅地图中均能很好地绕开障碍物，从起点到终点搜索到一条最优路径．

图6 栅格地图下的路径图图7 蜂巢栅格下的路径图

蜂巢栅格下的TGSA算法和普通栅格下的TGSA算法仿真结果对比如表2所示.30*30最优路径收敛曲线图如图8所示.由表2和图8可以看出，蜂巢栅格下的TGSA算法相比普通栅格下的TGSA算法，迭代次数和运行时间都有所降低，最优路径长度减小．

表2 蜂巢栅格下的TGSA算法和普通栅格下的TGSA算法仿真结果对比

4.2 同种环境地图下不同算法的实验对比

实验地图环境区域设置在30*30的蜂巢栅格中，如图9所示．蚁群算法下的机器人路径如图9中粗折线所示，TGSA算法下的机器人路径图如图9中细折线所示．障碍物全部扩展为圆形障碍物，两种地图中的障碍物圆心及半径已知，即地图中全部静态圆形障碍物位置已知，且全部位置对应相同，两种地图中的起始位置和目标位置均相同．

图8 30*30最优路径收敛曲线图图9 蜂巢栅格下的路径图

仿真结果对比如表3所示.40*50最优路径收敛曲线图如图10所示.在表3和图10中，相同规模大小的环境地图，通过对比蚁群算法下的机器人路径规划，由仿真实验结果可以看出蜂巢栅格法下结合树生长模拟算法具有迭代层次少，路径长度短，规划时间更短的优点，同时树生长模拟算法具有更快的收敛速度和全局搜索能力，使移动机器人路径规划问题得到一定的提高．

表3 蚁群算法和TGSA算法仿真结果对比

图10 40*50最优路径收敛曲线图

5 结论

树生长模拟算法不同于以往的仿生算法，它是模拟现实中树木的一般生长过程，从树木的内在生长机理出发，打破了以往众多其他仿生算法模型中主要以模拟自然规律或者细菌、昆虫以及动物的生长生活方式为主的传统研究方法，为群智能计算的发展开辟了新的领域[13]．

植物与动物有着不同的生长方式，植物的生长周期慢、生长区域范围较广，而且植物种群在一定程度上对自然的适应能力要超过动物群体，这些使问题研究的稳定性和可靠性得到保证．其他生物由于生长周期短，所以一些行为必须要求在较短时间内完成，这使得在模拟相关算法求解优化问题时，算法收敛速度较快，容易使算法陷入局部极值点．可见，树生长算法为机器人路径规划优化问题提供了一种新思路，丰富了群智能算法[14]．

文中提出了一种基于树生长机制的路径规划算法，详细描述了TGSA的基本原理，建模和实现过程．TGSA的运行效率高，操作过程稳定，具有良好的路径规划能力．未来TGSA在其他最优问题上的应用将是一个必要和有趣的研究．

[1] 曾辰,许瑛.一种蜂巢栅格下机器人路径规划的蚁群算法[J].机械科学与技术,2016,35(8):1 308-1 312.

[2] A KARCI.Natural inspired computational intelligence method:saplings growing up algorithm[C]//IEEE International Conference on Computational Cybernetics，Gammarth：IEEE,2007:221-226.

[3] 李彤,王春峰,王文波,等.求解整数规划的一种仿生类全局优化算法-模拟植物生长算法[J].系统工程理论与实践,2005，25(1):76-85.

[4] X CAI,X WU,L WANG,et al.Hydrophobic-polar model structure prediction with binary-coded artificial plant optimization algorithm[J].Journal of Computational & Theoretical Nanoscience,2013,10(6):1 550-1 554.

[5] 刘坤.人工植物优化算法混合策略的研究及应用[D].太原：太原科技大学,2011.

[6] 郭改文,黄卡玛.模拟自然树生长的竞争算法及在曲线拟合中的应用[J].电子学报,2008,36(9):1 839-1 843.

[7] Y ZHOU,Y WANG,X CHEN,et al.A novel path planning algorithm based on plant growth mechanism[J].Soft Computing,2016，21(2):1-11.

[8] 孔令飞,王淳,熊云,等.模拟植物多向生长的配电网重构算法[J].电测与仪表,2016,53(24):1-5.

[9] 吴俊秋,何迪.模拟植物生长算法及其改进研究[J].通信技术,2016,49(12):1 629-1 634.

[10] 王莉,秦勇,徐杰,等.植物多向生长模拟算法[J].系统工程理论与实践,2014,34(4):1 018-1 027.

[11] S AKYOL,B ALATAS.Plant intelligence based metaheuristic optimization algorithms[J].Artificial Intelligence Review,2016,47(4):1-46.

[12] 蔡伟.不确定性多目标MDO理论及其在飞行器总体设计中的应用研究[D].北京：国防科学技术大学,2008.

[13] 杨红娟.人工植物算法设计[D].太原：太原科技大学,2011.

[14] 曹策俊,李从东,杨琴,等.模拟植物生长算法在组合优化问题中的应用:研究进展[J]. 技术经济,2017,36(5):127-136.