1292.98 구조적 일관성 검증

1. 구조적 일관성 검증의 정의

구조적 일관성 검증(structural consistency verification)이란, 행동 트리의 구조가 행동 트리의 형식 정의에서 규정하는 모든 구조적 제약 조건을 충족하는지를 검사하는 정적 분석 기법이다. 구조적 일관성이 확보된 행동 트리는 실행 시 구조적 원인에 의한 오류가 발생하지 않음이 보장된다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 구조적 제약 조건의 분류

행동 트리의 구조적 제약 조건은 다음과 같이 분류된다.

2.1 트리 구조 제약

제약 조건	설명	위반 시 결과
루트 노드의 유일성	트리에 정확히 하나의 루트 노드가 존재해야 한다	트리 실행 불가
비순환성	노드 간 순환 참조가 없어야 한다	무한 루프 발생
연결성	모든 노드가 루트로부터 도달 가능해야 한다	고립 노드 발생
단일 부모	각 노드는 최대 하나의 부모를 가져야 한다	DAG가 아닌 그래프 형성

2.2 노드 유형별 제약

노드 유형	자식 수 제약	위반 예시
루트 노드	정확히 1개	루트에 복수의 자식
제어 흐름 노드	1개 이상	자식 없는 Sequence
데코레이터 노드	정확히 1개	데코레이터에 복수의 자식
실행 노드 (리프)	0개	액션 노드에 자식 존재

2.3 포트 연결 제약

제약 조건	설명
필수 포트 연결	필수(mandatory) 입력 포트는 반드시 블랙보드 키 또는 기본값에 바인딩되어야 한다
타입 일치	입력 포트와 출력 포트가 동일한 블랙보드 키를 참조할 때 타입이 일치해야 한다
키 존재성	입력 포트가 참조하는 블랙보드 키가 트리 내 어딘가에서 설정되어야 한다

3. 구조적 일관성 검증 알고리즘

구조적 일관성 검증은 트리를 순회하면서 각 노드에 대해 제약 조건의 충족 여부를 검사하는 방식으로 수행된다.

function verify_structural_consistency(tree):
    errors = []

    // 1단계: 루트 노드 검증
    if count(tree.roots) != 1:
        errors.append("루트 노드는 정확히 하나여야 한다")

    if count(tree.root.children) != 1:
        errors.append("루트 노드는 정확히 하나의 자식을 가져야 한다")

    // 2단계: 순환 검출
    if has_cycle(tree):
        errors.append("트리에 순환 참조가 존재한다")

    // 3단계: 노드별 제약 검사
    for each node in tree.traverse():
        // 자식 수 제약 검사
        if node is Decorator and count(node.children) != 1:
            errors.append(node.name + ": 데코레이터는 정확히 1개의 자식 필요")

        if node is ControlFlow and count(node.children) == 0:
            errors.append(node.name + ": 제어 흐름 노드는 최소 1개의 자식 필요")

        if node is Leaf and count(node.children) > 0:
            errors.append(node.name + ": 리프 노드는 자식을 가질 수 없다")

        // 포트 제약 검사
        for each port in node.required_input_ports:
            if not port.is_bound():
                errors.append(node.name + ": 필수 입력 포트 미연결")

    // 4단계: 포트 타입 일관성 검사
    for each key in tree.blackboard.keys():
        writers = find_writers(tree, key)
        readers = find_readers(tree, key)
        if not types_consistent(writers, readers):
            errors.append(key + ": 포트 타입 불일치")

    return errors

4. 순환 검출

트리 구조에서 순환(cycle)이 존재하면 tick 전파가 무한 루프에 빠질 수 있다. 순환 검출은 깊이 우선 탐색(DFS)을 수행하면서 방문 상태를 추적하는 방식으로 구현된다.

function has_cycle(tree):
    visited = {}
    in_stack = {}

    function dfs(node):
        visited[node] = true
        in_stack[node] = true

        for each child in node.children:
            if not visited[child]:
                if dfs(child):
                    return true
            else if in_stack[child]:
                return true  // 순환 검출

        in_stack[node] = false
        return false

    return dfs(tree.root)

서브트리 참조에 의해 동일한 서브트리가 여러 위치에서 참조되는 경우, 인스턴스화(instantiation)가 올바르게 수행되었는지를 확인하여 순환 참조를 방지해야 한다 (Faconti, BehaviorTree.CPP Documentation, 2024).

5. BehaviorTree.CPP에서의 구조적 검증

BehaviorTree.CPP 라이브러리는 XML로부터 트리를 생성하는 과정에서 다음의 구조적 일관성 검증을 자동으로 수행한다.

검증 항목	검증 시점	오류 처리
노드 등록 여부	XML 파싱 시	미등록 노드 이름에 대해 예외 발생
자식 수 제약	트리 생성 시	데코레이터의 복수 자식에 대해 예외 발생
필수 포트 연결	트리 생성 시	미연결 필수 포트에 대해 예외 발생
포트 타입 일치	런타임 접근 시	타입 변환 실패 시 예외 발생

6. 구조적 일관성 검증의 완전성

구조적 일관성 검증은 트리의 형식적 제약 조건의 충족 여부를 판정하는 것이므로, 검증 규칙이 완전하게 정의되어 있다면 결정 가능(decidable)하다. 그러나 의미론적 일관성(예: 조건 노드의 논리적 모순, 블랙보드 값의 범위 제약)은 구조적 검증의 범위를 초과하며, 별도의 의미론적 분석이 필요하다.

7. 로봇 공학에서의 의의

구조적 일관성 검증은 행동 트리가 형식 정의에 부합하는 유효한 트리임을 배포 전에 보장하는 필수적 절차이다. 로봇 시스템에서 구조적으로 결함이 있는 행동 트리의 실행은 예측 불가능한 동작으로 이어질 수 있으므로, 구조적 일관성 검증은 로봇의 안전하고 신뢰할 수 있는 행동 제어를 위한 기본 요건이다 (Colledanchise & Ögren, 2018).

참고 문헌

Colledanchise, M. & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
Faconti, D. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/