396.44 계층적 상태 머신(Hierarchical FSM)의 적용
1. 개요
계층적 상태 머신(Hierarchical Finite State Machine, HFSM)은 평탄한(Flat) FSM의 상태 폭발 문제를 극복하기 위해 상태를 계층적으로 구조화한 확장 모델이다. HFSM은 Harel(1987)이 제안한 스테이트차트(Statecharts)에 이론적 기반을 두며, 상태의 중첩(Nesting), 직교적 분해(Orthogonal Decomposition), 그리고 이력(History) 메커니즘을 통해 복잡한 임무 관리 시스템의 설계를 체계화한다.
2. 스테이트차트의 형식적 정의
2.1 기본 구조
스테이트차트는 다음의 구성 요소로 정의된다(Harel, 1987).
\text{SC} = (S, s_0, E, A, \delta, H)
- S: 상태의 집합 (계층 구조 포함)
- s_0 \in S: 초기 상태
- E: 이벤트의 집합
- A: 행동의 집합
- \delta: 전이 함수
- H: 계층 함수 (상태 간 포함 관계)
2.2 상태의 계층적 분류
스테이트차트에서 상태는 다음의 세 가지 유형으로 분류된다.
기본 상태(Basic State): 더 이상 분해되지 않는 원자적(Atomic) 상태이다.
s \in S_{\text{basic}} \iff \text{children}(s) = \emptyset
합성 상태(Composite State): 하위 상태(Substate)를 포함하는 상태이다. 합성 상태에 진입하면 그 내부의 초기 하위 상태가 활성화된다.
s \in S_{\text{composite}} \iff \text{children}(s) \neq \emptyset
직교 상태(Orthogonal State): 복수의 직교 영역(Orthogonal Region)을 포함하며, 각 영역이 독립적으로 동시에 활성화된다.
s \in S_{\text{orthogonal}} \iff s = R_1 \parallel R_2 \parallel \ldots \parallel R_k
여기서 R_i는 직교 영역, \parallel은 병렬 합성 연산자이다.
2.3 포함 관계와 계층 트리
상태의 포함 관계는 트리 구조로 표현된다. 상태 s_i가 상태 s_j의 하위 상태이면, s_j를 s_i의 상위 상태(Superstate)라 한다.
H : S \rightarrow S \cup \{\text{root}\}
여기서 H(s)는 상태 s의 부모 상태를 반환한다. 최상위 상태(Root State)는 부모가 없다.
\text{depth}(s) = \begin{cases} 0 & \text{if } H(s) = \text{root} \\ 1 + \text{depth}(H(s)) & \text{otherwise} \end{cases}
3. HFSM의 핵심 메커니즘
3.1 상태 중첩(State Nesting)
상태 중첩은 관련된 상태들을 하나의 합성 상태로 그룹화하는 메커니즘이다. 이를 통해 공통적인 전이를 합성 상태 수준에서 한 번만 정의할 수 있다.
예를 들어, 임무 수행 중 어떤 하위 상태에 있든 비상 정지 이벤트에 대한 전이는 합성 상태에서 한 번만 정의하면 된다.
┌──────────── MISSION_ACTIVE ─────────────┐
│ │
│ ┌─────────┐ ┌──────────┐ ┌─────┐ │
│ │NAVIGATE │───→│ INSPECT │───→│REPORT│ │
│ └─────────┘ └──────────┘ └─────┘ │
│ │
└────────────────────┬─────────────────────┘
│ emergency_stop
↓
┌──────────┐
│ EMERGENCY│
└──────────┘
평탄한 FSM에서는 NAVIGATE, INSPECT, REPORT 각 상태에서 EMERGENCY로의 전이를 개별적으로 정의하여야 한다. HFSM에서는 MISSION_ACTIVE 합성 상태에서의 단일 전이로 이를 간결하게 표현한다.
전이 절감 효과를 정량적으로 분석하면, n개의 하위 상태와 k개의 전역 이벤트가 있을 때 다음과 같다.
\Delta|\delta| = n \times k - k = k(n - 1)
3.2 그룹 전이(Group Transition)
합성 상태에 정의된 전이는 해당 합성 상태 내의 모든 하위 상태에 자동으로 적용된다. 이를 그룹 전이(Group Transition)라 한다.
\delta(s_{\text{composite}}, e) = s' \implies \forall s_i \in \text{descendants}(s_{\text{composite}}) : \delta(s_i, e) = s'
그룹 전이는 오류 처리, 비상 정지, 타임아웃 등 전역적 이벤트의 처리에 특히 효과적이다.
3.3 기본 진입 전이(Default Entry Transition)
합성 상태에 진입할 때 활성화되는 하위 상태를 결정하는 기본 진입 전이(Default Entry Transition)가 정의된다.
\text{defaultEntry}(s_{\text{composite}}) = s_{0,\text{sub}} \in \text{children}(s_{\text{composite}})
3.4 이력 메커니즘(History Mechanism)
이력 메커니즘은 합성 상태를 이탈한 후 재진입할 때, 마지막으로 활성화되었던 하위 상태를 기억하고 복원하는 기능이다.
얕은 이력(Shallow History, H): 직계 하위 상태만 기억한다.
H : s_{\text{composite}} \rightarrow \text{children}(s_{\text{composite}})
깊은 이력(Deep History, H)*: 모든 중첩 수준의 활성 상태를 기억한다.
H^* : s_{\text{composite}} \rightarrow \text{activeConfiguration}(s_{\text{composite}})
임무 관리에서 이력 메커니즘은 임무 중단 후 재개 시 이전 실행 상태를 복원하는 데 활용된다. 예를 들어, 순찰 임무 중 비상 상황이 발생하여 임무를 일시 중단한 후, 비상이 해소되면 이력 메커니즘을 통해 중단 시점의 순찰 상태로 복귀할 수 있다.
3.5 직교 영역(Orthogonal Regions)
직교 영역은 독립적으로 동시에 활성화되는 병렬 상태 영역이다. 이를 통해 동시성을 명시적으로 표현할 수 있다.
s_{\text{orthogonal}} = R_1 \parallel R_2 \parallel \ldots \parallel R_k
각 영역 R_i는 독립적인 FSM으로 동작하며, 영역 간의 상호작용은 이벤트 방송(Event Broadcasting)이나 가드 조건(Guard Condition)을 통해 이루어진다.
임무 관리 맥락에서 직교 영역의 활용 예시는 다음과 같다.
┌────────────── MISSION_ACTIVE ──────────────────┐
│ │
│ ┌── 임무 실행 영역 ──┐ ┌── 모니터링 영역 ──┐ │
│ │ NAVIGATE → INSPECT │ │ BATTERY_CHECK │ │
│ │ → REPORT │ │ COMM_STATUS │ │
│ └────────────────────┘ └───────────────────┘ │
│ │
└──────────────────────────────────────────────────┘
직교 영역을 통한 상태 수 절감은 다음과 같이 분석된다.
|Q_{\text{orthogonal}}| = \sum_{i=1}^{k} |Q_{R_i}| \quad \text{vs.} \quad |Q_{\text{flat}}| = \prod_{i=1}^{k} |Q_{R_i}|
예를 들어, 5개의 영역이 각각 4개의 상태를 가질 때, 직교 표현에서는 5 \times 4 = 20개의 상태로 충분하지만, 평탄한 FSM에서는 4^5 = 1024개의 상태가 필요하다.
4. 로봇 임무 관리에서의 HFSM 적용
4.1 임무-과업-행동 계층의 매핑
HFSM의 계층 구조는 임무 관리의 자연스러운 추상화 계층과 직접적으로 대응된다.
| HFSM 계층 수준 | 임무 관리 추상화 | 예시 |
|---|---|---|
| 최상위 (Level 0) | 임무(Mission) | 순찰 임무 |
| 중간 (Level 1) | 과업(Task) | 지점 A 감시 |
| 하위 (Level 2) | 행동(Behavior) | A로 이동, 센서 스캔 |
| 최하위 (Level 3) | 원시 행동(Primitive) | 모터 제어, 센서 읽기 |
4.2 다중 계층 임무 FSM의 설계 예시
감시-순찰 임무를 HFSM으로 설계하면 다음과 같다.
PATROL_MISSION (Level 0)
├── INITIALIZE (Level 1)
│ ├── SELF_CHECK (Level 2)
│ └── LOAD_WAYPOINTS (Level 2)
├── PATROL (Level 1)
│ ├── NAVIGATE_TO_WP (Level 2)
│ │ ├── COMPUTE_PATH (Level 3)
│ │ └── FOLLOW_PATH (Level 3)
│ ├── OBSERVE (Level 2)
│ │ ├── SCAN_ENVIRONMENT (Level 3)
│ │ └── ANALYZE_DATA (Level 3)
│ └── REPORT (Level 2)
├── RETURN_TO_BASE (Level 1)
└── EMERGENCY (Level 1)
├── SAFE_LANDING (Level 2)
└── WAIT_FOR_RESCUE (Level 2)
4.3 전이의 유형과 의미론
HFSM에서는 전이의 유형이 다양화된다.
내부 전이(Internal Transition): 동일 합성 상태 내의 하위 상태 사이의 전이이다.
\delta_{\text{internal}} : s_i \rightarrow s_j, \quad H(s_i) = H(s_j)
외부 전이(External Transition): 서로 다른 합성 상태에 속하는 상태 사이의 전이이다.
\delta_{\text{external}} : s_i \rightarrow s_j, \quad H(s_i) \neq H(s_j)
자기 전이(Self-Transition): 동일 상태로의 전이로, 이탈 행동과 진입 행동이 재실행된다.
\delta_{\text{self}} : s_i \rightarrow s_i
외부 전이 시에는 공통 조상(Least Common Ancestor, LCA)까지의 이탈 행동과 목표 상태까지의 진입 행동이 순차적으로 실행된다.
\text{exitSequence}(s_{\text{source}}, \text{LCA}) \rightarrow \text{entrySequence}(\text{LCA}, s_{\text{target}})
5. HFSM의 구현 프레임워크
5.1 SMACH의 계층 구조 지원
ROS1의 SMACH 프레임워크는 StateMachine 컨테이너를 중첩하여 HFSM을 구현할 수 있다(Bohren & Cousins, 2010). 거시적 상태 머신(Top-Level SM) 내부에 하위 상태 머신을 중첩함으로써 계층적 구조를 형성한다.
5.2 UML 스테이트 다이어그램
UML(Unified Modeling Language)의 스테이트 다이어그램(State Machine Diagram)은 Harel의 스테이트차트를 기반으로 하며, 합성 상태, 직교 영역, 이력 의사 상태(History Pseudostate) 등을 표준화된 표기법으로 지원한다(OMG, 2017).
5.3 YAKINDU Statechart Tools
YAKINDU Statechart Tools는 스테이트차트의 시각적 설계, 시뮬레이션, 코드 생성을 지원하는 통합 개발 환경(IDE)이다. C, C++, Java 등의 대상 언어로 자동 코드 생성이 가능하며, 형식적 검증 기능도 제공한다(Itemis AG, n.d.).
6. HFSM의 형식적 분석
6.1 계층적 검증
HFSM의 계층 구조는 검증을 단순화하는 데 기여한다. 각 합성 상태의 내부를 독립적으로 검증한 후, 상위 수준에서 합성 상태를 추상적으로 검증하는 분할 정복(Divide and Conquer) 전략이 적용된다.
\text{Verify}(M) = \bigwedge_{s \in S_{\text{composite}}} \text{Verify}_{\text{local}}(s) \wedge \text{Verify}_{\text{global}}(M_{\text{abstract}})
6.2 상태 정제(State Refinement)
합성 상태의 내부 구조를 점진적으로 상세화하는 정제(Refinement) 과정은 HFSM의 설계 방법론에서 핵심적이다. 수학적으로, 정제 관계 \sqsubseteq는 다음과 같이 정의된다.
M_{\text{abstract}} \sqsubseteq M_{\text{refined}} \iff \text{Traces}(M_{\text{abstract}}) \supseteq \text{Traces}(M_{\text{refined}})
정제된 모델의 실행 트레이스(Trace)는 추상 모델의 트레이스의 부분 집합이므로, 추상 모델에서 검증된 속성이 정제된 모델에서도 보존된다.
7. HFSM의 장점과 한계
7.1 장점
- 상태 폭발 완화: 계층적 분해와 직교 영역을 통해 상태 수를 지수적에서 선형적으로 감소시킨다.
- 재사용성 향상: 합성 상태를 독립적인 모듈로 정의하여 여러 임무에서 재사용할 수 있다.
- 가독성 향상: 추상화 수준별로 세부 사항을 은닉(Information Hiding)하여 설계의 가독성을 향상시킨다.
- 점진적 설계: 상위 구조를 먼저 설계하고 하위 세부 사항을 점진적으로 추가하는 하향식 설계 방법론을 지원한다.
- 이력을 통한 임무 재개: 이력 메커니즘을 통해 임무 중단 후 재개가 자연스럽게 지원된다.
7.2 한계
- 여전한 상태 중심 설계: 행동의 모듈적 조합보다는 상태의 전이에 초점이 맞추어져 있어, 동적인 행동 합성에는 부적합하다.
- 전이 복잡도: 계층 간 전이의 의미론이 복잡하여 설계자의 이해 부담이 증가할 수 있다.
- 직교 영역 간 동기화: 병렬 영역 간의 복잡한 동기화 요구사항이 존재할 경우, 설계의 복잡도가 증가한다.
8. 요약
HFSM은 평탄한 FSM의 상태 폭발 문제를 계층적 분해, 직교 영역, 이력 메커니즘을 통해 체계적으로 완화한다. 임무-과업-행동의 계층적 구조와 자연스럽게 대응되며, SMACH, UML 스테이트 다이어그램, YAKINDU 등의 도구를 통한 실용적 구현이 지원된다. 분할 정복 기반의 검증 전략과 정제 관계를 통해 형식적 분석의 효율성도 향상된다.
9. 참고 문헌
- Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
- Bohren, J., & Cousins, S. (2010). “The SMACH High-Level Executive.” IEEE Robotics & Automation Magazine, 17(4), 18–20.
- OMG. (2017). Unified Modeling Language (UML) Specification, Version 2.5.1. Object Management Group.
- Harel, D., & Naamad, A. (1996). “The STATEMATE Semantics of Statecharts.” ACM Transactions on Software Engineering and Methodology, 5(4), 293–333.
- Alur, R., Kannan, S., & Yannakakis, M. (1999). “Communicating Hierarchical State Machines.” Proceedings of ICALP, LNCS 1644, pp. 169–178.
v0.1