396.42 상태 머신(Finite State Machine) 기반 임무 관리

1. 개요

유한 상태 머신(Finite State Machine, FSM)은 자율 로봇 시스템의 임무 관리에서 가장 오랜 역사를 가진 실행 모델 중 하나이다. FSM은 시스템의 행동을 유한 개수의 상태(State)와 상태 간 전이(Transition)로 명시적으로 기술하며, 그 직관성과 형식적 분석 가능성으로 인해 다양한 로봇 응용 분야에서 널리 채택되어 왔다.

2. 유한 상태 머신의 수학적 정의

2.1 결정론적 유한 상태 머신(DFSM)

결정론적 유한 상태 머신은 5-튜플 $M = (Q, \Sigma, \delta, q_0, F)$ 로 정의된다.

$Q$ : 유한 상태의 집합
$\Sigma$ : 유한 입력 알파벳(이벤트의 집합)
$\delta : Q \times \Sigma \rightarrow Q$ : 상태 전이 함수
$q_0 \in Q$ : 초기 상태
$F \subseteq Q$ : 최종 상태(종료 상태)의 집합

임의의 시각 $t$ 에서 시스템이 상태 $q_t \in Q$ 에 있고 이벤트 $\sigma \in \Sigma$ 가 발생하면, 시스템은 상태 $q_{t+1} = \delta(q_t, \sigma)$ 로 전이한다.

2.2 밀리 머신(Mealy Machine)과 무어 머신(Moore Machine)

임무 관리 맥락에서 FSM은 출력을 동반하므로, 밀리 머신 또는 무어 머신으로 확장된다.

밀리 머신(Mealy Machine): 출력이 현재 상태와 입력 이벤트의 조합에 의해 결정된다.

$M_{\text{Mealy}} = (Q, \Sigma, \Omega, \delta, \lambda, q_0)$

$\lambda : Q \times \Sigma \rightarrow \Omega$

여기서 $\Omega$ 는 출력 알파벳, $\lambda$ 는 출력 함수이다.

무어 머신(Moore Machine): 출력이 현재 상태에만 의존한다.

$M_{\text{Moore}} = (Q, \Sigma, \Omega, \delta, \omega, q_0)$

$\omega : Q \rightarrow \Omega$

로봇 임무 관리에서 무어 머신은 각 상태에 진입할 때 특정 행동(Action)을 실행하는 모델로 해석되며, 밀리 머신은 상태 전이 시 행동이 실행되는 모델로 해석된다.

3. 임무 관리에서의 FSM 모델링

3.1 상태의 정의

임무 관리를 위한 FSM에서 각 상태는 로봇의 임무 수행 단계(Mission Phase)에 대응한다. 예를 들어, 순찰 임무의 FSM은 다음과 같이 정의될 수 있다.

$Q = \{\text{IDLE}, \text{NAVIGATING}, \text{INSPECTING}, \text{REPORTING}, \text{RETURNING}, \text{COMPLETED}, \text{ERROR}\}$

각 상태에 진입할 때 수행되는 행동은 다음과 같다.

상태	진입 행동	설명
IDLE	대기 모드 활성화	새 임무 수신 대기
NAVIGATING	경로 추종 시작	목표 지점으로 이동
INSPECTING	센서 데이터 수집	현장 점검 수행
REPORTING	보고서 전송	임무 결과 전달
RETURNING	귀환 경로 생성	기지 복귀
COMPLETED	임무 종료 처리	로그 기록 및 자원 해제
ERROR	오류 대응 절차	안전 모드 전환

3.2 이벤트와 전이

이벤트는 상태 전이를 유발하는 트리거(Trigger)이다. 이벤트의 유형은 다음과 같이 분류된다.

외부 이벤트(External Event): 센서 데이터, 운용자 명령, 통신 수신 등 시스템 외부에서 발생하는 자극이다.

내부 이벤트(Internal Event): 타이머 만료, 자원 임계 도달, 과업 완료 등 시스템 내부에서 생성되는 자극이다.

전이는 가드 조건(Guard Condition)을 동반할 수 있다.

$\delta(q, \sigma) = q' \quad \text{if } g(q, \sigma) = \text{true}$

여기서 $g$ 는 가드 조건 함수이다. 가드 조건은 동일한 상태에서 동일한 이벤트에 대해 서로 다른 전이 대상을 선택하는 데 사용된다.

3.3 행동의 유형

FSM 기반 임무 관리에서 행동은 다음의 세 가지 유형으로 구분된다.

진입 행동(Entry Action): 상태에 진입할 때 한 번 실행되는 행동이다.

$\text{onEntry}(q) : q \in Q$

상주 행동(During Action): 해당 상태에 머무는 동안 주기적으로 실행되는 행동이다.

$\text{onDuring}(q) : q \in Q$

이탈 행동(Exit Action): 상태를 이탈할 때 한 번 실행되는 행동이다.

$\text{onExit}(q) : q \in Q$

4. 순찰 임무 FSM의 설계 예시

순찰 임무를 FSM으로 모델링하면 다음과 같다.

        mission_received                goal_reached
IDLE ──────────────→ NAVIGATING ──────────────→ INSPECTING
 ↑                      │                          │
 │                      │ obstacle/error           │ inspection_done
 │            ┌─────────↓─────────┐               │
 │            │      ERROR        │               ↓
 │            └─────────┬─────────┘         REPORTING
 │                      │ recovered              │
 │                      ↓                        │ report_sent
 │               NAVIGATING                      ↓
 │                                          RETURNING
 │              mission_complete                 │
 └───────────────────────────────────────────────┘

전이 테이블은 다음과 같이 정의된다.

현재 상태	이벤트	가드 조건	다음 상태	행동
IDLE	mission_received	임무 유효성 검증 통과	NAVIGATING	경로 계획 요청
NAVIGATING	goal_reached	-	INSPECTING	센서 활성화
NAVIGATING	obstacle_detected	복구 불가	ERROR	안전 정지
INSPECTING	inspection_done	-	REPORTING	보고서 생성
REPORTING	report_sent	-	RETURNING	귀환 경로 생성
RETURNING	base_reached	-	IDLE	임무 종료
ERROR	recovered	-	NAVIGATING	경로 재계획

5. FSM 기반 임무 관리의 구현

5.1 이벤트 구동 실행 루프

FSM 기반 임무 관리의 핵심 실행 루프는 이벤트 구동(Event-Driven) 방식으로 동작한다.

$\text{while}(\text{active}) \{$
$\quad e \leftarrow \text{waitForEvent}()$
$\quad q' \leftarrow \delta(q, e)$
$\quad \text{if } q' \neq q :$
$\quad \quad \text{onExit}(q)$
$\quad \quad \text{onEntry}(q')$
$\quad \quad q \leftarrow q'$
$\quad \text{onDuring}(q)$
$\}$

5.2 상태 전이 테이블 기반 구현

전이 테이블(Transition Table)을 데이터 구조로 표현하여, 상태와 이벤트의 조합에 대한 전이 목표와 행동을 조회하는 방식으로 구현한다. 이 방식은 상태의 추가와 수정이 용이하며, 전이 규칙의 완전성(Completeness)과 결정성(Determinism)을 검증하기에 적합하다.

$\text{TransitionTable} = \{(q_i, \sigma_j) \mapsto (q_k, a_{ijk}) \mid q_i, q_k \in Q, \sigma_j \in \Sigma, a_{ijk} \in \mathcal{A}\}$

5.3 ROS1의 SMACH 프레임워크

ROS1 환경에서 FSM 기반 임무 관리는 SMACH(State Machine) 라이브러리를 통해 구현되었다(Bohren & Cousins, 2010). SMACH는 다음의 기능을 제공한다.

상태의 계층적 합성(Hierarchical Composition)
병행 상태(Concurrent State)의 정의
상태 내 서브머신(Sub-machine)의 중첩
인트로스펙션(Introspection)을 통한 상태 시각화

SMACH에서 각 상태는 execute() 메서드를 구현하며, 반환값으로 결과(Outcome)를 전달한다. 결과값은 상위 상태 머신의 전이 조건으로 사용된다.

5.4 FlexBE 프레임워크

FlexBE(Flexible Behavior Engine)(Schillinger et al., 2016)는 ROS 기반의 FSM 임무 관리 프레임워크로, 운용자의 실시간 개입을 지원하는 혼합 이니셔티브(Mixed-Initiative) 기능을 제공한다. FlexBE에서는 각 상태를 행동 블록(Behavior Block)으로 정의하고, 시각적 편집기를 통해 상태 머신을 설계한다.

6. FSM의 분석적 특성

6.1 도달 가능성 분석(Reachability Analysis)

FSM의 모든 상태가 초기 상태로부터 도달 가능한지 검증하는 것은 임무 관리 시스템의 안전성을 보장하는 데 필수적이다. 도달 가능 상태의 집합은 다음과 같이 정의된다.

$\text{Reachable}(q_0) = \{q \in Q \mid \exists \sigma_1, \ldots, \sigma_k \in \Sigma^* : \delta^*(\ldots\delta^*(\delta^*(q_0, \sigma_1), \sigma_2)\ldots, \sigma_k) = q\}$

만약 $\text{Reachable}(q_0) \neq Q$ 이면, 도달 불가능한 상태가 존재하며 이는 설계 오류를 의미한다.

6.2 교착 상태(Deadlock) 검출

특정 상태에서 어떤 이벤트도 전이를 유발하지 않는 경우, 시스템은 교착 상태에 빠진다. 교착 상태는 다음 조건으로 검출된다.

$\text{Deadlock}(q) \iff \forall \sigma \in \Sigma : \delta(q, \sigma) = \text{undefined} \wedge q \notin F$

교착 상태는 FSM 설계 시 반드시 제거되어야 하며, 모든 비종료 상태에 대해 최소한 하나의 유효한 전이가 정의되어 있어야 한다.

6.3 활동성 분석(Liveness Analysis)

FSM이 임무의 완료 상태에 최종적으로 도달할 수 있는지를 검증하는 것이 활동성 분석이다.

$\text{Live}(M) \iff \forall q \in \text{Reachable}(q_0) : \exists \sigma_1, \ldots, \sigma_m \in \Sigma^* : \delta^*(\ldots, q, \ldots) \in F$

7. 확장된 FSM 모델

7.1 가드 조건과 행동이 포함된 EFSM

확장된 유한 상태 머신(Extended Finite State Machine, EFSM)은 기본 FSM에 변수(Variable)와 가드 조건을 추가한 모델이다.

$M_{\text{EFSM}} = (Q, \Sigma, \Omega, V, \delta', q_0, F)$

여기서 $V$ 는 변수의 집합이고, $\delta' : Q \times \Sigma \times G(V) \rightarrow Q \times A(V)$ 는 가드 조건 $G(V)$ 와 변수 갱신 행동 $A(V)$ 를 포함하는 확장된 전이 함수이다.

EFSM은 임무 관리에서 카운터(방문 횟수), 타이머(경과 시간), 누적값(수집 데이터양) 등의 상태 변수를 관리하는 데 유용하다.

7.2 시간 제약이 포함된 타이머 FSM

임무 관리에서 시간 제약은 핵심적인 요소이다. 타이머 FSM은 각 상태에 체류 시간 제한을 부여한다.

$\delta_{\text{timeout}}(q, T_q) = q_{\text{timeout}} \quad \text{if } t_{\text{stay}}(q) \geq T_q$

여기서 $T_q$ 는 상태 $q$ 의 최대 체류 시간, $t_{\text{stay}}(q)$ 는 현재 체류 시간이다.

8. FSM 기반 임무 관리의 장점

직관성: 그래프 기반의 시각적 표현이 가능하여 설계와 검증이 용이하다.
형식적 검증 가능성: 도달 가능성, 교착 상태, 활동성 등의 형식적 분석이 가능하다.
결정론적 실행: 동일한 이벤트 시퀀스에 대해 항상 동일한 행동 시퀀스가 생성된다.
실시간 성능: 상태 전이 연산의 시간 복잡도가 $O(1)$ 이므로 실시간 보장이 용이하다.
광범위한 도구 지원: SMACH, FlexBE, YAKINDU Statechart Tools 등 다양한 개발 도구가 존재한다.

9. 요약

FSM은 자율 로봇 임무 관리의 기본적이면서도 강력한 실행 모델이다. 시스템의 행동을 유한 개수의 상태와 전이로 명시적으로 기술함으로써, 임무 흐름의 설계, 시각화, 형식적 검증이 체계적으로 이루어진다. EFSM과 타이머 FSM 등의 확장을 통해 변수, 가드 조건, 시간 제약이 통합될 수 있으며, SMACH와 FlexBE 등의 프레임워크는 ROS 기반 시스템에서 FSM의 실용적 구현을 지원한다.

10. 참고 문헌

Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
Bohren, J., & Cousins, S. (2010). “The SMACH High-Level Executive.” IEEE Robotics & Automation Magazine, 17(4), 18–20.
Schillinger, P., Kohlbrecher, S., & von Stryk, O. (2016). “Human-Robot Collaborative High-Level Control with Application to Rescue Robotics.” Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 2796–2801.
Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
Arkin, R. C. (1998). Behavior-Based Robotics. MIT Press.

v0.1