1291.11 상태 머신의 계층적 분해에도 남는 복잡도 문제

1. 계층적 상태 머신의 목적

계층적 상태 머신(Hierarchical State Machine, HSM)은 유한 상태 머신(FSM)의 평탄화된(flat) 상태 공간이 유발하는 관리 불가능한 복잡도를 완화하기 위하여 도입된 확장 모델이다. HSM에서는 복합 상태(composite state)를 통하여 관련된 상태들을 계층적으로 그룹화하고, 추상화 수준(abstraction level)을 도입하여 설계의 가독성과 관리성을 향상시킨다. Harel (1987)의 Statecharts는 이러한 계층적 분해를 형식화한 대표적 모델이다.

계층적 분해는 다음과 같은 원리에 기반한다:

추상화: 하위 상태들의 집합을 하나의 복합 상태로 추상화하여, 상위 수준에서는 세부 사항을 은닉한다.
범위 제한: 복합 상태의 경계 내에서만 유효한 전이를 정의하여, 전이의 영향 범위를 제한한다.
기본 전이 상속: 상위 복합 상태에 정의된 전이가 모든 하위 상태에 상속되어, 반복적 전이 정의를 줄인다.

2. 계층적 분해 후에도 잔존하는 복잡도

2.1 계층 간 전이의 의미론적 복잡성

HSM에서 계층을 횡단하는 전이(cross-hierarchy transition)는 FSM에서는 존재하지 않는 새로운 형태의 복잡도를 유발한다. 다음 유형의 교차 전이가 존재한다:

외부 전이(external transition): 복합 상태 $S_A$ 의 내부 상태에서 $S_A$ 외부의 상태로 직접 전이한다. 이때 $S_A$ 의 퇴출 행동이 실행되어야 하며, 중첩 깊이에 따라 다수의 퇴출 행동이 연쇄적으로 실행될 수 있다.
깊은 전이(deep transition): 복합 상태의 경계를 무시하고 내부의 특정 하위 상태를 직접 대상으로 하는 전이이다. 이는 캡슐화를 파괴하며, 복합 상태의 내부 구조에 대한 외부 의존성을 생성한다.
포크/조인 전이(fork/join transition): 직교 영역의 진입/퇴출 시 복수의 영역을 동시에 활성화하거나 비활성화하는 전이이다.

각 유형의 전이에 대한 의미론(semantics)—진입/퇴출 행동의 실행 순서, 이력 상태의 복원 여부, 직교 영역의 동기화 규칙 등—이 정확하게 정의되어야 하며, 이러한 규칙의 복잡성은 계층 깊이와 전이 유형의 조합에 의하여 증가한다.

2.2 계층 깊이에 따른 진입/퇴출 체인

복합 상태 $S_1 \supset S_2 \supset \cdots \supset S_d$ 와 같이 $d$ 수준의 중첩이 존재할 때, 최하위 상태로의 진입은 $S_1$ 의 진입 행동부터 $S_d$ 의 진입 행동까지 순차적으로 실행하는 진입 체인(entry chain)을 형성한다. 유사하게, 최하위 상태로부터의 퇴출은 역순의 퇴출 체인(exit chain)을 형성한다.

깊이 $d$ 의 진입/퇴출 체인에서 관리해야 하는 행동의 수는 $O(d)$ 이며, 서로 다른 계층 경로 간의 전이에서 어떤 수준까지 퇴출하고 어떤 수준부터 진입할 것인지를 판정하는 최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘이 필요하다.

2.3 이력 상태의 관리 복잡도

이력 상태(history state)는 복합 상태가 마지막으로 활성화되어 있을 때의 내부 상태를 기억하여, 재진입 시 이전 상태를 복원하는 메커니즘이다. 얕은 이력(shallow history, $H$ )은 직접 하위 수준의 마지막 활성 상태만 기억하며, 깊은 이력(deep history, $H^*$ )은 모든 하위 수준의 마지막 활성 상태를 기억한다.

이력 상태의 관리에서 발생하는 복잡도는 다음과 같다:

이력 저장소 관리: 각 복합 상태에 대한 이력 정보를 저장하고 갱신하는 메커니즘이 필요하다.
이력 유효성 검증: 복합 상태의 구조가 변경된 경우, 기존 이력 정보가 여전히 유효한 상태를 참조하는지 검증해야 한다.
깊은 이력의 재귀적 복원: $H^*$ 는 중첩된 모든 수준의 이력을 재귀적으로 복원해야 하며, 중첩 깊이에 비례하는 복원 비용이 발생한다.

2.4 상태 공간의 실질적 크기 미감소

계층적 분해는 설계 표현(design representation)의 복잡도를 감소시키나, 시스템의 실제 실행 상태 공간(execution state space)은 감소하지 않는다. $p$ 개의 직교 영역이 각각 $s_i$ 개의 리프 상태를 가질 때, 실행 가능한 상태 조합의 수는 여전히 $\prod_{i=1}^{p} s_i$ 이다.

이는 모델 검사(model checking), 도달 가능성 분석(reachability analysis), 경로 기반 테스트(path-based testing) 등 형식적 검증 기법의 계산 복잡도가 계층적 분해에 의하여 감소하지 않음을 의미한다. 계층적 표현은 인간 설계자의 인지적 부하를 완화하나, 자동화된 검증 도구의 부담은 경감하지 못한다.

2.5 계층 설계의 임의성

HSM에서 어떤 상태들을 하나의 복합 상태로 묶을 것인가의 결정—즉 분해 기준(decomposition criteria)—은 형식적으로 정의되지 않으며, 설계자의 판단에 의존한다. 동일한 시스템에 대하여 다수의 상이한 계층 분해가 가능하며, 분해의 품질에 따라 관리 용이성이 크게 달라진다.

최적이 아닌 계층 분해는 다음과 같은 문제를 유발한다:

과도한 계층 횡단 전이: 빈번하게 상호작용하는 상태들이 서로 다른 복합 상태에 배치된 경우, 계층을 횡단하는 전이가 다수 발생하여 계층화의 이점이 상실된다.
불균등한 추상화 수준: 일부 복합 상태는 다수의 하위 상태를 포함하고 다른 복합 상태는 소수의 하위 상태만 포함하는 불균등한 계층 구조가 형성될 수 있다.
리팩토링의 어려움: 계층 구조의 변경은 해당 복합 상태의 경계를 통과하는 모든 전이의 재정의를 요구하며, 이력 상태 정보의 무효화를 초래할 수 있다.

3. 행동 트리의 구조적 이점

행동 트리에서 계층적 분해는 서브트리(subtree)의 중첩으로 자연스럽게 실현되며, 다음과 같은 점에서 HSM의 잔존 복잡도가 해소된다:

전이 규칙의 부재: 서브트리 간에 명시적 전이가 존재하지 않으므로, 계층 횡단 전이의 문제가 원천적으로 발생하지 않는다.
이력 상태의 불필요: Tick 기반 재평가에 의하여 매 주기마다 적절한 리프 노드까지의 경로가 결정되므로, 별도의 이력 관리가 필요하지 않다.
분해의 구성적 특성: 서브트리의 추가와 제거가 다른 서브트리에 영향을 미치지 않으므로, 계층 구조의 리팩토링이 국소적 작업으로 제한된다.

4. 참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
Samek, M. (2008). Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems. 2nd ed., Newnes.

v0.1.0