更全的杂志信息网

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

更新时间:2016-07-05

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

式中,P表示t+1代枝叶生长周期的任意一点i的坐标位置.

图3 蜂巢栅格坐标图

(1) 坐标变换.蜂巢栅格坐标图如图3所示.设蜂巢栅格的边长为1,xmaxymax分别表示X轴方向和Y轴方向的最大值;e1e2表示X轴和Y轴上一个单位的向量,且

他写下了“行到水穷处,坐看云起时”,写下了“返景入深林,复照青苔上”,写下了“独坐幽篁里,弹琴复长啸。深林人不知,明月来相照”。每一个字都能让人感受到他心绪的平静。

(1)

式中,NxX轴上的最大序号数,NyY轴上的最大序号数.

从表2可以看出,随着乙酸铵与对硝基苯甲腈物质的量比增加至1.05时,产品的收率也得到逐步提高,当达到1.10时,收率变化不大。主要原因是:乙酸铵用量的增加,一定程度上促进了氨气的释放,进而促进了反应的正向进行,提高了反应收率;但如果乙酸铵的量过大,反应释放的氨气来不及反应就被系统排出,从而导致反应收率偏低。从工业化生产方面来讲,乙酸铵用量过大,不仅造成原料成本增加,更重要的是增加了企业的“三废”,使后处理成本明显增加。综合考虑以上因素,选择乙酸铵与对硝基苯甲腈的物质的量比为1.05。

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

(2)

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

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

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

(3)

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

(4)

式中,α为光合作用中光响应曲线在光照强度为零时的斜率,即光响应曲线的初始斜率(初始量子效率),β为修正系数,PRmax是最大净光合速率,γ为初始量子效率与植物最大光合速率之比,即是暗呼吸速率.αPRmaxRd这3个参数都是用于控制光合速率大小的[11]

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

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

(5)

式中,表示t代枝叶所感应到的光照强度的最强位置;表示该点处向光方向的随机数,t表示分枝前该枝生长周期,t+1表示分枝后该枝生长周期.

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

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

式中,表示t+1代枝叶生长周期的任意一点所对应的i)的坐标位置;是以为中心的邻域范围内t代生长周期的任意一点i的坐标位置; growth是权重,r是(0,1]之间的随机数.

(6)

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

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

(7)

式中,表示t+1代枝叶生长周期的任意一点i的坐标位置;P(xmax,ymax),P(xmin,ymin)分别是以为中心的邻域范围边界上的最优值点和最差值点;其中,r是(0,1]之间的随机数.

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

根据GB/T50801《可再生能源建筑应用工程评价标准》将计算出的EER进行能效等级划定[5],如表1所示:

P

(8)

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

在事业上,拉加德一往无前,但个人生活却充满遗憾。1982年,她与一位银行家结婚并生了两个儿子,但这段婚姻维持没多久就结束了,拉加德说:“我生命里的男人都无法接受我的成功。”

(9)

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

浙江属东部沿海省份,素有“七山一水二分田”之称,长年受梅雨和台风暴雨的影响,由于特殊的地理环境和气候条件,浙江省是山洪灾害易发、多发省份,山洪灾害对经济社会和人民生命财产造成极大的危害。随着全球气候变化,极端天气事件增多,浙江省出现强降雨特别是局地强降雨的趋势明显,雨强纪录不断被刷新,山洪灾害呈多发的态势。据统计,近年全省小流域山洪灾害造成的人员伤亡占洪涝灾害伤亡总人数的70%以上。山洪灾害已成为浙江省自然灾害造成人员伤亡的主要灾种,是当前防洪减灾亟待解决的突出问题。

样品的全部制备过程均应遵循无菌操作程序,无菌生理盐水作为稀释液。以无菌操作称取25 g样品,置于225 mL稀释液的无菌均质袋中,用拍击式均质器拍打2 min制成1:10的样品稀释液。

3.2 基本算法流程

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

图5 TGSA流程图

4 仿真实验对比分析

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

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

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

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

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

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

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

算法类型问题规模最优路径长度运行时间/min迭代次数栅格法+TGSA30*3055.451.30102蜂巢栅格法+TGSA30*3046.231.1590

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

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

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

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

经综合平衡分析后,各试验因素的最优组合确定为A3B1C2,即吸孔直径按位,种箱相对于滚筒的角度为0°,输送带的速度为0.03m/s。此时空穴率为9.26%,单粒率为68.52%,重播率为22.22%。

无一例外的是,在上述三种情况下,入住公办的养护院是照料者的一致首选。尤其是对于照料者去世后的情形,高达四成多的照料者选择入住公办的养护院。在最理想的情境下,入住公办的养护院也依然最受照料者的青睐。值得一提的是,在第三种情况下,照料者表露出对心智障碍成员社会融入的渴求——近三分之一的照料者希望这些成员能主要依靠助残日托照料(综合照料体系)来实现未来安置,而不是进入公办的养护院简单了事。在三种情形中,心智障碍成员由亲朋负责照料是入住公办的养护院与还没有计划后的主要选择。

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

算法类型问题规模最优路径长度运行时间/min 迭代次数 蜂巢栅格法+蚁群算法30*3058.131.28100蜂巢栅格法+TGSA算法30*3046.231.1590

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

5 结论

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

而对应用于造纸、无机凝胶、有机膨润土、药用及饲料膨润土等膨润土的高附加值产品制备,除对膨润土含蒙脱石属型有限制要求外,其加工过程涉及湿法选矿提纯,根据原料类型及产品用途,精矿产品选矿回收率一般仅控制在≥30%,但提纯精矿后的中(尾)矿一般再次配矿做球团、铸造、建材原料等生产低附加值产品,按分级利用蒙脱石的思路,其精矿及低档用途合计膨润土选矿回收率实际值也多接近100%,原矿利用率(即选矿回收率)较高。

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

Research on Robot Path Planning Algorithm Based on HGM and TGSA

YAO Chengxin,WANG Guanling*,CHEN Mengyuan

(Key Laboratory of Electric Drive and Control,Anhui Polytechnic University, Wuhu 241000, China)

AbstractAiming at the problems poor global search ability of the mobile robot in the global path planning,accumulated large turning Angle, low operation efficiency and low security in the process of motion,the tree growth simulation algorithm (Tree Growth Simulation Algorithm,TGSA) is introduced and combined into the honeycomb grid environment map (Honeycomb Grid Map,HGM) to plan out one of the most Excellent path.This method combines the faster convergence rate of TGSA,the global search capability and the security and effectiveness of HGM.It possesses a very good planning and obstacle avoiding effect.The test results show that the combination of TGSA and HGM can get out of the local minimum point and the safety and convergence speed are improved and the path planning ability is good.

Key wordspath planning;tree growth;honeycomb grid;light intensity

中图分类号:TP242.6;Q811.211;TP751

文献标识码:A

文章编号1672-2477(2018)02-0051-07

收稿日期2017-11-14

作者简介姚成信(1991-),男,安徽铜陵人,硕士研究生.

通讯作者王冠凌(1971-),男,安徽芜湖人,教授,硕导.

姚成信,王冠凌,陈孟元
《安徽工程大学学报》2018年第2期文献

服务严谨可靠 7×14小时在线支持 支持宝特邀商家 不满意退款

本站非杂志社官网,上千家国家级期刊、省级期刊、北大核心、南大核心、专业的职称论文发表网站。
职称论文发表、杂志论文发表、期刊征稿、期刊投稿,论文发表指导正规机构。是您首选最可靠,最快速的期刊论文发表网站。
免责声明:本网站部分资源、信息来源于网络,完全免费共享,仅供学习和研究使用,版权和著作权归原作者所有
如有不愿意被转载的情况,请通知我们删除已转载的信息 粤ICP备2023046998号