확률적로드맵 (Probabilistic Roadmap (PRM))
쉽게 풀면
미리 여러 지점을 점으로 찍고 서로 연결해서 지도(로드맵)를 만들어 놓은 다음, 그 지도 위에서 길을 찾는 방법이에요.
왜 중요한가
형상공간에서 무작위 표본을 뽑아 충돌 없는 것들을 이웃과 연결해 그래프를 미리 만들어 두고, 이후 질의마다 그래프 탐색만으로 경로를 찾는 방법입니다. 같은 환경에서 여러 번 계획해야 하는 고정 셀의 로봇팔이나 창고 로봇에 유리해 모션 계획의 두 축 중 하나로 자리 잡았습니다.
논문에서는 이렇게 쓰입니다
논문에서 확률적로드맵은 정적인 환경에서 여러 시작-목표 쌍에 대한 경로계획을 재사용할 수 있는 방법으로 RRT와 대비되어 소개됩니다.
확률적로드맵 (Probabilistic Roadmap (PRM))이 개별 논문 하나에 국한되지 않고 로봇공학 분야 전반의 연구에서 공통적으로 참조되는 개념임을 보여주는 예이다.
조금 더 깊게 보면
그래프 구축 비용을 여러 질의에 나누어 갚는 다중 질의 방식이므로, 환경이 바뀌면 그래프를 다시 만들어야 하고 단일 질의에는 RRT가 더 빠릅니다. 좁은 통로에는 표본이 거의 떨어지지 않아 연결이 끊기는 협통로 문제가 본질적 약점이며, 확률적 완전성만 보장하므로 경로가 없다는 판정은 원리적으로 내릴 수 없습니다. 로드맵 구축 단계에서는 형상공간에 무작위 표본을 뿌린 뒤 각 표본이 충돌 없는 상태인지 검사하고, 통과한 표본들을 근처 이웃과 직선(또는 국소 경로)으로 연결해 그 연결선도 충돌이 없는지 확인하는 과정을 반복한다. 좁은 통로처럼 자유공간이 얇은 영역에서는 무작위 표본이 좀처럼 그 안에 떨어지지 않아 로드맵이 끊기는 협통로 문제가 있어, 좁은 영역을 감지해 표본을 집중시키는 편향 샘플링 기법이 함께 연구된다.
주의할 점
확률적로드맵은 환경이 변하면(동적 장애물 등) 로드맵을 다시 구축해야 하므로 정적 환경에 더 적합하다.
확률적로드맵은 완전성이 아닌 확률적 완전성만 보장하므로, 실제로 경로가 존재하더라도 표본 수가 부족하면 찾지 못할 수 있고 경로가 없다고 단정할 수도 없다.