397.15 임무 계획의 수학적 제약 조건 분석

1. 제약 조건의 개요와 분류

자율 로봇 시스템의 임무 계획은 다양한 제약 조건(constraint)의 동시 충족을 요구하는 제약 만족 문제(Constraint Satisfaction Problem, CSP) 또는 제약 최적화 문제(Constrained Optimization Problem, COP)로 정식화된다. 임무 계획에서 제약 조건은 로봇의 물리적 한계, 환경적 조건, 임무 요구사항, 운용 규정 등 다양한 원천으로부터 발생하며, 이들의 체계적 분류와 수학적 모델링은 효과적인 임무 계획 알고리즘 설계의 기초를 형성한다 (LaValle, 2006).

임무 계획의 제약 조건은 다음의 기준에 따라 분류된다.

1.1 경성 제약과 연성 제약

경성 제약(Hard Constraint): 반드시 충족되어야 하는 불가침 제약으로서, 위반 시 임무의 실행 자체가 불가능하거나 안전성이 훼손된다. 물리적 한계, 장애물 회피, 비행 금지 구역 제약 등이 이에 해당한다.

g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m_h

연성 제약(Soft Constraint): 충족이 권장되나, 위반 시에도 임무 수행이 가능한 제약으로서, 위반 정도에 비례하는 비용(penalty)이 부과된다. 최적 경로 선택, 에너지 효율 최대화 등의 목표가 이에 해당한다.

\min_{\mathbf{x}} \sum_{j=1}^{m_s} w_j \cdot \max(0, h_j(\mathbf{x}))

여기서 w_j는 각 연성 제약의 가중치이다.

1.2 등식 제약과 부등식 제약

등식 제약(Equality Constraint): 상태 변수가 특정 값을 정확히 취해야 하는 조건이다. 시스템 역학(dynamics), 초기 조건, 종단 조건 등이 등식 제약으로 표현된다.

h_k(\mathbf{x}) = 0, \quad k = 1, \ldots, p

부등식 제약(Inequality Constraint): 상태 변수가 허용 범위 내에 있어야 하는 조건이다. 안전 거리 유지, 속도 제한, 에너지 소비 상한 등이 부등식 제약으로 표현된다.

g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m

2. 임무 계획의 일반적 수학적 정식화

자율 로봇의 임무 계획 문제는 다음의 일반적 제약 최적화 문제로 정식화된다:

\begin{aligned} \min_{\mathbf{u}(t), \, t \in [t_0, t_f]} \quad & J = \Phi(\mathbf{x}(t_f)) + \int_{t_0}^{t_f} L(\mathbf{x}(t), \mathbf{u}(t), t) \, dt \\ \text{subject to} \quad & \dot{\mathbf{x}}(t) = f(\mathbf{x}(t), \mathbf{u}(t), t) \quad (\text{시스템 역학}) \\ & \mathbf{x}(t_0) = \mathbf{x}_0 \quad (\text{초기 조건}) \\ & \psi(\mathbf{x}(t_f)) = \mathbf{0} \quad (\text{종단 조건}) \\ & g(\mathbf{x}(t), \mathbf{u}(t), t) \leq \mathbf{0} \quad (\text{경로 제약}) \\ & \mathbf{u}_{\min} \leq \mathbf{u}(t) \leq \mathbf{u}_{\max} \quad (\text{제어 입력 제약}) \\ & \varphi \text{ 만족} \quad (\text{시제 논리 명세}) \end{aligned}

여기서 \mathbf{x}(t) \in \mathbb{R}^n은 상태 벡터, \mathbf{u}(t) \in \mathbb{R}^m은 제어 입력 벡터, J는 비용 함수(cost function), \Phi는 종단 비용(terminal cost), L은 실행 비용(running cost), f는 시스템 역학 함수, \varphi는 시제 논리(temporal logic)로 명세된 임무 요구사항이다.

3. 제약 조건의 유형별 수학적 구조

3.1 역학적 제약

로봇의 운동 역학(kinematics and dynamics)은 임무 계획의 기본적 등식 제약을 형성한다. 비홀로노믹 로봇(nonholonomic robot)의 경우, 운동학적 제약은 다음과 같이 표현된다:

\dot{x} = v \cos\theta, \quad \dot{y} = v \sin\theta, \quad \dot{\theta} = \omega

여기서 (x, y)는 평면 위치, \theta는 방향각, v는 선속도, \omega는 각속도이다. 이러한 비홀로노믹 제약 A(\mathbf{q})\dot{\mathbf{q}} = \mathbf{0}은 구성 공간(configuration space)에서의 운동 가능성을 제한하며, 임무 계획 시 로봇이 물리적으로 실현 가능한(feasible) 궤적만을 생성하도록 보장한다.

쿼드로터(quadrotor) 드론의 경우, 6자유도 강체 역학이 다음과 같이 기술된다:

m\ddot{\mathbf{p}} = -mg\mathbf{e}_3 + f R\mathbf{e}_3, \quad J\dot{\boldsymbol{\omega}} = \boldsymbol{\tau} - \boldsymbol{\omega} \times J\boldsymbol{\omega}

여기서 \mathbf{p}는 위치 벡터, R는 회전 행렬, f는 총 추력, \boldsymbol{\tau}는 토크 벡터, J는 관성 행렬이다.

3.2 상태 공간 제약

상태 변수의 허용 범위에 대한 제약은 다음과 같이 표현된다:

\mathbf{x}(t) \in \mathcal{X}_{\text{safe}} \subseteq \mathbb{R}^n, \quad \forall t \in [t_0, t_f]

안전 상태 공간 \mathcal{X}_{\text{safe}}는 일반적으로 장애물 영역의 여집합(complement)으로 정의된다:

\mathcal{X}_{\text{safe}} = \mathcal{X} \setminus \bigcup_{i=1}^{N_{\text{obs}}} \mathcal{O}_i

여기서 \mathcal{O}_i는 i번째 장애물의 점유 영역이다. 장애물이 볼록 다면체(convex polyhedron)로 모델링되는 경우, 장애물 회피 제약은 다음의 분리 제약(disjunctive constraint)으로 인코딩된다:

\exists j \in \{1, \ldots, n_f^{(i)}\}, \quad \mathbf{a}_j^{(i)} \cdot \mathbf{x}(t) > b_j^{(i)}

여기서 \mathbf{a}_j^{(i)} \cdot \mathbf{x} \leq b_j^{(i)}는 i번째 장애물의 j번째 반평면(halfplane) 제약이다. 이러한 분리 제약은 혼합 정수 프로그래밍(Mixed Integer Programming, MIP) 기법으로 처리할 수 있다.

3.3 제어 입력 제약

제어 입력의 물리적 한계는 다음의 상자 제약(box constraint)으로 표현된다:

\mathbf{u}_{\min} \leq \mathbf{u}(t) \leq \mathbf{u}_{\max}, \quad \forall t \in [t_0, t_f]

추력 크기 제한, 조향각 제한, 모터 토크 제한 등이 이 형태로 모델링된다. 또한 제어 입력의 변화율(rate of change)에 대한 제약도 부과될 수 있다:

\lVert \dot{\mathbf{u}}(t) \rVert \leq \delta_{\max}

이는 액추에이터의 응답 속도 한계를 반영하며, 급격한 제어 입력 변동으로 인한 기계적 응력(stress)을 방지한다.

3.4 선후 관계 제약

복수의 임무 작업(task) 간의 실행 순서에 대한 제약은 선후 관계 제약(precedence constraint)으로 표현된다:

t_{\text{end}}^{(i)} \leq t_{\text{start}}^{(j)}, \quad \forall (i, j) \in \mathcal{E}

여기서 t_{\text{end}}^{(i)}는 작업 i의 종료 시각, t_{\text{start}}^{(j)}는 작업 j의 시작 시각, \mathcal{E}는 선후 관계 에지(edge)의 집합이다. 이러한 제약은 방향 비순환 그래프(Directed Acyclic Graph, DAG)로 모델링되며, 위상 정렬(topological sorting)을 통하여 실행 가능한 작업 순서를 결정할 수 있다 (Cormen et al., 2009).

3.5 상호 배제 제약

동시에 수행될 수 없는 작업 쌍에 대한 제약은 상호 배제 제약(mutual exclusion constraint)으로 표현된다:

[t_{\text{start}}^{(i)}, t_{\text{end}}^{(i)}] \cap [t_{\text{start}}^{(j)}, t_{\text{end}}^{(j)}] = \emptyset, \quad \forall (i, j) \in \mathcal{M}

여기서 \mathcal{M}은 상호 배제 관계에 있는 작업 쌍의 집합이다. 단일 로봇이 동시에 두 지점에 존재할 수 없는 물리적 제약, 또는 공유 자원에 대한 배타적 접근 요구가 이에 해당한다.

4. 제약 만족 문제로서의 정식화

임무 계획의 제약 조건들을 통합하면, 다음의 제약 만족 문제(CSP)로 정식화된다:

\text{CSP} = (\mathcal{V}, \mathcal{D}, \mathcal{C})

여기서:

• \mathcal{V} = \{v_1, v_2, \ldots, v_n\}: 결정 변수(decision variable)의 집합
• \mathcal{D} = \{D_1, D_2, \ldots, D_n\}: 각 변수의 정의역(domain) 집합
• \mathcal{C} = \{C_1, C_2, \ldots, C_m\}: 제약 조건의 집합

임무 계획의 경우, 결정 변수는 작업의 할당(assignment), 시작 시각, 종료 시각, 자원 배분량 등을 포함하며, 제약 조건은 시간, 공간, 자원에 대한 다양한 요구사항을 인코딩한다.

4.1 호 일관성과 제약 전파

CSP의 효율적 해결을 위하여, 호 일관성(arc consistency) 기법과 제약 전파(constraint propagation) 기법이 활용된다. 호 일관성은 각 변수의 정의역에서, 제약 조건을 위반하는 값을 사전에 제거하여 탐색 공간을 축소하는 기법이다 (Mackworth, 1977).

변수 v_i와 v_j 사이의 제약 C_{ij}에 대하여, 호 일관성은 다음과 같이 정의된다:

\forall a \in D_i, \; \exists b \in D_j \text{ s.t. } (a, b) \in C_{ij}

이 조건이 충족되면, v_i의 정의역 D_i의 모든 값에 대하여 v_j에서 호환 가능한 값이 존재함이 보장된다.

5. 제약 조건의 계산 복잡도

임무 계획의 제약 조건이 포함하는 구조에 따라 문제의 계산 복잡도가 결정된다.

선형 제약만을 포함하는 임무 계획은 선형 계획법(Linear Programming, LP)으로 다항 시간 내에 해결 가능하나, 장애물 회피와 같은 분리 제약이나 정수 변수가 포함되면 NP-hard 문제가 된다. 시제 논리 명세가 추가되면 복잡도는 더욱 증가한다. 따라서 실제 임무 계획 시스템에서는 완화(relaxation), 근사(approximation), 분해(decomposition) 등의 전략을 통하여 계산 가능성을 확보하는 것이 필수적이다 (Wolsey, 1998).

6. 제약 완화 기법

6.1 라그랑주 완화

경성 제약을 라그랑주 승수(Lagrange multiplier) \boldsymbol{\lambda}를 사용하여 목적 함수에 통합하는 라그랑주 완화(Lagrangian relaxation) 기법은 다음과 같이 정식화된다:

\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = J(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i g_i(\mathbf{x})

라그랑주 쌍대 문제(Lagrangian dual problem)를 통하여 원 문제의 하계(lower bound)를 획득하고, 이를 기반으로 분기 한정법(branch and bound) 등의 정확 해법에 활용할 수 있다.

6.2 제약 조건 계층화

임무 계획의 제약 조건을 중요도에 따라 계층적(hierarchical)으로 구조화하는 접근법이 있다. 높은 우선순위의 제약(안전성, 물리적 한계)을 먼저 충족하고, 이어서 낮은 우선순위의 제약(성능 최적화, 편의성)을 점진적으로 충족하는 전략이다 (Siciliano et al., 2009):

\text{우선순위 1}: \quad g_1(\mathbf{x}) \leq 0 \quad (\text{안전성}) \\ \text{우선순위 2}: \quad g_2(\mathbf{x}) \leq 0 \quad (\text{시간 제약}) \\ \text{우선순위 3}: \quad \min J(\mathbf{x}) \quad (\text{비용 최적화})

이러한 계층적 접근은 모든 제약을 동시에 만족하는 해가 존재하지 않는 경우에도, 높은 우선순위의 제약을 보장하면서 최선의 해를 산출할 수 있다.

7. 참고문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
• Mackworth, A. K. (1977). “Consistency in Networks of Relations.” Artificial Intelligence, 8(1), 99–118.
• Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.
• Wolsey, L. A. (1998). Integer Programming. John Wiley & Sons.