논문 목적

다중 에이전트 시스템에서 충돌 회피를 위한 VO 접근 방식들에 대한 분석

• 속도 장애물(VO)
• 상호 속도 장애물(RVO)
• 최적 상호 충돌 회피(ORCA)

1. Velocity Obstacle(VO)

• VO : 충돌 원뿔 $CC_{ij}$ 와 장애물 속도 $\mathbf{v}_j$의 민코프스키 합

  • $VO_j = CC_{ij} \oplus \mathbf{v}_j$

• 다중 장애물 고려 시 에이전트 i의 속도가 여러 장애물에 대한 VO의 합집합에 속하지 않으면 속도가 유효하다고 판단

  • $\mathbf{v}_{i,k+1} \notin VO_k$
    ($VO_k = \bigcup_{j=1}^{n} VO_{j,k}$)

• 다중 에이전트를 고려한 실제 상황에서, 두 에이전트가 서로 충돌을 해결하려고 시도하는 경우 oscillatory trajectories 현상이 발생할 수 있음. 이러한 현상은 두 에이전트가 서로의 속도를 반복적으로 수정하는 과정에서 다음 시간 $t_{k+1}$ 에서 새로운 충돌이 발생하기 때문에 발생함. 결국 충돌 지점에 이르기까지 진동이 지속됨

• 정적인 장애물이나 일정한 속도로 움직이는 장애물은 VO 기법을 사용하여 보다 쉽게 처리할 수 있음

2. The Reciprocal Velocity Obstacle(RVO)

• VO 진동 제거를 위해 등장, 장애물 또는 다른 에이전트 $j$의 상호적인 움직임을 고려하여 보다 부드러운 회피 경로를 생성

• 두 물체 속도의 평균에 의해 collision cone을 이동

  • $\mathbf{v}_{i,k+1} \notin CC_{ij} \oplus \frac{\mathbf{v}_{i,k} + \mathbf{v}_{j,k}}{2}$

• 에이전트 i와 장애물 j가 서로 어느 방향으로 회피할지 명확하게 합의하지 않는 경우가 발생할 수 있음

3. Optimal Reciprocal Collision Avoidance(ORCA)

• truncation parameter $\tau$ 를 이용하여 충돌 없는 경로를 보장하는 time window 생성
  ($\tau$ 초 동안 새로운 속도로 충돌 없이 이동할 수 있다.)

• 만약, $\mathbf{v}_i, \mathbf{v}_j$ 가 충돌로 이어진다고 가정하면, $\mathbf{u}$ 를 충돌을 유발하는 $VO_j$ 의 경계에 가장 가까운 점으로 향하는 벡터로 정의할 수 있음 (Fig.5)

  • $\mathbf{u} = \left( \arg\min_{\textbf{v} \in \partial VO^\tau} \| \textbf{v} - (\textbf{v}_i - \textbf{v}_j) \| \right) - (\textbf{v}_i - \textbf{v}_j)$

• boundary "바깥쪽"을 향하는 법선 $\mathbf{n}$ 을 이용하여 ORCA의 제약 조건을 다음과 같이 표현

  • 점 $(\mathbf{v}_i-\mathbf{v}_j) + \mathbf{u}$ 에서의 경계와 회피 책임이 동등하게 공유된다고 가정하면, ORCA의 제약 조건을 다음과 같이 표현할 수 있다.
  • $ORCA_k^\tau=\mathbf{v} \left\lvert\, \mathbf{v}-\left(\mathbf{v}_i+\frac{1}{2} \mathbf{u}\right) \cdot \mathbf{n} \geq 0\right.$

• 속도 $\vec{v}$ 의 기하학적 표현은 Fig.5(b) 에 나타나 있다. 여기서 half plane 으로 표시되며, 법선 $\vec{n}$ 을 갖고 초기 지점은 다음과 같다.

  • $\mathbf{p} = \mathbf{v}_i + \frac{1}{2}\mathbf{u}$

• ORCA 선 자체는 시나리오를 선형 제약 조건만을 사용하여 설명할 수 있도록 해준다. 또한, 상대 속도 공간(RVO, Reciprocal Velocity Obstacle)을 반평면으로 표현하면, 다른 ORCA 선에 의해 이미 포함된 제약 조건을 제거하여 제약 조건 집합을 단순화할 수 있다. 이를 통해 연속적으로 부드러운 에이전트의 경로를 보장할 수 있다.