智能驾驶规划控制理论学习-基于采样的规划方法

目录

一、基于采样的规划方法概述

二、概率路图(PRM)

1、核心思想 

2、实现流程

3、算法描述

4、节点连接处理

5、总结

三、快速搜索随机树(RRT)

1、核心思想

2、实现流程

 3、总结

4、改进RRT算法

①快速搜索随机图(RRG)

②基于运动学的快速搜索随机树(Kinematic-based RRT)


一、基于采样的规划方法概述

        基于采样的方法就是在状态空间中不断地随机撒点,将这些节点根据一定的规则与周围的节点进行连接,以此构造一条条局部路径,最终找到一条从起点到终点的路径。随着采样点的不断增多,最终得到的解会不断逼近最优解。

        一般步骤:

  • 为图表添加随机数种子
  • 以某种策略或者给定条件采样到起始节点
  • 选择和哪些其他节点进行连接
  • 选择添加或者移除哪些边

二、概率路图(PRM)

1、核心思想 

        PRM有两个阶段分别是学习阶段(Learning Phase)和查询阶段(Query Phase)。

        学习阶段:

  • 在配置空间中随机采样足够数量的点;
  • 将相互之间能够到达的节点进行连接。

        查询阶段:

  • 利用图搜索算法寻找图表中从起始节点到目标节点的路径。 

2、实现流程

(a)图中所示为一个用于采样的配置空间,在配置空间中,自动驾驶车辆可以被近似看成一个质点,环境中的障碍物等信息都被近似为图中的forbidden space,自动驾驶车辆在free space空间中运动,二无需考虑其几何形状和运动状态;

(b)图中通过随机采样的方式获得一个坐标点,采样的方法也要根据特定的场景做出不同的选择,常见的采样算法有均匀分布采样(在未知场景中采样)、高斯分布采样(在自动驾驶场景中通常以车道中心线为均值)等;

 (c)图中通过采样大量的点来获取地图的形状;

 (d)图中对采样点进行碰撞检验,删除forbidden space中的采样点;

 (e)图中为删除forbiden space中的采样点后,在free space中保留下来的有效采样点;

  (f)图中每个有效采样点会连接以当前节点为圆心,半径r圆形范围内的所有采样点

 (g)图中若采样点之间的连线与forbiden space相交则发生碰撞,删除发生碰撞的连线;

  (f)图中碰撞检测通过的连线得到保留,作为构成图表graph的边;

 (i)在连线得到的图表graph中添加起始节点和目标节点;

 (j)在graph图中利用图搜索算法寻找最优路径。

3、算法描述

        用伪代码的方式对PRM进行简要描述:

V <- ∅; E <- ∅ // 分别维护两个集合,一个存放顶点,一个存放边
for i = 0,...,n do //假定最大采样点为n,进入循环x <- SampleFree;  //在freespace通过特定的采样策略采样得到一个节点U <- Near(G = (V,E), x, r);  //将节点半径r范围内要专注的邻居节点加入集合U中V <- V ∪ {x}; //将当前采样点x加入集合V中,更新集合Vforeach u in U, in order of increasing ||u - x||, do //对集合U中存入的节点进行处理,为了避免节点过于密集,u和x不能过于接近if x and u are not in the same connected component of G = (V,E) then  // 保证u和x之间的连线与其他连线不重合if CollisionFree(x,u) then E <- E∪{(x,u),(u,x)};  // 通过碰撞检验则将x和u的连线加入集合E
return G=(V,E); // 返回V和E表示的图

        上面是经典的PRM算法描述,也可以对其进行简化:

V <- {x}∪{SampleFree}; E <- ∅;
foreach v in V do U <- near(G=(V,E),v,r)\{v};foreach u in U doif CollisionFree(v,u) then E <- E∪{(v,u),(u,v)}
return G=(V,E);

        主要就是减少了剔除部分节点的步骤,因此在算法实现上效率会降低。

4、节点连接处理

        在PRM实现过程中,选择那些节点相连也是需要考虑的问题,下面给出三种可行的方法:

  • k-Nearest PRM:选择当前节点最近的k个邻居节点

U ← kNearest(G=(V,E),v,k)

  • Bounded-degree PRM:对半径范围内添加的最近节点添加一个边界值k

U ← Near(G,x,r) ∩ kNearest(G=(V,E),v,k)

  • Variable-radius PRM:让连接半径称为对应节点个数的函数,而不是固定的参数

5、总结

        PRM优点:具有概率完备性,只要采样点足够多,并且生成的图表有解那么一定可以结合图搜索算法找到一条最优解路径;

        缺点:

  • 如果是连接特定起点和终点,那么通过PRM的两个阶段先建图在搜索是比较浪费资源的;
  • 搜索得到的路径是节点之间通过直线连接的,不符合车辆的运动学约束。

三、快速搜索随机树(RRT)

1、核心思想

        与PRM有学习和查询两个阶段,并且在学习阶段构造的是一个图不同,RRT只有一个阶段,在采样结束的同时就能确定路径,RRT在采样的过程中维护的是一个树结构。相比图描述的网络关系,树结构描述的是一种层次关系。

        在RRT算法中,通常将起始节点作为树的根节点,在采样搜索到目标节点时通过回溯就可以确定路径。

2、实现流程

        依然使用伪代码对实现流程进行简要描述:

V <- {root}; E <- ∅; // 维护集合V和E,分别存放节点和边,在V中先将初始节点作为根节点放入
for i = 1,...,n doxrand ← SampleFree; // 在freespcace中得到采样点xrandxnearest ← Nearest(G=(V,E),xrand); // 设置离xrand距离最近的树节点为xnearestxnew ← steer(xnearest,xrand); // 通过特定的方式将xnearest与xrand进行连接,此处直接设置了一个中间节点,比较经典的方式设置一段弧长if ObtacleFree(xnearest,xrand) then  // 进行连线障碍物检测V ← V∪{xnew}; E ← E∪{xnearest,xnew};  // 检测通过将边保存到集合E中
return G={V,E};

 3、总结

        优点:如果是找寻找两个特定节点间的路径,RRT的效率会显著地优于PRM;

        缺点:RRT不具备概率完备性,因为它每次都是树的最近节点连接,如下图红色区域中搜索得到的路径显然不是最优解。

4、改进RRT算法

        为了解决RRT算法不具备概率完备性的缺陷,后来又提出了多种改进的RRT算法。

①快速搜索随机图(RRG)
V <- {root}; E <- ∅; 
for i = 1,...,n doxrand ← SampleFree; xnearest ← Nearest(G=(V,E),xrand); xnew ← steer(xnearest,xrand);if ObtacleFree(xnearest,xrand) then Xnear ← Near(G=(V,E),xnew,min{γRRG(log(card(V))/card(V)^(1/d),η); // 将xnew附近给定半径内的所有节点都存入Xnear集合中V ← V∪{xnew}; E ← E∪{xnearest,xnew};foreach xnear in Xnear doif CollisionFree(xnear,xnew) then E ← E∪{xnearest,xnew};  // 将通过碰撞检测的所有Xnear集合中的节点与xnew的连线都存入集合E中return G={V,E};

        核心思想:不仅仅只是连接xnew和xnearest,将xnew半径范围内的所有符合非碰撞条件的节点都连接。

        虽然RRG使得算法具有概率完备性,但是却违背了RRT算法提高效率的初衷,因为RRG算法在实现过程中并没有在维护树结构,输出的依然是一个图,相当于是PRM的学习阶段,还要再利用搜索算法进行最优路径确定。

②基于运动学的快速搜索随机树(Kinematic-based RRT)

        核心思想:利用车辆运动学方法在两个节点之间进行转向,主要在于RRT伪代码中xnew获取步骤的优化。

        上图所示是基于杜宾斯规划(dubins_path_planning)得到的路径,可以看出在引入车辆运动学方法后,得到的最终路径是一条较为平滑的曲线。dubins_path_planning的具体介绍在后面会具体介绍。

        

        

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

postman切换成黑色主题

postman安装以后默认是白色背景&#xff0c;如果想要切换成黑色的&#xff0c;大家可以按照下图箭头指示来操作。 1打开设置 2在Themes页面选择黑色主题

4G 蜂窝移动通信系统

4G 蜂窝移动通信系统 第四代 (4G) 蜂窝移动通信系统 2008 年&#xff0c;名称定为高级国际移动通信 IMT-Advanced (International Mobile Telecommunications-Advanced) 。 IMT-Advanced 的一个最重要的特点&#xff1a;取消了电路交换&#xff0c;无论传送数据还是话音&#…

从 iOS 设备恢复数据的 20 个iOS 数据恢复工具

作为 iPhone、iPad 或 iPod 用户&#xff0c;您可能普遍担心自己可能会丢失存储在珍贵 iOS 设备中的所有宝贵数据。数据丢失的原因多种多样&#xff0c;这里列出了一些常见原因&#xff1a; 1. iOS 软件更新 2. 恢复出厂设置 3. 越狱 4. 误操作删除数据 5. iOS 设备崩溃 …

易货模式微信小程序的可行性分析

随着移动互联网技术的快速发展&#xff0c;微信小程序作为一种轻量级的应用形态&#xff0c;已经成为众多创业者和服务提供者关注的焦点。微信小程序以其便捷的使用体验、较低的开发成本和广泛的用户基础&#xff0c;成为了各类业务模式的创新平台。在这样的背景下&#xff0c;…

c# ABB 机械手上位机连接

c# 程式开发和调试步骤如下&#xff1a; ABB 机械手要开启PC Interface功能。ABB 机械手设定ip地址。设定测试笔记本和机械手同一网段&#xff0c;用网线直连机械手&#xff0c;也可以通过交换机连接机械手。确保笔记本能够ping通和telnet 机械手80端口都是OK的。以上都OK的话…

图神经网络实战——图论

图神经网络实战——图论 0. 前言1. 图属性1.1 有向图和无向图1.2 加权图与非加权图1.3 连通图非连通图1.4 其它图类型 2. 图概念2.1 基本对象2.2 图的度量指标2.2 邻接矩阵表示法 3. 图算法3.1 广度优先搜索3.2 深度优先搜索 小结系列链接 0. 前言 图论 (Graph theory) 是数学…

ifort 自定义命名可执行程序

背景 在Linux上用ifort编译Fortran程序时&#xff0c;想自定义可执行程序的名字 有帖子&#xff08;ifort编译命令&#xff09;说可以使用这个&#xff1a; ifort -c 自定义命名 ***.f90 亲测不行 步骤 ifort ***.f90 &#xff1a; 默认产生的是a.out可执行程序 亲测有效&…

内网穿透 nas/树莓派+ipv4服务器 (ipv6)

nas 1.有个服务器 2.有个nas https://github.com/snail007/goproxy/blob/master/README_ZH.md https://github.com/snail007/proxy_admin_free/blob/master/README_ZH.md 2个官网一个是程序&#xff0c;一个是网站 手册 https://snail007.host900.com/goproxy/manual/zh/#/?i…

KubeEdge 边缘计算

文章目录 1.KubeEdge2.KubeEdge 特点3.KubeEdge 组成4.KubeEdge 架构 KubeEdge # KubeEdgehttps://iothub.org.cn/docs/kubeedge/ https://iothub.org.cn/docs/kubeedge/kubeedge-summary/1.KubeEdge KubeEdge 是一个开源的系统&#xff0c;可将本机容器化应用编排和管理扩展…

「MySQL」增删查改

在操作数据库中的表时&#xff0c;需要先使用该数据库&#xff1a; use database;新增 创建表 先用 use 指定一个数据库,然后使用 create 新增一个表 比如建立一个学生表 mysql> use goods; mysql> create table student(-> name varchar(4),-> age int,-> …

初学JavaWeb开发总结

0 什么是Web开发 Web: 全球广域网&#xff0c;又称万维网(www World Wide Web)&#xff0c;能够通过浏览器访问的网站。 Web开发&#xff0c;就是开发网站的&#xff0c;如&#xff1a;淘宝、京东等等。 1 网站的工作流程 流程&#xff1a; 浏览器先向前端服务器请求前端资…

【计算机网络——应用层】http协议

文章目录 1. http协议1.1 http协议简介1.2 url组成1.3 urlencode与urldecode 2. http协议的格式2.1 http协议的格式2.2 一些细节问题 3. http的方法、状态码和常见响应报头3.1 http请求方法3.2 http状态码3.3 http常见的响应报头属性 4. 一个非常简单的http协议服务端5. http长…

蓝桥杯练习系统(算法训练)ALGO-995 24点

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 24点游戏是一个非常有意思的游戏&#xff0c;很流行&#xff0c;玩法很简单&#xff1a;给你4张牌&#xff0c;每张牌上有数…

LeetCode -- 79.单词搜索

1. 问题描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff0c;其中“相邻”单元格是那些水…

arm板运行程序时寻找动态库的路径设置

问题&#xff1a;error while loading shared libraries: libQt5Widgets.so.5: cannot open shared object file&#xff1f; 第一种方法---- 解决&#xff1a; ①复制需要用到的arm库到板子上。 ②pwd指令获取该库的绝对路径&#xff0c;把路径复制到/etc/ld.so.conf文件 ③输…

Python:练习:编写一个程序,写入一个美金数量,然后显示出如何用最少的20美元、10美元、5美元和1美元来付款

案例&#xff1a; python编写一个程序&#xff0c;写入一个美金数量&#xff0c;然后显示出如何用最少的20美元、10美元、5美元和1美元来付款&#xff1a; Enter a dollar amout:93 $20 bills: 4 $10 bills: 1 $5 bills:0 $1 bills:3 思考&#xff1a; 写入一个美金数量&…

Day06:基础入门-抓包技术HTTPS协议APP小程序PC应用WEB转发联动

目录 HTTP/HTTPS协议抓包工具 Web浏览器抓包 APP应用抓包 WX小程序&PC应用抓包 思维导图 章节知识点&#xff1a; 应用架构&#xff1a;Web/APP/云应用/三方服务/负载均衡等 安全产品&#xff1a;CDN/WAF/IDS/IPS/蜜罐/防火墙/杀毒等 渗透命令&#xff1a;文件上传下载…

lv20 QT对话框3

1 内置对话框 标准对话框样式 内置对话框基类 QColorDialog, QErrorMessage QFileDialog QFontDialog QInputDialog QMessageBox QProgressDialogQDialog Class帮助文档 示例&#xff1a;各按钮激发对话框实现基类提供的各效果 第一步&#xff1a;实现组件布局&…

小(2)型土石坝安全监测设施配置详解

小(2)型土石坝的安全监测是确保大坝稳定、安全运行的重要环节。为此&#xff0c;合理配置安全监测设施显得尤为重要。以下是对小(2)型土石坝安全监测设施配置的详细介绍。 一、渗流量监测 渗流量是反映大坝安全状况的关键指标之一。为准确监测渗流量&#xff0c;我们采用仪器量…

【Android12】Monkey压力测试源码执行流程分析

Monkey压力测试源码执行流程分析 Monkey是Android提供的用于应用程序自动化测试、压力测试的测试工具。 其源码路径(Android12)位于 /development/cmds/monkey/部署形式为Java Binary # development/cmds/monkey/Android.bp // Copyright 2008 The Android Open Source Proj…