IV. M ULTI -S TAGE C ONTROL E FFORT M INIMIZATION
- video1: https://www.youtube.com/watch?v=pQ4oSf1rdBU
- vidoe2: https://www.youtube.com/watch?v=QQS0AM3iOmc
- github: https://github.com/ZJU-FAST-Lab/GCOPTER
GitHub - ZJU-FAST-Lab/GCOPTER: A General-Purpose Trajectory Optimizer for Multicopters
A General-Purpose Trajectory Optimizer for Multicopters - GitHub - ZJU-FAST-Lab/GCOPTER: A General-Purpose Trajectory Optimizer for Multicopters
github.com
Abstract 정리
- 본 논문에서는 다중콥터 궤적 계획을 위한 최적화 기반 프레임워크를 제시한다. 이는 기하학적 구성 제약과 사용자 정의 동적 제약을 고려한 것이다. 이 프레임워크의 기반은 제약이 없는 제어 노력 최소화를 위한 (for unconstrained control effort minimization) 새로운 최적성 조건에 기반한 새로운 궤적 표현이다. 우리는 이 표현에 선형 복잡도 작업(linear-complexity
operations)을 설계하여 다양한 계획 요구 사항에 따른 시공간 변형을 수행(spatial-temporal deformation)한다. Smooth maps are utilized to exactly eliminate geometrical constraints in a lightweight fashion. 다양한 상태-입력 제약은 밀집된 제약 평가와 희소한 매개변수화의 분리, 그리고 평탄도 맵의 역방향 차별화에 의해 지원된다 (variety of state-input constraints are supported by the decoupling of dense constraint evaluation from sparse parameterization, and backward differentiation of flatness map.) 결과적으로, 이 프레임워크는 일반적으로 제약된 다중콥터 계획 문제를 신뢰성 있고 효율적으로 해결할 수 있는 비제약 최적화로 변환한다. 우리의 프레임워크는 제한된 자원과 기동 능력을 가진 다중콥터의 솔루션 품질, 계획 효율성, 그리고 제약 충실도 사이의 격차를 해소한다. 그 일반성과 강인함은 다양한 비행 작업에의 적용을 통해 입증되었다. 광범위한 시뮬레이션과 벤치마킹 또한 전문화된 다른 방법들에 비해 수백 배의 계산 속도를 유지하면서 고품질 솔루션을 생성하는 능력을 보여주기 위해 수행되었다. 우리 프레임워크의 소스 코드는 https://github.com/ZJU-FAST-Lab/GCOPTER에서 이용할 수 있다.
이해 안가는 부분들
- linear-complexity operations? -> spatial-temporal deformation?
- smooth map? 을 이용하여 geometrical constraints를 제거한다?
- dense constraint evaluation from sparse parametriazation (이거는 LU factorization을 의미 하는 것 같음.)
- backward differentiaion of flatness map? 이 두가지로 variety of state-input constraints가 supported 된다??
Introduction 정리
- 다중로터(멀티콥터)는 복잡한 환경에서 안전하면서도 민첩한 자율 비행을 위해 견고하고 효율적인 궤적 계획을 의존합니다. 로봇 공학 분야에서는 역학, 부드러움 및 안전성을 정확하게 통합하는 것이 고품질의 움직임을 생성하는 데 필수적입니다. 또한, 크기, 무게 및 전원(SWaP) 제약 사항 하에서의 다중로터와 같은 경량 로봇은 제한된 기기 내 자원을 사용하여 실시간 계산에 대한 더 강력한 요구 사항을 제시합니다. 일반적인 키노다이나믹(운동역학) 계획이나 최적 제어에 성공한 도구들이 다양하게 제안되었지만, 그중에서도 다중로터의 역학에 대한 일반 제약 조건을 고려하면서도 효율적인 온라인 계획을 보장하는 도구는 거의 없습니다. 그 결과, 기존 응용 프로그램은 계산 효율성을 높이기 위해 궤적에 대한 과도한 간소화된 요구 사항을 사용하므로 차량 능력의 전체 활용이 제한됩니다. (기존 방법의 단점)
위에서 언급한 고성능 계획은 네 가지 주요 알고리즘적 도전 과제를 가지고 있습니다. 첫째, 안전성을 보장하기 위해서는 자주 높은 해상도의 환경 데이터와 상호 작용이 필요합니다. (Real-time property) 둘째, 차량 역학의 비선형성은 다중로터가 능력 한계에 도달할 때 물리적으로 허용 가능한 상태와 입력을 직접 강제하는 데 어려움을 초래합니다. 셋째, 고품질의 움직임을 위해서는 업무 자원에 대한 요구 사항이 비현실적으로 미세하게 이산화되어야 하며, 네 번째로 궤적에 대한 희소 표현을 사용하는 방법은 연속 시간 제약을 만족하면서 시간 프로필을 최적화하는 효과적인 방법이 없습니다. - 본 논문에서는 이러한 도전 과제를 극복하기 위해 사용자 정의 요구 사항을 충족시키기 위한 가벼운 및 유연한 최적화 프레임워크를 설계합니다. 이 프레임워크의 이론적 기반으로 우리는 관련된 선형 역학에 대한 다단계 제어 노력 최소화에 대한 필수 및 충분한 최적성 조건을 제시합니다. 이 조건은 시간 및 공간 측면 모두에서 선형 복잡성으로 고유한 최적해를 직접 구성할 수 있는 사용이 쉽습니다. 더 중요한 것은 이러한 조건의 존재와 고유성이 문제 매개 변수 민감도의 부드러움에 대한 중요한 정보를 제공합니다.
궤적 품질을 희생하지 않고 계산 부담을 줄이기 위해서는 다중로터 역학에 적합한 희소 매개 변수화를 사용하는 것이 중요합니다. 따라서 우리는 최적성 조건을 기반으로 한 새로운 궤적 클래스를 설계합니다. 이 클래스의 어떤 요소든 기본적으로 제약이 없는 제어 노력 최소화자이므로 이를 MINCO(최소 제어)라고 명명합니다. MINCO는 주로 기하학적 모양의 부드러움에 중점을 둔 기존 스플라인인 B-스플라인 및 베지에 곡선과 다릅니다. 그것의 희소 매개 변수는 궤적의 공간 및 시간 프로필을 직접 제어하기 위해 설계되었으며, 이 두 가지는 동적 적합성에 있어 동등한 중요성을 가집니다. 또한, 공간-시간 변형 방법도 설계되어 MINCO가 사용자 정의 목표에 맞게 최적화될 수 있도록 합니다.
우리의 프레임워크는 샘플링 기반 또는 검색 기반 글로벌 방법의 결과를 기반으로 저차원 자유 공간의 기하학적 근사를 활용합니다. 안전성은 장애물이 없는 볼록한 기본 형태의 구성 제약 조건을 통해 보장됩니다. 제약 조건 제거 스키마가 제안되어 MINCO가 제약 조건을 자유롭게 변형할 수 있도록 합니다. (이 스키마가 핵심!) 이러한 스키마는 의사 결정 변수에 직접 정의된 제약 조건을 정확하게 제거하여 extra local minima을 도입하지 않습니다.
신뢰할 수 있는 움직임 계획은 허용 가능한 상태와 입력을 필요로 하지만 대부분의 기존 플래트니스(Flatness) 기반 방법은 미분 제약 조건만 지원합니다. 고품질의 실행 가능성을 보장하기 위해 우리는 경로의 미세한 이산화 없이도 희소 매개 변수화에 사용자 정의 상태-입력 제약 조건을 강제하는 체계적인 방법을 제안합니다(?). 우리는 플래트니스 맵의 역방향 미분(?)을 활용하여 제약 조건 위반을 희소 매개 변수에 대한 그래디언트에 반영할 수 있습니다. 또한, 연속 시간 제약을 강제하기 위한 미분 가능한 패널티 기능도 제안됩니다.
우리의 프레임워크는 복잡한 안전 제약 조건, 역학의 중요한 한계 및 작업 지정 요구 사항이 있는 다중로터에 대한 계산적으로 효율적이면서도 고품질의 궤적 계획에 중점을 두고 있습니다. 이의 효과를 검증하기 위해 우리는 다양한 최첨단 다중로터 궤적 계획 방법에 대한 광범위한 벤치마크를 수행합니다. 결과는 우리의 방법이 효율성에서 기존 방법을 대폭 능가하며, 일반 목적 최적 제어 해결사에 대비하여 비슷한 해결책 품질을 유지함을 보여줍니다. 또한 우리는 다양한 시뮬레이션과 극한의 실제 비행을 통해 우리 접근 방식의 실제 성능을 보여줍니다.
중요 Points
- lightweight and flexible optimization framework 제시
- 이를 위해 필수 충분한 optimality conditions 제시
- MINCO는 b-spline과 bezier curve와는 다르다.
- 제약 조건을 제거하는 스키마가 제안 되었다. 이를 통하여 제약 조건을 자유롭게 변형 가능.
Related Works 정리
- 기존 문헌에서는 다중로터의 대규모 시간적으로 중요한 궤적 계획을 수행하면서 상태 및 제어에 대한 사용자 정의 연속 시간 제약을 통합한 완전한 프레임워크가 아직 나오지 않았습니다. 우리의 프레임워크는 최적 제어와 모션 계획의 서로 다른 능력을 탐색하고 활용함으로써 이 간극을 줄입니다.
A. Differentially Flat Multicopters
미분 플랫성의 개념은 Fliess 등에 의해 소개되었으며 로봇 궤적 계획에서 큰 관심을 받고 있습니다. 이 속성은 유한한 미분값에서 평면 출력의 전체 상태와 입력을 복구하는 것이 가능하게 합니다. Mellinger와 Kumar는 정렬된 프로펠러를 가진 쿼드콥터의 플랫성을 검증하였으며, 이는 추력과 3차원 토크를 입력으로 취합니다. Watterson과 Kumar는 쿼드콥터 회전을 분해하기 위해 Hopf 피브레이션을 사용하여 플랫 맵에서 최소한의 특이점 수를 달성합니다. Ferrin 등은 원하는 방향과 추력을 입력으로 취하는 헥사콥터의 플랫성을 보여줍니다. 그들은 플랫성을 활용하여 선형 제곱 레귤레이터(LQR)를 적용하는 정상 상태를 계산합니다. Faessler 등은 추가적인 선형 가속도와 각 가속도를 생성하는 선형 저항을 고려합니다. 그들은 드래그 효과에 따라 병렬 로터 다중로터의 플랫성을 보여줍니다. 뿐만 아니라 Mu와 Chirarattananon은 기울어진 프로펠러를 가진 무행동 다중로터를 조사합니다. 그들은 입력 순위 조건이 충족되는 한 광범위한 범위의 트리콥터, 쿼드콥터 및 헥사콥터에 대해 플랫성이 성립한다는 것을 증명합니다.
다중로터의 플랫성이 성립하는 경우, 미분 방정식을 통합하지 않고 참조 상태와 입력을 얻는 궤적 생성 및 추적 제어에 이점이 있습니다. 위에서 언급한 문헌은 계획 중에 시스템 역학을 직면하지 않도록 플랫성을 사용합니다. 그러나 실제 물리적 시스템의 역학은 합리적인 상태와 허용 가능한 입력에 대해서만 유효합니다. (기존 방법론의 한계점) 우리의 프레임워크도 플랫성 특성을 활용하지만, 이전 연구와는 달리 상태-입력 제약 조건의 일반적 형태를 공식적으로 지원합니다 (이 논문의 장점).
B. Sampling-Based Motion Planning
샘플링 기반 모션 계획자는 환경으로부터 발생하는 복잡성이 주로 구성 공간에서 기인하는 문제의 전역 솔루션에 중점을 둡니다. 확률적 로드맵 (PRM) 및 빠르게 탐색하는 무작위 트리 (RRT)은 무작위 샘플 수가 무한대로 갈 때 실패 확률이 지수적으로 감소하므로 확률적으로 완전합니다. Karaman과 Frazzoli는 PRM 및 RRT의 점진적으로 최적화된 변형인 PRM* 및 RRT*를 제안하였으며, 샘플 수가 무한대로 갈 때 전역 최적 솔루션으로 수렴하는 것을 보장합니다. 확률적 모션 계획의 효율성 또는 적용 가능성을 더 개선하는 알고리즘들도 있습니다. 우리의 방법은 환경으로부터 발생하는 복잡성을 극복하기 위해 sampling-based planners를 활용합니다. 이는 주어진 저차원 충돌 없는 경로에 homotopic 다중 로터 동적으로 실행 가능한 궤적을 최적화합니다. 이는 시스템 상태-입력 제약 조건을 유연하게 통합하기 위해 설계되었으며, 이는 샘플링 기반 방법의 강점이 아닙니다. 이렇게 함으로써 환경과 동역학의 복잡성을 나눠서 처리합니다.
C. Optimization-Based Motion Planning
최적화 기반 계획자는 문제의 고차 정보를 사용하여 로컬 솔루션에 중점을 둡니다. 이들은 최적화에 장애물 정보가 인코딩되도록 특정 환경 전처리 방법에 의존합니다. 일반적으로 최적 경로 계획은 제어 커뮤니티에서 일반 시스템에 대해 오랫동안 연구되어 왔습니다. 고품질의 솔루션을 위해 GPOPS-II와 같은 열 형식 기반 방법 및 ACADO와 같은 슈팅 기반 방법과 같은 많은 범용 방법이 개발되었습니다. 이들은 원래 문제를 비선형 프로그래밍 (NLP)으로 변환하고 많은 등식과 변수를 사용하여 NLP 솔버 (SNOPT 또는 IPOPT와 같은)로 돌아가도록 합니다. 그러나 로봇 과학에서의 궤적 계획은 공식으로 정의하기 어려운 제약 조건, 부드러움 및 정수 변수를 가할 수 있습니다. 게다가, general-purpose methods은 종종 시간이 오래 걸려 시간이 중요한 작업에 적합하지 않습니다. 예를 들어 Bry 등은 직접 콜로케이션 (DC)과 SNOPT를 사용하여 실린더 모양 장애물 사이를 비행하는 12 상태 비행기의 4.5m 궤적을 최적화하는 데 몇 분이 걸린다고 보고하였습니다. 따라서 이러한 어려움을 극복하기 위해 전문화된 방법이 필요합니다. (기존 방법의 단점)
미분 플랫 다중로터의 경우, 모션 계획은 평면 출력의 저차원 궤적의 최적화로 변환될 수 있습니다. Mellinger와 Kumar는 쿼드콥터 궤적을 나타내기 위해 고정 기간 스플라인을 사용합니다. 스냅의 이차 비용과 안전성의 선형 제약 조건을 포함하는 이차 프로그래밍 (QP)이 고안되었습니다. 그러나 시간 할당의 그래디언트를 추정하기 위해 유한 차분에서 발생하는 변동 문제를 해결해야 합니다. 또한, 그의 액추에이터 제약 조건은 과도하게 단순화되어 있습니다. Bry 등은 안전 제약 조건 없이 이 QP의 닫힌 형태 솔루션을 제안합니다. 그들은 RRT*의 충돌 없는 경로에서 웨이 포인트를 추정적으로 추가하여 안전성이 충족될 때까지 솔루션을 다시 계산합니다. 이 방법은 효율적일 수 있지만 장애물이 많은 환경에서 고품질 솔루션을 보장할 수 없습니다. 게다가, 행렬의 역을 포함하는데, 이 행렬의 비특이성은 결코 논의되지 않습니다. Deits와 Tedrake는 폴리톱을 사용하여 자유 공간을 근사화합니다. 각 궤적 조각의 안전성은 폴리톱 내부에 완전히 위치한 경우 Sum-of-Square (SOS) 조건과 동등합니다. 그들은 혼합 정수 2차원 원뿔 프로그래밍 (MISOCP)을 사용하여 간격 할당을 해결합니다. 이것은 전역 최적 궤적을 생성하지만 계산 시간이 허용되지 않습니다. Gao 등도 폴리헤드론 모양의 자유 공간 표현을 사용합니다. 그들은 궤적의 기하학적 및 시간적 프로필을 번갈아 최적화합니다. 안전은 Bézier 곡선의 convex-hull property에 의해 강제되며, 동적 프로필은 Time-Optimal Path Parameterization (TOPP)을 통해 최적화됩니다. 위의 방법들을 개선하기 위한 변형 방법들도 있습니다. 예를 들어, Tordesillas 등은 다항식의 SOS 조건을 Bézier 곡선의 선형 제약 조건으로 대체하여 [30]의 효율성을 개선합니다. Sun 등은 민감도를 활용하여 시간 할당을 최적화하기 때문에 정수 변수를 피합니다.
이러한 특수화된 방법들은 세부 이산화에 대한 계산 부담을 피하기 위해 연속 시간 궤적 매개 변수화를 활용합니다. 그러나 they do not support flexibly optimizing its time allocation 하거나 제약 조건의 시간 분해를 의사 결정 변수 차원에서 분리하거나 도함수 정규화에 대한 제약 조건을 강화하는 기능을 지원하지 않습니다. (기존 방법들의 단점) 이 논문에서는 이러한 기능을 모두 지원하기 위해 새로운 희소 매개 변수화에 대한 통합된 기술을 소개합니다. 또한, 솔루션 품질은 범용 최적 제어 솔루션과 유사합니다.
Methodology 정리
PRELIMINARIES
A. Differential Flatness
- 위의 그림에서 $\Psi_{u}, \Psi_{x}$ 는 mapping 함수이다.
- 왼쪽 그림은 state-input이 $\dot{x}=f(x)+g(x)u$ 와 같은 동역학 방정식으로 표현되어 있으며 $G_D(x,u) \preceq 0$ 의 제약 조건은 red 영역을 나타낸다. mapping 함수인 $\Psi_{u}, \Psi_{x}$ 에 의해서 오른쪽 flat-output space로 변형되며 제약 조건도 $G(z, \dot{z}, \cdots, z^{(s)}) \preceq 0$으로 변형된다.
- flat output $z$ 를 이용하여 적절한 mapping 함수인 $\Psi_{u}, \Psi_{x}$ 와 함께 system state $x$ 와 input state $u$ 를 표현할 수 있다. 즉, flatness property를 가지고 있다는 의미.
새로운 control variable인 $v=z^{(s)}$를 소개하여 $i$-th integrator chain을 표현한다. integrator chain 이란 입력 신호를 연속적으로 적분하여 다음 상태를 생성하는 일련의 적분기들로 구성됩니다. 예를 들어, 어떤 시스템의 출력이 제어 입력의 두 번째 미분, 즉 가속도에 의존한다고 가정해 보겠습니다. 이 경우에는 두 개의 적분기를 연속적으로 배치하여 첫 번째 적분기가 속도를, 두 번째 적분기가 위치를 출력하도록 모델링할 수 있습니다. 이를 통해 초기 입력(가속도)이 시간에 따라 어떻게 위치로 통합되는지를 파악할 수 있습니다. 따라서, 여기에서 initial staet와 goal state가 주어진다면, (5)를 통해 boundary values(?)을 수학적으로 계산 할 수 있습니다.
B. Direct Optimization in Flat-Output Space
Differential flatness은 멀티콥터가 물리적으로 의미 있는 flat-output space을 가지며, 이 공간이 구성 공간과 중첩된다는 것이 잘 연구되어 입증되었습니다. 평탄 출력의 명시적 형태는 다양한 미약동력(mildly actuated) 멀티콥터에 대해 문헌 [11]-[14]에서 찾아볼 수 있습니다. 더 중요한 것은, 이들 flat-output이 일반적인 형태를 공유한다는 것입니다:
\[ z = (p_x, p_y, p_z, \psi)^T \] (6)
여기서 \( (p_x, p_y, p_z)^T \)는 중력 중심(Center of Gravity, CoG)의 변환을, \( \psi \)는 차량의 요 각도를 나타냅니다. flat-output \( z \)는, 특히 이동, 회전 및 복잡한 공간 제약 조건을 가진 멀티콥터 모션 계획에 매우 유용합니다.
멀티콥터에 대한 실행 가능한 동작을 생성하기 위해, 먼저 flat-output space에서 시간 \( T \)에 대해 \( z(t) : [0, T] \rightarrow \mathbb{R}^m \)의 궤적을 최적화하여 대부분의 공간 제약 조건이 직접 적용되도록 합니다. 그런 다음, 평탄성 맵 \( \Psi_x \)와 \( \Psi_u \)를 사용하여 \( z(t) \)를 상태-입력 궤적 \( x(t) \)와 \( u(t) \)로 변환합니다.
동작의 매끄러움을 위해, 제곱 제어 노력(quadratic control effort)과 시간 정규화를 궤적의 비용 함수로 사용합니다. 일반적으로 구성 제약 조건과 사용자 정의 동적 제약 조건으로 분류될 수 있습니다. 보통 충돌이 없는 동작은 다음과 같이 의미합니다:
\[ z(t) \in F, \forall t \in [0, T] \] (7)
여기서 \( F \)는 구성 공간에서의 관심 있는 장애물이 없는 영역입니다. 또한, 사용자 정의 상태-입력 제약 조건들은 액츄에이터 한계나 작업 특정 제약 조건들로 표시되며, 다음과 같이 나타낼 수 있습니다:
\[ G_D(x(t), u(t)) \leq 0, \forall t \in [0, T] \] (8)
\( \Psi_x \)와 \( \Psi_u \)를 활용하여, \( z(t) \)에 대한 해당 제약 조건들이 계산됩니다:
\[ G_D(\Psi_x(z^{[s-1]}(t)), \Psi_u(z^{[s]}(t))) \leq 0, \forall t \in [0, T] \] (9)
명백하게, flatness을 통해서 \( x \)와 \( u \)에 대한 제약 조건은 \( z(t) \)의 유한 미분에 대한 등가형으로 가질 수 있습니다. 단순화를 위해, 이후에 (9)를 다음과 같이 표시합니다:
\[ G(z(t), \dot{z}(t), ..., z^{(s)}(t)) \leq 0, \forall t \in [0, T] \] (10)
여기서 \( G \)는 \( n_g \)개의 equivalent constraints로 구성됩니다.
멀티콥터 동력학과 flatness 맵에 대한 추가적인 가정을 하지 않는다는 점을 주목할 가치가 있습니다. 다시 말해, 제안된 프레임워크는 [11]-[15]에 언급된 것을 포함하여 다양한 범위의 멀티콥터를 지원합니다.
C. Problem Formulation
IV. MULTI-STAGE CONTROL EFFORT MINIMIZATION
A. Unconstrained Control Effort Minimization
B. Optimality Conditions
증명. 필요성의 증명은 정리 1에서 직접 도출된 (33)부터 (44)까지의 조건들에 의해 명백하다. 충분성의 증명은 아래와 같이 개략적으로 설명된다: (a) 첫 번째와 네 번째 조건들은 항상 \( d_i \) 의 어떤 수열에 대해서도 차원이 \( 2s + \sum_{i=1}^{M-1} d_i - 1 \) 인 선형 스플라인 공간을 결정한다; (b) 두 번째와 세 번째 조건들은 정사각형 계수 행렬을 기반으로 하는 스플라인 공간을 형성한다; (c) 행렬은 각 \( i \)에 대해 \( t_{i-1} < t_i \) 이므로 nonsingular하며, 이는 해의 존재와 유일성을 의미한다; (정사각행렬이 nonsinular 하기 때문에 해가 유일하다.) (d) 필요 조건들의 존재와 유일성은 그들의 충분성을 내포한다. 이 충분성 증명은 부록 A에 상세히 설명되어 있다. □
최적 조건을 더 설명하기 위해서, 우리는 여러 단계의 저크 최소화를 예로 든다. 이 예에서, 위치, 속도, 가속도는 저크 제어된 시스템의 상태이며 \( s = 3 \) 이다. 상태의 연속성은 최소 저크 궤적의 가속도까지만 요구하며, 최적 궤적의 저크와 스냅도 모든 곳에서 연속이다. 따라서 우리가 이 모든 연속성 조건들을 강제한다면, 연속성 2는 원하는 모든 시점을 통과해야 하는 궤적을 생성한다는 것을 암시한다. 그리고 만약 우리가 이 모든 연속성 조건들을 강제한다면, 유일하게 존재하는 것이 바로 최적의 해이다.
C. Minimization Without Cost Functional
Experiments 정리
