VelocityObstacle(速度障碍)

  1. 定义:速度障碍(VO: velocity obstacle)指的是机器人速度的一阶近似值,在给定时间范围内以这些速度运动,未来某个时间会导致与障碍物发生碰撞。
  2. 概述:速度障碍在机器人运动规划里面是个非常基本的概念, 他定义了一个速度集合。如果机器人的速度在这个集合内,就代表机器人会和周围的其他物体(机器人或者障碍物)发生碰撞。在详细介绍这个概念之前,我们首先介绍下什么叫做速度锥(collision cone)。
  3. 碰撞锥(collision cone): 两个机器人A和B在2D空间里面运动,

我们假设他们的形状是圆形,圆的半径分别为rA,rBr_{A}, r_{B}, 速度向量分别为vA,vB\mathbf{v}_{A},\mathbf{v}_{B}。为了计算VO,我们首先将B映射到A的配置空间中, 即通过将A简化为一个质点A^\hat{A}, 用B的半径加上A的半径来扩大B,从而形成B^\hat{B}来实现。这里,我们将碰撞锥定义为一个A^B^\hat{A}\text{和}\hat{B}之间发生碰撞时的相对速度集合, 即CCAB={vA,B|λA,BB^}CC_{AB} = \{\mathbf{v}_{A,B}|\lambda_{A,B} \cap \hat{B} \neq \emptyset \}。其中vA,B\mathbf{v}_{A,B}表示A^\hat{A}相对于B^\hat{B}的相对速度vA,B=vAvB\mathbf{v}_{A,B} = \mathbf{v}_{A} – \mathbf{v}_{B},λA,B\lambda_{A,B}vA,B\mathbf{v}_{A,B}那条线。如下图Fig.2 所示:这个锥是一个以A^\hat{A}为起点,方向从A^\hat{A}B^\hat{B},被λf\lambda_{f}λr\lambda_{r}包围的一个平面扇形区,其中λf,λr\lambda_{f} , \lambda_{r}是经过点A^\hat{A}, 并和B^\hat{B}相切的2条切线,相对速度位于这个锥内将会导致A和B发生碰撞。 换句话说,只要障碍B^\hat{B}保持当前的形状和速度运动,任何在CCABCC_{AB}之外的相对速度确保是无碰撞的。

4.速度障碍(velocity obstacle):根据上面定义可知碰撞锥是针对一对 机器人- 障碍,为了考虑多个机器人,基于A的绝对速度去构建一个等价的条件是很有用的。为此,我们只需要将B的速度vB\mathbf{v}_{B}CCABCC_{AB}集合里面的每个速度相加(或者说将CCABCC_{AB}沿着vB\mathbf{v}_{B}的方向进行平移),即VO=CCABvAVO = CC_{AB} \oplus \mathbf{v}_{A}, 其中\oplus是闵可夫斯基求和符号。如图Fig.3所示

因此我们可知VO将A的绝对速度划分成了两个部分,无碰撞速度和碰撞速度。A选择VOVO之外的速度将使得A和B不发生碰撞, 速度在VO的边界部分会导致A和B刚好擦边。因此为了避开多个障碍物,我们考虑多个VO的并集,即VO=i=1mVOBiVO = \bigcup_{i=1}^{m} VO_{B_{i}}, m是障碍物的个数。 如果Fig.4所示,当A选择2个灰色锥之外的速度时候,不会和B1,B2B_{1}, B_{2}发生碰撞。

当遇到有许多障碍物的场合,我们优先考虑那些最快可能产生碰撞的障碍会更好。因为VO是对障碍物轨迹的一个线性逼近,如果障碍物不是沿着直线运动, 用他去预测距离比较远的障碍物会不准确。 另外,如果碰撞发生在某个时间t<Tht < T_{h},我们称机器人与障碍物之间即将发生碰撞。其中ThT_{h}是一个合适的时间范围,跟系统的动力学,障碍物的轨迹,和算法的计算率(computation rate)有关。因此为了考虑迫切避障,我们定义VOh={vA|vAVO,||vA,B||dmTh}VO_{h} = \{ \mathbf{v}_{A} | \mathbf{v}_{A} \in VO, || \mathbf{v}_{A, B}|| \leq \frac{d_{m}}{T_{h}} \}, 其中dmd_{m}是机器人和障碍物之间的最小距离。因此VOhVO_{h}定义了在时间ThT_{h}之外会发生碰撞。因此我们重新定义VO,即从VO中减去VOhVO_{h}部分,新的VO如Fig.5所示。

5. 可达避障速度(reachable avoidance velocity): 机器人A在给定状态下某一段时间Δt\Delta t内的可达避障速度是通过将执行器的约束(actutor constraints)映射到加速度约束(acceleration constraints)上的。在定义它之前, 我们先定义可行加速度:FA(t)={x¨|x¨=f(x,x˙,u),uU)}FA(t) = \{ \ddot{x} | \ddot{x} = f(x, \dot{x}, \mathbf{u}), u \in U) \}, 其中xx是位置向量,f(x,x˙,u)f(x, \dot{x}, \mathbf{u})代表机器人动力学,u\mathbf{u}是执行器的控制输入,UU表示可控制量的集合。

那么在Δt\Delta t时间内的可达速度集合定义为:RV(t+Δt)={v=vA(t)Δt.FA(t)}RV(t + \Delta t) = \{ \mathbf{v} = \mathbf{v}_{A}(t) \oplus \Delta t . FA(t)\}, 他是通过将A的当前速度加上Δt.FA(t)\Delta t . FA(t)的集合(注意这个公式只考虑了动力学约束,对于非完整性约束机器人,还应该考虑运动学约束)。因此可达避障速度集合可以定义为:RAV(t+Δt)=RV(t+Δt)VO(t)RAV(t + \Delta t) = RV (t + \Delta t) \ominus VO(t),\ominus是集合求差符号。由图Fig.7, 我们可以看出RAV(t+Δt)RAV(t + \Delta t)是由两个互不相交的子集合(H,K点所在的四边形区和M,L所在的四边形区)构成。对于有多个障碍物的情况,RAVRAV会有多个互不相交的子集合构成。

是由两个互不相交的子集合构成

6.计算避障轨迹:这里我们介绍一种计算避障轨迹的方法,使得机器人可以避开静态和动态障碍物,达到目标点,并且满足机器人动力学约束。一条轨迹包含一系列的避障行为,它是在离散的时间间隔内通过在一棵可行行为树搜索到的。这里我们只介绍用于线上应用的启发式搜索。 对于线上应用,轨迹可以根据机器人的当前位置来进行节点扩张,每个节点只产生一个分支节点,这个分支节点是使用一些启发式策略,从可能的分支中选择出来的。这些启发式规则可以是为了使机器人达到一系列的目标点而设计的,启发式规则搜索是为了去找一个最好的局部最优解的。我们设计了如下的一些启发式规则:

(a) 选择一个朝向目标点的最大速度,从而使得机器人达到目标点

(b) 选择一个和目标点连线有夹脚的,最大的避障速度

(c) 根据可以避开障碍物风险的速度

参考文献:

[1] P. Fiorini and Z. Shiller, Motion planning in dynamic environments using velocity obstacles, Int. J. Robot. Res., vol. 17, no. 7, pp. 760–772, Jul. 1998.

发表评论

您的电子邮箱地址不会被公开。