Probabilistic Roadmap

• 다른 이름: PRM, probabilistic roadmap method
• 카테고리: Planning & manipulation › Motion planning
• 태그: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

무작위로 뽑은 충돌 없는 구성들과 그 사이의 실행 가능한 경로로 재사용 가능한 그래프를 만든 뒤, 그래프 탐색으로 계획 질의에 답하는 샘플링 기반 동작 플래너.

정의

확률적 로드맵(Probabilistic Roadmap, PRM)은 1996년 Kavraki, Švestka, Latombe, Overmars가 제안한 샘플링 기반 동작 계획 방법이다. 요청이 있을 때마다 구성 공간을 새로 탐색하는 대신, PRM은 먼저 로봇의 자유 공간의 연결성을 담은 그래프, 즉 로드맵을 만든 뒤, 그 그래프를 사용해 출발점-목표점 질의에 몇 번이든 답한다.

계획은 두 단계로 이루어진다. 구축 단계에서 플래너는 로봇의 무작위 구성을 샘플링하고, 충돌이 없는 것들을 노드로 남기며, 단순한 지역 플래너로 각 노드를 가까운 노드들과 연결하려 시도한다. 지역 플래너는 보통 구성 공간에서의 직선으로, 촘촘한 간격으로 충돌 여부를 검사한다. 연결에 성공하면 간선이 된다. 질의 단계에서는 출발 구성과 목표 구성을 로드맵에 연결하고, Dijkstra 알고리즘이나 A* 같은 그래프 탐색으로 로드맵을 통과하는 경로를 찾는다.

PRM은 환경이 정적이고 로봇이 같은 공간에서 많은 동작을 계획해야 하는 다중 질의 문제에 적합한데, 비용이 큰 로드맵 구축을 한 번만 하면 되기 때문이다. PRM은 확률적으로 완전하다. 경로가 존재한다면, 샘플 수가 늘어날수록 로드맵이 경로를 포함할 확률이 1에 가까워진다.

주된 약점은 좁은 통로이다. 균일한 무작위 샘플은 자유 공간의 얇은 영역에 거의 떨어지지 않으므로, 로드맵이 실제로는 이어져 있는 영역들을 연결하지 못할 수 있다. 이를 해결하기 위해 장애물 경계 근처를 샘플링하는 것 같은 편향 샘플링 전략이 개발되었다. PRM*는 로드맵이 점근적으로 최적이 되도록 연결 반경을 고르는 변형이다.

중요한 이유

PRM은 정확한 방법으로는 다루기 어려운 자유도가 많은 로봇에서도 무작위 샘플링으로 동작 계획을 실용적으로 만들 수 있음을 보여 주었다. 고정된 산업용 셀처럼 로봇이 같은 환경에서 반복적으로 작업할 때면 언제나 로드맵이라는 아이디어가 여전히 유용하다.

주요 응용

• 고정 작업 셀에서 로봇 암의 다중 질의 동작 계획
• 정적 지도에서 모바일 로봇의 경로 계획
• 휴머노이드와 양팔 로봇 같은 고자유도 시스템의 계획
• 샘플링 기반 계획의 교육과 벤치마킹

실제 사례

팀은 보통 PRM을 OMPL을 통해, 로봇 암 계획의 경우 흔히 MoveIt을 거쳐 사용하며, 여기서 PRM과 PRM*는 RRT-Connect 같은 트리 기반 플래너와 나란히 제공된다. 로드맵은 저장해 재사용할 수 있으므로, PRM은 로봇 암이 같은 고정구 주변의 여러 자세 사이를 오가는 고정 작업 셀에 잘 맞는다. 로드맵은 오프라인으로 만들고 실행 시점에 질의하며, 충돌 검사는 물체가 움직였을 수 있는 곳에서만 반복한다. 엔지니어는 샘플 수와 연결 반경을 조정하고, 로드맵에 끊어진 연결 요소가 없는지 살피는데, 이는 대개 더 많은 샘플이나 더 잘 겨냥한 샘플이 필요한 좁은 통로를 가리킨다.

흔한 오해

• PRM은 경로가 존재하면 항상 찾는다 — 확률적으로 완전하므로, 이 보장은 샘플이 무한히 많은 극한에서만 성립한다
• PRM은 주로 2D 지도용이다 — 주된 용도는 로봇 암의 관절 공간 같은 고차원 구성 공간이다
• 로드맵은 영원히 유효하다 — 장애물이 움직이면 영향을 받은 간선을 다시 검사하거나 로드맵을 다시 만들어야 한다

알아야 할 사람

• 동작 계획 엔지니어
• 산업용 로봇 셀 통합 업체
• 조작 연구자
• 샘플링 기반 계획을 배우는 로봇공학 학생

관련 기술

• OMPL
• MoveIt
• RRT
• PRM*
• A 탐색(A Search)
• 구성 공간(Configuration Space)

관련 용어

• Motion Planning
• RRT*
• Configuration Space

관련 프로젝트

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

동영상

• Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics