[RRT] A Method of Enhancing Rapidly-Exploring Random Tree Robot Path Planning Using Midpoint Interpolation

A Method of Enhancing Rapidly-Exploring Random Tree Robot Path Planning Using Midpoint Interpolation

A Method of Enhancing Rapidly-Exploring Random Tree Robot Path Planning Using Midpoint Interpolation

 

 

 

Abstract

• sampling-based rapidly-exploring random tree (RRT) 방법으로는 optimality를 보장하기가 어렵다.
• 이 문제를 해결하기 위해, 본 논문은 sampling-based 알고리즘의 planning time을 최소화하고 path length를 단축하기 위한 midpoint interpolation method의 post triangular processing을 제안한다.
• 제안된 방법은 interpolation 과정을 통해 optimal path에 더 가까운 경로를 생성하며, sharp path problem을 어느 정도 해소한다.
• 제안 방법의 성능을 검증하기 위해 실험을 수행하였다.
• 본 논문의 방법을 RRT 알고리즘에 적용하면 planning time을 최소화함으로써 optimization 효율이 향상된다.

 

---

 

1. Introduction

• 최근 로봇을 위한 path planning 연구는 매우 폭넓은 주제를 다루고 있다 [1,2].
• Path planning은 자율 이동 로봇에게 필수적인 능력으로, 로봇이 성공적으로 이동하려면 현재 위치에서 목적지까지의 경로를 찾아낼 수 있어야 한다.
• 이동 로봇은 시작 위치에서 목적지까지 환경 내에서 collision-free이면서 optimal 또는 sub-optimal한 경로를 스스로 발견할 수 있어야 한다 [3].
• Path planning은 유클리드 공간에서 시작점부터 목적지점까지 로봇이 가능한 한 효율적으로 진행하도록 하는 route를 정식화하는 문제이며, 이때 static 및 dynamic obstacles를 회피하면서 optimality, clearance, completeness를 유지해야 한다 [4].
• 여기서 optimal path는 이상적인 path length를 갖는 경로, clear path는 로봇이 장애물과 충돌하지 않는 경로, complete path는 로봇이 시작점에서 목적지까지 장애물과 충돌 없이 실제로 이동할 수 있는 경로를 의미한다.
• 더 나아가 로봇은 시간과 에너지를 절약하기 위해 목적지까지 가장 빠르고 안전한 경로를 선택함으로써 자신의 경로를 최적화할 수 있어야 한다.
• 그러나 최적 경로를 생성하는 알고리즘은 연산량이 증가하고, 빠르게 경로를 생성하는 알고리즘은 optimality를 보장하지 못하는 경향이 있다 [5].
• Sampling-based rapidly-exploring random tree (RRT) 알고리즘으로는 optimality를 보장하기 어렵다 [6].
• Figure 1-a에 보이듯, RRT는 시작점을 루트 노드로 하는 트리에 무작위로 샘플된 위치를 child node로 반복적으로 추가하여 목적지에 도달할 때까지 확장하는 path planning 알고리즘이다.
• Figure 1-b와 같이 트리는 stochastic fractal과 유사한 형태로 뻗어나가며, 목적지 위치를 찾아가는 데 사용된다.
• RRT 및 기타 sampling-based 알고리즘들 [7,8]은 visibility graph[9], cell decomposition[10], potential field 기반 알고리즘들 [11]에 비해 짧은 시간과 적은 계산량으로 경로를 계획할 수 있다는 이점을 제공한다.
• 반면 optimality를 보장하지 못하고, probabilistically assured completeness만을 갖는 단점이 있다.
• 즉, probabilistic completeness[12]란 무작위 샘플의 수가 무한대일 때는 completeness가 보장되지만, 샘플 수가 제한적일 때는 항상 보장되지 않음을 의미한다.
• 이러한 문제를 해결하기 위해 본 논문은 midpoint interpolation method의 post triangular processing을 제안한다.
• 이 방법은 RRT처럼 locally piecewise linear한 형태의 경로를 내놓지만 optimality를 보장하지 않는 path planning 알고리즘들에서 효과적이며, 이들 알고리즘으로 경로가 한 번 계획된 이후에 적용하는 post-processing으로 사용할 수 있다.
• 또한 post-processing 기법이므로 계산 시간에 영향을 주지 않으면서 다양한 route planning 방법에도 적용 가능하다.
• Sampling-based path planning 알고리즘의 주요 강점은 전통적 방법들에 비해 적은 계산량에 기반한 빠른 planning speed이다 [7].
• 본 논문에서는 제안 방법의 성능을 검증하기 위해 다양한 환경에서의 시뮬레이션과 수학적 모델링을 사용하였다.
• 구체적으로, sampling-based path planning 방법에 제안 알고리즘을 적용한 경우와 적용하지 않은 경우를 시뮬레이션으로 비교하며, 시작점에서 목적지점까지 최초로 complete path에 도달할 때의 planning time과 path length를 평가한다.
• 본 논문의 구성은 다음과 같다.
• Section 2에서는 관련 연구를 검토하고, Section 3에서는 제안하는 post triangular processing of the midpoint interpolation method를 소개한다.
• Section 4에서는 path planning의 다양한 실험 환경을 구성하여 제안 방법의 효과와 개선 사항을 검토한다. 마지막으로 결론을 제시한다.

---

 

3. Proposed Post Triangular Processing of the Midpoint Interpolation Method

• 제안하는 midpoint interpolation method의 post triangular processing은 RRT처럼 optimality를 보장하지 않는 경로 계획 알고리즘들에 적용할 수 있으며, triangular inequality 원리에 기반한 rewiring과 midpoint interpolation을 이용한다.

 

가정(Assumptions)과 기본 원리

 

• 목적지점(destination point)은 시간이 지남에 따라 점진적으로 변할 수 있으나,
  각 트리에는 시작점과 목적지점이 각각 하나만 존재한다.
• 로봇이 omnidirectional motion을 수행할 수 없다면, 경로 계획 결과 위에서 local planning 또는 kinodynamic planning을 별도로 수행한다.

 

기본 원리:

• 계획된 경로의 각 waypoint는 자신의 grandparent node와의 연결이 장애물과 충돌하는지 확인한다.
  • 충돌이 없으면 grandparent → parent로 rewire한다(postTriangular).
• 충돌이 있으면, Figure 3처럼 node–parent–grandparent가 만드는 locally piecewise linear 경로 구간을 interpolation으로 더 최적에 가깝게 만든다.
• 이 과정에서 경로 상에 새 노드가 보간되어 조각선에서 벗어나므로, 기구학적 제약으로 경사가 매끄럽지 않아 생기는 sharp path problem을 어느 정도 완화한다.

 

ε(최소 여유거리 임계값)과 d의 정의

• 이 post 처리법은 polygon approximation 알고리즘 아이디어를 바탕으로 설계되었고(Figure 4), **ε(최소 clearance 임계값, ε>0)**이라는 상수를 통해 경로가 장애물에 얼마나 가깝게 근사되는지—다시 말해 optimal path에 얼마나 가까운지—를 결정한다.
• 식 (1)에서 d는 다음과 같이 정의된다.