点击上方“3D视觉工坊”，选择“星标”
干货第一时间送达
作者丨 Li-Jianghao
来源丨古月居
快速搜寻随机树（RRT）算法是一个增量式采样的搜寻技术，这个算法在实际使用中并不要求将任何参数整定，因此具有极好的使用性能。
它可以通过增量式方法构造搜寻树，并逐渐增加分辨时间，而不需设定任何高解析度参数。
在极端环境情况下，该搜寻树将稠密的充满全部空间，此时搜寻树由许多较小曲线或路经组成，以达到填满全部空间的目的。
增量式运算中，所建立的速率搜寻树其方向通常都是稠密采样次序，但一旦该顺序是绝对随意的时，那么这种速率搜寻树就叫做速度搜寻绝对随机树（Rapidly Exploring Random Tree，RRT）[5]，而不管该次序为绝对随意的或是确定性次序，都被称之为速率搜寻稠密树（Rapidly Exploring Dense Trees，RDTs），而利用这些计算方式则需考虑微分的各种约束。
算法步骤
考虑二维和三维的操作空间，当环境条件中存在静止障碍物。且当首先初始化速度是随机搜索的状态树T时，并不存在根结点，即为初始状态的树S。
然后，先从自由空间中随机选择下一个新的状态结点xrand，然后再以遍过当前的速度随机寻找新状态树T，并寻找在T上离xrand最近的新状态结点xnear，在充分考虑机器人的动力学约束之后，在限制注入集U中选择限制注入U∈U，从最近新状况xnear开始作用，并使用下一次限制时间T到最近新的状态xnew。
符合状况xnew和xrand中的限制注入U的最佳控制量之后。把新状况xnew加载在速度随机搜索树T中。然后根据这样的获取方式继续创造新状态，直至达到目标状态G。
完成搜索树构造之后，再从目标节点入手，逐渐查找父节点直至达到初始状态，即开始查找下一棵树的根结点，如图所示。
因为在寻找流程中充分考虑了机器人的动力学制约，所以形成的路线的可能性非常好。但由于计算的高度随机性，造成了它只具有机率的完全性质。
改进算法
在采集策略方面，RRTGoalBiaS方式在监控机器人随机运动的时候，也以特定几率向最终目标运动；而RRTGoalZoom方式则需要从整体空域，以及在目标地点附近的小空域中完成采集；RRTCon方法则由于增加随机步长提高了计划速率。
同样双向规划思想也被引入，从而产生出了RRTExtExt，RRTExtCon，RRTConCon等多个算法。
基本RRT方法，在收敛到终点位置上运行的速率稍许缓慢。为进一步提高计算的质量与稳定性，应进一步对方法加以完善。如进一步提高搜寻工作效率，引入了双向随机搜索树（Bi~RRT），在初始节点上与目标节点之间并行产生二棵RRT，直到最后二棵树相遇，计算才收敛。
因此这个计算方法，相对于原始RRT树而言具有相当高的收敛性，而且对于目前路径算法中也是较为普遍的。
而由NikAMelchior所提出的粒子RRT树算法中，也考虑了地形的高度不确定性，并因此实现了在较低不确定性条件下搜索树的拓展。但Kuffner和Lavane后来又给出了RRT-connectlv，使节点的扩散与利用率大幅度地增加。
在运动计划中，基于距离的概念非常复杂，而且Pengcheng还深入研究了在RRT生长进程中距离函数通过持续学习适应环境改变的方法，以降低间距函数对环境改变的影响敏感。
充分思考到从最基本RRT计算器上获得的路径宽度，通常为最佳路径的1.3~1.5倍，因此加拿大的J.Desmithl还开发出了变分法技术，并使之得以实现。
AmnA A通过引入KD树，可为二级数据结构加速找到距在实际环境中得到的随机节点数量最近的叶节点，从而减少了搜寻成本。
该方法在移动车辆、多维状态空间结构，以及在具有运行学、动力学等微分约束的复杂环境中的运动规划上也已获得了普遍的运用，如图所示。
本文仅做学术分享，如有侵权，请联系删文。
3D视觉工坊精品课程官网：3dcver.com
1.面向自动驾驶领域的多传感器数据融合技术
2.面向自动驾驶领域的3D点云目标检测全栈学习路线！(单模态+多模态/数据+代码) 3.彻底搞透视觉三维重建：原理剖析、代码讲解、及优化改进 4.国内首个面向工业级实战的点云处理课程 5.激光-视觉-IMU-GPS融合SLAM算法梳理和代码讲解 6.彻底搞懂视觉-惯性SLAM：基于VINS-Fusion正式开课啦 7.彻底搞懂基于LOAM框架的3D激光SLAM: 源码剖析到算法优化 8.彻底剖析室内、室外激光SLAM关键算法原理、代码和实战(cartographer+LOAM +LIO-SAM)
9.从零搭建一套结构光3D重建系统[理论+源码+实践]
10.单目深度估计方法：算法梳理与代码实现
11.自动驾驶中的深度学习模型部署实战
12.相机模型与标定(单目+双目+鱼眼）
13.重磅！四旋翼飞行器：算法与实战
14.ROS2从入门到精通：理论与实战
15.国内首个3D缺陷检测教程：理论、源码与实战
16.基于Open3D的点云处理入门与实战教程
重磅！3DCVer-学术论文写作投稿 交流群已成立
扫码添加小助手微信，可申请加入3D视觉工坊-学术论文写作与投稿 微信交流群，旨在交流顶会、顶刊、SCI、EI等写作与投稿事宜。
同时也可申请加入我们的细分方向交流群，目前主要有3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、多传感器融合、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流、ORB-SLAM系列源码交流、深度估计等微信群。
一定要备注：研究方向+学校/公司+昵称，例如：”3D视觉 + 上海交大 + 静静“。请按照格式备注，可快速被通过且邀请进群。原创投稿也请联系。
▲长按加微信群或投稿
▲长按关注公众号
3D视觉从入门到精通知识星球：针对3D视觉领域的视频课程（三维重建系列、三维点云系列、结构光系列、手眼标定、相机标定、激光/视觉SLAM、自动驾驶等）、知识点汇总、入门进阶学习路线、最新paper分享、疑问解答五个方面进行深耕，更有各类大厂的算法工程人员进行技术指导。与此同时，星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息，打造成集技术与就业为一体的铁杆粉丝聚集区，近4000星球成员为创造更好的AI世界共同进步，知识星球入口：
学习3D视觉核心技术，扫描查看介绍，3天内无条件退款
圈里有高质量教程资料、答疑解惑、助你高效解决问题
觉得有用，麻烦给个赞和在看~
