VO :: Velocity Obstacles

문제
각 에이전트는 서로 통신하지 않고 독립적으로 탐색, 장애물 및 환경의 다른 에이전트와 충돌하지 않아야함

A와 B를 같은 환경에서 주행하는 로봇이라고 하자.
A와 B는 각 자신을 기준으로 하였을때 상대 로봇인 A혹은 B는 Obstacle 즉 피해야 할 장애물이다.

측정을 통해 장애물의 모양, 위치와 속도를 알고, 속도는 일정하다고 가정한다.

Fig.1

이때 A를 기준으로 한다면 B의 상대속도는 다음과 같이 표현할 수 있다 [Fig.2]

Fig.2

A의 반지름 : rA
B의 반지름 : rB
Local하게 장애물을 회피하기 위해서 Collision Cone 개념을 도입하는데 A의 상대속도 벡터가 Collision Cone 영역내에 존재 한다면 충돌한다고 얘기할 수 있고 Collision Cone 영역은 A와 B가 충돌하는 A의 상대속도 벡터의 집합이라고 볼 수 있다. 그리고 이러한 집합(영역)을 VO( Velocity Obstacle)이라고 한다.
A는 점 형태인 Object, B는 rA+ rB의 반지름을 가지는 Object로 다시 정의하고 Collision Cone은 점 A를 기준으로 B를 외접하는 두개의 직선을 그리는 것으로 한다.[Fig.3] (A를 점으로 보고 B에 크기를 더 해줌으로서 보상해준 것으로 볼 수 있음)

Fig.3

VO는 Symmetry, Translation Invariance와 같은 성질을 만족한다.[Fig.4]

Fig.4

그렇다면 회피는 어떻게 한다는 것인가?
기본적으로 VO 영역 외에 있는 속도 v를 선택하면 된다.[Fig.5]

Fig.5

RVO까지 진행해보려 했지만 RVO의 개념은 Collision Free와 Oscillation Free를 보장받기 위해 VO의 정점을 A와 B의 평균속도 지점으로 translation시키고 두 agent는 같은 알고리즘을 가지고 같은 방향으로 회피를 해야한다는 것인데 나에게는 와닿지 않았다.. 물류센터와 같은 환경에서는 유용할 것 같다.
--> RVO