基于ACO算法的变电站运载机器人路径优化方法研究

严 宇,潘舒妍,黄文杰,江 维,樊绍胜

(1. 国网湖南省电力有限公司超高压变电公司, 湖南 长沙 410004;2. 变电智能运检国网湖南省电力有限公司实验室, 湖南 长沙 410004;3. 长沙理工大学电气与信息工程学院, 湖南 长沙 410114;4. 武汉纺织大学机械工程与自动化学院, 湖北 武汉 430073)

变电站运载机器人作为一种新型运输机器人,其主要工作任务是按照既定的路径规划或者自主规划的路径进行变电站工具、货物、作业人员的运输[1-4].由于机器人在运输时从起始点到达目标点会有多条行进路径,而且要求机器人能够自主避障,因此,在众多行进路径中按照一定的性能准则选取最优路径,即对机器人的路径进行最优规划是提升机器人智能行为能力的关键.当前,在工业机器人领域路径规划已有较多的研究成果,总体可分为传统路径规划算法[5]和智能路径规划算法[6]两大类.传统路径规划算法根据环境的不同可分为全局规划和局部规划,全局规划为已知环境信息基本不变,而局部规划是在未知环境中进行规划,需要借助传感器对局部环境进行信息感知才能实现机器人的自主寻迹和避障;智能路径规划算法包括遗传算法、蚁群算法、粒子群算法等群体智能算法[7-11],已取得了一些实际应用成果.变电站运载机器人属特种机器人行业,其工作于极端电力环境下,因此,变电检修运载机器人对于路径规划的实时性和精确性要求高,亟需寻找一种实时性好、规划精度高的算法.目前已有基于激光导航并结合蚁群算法的最优路径规划方法[12]、改进蚁群优化IACO算法[13]、模拟退火法[14]等,并在实际变电站进行了路径规划,提升了系统鲁棒性和复杂环境下的规划能力.机器人路径规划性能与算法本身及算法参数有关,特别是算法的参数对算法收敛性及收敛精度具有较大影响,会直接影响到机器人路径规划的实时性和路径的精确性,因此,各类改进算法在机器人路径规划领域的应用层出不穷.

本文提出一种基于蚁群算法(ant colony algorithm,ACO)的变电站运载机器人最优路径规划算法.首先介绍ACO算法的基本原理和搜索过程,对变电站检修运载机器人建立路径规划地图;通过ACO算法与A*算法的仿真对比验证ACO算法在处理复杂路径问题上的优势;采用不同参数对ACO算法路径规划性能进行仿真得到最优算法参数;通过机器人物理样机在现场变电站中的测试与应用验证了本文所提出算法的工程实用性.

1 ACO算法基本原理与参数分析

1.1 ACO算法原理

蚁群算法是模仿自然界中蚁群的觅食方式而提出的,即蚁群在存在障碍物的情况下能够找到一条较短的路径到达食物源或者洞穴.从生物学角度出发,单只蚂蚁在行进过程中会释放一种信息素物质,用于与其它蚂蚁进行信息交流.信息素在自然环境中会以一定的速率挥发在空气中,表现为浓度的降低,而蚁群则趋向于向信息素浓度高的方向行动.当系统开始工作时,首先需要设置各个边上的信息素量,在此基础上通过比较判断是否符合最短路径的要求,如果不满足随机分配变电站内工作点,并以此开始遍历计数,如果计数次数小于工作点数目,则根据启发式信息和信息素浓度信息开始访问下一工作点,直到遍历所有工作点为止,最终选择所有完整路径中最短路径作为路径的最优解,从而实现最优路径的选择.

1.2 ACO算法参数分析

1.2.1 概率转移函数

ACO算法的概率转移函数计算式为:

(1)

式中:τij为信息素残留量;ηij为启发式因子;α为信息素重要程度;β为启发式因子重要程度.

信息素重要程度α值越大,信息素高浓度对个体的吸引力越大,个体越趋向于该条路线,搜索路径的随机性越弱,系统陷入局部最优解的可能性越大.启发式因子重要程度β表示个体对于局部最优解的趋向性,β越大选择局部最短路径可能性越大,可以有效地降低系统的收敛速度,但易陷入局部最优解的困境.为了避免上述情况,通常会根据经验要求α、β∈[0,5].

1.2.2 启发式因子与信息素浓度

为了高效区分个体自身对于路径的选择,定义路径距离的倒数为选择该路径的概率:

ηij=1/dij

(2)

通常ηij为一个介于0和1之间的小数.当群体完成了一次完整的迭代后,各个位置上的信息素浓度计算式为:

τij(t+n)=(1-ρ)τij(t)+Δτij

(3)

2 路径规划地图建模

变电站地图建模是路径规划的基础,首先对实际环境栅格化,选择合适的比例尺,要求能够比较合理地得到障碍物与机器人之间的大小相对关系;然后人为设定禁行区域,该区域包含无法通过的障碍物区域、可能发生碰撞的区域和保证电力设备运行安全的安全区域,同时应考虑到变电站环境处于动态环境下的复杂情况;最后比对上述禁行区域和栅格化处理的最小单位,根据碰撞概率确定处理结果,得到如图1所示的变电站二维点阵图.

图1 变电站二维点阵图

3 仿真试验与现场测试

3.1 不同算法路径规划比较分析

采用规格为20×20的二维栅格障碍图,仿真比较A*算法和ACO算法.采用A*算法而不是Dijkstra算法是因为Dijkstra算法需要遍历所有栅格,虽然相对来说更稳定可靠,但是每次增加一个新的节点都要进行大量计算,对于其中大部分偏远节点来说,无疑是冗余的算力和大量的计算时间.仿真试验采用路径优先原则,对平滑程度要求不高.图2为A*算法和ACO算法在简单环境下分别拟合出的路径情况,两者路线规划相似,且距离相同,A*算法耗时约10 s,ACO算法耗时约8 s.

(a) A*算法

在如图3所示的复杂环境下,当起点和终点之间的路径需要进行大量迂回才能到达时,A*算法和ACO算法都能搜索到相同最短路径,但A*算法耗时约168 s,ACO算法耗时约9 s.

(a) A*算法

为了更好地探索算法路径规划效果,对A*算法在简单和复杂环境下的搜索深度进行比较(见图4).由图4(a)可见,对简单环境的起点和终点距离进行路径拟合时,A*算法获取结果较快、搜索范围相对较少;由图4(b)可见,在路径需要偏转一个稍大角度进行迂回时的复杂环境下,随着搜索栅格数目的增多,每次增加的栅格都需要与上一次探索的所有节点进行一次更新,而搜索时没有一个终点作为参考,数据的更新相对来说比较盲目,再次增加了运算量,最终搜索速度越来越慢.如果扩大地图范围,会由于同样的原因造成整体搜索进度缓慢.

(a) 简单环境

ACO算法中个体的初始位置虽然是随机的,但是可以根据地图规模适当调整种群数量,覆盖地图获取更多信息的可能性也越大;ACO算法采取分布式控制方法,对运算要求不高,即使种群数量增长较多,但总时长并没有增加太多;ACO算法获取信息后决策形成最终路径的速度也比较快.综上所述,ACO算法在应对动态复杂环境时比A*算法表现更为优异.

3.2 ACO算法参数对检修机器人路径规划的影响分析

为了增加路径搜索难度,采用图3的复杂环境以更好地模拟变电站实际环境,在控制单一变量的条件下进行仿真试验.

3.2.1 种群规模的影响

以10次完整的路径规划为一个样本容量,研究种群数量对于最优路径规划的影响,结果如表1和图5所示.

表1 种群数量N对路径迭代的影响

图5 种群数量N对路径迭代的影响

由表1和图5可见:N=25时,由于收敛速度过慢,最短路径误差为5%;随着种群数量的增加,获得可接受较优路径所耗费的迭代次数逐渐减少.种群数量越大,对应的覆盖规划区域面积也相对更广,迭代出更优路径的速度也更快.种群数量大意味着离群者的基数越大,当有离群者偏离航道,就有更多寻找潜在最优解的可能性.当N超过一定范围后,对于提高寻找较优解效率的影响就比较小.另外,在N增加的过程中,每次迭代种群数量激增,会造成额外的算力消耗,经过迭代后会使用大量资源,所以通过不断增加种群数量以达到最优路径的目的不可取,需要寻找适合于变电站路径规划规模的种群数量.根据种群数量-平均迭代次数的迭代曲线,选取拐点所对应的种群数量作为算法最优参数,本文选取N=200.

3.2.2 信息素和启发因子的影响

对照组路径规划效果和收敛曲线如图6所示.

(a) 路径规划效果

当调整α时,静态障碍物路径规划和路线距离没有发生明显变化,规划路径长度随时间的变化如图7所示.由图7可见:随着α的增加,路线的路径长度趋于稳定,最终的实际规划距离和实际最优解的结果相差不大,在可接受范围内;α的增大提升了信息素在概率转移中的权重,加快了机器人路径搜索收敛速度,达到一个相对最短路径速度也就越快;α并不是越大越好,在α较大时整个路径虽然趋于收敛,但是和实际最短距离仍有差别,而且这个差别随着α的增大而增大,逐渐偏离目标;反观α=1时,虽然前期收敛速度较慢,但中后期保证了较好的收敛速率,最终获得一个目前最优路线.这里推测为:虽然增加离群者路径的采纳概率,但是离群者中更优策略毕竟是少数,种群有被误导的可能性;另外,由于是指数权重,会占用大量的计算资源,造成用时过长等问题,所以α也不宜过大.

图7 信息素重要程度α对规划路径长度的影响

如图8所示,随着启发因子重要程度β增加,迭代曲线收敛明显.β直接体现了群体对于最短路径的趋向性,β的增加可以有效提高路径规划效率,但存在算力占用问题,所以β设定值也不宜过大.

图8 启发因子重要程度β对规划路径长度的影响

综上所述,信息素重要程度α与路径收敛呈反相关,而启发因子重要程度β与路径收敛呈正相关,两个参数共同影响变电站运载机器人路径规划的收敛速度,但是两者都存在边缘效应,当到达一定范围后需要投入更多的资源,与收益增量不成比例.通过多轮试验,结合实际情况,确定α=1、β=7作为一个比较折中的参数,既能保证一定的收敛速度又不至于占用过多资源.

3.2.3 信息素蒸发系数ρ的影响

ρ为信息素自然蒸发下的残留量,在一定程度上决定了群体决策过程中采纳现有规划的趋向性.分别采用5组信息素蒸发系数进行比较,结果如图9所示.

图9 信息素蒸发系数ρ对规划路径长度的影响

由图9可见:当ρ较小时,路径距离有明显的收敛趋势,且随着ρ的增大收敛趋势加强;当ρ超过某一限定值时,随着迭代次数的增加,路径逐渐固定,不再出现距离减小趋势,甚至当ρ到达0.9时,终值和理想最优路径相差较远.由式(3)可知:ρ越小,信息素残留越多,在同重要程度因子的限制下,路径决策会倾向于既往路径,残留信息素过多导致大量资源耗费在无效路径的搜索上,会极大程度地影响算法的收敛速率;而ρ越大,残留信息素越少,虽然可以减少无效路径的搜索,但是对应的信息素能起到的作用会很小,有效路径的搜索也可能被摒弃,最终形成的路线趋向于快速稳定而并非最短路径.信息素蒸发系数最好控制在一定范围内,在保证收敛速度的同时,还要兼顾终值误差,防止出现负优化的情况.因此,在面对复杂的变电站环境时,ACO算法能够针对变电站运载机器人路径规划工作进行最优路径搜索,满足不同任务的需求,且能根据环境要求适当调节各项重要参数以符合不同特点的实际环境,完成资源的最优配置,可保证搜索性能优于其他算法.

由仿真试验结果可知,将地图栅格单位长度定为1 m,在改变机器人体型时,仿真结果没有多大改变;将地图栅格单位长度定为1.5、2.0 m时,算法搜索速度明显加快.由此可知,影响算法搜索速度的因素为地图建模时栅格单位长度,而栅格宽度代表实际环境中道路宽度.因此,结合实际环境,对ACO算法进行合理的参数设置,能够加快算法搜索的时间、提高搜索效率,进一步提高运载机器人的运载水平和智能性.

3.3 现场测试

为验证本文提出机器人路径规划方法的可行性和工程实用性,通过系统集成开发了变电站运载机器人物理样机系统,并在国网湖南省电力有限公司所辖的变电站区域内进行现场应用.图10(a)为机器人在工区充电桩上充电;图10(b)为机器人搭载重物;图10(c)为操控人员通过人机交互系统设置目标点;图10(d)为机器人根据集成的路径规划控制算法在变电站自主运行.人工设置变电站内01#充电桩为起始点,08#变压器为终止点进行检修工具运输,起始点至终止点直线距离为324 m,取仿真试验中的最优算法参数,通过A*算法和ACO算法进行路径规划对比测试,结果如表2所示.由表2可见,整个运载过程中两种算法机器人能够实现在变电站内无碰避障、选取最优路径将所载工具准确运送至目标点,但ACO算法规划路径和耗时较短,说明基于ACO算法的机器人自主路径规划具有较强的工程实用性.

表2 两种算法现场测试试验性能对比

(a) 起始点充电

4 结语

针对变电站运载机器人的作业需求,本文提出一种基于ACO算法的变电站运载机器人最优路径规划方法.该算法能够针对变电站运载机器人运载任务所需要的路径规划需求进行最优路径搜索.通过建立机器人在变电站内的运载运动地图,对ACO算法的优化性能进行了仿真试验.变电站运载机器人在现场进行运行测试,与A*算法相比,ACO算法收敛速度更快、规划路径更短,更好地满足了机器人在变电站内进行检修工具自主运输的需求,进一步提升了运载机器人的智能化和实用性水平.