基于树结构的路径规划方法

REF：受限空间下变电站巡检机器人建图及路径规划研究

1. 概念解释

• 概率道路图算法（PRM）：一种用于路径规划的随机化算法，核心是在环境中随机采样中构建“道路图”，这个道路图由一系列节点和线组成

a1cf4968481dc09a278b297bc447b043.png

• 快速扩展随机树（RRT）：主要思想是将初始位置设定为根节点，通过随机采样的方式构建成一棵树，从该树的根节点，逐步扩展到目标点。能够快速地在自由空间中扩展搜索树，同时保证算法概率完备性的基础上找到一条连接起始位置和目标位置的路径

05b8272c688881eda69b014390ece2d6.png

• 蒙特卡洛树搜索(MCTS)：一种启发式的搜索算法，适用于部分可观测和非完全信息下的决策过程中，结合了随机采样与树形结构探索的优点，可以模拟从当前状态出发到目标点的不同可能路径，并通过大量随机游走来评估这些路径的质量。每次迭代过程中，算法会选择最具有潜力的节点进行扩展，逐渐构建出一个代表可行路径的树状结构，关键在于设计合适的随机策略以及如何高效地评估所生成路径的好坏。
• 动态窗口法(DWA)：核心思想是使用一个称为“动态窗口”的概念用来限制速度空间搜索范围，窗口定义的当前时刻下机器人能够安全执行的速度集（窗口大小根据机器人的运动学模型确定，确保所有的速度命令都可执行），同时根据机器人的动力学模型、环境感知信息以及预设的安全边界来确定，在每个控制周期内，DWA 评估动态窗口内的所有可行速度组合，并选择最优的一个作为下一步的控制命令。

f372515085eb9a9ebf67c3ff9382f831.png

622bc85a7c1856b1d40d031d576429d6.png

f50269290373245b5b1623e08e202acc.png

• 时序弹性带算法（TEB）：核心思想是通过一种类似于弹性带的模型来规划路径，并且在规划过程中考虑时间因素，使得生成的轨迹不仅平滑而且能够有效地避开障碍物，同时考虑到动态环境中的时间变化。
• 人工势场法（APF）：将环境中的目标位置视为吸引点，而障碍物则被视为排斥点，通过构建一个虚拟的力场，机器人能够被引导至目标同时避开障碍物，关键在于运用数学模型描述虚拟力场，一般情况下，目标吸引机器人，障碍物排斥机器人，这些力的综合确定机器人的运动方向。

f6eb73b8433686641226c3376f792497.png

• 光电编码器：能够精确检测机器人每个车轮每转过一定角度时产生的脉冲信号，并通过累计这些脉冲数，可以确定每个车轮自上一次读数以来转过的总圈数，计算出机器人的速度信息

11c2259ec366514ebafd3ef6be5ea80f.png

• 单线激光雷达：由激光束发射、接收和信号处理三部分组成，通常采用三角测距法进行目标距离测量，向障碍物发射一束激光束，该激光束达到障碍物后被反射会雷达激光接收端，并记录下从发射到结束到激光束的时间，并依据激光发射端与激光接收端的位移差，利用三角函数计算出障碍物与激光雷达之间的距离。

b3142a564a79ffe5d74c2f22d77e8b8f.png

• 多线激光雷达：3D 激光雷达以 ToF（Time of Flight）测距法为基本 原理，激光从发射器发出，在遇到场景中的物体时产生反射，反射光由接收器感应并检测，并计算该过程的持续时间 ToF

f4faff7b22c2f85765dbb447cd1b86a9.png

• 栅格地图：是将物理空间离散化为均匀分布的二维网格单元，每个栅格存储占据概率值，量化该区域存在障碍物的可能性，在地图构建的过程中，都有相应的值代表栅格状态

241008b876f41f47ad2abdbc570af0e7.png

• 拓扑地图：用于描述环境空间结构，核心思想是通过节点和连接线的抽象关系来建模环境，强调空间之间的连接性和相对位置，而非精确的几何细节，适用于大面积且障碍物简单的环境，具有占用内存少、规划效率高

5aaf7941487617c08c7349d1fec57a98.png

• 语义地图：一种高阶环境表征模型，通过多模态信息融合实现了对物理空间的深度解析，集成环境的几何结构与拓扑连接关系，并赋予环境要素语义层级的理解

3af0b74a989026640c5cef9357d48ea6.png

• Gmapping算法：将环境地图构建过程和定位系统进行隔 离分开处理，并且每一个粒子都携带一个地图，先根据机器人的传感数据对下一时刻的位姿进行预测，将预测的位姿与地图数据进行匹配，匹配通过就开始采样点选择并计算轮式里程计模型的概率分布，再进行粒子姿态的更新并计算位姿粒子的权重，在得到新的抽样粒子群后，然后通过阈值 N 判断筛选有效粒子。

0e4e5fc9b92dccf0c7ed6696188c90fe.png

• Cartographer算法：基于图优化算法，由模型前端局部建图和全局地图优化共同组成，在前端局部建图中本文利用概率栅格对激光雷达的扫描数据帧进行描述，然后通过闭环检测纠正子图位姿与激光扫描位姿之间的误差，新的激光扫描数据位姿与子图的位姿相匹配，最终建立环境地图。

2. RRT树结构改进算法

2d9b8e0f94805a5c3e5afdb5c28b9953.png

93dfe8912054fa27d5611be87b520a69.png

• 自适应目标偏置函数：使用采样节点与目标节点之间的权重系数决定采样节点的产生，系数的大小决定了RRT算法的搜索性能和目标偏置性能，当新节点与目标节点之间的距离变近时， 权重系数就会变大，实现了动态化影响算法的目标偏置。

e7c49ee39cfa4ad14a3c2c8fae7b925d.png

• 狭长通道启发式圆采样：与方向偏置相结合避免随机点生成在障碍物内部，重采样节点的生成由连线的水平夹角和预设的方向偏置角共同决定，使得重采样节点生成在狭窄空间的空白处并且偏置方向朝向目标节点，在很大程度上提升了 算法在狭窄通道的搜索效率。
• 路径修剪：RRT依靠大量离散点并将其依次连接生成行驶轨迹不具备连续性，存在大角度转弯点，直接使用会造成机 器人在行走过程中发生震荡和急转的现象，机器人的自身结构的约束导致机器人存在最小转弯半径的约束，依次对算法规划出的路径进行节点修剪。
  • 步骤一：对初始节点到路径中（除目标节点以外）倒数第二个节点间的所有节点进行遍历，对每个节点相邻的两个节点进行碰撞检测。
  • 步骤二：若碰撞检测通过，从路径的一端开始，逐一计算两相邻边之间的夹角以及该角度对应的半径 r，若 r 小于机器人最小转弯半径，则去除该节点，并将节点 k +1 与节点 k +3 相连接。
  • 步骤三：重复一、二步骤，并遍历所有路径上的节点使得所有路径满足机器人最小转弯半径的约束。

e444abadb4485617bdb1d0a23c31d068.png

• 路径平滑优化：为了满足机器人行走过程的稳定及流畅的运行，采用三次B 样条曲线对路径进行平滑处理，B 样条曲线是由一组控制点和一组基函数所组成。

e4542826c6b08efe0c2ce4c0f610f46a.png