[AD] PRM(Probabilistic Road-Map) 알고리즘 설명

Author: Joonhee Lim
Date: 2022/09/13

출처: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=508439

https://theclassytim.medium.com/robotic-path-planning-prm-prm-b4c64b1f5acb

Paper: DTED 맵에서 무인기 경로 생성을 위한 Probabilistic RoadMap 병렬화

---

0. Motivation

...

---

1. PRM?

PRM 알고리즘은 다음 그림과 같이 구성 공간에서 임의의 샘플링을 통해 노드를 생성하고 노드 간의 지역적 관계를 확인하고 연결하여 하나의 Roadmap 그래프를 생성하는 방식을 사용한다. 이후 시작점과 목표점을 추가하여 최종적으로 두 지점 간을 연결하는 경로를 탐색한다.

 

PRM 알고리즘은 크게 구성 단계와 쿼리 단계로 이뤄진다.

 

구성 단계는 구성공간을 장애물 영역과 비장애물 영역으로 구분한다. 다음으로 구성공간 내에서 정해진 수만큼 임의의 샘플링을 진행하고 샘플링 된 노드 중 장애물 영역에 포함된 노드를 제거한다.

남은 노드들 각각을 이웃 노드 선택 조건(일정 거리 이내에 포함되는 노드들 혹은 k개의 가까운 노드들을 선택)에 따라 노드 간에 장애물이 없다면 연결한다. 이러한 방식을 통해 구성공간을 채우는 Roadmap을 생성한다.

 

쿼리 단계에서는 생성된 로드맵 그래프에 시작점과 목표점을 포함하여 Dijkstra, A*  등 알고리즘을 활용하여 최단 경로를 탐색한다. PRM 알고리즘은 샘플링되는 노드의 개수가 무한대로 수렴할수록 경로를 찾지 못할 확률이 0으로 수렴한다. 그러나 알고리즘의 계산 시간 및 계산량의 한계로 인해 노드를 무한정으로 샘플링 할 수 없다. 샘플링되는 노드가 많아지면 더 나은 경로를 생성할 가능성이 증가하지만, 노드 간의 연결 관계 확인을 위한 장애물을 확인하는 계산이 많아지고 연결되는 노드 수가 많아짐에 따라 저장 데이터가 커지는 단점이 있다.