Robot planning and control method based on improved time elastic band algorithm 논문 리뷰

안녕하십니까. KROAD 5기 조윤서입니다.

저는 이번에 2023년 6월 1일 IEEE에 등재된 논문인 “Robot planning and control method based on improved time elastic band algorithm”을 리뷰 하겠습니다. 해당 논문은 Chaojie Liu, Yang Liu가 작성하였습니다.

판단은 차량의 경로를 실시간으로 판단하고 계획하는 파트입니다. 지금보다 동적인 상황에 더 잘 대처할 수 있는 최적의 알고리즘으로 경로를 계획하고자 다양한 경로 계획 기법들을 비교 분석하고 있습니다. 그 중 대표적인 것이 Timed Elastic Band(TEB)입니다. 본 논문에서는 기존의 TEB가 갖고 있는 문제점들을 해결한 ‘향상된 TEB’를 제시하고 있습니다. 이를 이용하여 경로를 계획하면 빠르고 유연한 경로를 생성할 수 있어 본 연구회의 자율차에 적용하기 위해 해당 논문을 리뷰하게 되었습니다.

1. 배경 지식

• Elastic Band

  Elastic Band Method(EBM)이란 인공적인 힘을 받은 탄성 밴드(Elastic Band)를 통해 실시간으로 장애물을 확인하여 경로를 생성하는 알고리즘입니다. 전역 경로 계획을 기반으로 짧고 부드러운 지역 경로를 변형 버블에 근거하여 효율적으로 구현합니다.

Elastic Band의 특징은 다음 표와 같습니다.

[표 1 ] - Elastic Band Method의 장단점

• TEB(Timed Elastic Band)

  표 1에서 나타난 바와 같은 Elastic Band의 문제점을 보완하기 위해 나온 것이 TEB(Timed Elastic Band) 알고리즘입니다. Timed Elastic Band는 (현재 위치 점, 다음 위치 점까지 걸리는 시간) 순서쌍의 집합을 감지된 제약 조건에 따라 경로를 지역적으로 변형하는 방식입니다. 변형하는 과정에서 초기 위치와 목표 위치는 고정됩니다.

TEB는 이러한 방식을 통해서 기존 Elastic Band의 단점 중 많은 부분을 개선했지만 여전히 복잡한 환경에서 계획이 느리고 동적 효과가 떨어진다는 단점이 있습니다.

• RANSAC(Random Sampling Consensus)

  RANSAC은 데이터를 random하게 sampling 하여 사용하고자 하는 모델을 fitting 시키는 방법입니다. RANSAC은 outlier에 강건한 모델을 만들 수 있습니다.

outlier은 관측된 데이터들 중 분포에서 크게 벗어나는 데이터로 이상치를 얘기합니다. outlier에 해당되지 않는 값들은 inlier라고 합니다.

2. 논문의 배경

기존의 Timed Elastic Band는 실제로 제어할 때 동적 장애물 회피 효과가 좋지 않고, 제어량이 급변하며, 운영이 불안정한 문제들이 있습니다. 본 논문은 이러한 문제점을 해결하기 위해 작성되었으며, RANSAC을 이용해 비선형 최적화 문제를 해결함으로써 기존 TEB보다 계산량을 줄이고 제어량을 최적화 했습니다.

3. 상세 내용

TEB의 목표는 제약조건에 맞게 최적화된 경로를 생성하는 것입니다. 이 제약조건은 최적화 목표에 따라 다양하게 설정할 수 있습니다. 본 논문에서는 경로 추적, 장애물 회피, 선형 속도, 선형 각속도, 선형 가속도, 선형 각가속도에 대해 제약조건을 설정하고 패널티 함수를 부여했습니다.

TEB의 목적 함수는 희소 시스템 행렬을 행성합니다. 이를 그래프 최적화를 통하면 다음과 같은 그래프가 완성됩니다.

출처 : Robot planning and control method based on improved time elastic band algorithm

위치와 시간 시퀀스를 그래프 최적화의 node로 설정하고 각 node는 제약조건 패널티 함수라는 edge로 연결되었습니다.

TEB 목적 함수의 설정이 완료되었다면 RANSAC을 이용해 그 성능을 향상시킬 수 있습니다. 향상된 TEB는 다음과 같은 알고리즘으로 동작합니다.

1) 모델의 최소 샘플 수를 무작위로 선택한다.

2) 샘플 집합을 사용하여 모델의 매개변수를 계산한다.

3) 나머지 데이터들을 모델에 대입하고 이들이 모델로부터 떨어진 거리를 계산한다. 거리가 미리 정해진 임계값보다 작으면 inlier로 분류하고, 아니면 outlier로 분류한다.

4) inlier 데이터의 개수를 세고 이를 기반으로 최적의 모델을 유지하며 inlier 데이터 수의 최대값을 업데이트한다.

5) 수렴하거나 반복이 끝날 때까지 1-4단계를 반복한다.

이를 통해 최적화된 경로 point 순서를 얻을 수 있습니다.

향상된 TEB를 통해 얻은 경로에 따라 차량을 제어하는 프로세스는 다음과 같이 이루어집니다.

출처 : Robot planning and control method based on improved time elastic band algorithm

4. 결과

본 논문에서는 시뮬레이션 테스트와 실차 테스트, 총 두 번의 실험을 진행합니다. 각 테스트에 따른 결과는 다음과 같습니다.

가) 시뮬레이션 테스트

다익스트라 알고리즘과 향상된 TEB 알고리즘에 대해 시뮬레이션 테스트를 진행했습니다. 시뮬레이션을 통해 각 알고리즘이 생성한 경로를 보면 같은 전역 경로에 대해 다익스트라 알고리즘은 굉장히 짧은 화살표의 지역 경로들을 여럿 생성하는 것을 확인할 수 있습니다.

반면에 odometer의 실시간 경로 추적 제어 효과 시각화 결과를 토대로 향상된 TEB가 생성한 경로를 보면 긴 화살표 군집의 궤적으로 이루어져 있음을 확인할 수 있습니다. 또한 급격하게 꺾이는 부분 없이 굉장히 부드럽게 경로 추종이 이루어짐을 알 수 있습니다.

나) 실차 테스트

전통적 TEB와 향상된 TEB에 대해 각각 실차 테스트를 진행하고, 속도와 각속도에 대한 제어량을 측정했습니다. 각각에 대한 제어량의 변동 정도를 표로 나타내면 다음과 같습니다.

[표 2 ] - 전통적 TEB와 향상된 TEB에 대한 속도 및 각속도 분산 비교분석

향상된 TEB가 전통적 TEB보다 제어량의 변동이 작음을 확인할 수 있습니다.

5. 이러한 결과가 나온 이유

시뮬레이션 및 실차 테스트에 사용된 알고리즘은 다익스트라 알고리즘, 전통적 TEB, 향상된 TEB입니다.

다익스트라 알고리즘은 시작점을 중심으로 원을 넓혀가며 목적지에 도달할 때까지 노드를 추가해 확장합니다. 이후 목적지에 도착할 때까지 방문하지 않은 노드들 중 최소 거리를 가진 노드를 방문해가면서 경로를 계획하는 방식입니다. 노드들에 대해서 지역 경로를 생성하기 때문에 짧고 딱딱한 경로가 여럿 생성됩니다.

전통적 TEB는 경로 상의 모든 점 중 장애물과의 거리가 가장 가까운 점들과 이웃한 점들의 집합을 이용하여 경로를 생성합니다. 그러므로 초기 경로 계획시 노이즈가 포함될 경우 필터링하기 어렵습니다. 또한 초기 경로가 고정되어 있기 때문에 동적이고 복잡한 환경에서 제대로 된 경로를 생성하기 어렵습니다.

반면 향상된 TEB는 RANSAC을 이용하여 경로 생성에 사용할 점들의 집합을 얻습니다. RANSAC은 랜덤으로 선택된 점들을 전체 데이터와 비교하며 outlier 여부를 평가하기 때문에 노이즈나 outlier를 잘 필터링 할 수 있습니다. 또한 이러한 과정을 여러번 반복하여 진행하기 때문에 최적해에 더욱 근접한 최적의 모델을 찾을 수 있습니다.

즉, TEB는 상대적으로 경로에 노이즈와 이상치가 적어 추종 시 불필요한 경로 변동을 일으키지 않습니다. 또한 최적의 모델을 찾기 때문에 다른 알고리즘보다 자연스럽고 부드러운 경로를 생성합니다. 이 때문에 추종 시 다익스트라보다 향상된 TEB가 더욱 부드러운 궤적을 그리며 추종하게되는 것이고, 전통적 TEB보다 향상된 TEB를 사용했을 때 차량의 속도와 각속도가 부드럽게 변하는 것입니다.

6. 연구에 적용할 수 있는 부분

본 논문에서 제시한 향상된 TEB를 통해 정확하고 부드러운 경로를 생성할 수 있음을 알았으므로 이를 본 연구회 내 자율차의 경로 계획에 적용해 볼 가치가 있을 것입니다. 그러나 본 경로 계획이 RRT*나 DWA와 같은 다른 경로 계획에 비해 우수한 지에 대해서는 가시화 된 결과로 나와 있는 바가 없으므로 직접 실험을 해 보고 각 알고리즘이 생성하는 경로의 부드러움 정도와 생성 속도를 비교 분석해보아야 할 것입니다. 특히 DWA와의 비교 분석에 집중할 예정입니다. 현재 가장 유력하게 사용할 경로 계획법일 뿐더러 논문 초반에 DWA보다 향상된 TEB가 성능이 좋다고 말한 바 있지만 논문이 발표되고 나서 이후로도 DWA에 대한 성능 향상이 계속해서 진행되어 왔기 때문입니다. 그러므로 현재 시점에서 나와있는 DWA가 향상된 TEB보다 우수한지 주의 깊게 살펴봐야 할 필요성이 있습니다.

또한 본 논문에서는 동적 장애물을 이용하여 실험을 진행하지는 않았는데, 저희의 경로 계획 목표 중에는 동적 장애물에도 유연하게 대처하는 것이 있으므로 향상된 TEB에 대해 동적 장애물에 대해서도 실험을 진행해 볼 것입니다. 천천히 움직이는 동적 장애물부터 갑자기 빠르게 나타나는 동적 장애물(길고양이 등)에 대해 얼마나 빠르게 반응하는지를 중점적으로 실험해볼 것입니다.

TEB에 사용되는 각 패널티 함수에 얼마만큼의 가중치를 줄 것인지도 역시 실험을 통해 반복해서 수정해가며 저희의 주행 상황에 제일 맞는 가중치를 부여할 예정입니다.