Autonomous Driving

[AD] DWA(Dynamic Window Approach) 알고리즘 설명 및 개선 과정

진정한남자준희 2022. 8. 27. 14:06
728x90

Author: Joonhee Lim
Date: 2022/08/27

출처: https://jkimst.org/journal/view.php?doi=10.9766/KIMST.2021.24.1.061


0. Motivation

다양한 Path Planning에 대한 기존 알고리즘을 공부하던 도중 Local 경로 계획 알고리즘 DWA를 발견하게 되어 간단하게 정리해보고자 한다. 필자가 사용하는 ROS 환경에서도 자주 사용하는 알고리즘이라고 하니 어떻게 굴러가는지 확인해보자

 

또한 추가적으로 설명하자면 Path Planning은 Global Path Planning과 Local Path Planning으로 나뉘어지는데 Global Path Planning이란 자율 이동체가 목적지를 향해 출발하기에 앞서, 주어진 환경 지도를 바탕으로 목적지까지의 전체 이동 경로를 계획하는 것이고, Local Path Planning은 예기치 못한 장애물을 회피하기 위해 전역 경로를 크게 벗어나지 않으면서 안전하게 회피 경로를 계획하는 것이다.


1. Dynamic Window Approach

DWA는 평면 상의 로봇을 제어하기 위한 Local Path Planning 알고리즘으로 Ego의 속도, 방향 및 장애물과의 거리를 토대로 최적의 선속도와 각속도를 도출하여 장애물을 회피하고 목적지에 도달하는 방법이다. DWA는 적은 연산량을 통한 빠른 수행속도(Real time)의 장점을 가지고 있다. 다만 기존의 DWA은 전역 경로선에 대한 추종을 고려하지 않기 때문에 충돌 회피 기동 이후 경로선에서 벗어난 운항을 할 수 있다.

DWA 알고리즘은 현재 차량의 속도에서 다음 시간까지 취할 수 있는 선속도와 각속도의 입력 범위를 나타내는 Dynamic Window를 생성하고 해당 영역 안 선속도와 각속도 쌍 (V, W) 중에 목적함수의 값이 최대가 되는 목표 선속도와 각속도의 쌍을 도출한다.

해당 그림에서

$V_d$ 영역은 다음 Time step까지 취할 수 있는 선속도와 가속도의 영역을 나타낸 것이며(작은 네모) 다음과 같은 수식으로 표현할 수 있다.

$V_s$ 영역은 차량이 위치한 공간 내에 취할 수 있는 최대, 최소 영역이며(최대 or 최소 속도로 주행 시)

$V_a$ 는 차량의 현재 속도에서 장애물과 충돌하지 않고 제동 가능한 속도 범위이다

최종적으로 3개의 영역의 교집합에 해당하는 영역 $V_r$ 내의 제어 입력을 사용한다. 

해당 영역에서 가능한 V, W 조합은 DWA 알고리즘의 목적함수에 대입되어 목적함수가 최대가 되는 (V, W) 쌍을 차량의 목표 선속도와 각속도로 결정한다.

 

각각 Heading은 차량의 방향, Clearance는 충돌, Velocity는 속도에 관련된 함수이고 앞에 붙은 계수는 가중치이다.

Heading: 제어 입력 시 선박과 목표점과의 방향 차이

Clearance: 차량에서 가장 가까운 장애물과의 거리

Velocity: 제어 입력 이후의 속도

 

다음과 같이 구성된 목적함수를 사용하게 되면 장애물은 회피할 수 있게 되지만 앞서 말한 경로선 추종에 대한 문제가 발생하게 된다.


2. Advanced Dynamic Window Approach

차량이 충돌 회피 이후에도 경로선 추종을 위해 차량의 위치와 경로선과의 거리를 평가하는 $d_{line}$의 등장으로 점차 해결되었다. 변경된 목적함수는 다음과 같다.

이 때 추가된 k는 장애물 감지 유무에 대한 계수로 감지 시 1, 비 감지 시 0이다. 또한 해당 가중치 값들을 통해 경로 최적화가 되기 때문에 가중치를 신중하게 잘 결정해주어야 한다. 현재는 해당 가중치를 RL을 통해 결정하는 알고리즘까지 나와있는 상태이다.

 

강화학습 기반 알고리즘에서는 k 파라미터를 다음과 같이 수정하였고

목적함수는 다음과 같이 정의하였다.

또한 간단하게 다음과 같은 RL 알고리즘을 구성하여 최고의 주행을 선보일 수 있는 파라미터들을 결정하였다.

지금까지 충돌 회피 지역 경로 계획 알고리즘인 DWA에 대해 알아보았다. 짱짱맨

반응형