VAN DEN BERG, Jur; LIN, Ming; MANOCHA, Dinesh. Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE international conference on robotics and automation. Ieee, 2008. p. 1928-1935.
로봇의 지역 경로 계획(local planning)을 개선하여 충돌을 해소하는 방식인데 결과가 놀라웠습니다. 한번 같이 봐보시죠!
0. 전역 경로 계획, 지역 경로 계획이란
로봇을 원하는 지점으로 이동시키기 위해서는 전역 경로 계획(global planning)과 지역 경로 계획(local planning)이 필요합니다.
global planning은 목적지까지 가기 위해서 로봇이 어떤 지점들을 들려야 하는지 계획하는 것이고,
local planning은 로봇이 실제로 움직이면서 장애물을 어떻게 피하고, 가속/감속을 어떻게 할지 계획하는 것입니다.
사람이 운전하는 것에 비유하자면
global planning은 목적지에 가기 위해 네비게이션을 사용하여 경로를 찾는 것과 대응되고 local planning은 운전자가 네비게이션이 알려주는 경로대로 운전하는 것과 대응됩니다.
1. 지역 경로 계획에서 속도를 어떻게 정하나요?
로봇의 속도를 정하는 방법으로는 Proportional Integral Differential(PID), Model Predictive Control(MPC) 여러 가지가 있지만 이번에 새롭게 알게 되었던 것은 Velocity Obstacle(VO)입니다.
트위니에서 일하면서 어깨 너머로 PID, MPC를 이용해서 local planning을 한다고 듣기만 했지 자세히 알지는 못합니다...ㅋㅋㅋ
VO는 다음과 같이 로봇의 최적 속도를 찾고, 이를 주기적으로 반복합니다.
local planning이 실행되는 순간의 로봇들의 속도를 이용해서 충돌이 발생할 수 있는 속도값들을 모두 찾습니다.
local planning이 실행되는 순간의 로봇들의 속도가 이번 주기 동안은 유지된다고 가정합니다.
1에서 찾은 속도값들을 제외한 값 중에서 기준에 맞는 최적 속도를 찾습니다.
최단 시간, 에너지 효율, 장애물과의 충돌 가능성 등 다양한 기준이 있습니다.
2. 구체적인 예시를 통해서 VO 설명해주실 수 있을까요?
예시를 통해서 구체적으로 살펴보겠습니다.
속도는 시간 당 변위를 뜻하므로 각 좌표 축에 대한 속도가 존재합니다.
예를 들어, 하늘을 날아다니는 비행기의 속도는 x, y, z축에 대한 속도인 (Vx, Vy, Vz)로 표현할 수 있습니다.
AMR 같은 경우에는 z축 이동이 없으므로 x, y 축에 대해서만 속도를 고려하면 되므로 (Vx, Vy)로 표현할 수 있습니다.
2.1. 로봇들의 상태 확인하기
다음과 같이 (3, 0) 좌표에서 정지한 로봇1과 (-5, 0) 좌표에서 (1, 1)의 속도로 움직이고 있는 로봇2가 있는 상황을 가정해봅시다.
초기 상태
Q. 로봇의 형태를 원형으로 그렸는데 이유가 있을까요? A. 로봇 간의 충돌이 발생하는지 계산할 때에는 로봇의 형태가 중요한데 가장 계산하기 쉬운 형태가 원형이라서 원형으로 가정했습니다. - "로봇1의 반지름 + 로봇2의 반지름 < 로봇1의 중심으로부터 로봇2의 중심까지의 거리" 이 참이라면 충돌이 발생한 것입니다. 만약 로봇의 형태를 정교하게 계산한다면 조금 더 복잡한 계산이 필요해집니다.
Q. 로봇1이 정지한 상태인데 로봇1이 이동 중이면 결과가 달라지나요? A. 동일한 결과를 보여줍니다. 로봇2의 속도를 로봇1에 대한 상대 속도로 변환하면 로봇1은 정지한 상태라고 볼 수 있기 때문에 위와 동일한 형태를 띄게 됩니다.
2.2. VO 구하기
로봇1, 로봇2가 원형이고 "로봇1의 반지름 + 로봇2의 반지름 < 로봇1의 중심으로부터 로봇2의 중심까지의 거리"으로 로봇 간의 충돌을 확인하므로
로봇1을 반지름을 0인 점으로 치환하고, 로봇2를 반지름이 "로봇1의 반지름 + 로봇2의 반지름"인 원으로 치환해도 똑같이 충돌을 확인할 수 있습니다.
로봇 크기 변환
시간 t에 대해서 로봇들의 좌표를 표현하면 다음과 같습니다.
로봇1: (Vx*t+3,Vy*t)
로봇2: (t-5, t)
위의 좌표를 이용해서 시간 t에 대해서 로봇 간의 충돌을 확인할 수 있는 식을 만들면 다음과 같습니다.
((Vx - 1)*t + 8)^2 + ((Vy - 1)*t)^2 <= 4, t는 양의 실수
=> (Vx - 1 + 8/t)^2 + (Vy - 1)^2 <= (2/t)^2
그리고 위의 식을 풀어서 Vx, Vy가 존재할 수 있는 영역을 그려보면 다음과 같습니다.
계산한 Velocity Obstacle!
Q. (1, 1)은 속이 빈 원이 그려져 있는데 의미가 있을까요? A. (1, 1)에서는 충돌이 발생하지 않는다는 것을 의미합니다. 실제로 (1, 1)을 위에 식에 대입해보면 64 <= 4 으로 성립하지 않습니다. 그래서 (1, 1)을 포함시키지 않기 위해서 위와 같이 표현했습니다.
Q. 위의 부등식은 어떻게 풀었나요? A. 위의 부등식이 의미하는 것은 0보다 큰 t에 대해서 (1 - 8/t, 1)를 중점으로 가지며 반지름이 2/t인 원과 내부에 있는 점들을 의미합니다. 그림으로 그려보면 아래와 같은 형태라는 것을 알 수 있습니다. tan 값을 구하면 직선의 기울기를 구할 수 있고, 이를 이용해서 충돌이 발생하는 영역을 구했습니다. 직선의 기울기
2.3. 최적 속도 구하기
이제 VO가 아닌 속도 중에서 값을 고르면 됩니다. 그런데 어떤 값을 골라야 할까요?
로봇의 스펙과 어떤 기준을 더 중요시 여기느냐에 따라서 달라집니다.
1차적으로 로봇이 현재 낼 수 있는 가속도로 한번 필터링 하고, 기준에 따른 cost 값이 최소가 되는 속도를 정해야 합니다.
예를 들어서 로봇이 낼 수 있는 가속도가 "x^2+y^2 <= 1" 를 만족해야 하고, 최단 거리를 기준으로 한다고 가정해보겠습니다.
1차적으로 하늘색 원에서 VO를 제외한 영역이 우리가 선택할 수 있는 속도 영역이 됩니다.
다음으로 (-5, 0)으로 가장 빠르게 가까워지는 (-1, 0)을 최적 속도로 구할 수 있습니다.
최적 속도 정하기
3. 오, VO는 이해한 것 같아요. 그러면 Reciprocal VO는 뭐에요?
3.1. Oscillation 문제
VO로 충돌을 회피하는 최적 속도를 계산하더라도 "Oscillation" 이라는 문제가 발생할 수 있습니다.
다음 그림들과 같이 로봇1, 로봇2가 서로 마주보며 이동하고 있으면 적당히 피해가는 그림을 생각하실 거에요.
매끄럽게 피해가는 것을 희망함!
하지만 VO는 그 순간의 충돌 여부만을 계산해서 최적 속도를 고르기 때문에 다음과 같이 움직이게 됩니다.
어! 이제 충돌 안하네? 다시 원래대로 돌아가자!
그래서 로봇들이 확실히 충돌이 발생하지 않는 구간으로 이동하기 전까지는 "왔다 갔다" 하는 움직임을 보이게 됩니다.
Oscillation이라고 문제를 명명한 이유가 이거인 것 같더라고요 ㅋㅋㅋ
3.2. Reciprocal VO
Reciprocal VO(RVO)는 로봇의 현재 속도와 VO를 이용해서 RVO를 만들어 이 문제를 해결했습니다.
논문에서 정의한 RVO는 다음과 같습니다.
RVO 정의
위와 같이 RVO를 정의하게 되면 이전 속도가 RVO에 포함되어서 Oscillation 문제가 해소됩니다.
RVO가 로봇들을 얼마나 효율적으로 이동시킬 수 있는지 알 수 있는 실험 결과도 제시되었습니다.
수많은 로봇들이 몰리는 환경 속에서도 교착 상태가 발생하지 않고 로봇들이 목적지로 가게됩니다.
Fig8 and Fig9 of VAN DEN BERG, Jur; LIN, Ming; MANOCHA, Dinesh. Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE international conference on robotics and automation. Ieee, 2008. p. 1928-1935.
게다가 알고리즘의 실행 속도도 매우 빠릅니다! 로봇이 1000대가 있어도 10Hz가 나옵니다.
Intel Core2 Duo 1.66 GHz에 1GByte 메모리로 이만큼의 성능이 나왔으니 성능 걱정은 필요 없을 것 같습니다.
Fig11 of VAN DEN BERG, Jur; LIN, Ming; MANOCHA, Dinesh. Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE international conference on robotics and automation. Ieee, 2008. p. 1928-1935.
※ RVO를 사용했을 때 충돌이 발생하지 않는 것을 어떻게 보장할 수 있는지, Oscillation 문제가 해소되었다는 증명을 보고 싶으시다면 논문을 보시는 것을 추천드립니다!
4. 그렇다면 RVO로 로봇 관제를 하면 모든 것이 해결되는 건 아닌가요?
아쉽게도 RVO가 모든 문제를 해결해주지는 않습니다.
교착 상태가 발생했을 상황에서도 좋은 local planning으로 로봇들이 목적지로 갔지만, 애초에 로봇들이 몰리는 상황을 방지하는 것이 더 효율적이기 때문에 global planning 혹은 작업 배정 알고리즘도 필요합니다.
MAPF 알고리즘의 탐색 시간을 줄이기 위해서 RVO를 활용할 수 있지 않을까 싶습니다.
RVO라는 좋은 local planning이 있으니 Following Conflict, Cycle Conflict, Swapping Conflict는 고려하지 않는 것은 어떨까요? Conflict 수가 줄어들면서 탐색 시간이 빨라질 것입니다.
