Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

기술 요약: 제어 아키텍처를 통한 선형 확률 시스템의 도달-회피 확률 극대화

문제 정의
본 논문은 유한 시간 지평선 동안 선형 확률 시스템의 도달-회피(reach-avoid) 확률을 극대화하는 문제를 다룹니다. 시스템은 결정론적으로 진화하는 상태($x_d$)와 i.i.d. 노이즈가 가해진 확률적으로 진화하는 상태($x_s$)를 포함하는 동역학으로 정의됩니다. 제어 목표는 시스템이 $[0, T]$ 기간 동안 안전 집합 $S$ 내에 머물면서 동시에 목표 집합 $T$에 도달할 확률을 극대화하는 정책을 찾는 것입니다. 이때 모든 시점에서 결정론적 제약 조건 $G$(입력 제한 및 상태 경계 등)를 만족해야 합니다.

기존 방법들은 트레이드오프 문제에 직면해 있습니다. 통계적 경계 기반 접근 방식(예: 확률적 튜브, 시나리오 MPC)은 확장성은 높지만 종종 지나치게 보수적인 성능을 보이는 반면, 직접 최적화 방법(예: 마르코프 결정 과정, MDP)은 엄격한 보장을 제공하지만 고차원 또는 연속 상태 공간에서는 계산적으로 불가능합니다.

방법론
저자들은 MPC의 확장성과 동적 계획법(DP)의 최적성을 결합한 계층적 제어 아키텍처를 제안합니다. 핵심 혁신은 폐루프 시스템(플랜트 + MPC)을, 직접적인 제어 입력 대신 MPC로 전달되는 참조 신호를 '행동(action)'으로 취급하는 마르코프 결정 과정(MDP)으로 다루는 데 있습니다.

1. 계층적 아키텍처:

   • 하위 계층 (MPC): 상위 계층에서 생성된 참조 신호를 추적하는 모델 예측 제어기(MPC)입니다. 이 MPC는 확률적 도달-회피 목적 함수와 무관하게 설계되며, 유일한 목적은 시스템이 결정론적 제약 조건 $G$와 입력 제한 $U$를 준수하도록 보장하는 것입니다. 이산 시간 MPC 최적화와 연속 시간 제약 조건 준수 사이의 간극을 메우기 위해, 저자들은 샘플링 구간 동안의 시스템 동역학 및 노이즈를 고려하는 제약 조건 수축 기법(Lemma III.1)을 도출합니다.
   • 상위 계층 (DP 참조 생성기): 고정된 시간 간격($\Delta t$)으로 작동하는 DP 기반 정책입니다. 이 정책은 목표에 도달할 확률을 극대화하고 안전하지 않은 영역을 회피하기 위해 MPC를 위한 참조 시퀀스(명령)를 선택합니다. 이 MDP의 상태 공간은 시스템 상태 $x_k$이며, 행동 공간은 유한한 참조 궤적 집합으로 구성됩니다.

2. 연속 상태 공간 및 추상화 처리:
   상태 공간이 연속적이므로, 저자들은 DP를 계산 가능하게 만들기 위해 유한 그리드 추상화를 채택합니다. 이러한 이산화에도 불구하고 이론적 보장이 유지되도록 하기 위해, 저자들은 강건화 프레임워크를 도입합니다.

   • 강건 MPC (RMPC): MPC는 특정 초기 상태에 관계없이 불변하는 입력 시퀀스를 생성하도록 수정됩니다. 이는 MPC 예측을 격자(partition)의 중심점에서 시작함으로써 달성되며, 이를 통해 격자 내의 모든 상태에 동일한 제어 시퀀스가 적용되도록 합니다.
   • 강건 가치 반복 (Robust Value Iteration): 격자 셀 내에서의 궤적 최대 편차로부터 유도된 반지름 $r$만큼 안전 집합과 목표 집합을 수축시킵니다. DP 알고리즘은 각 격자 셀의 이웃 내에서 발생할 수 있는 최악의 전이를 고려하여 도달-회피 확률의 하한을 계산하도록 수정됩니다.

주요 기여

• 제어 아키텍처: 본 논문은 DP 계획 공간의 차원을 전체 상태 차원 $n$에서 확률적으로 진화하는 성분의 차원 $n_s$로 줄이는 새로운 아키텍처를 소개합니다. 이는 $x_d$의 결정론적 진화와 MPC의 추적 능력을 활용함으로써 달성됩니다.
• 이론적 보장: 저자들은 이 접근 방식에 대한 공식적인 인증(certificate)을 제공합니다. 저자들은 강건한 아키텍처가 연속 시간 제약 조건 준수를 보장하며, 강건한 DP 알고리즘에 의해 계산된 값이 실제 시스템이 달성하는 도달-회피 확률의 엄격한 하한 역할을 함을 증명합니다(Theorem IV.4).
• 확장성 및 유연성: 이 방법은 고차원 시스템(구체적으로 12D 쿼드콥터 모델)에 대한 확장성을 입증하였으며, 복잡하고 장애물이 많은 환경을 처리할 수 있을 만큼 충분히 유연합니다.

결과
이 접근 방식은 다양한 복잡한 환경(예: 미로, 지그재그 경로, 장애물 필드)을 항해하는 섭동이 가해진 12D 쿼드콥터 모델을 통해 검증되었습니다.

• 성능: 미로 시나리오에서 이 아키텍처는 40%의 성공률을 달 기록하며, 보수적인 베이스라인 모델들을 크게 앞질렀습니다.
• 비교: 여러 시나리오에 걸쳐, 경험적 도달-회피 확률($V_0(x_0)$)은 강건 가치 반복에 의해 계산된 하한($\tilde{V}_0(x_0)$)과 일치하거나 이를 초과하여 이론적 보장을 입증했습니다. 예를 들어, "지그재그" 환경에서 경험적 성공률은 44%였으며, 이는 이론적 하한인 0.3%와 대비됩니다.
• 트레이드오프: 본 논문은 또한 제약이 있는 최적 제어 문제를 해결하는 아키텍처의 능력을 보여줍니다. 라그랑주 승수(Lagrange multiplier)를 조정함으로써, 시스템은 경로 비용(궤적을 중심에 가깝게 유지)과 도달-회피 확률 사이의 균형을 맞추며 파레토 최적해(Pareto front)를 생성할 수 있습니다.

의의 및 주장
본 논문은 이 연구가 MDP 기반 방법의 이론적 최적성과 MPC의 실용적 확장성 사이의 간극을 메운다고 주장합니다. 안전 확보(강건한 MPC가 담당)와 확률적 최적화(DP 참조 생성기가 담당)를 분리함으로써, 저자들은 고차원 시스템에 대해 계산적으로 실행 가능하면서도 과도하게 보수적인 통계적 경계에 의존하지 않고 공식적인 도달-회피 인증을 제공할 수 있는 제어 전략을 달성했습니다. 저자들은 자신들의 방법이 확장 가능한 휴리스틱 접근 방식에서 흔히 결여되는 '확률적 시스템에 대한 공식적 인증'을 제공하는 동시에, 전체 상태 MDP 솔루션의 계산적 불가능성을 피한다는 점을 강조합니다.