精华内容
下载资源
问答
  • #资源达人分享计划#
  • 移动机器人路径规划方法概览

    千次阅读 多人点赞 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

    展开全文
  • 移动机器人依据某个或某些性能指标(如工作代价最小、行走路线最短、行走时间最短等),在运动空间中找到一条从起始状态到目标状态、可以避开障碍物的最优或者接近最优的路径路径规划分为全局路径规划和局部路径...

    A 路径规划定义

    移动机器人依据某个或某些性能指标(如工作代价最小、行走路线最短、行走时间最短等),在运动空间中找到一条从起始状态到目标状态、可以避开障碍物的最优或者接近最优的路径。
    路径规划分为全局路径规划和局部路径规划

    • 全局路径规划:是宏观的规划,主要为机器人在运动中提供核心运动点,保证机器人安全到达目的地,但全局路径规划生成的可能不是一条轨迹,而是一些离散的点。
    • 局部路径规划:为了实现机器人的路线更加合理,还需要局部路径规划。它可以对机器人的速度、加速度等进行约束。

    B 构型/位型空间(configuration Space)

    构型/位型:能够反映机器人上每个点位置的变量
    在这里插入图片描述

    (a)中的 θ \theta θ角就是门的构型
    (b)中的点的坐标就是点的构型
    (c)旋转角度 θ \theta θ和坐标(x,y)构成硬币的构型。

    机器人的自由度能反映构型。

    构型/位型空间(C-space):包含机器人所有构型的n维空间


    在这里插入图片描述
    二自由度机械臂的两个关节角构成它的C-space,中间图为C-space的拓扑空间,最右为其坐标表示。


    C 障碍物与构型空间

    将构型空间障碍物 Q O 1 QO_1 QO1定义为机器人与工作空间中的障碍物 W O 1 WO_1 WO1相交的构型集合。

    自由空间或自由构型空间 Q f r e e Q_{free} Qfree是机器人不与任何障碍物相交的构型集合。
    在这里插入图片描述

    黄色为机器人;蓝色为障碍物。


    例子:
    圆为机器人,三角形为障碍物
    在这里插入图片描述

    由于机器人本身是有工作半径的,把三角形机器人半径宽的外环都划分为障碍物部分。则自由此例子的自由构型空间就是实际障碍物部分。


    C 环境模型建立

    定义:建立机器人所处环境中的各种物体,包括障碍、路标等的准确空间位置描述,即建立空间模型或地图。

    两种建立环境模型方法:
    <1>栅格法
    所谓栅格法,是将移动机器人需要工作的环境信息分割成等大小的正方形栅格,此方法是W.E.Howden提出的,并成为移动机器人路径规划最常用的地图建模方法。
    如:
    在这里插入图片描述


    栅格法环境信息表示方法:
    障碍物栅格赋值为1,自由空间栅格赋值为0。
    在这里插入图片描述
    重要参数:栅格大小:
    栅格法建模,栅格大小的选取尤为重要,既要考虑机器人尺寸,也要考虑到整个环境的复杂程度。
    在这里插入图片描述

    较为理想的栅格单位长度为机器人的直径大小。


    栅格法环境信息表示方法:
    在这里插入图片描述


    栅格地图的标识方法:
    栅格地图建立模型后,需要将整个二维工作区内的栅格单元用序号法或直角坐标系法进行标识。这样有助于移动机器人对栅格单元位置的记录,分辨出是障碍物栅格还是可以通过的自由空间栅格。
    在这里插入图片描述
    <2>可视图法

    所谓可视图,是在二维情况下,起点S、障碍物的顶点以及目标点G相连,并确保所有直线段不穿过障碍物,得到的图称之为可视图。

    在这里插入图片描述


    D 欧氏距离与曼哈顿距离

    <1>欧氏距离
    在二维和三维空间中的欧氏距离的计算公式分别为:

    在这里插入图片描述
    两个n维向量 a ( x 11 , x 21 , . . . , x 1 n ) a(x_{11}, x_{21},..., x_{1n}) a(x11,x21...,x1n) b ( x 21 , x 22 , . . . , x 2 n ) b(x_{21},x_{22},..., x_{2n}) b(x21,x22,...,x2n)间的欧式距离为:
    ρ 12 = ∑ k = 1 n ( x 1 k − x 2 k ) 2 \rho _{12}=\sqrt{\sum_{k=1}^n(x_{1k}-x_{2k})^2} ρ12=k=1n(x1kx2k)2

    <2>曼哈顿距离
    顾名思义,在曼哈顿街区,要从一个十字路口到另一个十字路口,驾驶距离显然不是两点间的直线距离,这个实际驾驶距离就是曼哈顿距离,它也称为城市街区距离。
    在这里插入图片描述


    展开全文
  • 扫地机器人有这些路径规划方法

    万次阅读 2017-03-16 22:08:15
    路径规划技术是扫地机器人研究的核心内容之一,机器人定位与环境地图构建就是为路径规划服务的。所谓机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务...
    
    路径规划技术是扫地机器人研究的核心内容之一,机器人定位与环境地图构建就是为路径规划服务的。所谓机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务。

      通常,移动机器人路径规划需要解决3个问题:

      1)使机器人能从初始位置运动到目标位置;

      2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;

      3)在完成以上任务的前提下,尽量优化机器人运行轨迹。

      移动机器人的路径规划根据其目的的不同可以分为两种,一种是传统的点到点的路径规划,另一种就是完全遍历路径规划。

      点到点的路径规划是一种从起始点到终点的运动策略,它要求寻找一条从始点到终点的最优(如代价最小、路径最短、时间最短)并且合理的路径,使移动机器人能够在工作空间顺利地通行而不碰到任何障碍物。完全遍历路径规划是一种在二维工作空间中特殊的路径规划,指在满足某种性能指标最优或准优的前提下,寻找一条在设定区域内从始点到终点且经过所有可达到点的连续路径。

      对于扫地机器人来说,其作业任务是清扫房间,它的路径规划属于完全遍历路径规划,需满足两个指标:遍历性和不重复性。所谓遍历性是指扫地机器人运动轨迹需要最大程度的遍布所有可大空间,它反映的是机器人的工作质量问题。所谓不重复性是指扫地机器人的行走路线应尽量避免重复,反映的是机器人的工作效率问题。

      扫地机器人的自主寻路可以分为两种:随机覆盖法和路径规划式。

      | 随机覆盖法

      随机覆盖法,有人也称为随机碰撞式导航,但这并非是指机器人真正与环境中的物体产生碰撞,也非毫无章法的在地板上随机移动,换言之在工程操作中“随机”也是一个难以达到要求,随机覆盖法是指机器人根据一定的移动算法,如三角形、五边形轨迹尝试性的覆盖作业区,如果遇到障碍,则执行对应的转向函数。这种方法是一种以时间换空间的低成本策略,如不计时间可以达到 100%覆盖率。随机覆盖法不用定位、也没有环境地图,也无法对路径进行规划,所以其移动路径基本依赖于内置的算法,算法的优劣也决定了其清扫质量与效率的高低。

      美国iRobot公司研发的iRobot Roomba 3-8系列是随机碰撞寻路系统的典型代表。

      据称,其采用iAdapt智能化清扫技术的专利技术,这是一种软、硬件相结合的智能化AI清扫系统,硬件由Roomba前方的若干红外探测器、底部灰尘侦测器和落差传感器、毛刷胶刷边刷测速系统等等组成,通过Roomba的硬件传回的信息,iRobot自身的软件可以对回传信息进行分析,根据红外回传信息的强度、范围、高度、转速、电流大小、阻力等参数,计算出前方障碍物大致形状,再经过软件的处理运算,得出的结果就是Roomba下一步清洁方式,Roomba以每秒60次的速度计算周边障碍物的情况,同时根据所处环境作出40余种清扫动作,如围绕、折返、螺旋、贴边、转身等等。

      其次iRobot采用面积模糊判定算法,根据房间面积自动设定清扫时长。和路径规划不同的是,Roomba开始收集算法估算所需的两个重要参数:单次行进距离和单位时间碰撞频率。单次行进距离越长则间接代表房间面积越大,走几步就调头则间接代表房间面积较小。每次碰撞Roomba都能收集到相关信息,单位时间内碰撞频率越高代表房间面积越小,碰撞频率低则表示需要清扫的面积较大。

      市面上大多数扫地机器人虽都采用随机碰撞寻路方式,然而清洁效率却差异很大,归根到底还是软件算法上的问题,这也是为什么同样大家买的都是随机碰撞寻路方式的扫地机器人,在覆盖率与效率上面却有天壤之别。

      | 路径规划式

      规划式导航需要建立起环境地图并进行定位。对路径规划的研究已经持续很多年了,也提出了很多种类的方法。不同的方法有各自的优缺点,适用范围各不相同,没有一种路径规划方法能适用于所有的环境信息。其中的人工势场法、栅格法、模板模型法、人工智能法等是路径规划中很典型的方法,并且受到越来越多的关注。下面将分别介绍上述这些典型的路径规划方法。

      1.人工势场法

      人工势场法是机器人导航中提出的一种虚拟力法,其基本方法是将机器人在周围环境中的运动设计成在一种势场中的运动,是对机器人运动环境的一种抽象描述,机器人在场中具有一定的抽象势能,势能源有两种:斥力极和引力极。

      机器人在不希望进入的区域和障碍物属于斥力极:目标及机器人系统建议通过的区域为引力极。在极的周围产生相应的势,在任何一点的势为该点产生的势之和.该势的负梯度称为势力。势场的建立主要用于动态避障,此时的引力极是局部环境中的中间目标,斥力极则是局部环境中的障碍物。引力和斥力的合力作为机器人的加速力,来控制机器人的运动方向和计算机器人的位置。该方法结构简单,便于低层的实时控制,在实时避障和平滑的轨迹控制方面,得到了广泛的应用。但对存在的局部最优解的问题,容易产生死锁现象,因而可能使机器人在到达目标点之前就停留在局部最优点。

      2.栅格法

      设定移动机器人实际几何形状可用方形区域表示。规划过程中将机器人缩为一个点,而环境中的障碍物边界做相应的扩展及模糊化处理。采用网格表示工作空间,即把工作空间划分为一个个大小相同的方格,方格大小与机器人几何外形相同。

      用栅格法表示环境:使用大小相同的栅格划分机器人的工作空间,并用栅格数组来表示环境,每个栅格是两种状态之一,或者在自由空间中,或者在障碍物空间中。这种方法的特点是简单,易于实现,从而为路径规划的实现带来了很多方便,具有表示不规则障碍物的能力;其缺点是表示效率不高,存在着时空开销与精度之间的矛盾,栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。栅格划分大了,环境信息存储量就小了,规划时间短,分辨率下降,在密集环境下发现路径的能力减弱;栅格划分小了,环境分辨率高,在密集环境下发现路径的能力强,但环境的存储量大。所以栅格的大小直接影响着控制算法的性能。

      3.模板模型法

      另外一种常用的方法是模板模型。DeCaravalh提出了一种依靠二维清洁环境的地图并且是基于完全遍历路径规划的模板。为了完成完全遍历路径规划,DeCaravalh定义了五种模板,分别是:前进模型(Towards Model),沿边转向模型(Side Shift)、回逆跟踪(Backtracker),U转弯模型,U转弯交替模型。模板模型法是基于先验知识和先前的环境地图遍历机器人让得到的环境信息来匹配事先定义的模板。因此,整个路径就是一系列的模板组成的。在这个方法中,为了简化路径规划过程,环境事先扩大,这样这种小巧灵活的机器人就可以考虑成一个质点。基于模板的模型完全遍历路径规划,它要求事先定义环境模型和模板的记忆,因此对于变化着的环境就不好处理了,比如在遍历机器人的工作过程中突然出现一个障碍等。

      4.人工智能法

      近年来有许多学者利用模糊逻辑、人工神经网络、遗传算法等现代计算智能技术来解决机器人的路径规划问题,并取得了一些可喜的成果。

      1)模糊控制算法

      模糊控制方法应用与路径规划,是一种很有特色的方法,是在线规划中通常采用的一种规划方法,包括建模和全局规划。它用若干个传感器探测前方道路和障碍物的状况,依据驾驶员的驾车经验制定模糊控制规则,用于处理传感器信息,并输出速度、加速度、转角等控制量,指导小车的前进。该方法最大的优点是参与人的驾驶经验,计算量不大,能够实现实时规划,可以做到克服势场法易产生的局部极点问题,效果比较理想。

      模糊控制的路径规划方法特别适用于局部避碰规划,具有设计简单、直观、速度快、效果好等特点。

      2)神经网络路径规划

      神经网络已经被应用到很多的工程领域,机器人领域当然也不例外。神经网络在路径规划中的应用也很多。Tse为清扫移动机器人从一个地方到另外一个地方的运输,提出了BP神经网络,这个模型通过自学习能进行自主导航的路径规划。避障的完全遍历路径规划能够通过离线学习达到,并且有运动行为,路线规划和全局路径规划三个步骤。在运动行为阶段机器人通过各种传感器采集3d环境信息,然后把这些信息输入到BP神经网络中,机器人可以清扫周边的区域直到周边没有未清扫区域。在路线规划阶段,清洁机器人要决定一条最短的路径通向工作空间中其他未清扫区域,在全局路径规划中,产生一个全局环境地图,然后机器人从起始点开始,清扫整个工作空间。

      3)遗传算法

      遗传算法是由JohnH oland在70年代早期发展起来的一种自然选择和群体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖,交配和突变现象。它将每个可能的解看作是群体(所有可能解)中的一个个体,并将每个个体编码成字符串的形式,根据预定的目标函数对每个个体进行评价,给出一个适合值。开始时总是随机地产生一些个体(即候选解),根据这些个体的适合度利用遗传算法(选择、交叉、变异)对这些个体进行交叉组合,得到一个新的个体。这一群新的个体由于继承了上一代的一些优良性质,因而明显优于上一代,这样逐步朝着更优解的方向进化。遗传算法对于复杂的优化问题无需建模和进行复杂的运算,只要用遗传算法的三种算子就能找到优化解,因而在各种领域中得到了广泛的应用。在机器人相关领域研究中,遗传算法已被应用于机械手的轨迹生成、多机器人的路径规划、冗余机械手的障碍避碰。

      另一方面,当遗传算法与模糊逻辑,人工神经网络等技术相结合,组合成一个智能学习和进化系统时,便显示了它的强大威力。有很多学者综合运用上述智能方法作了路径规划的尝试。如Toshio Fukuda等人提出了一个具有“结构化智能”的机器人导航系统。它以模糊控制器为核心。路径规划的一种分层决策机构,并且根据反馈得到的奖赏,惩罚信息进行学习和进化。其优点是系统自学习能力,这也是其研究的侧重点,然而他们把系统做的比较复杂,效率较低。

      | 总结

      移动机器人的路径规划技术已经取得了丰硕成果,但各种方法各有优缺点,也没有一种方法能适用于任何场合,如模版匹配方法过于依赖机器人过去的经验; 人工势场路径规划方法通常存在局部极小点和计算量过大的问题。不过随着科技不断发展,这些问题都会出现新的解决或者替代方法,同时机器人应用领域还将不断扩大,机器人工作环境会更复杂,移动机器人路径规划这一课题领域还将不断深入。


    http://www.asmag.com.cn/tech/201606/75508.html


    展开全文
  • 本文聚焦于不完整约束机器人在已知环境中的覆盖问题,假定覆盖路径已经规划成功,本文聚焦于如何让机器人执行该路径 提示:以下是本篇文章正文内容,下面案例可供参考 一、机器人 幻宇阿克曼机器人 二、机器人-...

     前言

    覆盖路径规划是一类特殊的路径规划问题,其复杂度与机器人运动学约束和环境复杂度相关。本文聚焦于不完整约束机器人在已知环境中的覆盖问题,假定覆盖路径已经规划成功,本文聚焦于如何让机器人执行该路径


    提示:以下是本篇文章正文内容,下面案例可供参考

    一、机器人

    幻宇阿克曼机器人

    二、机器人-覆盖路径规划-实物试验

    1.基于slam生成地图

    第一步是获取环境信息,可以使用各种slam方法生成环境信息。本文使用gmapping_slam,通过手动设置导航点来生成目标区域的地图信息。当然,环境比较大的时候,可以用诸如前沿的方法生成地图。

    2.根据地图信息,规划覆盖路径

    参考机器人环境边界、障碍物边界、机器人最大最小速度、最大最小角速度,使用astp\STC等算法规划出覆盖路径。

    参考链接:https://www.mathworks.com/matlabcentral/fileexchange/63308-ewingkang-dubins-curve-for-matlab?s_tid=FX_rc2_behavhttps://www.mathworks.com/help/uav/ug/motion-planning-with-rrt-for-fixed-wing-uav.html

    3. 机器人执行路径

    基于机器人发布的amcl_pose信息,控制机器人跟随规划的路径运动。路径跟随最广泛应用的就PID算法或追踪算法。(PID资料可见https://blog.csdn.net/u013468614/article/details/103492847

    全向机器人的PID控制比较容易,但是阿克曼机器人的PID很难控制。阿克曼机器人有前进速度和角速度两种。前进速度对应x,y,z三个方向的分量,因为阿克曼机器人只能前进或者后退,所以vy,vz值为0;角速度可以控制机器人转向,包含x,y,z,w四元组。机器人如果偏离规划的路径,需要调整转角速度使得机器人回到预期的路径上。这个角速度由偏移量控制,偏移量越大,角速度越大。但是实际测试过程发现,很难由位置偏移来计算角速度,其对应的PID控制会使得机器人一直在转圈。

    另一个方法是使用/cmd_vel机器人发布速度命令,控制机器人直行和转弯。但是与实际路径会有偏差,当偏差特别大的时候,调用teb_local_planner将机器人导航到目标位置进行校偏。就这样不停的校偏,最终也能实现覆盖。

    在实验过程中遇到诸多问题,目前第三步还没有执行成功。机器人的雷达还坏了,特此记录一下。等机器人配件到了,再实现第三步。


    总结

    阿克曼机器人-实物试验-覆盖路径规划-PID

    展开全文
  • 针对这些不足,提出了能够计算出拐点、旋转方向及旋转最小角度的A* 路径规划改进算法并进行了实验。移动机器人定位实验结果表明:利用改进后的A* 路径规划算法不仅简化了路径,而且在拐点处移动机器人能够调整自身...
  • 对于自由漂浮空间机器人,位置级逆运动学方程不适合于笛卡尔连续路径的规划,而且机械臂的运动会对基座产生扰动.为此提出了基于速度级逆运动学方程的方法,可实现5 个目标:1)惯性空间连续位姿跟踪;2)基座姿态无扰动的...
  • 目的是在不与障碍物碰撞的情况下最小路径长度和匝数。 在仿真研究中,采用两种具有不同障碍物分布的静态环境测试场景来评估该方法的性能。 仿真结果表明,该方法能够在复杂环境下生成无碰撞路径
  • CBS多机器人路径规划

    千次阅读 2021-06-06 15:37:04
    CBS多机器人路径规划
  • 机器人路径规划之Dijkstra算法

    千次阅读 2020-07-15 20:19:02
    Dijkstra算法(狄克斯特拉算法)是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。 基本原理 其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。 以下图为例,计算左上角...
  • 机器人全局路径规划算法——A*

    千次阅读 2020-02-29 14:47:32
    我们的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。 如上所述, G 是从起点A移动到指定方格的移动代价。在本例中,横向和...
  • 为了使机器人的固定成本和机器人操作成本之和最小,建立了整数规划模型,并设计了求解该模型的遗传算法。 为了使各个机器人协调高效地完成各自的任务,本文采用自然数编码方式。 目标函数基于惩罚项,该惩罚项由...
  • 代价地图(costmap)用于导航,机器人最小cost总和完成任务。 规划:基于得到的机器人位置信息及环境地图信息,以及给定的目标点,规划完成导航任务。 规划包括:全局规划和局部规划。 全局规划是基于占用栅格...
  • 为了机器人在寻路的过程中避障并且找到最短距离,我们需要使用一些算法进行路径规划(Path Planning),常用的算法有Djikstra算法、A*算法等等,在github上有一个非常好的项目叫做PythonRobotics,其中给出了源代码...
  • DWA算法是基于机器人运动学与动力学理论的一种局部避障算法,它将对机器人的位置控制转换为对机器人的速度控制。DWA算法可以概括为三步:一是根据机器人自身的限制以及环境制约将速度的采样空间约束在一定范围内; 二...
  • 比如(-1,-1),同时机器人在寻路过程中遵循“下右上左”的原则,即机器人先向下行走,当机器人前方遇到障碍物时,机器人转向右走,遵循这样的规则,机器人最终可以搜索出所有的可行路径,并且机器人最终将返回起始...
  • 总感觉动态规划问题有理解不扎实,拿了2道dp基础题打夯,最小路径和 & 机器人走方格。 一. 最小路径和 64. 最小路径和 [ 题目描述 ] 给定一个包含非负整数的 mxn网格grid ,请找出一条从左上角到右下角的...
  • 一、简介 DWA算法全称为dynamic window approach,其原理主要是在速度空间(v,w)...(一)移动机器人受自身最大速度最小速度的限制 (二) 移动机器人受电机性能的影响:由于电机力矩有限,存在最大的加減速限制,因此移
  • 自主移动机器人的导航就是让机器人可以自主按照内部预定的信息,或者依据传感器获取外部环境进行相应的引导,从而规划出一条适合机器人在环境中行走的路径。定位,就是机器人通过已经观测到的环境信息,结合自身已知...
  • 文章针对移动机器人系统在复杂环境中搜索目标和寻求最短路径问题,介绍了一种基于MMAS的机器人路径规划新方法;在MMAS算法的信息素更新中,采用了最大-最小蚂蚁系统的思想动态调整信息素,加强了正反馈的效果,同时...
  • 文章着重对移动机器人路径规划和多机器人调度问题展开研究。 1.针对移动机器人路径规划问题,在蚁群算法基础上做出了巨大改进,设计了基于独狼蚁群混合算法的路径规划,算法在路径选择方向、信息素控制和路径停滞上...
  • 提出了基于粒子群径向基函数网络的矿井救援机器人局部路径规划研究。利用算法模拟矿井复杂环境对救援机器人进行训练,调整权值,从而得到最优解,同时利用确定性局部规划算法来优化粒子群算法,使其对局部的处理更加合理...
  • MATLAB--基于蚁群算法的机器人最短路径规划

    千次阅读 多人点赞 2020-03-14 11:06:29
    路径规划是实现移动机器人自主导航的关键技术,是指在有障碍物的环境中,按照一定的评价标准(如距离、时间、能耗等),寻找到一条从起始点到目标点的无碰撞路径,这里选取最短距离路径规划的评价标准,即最短路径...
  • 然后采用NLP算法,把移动机器人在未知环境中的路径规划问题,描述成了满足一组非线性约束和目标函数最小的非线性规划问题,从而实现复杂未知环境下机器人路径规划。最后进行物理与仿真实验,验证了该方法的有效性。
  • 将状态空间离散化为网格,利用立体视觉和平面提取方法建立环境地图,将仿人机器人的轮廓简化为双圆柱模型进行避障检测,最终在环境地图中搜寻代价最小的一系列可行的动作作为路径,通过仿真实验验证了方法的有效性。
  • 基于粒子群优化算法的移动机器人全局路径规划-附代码 文章目录基于粒子群优化算法的移动机器人全局路径规划-附代码1.问题描述与建模2.基于粒子群算法的路径规划3. 实验结果4.参考文献5.Matlab代码 摘要:本文主要...
  • 施工过程涉及很多过程,因此有必要优化施工机器人路径规划。 大多数研究更多地集中在优化算法上,而较少关注基于这些算法的优缺点的比较分析。 因此,本文的创新之处在于分析三种先进的优化算法(遗传算法,混合...
  • 这里写自定义目录标题移动机器人路径规划算法介绍及A*算法详解路径规划算法总结各种算法比较A*算法详解 移动机器人路径规划算法介绍及A*算法详解 随着人工智能的兴起,移动机器人逐渐走入了更多人的视线,ML和DL为...
  • 移动机器人路径规划问题 移动机器人运动轨迹规划是移动机器人导航技术的核心技术之一。我认为移动机器人的导航技术无疑是在解决三个问题:①我现在在何处?②我要往何处去?③我要如何到那里去? 在智能服务机器人...
  • 在处理工业机器人的离线编程时,有一些复杂的软件可用于机器人路径规划,其中一个是Fraunhofer Chalmers中心开发的工业路径解决方案(IPS)。在寻找机器人路径时,有一件事没有考虑到,那就是机器人的电缆梳理台可能...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,622
精华内容 4,248
关键字:

机器人最小时间路径