RRT 경로 생성 알고리즘

고속도로나 자동차 전용도로에서 차로변경, 조향, 가감속, 차간거리 차선유지등의 기능을 수행하기위해서 매순간 정확한 경로생성이 필요하다.

대표적인 경로생성 알고리즘 = RRT*, RRT, A star, Dijkstra, Aritificial Potential Field 등등

 

https://github.com/mkyun2/RRT_Algorithm

GitHub - mkyun2/RRT_Algorithm: Rapidly Exploring Random Tree

개념

무작위 샘플링(Random Sampling)을 사용하여 고차원 공간을 탐색하는 알고리즘

원리

시작지점에서 목적지점으로 도달할 때까지 랜덤포인트를 계속적으로 생성하고 가까이 있는 노드와 연결지으며 확장하여 탐색하는 기술

 

초기 지점을 start로 하고 난수를 이용해 랜덤한 좌표를 지닌 노드를 생성하고 이미 생성되어진 노드들중에 가장 가까이 위치한 노드를 찾는다.

random sample 가장 가까이 위치한 노드와의 직선위에 새로운 점 new를 만드는데 이때 상수 a만큼 떨어진 위치에 생성한하고 가까이 위치한 노드를 부모노드로 한다. (가까이 위치한 노드의 상대적 거리, 각도를 알수있으니 가능하다)  

이때 해당 직선이 어떤 장애물과 겹쳐지면 안된다. (충돌방지)

이후 위 과정을 goal 지점 혹은 goal 노드와 연결될때까지 반복해나간다. 

 

 

결과