사전지식
Velocity Obstacle(VO)
Reciprocal Collision Avoidance (RCA)
정의
B의 속도가 어떻게 되었든, (t초내에) 절대 충돌하지 않을 수 있는 A의 속도 집합
t초내에 충돌하는 상대속도 V_a-V_b의 집합
- V_b: 가능한 모든 b의 속도 집합
Optimal Reciprocal Collision Avoidance(ORCA)
- A와 B의 속도집합이 각각 RCA 집합과 일치하는 상황: reciprocally maximal.
- RCA를 구하기 위해서는, A가 B의 속도 허용 범위를 알아야 하고, B도 A의 속도 허용 범위를 알아야하는데, 실제 세계에서는 다른 agent와 통신이 안되는 경우가 많다.
정의 1
- RCA 범위 내에서, 우리는 최적 속도 V_a^opt와 V_b^opt 에 근접한 V_a와 V_b 집합을 극대화하는 속도들을 고르고싶다.
- 뜻: ORCA A 집합은, V_a 집합 중에서,
오차범위 내 최적속도 v_a^opt와 가장 교집합이 많은 집합이다. - 뜻: ORCA B 집합은, V_b 집합 중에서,
오차범위 내 최적속도 v_b^opt와 가장 교집합이 많은 집합이다.
- 뜻: ORCA A 집합은, V_a 집합 중에서,
개념
- 위 그림에서, 직선 2개가 각각 ORCA of A and B 이다.
로봇의 위치, 반지름, optimization velocity를 관측으로도 알 수 있다면, 로봇끼리는 통신 없이도 ORCA를 구할 수 있다.- 로봇의 optimization velocity의 합리적 선택 방법은 추후 설명 계획
n-body Collision aviodance
Basic Approach
- 로봇의 위치, 반지름, optimization velocity를 관측으로도 알 수 있다는 가정
Step 1
- 상대 로봇의 최대 속도를 알 수 있다는 가정하에, t초 내에, 서로 최대 속도로 다가와도 충돌을 절대 못하는 범위 내에 있는 로봇들은 관심 로봇에서 제외.
Step2
- 모든 로봇에 대해 t초 내로 충돌을 일으키지 않는, A의 가능한 속도 범위는 아래와 같음.
- 위 그림의 색칠된 영역임.
Step3
- 위 색칠된 영역 중에서, 선호 속도와 가장 가까운 속도를 선택하여, 앞으로 나아감
- 여기서 선호 속도는, 목적지와 직선으로 이은 후, 최고의 속도를 내는 속도 정도가 되겠다.
참고
- 위 step 2와 step 3는 linear programming으로 해결 가능함. (최적 속도와의 거리를 찾는 문제)
- 2차 최적화 문제이지만, 하나의 local minimum만을 가지기 때문에, linear programming 특성을 띈다.
- O(n)의 execution time. (n은 주위 로봇 수)
- 만약 로봇들의 최적 속도가 잘 선택된다면, ORCA A는 무조건 해를 지닌다. (항상 충돌을 회피하는 속도를 선택할 수 있다.)
Choosing the Optimization Velocity
- 주변 로봇의 최적 속도를 가정하는 방법은 아래 3가지가 있는데, 현재 속도로 가정하는 것이 가장 합리적이다.
주변 로봇속도를 0으로 가정
- 장점
- ORCA A가 항상 해를 지님
- 단점
- 주변 로봇이 정지하고 있다는 가정이므로, 성능 자체가 떨어진다.
주변 로봇속도를 preferred 속도로 가정
- 장점
- 주변 로봇이 정지해 있다는 가정보다는 합리적임
- 단점
- 로봇의 preferred 속도를 알려면, 통신이 가능해야함
- 밀도가 높은 상황에서 해를 구할 수 없음.
주변 로봇속도를, 현재 주변 로봇 속도라고 가정
- 장점
- 센싱을 통해 유추할 수 있음
- 로봇의 현재 속도가, 그 로봇의 현재 상황을 잘 반영한다고 볼 수 있음
- 단점
- 높은 밀도 상황에서, linear programming이 해를 가지지 않을 수 있음.
- 이 경우, 3-D linear program을 사용하여, 그나마 가장 안전한 속도를 고른다.
Densely Packed Conditions
- 공부중
Static Obstacles
새로운 것이 들어오면 이미 있는 것과 충돌을 시도하라.