1292.43 Parallel 노드의 성공 임계값 정책

1. 성공 임계값의 정의

Parallel 노드의 성공 임계값(success threshold) $M_S$ 는, Parallel 노드가 Success를 반환하기 위해 필요한 자식 노드의 최소 성공 횟수를 지정하는 매개변수이다. $N$ 개의 자식 중 $M_S$ 개 이상이 Success를 반환하면, Parallel 노드는 나머지 자식의 상태와 무관하게 즉시 Success를 반환한다. 이 매개변수는 Parallel 노드의 성공 판정 기준을 설계자가 유연하게 조정할 수 있도록 한다 (Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction, 2018).

2. 형식적 정의

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

$\text{status}(P) = Success \iff |\{c_i \mid \text{status}(c_i) = Success\}| \geq M_S$

여기서 $|\cdot|$ 는 집합의 원소 수(cardinality)를 나타낸다. 이 조건은 Success를 반환한 자식의 수가 임계값 이상이면 충족된다.

임계값의 유효 범위

성공 임계값 $M_S$ 는 $1 \leq M_S \leq N$ 의 범위에서 설정된다. 극단적인 값에서의 동작은 다음과 같다.

$M_S = 1$ 인 경우: 자식 중 하나라도 Success를 반환하면 Parallel 노드가 Success를 반환한다. 이는 Fallback 노드의 성공 조건과 의미론적으로 유사하다.

$M_S = N$ 인 경우: 모든 자식이 Success를 반환해야 Parallel 노드가 Success를 반환한다. 이는 Sequence 노드의 성공 조건과 의미론적으로 유사하되, 자식이 순차적이 아닌 동시적으로 실행된다는 차이가 있다.

$1 < M_S < N$ 인 경우: “N개 중 M개 이상 성공” (M-of-N) 정책을 구현한다. 이는 Sequence나 Fallback으로는 표현할 수 없는 고유한 의미론이다.

BehaviorTree.CPP에서의 기본값

BehaviorTree.CPP 라이브러리에서 Parallel 노드의 성공 임계값 기본값은 $M_S = N$ 이다. 즉, 기본 설정에서는 모든 자식이 성공해야 Parallel 노드가 성공한다. 이 기본값은 XML 트리 정의에서 success_count 속성을 통해 변경할 수 있다 (Faconti, BehaviorTree.CPP Documentation, 2024).

성공 임계값에 따른 동작 예제

자식 노드가 3개인 Parallel 노드에서 성공 임계값에 따른 동작 차이를 다음 표로 비교한다. 각 자식의 반환 상태가 $c_1 = S$ , $c_2 = F$ , $c_3 = S$ 인 경우를 가정한다( $n_S = 2$ , $n_F = 1$ ).

$M_S$	조건 충족 여부	P 반환 상태
1	$2 \geq 1$ (충족)	Success
2	$2 \geq 2$ (충족)	Success
3	$2 \geq 3$ (미충족)	실패 임계값에 따라 결정

$M_S = 3$ 인 경우 성공 조건이 충족되지 않으므로, Parallel 노드의 반환 상태는 실패 임계값 정책에 의해 결정된다.

임계값 도달 시의 처리

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

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

halt 요청은 진행 중인 불필요한 작업을 정리하는 역할을 한다. 예를 들어, 3개의 센서 데이터 수집 중 2개만 성공하면 충분한 경우( $M_S = 2$ ), 세 번째 센서의 데이터 수집이 아직 진행 중이더라도 이를 중단하고 후속 처리로 진행할 수 있다.

다중 Tick에 걸친 임계값 도달

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

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

Tick	A1	A2	A3	$n_S$	P1 반환
$t_1$	Running	Running	Running	0	Running
$t_2$	Success	Running	Running	1	Running
$t_3$	(기억)	Running	Success	2	Success

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

로봇 공학에서의 설계 지침

다수결 기반 센서 융합

$M_S$ 를 $\lceil N/2 \rceil + 1$ (과반수)로 설정하면, 다수결(majority voting) 기반의 성공 판정을 구현할 수 있다. 이 패턴은 복수의 센서가 동일한 조건을 독립적으로 검증하고, 과반수 이상의 센서가 성공을 보고할 때 전체 조건이 성립한다고 판정하는 경우에 활용된다 (Colledanchise & Ögren, 2018).

부분적 성공의 허용

모든 작업의 완료가 필수적이지 않은 경우, $M_S < N$ 으로 설정하여 일부 작업의 실패를 허용할 수 있다. 이 설계는 로봇 시스템의 내결함성(fault tolerance)을 높이는 데 기여한다. 예를 들어, 3개의 보조 센서 중 2개만 정상 작동하면 충분한 경우, $M_S = 2$ 로 설정하여 하나의 센서 고장을 허용한다.

성공 임계값과 실패 임계값의 상호 관계

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

$M_S + M_F \leq N + 1$

이 조건이 위반되면, 성공 조건과 실패 조건이 동시에 충족되지 못하는 교착 상태(deadlock)가 발생할 수 있다. 일반적으로 $M_S + M_F = N + 1$ 로 설정하면, 모든 자식이 완료된 시점에서 성공 또는 실패 중 하나가 반드시 확정된다.

참고 문헌

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/