12.13 확률적 로드맵(PRM) 방법

12.13 확률적 로드맵(PRM) 방법

1. PRM의 개요

확률적 로드맵(Probabilistic Roadmap, PRM) 방법은 로봇의 운동 계획을 위한 샘플링 기반 알고리즘이다. 1996년 라이드미 카브라키(Lydia Kavraki) 등이 제안하였으며, 고차원 구성 공간에서 효율적인 운동 계획을 가능하게 한다. PRM은 자유 공간을 무작위로 샘플링하여 그래프(로드맵)를 구축한 후, 그래프 검색 알고리즘으로 경로를 찾는다. 매니퓰레이터의 운동 계획, 인간형 로봇의 동작 생성, 다중 로봇 협조 등에서 핵심적으로 활용된다.

2. 샘플링 기반 접근법의 동기

2.1 고차원 공간의 도전

매니퓰레이터의 구성 공간은 자유도와 같은 차원이며, 일반적으로 6 이상이다. 이러한 고차원 공간에서 격자 분할은 차원의 저주(curse of dimensionality)로 인해 비효율적이다. 격자 셀의 수가 차원에 지수적으로 증가하기 때문이다.

2.2 명시적 표현의 한계

자유 공간을 명시적으로 표현하기 어려운 경우가 많다. 매니퓰레이터의 자기 충돌, 환경 충돌 등을 고려하면 자유 공간이 매우 복잡하다.

2.3 샘플링의 이점

샘플링 기반 방법은 자유 공간을 명시적으로 구축하지 않고, 무작위 샘플로 근사한다. 차원과 무관하게 작업하며, 충돌 검사만으로 자유 공간을 탐색한다.

3. PRM의 핵심 아이디어

3.1 로드맵의 구축

PRM은 자유 공간에서 무작위로 점을 샘플링하고, 가까운 점들을 연결하여 그래프(로드맵)를 구축한다. 이 로드맵이 자유 공간의 연결성을 표현한다.

3.2 경로 쿼리

시작 자세와 목표 자세를 로드맵에 추가하고, 그래프 검색 알고리즘으로 경로를 찾는다. 같은 로드맵을 여러 쿼리에 재사용할 수 있다.

3.3 두 단계의 분리

PRM은 두 단계로 분리된다.

  • 학습 단계: 로드맵 구축
  • 쿼리 단계: 경로 검색

이러한 분리가 PRM의 강점이다.

4. PRM의 알고리즘

4.1 학습 단계

PRM_Learning(C_free, n, k):
    V = empty set
    E = empty set
    
    // 노드 샘플링
    while |V| < n:
        q_rand = random sample from C_space
        if q_rand is in C_free:
            V.add(q_rand)
    
    // 엣지 연결
    for each q in V:
        neighbors = k nearest neighbors of q in V
        for each q' in neighbors:
            if local_planner(q, q') is collision-free:
                E.add((q, q'))
    
    return roadmap (V, E)

여기서

  • C_{\text{free}}: 자유 공간
  • n: 샘플 노드의 수
  • k: 각 노드를 연결할 이웃의 수
  • local_planner: 두 자세 사이의 경로가 충돌이 없는지 검사하는 함수

4.2 쿼리 단계

PRM_Query(roadmap, q_start, q_goal):
    // 시작과 목표를 로드맵에 추가
    add q_start, q_goal to V
    connect q_start to its k nearest neighbors in V
    connect q_goal to its k nearest neighbors in V
    
    // 경로 검색
    path = graph_search(roadmap, q_start, q_goal)
    
    return path

4.3 단계별 동작

  1. 샘플링: 자유 공간에서 무작위로 점을 샘플링한다.
  2. 충돌 검사: 샘플 점이 자유 공간에 있는지 검사한다.
  3. 연결: 각 노드를 가까운 이웃들과 연결한다.
  4. 로컬 플래너: 두 노드 사이의 경로가 충돌이 없는지 검사한다.
  5. 쿼리: 시작과 목표를 로드맵에 추가하고 그래프 검색으로 경로를 찾는다.

5. 핵심 구성 요소

5.1 충돌 검사

충돌 검사(collision detection)는 PRM의 가장 시간이 많이 걸리는 부분이다. 효율적인 충돌 검사 알고리즘이 필수이다.

5.1.1 충돌 검사 라이브러리

  • FCL (Flexible Collision Library): 일반적인 강체 충돌 검사
  • Bullet: 게임 엔진의 충돌 검사
  • PQP: 고급 충돌 거리 계산
  • MoveIt의 충돌 검사: 매니퓰레이터에 특화

5.2 가까운 이웃 검색

각 노드에 대해 가장 가까운 이웃을 찾아야 한다. 효율적인 가까운 이웃 검색 알고리즘이 필요하다.

5.2.1 알고리즘

  • k-d Tree: 저차원에서 효율적
  • Ball Tree: 다양한 메트릭에 적용 가능
  • Cover Tree: 일반 메트릭 공간
  • HNSW: 근사 검색, 매우 효율적

5.3 거리 함수

자세 사이의 거리는 응용에 따라 다르다.

  • 매니퓰레이터: 관절 공간의 유클리드 거리
  • 모바일 로봇: SE(2) 또는 SE(3)의 거리
  • 무인 항공기: 위치와 자세의 결합 거리

5.4 로컬 플래너

로컬 플래너는 두 자세 사이의 경로가 충돌이 없는지 검사한다. 일반적으로 두 자세를 직선으로 연결하고, 그 위의 여러 점에서 충돌 검사를 수행한다.

5.4.1 단순 보간

가장 단순한 로컬 플래너는 직선 보간이다.

def linear_local_planner(q1, q2, num_steps=10):
    for i in range(num_steps + 1):
        t = i / num_steps
        q = q1 + t * (q2 - q1)
        if is_in_collision(q):
            return False
    return True

5.4.2 적응적 검사

거리에 비례하는 검사 단계 수를 사용한다.

6. PRM의 변형

6.1 표준 PRM

위에서 설명한 기본 PRM이다. 균등 샘플링과 k-NN 연결을 사용한다.

6.2 Lazy PRM

Lazy PRM은 로드맵 구축 시 로컬 플래너를 호출하지 않고, 쿼리 시에만 경로의 충돌 검사를 수행한다. 학습 단계가 빠르지만 쿼리가 더 복잡하다.

6.3 sPRM (Simplified PRM)

sPRM은 알고리즘의 분석을 단순화한 변형이다. 점근적 최적성이 분석되어 있다.

6.4 PRM*

PRM*는 PRM의 점근적 최적 변형이다. 연결 반지름이 노드 수에 따라 자동으로 조정된다.

r(n) = \gamma\!\left(\frac{\log n}{n}\right)^{1/d}

여기서 d는 차원, \gamma는 상수이다.

6.5 가시성 PRM

가시성 PRM(Visibility PRM)은 노드를 가드(guard)와 연결자(connector)로 분류하여 효율적인 로드맵을 구축한다.

6.6 동적 PRM

동적 환경에서 사용되는 PRM의 변형이다. 환경 변화에 따라 로드맵을 부분적으로 갱신한다.

7. RRT와의 비교

7.1 차이

측면PRMRRT
접근 방식다중 쿼리단일 쿼리
그래프 구조로드맵트리
학습 단계분리통합
효율성학습 후 빠른 쿼리직접 탐색
메모리더 많음적음

7.2 적합한 경우

  • 다중 쿼리: PRM이 적합 (한 환경에서 여러 경로)
  • 단일 쿼리: RRT가 적합 (한 번의 경로)
  • 고차원: 둘 다 효과적
  • 동적 환경: RRT가 더 자연스러움

8. 성능 분석

8.1 점근적 완전성

PRM은 점근적으로 완전(asymptotically complete)이다. 즉, 노드의 수가 무한대로 증가함에 따라 해답이 존재하면 발견할 확률이 1로 수렴한다.

8.2 점근적 최적성

PRM*는 점근적 최적(asymptotically optimal)이다. 노드의 수가 증가함에 따라 발견된 경로의 비용이 최적 비용으로 수렴한다.

8.3 시간 복잡도

PRM의 시간 복잡도는 다음에 의존한다.

  • 노드의 수 n
  • 차원 d
  • 가까운 이웃 검색의 효율성

기본 PRM의 학습 단계 시간 복잡도는 O(n \cdot k \cdot T_{\text{collision}})이며, 여기서 T_{\text{collision}}은 충돌 검사 시간이다.

9. 실용적 고려사항

9.1 노드 수의 선택

너무 적은 노드는 좁은 통로를 발견하지 못할 수 있다. 너무 많은 노드는 계산 시간이 늘어난다. 일반적으로 1000 \sim 10000개의 노드가 사용된다.

9.2 좁은 통로 문제

자유 공간에 좁은 통로(narrow passage)가 있으면 균등 샘플링으로는 발견하기 어렵다. 이를 해결하기 위한 방법이 있다.

9.2.1 가우시안 샘플링

가우시안 샘플링은 충돌 영역과 자유 공간의 경계 근처를 더 많이 샘플링한다.

9.2.2 브리지 샘플링

브리지 샘플링은 두 충돌 점 사이의 자유 점을 샘플링한다.

9.2.3 의료 축 샘플링

의료 축(medial axis) 근처를 샘플링하여 좁은 통로를 발견한다.

9.3 연결 전략

이웃 연결 전략의 선택이 로드맵의 품질에 영향을 준다.

  • k-NN: 각 노드를 k개의 가장 가까운 이웃과 연결
  • 반지름 기반: 일정 반지름 내의 모든 노드와 연결
  • 적응적: 로컬 밀도에 따라 다른 전략

9.4 충돌 검사 최적화

충돌 검사가 PRM의 주요 비용이므로 최적화가 중요하다.

  • 계층적 충돌 검사
  • 보수적 검사 (일정 확률로 통과)
  • 학습된 충돌 분류기

10. Python 구현 예시

import numpy as np
from sklearn.neighbors import NearestNeighbors

def prm(c_free_check, dim, num_samples, k, q_start, q_goal):
    # 노드 샘플링
    samples = []
    while len(samples) < num_samples:
        q = np.random.uniform(0, 1, dim)
        if c_free_check(q):
            samples.append(q)
    
    samples = np.array(samples)
    
    # 가까운 이웃 검색
    nbrs = NearestNeighbors(n_neighbors=k+1).fit(samples)
    distances, indices = nbrs.kneighbors(samples)
    
    # 그래프 구축
    graph = {i: [] for i in range(len(samples))}
    for i, neighbors in enumerate(indices):
        for j in neighbors[1:]:  # 자기 자신 제외
            if local_planner(samples[i], samples[j], c_free_check):
                graph[i].append(j)
    
    # 시작과 목표 추가
    start_idx = len(samples)
    goal_idx = len(samples) + 1
    samples = np.vstack([samples, q_start, q_goal])
    graph[start_idx] = []
    graph[goal_idx] = []
    
    # 시작과 목표를 가까운 이웃과 연결
    for i in range(num_samples):
        if local_planner(q_start, samples[i], c_free_check):
            graph[start_idx].append(i)
            graph[i].append(start_idx)
        if local_planner(q_goal, samples[i], c_free_check):
            graph[goal_idx].append(i)
            graph[i].append(goal_idx)
    
    # 경로 검색
    path_indices = bfs(graph, start_idx, goal_idx)
    if path_indices is None:
        return None
    return samples[path_indices]

11. PRM의 응용

11.1 매니퓰레이터의 운동 계획

매니퓰레이터의 작업 공간이나 구성 공간에서 PRM이 사용된다. 다양한 작업에 대해 같은 로드맵을 재사용할 수 있다.

11.2 인간형 로봇

인간형 로봇의 전신 동작 계획에 PRM이 활용된다. 균형, 충돌 회피 등을 고려한 동작이 생성된다.

11.3 차량 운동 계획

비홀로노믹 차량(자동차 등)의 운동 계획에 PRM이 사용된다. 운동학적 제약이 로컬 플래너에 반영된다.

11.4 분자 도킹

분자 동역학에서 단백질의 구조와 약물 분자의 도킹 분석에 PRM이 사용된다.

11.5 다중 로봇 협조

다중 로봇이 동시에 운동 계획을 수행할 때 PRM의 변형이 사용된다.

12. 로봇공학에서의 응용 예시

12.1 매니퓰레이터의 픽 앤 플레이스

매니퓰레이터가 부품을 집어 옮기는 작업에서 PRM이 경로 계획에 사용된다.

  1. 작업 환경의 PRM을 미리 구축한다.
  2. 작업이 들어오면 시작과 목표를 로드맵에 추가한다.
  3. 경로 검색으로 경로를 찾는다.

12.2 인간형 로봇의 보행

인간형 로봇이 환경에서 이동할 때 PRM이 활용된다. 다리의 운동, 균형 유지, 환경 회피 등이 고려된다.

12.3 자율 주행 차량의 주차

자율 주차 시스템에서 PRM이 경로 계획에 사용된다. 차량의 운동학적 제약이 반영된다.

12.4 드론의 경로 계획

복잡한 환경에서 드론의 비행 경로를 PRM으로 계획한다. 3차원 환경에서 효과적이다.

12.5 의료 로봇

수술 로봇이 환자의 해부학적 구조를 회피하면서 도구를 이동시킬 때 PRM이 활용된다.

13. PRM의 한계

13.1 좁은 통로 문제

자유 공간에 좁은 통로가 있으면 균등 샘플링으로 발견하기 어렵다. 특수한 샘플링 전략이 필요하다.

13.2 메모리 사용

큰 로드맵은 메모리를 많이 사용한다. 노드 수가 많아질수록 메모리 부담이 크다.

13.3 동적 환경

PRM은 정적 환경을 가정한다. 환경이 변하면 로드맵을 다시 구축해야 한다.

13.4 매개변수 튜닝

노드 수, 이웃 수, 거리 함수 등의 매개변수가 결과에 영향을 준다. 응용에 따라 튜닝이 필요하다.

14. 라이브러리 지원

14.1 OMPL

Open Motion Planning Library(OMPL)는 PRM과 그 변형들을 구현한다. C++로 작성되었으며 ROS와 통합된다.

#include <ompl/geometric/planners/prm/PRM.h>
auto planner = std::make_shared<og::PRM>(si);
planner->setProblemDefinition(pdef);
planner->setup();
auto solved = planner->solve(time_limit);

14.2 MoveIt

MoveIt은 ROS의 매니퓰레이터 운동 계획 프레임워크이며, OMPL을 통해 PRM을 지원한다.

14.3 다른 라이브러리

  • ROS의 navigation 패키지
  • Klampt
  • Drake

15. 학습의 가치

PRM을 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

  • 샘플링 기반 운동 계획의 핵심 알고리즘을 익힌다.
  • 고차원 공간에서의 운동 계획을 학습한다.
  • 매니퓰레이터의 운동 계획의 표준 도구를 습득한다.
  • 로드맵 기반 접근법의 장단점을 이해한다.
  • OMPL 등의 운동 계획 라이브러리를 효과적으로 사용할 수 있다.

16. 학습 권장사항

16.1 직접 구현

간단한 2차원 환경에서 PRM을 직접 구현해 본다. 점차 고차원으로 확장한다.

16.2 시각화

PRM의 로드맵과 경로를 시각화하면 이해가 깊어진다.

16.3 매개변수 실험

다양한 매개변수(노드 수, 이웃 수, 거리 함수)를 시도해 본다. 결과에 미치는 영향을 관찰한다.

16.4 변형 학습

PRM*, Lazy PRM 등의 변형을 학습한다. 각 변형의 적용 영역을 이해한다.

16.5 OMPL 활용

OMPL을 사용하여 실제 응용을 다루어 본다.

17. 본 절의 의의

본 절은 확률적 로드맵(PRM) 방법을 자세히 다루었다. PRM은 고차원 운동 계획의 핵심 알고리즘이며, 매니퓰레이터를 비롯한 다양한 로봇 시스템에서 표준이다. 샘플링 기반 접근법의 이해는 현대 로봇공학의 운동 계획을 학습하는 데 필수적이다.

18. 참고 문헌

  • Kavraki, L. E., Svestka, P., Latombe, J. C., & Overmars, M. H. (1996). “Probabilistic roadmaps for path planning in high-dimensional configuration spaces.” IEEE Transactions on Robotics and Automation, 12(4), 566–580.
  • Karaman, S., & Frazzoli, E. (2011). “Sampling-based algorithms for optimal motion planning.” International Journal of Robotics Research, 30(7), 846–894.
  • LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
  • Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.
  • Bohlin, R., & Kavraki, L. E. (2000). “Path planning using lazy PRM.” IEEE International Conference on Robotics and Automation, 521–528.
  • Şucan, I. A., Moll, M., & Kavraki, L. E. (2012). “The Open Motion Planning Library.” IEEE Robotics & Automation Magazine, 19(4), 72–82.

version: 1.0