1292.96 도달 가능성 분석

1. 도달 가능성 분석의 정의

도달 가능성 분석(reachability analysis)이란, 행동 트리의 루트 노드로부터 각 노드까지의 실행 경로가 존재하는지를 검증하는 정적 분석 기법이다. 어떤 노드가 도달 가능(reachable)하다는 것은, 특정 조건의 조합 하에서 tick이 해당 노드까지 전파될 수 있는 실행 경로가 적어도 하나 존재함을 의미한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 도달 가능성의 형식적 정의

노드 $n$ 이 도달 가능하다는 것은 다음과 같이 형식적으로 정의된다. 루트 노드 $r$ 에서 노드 $n$ 까지의 경로 $r = n_0, n_1, \ldots, n_k = n$ 이 존재하고, 각 $n_{i+1}$ 이 $n_i$ 의 자식이며, $n_i$ 의 제어 흐름 의미론에 의해 $n_{i+1}$ 에 tick이 전달될 수 있는 조건이 존재하면, $n$ 은 도달 가능하다.

3. 제어 흐름 노드별 도달 가능성 조건

제어 흐름 노드의 조기 종료 규칙에 의해, 자식 노드의 도달 가능성은 해당 자식의 위치와 선행 자식의 반환 상태에 의존한다.

3.1 Sequence 노드에서의 도달 가능성

Sequence 노드의 $k$ 번째 자식 $c_k$ 가 도달 가능하려면, 선행하는 모든 자식 $c_1, c_2, \ldots, c_{k-1}$ 이 Success를 반환할 수 있는 경우가 존재해야 한다. 어떤 선행 자식이 항상 Failure를 반환한다면, 그 이후의 모든 자식은 도달 불가능하다.

선행 자식의 가능한 반환 상태	$c_k$ 의 도달 가능성
Success 가능	도달 가능
항상 Failure	도달 불가능
항상 Running	도달 불가능 (비반응형)

3.2 Fallback 노드에서의 도달 가능성

Fallback 노드의 $k$ 번째 자식 $c_k$ 가 도달 가능하려면, 선행하는 모든 자식 $c_1, c_2, \ldots, c_{k-1}$ 이 Failure를 반환할 수 있는 경우가 존재해야 한다. 어떤 선행 자식이 항상 Success를 반환한다면, 그 이후의 모든 자식은 도달 불가능하다.

3.3 Parallel 노드에서의 도달 가능성

Parallel 노드는 모든 자식을 동시에 tick하므로, 모든 자식이 항상 도달 가능하다. Parallel 노드의 도달 가능성 분석에서 조기 종료에 의한 도달 불가능 문제는 발생하지 않는다.

4. 도달 가능성 분석 알고리즘

도달 가능성 분석은 루트 노드에서 시작하여 트리를 전위 순회하면서, 각 노드의 도달 가능성을 재귀적으로 판정하는 방식으로 수행된다.

function reachability_analysis(node, reachable):
    node.reachable = reachable

    if node is leaf:
        return

    if node is Sequence:
        all_predecessors_can_succeed = true
        for each child in node.children:
            child_reachable = reachable and all_predecessors_can_succeed
            reachability_analysis(child, child_reachable)
            if child.always_fails():
                all_predecessors_can_succeed = false

    if node is Fallback:
        all_predecessors_can_fail = true
        for each child in node.children:
            child_reachable = reachable and all_predecessors_can_fail
            reachability_analysis(child, child_reachable)
            if child.always_succeeds():
                all_predecessors_can_fail = false

    if node is Parallel:
        for each child in node.children:
            reachability_analysis(child, reachable)

5. 도달 불가능 노드의 발생 원인

발생 원인	예시	설명
항상 실패하는 선행 조건	Sequence 내 항상 false인 조건 노드	이후 자식에 tick이 도달하지 않음
항상 성공하는 선행 대안	Fallback 내 항상 true인 조건 노드	이후 대안이 평가되지 않음
구조적 차단	ForceFailure 데코레이터가 Sequence의 선행 자식	후속 자식이 항상 차단됨
논리적 모순	상호 배타적 조건의 잘못된 배치	특정 경로가 논리적으로 불가능

6. 도달 가능성 분석의 한계

정적 도달 가능성 분석은 노드의 반환 상태를 구조적으로 추론할 수 있는 경우에만 정확하다. 액션 노드나 외부 센서에 의존하는 조건 노드의 반환 상태는 런타임에만 결정되므로, 정적 분석만으로는 이러한 노드의 도달 가능성을 완전히 판정할 수 없다. 정적 분석에서는 이러한 노드의 반환 상태를 비결정적(nondeterministic)으로 가정하여, 가능한 모든 반환 상태를 고려한 보수적 분석을 수행한다 (Faconti, BehaviorTree.CPP Documentation, 2024).

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/