RVO :: Reciprocal Velocity Obstacles

Velocity Obstacle이 무엇인지 -> [클릭]

VO :: Velocity Obstacles

Reciprocal Velocity Obstacles는 Velocity Obstacle을 multi-agent system에 적용하였을때 발생하는 Oscillation 문제를 해결한 것이 주요 Contribution이고 Velocity Obstacle의 Symmetry, Translation Invariance등 주요 성질을 이용해서
RVO가 Collision Avoidance와 Oscillation Avoidance함을 증명하고 있다.

Fig. 1

preferred velocity -> pref vel (너무 길어서 줄여서 쓰겠습니다.)
agent A와 B는 목적지를 향해 나아갈때 pref vel 를 가지며, 이는 충돌로부터 자유로운 상황 즉 VO영역에 pref vel가 포함되지 않은 상황을 이야기한다.

하지만 VO영역에 다음과 같이 pref vel가 포함될경우 Fig. 1에서 dashed line과 같이 충돌하지 않는 VO영역의 속도를 선택하여 회피기동을 하는데, 이때 회피기동을 하기 시작했을때 각자 agent는 dashed line속도를 가지게되고 이를 기반으로 VO 영역을 그렸을 때 Collision Free한 상황이므로 pref vel을 가지게 된다.

그렇게 pref vel을 agent의 속도로써 가지게 되고 바로 다시 VO 영역을 그리게되면 VO영역에 포함되게 되고 위와 같은 과정을 pref vel이 VO영역을 벗어날 때까지 무한 반복하게 되므로써 Oscillation이 발생하는 것 이다.

이를 그림으로 표현 한다면 아래와 같다.

Fig. 2

이러한 문제를 해결하기 위해 새롭게 RVO라는 영역을 다음과 같이 정의했다.

VO는 기본적으로 상대속도를 기준으로 했다면 RVO는 현재 나의 속도, 상대의 속도의 평균을 기준으로 한다.
따라서 VO를 상대속도를 기준으로 그렸다면 RVO는 평균을 기준으로 그린다. [Fig. 3]

Fig. 3

VO의 symmetry, Translation Invariance 특성을 이용해 RVO에서 구한 회피 속도가 VO영역에서도 회피될 수 있음을 증명한다. [Fig. 4]

 

Fig. 4

위는 VO의 특성을 그대로 물려받고 VO를 통해 Collision free한 상황을 만들 수 있다는 것을 보여준다.
Oscillation 문제역시 RVO에서 회피 속도를 선택하면서 위에서 언급했던 VO와 같은 과정을 진행하는데
회피속도를 선택한 이후 Collision Free가 되고 pref vel이 RVO 영역에 포함되면서 pref vel은 선택할 수 없게되고 새로운 회피속도를 계속 찾아가면서 회피기동을 좀 더 길게 하게되고 그로써 Oscillation 문제가 해결이 되는 것이다.[Fig. 5]
(이부분은 평균속도를 가지게되는 부분과 관련있는데 제가 의미를 다 파악하지 못해 엄밀히 말할 수 가 없는 상태라 다음과 같이 썻습니다.)

Fig. 5

이를 VO와 같이 순서대로 그려본다면 다음과 같다. [Fig. 6]

Fig. 6

여기까지 내용을 통해 RVO가 Collision과 Oscillation을 회피함을 알 수 있습니다.

이를 더 많은 Agent를 가진 상황으로 확장하고 하나의 Agent를 기준으로 삼아 살펴보자면

Fig. 7

다음과 같이 그려질 수 있겠습니다.
1.Agent들은 모두 다같이 같은 방향으로 회피를 하기로 돼있고
2.그렇다면 RVO1,2 영역의 회피하기로 한 선분을 기울기를 따라 쭉 그엇을때 A1 주변 영역만이 회피할 수 있는 RVO1, RVO2의 outside 영역이 되겠습니다.
3.회피 속도는 pref vel과 가장 가까운 속도를 선정하기로 돼있습니다.

하지만 많은 Agent가 존재해 RVO영역으로 꽉차버려서 회피할 수 있는 곳이 없을 수 있습니다.[Fig. 8]

Fig. 8 Reciprocal Velocity Obstacles 논문그림

이러한 경우에 두가지 개념을 도입해 상황을 해결하고 있습니다.
1.Penalty velocity
2.Neighbor region

Penalty velocity는 각각의 RVO영역의 outside에 해당하는 velocity를 충돌하기까지 걸리는 시간을 통해 penalty를 가중시키고 이 penalty가 최소인 회피속도를 선택하여 최대한 충돌이 늦게일어나는 방향으로 회피하게 됩니다.

Neighbor region은 굳이 멀리있는 Agent들까지 관심을 두지 않겠다는 것인데 관심영역을 줄이게 된다면 다음과같이 회피할 수 있는 곳을 좀 더 local하게 계속해서 찾아나갈 수 있는 개념입니다.

Fig. 9

본 논문의 주요한 결과 중 하나는 다음과 같습니다.