1291.56 전이 규칙 없이 제어 흐름 구성 (Composing Control Flow without Transition Rules)

1. 전이 규칙 기반 제어 흐름의 특성

유한 상태 머신(Finite State Machine, FSM)에서 제어 흐름은 **전이 규칙(transition rule)**에 의하여 정의된다. 전이 규칙은 현재 상태(source state), 전이 조건(guard condition), 그리고 목표 상태(target state)의 3요소로 구성되며, 형식적으로 다음과 같이 표현된다.

\delta: S \times \Sigma \rightarrow S

여기서 S는 상태 집합, \Sigma는 입력 기호(또는 이벤트) 집합, \delta는 전이 함수이다. 전이 규칙은 “상태 s_i에서 조건 \sigma가 만족되면 상태 s_j로 전이한다“는 형태로 개별적으로 정의되며, 시스템의 제어 흐름은 이 전이 규칙의 총체에 의하여 결정된다.

전이 규칙 기반 제어 흐름은 다음의 구조적 특성을 갖는다.

• 명시적 참조: 각 전이 규칙은 원천 상태와 목표 상태를 명시적으로 참조한다.
• 전역적 분산: 전이 규칙은 시스템 전체에 걸쳐 분산되어 정의된다.
• 맥락 의존성: 전이 조건의 해석이 현재 상태에 의존한다.

이 특성들은 시스템의 규모가 증가할 때 전이 규칙의 수가 급증하고, 규칙 간의 상호작용이 복잡해지며, 전체 제어 흐름의 파악이 어려워지는 근본적 원인이 된다.

2. 행동 트리의 전이 규칙 부재

행동 트리(Behavior Tree, BT)에서는 유한 상태 머신에서와 같은 명시적 전이 규칙이 존재하지 않는다. 행동 트리의 제어 흐름은 전이 규칙의 정의에 의해서가 아니라, 다음 두 메커니즘의 조합에 의하여 결정된다.

1. 제어 노드의 유형(type): Sequence, Fallback, Parallel 등 제어 노드의 유형이 자식 노드에 대한 제어 정책을 결정한다.
2. 자식 노드의 배치 순서(order): 동일 제어 노드 아래에서 자식 노드의 좌-우 배치 순서가 실행 및 평가의 우선순위를 결정한다.

이 두 메커니즘만으로 행동의 순차 실행, 대안적 선택, 병행 실행, 우선순위 기반 반응 등 로봇 행동 제어에 필요한 제어 흐름 패턴이 모두 표현된다.

3. 제어 노드에 의한 제어 흐름 패턴

3.1 Sequence에 의한 순차 실행

Sequence 노드는 자식 노드를 좌측부터 순서대로 실행하며, 모든 자식이 Success를 반환하면 Success를, 하나의 자식이 Failure를 반환하면 Failure를 반환한다.

\text{Sequence}(c_1, c_2, \ldots, c_n) = \begin{cases} Success & \text{if } \forall i: c_i = Success \\ Failure & \text{if } \exists i: c_i = Failure \\ Running & \text{otherwise} \end{cases}

이 제어 정책은 유한 상태 머신에서 “상태 s_1이 완료되면 s_2로 전이, s_2가 완료되면 s_3로 전이, …“라는 일련의 전이 규칙을 대체한다. n개의 순차적 행동에 대하여 유한 상태 머신에서는 n-1개의 전이 규칙이 필요하지만, 행동 트리에서는 하나의 Sequence 노드에 n개의 자식을 배치하는 것으로 충분하다.

3.2 Fallback에 의한 대안적 선택

Fallback(또는 Selector) 노드는 자식 노드를 좌측부터 순서대로 실행하며, 하나의 자식이 Success를 반환하면 Success를, 모든 자식이 Failure를 반환하면 Failure를 반환한다.

\text{Fallback}(c_1, c_2, \ldots, c_n) = \begin{cases} Success & \text{if } \exists i: c_i = Success \\ Failure & \text{if } \forall i: c_i = Failure \\ Running & \text{otherwise} \end{cases}

이 제어 정책은 “행동 c_1을 시도하고, 실패하면 c_2를 시도하고, 그것도 실패하면 c_3를 시도한다“는 우선순위 기반 대안 선택을 표현한다. 유한 상태 머신에서 동일한 패턴을 구현하려면, 각 상태에서의 실패 전이를 다음 대안 상태로 연결하는 전이 규칙을 개별적으로 정의하여야 한다.

3.3 Parallel에 의한 병행 실행

Parallel 노드는 모든 자식 노드를 동시에 실행하며, 성공 임계값(success threshold)에 기반하여 반환 상태를 결정한다.

유한 상태 머신에서 병행 실행을 표현하려면 직교 영역(orthogonal region)이나 별도의 동시 상태 머신을 도입하여야 하며, 동기화(synchronization)를 위한 추가적 전이 규칙이 필요하다. 행동 트리에서는 Parallel 노드 하나로 병행 실행이 표현된다.

3.4 조건-행동 패턴에 의한 조건부 실행

행동 트리에서 조건부 실행은 Condition 노드와 Action 노드를 Sequence의 자식으로 배치하는 것으로 간단히 표현된다.

Sequence
├── Condition: "IsBatteryLow"
└── Action: "ReturnToCharger"

이 패턴은 “배터리가 부족하면 충전소로 복귀한다“는 조건부 행동을 나타낸다. Condition 노드가 Failure를 반환하면 Sequence는 즉시 Failure를 반환하여 Action 노드가 실행되지 않는다. 유한 상태 머신에서 동일한 패턴을 구현하려면, “배터리 부족” 조건을 전이 가드(guard)로 정의하고 현재 상태에서 “충전 복귀” 상태로의 전이 규칙을 명시적으로 작성하여야 한다.

4. 전이 규칙 부재의 공학적 이점

4.1 설계 복잡도의 감소

n개의 행동을 가진 제어 시스템에서 전이 규칙의 수는 행동 간의 상호 관계에 비례하여 증가한다. 유한 상태 머신에서 전이 규칙의 수는 최악의 경우 O(n^2)에 달하며, 설계자는 이 전이 규칙을 하나하나 정의하고 검증하여야 한다.

행동 트리에서는 전이 규칙이 존재하지 않으므로, 설계자가 정의하여야 할 요소는 노드의 유형 선택과 자식의 배치 순서뿐이다. 이는 설계 복잡도를 O(n)으로 감소시킨다.

4.2 비결정성의 구조적 제거

유한 상태 머신에서 하나의 상태에 대하여 동일한 입력 기호에 대응하는 전이 규칙이 다수 존재하면, 비결정적 유한 상태 머신(NFA: Nondeterministic Finite Automaton)이 되며, 실행 경로의 예측이 불가능해진다. 실용적 시스템에서는 이를 방지하기 위하여 전이 조건 간의 상호 배타성(mutual exclusivity)과 우선순위를 명시적으로 정의하고 검증하여야 한다.

행동 트리에서는 제어 흐름이 트리의 깊이 우선 순회(depth-first traversal)에 의하여 결정론적(deterministic)으로 결정되므로, 비결정성이 구조적으로 발생하지 않는다. 동일한 트리 구조와 동일한 환경 조건에 대하여 실행 경로가 항상 동일하게 결정된다.

\forall t: \text{state}(t) = f(\mathcal{T}, \text{env}(t)) \quad \text{(결정론적)}

4.3 전이 조건 충돌의 원천적 제거

유한 상태 머신에서 새로운 전이 규칙을 추가할 때, 기존 전이 규칙과의 조건 충돌(condition conflict) 여부를 검증하여야 한다. 두 전이 규칙의 가드 조건이 동시에 참이 될 수 있는 경우, 비결정적 전이가 발생하며 시스템의 동작이 예측 불가능해진다.

행동 트리에서는 전이 규칙이 존재하지 않으므로, 전이 조건 간의 충돌이라는 문제 유형 자체가 발생하지 않는다. 제어 흐름의 우선순위는 자식 노드의 배치 순서에 의하여 자동으로 결정되며, 설계자가 별도의 우선순위 체계를 정의하거나 관리할 필요가 없다.

4.4 제어 흐름의 시각적 명료성

전이 규칙이 존재하지 않으므로, 행동 트리의 시각적 표현에서 상태 전이 다이어그램에서와 같은 간선 교차(edge crossing)가 발생하지 않는다. 제어 흐름은 트리의 구조 자체에 내재되어 있으며, 트리의 시각적 배치를 관찰하는 것만으로 제어 흐름의 전체 논리가 파악된다.

5. 제어 흐름 패턴의 예시

5.1 우선순위 기반 반응적 제어

ReactiveFallback
├── Sequence
│   ├── Condition: "IsEmergencyDetected"
│   └── Action: "EmergencyStop"
├── Sequence
│   ├── Condition: "IsBatteryLow"
│   └── Action: "ReturnToCharger"
└── SubTree: "PrimaryMission"

이 트리에서 제어 흐름은 다음과 같이 결정된다. 매 Tick마다 ReactiveFallback이 첫 번째 자식부터 순서대로 평가한다. “비상 감지” 조건이 참이면 비상 정지가 실행되고, 거짓이면 “배터리 부족” 조건이 평가된다. 배터리 부족이면 충전 복귀가 실행되고, 아니면 주요 임무가 실행된다.

이 제어 흐름의 전체 논리가 전이 규칙 없이 노드 유형과 배치 순서만으로 완전히 기술되어 있다. 유한 상태 머신에서 동일한 패턴을 구현하려면, 모든 상태에서 비상 감지와 배터리 부족 조건에 대한 전이 규칙을 개별적으로 정의하여야 한다.

5.2 순차적 임무 수행과 오류 복구

Sequence
├── Action: "ComputePath"
├── RetryNode num_attempts="3"
│   └── Action: "FollowPath"
└── Action: "ReportCompletion"

이 트리에서 경로 계획 후 경로 추종을 시도하되, 실패 시 최대 3회 재시도하며, 성공하면 완료를 보고한다. 재시도 로직이 Decorator 노드(RetryNode)에 의하여 표현되며, 별도의 전이 규칙(예: “경로 추종 실패 → 경로 추종 재시도” 전이)을 정의할 필요가 없다.

6. 전이 규칙 부재의 한계

행동 트리에서 전이 규칙이 없다는 특성은 대부분의 경우 장점이지만, 특정 상황에서 한계로 작용할 수 있다.

6.1 명시적 상태 전이가 필수적인 도메인

통신 프로토콜(예: TCP 상태 머신), 사용자 인터페이스 워크플로우 등 명시적 상태와 전이의 정의가 도메인 요구사항인 경우, 행동 트리의 전이 규칙 부재는 해당 도메인의 요구사항과 부합하지 않을 수 있다. 이런 경우 유한 상태 머신이 더 적합한 선택이 된다.

6.2 이력 의존적 행동

유한 상태 머신의 현재 상태는 과거 이벤트의 이력(history)을 암묵적으로 인코딩한다. 행동 트리에서는 이 이력 정보가 구조적으로 유지되지 않으므로, 이력 의존적 행동을 구현하려면 블랙보드에 상태 변수를 명시적으로 기록하고 관리하는 추가적 설계가 필요하다.

7. 참고 문헌

• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Colledanchise, M., & Ögren, P. (2017). “How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees.” IEEE Transactions on Robotics, 33(2), 372–389.
• Faconti, D. (2022). BehaviorTree.CPP 4.x Documentation. https://www.behaviortree.dev/
• Iovino, M., Scukins, E., Styrud, J., Ögren, P., & Smith, C. (2022). “A Survey of Behavior Trees in Robotics and AI.” Robotics and Autonomous Systems, 154, 104096.
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Pearson.

버전: 2026-03-31