提示

文章链接：https://doi.org/10.1016/j.eswa.2023.120254

（一）摘要

移动机器人路径规划（path planning）是指移动机器人自主设计从起点到终点的距离最短（shortest distance）、耗时最短（least time-consuming）、安全（safely）、无碰撞（collision-free）的路径。

根据环境信息的掌握情况，路径规划分为全局路径规划（global path planning）和局部路径规划（local path planning）。

在全局路径规划中，引入了两种方法：

• 环境建模方法（environment modeling methods）
• 路径评估方法（path evaluation method）

环境建模的方法包括：

• 网格法（grid method）
• 拓扑法（topology method）
• 几何特征法（geometric feature method）
• 混合表示法（mixed representation method）

在局部路径规划中，检测环境中常用的传感器，包括：

• 激光雷达（laser radar）
• 视觉传感器（visual sensor）

接下来，根据算法的特点，移动机器人路径规划算法分为经典算法、仿生算法（bionic algorithms）和人工智能算法三类。

在经典算法中，文章介绍了：

• 单元分解法（cell decomposition method）
• 基于采样的方法（sampling based method）
• 图搜索算法（graph search algorithm）
• 人工势场法（artificial potential field method）
• 动态窗口法（dynamic window method）

在基于仿生学的算法中，文章详细介绍了：

• 遗传算法（genetic algorithm）
• 蚁群算法（ant colony algorithm）
• 灰狼算法（gray wolf algorithm）

在人工智能算法中，文章引入了两种算法：

• 神经网络算法（neural network algorithm）
• 模糊逻辑（fuzzy logic）

（二）简介

移动机器人系统大致分为三个模块，包括信息感知（information perception）、路径规划（path planning）和运动控制（motion control）。

根据环境信息的水平，路径规划一般可以分为全局路径规划和局部路径规划。

全局路径规划是指机器人感知环境并能够按照预先定义的路径到达目标，基于这一特性，全局路径规划也称为离线路径规划（offline path planning）或静态路径规划（static path planning）。

局部路径规划是指机器人对环境部分或完全未知，通过组件进行实时监控并根据定义做出反应，因此局部路径规划也称为在线路径规划（online path planning）或动态路径规划（dynamic path planning）。

局部路径规划的特点是灵活性好，缺点是规划的路径可能是局部最优的，但无法保证全局最优，甚至可能无法到达目标。

另一方面，全局路径规划则需要移动机器人理解并构建全局地图模型，在地图模型上使用搜索算法获得最优或次优路径，引导机器人安全地向目标点移动在实际环境中。

在实际的路径规划策略中，常常需要集成结合全局路径规划和局部路径规划的系统，全局路径规划旨在寻找全局最优路径（global optimal path），而局部路径规划旨在实现实时避障规划（real-time obstacle avoidance planning）。

全局路径规划和局部路径规划没有根本区别。许多适用于全局路径规划的方法都可以改进为局部路径规划，而适用于局部路径规划的方法也可以改进为全局路径规划。

（三）全局路径规划与局部路径规划

3.1.1 全局路径规划

全局路径规划是根据现有的环境信息，为机器人设计一条从起点到终点的安全无碰撞路径。规划路径的准确性取决于环境信息的准确性。全局路径规划的过程可以看作是寻找最优解的过程。

3.1.2 环境建模法

环境建模的本质是对感知环境的组织和利用。合适的环境模型可以有效帮助移动机器人搜索路径。

环境建模的方法包括四个，即GM、TM、GCM、MR：

• 网格法（grid method）
• 拓扑法（topology method）
• 几何特征法（geometric feature method）
• 混合表示法（mixed representation method）

（1）GM（网格法）

Howden（1968）提出了 GM，本质上是将移动机器人的工作空间划分为一系列具有二进制信息且大小相等的网络单元。

当一个网格内没有障碍物时，我们称其为自由网格（ree grid），移动机器人可以自由行走。当网格中存在障碍物时，即使障碍物没有填满网格的整个区域，研究人员一般采用扩展的方法将障碍物扩展至填满整个网格，并将该网格称为障碍网格（obstacle grid）。

自由网格通常标记为0，障碍网格标记为1。我们一般根据机器人的实际尺寸来确定网格的大小。如果网格的尺寸很小，那么环境模型就会很清晰，规划的路径也很安全。但它会占用系统大量的存储空间，同时也会产生较多的干扰信号，导致路径规划时间较长。如果网格尺寸较大，则路径规划所需的时间较少，实时性较好，但如果环境信息模糊，则不利于路径规划。因此网格大小的确定对于后期的路径搜索非常重要。

但它会占用系统大量的存储空间，同时也会产生较多的干扰信号，导致路径规划时间较长。如果网格尺寸较大，则路径规划所需的时间较少，实时性较好，但如果环境信息模糊，则不利于路径规划。所以网格大小（grid size）的确定对于后期的路径搜索非常重要。

网格方法中的默认形状是正方形，搜索过程大多使用四叉树（quadtrees）或八叉树（octrees）来表示工作空间。

近年来，研究人员提出了蜂窝网格（honeycomb grid），以减少路径规划的时间和长度，提高移动机器人的行走安全性。

邵等人（2021）针对传统网格步长不均匀的问题，建立了基于方形网格的地图和基于蜂窝网格的地图。分析比较结果发现，蜂窝状网格在进行路径规划时路径长度更短、安全性更高，且避障角（obstacle avoidance angle）更小，路径更平滑，机器人在遇到障碍物时消耗的能量更少。

此外，对于网格方法，Orˇsulić等人（（2019）提出了一种基于边界检测（boundary detection）的二维占据网格地图创建系统用于支持机器人执行路径规划和探索任务。

考虑机器人和环境的多重约束（multiple constraints），张等人（2018a）提出一种基于LRF的二维网格图的多层次类人运动规划方法，引导机器人在非结构化的室内环境中自主导航。

GM 的特点是简单、易于实施以及易于扩展到 3D 环境。为 UAV（无人驾驶飞行器）的 3D 路径规划建立了方形网格（Wu et al., 2021c）。

网格的一致性（consistency）和正态性（normality）简化了网格空间中的邻接关系。在 Chen 的文献中（Chen et al., 2021），在对移动相机的环境进行建模时，使用白色网格表示相机可以自由通过的区域，黑色网格表示障碍物区域，其他颜色表示障碍物区域。

给每个网格一个通道因子后，路径规划问题就变成了寻找网格网络上两个网格节点之间的最优路径的问题。但它对工作区域的大小有一定的要求。如果面积太大，网格数量会急剧增加，进行路径搜索时会出现组合爆炸（combinatorial explosion）的问题。

（2）TM（拓扑法）

TM 是清华大学（中国）张教授于 1984 年提出的一种环境建模方法（Chien et al. 1984）。

其基本思想是用节点（nodes）来表示特定的位置，用边（edges）来表示这些位置的连接，可以表示为G=(V,E)来表征自由空间，其中V表示顶点集合，E表示连接顶点的边集。Voronoi图通常用来表示环境可行区域的骨架。

该方法的基本思想是从环境模型中生成到每个障碍物的最短距离相等的Voronoi边界，并在边的交汇处形成图的顶点。

Voronoi图由俄罗斯数学家G. Voronoi于1908年提出，最初应用于研究平面上点的邻近问题（Preparata等，1990）。邻近问题是指如果给定平面内存在某些点，并根据这些点划分平面，则该区域内的任何位置都比其他中心点更接近中心点（如上图所示） 。在移动机器人规划中，采用以障碍物为实体的Voronoi图来描述可行区域的网络结构。

TM可以有效降低度量空间的维数，Voronoi图可以将二维度量感知信息转化为可达区域的网络模型，使规划成为一维最优节点序列问题，是一种有效的拓扑表示更少的存储空间和规划时间的计算等。Voronni图表示以环境中的障碍物为中心的邻域划分的状态。因此，可以通过对子区域进行建模来实现增量拓扑环境建模（incremental topological environment modeling）。

戈麦斯等人（2020）提出了大规模室内场景的全局拓扑表示，其中每个房间都被建模为拓扑图的子图，用于机器人导航和轨迹规划。

杨等人（2021）提出了一种使用凸多面体估计三维空间几何形状的新方法。然后，利用几何信息将空间划分为不同的区域。并且这些区域被添加到拓扑图中作为节点来指导搜索过程。

Shin 和 Kim（2021）提出了一种通过并行卵石图提高规划 MPP（多智能体路径规划）解决方案的最优性的算法。将卵石图嵌入到任意复杂的环境中，结果表明可行性约束可以转化为可微的几何约束，并且这些约束满足约束数值优化的要求。

斯坦泽尔等人（2021）提出了一种计算中间点路线图的算法。该算法能够充分利用尽可能多的可用空间，并能够保证边和顶点之间不重叠。

TM路径规划效率高（路径也可能是次优的），但需要的存储空间很少，因此适合大规模环境中的应用。然而，拓扑图的创建和维护比较困难，并且当环境中存在两个相似的位置时很容易混淆。

（3）GCM（几何特征法）

GCM是指从环境感知信息中提取相对抽象的几何特征，如直线、圆弧、圆等来描述环境的移动机器人（Guivant等，2000）。

该方法建立了相对紧凑的模型并存储少量信息，这使得可以轻松地进行位置估计。然而，从原始数据中提取不随环境变化和机器人运动而变化的稳定特征的困难导致该方法主要适用于结构化操作环境。此外，找到观察到的特征与不断更新的环境信息之间的精确匹配也是一个技术难题。几何表示的缺点是环境几何特征提取困难，特别是在复杂的非结构化环境中。

梁等人（2018）提出了一种基于GCM的无人机路径规划方法。该方法关注障碍物的形状，最终找到一条无碰撞的路径。障碍物组织在树列表中。通过查询阻挡障碍物并连接它们的子目标来生成无碰撞路径。

Jafarzadeh 和 Fleming（2018）提出了一种新的精确算法来解决路径规划问题，该算法涉及在包含凸面和非凸面障碍物的 2D 环境中找到从起点到目标点的最短无碰撞路径。构建连接顶点和障碍物起点的线性网络，该网络比可见性图生成的网络要小，然后求网络中从起点到目标点的最短路径。

（4）MR（混合表示法）

1998年，Thrun（1998）提出了一种从全局度量地图中提取拓扑特征的方法，利用声纳传感器的距离信息在机器人导航过程中提取特征。当声纳的距离信息恰好与已知节点的特征显着不同时，生成新节点。如果特征信息与已知节点的特征相似，则使用部分可观察马尔可夫决策方法进行概率定位，同时生成环境的拓扑图。然而，在障碍物距离特征不够显着的区域生成拓扑图仍然不容易，并且对具有传感器噪声的动态环境也敏感。

1999年，Yeap & Jefferies (1999)提出了一种从局部度量图中提取全局拓扑图的方法。局部地图由网格表示，使用类似拓扑的边集连接多个已存在的局部地图。由于局部度量图保持在较小范围内，因此可以忽略误差。路径规划采用局部和全局两个层次的规划，即基于占据网格的区域规划和基于拓扑连通关系的全局规划，这是最原始的混合表示。

MR可以将拓扑路径规划的效率与度量空间中更高的建模精度结合起来，实现多层次的规划。在面向家庭服务的机器人研究中，提出了一种高效物品搜索的拓扑度量地图构建方法，使移动机器人能够在复杂的家庭环境中快速定位目标物品（Zhang，2021），为机器人高效地搜索物品提供了重要保障。与传统的拓扑地图不同，该方法通过参考环境项创建地图上的拓扑节点，减少了与项搜索无关的冗余节点，降低了移动机器人的搜索成本，提高了路径规划效率。

Gregorio & Stefano (2017) 提出了SkiMap 一种用于机器人导航的多级环境模型框架。 SkiMap包含3D体素网格图、2.5D高度图和2D占用网格图，并支持持续更新以提高步行过程中地图的准确性。

3.1.3 路径评估法

移动机器人路径搜索问题的主要任务是找到正确的搜索策略。为了评估每种搜索策略的能力并以客观的方式衡量其性能，本节将提出七种不同的评估方法（Tsardoulias 等），2016）。

（1）平均路径规划时间

用 $t_m$ 表示，指算法花费的平均路径规划时间，这个标准至关重要，因为任何算法都必须有效地为移动机器人规划路径，并在尽可能短的时间内给出结果。

（2）平均路径规划时间的相对标准偏差

算法所花费的平均路径规划时间的相对标准偏差 $RT$ ，计算公式为：

$$R T=\frac{\sqrt{\frac{1}{N \bullet K} \bullet \sum_{i=1}^{N \bullet K}\left(t_{i}-t_{m}\right)^{2}}}{t_{m}}$$

式中，$t_i$ 表示算法第i次规划路径所花费的时间； $N$ 为环境中的目标点； $K$ 是算法执行的次数。相对标准偏差是统计学中反映准确性和重复程度的指标。从算法规划时间的角度来看，相对标准差代表了一个算法的可靠性，即算法每次运行的时间与平均时间的偏离程度。

(3)平均路径长度

算法运行后生成的路径的平均长度 $D_m$。平均路径长度与移动机器人的路径跟踪时间直接相关，因此这个评价标准至关重要。我们假设每条路径有许多目标点，并将第 $i$ 个目标点标记为 $Path_i$。另外，机器人到达目标点的路径长度 $PathSize=|Path|$。所以 $Dm$ 的公式是：

$$D_{m}=\sum_{i=1}^{\text {PathSize }} \operatorname{Dist}\left(\text { Path }, \text { Path }_{i+1}\right)$$

其中公式：

$$\operatorname{Dist}(p, q)=\sqrt{\left(x_{p}-x_{q}\right)^{2}+\left(y_{p}-y_{q}\right)^{2}}$$

指坐标轴上点$p$与点$q$之间的欧氏距离。

（4）路径长度的相对标准偏差

用$RD$表示，算法计算后路径长度的标准偏差，类似于执行时间的相对标准偏差。计算公式为：

$$R D=\frac{\sqrt{\frac{1}{N \bullet K} \bullet \sum_{i=1}^{N \bullet K}\left(D_{i}-D_{m}\right)^{2}}}{D_{m}}$$

式中，$D_i$为算法运行第$i$次得到的路径长度。该标准评估算法生成的路径的准确性，即算法在不同的地图环境下是否生成相同的路径。

（5）路径曲率

用$RC$表示，路径曲率反映了算法生成路径的平滑程度，即机器人在跟踪路径时必须执行的旋转运动量。在这里，根据文献（Tsardoulias et al., 2016），我们指定 $RC$ 的范围为 $[0,1]$。当机器人穿过特定路径时，测量其转动运动。为了简化计算，默认车辆仅在目标点转弯，转弯的目的是与下一个目标点对齐。另外，假设机器人在转弯时始终旋转最小角度，因此转弯的角度范围为$[0°,180°]$。显然，最好的情况是机器人与最终目标对齐并且不需要旋转运动，因此角度和为$0°$。另一方面，最坏的情况是对每个子目标执行 $180°$ 转动，这是不现实的，但由此可以计算出 $RC$ 的上限，其计算方式如下：

$$R C=\frac{\sum_{i=1}^{\text {PathSize }} \theta_{i}}{(\text { PathSize }-1) \bullet 180^{\circ}} \in[0,1]$$

版权所有

版权归属：SAKE

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

编辑此页

上一页《虞美人 · 寒窗寄怀》

下一页《一剪梅 · 暮蛩声咽旧苑楼》