7.18 로봇 경로 계획에서의 포텐셜 필드법

1. 포텐셜 필드법의 기본 원리

포텐셜 필드법(potential field method)은 Khatib(1986)가 제안한 이래 로봇 경로 계획(path planning)의 고전적 접근법으로 자리잡았다. 이 방법의 핵심 발상은 로봇이 작업 공간(workspace) $\mathcal{W} \subseteq \mathbb{R}^m$ 내에서 가상의 포텐셜 에너지장(potential energy field)에 의해 구동된다고 모형화하는 것이다.

목표 지점(goal) $\mathbf{x}_g$ 는 로봇을 끌어당기는 인력 포텐셜(attractive potential)을 생성하고, 장애물 집합 $\{\mathcal{O}_k\}_{k=1}^{N}$ 은 로봇을 밀어내는 반발 포텐셜(repulsive potential)을 생성한다. 로봇의 위치를 $\mathbf{x} \in \mathbb{R}^m$ 이라 할 때, 총 포텐셜 함수(total potential function)는 다음과 같이 정의된다.

$U(\mathbf{x}) = U_{\text{att}}(\mathbf{x}) + U_{\text{rep}}(\mathbf{x})$

로봇에 작용하는 가상 힘(virtual force)은 총 포텐셜의 음의 그래디언트(negative gradient)로 결정된다.

$\mathbf{F}(\mathbf{x}) = -\nabla U(\mathbf{x}) = -\nabla U_{\text{att}}(\mathbf{x}) - \nabla U_{\text{rep}}(\mathbf{x})$

이 가상 힘의 방향이 곧 로봇의 이동 방향이 되며, 로봇은 포텐셜 에너지가 감소하는 방향으로 반복적으로 이동하여 목표 지점에 도달하게 된다. 이는 수학적으로 경사 하강법(gradient descent)과 동일한 구조이다.

2. 인력 포텐셜의 설계

2.1 이차 인력 포텐셜

가장 기본적인 형태의 인력 포텐셜은 목표점으로부터의 유클리드 거리(Euclidean distance)의 제곱에 비례하는 이차 포텐셜(quadratic potential)이다.

$U_{\text{att}}(\mathbf{x}) = \frac{1}{2} \xi \lVert \mathbf{x} - \mathbf{x}_g \rVert^2$

여기서 $\xi > 0$ 는 인력 이득(attractive gain) 계수이다. 이 포텐셜의 그래디언트는

$\nabla U_{\text{att}}(\mathbf{x}) = \xi (\mathbf{x} - \mathbf{x}_g)$

이므로, 인력 벡터는

$\mathbf{F}_{\text{att}}(\mathbf{x}) = -\xi (\mathbf{x} - \mathbf{x}_g)$

이 된다. 인력의 크기가 $\lVert \mathbf{F}_{\text{att}} \rVert = \xi \lVert \mathbf{x} - \mathbf{x}_g \rVert$ 이므로, 목표점에서 멀수록 힘이 강해진다. 이 성질은 목표점 근방에서는 부드러운 감속을 유도하지만, 원거리에서는 인력의 크기가 과도해지는 문제를 야기한다.

2.2 원추형 인력 포텐셜

원거리에서의 과도한 인력을 억제하기 위해, 임계 거리 $d^*$ 를 경계로 이차 포텐셜과 원추형 포텐셜(conic potential)을 결합하는 방법이 사용된다.

$U_{\text{att}}(\mathbf{x}) = \begin{cases} \dfrac{1}{2} \xi \lVert \mathbf{x} - \mathbf{x}_g \rVert^2, & \lVert \mathbf{x} - \mathbf{x}_g \rVert \leq d^* \\[10pt] d^* \xi \lVert \mathbf{x} - \mathbf{x}_g \rVert - \dfrac{1}{2} \xi (d^*)^2, & \lVert \mathbf{x} - \mathbf{x}_g \rVert > d^* \end{cases}$

$d^*$ 이상의 영역에서 그래디언트는

$\nabla U_{\text{att}}(\mathbf{x}) = d^* \xi \frac{\mathbf{x} - \mathbf{x}_g}{\lVert \mathbf{x} - \mathbf{x}_g \rVert}$

이며, 인력의 크기가 $\xi d^*$ 로 일정하게 포화(saturation)된다. 경계 $\lVert \mathbf{x} - \mathbf{x}_g \rVert = d^*$ 에서 포텐셜 함수값과 그래디언트가 모두 연속이므로, 결합 포텐셜은 $C^1$ 급 연속성을 보장한다.

3. 반발 포텐셜의 설계

3.1 기본 반발 포텐셜

장애물 $\mathcal{O}$ 에 대한 로봇의 최소 거리 함수를

$d(\mathbf{x}) = \min_{\mathbf{x}_o \in \mathcal{O}} \lVert \mathbf{x} - \mathbf{x}_o \rVert$

로 정의하고, 장애물의 영향 범위(influence range)를 $d_0 > 0$ 으로 설정하면, Khatib(1986)의 반발 포텐셜은 다음과 같다.

$U_{\text{rep}}(\mathbf{x}) = \begin{cases} \dfrac{1}{2} \eta \left( \dfrac{1}{d(\mathbf{x})} - \dfrac{1}{d_0} \right)^2, & d(\mathbf{x}) \leq d_0 \\[10pt] 0, & d(\mathbf{x}) > d_0 \end{cases}$

여기서 $\eta > 0$ 는 반발 이득(repulsive gain) 계수이다. 장애물 영향 범위 내에서의 그래디언트는

$\nabla U_{\text{rep}}(\mathbf{x}) = \eta \left( \frac{1}{d(\mathbf{x})} - \frac{1}{d_0} \right) \frac{1}{d^2(\mathbf{x})} \nabla d(\mathbf{x})$

이며, 거리 함수의 그래디언트 $\nabla d(\mathbf{x})$ 는 장애물 표면의 최근접점 $\mathbf{x}_o^*$ 로부터 로봇 방향을 가리키는 단위 벡터이다.

$\nabla d(\mathbf{x}) = \frac{\mathbf{x} - \mathbf{x}_o^*}{\lVert \mathbf{x} - \mathbf{x}_o^* \rVert}$

반발력은 $d(\mathbf{x}) \to 0$ 일 때 $\lVert \mathbf{F}_{\text{rep}} \rVert \to \infty$ 로 발산하여, 로봇이 장애물과 충돌하는 것을 원천적으로 방지한다. 반면 $d(\mathbf{x}) = d_0$ 인 경계에서 $U_{\text{rep}}$ 과 $\nabla U_{\text{rep}}$ 이 모두 0이므로, 영향 범위 밖에서는 반발 포텐셜이 경로에 영향을 미치지 않는다.

3.2 다중 장애물 환경

$N$ 개의 장애물이 존재하는 환경에서 총 반발 포텐셜은 각 장애물에 의한 개별 반발 포텐셜의 합으로 구성된다.

$U_{\text{rep}}(\mathbf{x}) = \sum_{k=1}^{N} U_{\text{rep},k}(\mathbf{x})$

각 장애물 $k$ 에 대해 거리 함수 $d_k(\mathbf{x})$ , 영향 범위 $d_{0,k}$ , 반발 이득 $\eta_k$ 를 독립적으로 설정할 수 있다. 총 반발력은 중첩 원리(superposition principle)에 의해

$\mathbf{F}_{\text{rep}}(\mathbf{x}) = \sum_{k=1}^{N} \mathbf{F}_{\text{rep},k}(\mathbf{x})$

로 결정된다.

4. 경로 생성 알고리즘

포텐셜 필드법에 기반한 경로 생성은 다음의 반복 알고리즘으로 구현된다.

알고리즘: 포텐셜 필드 경로 계획

로봇의 초기 위치 $\mathbf{x}_0$ 와 목표 위치 $\mathbf{x}_g$ 를 설정한다.
수렴 허용 오차 $\epsilon > 0$ 과 최대 반복 횟수 $K_{\max}$ 를 설정한다.
$k = 0, 1, 2, \dots$ 에 대해 반복한다:

총 가상 힘을 계산한다: $\mathbf{F}(\mathbf{x}_k) = -\nabla U(\mathbf{x}_k)$
위치를 갱신한다: $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \dfrac{\mathbf{F}(\mathbf{x}_k)}{\lVert \mathbf{F}(\mathbf{x}_k) \rVert}$
종료 조건을 확인한다: $\lVert \mathbf{x}_{k+1} - \mathbf{x}_g \rVert < \epsilon$ 또는 $k \geq K_{\max}$ 이면 종료한다.

경로 $\{\mathbf{x}_0, \mathbf{x}_1, \dots, \mathbf{x}_K\}$ 를 출력한다.

여기서 $\alpha_k > 0$ 는 보폭(step size)이다. 보폭의 선택은 알고리즘의 수렴 속도와 안전성에 직접적인 영향을 미치며, 장애물에 근접할수록 보폭을 줄이는 적응적 보폭 전략(adaptive step size strategy)이 필요하다.

5. 국소 최소점 문제

5.1 문제의 발생 원리

포텐셜 필드법의 가장 중대한 한계는 목표점이 아닌 위치에서 국소 최소점(local minimum)이 발생할 수 있다는 것이다. 인력과 반발력이 정확히 상쇄되는 점 $\mathbf{x}^* \neq \mathbf{x}_g$ 에서

$\nabla U(\mathbf{x}^*) = \nabla U_{\text{att}}(\mathbf{x}^*) + \nabla U_{\text{rep}}(\mathbf{x}^*) = \mathbf{0}$

이 성립하면, 로봇은 해당 위치에서 정지하게 된다. 이 점이 국소 최소점이 되려면 추가로 헤시안 행렬(Hessian matrix) $\mathbf{H}_U(\mathbf{x}^*)$ 가 양의 반정치(positive semi-definite)여야 한다.

전형적으로 국소 최소점은 로봇이 목표점과 장애물 사이의 직선 경로상에 위치하거나, 다수의 장애물에 의해 둘러싸인 좁은 통로(narrow passage)에서 빈번하게 발생한다.

5.2 국소 최소점 탈출 기법

랜덤 워크(random walk) 기법. 국소 최소점이 감지되면 구면(sphere) $\mathbb{S}^{m-1}$ 위에서 균일하게 추출한 무작위 방향 벡터 $\hat{\mathbf{r}}$ 를 이용하여 교란(perturbation)을 가한다.

$\mathbf{x}_{k+1} = \mathbf{x}_k + \delta \hat{\mathbf{r}}, \quad \hat{\mathbf{r}} \sim \text{Uniform}(\mathbb{S}^{m-1})$

교란 크기 $\delta > 0$ 는 로봇이 국소 최소점의 수렴 분지(basin of attraction)를 탈출할 수 있을 정도로 충분히 커야 하지만, 장애물과 충돌하지 않을 정도로 제한되어야 한다.

가상 목표점(virtual target) 기법. 국소 최소점 근처에 임시 중간 목표점 $\mathbf{x}_v$ 를 배치하여 포텐셜 지형(potential landscape)을 변형한다. 로봇이 가상 목표점에 도달한 후에는 원래 목표점 $\mathbf{x}_g$ 를 향한 포텐셜 필드로 복원한다.

접선 방향 힘(tangential force) 추가. 반발력에 접선 성분을 부가하여 장애물 표면을 따라 이동하도록 유도한다.

$\mathbf{F}_{\text{tangent}} = \mathbf{R}(\theta) \mathbf{F}_{\text{rep}}$

여기서 $\mathbf{R}(\theta)$ 는 반발력 방향을 각도 $\theta$ (통상 $\pm 90°$ )만큼 회전시키는 회전 행렬이다. 이 접선 힘은 국소 최소점에서의 힘 균형을 깨뜨려 로봇이 장애물을 우회하도록 한다.

6. 내비게이션 함수를 이용한 전역 수렴 보장

Rimon과 Koditschek(1992)는 구 세계(sphere world) 환경에서 목표점 $\mathbf{x}_g$ 를 유일한 극소점으로 가지는 내비게이션 함수(navigation function) $\varphi: \mathcal{F} \to [0, 1]$ 를 제안하였다. 내비게이션 함수는 다음 조건을 만족한다.

$\varphi(\mathbf{x}_g) = 0$ 이며, 이것이 자유 공간(free space) $\mathcal{F}$ 내의 유일한 극소점이다.
$\varphi$ 는 $\mathcal{F}$ 의 경계에서 최대값 1을 취한다.
$\varphi$ 는 모스 함수(Morse function)이다. 즉, 모든 임계점에서 헤시안 행렬이 비특이(nonsingular)이다.

구 세계에서의 내비게이션 함수는 다음과 같이 정의된다.

$\varphi(\mathbf{x}) = \frac{\lVert \mathbf{x} - \mathbf{x}_g \rVert^2}{\left( \lVert \mathbf{x} - \mathbf{x}_g \rVert^{2\kappa} + \beta(\mathbf{x}) \right)^{1/\kappa}}$

여기서 $\beta(\mathbf{x}) = \prod_{k=0}^{N} \beta_k(\mathbf{x})$ 는 장애물 함수(obstacle function)의 곱이며, $\beta_k(\mathbf{x}) > 0$ 은 로봇이 $k$ 번째 장애물 내부에 있지 않을 때 양수이다. 매개변수 $\kappa$ 가 충분히 크면 $\varphi$ 의 임계점 중 국소 최소점은 $\mathbf{x}_g$ 뿐이며, 나머지 임계점은 모두 안장점(saddle point)이 되어 전역 수렴이 보장된다.

7. 수정 반발 포텐셜

기존 반발 포텐셜의 국소 최소점 문제를 완화하기 위해, Ge와 Cui(2000)는 목표점까지의 거리를 반발 포텐셜에 결합한 수정 반발 포텐셜(modified repulsive potential)을 제안하였다.

$U_{\text{rep}}^{\text{mod}}(\mathbf{x}) = \begin{cases} \dfrac{1}{2} \eta \left( \dfrac{1}{d(\mathbf{x})} - \dfrac{1}{d_0} \right)^2 \lVert \mathbf{x} - \mathbf{x}_g \rVert^p, & d(\mathbf{x}) \leq d_0 \\[10pt] 0, & d(\mathbf{x}) > d_0 \end{cases}$

여기서 $p > 0$ 는 양의 상수이다. 이 수정에 의해 $\mathbf{x} = \mathbf{x}_g$ 에서 $\lVert \mathbf{x} - \mathbf{x}_g \rVert^p = 0$ 이므로 $U_{\text{rep}}^{\text{mod}}(\mathbf{x}_g) = 0$ 이 되어, 목표점이 반드시 총 포텐셜의 극소점이 된다. 수정 반발 포텐셜의 음의 그래디언트는 두 성분으로 분해된다.

$\mathbf{F}_{\text{rep}}^{\text{mod}}(\mathbf{x}) = \mathbf{F}_{\text{rep},1}(\mathbf{x}) + \mathbf{F}_{\text{rep},2}(\mathbf{x})$

여기서 $\mathbf{F}_{\text{rep},1}$ 은 장애물로부터 밀어내는 성분이고, $\mathbf{F}_{\text{rep},2}$ 는 목표점 방향으로 끌어당기는 성분이다. 이 추가적인 인력 성분이 국소 최소점 형성을 억제한다.

8. 관절 공간에서의 포텐셜 필드법

로봇 매니퓰레이터(manipulator)의 경우, 작업 공간 대신 관절 공간(joint space) $\mathbb{R}^n$ 에서 포텐셜 필드를 정의하는 것이 자연스럽다. 관절 벡터 $\mathbf{q} \in \mathbb{R}^n$ 에 대하여 총 포텐셜을 세 성분으로 구성한다.

$U(\mathbf{q}) = U_{\text{task}}(\mathbf{q}) + U_{\text{obs}}(\mathbf{q}) + U_{\text{joint}}(\mathbf{q})$

작업 포텐셜. 말단 장치(end-effector)의 위치 $\mathbf{f}(\mathbf{q})$ 가 목표 위치 $\mathbf{x}_d$ 에 도달하도록 유도하는 포텐셜이다.

$U_{\text{task}}(\mathbf{q}) = \frac{1}{2} \xi \lVert \mathbf{x}_d - \mathbf{f}(\mathbf{q}) \rVert^2$

관절 공간에서의 그래디언트는 연쇄 법칙(chain rule)에 의해

$\nabla_{\mathbf{q}} U_{\text{task}} = -\xi \mathbf{J}^T(\mathbf{q}) \bigl(\mathbf{x}_d - \mathbf{f}(\mathbf{q})\bigr)$

로 계산된다. 여기서 $\mathbf{J}(\mathbf{q}) = \partial \mathbf{f} / \partial \mathbf{q}$ 는 기하학적 야코비 행렬(geometric Jacobian)이다.

장애물 포텐셜. 작업 공간에서의 장애물 반발 포텐셜을 관절 공간으로 매핑한다.

$\nabla_{\mathbf{q}} U_{\text{obs}} = \mathbf{J}_o^T(\mathbf{q}) \nabla_{\mathbf{x}} U_{\text{rep}}$

여기서 $\mathbf{J}_o(\mathbf{q})$ 는 장애물에 가장 가까운 로봇 표면점에 대한 야코비 행렬이다.

관절 한계 포텐셜. 각 관절 $i$ 에 대해 관절 가동 범위 $[q_{i,\min}, q_{i,\max}]$ 의 한계를 회피하는 포텐셜이다.

$U_{\text{joint}}(\mathbf{q}) = \sum_{i=1}^{n} \frac{\gamma_i}{2} \left( \frac{1}{q_i - q_{i,\min}} + \frac{1}{q_{i,\max} - q_i} \right)$

여기서 $\gamma_i > 0$ 는 이득 계수이다. 이 포텐셜은 관절 값이 가동 범위의 경계에 접근할수록 급격히 증가하여, 관절 한계 위반을 방지한다.

9. 실시간 구현 고려 사항

9.1 계산 효율성

장애물 수 $N$ 이 증가하면 반발력 계산의 복잡도가 $O(N)$ 으로 증가한다. 영향 범위 $d_0$ 밖의 장애물을 배제하는 공간 분할(spatial partitioning) 기법, 예컨대 k-d 트리(k-d tree)나 격자 기반(grid-based) 색인을 적용하면 평균 탐색 복잡도를 $O(\log N)$ 으로 줄일 수 있다.

9.2 장애물 형상 근사

복잡한 형상의 장애물에 대한 정확한 최소 거리 계산은 계산 비용이 높다. 실시간 응용에서는 장애물을 구(sphere), 원통(cylinder), 캡슐(capsule) 등의 원시 기하학(primitive geometry)으로 근사하여 거리 계산을 단순화한다.

9.3 이산화 오차와 보폭 제어

보폭 $\alpha_k$ 가 과도하면 로봇이 한 단계에서 장애물을 관통할 수 있다. 이를 방지하기 위해 적응적 보폭 조절을 적용한다.

$\alpha_k = \min\left(\alpha_{\max},\; \frac{d_{\min}(\mathbf{x}_k)}{2}\right)$

여기서 $d_{\min}(\mathbf{x}_k)$ 는 현재 위치에서 가장 가까운 장애물까지의 거리이다.

9.4 진동 억제

좁은 통로에서 양쪽 장애물의 반발력이 교대로 우세해지면 로봇이 진동(oscillation)할 수 있다. 감쇠 항(damping term)을 도입한 운동 방정식

$\mathbf{M} \ddot{\mathbf{x}} + \mathbf{B} \dot{\mathbf{x}} = -\nabla U(\mathbf{x})$

을 적용하면 진동을 억제할 수 있다. 과감쇠(overdamped) 조건 $\mathbf{B} \gg \mathbf{M}$ 에서는

$\dot{\mathbf{x}} \approx -\mathbf{B}^{-1} \nabla U(\mathbf{x})$

로 근사되어 1차 경사 하강 동역학을 따르게 된다.

10. 포텐셜 필드법의 확장

10.1 조화 포텐셜 함수

조화 포텐셜 함수(harmonic potential function)는 라플라스 방정식(Laplace equation) $\nabla^2 U = 0$ 을 만족하는 포텐셜 함수이다. 조화 함수는 내부에 극소점을 갖지 않는 최대값 원리(maximum principle)를 만족하므로, 적절한 경계 조건하에서 국소 최소점이 존재하지 않는다(Connolly et al., 1990). 그러나 조화 포텐셜의 계산은 편미분 방정식의 수치 해법을 요구하여 실시간 응용에 제약이 있다.

10.2 속도 의존적 포텐셜 필드

동적 환경에서 이동하는 장애물을 회피하기 위해, 장애물의 속도 정보를 반발 포텐셜에 반영하는 속도 의존적 포텐셜 필드(velocity-dependent potential field)가 제안되었다(Ge and Cui, 2002). 장애물의 이동 방향 전방에는 반발력을 증강하고, 후방에는 반발력을 감소시켜 동적 장애물에 대한 효율적인 회피를 가능하게 한다.

11. 참고 문헌

Khatib, O. (1986). “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots.” International Journal of Robotics Research, 5(1), 90–98.
Rimon, E., & Koditschek, D. E. (1992). “Exact Robot Navigation Using Artificial Potential Functions.” IEEE Transactions on Robotics and Automation, 8(5), 501–518.
Ge, S. S., & Cui, Y. J. (2000). “New Potential Functions for Mobile Robot Path Planning.” IEEE Transactions on Robotics and Automation, 16(5), 615–620.
Ge, S. S., & Cui, Y. J. (2002). “Dynamic Motion Planning for Mobile Robots Using Potential Field Method.” Autonomous Robots, 13(3), 207–222.
Connolly, C. I., Burns, J. B., & Weiss, R. (1990). “Path Planning Using Laplace’s Equation.” Proceedings of the IEEE International Conference on Robotics and Automation, 2102–2106.
Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.

v 0.2