빠르게 탐색되는 랜덤 트리

Rapidly-exploring random tree
다음에 대한 시리즈 일부
확률론적
데이터 구조
랜덤 트리
관련
45회 및 390회 반복 후 RRT 그래프의 시각화
반복 0부터 10000까지의 RRT 애니메이션

빠르게 탐사하는 RRT(Random Tree, RRT)는 공간을 채우는 나무를 무작위로 만들어 비콘벡스, 고차원 공간을 효율적으로 탐색하도록 설계된 알고리즘이다.트리는 검색 공간에서 무작위로 추출한 샘플로부터 점진적으로 생성되며, 본질적으로 문제의 큰 미장착 영역으로 성장하도록 편중되어 있다.RRTs는 Steven M. LaValle과 James J. Kuffner Jr.에 의해 개발되었다.[1][2]장애물과 차등 제약(비혼합성과 운동역학)의 문제를 쉽게 다루며, 자율 로봇 모션 계획에 널리 이용되어 왔다.

RRT는 상태 제약이 있는 비선형 시스템에 대해 개방 루프 궤적을 생성하는 기법으로 볼 수 있다.RRT는 또한 구성 공간에서 그래프의 가장 큰 보로노이 영역으로 치우쳐 검색하는 몬테카를로 방법으로도 간주될 수 있다.어떤 변화들은 확률적 프랙탈로 간주될 수도 있다.[3]

RRT는 상태 및 작용 제약이 있는 고차원 비선형 시스템을 제어하기 위한 대략적인 제어 정책을 계산하는 데 사용될 수 있다.

설명

RRT는 검색 공간에서 무작위 샘플을 사용하여 시작 구성에 뿌리를 둔 트리를 성장시킨다.각 샘플이 그려질 때, 샘플과 트리에서 가장 가까운 상태 사이의 연결이 시도된다.연결이 가능한 경우(전체적으로 여유 공간을 통과하고 제약 조건을 준수함) 트리에 새 상태를 추가하게 된다.검색 공간의 균일한 샘플링으로 기존 주를 확장할 확률은 보로노이 지역의 크기에 비례한다.가장 큰 보로노이 지역은 수색이 진행 중인 주(州)에 속하기 때문에 나무가 우거지지 않은 넓은 지역으로 우선 확대되는 것을 의미한다.

트리와 새로운 상태 사이의 연결 길이는 종종 성장 인자에 의해 제한된다.무작위 표본이 이 한계가 허용하는 것보다 나무에서 가장 가까운 상태로부터 더 멀리 떨어져 있는 경우, 선을 따라 나무에서 무작위 표본에 이르는 최대 거리의 새로운 상태가 무작위 표본 자체 대신에 사용된다.그런 다음 무작위 표본은 성장 인자가 나무의 성장 방향을 결정하는 것으로 볼 수 있다.이것은 RRT의 공간을 채우는 편향성을 유지하면서 증분 성장의 크기를 제한한다.

RRT 성장은 특정 영역에서 샘플링 상태의 확률을 증가시킴으로써 편향될 수 있다.대부분의 RRT 실행은 이를 이용하여 계획 문제 목표를 향한 검색을 안내한다.이것은 주 표본 추출 절차에 목표를 표본 추출할 수 있는 작은 확률을 도입함으로써 달성된다.이 확률이 높을수록 목표를 향해 탐욕스럽게 나무가 자라난다.

알고리즘.

일반 구성 공간 C의 경우 가성코드 알고리즘은 다음과 같다.

Algorithm BuildRRT     Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq     Output: RRT graph G G.init(qinit)     for k = 1 to K do qrand ← RAND_CONF()         qnear ← NEAREST_VERTEX(qrand, G)         qnew ← NEW_CONF(qnear, qrand, Δq)         G.add_vertex(qnew)         G.add_edge(qnear, qnew)     return G
  • "직접"은 할당을 의미한다.예를 들어, "가장 큰 ←항목"은 가장 큰 값이 항목의 가치를 변화시킨다는 것을 의미한다.
  • "return"은 알고리즘을 종료하고 다음 값을 출력한다.

위의 알고리즘에서 "RAND_CONF"는 C에서 임의의 구성 q를rand 잡는다.이것은 일부 충돌 검출 알고리즘을 사용하여 C의obs 표본을 거부하는 동시에 C의free 표본을 사용하는 "RAND_FREE_CONF" 함수로 대체될 수 있다.

"NEESTERY_VERTEX"는 그래프 G의 모든 정점을 통과하여 일부 측정 기능을 사용하여 q와rand v 사이의 거리를 계산하여 가장 가까운 정점을 반환하는 함수다.

"NEW_CONF"는 q에서near Δq의 증분rand 거리를 q의 방향으로 이동하여new 새로운 구성 q를 선택한다(홀로노믹스 문제에 따라 qnew 대신 q를rand 사용해야 함).

모션 계획을 위한 변형 및 개선 사항

  • RRT-Roe는 개방형 및 대규모 환경에서 매우 효과적인 결정론적 단축 접근방식을 사용하여 신속하게 최적에 가까운 경로 계획을 위한 방법이다.[5]
  • Parti-game 디렉티드 RRTs(PDRRTs)는 RRT를 Parti-game 방법과 결합하여[7] 필요한 위치(예를 들어 장애물 주변)를 정밀하게 하여 RRT보다 더 빠른 계획을 세우고 더 많은 모션 계획 문제를 해결할 수 있도록 하는 방법이다.[6]
  • 차량과 컨트롤러로 구성된 안정적인 폐쇄 루프 시스템에 대한 입력을 샘플링하는 RRT의 확장인 폐쇄 루프 고속 탐상 랜덤(CL-RRT)[8]

'mild 기술 조건'에서는 RRT에서 최선의 경로에 대한 비용이 거의 확실히 최적치가 아닌 값으로 수렴되는 것으로 나타났다.[9]그러한 이유로 RRT*처럼 최적으로 수렴되는 RRT의 변형을 찾는 것이 바람직하다. 다음은 RRT* 기반 방법 목록(RRT* 자체부터 시작)이다.그러나 모든 파생된 방법들이 그 자체로 최적의 상태로 수렴되는 것은 아니다.

  • RRT의 변종인 RRG(Random Graph)와 RRT*[9][10][11]가 최적의 솔루션으로 수렴됨
  • RRT+ 기반 설계자 제품군인 RRT는 저차원 서브스페이스에서 점진적으로 검색하여 고차원 시스템 솔루션을 실시간으로 생성하는 것을 목표로 한다.
  • RRT*-Smart,[13] 경로 최적화(Teta*와 유사한 방식으로) 및 지능형 샘플링(경로 최적화 후 장애물에 가까울 가능성이 높은 경로 정점을 향해 샘플링을 편중시킴)을 사용하여 RRT*의 수렴 속도를 가속화하는 방법
  • 는 초기 실현 가능한 방향에 대한low-dimensional 우주에 첫번째 단계에(완전한 상태 공간을 고려하지 않)검색하고 선호 위험한 지역, 그리고 그것은 연속 high-dimen의 RRT* 찾고자 초점을 두고 있는 데 사용됩니다 위험이 낮은 노선을 면하기 그래프 탐색 알고리즘을 사용합니다 A*-RRT과 A*-RRT*,[14]두 단계 운동 계획 방법.sion2단계의 공간
  • RRT*FN,[15][16][17] RRT* 고정된 노드 수를 가진 RRT*FN, RRT* 모든 반복에서 트리의 리프 노드를 임의로 제거
  • RRT*-AR,[18] 샘플링 기반 대체 경로 계획
  • 지식 RRT*,[19][20] A*가 Dijkstra 알고리즘에서 향상되는 방식과 유사한 휴리스틱스를 도입하여 RRT*의 수렴 속도를 개선한다.
  • RRT*의 변형인 Real-T-RRT*(RT-RRT*)[21]는 컴퓨터 게임과 같은 동적 환경에서 실시간 경로 계획을 얻기 위해 이전에 샘플링된 경로를 폐기하지 않고 트리 루트가 에이전트와 함께 이동할 수 있는 온라인 트리 리와이어링 전략을 사용하는 RRT*에 대해 알려주었다.
  • RRTX 및 RRT#,[22][23] 동적 환경을 위한 RRT* 최적화
  • Teta*-RRT는 A*-RRT*와 유사한 2상 모션 계획법으로,[24] 복잡한 비혼합성 제약이 있는 환경에서 빠른 궤적 생성을 위해 RRT 모션 계획과 함께 임의각도 검색의 계층적 조합을 사용한다.
  • RRT* FND,[25] 동적 환경을 위한 RRT* 확장
  • RRT-GPU,[26] 하드웨어 가속을 활용하는 3차원 RRT 구현
  • APF-RT,[27] RRT 플래너와 인공 잠재 필드 방법을 조합하여 재생 작업을 단순화함
  • CERRT,[28] RRT 플래너 모델링 불확실성, 접점 활용 감소
  • MVRRT*,[29] 최소 위반 RRT*, 안전하지 않은 정도를 최소화하는 최단 경로를 찾는 알고리즘(예: 교통법규를 위반한 환경 규칙의 "비용")
  • RRT-Blossom,[30] 매우 제한된 환경을 위한 RRT 플래너.
  • TB-RT,[31] 두 동적 시스템의 랑데부 계획을 위한 시간 기반 RRT 알고리즘.
  • 여러 개의 로컬 트리를 사용하여 로컬 샘플링을 수행하여 공간의 탐색과 착취의 균형을 적극적으로 유지하는 RRT* 기반 플래너 RRdT*.[32][33]

참고 항목

참조

  1. ^ LaValle, Steven M. (October 1998). "Rapidly-exploring random trees: A new tool for path planning" (PDF). Technical Report. Computer Science Department, Iowa State University (TR 98–11).
  2. ^ LaValle, Steven M.; Kuffner Jr., James J. (2001). "Randomized Kinodynamic Planning" (PDF). The International Journal of Robotics Research (IJRR). 20 (5): 378–400. doi:10.1177/02783640122067453. S2CID 40479452.
  3. ^ http://msl.cs.uiuc.edu/rrt/about.html RRTs 소개: Steve LaValle
  4. ^ 빠르게 탐구하는 랜덤 트리: Steven M. Lavalle , James J. Kuffner , Jr.의 진행과 전망(2000년)알고리즘 및 컴퓨터 로보틱스:새로운 지침, http://eprints.kfupm.edu.sa/60786/1/60786.pdf[permanent dead link]
  5. ^ Petit, Louis; Desbiens, Alexis Lussier (2021-10-17). "RRT-Rope: A deterministic shortening approach for fast near-optimal path planning in large-scale uncluttered 3D environments". 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC). Melbourne, Australia: IEEE: 1111–1118. doi:10.1109/SMC52423.2021.9659071. ISBN 978-1-6654-4207-7.
  6. ^ 랑가나단 자손과 아난스 자손과 코에니그 자손과 스벤 자손이다.PDRT: "그래프 기반 및 셀 기반 계획 통합"IEEE 지능형 로봇 및 시스템에 관한 국제 회의(IROS)의 절차에서, 2004년 페이지 2799–2808.
  7. ^ 무어, A. W.; Atkeson, C. G., "다차원 상태 공간에서 가변 분해능 강화 학습을 위한 파트-게임 알고리즘," 기계 학습, 제 21권, 제 3호, 페이지 199–233, 1995.
  8. ^ Kuwata, Yoshiaki; Teo, Justin; Fiore, Gaston; Karaman, Sertac; Frazzoli, Emilio; How, Jonathan P. (September 2009). "Real-time Motion Planning with Applications to Autonomous Urban Driving" (PDF). IEEE Transactions on Control Systems Technology. 17 (5): 1105–1118. CiteSeerX 10.1.1.169.7922. doi:10.1109/tcst.2008.2012116. hdl:1721.1/52527. S2CID 14526513. Retrieved 10 April 2017.
  9. ^ a b Karaman, Sertac; Frazzoli, Emilio (3 May 2010). "Incremental Sampling-based Algorithms for Optimal Motion Planning". arXiv:1005.0416 [cs.RO].
  10. ^ Karaman, Sertac; Frazzoli, Emilio (5 May 2011). "Sampling-based Algorithms for Optimal Motion Planning". arXiv:1105.1186 [cs.RO].
  11. ^ OlzhasAdi (Jan 26, 2015). "RRT* Brief Explanation" (video). YouTube. Archived from the original on 2021-12-12. Retrieved 3 August 2016.
  12. ^ Xanthidis, Marios; Esposito, Joel M.; Rekleitis, Ioannis; O’Kane, Jason M. (2020-12-01). "Motion Planning by Sampling in Subspaces of Progressively Increasing Dimension". Journal of Intelligent & Robotic Systems. 100 (3): 777–789. doi:10.1007/s10846-020-01217-w. ISSN 1573-0409.
  13. ^ Islam, Fahad; Nasir, Jauwairia; Malik, Usman; Ayaz, Yasar; Hasan, Osman; "RRT*-Smart: Rapid convergence implementation of RRT* towards optimal solution", in Proceedings of IEEE International Conference on Mechatronics and Automation (ICMA), pages 1651–1656, Chengdu, China, August 2012.
  14. ^ 브런너, 브뤼게만, B, 슐츠, D..Int에서 "최적 샘플링 기반 방법을 이용한 상층적인 거친 지형 운동 계획". 2013년 독일 칼스루헤 로봇공학 및 자동화 관련 컨퍼런스.
  15. ^ 아디야토브와 올즈하스와 바롤과 후세인 아타칸이다."급격한 임의 트리 기반 메모리 효율적인 모션 계획"메카트로닉스 및 자동화(ICMA), 2013 IEEE 국제 컨퍼런스 페이지 354–359, 2013. doi:10.1109/ICMA.2013.6617944
  16. ^ Adiyatov, Olzhas; Varol, Atakan (2013). "MATLAB Toolbox of RRT, RRT* and RRT*FN algorithms". Retrieved 3 August 2016.
  17. ^ OlzhasAdi (Jan 26, 2015). "RRT*FN Brief Explanation" (video). YouTube. Archived from the original on 2021-12-12. Retrieved 3 August 2016.
  18. ^ 산지반의 Choudhury; Scherer, Sebastian; Singh, Sanjiv. "RT*-AR: 헬리콥터의 자동 비상 착륙에 대한 응용을 통한 샘플링 기반 대체 경로 계획".ICRA(로보틱스 및 자동화)에서 2013 IEEE 국제회의 on Karlsruhe, 2013년 5월 6–10페이지, 3947–3952. doi:10.1109/ICRA.2013.6631133
  19. ^ Gammell, Jonathan D.; Srinivasa, Siddhartha S.; Barfoot, Timothy D. (8 Apr 2014). Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic. 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 2997–3004. arXiv:1404.2334. doi:10.1109/IROS.2014.6942976. ISBN 978-1-4799-6934-0. S2CID 12233239.
  20. ^ utiasASRL (Jul 4, 2014). "Informed RRT* @ UTIAS (IROS 2014)" (video). YouTube. Archived from the original on 2021-12-12. Retrieved 3 August 2016.
  21. ^ 나데리, 쿠로시, 라자매키, 주세, 헤멜레이넨, 퍼투(2015년)."RT-RT*: RRT* 기반 실시간 경로 계획 알고리즘."제8회 ACM SIGRAPH 컨퍼런스 진행 중 (MIG '15)ACM, 뉴욕, 뉴욕, 미국, 113–118. 도이:10.1145/2822013.282036
  22. ^ RRTX: 예측 불가능한 장애물이 있는 환경을 위한 실시간 모션 계획/복제
  23. ^ 정적 환경에서 바로 가기가 발견될 때 RRTX, RRT# 및 RRT* 비교
  24. ^ Palmieri, Luigi, Koenig, Sven, Arras, Kai O. "Any-Angle Path Biasing을 이용한 RRT 기반 비혼합성 운동 계획"로봇공학 및 자동화(ICRA), 2016년 IEEE 국제 컨퍼런스의 절차 2775-2781, 2016페이지.
  25. ^ RRT* FND - 동적 환경에서 동작 계획
  26. ^ Ford, Christen (2018-06-12). RRT-GPU and Minecraft: Hardware Accelerated Rapidly Exploring Random Trees in Three Dimensions (Thesis). doi:10.13140/rg.2.2.15658.11207.
  27. ^ Amiryan, Javad; Jamzad, Mansour (2015). Adaptive motion planning with artificial potential fields using a prior path. Robotics and Mechatronics (ICROM), 2015 3rd RSI International Conference on. pp. 731–736.
  28. ^ Sieverling, Arne; Eppner, Clemens; Wolff, Felix; Brock, Oliver (2017). Interleaving motion in contact and in free space for planning under uncertainty (PDF). 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4011–4073.
  29. ^ Rus, Daniela; Frazzoli, Emilio; Karaman, Sertac; Tumova, Jana; Chaudhari, Pratik; Castro, Luis I. Reyes (2013-05-06). "Incremental Sampling-based Algorithm for Minimum-violation Motion Planning". arXiv:1305.1102 [cs.RO].
  30. ^ "Maciej Kalisiak - RRT-blossom". www.dgp.toronto.edu. Retrieved 2020-01-18.
  31. ^ Sintov, Avishai; Shapiro, Amir (2014). Time-based RRT algorithm for rendezvous planning of two dynamic systems. IEEE International Conference on Robotics and Automation (ICRA). doi:10.1109/ICRA.2014.6907855.
  32. ^ Lai, Tin; Ramos, Fabio; Francis, Gilad (2019). "Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees". 2019 International Conference on Robotics and Automation (ICRA). Montreal, QC, Canada: IEEE: 5537–5543. arXiv:1810.03749. doi:10.1109/ICRA.2019.8793618. ISBN 978-1-5386-6027-0. S2CID 52945105.
  33. ^ Lai, Tin; Morere, Philippe; Ramos, Fabio; Francis, Gilad (April 2020). "Bayesian Local Sampling-Based Planning". IEEE Robotics and Automation Letters. 5 (2): 1954–1961. arXiv:1909.03452. doi:10.1109/LRA.2020.2969145. S2CID 210838739.

외부 링크