1292.31 Sequence 노드의 동작 원리

1. Sequence 노드의 정의

Sequence 노드는 행동 트리(Behavior Tree)의 제어 흐름 노드(control flow node) 중 가장 기본적인 유형으로, 자식 노드를 왼쪽에서 오른쪽 순서로 순차적으로 실행하며, 모든 자식이 성공(Success)을 반환할 때에만 자신도 성공을 반환하는 노드이다. Sequence 노드는 “모든 자식이 성공해야 한다“는 논리곱(logical AND) 의미론을 구현하며, 임의의 자식이 실패(Failure)를 반환하는 즉시 나머지 자식의 실행을 생략하고 실패를 반환한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

행동 트리 다이어그램에서 Sequence 노드는 일반적으로 우향 화살표 기호(\rightarrow)로 표기된다.

2. Sequence 노드의 알고리즘

Sequence 노드의 동작을 의사 코드로 표현하면 다음과 같다.

function Sequence.tick():
    for i = current_child_index to N:
        status = child[i].tick()
        if status == Running:
            current_child_index = i
            return Running
        if status == Failure:
            current_child_index = 0
            return Failure
    current_child_index = 0
    return Success

여기서 N은 자식 노드의 총 수이며, current_child_index는 현재 실행할 자식의 인덱스이다. 이 알고리즘의 핵심 논리는 다음과 같다.

1. 현재 자식 인덱스부터 순차적으로 각 자식에 tick을 전달한다.
2. 자식이 Running을 반환하면, 현재 인덱스를 기억하고 Running을 반환한다.
3. 자식이 Failure를 반환하면, 인덱스를 초기화하고 즉시 Failure를 반환한다.
4. 모든 자식이 Success를 반환하면, 인덱스를 초기화하고 Success를 반환한다.

3. Sequence 노드의 논리적 의미론

Sequence 노드는 프로그래밍 언어에서의 단락 평가(short-circuit evaluation)를 동반한 논리곱(AND) 연산과 구조적으로 동등하다. 자식 노드 c_1, c_2, \ldots, c_N의 반환 상태를 s_1, s_2, \ldots, s_N이라 하면, Sequence 노드의 반환 상태 S는 다음과 같이 정의된다.

S = \begin{cases} Failure & \text{if } \exists\, i \in \{1, \ldots, N\} : s_i = Failure \\ Running & \text{if } \exists\, i \in \{1, \ldots, N\} : s_i = Running \wedge \forall\, j < i : s_j = Success \\ Success & \text{if } \forall\, i \in \{1, \ldots, N\} : s_i = Success \end{cases}

이 정의에서 조건의 평가 순서가 중요하다. Failure가 먼저 발견되면 즉시 Failure를 반환하고, Running이 발견되면 Running을 반환하며, 모든 자식이 Success일 때에만 Success를 반환한다 (Colledanchise & Ögren, 2018).

상태 기억 메커니즘

일반 Sequence 노드(비반응형)는 이전 tick에서 Running을 반환한 자식의 인덱스를 내부적으로 기억한다. 후속 tick에서는 해당 인덱스의 자식부터 실행을 재개하며, 이전에 Success를 반환한 자식에는 tick을 재전달하지 않는다. 이 상태 기억(memory) 메커니즘은 이미 성공적으로 완료된 작업의 불필요한 재실행을 방지하여 실행 효율을 높인다.

BehaviorTree.CPP 라이브러리에서는 이 동작을 하는 노드를 SequenceWithMemory 또는 SequenceStar로 명명하며, 매 tick마다 첫 번째 자식부터 재실행하는 ReactiveSequence와 구분한다 (Faconti, BehaviorTree.CPP Documentation, 2024).

예를 들어, 자식 노드가 c_1, c_2, c_3이고, tick t_k에서 c_1이 Success, c_2가 Running을 반환하였다면, tick t_{k+1}에서 Sequence 노드는 c_2부터 실행을 재개한다. c_1에는 tick이 전달되지 않는다.

Sequence 노드의 실행 흐름 예제

다음의 행동 트리를 통해 Sequence 노드의 동작을 단계별로 추적한다.

Root
 └─ Sequence [S1]
     ├─ Condition [C1: 목표 지점 설정 확인]
     ├─ Action [A1: 경로 계산]
     └─ Action [A2: 경로 추종]

모든 자식이 Success를 반환하는 경우

S1의 최종 반환 상태: Success

첫 번째 자식이 Failure를 반환하는 경우

A1과 A2에는 tick이 전달되지 않으며, S1의 최종 반환 상태는 Failure이다.

두 번째 자식이 Running을 반환하는 경우

Tick t_k:

A2에는 tick이 전달되지 않으며, S1의 반환 상태는 Running이다.

Tick t_{k+1} (A1이 이번에 Success를 반환하는 경우):

C1에는 tick이 재전달되지 않는다. 이것이 상태 기억 메커니즘의 동작이다.

Sequence 노드와 논리곱의 대응

Sequence 노드의 동작은 명제 논리의 논리곱(\wedge)과 다음과 같이 대응된다.

이 대응 관계에 의해 Sequence 노드는 “A를 수행하고, 그리고 B를 수행하고, 그리고 C를 수행하라“는 순차적 실행 의미론을 자연스럽게 표현한다 (Colledanchise & Ögren, 2018).

로봇 공학에서의 활용 패턴

Sequence 노드는 로봇 공학에서 순서가 보장되어야 하는 일련의 작업을 모델링하는 데 광범위하게 활용된다. 대표적인 활용 패턴은 다음과 같다.

선행 조건 검증 후 행동 실행

Sequence
 ├─ Condition: 선행 조건 확인
 └─ Action: 행동 수행

조건 노드가 Failure를 반환하면 액션 노드는 실행되지 않으므로, 선행 조건이 충족된 경우에만 행동이 수행되는 가드(guard) 패턴을 구현한다.

다단계 임무 수행

Sequence
 ├─ Action: 목표 지점으로 이동
 ├─ Action: 물체 인식
 ├─ Action: 물체 파지
 └─ Action: 복귀

각 단계가 성공적으로 완료되어야 다음 단계로 진행하는 순차적 임무 수행 구조를 표현한다. 임의의 단계가 실패하면 전체 임무가 실패로 처리된다.

중첩된 Sequence 구조

Sequence 노드는 다른 제어 흐름 노드와 중첩되어 복합적인 행동 논리를 구성할 수 있다. Sequence 노드의 자식으로 또 다른 Sequence 노드나 Fallback 노드를 배치하면, 계층적인 순차 실행과 대안 탐색을 결합한 복잡한 행동 패턴을 설계할 수 있다.

참고 문헌

• 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/