专栏首页机器人技术与系统RobotRRT: 机器人路径规划RRT算法(1)
原创

RRT: 机器人路径规划RRT算法(1)

RRT应用案例

1 RRT 算法概述

RRT*算法是一种基于随机采样的路径规划方法,不仅具有概率完备性,还具有渐进优化能力。假设X=(0,1)^d代表d维构型空间,d \in N,d\geq 2

进一步假设X_{obs}代表障碍物空间,X_{obs}属于X.X_{free}表示自由空间,X_{free}+X_{obs}=X.对于机器人来说,初始构型和x_{init}和目标构型x_{goal}X_{free}中的元素。由此可以将路径规划问题转化为以下形式

X_{free},x_{init},x_{goal}

假设函数\sigma:[0,1] \rightarrow R^4 ,\sigma 的全变差可以定义如下:

全变差

为了更好的理解算法,有必要实现熟悉三个定义:

定义一

\sigma的全变差TV(\sigma)<\infty,则称函数\sigma为区间[0,1]上的有界变差函数。

->\sigma是连续函数,则可以称\sigma为路径,

->\sigma是路径,且对所有\tau \in [0,1], \sigma(\tau) \in X_{free}.\sigma 为碰撞路径;

->σ是无碰撞路径, 且\sigma(0)=x_{init}\sigma(1)=x_{goal},则称\sigma 为可行路径。

由上述定义,路径的总变差可以理解为路径的长度。

定义二

(可行路径规划)给定一个路径规划问题(X_{free},x_{init},x_{goal}),如果可行路径存在,则规划一条可行路径,如果路径不存在,则返回可行路径失败信息。

定义三

规划一条路径问题,(X_{free}, x_{init}, x_{goal}),并定义价值函数c: \sum \rightarrow R \geq0 .\sum 是可行路径。如果最优路径存在,则会规划一条最优路径\sigma*且如果最优路径存在,则返回最优路径规划失败信息。

对于机器人的路径规划,从环境情况感知情况,可以将其分为以下两种:

  • 环境已知路径规划
  • 环境未知路径规划

2 RRT 算法的特点

RRT算法全称是快速扩展随机树,(RRT, Rapidly-exploring Random Trees)是最近十几年得到广泛发展与应用的基于概率采样的运动规划算法。由Steven M.LaValle教授在1998年提出。

RRT是采用一种特殊的增量方式进行构造,这种方式能迅速缩短一个随机状态点与树的期望距离。该方法的特点是能够快速有效搜索高维空间,通过状态空间的随机采样点,将搜索导向空白区域。从而得到一条从起始点到目标点的规划路径。它通过对状态空间中的采样点进行碰撞检测。避免了空间的建模,能够有效的解决高维空间和复杂约束的路径规划问题。

RRT算法适合解决多自由度机器人在复杂环境下和动态环境中的路径规划问题。

与其他的随机路径规划方法相比,RRT算法更适用于非完整约束和多自由度的系统中。

RRT 算法具有以下优势:

  • RRT 在扩展过程中,倾向于扩展(探索)未知的空间;
  • 该算法具有概率完备性,即随着迭代次数的增加,越来越多的未知空间被探索,当迭代次数趋于无穷大,所有的空间都能被探索,也就能保证目标构形一定能到达;
  • 节点的分布与采样点的分布状况一致;
  • 由于不用对障碍物进行精确建模,只用获得是否碰撞的信息,RRT 算法的避障规划效率高。

尽管RRT算法是一个相对高效率,同时可以较好的处理带有非完整约束的路径规划问题的算法,并且在很多方面有很大的优势,但是RRT算法并不能保证所得出的可行路径是相对优化的。因此许多关于RRT算法的改进也致力于解决路径优化的问题,RRT*算法就是其中一个。

RRT*算法的主要特征是能快速的找出初始路径,之后随着采样点的增加,不断地进行优化直到找到目标点或者达到设定的最大循环次数。RRT*算法是渐进优化的,也就是随着迭代次数的增加,得出的路径是越来越优化的,而且永远不可能在有限的时间中得出最优的路径。因此换句话说,要想得出相对满意的优化路径,是需要一定的运算时间的。所以RRT*算法的收敛时间是一个比较突出的研究问题。但不可否认的是,RRT*算法计算出的路径的代价相比RRT来说减小了不少。


Ref: 冗余机械臂运动学及避障路径规划研究

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 这可能是史上最全的 Python 算法集(建议收藏)

    该算法利用扩展卡尔曼滤波器(Extended Kalman Filter, EKF)实现传感器混合本地化。

    华章科技
  • 收藏 | 一文洞悉Python必备50种算法(附解析)

    其主要特点有以下三点:选择了在实践中广泛应用的算法;依赖最少;容易阅读,容易理解每个算法的基本思想。希望阅读本文后能对你有所帮助。

    Python数据科学
  • 这可能是史上最全的Python算法集!

    其主要特点有以下三点:选择了在实践中广泛应用的算法;依赖最少;容易阅读,容易理解每个算法的基本思想。希望阅读本文后能对你有所帮助。

    AI科技大本营
  • 用于移动机器人路径规划的优化通知随机树(cs.RO)

    基于基本的快速探索随机树(RRT)的路径规划器是快速有效的,并有利于实时机器人路径规划,但几乎肯定是次优的。相比之下,最佳RRT(RRT*)会收敛到最优解,但在...

    Sie
  • ROS和RRT的一些资料

    ROS和RRT结合的示例比较多,之前博文提过两次( 1 和 2 ),本文做一些汇总和整理,大部分都在roswiki和GitHub上有具体说明。需要认真阅读源码和...

    zhangrelay
  • 机器人如何使用 RRT 进行路径规划?

    最近,我一直在和实验室的研究生一起研究移动机器人。我们通过尝试替换ROS中的一些默认包,学习了解了一个典型的机器人技术栈的各种算法。我的主要研究领域是规划和强化...

    McGL
  • 路径规划算法简介

    经过查阅相关文献可知,若用A*算法进行路径规划,倘若存在最优路径必能找到,但是但对于高维空间的路径规划问题,A*算法并不适用。RRT算法与A*算法相比,不需要对...

    六四零
  • 总结 | 六大路径规划算法

    转载于:https://zhuanlan.zhihu.com/p/51372134, 知乎ID:搬砖的旺财

    计算机视觉联盟
  • 不确定条件下城市空中交通运营的风险有界路径规划

    防撞是飞行器在动态和不确定城市环境中自主运行的一个基本问题。本文介绍了一种在这种环境下运行的无人机(UAV)的风险有界路径规划算法。该算法提出了带有机会约束的快...

    用户8839980
  • 「万字综述」自动驾驶决策控制及运动规划方法「AI核心算法」

    知乎专栏:https://zhuanlan.zhihu.com/p/260707853

    用户7623498
  • 机器人相关学术速递[8.19]

    【1】 PerceMon: Online Monitoring for Perception Systems 标题:PerceMon:感知系统的在线监测 链接:...

    公众号-arXiv每日学术速递
  • 基于双DQN的复杂环境中机器人路径规划改进算法(cs.RO)

    根据我们的实验,深度Q网络(DQN)在应用于有许多两难问题的环境中规划路径时有几个局限。奖励函数可能很难建模,而且成功的经验转换在经验回放中很难找到。在这种情况...

    Sie
  • 自动驾驶中的决策规划算法概述

    作者简介:byheaven,2018年加入美团无人配送部,目前在pnc组负责决策规划相关工作。

    美团无人配送
  • RRT算法的基本程序模块(2)

    快速随机搜索树(RRT)算法是基于随机采样的路径规划算法,它相比于其他算法的一个优势在于可以有效地将非完整约束考虑在算法内部,从而避免了复杂的运动学约束的考虑,...

    ZC_Robot机器人技术
  • 伯克利人工智能研究:FaSTrack——一种确保动态系统的安全导航工具

    首先观看→https://www.youtube.com/watch?v=KcJJOI2TYJA 问题:快速和安全的运动规划 实时自主的运动规划和导航是很困难的...

    AiTechYun
  • 快速安全追踪(FaSTrack):确保动态系统的安全实时导航

    实时自主运动和导航是很难的,特别是当我们关心安全性时。当我们的动力系统复杂,以及外部干扰(如风)和先验条件未知时,这变得更加困难。我们在这项工作中的目标是为了保...

    人工智能资讯小编
  • ROS(indigo)RRT路径规划

    源码地址:https://github.com/nalin1096/path_planning

    zhangrelay
  • 工业机器人太笨,Mujin公司试图让他们变聪明

    “机器人将会改变世界!”“未来是属于机器人的!”最近,包括 Google Venture 在内的一些美国硅谷投资机构一再重申这样的言论,然而在通往机器人普及道路...

    机器人网
  • 伯克利人工智能研究:FaSTrack——一种确保动态系统的安全导航工具

    AiTechYun 编辑:Yining 首先观看→https://www.youtube.com/watch?v=KcJJOI2TYJA 问题:快速和安全的运动...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券