Marking Data-Informativity and Data-Driven Supervisory Control of Discrete-Event Systems

이 논문은 이산 사건 시스템의 모델이 알려지지 않은 상황에서 주어진 사양을 만족하는 비차단 마킹 감독기를 설계하기 위한 조건인 '마킹 데이터 정보성' 개념을 제안하고, 이를 검증하는 알고리즘을 개발하며 데이터가 불충분할 경우를 위한 확장 개념과 알고리즘을 제시합니다.

핵심

이 논문은 **"어떤 기계나 시스템의 작동 원리 (설계도) 를 전혀 모를 때, 오직 '관측된 데이터'만 가지고 어떻게 그 시스템을 안전하게 통제할 수 있을까?"**라는 질문에 답하는 연구입니다.

전통적인 제어 공학은 시스템의 정확한 설계도 (모델) 를 먼저 그리는 데서 시작합니다. 하지만 현실에서는 설계도가 없거나, 환경이 너무 복잡해서 설계도를 그리는 게 불가능한 경우가 많습니다. 이때 IoT 센서 등에서 수집된 '데이터'만 믿고 시스템을 제어하는 새로운 방법을 제안한 것이 이 논문입니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

---

1. 상황 설정: 설계도 없는 미로 탐험

상상해 보세요. 당신은 완전히 새로운 미로에 들어섰습니다.

• 미로 (시스템): 로봇이 이동할 수 있는 공간입니다.
• 목적지 (Marked State): 로봇이 도달해야 하는 안전한 출구입니다.
• 함정 (Danger): 로봇이 떨어지면 안 되는 구멍입니다.
• 데이터: 당신은 미로에 들어가기 전, 다른 탐험가들이 남긴 일부 기록만 가지고 있습니다.
  • D: "어떤 탐험가가 A 길을 거쳐 B 길을 갔다" (관측된 경로)
  • Dm: "그중 A-B-C 길은 성공적으로 출구에 도착했다" (성공 기록)
  • D-: "하지만 D 길은 절대 갈 수 없다, 벽이 있다" (불가능한 경로에 대한 지식)

이제 당신은 이 미로의 전체 지도를 모른 채, 로봇이 함정에 빠지지 않고 출구에 도달하도록 **스스로 길을 막거나 열어주는 통제자 (Supervisor)**를 만들어야 합니다.

2. 핵심 개념 1: "데이터가 충분한가?" (Marking Data-Informativity)

가장 먼저 묻는 질문은 **"지금 가지고 있는 기록 (데이터) 만으로 로봇을 안전하게 출구로 보낼 수 있을까?"**입니다.

논문은 이를 **'데이터 정보성 (Data-Informativity)'**이라고 부릅니다.

• 비유:
  • 만약 기록에 "A 길로 가면 B 로 갈 수 있다"는 기록만 있고, "B 로 가면 함정 (D 길) 으로 빠질 수 있다"는 기록이 없다면?
  • 통제자는 "B 로 가는 길은 함정일 수도 있으니 막아야겠다"라고 판단할 수 없습니다.
  • 하지만 기록에 **"B 로 가는 길은 절대 갈 수 없다 (D-)"**는 확실한 정보가 있다면? 통제자는 "B 로 가는 길은 막아야겠다"라고 확신할 수 있습니다.

이 논문은 **"관측된 성공 기록 (Dm) 과 불가능한 기록 (D-) 이 서로 잘 맞아서, 어떤 미로 (시스템) 에든 적용 가능한 안전한 통제 규칙을 만들 수 있는가?"**를 수학적으로 증명했습니다. 이를 **'마크 데이터 정보성'**이라고 합니다.

3. 핵심 개념 2: "데이터가 부족할 때怎么办?" (Restricted & Informatizability)

만약 가지고 있는 데이터가 부족해서 완벽한 통제 규칙을 만들 수 없다면 어떨까요?

• 상황: "A-B-C 길은 성공했지만, A-B-D 길은 함정일 수도 있고 아닐 수도 있어서 알 수 없다"는 식의 불확실성이 너무 많을 때입니다.
• 해결책: 논문은 **"완벽한 출구 (전체 목표) 를 포기하고, 안전이 보장되는 '부분적인 목표'만 달성하자"**고 제안합니다.
  • 예를 들어, "A-B-C-D 길까지 가는 건 위험하니까, A-B-C 길까지만 안전하게 도달하는 것"으로 목표를 줄입니다.
  • 이를 **'제한된 데이터 정보성 (Restricted Marking Data-Informativity)'**이라고 합니다.

그리고 더 나아가, **"어떤 부분적인 목표라도 달성 가능한가?"**를 확인하는 '데이터 변환 가능성 (Informatizability)' 개념을 만들었습니다. 만약 데이터가 너무 부족해서 어떤 목표도 달성할 수 없다면, 더 많은 데이터를 수집해야 한다고 말합니다.

4. 알고리즘: "데이터로 지도 그리기"

논문은 이 이론을 실제로 적용할 수 있는 3 단계 알고리즘을 제시합니다.

1. 데이터로 가상의 나무 만들기 (Data-Driven Automaton):
   • 가지고 있는 기록 (D, Dm, D-) 을 바탕으로, 가능한 모든 경로를 가진 '가상의 나무'를 그립니다. 이 나무는 실제 미로일 수도 있고, 다른 미로일 수도 있지만, 기록과 일치하는 모든 가능성을 포함합니다.
2. 위험한 가지 찾기 (Non-Informative State Check):
   • 이 나무에서 "어떤 가지로 가면 통제자가 함정을 막을지 알 수 없는 곳"을 찾아냅니다.
3. 가장 안전한 큰 가지 고르기 (Least Restricted Supervisor):
   • 위험한 가지를 잘라내고, 남은 가지 중에서 가장 크고 안전한 경로를 찾아냅니다. 이것이 바로 우리가 만들 수 있는 '최대 허용 통제 규칙'입니다.

5. 왜 중요한가요? (실생활 예시)

• 자율주행 자동차: 새로운 도시를 운전할 때, 모든 도로의 설계도를 미리 알 수 없습니다. 하지만 과거의 주행 데이터 (어디서 멈췄는지, 어디로 갔는지) 와 "이 길은 통행 금지"라는 정보만으로도, 사고 없이 목적지에 도달하는 운전 규칙을 실시간으로 만들 수 있습니다.
• 공장 자동화: 낡은 기계나 새로운 생산 라인의 내부 구조를 정확히 모를 때, 센서 데이터만 분석해서 기계가 고장 나지 않고 제품을 잘 만들어내도록 제어할 수 있습니다.

요약

이 논문은 **"설계도가 없어도, 데이터만 있다면 시스템을 통제할 수 있다"**는 것을 증명했습니다.

1. 데이터가 충분하면: 완벽한 통제 규칙을 만듭니다.
2. 데이터가 부족하면: 안전이 보장되는 '부분적인 목표'로 목표를 조정합니다.
3. 데이터가 너무 부족하면: 더 많은 데이터를 모으라고 조언합니다.

이는 우리가 모르는 환경에서도 데이터를 통해 지능적으로 대응할 수 있는 새로운 제어 공학의 길을 열어준 연구입니다.

기술 요약

논문 요약: 이산 사건 시스템 (DES) 의 마킹 데이터-정보성 및 데이터 기반 감시 제어

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

• 배경: 이산 사건 시스템 (DES) 의 감시 제어 (Supervisory Control) 는 전통적으로 시스템의 정확한 수학적 모델 (유한 상태 오토마타) 을 기반으로 설계됩니다. 그러나 IoT 와 센서 기술의 발전으로 시스템 모델은 알 수 없으나, 시스템의 동작에 대한 방대한 데이터는 수집 가능한 상황이 증가하고 있습니다.
• 문제: 기존 데이터 기반 제어 연구는 주로 시스템의 '폐쇄된 동작 (closed behavior)'에 초점을 맞추었으나, 실제 응용 (예: 목표 지점 도달, 데드락 방지) 에서는 '마킹된 동작 (marked behavior, 즉 목표 상태에 도달하는 동작)'이 필수적입니다.
• 핵심 질문: 시스템의 모델이 알려지지 않았고, 관찰 데이터 ($D$), 마킹된 관찰 데이터 ($D_m$), 그리고 불가능한 동작에 대한 사전 지식 ($D^-$) 만 주어졌을 때, 주어진 사양 (Specification) 을 만족하는 유효한 비차단 (nonblocking) 마킹 감시 제어기를 설계할 수 있는 조건은 무엇인가?

2. 방법론 (Methodology)

이 논문은 모델 식별 (Model Identification) 을 거치지 않고, 데이터 자체로부터 직접 감시 제어기를 구성하는 새로운 프레임워크를 제안합니다.

가. 데이터 기반 오토마타 (Data-Driven Automaton)

• 관찰 데이터 ($D$), 마킹 데이터 ($D_m$), 불가능 데이터 ($D^-$) 를 기반으로 전이 트리 형태의 오토마타 ($\hat{G}$) 를 구성합니다.
• 이 오토마타는 관찰된 모든 문자열을 상태와 매핑하며, $D^-$에 속하는 전이는 불가능한 것으로 간주합니다.

나. 마킹 데이터 - 정보성 (Marking Data-Informativity)

• 정의: 주어진 데이터 세트로 모든 일관된 (consistent) 시스템 모델에 대해 유효한 비차단 마킹 감시 제어기를 설계할 수 있는지를 판단하는 개념입니다.
• 필요충분 조건 (Theorem 1): 제어 사양 $K_{D_m}$ (데이터 기반 사양) 에 대해, 모든 관찰된 상태 $s$ 와 비제어 가능 사건 $\sigma$ 에 대해 다음 조건이 성립해야 합니다:
  $$s\sigma \in K_{D_m} \cup D^-$$
  즉, 비제어 가능 사건이 발생했을 때, 그 결과가 사양 내 ($K_{D_m}$) 에 있거나, 혹은 사전 지식 ($D^-$) 에 의해 불가능한 것으로 확인되어야 합니다. 만약 $s\sigma$가 $D$에는 있지만 사양에는 없고, $D^-$에도 없다면 (즉, 관찰되지 않았지만 가능할 수도 있는 경우), 데이터는 정보성이 부족합니다.

다. 검증 알고리즘 (Algorithm 1)

• 데이터 기반 오토마타를 구축하고, 사양에 해당하는 상태 집합 ($Q_K$) 에서 모든 비제어 가능 사건에 대한 전이를 확인합니다.
• 전이가 $Q_K \cup Q^-$ (사양 또는 불가능 영역) 밖으로 나가는지, 혹은 전이가 정의되지 않았는지 확인하여 정보성 유무를 판별합니다.

라. 제한된 마킹 데이터 - 정보성 및 마킹 정보화 가능성 (Restricted Marking Data-Informativity & Marking Informatizability)

• 전체 사양 $E$에 대해 데이터가 정보성이 없을 경우, 더 작은 부분 사양 $K \subseteq K_{D_m}$ 에 대해서는 정보성이 성립할 수 있습니다.
• 마킹 정보화 가능성 (Marking Informatizability): 비어 있지 않은 부분 사양 $K$ 가 존재하여 데이터가 정보성을 가지는지 판단하는 개념입니다.
• 최소 제한 마킹 정보성 (Least Restricted Marking Data-Informativity): 가능한 가장 큰 부분 사양 $K_{sup}$ 을 찾는 것입니다. 이는 시스템이 허용할 수 있는 최대한의 동작을 보장하면서도 사양을 만족하는 최적 제어기를 의미합니다.

마. 합성 알고리즘 (Algorithm 3)

• 비정보적 상태 (Non-informative state, 조건을 위반하는 상태) 를 식별하고 제거합니다.
• 수정된 오토마타 ($G_D$) 와 사양 오토마타 ($S_D$) 를 사용하여 표준 감시 제어 이론의 supcon 함수를 적용하여 최대 허용적 (maximally permissive) 인 제어기 $P_D$ 를 계산합니다.
• 결과적으로 얻어진 마킹 언어 $L_m(P_D)$ 가 $K_{sup}$ 이 되며, 이것이 공집합이 아니면 데이터는 '마킹 정보화 가능'하다고 판단합니다.

3. 주요 기여 (Key Contributions)

1. 마킹 데이터 - 정보성 (Marking Data-Informativity) 개념 정립: 기존 데이터 기반 제어 연구가 간과했던 '마킹된 동작 (목표 도달)'을 고려한 새로운 정보성 개념을 제안하고, 이를 위한 필요충분 조건을 수학적으로 증명했습니다.
2. 비차단성 보장: 마킹 정보를 고려함으로써, 단순히 동작을 제어하는 것을 넘어 시스템이 데드락에 빠지지 않고 목표 상태에 도달하도록 보장하는 비차단 제어기 설계 방법을 제시했습니다. (예 4 에서 마킹을 고려하지 않은 경우와 비교하여 차단 경로를 제거하는 효과를 입증).
3. 제한된 정보성 및 최적 합성 알고리즘: 데이터가 전체 사양을 만족하지 못할 때, 데이터가 정보성을 가지는 가장 큰 부분 사양 ($K_{sup}$) 을 자동으로 계산하는 알고리즘을 개발했습니다.
4. 데이터의 양과 질에 대한 통찰: 단순히 데이터의 양 ($D, D_m$) 이 많다고 해서 정보성이 보장되는 것이 아니라, 불가능한 동작에 대한 사전 지식 ($D^-$) 의 '품질'과 관찰 데이터 간의 매칭이 중요함을 강조했습니다.

4. 결과 및 시뮬레이션 (Results)

• 로봇 내비게이션 예시: 미지의 환경에서 로봇이 위험 지점을 피하고 목표 지점에 도달하는 시나리오를 통해 제안된 방법론을 검증했습니다.
  • 결과 1: 마킹 데이터 - 정보성 조건을 만족하는 데이터 세트를 통해 유효한 제어기가 생성됨을 확인했습니다.
  • 결과 2: 마킹 정보를 고려하지 않은 기존 방법과 비교하여, 제안된 방법은 목표 도달 실패 (차단) 를 방지하고 안전한 경로만 허용함을 보였습니다.
  • 결과 3: 초기 데이터가 정보성을 만족하지 못했을 때, Algorithm 3 을 통해 가장 큰 유효한 부분 사양 ($K_{sup}$) 을 추출하여 제어기를 합성할 수 있음을 시연했습니다.

5. 의의 및 결론 (Significance)

• 모델 없는 제어의 실용성: 시스템 모델링이 어렵거나 불가능한 복잡한 환경 (예: 자율 주행, 미지의 환경 탐사) 에서도 수집된 데이터만으로 안전하고 목표 지향적인 제어가 가능함을 입증했습니다.
• 안전성 및 목표 달성: 비차단성 (Nonblocking) 을 보장함으로써 시스템이 멈추거나 데드락에 빠지는 것을 방지하며, 명시된 목표 (Marked states) 를 달성하도록 보장합니다.
• 미래 연구 방향: 제안된 프레임워크는 관측 가능성 (Observability), 진단 가능성 (Diagnosability), 은닉성 (Opacity) 등 다른 중요한 시스템 속성으로 확장 가능하며, 새로운 데이터를 점진적으로 수집하여 제어기를 업데이트하는 적응형 제어 연구의 기초를 제공합니다.

요약하자면, 이 논문은 데이터 기반 DES 제어에 마킹 (목표) 정보를 체계적으로 통합하여, 모델이 불완전한 상황에서도 안전하고 목표 지향적인 비차단 제어를 가능하게 하는 이론적 토대와 알고리즘을 제시한 중요한 연구입니다.