On the Computation of Backward Reachable Sets for Max-Plus Linear Systems with Disturbances

논문 요약: 섭동이 있는 Max-Plus 선형 시스템의 역방향 도달 가능 집합 계산

1. 연구 배경 및 문제 정의 (Problem)

• 배경: Max-Plus 선형 시스템 (MPLS) 은 스케줄링, 제조, 교통 시스템 등 이벤트 기반의 동기화 및 지연 현상을 모델링하는 데 널리 사용됩니다. 그러나 실제 응용에서는 모델링 오차, 파라미터 변동, 외부 섭동 (disturbance) 으로 인한 불확실성이 존재합니다.
• 문제: 본 논문은 섭동이 있는 불확실한 Max-Plus 선형 시스템에 대한 **역방향 도달 가능 집합 (Backward Reachable Set)**의 계산을 다룹니다.
  • 목표: 주어진 목표 집합 (Target Set, $E$) 에 대해, **모든 허용 가능한 섭동 (admissible disturbances)**에 대해 다음 상태가 $E$에 속하도록 하는 **적합한 제어 입력 (admissible control input)**이 존재하는 상태들의 집합을 계산하는 것입니다.
  • 중요성: 이 문제는 안전성 분석 (Safety Analysis) 과 제어기 합성 (Controller Synthesis) 의 핵심 요소입니다.
• 도전 과제: 기존 접근법 (예: DBM 기반) 은 시스템 차원과 불확실성 구조가 커질수록 계산 복잡도가 급증하는 문제가 있으며, 섭동에 대한 '보편 양화 (universal quantification, $\forall w$)'가 포함되어 있어 기존 방법으로는 처리가 어렵습니다.

2. 방법론 (Methodology)

저자들은 열대 볼록성 (Tropical Convexity) 이론, 특히 **열대 다면체 (Tropical Polyhedra)**를 기반으로 한 계산 프레임워크를 개발했습니다.

• 수학적 표현:

  • 시스템, 제어 집합 ($U$), 섭동 집합 ($W$), 목표 집합 ($E$) 을 모두 열대 다면체로 표현합니다. 이는 구간 (interval) 기반 표현보다 더 유연하고 표현력이 높은 불확실성 모델링을 가능하게 합니다.
  • 시스템 모델: $x_k = A \otimes x_{k-1} \oplus B \otimes u_k \oplus C \otimes w_k$

• 연산자 분해:
  역방향 도달 연산자 $\Upsilon(E)$를 세 가지 기본 집합 연산자로 분해하여 분석합니다.

  1. 역연산자 ($A^{-1}$): 시스템 역동성에 의한 역전파.
  2. 존재적 역연산자 ($\gamma_U$): 제어 입력에 대한 존재 양화 ($\exists u$).
  3. 보편적 역연산자 ($\phi_W$): 섭동에 대한 보편 양화 ($\forall w$).
  • 전체 연산: $\Upsilon = A^{-1} \circ \gamma_U \circ \phi_W$

• 핵심 알고리즘적 접근:

  • 구조 보존성 증명: 위 세 연산자가 모두 열대 다면체의 구조를 보존함을 증명합니다. 즉, 입력 집합이 열대 다면체이면 출력 집합도 열대 다면체입니다.
  • $\phi_W$ 계산의 혁신: 섭동에 대한 보편 양화 ($\forall w$) 는 가장 어려운 부분입니다. 저자들은 이를 **의사 반공간 (Pseudo Half-Space)**의 교집합으로 재구성했습니다.
    • 섭동 집합 $W$를 유계 다면체 ($P$) 와 원뿔 ($R$) 의 합으로 분해하여 계산을 단순화합니다.
    • 생성 집합 (Generating Set) 을 구하기 위해 Theorem 1을 제시합니다. 이는 기존 생성 집합과 의사 반공간의 교집합을 통해 새로운 생성 집합을 유도하는 재귀적 알고리즘의 기초가 됩니다.
    • 생성 집합의 크기를 줄이기 위해 극점 필터링 (Extremal Points Filtering) 기법을 적용하여 계산 효율성을 높였습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 계산 프레임워크 제안: 섭동이 있는 Max-Plus 시스템의 역방향 도달성 분석을 위해 열대 다면체 이론을 적용한 최초의 체계적인 프레임워크를 제시했습니다.
2. 구조 보존성 증명: 불확실성 (섭동) 이 존재하는 상황에서도 역방향 도달 집합이 여전히 열대 다면체로 표현 가능함을 수학적으로 증명했습니다. 이는 반복적인 도달성 분석을 가능하게 합니다.
3. 효율적인 계산 알고리즘 개발:
   • 보편 양화 ($\forall w$) 문제를 의사 반공간의 교집합 문제로 변환하고, 이를 해결하기 위한 생성 집합 계산 알고리즘을 구체적으로 제시했습니다.
   • 기존 DBM 기반 방법보다 더 넓은 불확실성 구조를 다루면서도 기하학적 표현을 유지하여 계산 가능성을 확보했습니다.
4. 구체적 예시 및 검증: 간단한 시스템 예시를 통해 제안된 방법론이 실제로 작동하며, 목표 집합으로부터 역방향 도달 집합을 성공적으로 계산할 수 있음을 시연했습니다.

4. 결과 및 사례 연구 (Results & Case Study)

• 사례 연구: 2 차원 상태 변수를 가진 Max-Plus 시스템에 대해, 특정 안전 집합 (Safety Set) 을 기준으로 역방향 도달 집합을 계산하는 과정을 상세히 설명했습니다.
  • 섭동 집합 $W$와 안전 집합 $S$가 열대 다면체로 주어졌을 때, $\phi_W(S)$, $\gamma_U(\phi_W(S))$, 그리고 최종적으로 $A^{-1}(\dots)$ 순서로 계산했습니다.
  • 각 단계에서 생성 벡터 (Generating Vectors) 가 어떻게 변형되고 필터링되는지 수치적으로 보였습니다.
• 시각화: 계산된 집합들의 기하학적 형태 (안전 영역, 섭동 영역, 도달 가능 영역) 를 도표로 시각화하여 방법론의 직관적 이해를 도왔습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 안전성 검증 도구: 제안된 방법은 불확실한 Max-Plus 시스템의 안전성 검증 및 안전을 유지하는 제어기 합성을 위한 강력한 기하학적/대수적 도구를 제공합니다.
• 확장성: 확률적 접근법 (Probabilistic) 이 아닌 결정론적 불확실성 (Deterministic Ambiguity Sets) 을 다루므로, 최악의 경우 (Worst-case) 분석이 필요한 안전 임계 시스템에 적합합니다.
• 미래 과제: 계산 효율성을 더 높이기 위해 근사 기법 도입이나 시스템 파라미터 불확실성 처리 등을 향후 연구 과제로 제시했습니다.

결론적으로, 이 논문은 섭동이 있는 Max-Plus 시스템의 복잡한 역방향 도달성 문제를 열대 기하학 (Tropical Geometry) 을 통해 체계적으로 해결함으로써, 제어 이론 및 시스템 공학 분야에서 중요한 이론적, 실용적 기여를 했습니다.