作者：一个大胖猪 | 编辑：计算机视觉工坊
添加小助理：dddvision，备注：方向+学校/公司+昵称，拉你入群。文末附行业细分群
0. 笔者个人理解
机器人路径规划是一个重要的研究领域，涉及到如何让机器人安全、有效地在环境中导航和移动。这个领域的历史可以追溯到几十年前，随着如今机器人技术的进步和应用的扩展，路径规划算法在机械臂、移动机器人以及人形机器人等领域的重要性日益凸显。
1. 基于搜索的路径规划算法
基于搜索的路径规划算法是最早开始进行研究的。这类方法最开始主要用于迷宫求解问题中，在机器人导航时，往往将环境进行栅格化，生成栅格地图（Grid Map），然后在栅格地图中迭代搜索出从起点到终点的最短路径。
- BFS（广度优先搜索）算法：通过探索相邻栅格来搜索最短路径。BFS算法通常使用队列数据结构来存储待搜索的节点，并按照层次，逐层进行遍历。
BFS算法Demo
- Dijkstra算法：通过逐层搜索和更新最短路径树，找到从起点到终点的最短路径。算法的时间复杂度为O((V+E)logV)，其中V和E分别为图中顶点数和边的数量。Dijkstra算法在处理大规模环境和复杂障碍物时表现良好，具有较高的效率和鲁棒性。
Dijkstra算法Demo
- A*算法：通过代价函数来估计从起点到终点的成本，并使用最佳优先搜索策略来寻找代价函数值最低的节点，最终找到最短路径。它是一种启发式的搜索方式，极大地减少了搜索节点的数量，提高了搜索算法的效率。
A*算法Demo
如果有兴趣的话，可以在这个路径规划Demo设计障碍物并对比不同算法的表现。
优缺点总结：
优点：基于搜索的路径规划算法往往能根据环境地图，找到从起点到终点的最短路径，可以极大提高机器人的移动效率。
缺点：针对高维空间或者大规模地图是，基于搜索的路径规划算法的搜索效率较低，需要迭代的搜索绝大多数单元格，时间消耗大。
2. 基于采样的路径规划算法
针对基于搜索的路径规划算法出现的在大型场景下搜索效率低的问题，基于采样的路径规划算法被提出并且进行了广泛的应用。基于采样的路径规划算法，通过在环境地图中进行不断地采样，并将采样点进行连接，直到算法发现从起点到终点的通路。基于采样的路径规划算法往往具有概率完备性，这是指当采样点的数量足够多的时候，所得到的路径就越接近最优路径。因此，基于采样的路径规划算法往往只能够得到渐进最优解。
- 概率路线图（Probabilistic Road Map，PRM）：该算法的核心思想是通过在地图上进行采样，将环境地图表示为一个概率图，其中节点表示环境中的各种可能位置，边表示从一个位置到另一个位置的概率转移。PRM算法通过随机采样和优化来生成最优路径，最终找到从起点到终点的可行路径。
PRM算法
- 快速搜索随机树（Rapidly-Exploring Random Trees，RRT）：通过不断随机采样和将采样点相连构建搜索树，逐步探索环境并找到了起点A到目标点B的一条路径。RRT算法适用于复杂的环境，因为它不需要预先了解环境的完整信息，并且可以有效地处理障碍物和未知区域。需要注意的是，RRT算法生成的路径可能不是最优路径，但通常可以找到一条可行且相对较好的路径。
RRT算法
Imformed RRT 算法
优缺点总结：
优点：基于采样的路径规划算法鲁棒性强，能够处理各种环境变化，如障碍物移动、地形变化等；不需要对所有可能的路径进行搜索，它通过采样局部区域来生成路径，从而减少了计算量。
缺点：基于采样的路径规划算法寻找的是可行解，而不是全局最优解，可能错过一些更好的路径，特别是在环境中有多个可行路径；对初始采样的依赖性强，如果初始采样选择的位置不合适，可能会导致算法陷入局部最优解或找不到可行路径。
3. 全局路径规划的最新进展
接下来将介绍并总结近两年发表在机器人顶刊（Science Robotics，IJRR）上的关于全局路径规划的两篇文章。
《Motion planning around obstacles with convex optimization》
作者：Tobia Marcucci, Mark Petersen, David von Wrangel, Russ Tedrake
机构：MIT，Harvard
期刊：Science Robotics
原文链接：https://www.science.org/doi/10.1126/scirobotics.adf7843
场景：对于机器人，如机械臂、自动驾驶汽车等，在障碍物环境中，有效率的机器人路径规划是非常重要的。同时，在路径规划中，考虑机器人的dynamic和kinematic的限制，也是非常重要的。Dynamic限制主要是针对机器人系统的加速度约束，而kinematic限制主要是针对轨迹约束。基于搜索的路径规划算法难以实现在3维大场景下的实时路径规划，同时传统基于采样的方式只能得到路径的可行解，而无法得到最优解。因此，作者提出了一种基于凸优化的GCS算法用于实现在多维度上的路径规划的求解。
主要贡献： 1）将环境中可通行安全区域分解成凸形状的图形，分解后的图形如下图B中 至 所示。这种分割可以保证，如果两点位于同一区域，那么他们的连线不会与障碍物产生碰撞。
2）提出了一种针对凸优化松弛方法的路径求解器。这个求解器可以有效应对路径规划中出现的多种约束并且可以应用到多种场景之中。
3）在实验中验证了该方法能够有效生成符合约束条件的全局最优解，并且在时间上远远少于基于采样的路径规划算法。
GCS算法示意图
效果展示：
GCS算法效果展示
《Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning》
作者：Marlin P Strub, Jonathan D Gammell
机构：CalTech, Oxford
期刊：The International Journal of Robotics Research (IJRR)
原文链接：https://journals.sagepub.com/doi/full/10.1177/02783649211069572
场景：这篇文章主要针对路径规划中两个问题：1）规划从起点到终点的可行路径（feasible path）；2）规划出与障碍物保持一定距离的路径（obstacle clearance）。针对这两个问题，在这篇文章中，作者追求选择去生成路径的渐进最优解来提高基于采样的路径规划算法的效率。
主要贡献： 1）提出了AIT*与EIT*两个基于采样的路径规划算法路径，分别用于解决在环境中发现最短路径与生成与障碍物保持一定距离的路径。
AIT*算法示意图
EIT*算法示意图
2）利用图论的相关知识，证明了他们提出的算法能够实现渐进最优解。
3）在机械臂等平台上，设计实验证明了AIT*与EIT*的有效性，效果能够超过其他基于采样的路径规划算法。
效果展示：
AIT*算法效果展示
EIT*算法效果展示
4. 总结
今天笔者为大家首先介绍了传统的路径规划算法，主要分为基于搜索的路径规划与基于采样的路径规划，列举了例子并总结了他们的优缺点。之后，介绍了最新发表在机器人顶刊Science Robotics和IJRR上关于机器人全局路径规划算法的最近研究，总结了他们的背景与贡献。
本文仅做学术分享，如有侵权，请联系删文。
计算机视觉工坊交流群
目前我们已经建立了3D视觉方向多个社群，包括2D计算机视觉、大模型、工业3D视觉、SLAM、自动驾驶、三维重建、无人机等方向，细分群包括：
2D计算机视觉：图像分类/分割、目标/检测、医学影像、GAN、OCR、2D缺陷检测、遥感测绘、超分辨率、人脸检测、行为识别、模型量化剪枝、迁移学习、人体姿态估计等
大模型：NLP、CV、ASR、生成对抗大模型、强化学习大模型、对话大模型等
工业3D视觉：相机标定、立体匹配、三维点云、结构光、机械臂抓取、缺陷检测、6D位姿估计、相位偏折术、Halcon、摄影测量、阵列相机、光度立体视觉等。
SLAM：视觉SLAM、激光SLAM、语义SLAM、滤波算法、多传感器融合、多传感器标定、动态SLAM、MOT SLAM、NeRF SLAM、机器人导航等。
自动驾驶：深度估计、Transformer、毫米波|激光雷达|视觉摄像头传感器、多传感器标定、多传感器融合、自动驾驶综合群等、3D目标检测、路径规划、轨迹预测、3D点云分割、模型部署、车道线检测、BEV感知、Occupancy、目标跟踪、端到端自动驾驶等。
三维重建：3DGS、NeRF、多视图几何、OpenMVS、MVSNet、colmap、纹理贴图等
无人机：四旋翼建模、无人机飞控等
除了这些，还有求职、硬件选型、视觉产品落地、最新论文、3D视觉最新产品、3D视觉行业新闻等交流群
添加小助理: dddvision，备注：研究方向+学校/公司+昵称（如3D点云+清华+小草莓）, 拉你入群。
3D视觉学习知识星球
3DGS、NeRF、结构光、相位偏折术、机械臂抓取、点云实战、Open3D、缺陷检测、BEV感知、Occupancy、Transformer、模型部署、3D目标检测、深度估计、多传感器标定、规划与控制、无人机仿真、三维视觉C++、三维视觉python、dToF、相机标定、ROS2、机器人控制规划、LeGo-LAOM、多模态融合SLAM、LOAM-SLAM、室内室外SLAM、VINS-Fusion、ORB-SLAM3、MVSNet三维重建、colmap、线面结构光、硬件结构光扫描仪，无人机等。