1295.16 Parallel 노드의 조기 종료 메커니즘

1. 조기 종료의 정의

조기 종료(early termination)란, Parallel 노드가 모든 자식의 완료를 기다리지 않고, 성공 또는 실패 정책이 충족되는 즉시 최종 상태를 결정하고 나머지 RUNNING 상태의 자식을 중단하는 메커니즘이다. 이는 Parallel 노드의 효율적 실행과 적시적 반응을 보장하는 핵심 메커니즘이다(Colledanchise & Ögren, 2018).

2. 조기 종료가 발생하는 조건

2.1 성공 정책에 의한 조기 종료

성공 임계값 $M$ 에 도달하면, 아직 RUNNING 상태인 자식이 존재하더라도 Parallel 노드가 SUCCESS를 반환하고 종료한다. 이때 $N - S$ 개의 미완료 자식 중 RUNNING 상태인 자식에 halt()가 호출된다.

$S \geq M \;\land\; R > 0 \implies \text{조기 종료 (SUCCESS)}$

2.2 실패 정책에 의한 조기 종료

실패 임계값 $K$ 에 도달하면, 아직 RUNNING 상태인 자식이 존재하더라도 Parallel 노드가 FAILURE를 반환하고 종료한다.

$F \geq K \;\land\; R > 0 \implies \text{조기 종료 (FAILURE)}$

2.3 구조적 불가능성에 의한 조기 종료

성공 또는 실패 임계값에 도달하지 않았더라도, 남은 RUNNING 자식의 수로는 임계값에 도달하는 것이 구조적으로 불가능해지는 시점에서도 조기 종료가 발생한다.

$S + R < M \implies \text{조기 종료 (FAILURE, 성공 불가능)}$

$F + R < K \implies \text{조기 종료 (SUCCESS, 실패 불가능, 성공 조건 충족 시)}$

3. 정책별 조기 종료 시점

정책	조기 종료 조건	종료 시점 특성
SUCCESS_ONE ( $M = 1$ )	첫 SUCCESS 감지	매우 빠름
FAILURE_ONE ( $K = 1$ )	첫 FAILURE 감지	매우 빠름
SUCCESS_ALL ( $M = N$ )	첫 FAILURE 감지 (성공 불가능)	빠름 (첫 실패 시)
FAILURE_ALL ( $K = N$ )	첫 SUCCESS 감지 (실패 불가능, 성공 정책에 따라)	가변적
SUCCESS_COUNT( $M$ )	$M$ 번째 SUCCESS 또는 $(N-M+1)$ 번째 FAILURE	중간
FAILURE_COUNT( $K$ )	$K$ 번째 FAILURE 또는 $(N-K+1)$ 번째 SUCCESS	중간

4. 조기 종료의 절차

조기 종료가 결정되면 다음의 절차가 순서대로 실행된다.

4.1 단계 1: RUNNING 자식 식별

내부 상태 배열을 순회하여 아직 RUNNING 상태인 자식 노드를 식별한다.

4.2 단계 2: halt() 호출

식별된 RUNNING 자식 각각에 halt() 메서드를 호출한다. halt() 메서드는 다음의 작업을 수행한다.

자식 노드가 서브트리(subtree)인 경우, 서브트리 내의 모든 RUNNING 노드에 재귀적으로 halt()를 전파한다.
ROS2 액션 클라이언트와 연동된 경우, 진행 중인 목표에 대해 취소 요청(cancel_goal)을 전송한다.
노드의 내부 상태를 초기화하고, 상태를 IDLE로 재설정한다.
할당된 리소스를 해제한다.

4.3 단계 3: 내부 상태 초기화

Parallel 노드의 완료 플래그 배열, 캐싱된 상태 배열, 카운터 등의 내부 상태를 초기화하여, 다음 번 틱에서 깨끗한 상태로 실행을 재개할 수 있도록 한다.

4.4 단계 4: 최종 상태 반환

성공 정책이 충족된 경우 SUCCESS를, 실패 정책이 충족된 경우 FAILURE를 상위 노드에 반환한다.

5. 조기 종료의 의사 코드

Procedure: earlyTermination(final_status)
1   for i ← 1 to N do
2       if completed[i] = false then
3           children[i].haltNode()
4       end if
5   end for
6   resetCompletedFlags()
7   return final_status

6. 조기 종료의 효과

6.1 리소스 효율성

불필요한 행동의 즉시 중단으로 계산 리소스, 액추에이터 동력, 통신 대역폭 등의 낭비가 방지된다. 특히 SUCCESS_ONE 정책에서는 첫 번째 성공 이후 나머지 모든 자식이 즉시 중단되므로 효율성이 극대화된다.

6.2 반응 시간 단축

정책 충족 시점에서 즉시 최종 상태를 반환하므로, 상위 행동 트리의 다음 행동으로의 전환이 신속하게 이루어진다. 모든 자식의 완료를 기다리지 않으므로 전체 시스템의 반응 시간이 단축된다.

6.3 안전성 확보

FAILURE_ONE 정책에서 안전 위반이 감지되면 모든 병렬 행동이 즉시 중단되어, 위험한 상태에서의 지속적 행동 실행이 방지된다.

7. 조기 종료 시 주의 사항

7.1 halt() 구현의 정확성

halt() 메서드가 올바르게 구현되지 않으면, 리소스 누수, 상태 불일관, 또는 후속 실행에서의 비정상 동작이 발생할 수 있다. 특히 다음 사항에 주의해야 한다.

ROS2 액션 목표의 취소가 실제로 완료되었는지 확인해야 한다.
노드 내부의 타이머, 콜백, 구독(subscription) 등이 정상적으로 해제되어야 한다.
블랙보드에 기록된 중간 결과가 후속 처리에 영향을 미치지 않도록 관리해야 한다.

7.2 비동기 중단의 처리

ROS2 액션의 목표 취소는 비동기적으로 처리된다. cancel_goal 요청을 전송한 후 실제 취소 확인까지 시간이 소요될 수 있으며, 이 기간 동안 액션 서버가 계속 동작할 수 있다. 행동 노드의 halt() 구현에서 이러한 비동기성을 적절히 처리해야 한다.

7.3 부분 완료 결과의 처리

조기 종료 시점에서 일부 자식은 이미 성공하고, 일부는 중단되며, 일부는 실패한 상태이다. 이러한 부분 완료 결과가 후속 행동에 올바르게 전달되도록 블랙보드의 상태 관리가 필요하다.

8. 참고 문헌

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

Version: 1.0-2026.04.03