精华内容
下载资源
问答
  • 2021-06-30 16:27:33

    VO速度障碍算法学习

    索引

    VO

    在这里插入图片描述

    1. VO避障

    VO相对简单,尤其是在假设障碍物静止之前几乎没有任何理解难度
    然而在添加障碍物移动之后,速度障碍区的移动可能需要理解一些时间

    RVO

    在这里插入图片描述

    RVO是VO的变种,能解决VO所产生的抖动问题
    建议阅读顺序如下所示

    1. VO+RVO算法解释能够在学习VO的基础上稍微知道RVO的存在
    2. RVO与ORCA是如何工作的能够帮助理解RVO在做些什么
    3. RVO算法中文翻译能够在 第二步 的基础上了解RVO的计算方式,RVO是怎么做的
    4. RVO英文论文。回归本心,第三步帮助初步了解RVO,但RVO究竟是如何做到消除抖动的方法与证明,并对RVO做出泛化解释

    ORCA

    ORCA笔记
    ORCA详解
    ORCA英文论文

    NHORCA

    更多相关内容
  • 速度障碍法,非原创,有兴趣自己慢慢看,摘取自己需要的部分就好
  • 本文是研究速度障碍法的英文论文,论文以多个智能体为研究对象,研究速度障碍法在智能体避障时的应用,研究了速度障碍法在多智能体避障时的最优速度选择问题。
  • #资源达人分享计划#
  • 针对多移动机器人运动协调中的动态安全避碰问题,在分析速度障碍法原理的基础上,设计用于机器人之间相互避让的互动速度法则,并通过制定机器人的碰撞时间、碰撞距离因子对构型障碍的大小进行实时调整,把运动障碍物...
  • 避免加速度和速度障碍的相互碰撞 我们提出了一种考虑到加速约束的移动机器人避碰方法。 我们讨论了在移动障碍物中导航单个机器人的情况,以及在导航公共工作空间时相互避免碰撞的多个机器人的情况。 受速度障碍概念...
  • 针对相互速度障碍物(RVO)模型缺少全局路径规划,只依靠局部碰撞避免不能很好地模拟复杂的疏散场景问题,提出了一种剩余路径代价尽量小的动态全局路径选择方法。该方法包含路径预处理和路径实时更新两部分:第一部分...
  • 基于相对速度避障的matlab平台仿真程序可用
  • RVO2100/RVO2100L使用说明
  • ros_asv_system

    2021-05-29 14:56:34
    asv_ctrl_vo :用于避免碰撞的“速度障碍”算法的实现。 asv_path_trackers :实现(整体)视线(LOS)方法和简单的路径跟踪纯追踪方案。 asv_msgs :系统中使用的消息类型。 asv_obstacle_tracker :充当“黑...
  • 针对应用广泛的局部避障算法-----动态窗口(DWA)穿越稠密障碍物时存在路径不合理、速度和安全性不能兼顾等问题,提出参数自适应的DWA算法,根据机器人与障碍物距离和障碍物的密集度自动调整目标函数中的权值,以自适应...
  • 检测障碍物是机器人自主移动的基础. 为了提高检测的障碍物效率和准确率, 提出一种基于RGBD... 因此, 改良的帧差检测障碍物轮廓准确率高, 坐标转换法速度快, 可以证明基于RGBD摄像头的障碍物检测设计检测效果良好.
  • 将移动机器人的速度分解为目标方向速度和避障方向速度,通过分析移动机器人与障碍物的相对速度和相对位置之间的夹角,以此改变移动机器人的避障方向速度大小来完成移动机器人对动态障碍物的避障。仿真实验结果表明:该...
  • 此外,用O表示非智能障碍物o的集合,Po表示障碍物的当前位置,VO表示障碍物的当前速度。对于静态障碍物,速度为0. 整体过程如下: 首先我们选定一个很短的时间段作为模拟过程的时间间隔,表示为Δt 在每个时间段内,...

    原文地址:https://www.researchgate.net/publication/221073351_Reciprocal_Velocity_Obstacles_for_Real-Time_Multi-agent_Navigation

    1. 简介

    近些年,多个移动智能体的运动规划问题成为一个越来越受关注的问题。无论在机器人领域,还是在视频游戏等多个其他领域,该问题都有很多的影响。解决这类问题的一个普遍思路是进行持续的导航。这些方法通常包括一个持续的“感知——行动”循环,在每个循环中,智能体通过感知模块观察周边环境,并通过行动模块进行移动。在这个过程中,全局路径规划和局部碰撞避让往往是解耦的。

    因此,局部避障技术成为解决这类问题的关键技术,有很多人提出过各种方法。VO就是其中一种被广泛使用的方法。然而,这些模型通常都是基于障碍物是不能感知周围环境的非智能体,只能被动的沿预定速度运动的情况。然而这种假设导致这些模型无法适用在障碍物也可以进行避障,或多智能体互相避障的情形。在这种多智能体互相避障的情况下,往往会出现一些不符合预期的,且不真实的抖动现象。

    2. 简单介绍VO及其问题

    关于VO避障的详细内容可以参照我的这篇文章:VO避障,本文只做简单的介绍。

    2.1 VO避障的定义

    我们用A表示平面上正在进行移动的智能体,此时所在位置为PA,用B表示同一平面上的移动障碍物,此时位置为PB。用VOAB(VB)表示若持续以速度VB移动的情况下,在之后的某个时间会导致AB发生碰撞的所有A的速度VA的集合。

    定义1:
    VOAB(VB) = { VA | λ(PA, VA - VB) ∩ B ⊕ -A ≠ φ}

    其中:

    • λ(p,v) = { p + tv | t >= 0}
    • A ⊕ B = { a + b | a ∈ A,b ∈ B }
    • -A = { -a | a 属于A }

    上式表明,如果VA ∈ VOAB(VB),那么A和B将在之后的某个时间发生碰撞,否则,VA便是在B的VO区域之外,二者将不会发生碰撞。如果VA位于VO的边界上,则在将来的某个时刻,A和B将会刚好擦肩而过(切线机动)。

    图1:
    图1
    上图为VO区域的示意图,由图可知,VO区域是一个以VB为顶点的圆锥形。

    2.2 VO避障的属性

    现在,我们对VO的一些基本属性进行推导:

    引理 2:
    引理2
    引理 3:
    引理3
    从上文定义1即可推导出引理2和引理3.

    图2:
    图2
    此时,我们将VO之外的区域也考虑进去,如上图所示,通过VO 区域的两条边界,将VO之外的区域分成两个半平面。并且我们增加两种符号:

    1
    如果:
    v1
    表示VA位于VO之外的左半边区域内,这个区域内的速度会让A从B的左侧穿过。

    类似的,如果:
    v2
    则表示VA位于VO之外的右半边区域内,这个区域内的速度会让A从B的右侧穿过。

    注意图2中,左半边和右半边区域有一部分重叠区域,这个区域内的速度会让A与B分离。

    对于上文中所说的引理2和引理3,他们对于VO之外的区域依然有效。即,引理中的∈号可以被我们刚定义的两种符号中的任意一种代替。

    引理4:
    L4

    2.3 抖动现象

    在将VO避障的概念应用与多个智能体的导航场景中时,每个智能体都会将其他的智能体视为移动的障碍物,并根据对方的信息和自己的信息计算生成VO区域,然后从VO之外的区域中选择一个速度进行避障。理想状态下,通过这一系列行为,将使二者避开彼此继续前进,然而,实际情况下,却可能会出现预期之外的抖动现象。

    想象如下情景:
    两个智能体A和B分别以VA和VB的速度前进,且VA和VB分别在对方的VO区域内。因此,如果双方继续以当前速度移动下去,必然会发生碰撞。此时,智能体A从针对B的VO区域之外选择了速度VA‘。同时,智能体B也进行了避障操作,从针对A的VO区域之外选择了速度VB’。

    这种行动的结果是,A和B的速度都发生了变化,从而二者针对对方的VO区域也发生了变化。根据引理2,我们可以推导出,二者原来的速度都不在新的VO区域内:

    VB’ ∉ VOAB (vA) → VA ∉ VOBA (vB’)
    VA’ ∉ VOBA (vB) → VB ∉ VOAB (vA’)

    如果A和B之前的速度(VA和VB)分别是各自的最优速度(如该速度是直接指向目标点的速度),而此时计算该速度并不在当下的VO区域内(新VO区域),那么A和B由于倾向性,会再次选择最优速度,也即VA和VB。于是二者又再次回到原来的状态,并且在下一个循环中再次重复上面的行为,从而产生抖动现象。

    3. RVO介绍

    本节中我们将介绍一种解决上述抖动问题的新方法——RVO。它通过一种简单的方式来达到多智能体安全平滑的导航,并且在这个过程中,智能体之间不需要互相通信。

    3.1 定义

    RVO的基本思想很简单:在避障行为的速度选择时,与VO避障中智能体单纯选择VO区域之外的速度不同,这里我们选择的新速度是VO之外的某个速度与当前速度的平均值。

    RVO的一般定义如下:
    RVOAB(VB,VA) = {VA’ | 2VA’ - VA ∈ VOAB(VB)}

    RVOAB(VB,VA)表示A的当前速度与VO区域VOAB(VB)内任意速度的平均速度的集合。对原VO区域进行平移,使其顶点移动到(VA + VB)/2时,便可得到此RVO区域的范围,如下图:

    图3:
    图3

    3.2 证明

    下面我们将证明RVO的两点特性:无碰撞和无抖动。

    3.2.1 无碰撞

    假设A当前速度VA,B当前速度VB,AB分别选择RVO区域之外的速度VA’ 和 VB’。在AB都选择自己的同一边(左或右)进行避障时,下面的引理会证明此时是安全无碰撞的。

    引理6:

    T6
    T6证明
    这里的符号实在打不出来。。。就直接截图了,证明过程很简单,运用上文的各种引理很容易就能推导得出。

    3.2.2 同边选择

    对于AB需要同时选择各自同一边的这个前提,当二者中有一个选择了RVO外与当前速度最接近的速度时(下文简称最近避障速度),我们可以证明得到,另外一个智能体,也会对应做出同一选择。这个论断基于以下事实:

    • 对于智能体A,如果VA + u是其对于B的最近避障速度,那么对于智能体B,其对于A的最近避障速度为VB-u
    • 对于智能体A,如果其对于B的最近避障速度在RVO区域的右侧,则对于智能体B,其对于A的最近避障也位于RVO区域的右侧(左侧同理)。

    属于和不属于对于以上事实同样适用。

    引理7:

    VA + u ∉ RVOAB(VB, VA) ↔ VB - u ∉ RVOBA(VA, VB)

    证明:
    VA + u ∉ RVOAB(VB, VA)
    ↔ 2(VA + u) - VA ∉ VOAB(VB)
    ↔ 2(VB - u) - VB ∉ VOBA(VA)
    ↔ VB - u ∉ RVOBA(VA, VB)

    3.2.3 无抖动

    当选择最近避障速度时,也可保证不会发生抖动现象。以下引理可证:

    引理8:
    VA ∈ RVOAB(VB, VA) ↔ VA ∈ RVOAB(VB - u, VA + u)

    证明:
    VA ∈ RVOAB(VB, VA)
    ↔ 2VA - VA - VB ∈ VOAB(0)
    ↔ 2VA - VA - VB - u + u ∈ VOAB(0)
    ↔ VA ∈ RVOAB(VB - u, VA + u)

    由以上引理可知,对于智能体A而言,当AB同时选择最近避障速度时,AB的新速度分别是VA+ u 和 VB- u ,此时又构成了新的RVO区域 RVOAB(VB - u, VA + u),而A在避障前的旧速度VA仍然在此时的新RVO区域之内,因此A不会在之后再次选择VA,对于B同理,这样就避免了抖动现象的发生。

    3.3 RVO推广

    在上面的内容中,我们隐式地假设了每个智能体在避免碰撞的过程中各自平均分担了相同的避让。而实际上,各个智能体之间可能在规避碰撞的过程中分别承担不同比例。基于这个理念,我们将RVO的概念进行推广。在AB避障模型中,我们定义αAB为整个避障过程中A所承担的部分,自然地,B所承担的部分即为αBA = 1 - αAB(可见,在之前的表述中,我们一直都是在隐式的假设 αAB = αBA = 1/2)。
    其表达的思想是,对于智能体A而言,在避障时选择的新速度VA’不再是当前速度VA与RVO区域外的任意速度VRA二者的平均值(1/2 )VA + (1/2)VRA,而是按照一个动态的权重进行划分,即VA’ = αABVR + (1 - αAB)VA。整理可得 VR = (1/αAB)VA’ + (1 - 1/αAB)VA。智能体B同理。由此我们可以推广RVO的定义:

    RVOAB(VB, VA, αAB) = {VA’ | (1/αAB)VA’ + (1 - 1/αAB)VA ∈ VOAB(VB)}

    同样的,对原VO区域进行平移,使其顶点位于点(1 - αAB)VA + αABVB 时,便可得到此时RVO区域的范围,如下图。

    图4:
    图4
    上文中的各个引理对于RVO的推广定义依然适用(有兴趣的老板自己证吧),因此对于广义的RVO来讲,依然是满足无碰撞无抖动的。

    4.多智能体环境下的应用

    本节介绍的是RVO在拥有大量智能体以及静态和非静态非智能障碍物的环境中的应用。
    给定n个智能体A1…An,每个智能体Ai对应的当前位置表示为Pi,当前速度表示为Vi,目标位置表示为gi,优先速度表示为Vprefi。此外,用O表示非智能障碍物o的集合,Po表示障碍物的当前位置,VO表示障碍物的当前速度。对于静态障碍物,速度为0.
    整体过程如下:

    • 首先我们选定一个很短的时间段作为模拟过程的时间间隔,表示为Δt
    • 在每个时间段内,为每个智能体独立地选择新的速度,并据此更新其位置
    • 持续这个过程,直到所有智能体都达到其目标位置

    因此,在整个模拟过程中,每一步的新速度选择是最关键的地方。

    4.1 CRVO(组合RVO区域)

    在之前的内容中,我们探讨了由一对智能体组成的系统的RVO区域。当环境扩展为由许多个智能体组成,并且包含静态和非静态非智能障碍物时,对于其中的任意一个智能体Ai而言,其要面对的RVO区域RVOi就变成了它对于其他所有智能体的独立RVO区域,以及对于非智能障碍物的VO区域的组合区域。可见,RVOi为组合RVO区域,即CRVO。CRVO的定义如下:

    RVOi = Uj≠iRVOij(vj, vi, αij) ∪ Uo∈OVOio(Vo)

    理论上,每个智能体在选择速度时,只要从其CRVO区域之外选择,就可以无碰撞地导航直到目标位置。

    4.2 AV区域(可达速度集合)

    在实际情况中,对于拥有速度Vi的任意智能体Ai,可能会存在某些运动学和动力学约束,从而对其能够实际达到的速度产生约束。我们将其能够实际达到的速度的集合用AVi(vi)表示。对于不同的智能体,由于其特性不同,可达速度集合也会有不同的情况。比如,假设智能体Ai存在最大速度 Vmaxi 和最大加速度 amaxi ,那么它的可达速度集合为:

    AVi(Vi) = {VI’ | ||Vi’|| < Vmaxi ∩ ||Vi’ - Vi|| < amaxiΔt }

    4.3 速度选择

    在每个模拟循环的开始,我们需要先为每个智能体 Ai 确定它此时的最优速度,这个速度应该是直接指向其目标点的,用Vprefi 表示。接下来,需要为每个智能体选择新的速度作为当前速度。理想情况下,这个新速度应该在智能体Ai 的CRVO区域之外、在其可达速度集合之内,且与此时的最优速度最相近。然而,实际环境中可能存在着过多的智能体和障碍物,使得CRVO完全填满了AV区域。为了解决这个问题,在选择速度时,允许选择CRVO内的速度,即只要速度位于可达速度集合内就可以被选择。同时,对于每个速度都定义了一个惩罚值 penaltyi(Vi’)。这个值的大小与两方面因素有关:1是当前选择速度与此时最优速度的距离,2是当前选择速度导致碰撞的预期发生时间。由此,惩罚值的定义如下:

    penaltyi(Vi’) = wi / tci(Vi’) + || Vprefi - Vi’ ||

    其中wi是用于表示智能体在某些方面的特性,比如攻击性、活跃性之类的,会根据智能体的不同具体情况而定。
    tci(Vi’)表示碰撞的预期发生时间,计算也很简单:

    • 对于非智能体的VOAB(VB), 可以通过求解等式 λ(PA, VA - VB) = B ⊕ −A来得到
    • 对于智能体的RVOAB(VB, VA),可以通过求解λ(PA, 2VA - VA - VB) = B ⊕ −A得到
    • 对于CRVO,碰撞的预期发生时间所有智能体和非智能体求得的 tci(Vi’) 中的最小值
    • 对于CRVO之外的速度,也就是不会发生碰撞的情况,tci(Vi’) 为无限大

    我们通过对于可达速度区域AVi(Vi)内的速度进行均匀的随机采样,并计算样本速度的惩罚值,以惩罚值最低的一个作为本次选择的最新速度。

    4.4 邻近区域

    上文我们曾经提到过,在CRVO的情况下,计算惩罚值中的碰撞预期发生时间时,是取的所有智能体和非智能体中预期碰撞时间的最小值,对于那些与Ai距离过于遥远的对象来说,与它们发生碰撞的预期时间显然更长,计算出来的值根本不会被选中,因此,在实际的计算过程当中,完全可以节省下这部分计算量。

    我们以Ai的当前位置为中心定义了一个区域,称为邻近区域,用 NRi 表示,只有在邻近区域之内的智能体和非智能体才会速度选择时被计算在内。通过这种方式,便可减少很多计算量,对算法进行优化。至于邻近区域的最优大小,则可能跟环境内物体的平均速度、模拟的时间间隔等诸多因素有关。

    此外,邻近区域除了减少计算量,提高运行效率之外,也可以用于对某些自然特性的实现,比如视野范围等。

    5. 实验数据

    展开全文
  • VO避障

    千次阅读 多人点赞 2021-02-22 10:41:29
    动态环境下的运动规划始终是一个难题,这是因为它需要在状态空间下进行规划,也即需要同时解决路径规划和速度规划两个问题。其中,路径规划是一个运动学问题,旨在计算出一条从出发点到目标点的无碰撞路径。而速度...

    原文地址:https://www.researchgate.net/publication/2672667_Motion_Planning_in_Dynamic_Environments_Using_the_Relative_Velocity_Paradigm

    1. 简介

    动态环境下的运动规划始终是一个难题,这是因为它需要在状态空间下进行规划,也即需要同时解决路径规划和速度规划两个问题。其中,路径规划是一个运动学问题,旨在计算出一条从出发点到目标点的无碰撞路径。而速度规划由于需要考虑机器人的动态和执行器约束,天然地是一个动态规划问题。事实表明,在有限速度和多障碍条件下对平面内一点的动态运动规划是很困难的,这其中不仅包括计算的难度,还包括由于不确定的环境特性导致的解的不确定性,比如,在时间 t0 的可行解在之后的某个时间可能会变得不可行。

    对于如何解决动态环境下的运动规划问题,最初的思路是在假定速度边界和已知障碍物运动路径的情况下,在构型空间中增加时间维度,从而形成连续时间下的构型空间。Reif和Sharir在1985年提出了不断搜索可视图的方案,以解决由单个多边形机器人和多个多边形障碍组成的平面动态运动规划问题。1987年,Erdmann和Lozano-Perez提出将连续的构型空间离散化成由一系列的微小时间段的构型空间组成的序列的方式来求解,其本质是分别解决连续片段下的静态运动规划问题,然后将所有片段的解决方案组合起来得到最终的方案。1989年Fujimura和Samet也提出了网格法解决动态运动规划问题的思路。

    另外一个解决动态运动规划问题的方向是将其分解成小的子问题:即路径规划问题和速度规划问题。按照这个方法的思路,首先解决路径规划的问题,寻找出一条从出发点到目标点的可行路线。然后按照可行路线依次寻找能够避开移动障碍物的速度。Kant和Zucker首先于1986年通过可视图的方式成功得到可行的路径和速度分布。一年以后,Lee和Lee(没错,原文就是两个李)也独立地提出以类似的方式为两个协同机器人解决运动规划的问题,并且,他们还比较了在避障时采取延迟和减速两种方案对运动时间的不同影响。1993年,Fraichard将加速度边界考虑进去,通过在连续状态空间(state-time space)下搜索来求出最段路径下的速度分布。Fraichard和Laugier还在同年考虑了选定路径在被移动障碍物阻挡时切换到邻近路径的情况。1995年,Fujimura(上文提到的网格法大佬)也提出了定时网格(fixed time-dependent network)下解决网格被移动障碍物阻塞的方案。

    另一种不同的思路是基于对可视图的延申,尝试创建当前环境的无障碍图。Fujimura和Samet将其定义为当机器人以最大速度运动时会与障碍物发生碰撞的具体点的轨迹。这些点就形成了一条碰撞边界,并且可以从出发点连接至目标点。无障碍图的一个特性是,如果机器人以比障碍物更快的速度运行,那么通过图中搜索得到的路径就是耗时最少的路径。(这段没看懂,最好看原文)

    线上动态运动规划问题更多地关心决策的做出,而不是机器人的动态。Sanborn和Hendler曾在1988年提出交通领域的机器人应对环境的规则。机器人通过预测相关非智能体与自身移动路径的发生交叉的时间段来对外部环境做出反应。这种方式考虑了环境的物理特性,而忽略了机器人自身的物理局限性。之后又在以时间为轴的计算碰撞的笛卡尔坐标系中增加了机器人速度的条件。与之相关的另一个问题,即对未来发生碰撞的预测和排序,也开始成为研究课题。

    以上所有前期研究的一个共同点,就是他们都是基于位置信息对机器人和障碍之间的碰撞进行预测。由于当前算法都是通过位置信息对潜在碰撞进行预测,所以它们被统称为零阶算法。

    在本文中,我们提出一种通过速度信息直接预测随时间变化的环境中的潜在碰撞的算法,即一阶算法。这种方法利用了速度障碍的概念(Velocity Obstacle, VO),将动态环境映射到机器人的速度空间中。VO是在给定时间范围内,机器人与障碍物会在将来某个时刻发生碰撞的速度的一阶近似值。通过这种表示,可以简单地通过选择VO区域之外的速度作为避障策略。

    通过在离散时间间隔下计算生成的避障策略树,然后对该树进行搜索得到一系列的避障策略,最终组成一条路径。对于线上应用,可以根据不同的设计意图的优先级,比如避免碰撞、达到目标、最大速度等,对树进行启发式搜索以进行优化。

    2. VO避障说明

    本节我们将介绍对于单个障碍物和多个障碍物的VO。为了简单起见,我们会将分析的物体抽象成平面上的圆圈。由于多面体也可以用多个圆圈表示,所以这是一种相对合理的抽象。同时 ,我们也假设障碍物都以特定的轨迹运动,即,在某个特定的时间节点上,我们对障碍物的瞬间状态(位置和速度)是已知或者可预测的。

    图1:
    图1
    现在我们考虑一个由A和B两个圆圈组成的系统(如上图)。A和B的速度分别是VA和VB,半径分别是RA和RB,此时时间为t0。其中A代表寻路的机器人,B代表障碍物。为方便计算VO,我们首相将B映射到A的构型空间。我们可以将A抽象成一个点,同时将B的半径增加RA,从而得到新的A’和B’。他们的状态表示各自的位置和圆心的速度。

    为了方便理解,我们首先考虑相对速度。用VAB表示A’相对于B’的相对速度,即VAB = VA’ - VB’, 入AB 表示 VAB对应的向量。那么,我们把所有会导致A’B’发生碰撞的VAB 的集合定义为CCAB,其形状如下图所示。

    图2:
    图2
    可见,这是一个以A’为顶点的扇形,A’到B’的两条切线 入r 和 入f 分别形成了这个扇形的两个边界。那么显而易见,在B’保持当前形状和速度都不变的情况下,任何落在扇形区域CCAB内的相对速度都会导致A’和B’发生碰撞,相反,任何落在扇形区域以外的相对速度都不会使二者发生碰撞。

    由于我们采用的是相对速度,所以这个扇形只适用于A’和B’这一对物体的特定情况。为了将其推广,使之适用于多个碰撞体,就需要将CCAB 转化为与之等价的由A’的绝对速度形成的区域。很简单,只要将CCAB中的每个相对速度加上B’的速度VB即可。又或者,只要将整个扇形区域沿B’的速度向量移动一下即可。最终得到的结果如下图所示。

    图3:
    图3
    最终,我们将VO定义为:
    VO = CCAB ⊕ VB
    其中⊕代表明可夫斯基向量加。
    VO将A’的绝对速度分成了会碰撞和不会碰撞两个区域,只要选择VO以外的速度,就不会发生碰撞,也即满足下式:
    A(t) ∩ B(t) = Φ ,if VA(t) ∉ VO(t)
    位于VO边界上的速度,将导致A’和B’刚刚好擦到。而对于固定的障碍物,VO也依然适用,此时可以将B’的速度VB看做是0。

    对于多障碍物的避障,我们可以将其视为多个独立VO的联合:
    公式1
    其中m表示障碍物的总个数。那么,对于这种情况,不会引发碰撞的速度则是那些在所有VO区域外部的速度,如下图所示。

    图4:
    图4
    对于多个障碍物的情况,对障碍物按照碰撞发生的时间顺序进行优先级排序是一个很有效的优化思路。而且,由于VO是基于对物体的速度做线性模拟得出的,这对于远处的障碍物可能并不适用,因为障碍物实际并不是完全做线性运动,因此碰撞发生时间越远的情况越可能出现误差。如果碰撞发生在给定的时间Th之内,即 t < Th,那么我们便称之为紧迫的(imminent)。这其中时间Th根据不同的实际情况可能采取不同的值。我们用VOh定义那些发生碰撞的时间超过Th的速度的集合,用dm表示机器人和障碍物之间的相对距离,则VOh可定义为下式:

    VOh = { VA | VA ∈ VO, || VAB || <= dm / Th }

    从整个VO区域中将VOh的部分去除掉,就可得到我们认为紧迫的碰撞的速度区域(下图)。

    图5:
    图5

    3. 避让机动

    在本节中,我们将介绍能够避免在给定的一段时间内发生碰撞的避让机动,它包括一系列一步的速度变化。

    3.1 可达速度

    对于指定状态下的机器人A,其在给定时间Δt后的可达速度通过将执行器约束映射到加速度约束中可计算。
    首先我们定义FA(t) 为机器人A在时间时的可达加速度集合,其具体表示如下:
    式2
    其中X为位置向量,u为加速度影响,U代表所有可接受的控制条件。
    根据上式,可以将可达速度( RV(t + Δt) )表示为:
    式3
    这个式子很好理解,就是将速度变化按照时间进行缩放,然后与当前速度相加,得到受影响后的速度。其表示如下图所示:

    图6:
    图6
    而可达避障速度(RAV)定义如下:
    式4
    也就是从可达速度中将属于VO区域的那部分速度扣除出去,其结果如下图所示:

    图7:
    图7
    上图对于RAV的表示只是一种简单的示意图,从图中可见,此时RAV区域为可达速度RV被VO从中间分开后的两段区域,很显然,对于有多个障碍物的情况,RV可能会被多个VO区域进行阻隔出现多个分散不相连的区域的结果。

    3.2 避让机动的结构

    避让机动可以根据它们相对于移动障碍物的位置进行区域划分。通常,避让速度会被VO区域划分为两块不相连的独立区域,如上图所示。碰撞速度和非碰撞速度区域的边界分别为A’到B’的两条切线 入f和 入r。只要选择的速度位于这两块独立的区域 ——也就是RAV ——之中,就可以避免和障碍物发生碰撞,但是要从哪块区域中选择避让速度呢,这首先就要先决定要从障碍物的哪一边进行避让。
    首先我们如下图构建坐标系。

    图8:
    图8
    以B’的中心点为原点,B’的运动方向为X轴正方向,与X轴垂直且远离A’的方向为Y轴正方向。Y轴与B’的两个交点Yf和Yr将B’分为前后两个半圆,分别用∂Bf和∂Br表示。

    当A’相对与B’的相对速度位于入f或入r的时候,A‘会与B’擦肩而过,姑且称之为切线机动吧( tangent maneuvers)。但实际上,切线机动的切点却并不会像上图中所画的那样一定落在Tf和Tr上,这是因为这与二者的绝对速度有关。下图简单表示了在采取切线机动时,从时间t0到t1,A’和B’二者运行到相切位置的具体情况。

    图9:
    图9
    可见,实际的切点并不是发生在Tf点,而是在P点。那么切点的实际位置在哪里呢,下面的定理对切点的实际位置进行了描述。

    定理1:
    当且仅当机器人A’以相对于B’的相对速度为V∈{入f, 入r}时,二者会发生切线机动。其中入f为A’到B’前半圆的切线(切点Tf),入r为A’到B’后半圆的切线(切点Tr)。并且,切点只会落在Tf和Yf将B’圆周切割出的最短弧,以及Tr和Yr将B’圆周切割出的最短弧上。

    该定理的具体证明在原文附录A中有,感兴趣的老板可以自己看原文。
    上文中我们提到过,VO区域的两条边界线是基于相对速度下的切线入f和入r转换而来,因此可知这两条边界线也就是发生切线机动的速度。由于切线机动完全由入f和入r决定,我们根据VO的边界以及A’到VO区域顶点的连线,将可达区域划分为如下图所示的Sr Sf 和 Sd三部分(如下图),并得到定理2。

    图10:
    图10
    定理2:
    对于单个障碍物的可达速度区域(RAV)最多可被分割为三块互不覆盖的子区域 Sr Sf 和 Sd,它们分别代表后向区域,前向区域和远离区域。

    定理2的证明也在原文附录A中(万能的附录A),感兴趣的老板依然可以自己去看原文。
    前向区域表示机器人会在障碍物前方穿过障碍物的路径,从而避免碰撞,同理,后向区域表示机器人会在障碍物后方穿过其路径,而远离区域表示机器人会渐渐远离机器人而不会发生碰撞。

    另外,视具体情况不同,三块区域并不一定全都存在,可能存在一种,也能存在两种(图7),也可能一种都不存在(可达速度区域完全被VO覆盖,也就是无法避障)。

    对于有多个障碍物的情况,我们可以用其VO区域依次对RAV进行切割,并用Sss表示具体的切割后区域,比如Sfr即表示第一个障碍物的前向区域和第二个障碍物的后向区域的共同区域(如下图)。

    图11:
    图11
    定理2在多障碍物的情况下依然适用,其证明也依然在附录A中。

    4.计算避障路径

    这一部分概括来讲就是,由于这个模型是基于障碍物状态可预测的前提下进行的,因此可以在事前先按照一个时间间隔,在离散的时间点上计算出机器人的当前位置以及障碍物的当前位置,然后以机器人位置为节点,按照不同的避让机动做分支,从而形成一颗树,最终达到目标点。当然,这里的避让机动可以只做几种。而且,这里也可以在进行避让机动的时候增加一些条件,进行启发式的选择,从而达到更好的效果。

    由于在实际游戏开发中,我们很少会拿VO做路径规划,一般只是做寻路过程中的动态避障,所以这部分就不展开了。有感兴趣的老板,依然可以去看原文。

    5. 例子

    略。

    展开全文
  • 它的基本思想是将机器人在周围环境中的运动,设计成一种抽象的人造引力场中的运动,目标点对移动机器人产生“引力”,障碍物对移动机器人产生“斥力”,最后通过求合力来控制移动机器人的运动。应用势场规划出来的...
  • 这里写目录标题原始对偶函数原始−-−对偶对数障碍函数算法应用原始−-−对偶对数障碍函数程序压缩感知中的应用实验结果 原始对偶函数 \quad单纯形(SimplexMethod)(Simplex Method)(SimplexMethod)...

    内点法

    \quad 单纯形法 ( S i m p l e x M e t h o d ) (Simplex Method) SimplexMethod可以用来求解带约束的线性规划命题 ( L P ) (LP) LP,与之类似的有效集法 ( A c t i v e S e t M e t h o d ) (Active Set Method) ActiveSetMethod可以用来求解带约束的二次规划 ( Q P ) (QP) QP,而内点法 ( I n t e r i o r P o i n t M e t h o d ) (Interior Point Method) InteriorPointMethod则是另一种用于求解带约束的优化命题的方法。而且无论是面对 L P LP LP还是 Q P QP QP,内点法都显示出了相当的极好的性能,例如多项式的算法复杂度。内点法主要有障碍函数法 ( B a r r i e r M e t h o d ) (Barrier Method) BarrierMethod和原始对偶法 ( P r i m a l − D u a l M e t h o d ) (Primal-Dual Method) PrimalDualMethod
    本文中采用由 D o n o h o Donoho Donoho等人发表在论文 A t o m i c Atomic Atomic D e c o m p o s i t i o n Decomposition Decomposition b y by by B a s i s Basis Basis P u r s u i t Pursuit Pursuit中提出的原始 − - 对偶对数障碍函数法。该论文利用原始 − - 对偶对数障碍函数法和共轭梯度法成功求解了大规模的优化问题。

    原始 − - 对偶对数障碍函数法

    \quad 本文中主要利用原始 − - 对偶对数障碍函数法来求解下面的一个带扰动的线性规划问题,也可以理解为二次规划问题。
    min ⁡ x c T x + 1 2 ∥ γ x ∥ 2 + 1 2 ∥ p ∥ 2 s . t . A x + σ p = b x ≥ 0 {\rm{ }}\mathop {\min }\limits_x {c^T}x + \frac{1}{2}{\left\| {\gamma x} \right\|^2}{\rm{ + }}\frac{1}{2}{\left\| p \right\|^2} \quad {\rm{ s}}{\rm{.t}}{\rm{. }}Ax + \sigma p = b{\rm{ }}x \ge 0 xmincTx+21γx2+21p2s.t.Ax+σp=bx0
    p p p是一个高斯白噪声, σ \sigma σ是扰动的水平, γ \gamma γ x x x的扰动。论文中 γ \gamma γ代表扰动,也可以理解为范数。下面是原始 − - 对偶对数障碍函数法算法:
    在这里插入图片描述
    在这里插入图片描述
    如果对该算法感兴趣,可以浏览最后两篇参考文献,特别是第三篇参考文献给出了更一般的二次规划算法。

    信号分解中的应用

    上述参数设置不同的值,会有下面两个不同的模型。
    ( M O F ) min ⁡ ∥ x ∥ 2 s . t . y = A x x ≥ 0 (MOF) \quad{\rm{ }}\min {\rm{ }}{\left\| x \right\|_2} \quad {\rm{ s}}{\rm{.t}}{\rm{. }} \quad y = Ax \quad {\rm{ }}x\ge 0 (MOF)minx2s.t.y=Axx0

    ( B P D N ) m i n ∥ x ∥ 1 s . t . A x = y x ≥ 0 (BPDN) \quad{\rm{ min}}{\left\| x \right\|_1} \quad {\rm{ s}}{\rm{.t}}{\rm{. }} \quad Ax = y \quad {\rm{ }}x\ge 0 (BPDN)minx1s.t.Ax=yx0
    上述两个模型都是为了实现信号的自动分解, M O F MOF MOF存在两个问题:
    ( 1 ) (1) (1)分解出来的系数不稀疏。在某些情况下,如果信号本身就具有稀疏性,这样分解出来的结果就会非常糟糕。
    ( 2 ) (2) (2) M O F MOF MOF本身存在分辨率受限的问题。
    B P D N BPDN BPDN就是把 B P BP BP基追踪应用于去噪,所以命名。相比于 M O F MOF MOF B P D N BPDN BPDN 2 2 2范数变为 1 1 1范数,这就可以保持稀疏性。
    但是前者的运算速度会远远快于后者。尽管利用下面的程序,可能会得出完全相反的结论。这主要是利用原始 − - 对偶对数障碍函数法算法去实现 M O F MOF MOF并不是明智的选择。

    压缩感知中的应用

    \quad 在这里,我么将 B P D N BPDN BPDN模型,也就是 B P BP BP应用于压缩感知 C S CS CS恢复重建过程。我们使用高斯随机矩阵作为测量矩阵 A A A,稀疏度 K = 10 K=10 K=10,原始信号是一个只有 K K K个为 1 1 1,其余为 0 0 0的信号。那么只要 σ = 0 \sigma=0 σ=0 γ = 0 \gamma=0 γ=0 c c c是一个全 1 1 1的列向量即可。

    算法程序

    function [x,z] = PDLB_LP(c,A,b,delta,gama)
    %UNTITLED5 此处显示有关此函数的摘要
    %   此处显示详细说明
    %A Primal-Dual Log-Barrier LP Algorithm
    %set parameters
    FeaTol=1e-4;%the feasibility tolerance 
    PDGapTol=1e-4;%the duality gap tolerance
    % delta=0.01;%delta=1,即为BPDN,delta也可以为1e-4
    % gama=0.01;%gama,原始变量的扰动
    %Initialize
    [m,n]=size(A);
    x=ones(n,1);%生成全1向量
    y=zeros(m,1);%生成全0向量
    z=0.5*ones(n,1);
    e=ones(n,1);
    miu=1;
    %Loop
    t=c+(gama^2)*x-z-A'*y;
    r=b-A*x-(delta^2)*y;
    X=diag(x,0);%生成对角线元素为x的对角矩阵
    Z=diag(z,0);
    v=miu*e-Z*x;
    %step a
    D=inv(X\Z+(gama^2)*eye(n));%A\b=inv(A)*b
    PInfeas=norm(r,2)/(1+norm(x,2));%Primal infeasibility
    DInfeas=norm(t,2)/(1+norm(y,2));%Dual infeasibility
    DuGap=(z'*x)/(1+norm(x,2)*norm(z,2));
    while(PInfeas>FeaTol || DInfeas>FeaTol || DuGap>PDGapTol)
        %step b:solve
        if (delta>0)
            A1=[(D^(1/2))*A';delta*eye(m)];%(n+m,m)
            B=[(D^(1/2))*(t-X\v);r/delta];
            y1=pinv(A1)*B;%广义逆,最小二次法求delta_y,即y1
        else
            y1=(A*D*A')\(r+A*D*(t-X\v));
        end
        x1=D*(A'*y1+X\v-t);
        z1=X\(v-Z*x1);
        %step c:Calculate the primal and dual step sizes ρp,ρd and update the variables:
        index1=find(x1<0);
        index2=find(z1<0);
        if isempty(index1)==0 && isempty(index2)==0%不是空
            x2=x1(index1);%储存负数
            z2=z1(index2);
            x3=x(index1);%储存x1中负数对应的x值
            z3=z(index2);
            p1=abs(x3./x2);
            p2=abs(z3./z2);
        elseif isempty(index1)==0 && isempty(index2)==1
            x2=x1(index1);%储存负数
            x3=x(index1);%储存x1中负数对应的x值
            p1=abs(x3./x2);
            p2=p1;
        elseif isempty(index1)==1 && isempty(index2)==0
            z2=x1(index2);%储存负数
            z3=z(index2);%储存x1中负数对应的x值
            p2=abs(z3./z2);
            p1=p2;
        else
            p1=min(x./x1);
            p2=min(z./z1);
        end
        rou_p=0.99*min(p1);
        rou_d=0.99*min(p2);
        x=x+rou_p*x1;
        y=y+rou_d*y1;
        z=z+rou_d*z1;
        miu=(1-min([rou_p,rou_d,0.99]))*miu;
        %step a
        t=c+(gama^2)*x-z-A'*y;
        r=b-A*x-(delta^2)*y;
        X=diag(x,0);%生成对角线元素为x的对角矩阵
        Z=diag(z,0);
        v=miu*e-Z*x;
        D=inv(X\Z+(gama^2)*eye(n));%A\b=inv(A)*b
        PInfeas=norm(r,2)/(1+norm(x,2));%Primal infeasibility
        DInfeas=norm(t,2)/(1+norm(y,2));%Dual infeasibility
        DuGap=(z'*x)/(1+norm(x,2)*norm(z,2));
    end
    end
    

    实验结果

    在这里插入图片描述

    https://blog.csdn.net/dymodi/article/details/46441783
    Chen S S , Saunders D M A . Atomic Decomposition by Basis Pursuit[J]. Siam Review, 2001, 43(1):129-159.
    P. E. Gill, W. Murray, D. B. Ponceleón, and M. A. Saunders, Solving Reduced KKT Systems in Barrier Methods for Linear and Quadratic Programming, Report SOL 91-7, Stanford University, Stanford, CA, July 1991.

    展开全文
  • rvo动态避障算法源码分析

    千次阅读 2021-08-16 14:33:18
    就是处理动态障碍开始 1 计算相对速度,相对位置 代码: combineRadius就是把A看到质点后,B物体半径相对扩大 2 计算速度调整 代码截图 分析: 2.1 代码中变量对应的几何意义 2.2 dotProduct1 判断是否往cutoff-circle...
  • 为提升AGV工作效率并改善其躲避障碍物的执行能力,提出在静态与动态环境下的全局路径规划方法——多目标与速度控制.在静态环境下,以路径最短与平滑度最大建立路径规划的多目标数学模型,采用所提出的改进算法求解并...
  • 所述ROS移动机器人的激光雷达扫描室内环境信息,上位机通过wifi模块更新激光雷达实时返回的数据,上位机调用ROS系统的构建地图功能包,当激光雷达返回的数据中出现障碍物时,上位机中的rviz可视化工具将栅格地图...
  • 该方法采用栅格进行环境建模,利用量子粒子群优化算法参数少、收敛速度快、鲁棒性好、能够较好地收敛于全局最优点等优点,搜索一条无障碍路径。仿真实验结果验证了该方法的有效性,是在障碍环境中寻找一条空间最优...
  • 在战场环境中,战术分队的队形在面对复杂静态或动态障碍物时难以较好地保持...为解决面对动态障碍的避碰问题,基于相对速度障碍法,并加入速度协同控制,避免队形在避碰过程中失效。最后通过实验表明了该方法的有效性。
  • 除此之外,在经历了近四十年科学不太依赖自主创新的成长期且创新成为战略目标之后, 这些影响是否会浮出水面,成为中国发展的重大障碍。 对这些问题的分析往往分为两类。经济学的视角,但是由于数据本身的局限性,...
  • 一文详解激光雷达的障碍物检测

    千次阅读 多人点赞 2021-03-01 10:35:27
    点击上方“3D视觉工坊”,选择“星标”干货第一时间送达激光雷达感知自动驾驶中采用激光雷达做感知可以分为两个层次,低层次感知也叫作障碍物检测,只需要探测到前方有障碍物即可;高层次感知可以看做...
  • 随后,在传统人工势场的势场函数中加入速度因子,使用户可以躲避动态障碍物并到达动态目标,同时进行最大转弯角度设定,微调生成路径,以便获得相对平滑的路径。最后进行仿真实验,仿真实验首先证明本文所提算法在...
  • DWA算法全称为dynamic window approach,其原理主要是在速度空间(v,w)中采样多组速度,并模拟这些速度在一定时间内的运动轨迹,再通过一个评价函数对这些轨迹打分,最优的速度被选择出来发送给下位机。 通过一段...
  • 研究并对比了加速度计的静态标定和在线标定方法,实现了偏差的动态识别和补偿,并且根据Allan方差有效识别了加速度计的随机误差,为数据融合算法奠定了基础。进而根据捷联惯导工作机制和实际机器人运动,分析简化...
  • 针对传统人工势场在智能车辆局部路径规划中未充分考虑车辆动力学和运动学约束的不足,提出一种基于动态虚拟障碍物的局部路径规划方法.首先根据环境、车辆运行状态和道路交通规则分析车辆行驶安全性并获得虚拟车道线...
  • 区域生长分割matlab代码执行摘要 该项目旨在自动化 CNT TEM 图像的直径测量。 目前,它可以区分包含适合测量的 CNT 的感兴趣区域和不包含的感兴趣区域。 这是实现整个过程自动化的第一个障碍。 问题陈述 研究人员...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,843
精华内容 7,137
关键字:

速度障碍法