专栏首页机器人技术与系统RobotRRT算法的基本程序模块(2)
原创

RRT算法的基本程序模块(2)

RRT 效果图

承接上一节,在接下来的几篇文章中,作者将详细解剖机器人的避障路径规划算法。

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

RRT算法中包含了一些基本的函数模块,用于完成整个路径搜索过程。

采样:对应函数Sampling

Sampling函数中,首先在构型空间X中随机取一个点,这些采样点需要服从相互独立,恒等分布,为了简化,采样点需要满足均匀分布,同理,SampleFree就是在自由空间X_{free}中随机采样,并且满足与Sampling相同的要求。

最近节点 : 对应函数Nearest

给定一个图G(V,E)V属于XE表示将节点集V中两个相连的边, 定义函数Nearest: (G,x)-> v \in V ,定义距离的衡量函数

距离函数

附近节点: 对应函数Near

给定图G=(V,E),点x \in X, 正实数r \in R. 定义Near: (G,x,r)->V'

附近节点函数,球域

前进一个步长 : 对应函数Stearing

给定x,y \in X,正实数step \in R, 定义函数Stearing如下:

Stearing(x,y,z):={z:z=x+step(y-x)/|y-x|}

其中,是以x为起点。

碰撞检测: 对应函数 CollisionFree

给定点x,x' \in X, {Y:y \in Y,y=x+t(x‘-x),t \in [0,1]}. 如果Y属于X_{free},则函数CollisionFree(x,x’)返回值True, 即无碰撞,否则返回False,即有碰撞。如果,x属于X_{free}, 则函数CollisionFree(x,x’)返回True, 否则返回False.

到达目标构型

给定目标构型x_{goal},任一构型x \in Xerror \in R, 如果||x_goal-x||<error, 则构型x 落在了目标区域内。这个条件也适用于判断两个树形结构的图是否相遇。

RRT 的伪代码

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    计算机视觉联盟
  • 这可能是史上最全的 Python 算法集(建议收藏)

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

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

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

    Python数据科学
  • 自动驾驶中的决策规划算法概述

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

    美团无人配送
  • 「万字综述」自动驾驶决策控制及运动规划方法「AI核心算法」

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

    用户7623498
  • 这可能是史上最全的Python算法集!

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

    AI科技大本营
  • RRT: 机器人路径规划RRT算法(1)

    RRT*算法是一种基于随机采样的路径规划方法,不仅具有概率完备性,还具有渐进优化能力。假设 代表 维构型空间,

    ZC_Robot机器人技术
  • 路径规划算法简介

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

    六四零
  • ROS功能包- RRT_exploration使用RRT随机数进行地图探测

    1 ROSwiki:http://wiki.ros.org/rrt_exploration

    zhangrelay
  • ROS和RRT的一些资料

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

    zhangrelay
  • 机器人相关学术速递[8.19]

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

    公众号-arXiv每日学术速递
  • 用于移动机器人路径规划的优化通知随机树(cs.RO)

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

    Sie
  • 不确定条件下城市空中交通运营的风险有界路径规划

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

    用户8839980
  • 二值图像分析案例精选

    最近一直有人在知识星球上向我提问很多二值图像分析相关的问题,特别选择了两个典型的轮廓分析问题。进行分析与编码实现与演示,废话不多说,先看第一个问题。

    OpenCV学堂
  • 捕捉深度神经网络中的不确定性,实现自主驾驶车辆的安全运行(cs.RO)

    基于深度神经网络(DNN)的感知和车辆运动的不确定性对安全自动驾驶车辆的发展构成了挑战。在本文中,我们提出了一个安全的运动规划框架,其特点是对基于深度神经网络的...

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

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

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

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

    人工智能资讯小编
  • 伯克利人工智能研究:FaSTrack——一种确保动态系统的安全导航工具

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

    AiTechYun
  • 机器人相关学术速递[9.3]

    【1】 Learning Language-Conditioned Robot Behavior from Offline Data and Crowd-So...

    公众号-arXiv每日学术速递

扫码关注云+社区

领取腾讯云代金券