(AD) Obstacle Avoidance - APF

Artificial Potential Field

개요 및 구성

• Artificial Potential Field(APF)는 로봇이나 자율주행 차량의 장애물 회피(Obstacle Avoidance)를 위해 가상의 힘을 정의하는 경로 계획 기법이다.
• APF는 일반적으로 전역 경로 계획(Global Path Planner)과 함께 사용하는 지역 장애물 회피(Local Path Planner) 로 활용된다.
• APF는 로봇을 전하를 띤 입자로, 목표를 음극으로, 장애물을 양극으로 비유하여 인력과 척력의 개념을 이용해 장애물을 회피하면서 목표로 향하는 방향을 계산하는 방법이다.

• APF에서는 환경을 하나의 가상 에너지장으로 표현한다.
  • 목표 지점(Goal) : 낮은 퍼텐셜(Potential Well)을 형성하여 차량을 목표 방향으로 유도
  • 장애물(Obstacle) : 높은 퍼텐셜(Potential Hill)을 형성하여 차량이 접근하지 못하도록 유도
  • 차량(Robot/Vehicle) : 퍼텐셜의 기울기(Gradient)에 의해 결정되는 힘을 따라 이동

---

APF 방법

• APF 에서 전체 Potantial 함수는 일반적으로 다음과 같이 정의된다.

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

• $\mathbf{q}$ : 차량의 위치 벡터

• $U_{att}$ : 목표 지점의 인력 Potential

• $U_{rep}$ : 창애물의 척력 Potential

• 차량에 작용하는 가상 힘은 Potential 함수의 음의 기울기(Gradient)로 정의된다.

$$F(\mathbf{q})=-\nabla U(\mathbf{q})=-\nabla U_{att}(\mathbf{q})-\nabla U_{rep}(\mathbf{q})$$ $$\Rightarrow \mathbf{F}={\mathbf{F}}_{att}+{\mathbf{F}}_{rep}$$

• 차량은 최종적으로 합력 $\mathbf{F}$ 의 방향으로 이동하게 된다.

1. Attractive Potential

Attractive Potential Energy

• Attractive Potential Energy(인력 퍼텐셜 에너지)는 차량이 목표 지점으로 이동하도록 유도하는 에너지장으로, 목표 지점에 가까워질수록 퍼텐셜 에너지가 감소하도록 정의하며, 차량은 에너지가 감소하는 방향으로 이동하게 된다.
• 차량의 위치를 $\mathbf{q}$ , 목표 위치를 ${\mathbf{q}}_{\text{goal}}$라고 할 때,

$$\mathbf{q}=\left[\begin{array}{c}x\\ y\end{array}\right],{\mathbf{q}}_{\text{goal}}=\left[\begin{array}{c}{x}_g\\ y_g\end{array}\right]$$

• 인력 퍼텐셜 에너지 함수는 다음과 같이 정의된다.

$$U_{att}(\mathbf{q})=\frac{1}{2}{K}_{att}||\mathbf{q}-{\mathbf{q}}_{\text{goal}}|{|}^2$$

• $K_{att}>0$ : 인력 계수 (Attractive Gain)
• $||\mathbf{q}-{\mathbf{q}}_{\text{goal}}||$ : 차량과 목표 지점 사이의 거리
• 미분의 편의를 위해 $\frac{1}{2}$를 곱함

Attractive Force

• 인력 ${\mathbf{F}}_{att}$은 퍼텐셜 함수의 음의 그래디언트로 정의된다.

$${\mathbf{F}}_{att}=-\nabla U_{att}$$ $${\mathbf{F}}_{att}=-K_{att}(\mathbf{q}-{\mathbf{q}}_{\text{goal}})$$

• 즉, 차량에서 목표 지점을 향하는 방향의 힘이 발생하며, 목표와 멀리 떨어질수록 힘의 크기가 커진다.

2. Repulsive Potential

Repulsive Potential Energy

• Repulsive Potential Energy(척력 퍼텐셜 에너지)는 차량이 장애물에 접근하지 못하도록 밀어내는 가상의 퍼텐셜 에너지장이다.
• 차량의 위치를 $\mathbf{q}$, 장애물 위치를 ${\mathbf{q}}_{\text{obs}}$라고 할 때, 차량과 장애물 사이의 거리를 아래와 같이 표현한다.

$$\rho (\mathbf{q})=||\mathbf{q}-{\mathbf{q}}_{\text{obs}}||$$

• 척력 퍼텐셜 에너지 함수는 장애물 주변 일정 거리 이내에서만 작용하도록 다음과 같이 정의된다.

$$U_{rep}(\mathbf{q})=\{\begin{array}{ll}\frac{1}{2}{K}_{rep}{\left(\frac{1}{\rho (\mathbf{q})}-\frac{1}{{\rho }_0}\right)}^2,& \rho (\mathbf{q})\le {\rho }_0\\ 0,& \rho (\mathbf{q})>{\rho }_0\end{array}$$

• $K_{rep}>0$ : 척력 계수 (Repulsive Gain)
• ${\rho }_0$ : 장애물 영향 반경 (Infulence Distance)

Repulsive Force

• 척력 ${\mathbf{F}}_{rep}$는 퍼텐셜 함수의 음의 그래디언트로 정의된다.

$${\mathbf{F}}_{rep}=-\nabla U_{rep}$$ $$\begin{array}{rl}\nabla U_{rep}& =-K_{rep}\left(\frac{1}{\rho }-\frac{1}{{\rho }_0}\right)\frac{1}{{\rho }^2}\nabla \rho \end{array}$$ $$\nabla \rho =\frac{q-q_{\text{obs}}}{\rho }$$ $${\mathbf{F}}_{rep}=\{\begin{array}{ll}{K}_{rep}\left(\frac{1}{\rho }-\frac{1}{{\rho }_0}\right)\frac{1}{{\rho }^2}\frac{\mathbf{q}-{\mathbf{q}}_{\text{obs}}}{\rho },& \rho \le {\rho }_0\\ 0,& \rho >{\rho }_0\end{array}$$

• 즉, 척력은 장애물에 가까워질수록 급격히 증가하고, 영향 반경 밖에서는 척력이 0이 된다.

3. Artificial Potential Field

• 최종 Potential과 차량에 작용하는 힘 $\mathbf{F}$는 인력과 척력의 합으로 정의된다.

$$\mathbf{F}={\mathbf{F}}_{att}+{\mathbf{F}}_{rep}$$ $$\mathbf{F}=\left[\begin{array}{c}{F}_x\\ F_y\end{array}\right]$$

• 차량의 목표 진행 방향은 다음과 같이 결정할 수 있다.

$$\theta ={\tan }^{-1}\left(\frac{F_y}{F_x}\right)$$

---

APF 예시

상황

• 차량 위치 $\mathbf{q}$, 목표 위치 ${\mathbf{q}}_{\text{goal}}$, 장애물 위치 ${\mathbf{q}}_{\text{obs}}$를 다음과 같이 설정한다.

$$\begin{array}{rl}\mathbf{q}& =(4,0)\\ {\mathbf{q}}_{\text{goal}}& =(10,0)\\ {\mathbf{q}}_{\text{obs}}& =(5,1)\end{array}$$

Attractive Force 계산

• Attractive Gain $K_{att}$를 1이라고 할 때, 인력은 다음과 같이 계산된다.

$${\mathbf{F}}_{att}=-1(4-10,0-0)=\left[\begin{array}{c}6\\ 0\end{array}\right]$$

• 차량이 목표 지점 방향으로 이동하려 한다.

Repulsive Force 계산

• Repulsive Gain $K_{rep}=30$, ${\rho }_0=3$ 이라 할때, 척력 계산은 아래와 같다.

$$\rho =\sqrt{(4-5{)}^2+(0-1{)}^2}\approx 1.41$$ $$\mathbf{q}-{\mathbf{q}}_{\text{obs}}=(-1,-1)$$ $${\mathbf{F}}_{rep}=30\left(\frac{1}{1.41}-\frac{1}{3}\right)\frac{1}{1.41^3}(\mathbf{q}-{\mathbf{q}}_{\text{obs}})$$ $${\mathbf{F}}_{rep}\approx 4(-1,-1)=\left[\begin{array}{c}-4\\ -4\end{array}\right]$$

최종 Force 계산

• 인력과 척력을 합한 최종 힘 벡터 $\mathbf{F}$는 다음과 같다.

$$\mathbf{F}={\mathbf{F}}_{att}+{\mathbf{F}}_{rep}=\left[\begin{array}{c}6\\ 0\end{array}\right]+\left[\begin{array}{c}-4\\ -4\end{array}\right]=\left[\begin{array}{c}2\\ -4\end{array}\right]$$

• 따라서, 최종 진행 방향의 조향각 $\theta$는 다음과 같다.

$$\theta ={\tan }^{-1}\left(-\frac{4}{2}\right)\approx -63°$$

---

APF 한계

Local Minimum

• 장애물 배치에 따라 인력과 척력이 정확히 상쇄되어 Local Minimum에 빠질 수 있다.
• 이 문제를 해결하기 위해 랜덤 워크, 가상 장애물, 내비게이션 함수 등 여러 변형이 제안되었다.

Oscillations

• 여러개의 장애물이 존재하거나 좁은 공간에서 진동이 발생하고, 로봇의 불안정한 움직임을 초례한다.

---

참고

• 1-2. APF — 인공 포텐셜 필드 - 로봇 시뮬레이션
• Artificial Potential Field
• Robot Motion Planning - Artificial Potential Field Method - YouTube
• Predictive Artificial Potential Field algorithm - energy-efficient local path planning algorithm - YouTube
• PythonRobotics/PathPlanning/PotentialFieldPlanning/potential_field_planning.py at master · AtsushiSakai/PythonRobotics · GitHub
• (AD) Obstacle Avoidance - DWA