微型机器人环境感知与路径规划关键技术

微型机器人环境感知与路径规划关键技术

翁志能,程秀芹,王新宇 ,郭强,寇海军

北方自动控制技术研究所 山西太原 030006

摘要：机器人不仅可以在高危环境中帮助人们完成难度较髙的工作，而且还可最大程度提高工作效率。特别是物联网环境下机器人自主操作能力较强，可以减少事故发生，然而机器人在给人们带来便利的同时也存在着些许不足。在工作过程中机器人对路径的感知能力较差,往往对障碍物不能进行精准的躲避，因此需要对路径进行重复规划。如何在物联网环境下提高机器人对运行路径的感知，使其规划出最优的路径是该领域中最具应用价值的研究方向。

关键词：物联网；机器人;路径规划；测地线

前言:全局路径规划技术是移动机器人自主导航的关键技术之一，是机器人在路径规划领域的一项重点研究课题。通过对算法进行优化改进以提高移动机器人对环境信息获取的准确度、路径平滑性、减少冗余点和迭代次数便成为移动机器人全局路径规划算法的重点研究对象。

1. 完备性规划算法

完备性规划算法是指在起始点和目标点之间有路径解的存在，则一定可以得到路径解；若得不到路径解，则说明该路径不存在。现阶段，以基于图搜索为主的完备性规划算法主要有：Dijkstra算法、A*算法；以基于启发式为主的完备性规划算法主要有：遗传算法、蚁群算法。

1.1Dijkstra算法

Dijkstra是利用广度优先搜索算法有效解决有向图最短路径的全局路径规划算法。该算法设移动机器人所在的点为初始节点，遍历剩余节点，将与初始节点距离最近的节点加入结点集合，该集合从初始节点向外层层扩散，直至遍历图中所有节点，并根据路径权重的大小找到一条初始节点到目标节点的最短路径。当前国内外研究学者重点研究Dijkstra算法的模型优化和减少遍历节点数目。潘成浩等针对传统Dijkstra算法难以在障碍密集型的复杂空内搜索到最短路径的问题，提出松弛Dijkstra算法。栅格化作业环境，将整体环境离散化为单元环境，提高对地图的建模效率。仿真结果显示，与采用堆序列实现的Dijkstra算法搜索速度对比，验证了松弛Dijkstra算法的优越性。

1.2A*算法

A*算法是在Dijkstra算法基础上进行改进和优化后得到的一种启发式搜索算法，设初始节点为父节点，根据启发式函数搜索得到当前代价最低的节点作为子节点，直至搜索到目标节点，最终规划获得一条代价最小的路径，具有搜索速度快和较强的环境适应力。王红卫等针对在栅格模型下现有A*算法规划得到不平滑路径的局限，提出前后节点之间无障碍物即相接，从而构建平滑A*模型的方法。仿真结果表明，改进后的算法在规划的路径长度较原算法降低约5%，折线数量减少约50%，累计转角度数减少30%～60%。

1.3遗传算法

遗传算法是一种模拟自然界物种进化和遗传机制的计算模型，该算法参考达尔文的“物种进化论”和孟德尔的“生物遗传学”，对自然选择和遗传因子进行交叉、变异等遗传现象进行仿真，模拟生物朝着最优的方向发展进而寻找最优解的算法，其本质是一种基于基因遗传学原理的全局搜索优化算法。因其自身最大的优点是能在搜索过程中自适应迭代优化得到路径最优解，因而它与其他算法相融合成为目前人工智能科学领域的重要研究对象，并且广泛应用于单一移动机器人的路径规划研究领域。段俊花等针对GA算法存在难以解决大规模计算量而陷入“早熟”和因缺乏信息反馈而导致搜索速度慢等缺陷，常利用混合型的GA算法。GA算法结合图搜索算法，这样即减少了搜索的盲目性，又能优化原单一算法，实验结果表明，图搜索算法能有效删除冗余算子，二者相结合的算法较原GA算法在求解最优路径的次数上从363次增加到492次，寻优概率从72.6%提升至98.4%。

1.4蚁群算法

蚁群算法最初是从蚂蚁觅食行为中获取灵感进而设计的一种启发式仿生智能优化算法。蚂蚁在觅食道路上释放信息素，随着时间的推移，信息素浓度与路径长度成反比，蚂蚁对信息素具有感知能力，后来的蚂蚁以信息素浓度大小作为判断依据，引导自身运动并找寻到最优觅食路径。此过程具有正反馈调节机制，因此该算法能够快速搜索到最短路径。封声飞等针对蚁群算法发挥正反馈机制时间长、易陷入局部最优等问题提出一种自适应蚁群算法。该算法在蚁群算法的基础上调整初始化信息素，引入转角约束以限制算法随机性，并对路径尖峰进行平滑处理。实验结果证明，改进后的算法迭代次数降低至原来的1/4到1/3，规划得到的路径更加平滑，保证了移动机器人运动的平衡性。

1.5粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是由Kennedy和Eberhart在1995年提出。粒子群算法通过不断搜索当前的最优值，通过迭代不断更新粒子的速度和位置，类似于鸟类觅食的过程。通过个体与群体成员的适当交流，整个鸟群都能达到最终的食物源。该算法是通过模拟鸟群，单个鸟与鸟群之间的信息共享，通过计算分析优化，求出最优解。其基本原理是个体与群体协作和信息共享，从而获得最优解。它是一个以当前搜索到的最优值不断更新迭代来寻找全局最优值的算法。粒子群算法是概率型的全局路径规划算法，因为在迭代的过程中充满更多的可能性。PSO通过让单个粒子在路径规划空间里找出此粒子的最优解，再将个体最优解共享给粒子群的其他粒子，找出个体中最优解作为全局最优解，因此整个粒子群在搜索的过程中覆盖的范围更大，更容易找到全局最优解。针对粒子群算法生成因需要达到全局最优而造成的路径折线较多的和k-means算法易受初始中心影响等问题。Song提出通过加入自适应阶段速度，来减缓机器人路径的折线，优化路径平滑度，同时也提高了搜索空间的能力。汤深伟等提出了基于改进粒子群算法的k-means聚类算法，孟庆宽等通过粒子群算法计算得到最优加权因子，进而调整控制规则实现导航车辆的自适应控制。针对于标准PSO算法在一些基准函数上改进，PSO算法能快速收敛但是容易陷入局部最优的问题。王东风等基于粒子间适应值的差异，提出对粒子位置高斯采样均值的自适应调整策略，减缓粒子在中心的聚集趋势。Ma等提出将双重仓库下机器人最短路径问题转变为时变非线性规划问题来降低难度。Ajeil等针对静态环境下寻优的问题，通过与GA算法、PSO算法比较，提出通过设置蚁群不同的个体的寿命的优化算法，实验结果表明，在路径规划长度的减少有显著的效果。

2. 快速扩展随机树

快速扩展随机树（Rapidly-exploring Random Trees，RRT）是通过随机构建空间树来实现快速搜索的一种算法。基本思想是在已知地图上，通过给定的起始位置和目标位置的规划任务，在起始位置通过抽样随机构建随机无向图，类似于树形结构，在无障碍区域不断延伸树形结构。一般来讲，路径规划算法都是不断的朝着目标位置延伸，但是由于障碍物的存在，如果不断的指向目标位置，会有和障碍物相撞的风险。为解决上述问题，RRT算法主要通过随机采样的方法，选择延伸方向时，会设置一定的概率朝着目标位置生长，也有一定的概率随机在全局地图任意方向延伸。扩展树延伸分支选择距离采样点位置近的树节点，并且建立延伸的树节点是否撞到障碍物；采样点距离扩展树的距离要达到设定的阈值，通过两个约束防止发生碰撞和延伸的树节点重复。对于RRT算法对前期的的扩展比较敏感，全局最优解由于扩展树的结构，导致收敛速度慢的问题。基于此，NPérezHigueras等通过将强化学习的思想运用到RRT算法上，提出了一种改进型算法，改进初期的代价函数，使其在前期能够快速的找到较优扩展方向，从而加快收敛速度。

3.结束语：

综上所述，目前，大部分路径算法已广泛应用移动机器人的路径规划算法中，但当面临现实多变的场景下，移动机器人的路径规划仍然难以满足复杂环境中要求。因此移动机器人在路径效率、路线的优化等问题上需要提高。

参考文献：

[1]汤深伟,贾瑞玉.基于改进粒子群算法的k均值聚类算法[J].计算机工程与应用,2019,55(18):140-145.

[2]孟庆宽,仇瑞承,张漫,等.基于改进粒子群优化模糊控制的农业车辆导航系统[J].农业机械学报,2015,46(3):29-36.

[3]王东风,孟丽,赵文杰.基于自适应搜索中心的骨干粒子群算法[J].计算机学报,2016,39(12):2652-2667.

[4]朱冰,韩嘉懿,赵健,等.基于安全场改进RRT~*算法的智能汽车路径规划方法[J].汽车工程,2020,42(9):1145-1150.