1291.9 상태 머신의 확장 시 전이 규칙 수정의 파급 효과

1. 파급 효과의 개념

소프트웨어 공학에서 파급 효과(ripple effect)란 시스템의 한 부분에 대한 수정이 직접적으로 관련되지 않은 다른 부분에까지 영향을 미치는 현상이다. Yau와 Collofello (1980)는 코드 수정의 파급 효과를 정량적으로 분석하여, 높은 결합도를 가진 시스템에서 파급 효과가 증폭됨을 입증하였다. 유한 상태 머신(FSM)은 상태와 전이 간의 높은 결합도로 인하여 확장 시 광범위한 파급 효과를 발생시키는 대표적 아키텍처이다.

2. 상태 추가의 파급 효과

기존 $n$ 개의 상태를 가진 FSM에 새로운 상태 $q_{\text{new}}$ 를 추가하는 시나리오를 분석한다.

2.1 진입 전이의 정의

$q_{\text{new}}$ 로의 진입 전이를 정의해야 한다. $q_{\text{new}}$ 에 도달할 수 있는 기존 상태가 $k$ 개이고, 각 상태에서 $q_{\text{new}}$ 로의 전이를 유발하는 이벤트가 평균 $e$ 개라면, 추가해야 하는 진입 전이의 수는 $k \times e$ 이다. 이 전이 각각에 대하여 가드 조건(guard condition)과 행동(action)을 정의해야 하며, 기존 상태의 전이 테이블에 새로운 항목을 추가해야 한다.

2.2 퇴출 전이의 정의

$q_{\text{new}}$ 로부터의 퇴출 전이를 정의해야 한다. $q_{\text{new}}$ 에서 도달할 수 있는 대상 상태가 $l$ 개이고, 각 전이를 유발하는 이벤트가 평균 $e$ 개라면, $l \times e$ 개의 퇴출 전이가 추가된다.

2.3 긴급 전이의 일관성

시스템에 $e_{\text{emerg}}$ 개의 긴급 전이(비상 정지, 긴급 복귀 등)가 정의되어 있는 경우, $q_{\text{new}}$ 에서도 동일한 긴급 전이가 적용되어야 한다. 이는 $e_{\text{emerg}}$ 개의 추가 전이를 요구하며, 기존 긴급 전이의 일관성을 검증해야 한다.

2.4 기존 전이의 재검토

$q_{\text{new}}$ 의 추가가 기존 전이에 미치는 잠재적 영향을 검토해야 한다. 기존 상태 간의 전이 중 $q_{\text{new}}$ 를 경유해야 하거나, $q_{\text{new}}$ 의 존재로 인하여 전이 조건이 변경되어야 하는 경우가 있을 수 있다.

총 파급 비용은 다음과 같이 추정된다:

$C_{\text{add}} = (k \times e) + (l \times e) + e_{\text{emerg}} + C_{\text{review}}$

여기서 $C_{\text{review}}$ 는 기존 전이의 재검토 비용이다.

3. 상태 제거의 파급 효과

기존 상태 $q_{\text{old}}$ 를 제거하는 경우, 파급 효과는 더욱 광범위하다:

진입 전이의 무효화: $q_{\text{old}}$ 를 대상으로 하는 모든 전이 $\delta(q_i, \sigma) = q_{\text{old}}$ 가 무효화되며, 이 전이들의 대상을 다른 상태로 재지정해야 한다.
퇴출 전이의 상실: $q_{\text{old}}$ 에서 출발하는 모든 전이가 상실되며, $q_{\text{old}}$ 를 거쳐야만 도달 가능했던 상태가 도달 불능(unreachable)이 되지 않는지 검증해야 한다.
도달 가능성 분석: 상태 $q_{\text{old}}$ 의 제거 후 FSM의 도달 가능성(reachability) 분석을 재수행하여, 모든 상태가 초기 상태에서 도달 가능한지 확인해야 한다.

4. 전이 규칙 수정의 파급 효과

기존 전이 $\delta(q_i, \sigma) = q_j$ 를 $\delta(q_i, \sigma) = q_k$ 로 변경하는 경우:

경로 변경: $q_i$ 를 통하여 $q_j$ 에 도달하는 기존 실행 경로가 무효화되며, $q_k$ 를 경유하는 새로운 경로의 정합성을 검증해야 한다.
불변 조건의 위반: $q_j$ 에 대하여 “항상 도달 가능“이라는 불변 조건(invariant)이 존재했다면, 전이 변경 후 이 불변 조건이 여전히 유지되는지 확인해야 한다.
연쇄적 재조정: 변경된 전이가 다른 전이의 전제 조건(precondition)에 영향을 미치는 경우, 연쇄적인 전이 재조정이 필요할 수 있다.

5. 파급 효과의 정량적 모델

FSM의 파급 효과를 상태-전이 그래프의 연결 특성으로 모델링할 수 있다. 상태 $q_i$ 의 수정 파급 범위(ripple scope) $R(q_i)$ 를 $q_i$ 에서 전이 그래프를 통하여 $d$ 단계 이내에 도달 가능한 상태의 수로 정의하면:

$R_d(q_i) = |\{q_j \in Q \mid \text{dist}(q_i, q_j) \leq d\}|$

밀접하게 연결된 FSM에서 평균 도달 범위 $\bar{R}_d$ 는 상태 수 $n$ 에 대하여 $d$ 가 작아도 $n$ 에 근접할 수 있으며, 이는 하나의 수정이 전체 시스템에 영향을 미칠 수 있음을 의미한다.

6. 행동 트리에서의 파급 효과 제한

행동 트리에서 노드의 추가, 제거, 수정은 해당 노드의 직접적 부모와 자식에만 영향을 미친다. 트리의 다른 브랜치에 위치한 노드는 수정의 영향을 받지 않으며, 이는 트리 구조의 본질적 특성—각 노드가 정확히 하나의 부모를 가지며, 형제 노드 간에 직접적 전이가 존재하지 않음—에 기인한다.

노드 $v$ 의 수정 파급 범위는 $v$ 의 직접 부모와 자식으로 제한되므로:

$R(v) = 1 + \text{children}(v)$

이는 FSM에서의 $R_d(q_i) \approx n$ 수준과 비교하여 근본적으로 제한된 파급 범위이며, 행동 트리의 확장성이 FSM 대비 우수한 핵심적 구조적 근거이다.

7. 참고 문헌

Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Yau, S. S., & Collofello, J. S. (1980). “Some Stability Measures for Software Maintenance.” IEEE Transactions on Software Engineering, SE-6(6), 545–552.

v0.1.0