모든 공간을 격자로 채우지 않고 필요한 점을 고른다
높은 차원의 configuration 공간을 일정한 격자로 채우면 후보 수가 빠르게 커진다. PRM은 Probabilistic Roadmap의 약자로, 공간에서 여러 configuration을 샘플로 고르고 유효한 점과 연결을 그래프로 만드는 접근이다. sampling은 어떤 분포나 규칙에 따라 후보를 뽑는 일이다. 자유 공간의 모양을 전부 식으로 만들기보다 충돌 검사기에 필요한 질문을 하면서 근사 로드맵을 구성한다.
기본 절차는 후보 configuration을 뽑고, 충돌하지 않는 것을 node로 남기고, 가까운 이웃과의 짧은 경로를 검사해 간선을 넣는 것이다. local planner는 두 configuration 사이를 연결할 후보 경로를 만드는 국소 연결기다. 이름에 planner가 있어도 기본 직선 연결기가 장애물을 알아서 우회하는 것은 아니다. 충돌 검사를 통과한 연결만 유효 간선으로 승인한다.
이후 query는 주어진 시작과 목표를 로드맵에 연결하고 그래프 탐색으로 경로를 찾는 질의다. Modern Robotics 저자 PRM 설명은 미리 만든 로드맵을 여러 시작·목표 질의에 쓰는 구조를 보여 준다. 시작과 목표가 충돌하지 않는지, 로드맵의 다른 점까지 연결할 수 있는지 먼저 확인해야 한다. 지도 그림 위의 점을 선으로 이어 그렸다는 사실이 유효 경로를 뜻하지 않는다.
가까운 이웃도 연결할 수 있는지는 따로 확인한다
이 단위는 이미 로봇 형상을 반영한 2D C-space에서 점 로봇을 사용한다. 좌표 단위는 m이고 정적 장애물은 닫힌 사각형 0.8≤x≤1.2, −0.2≤y≤0.8이다. 경계 접촉도 충돌로 정한다. 이는 실제 로봇의 장착물이나 오차를 추정한 자료가 아니라 제공한 합성 모델이다. 회전과 차량 운동 제약도 포함하지 않는다.
그림 M17.03-1. 각 칸은 서로 다른 역할/근거다. 아래 방향은 자료/처리의 연결이며 실제 성공을 자동으로 보장하지 않는다. 직접 제작한 개념도이며 본문의 조건과 함께 읽는다.
시작 S=(0,0), 샘플 A=(0,1), B=(2,1), 목표 G=(2,0) m를 제공한다. 네 점은 모두 장애물 밖이다. 거리는 유클리드 거리이며 이웃 규칙은 두 점의 거리가 반경 ρ 이하일 때 모든 쌍을 후보로 만드는 것이다. 간선은 양방향 직선 구간이고 비용은 그 길이(m)다. 임의로 보이지 않는 추가 간선을 가정하지 않는다.
ρ=2.1 m이면 S-A와 B-G의 거리는 각각 1 m이고 A-B와 S-G는 각각 2 m다. 대각선 S-B와 A-G는 √5≈2.236 m여서 후보가 아니다. 네 후보 중 S-G는 y=0에서 사각 장애물을 관통하므로 제거한다. A-B는 y=1로 장애물 위를 지나며 최소 수직 간격 0.2 m가 있어 유효하다. S-A와 B-G도 각각 x=0과 x=2에서 유효하다. 따라서 S-A-B-G가 연결되고 길이는 1+2+1=4 m다.
샘플이 모두 자유 공간에 있어도 ρ=1.5 m로 줄이면 A-B가 너무 멀어 후보에서 빠진다. S-A와 B-G 두 조각만 남아 그래프가 끊긴다. 공간에 우회가 없어진 것이 아니라 연결 규칙과 현재 샘플로 그 우회를 표현하지 못한 것이다. 'PRM 실패'를 실제 경로 부재의 증명으로 쓰면 안 되는 이유다.
그림 M17.03-2. 별도 평면 점 configuration 개념도다. 자유 노드라도 그 사이 간선이 장애물과 충돌할 수 있다. 회색은 이미 로봇 크기를 반영했다고 가정한 금지 영역이며 본문 수치 입력을 대체하지 않는다. 직접 제작.
샘플을 어디에 더하는지가 중요하다
작은 반경 1.5 m를 유지하면서 C=(1,1) m를 추가하자. A-C와 C-B는 각각 1 m이고 y=1에서 유효하다. S-C와 G-C는 각각 √2≈1.414 m라 이웃 후보에 들어오지만, 전자는 장애물 모서리 (0.8,0.8), 후자는 (1.2,0.8)에 닿으므로 무효다. 새 경로는 S-A-C-B-G이며 길이는 다시 4 m다. 새 점 하나가 끊어진 두 조각 사이의 연결을 표현하게 했다.
이 사례는 점 개수만큼이나 위치와 간선 검사가 중요하다는 뜻이다. 같은 구석에 샘플을 여러 개 추가해도 좁은 통로와 먼 연결을 놓칠 수 있다. 무작위 샘플링은 특정 표본 집합을 보장하지 않으며 난수 seed를 기록해 재현할 수 있게 해도 모든 환경에서 성공하는 것은 아니다. 균일 분포 외에 장애물 경계나 좁은 통로를 더 찾는 전략도 있지만 어떤 영역을 거의 뽑지 않게 만들었는지 확인해야 한다.
관절 공간에서는 '가깝다'의 정의도 중요하다. 회전각의 0과 2π가 같은 방향인지 관절 제한으로 떨어져 있는지, m와 rad를 어떤 척도로 비교하는지에 따라 이웃이 바뀐다. 이 단위의 거리 공식은 같은 단위의 평면 좌표 두 개에 한정한다. 좌표마다 큰 숫자를 가진 성분이 무조건 거리를 지배하도록 두는 것은 의도한 기구학적 가까움과 다를 수 있다.
확률은 표본이 늘 때의 성질이지 유한 실행의 약속이 아니다
한 번의 독립 샘플이 중요한 자유 영역에 들어갈 확률을 합성 가정으로 p=0.1이라고 주자. N번 모두 빗나갈 확률은 (1−p)^N이고 적어도 한 번 들어갈 확률은 다음과 같다.
N=10이면 1−0.9^10≈0.6513, N=20이면 약 0.8784다. 표본을 늘려 가능성은 커지지만 20번이면 반드시 성공한다는 뜻은 아니다. 더구나 이 계산은 한 영역에 점이 하나 들어갈 확률이지 전체 경로를 연결할 확률이 아니다. 시작·목표 연결과 다른 영역의 표본, 간선 유효성도 필요하다. p는 이 지도에서 실측한 통로 면적비가 아니라 제공한 확률 모델이다.
확률적 완전성은 적절한 조건에서 표본 수가 무한히 늘면 존재하는 해를 놓칠 확률이 0으로 간다는 성질이다. 샘플 분포가 필요한 자유 영역을 계속 뽑을 가능성이 있고, 양의 여유를 가진 경로와 적절한 국소 연결·검사 규칙 등이 필요하다. 폭이 0인 접촉 경로를 유한 확률로 샘플한다고 기대하지 않는다. 정해진 시간 안에 성공하거나 경로 부재를 증명한다는 의미도 아니다.
PRM*, Lazy와 재사용의 계약을 구분한다
Karaman과 Frazzoli 원논문은 해를 찾는 성질과 해 비용이 최적에 수렴하는 성질을 구분한다. PRM*는 표본 수에 맞는 이웃 연결 규칙 등 조건 아래 점근 최적성을 갖도록 만든 변형이다. 점근 최적은 표본이 늘며 비용이 최적에 수렴한다는 뜻이며 지금 반환한 유한 경로가 연속 공간의 정확한 최단 경로라는 뜻은 아니다. 기본 PRM에 별표만 붙이거나 이웃 수를 임의로 고정하고 같은 보장을 주장하지 않는다.
OMPL 공식 목록은 PRM 계열과 LazyPRM을 구분한다. Lazy 방식은 비싼 유효성 검사를 후보 해에 필요할 때 수행하도록 미룬다. 미검사 간선은 유효성이 확정된 간선이 아니다. 후보 경로의 필요한 node와 간선을 검사하고 무효라면 제거·재탐색해야 한다. 검사 비용을 줄이는 전략을 충돌 검사를 생략해도 된다는 뜻으로 바꾸면 안 된다.
로드맵을 재사용할 때는 지도·장애물과 로봇 형상, 관절 제한, 충돌 허용 정책 및 국소 연결기의 버전을 묶어 관리한다. 새 장애물이 나타나거나 도구가 바뀌면 과거의 유효 간선을 다시 확인해야 할 수 있다. 기존 3.3 DLS 역기구학은 목표에 대한 configuration 후보를, 6.6 평가 설계는 조건별 성공·실패 분모를 보충한다. 이 종이 활동은 실제 PRM 또는 로봇의 성공률 측정이 아니다.