티스토리 뷰
https://www.youtube.com/watch?v=Ao7p_xiUu4s&t=4s
모션 플래너는 Rapidly Exploring Random Tree(RRT)를 기반으로 한다.
부분적으로 형성된 검색 트리 T부터 시작
x_start는 초기 상태이고, X는 상태 공간이며, X_goal의 모든 상태는 acceptable final state(로봇이 성공적으로 목표를 달성했다고 간주되는 상태 )이다.
RRT planner는 x_samp라는 상태를 랜덤으로 정한다.
그리고 트리 안에서 가장 가까운 노드 x_nearest에서 collision-free motion을 하면서 x_new로 선을 긋는다.
이는 x_samp에는 닿지 않지만, 적어도 x_samp에 최단거리로 가는 길목을 차지한다.
최종적으로는 x_samp를 없애면서, tree를 업데이트한다.
이 process는 node가 X_goal의 region에 들어갈때까지 반복한다.
따라서 완료를 위해서는, X_goal 내에서 샘플 x_samp를 선택해야 하는 경우가 많다.
직관적으로 말하자면, 무작위로 선택된 샘플이 트리를 당겨서 늘린다고 생각하면 된다.
완벽하게 랜덤이라면, 확장성이 부족하다(최단거리도 아니고, -로도 길이 생긴다)
따라서 RRT가 효율적이다.
3번째 줄에서는 상태 공간에서 샘플링
4번째 줄에서는 이미 트리에 있는 가장 가까운 노드를 찾는다.
5번째 줄에서는 로컬 플래너를 사용하여 가장 가까운 노드에서 샘플링된 상태에 더 가까운 상태로의 모션을 찾는다.
6,7번째 출에서는 모션에 충돌이 없는지 확인하고, 없을 경우 트리에 새 edge 추가
8,9 번째 줄에서는 새 노드가 목표 영역에 있는지 확인하고, 없다면 다시 반복
목표 영역의 노드에서부터 뒤로 가면서 부모 노드의 순서를 따라 계획(plan)을 재구성합니다
3행의 샘플러는 상태 공간 X에서 균일하게 무작위로 상태를 선택할 수 있다.
그러나 결정론적 샘플링 방식을 포함한 다른 옵션도 가능하다.
Van der Corput 샘플링
1차원 상태 공간에서 사용될 수 있다.
간격 주위를 이동하여 점진적으로 미세하고 균일한 간격 샘플링을 제공하는 결정적 시퀀스다.
최종적으로는 균일한 간격의 점들이 찍힌다.
이는 솔루션을 찾을 때까지 해상도가 증가하는 다중 해상도 샘플링과 같은 결과를 가져오기 때문에 매력적이다.
Van der Corput 수열을 고차원 공간으로 일반화한 것을 Halton 수열이라고 한다.
알고리즘 설계자는 작업에 자장 적합한 샘플링 알고리즘을 선택할 수 있다.
샘플러는 Plan의 프로세스를 완료하기 위해 목표 지역의 상태를 샘플링해야 한다(직선 거리이므로)
4번에서는 x_samp에 가장 가까운 트리의 노드를 선택한다.
이 작업을 효율적으로 하기 위해서, 다양한 데이터 구조와 알고리즘을 사용할 수 있지만,
두 x_samp과 x_nearest의 거리에 대한 합리적인 정의가 있어야 한다.
만약에 구성이 선형 좌표와 각도 조표로 구성된 경우, 1라디안 거리와 1미터를 비교할 수는 없다.
또한 파란 자동차 1개와, 하얀 자동차 3개가 있다고 해보자.
파란 자동차는 x_samp이고, 하얀은 트리의 edge이다.
샘플에 가장 가까운 자동차는 무엇인가? 어떤 걸 기준으로 삼아야 하는가?
자동차의 모션 제약(시간에 따른 움직임)을 고려한다면 아래쪽의 자동차가 합리적이다. 여기서는 로봇을 운행하는 것이기 때문. 즉, 시간에 따라 path를 결정하는 게 상대적으로 옳다.
로컬 플래너
라인 5는 트리의 노드에서 로컬 플래너로 x_new를 정한다. 이건 정해진 바가 없지만 빠르게 동작해야 한다.
라인 6에서는 계획된 모션에 충돌이 없는지 확인하므로 로컬 플래너에서 충돌을 걱정할 필요가 없어진다.
가장 간단한 로컬 플래너는 속도를 입력으로 사용하여 로봇의 운동에 대한 직선 경로를 반환하는 것.
보다 일반적인 역학을 도입하자면, x' = f(x,u)가 된다.
이는 로봇의 제어를 이산화(연속적인 함수나 불연속적인 점들로 변환)하고,
일정 시간을 정해 각 제어를 그 시간만큼 통합하고 x_samp과 제어에 가장 가까운 새 상태 x_new를 선택할 수 있다.
예를 들어, 자동차와 같은 로봇은 2개의 제어를 가진다. 선속도와 각속도
제한된 선형 속도와 제한된 회전 반경을 가진 자동차의 경우 컨트롤의 경계는 나비 넥타이 공식처럼 된다.
V가 높아지면 높아질수록 w는 컨트롤하기 어려워져서, 범위가 한정되어진다.
그리고 상식적으로 생각해도 제자리에서 순식간에 360도를 도는 자동차는 없다.
우리는 이 제어 세트를 전진 모션, 후진 모션,가장 좁은 회전 반경에서의 회전을 포함하는 6가지 속도로 분리할 수 있다.
이러한 컨트롤의 통합은 다음과 같이 표시된다.
x_new는 결국엔 나비 넥타이 경로 중 하나에 표시될 것이고, 이는 x_samp과 가까우므로 이 경로에 충돌이 없다면 x_new가 RRT에 추가된다.
이 로컬 플래너는 모든 로봇에 적용할 수 있다는 점에서 단순성과 일반성이 매력적이다.
마지막으로는 각 형태에 최적화된 로컬 플래너를 계획할 수 있다.
자동차와 유사한 로봇의 경우, Reeds-shepp 곡선이 장애물을 고려하지 않고 두 구성 사이의 경로 길이를 최소화하는 경로가 된다.
Reed-shepp 곡선은 로컬 플래너에 적합한 후보이다.
RRT는 아주 쉬운 코드이며 고치기도 쉽고, 여러가지 변형이 다양한 어플리케이션에 사용된다.
일반적으로 복잡한 모션 계획 문제를 신속하게 해결하도록 설계되었지만, 솔루션의 품질은 고려하지 않았다.
솔루션을 품질을 향상시키려면, 초기 솔루션을 찾은 후에도 RRT를 계속 늘리고 최상의 솔루션을 유지할 수 있다.
RRT-Star라고 하는 알고리즘은 트리 노드 수간 무한대로 증가함에 따라 솔루션이 최적의 솔루션이 되는 경향이 있도록 검색 트리를 지속적으로 다시 연결한다.
그러나 RRT-star는 임의의 로봇 동역학에 적용될 수 없다.
RRT,PRM 및 관련 알고리즘과 같은 샘플링 기반 방법은 단순성과 일부 복잡한 동작 계획 문제에 대한 성능으로 인해 널리 사용된다.
+사담 : 한 유튜브 댓글
필자도 매우 공감하는 바이다.