Steering with Contingencies: Combinatorial Stabilization and Reach-Avoid Filters

1. 문제 정의 (Problem Definition)

• 배경: 자율 착륙, 항법, 우주선 착륙, 자율 주행 차량 등 다양한 자율 시스템 응용 분야에서 시스템은 주된 목표 (Target) 로 이동하면서도, 예기치 못한 상황 (위험 감지, 배터리 소모 등) 에 대비하여 **적어도 $r$개의 대체 목표 ($p$개 중)**로 즉시 전환할 수 있어야 합니다.
• 핵심 요구사항: 시스템이 현재 활성화된 목표 ($j^\dagger$) 를 향해 이동하는 동안, 궤적의 모든 시점에서 $p$개의 후보 목표 중 최소 $r$개가 여전히 도달 가능 (Reachable) 해야 합니다. 이를 $r$-out-of-$p$ 컨팅전시 (Contingency) 요구사항이라고 합니다.
• 기존 방법의 한계:
  • 모든 가능한 $r$개의 조합을 고려하는 naive 한 접근법은 계산적으로 비효율적 (Combinatorial blow-up) 입니다.
  • 기존 제어 장벽 함수 (CBF) 는 모든 안전 조건을 동시에 만족 (AND) 하도록 설계되어 있어, 일부 조건만 만족하면 되는 유연한 논리 (OR 또는 $r$-out-of-$p$) 를 구현하기 어렵습니다.
  • 기존 Hamilton-Jacobi (HJ) 접근법은 단일 목표나 장애물 회피에는 효과적이지만, 여러 대체 목표를 동시에 유지하면서 주 목표를 향해 이동하는 문제를 다루기에는 부족했습니다.

2. 방법론 (Methodology)

저자들은 이 문제를 해결하기 위해 **제어 장벽 함수 (CBF)**와 **제어 리아푸노프 함수 (CLF)**를 결합한 최적화 기반 필터를 제안하며, 두 가지 주요 프레임워크를 개발했습니다.

A. 조합적 안정화 (Combinatorial Stabilization) - CLF 기반

• 목표: 선택된 평형점 (Equilibrium) 으로 점근적으로 안정화시키면서, 궤적이 $p$개의 평형점 중 최소 $r$개의 끌림 영역 (Region of Attraction, RoA) 내에 머무르도록 보장합니다.
• 수식화:
  • 각 목표 $j$에 대한 국소 CLF $V_j(x)$를 정의하고, 이를 CBF 형태로 변환합니다 ($h_j(x) = c_j - V_j(x)$).
  • $r$-out-of-$p$ 안전 집합 $\tilde{R}$은 $h_j(x)$ 값 중 $r$번째로 큰 값이 0 이상인 영역으로 정의됩니다 ($\tilde{h}(x) = \max^{(r)} \{h_j(x)\} \ge 0$).
  • 제어기 설계: 선택된 목표 $j^\dagger$에 대한 CLF 감소 조건과 조합적 CBF 조건을 동시에 만족시키는 2 차 계획법 (QP) 을 구성합니다.
  • 핵심 기법: 리아푸노프 조건이 적용되지 않는 영역에서도 제어기가 정의될 수 있도록 **슬랙 변수 (Slack variable, $\omega$)**와 ReLU 함수를 도입하여 조건을 완화 (Relaxation) 합니다. 이를 통해 $p+1$개의 제약 조건만으로 조합적 안정성을 보장합니다.

B. 조합적 도달 - 회피 (Combinatorial Reach-Avoid) - HJR 기반

• 목표: 유한 시간 구간 (Finite-horizon) 이나 자원 고갈 (연료, 배터리) 로 인해 도달 가능 영역이 축소되는 상황에서, 선택된 목표에 도달하면서 $r$개의 대체 목표를 유지합니다.
• 수식화:
  • 각 목표에 대한 해밀턴 - 야코비 (Hamilton-Jacobi, HJ) 도달 - 회피 (Reach-Avoid) 값 함수 $V_j(x, \tau)$를 사용합니다. 이는 유한 시간 구간에서 장애물을 피하고 목표에 도달할 수 있는 상태를 정의합니다.
  • 시간에 따라 변하는 도달 - 회피 집합 (BRA set) 을 조합적으로 정의합니다.
  • 제어기 설계: 값 함수의 미분 가능성 가정 하에, QP 기반 필터를 설계하여 시간 가변적인 도달 집합 내에서 궤적을 유지하도록 합니다. 이 또한 $p+1$개의 제약 조건으로 구현됩니다.

3. 주요 기여 (Key Contributions)

1. 조합적 컨팅전시 요구사항의 형식화: 자율 시스템이 주 목표를 향해 이동하면서도 $r$개의 대체 목표를 유지해야 하는 문제를 수학적으로 엄밀하게 정의했습니다.
2. 계산 효율성 (Combinatorial Blow-up 방지): $p$개의 후보 중 $r$개를 선택하는 모든 조합을 고려하지 않고, 단순히 $p+1$개의 제약 조건만으로 조합적 안정성 및 도달 - 회피 필터를 설계했습니다. 이는 실시간 구현 (Real-time implementation) 을 가능하게 합니다.
3. 두 가지 통합 프레임워크 제안:
   • CLF 기반: 무한 시간 안정화 문제에 적용 가능한 조합적 안정화 필터.
   • HJR 기반: 유한 시간 및 자원 제약이 있는 문제에 적용 가능한 조합적 도달 - 회피 필터.
4. 안전한 목표 전환 보장: 필터를 통해 시스템이 항상 $r$개의 대체 목표에 도달 가능한 상태에 머무르므로, 예기치 못한 상황에서 실시간으로 목표 (Target) 를 전환하더라도 안전성이 보장됨을 증명했습니다.

4. 실험 결과 (Results)

논문은 두 가지 시뮬레이션을 통해 제안된 프레임워크의 유효성을 입증했습니다.

• 예제 1: 선형 시스템 (CLF 기반)

  • 3 개의 목표와 3 개의 장애물이 있는 2 차원 선형 시스템에서 시뮬레이션 수행.
  • 결과: 필터를 적용하지 않은 경우 (Nominal controller), 시스템은 장애물과 충돌하거나 안전 영역을 벗어났습니다. 반면, 제안된 필터를 적용한 경우, 시스템은 선택된 목표 ($x_1$) 로 이동하면서도 항상 2 개 ($r=2$) 의 다른 목표에 도달 가능한 영역 내에 머무르도록 조정되었습니다.
  • 목표 전환: $t=0.5$s 에서 목표가 $x_2$로 변경되었을 때, 필터링된 궤적은 충돌 없이 안전하게 전환되었으며, 이는 필터가 항상 대체 경로를 유지했기 때문입니다.

• 예제 2: 항공기 착륙 (HJR 기반)

  • 건물 장애물 사이를 통과하여 6 개의 활주로 중 하나로 착륙하는 단순화된 항공기 모델.
  • 결과:
    • 컨팅전시 없음 ($r=0$): 장애물과 충돌.
    • $r=2$ (5 초 내 도달 가능): 필터가 2 개의 활주로를 항상 도달 가능하게 유지하도록 궤적을 수정하여 안전하게 착륙.
    • 시간 제약 변화: 착륙 가능 시간이 줄어들어 원래 목표가 불가능해지면, 필터는 자동으로 대체 목표 (Contingency runway) 로 전환하여 안전하게 착륙을 완료했습니다.
  • 모든 시나리오에서 필터가 조합적 도달 - 회보 보장을 유지함을 확인했습니다.

5. 의의 및 결론 (Significance)

• 실시간 안전성 보장: 복잡한 조합적 논리 ($r$-out-of-$p$) 를 실시간으로 처리할 수 있는 효율적인 QP 기반 필터를 제공함으로써, 고위험 자율 시스템의 신뢰성을 높였습니다.
• 유연한 대응: 시스템이 예상치 못한 환경 변화 (장애물 출현, 자원 고갈) 에 직면했을 때, 안전성을 해치지 않고 즉각적으로 대체 계획을 실행할 수 있는 능력을 부여합니다.
• 확장성: 제어 이론 (CLF) 과 최적 제어 (HJR) 를 결합하여 다양한 동적 환경 (무한 시간 안정화, 유한 시간 도달) 에 적용 가능한 일반적인 프레임워크를 제시했습니다.

이 연구는 자율 시스템이 단순히 "목표에 도달"하는 것을 넘어, "예상치 못한 상황에 대비하여 안전을 유지하며 도달"하는 고도화된 자율성 (Robust Autonomy) 을 실현하는 데 중요한 기여를 합니다.