1293.27 Sequence 노드에서의 Tick 전파

1. Sequence 노드의 정의

Sequence 노드는 행동 트리(Behavior Tree)에서 자식 노드들을 왼쪽에서 오른쪽으로 순차적으로 실행하며, 모든 자식이 SUCCESS를 반환해야 자신도 SUCCESS를 반환하는 제어 노드이다. Sequence 노드는 논리 AND 연산에 대응하며, “이 모든 것을 순서대로 수행하라“는 의미론을 가진다(Colledanchise & Ogren, 2018).

2. Tick 전파 알고리즘

Sequence 노드가 Tick을 수신하면, 다음 알고리즘에 따라 자식 노드에 Tick을 전파한다.

function Sequence.tick():
    for each child in children (왼쪽에서 오른쪽):
        child_status = child.tick()
        
        if child_status == RUNNING:
            return RUNNING
        
        if child_status == FAILURE:
            return FAILURE
    
    // 모든 자식이 SUCCESS를 반환한 경우
    return SUCCESS

이 알고리즘의 핵심 동작은 다음과 같다.

1. 첫 번째 자식부터 순서대로 Tick을 전파한다.
2. 자식이 SUCCESS를 반환하면 다음 자식으로 진행한다.
3. 자식이 FAILURE를 반환하면 나머지 자식을 Tick하지 않고 즉시 FAILURE를 반환한다(조기 종료).
4. 자식이 RUNNING을 반환하면 나머지 자식을 Tick하지 않고 RUNNING을 반환한다.
5. 모든 자식이 SUCCESS를 반환하면 SUCCESS를 반환한다.

3. 구체적 실행 흐름 예시

다음과 같은 Sequence 노드 구조를 가정한다.

Sequence
├── Condition_A (동기 조건)
├── Action_B (비동기 액션)
└── Action_C (동기 액션)

3.1 시나리오 1: 모든 자식이 SUCCESS

*WithMemory 모드에서 이미 SUCCESS인 자식은 재평가하지 않음

3.2 시나리오 2: 중간 자식이 FAILURE

Action_B가 FAILURE를 반환하면, Action_C는 Tick되지 않으며 Sequence 전체가 즉시 FAILURE를 반환한다.

3.3 시나리오 3: 첫 번째 자식이 FAILURE

Condition_A가 FAILURE를 반환하면, 후속 자식은 전혀 Tick되지 않는다.

4. Sequence의 메모리 모드 별 동작 차이

BehaviorTree.CPP에서 Sequence 노드는 메모리 속성에 따라 두 가지 변형을 가진다.

4.1 SequenceWithMemory (기본 Sequence)

이전 Tick에서 RUNNING을 반환한 자식의 인덱스를 기억하고, 다음 Tick에서 해당 인덱스부터 재개한다. 이전에 SUCCESS를 반환한 자식은 재평가하지 않는다.

// BehaviorTree.CPP에서의 Sequence 동작 (개념적)
NodeStatus SequenceNode::tick() {
    while (current_child_idx_ < children_.size()) {
        auto status = children_[current_child_idx_]->executeTick();
        
        if (status == NodeStatus::RUNNING) {
            return NodeStatus::RUNNING;
        }
        if (status == NodeStatus::FAILURE) {
            haltChildren();
            current_child_idx_ = 0;  // 리셋
            return NodeStatus::FAILURE;
        }
        // SUCCESS: 다음 자식으로 진행
        current_child_idx_++;
    }
    // 모든 자식 SUCCESS
    current_child_idx_ = 0;  // 리셋
    return NodeStatus::SUCCESS;
}

4.2 ReactiveSequence

매 Tick마다 첫 번째 자식부터 모든 자식을 재평가한다. 이전에 SUCCESS를 반환한 자식도 다시 Tick된다.

Tick k: ReactiveSequence → C0(SUCCESS) → C1(RUNNING)
Tick k+1: ReactiveSequence → C0(재평가, SUCCESS) → C1(재진입)

ReactiveSequence는 조건 노드와 액션 노드를 조합하여, 조건이 유지되는 동안만 액션을 수행하는 패턴에 적합하다.

5. Sequence에서의 Halt 전파

Sequence 노드가 FAILURE를 반환하거나 외부에서 Halt를 수신할 때, RUNNING 상태인 자식 노드에 대해 Halt를 호출한다.

5.1 자식 FAILURE에 의한 Halt

Sequence의 현재 자식이 FAILURE를 반환하면, 이전에 RUNNING 상태에 있던 자식(현재 자식 자체가 이전 Tick에서 RUNNING이었을 수 있음)에 대해 Halt가 호출된다.

5.2 외부 Halt에 의한 전파

Sequence 노드 자체가 부모 노드로부터 Halt를 수신하면, RUNNING 상태인 자식 노드에 Halt를 전파한다. 이는 Reactive 부모 노드에서 조건 변화가 감지되어 Sequence가 중단되는 경우에 발생한다.

6. Sequence 노드의 사용 패턴

6.1 순차적 작업 실행

가장 기본적인 사용 패턴으로, 복수의 작업을 정해진 순서로 수행한다.

<Sequence>
    <MoveToPickLocation/>
    <PickObject/>
    <MoveToPlaceLocation/>
    <PlaceObject/>
</Sequence>

각 작업이 성공해야 다음 작업으로 진행하며, 하나라도 실패하면 전체 시퀀스가 실패한다.

6.2 전제 조건 검증 후 실행

조건 노드를 Sequence의 앞부분에 배치하여, 조건이 충족된 경우에만 후속 액션을 실행하는 패턴이다.

<Sequence>
    <IsBatteryAbove threshold="20"/>
    <IsPathClear/>
    <NavigateToGoal goal="{target}"/>
</Sequence>

배터리 잔량과 경로 상태를 먼저 확인하고, 두 조건이 모두 만족되는 경우에만 네비게이션을 시작한다.

7. Sequence의 반환 상태 요약

참고 문헌

• Colledanchise, M., & Ogren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Faconti, D. (2022). BehaviorTree.CPP documentation and API reference. https://www.behaviortree.dev/