1292.20 반환 상태의 전이 규칙

1. 전이 규칙의 개요

행동 트리(Behavior Tree)에서 노드의 반환 상태는 고정된 값이 아니라 tick의 수신과 실행 결과에 따라 동적으로 변화한다. 반환 상태의 전이 규칙(transition rule)은 노드가 한 상태에서 다른 상태로 전이할 수 있는 허용된 경로와 조건을 정의하는 형식적 규칙이다. 이 규칙은 행동 트리의 결정론적 실행(deterministic execution)과 의미론적 일관성(semantic consistency)을 보장하는 기반이 된다.

BehaviorTree.CPP 라이브러리의 구현에서는 다섯 가지 상태(Idle, Running, Success, Failure, Skipped)를 정의하며, 이들 사이의 전이는 엄격한 규칙에 의해 제어된다 (Faconti, BehaviorTree.CPP Documentation, 2024).

2. 상태 전이 다이어그램

노드의 상태 전이는 다음과 같은 유한 상태 머신(Finite State Machine)으로 모델링된다. 각 전이에는 해당 전이를 유발하는 사건(event)이 연관된다.

                    ┌─────────────────────┐
                    │                     │
                    ▼                     │
              ┌──────────┐          tick(Running)
              │   Idle   │                │
              └──────────┘                │
               │    │    │                │
    tick(S)    │    │    │   tick(F)      │
               │    │    │                │
               ▼    │    ▼                │
         ┌─────┐   │   ┌─────┐     ┌─────────┐
         │ Suc │   │   │ Fai │     │ Running │
         └─────┘   │   └─────┘     └─────────┘
               │   │    │           │    │
               │   │    │      halt │    │
               │   │    │           │    │
               ▼   │    ▼           ▼    ▼
            (자동 Idle 복귀)    (Idle) (S/F)

3. 허용된 상태 전이

3.1 Idle에서의 전이

Idle 상태는 모든 노드의 시작 상태이자 종결 후 복귀 상태이다. Idle 상태에서 허용되는 전이는 다음과 같다.

현재 상태	전이 후 상태	전이 조건
Idle	Running	tick 수신 후 작업이 진행 중인 경우
Idle	Success	tick 수신 후 작업이 즉시 성공한 경우
Idle	Failure	tick 수신 후 작업이 즉시 실패한 경우
Idle	Skipped	사전 조건(precondition) 미충족으로 실행이 건너뛰어진 경우

Idle에서 tick을 수신하면 노드의 onStart 콜백이 호출되며, 이 콜백의 반환 값에 따라 Running, Success, Failure 중 하나로 전이한다. 사전 조건이 설정된 경우 onStart 호출 이전에 사전 조건이 평가되며, 미충족 시 Skipped로 전이한다 (Faconti, 2024).

3.2 Running에서의 전이

Running 상태는 노드가 현재 작업을 수행 중임을 나타낸다. Running 상태에서 허용되는 전이는 다음과 같다.

현재 상태	전이 후 상태	전이 조건
Running	Running	tick 수신 후 작업이 아직 진행 중인 경우
Running	Success	tick 수신 후 작업이 성공적으로 완료된 경우
Running	Failure	tick 수신 후 작업이 실패로 판정된 경우
Running	Idle	halt 요청을 수신한 경우

Running에서 tick을 수신하면 노드의 onRunning 콜백이 호출되며, 이 콜백의 반환 값에 따라 상태가 결정된다. Running에서 Running으로의 자기 전이(self-transition)는 작업이 여전히 진행 중임을 나타내며, 이는 장기 실행 비동기 작업에서 일반적으로 발생한다.

Running에서 Idle로의 전이는 halt 메커니즘에 의해서만 발생한다. 외부 중단 요청(부모 노드의 halt 전파)이 수신되면 노드의 onHalted 콜백이 호출되고, 자원 정리가 수행된 후 Idle 상태로 복귀한다.

3.3 Success에서의 전이

Success 상태에서 허용되는 전이는 단 하나이다.

현재 상태	전이 후 상태	전이 조건
Success	Idle	자동 복귀

노드가 Success를 반환하면 행동 트리의 실행 엔진에 의해 자동으로 Idle 상태로 재설정된다. 이 전이는 명시적인 사건에 의해 유발되는 것이 아니라, 종결 상태에 도달한 노드의 생명주기 관리 메커니즘에 의해 암묵적으로 수행된다. Success에서 Running이나 Failure로의 직접 전이는 허용되지 않는다.

3.4 Failure에서의 전이

Failure 상태에서 허용되는 전이 역시 단 하나이다.

현재 상태	전이 후 상태	전이 조건
Failure	Idle	자동 복귀

Success의 경우와 동일하게, Failure를 반환한 노드는 자동으로 Idle 상태로 재설정된다. 이 대칭적 처리는 종결 상태의 일관된 생명주기 관리를 보장한다.

3.5 Skipped에서의 전이

Skipped 상태에서 허용되는 전이도 단 하나이다.

현재 상태	전이 후 상태	전이 조건
Skipped	Idle	자동 복귀

Skipped 상태의 노드는 실행되지 않았으므로 내부 상태의 변경이 없으며, Idle로의 복귀는 즉시 수행된다.

4. 금지된 상태 전이

상태 전이 규칙은 허용된 전이뿐만 아니라 금지된 전이도 명시한다. 다음의 전이는 행동 트리의 의미론에 의해 금지된다.

4.1 Success/Failure에서 Running으로의 전이 금지

종결 상태(Success, Failure)에서 Running으로의 직접 전이는 금지된다. 노드가 이미 실행을 완료하였으므로, 완료된 실행을 “되돌려” 진행 중 상태로 변경하는 것은 의미론적으로 무결하지 않다. 종결 상태의 노드가 다시 실행되기 위해서는 반드시 Idle 상태를 경유하여야 한다. 이 규칙은 각 실행 주기의 독립성을 보장한다.

4.2 Idle에서 Idle로의 자기 전이

Idle 상태에서 Idle 상태로의 자기 전이는 의미론적으로 무의미하며, tick을 수신하지 않은 노드는 상태 변화 없이 Idle을 유지한다. 이는 전이가 아니라 상태의 유지(persistence)에 해당한다.

4.3 Skipped에서 Running으로의 전이 금지

Skipped 상태에서 Running으로의 직접 전이는 금지된다. Skipped된 노드는 실행되지 않았으므로 진행 중인 작업이 존재하지 않으며, Running으로의 전이는 논리적 모순이다.

5. 전이 규칙의 형식적 표현

노드 $N$ 의 시각 $t$ 에서의 상태를 $\sigma(N, t)$ 라 하면, 허용된 전이의 집합 $T$ 는 다음과 같이 정의된다.

$T = \{(Idle, Running), (Idle, Success), (Idle, Failure), (Idle, Skipped),$
$(Running, Running), (Running, Success), (Running, Failure), (Running, Idle),$
$(Success, Idle), (Failure, Idle), (Skipped, Idle)\}$

임의의 시각 $t$ 에서 $\sigma(N, t) = s_1$ 이고 시각 $t+1$ 에서 $\sigma(N, t+1) = s_2$ 이면, 반드시 $(s_1, s_2) \in T$ 이어야 한다. 이 불변 조건(invariant)의 위반은 행동 트리 실행 엔진의 오류를 나타낸다.

전이 규칙과 제어 흐름 노드의 관계

Sequence 노드의 전이 유발 규칙

Sequence 노드는 자식 노드의 반환 상태에 따라 자신의 상태 전이를 결정한다. $i$ 번째 자식 노드의 반환 상태를 $s_i$ 라 하면, Sequence 노드의 전이 규칙은 다음과 같다.

$s_i = Success$ : 다음 자식 $i+1$ 에게 tick을 전달한다. 모든 자식이 Success이면 자신도 Success를 반환한다.
$s_i = Failure$ : 즉시 Failure를 반환하고 후속 자식의 실행을 중단한다.
$s_i = Running$ : 즉시 Running을 반환하고 자식 인덱스 $i$ 를 기억한다.
$s_i = Skipped$ : 해당 자식을 무시하고 다음 자식 $i+1$ 에게 tick을 전달한다.

Fallback 노드의 전이 유발 규칙

Fallback 노드의 전이 규칙은 Sequence 노드와 대칭적이다.

$s_i = Failure$ : 다음 자식 $i+1$ 에게 tick을 전달한다. 모든 자식이 Failure이면 자신도 Failure를 반환한다.
$s_i = Success$ : 즉시 Success를 반환하고 후속 자식의 실행을 중단한다.
$s_i = Running$ : 즉시 Running을 반환하고 자식 인덱스 $i$ 를 기억한다.
$s_i = Skipped$ : 해당 자식을 무시하고 다음 자식 $i+1$ 에게 tick을 전달한다.

전이 규칙의 불변 조건

종결 상태는 반드시 Idle을 경유하여야 한다

노드가 종결 상태(Success, Failure, Skipped)에 도달한 후 다시 실행되기 위해서는 반드시 Idle 상태를 경유하여야 한다. 이 불변 조건은 다음과 같이 표현된다.

$\sigma(N, t) \in \{Success, Failure, Skipped\} \implies \sigma(N, t+1) = Idle$

이 규칙은 각 실행 주기가 항상 Idle에서 시작하여 종결 상태로 끝나는 깔끔한 생명주기를 보장하며, 이전 실행의 잔여 상태가 다음 실행에 영향을 미치지 않도록 방지한다.

5.1 Running에서 종결 상태로의 전이는 tick에 의해서만 발생한다

Running 상태의 노드가 Success 또는 Failure로 전이하는 것은 반드시 tick의 수신을 통해서만 발생하여야 한다. 외부의 임의적 상태 변경에 의한 전이는 금지된다. 이 규칙은 행동 트리 실행의 결정론성을 보장한다.

5.2 Halt에 의한 전이는 Running에서만 발생한다

Halt 메커니즘에 의한 Idle로의 강제 전이는 Running 상태의 노드에서만 발생할 수 있다. Idle, Success, Failure, Skipped 상태의 노드에 halt를 전달하는 것은 의미론적으로 무효하며, 실행 엔진은 이러한 호출을 무시하여야 한다 (Colledanchise & Ogren, Behavior Trees in Robotics and AI, 2018).

참고 문헌

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