Time Optimal Ergodic Search

저자: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023

라이선스

오픈 액세스
논문: CC BY 4.0

아래 내용은 모두 논문의 라이선스(CC BY 4.0)에 따라 논문 전문을 바탕으로 하며, 그림에는 저자를 표기했습니다.

요약

에르고딕 지표에 대한 상한 γ를 조건으로 탐색 시간을 최소화한다: 하나의 파라미터가 커버리지의 철저함을 정하고, 최적화기가 궤적의 지속 시간을 고른다.

중요한 이유

수색 및 구조나 측량 비행에서 운용자는 지속 시간을 추측하는 대신, 탐색이 얼마나 철저해야 하는지를 지정하고 이를 만족하는 가장 빠른 궤적을 얻을 수 있다. 속도 제한이나 장애물 배리어 같은 제약도 같은 최적화 안에 들어가며, 계획된 시간은 실제 쿼드로터에서 1.5 s 이내로 재현되었다.

문제

에르고딕 탐색은 각 영역에 그 정보량에 비례하는 시간을 보내는 연속 궤적을 계획하지만, 기존 방법은 계획 지평을 미리 고정하므로 사용자가 탐색의 철저함과 시간을 맞바꿀 수 없다. 에르고딕 지표를 최소화하면서 시간을 최소화하는 것은 잘 정의되지 않은 문제인데, 궤적은 시간이 무한대로 갈 때에만 완전히 에르고딕해지기 때문이다.

제안 방법

에르고딕 지표는 최소 시간 문제 안의 부등식 제약 E ≤ γ가 되므로, γ가 커버리지의 거칠거나 세밀한 정도를 정하고 최종 시간 tf는 결정 변수가 된다. 저자들은 '확장 에르고딕 상태'를 사용해 Pontryagin 최대 원리로 국소 최적성 조건을 증명한 뒤, 실제로는 N개의 매듭점(Δt = tf/N)에 대한 직접 전사와 자체 증강 라그랑지안 솔버로 문제를 푼다. 장애물은 이산 제어 배리어 함수 제약으로 처리한다.

핵심 통찰

에르고딕성을 목적함수가 아니라 상한으로 다루면 최소 시간 탐색 문제가 잘 정의된다; γ → 0일 때 최적 시간은 한없이 커지며, 이는 에르고딕 이론과 일치한다
봉우리가 4개인 정보 지도에서 γ를 두 자릿수(0.1에서 0.001로) 낮추자 최적 시간이 대략 두 배가 되었으며(9.86 s에서 19.59 s), 거친 계획조차 모든 봉우리를 방문했다
시간으로 정규화한 제어 노력은 궤적이 커버리지와 시간을 맞바꿔야 하는 γ 범위의 중간에서 양 극단보다 높다
매끄러운 초기 추정(선형 보간)은 일관된 해를 주며, 잡음이 있거나 무작위인 초기 궤적은 똑같이 에르고딕하지만 시간이 더 긴 지역 최솟값에 빠진다

주요 결과

2차원 질점의 균일 커버리지: γ를 바꾸면 고정 지평 10 s 에르고딕 궤적(E = 0.007)과 같은 커버리지를 가진 5–10 s 길이의 궤적이 나온다
불균일 정보 지도: 최적 시간은 γ = 0.1에서 9.86 s, γ = 0.001에서 19.59 s
γ = 0.05에서의 민감도: 초기 tf를 4에서 8 s까지 바꾸면 최적 시간은 4.97 ± 0.23 s; 매듭점 수 N을 50에서 600까지 바꾸면 5.45 ± 0.39 s
제어 배리어 함수를 쓴 장애물이 많은 2차원 환경: 최적 시간은 γ = 0.2에서 7.79 s부터 γ = 0.002에서 11.85 s까지이며, 배리어 제약이 궤적을 모든 장애물에서 떨어뜨려 놓았다
γ = 0.1, 0.05, 0.01에서의 드론 실험: 실제 비행 시간은 최적화된 시간과 1.5 s 이내로 차이 났다; Fig. 1의 궤적은 장애물이 많은 영역을 13.5 s에 커버한다
솔버는 무작위 타원체 장애물 사이에서 비선형 3차원 항공기 모델에 대한 균일 커버리지 궤적도 생성했다

한계

저자들은 에르고딕 지표가 매우 비선형이고 비볼록이므로 해가 국소 최적일 뿐이라고 밝힌다
저자들은 Pontryagin 최적성 조건이 긴 지평에서 수치적으로 불안정함을 발견했으며, 그래서 실용적인 솔버는 직접 전사 방법이다
계획은 알려진 장애물을 대상으로 오프라인에서 이루어진다; 저자들은 미지의 장애물과 환경 불확실성 하에서의 실시간 계획을 향후 과제로 꼽는다
결과는 초기 궤적과 N에 따라 달라진다; 필요한 시간이 매우 커지는 아주 작은 γ에서는 솔버가 해를 반환하지 않는다
저자들은 계산 비용이 탐사 공간의 차원에 따라 커진다고 언급한다

분야에 미친 영향

RSS 2023 Best Paper Award 수상작. 저자들은 github.com/ialab-yale/time_optimal_ergodic_search 에 코드를, 그리고 멀티미디어 시연 페이지를 공개한다.

초록

시간과 탐색의 철저함 사이에서 균형을 잡을 수 있는 로봇은 수색 및 구조 같은 응용에서 시간이 중요한 지원을 제공할 잠재력이 있다. 최근 에르고딕 커버리지 기반 탐색 방법의 발전으로 로봇은 정해진 시간 안에 한 영역을 완전히 탐사하고 탐색할 수 있게 되었다. 그러나 자율 에르고딕 탐색의 품질에 대해 시간을 최적화하는 것은 아직 시연된 바 없다. 본 논문에서는 빠르고 적응적인 로봇 탐색 및 탐사를 위해 시간 최적 에르고딕 탐색 문제의 해법을 연구한다. 우리는 이 문제를 상한이 탐색의 세분도와 시간 사이의 균형을 조절하는 에르고딕 부등식 제약을 가진 최소 시간 문제로 정식화한다. 문제의 해는 Pontryagin의 최적성 조건을 사용해 해석적으로 제시하고, 직접 전사(direct transcription) 최적화 접근법으로 수치적으로 시연한다. 우리는 시뮬레이션과 장애물이 많은 환경에서의 드론 실험을 통해 시간 최적 에르고딕 탐색 궤적을 생성하는 이 접근법의 효과를 보인다. 장애물 회피를 우리의 정식화에 쉽게 통합할 수 있음을 보이며, 최적화된 시간에 대한 파라미터 의존성과 탐색 궤적의 민감도를 조사하는 절제 연구를 수행한다.

링크

arXiv 2305.11643: https://arxiv.org/abs/2305.11643
PDF: https://arxiv.org/pdf/2305.11643v1
코드: https://github.com/ialab-yale/time_optimal_ergodic_search
프로젝트 페이지: https://sites.google.com/view/time-optimal-ergodic-search