396.54 임무 중단(Preemption)과 우선순위 재산정

1. 임무 중단의 개념

**임무 중단(preemption)**은 현재 실행 중인 과업 또는 임무를 상위 우선순위의 새로운 요청에 의해 일시적 또는 영구적으로 중지시키는 메커니즘이다. 자율 로봇 시스템에서 임무 중단은 환경의 급격한 변화, 비상 상황의 발생, 운영자의 개입 명령 등에 대한 신속한 대응을 가능하게 하는 핵심적 제어 기능이다. 임무 중단이 없는 시스템은 현재 과업이 완료될 때까지 새로운 요구에 반응할 수 없으므로, 동적 환경에서의 안전성과 적시성을 보장할 수 없다.

2. 임무 중단의 형식적 정의

2.1 중단 조건과 트리거

임무 중단은 중단 조건(preemption condition) \phi_p가 충족될 때 발생한다. 시간 t에서 현재 실행 중인 임무 M_{\text{current}}에 대한 중단 조건은 다음과 같이 정의된다:

\text{Preempt}(M_{\text{current}}, t) \iff \exists M_{\text{new}} : \phi_p(M_{\text{new}}, M_{\text{current}}, \mathcal{S}(t)) = \texttt{TRUE}

여기서 \mathcal{S}(t)는 시간 t에서의 시스템 상태이다. 중단 조건을 충족시키는 **중단 트리거(preemption trigger)**는 다음과 같이 분류된다:

2.2 중단의 유형

임무 중단은 중단된 임무의 이후 처리 방식에 따라 다음과 같이 분류된다:

\text{PreemptionType} \in \{\texttt{SUSPEND}, \texttt{ABORT}, \texttt{RESTART}\}

3. 우선순위 모델

3.1 정적 우선순위(Static Priority)

정적 우선순위(static priority) 모델에서, 각 임무 M_i에는 설계 시점에 고정된 우선순위 값 \pi(M_i) \in \mathbb{N}이 배정된다. 우선순위가 높은 임무가 도착하면 현재 임무를 중단한다:

\text{Preempt}(M_{\text{current}}) \iff \pi(M_{\text{new}}) > \pi(M_{\text{current}})

정적 우선순위의 장점은 구현의 단순성과 예측 가능성이다. 그러나 환경 변화에 따라 임무의 중요도가 변할 수 있는 동적 시나리오에서는 유연성이 부족하다.

3.2 동적 우선순위(Dynamic Priority)

동적 우선순위(dynamic priority) 모델에서, 임무의 우선순위는 시스템 상태, 환경 조건, 시간 등의 함수로 실시간 갱신된다:

\pi(M_i, t) = f\bigl(\text{urgency}(M_i, t), \text{importance}(M_i), \text{resource}(M_i, t), \text{deadline}(M_i, t)\bigr)

동적 우선순위를 결정하는 주요 요소는 다음과 같다:

3.3 Earliest Deadline First (EDF) 기반 우선순위

EDF(Earliest Deadline First) 알고리즘은 데드라인이 가장 임박한 임무에 최고 우선순위를 부여한다:

\pi_{\text{EDF}}(M_i, t) = \frac{1}{d_i - t}

여기서 d_i는 임무 M_i의 절대 데드라인이다. EDF는 단일 프로세서 환경에서 실행 가능한(schedulable) 과업 집합에 대해 최적의 스케줄링을 보장한다 (Liu and Layland, 1973).

4. 우선순위 재산정(Priority Reassessment)

4.1 재산정의 필요성

동적 환경에서 임무의 우선순위는 초기 배정 시점과 실행 중 시점에서 크게 달라질 수 있다. **우선순위 재산정(priority reassessment)**은 주기적으로 또는 특정 이벤트 발생 시 모든 활성 임무의 우선순위를 재계산하는 과정이다.

4.2 재산정 트리거

우선순위 재산정을 촉발하는 이벤트는 다음과 같다:

1. 새 임무 도착: 새로운 임무의 추가로 인한 전체 우선순위 체계의 재평가
2. 환경 상태 변화: 장애물 출현, 기상 변화 등 외부 조건의 변동
3. 자원 상태 변화: 배터리 잔량 감소, 통신 품질 저하 등
4. 임무 진행 상태 변화: 과업 완료, 실패, 지연 등
5. 주기적 재산정: 고정 주기 \Delta T마다 정기적으로 수행

4.3 재산정 절차

재산정 절차는 다음과 같이 형식화된다. 시간 t에서 활성 임무 집합 \mathcal{M}_{\text{active}}(t) = \{M_1, M_2, \ldots, M_k\}에 대해:

1단계: 각 임무의 현재 우선순위를 재계산한다:

\pi'(M_i) = f\bigl(\mathcal{S}(t), M_i\bigr), \quad \forall M_i \in \mathcal{M}_{\text{active}}(t)

2단계: 우선순위 순서를 갱신한다:

\text{Ranking}(t) = \text{sort}_{\pi'}\bigl(\mathcal{M}_{\text{active}}(t)\bigr)

3단계: 현재 실행 임무와 최고 우선순위 임무를 비교한다:

\text{if } \pi'(M_{\text{top}}) > \pi'(M_{\text{current}}) + \epsilon \implies \text{Preempt}(M_{\text{current}})

여기서 \epsilon은 불필요한 빈번한 전환을 방지하기 위한 **히스테리시스 임계값(hysteresis threshold)**이다.

4.4 히스테리시스(Hysteresis) 메커니즘

우선순위 값이 미세하게 변동할 때마다 임무를 전환하면, **전환 비용(switching cost)**이 과도하게 발생하고 시스템의 안정성이 저하된다. 히스테리시스 메커니즘은 우선순위 차이가 임계값 \epsilon을 초과할 때만 중단을 허용하여 이 문제를 해결한다:

\text{Preempt} \iff \pi'(M_{\text{new}}) - \pi'(M_{\text{current}}) > \epsilon

또한, 최근 중단으로부터의 경과 시간 \Delta t_{\text{last}}가 최소 보호 시간 T_{\text{guard}}를 초과해야만 다음 중단을 허용하는 시간 보호(time guard) 규칙을 추가할 수 있다:

\text{Preempt} \iff (\pi'(M_{\text{new}}) > \pi'(M_{\text{current}}) + \epsilon) \wedge (\Delta t_{\text{last}} > T_{\text{guard}})

5. 안전한 중단 프로토콜

5.1 안전 중단(Graceful Preemption)

로봇의 물리적 특성상, 임무 실행을 즉시 중단하면 안전하지 않은 상태가 발생할 수 있다. 예를 들어, 고속 이동 중인 로봇을 즉시 중단하면 관성에 의한 충돌 위험이 존재한다. **안전 중단(graceful preemption)**은 다음과 같은 절차를 따른다:

1. 중단 요청 수신: 중단 트리거 발생
2. 현재 행동의 안전 종료: 감속, 안전 자세 전환 등의 전이 행동 실행
3. 상태 저장(Checkpoint): 중단 시점의 임무 상태, 환경 인식 데이터, 진행 정보를 저장
4. 자원 해제 또는 유지: 중단 유형에 따라 자원 관리
5. 새 임무 시작: 상위 우선순위 임무의 실행 개시

5.2 체크포인트(Checkpoint) 기반 상태 보존

보류(\texttt{SUSPEND}) 유형의 중단에서, 중단된 임무의 상태를 보존하기 위한 체크포인트 \mathcal{CP}는 다음과 같이 정의된다:

\mathcal{CP}(M_i, t) = \bigl(\text{Phase}(M_i, t), \text{Progress}(M_i, t), \text{Context}(M_i, t)\bigr)

여기서:

• \text{Phase}: 현재 실행 중인 과업의 단계
• \text{Progress}: 과업의 완료 비율 또는 중간 결과
• \text{Context}: 환경 인식 상태, 블랙보드 데이터 등 실행 맥락

체크포인트를 통해, 상위 우선순위 임무 완료 후 중단된 임무를 보존된 상태로부터 재개할 수 있다.

6. 임무 제어 프레임워크별 중단 구현

6.1 행동 트리에서의 중단

행동 트리에서 중단은 구조적으로 내재화된다. 반응적 폴백(Reactive Fallback) 노드의 상위에 배치된 높은 우선순위 분기가 활성화되면, 하위 분기의 RUNNING 노드에 자동으로 halt() 신호가 전달된다. 이 메커니즘은 별도의 중단 프로토콜 설계 없이 트리 구조만으로 우선순위 기반 중단을 보장한다.

6.2 ROS2 액션 서버에서의 중단

ROS2 액션 인터페이스에서 중단은 cancel_goal 서비스를 통해 구현된다. 액션 서버는 취소 요청을 수신하면 \texttt{CANCELING} 상태로 전이하고, 현재 행동의 안전 종료 후 \texttt{CANCELED} 상태로 전이한다. 임무 관리자는 취소 완료를 확인한 후 새 목표를 전송한다.

6.3 유한 상태 머신에서의 중단

FSM에서 중단은 모든 상태에서 중단 이벤트에 대한 전이를 명시적으로 정의해야 구현된다. n개의 상태에 대해 중단 전이를 정의하면 n개의 전이 규칙이 필요하며, 이는 FSM의 확장성을 저해하는 요인이 된다.

7. 다중 수준 우선순위 체계

7.1 우선순위 수준(Priority Level)의 계층화

복잡한 임무 관리 시스템에서는 우선순위를 다수의 **수준(level)**으로 계층화한다:

동일 수준 내에서는 EDF, 라운드 로빈(Round Robin) 등의 세부 스케줄링 정책이 적용되며, 수준 간에는 상위 수준이 항상 우선하는 엄격 우선순위(strict priority) 규칙이 적용된다.

8. 중단 비용의 분석

임무 중단에는 다음과 같은 **비용(cost)**이 수반된다:

C_{\text{preempt}} = C_{\text{transition}} + C_{\text{context}} + C_{\text{progress\_loss}} + C_{\text{risk}}

우선순위 재산정 시 중단 비용을 함께 고려하면, 불필요한 중단을 방지하고 전체 시스템의 효율성을 향상시킬 수 있다:

\text{Preempt} \iff U(M_{\text{new}}) - U(M_{\text{current}}) > C_{\text{preempt}}

여기서 U(M)은 임무 M의 유용도(utility) 함수 값이다.

9. 참고 문헌

• Liu, C. L. and Layland, J. W. (1973). “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment.” Journal of the ACM, 20(1), 46–61.
• Sha, L., Rajkumar, R., and Lehoczky, J. P. (1990). “Priority Inheritance Protocols: An Approach to Real-Time Synchronization.” IEEE Transactions on Computers, 39(9), 1175–1185.
• Simmons, R. (1994). “Structured Control for Autonomous Robots.” IEEE Transactions on Robotics and Automation, 10(1), 34–43.
• Colledanchise, M. and Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Kortenkamp, D. and Simmons, R. (2008). “Robotic Systems Architectures and Programming.” Springer Handbook of Robotics, 187–206.

본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. v1.0