1292.99 행동 트리의 실행 의미론 (Execution Semantics)

1. 실행 의미론의 정의

행동 트리의 실행 의미론(execution semantics)이란, 행동 트리의 각 노드가 tick을 수신했을 때 어떤 계산을 수행하고, 어떤 상태를 반환하며, 자식 노드에 대한 tick 전파가 어떤 규칙에 따라 이루어지는지를 형식적으로 정의한 규칙 체계이다. 실행 의미론은 행동 트리의 동작을 모호함 없이 규정하는 형식적 기반이며, 트리의 설계, 검증, 구현의 정확성을 보장하는 근거이다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 실행 의미론의 구성 요소

행동 트리의 실행 의미론은 다음의 구성 요소로 이루어진다.

구성 요소	설명
상태 공간	노드가 반환할 수 있는 상태의 집합 {Success, Failure, Running}
Tick 함수	각 노드 유형에 대해 정의된 실행 함수
전파 규칙	부모 노드가 자식 노드에 tick을 전달하는 규칙
조기 종료 규칙	자식의 반환 상태에 따라 순회를 중단하는 규칙
상태 전이 규칙	노드의 내부 상태가 전이되는 규칙
Halt 규칙	노드의 실행이 외부에 의해 중단될 때의 규칙

3. 노드 유형별 실행 의미론

3.1 제어 흐름 노드의 실행 의미론

제어 흐름 노드의 실행 의미론은 자식 노드에 대한 tick 전파 순서와 조기 종료 조건으로 정의된다.

Sequence 노드의 실행 의미론:

function Sequence.tick():
    for i = 1 to N:
        status_i = child_i.tick()
        if status_i == Failure:
            return Failure
        if status_i == Running:
            return Running
    return Success

Sequence 노드는 자식을 왼쪽에서 오른쪽 순서로 tick하며, Failure 또는 Running을 반환하는 자식을 만나면 즉시 해당 상태를 반환한다. 모든 자식이 Success를 반환하면 Success를 반환한다.

Fallback 노드의 실행 의미론:

function Fallback.tick():
    for i = 1 to N:
        status_i = child_i.tick()
        if status_i == Success:
            return Success
        if status_i == Running:
            return Running
    return Failure

Fallback 노드는 자식을 왼쪽에서 오른쪽 순서로 tick하며, Success 또는 Running을 반환하는 자식을 만나면 즉시 해당 상태를 반환한다. 모든 자식이 Failure를 반환하면 Failure를 반환한다 (Colledanchise & Ögren, 2018).

3.2 실행 노드의 실행 의미론

액션 노드의 실행 의미론:

액션 노드는 tick을 수신하면 자신의 행동을 수행하고, 행동의 완료 여부에 따라 Success, Failure, 또는 Running을 반환한다. 액션 노드는 자식이 없으므로 tick 전파가 발생하지 않는다.

조건 노드의 실행 의미론:

조건 노드는 tick을 수신하면 조건을 즉시 평가하고, Success 또는 Failure를 반환한다. 조건 노드는 Running을 반환하지 않으며, 부작용을 발생시키지 않는다.

3.3 데코레이터 노드의 실행 의미론

데코레이터 노드는 단일 자식에 tick을 전달하고, 자식의 반환 상태를 변환하여 부모에게 반환한다. 변환 규칙은 데코레이터의 유형에 따라 정의된다.

데코레이터	변환 규칙
Inverter	Success ↔ Failure, Running → Running
ForceSuccess	모든 상태 → Success
ForceFailure	모든 상태 → Failure
Repeat(N)	Success 시 반복, N회 완료 후 Success
Retry(N)	Failure 시 재시도, N회 실패 후 Failure

4. 실행 의미론의 형식화

Colledanchise와 Ögren(2018)은 행동 트리의 실행 의미론을 형식적으로 다음과 같이 정의하였다.

행동 트리 $T$ 는 튜플 $T = (f_T, r_T, \Delta_T)$ 로 정의된다. 여기서 $f_T$ 는 트리의 실행 함수, $r_T \in \{S, F, R\}$ 는 반환 상태, $\Delta_T$ 는 내부 상태의 변화이다. 트리의 실행은 tick 함수 $f_T$ 의 호출에 의해 개시되며, $f_T$ 는 트리의 구조와 각 노드의 의미론에 따라 재귀적으로 평가된다.

5. 실행 의미론의 분류

행동 트리의 실행 의미론은 tick의 처리 방식에 따라 다음과 같이 분류된다.

실행 의미론	특성	적용
동기적 실행 의미론	단일 tick 내에서 모든 평가 완료	단순 조건, 즉각 응답
비동기적 실행 의미론	Running 상태로 다중 tick에 걸쳐 실행	장기 실행 액션
이벤트 주도 실행 의미론	이벤트 발생 시에만 tick 수행	반응형 시스템

각 실행 의미론은 행동 트리의 적용 영역과 실행 환경의 특성에 따라 선택된다 (Faconti, BehaviorTree.CPP Documentation, 2024).

6. 실행 의미론과 결정론

행동 트리의 실행 의미론은 결정론적(deterministic)이다. 동일한 트리 구조와 동일한 환경 상태에서 tick이 수행되면, 항상 동일한 노드가 동일한 순서로 평가되고 동일한 결과가 반환된다. 이 결정론적 특성은 실행 의미론의 규칙이 모호함 없이 정의되어 있기 때문에 보장된다.

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/