精华内容
下载资源
问答
  • 局部路径规划算法
    千次阅读
    2022-06-18 09:52:30

    本文参考Bug算法(Bug Algorithms)简介(Bug1 & Bug2 & Tangent Bug)_nullwh的博客-CSDN博客_bug算法

    原始书籍(PDF) Principles of Robot Motion: Theory, Algorithms, and Implementation ERRATA!!!! 1 (researchgate.net)

    这篇论文主要利用TangentBug与Dubins曲线进行轨迹规划,下面先介绍TangentBug算法的具体细节,以便对论文的理解

    目录

    1 Bug类算法

    更多相关内容
  • 机器人局部路径规划算法——VFH系列论文。主要根据传感器的观测数据,更新占用栅格地图,然后计算下一步的运动方向。
  • VFH*避障/局部路径规划算法

    千次阅读 2021-09-11 12:37:35
    VFH*避障/局部路径规划算法1、VFH+存在的问题——dead-end2、VFH*算法2.1 VFH*算法概述2.1.1 VFH*的参数2.2.2 表示2.2.3 算法步骤2.2 投影位置和方向2.3 代价函数2.3.1 kek_eke​项2.3.2 平滑项2.3.3 折扣因子λ2.4 ...


    做个正直的人

    VFH*是VFH、VFH+两个算法的持续改进,对这两个算法不熟悉的同学,不建议直接看这一篇文章。可以去看我写的两篇介绍VFHVFH+算法的文章。

    先说一下这三个算法的关系。VFH(Vector Field Histogram)的前身是VFF(Virtual Force Field),VFH+是对VFH的改进,VFH*又是对VFH+的改进。也就是下面这样的关系
    V F F > > V F H > > V F H + > > V F H ∗ VFF>>VFH>>VFH+>>VFH* VFF>>VFH>>VFH+>>VFH
    话不多说,直接上干货。

    1、VFH+存在的问题——dead-end

    VFH*之所以要改进VFH+,这是因为VFH+在某些情况下会出现很不希望出现的表现。请看下图,机器人检测到障碍物时,VFH+算法这个时候可以计算出两个可行的前进方向:A和B。VFH+这个时候是有很大的概率会选择A方向前进的。然而,很明显,如果机器人真的沿着A方向前进,那么很快机器人就会发现前方是一个dead-end(死胡同),机器人就不得不改变方向甚至原路返回后沿着B方向前进。
    在这里插入图片描述
    那我们就发现,这种情况下,机器人对待dead-end的表现是很差劲的。那我们就来分析一下,是什么导致机器人难以应对dead-end的呢?

    不难发现,VFH+采用一个圆(实际上是传感器的数据,比如声呐)来检测障碍物,但是这一个圆的半径总归是有限的,这就导致机器人实际上能看到的视野也是十分有限的,那已知信息很少,自然控制效果也就比较差了。那么我们该采取什么手段来解决问题呢?

    我们再来分析一下,VFH+之所以如此,是因为VFH+没有考虑如果真的沿着选择的方向前进后会遇到什么。如果他考虑了,那就有可能及早发现dead-end,从而尽早选择别的路。这就是VFH*算法。

    2、VFH*算法

    2.1 VFH*算法概述

    VFH*所做的改进其实非常少,只有一步,那就是纳入了前瞻距离(Look-ahead),即通过提前探查一下如果真的沿着某一个方向前进会不会遇到dead-end,根据探查的结果,来选择更好的前进方向。

    不过,虽然只是改进了一步,所做的工作却不少。下面我们来具体的描述一下这一个过程。

    VFH*首先也是构建极坐标直方图,然后根据直方图中的openings来确定所有候选的前进方向。只不过VFH*在此时并不急于确定最终的前进方向,而是要沿着每一个方向进行探查。探查的过程类似于A*算法中的expansion操作。

    假如说,机器人确定了N个候选的前进方向,那么以机器人的当前位置为根节点,沿着这N个前进方向进行探查。每一次探查的距离设置为 d s d_s ds(这是探查阶段的第一个重要参数),探查出来的新节点标记为projected node,然后计算该节点处的代价和启发函数值。然后,在新节点处继续探查。一直重复 n g n_g ng次(这是VFH*算法的第二个重要的参数)。

    在探查阶段完成之后,在搜索树中搜索那一条代价最短的路径。这一条路径VFH*算法规划出的避障路径。

    2.1.1 VFH*的参数

    总的说来,VFH*算法有三个主要的参数, d s d_s ds n g n_g ng d t d_t dt,并且这三者之间满足如下关系:
    d t = n g ∗ d s d_t=n_g*d_s dt=ngds

    其中, d s d_s ds每一次探查的距离,建议设置为机器人的直径; n g n_g ng是设定的探查次数,一般设置为2; d t d_t dt总共探查的距离,最好接近机器人传感器的有效检测距离。

    2.2.2 表示

    VFH算法重点关注的是边的方向,因此我们的描述也把重点放在边上。

    我们把机器人当前的位置记为primary node,把探查出来的节点记为projected node,它们有两个属性:position和orientation。

    把在primary node处计算出的候选前进方向称为 primary candidate orientation。

    把在projected node处计算出的候选前进方向称为 projected candidate orientation。

    我们把每一个探查出来的边称为方向段。

    2.2.3 算法步骤

    VFH*算法在节点 i i i处的探查总共分为5步:

    1. 在节点 i i i处,也就是projected position ( x i , y i ) (x_i,y_i) (xi,yi)构建极坐标直方图
    2. 在直方图中确定所有的候选前进方向
    3. 沿着所有的候选前进方向计算探查出来的新节点的位置和方向
    4. 计算这些新节点的代价
    5. 计算这些新节点的启发式距离。

    前两步和VFH+完全一样,下面只介绍3-5步。

    2.2 投影位置和方向

    进行探查时探查出来的方向段,是用圆弧和直线来近似表示的。探查距离设置为 d s d_s ds
    设置机器人向左转弯、向右转弯的最小转弯半径为 r l r_l rl r r r_r rr。其示意图如下图所示:
    在这里插入图片描述
    那么在沿着某一个候选前进方向探查时,首先判断机器人在投影距离内能不能到达到达这一方向。如果不能,那么投影轨迹就简单地用一个固定曲率的圆弧来代替。

    区分向左探查和向右探查也是很有必要的,并且规定,允许向左、向右选择的方向范围应该在 θ l θ_l θl θ r θ_r θr之间,其中
    θ l = θ i − d s / r l θ_l=θ_i-d_s/r_l θl=θids/rl
    θ r = θ i − d s / r r θ_r=θ_i-d_s/r_r θr=θids/rr

    说实话,作者的这一段描述,我是着实不理解。难道不就向着某一个方向新生长出来一个节点,然后在该节点处应用VFH+算法计算该点处的候选前进方向,然后计算代价函数并继续探查吗?怎么说的那么迷糊呢?

    2.3 代价函数

    在VFH+中使用的代价函数如下所示:
    在这里插入图片描述
    其中,第一项代表该方向和目标方向的差值;第二项代表该方向和机器人当前方向的差值;第三项代表该方向和上一次选择的方向之间的差值。如果希望VFH+是目标导向的,则需要满足 μ 1 > μ 2 + μ 3 μ_1>μ_2+μ_3 μ1>μ2+μ3

    在VFH*算法中,我们为每一个投影出的候选方向(方向段)计算代价,采用如下函数
    在这里插入图片描述

    2.3.1 k e k_e ke

    (4)的第一项依然是代表目标导向。但是这个函数和VFH+用到的函数略有不同,在某一个projected node处,我们计算它的代价时不仅考虑了目标方向,还引入了另一项,那就是 k e k_e ke,称为forward progress,这一项代表从该节点的父节点到该节点处的方向角,那么为什么要引入这一项呢?请看下图。
    在这里插入图片描述
    在每一个projected node处,候选前进方向都是和目标方向一致的,但是我们发现,节点的expansion却是在一个圆弧上,并不是靠近目标的,所以仅仅考虑该节点处的方向,不足以评价该节点的好坏,因此需要引入另一项,也就是 k e k_e ke,该项代表该节点是靠近目标了还是远离目标了,因而可以更好的评价一个节点趋向目标点的程度。

    值得强调的是,只有在计算连接projected node及其父节点的那一个方向段的代价时,才会考虑 k e k_e ke,在计算机器人primary node处的方向段时不考虑 k e k_e ke项。

    2.3.2 平滑项

    代价函数的第二项和第三项是用来决定机器人运动平滑程度的。为了保证机器人的目标导向性,需要满足
    μ 1 ’ > μ 2 ’ + μ 3 ’ μ_1’>μ_2’+μ_3^’ μ1>μ2+μ3
    同时为了强调primary 候选方向的重要性,需要满足
    μ 1 > μ 1 ’ μ_1>μ_1^’ μ1>μ1

    2.3.3 折扣因子λ

    代价函数中另一个很重要的因子是λ,该因子是基于这样的考虑,探查的越远,那么该处的节点对机器人的避障影响就越小,因此随着探查的深入,相应的代价也随之减小。
    那如果我们不设置这一个折扣因子,会发生什么事?请看下图。
    在这里插入图片描述
    上图中,有A、B、C三条路径,如果不设置折扣因子(等同于把折扣因子设置为1),那么搜索阶段搜索到的代价最低的路径将会是B。为什么呀?直观看来明显应该是A比B更好呀。这是因为没有折扣因子的话,每一个方向段对代价的影响是相同的,很明显B在最后几次探查中,一直和目标方向一致,导致其代价比较小,因而B的代价就比A小了。而在引入折扣因子之后,就强化了离机器人较近的方向段,削弱了离机器人较远的方向段。这个时候,A就可以战胜B成为代价最小的路径了。

    另外,上图中的探查次数 n g n_g ng为7。我们可以发现,只要 n g n_g ng再大一,B就会检测到障碍物,从而B的代价就会急剧增加。但是此时我们很可能依然无法判定A,因为此时,C依然是没有碰到障碍物,很可能C的代价还是比A小,我们依然没办法把A这一条我们期望的路径给挑出来。这说明仅仅通过调整探查深度 n g n_g ng是没有办法达到目的的。必须通过这一个折扣因子λ才能够实现。

    2.4 启发函数

    启发式函数是用来评价这一个projected node 距离目标远近程度的,可以帮助算法更快地收敛。最简单的一个启发函数为
    在这里插入图片描述
    可以看得出来上面这个启发函数直接用 k t k_t kt来代替 c 0 c_0 c0。这个函数只考虑了机器人当时的方向和前一节点处的方向,而没有考虑 k e k_e ke

    我们可以选择一个更好的启发函数:在这里插入图片描述
    这一个函数考虑了 k e k_e ke的影响,但是代价就是其计算量大了。

    2.5 枝叶因子b

    为了加快搜索阶段的执行效率,我们才可采取修剪搜索树的方法。

    每一个projected node在扩展之后,都会有几个successor node,successor node的数量和这一个节点的候选前进方向的数量是一致的。我们一般将探查距离 d s d_s ds设置为机器人的直径,这个值对于机器人所处的环境来说通常是很小的。因而这些新扩展出来的节点是很接近的,我们不妨把它们看成一个节点。

    并且,我们在前面确定过机器人可以向左、向右制动的最大方向角。
    θ l = θ i − d s / r l θ_l=θ_i-d_s/r_l θl=θids/rl
    θ r = θ i − d s / r r θ_r=θ_i-d_s/r_r θr=θids/rr
    那么所有那些,超过了这一个范围的新节点,都给整合成一个节点。并且在机器人的左侧方向和右侧方向我们均尽量只保留一枝,这样的话,一个节点的successor node个数很少会超过3。

    最后我们在这一个树中搜寻代价最小的“枝”,这就是我们期望的那一条路径。

    3、算法分析

    我觉得这个算法思路是很好的。只是 n g n_g ng这一个参数有些难整。
    作者说, n g n_g ng设置的小一些,算法速度更快,但是处理dead-end的能力也较弱。 n g n_g ng越大,处理dead-end的能力越强,但是计算量就大大增加。
    并且作者说, n g n_g ng设置为2可以应对绝大多数情况。

    展开全文
  • VFH避障/局部路径规划算法

    千次阅读 2021-08-31 16:43:04
    VFH避障/局部路径规划算法 本文章是我看《The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots》论文时候的笔记,感兴趣的欢迎去看原论文。 VFH中有一些概念是从其他算法中借鉴过来的,并且VFH...


    做个正直的人

    本文章是我看《The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots》论文时候的笔记,感兴趣的欢迎去看原论文。

    VFH中有一些概念是从其他算法中借鉴过来的,并且VFH算法本身就是对VFF(Virtural Force Field)的一种改进,其中有很多的相似之处。所以按照原论文的思路,先介绍由CMU提出的Certainty Grid算法中的一些概念,再介绍一下势场法中的一些概念,接着介绍一下VFF算法,最后介绍最重要的VFH算法。

    1、信度栅格(Certainty Grid)

    CMU提出的算法中最重要的思想就是The Certainty Grid for Obstacle Representation,即用一个置信度来表示这一个位置存在障碍物的可能性有多大。至于中文名字该叫什么,难道翻译成“基于置信度栅格的障碍物表示法”?

    具体来说就是,把整个地图用一幅二维的栅格(grid)地图来表示,比如大小是1024*1024。机器人的工作空间(就是局部地图)也用一个二维数组来表示,这个工作空间只包括以机器人为中心的一块正方形区域,比如30*30大小。每一个grid都有一个信度值(certainty value,CV)这一个CV值表示了这一个grid中存在障碍物的可能性有多大。CMU算法,使用一个概率函数来更新每一个CV值。比如通过超声波传感器来获取周边情况。

    VFH算法中工作空间中的每一个unite不再叫做grid,而是叫做cell。

    2、势场法(Potential Field Methods)

    势场法我觉得肯定是一个/一群物理相当不错的人提出来的。我觉得这种方法有一种天然的美感,自然、不做作。

    势场法比如人工势场法(APF),思路非常简单。可以这么理解,目标位置和障碍物会通过一种叫做场(就像磁场或者电场)的东西对我们机器人施加力的作用,所不同的是,目标位置对机器人施加的是吸引力 F a t t F_{att} Fatt ,障碍物对机器人施加的是排斥力 F r e p F_{rep} Frep 。并且距离越远,力就越小。根据力的分析,我们的机器人总体上是受到一个合力 R 的作用,这个力就会不断的推着我们的机器人绕过障碍物到达目标位置。

    3、VFH算法的前身——VFF(Virtual Force Field Method)

    VFF算法使用一个二维的笛卡尔直方图栅格区域(Cartesian histogram grid,我能怎么翻译?真的翻译不出来呀!)C来表示整个区域,和CMU方法一样,VFF的每一个cell具有一个属性CV 即 c i , j c_{i,j} ci,j 表示这一个cell存在障碍物的可能性有多大。和CMU方法不同的是,CV建立和更新的方法更加快速。
    CMU是通过传感器数据来给这一个传感器范围内的每一个grid赋予概率值,VFF则是只更新每一个传感器范围内仅仅一个cell的值。打一个比方,我们拿着手电筒照射一堵墙,很明显我们的手电筒会在墙上形成一个一定大小的圆形光斑,对待这一个光斑CMU和VFF有不同的处理方法,CMU会给整个光斑区域进行更新,而VFF只会更新位于光斑中心位置的那一个点,那其他的点怎么办?不用担心,我们的机器人是在运动的呀,虽然只更新一个点,但是点动成线,扫过去不就连续更新了嘛?看下图就清楚了。
    在这里插入图片描述
    很明显,VFF的计算量大大减少,速度比较快,这也是VFF可以允许机器人进行快速、连续、光滑运动的原因。不过凡事有好就有坏,VFF此举导致丢失了很多的信息,从控制的角度来说,我们对系统信息知道的越少,就越是难以对系统进行控制,所以VFF带来了一些比较大的缺点,后面会提到。
    此外,VFF还使用了势场法的思想。在机器人运动过程中,会维护一个特定大小的(比如30*30)、以机器人为中心的正方形区域,称为活跃窗口(active region),记为C*。C*中的每一个cell记为 c i , j c_{i,j} ci,j 。其实理论上应该维护的是一个圆形,但是如果用圆形就会大大增大算法的计算量,所以就用了矩形,这样处理起来比较方便。
    在这里插入图片描述
    C*内的每一个 c i , j c_{i,j} ci,j都会对机器人施加力(virtual force) F i , j F_{i,j} Fi,j ,这样就好象有一个力场一样推动机器人运动。 F i , j F_{i,j} Fi,j 的大小和 c i , j c_{i,j} ci,j 大小成正比,和 d x d^{x} dx 成反比,其中d是该cell到机器人中心的距离。x一般取为2。

    在每一次循环的时候,所有的 F i , j F_{i,j} Fi,j 被求合力得到排斥力 F r e p F_{rep} Frep 。同时目标位置对机器人的吸引力记为 F a t t F_{att} Fatt F r e p F_{rep} Frep F a t t F_{att} Fatt 求和力得到 R ,这个R 就是推动机器人运动的那个力。

    下面说说VFF算法的缺点:

    • 缺点一:过不了门。当机器人试图通过一扇门的时候,来自门两边的墙的斥力把机器人推走了。
    • 缺电二:由于离散性,在机器人移动过程中,C*也在不断的变化,导致机器人所受的合力R会发生大幅度的突变,给机器人的控制带来了难度。因此需要额外加入一个低通滤波器,来抑制剧烈的变化,但是这就大大减慢了系统的响应速度。
    • 缺点三:当机器人试图穿越一个走廊的时候,一旦机器人偏离中心线(来自两边的斥力相互抵消的位置),机器人受力发生变化,导致机器人围绕走廊的中心线进行振荡(左右摇摆)。

    4、VFH算法

    正式为了改善VFF算法的那些缺点,VFF的作者们又提出了VFH算法。他们指出,VFF算法之所以会发生大幅度的振荡,就是因为在机器人移动过程中,C*也在运动,所以会有上百个cell在短时间内离开C*,同时有上百个cell在短时间内进入C*,这就会导致计算出来的合力R剧烈变化。因为如此大规模的数据在一步内(很短时间)就被处理了,其处理结果用来产生合力R,包括其大小和方向,这样实际上丢失了很多的细节信息。所以他们把这一步拆成两步来做。

    相应的VFH算法分成了三层。

    • 最高层用来描述机器人工作环境,包括大量的细节信息。在这一步,通过板载传感器数据采样,C被不断的更新。这一步和VFF是一样的。
    • 在中间层,构造一个一维的极坐标直方图(polar histogram)H出来。H包含n个sector,每一个sector宽度为 α \alpha α ,所以 n = 360 ÷ α n=360\div\alpha n=360÷α 。随后把C*变换到H,每一个sector有一个属性 h k h_k hk 来表示第k个sector的极坐标障碍物密度(polar obstacle density),我觉得就是有障碍物的概率。
    • 最底层,给出控制机器人运动的参考值,Rref。

    我们分为4步来介绍VFH算法,就像原论文那样。

    A 第一次data reduction和构建极坐标直方图

    这一步的主要工作就是把C空间中的C*映射到极坐标直方图H。

    在VFF中的每一个栅格,到了VFH中就成了一个向量,即以机器人的中心位置为极坐标系原点,那么这一个cell就有角度 θ i , j \theta_{i,j} θi,j 和模 m i , j m_{i,j} mi,j 两个属性来唯一表示。

    记机器人的中心位置(VCP,vehicle center point)为 ( x 0 , y 0 ) (x_0,y_0) (x0,y0) ,某一个cell的位置为 ( x i , y i ) (x_i,y_i) (xi,yi) 。那么 c e l l i , j cell_{i,j} celli,j 的角度表示为
    在这里插入图片描述
    大小表示为
    在这里插入图片描述
    其中:a,b 都是正常系数; c i , j ∗ c_{i,j}^{*} ci,j 是cell(i,j)的信度值; d i , j d_{i,j} di,j 是cell(i,j)距离VCP的距离; m i , j m_{i,j} mi,j 是cell(i,j)的向量模,千万注意,cell的向量模不等于该cell到原点的距离; ( x 0 , y 0 ) (x_0,y_0) (x0,y0) 是VCP的坐标; ( x i , y i ) (x_i,y_i) (xi,yi) 是cell(i,j)的坐标; β i , j \beta_{i,j} βi,j 是cell(i,j)对应的向量的角度。
    注意,a,b 应当满足如下关系 a − b d m a x = 0 a-bd_{max}=0 abdmax=0 ,其实就是要保证正方形的工作空间的四个顶点的m值为0。因为这些点已经快离开机器人的工作空间了,这些位置的障碍物对机器人的作用应当为0。
    如果我们选择 α = 5 ∘ \alpha=5^{\circ} α=5 ,那么很明显就是把360分成了72个sector。不妨假设分成了n 个sector,那么sector的编号哦就是从0到n-1,对于任意一个cell(i,j)的角度 β i , j \beta_{i,j} βi,j 可知如下关系成立:
    在这里插入图片描述
    其中k是第k个sector的索引。
    相应的第k个sector的 h k h_{k} hk 按照如下公式计算:
    在这里插入图片描述
    请看此图, h k h_{k} hk 的计算一目了然:
    在这里插入图片描述
    此外,由于离散的特点,在映射的时候可能出现剧烈跳变得点,为此,还需要进行平滑。使用如下式子进行平滑,其中l一般选为5:
    在这里插入图片描述
    说实话这个式子我没看懂,看着像加权平均,但是仔细一看又不是。很明显结果已经被放大了若干倍,不过倒是不影响。

    B 第二次data reduction和方向控制

    这一步用来产生一个控制方向或者叫控制角度, θ \theta θ
    在这里插入图片描述
    在这里插入图片描述
    如上图所示,把我们的n个sector各自的 h k h_k hk 依次描在一个表中,就成了上图6中的a。其中A、B、C三个山峰对应三个障碍物,我们的目的就是避开这些障碍物,所以我们应该选择山谷作为我们候选的前进方向。我们需要一个阈值来挑选出来那些山谷,但是我们也在其中发现存在多个山谷,那么我们该怎么杨挑选出来那一个“最好”的山谷呢?这就是这一步要做的工作。
    首先,我们评估每一个山谷的宽度,我们会遇到两种情况,宽的山谷和窄的山谷。为此我们需要一个阈值 S m a x S_{max} Smax 来判断哪些山谷是窄的山谷,哪些山谷是宽的山谷。如果这个山谷的sector个数大于 S m a x S_{max} Smax 个,我们就认为这是一个宽的山谷。否则就是一个窄的山谷。
    对于宽的山谷也存在两种可能:山谷两侧的两个障碍物距离比较远;或者只有一测具有障碍物,另一测十分空旷。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    对于宽的山谷,记 k t a r g k_{targ} ktarg 是从VCP指向目标位置的方向,所有sector中距离 k t a r g k_{targ} ktarg 最近并且小于特定阈值(也就是属于某一个山谷)的那个sector记为 k n k_n kn ,表示山谷的最近邻边界,我们把另一端 k f k_f kf ,表示山谷的最远边界。(请看上面三幅图)宽的山谷的 k n k_n kn k f k_f kf 满足如下关系:
    在这里插入图片描述
    要知道我们的宽的山谷包含的sector的个数可能不只 S m a x S_{max} Smax 个sector,为什么这里不是加上山谷的真实宽度而是加上 S m a x S_{max} Smax 呢?因为我们不单纯是为了避障,我们还想要到达目的地呀,所以我们不能离目的地太远了,所以要加上 S m a x S_{max} Smax ,既保证安全,又不会偏离目的地太远。
    此时,我们选择的前进方向就是 k n k_n kn k f k_f kf 的中间位置,即:
    在这里插入图片描述
    对于窄的山谷,如下图,山谷的宽度不足 S m a x S_{max} Smax ,我们仍然选择方向为上式。
    在这里插入图片描述
    我们想一下,要穿过一扇门,就需要找到一个山谷,并选择一个合适的 θ \theta θ ,由此就避免了被门给推走的情况了。此外这还避免了在通过走廊时的振荡问题(真的嘛?我没有发现呀)。此外,VFH也不需要低通滤波器,因而速度比较快,允许机器人进行快速的移动。

    C 阈值的选择

    阈值的选择是比较重要的, S m a x S_{max} Smax 阈值太大,导致机器人对障碍物不够敏感。阈值太小,机器人又难以通过比较窄的通道。为此可以采用自适应动态阈值的方法。

    D 速度控制

    说实话,这个速度控制部分颠来倒去,我看迷糊了,总之就是既希望速度尽量小,又不希望机器人停下来。
    E还是有可能陷入局部最优怎么办?
    用全局路径规划器来解决。

    5、我在调试的时候,发现的问题

    这个算法太依赖于阈值了。说实话,不太喜欢这个算法。

    在调试程序的时候发现的几个要注意的点:

    1 、局部地图的大小。ros的局部地图默认分辨率是0.05m/cell,大小为80*80,也就是80*0.05=4m见方。地图太大,机器人很容易地就感知到了远处的障碍物,但是我们真的对远处的障碍物很感兴趣吗?很多时候,机器人距离附近的障碍物还是比较远的,避障还不是太重要,这时候地图太大就会干扰机器人的正常运动,此外还会导致机器人的运动变得复杂、计算量增加,甚至不断的调整自己的方向,影响了机器人的运动性能。所以机器人选择的局部地图的大小应当合适,不能太大,这会破坏机器人的运行表现;也不能太小,这会导致机器人对障碍物不够敏感,不适合快速运动。低速情况下,局部地图可以适当小一些,快速的时候,局部地图可以适当大一些。对于小体积机器人地图可以小一些;对于一些大块头,地图应当大一些,比如hit机器人,4m见方就挺好。

    2 、参数vfh_threshold,也就是 S_{max} ,这一个参数用来区分哪些sector应该归入山谷,哪些sector应该归入山峰。这个值太大,机器人对障碍物不够敏感;太小,导致机器人难以通过狭窄的通道。

    3 、参数vhf_detection_range,障碍物敏感距离。每个cell0.05m宽度,视机器人大小而调整,对于turtlebot来说,可以设置为7/8,也就是0.35/0.4m距离。对于hit这种大家伙,可以设置为1.4m也就是28个来试试。

    4 、权重参数goal_weight、curr_direction_weight、prev_direction_weight,当机器人调整自己的前进方向的时候,不能全凭着目标方向来决定,这会让我们的机器人转来转去,光顾着调整方向了。还必须考虑到当前前进方向,然而这还是不够,我们还必须考虑到前一次方向,不能转来转去。调试的时候发现,目标方向权重太大,机器人容易转来转去,应当让当前的前进的方向比目标方向更大一些,前一次方向比目标方向还要小一些,说实话,前一次方向貌似不太重要的。

    5、局部规划器更新频率是不是太重要,目前是5,,感觉不会有什么太大影响吧。

    6、计算出来一次新的前进方向,就必须朝向这一个方向?不必吧。如果这个角度太小,就会发现我们的机器人来回摆头像个傻子一样,为此设定一个不灵敏区域,这一次的方向和上一次的方向相差不大就不更新方向,否则就更新。

    引用:

    [1]Borenstein, J, Koren, et al. The vector field histogram-fast obstacle avoidance for mobile robots[J]. Robotics and Automation, IEEE Transactions on, 1991.

    展开全文
  • 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的认知还不是太深刻所以具体调试效果及调试经验日后分享,敬请期待。

    展开全文
  • 智能车高速稳定行驶局部路径规划算法[归纳].pdf
  • 常见的局部路径规划算法,先列出来,后面对算法做补充: 1.动态窗口法(DWA) 2.Time Elastic Band(Teb) 3.Eband方法(eband_local_planner) 4.lattcie planner 5.Vector Field Histogram(VFH及其改进的算法VFH...
  • 简介 ​ 最近,作者参加了关于RMUS 高校 SimReal挑战赛,首次接触到了机器人导航领域,...​ 机器人导航的路径规划问题主要分为全局路径规划和局部路径规划,这两者是根据对环境信息获取程度划分的。 全局规划通常需
  • Timed-Elastic-Band局部路径规划算法

    万次阅读 多人点赞 2018-10-30 11:30:43
    早前做工程时尝试了teb局部规划算法,觉得效果非常好。... teb局部路径规划算法github地址:https://github.com/rst-tu-dortmund/teb_local_planner。  作者列出的几篇文章均推荐阅读了解。本...
  • 基于RobotBasic的移动机器人局部路径规划算法的研究,宋莉,李彩虹,针对传统移动机器人局部路径规划存在死区或陷阱区域等问题,提出了一种新的两点法算法。在路径规划过程中,首先利用两点法确定机
  • VFH+避障/局部路径规划算法

    千次阅读 2021-08-31 17:27:39
    VFH+避障/局部路径规划算法 这篇文章是我看论文《VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots》(Iwan Ulrich and Johann Borenstein)的笔记,所以说是文章的翻译也可以。想看原paper的可以自己去找...
  • 在目标点周围构建引力势场,类似于物理学中的电磁场被控对象在这两种势场组成的复合场中受到斥力作用和引力作用,斥力和引力的合力指引着被控对象的运动,搜索无碰的避障路径。更直观而言, 势场法是将障碍物比作是...
  • 路径规划中经典算法和发展趋势介绍
  • DWA路径规划算法

    千次阅读 2022-06-21 00:43:59
    来源丨古月居1.DWA路径规划基本原理动态窗口法主要是在速度(v,w)空间中采样多组速度,并模拟机器人在这些速度下一定时间(sim_period)内的轨迹。在得到多组轨迹以后,对这些轨迹进行评价,选取最优轨迹所对应的速度来...
  • 总结 | 六大路径规划算法

    千次阅读 2022-02-04 01:51:04
    在滚动的每一步,根据探测到的局部信息,用启发式方法生成优化子目标,在当前滚动窗口内进行局部路径规划,然后实施当前策略(依局部规划路径移动一步),随滚动窗口推进,不断取得新的环境信息,从而在滚动中实现优化...
  • 前言:对于无人驾驶路径规划系列的第二篇RRT算法的改进部分,由于有些内容属于个人想到的创新点,有想法投一篇小论文所以暂时没有公开,等后续完成后我会再公开介绍。今天第三篇内容开启一个新的算法介绍:Frenet...
  • 除此之外,我们还可以加上其他的一些因素,比如所得路径是否贴合全局路径等等。 一些影响因素 当前速度的影响:当前的速度决定了能走的空间。比如在靠近障碍物的地方要转弯, 如果速度太快,可调的速度可能不...
  • 之前的文章都是基于搜索的路径算法,这两天在又学习了一下基于采样的路径规划算法,这里做一下记录,最后会奉上大神的链接 基于采样的路径规划算法大致可以分为综合查询方法和单一查询方法两种。 前者首先构建路线...
  • 为了实现未知复杂环境下机器人的局部路径规划,提出了一种新的局部路径规划方法,使机器人自主探测周边障碍物情况。通过滚动窗口计算局部目标等途径进行路径规划,从而实现机器人无碰撞到达全局目标点。该方法可以使...
  • 路径规划算法

    万次阅读 多人点赞 2021-11-14 10:20:44
    文章目录前言一、传统路径规划算法1.Dijkstra算法2.A*算法3.D*算法4.人工势场法二、基于采样路径规划算法1.PRM算法2.RRT算法三、智能仿生算法1.神经网络算法2.蚁群算法3.遗传算法 前言 随着机器人技术、智能控制...
  • 3 移动机器人路径规划3.1 Floyd路径规划算法原理3.2 Floyd路径规划算法图论示例3.3 Floyd路径规划MATLAB代码3.3.1 实例应用3.3.2 主代码Floyd_main.m3.3.3 函数代码Floyd_NextNode.m3.3.3 函数代码Floyd_GetPath.m...
  • 关于扫地机器人的路径规划算法的概括,为提高机器人路径规划的搜索速度,缩短搜索时间,总结归纳移动机器人在路径规划问题上的算法及其特点,并对路径规划技术进行概述;其次对移动机器人路径规划进行分类总结,并从...
  • 前言:由于后续可能要做一些无人驾驶相关的项目和实验,所以这段时间学习一些路径规划算法并自己编写了matlab程序进行仿真。开启这个系列是对自己学习内容的一个总结,也希望能够和优秀的前辈们多学习经验。 一、...
  • 基于采样的路径规划算法总结

    千次阅读 2021-04-18 12:05:27
    基于采样的路径规划算法总结 路径规划算法大致可以分为两类,一类是基于搜索的规划,另一类就是本文将要涉及的基于采样的规划。一般而言,基于搜索的规划(如A*)通常是运行在栅格地图上的。当栅格的分辨率越高时,...
  • 然后,在扩展节点时引入视线算法,增加本地父亲节点和远程父亲节点的概念,使得路径不局限于八邻域扩展,从而进化为任意角度路径规划算法;最后,在遇到未知障碍物时进行局部距离变换,结合启发距离值信息进行重规划,使得重...
  • 文章目录第一章 路径规划算法概述前言一、传统路径规划算法1.1 Dijkstra算法1.2 A*算法1.3 D*算法1.4 人工势场法二、基于采样的路径规划算法2.1 PRM算法2.2 RRT算法三、智能仿生路径规划算法3.1 神经网络算法3.2 蚁...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,835
精华内容 7,934
关键字:

局部路径规划算法

友情链接: boost.zip