396.49 유한 상태 트랜스듀서(FST) 기반 임무 관리
1. 유한 상태 트랜스듀서의 개념
**유한 상태 트랜스듀서(Finite State Transducer, FST)**는 유한 상태 머신(FSM)을 일반화한 형식 모델로서, 입력 심볼에 대한 상태 전이뿐 아니라 출력 심볼의 생성까지 동시에 정의한다. FSM이 입력 문자열의 인식(acceptance)에 초점을 맞추는 반면, FST는 입력-출력 간의 매핑(mapping) 또는 **변환(transduction)**을 형식적으로 표현한다. 로봇 임무 관리에서 FST는 센서 입력이나 환경 이벤트를 받아들이고, 이에 대응하는 제어 명령이나 행동 출력을 생성하는 반응적 시스템을 모델링하는 데 적합하다.
2. 유한 상태 트랜스듀서의 형식적 정의
2.1 밀리 머신(Mealy Machine)
밀리 머신(Mealy Machine)은 출력이 현재 상태와 입력의 조합에 의해 결정되는 FST로, 6-튜플(6-tuple)로 정의된다:
\mathcal{T}_{\text{Mealy}} = (Q, \Sigma, \Gamma, \delta, \lambda, q_0)
여기서 각 요소는 다음과 같다:
| 기호 | 정의 |
|---|---|
| Q | 유한 상태 집합 |
| \Sigma | 유한 입력 알파벳 |
| \Gamma | 유한 출력 알파벳 |
| \delta: Q \times \Sigma \rightarrow Q | 상태 전이 함수 |
| \lambda: Q \times \Sigma \rightarrow \Gamma | 출력 함수 |
| q_0 \in Q | 초기 상태 |
밀리 머신에서 출력은 **전이(transition)**에 연관되며, 동일한 상태에서도 서로 다른 입력에 따라 다른 출력을 생성할 수 있다. 즉, 상태 q에서 입력 \sigma를 수신하면:
q' = \delta(q, \sigma), \quad \gamma = \lambda(q, \sigma)
의 관계에 의해 새로운 상태 q'와 출력 \gamma가 동시에 결정된다.
2.2 무어 머신(Moore Machine)
무어 머신(Moore Machine)은 출력이 현재 상태에만 의존하는 FST로, 6-튜플로 정의된다:
\mathcal{T}_{\text{Moore}} = (Q, \Sigma, \Gamma, \delta, \omega, q_0)
여기서 \omega: Q \rightarrow \Gamma는 상태 기반 출력 함수이다. 무어 머신에서는 각 상태 q에 출력 \omega(q)가 고정적으로 배정되며, 입력과 무관하게 해당 상태에 진입하면 동일한 출력이 생성된다.
2.3 밀리 머신과 무어 머신의 동치성
밀리 머신과 무어 머신은 형식적으로 **동치(equivalent)**이다. 임의의 밀리 머신을 등가의 무어 머신으로, 그리고 그 역방향으로 변환할 수 있다. 다만, 무어 머신에서 밀리 머신으로의 변환은 상태 수를 유지하지만, 밀리 머신에서 무어 머신으로의 변환은 상태 수가 최대 |Q| \times |\Gamma|까지 증가할 수 있다:
|Q_{\text{Moore}}| \leq |Q_{\text{Mealy}}| \times |\Gamma|
3. 로봇 임무 관리에서의 FST 모델링
3.1 입력-출력 매핑으로서의 임무 제어
로봇 임무 관리를 FST로 모델링할 때, 입력 알파벳 \Sigma는 센서 이벤트, 환경 변화, 운영자 명령 등 시스템에 대한 외부 자극을 나타내고, 출력 알파벳 \Gamma는 로봇이 생성하는 제어 명령, 행동 선택, 상태 보고 등의 반응을 나타낸다:
\Sigma = \{\sigma_{\text{obstacle}}, \sigma_{\text{target}}, \sigma_{\text{battery\_low}}, \sigma_{\text{comm\_lost}}, \sigma_{\text{operator\_cmd}}, \ldots\}
\Gamma = \{\gamma_{\text{navigate}}, \gamma_{\text{avoid}}, \gamma_{\text{approach}}, \gamma_{\text{return}}, \gamma_{\text{report}}, \gamma_{\text{idle}}, \ldots\}
이 매핑에서 FST의 핵심적 이점은, 동일한 이벤트에 대해 현재 임무 상태에 따라 다른 출력 행동을 결정적으로 생성할 수 있다는 점이다.
3.2 밀리 머신 기반 임무 관리 예시
다음은 자율 로봇의 순찰(patrol) 임무를 밀리 머신으로 모델링한 예시이다:
Q = \{q_{\text{patrol}}, q_{\text{investigate}}, q_{\text{return}}, q_{\text{charge}}\}
전이 및 출력 함수의 일부는 다음과 같다:
| 현재 상태 | 입력 (\sigma) | 다음 상태 (\delta) | 출력 (\lambda) |
|---|---|---|---|
| q_{\text{patrol}} | \sigma_{\text{target}} | q_{\text{investigate}} | \gamma_{\text{approach}} |
| q_{\text{patrol}} | \sigma_{\text{battery\_low}} | q_{\text{return}} | \gamma_{\text{return}} |
| q_{\text{investigate}} | \sigma_{\text{confirmed}} | q_{\text{patrol}} | \gamma_{\text{report}} |
| q_{\text{investigate}} | \sigma_{\text{battery\_low}} | q_{\text{return}} | \gamma_{\text{return}} |
| q_{\text{return}} | \sigma_{\text{at\_base}} | q_{\text{charge}} | \gamma_{\text{dock}} |
| q_{\text{charge}} | \sigma_{\text{charged}} | q_{\text{patrol}} | \gamma_{\text{navigate}} |
이 모델에서 각 전이는 입력 이벤트에 대한 행동 출력을 명시적으로 포함하며, FSM에서는 별도로 관리해야 하는 입출력 관계가 FST에서는 형식적 구조 내에 통합되어 있다.
4. FST 기반 임무 제어의 확장
4.1 가중 유한 상태 트랜스듀서(WFST)
**가중 유한 상태 트랜스듀서(Weighted Finite State Transducer, WFST)**는 각 전이에 **가중치(weight)**를 부여하여 확률적 또는 최적화 기반 임무 제어를 가능하게 한다. WFST는 7-튜플로 정의된다:
\mathcal{T}_W = (Q, \Sigma, \Gamma, \delta, \lambda, w, q_0)
여기서 w: Q \times \Sigma \rightarrow \mathbb{K}는 가중치 함수이며, \mathbb{K}는 반환(semiring) 구조를 갖는 가중치 집합이다. 대표적인 반환 구조는 다음과 같다:
| 반환(Semiring) | (\mathbb{K}, \oplus, \otimes, \bar{0}, \bar{1}) | 용도 |
|---|---|---|
| 확률 반환 | ([0, 1], +, \times, 0, 1) | 확률적 전이 모델링 |
| 열대 반환(Tropical) | (\mathbb{R}^+ \cup \{\infty\}, \min, +, \infty, 0) | 최단 경로/최소 비용 |
| 로그 반환(Log) | (\mathbb{R} \cup \{\infty\}, \oplus_{\log}, +, \infty, 0) | 수치 안정적 확률 계산 |
WFST를 이용하면, 로봇이 여러 가능한 행동 경로 중 비용 또는 확률 기준으로 최적의 임무 실행 경로를 선택할 수 있다. 주어진 입력 시퀀스 \mathbf{\sigma} = (\sigma_1, \sigma_2, \ldots, \sigma_T)에 대한 최적 출력 시퀀스 \mathbf{\gamma}^*는 다음과 같이 결정된다:
\mathbf{\gamma}^* = \arg\min_{\mathbf{\gamma}} \bigotimes_{t=1}^{T} w(q_{t-1}, \sigma_t)
여기서 \bigotimes는 반환 구조의 곱셈 연산이다.
4.2 비결정적 유한 상태 트랜스듀서(NFST)
**비결정적 FST(Nondeterministic FST, NFST)**는 동일한 상태와 입력에 대해 여러 가능한 전이와 출력을 허용한다:
\delta_N: Q \times \Sigma \rightarrow 2^{Q \times \Gamma}
NFST는 임무 관리에서 불확실한 환경 인식 결과에 대한 다중 반응 후보를 표현하는 데 유용하다. 실행 시에는 추가적인 결정 규칙(heuristic, 확률적 선택 등)을 통해 실제 출력을 결정한다.
5. FST의 합성(Composition) 연산
5.1 합성 연산의 정의
FST의 강력한 특성 중 하나는 합성(composition) 연산이다. 두 FST \mathcal{T}_1 = (Q_1, \Sigma, \Omega, \delta_1, \lambda_1, q_{01})과 \mathcal{T}_2 = (Q_2, \Omega, \Gamma, \delta_2, \lambda_2, q_{02})가 주어졌을 때, \mathcal{T}_1의 출력 알파벳 \Omega가 \mathcal{T}_2의 입력 알파벳과 일치하면, 합성 FST \mathcal{T}_c = \mathcal{T}_1 \circ \mathcal{T}_2를 구성할 수 있다:
\mathcal{T}_c = (Q_1 \times Q_2, \Sigma, \Gamma, \delta_c, \lambda_c, (q_{01}, q_{02}))
여기서:
\delta_c\bigl((q_1, q_2), \sigma\bigr) = \bigl(\delta_1(q_1, \sigma), \delta_2(q_2, \lambda_1(q_1, \sigma))\bigr)
\lambda_c\bigl((q_1, q_2), \sigma\bigr) = \lambda_2\bigl(q_2, \lambda_1(q_1, \sigma)\bigr)
5.2 임무 관리에서의 합성 활용
합성 연산은 임무 관리 시스템을 다층적으로 구성하는 데 활용된다. 예를 들어:
- \mathcal{T}_{\text{perception}}: 원시 센서 데이터를 의미적 이벤트로 변환하는 인식 트랜스듀서
- \mathcal{T}_{\text{decision}}: 의미적 이벤트를 추상적 행동 명령으로 변환하는 의사결정 트랜스듀서
- \mathcal{T}_{\text{execution}}: 추상적 행동 명령을 구체적 제어 신호로 변환하는 실행 트랜스듀서
이들의 합성은 전체 임무 파이프라인을 하나의 통합 FST로 표현한다:
\mathcal{T}_{\text{mission}} = \mathcal{T}_{\text{perception}} \circ \mathcal{T}_{\text{decision}} \circ \mathcal{T}_{\text{execution}}
이 합성적 구조는 각 계층의 독립적 설계와 검증을 가능하게 하면서도, 전체 시스템의 형식적 분석을 허용한다.
6. FST 기반 임무 관리의 형식 검증
6.1 속성 검증
FST의 형식적 특성은 임무 관리 시스템의 **형식 검증(formal verification)**을 가능하게 한다. 다음과 같은 속성들을 검증할 수 있다:
기능성(Functionality): FST가 기능적(functional)이면, 각 입력 시퀀스에 대해 유일한 출력 시퀀스가 존재한다:
\forall \mathbf{\sigma}, \; |\{\mathbf{\gamma} : (\mathbf{\sigma}, \mathbf{\gamma}) \in \mathcal{R}(\mathcal{T})\}| \leq 1
여기서 \mathcal{R}(\mathcal{T})는 FST \mathcal{T}가 정의하는 관계이다. 기능성은 임무 제어의 결정론적 행동을 보장한다.
전역성(Totality): 모든 가능한 입력 시퀀스에 대해 출력이 정의되면, FST는 전역적(total)이다:
\forall \mathbf{\sigma} \in \Sigma^*, \; \exists \mathbf{\gamma} \in \Gamma^* : (\mathbf{\sigma}, \mathbf{\gamma}) \in \mathcal{R}(\mathcal{T})
이는 임무 관리 시스템이 모든 가능한 이벤트 시퀀스에 대해 반응을 생성함을 보장한다.
6.2 최소화(Minimization)
FST의 최소화(minimization) 알고리즘을 적용하면, 동일한 입출력 관계를 유지하면서 상태 수가 최소인 등가 FST를 구할 수 있다. 이는 임무 관리 시스템의 실행 효율성을 향상시키고, 임베디드 시스템에서의 메모리 사용을 최적화한다.
7. FSM 대비 FST의 차별적 이점
FST는 표준 FSM에 비해 임무 관리에서 다음과 같은 차별적 이점을 제공한다:
| 비교 항목 | FSM | FST |
|---|---|---|
| 출력 정의 | 상태 내 암묵적 정의 | 전이/상태에 명시적 정의 |
| 입출력 관계 | 별도 관리 필요 | 형식 구조 내 통합 |
| 합성 연산 | 직접 지원 안 됨 | 체계적 합성 가능 |
| 다층 구조 | Ad-hoc 연결 | 합성을 통한 형식적 연결 |
| 형식 검증 | 상태 도달성 중심 | 입출력 관계 검증 가능 |
| 최적화 | 상태 최소화 | 상태 + 전이 최소화 |
8. 적용 사례와 한계
8.1 적용 사례
FST 기반 임무 관리는 다음과 같은 영역에서 활용된다:
- 프로토콜 기반 통신 제어: 로봇 간 통신 프로토콜을 FST로 모델링하여, 메시지 수신에 따른 응답 및 상태 전이를 형식적으로 관리한다.
- 다층 임무 파이프라인: 인식-결정-실행의 계층적 구조를 합성 가능한 FST 체인으로 구현한다.
- 임무 명세 변환: 고수준 임무 명세를 저수준 행동 명령으로 변환하는 트랜스듀서를 설계한다.
- 적응적 행동 선택: WFST를 활용하여 환경 불확실성에 따른 확률적 행동 선택을 구현한다.
8.2 한계
FST 기반 접근법은 다음과 같은 한계를 가진다:
- 상태 폭발 문제: FSM과 마찬가지로 상태 수가 증가할 때 관리 복잡도가 지수적으로 증가한다.
- 동적 환경 적응: 사전에 정의된 전이 규칙에 기반하므로, 예측하지 못한 환경 변화에 대한 적응이 제한적이다.
- 합성 복잡도: 다수의 FST를 합성할 경우 상태 공간이 곱(product)으로 증가하여 |Q_c| = \prod_i |Q_i|가 된다.
- 연속적 행동 표현: 이산적(discrete) 입출력에 특화된 구조로서, 연속적 제어 행동의 표현에는 추가적 추상화가 필요하다.
이러한 한계에도 불구하고, FST는 입출력 관계가 명확하고 형식 검증이 중요한 임무 관리 하위 시스템에서 여전히 유효한 설계 도구로 활용된다. 특히 합성 연산의 체계성은 다층 임무 아키텍처의 형식적 구성과 검증에 핵심적 역할을 한다.
9. 참고 문헌
- Mohri, M. (2009). “Weighted Automata Algorithms.” Handbook of Weighted Automata, Springer, 213–254.
- Hopcroft, J. E., Motwani, R., and Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. 3rd Edition, Pearson.
- Beal, J. and Bachrach, J. (2006). “Infrastructure for Engineered Emergence on Sensor/Actuator Networks.” IEEE Intelligent Systems, 21(2), 34–41.
- Cassandras, C. G. and Lafortune, S. (2008). Introduction to Discrete Event Systems. 2nd Edition, Springer.
- Raimondi, F. and Pecheur, C. (2008). “Model Checking of Mealy Machines for Control and Data Flow Analysis.” NASA/TM-2008-215280.
본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. v1.0