396.53 복합 임무의 동시 제어(Concurrent Executive) 패러다임
1. 동시 제어의 개념과 동기
자율 로봇 시스템이 현실 세계에서 임무를 수행할 때, 다수의 행동과 과업이 동시에(concurrently) 실행되어야 하는 경우가 빈번하다. 내비게이션 중 장애물을 감시하고, 센서 데이터를 처리하며, 통신을 유지하는 행위는 순차적으로 수행될 수 없으며, 반드시 병렬적 실행을 요구한다. **동시 제어 패러다임(Concurrent Executive Paradigm)**은 이러한 복합 임무의 다중 과업을 체계적으로 병렬 실행하고 조율하는 소프트웨어 아키텍처와 실행 모델을 포괄하는 개념이다.
2. 동시 제어의 형식적 정의
2.1 복합 임무와 동시 과업 집합
복합 임무 \mathcal{M}은 동시 실행 가능한 과업 집합 \mathcal{T} = \{T_1, T_2, \ldots, T_n\}과 이들 간의 동기화 제약(synchronization constraint) \mathcal{C}로 정의된다:
\mathcal{M} = (\mathcal{T}, \mathcal{C}, \mathcal{R})
여기서 \mathcal{R} = \{r_1, r_2, \ldots, r_m\}은 공유 자원 집합이다. 동시 제어 실행기(Concurrent Executive)는 이 복합 임무를 수신하여, 제약 조건을 만족하면서 과업들을 병렬 실행하는 역할을 수행한다.
2.2 동기화 제약의 유형
과업 간 동기화 제약 \mathcal{C}는 다음과 같은 유형으로 분류된다:
| 제약 유형 | 형식적 표현 | 설명 |
|---|---|---|
| 선행 제약(Precedence) | T_i \prec T_j | T_i 완료 후 T_j 시작 |
| 상호 배제(Mutual Exclusion) | T_i \perp T_j | T_i와 T_j 동시 실행 불가 |
| 동기 시작(Synchronous Start) | \text{start}(T_i) = \text{start}(T_j) | 동시 시작 |
| 동기 종료(Barrier) | \text{end}(T_i) = \text{end}(T_j) | 모두 완료 대기 |
| 자원 경합(Resource Contention) | \text{Resource}(T_i) \cap \text{Resource}(T_j) \neq \emptyset | 공유 자원 순차 접근 |
3. 동시 제어 아키텍처의 핵심 구성 요소
3.1 작업 디스패처(Task Dispatcher)
**작업 디스패처(Task Dispatcher)**는 임무 계획으로부터 과업 집합을 수신하고, 동기화 제약과 자원 가용성을 고려하여 과업을 실행 슬롯에 배치하는 역할을 한다. 디스패처의 핵심 기능은 다음과 같다:
\text{Dispatch}: (\mathcal{T}, \mathcal{C}, \mathcal{R}, \text{State}(t)) \rightarrow \mathcal{T}_{\text{ready}}(t)
여기서 \mathcal{T}_{\text{ready}}(t) \subseteq \mathcal{T}는 시간 t에서 실행 가능한 과업의 집합이다. 과업 T_i가 실행 가능하려면 다음 조건을 만족해야 한다:
T_i \in \mathcal{T}_{\text{ready}}(t) \iff \begin{cases} \forall T_j \prec T_i : \text{Status}(T_j) = \texttt{COMPLETED} \\ \forall T_k \perp T_i : \text{Status}(T_k) \neq \texttt{RUNNING} \\ \text{Resource}(T_i) \subseteq \text{Available}(t) \end{cases}
3.2 실행 관리기(Execution Manager)
**실행 관리기(Execution Manager)**는 디스패처로부터 배정된 과업을 실제로 실행하고, 각 과업의 상태를 추적하며, 완료/실패/중단 이벤트를 처리한다. 실행 관리기는 각 과업에 대해 다음과 같은 상태 전이를 관리한다:
\text{TaskState}(T_i) \in \{\texttt{PENDING}, \texttt{RUNNING}, \texttt{COMPLETED}, \texttt{FAILED}, \texttt{CANCELED}\}
3.3 자원 관리기(Resource Manager)
**자원 관리기(Resource Manager)**는 공유 자원의 할당과 해제를 관리한다. 자원 r_j에 대한 할당 요청은 다음 조건에 따라 처리된다:
\text{Allocate}(r_j, T_i) = \begin{cases} \texttt{GRANTED} & \text{if } r_j \in \text{Available}(t) \\ \texttt{QUEUED} & \text{if } r_j \notin \text{Available}(t) \end{cases}
자원 관리기는 교착 상태(deadlock) 방지를 위해 자원 순서 규약(resource ordering protocol) 또는 **은행가 알고리즘(Banker’s algorithm)**을 적용할 수 있다.
4. 동시 제어 실행 모델
4.1 센스-플랜-액트(Sense-Plan-Act) 병렬화
전통적 센스-플랜-액트(SPA, Sense-Plan-Act) 아키텍처의 순차적 실행을 병렬화하여, 각 단계를 독립적인 동시 과업으로 구동한다:
\text{ConcurrentSPA} = \text{Parallel}(\text{Sense}_{\text{continuous}}, \text{Plan}_{\text{reactive}}, \text{Act}_{\text{feedback}})
이 구조에서 센싱은 연속적으로 환경 데이터를 수집하고, 계획기는 새로운 정보에 반응적으로 경로를 갱신하며, 실행기는 최신 계획에 따라 제어 명령을 출력한다.
4.2 에이전트 기반 동시 실행
에이전트 기반 접근에서, 각 과업은 독립적인 **에이전트(agent)**로 캡슐화되며, 에이전트 간의 협력과 경합은 메시지 전달(message passing) 또는 **공유 메모리(shared memory)**를 통해 조율된다. 에이전트 A_i의 실행 모델은 다음과 같다:
A_i : \text{Loop}\bigl(\text{Perceive}(\mathcal{E}) \rightarrow \text{Decide}(\mathcal{B}_i) \rightarrow \text{Execute}(\mathcal{A}_i)\bigr)
여기서 \mathcal{E}는 환경 상태, \mathcal{B}_i는 에이전트의 신념(belief) 집합, \mathcal{A}_i는 행동 집합이다. 다수의 에이전트가 동시에 실행되며, **조율기(coordinator)**가 전역적 목표 달성을 위한 중재 역할을 수행한다.
4.3 코루틴(Coroutine) 기반 협력적 동시성
코루틴(Coroutine) 기반 동시성은 운영체제 수준의 스레드를 사용하지 않고, 사용자 수준에서 과업 간 제어를 양보(yield)하는 협력적 멀티태스킹을 구현한다. 각 과업은 실행 중 적절한 시점에서 제어를 양보하고, 스케줄러가 다음 과업에 제어를 전달한다:
T_i : \text{Execute}(\text{step}_1) \rightarrow \texttt{yield} \rightarrow \text{Execute}(\text{step}_2) \rightarrow \texttt{yield} \rightarrow \cdots
코루틴 기반 접근은 스레드 동기화의 복잡성(경쟁 조건, 교착 상태)을 회피하면서도 동시적 행동 실행의 효과를 달성할 수 있다. 행동 트리의 틱(tick) 기반 실행 모델도 본질적으로 코루틴 패턴에 해당한다.
5. TCA/TDL과 EXEC 프레임워크
5.1 Task Control Architecture (TCA)
**TCA(Task Control Architecture)**는 Simmons (1994)에 의해 제안된 동시 제어 프레임워크로서, 과업 간의 **시간적 제약(temporal constraint)**과 **자원 제약(resource constraint)**을 명시적으로 관리한다. TCA의 핵심 구성 요소는 다음과 같다:
- 중앙 제어기(Central Controller): 과업의 생성, 디스패치, 모니터링을 관리
- 시간 제약 네트워크: 과업 간 선행/후행/동기 관계를 그래프로 표현
- 예외 처리기(Exception Handler): 과업 실패 시 복구 행동을 자동으로 실행
- 모니터(Monitor): 환경 조건을 지속적으로 감시하여 과업 실행에 영향을 주는 이벤트를 감지
5.2 Task Description Language (TDL)
**TDL(Task Description Language)**은 TCA를 확장한 과업 기술 언어로서, C++ 기반의 구문에 과업 관리 의미론을 추가하였다(Simmons and Apfelbaum, 1998). TDL은 다음과 같은 동시 제어 기능을 언어 수준에서 제공한다:
| 기능 | 설명 |
|---|---|
spawn | 하위 과업의 동시 생성 및 실행 |
wait | 특정 과업의 완료 대기 |
terminate | 실행 중인 과업의 강제 종료 |
monitor | 조건 기반 이벤트 감시 |
exception handler | 과업 실패 시 복구 행동 등록 |
temporal constraint | 과업 간 시간적 제약 명시 |
6. 이벤트 구동 동시 제어
6.1 이벤트 루프(Event Loop) 기반 실행
이벤트 구동(event-driven) 동시 제어에서는 과업들이 이벤트 큐(event queue)를 공유하며, 이벤트 루프가 큐에서 이벤트를 추출하여 해당 과업에 전달한다:
\text{EventLoop}: \textbf{while } \text{true} \textbf{ do } e \leftarrow \text{dequeue}(\mathcal{Q}); \; \text{dispatch}(e)
이 모델은 단일 스레드로 동시 제어를 구현할 수 있으며, 이벤트 처리기(event handler)가 비차단적(non-blocking)으로 설계되면 효과적인 동시적 실행이 가능하다.
6.2 발행-구독(Publish-Subscribe) 기반 과업 조율
ROS2의 발행-구독(publish-subscribe) 모델을 활용하여, 동시 실행 중인 과업들이 토픽을 통해 상태 정보를 공유하고 상호 조율하는 패턴이 있다. 각 과업은 자신의 상태를 토픽에 발행하고, 의존적 과업은 해당 토픽을 구독하여 실행 시점을 결정한다:
T_i \xrightarrow{\text{publish}} \text{Topic}(\text{Status}_i), \quad T_j \xrightarrow{\text{subscribe}} \text{Topic}(\text{Status}_i)
7. 동시 제어에서의 안전성 보장
7.1 경쟁 조건(Race Condition) 방지
다수의 과업이 공유 자원이나 상태 변수에 동시에 접근할 때 **경쟁 조건(race condition)**이 발생할 수 있다. 이를 방지하기 위해 다음과 같은 동기화 메커니즘이 적용된다:
| 메커니즘 | 적용 상황 |
|---|---|
| 뮤텍스(Mutex) | 공유 데이터의 배타적 접근 |
| 세마포어(Semaphore) | 유한 자원의 동시 접근 수 제한 |
| 조건 변수(Condition Variable) | 특정 조건 충족 대기 |
| 읽기-쓰기 잠금(RW Lock) | 동시 읽기 허용, 배타적 쓰기 |
| 원자적 연산(Atomic Operation) | 잠금 없는 경량 동기화 |
7.2 교착 상태(Deadlock) 예방
다수의 과업이 자원을 순환적으로 대기하는 교착 상태를 예방하기 위해, 교착 상태의 필요 조건(상호 배제, 점유 대기, 비선점, 순환 대기)중 하나 이상을 제거하는 전략이 적용된다. 순환 대기 조건의 제거를 위한 자원 순서 규약은 다음과 같다:
\text{Order}(r_1) < \text{Order}(r_2) < \cdots < \text{Order}(r_m)
각 과업은 자원 순서의 오름차순으로만 자원을 요청하며, 이로써 순환 대기가 구조적으로 방지된다.
7.3 우선순위 역전(Priority Inversion) 방지
우선순위 기반 동시 제어에서 우선순위 역전(priority inversion) 문제가 발생할 수 있다. 이를 방지하기 위해 우선순위 상속 프로토콜(Priority Inheritance Protocol, PIP) 또는 **우선순위 천장 프로토콜(Priority Ceiling Protocol, PCP)**이 적용된다:
\text{PIP}: \text{Priority}(T_{\text{low}}) \leftarrow \max(\text{Priority}(T_{\text{low}}), \text{Priority}(T_{\text{high}})) \quad \text{during lock hold}
8. 사례 연구: 자율 드론의 동시 임무 실행
자율 드론의 정찰 임무에서 동시 제어 패러다임의 적용 예시는 다음과 같다:
| 동시 과업 | 역할 | 자원 요구 |
|---|---|---|
| T_{\text{nav}} | 경로 추종 내비게이션 | GPS, IMU, 모터 |
| T_{\text{cam}} | 영상 촬영 및 전송 | 카메라, 통신 대역폭 |
| T_{\text{obs}} | 장애물 탐지 및 회피 | LiDAR, 계산 자원 |
| T_{\text{bat}} | 배터리 상태 감시 | 배터리 센서 |
| T_{\text{comm}} | 지상 통제국 통신 유지 | 통신 모듈 |
이 과업들은 동시에 실행되며, T_{\text{obs}}가 장애물을 탐지하면 T_{\text{nav}}에 회피 명령을 전달하고, T_{\text{bat}}가 배터리 임계치 이하를 감지하면 모든 과업에 귀환 명령을 전파한다. 이러한 동시적 실행과 과업 간 조율이 동시 제어 패러다임의 실질적 구현 형태이다.
9. 참고 문헌
- Simmons, R. (1994). “Structured Control for Autonomous Robots.” IEEE Transactions on Robotics and Automation, 10(1), 34–43.
- Simmons, R. and Apfelbaum, D. (1998). “A Task Description Language for Robot Control.” Proceedings of the Conference on Intelligent Robotics and Systems (IROS), 1931–1937.
- Gat, E. (1998). “On Three-Layer Architectures.” Artificial Intelligence and Mobile Robots, MIT Press, 195–210.
- Muscettola, N., Nayak, P. P., Pell, B., and Williams, B. C. (1998). “Remote Agent: To Boldly Go Where No AI System Has Gone Before.” Artificial Intelligence, 103(1-2), 5–47.
- 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