12.12 그래프 기반 경로 계획

12.12 그래프 기반 경로 계획

1. 그래프 기반 경로 계획의 개요

그래프 기반 경로 계획(graph-based path planning)은 로봇이 활동하는 환경을 그래프로 표현하고, 그래프 알고리즘을 사용하여 시작 위치에서 목표 위치까지의 경로를 찾는 방법론이다. 가장 직관적이고 널리 사용되는 경로 계획 접근법이며, 모바일 로봇, 매니퓰레이터, 무인 항공기, 자율 주행 차량 등 다양한 로봇 시스템에서 활용된다. 그래프 표현은 환경의 추상적 모델을 제공하며, 그래프 알고리즘의 효율적인 도구를 활용할 수 있게 한다.

2. 경로 계획의 정의

2.1 문제

경로 계획 문제는 다음과 같이 정의된다.

  • 입력: 환경 모델, 시작 위치 \mathbf{q}_{\text{start}}, 목표 위치 \mathbf{q}_{\text{goal}}
  • 출력: 시작에서 목표까지의 충돌 없는 경로 \mathbf{q}(t)

경로는 일반적으로 운동학적으로 가능해야 하며, 특정 비용 함수를 최소화하는 것이 바람직하다.

2.2 구성 공간

로봇의 자세는 구성 공간(configuration space, C-space)의 한 점이다. C-space의 차원은 로봇의 자유도이다.

  • 평면 모바일 로봇: 2D (x, y) 또는 3D (x, y, \theta)
  • 매니퓰레이터: 관절 수와 같은 차원
  • 무인 항공기: 3D 위치 또는 6D 자세

2.3 자유 공간

C-space에서 충돌이 없는 영역을 자유 공간(free space, C_{\text{free}})이라 한다. 충돌이 있는 영역은 장애물 공간(C_{\text{obs}})이다.

2.4 경로의 정의

경로는 자유 공간 위의 연속적인 곡선이다.

\mathbf{q} : [0, 1] \to C_{\text{free}}

\mathbf{q}(0) = \mathbf{q}_{\text{start}}이고 \mathbf{q}(1) = \mathbf{q}_{\text{goal}}이다.

3. 그래프 표현 방법

3.1 격자 분할

가장 단순한 그래프 표현은 환경을 격자로 분할하는 것이다.

  • 각 격자 셀이 노드가 된다.
  • 인접한 자유 셀들이 엣지로 연결된다.
  • 셀의 크기가 해상도를 결정한다.

격자 분할의 장점은 단순함이고, 단점은 차원의 저주(고차원에서 셀의 수가 폭발적으로 증가)이다.

3.2 가시성 그래프

가시성 그래프(visibility graph)는 다음과 같이 구축된다.

  • 시작점, 목표점, 장애물의 꼭짓점이 노드이다.
  • 두 노드를 연결하는 직선이 장애물을 통과하지 않으면 엣지가 있다.

가시성 그래프에서 시작점에서 목표점까지의 최단 경로는 가장 짧은 유클리드 경로이다.

3.3 보로노이 다이어그램

보로노이 다이어그램(Voronoi diagram)은 장애물에서 가장 멀리 떨어진 점들의 집합이다. 안전한 경로를 제공한다.

3.4 셀 분할

셀 분할(cell decomposition)은 자유 공간을 여러 셀로 나눈다. 각 셀은 일반적인 다각형이거나 정확한 형태이다.

  • 정확 셀 분할: 자유 공간을 정확히 분할
  • 근사 셀 분할: 격자 기반 등 근사 분할

3.5 샘플링 기반 그래프

샘플링 기반 방법은 자유 공간에서 무작위로 점을 샘플링하여 그래프를 구축한다.

  • PRM (Probabilistic Roadmap): 무작위 샘플과 가까운 이웃 연결
  • RRT (Rapidly-exploring Random Tree): 트리를 점진적으로 확장

4. 격자 기반 경로 계획

4.1 방향 격자

4방향 격자에서는 각 셀이 상, 하, 좌, 우의 4개 이웃과 연결된다.

def build_grid_graph(grid):
    rows, cols = len(grid), len(grid[0])
    graph = {}
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:  # 자유
                graph[(r, c)] = []
                for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                        graph[(r, c)].append((nr, nc))
    
    return graph

4.2 방향 격자

8방향 격자에서는 대각선 이웃도 포함한다. 대각선 이동의 비용은 일반적으로 \sqrt{2}이다.

4.3 알고리즘

격자 그래프에서 BFS, Dijkstra, A* 등이 사용된다. A*가 가장 일반적이다.

def plan_path_a_star(grid, start, goal):
    # A* 구현
    ...

5. 가시성 그래프

5.1 구축

가시성 그래프는 다음과 같이 구축된다.

  1. 시작점, 목표점, 모든 장애물의 꼭짓점을 노드로 한다.
  2. 두 노드 사이에 장애물이 가로지르지 않으면 엣지를 추가한다.
  3. 엣지의 가중치는 두 노드 사이의 유클리드 거리이다.

5.2 시간 복잡도

가시성 그래프 구축의 시간 복잡도는 O(n^2 \log n)이며, 여기서 n은 노드의 수이다. 더 효율적인 알고리즘도 있다.

5.3 응용

가시성 그래프는 다각형 장애물이 있는 평면 환경에서 효과적이다. 가장 짧은 경로를 보장한다.

6. 보로노이 다이어그램

6.1 정의

보로노이 다이어그램은 평면을 영역으로 분할하며, 각 영역은 가장 가까운 장애물 점에 대응한다. 보로노이 엣지는 두 가장 가까운 장애물 점에서 등거리에 있는 점들의 집합이다.

6.2 구축

보로노이 다이어그램은 Fortune 알고리즘으로 O(n \log n) 시간에 구축할 수 있다.

6.3 경로 계획

보로노이 엣지를 따라가면 장애물에서 멀리 떨어진 안전한 경로가 얻어진다. 시작점과 목표점을 가장 가까운 보로노이 엣지에 연결하여 경로를 완성한다.

7. 셀 분할

7.1 정확 셀 분할

자유 공간을 사다리꼴이나 다른 정확한 형태로 분할한다. 각 셀의 중심을 노드로 하고, 인접 셀을 엣지로 연결한다.

7.2 사다리꼴 분할

사다리꼴 분할(trapezoidal decomposition)은 평면 환경에서 자유 공간을 사다리꼴로 분할한다.

7.3 근사 셀 분할

근사 셀 분할은 자유 공간을 격자나 다른 단순한 형태로 분할한다. 정확하지는 않지만 단순하다.

8. 샘플링 기반 경로 계획

8.1 PRM (Probabilistic Roadmap)

PRM은 다음과 같이 동작한다.

  1. 샘플링: 자유 공간에서 무작위로 점을 샘플링한다.
  2. 연결: 각 점을 가까운 이웃들과 연결하여 그래프를 구축한다.
  3. 쿼리: 시작점과 목표점을 그래프에 추가하고 경로를 찾는다.

PRM은 다중 쿼리에 적합하다. 한 번 그래프를 구축하면 여러 쿼리에 재사용된다.

8.2 RRT (Rapidly-exploring Random Tree)

RRT는 다음과 같이 동작한다.

  1. 시작점을 트리의 루트로 한다.
  2. 자유 공간에서 무작위 점을 샘플링한다.
  3. 트리에서 가장 가까운 노드를 찾는다.
  4. 그 노드에서 무작위 점 방향으로 일정 거리 진행한 점을 트리에 추가한다.
  5. 목표에 도달하거나 시간이 초과될 때까지 반복한다.

RRT는 단일 쿼리에 효율적이며, 고차원 공간에서 효과적이다.

8.3 RRT*

RRT*는 RRT의 개선 버전이며, 점근적으로 최적이다. 새 노드를 추가할 때 주변의 노드들을 다시 연결하여 더 짧은 경로를 만든다.

8.4 Bidirectional RRT

양방향 RRT는 시작점과 목표점에서 동시에 트리를 확장한다. 두 트리가 만나면 경로가 완성된다.

9. 그래프 알고리즘의 적용

9.1 알고리즘 선택

경로 계획에 사용되는 그래프 알고리즘은 다음과 같다.

  • BFS: 비가중치 그래프, 단순한 시나리오
  • Dijkstra: 가중치 그래프, 알려진 휴리스틱이 없음
  • A*: 가장 일반적, 좋은 휴리스틱이 있음
  • D Lite*: 동적 환경

9.2 휴리스틱

휴리스틱은 응용에 적합해야 한다.

  • 격자 그래프: 맨해튼, 유클리드, 옥타일 거리
  • 도로 네트워크: 직선 거리
  • 매니퓰레이터: 작업 공간 거리

9.3 성능 고려사항

경로 계획의 성능은 다음에 의존한다.

  • 그래프의 크기
  • 알고리즘의 효율성
  • 휴리스틱의 품질
  • 자료 구조의 선택

10. 후처리

10.1 경로 평활화

격자 기반 경로는 지그재그 형태일 수 있다. 평활화(smoothing)로 더 매끄러운 경로를 얻는다.

10.2 경로 단순화

불필요한 중간점을 제거하여 경로를 단순화한다. 직선 구간으로 합칠 수 있는 노드들을 결합한다.

10.3 운동학적 변환

격자 기반 경로를 운동학적으로 가능한 경로로 변환한다. 예를 들어 자동차의 비홀로노믹 제약을 만족하도록 한다.

11. 동적 환경

11.1 동적 환경의 도전

동적 환경에서는 환경이 시간에 따라 변한다. 새로운 장애물이 나타나거나, 기존 장애물이 사라질 수 있다.

11.2 D* Lite

D* Lite는 동적 환경에서 효율적인 재계획 알고리즘이다. 변화에 따라 부분적으로만 갱신한다.

11.3 LPA*

Lifelong Planning A*(LPA*)도 동적 환경의 알고리즘이다.

11.4 응용

동적 환경의 경로 계획은 자율 주행, 인간이 있는 환경의 모바일 로봇, 군집 로봇 등에서 중요하다.

12. 다중 로봇 경로 계획

12.1 문제

여러 로봇이 동시에 경로를 계획할 때 충돌을 피해야 한다.

12.2 중앙 집중 vs 분산

  • 중앙 집중: 단일 계획자가 모든 로봇의 경로를 함께 계획
  • 분산: 각 로봇이 자체적으로 계획하고 통신으로 조정

12.3 알고리즘

  • CBS (Conflict-Based Search): 중앙 집중 방법
  • PBS (Priority-Based Search): 우선순위 기반
  • ORCA (Optimal Reciprocal Collision Avoidance): 분산 방법

13. 학습 기반 경로 계획

13.1 신경망

신경망이 경로 계획을 학습할 수 있다. 환경과 시작/목표를 입력으로 받아 경로를 출력한다.

13.2 강화 학습

강화 학습 에이전트가 경로 계획을 학습할 수 있다. 보상은 목표 도달과 충돌 회피로 정의된다.

13.3 학습과 모형 기반의 결합

학습 기반 초기 추정과 모형 기반 정제를 결합한 방법이 효과적이다.

14. 응용 예시: 청소 로봇

청소 로봇이 방을 효율적으로 청소하기 위한 경로를 계획한다. 격자 기반 환경에서 A*가 사용된다.

def plan_cleaning_path(grid, start):
    # 모든 자유 셀을 방문하는 경로
    ...

15. 응용 예시: 자율 주행

자율 주행 차량의 경로 계획에서 도로 네트워크와 운동학적 제약이 결합된다. Hybrid A*가 일반적이다.

16. 응용 예시: 매니퓰레이터

매니퓰레이터의 구성 공간에서 경로 계획에 RRT가 표준이다. 고차원 공간에서 효과적이다.

17. 응용 예시: 무인 항공기

드론의 3차원 비행 경로 계획에서 격자 기반 또는 샘플링 기반 방법이 사용된다.

18. 응용 예시: 군집 로봇

여러 로봇이 협력하여 작업을 수행할 때 다중 로봇 경로 계획 알고리즘이 사용된다.

19. 라이브러리와 도구

19.1 OMPL

Open Motion Planning Library(OMPL)는 다양한 운동 계획 알고리즘을 제공하는 C++ 라이브러리이다.

19.2 MoveIt

MoveIt은 ROS 기반 매니퓰레이터 운동 계획 프레임워크이다. 다양한 알고리즘과 통합되어 있다.

19.3 NetworkX

NetworkX는 그래프 알고리즘 라이브러리이며, 작은 규모의 경로 계획에 활용된다.

19.4 Path planning libraries

다양한 게임 엔진과 시뮬레이터에 내장된 경로 계획 라이브러리가 있다.

20. 학습의 가치

그래프 기반 경로 계획을 이해하는 것은 다음과 같은 이점을 제공한다.

  • 가장 기본적인 로봇 운동 계획 방법을 익힌다.
  • 다양한 그래프 표현과 알고리즘의 활용을 학습한다.
  • 응용에 적합한 방법을 선택할 수 있다.
  • 더 고급 운동 계획 알고리즘의 기초를 형성한다.

21. 학습 권장사항

21.1 직접 구현

격자 기반 경로 계획을 처음부터 구현해 본다. BFS, Dijkstra, A*를 모두 적용해 본다.

21.2 시각화

경로와 탐색 과정을 시각화하면 이해가 깊어진다.

21.3 다양한 환경

다양한 환경(개방, 미로, 좁은 통로 등)에서 알고리즘의 성능을 비교한다.

21.4 라이브러리 활용

OMPL, MoveIt 등의 라이브러리를 사용하여 실제 응용을 다루어 본다.

22. 본 절의 의의

본 절은 그래프 기반 경로 계획을 다루었다. 이는 로봇공학의 가장 기본적이고 중요한 영역이며, 다양한 응용에서 핵심적이다. 그래프 표현과 알고리즘의 결합이 경로 계획의 효율성과 정확성을 결정한다.

23. 참고 문헌

  • 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.
  • Karaman, S., & Frazzoli, E. (2011). “Sampling-based algorithms for optimal motion planning.” International Journal of Robotics Research, 30(7), 846–894.
  • Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). “A formal basis for the heuristic determination of minimum cost paths.” IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
  • Şucan, I. A., Moll, M., & Kavraki, L. E. (2012). “The Open Motion Planning Library.” IEEE Robotics & Automation Magazine, 19(4), 72–82.
  • Koenig, S., & Likhachev, M. (2002). “D* lite.” AAAI Conference on Artificial Intelligence, 476–483.

version: 1.0