396.36 상향식(Bottom-Up) 임무 합성 기법

1. 서론

상향식(bottom-up) 임무 합성 기법은 하양식(top-down) 분할과 대비되는 접근법으로, 개별 원자적 과업(primitive task)이나 행동(behavior) 단위에서 출발하여, 이들을 조합·합성(composition)하여 점진적으로 상위 수준의 복합 임무를 구성하는 방법론이다. 하양식 분할이 “무엇을 달성할 것인가“라는 목표로부터 출발하는 반면, 상향식 합성은 “무엇을 할 수 있는가“라는 가용 능력(capability)으로부터 출발한다.

상향식 접근법은 로봇의 현재 보유 능력과 사전 정의된 행동 라이브러리(behavior library)를 기반으로 실현 가능한 임무를 구성하는 데 적합하며, 특히 이기종(heterogeneous) 다중 로봇 시스템에서 각 로봇의 고유한 능력을 조합하여 협력 임무를 생성하는 데 효과적이다. 본 절에서는 상향식 합성의 기본 원리, 합성 연산자, 행동 라이브러리의 설계, 능력 기반 합성 기법, 그리고 하양식 분할과의 통합을 체계적으로 기술한다.

2. 상향식 합성의 기본 원리

2.1 능력 기반 접근(Capability-Based Approach)

상향식 합성은 로봇 시스템이 보유하는 원자적 능력(atomic capability)의 집합에서 출발한다. 로봇 $R_i$ 의 능력 집합 $\text{Cap}(R_i)$ 는:

$\text{Cap}(R_i) = \{a_1, a_2, \ldots, a_{n_i}\}$

여기서 $a_j$ 는 로봇 $R_i$ 가 수행할 수 있는 원자적 행동(예: 이동, 파지, 촬영, 전송 등)이다. 다중 로봇 시스템의 전체 능력 집합은:

$\text{Cap}_{\text{total}} = \bigcup_{i=1}^{N} \text{Cap}(R_i)$

상향식 합성은 이 능력 집합의 부분 집합을 선택하고, 적절한 순서와 조건으로 합성하여 임무를 구성한다.

2.2 합성(Composition)의 정의

행동의 합성은 기존의 행동들을 결합하여 새로운 복합 행동(compound behavior)을 생성하는 연산이다. 형식적으로, 합성 연산자 $\oplus$ 는:

$\oplus: \mathcal{B} \times \mathcal{B} \rightarrow \mathcal{B}$

여기서 $\mathcal{B}$ 는 행동의 집합이다. 합성의 결과로 생성된 복합 행동은 다시 합성의 입력으로 사용될 수 있으므로, 합성은 재귀적(recursive)으로 적용 가능하다.

3. 합성 연산자의 유형

3.1 순차 합성(Sequential Composition)

두 행동을 순서대로 수행하는 합성이다:

$b_{\text{seq}} = b_1 \;;\; b_2$

$b_1$ 의 종료 상태(terminal state)가 $b_2$ 의 전제 조건(precondition)을 만족하는 경우에만 유효하다:

$\text{post}(b_1) \subseteq \text{pre}(b_2)$

여기서 $\text{post}(b_1)$ 은 $b_1$ 수행 후의 사후 조건(postcondition), $\text{pre}(b_2)$ 는 $b_2$ 의 전제 조건이다. 이 조건은 합성의 **연결 가능성(composability)**을 보장한다.

순차 합성의 전이 시스템(transition system) 표현에서, 합성된 행동의 상태 공간은 개별 행동의 상태 공간의 직렬 연결이 된다.

3.2 병렬 합성(Parallel Composition)

두 행동을 동시에 수행하는 합성이다:

$b_{\text{par}} = b_1 \;\|\; b_2$

병렬 합성은 두 행동이 사용하는 자원이 상호 배타적(mutually exclusive)인 경우에 유효하다:

$\text{res}(b_1) \cap \text{res}(b_2) = \emptyset$

여기서 $\text{res}(b)$ 는 행동 $b$ 가 요구하는 자원의 집합이다. 자원 충돌이 발생하면 중재(arbitration) 메커니즘이 필요하다.

3.3 조건부 합성(Conditional Composition)

시스템 상태에 따라 행동을 선택하는 합성이다:

$b_{\text{cond}} = \text{if} \; \phi(\mathbf{s}) \; \text{then} \; b_1 \; \text{else} \; b_2$

여기서 $\phi(\mathbf{s})$ 는 시스템 상태 $\mathbf{s}$ 에 대한 부울 술어(Boolean predicate)이다. 이는 반응적(reactive) 임무 구성에 필수적인 합성 연산자이다.

3.4 반복 합성(Iterative Composition)

행동을 조건이 만족될 때까지 반복 수행하는 합성이다:

$b_{\text{iter}} = \text{while} \; \phi(\mathbf{s}) \; \text{do} \; b$

순찰(patrol), 탐색(search), 주기적 감시 등의 반복적 임무 패턴을 구성하는 데 사용된다.

3.5 우선순위 합성(Priority Composition)

복수의 행동에 우선순위를 부여하고, 가장 높은 우선순위의 활성화 가능한 행동을 선택하는 합성이다:

$b_{\text{pri}} = b_1 \triangleright b_2 \triangleright \ldots \triangleright b_n$

여기서 $\triangleright$ 는 우선순위 연산자이며, $b_1$ 이 가장 높은 우선순위를 가진다. 서브섬션 아키텍처(subsumption architecture)(Brooks, 1986)가 이 합성 유형의 대표적 사례이다.

3.6 퓨전 합성(Fusion Composition)

복수의 행동 출력을 가중 합산하여 단일 출력을 생성하는 합성이다:

$\mathbf{u}_{\text{fused}} = \sum_{i=1}^{n} w_i \cdot \mathbf{u}_i$

여기서 $\mathbf{u}_i$ 는 행동 $b_i$ 의 제어 출력, $w_i$ 는 가중치이다. 포텐셜 필드(potential field) 기반의 행동 합성, 모터 스키마(motor schema)(Arkin, 1998) 등이 이 접근법을 사용한다.

4. 행동 라이브러리(Behavior Library)

4.1 라이브러리의 구조

상향식 합성의 기반이 되는 행동 라이브러리는 사전 정의·검증된 원자적 행동의 모음집이다. 각 행동 $b$ 는 다음의 인터페이스 정보를 포함한다:

전제 조건 $\text{pre}(b)$ : 행동의 시작에 필요한 사전 상태
사후 조건 $\text{post}(b)$ : 행동 수행 후 보장되는 상태 변화
불변 조건 $\text{inv}(b)$ : 행동 수행 중 유지되어야 하는 조건
자원 요구 $\text{res}(b)$ : 필요한 센서, 액추에이터, 연산 자원
시간 특성 $\text{dur}(b)$ : 예상 소요 시간 (최소, 최빈, 최대)
에너지 소비 $\text{energy}(b)$ : 예상 에너지 소비량
매개변수 $\text{param}(b)$ : 목표 위치, 속도, 해상도 등의 조정 가능한 매개변수

4.2 라이브러리의 분류

행동 라이브러리는 기능별로 계층적으로 조직된다:

이동 행동: MoveTo, FollowPath, Hover, Land, Takeoff, Dock
감지 행동: Scan, Capture, Measure, DetectObject, ClassifyTarget
조작 행동: Grasp, Release, Push, Place, Assemble
통신 행동: Transmit, Receive, Relay, Broadcast
대기 행동: Wait, WaitForEvent, WaitForSignal

4.3 확장 가능한 라이브러리 설계

행동 라이브러리는 새로운 행동의 추가가 용이하고, 기존 행동의 수정이 다른 행동에 영향을 미치지 않도록 설계되어야 한다. 객체 지향 설계(object-oriented design)의 원칙, 특히 개방-폐쇄 원칙(Open-Closed Principle)이 적용된다:

새로운 행동 클래스의 추가는 개방(open)되어 있으나,
기존 행동의 인터페이스 수정은 폐쇄(closed)되어 있다.

5. 능력 기반 합성 기법

5.1 전제 조건-효과 체인(Precondition-Effect Chaining)

행동의 전제 조건과 효과를 연결하여 합성 가능한 행동 서열을 자동으로 탐색하는 기법이다. 이는 고전적 AI 계획(classical AI planning)의 전진 탐색(forward search) 또는 후진 탐색(backward search)과 동일한 원리이다.

전진 체이닝(forward chaining)에서, 초기 상태 $\mathbf{s}_0$ 에서 출발하여 적용 가능한 행동을 순차적으로 선택하며, 목표 상태 $\mathbf{s}_{\text{goal}}$ 에 도달하는 행동 서열을 탐색한다:

$\mathbf{s}_0 \xrightarrow{b_1} \mathbf{s}_1 \xrightarrow{b_2} \mathbf{s}_2 \xrightarrow{} \ldots \xrightarrow{b_n} \mathbf{s}_n \supseteq \mathbf{s}_{\text{goal}}$

후진 체이닝(backward chaining)에서는 목표 상태에서 출발하여 그 상태를 달성할 수 있는 행동을 역방향으로 탐색한다.

5.2 연결 가능성 그래프(Composability Graph)

행동 라이브러리의 모든 행동 쌍에 대한 순차 합성 가능성을 나타내는 유향 그래프 $G_{\text{comp}} = (\mathcal{B}, \mathcal{E}_{\text{comp}})$ 를 구성한다:

$(b_i, b_j) \in \mathcal{E}_{\text{comp}} \iff \text{post}(b_i) \supseteq \text{pre}(b_j)$

이 그래프 상의 경로(path)가 합성 가능한 행동 서열에 해당하며, 그래프 탐색 알고리즘(BFS, DFS, A* 등)을 적용하여 목표 달성 서열을 탐색할 수 있다.

5.3 임무 대수(Mission Algebra)

합성 연산자를 대수적 구조로 형식화하여, 임무의 합성·변환·동치 판정을 대수적 추론으로 수행하는 접근법이다. 행동 집합 $\mathcal{B}$ 와 합성 연산자(순차 $;$ , 병렬 $\|$ , 선택 $+$ ) 위의 대수적 구조를 정의한다.

프로세스 대수(process algebra)(Milner, 1989; Hoare, 1985)의 개념을 차용하여, CSP(Communicating Sequential Processes) 또는 CCS(Calculus of Communicating Systems)로 행동 합성을 형식화할 수 있다.

주요 대수적 법칙:

결합 법칙: $(b_1 \;;\; b_2) \;;\; b_3 = b_1 \;;\; (b_2 \;;\; b_3)$
교환 법칙(병렬): $b_1 \;\|\; b_2 = b_2 \;\|\; b_1$
분배 법칙: $b_1 \;;\; (b_2 + b_3) = (b_1 \;;\; b_2) + (b_1 \;;\; b_3)$

5.4 의미론적 웹 서비스 합성과의 유사성

상향식 행동 합성은 웹 서비스 합성(web service composition) 문제와 구조적으로 유사하다. 각 행동은 입력(전제 조건)과 출력(효과)을 가지는 서비스로 모델링되며, OWL-S(Web Ontology Language for Services)와 유사한 온톨로지 기반 매칭과 합성 알고리즘이 적용된다.

6. 하양식 분할과 상향식 합성의 통합

6.1 양방향 접근법(Meet-in-the-Middle)

실제 임무 설계에서는 하양식 분할과 상향식 합성을 결합한 양방향 접근법이 효과적이다. 상위 수준에서는 하양식으로 임무를 대략적 과업으로 분할하고, 하위 수준에서는 상향식으로 가용 행동을 합성하여 각 과업을 구현한다.

$M \xrightarrow[\text{top-down}]{\text{분할}} \{T_1, T_2, \ldots, T_m\} \xleftarrow[\text{bottom-up}]{\text{합성}} \{\oplus(b_{i_1}, b_{i_2}, \ldots)\}$

하양식 분할의 말단 과업과 상향식 합성의 최상위 복합 행동이 만나는 **계획 경계(planning boundary)**에서 두 접근법이 통합된다. 이 경계에서의 인터페이스 일관성(과업의 요구 사항과 합성된 행동의 능력 간의 매칭)이 통합의 핵심 과제이다.

6.2 통합시 고려사항

하양식 분할은 임무의 전체적 구조와 논리적 흐름을 보장하는 반면, 상향식 합성은 물리적 실현 가능성과 로봇의 실제 능력을 반영한다. 양자의 통합에서 고려하여야 할 사항은:

능력 격차(capability gap): 하양식 분할에서 요구하는 과업 중 가용 행동의 합성으로 달성할 수 없는 과업의 식별과 처리
잉여 능력(surplus capability): 상향식 합성에서 가능하나 하양식 분할에서 고려되지 않은 추가적 기회의 활용
추상화 수준 정합(abstraction level alignment): 양 방향의 추상화 수준이 일치하는 적절한 계획 경계의 설정

7. 참고문헌

Brooks, R. A. (1986). “A Robust Layered Control System for a Mobile Robot.” IEEE Journal on Robotics and Automation, 2(1), 14–23.
Arkin, R. C. (1998). Behavior-Based Robotics. MIT Press.
Milner, R. (1989). Communication and Concurrency. Prentice Hall.
Hoare, C. A. R. (1985). Communicating Sequential Processes. Prentice Hall.
Gat, E. (1998). “On Three-Layer Architectures.” Artificial Intelligence and Mobile Robots, MIT Press, 195–210.
Mataric, M. J. (1997). “Behavior-Based Control: Examples from Navigation, Learning, and Group Behavior.” Journal of Experimental and Theoretical Artificial Intelligence, 9(2–3), 323–336.
Burridge, R. R., Rizzi, A. A., and Koditschek, D. E. (1999). “Sequential Composition of Dynamically Dexterous Robot Behaviors.” The International Journal of Robotics Research, 18(6), 534–555.

본 절은 로봇공학 서적 Volume 9, Part 53, Chapter 396의 일부로 작성되었다. 버전: 2026-03-24 v2.0