1261.9 행동 제어에서의 상태 표현과 전이

1. 상태의 개념과 행동 제어에서의 역할

1.1 상태의 정의

행동 제어에서 상태(state)는 특정 시점에서 로봇 시스템의 행동 양식을 규정하는 이산적 또는 연속적 변수의 집합이다. 상태는 로봇이 현재 어떤 행동을 수행하고 있으며, 어떤 센서 조건에서 어떤 행동으로 전환할 수 있는지를 결정하는 핵심 추상화(abstraction) 단위이다.

제어 이론에서의 상태(예: 관절 각도, 각속도 등의 연속 변수)와 구별하여, 행동 제어에서의 상태는 주로 이산적 행동 모드(behavioral mode)를 지칭한다. 예를 들어, 이동 로봇의 행동 상태는 ‘대기(idle)’, ‘배회(wandering)’, ‘목표 추적(goal tracking)’, ‘장애물 회피(obstacle avoidance)’, ‘도킹(docking)’ 등의 이산적 범주로 정의될 수 있다. 각 상태는 해당 상태에서 활성화되는 행동 모듈의 집합과 해당 행동의 파라미터를 결정한다.

1.2 행동 제어에서 상태의 역할

상태는 행동 제어 시스템에서 다음의 핵심 역할을 수행한다.

첫째, 행동 선택의 기준이다. 현재 상태에 따라 활성화되는 행동 모듈과 비활성화되는 행동 모듈이 결정된다. 이는 행동의 맥락 의존적(context-dependent) 실행을 가능하게 한다.

둘째, 이력 정보의 보존이다. 무상태 반응적 행동이 현재 센서 입력만을 처리하는 데 반해, 상태를 유지하는 행동 제어는 과거의 이벤트나 행동 결과를 기억하여 이후 행동 결정에 반영할 수 있다.

셋째, 통신의 의미적 기반이다. 상태 정보는 행동 제어 시스템의 현재 작동 모드를 외부 모듈(상위 계획기, 모니터링 시스템, 사용자 인터페이스 등)에 전달하는 의미적 기반을 제공한다.

2. 상태 표현의 형식적 모델

2.1 유한 상태 기계 (Finite State Machine)

행동 제어에서 상태와 전이를 표현하는 가장 기본적이고 널리 사용되는 형식적 모델은 유한 상태 기계(Finite State Machine, FSM)이다. FSM은 다음의 5-튜플(5-tuple)로 정의된다.

M = (Q, \Sigma, \delta, q_0, F)

여기서 각 요소의 의미는 다음과 같다.

• Q: 유한 상태 집합. 예: Q = \{q_{\text{idle}}, q_{\text{navigate}}, q_{\text{avoid}}, q_{\text{dock}}\}
• \Sigma: 입력 기호(이벤트) 집합. 예: \Sigma = \{e_{\text{goal\_received}}, e_{\text{obstacle\_detected}}, e_{\text{goal\_reached}}, e_{\text{dock\_aligned}}\}
• \delta: 전이 함수 \delta: Q \times \Sigma \rightarrow Q. 현재 상태와 입력 이벤트의 조합으로부터 다음 상태를 결정한다.
• q_0: 초기 상태. 예: q_0 = q_{\text{idle}}
• F: 종료 상태 집합 (행동 제어에서는 선택적이며, 연속 작동 시스템에서는 명시되지 않을 수 있다)

행동 제어에서 FSM의 각 상태는 특정 행동 모듈의 활성화에 대응하며, 전이는 센서 이벤트, 행동 완료 신호, 외부 명령 등에 의해 촉발된다.

2.2 확장된 상태 기계 모델

2.2.1 무어 기계와 밀리 기계

FSM은 출력 생성 방식에 따라 무어 기계(Moore machine)와 밀리 기계(Mealy machine)로 구분된다.

무어 기계에서 출력은 현재 상태에만 의존한다. 행동 제어의 관점에서, 각 상태에 진입하면 해당 상태에 고정적으로 연결된 행동이 실행된다.

\lambda_{\text{Moore}}: Q \rightarrow \Gamma

여기서 \Gamma는 출력(행동 명령) 집합이다.

밀리 기계에서 출력은 현재 상태와 입력 이벤트의 조합에 의존한다. 동일 상태에서도 입력 이벤트에 따라 상이한 행동이 생성될 수 있다.

\lambda_{\text{Mealy}}: Q \times \Sigma \rightarrow \Gamma

로봇 행동 제어의 실무에서는 무어 기계와 밀리 기계의 혼합 형태가 빈번히 사용된다. 상태 진입 시 기본 행동이 개시되고(무어), 특정 이벤트 발생 시 전이와 함께 추가적 행동이 수행된다(밀리).

2.2.2 계층적 상태 기계 (Hierarchical State Machine)

Harel(1987)이 제안한 상태 차트(statechart)에 기초한 계층적 상태 기계(Hierarchical State Machine, HSM)는, 상태의 중첩(nesting)과 병렬 영역(parallel regions)을 허용하여 FSM의 표현력을 확장한 모델이다.

HSM에서 하나의 상태는 내부에 하위 상태 기계를 포함할 수 있다. 이를 합성 상태(composite state) 또는 슈퍼 상태(superstate)라 한다. 예를 들어, ‘항법(navigation)’ 상태가 내부에 ‘경로 계획(path planning)’, ‘경로 추종(path following)’, ‘경유점 도달(waypoint reached)’ 등의 하위 상태를 포함하는 구조가 가능하다.

HSM의 핵심 이점은 다음과 같다.

• 상태 폭증 문제의 완화: 단순 FSM에서 n개의 독립적 속성이 각각 m개의 값을 가질 때 최대 m^n개의 상태가 필요하나, HSM에서는 병렬 영역을 통해 이를 m \times n으로 축소할 수 있다.
• 추상화 수준의 관리: 상위 수준에서는 거시적 행동 전환만을 표현하고, 하위 수준에서 세부 실행 논리를 기술하는 계층적 추상화가 가능하다.
• 전이 규칙의 간소화: 슈퍼 상태로부터의 전이는 내부의 모든 하위 상태에 공통적으로 적용되므로, 전이 규칙의 중복 정의가 방지된다.

3. 상태 전이의 메커니즘

3.1 이벤트 구동 전이

행동 제어에서 상태 전이는 주로 이벤트(event)에 의해 촉발된다. 이벤트의 유형은 다음과 같이 분류된다.

이벤트 구동 전이는 다음의 형식으로 기술된다.

\delta(q_i, e_k) = q_j

이는 “상태 q_i에서 이벤트 e_k가 발생하면 상태 q_j로 전이한다“를 의미한다.

3.2 조건 기반 전이

이벤트 외에, 연속적으로 평가되는 불리언 조건(guard condition)에 의해 전이가 결정되는 경우가 있다. 조건 기반 전이는 다음과 같이 표현된다.

\delta(q_i) = q_j \quad \text{if } g(q_i, \mathbf{o}) = \text{true}

여기서 g는 현재 상태와 센서 관측 \mathbf{o}에 의존하는 보호 조건(guard)이다. 예를 들어, “배터리 잔량이 10% 미만이면 귀환 상태로 전이“와 같은 규칙이 조건 기반 전이에 해당한다.

3.3 전이 동작 (Transition Action)

상태 전이 시 부수적으로 실행되어야 하는 동작(action)이 존재할 수 있다. 이를 전이 동작(transition action)이라 하며, 진입 동작(entry action), 퇴출 동작(exit action), 전이 동작으로 세분된다.

• 진입 동작(entry action): 새 상태에 진입할 때 실행되는 동작. 예: 행동 모듈 초기화, 센서 구독 시작.
• 퇴출 동작(exit action): 현재 상태를 떠날 때 실행되는 동작. 예: 행동 모듈 종료, 자원 해제.
• 전이 동작(transition action): 특정 전이가 발생할 때 실행되는 일회성 동작. 예: 로그 기록, 상태 보고 메시지 전송.

4. 상태 표현의 실용적 사례

4.1 이동 로봇의 행동 상태 기계

이동 로봇의 전형적 행동 상태 기계를 구성하면 다음과 같다.

                    goal_received
        ┌──────────────────────────────┐
        │                              ▼
  ┌──────────┐                  ┌──────────────┐
  │   IDLE   │                  │  NAVIGATING  │◄──────────┐
  └──────────┘                  └──────────────┘           │
        ▲                         │         │              │
        │ mission_complete        │         │ obstacle     │ obstacle
        │                         │         │ _cleared     │ _cleared
  ┌──────────┐              goal  │   ┌───────────────┐    │
  │  DOCKING │◄─── dock ────reached  │   AVOIDING    │────┘
  └──────────┘                    │   └───────────────┘
                                  ▼         ▲
                             obstacle_detected

이 상태 기계에서 상태 집합은 Q = \{\text{IDLE}, \text{NAVIGATING}, \text{AVOIDING}, \text{DOCKING}\}이며, 전이는 센서 이벤트(obstacle_detected, obstacle_cleared), 행동 완료 이벤트(goal_reached, mission_complete), 외부 명령 이벤트(goal_received)에 의해 촉발된다.

4.2 비결정적 전이와 확률적 상태 기계

실세계 로봇 시스템에서 센서 잡음과 환경 불확실성으로 인해, 동일 상태에서 동일 이벤트가 발생하여도 상이한 결과가 나타날 수 있다. 이를 모델링하기 위해 확률적 유한 상태 기계(stochastic FSM)가 사용될 수 있다. 확률적 FSM에서 전이 함수는 다음 상태의 확률 분포를 반환한다.

\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)

여기서 \mathcal{P}(Q)는 상태 집합 Q 위의 확률 분포 공간이다.

5. 상태 표현의 설계 고려사항

5.1 상태 폭증 문제 (State Explosion)

행동 제어 시스템의 복잡도가 증가함에 따라 상태의 수가 급격히 증가하는 현상을 상태 폭증(state explosion)이라 한다. n개의 독립적 행동 속성이 각각 k개의 상태를 가질 때, 단순 FSM에서는 최대 k^n개의 합성 상태가 필요하다. 이 문제를 완화하기 위한 접근법으로는 전술한 계층적 상태 기계, 병렬 상태 영역, 그리고 행동 트리(behavior tree)와 같은 대안적 실행 구조가 활용된다.

5.2 완전성과 결정성

올바른 상태 기계 설계를 위해서는 두 가지 속성이 검증되어야 한다. **완전성(completeness)**은 모든 상태에서 발생 가능한 모든 이벤트에 대해 전이가 정의되어 있는 것을 의미한다. 미정의 전이는 로봇이 예상치 못한 이벤트에 대해 무반응 상태에 빠지는 원인이 된다. **결정성(determinism)**은 하나의 상태에서 하나의 이벤트에 대해 유일한 다음 상태가 결정되는 것을 의미한다. 비결정적 전이가 의도치 않게 존재하면 행동의 예측 불가능성이 초래된다.

5.3 도달 가능성과 사장 상태

상태 기계의 건전성(soundness)을 보장하기 위해, 초기 상태로부터 모든 상태에 도달 가능한지(reachability), 그리고 어떤 상태에서도 빠져나올 수 없는 사장 상태(dead state)가 존재하지 않는지를 검증하여야 한다. 모델 검증(model checking) 도구를 활용한 자동화된 검증이 안전 관련 로봇 시스템에서 활용된다.

참고 문헌

• Arkin, R. C. (1998). Behavior-Based Robotics. MIT Press.
• Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
• Siciliano, B., & Khatib, O. (Eds.). (2016). Springer Handbook of Robotics (2nd ed.). Springer.