1291.54 서브트리를 통한 구조적 분해 (Structural Decomposition via Subtrees)

1. 구조적 분해의 개념과 복잡도 관리

구조적 분해(structural decomposition)란 복잡한 시스템을 관리 가능한 크기의 하위 구성 요소로 분할하고, 각 구성 요소를 독립적으로 다루면서 전체 시스템을 체계적으로 구축하는 설계 방법론이다. Dijkstra(1968)가 제안한 구조적 프로그래밍(structured programming) 이래, 분할 정복(divide and conquer) 원칙은 소프트웨어 공학의 근본적 복잡도 관리 전략으로 자리잡았다.

로봇 행동 제어 시스템에서 임무의 복잡도는 행동의 수, 상호작용의 수, 예외 조건의 수에 비례하여 증가한다. 대규모 자율 로봇의 행동 논리가 수십에서 수백 개의 개별 행동을 포함할 때, 이를 단일한 편평(flat) 구조로 표현하면 시스템의 이해, 수정, 검증이 극도로 어려워진다. 구조적 분해는 이 복잡도를 계층적으로 조직하여 각 수준에서의 인지 부담을 인간의 처리 용량 이내로 유지하는 수단을 제공한다.

행동 트리(Behavior Tree, BT)에서 구조적 분해의 핵심 메커니즘은 **서브트리(subtree)**이다. 서브트리란 행동 트리의 임의의 부분 트리를 독립적인 단위로 캡슐화한 것으로서, 상위 트리에서 단일 노드처럼 취급된다.

2. 서브트리의 형식적 정의

행동 트리 $\mathcal{T} = (V, E, r)$ 에서 $V$ 는 노드 집합, $E$ 는 간선 집합, $r$ 은 루트 노드이다. 노드 $v \in V$ 를 루트로 하는 서브트리 $\mathcal{T}_v = (V_v, E_v, v)$ 는 $v$ 와 $v$ 의 모든 후손 노드(descendant node), 그리고 그 사이의 간선으로 구성되는 부분 트리이다.

행동 트리에서 서브트리의 핵심 속성은 다음과 같다.

$\forall \mathcal{T}_v \subseteq \mathcal{T}: \text{output}(\mathcal{T}_v) \in \{Success, Failure, Running\}$

즉, 임의의 서브트리는 그 내부 구조와 무관하게 상위 트리에 대하여 3값 반환 상태 중 하나만을 반환한다. 이 속성에 의하여 서브트리는 상위 트리의 관점에서 단일 리프 노드와 동일한 인터페이스를 갖는다.

3. 분해 전략

3.1 기능 기반 분해

가장 일반적인 서브트리 분해 전략은 **기능 기반 분해(function-based decomposition)**이다. 로봇 시스템의 전체 행동을 기능적 영역(functional domain)별로 분할하고, 각 영역을 독립적인 서브트리로 캡슐화한다.

자율 이동 로봇의 행동 트리를 기능 기반으로 분해한 예시:

MainTree (루트)
├── SubTree: "SafetyMonitor"          [안전 감시]
├── SubTree: "EnergyManagement"       [에너지 관리]
├── SubTree: "NavigationStack"        [네비게이션]
└── SubTree: "MissionExecution"       [임무 수행]

이 분해에서 각 서브트리는 하나의 명확한 기능적 영역을 담당하며, 다른 서브트리의 내부 구현에 의존하지 않는다. 상위 트리(MainTree)의 구조만을 관찰하면, 로봇의 행동이 안전 감시, 에너지 관리, 네비게이션, 임무 수행의 네 가지 기능 영역으로 구성됨을 즉시 파악할 수 있다.

3.2 추상화 수준 기반 분해

복잡한 행동 패턴은 **추상화 수준(abstraction level)**에 따라 계층적으로 분해될 수 있다. 상위 수준의 서브트리는 “무엇을” 달성하는가를 기술하고, 하위 수준의 서브트리는 “어떻게” 달성하는가를 기술한다.

수준 0 (임무): SubTree "DeliverPackage"
    수준 1 (단계): Sequence
        ├── SubTree: "NavigateToPickup"
        ├── SubTree: "PickupPackage"
        ├── SubTree: "NavigateToDestination"
        └── SubTree: "DropoffPackage"
            수준 2 (행동): Sequence
                ├── Action: "ApproachDropoffStation"
                ├── Action: "AlignWithStation"
                ├── Action: "ReleaseGripper"
                └── Action: "ConfirmDropoff"

이 계층적 분해에서 각 수준은 이전 수준보다 구체적인 행동을 기술하며, 관찰자는 관심 있는 추상화 수준에서만 트리를 관찰하면 된다. 이는 소프트웨어 설계에서의 점진적 공개(progressive disclosure) 원칙과 동일하다.

3.3 예외 처리 분리

주요 행동 로직과 예외 처리 로직을 별도의 서브트리로 분리하는 전략도 효과적이다. 주요 행동 서브트리는 정상적인 임무 수행 로직만을 다루고, 예외 처리 서브트리는 오류 복구, 대안 행동, 재시도 등의 로직을 캡슐화한다.

ReactiveFallback
├── SubTree: "ErrorRecovery"       [예외 처리]
│   ├── Sequence
│   │   ├── Condition: "IsLocalizationLost"
│   │   └── Action: "ReInitializeLocalization"
│   └── Sequence
│       ├── Condition: "IsPathBlocked"
│       └── Action: "RequestAlternatePath"
└── SubTree: "NormalOperation"     [정상 행동]
    └── Sequence
        ├── Action: "ComputePath"
        ├── Action: "FollowPath"
        └── Action: "ReportCompletion"

이 분리에 의하여 정상 행동 로직과 예외 처리 로직이 서로의 가독성과 유지보수성을 저해하지 않는다.

4. BehaviorTree.CPP에서의 서브트리 구현

4.1 XML 정의에 의한 서브트리 참조

BehaviorTree.CPP에서 서브트리는 별도의 <BehaviorTree> 블록으로 정의되며, 상위 트리에서 <SubTree> 태그를 통하여 참조된다.

<!-- 서브트리 정의 -->
<BehaviorTree ID="NavigateToGoal">
    <Sequence>
        <Action ID="ComputePathToPose" goal="{target_pose}" path="{nav_path}"/>
        <Action ID="FollowPath" path="{nav_path}"/>
    </Sequence>
</BehaviorTree>

<!-- 상위 트리에서의 참조 -->
<BehaviorTree ID="MainTree">
    <ReactiveFallback>
        <SubTree ID="SafetyMonitor"/>
        <Sequence>
            <SubTree ID="NavigateToGoal" target_pose="{mission_goal}"/>
            <Action ID="ReportArrival"/>
        </Sequence>
    </ReactiveFallback>
</BehaviorTree>

서브트리 정의와 상위 트리 정의는 동일한 XML 파일에 포함될 수도 있고, 별도의 XML 파일로 분리될 수도 있다. 별도 파일로 분리하는 경우, BehaviorTreeFactory의 registerBehaviorTreeFromFile() 메서드를 통하여 서브트리를 등록한다.

4.2 포트 매핑에 의한 데이터 전달

서브트리와 상위 트리 간의 데이터 교환은 **포트 매핑(port remapping)**을 통하여 이루어진다. 서브트리는 내부적으로 사용하는 블랙보드 키를 선언하고, 상위 트리에서는 이 키를 자신의 블랙보드 키에 매핑한다.

<SubTree ID="NavigateToGoal" target_pose="{mission_goal}" nav_path="{computed_path}"/>

이 매핑에서 서브트리 내부의 target_pose 키는 상위 트리의 mission_goal 키에 연결되고, nav_path 키는 computed_path 키에 연결된다. 서브트리는 상위 트리의 블랙보드 키 명칭을 직접 참조하지 않으므로, 서브트리와 상위 트리 간의 데이터 의존성이 명시적으로 관리된다.

4.3 블랙보드 네임스페이스 격리

BehaviorTree.CPP 4.x에서는 각 서브트리가 독립적인 블랙보드 인스턴스를 가질 수 있다. 이 네임스페이스 격리(namespace isolation)에 의하여, 서로 다른 서브트리가 동일한 키 명칭을 사용하더라도 충돌이 발생하지 않는다.

예를 들어, NavigateToGoal 서브트리와 ReturnToCharger 서브트리가 모두 내부적으로 path라는 키를 사용하더라도, 각 서브트리의 블랙보드가 독립적이므로 하나의 서브트리에서 path에 기록한 값이 다른 서브트리의 path 값에 영향을 미치지 않는다.

5. 구조적 분해의 효과

5.1 인지 복잡도의 감소

서브트리에 의한 구조적 분해는 각 수준에서 관찰자가 처리하여야 할 정보의 양을 제한한다. 전체 행동 트리가 $N$ 개의 노드를 가질 때, 서브트리에 의한 분해 없이 전체 트리를 한 번에 이해하려면 $O(N)$ 개의 노드를 동시에 인지하여야 한다. 반면, $k$ 개의 서브트리로 분해하면, 상위 트리 수준에서는 $k$ 개의 노드만 관찰하면 되고, 특정 서브트리의 내부를 확인할 때는 해당 서브트리의 노드 수( $N/k$ 정도)만 관찰하면 된다.

$\text{단일 수준 인지 부담} = O(k) \quad \text{vs.} \quad \text{분해 없는 인지 부담} = O(N)$

Miller(1956)의 연구에 따르면 인간의 작업 기억은 $7 \pm 2$ 개의 정보 덩어리를 처리할 수 있으므로, 각 수준의 자식 노드 수를 이 범위 이내로 유지하면 효과적인 인지 복잡도 관리가 달성된다.

5.2 관심사 분리에 의한 유지보수성 향상

서브트리에 의한 분해는 관심사 분리(separation of concerns) 원칙을 자연스럽게 실현한다. 네비게이션 로직의 수정은 네비게이션 서브트리 내부에서만 이루어지며, 안전 감시 서브트리나 임무 수행 서브트리에는 영향을 미치지 않는다. 이 격리에 의하여 수정에 따른 회귀 오류의 범위가 해당 서브트리 내부로 한정되며, 회귀 테스트의 범위도 축소된다.

5.3 팀 병렬 개발의 지원

서브트리 단위의 독립적 개발이 가능하므로, 각 서브트리를 서로 다른 개발자 또는 팀에 할당하여 병렬적으로 개발할 수 있다. 서브트리 간의 인터페이스가 반환 상태와 포트 매핑으로 한정되므로, 인터페이스 명세가 합의되면 각 팀이 독립적으로 작업을 진행하고, 통합 시 인터페이스의 호환성만 검증하면 된다.

5.4 점진적 검증의 가능

서브트리 단위로 독립적인 단위 테스트와 통합 테스트를 수행할 수 있다. 개별 서브트리가 정상적으로 동작함을 먼저 검증한 후, 서브트리를 조합한 상위 수준에서의 통합 테스트를 수행하는 상향식 테스트(bottom-up testing) 전략이 자연스럽게 지원된다. 이 점진적 검증 방식에 의하여 결함의 원인 추적(fault localization)이 용이해진다.

6. 유한 상태 머신에서의 분해와의 비교

유한 상태 머신에서도 계층적 상태 머신(Hierarchical State Machine, HSM) 또는 Statecharts를 통한 계층적 분해가 가능하다. Harel(1987)이 제안한 Statecharts는 복합 상태(composite state) 내에 하위 상태 머신을 내장하는 개념을 도입하였다. 그러나 Statecharts에서의 분해에는 다음과 같은 구조적 한계가 존재한다.

비교 항목	Statecharts	행동 트리 서브트리
하위 구조의 인터페이스	하위 상태 머신의 진입/탈출 지점 정의 필요	3값 반환 상태만으로 충분
상위-하위 간 전이	상위 상태에서 하위 상태로의 전이 규칙 정의 필요	명시적 전이 불필요, tick 전파에 의한 자동 제어
동시 영역	직교 영역(orthogonal region) 간 동기화 복잡도	Parallel 노드에 의한 단순화된 병행 제어
데이터 격리	상태 간 공유 변수의 관리 복잡도	블랙보드 네임스페이스에 의한 격리

Statecharts에서 복합 상태를 독립적 모듈로 격리하려면, 해당 복합 상태로의 진입 전이와 탈출 전이, 그리고 내부 상태와 외부 상태 간의 데이터 공유를 모두 관리하여야 한다. 반면, 행동 트리의 서브트리는 반환 상태와 포트 매핑만으로 상위 트리와의 인터페이스가 완결되므로, 분해의 복잡도가 현저히 낮다.

7. 분해 설계 지침

7.1 적절한 분해 깊이의 유지

서브트리에 의한 분해가 과도하게 깊어지면, 관찰자는 전체 행동 논리를 파악하기 위하여 다수의 서브트리를 순차적으로 탐색하여야 한다. 일반적으로 분해의 깊이를 3~4단계 이내로 유지하는 것이 권장되며, 이를 초과하는 경우 분해 구조의 재설계를 고려하여야 한다.

7.2 동일 추상화 수준의 자식 노드 구성

하나의 제어 노드 아래에 배치되는 자식 노드는 가능한 한 동일한 추상화 수준에 속하여야 한다. 고수준의 서브트리(예: “NavigateToGoal”)와 저수준의 개별 Action(예: “SetLED”)이 동일한 제어 노드의 자식으로 배치되면, 관찰자는 추상화 수준의 불일치로 인하여 인지적 혼란을 경험한다.

7.3 분해 기준의 일관성

시스템 전체에서 서브트리 분해의 기준을 일관되게 적용하여야 한다. 기능 기반 분해, 추상화 수준 기반 분해, 예외 처리 분리 등의 전략 중 하나를 주요 분해 기준으로 채택하고, 이를 전체 행동 트리에 일관되게 적용하면 구조의 예측 가능성이 향상된다.

8. 참고 문헌

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/
Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
Dijkstra, E. W. (1968). “Go To Statement Considered Harmful.” Communications of the ACM, 11(3), 147–148.
Miller, G. A. (1956). “The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information.” Psychological Review, 63(2), 81–97.

버전: 2026-03-31