自动驾驶(六十二)---------导航路径规划

2023-11-08 11:20

本文主要是介绍自动驾驶(六十二)---------导航路径规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

    实际上关于路径规划,我在轨迹规划中有介绍,主要是A*算法,但是目前有强需求,所以只能在系统总结一下了,可以算是水一篇文章,抓紧时间吧,有效的时间不多了!

      导航路径规划需要掌握的方法我总结有四个:RRT、PRM、A*、hybrid A*。A*我之前有介绍:再论轨迹规划,这里就不做赘述。

1. RRT

       RRT(快速探索随机树),首先在环境中,我们有一个起始点,定义为Xinit, 然后我们在环境中随机撒一个点,得到点x_rand,如果x_rand不在障碍物区域,则连接起x_init和x_rand, 我们得到一条连线L,如果L整个不在障碍物里面,则沿着L,从x_init向x_rand的方向移动一定的距离,得到一个新的点,x_new,则x_init,x_new和他们之间的线段构成了一颗最简单的树。

       树的扩展: 在开始的基础上,继续重复,在环境中撒点,得到无障碍物区域的点x_rand,然后在已经存在的树上找一个离x_rand最近的点x_near,连接两个点,如果这条线没有障碍物,则沿着这条线,从x_near到x_rand移动一定的距离,得到新的点,x_new, 该点被添加到已经存在的树上

       规划: 重复上述过程,直到目标点(或其附近的点)被添加到树上,这时我们就可以在树上找到一条从起点到目标点的路径

                                               

2. PRM

      RRT当环境中的障碍物较为复杂时计算量较大,有没有什么办法优化呢?PRM(Probabilistic Roadmaps)是一种基于图搜索的方法,一共分为两个步骤:学习阶段、查询阶段。它将连续空间转换成离散空间,再利用A*等搜索算法在路线图上寻找路径,以提高搜索效率。

      学习阶段:在给定图的自由空间里随机撒点,构建一个路径网络图。  必须是自由空间里的随机点,每个点都要确保机器人与障碍物无碰撞。

      查询阶段:根据设定的起点s和终点g,选择合适的路径,首先将s和g点与路径网络中的两个点x,y分别连接,寻找无向路径网络图中x与y连接的路径,这样就可以将起点和终点连接起来,构成全局路径。得到全局路径后,可以使用平滑的方法寻找捷径,优化路径。

                                              

3. Hybrid A*

       A*算法主要是用在导航中,在车辆轨迹规划中并不好用,这是因为生成的轨迹是折线,这不满足车辆运动学特性,但是A*算法也同样是从一个点到另一个点的一条最优路径,有没有办法转化成车辆可以行使的轨迹线呢?

      2010年,斯坦福首次提出一种满足车辆运动学的算法(Hybrid A*),并在(DARPA)的城市挑战赛中得以运用。首先我们采用A*生成一天折线轨迹,节点之间不采用直线相连,而是Reeds-Shepp曲线相连,当然每个节点与节点相连的曲线,要考虑与之相连的节点状态。这样生成的轨迹就是Hybrid A*。那么什么是Reeds-Shepp呢?请看下节:

4. Reeds-Shepp

      APA自动泊车可以有各种轨迹实现,如何用最短路径来实现自动泊车呢?首先假设车辆能以固定的半径转向,且车辆能够前进和后退,那么Reeds-Shepp曲线就是车辆在上述条件下从起点到终点的最短路径。在轨迹规划中不仅要求车辆能够到达终点,而且需要车辆的角度也有要求,比如在垂直泊车的过程中,开始车辆平行于道路,终点要求车辆垂直于道路等等,总之车辆的终点位置和终点角度都提出了要求。

      首先我们回到车辆运动学:

                                其中:

       这种固定的运动方式在低速情况下轨迹可以近似一个圆,方向盘转角转到最大,其转向半径最小,假设最小转向半径为rmin。为了方便起见Reeds-Shepp中最小转向半径强制设置为1,如果车辆的实际最小转向半径不是1,可也通过适当放缩终点坐标来计算该曲线。

      下面曲线就是一条Reeds-Shepp曲线,R表示右打方向,+表示前进,图中从到 ,首先右打方向前进,再左打方向后退,最后右打方向前进到达终点。

                          

      下表是Reeds-Shepp曲线的基本操作方式,一共有48种操作模式,归为9种Base word,但是在编程求解我们不需要每一种都分开求解,其中他们之间的对称性可以帮助我们减少工作量。例如求解到终点  的  后,我们可以用同样的方法来求解 但是需要将终点换为  ,这种处理方法在文中叫timeflip,还有其他的f对称,这里不做介绍可以参看原文。

                      

      通过这几种组合可以得到最短路径。这里举个例子,从不同位置到达同一目标的Reeds-sheep:

                  

这篇关于自动驾驶(六十二)---------导航路径规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369514

相关文章

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

pytorch自动求梯度autograd的实现

《pytorch自动求梯度autograd的实现》autograd是一个自动微分引擎,它可以自动计算张量的梯度,本文主要介绍了pytorch自动求梯度autograd的实现,具有一定的参考价值,感兴趣... autograd是pytorch构建神经网络的核心。在 PyTorch 中,结合以下代码例子,当你

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

Spring Boot项目中结合MyBatis实现MySQL的自动主从切换功能

《SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能》:本文主要介绍SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能,本文分步骤给大家介绍的... 目录原理解析1. mysql主从复制(Master-Slave Replication)2. 读写分离3.

微信公众号脚本-获取热搜自动新建草稿并发布文章

《微信公众号脚本-获取热搜自动新建草稿并发布文章》本来想写一个自动化发布微信公众号的小绿书的脚本,但是微信公众号官网没有小绿书的接口,那就写一个获取热搜微信普通文章的脚本吧,:本文主要介绍微信公众... 目录介绍思路前期准备环境要求获取接口token获取热搜获取热搜数据下载热搜图片给图片加上标题文字上传图片

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》:本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言:详细操作:步骤一:点击上方的 文件(File),点击&nbmyHIgsp;设置(Setti

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新