Velocity Obstacle(VO)란?

 

논문의 핵심 내용

 

속도 장애물은 바뀌는 시간 환경을 위한 configuration space obstacle의 확장 개념이다.

즉 실시간 환경에 적합하다.

Velocity Obstacle(속도 장애물)은 객체의 Velocity가 속도 장애물인 VO 영역에 들어가지 않으면 물체는 충돌하지 않는다는 개념이다.
 

만약 위 그림과 같이 A와 B 객체가 존재한다면, A와 B가 충돌하지 않기 위해서 A는 B가 존재할 수 있는 공간에 들어가지 않으면 피할수 있다는 생각을 가지는 속도 조절 방법이다.
 

 
군중에서 한개의 객체들은 각각의 Velocity(방향을 가진 속도)를 가진다.  위의 그림에서는 A가 가진 속도는 VA로 나타내고, B가 가진 속도는 VB로 나타내었다.

VO를 계산하기 위해서는 Configurations Space로 변환해야하는데, Configuration Space는 수학에서는 위상 공간의 위치에 대한 점 모음 할당을 설명하는데 사용된다.
위상공간은 특정한 계가 가질 수 있는 모든 상태들의 공간이다.

점 A의 위치에서 바라볼 때 A의 몸체(원형)과 B의 몸체(원형)이 닿지 않는 점까지 고려해야 하기 때문에 A와B의 몸체의 위치들을 고려한 A+B 몸체(원형)과 맞닿아 있는 2개의 직선을 그어서 VO를 정의한다.
A에서 B에 대한 VO를 계산할 때, 위의 그림과 같이 점 A의 위치에서 B의 외곽을 지나는 직선 2개를 구한다. 이 직선 두개를 기준으로 VO는 회색 공간으로 표시된 공간이다. 현재 프레임에서 이 공간에 들어가지 않으면 B와 절대 충돌하지 않는다.
군중 시뮬레이션에서 Path Planning(경로 계획)을 지정할 때, 이러한 속도 장애물을 응용해서 넣는다.

다음 프레임에서 A가 B에 대해 계산한 회색 영역은 VB만큼 이동할 것이다.
회색 영역은 "Collision cone"이라고 부른다.
Collision cone은 계산할때 A와 B의 반지름을 더한 원에 대해서 외곽을 지나는 선 2개를 이용하여 구한다.
 
따라서, A의 Velocity를 조절할 때 VB만큼 이동한 회색 영역 VO를 침범하지 않는 Velocity를 조절하면 다음 프레임에서 A는 B를 피해서 이동하는 것처럼 보일것이다.

따라서 기존의 VA 속도를 VO를 피해서 빨간색 부분만큼으로 조정하면서 시뮬레이션을 진행시키면 충돌을 회피하는 시뮬레이션을 제작할 수 있다.

 

VO의 진동 현상을 줄인 RVO

Reciprocal Velocity Obstacle(RVO) : RVO2

 

 
velocity obstacle 관련 자료 : https://en.wikipedia.org/wiki/Velocity_obstacle

논문 참고 : Motion Planning in Dynamic Environments using Velocity Obstacles - 1998년도 발행