1291.6 직교 영역 기반 동시성의 설계 복잡도

1291.6 직교 영역 기반 동시성의 설계 복잡도

1. Statecharts와 직교 영역의 개념

Harel (1987)이 제안한 Statecharts는 유한 상태 머신(FSM)의 상태 폭발 문제를 완화하기 위하여 세 가지 핵심 확장 메커니즘을 도입하였다: 계층적 상태 중첩(state nesting), 직교 영역(orthogonal region), 이력 상태(history state). 이 중 직교 영역은 다중 병행 행동의 표현을 위하여 설계된 메커니즘으로, 복합 상태(composite state) 내부에 독립적으로 진행되는 복수의 하위 상태 머신을 정의함으로써, 상태 공간의 곱적 평탄화(flat product) 없이 동시성(concurrency)을 표현한다.

직교 영역을 탑재한 복합 상태 S_{\text{comp}}가 p개의 직교 영역 R_1, R_2, \ldots, R_p를 포함할 때, 시스템은 각 영역의 현재 상태를 독립적으로 유지하며, 전체 시스템의 상태는 각 영역의 현재 상태의 튜플 (q_1, q_2, \ldots, q_p)로 표현된다. 이는 개념적으로 상태 공간의 곱 Q_1 \times Q_2 \times \cdots \times Q_p를 나타내나, 설계 표현에서는 각 영역을 독립적으로 기술하므로 상태 수의 합적(additive) 표현이 가능하다.

2. 직교 영역이 완화하는 문제

직교 영역의 도입으로 다음과 같은 문제가 완화된다:

  1. 상태 수의 합적 표현: p개의 직교 영역이 각각 s_i개의 상태를 가질 때, 명시적으로 정의해야 하는 상태의 수는 \sum_{i=1}^{p} s_i이며, 이는 평탄화된 곱공간의 \prod_{i=1}^{p} s_i에 비하여 크게 감소한다.
  2. 독립적 전이 정의: 각 영역 내부의 전이는 해당 영역의 상태에만 적용되므로, 다른 영역의 상태와 독립적으로 정의될 수 있다.
  3. 시각적 분리: 상태 전이 다이어그램에서 각 영역이 시각적으로 분리되어 표현되므로 가독성이 향상된다.

3. 직교 영역이 유발하는 추가 설계 복잡도

그러나 직교 영역은 상태 평탄화 문제를 완화하는 대가로 새로운 형태의 설계 복잡도를 유발한다.

3.1 영역 간 동기화 이벤트

독립적으로 실행되는 직교 영역이 상호작용해야 하는 경우, 영역 간 통신을 위한 동기화 이벤트(synchronization event)가 필요하다. 예를 들어, “감시” 영역에서 장애물을 감지한 경우 “이동” 영역의 현재 행동을 중단하고 회피 행동으로 전환해야 한다면, 감시 영역에서 이동 영역으로의 이벤트 전달이 정의되어야 한다.

p개의 직교 영역 간의 양방향 이벤트 채널(bidirectional event channel)의 최대 수는

C_{\text{events}} = p \times (p - 1)

이며, 각 채널에서 전달되는 이벤트의 종류와 수신 측의 반응 규칙을 정의해야 한다. p = 5인 경우 20개의 이벤트 채널이 존재하며, 각 채널에 대한 이벤트 종류가 3–5개라면 60–100개의 영역 간 상호작용 규칙이 필요하다.

3.2 이벤트 순서 의존성

동기화 이벤트의 처리 순서(event ordering)는 시스템의 행동에 중대한 영향을 미친다. 동일 Tick 또는 동일 시각에 복수의 직교 영역에서 이벤트가 동시에 발생할 경우, 이벤트의 처리 순서에 따라 시스템의 최종 상태가 달라질 수 있다. Harel의 원래 Statecharts 형식론에서는 이벤트의 동시 처리를 가정하나, 실제 구현에서는 순차적 처리가 불가피하며, 이때 처리 순서의 결정이 설계상의 추가적 관심사로 부상한다.

3.3 복합 전이의 의미론적 복잡성

직교 영역을 포함하는 복합 상태에서 외부 상태로의 전이(exit transition)가 발생할 때, 모든 직교 영역의 현재 활성 상태에 대한 퇴출 행동(exit action)이 올바른 순서로 실행되어야 한다. 역으로, 복합 상태로의 진입 전이(entry transition)에서는 모든 직교 영역이 각각의 초기 상태 또는 이력 상태로 진입해야 한다.

이러한 계층 횡단 전이(cross-hierarchy transition)의 의미론은 다음과 같은 규칙을 동시에 만족해야 한다:

  1. 현재 복합 상태 내 모든 활성 영역의 퇴출 행동을 리프에서 루트 방향으로 실행한다.
  2. 대상 상태가 속한 계층 경로를 따라 루트에서 리프 방향으로 진입 행동을 실행한다.
  3. 이력 상태가 관련된 경우, 가장 최근의 활성 상태 정보를 복원한다.

이 규칙들의 정합적 구현은 상태 계층의 깊이와 직교 영역의 수가 증가할수록 복잡해진다.

3.4 테스트와 검증의 난이도

직교 영역의 도입은 형식적 검증의 관점에서도 추가적인 과제를 유발한다. 비록 설계 표현에서는 각 영역이 독립적으로 기술되나, 시스템의 실제 실행 상태 공간은 여전히 곱공간 Q_1 \times Q_2 \times \cdots \times Q_p이므로, 모델 검사(model checking) 시 탐색해야 하는 상태 공간의 크기는 평탄화된 FSM과 동일한 \prod s_i이다. 즉, 직교 영역은 설계의 편의성을 향상시키나 검증의 본질적 복잡도를 감소시키지는 않는다.

4. 구현 도구의 한계

ROS2 생태계에서 SMACH (Bohren & Cousins, 2010), FlexBE (Schillinger et al., 2016) 등의 상태 머신 라이브러리는 Statecharts의 일부 기능을 지원하나, 직교 영역의 완전한 의미론적 구현을 제공하지 않는 경우가 많다. 특히 영역 간 동기화 이벤트의 체계적 관리, 계층 횡단 전이의 정확한 의미론, 이력 상태의 복원 등이 제한적으로만 지원되며, 이는 실무적으로 Statecharts 기반 설계의 이론적 장점이 구현 수준에서 충분히 실현되지 않음을 의미한다.

5. 행동 트리와의 비교

행동 트리에서는 Parallel 노드가 직교 영역의 동시성 개념을 구조적으로 대체한다. Parallel 노드의 자식 서브트리는 매 Tick에서 독립적으로 실행되며, 노드의 성공 정책에 의하여 전체 결과가 결정된다. 서브트리 간의 데이터 공유는 블랙보드(Blackboard)를 통하여 간접적으로 이루어지므로, 직교 영역 간 동기화 이벤트에 해당하는 별도의 통신 메커니즘을 정의할 필요가 없다. 또한 서브트리의 추가와 제거가 다른 서브트리에 미치는 영향이 국소적이므로, 확장성이 구조적으로 보장된다.

6. 참고 문헌

  • Bohren, J., & Cousins, S. (2010). “The SMACH High-Level Executive.” IEEE Robotics & Automation Magazine, 17(4), 18–20.
  • 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.
  • Schillinger, P., Kohlbrecher, S., & von Stryk, O. (2016). “Human-Robot Collaborative High-Level Control with Application to Rescue Robotics.” IEEE International Conference on Robotics and Automation (ICRA), 2796–2801.

v0.1.0