경로 계획

수치해석 게임 개발 마지막 수정: 2026-08-20 04:39:08

1. 개요[편집]

경로 계획 Path Planning
목표	시작 자세 → 목표 자세, 충돌 없는 경로
무대	구성공간(configuration space, C-space)
그래프 기반	다익스트라 · A* · D*
샘플링 기반	PRM · RRT · RRT*
연속장 기반	퍼텐셜장 · 고속 행진법
난이도	일반 3D 경로계획은 PSPACE-난해

경로 계획(path planning)은 로봇이나 이동체를 시작 상태에서 목표 상태까지, 장애물과 충돌하지 않으면서 이동시키는 경로를 자동으로 찾는 문제다. 자율주행차의 차선 변경, 로봇 팔의 집기 동작, 게임 속 NPC의 길찾기, 드론의 회피 기동이 전부 같은 문제의 얼굴들이다.

언뜻 “두 점을 잇는 선을 그으면 되지”처럼 보이지만, 진짜 어려움은 세 겹이다 — 장애물을 피해야 하고(기하), 이동체가 부피와 모양을 가지며(형상), 마음대로 움직이지 못한다(동역학 제약). 이 어려움들을 다루는 통일된 무대가 구성공간이고, 그 위에서 그래프 탐색·무작위 샘플링·연속장이라는 세 가지 큰 전략이 경쟁한다. 이 문서는 그 지도를 그린다.¹

2. 구성공간 (C-space)[편집]

경로 계획의 핵심 추상화는 구성공간(구성 공간, configuration space)이다. 이동체의 자세를 완전히 기술하는 파라미터들(위치 $x,y$ , 방향 $\theta$ , 로봇 팔이면 각 관절 각도)을 좌표축으로 삼은 공간이다. $n$ 자유도 로봇의 한 자세는 이 $n$ 차원 공간의 한 점이 된다.

이 변환의 위력은 하나다 — 부피를 가진 이동체가 C-space에서는 점이 된다. 대신 장애물이 부풀려진다. 이동체 모양을 장애물 경계를 따라 훑어 민코프스키 합으로 부풀린 것이 C-장애물(configuration obstacle)이고, 이동체가 어디든 갈 수 있는 나머지 영역이 자유공간 $\mathcal{C}_{\text{free}}$ 다. 이제 문제는 깔끔해진다:

\text{시작점 } q_{\text{start}} \in \mathcal{C}_{\text{free}} \text{ 에서 } q_{\text{goal}} \text{ 로 } \mathcal{C}_{\text{free}} \text{ 안의 연속 곡선을 찾아라.}

문제는 C-space를 명시적으로 계산하는 비용이 차원에 지수적이라는 것. 6자유도 로봇 팔의 C-장애물을 통째로 그리는 것은 사실상 불가능하다. 그래서 실용적 방법들은 C-space를 통째로 짓지 않고 필요한 곳만 국소적으로 질의한다(충돌 감지 함수로).

3. 그래프 기반 — 이산화하고 최단경로[편집]

가장 고전적인 접근은 공간을 그래프로 이산화한 뒤 최단경로 알고리즘을 돌리는 것이다.

격자(grid). 공간을 셀로 나눠 인접 셀을 잇는다. 구현이 쉽고 게임에서 지배적이지만, 해상도와 메모리가 차원에 지수적이고 격자축에 묶인 경로가 나온다.
가시성 그래프(visibility graph). 다각형 장애물의 꼭짓점들을 서로 보이는 것끼리 잇는다. 2D 다각형 세계에서 진짜 최단경로를 준다(최단경로는 장애물 꼭짓점을 스치므로).
보로노이 다이어그램. 장애물에서 최대한 먼 길을 따라간다 — 안전 여유를 최대화하는 경로.

이렇게 만든 그래프 위에서 다익스트라 알고리즘이 단일 시작점 최단경로를 준다. 그러나 다익스트라는 목표 방향을 모른 채 사방으로 퍼지므로 낭비가 크다. 여기에 목표까지 남은 비용의 추정치(휴리스틱) 를 더해 탐색을 목표 쪽으로 편향시킨 것이 A* 알고리즘이다. 평가함수

f(n) = g(n) + h(n)

에서 $g$ 는 시작점부터의 실제 비용, $h$ 는 목표까지의 추정 비용이며, $h$ 가 실제 비용을 넘지 않으면(허용적, admissible) A는 최적해를 보장한다. 휴리스틱이 완벽하면 A는 직선으로 목표에 가고, $h=0$ 이면 다익스트라로 퇴화한다. 환경이 변하면 매번 다시 풀지 않고 이전 탐색을 재활용하는 D*·D* Lite가 자율주행·화성 탐사차에서 쓰인다.

3.1. 연속장으로 보는 최단경로 — 고속 행진법과의 관계[편집]

격자 그래프의 A*는 경로가 격자축(상하좌우·대각선)에 묶여 8방향 계단 경로를 낸다는 고질병이 있다. 이를 연속적으로 푸는 관점이 고속 행진법(fast marching method)이다. 이동 비용을 속도장 $F$ 로 놓고 도달시간 $T$ 에 대한 아이코날 방정식

|\nabla T|\,F = 1

을 풀면, $T$ 는 시작점으로부터의 연속적 최단 도달시간장이 되고, 목표점에서 $-\nabla T$ 를 따라 경사하강하면 격자에 얽매이지 않은 매끄러운 최적 경로가 나온다. 고속 행진법은 사실상 다익스트라의 연속판이다 — 둘 다 도달시간이 작은 곳부터 우선순위 큐로 확장한다. 다만 다익스트라가 그래프 간선을 따라가는 반면 FMM은 삼각부등식 대신 아이코날 이산화를 풀어 격자 이방성 오차를 없앤다. 관계의 세부는 고속 행진법 문서에 있다.

4. 샘플링 기반 — 고차원의 구원[편집]

로봇 팔처럼 자유도가 6, 7을 넘어가면 격자는 죽는다(차원의 저주). 그 벽을 넘은 것이 샘플링 기반 계획이다. C-space를 통째로 짓는 대신, 무작위 표본점을 뿌리고 충돌 없는 것만 이어 붙여 자유공간의 성긴 지도를 만든다.

PRM(확률적 로드맵). 무작위 자세를 잔뜩 뽑아 충돌 없는 것을 노드로 삼고, 가까운 노드끼리 직선 이동이 가능하면 간선으로 잇는다. 로드맵을 한 번 지어 두면 여러 질의를 빠르게 답한다(멀티 질의). 정적 환경의 반복 계획에 강하다.
RRT(급속 탐색 무작위 트리). 시작점에서 트리를 키운다 — 무작위 점을 뽑고, 트리에서 가장 가까운 노드를 그 방향으로 조금 뻗는다. 이 규칙이 트리를 미탐색 영역으로 편향되게 자라게 해(보로노이 편향) 넓은 공간을 빠르게 덮는다. 단일 질의·고차원·동역학 제약에 강해 사실상 로보틱스의 기본기다.

두 방법의 성질은 확률적 완비성(probabilistic completeness)이다 — 해가 존재하면 표본 수를 늘릴수록 찾을 확률이 1로 간다. 대신 찾은 경로가 최적이라는 보장은 없다. RRT의 경로는 대개 삐뚤빼뚤하다.

4.1. 최적성 — RRT*[편집]

이 결함을 메운 것이 카라만·프라줄리(2011)의 RRT*다. 새 노드를 붙일 때 단순히 가장 가까운 노드에 잇지 않고, 근방 안에서 시작점까지 비용이 최소가 되는 부모를 고르고(choose parent), 새 노드를 경유하면 더 싸지는 이웃들의 연결을 다시 잇는다(rewire). 이 두 연산이 트리를 점진적으로 개선해, 표본 수가 무한대로 가면 경로가 최적해로 수렴한다(점근적 최적성). PRM에도 같은 원리를 적용한 것이 PRM*다. “일단 아무 경로나 빨리, 그다음 계속 다듬어 최적으로”가 RRT*의 정신이며, 시간 예산에 맞춰 언제든 멈추고 현재 최선을 쓸 수 있는 애니타임(anytime) 성질이 실무에서 사랑받는 이유다.

5. 퍼텐셜장 — 힘으로 미는 방법[편집]

전혀 다른 계열이 인공 퍼텐셜장(artificial potential field)이다. 목표는 이동체를 끌어당기는 인력장, 장애물은 밀어내는 척력장을 만들고, 두 힘의 합의 음의 기울기를 따라 내려간다.

U(q) = U_{\text{att}}(q) + U_{\text{rep}}(q), \qquad \dot q = -\nabla U(q)

계산이 값싸고 실시간 반응이 좋아 국소 회피에 널리 쓰이지만, 치명적 약점이 국소최소다 — 목표가 아닌 곳에서 인력과 척력이 상쇄되면 이동체가 갇힌다(오목한 장애물 앞에서 특히). 그래서 퍼텐셜장은 전역 계획기의 하위 국소 계획기로 쓰거나, 국소최소가 없도록 설계된 항법함수(navigation function)를 쓴다. 앞의 고속 행진법 기반 장은 국소최소가 없는 전역 퍼텐셜을 준다는 점에서 이 계열의 상위호환으로 볼 수 있다.

6. 동역학 제약 — kinodynamic[편집]

지금까지는 이동체가 어느 방향으로든 즉시 움직일 수 있다고 가정했다. 하지만 자동차는 옆으로 못 가고(비홀로노믹), 드론은 관성이 있으며, 속도·가속도에 한계가 있다. 이런 미분 제약까지 함께 만족하는 경로를 찾는 것이 kinodynamic planning이다.

핵심은 C-space를 위치뿐 아니라 속도까지 포함한 상태공간으로 확장하고, 두 상태를 잇는 이동을 직선이 아니라 실제로 실현 가능한 궤적(제어입력을 적분해 얻는)으로 바꾸는 것이다. RRT 계열은 이 확장이 자연스러워(뻗기 연산을 제어입력 적분으로 바꾸면 끝) kinodynamic 문제의 주력이 된다. 다만 최적 궤적을 이으려면 두 상태를 잇는 국소 경계값 문제(steering)를 풀어야 하고, 이 지점에서 최적 제어와 만난다.

7. 복잡도와 응용[편집]

일반 경로 계획은 생각보다 어렵다. 라이프-샤리르(1979)의 피아노 운반공 문제(piano mover’s problem)는 다관절 로봇의 일반 경로계획이 PSPACE-난해임을 보였다. 자유도가 늘면 지수적으로 어려워진다는 이 결과가, 정확한 방법 대신 샘플링 기반 근사가 지배하게 된 근본 이유다. 관련 계산복잡도 개념은 NP-완전 문서를 참고.

응용은 로봇공학 전 분야에 걸친다 — 자율주행(전역 경로 + 국소 회피의 계층 구조), 로봇 팔 조작, 드론 군집, 그리고 게임의 NPC 길찾기(대개 격자 A*로 충분하다). 실무에서는 대개 전역 계획기(A·RRT)로 큰 그림을 그리고, 국소 계획기(퍼텐셜장·DWA)로 실시간 회피를 하는** 이층 구조를 쓴다.

8. 관련 문서[편집]

“경로 계획(path planning)“과 “궤적 계획(trajectory planning)“은 종종 혼용되지만 엄밀히는 다르다. 경로는 공간상의 기하학적 곡선(어디를 지나는가)이고, 궤적은 거기에 시간을 입힌 것(언제 어디에 있는가)이다. 경로를 먼저 찾고 속도 프로파일을 씌우는 2단계 분리가 실무의 관행이며, 그래서 “매끄러운 경로를 찾았는데 로봇이 그대로 못 따라간다”는 사고가 두 단계의 경계에서 터진다. ↩