1292.35 Sequence 노드의 Running 처리

1. Running 상태의 의미

Sequence 노드가 Running을 반환한다는 것은, 현재 실행 중인 자식 노드가 아직 작업을 완료하지 못하였으며 추가적인 tick이 필요함을 부모 노드에 보고하는 것이다. Running 상태는 행동 트리의 비동기적 실행(asynchronous execution)을 가능하게 하는 핵심 메커니즘으로, 단일 tick 내에 완료되지 않는 장시간 작업을 다수의 tick에 걸쳐 수행할 수 있도록 한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. Running 반환의 조건

Sequence 노드가 Running을 반환하기 위한 조건은 다음과 같다: 자식 노드 c_i가 Running을 반환하고, c_i 이전의 모든 자식 c_1, \ldots, c_{i-1}이 Success를 반환한 경우이다.

\text{status}(S) = Running \iff \exists\, i : \text{status}(c_i) = Running \wedge \forall\, j < i : \text{status}(c_j) = Success

이 조건에서 자식 c_i가 Running을 반환하면, Sequence 노드는 후속 자식 c_{i+1}, \ldots, c_N에 tick을 전달하지 않고 즉시 Running을 반환한다. 후속 자식은 Idle 상태를 유지한다.

상태 기억형 Sequence의 Running 처리

인덱스 기억 메커니즘

상태 기억형 Sequence 노드(SequenceWithMemory)는 Running을 반환한 자식의 인덱스를 내부 변수에 저장한다. 이 인덱스를 i_{running}이라 하면, 후속 tick에서 Sequence 노드는 c_1이 아닌 c_{i_{running}}부터 실행을 재개한다.

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

이 메커니즘에 의해, 이전 tick에서 이미 Success를 반환한 자식은 재실행되지 않으며, Running을 반환한 자식부터 실행이 재개된다 (Faconti, BehaviorTree.CPP Documentation, 2024).

다중 Tick에 걸친 실행 예제

다음의 Sequence 노드를 고려한다.

Sequence [S1]
 ├─ Action [A1: 목표 지점으로 이동]
 ├─ Action [A2: 물체 파지]
 └─ Action [A3: 복귀]

이 예제에서 A1이 tick t_1과 t_2에서 Running을 반환하는 동안, S1은 A1의 인덱스(0)를 기억한다. tick t_3에서 A1이 Success를 반환하면, 동일한 tick 내에서 A2에 tick이 전달된다. A2가 Running을 반환하면, 인덱스가 1로 갱신된다.

반응형 Sequence의 Running 처리

재평가 메커니즘

ReactiveSequence 노드는 Running 상태에서도 매 tick마다 첫 번째 자식부터 재평가한다. 이전에 Success를 반환한 자식이라도 환경 변화에 의해 Failure를 반환할 수 있으며, 이 경우 Running 상태의 자식에 halt가 요청된다.

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

여기서 halt_children_after(i)는 인덱스 i 이후의 자식 중 Running 상태에 있는 노드에 halt를 요청하는 함수이다.

재평가에 의한 Running 자식의 전환

ReactiveSequence에서 Running 자식이 전환되는 상황을 다음 예제로 설명한다.

ReactiveSequence [RS1]
 ├─ Condition [C1: 안전 조건 확인]
 ├─ Action [A1: 이동]
 └─ Action [A2: 보고]

Tick t_k: C1(Success) \rightarrow A1(Running) \rightarrow RS1(Running)

A1이 Running 상태이며, RS1도 Running을 반환한다.

Tick t_{k+1}: C1(Success) \rightarrow A1(Success) \rightarrow A2(Running) \rightarrow RS1(Running)

A1이 완료되어 Success를 반환하고, 동일 tick에서 A2에 tick이 전달된다. A2가 Running을 반환하므로 RS1도 Running을 반환한다. Running 자식이 A1에서 A2로 전환되었다.

Running 상태의 상향 전파

자식 노드의 Running 상태는 Sequence 노드를 통해 부모 노드로 상향 전파된다. Sequence 노드가 다른 제어 흐름 노드의 자식인 경우, Running 상태의 전파는 재귀적으로 이루어진다.

Root
 └─ Fallback [F1]
     ├─ Sequence [S1]
     │   ├─ Condition [C1]
     │   └─ Action [A1]   ← Running 반환
     └─ Action [A2]

A1이 Running을 반환하면, S1도 Running을 반환하고, F1도 Running을 반환한다. Running 상태가 리프 노드(A1)에서 루트 노드까지 전파되며, 이는 전체 행동 트리가 아직 실행 중임을 실행 엔진에 보고한다.

Running 처리와 실행 효율

Sequence 노드의 Running 처리에서 상태 기억형과 반응형의 선택은 실행 효율과 반응성 사이의 설계 균형(design trade-off)에 해당한다.

상태 기억형은 이미 성공한 자식을 재실행하지 않으므로 tick당 계산 비용이 낮지만, 환경 변화를 감지하지 못할 수 있다. 반응형은 매 tick마다 조건을 재평가하므로 환경 변화에 즉각적으로 대응하지만, tick당 계산 비용이 높다 (Colledanchise & Ögren, 2018).

Running 상태의 지속과 종결

Running 상태는 해당 자식이 최종적으로 Success 또는 Failure를 반환할 때 종결된다. Success를 반환하면 Sequence는 다음 자식으로 진행하고, Failure를 반환하면 Sequence 전체가 Failure를 반환한다. 자식이 무한히 Running을 반환하는 경우, Sequence 노드도 무한히 Running 상태를 유지하게 되므로, Timeout 데코레이터와 같은 시간 제약 메커니즘을 통해 이를 방지하는 설계가 필요하다.

참고 문헌

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