(AD) Obstacle Avoidance - DWA

Dynamic Window Approach

개요

• Dynamic Window Approach(DWA) 는 로봇의 경로 계획과 충돌 회피를 위해 사용되는 대표적인 지역 경로 계획(Local Path Planning) 알고리즘으로, 로봇의 현재 동적 제약(최대 속도, 가속도 등)을 고려하여 다음 시간 스텝 동안 도달 가능한 속도 공간(Velocity Space : Dynamic Window)을 정의한다.
• 속도 공간 내에서 여러 궤적을 예측하고, 목표 지점 도달, 장애물 회피, 속도 유지 등의 평가 함수를 통해 최적의 궤적을 선택하여 로봇을 제어한다.
• 위치 공간(Position Space)이 아닌 속도 공간에서 미래 궤적을 예측하여, 차량의 운동학적 및 동역학적 제약을 직접 고려할 수 있다.

---

Dynamic Window

• Dynamic Window는 차량이 다음 제어 주기 $\Delta t$ 동안 실제로 만들어낼 수 있는 모든 속도 명령의 집합(=속도 공간)을 말하며, 2차원 이동 로봇에서 속도의 상태는 선속도 $v$ 와 각속도 $\omega$ 로 정의할 수 있다.
• 이때 로봇의 물리적 속도 한계를 고려하여 현재 차량의 상태(속도)에서 실제로 도달 가능한 영역(Window)만 탐색하는 것이 핵심이다.
• 세로축, 가로축 : 선속도 $v$와 각속도 $\omega$
• $V_d$ : Dynamic Window - 현재 속도에서 제어 주기($\Delta t$) 동안 차량이 실제로 도달 가능한 속도 집합
• $V_s$ : Velocity Space - 차량이 구조적으로 가질 수 있는 모든 속도의 집합
• $V_a$ : Admissible Velocity - 허용 가능한 속도 집합 (현재 속도에서주행하다가 최대 제동을 했을 때 장애물과 충돌하기 전에 완전히 정지할 수 있는 속도들의 집합)
• $V_r$ : Reachable Velocity - $V_d,V_s,V_a$를 모두 고려하여 실제로 탐색할 후보 집합

Velocity Space

• 차량 자체가 낼 수 있는 모든 속도의 집합.

$$V_s=\{(v,\omega )|V_{min}\le v\le V_{max},W_{min}\le \omega \le W_{max}\}$$

• $V_{max},V_{min}$ : 차량의 최대, 최소 선속도
• $W_{max},W_{min}$ : 차량의 최대, 최소 각속도 (좌회전, 우회전)

Dynamic Window

• 현재 속도에서 차량의 가속도 한계를 고려했을 때 다음 제어 주기 내에 실제로 도달 가능한 속도들의 집합.

$$V_d=\left\{\begin{array}{cc}(v,\omega )& \begin{array}{r}v\in [v_c+{\dot{v}}_{min}\Delta t,v_c+{\dot{v}}_{max}\Delta t]\\ \omega \in [{\omega }_c+{\dot{\omega }}_{min}\Delta t,{\omega }_c+{\dot{\omega }}_{max}\Delta t]\end{array}\end{array}\right\}$$

• $v_c,{\omega }_c$ : 현재 차량의 선속도, 각속도
• ${\dot{v}}_{max},{\dot{v}}_{min}$ : 차량의 최대, 최소 선가속도
• ${\dot{\omega }}_{max},{\dot{\omega }}_{min}$ : 차량의 최대, 최소 각가속도

선속도 범위

$$v_c+{\dot{v}}_{min}\Delta t\le v\le v_c+{\dot{v}}_{max}\Delta t$$

• 차량의 현재 속도가 $1.0m/s$ , 최대 가속도가 $0.5m/s^2$, 최소 각가속도(=최대 감속도)가 $-0.8m/s^2$ 일 때, 제어주기 $\Delta t=0.1s$ 에서 가능한 선속도 범위는 아래와 같다.

$$1.0-0.8\times 0.1\le v\le 1.0+0.5\times 0.1$$ $$0.92\le v\le 1.05$$

각속도 범위

$${\omega }_c+{\dot{\omega }}_{min}\Delta t\le \omega \le {\omega }_c+{\dot{\omega }}_{max}\Delta t$$

• 차량의 현재 각속도가 $0.2rad/s$, 최대 각가속도가 $1.0rad/s^2$, 최소 각가속도(=최대 각감속도)가 $-1.0rad/s^2$ 일 때, 제어주기 $\Delta t=0.1s$ 에서 가능한 선속도 범위는 아래와 같다.

$$0.2-1.0\times 0.1\le \omega \le 0.2+1.0\times 0.1$$ $$0.1\le \omega \le 0.3$$

Admissible Velocity

• Velocity Space에서 장애물과 충돌하기 전에 차량이 완전히 정지할 수 있는 안전한 속도들의 집합.
• 제동거리는 현재 속도에서 최대 감속(최대 제동)을 했을 때 차량이 완전히 정지하기까지 이동하는 거리를 말하며, 등가속도 운동식을 이용해 제동거리 $d_{stop}$은 아래와 같이 정의한다.

$$d_{stop}=\frac{v^2}{2a_b}=\frac{v^2}{2|{\dot{v}}_{min}|}$$

• 여기서 $a_b$ 는 최대 감속도를 말하며 $|{\dot{v}}_{min}|$과 같다.

$$V_a=\{(v,\omega )|d(v,\omega )\ge d_{stop}\}$$

• $d(v,\omega )$ : 후보 속도로 생성한 예측 미래 궤적 상에서 가장 가까운 장애물까지의 거리

Reachable Velocity

• 성능 제한, 동역학적 제약, 안정성 제약을 모두 만족하는 최종 후보 속도 집합으로, DWA는 이 영역에서 후보 속도를 샘플링하여 최적의 속도를 선택한다.

$$V_r=V_s\cap V_d\cap V_a$$

---

Trajectory Generation

• DWA는 모든 후보 속도 $(v,\omega )\in V_r$에 대하여 각 후보 속도에 대한 이동 궤적(Trajectory)를 예측한다.
• 생성된 궤적은 차량의 운동학 모델을 수치적으로 적분하여 계산되며, 일정한 선속도와 각속도를 유지하므로 일반적으로 원호(Circular Arc) 형태를 갖는다.
• $V_r$은 연속적인 집합이므로 실제 구현에서는 일정 간격으로 샘플링(discretization)하여 값을 추출한다.

Trajectory using Kinematic Model

• DWA는 differential drive robot을 대상으로 제안되었기 때문에 다음과 같이 Kinematic Model의 단순화된 식을 이용한다.

$$\begin{array}{rl}\dot{x}& =v\cos \theta \\ \dot{y}& =v\sin \theta \\ \dot{\theta }& =\omega \end{array}$$

• 이렇게 구한 차량의 위치 변화를 수치 적분(Numerical Integration)하여 궤적을 생성한다.

$$\begin{array}{rl}& x_{i+1}=x_i+v\cos {\theta }_i\Delta t\\ & y_{i+1}=y_i+v\sin {\theta }_i\Delta t\\ & {\theta }_{i+1}={\theta }_i+\omega \Delta t\end{array}$$

• 이때, 예측하고자 하는 궤적의 총 시간 $T$ 와 샘플링 시간 $\Delta t$ 에 따라 총 적분 step 수가 정해진다.
• 예를 들어 총 시간이 3초, 샘플링 간격이 0.1초라면 30개의 점들로 궤적이 구성된다.

Circular Arc

• 후보 속도는 예측시간 $T$ 동안 일정하므로, 이렇게 구한 궤적들은 모두 원호(Circular Arc)의 형태를 가진다.
• 이때 원호의 반지름 $R$은 다음과 같다.

$$R=\frac{v}{\omega }$$

---

Objective Function

• 따라서, DWA는 각 후보 속도 및 궤적에 대해 여러 평가 기준을 적용하여 목적 함수로 정의하고, 후보 $V_r$ 집합에서 제어입력 쌍 $v,\omega$를 샘플링하여 목적 함수 $G(v,\omega )$가 최대가 되는 $(v,\omega )$를 도출한다.

목적 함수 정의

• DWA의 목적 함수는 다음과 같이 정의한다.

$$G(v,\omega )=\alpha Heading(v,\omega )+\beta Dis\tan ce(v,\omega )+\gamma Velocity(v)$$ $$(v^{\ast },{\omega }^{\ast })=\arg \max G(v,\omega ),(v,\omega )\in V_r$$

• $Heading(v,\omega )$ : 목표 방향과 얼마나 일치하는가
• $Distnace(v,\omega )$ : 장애물과 얼마나 떨어져 있는가
• $Velocity(v)$ : 속도가 빠를수록 높은 점수
• $\alpha ,\beta ,\gamma$ : 각 평가 함수의 가중치

Heading Evaluation

• Trajectory의 최종 위치가 목표점을 얼마나 바라보는가를 평가한다.
• Trajectory 생성을 통해 후보 속도 $(v,\omega )$에 대한 Trajectory의 마지막 점의 위치를 $P_f=(x_f,y_f)$, 목표 점을 $P_g=(x_g,y_g)$라고 하면 마지막 점이 목표를 가리키는 방향 ${\theta }_g$는 다음과 같다.

$${\theta }_g={\tan }^{-1}\left(\frac{y_g-y_f}{x_g-x_f}\right)$$

• Heading Error는 다음과 같다.

$$e_{\theta }=|{\theta }_g-{\theta }_f|$$

• Heading Score는 error를 정규화하여 사용할 수 있다.

$$H=1-\frac{e_{\theta }}{\pi }$$

• 따라서, 만약 Trajectory의 마지막 점이 목표를 정화하게 바라보아 Heading Error $e_{\theta }$가 0이 되면 Heading Score $H$는 최대값인 1이 된다.

Clearance Evaluation

• Clearance는 Trajectory가 장애물과 얼마나 안전한 거리를 유지하는지를 평가한다.
• 하나의 Trajectory를 구성하는 모든 점들에 대해, 각 점에서 장애물까지의 거리를 계산하고 그 중 가장 작은 거리값을 구한다.

$$\mathbf{Trajectory}(\mathbf{P})=\{P_1,P_2,\dots ,P_f\}$$ $$d_i=\text{distance}(P_i,P_g)$$ $$d_{min}=\underset{i}{\min }{d}_i$$

• 이 값을 아래와 같이 정규화하여 Clearance Score로 사용한다.

$$C=\frac{d_{min}}{D_{max}}$$

• 이때, 일반적으로 $D_{max}$는 모든 후보 Trajectory의 모든 점들에 대한 $d_{min}$ 값 중 가장 큰 값을 의미한다.
• 따라서, 만약 장애물과 거리가 멀수록 $d_{min}$ 값이 증가하므로 장애물을 최대한 회피하는 경로라고 할 수 있다.

Velocity Evaluation

• 목표 위치까지 빠르게 이동하도록 유도하기 위해, 후보 속도의 선속도 $v$를 다음과 같이 정규화하여 Velocity Score로 사용한다.

$$V=\frac{v}{V_{max}}$$

• 이때, 일반적으로 $V_{max}$는 전체 후보 속도 중 가장 큰 선속도 값을 의미한다.

Weight Parameters

• DWA의 목적함수에 사용되는 각 평가항목의 가중치 $\alpha ,\beta ,\gamma$에 대하여 다음과 같이 해석할 수 있다.

$$G(v,\omega )=\alpha Heading(v,\omega )+\beta Dis\tan ce(v,\omega )+\gamma Velocity(v)$$

• $\alpha$ : 커질수록 목표 방향을 우선한다.
• $\beta$ : 커질수록 장애물에서 멀리 떨어진다.
• $\gamma$ : 커질수록 빠르게 이동한다.
• 일반적으로 가중치를 모두 합하여 1이 되도록 구성한다.

Trajectory Selection

• 모든 후보속도에 대한 Trajectory를 대상으로 목적함수를 이용해 점수를 계산한다.
• 점수가 가장 높은 Trajectory를 최종 제어입력 $(v,\omega )$로 선택한다.
• 이러한 Trajectory를 선택하는 과정은 매 제어주기($\Delta t$) 또는 설정한 주기마다 반복하여 계산함으로써 로봇이 실시간으로 장애물을 피하며 주행할 수 있게 한다.

---

DWA 한계

• 지역 최적해 문제 (Local Minimum): 일반적으로는 DWA가 APF보다 Local Minimum 문제에 더 강하지만, U자 형태의 장애물 등에서 빠져나오지 못하는 문제가 발생할 수 있다.
• 예측 기간의 의존성 (Prediction Horizon): 예측 Trajectory의 시간이 길어질수록 더 안정적이지만, 구성하는 점의 수가 증가하여 계산량이 증가한다. 예측 성능과 계산량 사이의 적절한 균형이 요구된다.
• 파라미터 튜닝의 어려움 (Parameter Tuning): 목적 함수의 가중치 설정에 따라 주행 특성이 크게 달라지므로, 적절한 파라미터를 선택하는 과정이 매우 중요하다. 강화학습을 통해 가중치를 결정하는 알고리즘 등이 연구되고 있다.
• 동적 장애물 처리의 한계 (Dynamic Obstacle Handling): 예측 불가능하게 움직이는 동적 장애물에 대한 효과적인 회피 능력이 제한적이다. 이후 많은 DWA 관련 연구에서 Dynamic Obstacle 의 움직임을 예측 및 반영하여 Trajectory를 계산하는 방식으로 진화하였다.

---

참고

• Fox, D., Burgard, W., & Thrun, S. (1997). The dynamic window approach to collision avoidance.pdf
• [AD] DWA(Dynamic Window Approach) 알고리즘 설명 및 개선 과정
• Dynamic Window Approach Tutorial - YouTube
• (AD) Obstacle Avoidance - APF
• How a robot can be autonomous | Yusuf Butt posted on the topic | LinkedIn