1292.44 Parallel 노드의 실패 임계값 정책

1. 실패 임계값의 정의

Parallel 노드의 실패 임계값(failure threshold) $M_F$ 는, Parallel 노드가 Failure를 반환하기 위해 필요한 자식 노드의 최소 실패 횟수를 지정하는 매개변수이다. $N$ 개의 자식 중 $M_F$ 개 이상이 Failure를 반환하면, Parallel 노드는 나머지 자식의 상태와 무관하게 즉시 Failure를 반환한다. 실패 임계값은 성공 임계값과 함께 Parallel 노드의 종료 조건을 완전히 정의한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 형식적 정의

Parallel 노드 $P$ 가 자식 노드 $c_1, c_2, \ldots, c_N$ 을 가지고, 실패 임계값이 $M_F$ 로 설정되었을 때, $P$ 가 Failure를 반환하기 위한 조건은 다음과 같다.

$\text{status}(P) = Failure \iff |\{c_i \mid \text{status}(c_i) = Failure\}| \geq M_F$

여기서 $|\cdot|$ 는 집합의 원소 수를 나타낸다. 이 조건은 성공 임계값의 형식적 정의와 대칭적 구조를 가진다.

임계값의 유효 범위

실패 임계값 $M_F$ 는 $1 \leq M_F \leq N$ 의 범위에서 설정된다.

$M_F = 1$ 인 경우: 자식 중 하나라도 Failure를 반환하면 Parallel 노드가 즉시 Failure를 반환한다. 이는 가장 엄격한 실패 판정으로, 모든 자식의 성공이 요구되는 경우에 사용된다. BehaviorTree.CPP에서의 기본값이다 (Faconti, BehaviorTree.CPP Documentation, 2024).

$M_F = N$ 인 경우: 모든 자식이 Failure를 반환해야 Parallel 노드가 Failure를 반환한다. 이는 가장 관대한 실패 판정으로, 하나의 자식이라도 성공하면 실패를 회피할 수 있다.

$1 < M_F < N$ 인 경우: “ $N$ 개 중 $M_F$ 개 이상 실패” 정책을 구현한다.

실패 임계값에 따른 동작 예제

자식 노드가 4개인 Parallel 노드에서 $c_1 = S$ , $c_2 = F$ , $c_3 = F$ , $c_4 = R$ 인 경우( $n_S = 1$ , $n_F = 2$ , $n_R = 1$ )를 고려한다.

$M_F$	조건 충족 여부	P 반환 상태
1	$2 \geq 1$ (충족)	Failure
2	$2 \geq 2$ (충족)	Failure
3	$2 \geq 3$ (미충족)	성공 임계값 또는 Running
4	$2 \geq 4$ (미충족)	성공 임계값 또는 Running

$M_F = 3$ 이고 성공 임계값도 충족되지 않은 경우, A4가 아직 Running이므로 P는 Running을 반환한다.

임계값 도달 시의 처리

실패 임계값에 도달하면 Parallel 노드는 다음의 처리를 수행한다.

자신의 반환 상태를 Failure로 확정한다.
아직 Running 상태에 있는 모든 자식에 halt를 요청한다.
내부 상태를 초기화한다.

halt 요청은 실패가 확정된 후 더 이상 의미 없는 진행 중인 작업을 정리하는 역할을 한다 (Colledanchise & Ögren, 2018).

성공 임계값과 실패 임계값의 상호작용

우선순위 규칙

단일 tick에서 성공 임계값과 실패 임계값이 동시에 충족되는 경우, 구현에 따라 둘 중 하나가 우선된다. BehaviorTree.CPP에서는 일반적으로 실패 검사가 성공 검사보다 먼저 또는 동등하게 수행된다. 그러나 이 상황은 임계값 설정이 적절하면 발생하지 않는다.

일관성 제약 조건

성공 임계값 $M_S$ 와 실패 임계값 $M_F$ 는 다음의 제약 조건을 만족하여야 한다.

$M_S + M_F \leq N + 1$

이 조건이 만족되면, 임의의 시점에서 성공 조건과 실패 조건이 동시에 충족되는 모순이 발생하지 않는다. $M_S + M_F = N + 1$ 로 설정하면, 모든 자식이 완료된 시점에서 성공 또는 실패 중 정확히 하나가 확정되어 Running 상태가 무한히 지속되는 교착 상태가 방지된다.

예를 들어, $N = 3$ 인 경우:

$M_S = 2$ , $M_F = 2$ : $M_S + M_F = 4 = N + 1$ . 적절한 설정이다.
$M_S = 3$ , $M_F = 1$ : $M_S + M_F = 4 = N + 1$ . 적절한 설정이다.
$M_S = 1$ , $M_F = 1$ : $M_S + M_F = 2 < N + 1$ . 적절하나, 첫 번째 완료된 자식의 결과에 의해 즉시 종료된다 (Faconti, 2024).

3. 다중 Tick에 걸친 임계값 도달

실패 임계값의 도달은 다수의 tick에 걸쳐 점진적으로 이루어질 수 있다.

Parallel [P1, M_S=3, M_F=2]
 ├─ Action [A1]
 ├─ Action [A2]
 └─ Action [A3]

Tick	A1	A2	A3	$n_F$	P1 반환
$t_1$	Running	Running	Failure	1	Running
$t_2$	Failure	Running	(기억: F)	2	Failure

tick $t_1$ 에서 $n_F = 1 < M_F = 2$ 이므로 아직 임계값에 도달하지 않았다. tick $t_2$ 에서 A1이 Failure를 반환하여 $n_F = 2 \geq M_F = 2$ 가 되면, P1은 Failure를 반환하고 아직 Running 상태인 A2에 halt를 요청한다.

4. 로봇 공학에서의 설계 지침

4.1 내결함성 설계

$M_F$ 를 높게 설정하면, 개별 자식의 실패에 대한 내결함성(fault tolerance)이 증가한다. 예를 들어, 4개의 센서 중 1개의 고장을 허용하려면 $M_F = 2$ 로 설정한다. 이는 2개 이상의 센서가 실패해야만 전체 작업이 실패로 판정됨을 의미한다 (Colledanchise & Ögren, 2018).

4.2 조기 실패 감지

$M_F = 1$ 로 설정하면, 하나의 자식이라도 실패하는 즉시 전체 작업이 중단된다. 이 설정은 모든 병렬 작업의 성공이 필수적인 경우에 적합하며, 불필요한 작업의 지속을 조기에 차단하여 자원 낭비를 방지한다.

4.3 다수결 기반 실패 판정

$M_F = \lceil N/2 \rceil + 1$ 로 설정하면, 과반수 이상의 자식이 실패해야 전체가 실패로 판정되는 다수결 기반 실패 정책을 구현할 수 있다. 이 정책은 소수의 자식이 일시적으로 실패하더라도 전체 작업을 계속 진행할 수 있도록 하며, 로봇 시스템의 견고성(robustness)을 높인다.

참고 문헌

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/