2024.01.15-2024.01.21

移动机器人的路径规划是机器人领域的一个重要问题。路径规划算法的效率直接影响机器人在实际应用中的性能和可用性。传统的路径规划算法在复杂环境下存在一定的局限性，比如在陷阱空间（如迷宫和S型走廊）中，规划效率较低，难以快速找到最优路径。因此，需要一种高效的路径规划算法来克服这些问题。

文章提出了一种基于广义沃罗诺伊图（GVD）的启发式路径规划算法，旨在解决复杂环境下移动机器人路径规划的效率问题。该算法利用GVD特征矩阵来提高路径规划的效率和实时性。通过自动识别环境特征并生成合理的启发式路径，该算法可以指导实时运动规划，并提高路径规划的性能。

文章利用GVD提取环境的特征，并通过特征矩阵来指导路径规划过程，以提高路径规划的效率和准确性。具体来说，算法首先利用GVD对环境进行特征提取，并生成特征图。这个特征图可以保证在自由空间中的任何状态都可以通过连接到特征图的特征节点来避免碰撞。然后，为了消除特征节点之间的冗余，算法提出了特征矩阵的概念来表示特征节点之间的连接关系。根据特征矩阵，可以进行特征节点融合，删除冗余节点，保持每个自由区域至少连接一个特征节点。

该方法的创新和贡献如下：

1）提出了一种基于广义Voronoi图的启发式路径规划算法：该算法通过在给定环境中构建广义Voronoi图，并提取特征节点，生成合理的启发式路径。与其他启发式算法相比，该算法不依赖于特定的环境或参数设置，能够自动识别环境特征并生成合理的启发式路径。

2）引入了特征矩阵来优化特征节点的选择和连接：为了减少特征节点的冗余，提出了特征矩阵来表示特征节点之间的连接，并使用特征节点融合技术删除冗余节点。这样可以进一步提高算法的效率，并保证每个自由空间中的节点都能连接至少一个特征节点。

3）结合RRTs进行实时运动规划：通过使用生成的启发式路径来引导RRTs的采样过程，实现了实时运动规划。启发式路径上的节点作为子目标，提高了样本的采样概率，并在动态环境中实现了高效的运动规划。

4）提出了特征矩阵的应用：特征矩阵不仅用于优化特征节点的选择，还可以用于改进重新规划的效率。这为后续的路径规划和动态环境中的重新规划提供了便利。

（1）问题描述

RRT运动规划器的一般步骤包括节点采样、父节点选择、碰撞检查和节点连接。从自由空间中随机抽取一个节点。然后，选择树上最近的节点作为父节点，如果采样节点与其父节点之间没有障碍，则采样节点演化为一个具有转向功能的新节点，然后连接到父节点。这个过程会重复进行，直到找到一个可行的轨迹。

设和X∈R_n为状态空间。设X_obs为障碍空间，X_free = X \X_obs为无障碍空间。陷阱空间问题是由可行陷阱区域产生的样本的概率引起的，表示为

给定映射的GVD定义为与最近的障碍物具有相同欧氏距离的节点集。换句话说，需要一个GVD节点f来满足以下条件：

设机器人的初始姿态和目标姿态为x_start和x_glob。x_start和x_glob对应的特征节点分别用f_start和f_glob表示。定义启发式规划问题，在GVD特征集中寻找路径τ，表示为

（2） GVD算法

提出了一种基于GVD特征矩阵的二维网格图中移动机器人的有效路径规划策略。采用轻量级度量过滤器从地图的GVD中提取初步特征节点。提出了一种特征矩阵结构来表示和检索特征节点之间的连接。提出了一种减少冗余特征节点的节点融合算法，并为映射提供了一种简洁的表示方法。基于GVD特征矩阵，提出了一种有效的启发式路径规划算法，以进一步指导运动规划。所提出的特征矩阵结构可以促进特征融合和启发式路径规划过程。

A. 特征提取

图1 GVD的初步特征提取

如图1所示，A和B是与GVD节点f_n距离r相同的障碍物上的两个点。将f_n的特征区域定义为一个以f_n为中心，半径为r的圆。清晰可见，特征区域内的每个网格都可以无碰撞的连接到GVD节点。因。但是，也可以发现f_n的特征区域与其周围GVD节点的特征区域有很多重叠，图中深紫色所示这种可行区域的表示仍然有许多冗余性。首先利用一个度量过滤器将一个特征区域内的GVD节点聚类到一个特征节点中，随后将移除节点的特征区域连接到特征节点。经过度量滤波后，原来属于f_2的橙色区域将连接到f_1。只要f_2在f_1的特征区域内，很明显，f_2的特征区域内的所有网格都可以连接到f_1，而没有任何碰撞。因此，可以使用f_1来表示其特征区域内的所有GVD节点。度量滤波器提取的特征节点如图2(c)所示，其中f_n表示特征节点，f`表示被删除的节点。

B.GVD特征矩阵

图2 构建特征矩阵

一个N阶方阵来表示特征节点之间的几何连接，其中N是特征节点的数量。在获取特征节点集时，首先对每个特征节点提取其相邻的节点。如图2所示，f_n的相邻节点包括f_2、f_4和f_n−1。基于相邻节点，构造了f_n的特征向量。如果一个节点属于f_n的相邻节点，则将具有其索引的元素设为f_n与当前节点之间的距离，否则设为零。

C.特征节点融合

图3 特征节点融合

提出了一种特征节点融合策略去除冗余的特征节点。冗余节点是指删除它不会破坏其余节点之间的连接的节点，它所表示的所有网格都可以连接到它的邻居节点。因此，特征节点的融合仍然可以保证具有代表性的完整性，这意味着地图自由区域中的每个节点都可以连接到至少一个特征节点。

在特征节点排序后，通过依次查找特征节点的邻居节点来检索融合候选节点。由于特征节点之间的几何连接已经记录在特征矩阵中，因此利用特征矩阵检索给定特征节点的邻居节点，从特征矩阵的第i行得到f_i的特征向量。具体判断方式如下：

其中阿达玛积指的是相同维的两个向量的分量乘法。这种候选节点检索方法可以避免遍历重复的邻居节点。本文利用该特征矩阵进行邻居检索，避免了耗时的碰撞检查，降低了邻居节点搜索的计算复杂度，从而提高了特征节点融合的效率。

需要进行碰撞检查的其余邻居节点将通过以下函数进行过滤：

（3） 基于特征矩阵的启发式路径规划

图4 基于特征矩阵的启发式路径规划

该方法使用广义Voronoi图（GVD）来生成启发式路径，并指导采样算法进行实时运动规划。在该方法中，首先通过GVD提取环境的特征节点，并使用特征矩阵来表示特征节点之间的连接关系。通过特征矩阵，可以快速检索特征节点的邻居节点，提高路径规划的效率。此外，还提出了特征节点融合算法，用于减少冗余的特征节点，提供紧凑的地图表示。通过建立特征树，并使用特征节点进行启发式路径规划，可以生成合理的启发式路径。该启发式路径可以作为子目标，通过风险-快速随机树（RRT）进行实时运动规划。通过偏置采样和选择下一个子目标，最终达到目标姿态。

（1）仿真参数设置

表1

对比算法：1））A*；2）Bi-RRT；3）GVD-FM

性能评价指标：

1）启发式路径规划时间；2）搜索节点数量；3）实时运动规划性能；4）特征节点紧凑度和代表性评价指标

（2）仿真结果与分析

表2 四种典型场景下的启发式路径规划实验的统计数据

表一列出了50次重复试验中获得的数据。结果表明，该算法明显减少了启发式路径规划时间。特别是在复杂的迷宫场景中，该算法的规划时间小于0.6 ms，验证了该算法在复杂的环境下仍能保证实时性能。还可以发现，与其他三种方法相比，要搜索的节点数量大大减少，这大大减少了处理时间。同时，算法生成的所有启发式路径都在A*算法的同一同伦类中。因此，虽然该算法的路径长度大于最优路径，但仍可为运动规划提供有效的指导。

图6

图6中额外显示了GVD提取和特征矩阵构造所需的时间。可以发现，即使在复杂的迷宫环境中，整个预处理时间也小于10 s，这说明了该方法在实际系统中的可行性。以A*算法的平均规划时间的三分之一和Bi-RRT算法的平均规划时间作为参考。除了相对简单的环境，即前后场景外，即使有预处理时间，提出的算法仍然优于A*算法和Bi-RRT算法。通过比较，可以看出该算法在复杂环境中的优势更为明显，而在简单环境中，基于采样的Bi-RRT算法具有更多的优势。

图7

不同场景下特征提取过程中的特征节点数如图7(a).所示分别记录了GVD提取后、初步特征提取后和特征节点融合后的特征节点数量。自由区域中的网格总数也被列为参考。对应的Cscore如图7(b).所示即使在迷宫的场景中，Cscore仍然能够低于0.05%。此外，还计算了四种场景的Rscore，且均为零，这意味着该算法可以很好地表示映射。

图8

四种情况下的导航运行时和轨迹的长度，以进行评估。每个病例均进行10次重复试验，实验结果如图8所示。显然，与risk-RRT算法相比，该算法在四种情况下都能获得更鲁棒的运动规划结果，导航运行时间更短，轨迹长度更短。

本文提出了一种基于 GVD 特征矩阵的高效启发式路径规划框架，用于动态环境中移动机器人的运动规划。首先，基于地图的 GVD，提出了一种特征提取和融合方法，以给出地图的简明表示。提出了一种特征矩阵结构来表示特征节点之间的联系。基于 GVD 特征矩阵，提出了一种高效的启发式路径规划算法。在实验研究中，对启发式路径生成、特征提取评估和实时运动规划的效率进行了实验。提出了两个指标来评价特征节点的紧凑性和代表性。实验结果证明，提出的方法可以在不同复杂度的环境中取得令人满意的性能。通过使用所提出的方法，机器人在二维环境中的运动规划的有效性和鲁棒性得到了大幅提高。

END

==河海大学网络与安全实验室==

微信搜索：Hohai_Network

联系QQ：1084561742

责任编辑：何宇