[RRT] Anytime RRTs , Dave Ferguson

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwi30q3ZstuMAxWedfUHHXn1JEQQFnoECBgQAQ&url=https%3A%2F%2Fwww.ri.cmu.edu%2Fpub_files%2Fpub4%2Fferguson_david_2006_4%2Fferguson_david_2006_4.pdf&usg=AOvVaw1BxJeogmAkr43_sDTLjuFx&opi=89978449

https://www.google.com/url?cad=rja&cd=&esrc=s&opi=89978449&q=&rct=j&sa=t&source=web&uact=8&url=https%3A%2F%2Fwww.ri.cmu.edu%2Fpub_files%2Fpub4%2Fferguson_david_2006_4%2Fferguson_david_2006_4.pdf&usg=AOvVaw1BxJeogmAkr43_sDTLjuFx&ved=2ahUKEwi30q3ZstuMAxWedfUHHXn1JEQQFnoECBgQAQ

 

---

0. abstract

• 고차원이며, cost가 균일하지 않은 탐색 공간에서의 path planning을 위한 anytime 알고리즘을 제안한다.
  • 접근 방식은 RRTs를 생성하는 방식으로 작동하며, 각 트리는 이전 트리의 정보를 재사용해서, 성장 속도와 생성되는 path의 품질을 향상시킨다.
  • 또한 RRT을 수정하여, 더 적은 cost의 solution을 선호하도록 탐색을 편향시키는 방법도 제시한다.
    • 우리의 접근 방식은 초기 해를 매우 빠르게 생성하며, 이후 충분한 연산 시간이 주어지면, 이 해의 품질을 지속적으로 개선할 수 있다.
    • 위와 더불어서, 사용자에 의해서 설정된 개선 기준에 따라 이후에 생성되는 해가 이전의 해보다 항상 우수함을 보장한다.

 

---

1. Introduction

• RRT는 path planning문제를 해결하는데 효과적임이 입증되었다. ( 1,2,3,4,5 )
  • RRT는 configuration space의 무작위 샘플링과 원하는 목표 구성 주변의 편향된 sampling을 결합함으로써, 효과적으로 해를 제공한다.
  • 하지만 RRT는 실행가능한 해를 생성하는데 좋지만, 품질에 대한 제어는 없다
    • 특히, ocst가 균일하지 않은 탐색 공간에서, 서로 다른 해 경로의 실행 난이도는 크게 달라질수 있으니 탐색과정에서 해의 비용을 고려하는 것도 중요하다.
      • 예외적으로 [6]에서는 초기 노드로부터의 현재 경로 비용을 기준으로 트리 노드를 확장 대상으로 선택하는 RRT 알고리즘의 변형을 제안했다. 하지만 품질 향상이 되는 대신 계산 비용이 증가했다.

 

• 실제 환경에서는 시간 제약 하에 작동하는 agent에게는 좋은 품질의 해를 빠른 시간에 생성하는게 중요하다.
  • 그래서 우리의 anytime planner는 초기에 매우 비효율적인 plan을 찾아내고, 남은 시간 동안 해당되는 plan을 지속적으로 개산시킨다.

 

• 본 논문의 접근 방식은 연속적으로 RRTs를 생성합니다. 처음에 생성된 tree는 최대한 빠르게 유효한 해를 확보하기 위해서 수정되지 않은 RRT를 사용해서 생성합니다. 이후에, 탐색 단계에서 더 낮은 비용의 해를 찾기 위해 RRT에 여러 수정을 더했습니다.
  • 이로 인해 본 접근 방식은 초기 해를 매우 빠르게 생성하고, 주어진 계산 시간이 허용할때까지 해의 품질을 점진적으로 개선합니다.
• 우리는 먼지 RRT알고리즘과 생성된 해의 품질을 개선하기 위한 RRT의 확장 기법을 설명합니다. 이어서 anytime RRTs를 소개하고 이것이 어떻게 low cost solution을 생성하는지 보여줍니다. 마지막에는 단일 로봇 네비게이션과 다중 로봇을 이용한 여러 결과를 제시하고, 논의를 마무리하며 추가 확장 가능성에 대해서 설명합니다.

 

---

 

 

5. Discussion

• 지금까지의 sampling기반의 planner의 한계중 하나는 '좋은 품질의 해를 제공하지 못한다'나 '생성한 해의 최적성 편차에 대한 경계를 제시하지 못한다'입니다.
• 본 연구에서 sampling기반의 planner가 더 나은 해를 선호하게 유도하는 효과적인 방법을 제안했습니다.
  • 이 기법은 비균일 비용 탐색 공간에서 낮은 비용의 해를 생성하는데 매우 유용합니다.
  • 더불어서, 이 기법이 시간이 지남에 따라서 해를 개선할 뿐만 아니라, 개선의 품질에 대한 경계를 제공하고 수용할 수 있는 anytime sampling 기반의 planner에 통합될 수 있음을 보였습니다.
• 본 연구의 anytime 방식은 일련의 RRT를 생성하며, 각 RRT는 사용자 정의 개선 계수에 의해서 이전의 해보다 cost가 낮은 새로운 해를 보장합니다.
  • 즉, 표준 RRT만큼 빠르게 유효해가 리턴되지만, 이후 plan시간이 허용하는 동안 해의 품질이 개선됩니다.
    • 이로 인해서 최근 개발된 이산 anytime알고리즘과 유사한 이점을 제공하면서도 훨씬 더 고차원인 탐색 공간에 대해서 plan을 수립할 수 있습니다.

 

• 본 연구 확장을 위해 아래의 방법을 모색하고 있습니다.
  • 1. 이전의 해들로부터 더 많은 정보를 활용
  • 2. 휴리스틱을 사용해서 트리의 성장을 효과적으로 집중시키기
  • 3. 자율주행에 적용 

 

---

 

 

 

fig 1

2. RRT

==> 'RRT소개하고 ARA*라는 알고리즘 간단히 말하고, 이를 ARA*의 원리를 RRT에 적용해보겠다.'라는 내용

• 표준적인 RRT는 fig1에 제시되어 있습니다. ( RRT는 q_start에서 q_goal로 가는 path를 계획하기 위한 알고리즘.)
  • 라인 1 : 알고리즘은 초기 루트 노드로 하는 탐색 트리를 초기화 합니다. 그리고 goal에 도달할때 까지 점진적으로 확장해 나갑니다.
  • 라인4 : 트리 확장을 위해서 ChooseTarget함수로 configuration space안에서 임의의 목표인 q_target을 선택합니다.
  • 라인 5 : NearestNeighbor함수로 트리에 존재하는 노드들중 q_target와 가장 가까운 노드를 선택합니다.
  • 라인 6 : Extend함수로 q_nearest로부터 q_target방향으로 일정 거리만큼 트리를 확장합니다. 만약에 충돌이 존재해면 null이 됩니다. 충돌이 없다면 q_new에는 해당 위치가 저장됨.
  • 라인 2~8 : GrowRRT는 사용자가 설정한 임계값까지 도달할때 까지 반복한다.
• RRT의 뛰어난 속성중 하나는, 미탐색 영역으로 강하게 편향된다는 점입니다.
  • 이러한 탐색을 목표에 집중시키면 RRT의 효율성을 향상 시킬수있습니다.( 라인 9~11)

 

• 앞에서 말했는 기존의 RRT는 탐색 과정 중에 해의 비용을 고려하지 않아서 비균일 비용 탐색 공간에서는 비효율적인 해를 만들수 있습니다. 
  • 그래서 Urmson은 트리 확장을 위한 노드를 선택할때 비용을 고려하는 3가지 수정된 RRT알고리즘을 제안했습니다.
    • 1. 라인 5의 단순한 NearestNeighbor함수를 대체하기 위해서, 현재의 q_target에 대해서 k개의 가장 가까운 이웃을 찾은후에, 이 k개의 노드 중에서 아래 3가지 기준에 의해서 노드를 선택했습니다.
      • 1-1. q_target에서 가장 가까운 q_nearest를 선택하는 경우.( 단, 'q_start에서 시작해서 q_nearest를 거쳐서 q_goal까지의 경로 비용 추정치'가 임계값보다 낮은 경우)
      • 1-2. k개 노드를 비용 추정치 기준으로 정렬 후, 추정 경로 비용이 threshold보다 작은 첫번째 노드를 선택하는 경우
      • 1-3. 추정 경로 비용이 최소인 노드를 선택하되, 해당 비용이 threshold보다 낮은 경우
      • ==> 위의 3가지 선택 방식은 각각 다른 알고리즘을 유도했으며, 이중에서 3번째 방식이 가장 우수했으나 표준 RRT보다 많은 계산을 요구 했습니다.

 

• 필자는 부분적으로 알려진 실외 환경에서 단일,다중 에이전트의 네비게이션을 위해 RRT를 사용하고자 합니다.
  • 실제 환경에서 작동하는 agent는 plan이 빠르게 생성되어야하는 상황과 충분한 시간을 가지고 더 나은 plan을 요구하는 상황 모두에 직면할 수 있다.
  • 에이전트는 사용 가능한 plan시간이 얼마나 되는지 알수 없으니, 여러 해를 생성한 후에 실행 시점에 가장 좋은 해를 선택하는 것이 유용하다.

 

• 이산 계획 분야에는 이러한 알고리즘이 이미 존재합니다.(7,8)
  • Thrun이 개발한 ARA*는 높은 최적성 한계 e를 가지는 확장된 A*탐색을 수행하여, 초기에는 비효율적인 해를 생성한 뒤에, 이후 점차적으로 e를 줄여가며 해를 반복적으로 개선합니다. 
  • 저자는 고차원 공간에서 plan을 만들기 위해서 위의 알고리즘을, sampling기반에 대응하기 원합니다.
    • 그래서 저자는 다음 섹션에서 표준 RRT를 가지고 초기 해를 효율적으로 구성한후, 일련의 해를 생성함으로써, 이전의 모든 해보다 일정 개선 계수만큼 비용이 낮은 해를 보장하는 anytime 알고리즘을 제안한다. 
      이러한 후속 해는 현재 트리내의 노드와 이전 해의 비용을 모두 고려하여, 탐색 공간의 샘플링 , 트리확장을 위한 노드선책 , 그리고 확장 연산 자체에 영향을 주는 방식으로 생성된다.

 

 

 

---

3-1. ANYTIME RRT

• 이산 anytime 알고리즘들은 연속적으로 이전 solution보다 개선된 solution을 효율적으로 생성함으로써 anytime성능을 달성합니다.
  • 이는 언제든지 지금까지 발견된 최상의 solution과 이 solution의 최적성 편차를 함께 반환할 수 있습니다.
• 이와 동일한 기본 아이디어를 사용해서 sampling기반의 anytime알고리즘을 만들 수 있습니다.
  • 1. 우선, cost를 고려하지 않고 RRT를 사용해 initial solution을 얻습니다.
  • 2. 그 다음에 RRT가 반환한 solution의 cost를 Cs에 기록합니다.
  • 3. 이후 새로운 RRT를 생성할때마다, 트리에 추가되는 노드들의 전체 cost가 Cs보다 낮은 solution에 기여할 수 있는 노드들로 제한하여 이전의 solution보다 개선된 solution을 보장합니다.
    • 또한, 비용한계 Cs에 (1 − ϵ_f)와 같은 계수를 곱하여 다음 solution이 이전 solution보다 최소 ϵ_f만큼 비용 면에서 개선되게 합니다. 이때 ϵ_f는 solution improvement factor라고 합니다.
  • 4. 이후 새로운 solution의 cost를 바탕으로 Cs를 업데이트하고, plan시간이 다 될때까지 위의 과정을 반복합니다.
  • ==> 이러한 방식은 각  solution이 이전의 모든 solution보다 좋은 solution임을 보장하나, 새로운 solution을 생성할수 없는 경우도 있습니다. 따라서 해당 방식이 효과적이기 위해서는 연속적으로 낮은 비용의 해를 생성할 수 있는 신뢰할 만한 방법이 필요합니다.
    • 그래서 저자는 cost고려와 가변 bias 계수를 통합한 새로운 노드 샘플링A, 노드 선택B , 노드 확장 기법C에 의존해서 주어진 cost 한계를 만족하는 해들을 효율적으로 생성합니다.

 

---

3-2. ANYTIME RRT - ( A. Node Sampling )

• 만약 우리가 '상한 비용 Cs'보다 낮은 solution을 생성하는데 관심이 있다면, 해당 상한 값을 RRT알고리즘에서 사용하는 sampling 과정에 반영할 수 있습니다.
• 전체 configuration space를 random하게 sampling하는 대신에, 상한을 만족할 가능성이 있는 configuration space로 sampling을 제한합니다.
  • 특정 노드 q_target에 대해서, '초기 노드 q_start에서 q_target까지의 휴리스틱 비용 h ( g_start , q_target)'과 'q_target에서 목표노드 q_goal까지의 휴리스틱 비용 h ( q_target , q_gaol)'을 계산할 수 있습니다.
    • 만약 휴리스틱 값들이 최적 경로의 비용을 과대 평가 하지 않는다면, 위의 2개의 휴리스틱의 합은 'q_start에서 q_target을 거쳐서 q_goal까지'의 경로 비용의 하한( lower bound)를 제공합니다.
    • 이때 하한 비용이 상한 Cs보다 크다면, q_target은 상한 Cs를 만족할 수 없으니 무시할 수 있습니다.
  • 그래서 제한된 sampling아이디어를 구현하는 방법은, 결합된 휴리스틱 비용이 상한(Cs)보다 작은 노드를 찾을때까지 configuration space에서 임의의 샘플 q_Target을 계속해서 생성하는 것입니다.
  • 또 다른 방법도 존재하는데, 이는 휴리스틱 함수를 사용해서 sampling자체를 수행함으로써, sampling되는 모든 노드가 상한을 만족하게 하는 것입니다.
• ==> 전반적으로 이러한 제한된 sampling기법은 관련성이 없는 configuration space에 소비되는 불필요한 연산을 줄여줍니다.

 

fig 2

• 위의 그림은 초기 구성에서 목표 구성까지 확장되고 있는 부분적인 RRT가 주어질때, anytime RRT가 어떻게 tree를 sampling하고, 선택하며, 확장하는지 보여준다.
  • a : 어떠한 이전 해가 이미 생성되었다.
  • b : anytime RRT접근 방식으로 구성공간을 sampling할때, 개선된 solution으로 이어질 가능성이 있는 곳만 고려됩니다. 이로 인해서 검은 노드들은 제외되고 흰색 노드만 채택됩니다.
  • c : 트리 내에서 다음으로 확장할 노드를 선택할때, sample지점에 가장 가까운 노드 k개를 찾고, 이들 노드를 sample지점과의 거리 및 시작 노드로부터의 path cost를 모두 고려해서 정렬합니다. ( 흰색 노드와 2개의 검정 노드가 가장 가까운 노드로 선택되며, 흰색 노드의 cost가 검정 노드의 cost보다 적으니 흰색 노드가 우선 선택됨. )
  • d : c에서 선택된 트리 노드는 확장 가능한 확장 집합을 생성하고, 가장 비용이 적은 확장을 확률적으로 선택하여 확장된다. ( 흰색 노드로의 확장 비용이 검정 노드들보다 적기에, 흰색 노드가 다음 트리에 추가될 요소로 선택된다 . )
  • e : start에서 트리를 거쳐 새 요소까지의 경로의 cost와 새 요소에서 goal까지의 휴리스틱 경로 cost가 solution의 하한보다 작다는 것을 확인후에, 해당 요소가 트리에 추가된다.

 

---

3-3. ANYTIME RRT - ( B. Node Selection )

• 앞에서 언급한 방식으로 sample node인 q_target이 생성되었다.
  그러면 이제 트리 내에서 q_target방향으로 확장할 노드 q_tree를 선택한다.
  ( 원래의 RRT 알고리즘은 q_target과 가장 가까운 노드를 선택하지만, Urmson[6]의 연구에서 보듯이, cost를 고려하도록 선택 과정을 수정하면 훨씬 더 낮은 cost의 solution을 얻을수있었다. )
• 저자의 방식은 위의 방법을 기반으로 하여, 시간이 지남에 따라서 cost의 영향력을 변화시키기 위해서 bias 계수를 사용한다.
  • 처음에는 node선택이 오직 q_target과의 거리 비용이 결합된 형태이지만, 나중에는 순수하게 cost에 기반한 선택으로 점진적으로 변화한다.
    이를 위해서 저자는 거리 bias 매개변수(db)와 cost bias 매개변수(cb)를 사용한다.
    • 1. 먼저, q_target에 대해서 트리 내의 k개의 최근접 이웃 노드들을 계산한다.
    • 2. 이후에 k개의 노드들을 아래와 같이 오름차순으로 정렬한다.
      • 아래의 식에서 c( q_start , q )는 q_start에서 q까지의 현재 경로의 cost이다.
      • 이 정렬된 노드들을 순차적으로 처리하여 유효한 확장이 가능한 노드들을 찾는다. ( fig2의 c에서 노드 선택 과정을 나타냄 )
      • 초기에는 db=1 , cb=0으로 설정하여 노드 선택이 단순한 knn과 동일하게 동작한다. 
        • 하지만 각 성공적인 탐색 후에는 db는 δ_d 만큼 감소시키고, cb는 δ_c 만큼 증가시켜 시간이 지남에 따라 트리 노드의 비용이 점점 더 중요한 요소로 작용하도록 만든다.
        • ===> 이에 따른 결과로, 초기에는 유효한 solution을 확보하는데 중점을 두어 비교적 높은 cost의 solution이 만들어진다면, 이후에는 계획에 여유가 있을 경우 cost가 낮아지는 solution으로 개선된다.

3-3의 2의 내용인 k개의 노드들을 오름차순으로 정렬하는 식

 

---

\

식1

3-3. ANYTIME RRT - ( C. Node Extension )

• 트리에서 선택된 노드를 확장할때, 저자는 해당 노드 주변의 configuration space 특성을 고려해서, 새로운 저비용의 트리 branch를 생성합니다. 이를 위해서 2가지 접근 방식을 사용합니다.
  • 1. 트리 노드 q_tree로부터 sample node인 q_target방향으로 일반적인 확장이 이루어질 수 있는 여러 가능한 확장들을 생성합니다. 
    그리고 확장들중에서 cost가 가장 낮은 확장을 선택합니다. 이러한 방식으로 생성한 q_new는 아래의 조건을 만족하면 트리에 추가 됩니다. ( 식 1 참고 )
    • 식1 :  c ( q_start , q_tree ) + c ( q_tree , q_new ) + h ( q_new , q_goal ) <= Cs   
      • 위의 식에서 c( q_start , q_tree )는 q_start에서 q_tree까지의 현재 path cost이며, c ( q_tree , q_new )는 q_tree부터 q_new까지의 방금 생성한 확장 비용입니다.
        • 만약에 q_new가 solution 한계를 만족하지 않는다면, q_target으로 직접적으로 이어지지 않는 다른 확장 집합을 고려합니다.
        • 위의 과정을 q_new가 상한을 만족하는 노드를 생성하거나 최대 시도 횟수에 도달할 때까지 반복합니다.
  • 2.  초기에 확장 가능한 노드들의 집합을 크게 생성하여, 이들중에서 가장 비용이 낮은 확장을 선택하는 방식이다.
    여기에도 역시 q_new가 해 한계를 만족했는지 확인한 후에 트리에 추가한다. ( 그림 2 d 에 설명 )
  • ==> 위의 1번째 방법이 좀 더 빠른 반면에, 2번째 방법을 더 낮은 비용의 해를 산출한다. 두가지 모두 anytime 프레임워크 내에서 유용하다.
  • 첫번째 방법은 초기 단계에서 효율적으로 RRT를 생성하는데 사용되며, 두번째 방법은 후반 단계에서 비용이 낮은 해를 생성하는데 사용된다. ( 또하느 확장 연산에 약간의 무작위성을 포함하는 것도 유익할 수 있으며, 일정 확률로 무작위 확장 연산을 선택하여 해 한계를 비교 할 수 있다. )

 

 

---

그림3 , 4

3-4. ANYTIME RRT ( pseudocode )

• anytime RRT의 접근법에 대한 pseudocode는 그림 3과 4에 나와 있습니다.
  • 너무 복잡하게 표현하는 것을 방지하고자, 앞에서 논의한 모든 기능을 포함하지는 않았습니다.
  • 특히, 실제 구현에서는 표준 RRT를 가지고 초기 해와 경계(bound)를 생성하며, 시간이 지남에 따라서 ExtendToTarget함수가 서로 다른 확장법들 사이들 전환하도록 수정되어 있습니다.
  • 의사코드에서는 UpdateTime( time )은 경과 시간을 증가 시키며, kNearestNeighbors( q_target , k , T )는 트리 T에서 샘플 노드 q_target에 가장 가까운 k개의 노드를 반환하며, GenerateExtensions는 앞에서 말한 방식으로 일련의 확장 연산을 생성하며, 확장들의 끝점에 해당하는 노드들을 반환하고, PostCurrentSolution은 현재 해를 게시하여, 실행해야할 때 실행시킬수 있게 합니다.
  • num-neighbors같은 일반적인 텍스트는 상수이며, db와 같은 기타 텍스트는 앞에서 나온 내용에 따라서 트리 식별자T가 접두사로 붙어서 해당 트리에 속한 변수임을 나타내줍니다.