精华内容
下载资源
问答
  • ROS常用局部路径规划算法比较
    千次阅读 多人点赞
    2021-06-07 20:07:39

    本博文主要讨论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的认知还不是太深刻所以具体调试效果及调试经验日后分享,敬请期待。

    更多相关内容
  • 导航局部路径规划eb算法的详细代码注释,里面包括自己的见解和debug测试结果,特别适合初学者进行研究学习。
  • 路径规划】基于matlab DWA算法机器人局部避障路径规划【含Matlab源码 890期】.zip
  • 人工势场法是一种常用的具有算法简单和便于实时控制的局部路径规划方法,但存在容易产生局部极小值的问题。基于模糊逻辑的局部路径规划法具有环境适应性强等优点,它在连续论域内采用模糊路径规划时,计算量比较大。...
  • 在ROS的navigation-kinetic-devel中,使用现成的RAstar接口,编写遗传算法路径规划程序。能完成小车自主寻路,效率略低于Astar算法
  • 基于模糊逻辑算法路径规划,matlab版本
  • 车载导航系统中最重要的功能是路径规划,传统车载导航设备大多采用静态算法,没有采用实时交通信息规划出的路径可能不是最优路径。结合一种动态行程时间表对传统A*算法进行调整,可以有效利用路网实时交通数据规避...
  • 局部RRT路径规划matlab代码运动计划 Python 用于几种路径规划算法的Python代码位于文件夹中。 让我们来看几个例子。 为了熟悉人工势能场(APF)算法,请执行以下操作: jupyter-notebook python_src/adaptive_...
  • 作者 |果冻啤知圈 |进“ISO26262社群”,请加微信15221054164,备注ISO以下是本人在学习路径规划过程中的一些总结,借着机会写了一下,不妥之处欢迎批评指正,谢谢。路径规划部分在无人车架构体系当中分属控制或...

    1cd1803c7ba139ebfa1ca115d1799384.gif364f99366192519b7a402c010d374877.png

    作者 | 果冻啤

    知圈 | 进“ISO26262社群”,请加微信15221054164,备注ISO

    以下是本人在学习路径规划过程中的一些总结,借着机会写了一下,有不妥之处欢迎批评指正,谢谢。 路径规划部分在无人车架构体系当中分属控制或决策部分,如图1,是实现无人化驾驶的关键技术之一。路径规划模块性能的高低直接关系车辆行驶路径选择的优劣和行驶的流畅度,而路径规划算法的性能优劣很大程度上取决于规划算法的优劣,如何在各种场景下迅速、准确的规划出一条高效路径且使其具备应对场景动态变化的能力是路径规划算法应当解决的问题

    d68988f66e19480d1ce302c5f6b10db7.png 图 0.1

    根据对环境信息的把握程度可把路径规划划分为基于先验完全信息的全局路径规划和基于传感器信息的局部路径规划。其中,从获取障碍物信息是静态或是动态的角度看,全局路径规划属于静态规划,局部路径规划属于动态规划。全局路径规划需要掌握所有的环境信息,根据环境地图的所有信息进行路径规划;局部路径规划只需要由传感器实时采集环境信息,了解环境地图信息,然后确定出所在地图的位置及其局部的障碍物分布情况,从而可以选出从当前结点到某一子目标结点的最优路径。 在全局路径规划算法中,大致可分为三类:传统算法(Dijkstra算法、A*算法等)、智能算法(PSO算法、遗传算法、强化学习等)、传统与智能相结合的算法。智能算法种类繁多,但传统算法更为基础,故本着由浅入深的原则,首先对传统算法展开学习。

    1 算法综述

    在传统路径规划算法中,各种算法的实现原理和应用范围差异很大,但可以将以下五种算法看作一类(Dijkstra、A*、D*、LPA*、D* lite),以下对各算法的基本原理进行阐述,并在搜索原理和应用场景等方面进行了对比区分。

    1.1 算法简述

    1.1.1 Dijkstra算法

    Dijkstra算法是由E.W.Dijkstra于1959年提出,又叫迪杰斯特拉算法。该算法采用了一种贪心模式,其解决的是有向图中单个节点到另一节点的最短路径问题,其主要特点是每次迭代时选择的下一个节点是当前节点最近的子节点,也就是说每一次迭代行进的路程是最短的。而为了保证最终搜寻到的路径最短,在每一次迭代过程中,都要对起始节点到所有遍历到的点之间的 最短路径 进行更新,具体看一下过程

    067cc09cc4672a8452f6896fcac447b3.png

    图 1.1 节点有向图 初始化: 建立distance[](起点到其他所有点的距离信息)、Top_node[](最短路径信息)两个列表存放信息。其中,distance[]的维度为节点的个数,每一个数值为到达对应索引节点的最短路径距离,比如distance[2]的值代表当前迭代时刻到达3号节点的最短距离。初始状态distance[0 inf 10 inf 30 100],其中0代表自身,inf代表无法到达;Top_node[num1],其中num1代表一号节点并以此类推。 搜索最小点: 找到当前节点到下一点的最小值,即从num1开始搜索到1->5/1->3/1->6三条路,并找到距离最小的路1->3。则此时到达num3点的最短路径确定为10,将num3存入Top_node[]。 松弛: 确定num3找到最短路径,然后num3开始搜寻其弧尾,找到3->4路径,此时1->3->4路径距离为10+50=60,小于inf,故将列表更新为distance[0 inf 10 60 30 100]。注意这里通过3->4这条路径缩短1->4这条路径的过程叫做“松弛”,该算法证实通过这样的方法进行路径寻优。 重复迭代: 除去num1和num3,从剩余点搜寻距离最小,找到num5,故将num5加入Top_node[]。找到弧尾路径5->4/5->6,进行松弛,其中1->5->4距离为30+20=50<60,1->5->6距离为30+60=90<100,所以列表更新为distance[0 inf 10 50 30 90]。 重复迭代: 除去num1、num3和num5,其余点寻最小,找到num4,将其加入Top_node[]。然后找到弧尾4->6,进行松弛,1->5->4->6距离30+20+10=60<90,1->3->4->6距离10+50+10=70>60,进行列表更新distance[0 inf 10 50 30 60]。 重复迭代: 除去num1、num3、num4和num5,其余点寻最小,找到num6,将其加入Top_node[],然后没有找到弧尾,则此时到达num6的最优路径找到。 以上就是Dijkstra算法的简单实例,可见其主要是通过贪心原则逐个遍历最小子节点,然后利用松弛方法去优化路径选择,最终将最优路径存放到可读列表当中,以此来解决最优路径规划问题。

    1.1.2 A*算法

    A*算法是启发式搜索算法,启发式搜索即在搜索过程中建立启发式搜索规则,以此来衡量实时搜索位置和目标位置的距离关系,使搜索方向优先朝向目标点所处位置的方向,最终达到提高搜索效率的效果。 A*算法的基本思想如下:引入当前节点x的估计函数f(x),当前节点x的估计函数定义为: f (x)= g(x)+h(x) 其中g(x)是从起点到当前节点x的实际距离量度(代码中可以用两点之间距离代替);h(x)是从节点x到终点的最小距离估计, h (x) 的形式 可以 从欧几里得距离

    d5a9f5c252ab7c60936faca501912327.png

    或者曼哈顿距离

    21a5dae690db200c747d2442cdfed273.png

    算法基本实现过程为:从起始点开始计算其每一个子节点的f值,从中选择f值最小的子节点作为搜索的下一点,往复迭代,直到下一子节点为目标点。

    1.1.3 D*算法

    基于A*算法,Anthony Stentz在1994年提出了Dynamic A*算法,也就是D*算法。D*算法是一种反向增量式搜索算法,反向即算法从目标点开始向起点逐步搜索;增量式搜索,即算法在搜索过程中会计算每一个节点的距离度量信息H(x),在动态环境中若出现障碍物无法继续沿预先路径搜索,算法会根据原先已经得到的每个点的距离度量信息在当前状态点进行路径再规划,无需从目标点进行重新规划。

    其中,距离度量信息H(x)=H(y)+C(y, x),H(y)代表x点到目标点的距离度量,C(y,x)代表y点到x点的距离度量,在算法中均可用两点间实际距离代替。

    1.1.4 LPA*算法

    2001年,由斯文·柯尼格(Sven Koenig)和马克西姆·利卡切夫(Maxim Likhachev)共同提出的Life Planning A*算法是一种基于A*算法的增量启发式搜索算法。 LPA*算法实现原理: 搜索起始点为所设起点(正向搜索),按照Key值的大小作为搜索前进的原则,迭代到目标点为下一搜索点时完成规划;Key值中包含启发式函数h项作为启发原则来影响搜索方向;处于动态环境时,LPA*可以适应环境中障碍物的变化而无需重新计算整个环境,方法是在当前搜索期间二次利用先前搜索得到的g值,以便重新规划路径。 其中,Key[]为一个二维数组:

    b66faaf97a3515287caa79c9ec2d6795.png

    g(n)代表起点到当前点的距离度量。rhs(n)为min(g(n’)+c(n’, n)),n’为n的父节点,h(n, goal)为启发项;搜索原则为:优先判断k1大小,若k1小则优先遍历,若k1=k2,则选择k2较小的点。

    1.1.5 D* lite算法

    D* lite算法是Koenig S和Likhachev M基于LPA_star 算法基础上提出的路径规划算法。D* lite与LPA*的主要区别在于搜索方向的不同,这就将Key[]定义中涉及到的目标点goal替换为起始点start的相应信息。 D*_lite算法是先在给定的地图集中逆向搜索并找到一条最优路径。在其接近目标点的过程中,通过在局部范围的搜索去应对动态障碍点的出现。增量式算法的优势在于,各个点的路径搜索已经完成,在遇到障碍点无法继续按照原路径进行逼近时,通过增量搜索的数据再利用直接在受阻碍的当前位置重新规划出一条最优路径,然后继续前进。

    1.2 算法对比

     1.2.1 性能和应用对比

    搜索方向启发式增量式适用范围现实应用
    Dijkstra正向搜索全局信息已知,静态规划网络通信中的最短路由选择
    A*正向搜索全局信息已知,静态规划Apollo、游戏、无人机路径规划
    D*反向搜索部分信息已知,动态规划机器人探路、火星探测车路径规划
    LPA*正向搜索部分信息已知,假设其余为自由通路,动态规划机器人路径规划
    D* lite反向搜索部分信息已知,假设其余为自由通路,动态规划机器人路径规划
    表 1.1 表 1.1中给出了五种算法分别在搜索方向、启发式、增量式、适用范围和现实应用五个方面的对比。以上五种算法的效能和适用范围各不相同,效能高且解决问题范围广并不一定代表应用广泛,目前实际应用的算法应偏向竭力发挥某一算法的专长,在基础功能之上不断优化算法性能。

    1.2.2 理解浅见对比

    搜索方向的正反: 在静态环境中全局地图信息已知,则无论正向搜索还是反向搜索都可以发挥效能。但是在动态环境中,面对未知地图,要想获得最短路径则需要不断的尝试,正向搜索很容易产生与最优路径背道而驰的现象,而此时反向搜索算法能够很好的处理这种情况。反向搜索配合增量式搜索使得D* lite算法在动态障碍图中,可以利用先前迭代中产生的节点距离信息,不断更新当前点到目标点的最优路径。而在正向搜索中,增量式算法只能提供当前点到起始点的距离信息和到目标点的启发估计信息,并不能保证未搜索区域的可通行性。 启发式与非启发式: 启发式算法能够在每次搜索时将搜索方向导向目标点,替代了非启发式算法向四周无规则遍历的局限,正常情况下能够大大提高搜索效率。但是在启发式路径受阻的情况下,搜索效果将适得其反。如图1.2

    9c5cbdb615af8ad09a55744a536bfbef.png

    图 1.2 启发式与增量式: 启发式搜索是利用启发函数来对搜索进行指导,从而实现高效的搜索,启发式搜索是一种“智能”搜索,典型的算法例如A*算法、遗传算法等。增量搜索是对以前的搜索结果信息进行再利用来实现高效搜索,大大减少搜索范围和时间,典型的例如LPA*、D* Lite算法等。 搜索方向的正反多与是否能处理动态规划有关;启发式搜索带来的时效能的提高,避免全局盲目搜寻;增量式搜索则代表着迭代信息的二次利用,多用于提高算法效率。 cd6dcbacfe5fe634c657a785b547b0f0.png f5fa63157ced5aaaae4d5709e4519cec.png
    展开全文
  • 采用D*Lite算法规划出的路径并不平滑,且预规路径与障碍物均十分接近.除此之外,在动态环境下时,由D*Lite算法规划得到的路径也离障碍物距离很近,十分容易发生碰撞.针对此问题,引入懒惰视线算法与距离变换相结合的...
  • 简介 ​ 最近,作者参加了关于RMUS 高校 SimReal挑战赛,首次接触到了机器人导航领域,...​ 机器人导航的路径规划问题主要分为全局路径规划局部路径规划,这两者是根据对环境信息获取程度划分的。 全局规划通常需

    简介

    ​ 最近,作者参加了关于RMUS 高校 SimReal挑战赛,首次接触到了机器人导航领域,这里记录一下这段时间的收货。sim2real的全称是simulation to reality,是强化学习的一个分支,同时也属于transfer learning的一种。主要解决的问题是机器人领域中,直接让机器人或者机械臂在仿真中对于物理环境存在误差,如何将仿真上取得的成果应用到实际中的问题。

    ​ 机器人导航的路径规划问题主要分为全局路径规划和局部路径规划,这两者是根据对环境信息获取程度划分的。

    • 全局规划通常需要在已知环境中进行,属于一种事前规划,可以找到最优解,一旦环境发生变化,未及时更新地图时,该方法就不能达到预期效果。
    • 局部路径规划通常用在未知或部分已知的环境中,系统根据传感器实时获取到环境障碍物的信息,并做出相应规划,这对系统的实时计算处理能力有着较高的要求。由于缺乏全局环境信息,结果很可能不是最优的。

    ​ 全局路径规划和局部路径规划并没有本质的区别,很多适用于全局路径规划的方法经过改进也可以用于局部路径规划,而适用于局部路径规划的方法同样经过改进后也可适用于全局路径规划。两者协同工作,机器人可更好的规划从起始点到终点的行走路径。

    ​ 本文主要针对局部路径规划作介绍。

    局部路径规划

    ​ 机器人在获得目的地信息后,首先经过全局路径规划规划出一条大致可行的路线,然后调用局部路径规划器根据这条路线及costmap的信息规划出机器人在局部时做出具体行动策略。常用的局部路径规划算法有动态窗口法(DWA)、时间弹性带(TEB)和模型预测控制(MPC)。

    动态窗口法(DWA)

    ​ 动态窗口法在一定程度上采用了粒子滤波的思想,在速度空间(v,w)中采样多组速度,并模拟出这些速度在一定时间内的运动轨迹,并通过评价函数对这些轨迹进行评价,选取最优轨迹对应的速度驱动机器人运动。

    基本思想

    1. 在机器人的控制空间中离散采样 (dx,dy,dtheta)
    2. 对于每个采样速度,从机器人的当前状态执行前向模拟,以预测如果采样速度应用于某个(短)时间段会发生什么。
    3. 使用包含以下特征的度量来评估前向模拟产生的每个轨迹:与障碍物的距离、与目标的距离、与全局路径的距离和速度,排除非法轨迹(与障碍物相撞的轨迹)。
    4. 选择得分最高的轨迹并将相关的速度发送到移动基地。
    5. 重复执行上述步骤。

    优点

    • 计算简单
    • 适用于差分和全向车模

    缺点

    • 前瞻性不足
    • 动态效果差
    • 不适用于阿克曼模型车模

    时间弹性带(TEB)

    ​ 时间弹性带(TEB)简而言之,就是连接起始、目标点,并让这个路径可以变形,变形的条件就是将所有约束当做橡皮筋的外力。起始点、目标点状态由用户/全局规划器指定,中间插入N个控制橡皮筋形状的控制点(机器人姿态),当然,为了显示轨迹的运动学信息,我们在点与点之间定义运动时间Time。

    t i m e + e l a s t i c b a n d = t i m e d e l a t i c s b a n d time + elastic band = timed elatics band time+elasticband=timedelaticsband

    其目标函数的定义:

    ​ 虽然待优化的橡皮筋有不少状态点与时间段,目标函数也好像很多。但是,每个目标函数只与橡皮筋中的某几个状态有关,而非整条橡皮筋。将它描述成图,然后用图优化。

    优点

    • 前瞻性好
    • 适用于各种车模

    缺点

    • 计算复杂
    • 速度和角速度波动大,控制不稳定

    模型预测控制(MPC)

    ​ MPC其实是一种基于对受控对象进行预测的控制方法。MPC最大的特点在于,相对于LQR控制而言,MPC可以考虑空间状态变量的各种约束,而LQR,PID等控制只能够考虑输入输出变量的各种约束。

    ​ MPC的作用机理可以表述为:在每一个采样时刻,根据当前的测量信息,在线求解一个有限时间开环优化问题,并将得到的控制序列的第一个元素用于被控对象;在下一个采样时刻,用新的测量值作为此时预测系统未来动态的初试条件,刷新优化问题求解。应用于机器人的典型的模型预测控制方法:

    问题模型

    m i n C F ( x ( t f ) ) + f t = t 0 t f C R ( x , u ) d t x ˙ = f ( x , u ) g ( x , u ) < 0 h ( x , u ) = 0 minC_F(x(t_f))+f_{t=t_0}^{t_f}C_R(x, u)dt\\ \dot{x}=f(x, u)\\ g(x, u)<0\\ h(x,u)=0\\ minCF(x(tf))+ft=t0tfCR(x,u)dtx˙=f(x,u)g(x,u)<0h(x,u)=0

    参数空间

    m i n C F ( x ( t f ) ) + f t = t 0 t f C R ( x , u ) d t minC_F(x(t_f))+f_{t=t_0}^{t_f}C_R(x, u)dt\\ minCF(x(tf))+ft=t0tfCR(x,u)dt

    控制

    传统MPC控制框图为

    1. 设置优化问题
    2. 使用测量模块告诉我们当前的initial state
    3. 求解优化问题得到参数,这些参数构成系统的最优输入 u*
    4. 使用 u*驱动系统,由于系统受到干扰无法保证求解得到的 u*我们想要的,仅此旨在很小一段时间中使用,然后利用观测的状态重新求解问题,转回步骤(2)

    局部规划器的应用

    ​ 这里以mpc_local_planner为例,首先,在本地终端中键入

    sudo apt install ros-melodic-mpc-local-planner
    

    ​ 由于apt安装有可能导致我们运行失败,上面的指令只是用来安装依赖。同时,克隆远程仓库mpc_local_planner到ros的工作空间中,执行catkin_make编译。对应ros navigation中的move_base.launch,修改其中的局部路径规划器类型

    <?xml version="1.0"?>
    <launch>
    
      <!-- 运行move_base节点  -->
      <node pkg="move_base" type="move_base" respawn="false" name="move_base" output="screen" clear_params="true">
        
        <!--move_base参数配置http://wiki.ros.org/move_base -->
        <param name="base_global_planner" value="global_planner/GlobalPlanner" /><!-- 选择全局规划器类型 -->
        <rosparam file="$(find mpc_navigation)/config/base_global_planner_params.yaml" command="load" />
        
        <rosparam file="$(find mpc_navigation)/config/mpc_local_planner_params_minimum_time.yaml" command="load" />
        <param name="base_local_planner" value="mpc_local_planner/MpcLocalPlannerROS" />
    
        <rosparam file="$(find mpc_navigation)/config/move_base_params.yaml" command="load" /><!-- 其它参数 -->
    
        <param name="controller_frequency" value="1" /><!-- 选择全局规划器类型 -->
    
        <!-- 全局代价地图和局部代价地图参数配置http://wiki.ros.org/costmap_2d -->
        <rosparam file="$(find mpc_navigation)/config/costmap_common_params.yaml" command="load" ns="global_costmap" />
        <rosparam file="$(find mpc_navigation)/config/costmap_common_params.yaml" command="load" ns="local_costmap" />
        <rosparam file="$(find mpc_navigation)/config/local_costmap_params.yaml" command="load" />
        <rosparam file="$(find mpc_navigation)/config/global_costmap_params.yaml" command="load" />
        
      </node>
    
    </launch>
    

    ​ 对应mpc_local_planner的参数文件可以在克隆仓库中的mpc_local_planner_examples中获得,将cfg/diff_drive中的参数yaml文件复制到对应的config文件夹中即可,base_ local_planner参数设置为mpc_local_planner中定义的类型MpcLocalPlannerROS。

    ​ mpc_local_planner提供了两个参数文件,一个是以最短时间为目的,另一个是二次规划模型,可以根据需求自行选择。

    ​ 其他的局部规划器同样是修改base_local_planner的类型和提供相应的功能包以及yaml参数文件实现。

    参考

    ros-dwa_local_planner

    ros-teb_local_planner

    ros-mpc_local_planner

    ROS学习笔记-局部路径规划算法对比

    后续

     喜欢的话可以关注一下我的公众号技术开发小圈,尤其是对深度学习以及计算机视觉有兴趣的朋友,我会把相关的源码以及更多资料发在上面,希望可以帮助到新入门的大家!
    在这里插入图片描述

    展开全文
  • 为了实现未知复杂环境下机器人的局部路径规划,提出了一种新的局部路径规划方法,使机器人自主探测周边障碍物情况。通过滚动窗口计算局部目标等途径进行路径规划,从而实现机器人无碰撞到达全局目标点。该方法可以使...
  • 机器人局部路径规划算法——VFH系列论文。主要根据传感器的观测数据,更新占用栅格地图,然后计算下一步的运动方向。
  • 利用遗传算法( GA)实现 AUV(自主水下机器人)对于运动目标的自主避碰,根据前视声纳信息探测到 的障碍物距离信息,AUV的运动信息以及航迹规划信息。算法采用了二进制编码规则,并把避碰、航迹跟踪等 约束条件作为适应度...
  • 通过对全局和局部路径规划的深入分析,提出了一种全局和局部路径规划方法相结合的混合算法路径规划。使用A-Star算法在静态环境中进行全局规划并且将该路径的拐点作为子目标点,通过改进模糊人工势场法来进行实时的局部...
  • VFH+避障/局部路径规划算法

    千次阅读 2021-08-31 17:27:39
    VFH+避障/局部路径规划算法 这篇文章是我看论文《VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots》(Iwan Ulrich and Johann Borenstein)的笔记,所以说是文章的翻译也可以。想看原paper的可以自己去找...


    做个正直的人

    这篇文章是我看论文《VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots》(Iwan Ulrich and Johann Borenstein)的笔记,所以说是文章的翻译也可以。想看原paper的可以自己去找,看过VFH算法的话,这个VFH+算法还是非常好懂的。

    我前面写过一篇讲VFH算法的文章,感兴趣的可以去看看。
    VFH局部路径规划算法

    我在讲VFH算法的最后,写了一点我对VFH算法的评价,主要有两点,一是VFH算法涉及的参数比较多,很麻烦;二是机器人总是会像个傻子一样在原地摆头,我设置了一个不灵敏区域稍微缓解了一下摆头的问题,但是这导致机器人对障碍物的灵敏性降低。

    今天看了VFH+算法,才发现原来这些问题前人们早就研究过了。VFH+对VFH提出了几点修正,VFH还带了个正号,这是增强版的意思吗?hhhhhhhh…接下来进入正题。
    VFH+算法同样分成四个部分,不过和VFH的四个部分可是不一样。

    1、第一部分:映射到极坐标系

    VFH算法的第一部分就是把局部地图从笛卡尔空间映射到极坐标系,VFH+算法的做法跟VFH一样,只不过VFH+不再像VFH那样采用正方形的工作空间(可以当成是局部地图),而是采用了圆形的工作空间,本来就该是圆形的好吧,VFH那是为了简便而已。这工作空间一旦变成圆形,就有了一个性质——机器人原地旋转感知到的局部地图是不变的,这称为旋转不变性。

    VFH+对VFH的改进——考虑机器人的宽度&对障碍物进行膨胀

    VFH并没有考虑机器人的宽度,而是采用一个低通滤波器进行补偿,这个滤波器的参数的设置还比较麻烦。
    VFH+考虑到了机器人的宽度 r r r_r rr ,这里假定机器人是正圆盘形状。同时为了安全起见又设置了一个距离障碍物的安全距离 d x d_x dx ,基于此,我们就可以得到需要对障碍区进行膨胀的幅度 r r + x = r r + d x r_{r+x}=r_r+d_x rr+x=rr+dx 。这样我们就可以把机器人完全看做一个点来进行规划,是不是感觉事情变得简单了。
    在这里插入图片描述
    从上图可以看出,如果障起舞膨胀幅度为 r r + x = r r + d x r_{r+x}=r_r+d_x rr+x=rr+dx ,机器人距离障碍物的距离为
    d i j d_{ij} dij ,此时这一个障碍物对应的张角为 2 γ i , j 2\gamma_{i,j} 2γi,j 。其中 γ i , j = a r c s i n ( r r + x / d i , j ) \gamma_{i,j}=arcsin(r_{r+x}/d_{i,j}) γi,j=arcsin(rr+x/di,j)

    此时,这个障碍物很可能就不再仅仅位于一个sector内了,而是同时处于多个sector上,这时候更新工作空间就必须同时对多个sector进行更新。

    2、第二部分:二值化极坐标直方图

    VFH算法的一个大问题就是机器人会出现在原地频繁的左右摆头的现象,我在调试VFH算法的时候分析是VFH算法对新计算出的前进方向过于敏感,导致机器人频繁的更新自己的前进方向。所以我给VFH算法设置了一个不灵敏区间,只有当新的前进方向和自己当前的前进方向角度相差大于一定阈值的时候才会更新前进的方向,否则不会更新。但是这导致机器人对障碍物的灵敏性降低,限制了机器人的运行速度。

    VFH+算法对此提出了一种解决办法——二值化极坐标直方图

    VFH算法之所以会出现摆头现象(VFH+算法称之为犹豫不决的行为),是因为在存在一些比较窄(不是真的特别特别窄,只是比较窄而已)的通道的环境中,一些山谷可能会在opening和block的状态之间频繁变换。比如对于一扇开着的门,当离得比较远的时候,这一扇门占据的sector比较窄,而VFH更加倾向于选择那些宽的山谷(占据sector比较多的山谷方向),这时候这一扇门被当作是block,不会成为机器人的候选前进方向;可是随着机器人的运动,机器人离门越来越近,这一扇门占据的sector越来越多,当大于一个阈值的时候,这一扇门突然成了宽的山谷,而成为了候选的前进方向。这就导致一些方向频繁的在opening和block之间跳换,就像一条路,一会跟我说这条路可以走,一会又跟我说不可以走,这不是在拿机器人涮着玩嘛。

    VFH+算法的做法是设置两个阈值, τ H i g h \tau_{High} τHigh τ L o w \tau_{Low} τLow ,这样做的目的是降低一些方向在opening和block状态之间跳转的速度,你不是变大了吗(变小也是一样),虽然满足了我的第一个条件,但是我并不马上认可你,而是继续考核你一下,满足我的第二个要求后才是真的合格了,我才会认可你。就是这个思路,在机器人运动过程中,极坐标直方图也在慢慢的发生着变化,有些区域离开了工作空间,有些区域新加入工作空间,并且工作空间内部的物体相对于机器人的位置也在变化,所以会在每一个时刻生成一个极坐标直方图。将n时刻的极坐标直方图中的每一项 H k , n p H_{k,n}^p Hk,np 都和前一时刻对应的项 H k , n − 1 p H_{k,n-1}^p Hk,n1p 做比较,同时跟设定的两个阈值 τ H i g h \tau_{High} τHigh τ L o w \tau_{Low} τLow 进行比较,依次来决定这一项应该二值化为1还是0,亦或是继续保持前一时刻的值。下面的公式一看就明白了

    • H k , n p H_{k,n}^p Hk,np =1 if H k , n p > τ H i g h H_{k,n}^p >\tau_{High} Hk,np>τHigh :这一项都大于更大的那个阈值了,肯定得是1,也就是block
    • H k , n p = 0 H_{k,n}^p =0 Hk,np=0 if H k , n p < τ L o w H_{k,n}^p <\tau_{Low} Hk,np<τLow :这一项比更小的那个阈值都要小,得是0,也就是openning
    • H k , n p = H k , n − 1 b H_{k,n}^p = H_{k,n-1}^b Hk,np=Hk,n1b others :这一项不算大,也不算小,咋办?就维持前一时刻的状态吧,先观望一下。其中, H b H^b Hb 是二值化之后的极坐标直方图。

    3、第三部分:限制机器人可选的前进方向

    VFH算法中,机器人可选的前进方向是一圈360度都可能称为机器人的前进方向,看下图a。想一想这合适吗?我可不希望我的机器人一会向前,一会向后,一会向左,一会又向右,机器人的运动轨迹非常的不平滑。而且还有一个最大的问题,机器人很难进行高速的运动。想一想机器人的车轮正在飞速的旋转,机器人在欢快的向前奔跑,突然控制器发来命令,说,“嘿,老哥,你下一时刻的前进方向在你后面,跟现在的正相反”。机器人听了是什么感受,我正先前飞奔,你现在让我倒退,玩我呢?就算是电机再好,老这么搞,电机也是遭不住啊!
    在这里插入图片描述
    所以,VFH+算法对此作出了改进,限制了机器人可选的前进方向,看上图b,大大平滑了运动轨迹。骑过小电瓶车的小伙伴应该都有感受,车速越快,越是忌讳急转弯,太危险了,搞不赢就躺地上了啊。也就是说,车速越快,转弯半径越大,相应的曲率就越小;车速越慢,可以承受的转弯半径就越小,相应的曲率就越大。如此,机器人的可选择的前进方向就只有上图b中被两个(转弯)圆夹出来的部分。(姑且叫它转弯圆吧,这名字应该好理解吧。)
    假如说机器人当前的速度是v ,对应的最小转弯半径是 R 。前面提过,障碍物的膨胀幅度是 r r + x r_{r+x} rr+x ,看下图
    在这里插入图片描述
    在机器人的前面存在两个障碍物A和B,这两个障碍物被膨胀之后分别为上图中两个阴影圆所示。机器人的左右侧两个转弯圆的半径为R,那么机器人会和障碍物碰撞的条件是什么呢?或者说满足什么条件的话,机器人很大概率上会撞上障碍物呢?上图中的障碍物A ,A 和左侧转弯圆的圆心的距离为 d C , A d_{C,A} dC,A 由于存在 d C , A < r r + x + R d_{C,A}<r_{r+x}+R dC,A<rr+x+R ,所以此时机器人再不采取措施避开A,大概率就撞上了。所以此时机器人应当向右偏转避开A,从A和B的中间穿过。

    那么机器人是怎么实现避开A 的呢?下图中,b是第二部分二值化之后的极坐标直方图。由于障碍物A和机器人的左侧转弯圆有重合部分,再加上机器人可选择前进方向是两个转弯圆之间夹出来的部分,那么对于机器人来说,从A 障碍物开始逆时针旋转大半圈(一直转到右侧转弯圆为止)都不可以通过,都是block。这一来二值化的极坐标直方图就从b变成了c,这时候机器人该选择哪一个方向前进就一目了然了。
    在这里插入图片描述

    4、第四部分:方向选择

    这一部分,对应VFH算法的第二部分——方向控制。只不过VFH是直接从第一步生成的极坐标直方图来生成方向,而VFH+是经过了第二部分和第三部分的处理之后才开始生成前进方向。

    VFH +和VFH的方向产生一样,只不过,VFH在这一步——考虑目标方向、当前方向、前一时刻方向。什么意思呢?在VFH算法中,方向控制就是单纯的从极坐标直方图生成前进方向,没有考虑目标在哪里、当前的方向为何、前一时刻方向为何;而且由于工作空间的更新,方向控制生成的前进方向变化比较剧烈,这也是导致机器人频繁的原地摆头的原因。VFH+算法同时将目标方向、当前方向、前一时刻方向考虑进来。采用如下的代价函数来得到最佳的前进方向

    g ( c ) = μ 1 ∗ Δ ( c , k t ) + μ 2 ∗ Δ ( c , θ n / α ) + μ 3 ∗ Δ ( c , k d , n − 1 ) g(c)=\mu_1*\Delta(c,k_t)+\mu_2*\Delta(c,\theta_n/\alpha)+\mu_3*\Delta(c,k_{d,n-1}) g(c)=μ1Δ(c,kt)+μ2Δ(c,θn/α)+μ3Δ(c,kd,n1)

    其中,第一项的 Δ \Delta Δ 是生成的前进方向和目标方向的差值,系数是 μ 1 \mu_1 μ1 ;第二项的 Δ \Delta Δ 是生成的前进方向和当前前进方向的差值,系数是 μ 2 \mu_2 μ2 ;第三项的 Δ \Delta Δ 是生成的前进方向和前一时刻前进方向的差值,系数是 μ 3 \mu_3 μ3 。通过配置三个系数的大小可以得到不同特性的VFH+算法。

    如果是第一项的系数最大,那么无疑我们更加看中目标方向的作用,这时候得到目标导向的VFH+算法。相应的路径很可能不是那么光滑。此时最好满足关系 μ 1 > μ 2 + μ 3 \mu_1>\mu_2+\mu_3 μ1>μ2+μ3 。这是论文作者提出来的,我不是太理解,我的三个系数分别是2、2、1,感觉效果也挺好的。可能是我还没有发现一些东西吧。

    如果第二项系数最大,那么说明我们更加看中路径的光滑程度。

    如果觉得路径还是不够光滑,当然可以增大 μ 2 \mu_2 μ2 ,然而如果 μ 2 \mu_2 μ2 太大,比如 μ 1 \mu_1 μ1 是1, μ 2 \mu_2 μ2 是100,那说真的,还搞个什么劲啊,直接取消第一项算了。所以第二项的系数也不能大的离谱,这时候就可以加入第三项,来使得路径更加的光滑。
    除此以外,还可以增加其他的项,比如我们还希望关注一下各个opening的宽度,这时候就可以考虑加入第四项将opening的宽度也纳入。

    展开全文
  • 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 ...
  • D*算法又称为动态A*算法,在未知环境或动态障碍物出现时,采用A*算法需要丢弃初始规划完成的open表和close表,重新进行规划。造成规划时间的增加,D*算法的核心思想是先用dijkstra或A*从目标点向初始点进行反向...
  • VFH避障/局部路径规划算法

    千次阅读 2021-08-31 16:43:04
    VFH避障/局部路径规划算法 本文章是我看《The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots》论文时候的笔记,感兴趣的欢迎去看原论文。 VFH中一些概念是从其他算法中借鉴过来的,并且VFH...
  • 文章针对近年来的无人驾驶汽车路径规划算法进行总结和归纳。首先对目前主流的环境建模方法进行阐述;其次对路径规划算法进行介绍,通过分析其优缺点,指出融合轨迹规划算法具有最好的适用性;最后总结当前研究挑战并提出...
  • 提出一种全局静态环境下移动机器人路径规划的改进势场蚁群算法.该算法采用人工势场法求得的初始路径和机器人与下一个节点之间的距离综合构造启发信息,并引入启发信息递减系数,避免了传统蚁群算法由于启发信息误导所...
  • dwa算法简介 动态窗口法(dynamic window approach, dwa),用于实现机器人的局部路径规划 实现原理: 在速度空间(v,w)中不断采样,模拟机器人在采样得到的速度下的运行轨迹,并针对这些轨迹进行评价,从而选取最优的...
  • NULL 博文链接:https://lvdccyb.iteye.com/blog/1328125
  • 常见的局部路径规划算法,先列出来,后面对算法做补充: 1.动态窗口法(DWA) 2.Time Elastic Band(Teb) 3.Eband方法(eband_local_planner) 4.lattcie planner 5.Vector Field Histogram(VFH及其改进的算法VFH...
  • 路径规划算法学习笔记(三)——局部路径规划(Dubins Curve)路径规划算法学习笔记(三)——局部路径规划(Dubins Curve)路径规划算法学习笔记(三)——局部路径规划(Dubins Curve)实际问题Dubins曲线基础问题关键CSC型CCC...
  • 路径规划算法简介

    千次阅读 2021-07-28 17:13:30
    文章目录前言一、传统路径规划算法二、图形学方法三、智能仿生算法四、其他算法总结 前言 移动机器人的自动探索需要对机器人进行路径规划,移动机器人的路径规划问题始于20世纪60年代。路径规划作为机器人导航最...
  • 路径规划中经典算法和发展趋势介绍
  • 路径规划算法介绍

    2021-11-27 14:21:33
    传统路径规划算法有:人工势场算法、模拟退火算法、禁忌搜索算法、模糊逻辑算法等。 模拟退火算法 模拟退火算法(Simulated Annealing,简称SA)诞生之初是用于求解复杂系统的能量分布问题lS。美国 IBM 公司物理学家S...
  • 路径规划算法

    千次阅读 多人点赞 2021-11-14 10:20:44
    文章目录前言一、传统路径规划算法1.Dijkstra算法2.A*算法3.D*算法4.人工势场法二、基于采样路径规划算法1.PRM算法2.RRT算法三、智能仿生算法1.神经网络算法2.蚁群算法3.遗传算法 前言 随着机器人技术、智能控制...
  • 路径规划问题转化为以加权路径网的以路径长度与通行时间的线性组合为目标函数的优化问题,并提出一种改进的蚁群算法应用于该问题,使规划路径更加符合各种要求。仿真结果表明,该算法能在较短时间内根据不同需求...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 90,452
精华内容 36,180
关键字:

局部路径规划有哪儿些算法