欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

路径规划之RRT类算法简述

时间:2023-04-26

  关注同名微信公众号“混沌无形”,阅读更多有趣好文!

原文链接:机器人空间采样算法研究现状简述(包含原文PDF百度云下载链接)

空间采样算法按照采样空间不同,可分为:状态空间采样和运动空间采样。如图 2.1所示,基于状态空间采样的算法能够在大面积、高纬度的空间中快速生成路径,包括RRT和PRM类算法等,具有概率完备性,其主要步骤包括随机采样、度量连接、碰撞检测和路径查询。基于运动空间采样的算法则在速度空间等距采样,通过评价函数选择最佳控制指令,驱动机器人运动,主要包括CVM类算法及DWA类算法等。

(请横屏看图)

图 2.1 空间采样算法发展路线概况

 

第二类算法是RRT(Rapidly Exploring Random Tree)类算法,此类算法的核心思想和PRM相似:RRT也是在搜索空间中随机采样,并以起始点或终止点为树根节点开始扩展,仅连接符合约束条件的临近采样节点,直到树中的某一节点靠近目标点或起始点,最后基于上述生成的树搜索出一条最短路径。

图 2.3 RRT算法(图片来源:https://github.com/AtsushiSakai/PythonRobotics)

 

所以,不同于PRM图状结构,RRT采用树状结构,查询效率更快。传统RRT[5]算法与传统A*算法在多方面极为相似,诸多研究者对传统RRT算法也做出相似的改进,本文根据RRT特性分为单向、双向、导向及非全向四种类型,具体如下: 

单向搜索 

Karaman、Gammell等人针对RRT随机性强、路径粗糙及动态适应性差等问题提出了改进算法,如RRT*[6]可重计算新节点实现渐进最优,Informed RRT*[7]基于初始路径采用椭圆收缩策略,减少锯齿状路径情况,RRTX[8]设计重规划策略以适应动态环境,提升算法的实用性。

图 2.4 Informed RRT*(图片来源:https://github.com/AtsushiSakai/PythonRobotics)

 

双向搜索 

Kuffner、Jordan等人为提升搜索效率,同时从起点、终点构建两(多)棵树,如RRT-connect[9],Optimal B-RRT*[10]在此基础上加入了启发式函数,进一步提高收敛速度,HARRT*[11]将同伦拓扑空间与双向树结合,并从理论上证明了该方法的有效性。

图 2.5 RRT-connect(图片来源:https://arxiv.org/pdf/1703.08944.pdf)

导向搜索 

除双向扩展树策略外,Jaillet、Rodriguez等人根据环境特征诱导采样点的生成,如ADD-RRT[12]将边界点采样区限制于球体中,并建立球半径与边界点扩展成功率的映射关系,以此提升扩展成功率。OB-RRT[13]与之类似,通过收集障碍物数据以确定节点生长方向。CL-RRT[14]将闭环预测应用于RRT框架,使用了物理与/或逻辑环境来偏置高斯采样云,并被应用于MIT Talos。 

非全向限制搜索 

Karaman、Webb等人研究改进RRT算法以满足存在非全向约束条件的机器人,如Kinodynamic-RRT*[15]考虑了机器人模型硬约束,但计算内存消耗较大,Adapted RRT*[16]克服了该缺点并得到渐进最优解,可解决5D状态空间下的类车机器人和10D状态空间下飞行器的运动规划问题。RTR+C*CS[17]提供完整规划方案,RTR生成全局路径,C*CS使用直线段和圆弧拟合得到局部路径(图 2.6),但需要的迭代次数较多。针对高维度规划问题,RABIT*[18]使用同伦类生成初始路径,并采用局部优化技术达到全局优化的结果。

图 2.6 C*CS [17]

 精彩的理论论证过程见原文链接(含全文下载链接)

由于网页排版效果一般,所以笔者按照期刊论文版式为小伙伴们整理了原文PDF,方便收藏和回味。

原文链接:(包含原文PDF百度云下载链接)
CSDN下载链接:移动机器人路径规划之一空间采样算法

如果喜欢的话,可以关注我,阅读更多有趣好文!

微信公众号:混沌无形

知乎号:混沌无形

B站:混沌无形R

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。