1. 논문 목적

본 논문은 실시간 충돌 회피 알고리즘이 필요한 동적 장애물 , 특히 로봇의 최대 속도보다 빠른 속도를 가진 장애물을 회피하는 문제에 대해 다룬다.

본 논문은 두 가지 영역을 설정하고, 로봇의 속도를 해당 영역 밖으로 설정하여 고속 동적 장애물을 회피한다.

• 제한된 time step 내에서 장애물과의 잠재적 충돌 발생 영역
• 해당 time step을 넘어 충돌이 발생할 수 있는 영역

2. Related Works

1) 로봇과 장애물의 상대적 거리 기반 방법

A. artificial potential field

• 로봇이 접근할수록 로봇을 장애물로부터 멀어지도록 하는 반발력을 생성하여 충돌을 방지한다.
• 장애물의 속도가 로봇의 속도보다 빠른 경우 로봇이 장애물에 의해 "쫓기게 되어" 결국 충돌하게 되는 문제가 있다.

B. MPC(모델 예측 제어)

• 공정 모델을 이용해 미래 출력치를 예측하고 이를 최적화하여 얻어진 제어 입력을 사용하는 제어 기법
• penalty function으로 거리 기반 potential 함수를 사용하므로 같은 문제를 겪는다.

2) 매 단계에서 로봇의 이동 속도를 계획

A. VO(velocity obstacle)

• 로봇이 현재의 속도를 유지한다고 가정할 때, 어떤 순간에 다른 로봇과 충돌하게 되는 장애물의 모든 속도의 집합
• 로봇이 velocity Obstacle안에 있는 속도를 선택하면 결국 충돌하게 되며, velocity obstacle 외부에 있는 속도를 선택하면 충돌이 발생하지 않도록 보장된다.

B. RVO(Reciprocal Velocity Obstacle)

• RVO(Recirprocal Velocity Obstacle)는 VO에서 발생하는 진동(Oscillation) 현상을 해결하기 위해 고안된 방법이다.

C. ORCA(Optimal Reciprocal Collision Avoidance)

3. 문제 정의

• Fig 1-(a): 원형으로 표현되는 로봇 A (반경 rA, 중심 pO(원점)) 와 움직이는 장애물 O (반경 rO, 중심 pO, 속도 vO)

• Fig 1-(b): 장애물의 속도가 미래의 시간 범위 𝜏 > 0 에서 constant하다고 가정하면, 𝜏 내에서 충돌을 일으키는 장애물 O와 로봇 A의 상대 속도 set을 velocity obstacle이라고 함 (회색 영역)

  • $V O_{A \mid O}^\tau\left(\mathbf{P}_{O \mid A}\right):=\left\{\mathbf{v}: \mathbf{v} \in D\left(\mathbf{p}_{O \mid A} / t, r / t\right), \forall t \in(0, \tau]\right\}$
  • $\mathbf{p}_{O \mid A}=\mathbf{p}_O-\mathbf{p}_A, \quad r=r_A+r_O$
  • $D\left(\mathbf{p}_{O \mid A} / t, r / t\right):=\left\{\mathbf{v}:\left\|\mathbf{v}-\mathbf{P}_{O \mid A} / t\right\| \leq r / t\right\}$
    (반지름이 r/t, 중심이 $\mathbf{P}_{O \mid A} / t$ 인 원)

로봇 A는 장애물 O에 대한 상대속도 set $D\left(-\mathbf{v}_O, v_A^{\max }\right)$ 가 속도 장애물 set에 있을 때
(i.e., if $\mathbf{v}_A-\mathbf{v}_O \in V O_{A \mid O}^\tau$ ), 이것을 피하기 위해 속도를 제어한다.

• Fig 2: $D\left(-\mathbf{v}_O, v_A^{\max }\right) \subset V O_{A \mid O}^\tau$ 인 경우, 시간 범위 $\tau$ 안에 장애물 O를 피하는 것은 불가능함
  ($\mathbf{v}_O > v_A^{\max }$ 인 경우)

• Fig 3: 시간 범위 $\tau$ 너머 장애물 O에 대한 로봇 A의 velocity obstacle set
  이 논문은 이러한 고속 장애물을 처리할 수 있는 장애물 회피 알고리즘을 제안한다.

  $V O_{A \mid O}\left(\mathbf{p}_{O \mid A}\right):=\left\{\mathbf{v}: \mathbf{v} \in D\left(\mathbf{p}_{O \mid A} / t, r / t\right), \forall t>0\right\}$

수식이 너무 많아 간단하게 정리

• veloticy obstacle은 장애물 속도가 일정하다고 가정한다.

• 장애물 반경이 $r_O$일 때, velocity obstacle의 중심좌표는 $\mathbf{p}_{O \mid A}=\mathbf{p}_O-\mathbf{p}_A$ 이고 반경은 $r/t = (r_A - r_O)/t$ 이다.

• Fig 1-(b)의 영역을 velocity obstacle이라 하는데, 이는 로봇과 장애물이 해당 속도를 유지한다고 가정했을 때 장애물이 존재할 가능성이 있는 영역을 나타낸다.

• 따라서 velocity obstacle을 사용하여 장애물 충돌을 방지하기 위해서는, time step 이후 로봇의 중심이 velocity obstacle 영역으로 이동하지 않게끔 로봇의 속도를 조절해 주면 된다.

• Fig 2: $D\left(-\mathbf{v}_O, v_A^{\max }\right) \subset V O_{A \mid O}^\tau$ 인 경우, time step 이후 로봇의 최대 속도 $v_{max}$ 로 이동해도 VO를 벗어나지 못하므로 장애물을 회피하지 못하고 반드시 충돌이 일어난다.

• 본 논문은 $\mathbf{v}_O > v_A^{\max }$ 인 고속 장애물을 처리할 수 있는 알고리즘을 제안하여 이 문제를 해결한다.

4. Avoiding High-Speed obstacles

A. 장애물을 피할 수 없는 상대속도 집합

• $\mathbf{v}_{A \mid O}^{\text {new }}=\mathbf{v}_A^{\text {new }}-\mathbf{v}_O$ : 시간 범위 $\tau$ 동안 장애물과 충돌하지 않는 로봇의 새로운 속도
• $\mathbf{p}_{O \mid A}^{\text {new }}=\mathbf{p}_O+\mathbf{v}_O \cdot \tau-\mathbf{p}_A^{\text {new }}$ : $\tau$ 이후 새 VO 위치
• $\mathbf{p}_{O|A}^{\text{new}} = \mathbf{p}_{O|A} - \mathbf{v}_{A|O}^{\text{new}} \cdot \tau$ : 위 두 식을 합치면 다음과 같다.

만약 $\mathbf{v}_{A \mid O}^{\text {new }}$ 와 $\mathbf{p}_{O \mid A}^{\text {new }}$ 가 아래 두 식을 만족하면 로봇이 속도를 어떻게 바꾸든 더 이상 장애물을 피할 수 없다.

• $\mathbf{v}_{A|O}^{\text{new}} \in VO_{A|O}(\mathbf{p}_{O|A}^{\text{new}})$
• $D(-\mathbf{v}_O, v_A^{\text{max}}) \subset VO_{A|O}(\mathbf{p}_{O|A}^{\text{new}})$

이러한 새 상대 속도 set은 다음으로 표현이 가능함.