1291.18 상태 머신의 동적 재구성 한계

1291.18 상태 머신의 동적 재구성 한계

1. 동적 재구성의 정의와 필요성

동적 재구성(dynamic reconfiguration)이란 시스템이 실행 중(runtime)에 자신의 구조나 동작 규칙을 변경하는 능력을 의미한다. 자율 로봇 시스템에서 동적 재구성이 요구되는 시나리오는 다음과 같다:

  1. 임무 변경: 운용 중 새로운 임무가 할당되거나 기존 임무의 우선순위가 변경될 때, 행동 제어 로직을 런타임에 갱신해야 한다.
  2. 환경 적응: 예측하지 못한 환경 조건(기상 변화, 지형 변화, 새로운 장애물 유형)에 대응하기 위하여 행동 전략을 런타임에 조정해야 한다.
  3. 하드웨어 관련 재구성: 센서나 액추에이터의 고장 시, 해당 장치에 의존하는 행동을 비활성화하고 대안 행동으로 전환해야 한다.
  4. 소프트웨어 업데이트: 시스템을 정지시키지 않고 행동 로직을 업데이트하는 무중단 갱신(hot update)이 필요한 경우가 있다.

2. FSM의 동적 재구성 제약

2.1 상태-전이 구조의 정적 특성

유한 상태 머신(FSM)은 본질적으로 정적(static) 구조로 설계된다. 상태 집합 Q, 입력 알파벳 \Sigma, 전이 함수 \delta는 설계 시점에서 고정되며, 이 구조가 런타임에 변경되는 것을 FSM의 형식적 정의는 고려하지 않는다.

런타임에 FSM의 구조를 변경하려면 다음 작업이 필요하다:

  1. 상태 추가/제거: 상태 집합 Q의 동적 수정
  2. 전이 규칙 변경: 전이 함수 \delta의 동적 갱신
  3. 현재 상태 보존: 구조 변경 중 시스템의 현재 활성 상태를 올바르게 유지하거나 안전한 상태로 전환

이러한 작업의 동적 수행은 다음과 같은 기술적 과제를 수반한다.

2.2 일관성 보장 문제

FSM의 구조를 런타임에 변경할 때, 변경 과정 중 시스템이 일관되지 않은 중간 상태(inconsistent intermediate state)에 놓이지 않도록 보장해야 한다. 예를 들어, 현재 활성 상태가 q_i인 상황에서 q_i를 제거하면, 시스템은 정의되지 않은 상태에 진입하게 된다. 유사하게, q_i에서의 퇴출 전이를 제거한 후 새로운 전이를 추가하는 과정에서, 제거와 추가 사이의 시간 동안 시스템이 이벤트를 수신하면 전이 규칙이 불완전한 상태에서 동작하게 된다.

이러한 일관성 문제를 해결하기 위해서는 원자적(atomic) 재구성 연산이 필요하며, 이를 위한 잠금(lock) 메커니즘이나 더블 버퍼링(double buffering) 기법의 구현이 필요하다.

2.3 활성 상태의 마이그레이션

FSM의 구조가 변경되면, 현재 활성 상태가 새로운 구조에서도 유효한지 검증해야 한다. 현재 상태가 새로운 구조에 존재하지 않거나 의미가 변경된 경우, 활성 상태를 새로운 구조의 적절한 상태로 마이그레이션(migration)하는 규칙이 정의되어야 한다. 이 마이그레이션 규칙은 도메인 특화적(domain-specific)이며, 일반적인 자동 마이그레이션 알고리즘의 설계가 어렵다.

2.4 전이 일관성의 동적 검증

새로운 전이가 런타임에 추가되면, 해당 전이가 기존 전이와 충돌하지 않는지, 비결정적(nondeterministic) 전이를 생성하지 않는지, 도달 불능 상태를 유발하지 않는지 등을 동적으로 검증해야 한다. 이러한 동적 검증의 계산 비용은 FSM의 규모에 비례하며, 실시간 시스템에서의 검증 제한 시간 내에 완료되어야 한다는 추가 제약이 존재한다.

3. 기존 접근의 한계

3.1 표 전환 방식

FSM의 전이 함수를 상태 테이블(state table)로 구현할 경우, 새로운 상태 테이블을 준비하고 활성 테이블을 원자적으로 교체하는 방식으로 동적 재구성이 가능하다. 그러나 이 방식은 전체 FSM을 한 번에 교체하는 것이므로, 부분적 변경(예: 하나의 전이만 수정)에 대해서도 전체 테이블의 복제가 필요하여 비효율적이다.

3.2 해석기 기반 방식

FSM의 정의를 XML이나 스크립트 형식으로 외부화하고, 런타임에 정의 파일을 재로드하는 해석기(interpreter) 기반 방식이 가능하다. 이 방식은 유연성을 제공하나, 정의 파일의 파싱과 검증에 소요되는 시간이 실시간 제약과 충돌할 수 있으며, 재로드 시점에서의 상태 마이그레이션 문제가 그대로 잔존한다.

4. 행동 트리의 동적 재구성 지원

행동 트리는 동적 재구성에 대하여 FSM보다 구조적으로 유리한 특성을 제공한다:

  1. 서브트리 교체: 행동 트리에서 특정 서브트리를 런타임에 다른 서브트리로 교체하는 것이 구조적으로 가능하다. 교체 대상 서브트리의 부모 노드만 수정하면 되며, 트리의 나머지 부분에 영향을 미치지 않는다.
  2. Tick 기반 자연스러운 전환: 행동 트리의 Tick 기반 실행 모델에서, 서브트리 교체는 현재 Tick이 완료된 후 다음 Tick에서 새로운 서브트리가 자동으로 실행되므로, 교체 시점의 일관성 문제가 자연스럽게 해소된다.
  3. BehaviorTree.CPP의 동적 전환 기능: BehaviorTree.CPP 라이브러리는 SwitchNode를 통한 런타임 트리 전환, XML 기반 트리 정의의 동적 로드 등 동적 재구성을 위한 명시적 메커니즘을 제공한다 (Faconti, 2018).
  4. 상태 없는 노드의 교체 안전성: 조건 노드와 대부분의 제어 노드는 내부 상태를 유지하지 않으므로, 교체 시 상태 마이그레이션이 불필요하다. Running 상태의 액션 노드가 교체될 경우에만 해당 노드의 중단(halt) 처리가 필요하다.

5. 참고 문헌

  • Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
  • Faconti, D. (2018). BehaviorTree.CPP: A C++ library for behavior trees. GitHub Repository.
  • Kramer, J., & Magee, J. (1990). “The Evolving Philosophers Problem: Dynamic Change Management.” IEEE Transactions on Software Engineering, 16(11), 1293–1306.

v0.1.0