快速探索随机树-RRT

文章目录

  • 简介
  • 原理
  • 算法
  • 运动规划的变体和改进

简介

快速探索随机树(RRT)是一种算法,旨在通过随机构建空间填充树来有效搜索非凸高维空间。该树是从搜索空间随机抽取的样本中逐步构建的,并且本质上偏向于向问题的大型未搜索区域生长。RRT 由 Steven M. LaValle 和 James J. Kuffner Jr. 开发。它们可以轻松处理障碍物和微分约束(非完整和动力学)问题,并已广泛用于自主机器人运动规划。

RRT可以看作是一种为具有状态约束的非线性系统生成开环轨迹的技术。RRT 也可以被视为一种蒙特卡洛方法,用于将搜索偏置到配置空间中图的最大 Voronoi 区域。有些变化甚至可以被认为是随机分形。

RRT 可用于计算近似控制策略,以控制具有状态和动作约束的高维非线性系统。

原理

RRT 通过使用搜索空间中的随机样本,来生长植根于初始配置的树。 在绘制每个样本时,会尝试与树中最近的状态之间建立连接。 如果连接是可行的(完全通过自由空间并服从任何约束),则新状态添加到树中。 通过对搜索空间进行均匀采样,扩展现有状态的概率与其 Voronoi 区域的大小成正比。 由于最大的Voronoi地区属于搜索前沿的state,这意味着这棵树优先向大片未搜索区域扩展。

树与新状态之间的连接长度通常受到生长因子的限制。 如果随机样本离树中的最近状态比此限制允许的更远,则使用从树沿线到随机样本的最大距离处的新状态,而不是随机样本本身。 然后,随机样本可以被视为控制树木生长的方向,而生长因子决定其生长速度。 这保持了RRT的空间填充偏差,同时限制了增量增长的大小。

通过增加从特定区域采样状态的概率,可以对RRT增长产生偏差。 RRT 的大多数实际实施都利用这一点来指导对规划问题目标的搜索。 这是通过在状态抽样过程中引入对目标进行小概率抽样来实现的。 这种概率越高,树就越贪婪地朝着目标生长。

算法

对于通用配置空间 C,伪代码中的算法如下:
在这里插入图片描述
在上面的算法中,“RAND_CONF”在 C 中获取随机配置 q r a n d q_{rand} qrand。这可以替换为函数“RAND_FREE_CONF”,该函数使用 C

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547253.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Unity 扩展自定义编辑器窗口

在Assets文件夹路径下任意位置创建Editor文件夹,将扩展编辑器的代码放在Editor文件夹下 生成编辑器窗口 代码中首先引用命名空间 using UnityEditor; 然后将创建的类继承自EditorWindow public class MenuEditor : EditorWindow 然后通过扩展编辑器菜单功能调用…

Jackson 2.x 系列【24】Spring Web 集成之 Jackson2ObjectMapperBuilder

有道无术,术尚可求,有术无道,止于术。 本系列Jackson 版本 2.17.0 源码地址:https://gitee.com/pearl-organization/study-jaskson-demo 文章目录 1. 前言2. Spring Web3. Jackson2ObjectMapperBuilder3.1 成员属性3.2 静态方法3…

FMEA分析

目录 1、FMEA的核心目的 2、FMEA的种类 3、FMEA的实施步骤 4、FMEA的SOD等级 5、FMEA的例子 FMEA(Failure Modes and Effects Analysis,失效模式与影响分析)是一种预防性的可靠性设计分析,用来确定潜在失效模式及其原因。它主…

IDEA使用SCALA

一、在IDEA中下载插件 在设置->插件中找到scala,并下载。 下载完成后重启idea 二、在idea中创建spark的RDD操作项目 新建项目选中Scala。 创建完成后为项目添加java包,这个添加的是spark安装包中jars目录下的所有jar包 然后编写RDD操作 import or…

安全中级-初开始

一、网络基础 重要点:TTL值(防环,linux64.Windows128 ),IP数据包包头格式字节(20) 标识标志偏移量起到什么作用(数据超过1500会分片) wireshack抓包会有一个MSS&#x…

铭飞 MCMS 存在SQL注入漏洞

声明: 本文仅用于技术交流,请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失,均由使用者本人负责,文章作者不为此承担任何责任。 简介 铭飞(MCMS)是一种计算机管理…

Opencv3.4+FFMpeg3.4+pkg-config交叉编译arm开发板

Ubuntu16.04 64位 FFmpeg3.4 OpenCv3.4 一、下载FFmpeg https://github.com/FFmpeg/FFmpeg 1.配置 ./configure --prefix/home/zeng/ffmpeg_install --enable-cross-compile --cross-prefixarm-linux-gnueabihf- --ccarm-linux-gnueabihf-gcc --target-oslinux --cpuco…

算法课程笔记——排序

Bool返回真假 为何用const不用define 1.保护被修饰的东西 2.通常不分配存储空间, 效率高 匿名函数只在一处用,其他处用不到 不写&就是拷贝 u相等就u,不等就v 一个字符是空格一个是换行,后面是取下标i那就是1(true&…

图解数学:拉格朗日松弛方法的直观理解

昨晚写了拉格朗日松弛方法的原理分析,今天意犹未尽,图解一下,从直观上进一步理解这种方法。 一、一个简单例子 我们先来看一个简单的例子,下面数学规划问题没有约束条件: min ⁡ f ( x ) − x 2 8 x − 10 \begin…

全排列问题

日升时奋斗,日落时自省 目录 1、全排列 2、全排列II 3、子集 4、组合 1、全排列 首先要了解全排列是怎么样的 例如:数组[1,2,3]的全排列(全排列就是不同顺序排列方式) 例子所有的排列方式如:[1,2,3],[1,3,2],[2,1,3],[2,3…

Leetcode876_链表的中间结点

1.leetcode原题链接:. - 力扣(LeetCode) 2.题目描述 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入:head [1,2,3,4,5…

PTA 编程题(C语言)-- 判断素数

题目标题: 判断素数 题目作者 陈越 浙江大学 本题的目标很简单,就是判断一个给定的正整数是否素数。 输入格式: 输入在第一行给出一个正整数N(≤ 10),随后N行,每行给出一个小于…

康耐视visionpro-CoglntersectLineLineTool操作说明工具详细说明

◆CogIntersectLineLineTool功能说明: 创建两条线的交点 备注:在“Geometry-Intersection”选项中的所有工具都是创建两个图形的交点工具,其中包括圆与圆的交点、线与圆的交点、线与线的交点、线与圆的交点等,工具使用的方法相似。…

C++ - set 和 map详解

目录 0. 引言 1. 关联式容器 2. 键值对 3. 树形结构 4. set 4.1 set 的定义 4.2 set 的构造 4.3 set 的常用函数 4.4 set 的特点 5. multiset 5.1 multiset 插入冗余数据 5.2 multiset - count 的使用 6. map 6.1 map 的定义 6.2 map 的构造 6.3 map的常…

dcoker+nginx解决前端本地开发跨域

步骤 docker 拉取nginx镜像跑容器 并配置数据卷nginx.conf nginx.conf文件配置 这里展示server server {listen 80;listen [::]:80;server_name localhost;#access_log /var/log/nginx/host.access.log main;location / {# 当我们访问127.0.0.1:8028就会跳转到ht…

软件2班20240415

快速引用类选择器 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevi…

二进制离散无记忆对称信道

目录 引言 二进制离散无记忆对称信道 引言 在无线通信中&#xff0c;信源与信宿是分开的&#xff0c;两者间的通信环境的复杂度通常会随着距离 的增加而提升。信道是用来连接信源与信宿的媒介。信源与信宿之间的信息传递则需要 借助于信道&#xff0c;因此信道质量的优劣通常…

移动端web适配方案

以下是移动端适配的多个方案&#xff0c;也可以说说你是怎么做的。 正文 自适应&#xff1a;根据不同的设备屏幕大小来自动调整尺寸、大小 响应式&#xff1a;会随着屏幕的实时变动而自动调整&#xff0c;是一种更强的自适应 为什么要做移动端适配&#xff1f; 目前市面上…

【深度剖析】曾经让人无法理解的事件循环,前端学习路线

先自我介绍一下&#xff0c;小编浙江大学毕业&#xff0c;去过华为、字节跳动等大厂&#xff0c;目前阿里P7 深知大多数程序员&#xff0c;想要提升技能&#xff0c;往往是自己摸索成长&#xff0c;但自己不成体系的自学效果低效又漫长&#xff0c;而且极易碰到天花板技术停滞…

Redis入门到通关之ZSet命令

文章目录 ⛄概述⛄常见命令有⛄RedisTemplate API❄️❄️ 向集合中插入元素&#xff0c;并设置分数❄️❄️向集合中插入多个元素,并设置分数❄️❄️按照排名先后(从小到大)打印指定区间内的元素, -1为打印全部❄️❄️获得指定元素的分数❄️❄️返回集合内的成员个数❄️❄…