[AD] TEB(Timed-Elastic-Bands) 알고리즘 설명

Author: Joonhee Lim
Date: 2022/08/27

출처: https://ieeexplore.ieee.org/document/6309484

---

0. Motivation

방금 전 포스팅한 DWA 알고리즘처럼 Local Path Planning 알고리즘에 대해서 알아보다가 발견하게 된 TEB이다. 사실 DWA에 대한 내용을 정리하고 내가 하는 연구에 학습 기반 방법이나 Rule-Based 방법과 결합하여 사용해보면 괜찮을 것 같다라는 생각을 했는데 TEB는 뭐지란 생각이 들어서 정리하게 되었다.(사실 DWA 알고리즘을 주로 사용한다고 들었었는데 왜 TEB보다 DWA가 뛰어난지에 대해서도 알아보겠다.)

 

아 또한 지역 경로 계획을 위해서는 전역 경로 계획이 필요한데 대부분의 알고리즘들은 A* 알고리즘을 이용한다고 명시되어 있었다.

---

1. Timed-Elastic-Bands

TEB는 시간, 장애물, 역학 제약 등을 고려해서 최적의 지역 경로를 만든다. TEB가 제안하는 로봇 동작 시스템은 다음과 같다.

TEB는 x,y 좌표와 방향을 포함한 Pose의 집합을 따르는 시스템이다. 이러한 Pose들과 시간 간격들을 Tuple로 묶어 정의한다.

Key Idea는 DWA와 마찬가지로 목적함수를 최적화하는데 있다. TEB의 목적함수와 그에 따른 최적의 B는 다음과 같다.

TEB 또한 최소 거리와 가장 빠른 경로를 목적으로 두기 때문에 다음과 같은 목적함수로 표현된다.

 

다음과 같은 Penalty 함수로 현실적인 상황에서 제약 조건의 위반이 다른 목적 함수보다 훨씬 높은 페널티를 부과하도록 정의한다.

$x_r$: bound

$S, n, \epsilon$ : Scailing, 차수, 근사치의 작은 Translation

 

Path와 Obstacle에 대한 목적함수는 다음과 같다.

$d_{min}$: 가장 가까운 way point 또는 장애물과의 거리

$r_{p_{max}}$: maximal target radius

$r_{o_{mim}}$: minimal distance(Obstacle)

 

Non-holonomic kinematics에 대한 목적함수는 다음과 같다.

다음과 같은 함수로 Non-holonomic한 옴직임에 대해 페널티를 가한다.

 

Fastest Path에 대한 목적함수는 다음과 같다.

시간 간격의 총합을 통해 가장 빠른 Path를 형성하도록 한다.

 

결론적으로 다음과 같은 사항들을 고려하여 시간 간격과 x, y, 방향의 집합을 만들어내어 제어하는 것 같다. 각 위치로 가는 속도는 다음과 같다.