聊聊路径规划算法（四）——滚动在线RRT算法和BUG算法

基本RRT算法更偏向于遍历所有自由空间直到获取可行路由性，这使得它不能够进行未知或动态环境条件中的机器人实时运动计划。利用滚动计划的思路可以将RRT算法加以完善，使之更具有实时规划能力。

滚动规划

机器人在不确定的或动态周围环境中行走时，可以探知在其传感器区域内或限定区域的周围环境讯息。机器人可以使用局部信息制定局部运动规划，并使用适当的评估标准达到部分总体目标。然后机器人可以在到达部分总体目标以后，继续制定新的部分计划。就这样，不断实施直至抵达新全局目标。

滚动规划算法的基本原理:

环保信息系统预测:在滚动的每一次，机器人通过检测到的视野内的环保信息系统、或任何存在的环保信息系统，建立保护模式，包含设定在已知范围内的环保节点类型信息系统等；

局部的优化:把这些环境信息模式视为下一次优化的窗口，并在此基础上，按照子目标点的实际情况和特定的优化对策，设计出下一次的最佳子总体目标，接着再依据子总体目标的环境信息模式，选用局部规划算法，先设定向子总体目标前进的部分路线，再执行当前对策，即依所制定的部分路线前进若干步骤，窗口也随之往前滑动；

反馈信息修正:通过局部最优路线，驱动机器人走过一个路线时，机器人将检测到新的未知信号，此时可通过其在行进中检测到的信息数据调整或修正原有的环境模式，进行滚动和下步的局部设计。

这里，部分子目标是在滚动窗口中对某个全局目标的进行条件反射，它需要远离障碍物，并符合一些优化目标。子目标的选定方式，体现了对全局优势的追求和对局部整体受限信息条件的折衷，是在给定的社会环境条件下企图进行整体性考虑的天然选项。

通过滚动窗口的路径规划算法把实时检测到的局部环境信号，以滚动方法实现网络设计。在滑动的每一次，将针对已检测到的环境保护局部信息，采用启发式策略生成环境优化子目标，在当前的视窗中完成环境保护局部路径计划，进而执行当前决策（依局部规划路径推移一次），随着滚动窗口推移，将持续地获取最新的环境信息，以便于在滚动中进行环境优化和反馈信息的整合。同时由于环境规划问题压缩在滚动窗口中，其与环境保护全局计划比较的运算工作量将大为减轻。

采用滚动窗口的路径规划方式的具体步骤为:

第一步为0:先对起始、终端、环境、机器人的视线半径、步长等完成初始化；

步骤1:若终点抵达，则规划中止；

操作2:对当前滚动窗内的所有环境消息予以刷新；

步骤3:产生局部子目标；

过程4:基于子目标和现存条件信息，在当前滚动窗口内计划一个经过调整的局部有效路线；

方法5:按规划的局部路径走进每一步，步长必须等于视野半径；

步骤6:返回步骤1。

滚动在线RRT算法流程

在一个滚动窗口内，随机树以当前区域为开始节点，并建立传感器区域内的所有随机树。结构方式与最基本RRT算法相同。但能够使在全局条件中随机树产生朝目标方向发展的态势，在运动规划时导入启发信号，以降低随机树的随机性，并增加搜索效果[7]。

以Road（x1，x2）指代随意树中二个位置节点间的道路价格，Dis（x1，x2）指代随意树中二个位置节点间的欧几里德距离。相似于Astar方法，本方法为随意树中各个节点设定一种估值参数:f（x）=g（x）+h（x）。当中g（x）=Road（x，xrand）为随意节点，而xrand则代表到树中目的结点x所需的道路时间。H（x）是启发的估值参数，在此处可取随意节点xrand到目标节点xgoal的距离作为估计值，h（x）=Dis（xrand，xgoal）。所以，f（x）就代表了从目的节点x经随机结点xrand至目的地节点xgoal的路线估量值。遍历滚动窗内随机树T时，若取估量函数中较小值的结点xnear，则f（xnear）=min（f（x））。它允许随机树按照距离为目标节点估计值f（x）很小的地方开始延伸，如图所示。