A*알고리즘과 RRT, RRT* 알고리즘

A* 알고리즘 

A* 알고리즘은 경로가 그려질 수 있는 공간에 대하여 2D Grid를 그리고 해당 그리드 맵 상에서 최단 경로를 탐색 및 결정하는 알고리즘이다. 2차원 그리드를 그림으로써 현재 위치로부터 8방향에 대하여 각각 Cost를 계산한다. Cost 값을 기준으로 목표지점까지의 최적 경로를 찾을 수 있다. 이때, 그리드는 장애물 유무에 따라 0 또는 1로 채워지며, 1이면 장애물이 있어 진행하지 못하는 그리드, 0이면 그리드가 비어 있어 진행이 가능한 그리드임을 의미한다. 각 그리드에 채워진 0 또는 1 값으로 Cost를 계산할 수 있다.

 

또한 주변 8방향에 대하여 Cost를 계산하고 최단거리를 탐색하는 기법은 트리구조를 활용하여 구현할 수 있다. 이러한 A 알고리즘은 그리드의 크기를 어떻게 설정하느냐에 따라서 결과값이 달라진다. 그리드의 크기가 작으면 경로가 좀 더 섬세해지나, 계산량이 많아진다는 단점이 있다. 그리드 크기가 크면 계산량이 적어 연산속도는 빨라질 수 있으나, 세밀한 장애물 회피 경로가 생성되기 어렵다는 단점이 존재한다. 이에 따라, 환경 정보와 자차의 크기를 고려하여 그리드의 크기를 적절히 선정해야 한다.

 

728x90

 

RRT 알고리즘 

RRT 알고리즘은 무작위 샘플링을 활용하여 고차원의 구성 공간을 탐색하는 알고리즘이다. 시작지점에서 목표지점으로 도달할 때까지 랜덤 포인트를 연속적으로 생성 하고 해당 랜덤 포인트로 확장하여 탐색하는 경로 생성 알고리즘이다. 랜덤 포인트를 뿌려 탐색 공간에 대한 경로 후보들을 확보하고 기존의 트리에서 가장 가까운 포인트와 랜덤 포인트를 연결하여 트리를 갱신한다. 이때 랜덤 포인트를 뿌리는 방식은 균등 분포 방식을 변형하여 이동체 특성에 맞는 방식을 채택할 수 있다. 예를 들어 차량은 종방향 이동이 주를 이루므로 타원 분포 방식을 고려할 수 있다. RRT 알고리즘에서, 확장하는 트리가 목적지에 도착하면 목적지로부터 시작점까지 트리를 재귀적으로 검색하게 된다. 이를 통해 실시간으로 경로를 선택할 수 있다.

 

RRT와 RRT* 알고리즘 간의 차이 

RRT 알고리즘은 샘플링 방식으로 구현이 용이하나, 최적의 랜덤 샘플링이 이뤄지지 않으면 해당 경로가 최적이라는 보장이 불가하다는 단점이 있다. 이러한 RRT 알고리즘으로부터 발전되어 도입된 알고리즘은 RRT* 알고리즘이다. 기존의 RRT 알고리즘은 트리에 각 노드를 추가한 뒤 재귀적으로 탐색하는 방식이었다면 RRT*알고리즘은 랜덤 샘플링 뒤, cost가 더 적은 path를 구하기 위하여 부모 노드를 최적화 한다는 차이가 있다. 랜덤 포인트의 주변 노드들을 탐색하여 이웃 노드 간의 연결을 최적화하고 최적의 부모 노드를 선정함으로써 기존의 RRT 알고리즘보다 더욱 효율적인 계산이 가능하도록 한다. 이것이 RRT와 RRT* 알고리즘의 차이이다.

 

본 게시물은 필자가 작성한 다음의 게시글을 이관하였습니다: A*알고리즘과 RRT(*) 알고리즘 (velog.io)