精华内容
下载资源
问答
  • 无人驾驶常用路径规划

    千次阅读 2019-07-30 16:56:47
    无人驾驶系统介绍行为决策运动轨迹规划路径规划的不同之处路径规划的定义路径规划方法全局路径规划Dubins路径方法Dubins路径改良算法局部路径规划模糊逻辑算法基于行为的路径规划算法基于再励学习的路径规划算法基于...

    原地址: https://blog.csdn.net/qq_30683329/article/details/85859096
    无人驾驶系统介绍

    • 行为决策
    • 运动轨迹规划
    • 无人驾驶系统介绍

      无人驾驶系统非常复杂,由多个模块组成,例如感知、融合、规划、控制、定位等等组成。其中规划主要包括行为决策、运动轨迹规划等等。
      自动驾驶子系统结构图

      行为决策

      行为决策是人们在行动之前按照某些行为准则在若干可行备选方案中选择或判断某种最佳行动方案的思维活动。
      行为决策系统根据驾驶员的任务请求以及车辆的行驶状态和环境感知信息,对任务进行优先级排序,对车辆的驾驶行为,包括换道、超车和躲避障碍物等进行决策,并将行为决策的结果传给运动轨迹规划系统。

      运动轨迹规划

      运动轨迹规划系统根据行为决策的结果以及车辆的行驶状态和环境信息,考虑时间因素,规划出车辆的行驶轨迹。规划的轨迹包括和时间相关的速度、加速度、行驶时间、燃油消耗量等状态和控制量,并将轨迹信息传给运动控制系统,运动控制系统接收到规划轨迹的详细信息以后,对车辆的姿态进行控制使其沿着规划轨迹进行循迹行驶,以达到对智能车辆自动控制的目的。
      规划和控制系统

      运动轨迹规划是运动控制的前提。因此,要对某种驾驶行为实施控制,首先要根据车辆的行驶状态和道路信息规划出期望的运动轨迹,并从中提取需要的轨迹参数提供给后续跟踪控制器,以便于控制器能够控制车辆按照规划的轨迹行驶。
      运动轨迹规划一般首先生成路径,然后在路径的基础上考虑时间因素及车辆的运动学和动力学模型,通过平滑和速度规划等步骤得到开环的运动轨迹。但是对车辆沿着规划轨迹行驶的稳定性分析也存在一定的困难,即运动控制能否控制车辆准确地沿着规划轨迹行驶而不发生侧滑或侧翻等达不到行驶稳定性要求的问题。

      路径规划的不同之处

      运动轨迹规划与路径规划是有所区别的,路径规划主要是生成从起点到终点不发生碰撞的静态几何轨线,不包含时间概念;而轨迹规划考虑时间因素,生成的不仅是轨迹,还包括车辆行驶速度、加速度、行驶时间和燃油消耗量等状态和控制参数。
      车辆运动控制的主要任务是利用对车辆速度和方向的控制实现车辆位姿对规划轨迹的快速跟踪,并对车辆沿着规划轨迹行驶的状态和控制参数的响应参数进行闭环反馈,使得车辆能够准确沿着规划轨迹进行循迹行驶。

      路径规划的定义

      路径规划方法是在障碍物环境下,按照一定的评价标准规划出一条从起始状态(位置,姿态)到目标状态的无碰路径,主要考虑局部移动主体和障碍物之间的几何关系,找到一条不发生碰撞的路径。路径是一条静态的几何轨线,不包含时间概念,通常表示智能车辆在笛卡尔坐标下的位置和姿态关系。
      根据智能车辆对环境信息掌握的程度,路径规划可以分为两种:

      1. 环境信息完全已知的全局路径规划
      2. 环境信息完全未知或部分未知,通过传感器在线对智能车辆的行驶环境进行感知,以获取障碍物的位置形状和尺寸等信息的局部路径规划

      路径规划方法

      在无人驾驶或者机器人路径规划总,路径规划其实在广义上分为两种:

      1. 全局路径规划–这种路径规划就跟你在高德地图上的导航一样,规划了全局范围的、从起点到终点的行驶路径
      2. 局部路径规划–在全局路径规划的基础上,当你想要躲避障碍物、变道、超车等等操作时,就会涉及到局部路径规划技术,通过局部路径规划,可以使得无人驾驶汽车更加平稳的度过这些操作

      全局路径规划

      全局路径规划方法有 Dubins 路径及其改进算法、可视图法和单元分解法等方法。

      Dubins路径方法

      Dubins路径是生成光滑路径最常用、最广泛、最出名的一种方法。其表示机器人向前行驶的最短路径,通过两个圆弧和直线段组成,其中直线段部分是对应的圆弧的切线。
      但是这个方法有个很大的缺点,那就是在圆弧和直线的连接点处不连续,如果想要精确按照预先设定好的路径行驶,就必须要在连接点处停下来,然后原地转弯,再开始行驶。这对于无人驾驶来说,是完全无法接受的!!

      Dubins路径改良算法

      后来Scheuer等大佬在Dubins路径规划算法上进行了改良,使得行驶路径由原来的圆弧+直线变成了圆弧+直线段+CC(Continous Curvature)转向路径 ** 3段组成,圆弧和直线段之间使用CC转向路径进行相连,这样就避免了路径在连接点处不连续,需要原地停下来转向的尴尬出现。
      CC转向路径是一种特殊的螺旋曲线,它的曲率随着曲线长度的变化而变化,但是
      曲率一直是连续变化的**。但是其生成的路径在长度上有可能就不是最短的了,而且生成的路径曲线的坐标(x,y)无法直接闭环来表示,只能通过对曲线长度s进行积分得到,计算成本较大。

      局部路径规划

      局部路径规划有人工势场法、模糊逻辑算法和基于行为的路径规划算法等方法。

      模糊逻辑算法

      模糊逻辑算法主要是对驾驶员的驾驶经验进行模拟,将驾驶员生理上的感知和行为动作进行结合,然后根据传感器提供的信息,通过查表可以得到规划轨迹的信息。
      该算法最符合人类的思维习惯和行为特点,能够很好的体现出跟人驾驶行为上的一致性。但是由于太过于模糊的设计函数,导致该方法主要依赖人的经验和试验,总结、量产十分困难。且一旦模糊规则制定后,再次想要调整起来困难重重。因此业界的主要用法都是讲其余其他逻辑方法相结合使用。

      基于行为的路径规划算法

      基于行为的路径规划算法是把机器人需要完成的任务进行分解成一些简单的行为单位,机器人根据行为的优先级以及需要完成任务作出适当的反应。
      但是由于是对任务进行了分解,所以对于不同的行为来说需要完成不同的目标,不同的行为之间经常会产生冲突。此时就需要使用仲裁机制来对这些行为进行仲裁协调,谁先谁后。落实到具体操作上时,同一时刻只能有一个行为或者任务在被执行,行为按照不同的执行顺序组合成了一个完整的任务。
      该方法实时性很强,且非常灵活,但是缺点是在多种行为模式下,它的系统对于正确判断的概率会降低。

      基于再励学习的路径规划算法

      基于再励学习的路径规划算法来源于行为心理学,用动物学习心理的“试错法”原理,对机器人在未知环境中移动的路径进行规划。
      此方法利用评价性反馈信号在与环境的交互反馈中进行学习,为实现智能系统的自学习能力提供有效手段。由于再励学习不需要先验知识和环境模型,也不需要样本训练数据,主要是通过与环境的直接交互进行学习,能够在线实现,所以对环境模型不确定的系统比较适用。但是此算法由于需要与环境进行直接交互,计算量较大

      基于仿生学的路径优化算法

      该方法准要是模拟一些生物上的生理特点进行的算法,如遗传算法、CNN、蚁群优化、栗子滤波等等。

    展开全文
  • 移动机器人路径规划方法概览

    千次阅读 多人点赞 2019-09-03 23:20:44
    路径规划方法综述概述主要方法基于图搜索的方法DijkstraA*状态栅格法基于采样的搜索方法Rapidly-Exploring Random Tree (RRT) 概述 路径规划的过程大致如下图所示,信息获取-感知-通信-决策-控制-执行。 主要方法 ...

    概述

    在路径规划中,几个名词的含义为:

    完备性:是指如果在起始点和目标点间有路径解存在,那么一定可以得到解,如果得不到解那么一定说明没有解存在;

    概率完备性:是指如果在起始点和目标点间有路径解存在,只要规划或搜索的时间足够长,就一定能确保找到一条路径解;

    最优性:是指规划得到的路径在某个评价指标上是最优的(评价指标一般为路径的长度);

    渐进最优性:是指经过有限次规划迭代后得到的路径是接近最优的次优路径,且每次迭代后都与最优路径更加接近,是一个逐渐收敛的过程;
    在这里插入图片描述
    路径规划的过程大致如下图所示,主要包括信息获取-感知-通信-决策-控制-执行,一般狭义的路径规划指的是决策部分。
    在这里插入图片描述

    主要方法

    基于图搜索的规划方法

    基于图搜索的方法是最常见的路径规划方法,不仅在机器人,甚至在网络中(如路由的寻路转发中)也有广泛的应用。
    几种经典的方法,包括Floyd,Bellman-Ford,Dijkstra,A*我在这里就不赘述了,相关的资料以及十分齐全了。这里主要介绍一些A*的改进版。

    D*

    D*是Anthony Stentz 1994年发表在ICRA上的, Optimal and Efficient Path Planning for Partially-KnownEnvironments 。关于D*算法我之前写了一篇博客,感兴趣可以戳链接。相比A-star算法,D-star的主要特点就是由目标位置开始向起始位置进行路径搜索,当物体由起始位置向目标位置运行过程中,发现路径中存在新的障碍时,对于目标位置到新障碍之间的范围内的路径节点,新的障碍是不会影响到其到目标的路径的。新障碍只会影响的是物体所在位置到障碍之间范围的节点的路径。通过将新的障碍周围的节点加入到Openlist中进行处理然后向物体所在位置进行传播,能最小程度的减少计算开销。D*路径搜索的过程和Dijkstra算法比较像,A-star算法中f(n)=g(n)+h(n),h(n)在D-star中并没有体现,路径的搜索并没有A-star所具有的方向感,即朝着目标搜索的感觉,这种搜索更多的是一种由目标位置向四周发散搜索,直到把起始位置纳入搜索范围为止,因此,D_star算法虽然能够在障碍物发生变化时找到一条路径,但不一定是一条最短的路径

    LPA*

    Lifelong Planning A*是Sven Koenig 和 Maxim Likhachev在2004发表在Artificial Intelligence上的。这个方法在A*的基础上,加了一步对cost变化的处理。定义了一个rhs函数
    在这里插入图片描述
    rhs函数的作用是通过前瞻一步的方式来判断cost的变化。同时定义了三种状态
    在这里插入图片描述
    处于局部一致状态就是说明环境中的最短路径没有发生改变,处于过一致状态说明可以通过改变父节点降低当前的cost,处于欠一致状态则说明由于某个父节点的cost发生变化导致最短路径的cost变大,需要重新规划。伪代码中对应的是下图红框部分
    在这里插入图片描述
    主要思想是当某个节点不可达时,将以其为父节点的子节点放入U中重新考察,同时利用之前探索的部分继续向目标拓展,直到重新规划出一条可以到达目标的路径。因为这一类方法是通过对以前搜索的信息进行再利用来减少搜索空间,所以又称为增量式搜索。
    LPA*和A*一样,可以通过启发函数来减少搜索空间,同时可以解决环境发生变化的情况。缺点就是,同D*不同,它是从起点向终点搜索,这就意味着,当机器人移动后,他必须重新计算启发函数再进行搜索,会造成很大的浪费。

    D* Lite 和Field D*

    D* Lite还是上面两个老哥在2005年发表在Trans of Robotics上,Fast Replanning for Navigation in Unknown Terrain
    为了解决之前所说的LPA的问题,很自然地想到是否可以将LPA和D结合起来,没错,这就是D Lite。D* Lite 的逻辑基本和LPA*差不多,不过是从终点向起点扩展,这里也不多介绍了。不过科研就是发现问题和解决问题,很快,又有人提出新的问题了,基于图的方法总是将图划分成栅格,再在栅格中心移动,这样实际限制了机器人的移动。举个例子,下图机器人从左下到右上肯定是走红线比较近,但是如果按照图搜索每次移动一个栅格来规划的话,得到的路径就是蓝线。
    在这里插入图片描述
    那理所应当的想法就是不一定非要走栅格中心,这就是Field D*了,2005年由David Ferguson 和 Anthony (Tony) Stentz 提出,主要思想是我不用之前那种从一个中心到另一个中心来计算cost了,我换成从一个中心到边界,再从边界到另一个中心的方式。这样,就可以规划出红线了。
    在这里插入图片描述
    总的来说,基于图的搜索方法都需要全局信息。如果你没有所有的信息,A*可能会出错;D*的贡献在于,它能纠正那些错误而不用过多的时间。LPA*用于代价会改变的情况。在A*中,当地图发生改变时,路径将变得无效;LPA*可以重新使用之前A*的计算结果并产生新的路径。然而,D*和LPA*都需要很多内存——用于运行A*并保存它的内部信息(OPEN和CLOSED集,路径树,g值等),当地图发生改变时,D*或者LPA*会告诉你,是否需要就地图的改变对路径作调整。在一个有许多运动者的物体的游戏中,你经常不希望保存所有这些信息,所以D*和LPA*在这里并不适用。它们是为机器人技术而设计的,这种情况下只有一个机器人——你不需要为别的机器人寻路而重用内存。

    基于采样的规划方法

    图搜索的基于遍历或者改进遍历的逻辑,对于高维的情况,比如多自由度机械臂等情况,很容易出现指数爆炸。而且,在实际场景中,能找到最优的路径固然是最好的,但更多的情况是,能找到一条次优或者可行的较优路径就行。这种情况下,基于采样的规划方法应运而生,其中最典型的就是PRM和RRT。

    Probabilistic Roadmap Method (PRM)

    PRM全称是Probabilistic Roadmap Method,上世纪90年代初由M.H.Overmars等人提出的,伪代码如下
    在这里插入图片描述
    算法十分简洁有效,主要思想是现在全局建立一个道路拓扑图,然后利用这些道路拓扑来规划路径。好比全国修了若干条铁路,之后不管你要去哪,只要上离起点最近的车站,再在终点附近的车站下车即可。
    在这里插入图片描述
    缺点也很明显,首先很难保证最优,其次,路径的性能很大程度取决于生成道路图的质量,而道路图的质量又和节点数以及边数相关,也就是算法中的n和k,一个典型的trade-off问题。

    Rapidly-Exploring Random Tree (RRT)

    RRT算法的伪代码如下
    在这里插入图片描述
    核心思想是每次随机从全局选中一个点,并使随机树向该方向生长,当到达终点或者终点附近时停止生长。单向的随机树其实效率并不高,而且对特定情况效率很差,比如下图所示狭窄路口
    在这里插入图片描述
    对RRT的改进一般从以下三个方面着手
    1)如何选取随机点?
    2)如何选择距离?
    3)如何扩展随机树?
    第一个问题很好理解,完全随机肯定是低效的,最简单的逻辑就是往终点优先选取。第二个问题可以体现RRT的一个优点,能够考虑机器人的非完整约束(如车辆的最大转弯半径和动量等),在图搜索中,无论用欧式距离,曼哈顿距离或者切比雪夫距离等,其实影响不太大。但是考虑下图情况
    在这里插入图片描述
    以差分机器人为例,前进显然是最容易实现的,原地转向则需要考虑转弯半径,侧向移动则是完全无法实现。那么单纯用欧式距离显然是不合理的,一种朴素的想法是通过剪枝把不合理的边裁掉,但是在代码中也不是特别好实现,另一种常见的方法是对不同的移动通过赋予不同的权值,来尽量避免不合理的运动。
    第三个问题,如何扩展?扩展距离过大,容易造成震荡,过小则增大了计算量。
    对RRT的改进有两种比较经典的方法,RRT Connected和RRT*

    RRT connected/Bi-RRT

    为了使随机树能迅速扩展到终点附近,采取双向搜索的方法(这个思想很常见,Dijkstra和A*也有类似的改进)。不过这里还是有一个小细节,起码一开始是我没想到的。双向搜索正常逻辑就是随机取一个点,然后两棵随机树往该处生长,直到相遇或者小于一定阈值。这样做虽然是比单随机树要快,但是还有很大改进空间,因为随机取点很可能并不是我们要拓展的发现,最好的逻辑是什么呢?就是我下图红框处,既然已经找到一个中间节点,那么我就铆足了劲往这冲就对了,直到遇见障碍物或者相交。
    在这里插入图片描述
    当然,这样做的弊端是什么呢?RRT本身会拓展出一些绕远路的路径,而上述这种死循环会无限放大错误的路径。那怎么办呢?于是就有人提出了一种办法,我每次拓展完都修剪一下,把cost优化一下,这样最后得到的路径起码是较优的,这就是RRT*。

    RRT*

    伪代码如下
    在这里插入图片描述
    具体来讲,RRT*做了两件事,也就是上面红框的部分
    下图中的序号表示随机树拓展的顺序,9号是新拓展的,原始父节点为4号,我们以9号为圆心,半径为事先设好的参数,画圆。
    1)试着将9号挂到圆内的其他节点上,最后留下使9号cost最小的,作为新的父节点,并替换原边,比如这里为5号。
    在这里插入图片描述
    2)还是在该圆范围内,若其他节点以9号为新的父节点可以降低cost,则替换其原父节点,如下图中的6号。
    在这里插入图片描述
    我们之所以将RRT*称作渐近最优原因就是,当节点足够多,迭代次数足够多的时候,RRT*是可以收敛到全局最优的。

    Interpolating Curve Planners 插值曲线规划

    插值法主要是利用计算机图形技术来对一系列的路标点形成的路径做平滑处理。逻辑就是在已知一系列轨迹点的情况下,考虑动力学约束和环境约束,利用一些曲线生成一条可行的平滑的路径。
    常见的插值曲线有

    直线和圆

    这个方法比较直观,假设有若干个点,直线没啥好说的,圆的话,只要相邻三个点不共线,总能找到一段圆弧同时过这三个点。

    回旋曲线

    回旋曲线一般设置在直线与圆之间或大圆与小圆之间,由较大圆向较小圆过渡的一种曲线,在道路设计中应用较为广泛。回旋曲线的曲率半径连续变化,曲率变化速率可依据需要灵活设置,能平稳的在直线和圆弧之间过渡而不引起曲率的突变。回旋曲线进行路径规划具有以下优点:
    1)曲线曲率连续,无突变
    2)减小了离心力的变化,增加了机器人稳定性;
    回旋线的基本公式为
    R l = s 2 Rl=s^2 Rl=s2
    其中:
    R R R是回旋线上某点的曲率半径
    l l l是该段回旋线上某点到该段起点的曲线长
    s s s为常数参数

    多项式曲线

    常用的是三次曲线和五次曲线,为什么呢?这要考虑实际背景,插值的逻辑是在一系列机器人的轨迹点上做平滑,隐含的条件就是这些点首先机器人是可达的,一系列剧烈震荡的点再怎么平滑也没有用。所以,我们考虑假设有若干个点,我们可能获得哪些条件。比如,起点的初速度,位移肯定为0,终点的速度位移也应该为0,这就是最简单的约束,一共四个条件,对应的就是一条三次曲线
    s ( t ) = a 0 + a 1 t + a 2 t 2 + a 3 t 3 s(t)=a_0+a_1t+a_2t^2+a_3t^3 s(t)=a0+a1t+a2t2+a3t3
    更进一步地,如果对加速度也有相应的约束,那么就可以拟合成一条五次曲线。

    Bezier(贝塞尔)曲线

    考虑一种情况,n个顶点连接成为平滑的曲线。那肯定得在这些顶点之间插值了,最简单的办法是用直线全连起来,当然,如果用上述曲线也行,但这些插值的方法都有一个问题,局部可能是光滑的,整体上未必是平滑曲线,那么是否存在一个曲线方程,根据这个曲线方程来找到这些插值的点,而且这条曲线方程不仅过原来条件中规定的n个顶点,还是全局光滑的。这就是贝塞尔曲线了。如下图所示,锚点(anchor)就是我们要过的顶点,控制点(control)是用来控制贝塞尔曲线的参数。通过调整控制点的位置,可以实现全局光滑。怎么确定这些控制点大家可以参考这个博客

    在这里插入图片描述

    贝塞尔插值的效果这个博主画了很多漂亮的实现。

    总结

    这里主要介绍了三类机器人路径规划方法:基于图搜索,基于采样和基于插值,但是实际上这些方法都有许多局限性,而且目前机器人(甚至自动驾驶)规划考虑的问题越来越接近实际,比如上述方法说是可以动态避障,实际上并不是真动态避障,更多是依赖于先验的环境信息做的决策,而非向DWA那样,实时根据环境改变。另一个点就是实际上除了考虑环境,更多要考虑其他机器人(车辆)的行为,基于行为的预测来做决策,这是更难的。当然,科研有很大一个方向就是没事找事,比如机器人感知受限,控制受限这种,在附加约束情况下去做规划,也是目前许多人做的一个方向。

    参考文献:

    https://www.cnblogs.com/21207-iHome/
    https://blog.csdn.net/lqzdreamer
    A Review of Motion Planning Techniques for Automated Vehicles

    展开全文
  • 自动驾驶路径规划中的实用搜索技术 Frenet框架中动态街道场景的最优轨迹生成 控制 推荐材料 纯追求路径跟踪算法的实现 自主汽车路径跟踪的自动转向方法 Stanley:赢得DARPA大挑战赛的机器人 ApolloAuto / apollo...
  • 基于蚁群算法的三维路径规划算法,结合具体的案例给出了程序分析
  • ROS常用局部路径规划算法比较

    千次阅读 热门讨论 2021-06-07 20:07:39
    本博文主要讨论ROS导航包中集成的局部路径规划算法,DWA、TEB、MPC等算法在使用过程中的各自的优缺点。以下均为自己在使用过程中总结的经验及查阅资料得来,如有理解不到位的地方,还希望在评论区多多讨论。 1. 动态...

    本博文主要讨论ROS导航包中集成的局部路径规划算法,DWA、TEB、MPC等算法在使用过程中的各自的优缺点。以下均为自己在使用过程中总结的经验及查阅资料得来,如有理解不到位的地方,还希望在评论区多多讨论。

    1. 动态窗口法(DWA)

    算法简介:
    DWA算法全称为dynamic window approach,其原理主要是在速度空间(v,w)中采样多组速度,并模拟出这些速度在一定时间内的运动轨迹,并通过评价函数对这些轨迹进行评价,选取最优轨迹对应的速度驱动机器人运动。

    动态窗口法与ROS默认局部路径规划算法TrajectoryPlanner类似,不同之处在于对机器人控制空间的采样:在给定机器人的加速度极限的情况下,TrajectoryPlanner在整个前向模拟周期内从可实现的速度集合中进行采样,而DWA在给定机器人的加速度极限的情况下仅针对一个模拟步骤从可实现的速度集合中进行采样。在实际使用过程中,TrajectoryPlanner和DWA算法效果类似,但是DWA算法更加高效,占用内存更少,所以在这两种算法中间一般直接选择DWA。

    DWA算法在ROS中为dwa_local_planner
    DWA算法分析参考博文DWA算法分析及实现

    优点:

    • 计算复杂度低:考虑到速度和加速度的限制,只有安全的轨迹会被考虑,且每次采样的时间较短,因此轨迹空间较小
    • 可以实现避障:可以实时避障,但是避障效果一般
    • 适用与差分和全向车模

    缺点:

    • 前瞻性不足:只模拟并评价了下一步,如在机器人前段遇见“C”字形障碍时,不能很好的避障
    • 动态避障效果差: 模拟运动轨迹断,动态避障效果差
    • 非全局最优路径: 每次都选择下一步的最佳路径,而非全局最优路径
    • 不适用于阿克曼模型车模

    2. 时间弹性带(TEB)

    算法简介:
    TEB全称为Time Elastic Band,算法浅析参考博文TEB浅析,文中关于eletic band(橡皮筋)的定义:连接起始、目标点,并让这个路径可以变形,变形的条件就是将所有约束当做橡皮筋的外力。关于time eletic band的简述:起始点、目标点状态由用户/全局规划器指定,中间插入N个控制橡皮筋形状的控制点(机器人姿态),当然,为了显示轨迹的运动学信息,我们在点与点之间定义运动时间Time,即为Timed-Elastic-Band算法。通过此方法可以把问题描述为一个多目标优化问题,通过构建超图(hyper-graph),使用g2o框架中的图优化来求解。

    TEB算法在ROS中为teb_local_planner
    TEB算法分析参考以上链接中所列论文如图
    参考论文
    亦可参考博文TEB轨迹优化算法-代码解析
    针对速度障碍模型(VO)参考博文VO避障

    优点:

    • 适用于各种常见车模:如差分、全向、阿克曼模型
    • 有很强的前瞻性: 对前方一段轨迹进行优化
    • 动态避障: 对动态障碍有较好的避障效果,可直接使用其封装好障碍类Obstacle
      如:静态障碍时TEB算法轨迹规划效果
      静态障碍
      当障碍有个0.15m/s向右的速度时,TEB算法轨迹规划效果如下图
      在这里插入图片描述

    缺点:

    • 计算复杂度较大:可通过牺牲预测距离来降低复杂度
    • 速度和角度波动较大、控制不稳定: 源码中是通过两状态之间的距离和角度差及时间差来计算该控制周期内的速度和角速度,使得在控制过程中速度和角度波动较大,如下图所示。在计算资源足够的情况下,提高控制频率可以改善此现象。
      在这里插入图片描述
    • 非全局最优: 但是好于DWA

    改进策略
    针对其控制不稳定问题,主要原因是每个控制周期内,速度变化较大。一种方法是提高控制频率,另一种方法是使用优化的方法,即修改TEB算法的评价函数,把每次速度和角度的变化量除以时间再乘一个代价系数。

    3. 模型预测控制(MPC)

    算法简介
    MPC(Model Predictive Control)与上文提到的DWA和TEB算法不同,MPC只是一个控制器,在自动驾驶领域,其与PID控制器一样,控制器输入包括车辆下一步的运行轨迹,车辆的当前状态,输出是速度和转角。不同之处在于,PID控制器是实时处理当前车辆与目标轨迹的差距来调整输出,使车辆接近目标轨迹,而MPC控制器将未来一个时间段 t 分成 N 个节点,预测每个节点的车辆状态,再调整控制器的输出使车辆尽可能接近参考轨迹。相比于PID控制器的单输入单输出特性,模型预测控制更加适用于多输入多输出的复杂控制系统,可以通过调参,使得车辆的控制更加平稳、更接近于期望轨迹等。

    MPC参考博文基于阿克曼模型和差速模型小车的MPC算法推到及分析
    MPC在ros中为mpc_local_planner

    优缺点:
    目前正在调试MPC,由于现在对MPC的认知还不是太深刻所以具体调试效果及调试经验日后分享,敬请期待。

    展开全文
  • 路径规划方法

    万次阅读 2018-05-14 16:05:00
    作者:小队长的零链接:...根据题主所说的场景,愚以为是在询问在二维二值地图(FREE or OCCUPIED)场景下进行路径规划方法。我看之前有同学在回答的时候配上了这幅图:这幅图上的算法罗列的还是很全面的,体现...
    作者:小队长的零
    链接:https://www.zhihu.com/question/26342064/answer/126834336
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    根据题主所说的场景,愚以为是在询问在二维二值地图(FREE or OCCUPIED)场景下进行路径规划的方法。我看之前有同学在回答的时候配上了这幅图:


    这幅图上的算法罗列的还是很全面的,体现了各个算法的出生顺序。但是并不能很好的对他们进行一个本质的分类。刚刚那位同学说的graph-based和sampling-based的分类方法我感觉有点概念重叠不能够对规划算法进行这样的分类,下面通过自己这一年多的研究和实践对规划算法进行一个简单的分类:

    两大类:
    1. 完备的(complete)
    2. 基于采样的(sampling-based)又称为概率完备的

    一 完备的规划算法


    图为A*算法
    所谓完备就是要达到一个systematic的标准,即:如果在起始点和目标点间有路径解存在那么一定可以得到解,如果得不到解那么一定说明没有解存在。
    这一大类算法在移动机器人领域通常直接在occupancy grid网格地图上进行规划(可以简单理解成二值地图的像素矩阵)以深度优先寻路算法、广度优先寻路算法、Dijkstra(迪杰斯特拉)算法为始祖,以A*算法(Dijstra算法上以减少计算量为目的加上了一个启发式代价)最为常用,近期的Theta*算法是在A*算法的基础上增加了line-of-sight优化使得规划出来的路径不完全依赖于单步的栅格形状(答主以为这个算法意义不大,不就是规划了一条路径再简单平滑了一下么)。
    完备的算法的优势在与它对于解的捕获能力是完全的,但是由此产生的缺点就是算法复杂度较大。这种缺点在二维小尺度栅格地图上并不明显,但是在大尺度,尤其是多维度规划问题上,比如机械臂、蛇形机器人的规划问题将带来巨大的计算代价。这样也直接促使了第二大类算法的产生。

    二 基于采样的规划算法


    图为RRT-connect算法
    这种算法一般是不直接在grid地图进行最小栅格分辨率的规划,它们采用在地图上随机撒一定密度的粒子来抽象实际地图辅助规划。如PRM算法及其变种就是在原始地图上进行撒点,抽取roadmap在这样一个拓扑地图上进行规划;RRT以及其优秀的变种RRT-connect则是在地图上每步随机撒一个点,迭代生长树的方式,连接起止点为目的,最后在连接的图上进行规划。这些基于采样的算法速度较快,但是生成的路径代价(可理解为长度)较完备的算法高,而且会产生“有解求不出”的情况(PRM的逢Narrow space卒的情况)。这样的算法一般在高维度的规划问题中广泛运用。

    三 其他规划算法
    除了这两类之外还有间接的规划算法:Experience-based(Experience Graph经验图算法)算法:基于经验的规划算法,这是一种存储之前规划路径,建立知识库,依赖之进行规划的方法,题主有兴趣可以阅读相关文献。这种方法牺牲了一定的空间代价达到了速度与完备兼得的优势。此外还有基于广义Voronoi图的方法进行的Fast-marching规划,类似dijkstra规划和势场的融合,该方法能够完备地规划出位于道路中央,远离障碍物的路径。答主最近也在研究此类算法相关的工作。


    图为APF(人工势场)算法
    至于D* 、势场法、DWA(动态窗口法)、SR-PRM属于在动态环境下为躲避动态障碍物、考虑机器人动力学模型设计的规划算法。

    最后推荐一本圣经《Planning Algorithms》伊利诺伊大学教授Lavalle于2006年写的这本书,可以网上看看英文原版的,中文版的书我校图书馆还有两本,市面上貌似买不到了。。

    先说到这,以后有时间再谈谈细节。
    展开全文
  • 本文将为大家介绍四种常用路径规划算法,分别是搜索算法、随机采样、曲线插值和人工势场法。1.搜索算法搜索算法主要包括遍历式和启发式两种,其中Dijkstra算法属于传统的遍历式,A*算法属于启发式,在A*算法的...
  • 关于路径规划的几种算法的比较与分析,为解决物流配送的路径问题提供一些帮助或想法
  • 路径规划算法总结

    万次阅读 多人点赞 2019-08-07 13:36:27
    可以证明,只要从起点开始的扩散过程能够遍历到终点,那么起点和终点之间一定是连通的,因此他们之间至少存在一条路径,而由于BFS从中心开始呈放射状扩散的特点,它所找到的这一条路径就是最短路径; 启发式搜索 ...
  • 对于移动机器人中的地图,常见的数据结构包括: 1.栅格地图 将空间中连续的地图在X、Y轴上(3D地图中还包含Z轴)进行离散化,得到一系列栅格,每个栅格只有占据、空闲和未知三个状态。 3D栅格地图 ...
  • 路径规划算法简介

    2021-07-28 17:13:30
    文章目录前言一、传统路径规划算法二、图形学方法三、智能仿生算法四、其他算法总结 前言 移动机器人的自动探索需要对机器人进行路径规划,移动机器人的路径规划问题始于20世纪60年代。路径规划作为机器人导航最...
  • 基于机器人小车运动到定点常用的Tum-Run-Turn控制方法,根据机器人小车的物理特性,设计了一种新的切线路径规划方法。该方法把小车在运动过程中受到的物理特性限制抽象为障碍物,加入到环境中,使得算法简单,计算量...
  • 路径规划五种算法简述及对比

    千次阅读 多人点赞 2021-01-11 10:34:35
    以下是本人在学习路径规划过程中的一些总结,借着机会写了一下,有不妥之处欢迎批评指正,谢谢。 路径规划部分在无人车架构体系当中分属控制或决策部分,如图1,是实现无人化驾驶的关键技术之一。路径规划模块性能...
  • 【导语】:一个实现了机器人技术中常用路径规划算法的开源库,还有动图直观演示运行过程。该库公开时间不长,在 GitHub 已有 1200+ Star。 简介 在机器人研究领域,给定某一特定任务之后,如何规划机器人的运动...
  • 路径规划基本介绍(一)

    万次阅读 多人点赞 2019-04-24 21:30:03
    这里仅针对静态路径规划方法进行简单的介绍,以下路径规划仅指在静态环境下的路径规划。 在进行路径规划的时候,我们首先需要考虑的有以下几个方面: a.起点与终点的位置获取 b.障碍物的环境表示 c.规划方法 d.搜索...
  • 文章目录A 路径规划定义B 构型/位型空间(configuration Space)C 障碍物与构型空间 A 路径规划定义 移动机器人依据某个或某些性能指标(如工作代价最小、行走路线最短、行走时间最短等),在运动空间中找到一条从...
  • matlab路径规划系列

    千次阅读 2021-04-22 18:30:05
    前言:本博客将结合常用路径规划算法进行matlab讲解。一、路径规划问题所需操作1.生成地图告诉电脑你的当前地图环境。比如一个迷宫。这里面就涉及一些图像处理的内容,以及如何把地图转换为matlab数据例子:有一张...
  • 学习笔记之——路径规划

    万次阅读 多人点赞 2020-03-03 12:17:04
    最近在做移动机器人路径规划相关的topic,打算对路径规划算法做一个调研,并写下这篇记录。本博文的大部分内容来源于网络的博客或者论文,相关的参考也会给出来。本博文仅作本人学习记录用。 ...
  • 浅谈路径规划算法

    万次阅读 多人点赞 2017-09-19 16:32:09
    不带路径搜索的运动(movement)可以在很多种情形下工作,同时可以扩展到更多的情形,但是路径搜索是一种更常用的解决更多问题的方法。 1.1 算法 计算机科学教材中的路径搜索算法在数学视角的图上工作——由边联结...
  • 路径规划算法

    2021-11-14 10:20:44
    文章目录前言一、传统路径规划算法1.Dijkstra算法2.A*算法3.D*算法4.人工势场法二、基于采样路径规划算法1.PRM算法2.RRT算法三、智能...移动机器人的路径规划方法主要分为传统的路径规划算法、基于采样的路径规划算法
  • 目前,已经存在很多组合优化算法来解决机器人路径规划问题,但很多算法都存在一定的局限性。而蚁群算法具有正反馈、灵活性和协同性等特点,顺应路径规划算法的研究现状和向智能化、仿生化发展的趋势。因此,本课题拟...
  • 无人驾驶汽车路径规划概述

    千次阅读 多人点赞 2019-07-30 17:18:42
    无人驾驶汽车路径规划概述 原地址:http://imgtec.eetrend.com/blog/2019/100018447.html 无人驾驶汽车路径规划是指在一定的环境模型基础上,给定无人驾驶汽车起始点和目标点后,按照性能指标规划出一条无碰撞、能...
  • 常见路径规划算法介绍

    千次阅读 2021-08-29 21:26:35
    本文介绍了算法书上常见的路径规划算法和工业界目前比较流行的高效分层路径规划算法。 目录 1. 经典路径规划算法 1.1Dijkstra 1.2 Bellman-Ford 1.3 SPFA 1.4A* 1.5Bidirectional Search(双向搜索) 2.分层...
  • 扫地机器人有这些路径规划方法

    万次阅读 2017-03-16 22:08:15
    路径规划技术是扫地机器人研究的核心内容之一,机器人定位与环境地图构建就是为路径规划服务的。所谓机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务...
  • Hello,everyone! 我是CS科研GO,一个热衷于科研和软开的胖子! 论文题目:An Indoor Route Planning Method With Environment ...基于环境感知的室内路径规划方法1. 论文摘要2. 引言3.室内导航网络模型3.1 室.
  • 分析了自主移动机器人路径规划中的常用的几种方法,对于学习机器人路径规划很有价值。
  • 路径规划1

    2020-10-22 17:21:29
    路径规划1 参考博客: ...路径规划的作用: 让目标对象在规定范围的区域内找到一条从起点到终点的无碰撞安全路径。...路径规划方法 a. 栅格表示法 栅格法通过使用大小相同的栅格划分空间环境,并用数组
  • 路径规划基本理论

    千次阅读 2019-05-31 10:10:38
    路径规划有三个组成部分:空间表示、搜索和启发式算法, 空间表示 空间表示意思就是在执行路径规划之前,为目标构建地图环境。执行任何类型的路径规划,都需要先将地图环境离散化为图形。为了提高...
  • 常用的地图导航和路径规划算法

    万次阅读 2018-12-06 19:27:31
    作者:李传学 ...明确一点,基本的图搜索算法dijkstra是无法满足互联网地图检索实时响应这种性能要求,所以各家公司都有各自的预处理方法:分层或者预计算。具体采用何种方式,这取决于采取的加速算法相...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,590
精华内容 15,436
关键字:

常用的路径规划方法