(AD) Obstacle Avoidance - TEB

Time Elastic Band

개요

• Time Elastic Band(TEB)는 로봇의 지역 경로 계획(Local Path Planning) 및 충돌 회피를 위한 최적화 기반 알고리즘으로, DWA와 마찬가지로 로봇의 현재 위치에서 목표 지점까지의 최적 궤적(Trajectory) 을 실시간으로 생성한다.
• TEB는 로봇의 궤적을 시간적으로 연결된 일련의 포즈(poses)들로 구성된 “탄성 밴드(Elastic Band)“로 표현하고, 이 밴드를 최적화하여 로봇의 동적 제약, 장애물 회피, 목표 지점 도달, 그리고 시간 효율성을 동시에 고려한 최적의 궤적을 찾는다.
• 특히, 궤적의 각 포즈 사이의 시간 간격까지 최적화함으로써, 단순히 공간적인 경로뿐만 아니라 시간적인 측면까지 고려한 동적 궤적을 생성하는 것이 특징이다.

주요특징

• APF : 힘(Potential)을 이용하여 장애물을 회피
• DWA : 속도 공간(Velocity Space)에서 안전한 속도를 선택
• TEB : 위치와 시간을 고려하여 Trajectory 자체를 최적화
  • TEB는 예측 구간 전체를 최적화 하므로 DWA에 비해 상대적으로 계산량이 크다.
  • Global Path를 초기 Trajectory(초기 추정값)로 사용하면서 Cost Function에도 반영한다.

---

TEB 방법

TEB의 궤적 표현 (Trajectory Representation)

• TEB는 이동 로봇의 이동 경로를 단순한 좌표의 나열이 아니라 시간 정보가 포함된 궤적(Timed Trajectory) 으로 표현한다.
• 일반적인 경로는 $\mathbf{P}$ 처럼 표현하지만, TEB에서 하나의 Trajectory $\mathbf{B}$는 다음과 같이 정의된다.

$$\mathbf{P}=\{{\mathbf{p}}_0,{\mathbf{p}}_1,\dots ,{\mathbf{p}}_n\}$$ $$\mathbf{B}=({\mathbf{s}}_0,\Delta T_0,{\mathbf{s}}_1,\Delta T_1,\dots ,{\mathbf{s}}_n)$$

• ${\mathbf{s}}_i$ : $i$ 번째 Pose
• $\Delta T$ : 두 Pose 사이의 이동시간
• 즉, 위치와 시간 $\{{\mathbf{s}}_i,\Delta T_i\}$을 동시에 최적화 하는 것이 TEB 방법의 핵심이다.

Pose Sequence

• 차량(이동 로봇)의 상태는 일반적으로 아래와 같이 표현된다.

$${\mathbf{s}}_i=(x_i,y_i,{\theta }_i)$$ $$\text{Pose Sequence}:{\mathbf{s}}_0\to {\mathbf{s}}_1\to \cdots \to {\mathbf{s}}_n$$

• $x_i,y_i$ : 위치

• ${\theta }_i$ : 헤딩 각도

• TEB에서 Trajectory는 이러한 Pose Sequence로 구성되며, Global Planner가 생성한 Global Path가 초기 Pose Sequence가 된다.

• 이후 최적화 과정에서는 각 Pose가 자유롭게 이동하며 더 좋은 Trajectory를 찾는다.

Time Intervals

• Pose 사이에는 시간 간격 $\Delta T$가 존재하며 아래와 같이 표현한다.

$$\Delta T_i=t_{t+1}-t_i$$

• 따라서 선속도 $v$와 각속도 $\omega$는 다음과 같이 계산할 수 있다.

$$v_i=\frac{||{\mathbf{P}}_{i+1}-{\mathbf{P}}_i||}{\Delta T_i}$$ $${\omega }_i=\frac{{\theta }_{i+1}-{\theta }_i}{\Delta T_i}$$

• TEB는 모든 로봇이 궤적을 완료하는 데 걸리는 총 시간 $T_{all}={\sum }_{i=0}^{N-1}\Delta T_i$ 을 최소화하는 방향으로 궤적을 최적화한다.

TEB 최적화 (TEB Optimization)

• 궤적을 구성하는 포즈 시퀀스와 시간 간격들을 조정하여, 여러 목적 함수(Objective Function)를 최소화하고 동시에 다양한 제약 조건(Constraints)을 만족시키는 최적의 궤적을 찾는 과정이다.

목적 함수 (Objective Function)

• TEB의 목적 함수는 아래와 같이 여러개의 목표를 최소화하도록 구성되어 있다.

제약 조건 (Constraints)

목적 함수 구성 요소 (Components of the Objective Function)

경로 길이 및 시간 최소화 (Path Length & Time Minimization)

장애물 회피 (Obstacle Avoidance)

로봇 동적 제약 (Robot Dynamics Constraints)

전역 경로 추종 (Global Path Following)

궤적의 부드러움 (Trajectory Smoothness)

최적화 과정 (Optimization Process)

TEB의 장점 (Advantages of TEB)

TEB의 한계 (Limitations of TEB)

---

참고

• [AD] DWA(Dynamic Window Approach) vs TEB(Timed-Elastic-Band) 알고리즘 비교
• [AD] TEB(Timed-Elastic-Bands) 알고리즘 설명
• Collision Avoidance Reliability Analysis of the Timed Elastic Band Method For Autonomous Navigation - YouTube
• Trajectory modification considering dynamic constraintsof autonomous robots
• TEB Planner Trajectory modification considering dynamic constraints of autonomous robots [ROBOTIK 2012].pdf