1、工业控制计算机2023年第36卷第1期基于改进 RRT*算法的深海采矿车局部路径规划算法郭玲玲樊蓓蓓（上海大学机电工程与自动化学院，上海200444）路径规划技术贯穿着整个深海采矿车自主行走任务的始终，也是保障深海采矿车能够安全完成采矿作业的重要基础技术，对于深海采矿车高效完成采矿作业，降低能耗以及安全行驶都具有重要的实际意义1。依靠现有的探测技术，研究人员还无法得到海底的全部地形信息，已经获得的环境信息存在着不同程度的不确定性，这种不确定性必然导致所建立的环境模型的不确定性，进而导致深海采矿车陷入不可通行区域而损害其性能，或造成其他更严重的影响。为了保障深海采矿车行驶的安全，深海采矿车需要具
2、备一定的动态避障能力，而局部路径规划算法可以实现深海采矿车的动态避障。快速搜索随机树（Rapidly-exploring Random Tree，RRT）算法2常用于全局路径规划，因其采用随机采样，不需要对规划空间进行预处理，具有良好的实时性，在局部路径规划中也具有较高的应用价值。但RRT算法生成的路径具有一定的随机性，而且路径并非最优。要想求得最优路径需要经过不断地迭代，会存在节点利用率低和计算量偏大等问题。针对路径的随机性以及生成路径并非最优的问题，文献3提出通过渐进优化达到最优路径的RRT*算法。针对RRT*算法后期路径收敛速度缓慢，计算量偏大的问题；文献4提出informed RRT*
3、算法，通过限制采样范围来提升算法的收敛性；文献5提出的改进双向RRT算法，有效地改善了RRT算法随机性过强，规划的路径过于曲折的问题；文献6-7采用贪婪算法对规划后的路径进行平滑处理，减少了拐点对路径的影响，使路径更平滑。在深海环境中，规划路径的安全性是路径质量的关键评估因素之一。上述改进的RRT算法并未考虑路径的安全性能并不适用于规划深海采矿车的行驶路径。为了保障深海采矿车行驶的安全性，本文提出了一种改进RRT*算法。该算法对采样节点进行通行性分析，将通行性值引入到新的采样策略里，改善RRT*算法目标导向性差的问题。随后对路径进行剪枝优化，使改进RRT*算法规划出的路径能够适用于深海采矿车行
4、驶。1RRT*算法概述RRT算法的基本原理是将状态空间中的起点作为随机树的根节点，采用随机采样策略进行节点扩展，生成一棵随机扩展树。当随机扩展树上的采样点抵达目标点或进入目标范围内，回溯该采样点到根节点的全部路径点得到一条可行路径8。RRT*算法则在RRT算法的基础上加入了重选父节点和重新布置随机树两个核心步骤，通过渐进优化生成最优路径9。具体的算法流程如下：1）初始化随机搜索树，将xstart作为随机搜索树的根节点；2）在状态空间内随机采样得到一个采样点xrand；3）遍历整个随机树T的节点，找到距离xrand最近的节点xnear；4）在节点xnear沿xrand的方向上拓展一个值为step
5、size的步长，得到新节点xnew，如果xrand距离xnear的值小于步长，则xrand为新节点xnew；5）以节点xnew为圆心，遍历整个随机搜索树，筛选出与节点xnew的距离小于半径r的所有节点X，计算集合X中所有节点与xnew连接的权值大小，找到权值最小的节点xmin，将此节点作为xnew的父节点，删除与原父节点xnear的连接；6）在节点xnew和其父节点xmin的连线之间进行碰撞检测，判断是否存在障碍物，若存在障碍物，则删除节点xnew跳到步骤2）重新进行采样，不存在障碍物就将xnew加入到随机搜索树；7）随后，优化集合X中节点的权值，若存在节点的权值大于以xnew为父节点到该节点
6、的权值，则删除该节点与原父节点的连接，选xnew作为其父节点；8）迭代重复，直到找到目标点xgoal或距离xgoal很近的节点，则停止生长，得到生成的搜索树。由RRT*算法的流程可知，算法能快速寻找出一条可行路径，再通过不断地优化节点的权值实现路径渐进优化的效果。但随着随机树节点的增加，算法的内存消耗、计算量以及计算时间会呈指数上升。因此，算法收敛到最优路径需要一定的计算时间，影响深海采矿车路径规划的实时性效果。Local Path Planning Algorithm for Deep-sea Mining VehicleBased on Improved RRT*Algorithm摘要：针
7、对海底环境可能会出现未知障碍物，进而影响采矿车行驶安全的问题，提出一种改进RRT*算法。该算法考虑海底地形的复杂性，对采样点进行通行性分析。同时在采样策略上，进行目标导向性的改进，并对生成的路径进行剪枝优化。实验证明提出的算法保留了RRT*算法的概率完备性，同时在安全性能和路径长度上提高了生成路径的质量。关键词：深海采矿车；局部路径规划；改进RRT*算法Abstract:An enhanced RRT*algorithm is proposed in this paper to address the problem of unknown obstacles ap-pearing in the
8、 seabed environment,which affects the travel safety of the mining vehicle.The method takes into account thetopography of the seafloor and performs a traversability analysis on the sampling nodes.In addition,the goal-orientednessof the sampling strategy is improved,and the resulting path is trimmed a
9、nd optimized.It is experimentally demonstratedthat the proposed algorithm retains the probabilistic completeness of the RRT*algorithm while improving the quality of thegenerated paths in terms of safety performance and path length.Keywords:deep-sea mining vehicle,local path planning algorithm,improv
10、ed RRT*algorithm97基于改进RRT*算法的深海采矿车局部路径规划算法2改进的RRT*算法2.1可通行性值的计算考虑到规划路径的安全性能，本文对采样点的可通行性值进行计算。首先栅格化当前地形，根据各个栅格内存储的高度值提取出栅格的坡度信息、高度信息和粗糙度信息等地形信息。随后根据采矿车的机械性能和自身越障能力，设定深海采矿车的最大爬坡角度为max，可跨越的最大高程差为Hmax，可通行的最大地面粗糙度Rmax。若区域内对应的地形信息大于最大爬坡角度为max，可跨越的最大高程差为Hmax，可通行的最大地面粗糙度Rmax其中之一，将该区域认定为障碍物区域，可通行性值设置为1。对非障碍物
11、区域的坡度信息、高度信息和粗糙度信息进行归一化，得到的数值为该区域内的可通行性值，采用的计算公式如下：T=1n+2Hn+3Rn（1）其中，1、2、3非负且满足a1+a2+a3=1，通行性值T的值区间是0，1，值越大表示深海采矿车通行的难度越大。根据可通行性值可将海底地形分为平坦区域、易通行区域、难通行区域、不可通行区域。2.2改进的采样方式为了进一步减少随机性带来的收敛速度慢的问题，不少学者采用目标导向的方案，该方法能使随机树偏向目标生长，加快RRT*算法的收敛速度，也增加了路径规划失败的可能性。当障碍物靠近目标点时，碰撞检测失败的可能性较大，可能搜索不到靠近目标点的路径，影响算法的概率完备性
12、。为保留了RRT*算法的概率完备性，本文设计了一种改进的采样策略。在RRT*算法筛选采样点并取得新节点xnew这步骤时，对xnew到目标节点xgoal的行走代价进行计算得到代价值cost(xnew，xgoal)，并继续评估xnew的父节点xmin到目标节点xgoal的代价值cost(xmin，xgoal)，如果满足cost(xnew，xgoal)cost(xmin，xgoal)这个条件，执行后续步骤；否则，返回步骤2）重新进行采样。基于海底场景的复杂性，代价值cost的计算将高度坐标考虑进去；此外，考虑到地形的粗糙度、坡度等地形信息的影响，将可通行性值按一定的权重加入到代价值计算公式中，平坦区
13、域、易通行区域、难通行区域、不可通行区域的代价值计算系数分别为1、2、3、+。最终得到的代价值计算公式如式（2）所示：H（n）=k（xm-xn）2+（ym-yn）2+（zm-zn）2（2）式中，（xm，ym，zm）为目标点xgoal的坐标，（xn，yn，zn）为需要计算代价值的节点坐标，k为代价值系数，k1，2，3，+。通过以上的采样策略，既保留了RRT*算法的概率完备性，选出的节点，也具有靠近目标点的趋势。当采样点足够多的时候，能够生成一条较优的初始路径。当采样节点一定时，该改进的采样策略能够加快RRT*的收敛速度，但是路径长度相差不大，说明路径还存在一定的绕远现象。2.3剪枝优化路径存在的
14、绕远现象影响了路径的质量，为了兼顾RRT*算法实时性要求和路径的高质量要求，在RRT*算法未收敛至路径最优之前，对规划的路径进行剪枝处理提高路径规划的质量。如图1是路径简化示意图，图中黑色路径为RRT*算法生成的路径，该路径上有很多的拐点，存在小范围内的曲折现象，路径不连续，采矿车行驶该路径时转弯次数较多会产生较大的能源消耗。浅色虚线路径是经过剪枝优化后的路径，路径的转折次数减少，路径长度也相应缩短，可见浅色虚线路径更符合深海采矿车的行驶需求。剪枝处理的算法思想是遍历整个路径的路径点，以起点x0为根节点，判断起点和其后续节点x1的下一节点x2是否存在障碍物，若不存在障碍物，则将x2的父节点改为
15、起点，删除节点x1。继续判断后续节点x3与起点的通行性，检测到障碍物，则保留节点x2，并以节点x2作为当前节点，继续判断其后续节点的通行性，循环以上步骤直至找到目标点。3仿真实验及结果分析为了验证改进RRT*算法的有效性和可行性，对改进RRT*算法的避障效果进行仿真验证。实验环境选择的是海底数据绘制成的海底地图，取其栅格地图尺寸为200200的部分地形。计算机的配置是Windows10，处理器为Core i5-1135G7，运行内存为16 GB。在该仿真实验中，仿真区域选取的是X=300，500，Y=0，200范围内的地形信息，分别设置起始点坐标为480，70，8，目标点坐标为300，179，
16、16，RRT*算法的步长stepsize为5，采样点数量为2000。为了清晰地展示改进RRT*算法的可行性，分别对初始RRT*算法、改进RRT*算法1（引入了目标导向）、改进RRT*算法2（引入了目标导向、通行性值）进行对比仿真实验。为了验证剪枝优化的有效性，最终进行一个剪枝优化前后的对比实验。如图2所示是传统RRT*算法的采样结果，采样点在整个探测范围内随机采样，对于一些较难通行区域也生成了可通行的路径，最终生成的路径可能会极大地增加采矿车工作时的能源消耗，不能保障采矿车的安全性能。同时，由于无目标地随机采样，在采样点数量较小的情况下，存在的偏离目标点的采样点也增大了RRT*算法规划路径失败的可能性。图3所示为改进RRT*算法1的采样结果，该算法改进了采样策略但是代价值计算中未引入通行性值的权重。对比图2的曲线包含区域可知，改进了采样策略的RRT*算法有效地规避了一些远离目标点的节点采样，提升了算法的节点利用率。图2RRT*算法（Samples=2000）图4为改进RRT*算法2的采样结果，该算法改进了采样策略同时引入了通行性值的权重。对比图3的椭圆区域可知，RRT*改进算法1虽然提
