英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

基于改进PRM的狭窄通道的路径规划

摘要

针对通道狭窄情况下概率路标图（PRM）的缺点，提出了一种基于最佳采样策略的改进方法。通过对障碍物的密集区域进行采样，选择分布在障碍物内部的采样点，并按一定的距离均匀采样，从而在自由区域内的障碍物周围生成采样点，从而增加了狭窄区域中采样点的数量。仿真结果表明，改进的PRM在狭窄通道中比标准PRM具有更多的采样点。路径规划的时间，成功率和路径长度也得到了显着改善。

关键词：路径规划，PRM，采样策略，狭窄通道

1. 引言

在自主移动机器人的研究中，路径规划作为核心部分，研究人员已经对其进行了广泛的研究。路径规划是指按照一定的特征（时间，距离）连接起点和终点的路径，以使路径和障碍物保持相对安全的距离，同时确保路径长度和规划时间为尽可能短[1]。因此，各种路径规划方法，例如人工势场，概率路线图（PRM），快速探索随机树（RRT），蚁群优化（ACO），人工势场（APF）和遗传算法（GA）[2-7] 。但是，大多数算法（例如APF，ACO和GA）都需要对环境图进行准确建模，并且大多数障碍必须是规则图形。在实践中，环境通常很复杂，并且障碍物形状不确定性因素过高，因此该模型比较困难且计算量大，难以应用。但是，PRM基于随机采样，并且具有概率完整性。它们擅长处理高不确定性和高维地图，因此已在实践中得到广泛使用。

PRM随机采样自由空间，并连接采样样本点构建路径图。但是，由于PRM采样策略的概率属性，图中每个区域的采样概率是相同的。因此，当采样点数恒定时，自由区域的面积越大，采样点越多。但是，很难确保在地图的狭窄通道区域中有足够的多个采样点。因此，实时识别窄通道并有效改善采样点非常重要。

通过建立障碍物地图的概率模型并分析和预测模型来检测障碍物和狭窄通道，可以有效地增加这些区域中的采样点数量。参考文献[8]提出了动态环境中路径规划者的狭窄通道预测模型（NPP）。预测模型是通过著名的支持向量机（SVM）分类方法获得的，其中考虑了地图环境障碍物的实时变化，在建立模型时引入了时间因素和空间信息。所获得的地图概率模型可用于检测狭窄通道的位置，从而增加了狭窄通道中的采样点数量。参考文献[9]提出了一种长短期记忆（LSTM）模型，通过预测障碍物的位置，将障碍物的轨迹划分为时间序列，并将下一次的位置估计值纳入规划算法的状态有效性测试中。生成最佳路径。障碍物模型的预测可以减少遍历和重新编程的时间，并且通过优化采样阶段还可以增加窄通道中的采样点数量。针对这种情况，Boor提出了高斯采样方法[10]，高斯采样基于障碍物的密度，这使得障碍物的采样点密集，从而形成了合理的路径图。Hsu提出了一种桥梁测试方法，该方法从障碍物中随机提取两个点并连接两个点[11]。如果两个点的中点在自由区域中，则将提取该点。该点是在狭窄通道中获取的，这大大增加了狭窄通道中的采样点数量。但是，高斯采样和桥梁测试方法都适用于存在障碍物的区域，如果远离障碍物甚至没有规划路径，规划效率就会大大降低。参考文献[12]提出了一种自适应采样方法，该方法将概率似然函数和高斯采样相结合，大大增加了落在狭窄空间中的采样点，从而提高了PRM在实际不确定环境中的使用。但是，它并不专注于对狭窄通道的路径规划的深入研究。提出了一种改进的PRM，在学习阶段引入了一种人工势场方法，以使障碍物内的点由于障碍物的排斥力而从障碍物移动到自由空间，从而增加了狭窄通道中的采样点[13]。但是在实际使用中很难确定势场力的值，并且不同势场力的结果也有很大差异。混合路径规划提出了基于谐波函数（HF）和概率路线图（PRM）的技术[14]，该方法使用流体动力学来建立概率路线图，并使用流体动力学（FD）来识别狭窄的通道，从而增加狭窄通道的连通性。在存在狭窄通道的环境中，该方法要比每个个体都要好，但要找到一条无碰撞的路径，但这会大大增加算法的复杂性。在找到可行的路径后，狭窄通道中的规划结果通常不平滑，因此需要优化路径。参考文献[15]提出了一种基于五次Pythagorean-Hodograph（PH）曲线的时间最优轨迹规划方法，该方法不仅可用于机器人运动控制，而且可用于路径规划，以使机器人的路径更加平滑。

本文对PRM进行了改进，以解决狭窄通道中采样点的缺点。改进了PRM的采样策略。首先，对自由区域进行采样并获取一定数量的采样点。其次，基于障碍物采样，该方法的主要思想是在障碍物中获取一个点，然后在采样点的一定范围d内再次进行均匀采样。如果采样在自由区域中，则保留该点，反之亦然。最后，在障碍物周围生成采样点，并且局部地图中有足够的采样点来规划合理的路径。本文分为四个部分。第一部分介绍PRM的基本原理和不足。第二部分介绍了基于优化采样策略的改进PRM的原理和步骤。在第三部分中，对改进的PRM进行了仿真，并与其他算法进行了比较，并对结果进行了分析。第四部分总结了改进算法。

2.概率路标图法

2.1 PRM算法的基本原理

PRM的基本思想是使用概率图表示移动机器人所处环境的自由空间，然后通过构建路线网络图来找到最佳路径。该算法可以分两个阶段完成，即预处理阶段和查询阶段。PRM路径规划的主要步骤如下：

1. 预处理阶段：使用自由空间中的均匀分布对环境图进行均匀采样，以构建采样点图。然后连接各个点以构建路径网络图。如图1所示。预处理阶段可以分为两个阶段：

(1) 在图中进行采样，如果采样点在自由区域中，则采用该点，否则丢弃该点，最后构建采样图。

(2) 建立无向路径网络图R=（N,E），其中N表示点的随机数（点集），E表示所有可能的两个点之间的路径。

2.查询阶段：查询从起点到终点的路径，如图2所示。在查询阶段，使用无向路径网络图 R=（N,E），只需根据设定的起点(s)和目标点(g)在无向路径网络映射中选择适当的路径。在查询阶段使用A*启发式算法，以确保在网络图中找到合理的路径。

2.2 PRM算法的缺陷

PRM的采样点数量和采样点位置可以确定整个路径图的构造以及在查询阶段中最终路径的计划。在预处理阶段，PRM通常使用均匀采样，以确保全局地图的每个自由空间都具有采样点，并且可以最大可能地规划一条合理的路径。但是，当局部地图中有一条狭窄的路径，并且最佳路径需要经过狭窄的通道时，均匀采样是非常不适用的。在整个地图空间中，采样概率在任何地方都是相等的，并且采样点的数量与空间的大小成正比。与其他区域相比，狭窄通道没有足够的采样点。因此在构建路线图时，狭窄的通道没有最佳路径，因为没有足够的采样点。

在图3中，当在预处理阶段获取50个采样点时，狭窄通道中的采样点太少。因此，在查询阶段，由于狭窄通道中的采样点太少，因此无法构建通过狭窄通道的路线图。因此，无法构建最佳路径。

但是，当采样点足够时，标准PRM可以解决该问题。因为随着总采样点的增加，可以在狭窄的通道中获得足够的采样点，并且可以规划最佳路径。结果如图4所示。

表I中显示了标准PRM的不同采样点数的结果。当采样点数足够时，可以在狭窄通道中规划路径。但是，当采样点过多时，在查询阶段构造路径图和查询路径会花费很多时间，这将大大降低PRM的运行效率。因此，我们需要一种根据狭窄通道进行采样的方法，同时确保PRM的效率。

3.改进的PRM算法

3.1基于优化采样策略的改进方法

标准PRM使用均匀分布进行采样，由于均匀采样的可能性等，地图中空白区域较大的区域具有较高的采样点概率，因此采样点位于狭窄通道中通常很难收集障碍物，但是可以使用位于障碍物区域内或附近的采样点来连接狭窄通道的末端。因此，我希望抓住障碍物附近的那一点。本文将采样方法分为以下两个步骤：1）环境图中的自适应随机采样；2）在障碍物区域采样，在障碍物中选择采样点，在该点的一定范围内进行均匀采样，直到其落到自由区域。具体过程如下：

首先，在地图中使用自适应随机采样。为了克服标准PRM的缺点，在采样阶段的空白区域有大量的采样点，而狭窄的通道区域具有相对较少的采样点。在本文中，障碍物的密度用于自适应采样。在障碍物的密集区域中采集了大量样本，而在较大的空闲区域中则相对分散了采样点。采样点的数量与障碍物的密度成正比。

第二步继续在障碍区域采样，以增加狭窄通道中的点。图5中的采样点位于障碍物中，例如点b，并且围绕该点构造了半径为d的圆形区域，并且在该区域中执行均匀采样。如果获取的点在自由区域中，例如c点，则获取该点。如果它在障碍物之内，例如e点，则丢弃该点并继续采样。这确保了在障碍物区域或狭窄通道中有大量采样点。

3.2 动态采样距离

距离d是根据地图的大小和障碍物的复杂程度动态选择的。当d值较大时，所采样点在很大程度上远离障碍物，影响了规划效率。当d选得太小时，该范围内没有空闲区域的可能性将大大增加，因此需要在障碍物内进行频繁的重新采样，从而增加了算法的运行时间。因此，合理的距离d可以在一定程度上进一步提高改进算法的运算效率。在本文中，D是动态获取的，并且预先设置了最小距离d分。当范围内的点未移至自由区域时，d分将加倍，直到范围内的点位于自由空间中。

改进的PRM在预处理阶段得到了改进，并采用了具有更高灵活性的自适应采样。抽样策略的基本步骤如下：

1. 仿真

为了验证改进算法是否有效并提高窄通道处理能力，本文在Matlab2018a下模拟了改进算法的采样阶段和总体算法规划效率。采样阶段仿真是为了验证通过改进算法是否可以改善狭窄通道中的采样点数量。总体规划效率模拟主要从规划成功率，规划时间和路径长度以及改进算法在这三个方面是否有明显变化方面进行。为了更好地说明改进的算法处理狭窄通道的能力。使用具有大面积自由区域和狭窄通道的地图进行模拟，其中蓝色点表示起点，绿色点表示终点。

4.1改进的PRM采样阶段算法

改进的PRM主要体现在采样策略的改进上。为了在采样阶段验证改进型PRM狭窄通道中采样点的变化，将改进型PRM与标准PRM进行比较，以得出相同的采样点。仿真结果如图6所示。改进后的PRM在障碍物区域的采样点密度高于标准PRM，在狭窄通道中的采样点密度也更高。

为了更好地验证改进算法在窄通道问题中的应用，本文分别在采样点分别为50、150、500的情况下重复了50次实验，并对每个窄通道中的节点数进行计数。比较平均值，最终结果列于表II。

在图6和表II中，改进的PRM在处理狭窄通道时比标准PRM具有更好的适应性和适用性。在采样点数相同的情况下，改进的PRM在狭窄通道中的采样点比标准PRM多，因此PRM可以规划狭窄通道中的路径，并且采样点的数量增加。更多，优势更加明显。根据仿真结果，改进后的PRM可以有效地弥补标准PRM在狭窄通道中的缺点。

4.2改进的PRM路径规划效率分析

改进的PRM可以在采样阶段有效地获取适当的采样点，从而使PRM遇到狭窄通道时具有很强的适应性。本文分析了PRM规划的效率，规划时间和路径长度。分别模拟了标准PRM，桥测试方法和改进的PRM。对于每种方法，采样点为150。仿真运行结果如图所示。图7（a）为标准PRM。根据运行结果，标准PRM在150个采样点的情况下无法规划路径。图7（b）显示了电桥测试方法。桥梁测试方法可以规划路径，因为在狭窄的通道中有大量的采样点。但是，狭窄通道中的采样点太多，大面积的自由区域中的采样点太少，因此规划时间和路径长度不是最佳的。图7（c）显示了改进的PRM。改进的PRM在狭窄通道中还具有足够的采样点以规划路径。从结果图中，改进的PRM可以有效地规划狭窄的地图通道。

为了验证改进算法的效率，算法仿真在图7的窄通道障碍图中进行，每个仿真采样点取为150，并对每种算法进行50次重复实验。仿真实验结果列于表Ⅲ。

从图8和表III可以看出，改进的PRM在处理狭窄通道问题时比其他算法具有更高的实用性。标准PRM的成功率非常低。经过实验比较，改进后的PRM在通道狭窄的地图上获得了成功。该比率具有比其他两种算法更高的成功率。就计

划时间而言，改进的PRM具有比标准PRM和网桥测试方法更快的计划速度，而就计划的路径长度而言，具有改进的PRM有比其他两种算法更短的路径。经过反复实验，改进后的PRM在成功率和路径长度上有了很大的提高，总体规划效率得到了显着提高。

5.结论

为了解决PRM处理狭窄通道的不足，提出了一种改进的PRM。通过优化标准PRM的采样策略，可以增加狭窄通道中的采样点数量。当遇到狭窄通道时，使算法具有更好的适应性。最后，在不同情况下模拟了标准PRM方法，桥测试方法和改进的PRM。仿真结果表明，改进的PRM不仅在狭窄通道中具有较高的成功率，而且比其他方法具有更好的执行时间和路径长度，并且具有有效性和稳定性。

6.致谢

作者要感谢陕西省国际科技合作计划项目。（2019KW-014）和陕西省国际科学技术合作基地项目（2017GHJD-009）的支持以及对项目前期道路规划理论部分的深入研究和分析。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[239240]，资料为PDF文档或Word文档，PDF文档可免费转换为Word