확률적 로드맵

표본에서 그래프로

구성공간에서 후보 배치를 생성하고 충돌하지 않는 표본을 정점으로 남긴다. 각 정점 주변의 이웃들을 선택한 뒤 간단한 국소 경로로 연결해 본다. 그 경로 전체가 유효하면 간선을 추가한다. 직선 연결은 가능한 국소 방법의 하나이며, 장애물을 스스로 우회하는 복잡한 탐색을 각 연결에서 반드시 수행하는 것은 아니다.

정점이 안전해도 간선은 별개

평면에서 A=(−1,0), B=(1,0)는 원점 중심 반지름 0.5인 금지 원판 밖에 있다. 그러나 선분 AB는 원판을 가로지르므로 간선을 넣을 수 없다. 위쪽의 C=(−1,1), D=(1,1)를 통해 A→C→D→B로 연결하면 각 선분은 원판을 피한다. 표본 위치만 검사하는 구현은 이 구별을 놓치므로 연결 구간 검사가 중요하다.

여러 요청에서 재사용

로드맵을 만든 뒤 새로운 시작점과 목표점을 가까운 정점들에 연결하고 그래프 탐색을 수행한다. 같은 장애물 환경이라면 구축 비용을 여러 요청에 나누어 쓸 수 있다. 다만 로봇 형상이나 장애물이 바뀌면 기존 간선의 유효성을 다시 확인해야 한다. 그래프에서 얻은 짧은 경로가 실제 연속 공간의 최단 경로라는 보장은 없다.

좁은 통로의 어려움

비중이 작은 자유 영역은 표본이 잘 들어가지 않을 수 있다. 독립 균일 표본에서 어떤 영역을 뽑을 확률이 p라면 N회 모두 놓칠 확률은 (1−p)ᴺ이다. p=0.01,N=100이면 약 0.366이다. 이는 단순 표본 예제이며 경로 발견 확률 자체는 아니다. 표본 수와 이웃 연결 규칙, 통로를 겨냥한 표본 전략이 함께 성능에 영향을 준다.