기술 요약: TinySDP

문제 제기

동적 환경에서의 안전한 운동 계획 및 제어는 로봇공학, 특히 리소스가 제한된 임베디드 시스템에서 여전히 중요한 과제로 남아 있습니다. 모델 예측 제어 (MPC) 는 시스템 동역학과 제약을 추론하는 데 효과적이지만, 실시간으로 비볼록 장애물 회피에 대한 형식적 안전 보장을 부과하는 것은 어렵습니다. 기존 접근법은 종종 보수적인 과대 근사 (예: 선형화된 거리 제약) 나 전역 기하학적 구조를 포착하지 못하는 국소 볼록화에 의존합니다. 이러한 방법들은 좁은 통로, 막다른 길, 또는 동적 장애물이 포함된 시나리오에서 실패하기 쉬우며, 종종 로봇의 유효 발자국을 팽창시키는 안전 마진의 광범위한 휴리스틱 튜닝을 요구합니다. 반면, 반정규 프로그래밍 (SDP) 은 리프팅을 통해 비볼록 기하학적 제약을 볼록화하는 원칙적인 프레임워크를 제공하지만, 범용 SDP 솔버는 계산 비용이 많이 들고 메모리 집약적이어서 마이크로컨트롤러에서의 실시간 후퇴 시간 제어에는 적합하지 않습니다.

방법론

저자들은 실시간으로 검증 가능한 장애물 회피를 가능하게 하는 임베디드 시스템을 위해 설계된 최초의 반정규 프로그래밍 솔버인 TinySDP를 소개합니다. 이 접근법은 세 가지 핵심 요소를 통합합니다:

1. 구조화된 리프팅 및 완화

TinySDP 는 비볼록, 2 차, 원형 기반 장애물 회피 제약을 단계별, 볼록, 반정규 완화로 구성된 MPC 문제를 공식화합니다.

• 리프팅: 이 방법은 기하학적 상태 (예: 평면 위치 $p_k$) 를 고차원의 양의 반정규 (PSD) 원뿔로 리프팅합니다. 구체적으로, 상태와 입력의 외적에 대한 보조 변수 (예: $X_k = x_k x_k^\top$) 를 도입합니다.
• 선형화: 이 리프팅은 리프팅된 변수에서 2 차 장애물 제약 (예: $\|p_k - c_j\|^2 \geq r_j^2$) 을 선형 아핀 부등식으로 변환하면서, 리프팅된 공간에서 시스템의 선형 동역학을 유지합니다.
• 완화: 모멘트 행렬에 대한 정확한 랭크 -1 제약을 PSD 제약 ($M_k \succeq 0$) 으로 완화하여 문제를 볼록화합니다.

2. 리카티 기반 ADMM 솔버

임베디드 하드웨어에서 생성된 볼록 문제를 효율적으로 해결하기 위해, 저자들은 단계별 PSD 제약을 처리할 수 있도록 TinyMPC 프레임워크 (캐시된 리카티 재귀를 사용) 를 확장합니다.

• 알고리즘: 솔버는 승수 교대 방향법 (ADMM) 을 활용합니다.
• 프라이멀 업데이트: 프라이멀 부분 문제는 리프팅된 선형 2 차 조절기 (LQR) 문제입니다. 중요한 점은 시스템 동역학이 리프팅된 변수에서 선형으로 유지되므로, 사전 계산된 캐시된 정상 상태량을 사용하여 효율적인 후방 - 전방 리카티 스윕을 사용할 수 있다는 것입니다.
• 슬랙 및 듀얼 업데이트: PSD 제약은 투영 단계를 통해 처리됩니다. 각 ADMM 반복에서 솔버는 행렬을 PSD 원뿔로 유클리드 투영 (고유값 분해 및 고유값 클램핑을 통해) 하고 듀얼 변수를 업데이트합니다. 이 투영은 단계별로 수행되어 실시간 실행에 필요한 계산 구조를 유지합니다.

3. 사후 랭크 -1 안전 증명서

SDP 완화로 인한 느슨함을 해결하기 위해, 논문은 모든 시간 단계에서 평가되는 간단하고 계산 비용이 저렴한 증명서를 제안합니다.

• 트레이스 갭: 증명서는 리프팅된 위치 블록의 트레이스와 물리적 위치의 제곱 노름 사이의 차이 ($\text{trace}(X^{(p)}_k) - \|p_k\|^2$) 로 정의된 "트레이스 갭"($\Delta_k$) 을 측정합니다.
• 증명 로직: 리프팅된 마진 (선형화된 장애물 제약의 값) 이 음이 아니고 트레이스 갭이 이 마진에 비해 충분히 작으면, 그 해가 충돌이 없는 것으로 증명됩니다.
• 폴백: 증명서가 실패하면, 시스템은 계획된 제어 입력을 폐기하고 반응형 폴백 정책 (정지 및 호버) 을 실행하여 증명되지 않은 명령이 물리적 로봇에 적용되지 않도록 보장합니다.

주요 기여

1. TinySDP 솔버: 캐시된 리카티 구조를 활용하여 실시간으로 PSD-완화된 MPC 문제를 해결하는 최초의 임베디드 SDP 솔버 개발.
2. 완화와 증명의 통합: 효율적인 볼록 완화와 명시적인 사후 기하학적 안전 증명서를 결합하여 이론적 최적성과 실제 안전 보장 사이의 간극을 메우는 프레임워크.
3. 하드웨어 검증: 25Hz 제어 속도로 실행되는 Crazyflie 2.1 쿼드콥터 (STM32F405 마이크로컨트롤러) 에서의 성공적인 배포를 통해, 리소스가 제한된 플랫폼에서도 반정규 제약을 부과할 수 있음을 입증.

실험 결과

저자들은 시뮬레이션 및 실제 하드웨어에서 TinySDP 를 최신 베이스라인 (TinyMPC-LIN, TinyMPC-HOCBF, RPCBF) 과 비교 평가했습니다.

• 정적 U 자형 막다른 길: 국소 방법으로 인해 교착 상태가 발생하도록 설계된 시나리오에서 TinySDP 는 충돌 없는 항해를 달성하여 최상위 베이스라인 (RPCBF) 보다 31~73% 짧은 경로 길이를 보였습니다. 베이스라인 방법들은 충돌 (안전 마진 0) 이 발생하거나 성공하기 위해 비현실적으로 큰 안전 마진 (드론 크기의 최대 30 배) 을 요구했는데, 이는 충돌 발자국을 팽창시켜 목표 도달을 방해했습니다.
• 동적 장애물 회피: 좁은 통로를 막는 이동 장애물이 있는 동적 시나리오에서 TinySDP 는 충돌을 성공적으로 예측하고 회피했습니다. RPCBF 보다 30% 짧은 경로를 생성하고 베이스라인보다 높은 정밀도 (목표에 더 가까움) 를 유지했습니다.
• 3D 확장: 저자들은 리프팅 프레임워크가 3D 구형 장애물로 자연스럽게 확장될 수 있음을 입증하여, 시뮬레이션에서 동적 3D 시나리오를 성공적으로 항해했습니다.
• 실제 배포: Crazyflie 에서 솔버는 40ms 제어 주기 내에서 약 14.8ms 내에 5 회 ADMM 반복을 실행했습니다 (약 25ms 마진 확보). 메모리 발자국은 적절했습니다 (PSD 논리를 위한 약 1.47KB 정적 메모리 오버헤드). 이동하는 로봇 팔이 포함된 5 개의 독립적인 시험에서 온라인 안전 증명서는 모든 시간 단계에서 유효하게 유지되어 실제 환경의 교란 하에서도 랭크 -1 기하학이 보존됨을 확인했습니다.

중요성 및 주장

이 논문은 TinySDP가 반정규 제약이 임베디드 시스템의 실시간 후퇴 시간 제어와 본질적으로 양립할 수 없음을 보여주지 않는다고 주장합니다. 특정 문제 구조 (리카티 동역학) 를 활용하고 최적화와 증명을 분리함으로써, 저자들은 계산적 처리 가능성을 희생하지 않고도 보수적인 선형 근사를 넘어설 수 있음을 보여줍니다.

이 연구는 오프라인 반정규 계획과 실제 임베디드 배포 사이의 간극을 메웁니다. 솔버 설계가 근본적인 MPC 구조를 존중한다면 더 풍부한 볼록 안전 모델을 고율 제어기에 통합할 수 있음을 시사합니다. 저자들은 이를 휴리스틱 튜닝이나 작은 임베디드 플랫폼에 배포하기 어려울 수 있는 학습 기반 방법에 의존하지 않고, 형식적 안전 보장을 갖춘 복잡하고 비볼록한 환경을 항해할 수 있는 "민첩한" 엣지 로봇을 가능하게 하는 한 걸음으로 위치시킵니다.

저자들은 한계에 대해 겸손하게 언급하며, 증명서가 폐루프 재귀적 실현 가능성 보장이 아닌 시간 단계별 확인을 제공한다는 점과, 더 큰 PSD 투영에 대한 증가된 계산 비용으로 인해 완전한 3D 기능을 마이크로컨트롤러로 확장하는 것이 여전히 과제임을 지적합니다.