2.1 알고리즘 개요

최적 경로 생성 알고리즘은 Extend Spline-RRT* 알고리즘을 참고하여 작성되었다^[12]. 그림 1은 알고리즘의 flow chart를 도시한다. Flow chart에서 트리의 node가 아닌 점은 $P$, 트리의 node인 점은 $x$로 나타내었다. $P$는 단순히 점의 위치만을 포함하고 있으며, $x$는 점의 위치, 방향, cost 및 parent 정보를 포함하고 있다. 우선 알고리즘 수행 전 주어진 point cloud 데이터는 Map Clustering 과정에서 사용자 지정 단위(cluster resolution)로 조직화한다. 이 과정에서 장애물이 각 Cluster 점유 여부를 판단하여 Cluster의 요소로 저장한다. 즉, 한 Cluster는 Cluster의 위치, 점유 여부의 2가지 데이터를 가지고 있다. 알고리즘 중 Loop는 사용자가 지정하는 횟수만큼 반복한다. 주요 하위 함수에는 Feasibility Check와 Cost 산출이 있다. Feasibility Check 함수는 spline을 생성하고 생성된 spline이 Map 안에 존재하는지(Edge 충돌 확인), 기체의 선회 반경 동적 한계 내에 존재하는 경로인지, 그리고 장애물과 충돌하지 않는지 판단한다. Cost 산출 함수는 한 spline을 선택하였을 때 소개할 원리에 따라 해당 경로가 소모하는 비용을 산출한다. 알고리즘 과정 중 Re-wiring 과정을 포함하여 비용 감소가 가능한 경로를 효과적으로 탐색할 수 있다.

2.2 선회 반경 제한

멀티콥터는 고정익에 비해 동역학 특성에 따른 기동의 자유도가 높은 특징이 있으나, 선회 반경에 대한 동적 한계를 판단할 필요가 있다. 선회 반경 동적 한계 판단은 Feasibility Check 함수에서 이루어진다. 멀티콥터의 선회 반경 제한을 설정하기 위해 MATLAB Simulink로 작성된 멀티콥터의 3차원 동역학식이 반영되어 있는 시뮬레이터를 이용하였다^[13]. 시뮬레이션 상에서 위의 그림 2와 같은 선회 경로를 지정하여 시뮬레이션을 수행하였다. 경로는 Dm 북쪽으로 이동한 후 R[m]의 반경을 가진 원 궤도를 돌아 다시 동쪽으로 D[m] 이동하는 경로이다. 제어기 및 유도기 성능을 최대한 배제하고 기체의 기동 한계를 시험하기 위해 간단한 경로를 지정하였다. 시뮬레이션의 대상 멀티콥터는 680급 헥사콥터이다. 680급 헥사콥터는 모터 축간 거리가 680mm인 헥사콥터로 정의되며, 위 그림 3의 헥사콥터 예시 그림에서 $l=680mm$인 헥사콥터이다. 비행속도는 실내 운용을 고려하여 수 m/s의 수준의 속도로 설정하였다.

2.2.1 시뮬레이션1(R=0.01m 회전반경 케이스)

경로 중 선회 반경인 R이 0.01m로 매우 작은 경우의 시뮬레이션 결과이다. 그림 4와 그림 5는 각각 위치와 자세 결과를 도시한다. 경로에 대해서는 북쪽 방향으로 약 83cm의 오버슈트가 있다. 제어기 등의 성능을 고려하였을 때 큰 오차는 아니지만, 실내 비행을 염두에 두었을 때에는 허용 범위를 넘어선 오차라고 볼 수 있다. 자세의 경우 roll, pitch 모두 최대 28deg로, 시뮬레이션과 같은 크기의 멀티콥터를 사용한 ^[14]의 실험 결과와 비교하였을 때 멀티콥터에 무리하지 않은 기동인 것으로 판단된다.

2.2.2 시뮬레이션2 (R=1m 회전반경 케이스)

경로 중 선회 반경인 R을 1m로 증가시켰을 때의 결과이다. 그림 6과 그림 7은 각각 위치와 자세 결과를 도시한다. 경로에 대해서는 북쪽 방향으로 38cm의 오버슈트가 있다. 기존 시뮬레이션 1의 결과보다 많이 줄어든 것을 확인할 수 있고, 기체의 크기, 제어기 및 유도기의 추종 성능 그리고 실내 비행임을 고려하였을 때에도 허용 범위 내의 결과이다. 자세는 roll, pitch 모두 최대 22deg로 시뮬레이션1의 결과보다 감소하였지만 큰 차이를 보이지 않는다. 전반적으로 낮은 속도인 2m/s에서의 기동은 기체에 큰 무리가 되지 않는 것으로 판단된다. 시뮬레이션 결과를 종합하여 Feasibility Check 중 선회 반경 제한은 1m로 설정하였다.

2.3 충돌 판단

경로가 장애물과 충돌하는 것을 피하기 위해 Feasibility check 함수에는 충돌 판단이 포함되어 있다. 충돌 판단 알고리즘은 Map cluster의 점유 여부로 판단한다. 경로는 3차원 spline이 여러 개 연속적으로 이어진 형태이다. 한 spline은 20개의 직선(21개의 점)으로 이루어져 있고, 그림 8은 이 spline의 예시를 도시한다. 기체의 중심이 이 경로점들을 지나간다. 기체의 중심이 $<i,\: j,\: k>$ Cluster에 존재한다고 하면, $<i-1:i+1,\: j-1:j+1,\: k-1:k+1>$의 Cluster에 대하여 점유 여부를 판단한다. 그림 9는 점유 여부를 판단하는 cluster의 예시를 도시한다. 빨간색 큐브가 $<i,\: j,\: k>$ Cluster로 기체의 중심이 속해 있는 Cluster이고, 이를 포함한 총 27개의 큐브에 대해 점유 여부를 판단한다. 선회 반경이 1m일 때 38cm의 오버슈트가 있는 시뮬레이션 결과를 고려하여 Cluster Resolution은 0.8m로 설정하였다. 이때 기체와 장애물이 가장 가까운 경우, 기체와 장애물 사이에 46cm(>38cm)의 여유가 있게 된다.

2.4 Cost 산출

^[14]의 제어기에서 목표 위치/속도가 실제 위치/속도와 일치하는 이상적인 제어 상태이고, 모터에 시간 지연이 없다고 가정하면 멀티콥터가 발생시키는 힘은 아래 식 (1)과 같다.

$\overrightarrow{F}$는 멀티콥터가 발생시키는 힘, $C_{drag}$는 각 성분이 각각 x, y, z 방향으로의 공기 저항 계수이다. 그리고 $\overrightarrow{V}$는 멀티콥터의 속도이고, 방향은 각 점에서 spline에 접한다. 에너지는 힘과 거리의 곱으로 나타내어지므로 한 경로가 정해졌을 때 임무 거리와 에너지 소모를 고려한 Cost는 식 (4)와 같다.

$W_{1}$, $W_{2}$는 거리 및 에너지에 대한 가중치를 나타낸다. $W_{1}$이 더 크다면 이동 거리에 Cost의 가중치가 더해진 것이고, $W_{2}$가 더 크다면 에너지 소모에 가중치를 더한 것이다. $s_{i}$는 그림 8의 $s_{1\sim 20}$이고, $\overrightarrow{F}_{i}$ 및 $E_{i}$는 각각 $s_{i}$를 지날 때의 힘과 에너지 소모이다. 멀티콥터의 속력 변화는 없다고 가정하였다. $W_{2}$를 더 크게 지정할수록 에너지 소모를 절감하는 경향의 경로를 생성할 것이다.

3.1 시뮬레이션 결과

장애물이 존재하는 복잡한 환경에서 path planning 알고리즘이 유효한지 확인하기 위해 그림 10에서 도시하고 있는 가상의 map을 활용하여 path planning 알고리즘을 수행하였다. Map의 크기는 80×100×20m이고, Map 내에 6개의 장애물이 존재한다. 높이가 높은 2개의 파란 장애물은 20m이고, 다른 높이가 낮은 4개의 장애물은 10m이다. 시작점은 $<5,\:5,\:3>$이고, 도착점은 $<75,\:95,\:3>$이다. 시뮬레이션에서 Cost 산출 함수에서 계수는 각각 $C_{drag}=\begin{bmatrix}0.2&0.2&0.3\end{bmatrix}$, $\|\overrightarrow{V}\|=2$로 설정하였다.

그림 11은 가상의 Map에서 알고리즘을 수행한 결과 예시를 도시한다. 알고리즘 loop를 3000번 수행한 결과이고, Cost 가중치는 $W_{1}= 0.5$, $W_{2}= 0.5$로 균등하게 배분한 경우이다. 왼쪽 그림은 3000번의 알고리즘 수행 중 생성한 트리 전체를 도시한다. 녹색 spline들은 알고리즘 과정 중 Re-wiring 과정을 거치기 전 생성된 트리이고, 노란색 spline들은 기존 트리보다 cost를 더 작게 만드는 Re-wiring과정 중에 새로이 생성된 트리이다. 그리고 빨간색이 최종적으로 선택된 경로이다. 오른쪽 그림에서는 이 최종 선택된 경로만을 도시한다. 알고리즘 수행 결과 중간 10m 높이의 장애물을 모두 위로 넘어가는 경로가 생성되었다. 아래의 표 1은 위와 같은 방법으로 iteration 및 cost 가중치를 다르게 설정했을 때의 cost value 등을 표로 정리한 결과이다.

Case1이 그림 11에서 도시한 예시이다. Cost에 에너지 소모만 요소로 사용하는 Case 2, 3, 4를 서로 비교하면, Case2에서 고도 변화를 최소화하려는 경향이 있으나 결국 10m 장애물을 넘어 가는 경로가 생성된다. Case3은 강제로 10m 고도 제한을 준 경우이다. 장애물 사이를 지나가는 경로가 생성되었으나 Case2보다 cost가 더 작게 산출되었다. 이는 같은 알고리즘 수행 횟수 동안 더 좁은 영역에서 효과적으로 알고리즘을 수행하였기 때문인 것으로 분석된다. Case4에서 고도 제한을 주지 않고 알고리즘 수행 횟수를 더 크게 하였다. 10m 장애물들을 넘어가는 경로를 선택하며, 고도 제한을 준 Case3보다 더 작은 cost를 가진다. 따라서 고도 제한과 같이 사전에 제한 조건이 있다면 제한 조건을 미리 고려하는 것이 알고리즘의 효율을 높이는 방안이고, 같은 제한 조건이라면 알고리즘 수행 횟수를 높여 cost가 더 작은 경로를 선택할 수 있다.

3.2 실제 점유격자지도를 이용한 결과

실제 Map에서 path planning 성능을 검증하기 위해 그림 13과 같이 실험 환경을 구축하여 실험하였다. 실험 공안 내에 약 2.85m의 장애물 6개를 놓고 지도를 생성하였다. 생성된 지도는 그림 12에 도시하였으며, 6개의 장애물은 주황색 박스로 표시하였다.

시작점은 <-15, -1, 1>이고, 도착점은 <15, 15, 1>이다. 알고리즘의 효율을 위해 map 크기를 제한하였다. 시작점과 도착점을 고려하여 x=[-20, 20], y=[-10, 20], z=[-1, 5]로 제한하였다. 그리고 장애물의 높이를 고려하여 알고리즘을 수행하는 동안 고도를 2.8m로 제한하였다. 크기를 제한한 map은 크기가 크지 않기 때문에 알고리즘 수행 횟수를 1000번으로 하였고, cost의 가중치는 $W_{1}=0.5$, $W_{2}=0.5$로 배분하였다. 그림 14는 실제 실험 환경에서의 경로 생성 결과를 도시한다. 주어진 장애물을 피해 경로가 생성되는 것을 확인할 수 있다. 실제 실험 환경에서 에너지 소모 절감 효과를 확인하기 위해 반복적인 경로 계획 알고리즘을 수행하였다. $W_{1}= 1$, $W_{2}= 0$에서부터 두 가중치의 합이 1을 만족하도록 0.2 단위로 $W_{1}= 0$, $W_{2}= 1$까지 바꾸어 가며 알고리즘을 수행하였다. 각 가중치에 대한 생성 경로의 분포특성을 고려하여 평균적 비용함수를 비교 대상으로 이용하였다. 즉, 수행 횟수 1000번으로 구성된 알고리즘을 각 가중치 케이스 당 100회씩 수행하여 나온 결과를 정량적 분석에 적용하였다. 아래 그림 15에는 에너지 가중치 $W_{2}$에 따른 거리 및 에너지 비용의 100회 결과를 모두 도시하였다.

그림 16은 그림 15의 분석을 위해 $W_{2}$에 대한 에너지 소모를 0.2 단위 히스토그램을 그린 결과이다. 히스토그램에서 확인할 수 있듯이 알고리즘의 무작위성에 의한 결과로 여러 값에 데이터가 분포하는데, 이 중 유효성 있는 데이터를 추출하여 분석할 필요가 있다. 추출한 데이터 유효군은 가장 많이 카운트 된 값의 데이터(최빈값), 두번째 그리고 세번째로 많이 카운트 된 값들을 선정하였다. 표 2는 가중치 별 선정된 유효군들의 기댓값을 비교한 결과이고 그림 17은 이를 그래프로 도시한 결과이다.

표 2 및 그림 17의 그래프를 보면 에너지 가중치가 증가함에 따라 에너지 소모는 줄어드는 반면 이동 거리는 커지는 것을 확인할 수 있다. 따라서 이동 거리를 최소로 하는 경우와 에너지를 최소로 하는 경우는 서로 다른 경로를 선택한다는 것을 확인할 수 있고, 이때 경로의 이동 거리가 최소인 경로가 반드시 에너지를 최소화하지는 않는다는 것을 알 수 있다. 그리고 가중치 $W_{2}= 0.8$ 부근으로 정하는 것이 에너지 소모와 이동 거리를 모두 고려했을 때 전체 비용을 최소화하는 선택이 된다는 점을 시사한다.