397.17 공간 제약 조건의 모델링

1. 공간 제약의 개요

자율 로봇 시스템의 임무 계획에서 공간 제약 조건(spatial constraint)은 로봇의 운동 범위, 허용 작업 영역, 금지 구역, 목표 영역, 상호 간 거리 제약 등 공간적 성질에 관한 요구사항을 형식적으로 기술하는 수학적 조건이다. 공간 제약은 물리적 환경과 로봇의 기하학적(geometric) 특성에 의하여 결정되며, 안전한 임무 수행과 작업 영역의 효과적 활용을 보장하기 위한 필수적 요소이다 (LaValle, 2006).

공간 제약 조건은 다음의 기본 유형으로 분류된다:

영역 제약(Region Constraint): 로봇이 특정 영역 내에 머물거나 특정 영역에 도달해야 하는 조건
회피 제약(Avoidance Constraint): 로봇이 특정 영역이나 장애물에 진입하지 않아야 하는 조건
거리 제약(Distance Constraint): 로봇 간 또는 로봇과 특정 지점 간의 거리가 특정 범위 내에 있어야 하는 조건
경계 제약(Boundary Constraint): 작업 공간의 물리적 한계에 의한 운동 범위 제한

2. 구성 공간과 자유 공간

2.1 구성 공간의 정의

구성 공간(Configuration Space, $\mathcal{C}$ -space)은 로봇의 모든 가능한 구성(configuration)을 포함하는 공간이다 (Lozano-Pérez, 1983). $n$ 개의 자유도(degree of freedom)를 가진 로봇의 구성은 $\mathbf{q} = (q_1, q_2, \ldots, q_n) \in \mathcal{C}$ 로 표현되며, 구성 공간의 차원은 자유도의 수와 동일하다.

평면 이동 로봇: $\mathcal{C} = \mathbb{R}^2$ (위치 $(x, y)$ )
평면 이동 + 회전 로봇: $\mathcal{C} = \mathbb{R}^2 \times SO(2)$ (위치와 방향 $(x, y, \theta)$ )
6자유도 비행체: $\mathcal{C} = \mathbb{R}^3 \times SO(3)$ (위치와 자세)
$n$ -링크 매니퓰레이터: $\mathcal{C} = \mathbb{T}^n$ ( $n$ 차원 토러스)

2.2 장애물 공간과 자유 공간

임무 공간에 존재하는 장애물(obstacle)들은 구성 공간에서 장애물 영역( $\mathcal{C}_{\text{obs}}$ )으로 변환된다. 자유 공간(free space)은 장애물 영역의 여집합으로 정의된다:

$\mathcal{C}_{\text{free}} = \mathcal{C} \setminus \mathcal{C}_{\text{obs}}$

로봇의 물리적 형상을 $\mathcal{A}(\mathbf{q})$ 라 하면, 장애물 $\mathcal{O}_i$ 에 대한 구성 공간 장애물은 민코프스키 합(Minkowski sum)을 활용하여 다음과 같이 계산된다:

$\mathcal{C}_{\text{obs}}^{(i)} = \{\mathbf{q} \in \mathcal{C} \mid \mathcal{A}(\mathbf{q}) \cap \mathcal{O}_i \neq \emptyset\}$

전체 장애물 영역은 개별 장애물 영역의 합집합이다:

$\mathcal{C}_{\text{obs}} = \bigcup_{i=1}^{N_{\text{obs}}} \mathcal{C}_{\text{obs}}^{(i)}$

3. 영역 제약의 수학적 모델링

3.1 볼록 다면체 영역

볼록 다면체(convex polyhedron)로 표현되는 영역 $\mathcal{R}$ 은 반평면(halfplane) 교차로 정의된다:

$\mathcal{R} = \{\mathbf{x} \in \mathbb{R}^n \mid A\mathbf{x} \leq \mathbf{b}\}$

여기서 $A \in \mathbb{R}^{m \times n}$ 은 반평면 법선 벡터(normal vector)의 행렬, $\mathbf{b} \in \mathbb{R}^m$ 은 오프셋 벡터이다. 로봇의 위치 $\mathbf{p}(t)$ 가 시각 $t$ 에서 영역 $\mathcal{R}$ 내에 있어야 하는 제약은 다음과 같이 표현된다:

$A\mathbf{p}(t) \leq \mathbf{b}, \quad \forall t \in [t_0, t_f]$

3.2 원형 및 타원형 영역

원형 영역은 중심 $\mathbf{c}$ 와 반지름 $r$ 에 의하여 정의된다:

$\mathcal{R}_{\text{circle}} = \{\mathbf{x} \in \mathbb{R}^2 \mid \lVert \mathbf{x} - \mathbf{c} \rVert_2 \leq r\}$

타원형 영역은 양의 정부호 행렬(positive definite matrix) $Q$ 에 의하여 정의된다:

$\mathcal{R}_{\text{ellipse}} = \{\mathbf{x} \in \mathbb{R}^n \mid (\mathbf{x} - \mathbf{c})^\top Q (\mathbf{x} - \mathbf{c}) \leq 1\}$

이러한 이차(quadratic) 형태의 영역 제약은 이차 부등식 제약으로 직접 인코딩되며, 볼록 최적화(convex optimization) 기법을 통하여 효율적으로 처리할 수 있다.

3.3 비볼록 영역

비볼록(non-convex) 영역은 볼록 영역의 합집합(union)으로 근사할 수 있다:

$\mathcal{R}_{\text{non-convex}} = \bigcup_{k=1}^{K} \mathcal{R}_k$

로봇의 위치가 비볼록 영역 내에 있어야 하는 제약은, 적어도 하나의 볼록 영역에 속해야 함을 의미하므로 분리적(disjunctive) 구조를 가진다:

$\bigvee_{k=1}^{K} \left( A_k \mathbf{p}(t) \leq \mathbf{b}_k \right)$

이러한 분리 제약은 혼합 정수 프로그래밍(Mixed Integer Programming, MIP)의 빅-M 기법(big-M method)을 사용하여 이진 변수(binary variable) $z_k$ 로 인코딩된다:

$A_k \mathbf{p}(t) \leq \mathbf{b}_k + M(1 - z_k), \quad \sum_{k=1}^{K} z_k \geq 1, \quad z_k \in \{0, 1\}$

여기서 $M$ 은 충분히 큰 상수이다.

4. 장애물 회피 제약의 모델링

4.1 점 장애물 회피

점 장애물(point obstacle)에 대한 회피 제약은 안전 거리(safety distance) $d_{\text{safe}}$ 를 통하여 다음과 같이 표현된다:

$\lVert \mathbf{p}(t) - \mathbf{p}_{\text{obs}} \rVert_2 \geq d_{\text{safe}}, \quad \forall t \in [t_0, t_f]$

이 제약은 비볼록(non-convex)이므로, 직접적인 볼록 최적화로 처리할 수 없다. 이를 해결하기 위한 접근법으로는 다음이 사용된다:

선형화(Linearization): 현재 위치에서의 장애물 방향으로의 분리 반평면(separating hyperplane)을 통한 선형 근사
순차 볼록 프로그래밍(Sequential Convex Programming, SCP): 비볼록 제약을 반복적으로 선형화하여 수렴하는 기법 (Schulman et al., 2014)
혼합 정수 인코딩: 장애물의 볼록 다면체 표현에 기반한 MIP 인코딩

4.2 다면체 장애물 회피

볼록 다면체 장애물 $\mathcal{O} = \{\mathbf{x} \mid A_{\text{obs}}\mathbf{x} \leq \mathbf{b}_{\text{obs}}\}$ 에 대한 회피 제약은, 장애물을 정의하는 반평면 중 적어도 하나의 외부에 위치해야 함을 의미한다:

$\mathbf{p}(t) \notin \mathcal{O} \iff \bigvee_{j=1}^{n_f} \left( \mathbf{a}_j^\top \mathbf{p}(t) > b_j \right)$

여기서 $\mathbf{a}_j^\top \mathbf{x} \leq b_j$ 는 장애물의 $j$ 번째 면(facet)을 정의하는 반평면 제약이다.

이진 변수 $\delta_j \in \{0, 1\}$ 를 도입하여 MIP 형태로 인코딩하면:

$\mathbf{a}_j^\top \mathbf{p}(t) \geq b_j + \epsilon - M(1 - \delta_j), \quad \sum_{j=1}^{n_f} \delta_j \geq 1$

여기서 $\epsilon > 0$ 은 엄격한 부등식을 보장하기 위한 작은 양수이다.

4.3 동적 장애물 회피

이동하는 장애물(dynamic obstacle)에 대한 회피 제약은 시간에 따라 변화하는 장애물 위치를 고려해야 한다:

$\lVert \mathbf{p}(t) - \mathbf{p}_{\text{obs}}(t) \rVert_2 \geq d_{\text{safe}}, \quad \forall t \in [t_0, t_f]$

동적 장애물의 궤적 $\mathbf{p}_{\text{obs}}(t)$ 가 알려진 경우, 시간 이산화(time discretization)를 통하여 각 시간 단계에서의 회피 제약으로 변환할 수 있다. 불확실한 장애물 운동에 대해서는 확률적 회피 제약(chance constraint)이 도입된다:

$P(\lVert \mathbf{p}(t) - \mathbf{p}_{\text{obs}}(t) \rVert_2 \geq d_{\text{safe}}) \geq 1 - \alpha$

여기서 $\alpha$ 는 허용 충돌 확률(risk tolerance)이다.

5. 거리 제약의 모델링

5.1 로봇 간 상호 거리 제약

다중 로봇 시스템에서 충돌 방지를 위한 최소 거리 제약은 다음과 같이 표현된다:

$\lVert \mathbf{p}_i(t) - \mathbf{p}_j(t) \rVert_2 \geq d_{\min}, \quad \forall i \neq j, \; \forall t$

반대로, 통신 범위 유지를 위한 최대 거리 제약은 다음과 같이 표현된다:

$\lVert \mathbf{p}_i(t) - \mathbf{p}_j(t) \rVert_2 \leq d_{\max}, \quad \forall (i, j) \in \mathcal{E}_{\text{comm}}, \; \forall t$

여기서 $\mathcal{E}_{\text{comm}}$ 은 통신 연결이 필요한 로봇 쌍의 집합이다.

5.2 대형 유지 제약

다중 로봇이 특정 대형(formation)을 유지하면서 이동해야 하는 제약은 다음과 같이 표현된다:

$\mathbf{p}_i(t) = \mathbf{p}_{\text{center}}(t) + R(\theta(t)) \mathbf{d}_i, \quad \forall i$

여기서 $\mathbf{p}_{\text{center}}(t)$ 는 대형의 기준점, $R(\theta(t))$ 는 대형의 회전 행렬, $\mathbf{d}_i$ 는 로봇 $i$ 의 대형 내 상대 위치이다. 완벽한 대형 유지가 불가능한 경우, 허용 오차를 도입한 연성 제약으로 완화할 수 있다:

$\lVert \mathbf{p}_i(t) - (\mathbf{p}_{\text{center}}(t) + R(\theta(t)) \mathbf{d}_i) \rVert_2 \leq \epsilon_{\text{form}}$

6. 공간 분할과 셀 분해

6.1 셀 분해 기법

셀 분해(cell decomposition)는 자유 공간 $\mathcal{C}_{\text{free}}$ 를 유한 개의 단순한 셀(cell)로 분할하여, 연속 공간의 제약을 이산적 그래프 구조로 변환하는 기법이다 (Latombe, 1991).

정확 셀 분해(Exact Cell Decomposition): 자유 공간을 정확하게 분할한다. 수직 분해(vertical decomposition)나 사다리꼴 분해(trapezoidal decomposition)가 대표적이며, 2차원 다각형 장애물 환경에서 $O(n \log n)$ 의 시간 복잡도로 수행 가능하다.

근사 셀 분해(Approximate Cell Decomposition): 자유 공간을 일정 해상도의 격자(grid) 또는 사분 트리(quadtree)로 근사한다. 해상도를 높이면 정밀도가 향상되나 계산 비용이 증가한다.

6.2 보로노이 다이어그램

보로노이 다이어그램(Voronoi diagram)은 장애물로부터 등거리에 위치하는 점들의 궤적으로 정의되며, 장애물 회피 여유를 최대화하는 경로의 기반 구조를 제공한다:

$\mathcal{V}(\mathbf{x}) = \{\mathbf{p} \in \mathcal{C}_{\text{free}} \mid d(\mathbf{p}, \mathcal{O}_i) = d(\mathbf{p}, \mathcal{O}_j), \; i \neq j\}$

보로노이 다이어그램 위에서의 임무 계획은 장애물로부터의 최대 안전 거리를 유지하면서 목표에 도달하는 경로를 탐색하므로, 안전성 제약을 자연스럽게 충족한다.

7. 고도 및 3차원 공간 제약

7.1 고도 제약

비행 로봇(드론)의 경우, 고도에 대한 제약이 추가된다:

$h_{\min} \leq z(t) \leq h_{\max}, \quad \forall t \in [t_0, t_f]$

여기서 $h_{\min}$ 은 최소 비행 고도, $h_{\max}$ 는 최대 비행 고도이다. 지형 추종 비행(terrain-following flight)에서는 지표면 높이 $h_{\text{terrain}}(\mathbf{p}_{xy})$ 에 대한 상대적 고도 제약이 적용된다:

$z(t) - h_{\text{terrain}}(\mathbf{p}_{xy}(t)) \geq h_{\text{AGL\_min}}$

여기서 $h_{\text{AGL\_min}}$ 은 최소 지상 고도(Above Ground Level)이다.

7.2 비행 금지 구역

비행 금지 구역(No-Fly Zone, NFZ)은 3차원 다면체 또는 원통형 영역으로 모델링되며, 회피 제약으로 인코딩된다:

$\mathbf{p}(t) \notin \mathcal{NFZ}_k, \quad \forall k, \; \forall t$

원통형 비행 금지 구역 $\mathcal{NFZ} = \{(x, y, z) \mid (x - c_x)^2 + (y - c_y)^2 \leq r^2, \; z_{\min} \leq z \leq z_{\max}\}$ 에 대한 회피 제약은 다음의 분리 조건으로 표현된다:

$(x(t) - c_x)^2 + (y(t) - c_y)^2 > r^2 \;\vee\; z(t) < z_{\min} \;\vee\; z(t) > z_{\max}$

8. 참고문헌

Latombe, J. C. (1991). Robot Motion Planning. Kluwer Academic Publishers.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Lozano-Pérez, T. (1983). “Spatial Planning: A Configuration Space Approach.” IEEE Transactions on Computers, C-32(2), 108–120.
Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., & Abbeel, P. (2014). “Motion Planning with Sequential Convex Optimization and Convex Collision Checking.” International Journal of Robotics Research, 33(9), 1251–1270.