1291.64 행동 트리의 깊이 증가에 따른 성능 문제

1291.64 행동 트리의 깊이 증가에 따른 성능 문제

행동 트리(Behavior Tree, BT)는 트리(Tree) 자료 구조를 기반으로 행동 제어 논리를 계층적으로 조직한다. 임무의 복잡도가 증가함에 따라 트리의 깊이(Depth)와 노드 수가 비례적으로 증가하며, 이는 틱(Tick) 기반 실행 모델에서의 계산 비용 증가와 실시간 성능 저하로 직결된다. 로봇 시스템과 같이 엄격한 실시간 제약(Real-Time Constraints)을 갖는 환경에서 이 문제는 시스템의 안전성과 반응성에 직접적인 영향을 미치는 핵심적 한계이다.

1. 틱 순회 비용과 트리 깊이의 관계

행동 트리의 실행 모델에서 매 틱 주기마다 루트 노드로부터 하향식 깊이 우선 순회(Depth-First Traversal)가 수행된다. 리액티브(Reactive) 제어 노드를 포함하는 트리에서는 매 틱마다 루트로부터 현재 실행 중인 노드까지의 경로에 위치한 모든 조건 노드가 재평가된다. 트리의 깊이가 d이고 각 수준에서의 평균 분기 계수(Branching Factor)가 b일 때, 최악의 경우 단일 틱에서 평가해야 하는 노드 수는 O(b^d)에 달할 수 있다.

비반응형 시퀀스(SequenceWithMemory)를 사용하는 경우에는 이미 성공한 자식 노드의 재평가를 회피하여 틱당 순회 비용을 줄일 수 있으나, 이 경우 환경 변화에 대한 반응성이 희생된다. 따라서 반응성과 계산 효율 사이의 상충(Trade-off)이 발생하며, 트리의 깊이가 증가할수록 이 상충은 더욱 심화된다.

2. 조건 노드 재평가의 누적 비용

리액티브 시퀀스(ReactiveSequence)나 리액티브 폴백(ReactiveFallback) 노드를 사용하는 행동 트리에서는 매 틱마다 실행 노드에 도달하기 전에 경로상의 모든 조건 노드가 재평가된다. 각 조건 노드가 센서 데이터 읽기, 블랙보드 변수 조회, 또는 외부 서비스 질의 등의 연산을 수행하는 경우, 개별 조건 노드의 평가 비용이 미미하더라도 트리의 깊이에 비례하여 누적 비용이 증가한다.

예를 들어, 자율 이동 로봇의 행동 트리에서 안전 조건 검사(배터리 상태, 장애물 근접도, 통신 상태), 임무 조건 검사(목표 유효성, 경로 유효성), 행동 전제 조건 검사(센서 가용성, 액추에이터 상태)가 계층적으로 배치된 경우, 최말단의 액션 노드에 틱이 도달하기 전에 수십 개의 조건 노드가 순차적으로 평가되어야 한다. 틱 주기가 수십 밀리초(ms) 이내로 설정되는 실시간 시스템에서 이러한 누적 평가 비용은 틱 주기 초과(Tick Overrun)를 유발할 수 있다.

3. 메모리 소비와 스택 깊이

트리의 깊이 증가는 메모리 소비에도 영향을 미친다. 재귀적 틱 순회 구현에서는 트리 깊이에 비례하여 호출 스택(Call Stack)이 성장하며, 임베디드 시스템이나 메모리 제약이 있는 로봇 플랫폼에서는 스택 오버플로(Stack Overflow)의 위험이 존재한다. BehaviorTree.CPP 라이브러리에서는 반복적(Iterative) 순회 방식을 채택하여 스택 깊이 문제를 완화하지만, 각 노드의 상태 정보와 블랙보드 데이터의 메모리 소비는 노드 수에 비례하여 증가한다.

또한, 서브트리(Subtree)를 통한 모듈화는 논리적으로는 트리를 분리하지만, 실행 시에는 단일 트리로 결합되어 순회되므로 물리적인 깊이 감소 효과는 제한적이다. 서브트리 참조가 중첩되는 경우 실효적 트리 깊이는 설계자의 직관보다 상당히 깊어질 수 있으며, 이는 성능 프로파일링을 통해서만 정확하게 파악할 수 있다.

4. 틱 주기와 실시간 제약의 상충

로봇 시스템에서 행동 트리의 틱 주기는 제어 루프의 주기와 밀접하게 연관된다. 이동 로봇의 경우 경로 추종 제어기가 10~50Hz의 주기로 동작하며, 동일한 주기 또는 그보다 빠른 주기로 행동 트리의 틱이 수행되어야 반응적 행동 제어가 가능하다. 트리 깊이 증가로 인해 단일 틱의 실행 시간이 허용 주기를 초과하면, 제어 루프의 지터(Jitter)가 증가하거나 틱이 누락되는 현상이 발생한다.

Nav2에서는 행동 트리의 틱 주기를 10~100Hz 범위에서 설정하며, 틱 실행 시간이 주기를 초과하는 경우 경고 로그를 출력한다. 이러한 현상은 행동 트리의 규모가 증가할수록 빈번해지며, 특히 다수의 리액티브 노드가 포함된 대규모 트리에서 두드러진다.

5. 성능 최적화 접근 방법

트리 깊이 증가에 따른 성능 문제에 대한 주요 최적화 전략은 다음과 같다.

첫째, 조건 노드의 캐싱(Caching) 기법이다. 매 틱마다 반복적으로 평가되는 조건 노드의 결과를 일정 시간 동안 캐싱하여 불필요한 재평가를 방지한다. 센서 데이터의 갱신 주기보다 틱 주기가 빠른 경우, 동일한 센서 값에 대한 중복 평가를 제거할 수 있다.

둘째, 선택적 틱(Selective Tick) 전략이다. 트리 전체를 매 틱마다 루트로부터 순회하는 대신, 이전 틱에서 Running 상태를 반환한 노드의 경로만을 선택적으로 재순회하여 순회 범위를 축소한다. 이 접근은 반응성을 일부 희생하지만 계산 비용을 현저히 줄인다.

셋째, **트리 구조의 평탄화(Flattening)**이다. 깊은 중첩을 유발하는 불필요한 중간 제어 노드를 제거하고, 트리의 깊이를 줄이면서 동일한 논리를 표현하도록 구조를 재설계한다.

넷째, **다중 트리 분리(Multi-Tree Decomposition)**이다. 단일 대규모 트리를 기능적으로 독립적인 다수의 소규모 트리로 분리하고, 각 트리를 서로 다른 틱 주기로 실행한다. 안전 관련 행동은 높은 주기로, 고수준 임무 계획은 낮은 주기로 실행함으로써 계산 자원을 효율적으로 분배할 수 있다.

참고 문헌

  • Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
  • Faconti, D., & Aurys, M. (2022). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/
  • Iovino, M., Scukins, E., Styrud, H., Ögren, P., & Smith, C. (2022). “A Survey of Behavior Trees in Robotics and AI.” Robotics and Autonomous Systems, 154, 104096.
  • Macenski, S., Martín, F., White, R., & Clavero, J. G. (2020). “The Marathon 2: A Navigation System.” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).