다중 무인 항공기 이용 감시 및 탐색 경로 계획 생성

1. 서 론

무인 항공기(Unmanned Aerial Vehicle) 기술은 빠르게 개발이 진행중인 자율 시스템 분야로, 농업 분야^[1], 소방 분야^[2], 전력선 점검 분야^[3], 감시 및 탐색^[4] 등 분야에 활용된다. 이 중 논문에서 다루고 있는 감시 및 탐색 임무는 무인 항공기의 주된 활용 분야이다. 일반적으로, 이러한 임무는 경로를 설계하고 무인 항공기가 설계된 경로를 추종하며 진행이 된다. 경로가 설정이 되면 사용자의 판단이 항공기 비행의 매 순간 개입을 할 필요가 없으며, 알고리즘을 이용한 효율적인 경로 설계 및 무인항공기의 경로 추종 능력이 가능하게 되어 무인 항공기 임무 수행 효율이 증가된다.

다수 무인항공기 탐색 임무에서, 경로 계획은 임무 영역 사전 할당 단계와 경로 설계 단계로 구분할 수 있다.

먼저 사전 할당 단계에서는, 정찰 구역을 나누고, 지정하는 과정을 진행한다. 이 과정을 Cellular Decomposition이라고 하며, 관련된 연구로는 정확한 영역 나누기(exact cellular decomposition)^[5], 관련 지점 대표법(point of interest representation)^[6] 등이 존재한다. [5]의 경우에는, 탐색 요구 구역 안에서 영역을 수직 방향의 여러 다각형 형태로 나눈다. 장애물이 없는 경우, 나눠진 영역들이 동일한 영역을 갖을 수 있으며, 무인항공기 간의 속도 차이를 고려하지 않아, 속도 차이가 크게 나면, 각 항공기당 미션 종료 시간의 큰 차이를 보일 수 있는 한계점이 존재한다.

탐색 경로 생성 패턴의 대표적인 예로는, 나선형 패턴(spiral pattern)^[7], 지그재그(back-and-forth)^[8], 그리드 기반(grid-based)^[9] 등의 경로 패턴을 형성하는 방향으로 연구가 이루어졌다.

그 외의 연구로 3차원 공간에서 에너지 효율 최적화를 바탕으로 경로를 생성하는 연구^[10], 탐색 지역을 나누지 않고 경로 생성 및 탐색하는 방법^[11], approximate-cellular decomposition을 이용하여 경로를 생성하는 경우^[12], concave와 convex 한 영역을 동시에 고려하여 경로를 계획하는 연구^[13] 등이 있다.

대표적인 알고리즘 중, [8]의 연구에서는 탐색 영역에서 경계에 위치한 끝점들을 파악하여, 순서대로 이어가며, 지그재그의 패턴을 보이는 경로 계획이다. 이러한 방식은 non-convex 영역에서는 비 탐색 구역을 여러 차례 침범하는 문제가 발생할 수 있다. 또한 탐색 경로의 시작점이 항상 탐색 영역의 한쪽 끝 지점에서 시작되는 제한점이 있다.

[14]의 알고리즘에서는 탐색 영역을 그리드로 나누며, 나선 형태의 경로로 영역을 탐색하되, 한개의 경로로 탐색이 종료가 되지 않는다면, 탐색 되지 않은 지역으로 이동을 하며, 또 다른 나선형 경로를 그리며 탐색 진행을 반복한다. 이런 방식의 단점으로는, 1개 경로가 끝나는 지점에서 기타 비 탐색 지역의 그리드로 이동을 할 시에, 탐색이 완료된 그리드를 재방문 하는 시나라오가 발생하며, 탐색 시간이 길어지는 단점이 존재한다. 또한, 무인기가 탐색 영역 내부에서 출발하는 것을 가정하여 알고리즘이 개발되어, 탐색 영역까지 무인기가 이동시에 이동 경로가 길어질 수 있다. 이 외에도 기존에 이루어진 경로 계획에 관련된 연구는 각 비행체에 할당된 속도, 이륙 및 착륙 지점까지의 거리 등을 고려하지 않아 경로의 비효율성이 증가하는 점들이 존재한다^[15].

그리하여, 본 논문에서 개발되는 알고리즘은 탐색 지역 모양이 볼록하거나 볼록하지 않아도 적용 가능하고 무인기의 이륙 및 착륙 지점과 설정된 비행 속도를 종합적으로 고려하며 효율적 영역 분배를 하는 것이 특징이다.

제안된 알고리즘 전략을 Search Efficient-Cellular Decomposition (SE-Cellular Decomposition)이라 명명하며, 탐색 요구 구역을 다양한 형태의 다각형으로 분배를 하며, 무인기의 이착륙 지점과 지정된 비행 속도를 고려하여 나눈다. 이착륙 지점이 탐색 지역에서 가깝거나, 비행 속도가 빠르다면 더욱 넓은 영역을 분배하여, 미션 종료 시간을 줄인다. 영역들의 경계는 직선이 아닌 형태로 나타나기도 한다.

각 무인기가 정찰할 지역 정보를 받은 다음, 무인기의 이착륙지점을 고려하여 최단 거리로 통과하는 경로를 생성한다. 볼록하거나(convex) 볼록하지 않은(non-convex) 영역을 동시에 대응할 수 있도록 알고리즘이 개발되었다. 또한 최대한 짧은 시간 내에 탐색 요구 지역을 여러 대의 특성이 다른 무인항공기로 빠지는 구역과 탐색 완료 지역 재방문 없이, 완전히 탐색할 수 있게 하였다.

섹션 2에서는 세부 알고리즘, 섹션 3에서는 알고리즘을 검증하기 위한 시뮬레이션 실험 결과를 수록하였고, 결론은 섹션 4에 작성되었다.

2. 본 론

2.1 Problem Definition

총 N개의 무인 항공기를 사용하여, 임의의 다각형 형상의 단일 영역 R을 탐색하는 알고리즘을 제안한다. 제안된 알고리즘은 grid map 기반으로 영역을 빠짐없이 탐색을 하도록 설계가 되었으며, 최종적 목표는 최단시간 내에 탐색을 종료하는 것으로 한다. 또한 개발된 알고리즘의 일반화를 위하여, 무인항공기들의 순항 속도 및 이착륙 지점이 다를 수 있다는 점이 고려되었다.

알고리즘 개발에 앞서 탐색 영역 및 무인항공기에 대한 다음과 같은 가정을 이용하여 문제를 정의하고, 알고리즘을 개발하였다.

Assumption 1. 무인항공기는 직선 운동시에 서로 같거나 다른 비행 속도 v_i ∈ {v₁, v₂, ⋯, v_N}로 등속 운동하는 단순 모델로 가정하며 외부적 영향은 고려하지 않는다.

Assumption 2. 탐색 영역 R은 닫힌 경계선을 갖는 단일의 다각형 형태의 영역이다.

Assumption 3. 탐색 영역은 [Fig. 1]과 같이 임의의 원점 O를 중심으로 하는 지역 좌표계(local coordinate)의 축방향으로 나뉘는 grid map으로 표현되며, 각 grid 한 변의 크기는 ∆x로 칭하며, grid 크기 설정은 무인 항공기가 한 순간에 탐지가 가능한 범위로 설정을 한다. 탐색 시에 field of view의 overlap 은 없다고 가정을 하며, grid는 정사각형의 형태이다.

[Fig. 1]

Search area grid is shown with the grid size determination based on vehicle’s field of view size

Assumption 3를 바탕으로, 무인항공기들이 탐색 영역내의 모든 grid를 빠짐없이 방문하면 영역 탐색이 종료가 된 것으로 간주하며, 탐색 경로는 이륙지점에서 첫 탐색 gird까지의 경로와 마지막 탐색 grid에서 착륙지점까지의 경로를 포함하는 것으로 정의된다.

위의 조건하에서 정의된 다수 무인항공기의 최단 시간 탐색 경로 설계의 문제는 두가지의 문제로 분류가 된다^[5]. 하나는 다수의 탐색 에이전트에게 임무를 진행해야 하는 영역을 효율적으로 할당하기 위한 최적 할당 문제이고, 나머지 하나는 영역 내에서 효율적 경로를 수행해야 하는 순회 세일즈맨 문제(traveling salesman problem)이다. 본 논문에서는 두 가지의 문제를 풀기 위하여 SE-cellular decomposition 알고리즘과 경로의 총 길이와 총 회전수에 의거한 최단 거리 커버리지 경로 계획 알고리즘을 제안한다. 또한, 제안하는 알고리즘은 그리드를 바탕으로 영역을 나눈 뒤 경로를 설정하며, 영역을 나누는 이유는 경로들이 겹치지 않게 하기도 하며, 계산의 효율을 증대시킬 수 있다.

2.2 SE-Cellular Decomposition

탐색 경로 생성에 앞서 각 무인기에 탐색 영역을 분배하는 방법을 제안한다. 본 연구는 그리드 기반 방법으로 탐색 영역의 모양에 무관하게 적용할 수 있으며 각 무인기에 convex형태의 탐색 영역을 분배하도록 유도하고, 각 무인기의 속도와 탐색 지역까지 거리를 고려한 영역 분배를 목적으로 하였다. 제안하는 방법은 탐색 영역을 포함하는 이차원 그리드를 생성한 후 각 무인기가 탐색할 넓이를 계산하고, 탐색 영역 그리드를 계산된 넓이로 분배하는 과정을 통해 이뤄진다. [Fig. 2]에서 파란색 영역은 탐색영역, 초록색 영역은 비 탐색 영역을 의미한다.

[Fig. 2]

Grid expansion process. (a) 2D grid generation on the coverage area, (b) expansion of grid allocated to the UAV 1

각 무인기에 영역을 할당하기에 앞서 각 무인기에 할당될 넓이 크기를 배당하고 시작한다. 무인기의 탐색 경로에 겹치는 영역이 없다고 가정하였을 때 탐색지까지의 거리를 고려한 총 넓이와 각 무인기가 탐색하는데 걸리는 시간에 관해 식 (1a)과 같은 관계가 성립한다.

$\[ A_{total}+\sum _i^N{L}_i. ∆x=\sum _i^N{v}_i{t}_i \]$

(1a)

$\[ A_{i,total}=\left[A_{total}+\sum _i^N{L}_i. ∆x\right]. \frac{v_i}{\sum _i^N{v}_i} \]$

(1b)

A_total는 탐색 영역의 총 넓이; v_i는 i번째 무인기의 운행속도; t_i는 i번째 무인기의 탐색시간; N은 총 무인기 개수; ∆x는 그리드 크기; L_i는 i번째 무인기의 시작 위치와 목적지로부터 탐색지까지의 거리이다. L_i는 아직 탐색지가 할당이 되지 않았으므로 전체 탐색 영역 중 무인기의 시작위치와 목적지로부터 가장 가까운 그리드 까지의 거리를 사용하였으며, 탐색영역을 제외한 이동경로를 고려하기 위해 L_i에 그리드 크기인 ∆x을 곱해 단위를 맞추었다. 이 때 각 무인기의 탐색 시간 중 최댓값이 최종 임무 종료 시간이 되며 각 무인기의 탐색 시간이 같아졌을 때 최솟값을 가진다. 따라서 이를 위해 i번째 무인기에 할당돼야 할 넓이 A_i,total는 식 (1b)과 같이 총 넓이에 각 무인기의 속도 비를 곱한 값으로 분배된다.

그리드 할당 시 각 무인기는 탐색 영역으로 표시된 그리드 중 가장 가까운 탐색 영역 그리드를 [Fig. 2(b)]와 같이 초기 그리드로 지정한다. 각 무인기의 영역은 [Fig. 2(b)]와 같이 현재 분배된 영역의 인접 그리드들이 예비 확장영역으로 지정되며 그중 탐색 영역 내부의 그리드 만이 각 무인기의 탐색 그리드로 할당된다.

[Fig. 3]과 같이 무인기 간에 예비 확장영역이 겹치는 경우 식 (2)의 비중을 비교하여 비중이 큰 무인기의 영역으로 할당된다.

$\[ w_{i,k}=\frac{A_{i,total}}{A_{i,k}+L_{i,k}∆x}. N_i \]$

(2a)

$\[ A_{i,total}=\left[A_{total}+\sum _i^N{L}_{i,k}. ∆x\right]․\frac{v_i}{\sum _i^N{v}_i} \]$

(2b)

[Fig. 3]

Grid expansion process between each UAV. (a) decision of grid ownership, (b) Effect of considering distance to the take-off position. Kinematic diagram

w_i,k은 i번째 무인기의 k번째 반복에서의 비중 값; N_i는 해당 그리드의 인접한 그리드 중 i번째 무인기에게 할당된 그리드의 개수이며 [Fig. 3(a)]의 겹치는 확장영역인 보라색 그리드 들의 경우 위에서부터 순서대로 UAV 1과 2 둘 다 2, 3, 2가 된다. 이는 무인기에 할당된 탐색영역들이 오목하지 않도록 유도하기 위해 이렇게 설계되었다. A_i,k은 i번째 무인기의 k번째 반복에서 분배된 탐색 그리드 넓이이다. A_i,k는 그리드 개수에 단위 그리드 넓이를 곱하여 구해진다. 여기서 식 (2)가 식 (1b)과 다른 점은 L_i 대신 L_i,k를 사용하는 것이다. L_i,k는 k 번째 반복에서 i번째 무인기의 탐색 영역을 제외한 이동거리이다. L_i과 다르게 전체 탐색 영역 내의 그리드 중 가까운 그리드가 아닌 k번째 반복에 i번째 무인기에 할당된 그리드 중 가까운 그리드로부터의 거리이다. [Fig. 3(b)]에서는 탐색영역에서 목적지 까지의 거리는 생략되었다.

영역 확장 과정은 [Fig. 4]의 순서도에서 보이는 바와 같이 알고리즘이 수렴되었다고 판단될 때까지 반복하며 알고리즘의 수렴 여부는 영역 확장 과정이 반복될 때마다, 탐색 그리드들이 모두 무인기들에 할당이 되었는지에 대한 여부와 각 무인기에 분배된 넓이가 확장 과정 전과 비교하여 변화가 충분히 작은 지 판단 후 결정된다. 이는 [Fig. 4]와 같이 N개의 무인기 영역 중 k번째 반복에서 k-1번째 대비 할당된 넓이 변화가 가장 큰 값이 사용 자가 설정 한 값인 ε_A보다 작을 때 수렴했다고 가정하여 행해진다.

[Fig. 4]

Flow chart of proposed SE-cellular decomposition algorithm

2.3 Coverage Path Planning Algorithm

경로 계획은 탐색지역을 SE-cellular decomposition 단계에서 그리드 형식으로 영역 분배가 이루어진 이후 시작된다. 그리드는 탐색 영역을 행과 열로 나누어 규정하게 되며, 제안된 전략에서는 1개의 행, 혹은 열의 가장 끝에서부터 탐색을 시작하는 것을 원칙으로 한다. 이 전략에서는 지그재그 형태를 기반으로 하되, 통과 방향이 수평, 혹은 수직에 따라 패턴이 달라진다.

End Point의 예시로는 [Fig. 5]에 나와 있으며, 끝 단에 위치한 그리드를 end point라고 칭한다. 탐색 시작점을 선택할 시에는, 이륙 지점에서 가장 가까운 end point를 지정한다. 수평으로 경로를 계획할 때는 [Fig. 5(a)]와 같은 end point를 바탕으로 경로를 형성, 수직일때는 [Fig. 5(b)]와 같은 end point를 바탕으로 생성된다.

[Fig. 5]

(a) horizontal end point, (b) vertical end point, and entrance selections are shown

1개의 분배된 영역에 존재하는 모든 end point의 집합을 A라고 정의하며, a는 1개의 end point이고, a∈A이다. n은 A에서의 end point 총 개수이며, [Fig. 5(a)]에서 우측 적색 영역의 경우에는, n이 26이다.

경로를 계획할 시에는, 1개의 경로를 u라고 칭하며, m∈u, 즉 u안에 저장되는 웨이포인트를 m이라고 한다. 무인항공기가 이륙하는 지점에서 가장 가까운 a를 탐색의 시작 지점으로 하며, [Table 1]에서의 getFirstPoint 함수가 이 지점을 찾는다. [Fig. 5(a)]에서 j가 1일 때, 왼쪽 end point set에서 시작 그리드를 찾고, j가 2일 때 [Fig. 5(a)]의 오른쪽 end point set에서 계획을 시작한다. j가 3일 때 [Fig. 5(b)]의 위쪽 end point set에서 시작 그리드를 찾고, j가 4일 경우 [Fig. 5(b)]의 아래쪽 end point에서 경로가 시작된다. 시작 지점 지정 이후, 해당 포인트가 포함되어 있는 열 혹은 행에서 반대쪽 끝 end point를 다음 웨이포인트로 가져간다. 그 후, 알고리즘에서 마지막으로 업데이트 된 end point로부터 방문하지 않은 가장 가까운 end point를 다음 웨이포인트로 지정을 하고, 해당 end point가 포함된 열 또는 행의 반대쪽 end point로 이동하도록 업데이트한다. [Table 1]에서의 getGridUpdate 함수가 웨이포인트 업데이트를 한다. j가 1,2일때 수평 경로를 형성하고, j가 3,4일때 수직 경로를 형성한다. 또한, 1개의 경로에 항공기 이륙지점인 m₀ = m_st, 항공기 착륙 지점인 m_n+1 = m_fn를 포함한다. 탐색 경로를 생성할 때, 시작 지점 변경으로 경로 패턴의 차이가 발생한다. 그리드 열의 왼쪽, 혹은 오른쪽으로부터 경로를 시작할 수 있다. 또한, 경로의 형상이 수직, 수평 등 진행 방향에 따라서도 변경된다. 그리하여 가장 좋은 경로를 선택하여 시간 효율 증가를 하기 위하여, 무인기 1대당 4개의 경로 후보를 생성한다. 이 4개의 경로의 묶음을 경로 후보군으로 칭하며, U = {u_hl, u_hr, u_vl, u_vr}라고 정의되며, [Table 1]에서는 U = {u₁, u₂, u₃, u₄}로 표현되었다.

[Table 1]

Path planning algorithm structure

제안된 전략에서 최적 경로 선택 과정은 경로 후보군의 생성을 바탕으로 진행이 된다. 경로 후보군 내에서 가장 짧은 경로, 혹은 가장 적은 회전수를 갖는 경로를 선택을 한다. 경로 후보군 U에서 각각의 경로의 길이를 식 (3)를 사용하여 계산한다.

$\[ \rho \left(u_j\right)=\sum _{n=0}^{n+1}‖m_{n+1}-m_n‖ \]$

(3)

n는 좌표의 총 개수, ρ는 경로의 총 길이, u_j∈U이다. 알고리즘에서 가장 짧은 경로 길이와 두 번째로 짧은 경로 길이의 차이인 ξ를 사용자가 지정한 threshold ε와 비교하며, [Table 1]에서의 getLengthDiff로 ξ를 구한다. 만약 ε가 ξ보다 크다면, 가장 짧은 경로를 getShortestPath 함수로로 불러와 최종 경로인 u^*로 선택한다. 그렇지 않다면, 회전수가 가장 적은 경로를 getMinTurn 함수로 가져와 최종 경로로 선택한다. 알고리즘의 전반적 구조는 [Table 1]에 나와 있다.

3. 결과 및 토론

영역 분배 및 경로 설정 알고리즘은 MATLAB의 numerical simulation으로 구현이 되었다. 이 섹션에서는 3가지의 결과를 보여줄 것이다. 동일한 비행 속도 하에 SE-cellular decomposition 알고리즘에서 이착륙 지점 고려 여부가 탐색 효율에 미치는 영향, 동일한 비행 속도에 대한 경로 최적화 선택 과정의 시간적 비용에 대한 영향을 시뮬레이션 하였고, 한가지의 조건만의 변경을 통하여 알고리즘의 결과 변화를 이끌어내기 위하여 속도를 동일하게 지정하였다. 마지막으로 non-convex 형태 영역 내에서의 지상 관제 센터에서 계획된 경로와 제안한 알고리즘으로 생성된 경로를 비교하며, non-convex 지역에 대한 강건성을 증명한다.

아래 [Fig. 6]에는 총 4대의 무인기가 동일한 속도로 영역을 탐색하는 시나리오를 설정하였다. 따라서, 이착륙 위치에만 의거하여 탐색 영역이 분배되었다. [Fig. 6]에서 보이듯, UAV1이 탐색 지역에서 가장 먼 곳에서 이착륙 한다. [Fig. 6(a)]는 무인 항공기의 이착륙지점 및 속도가 SE-cellular decomposition 과정에 반영이 되어있으며, [Fig. 6(b)]에서는 반영이 되지 않았다.

[Fig. 6]

(a) Cellular decomposition process of accounting the take-off and landing positions, path generated under the area division and (b) shows the result for not accounting take-off and landing positions

탐색 임무의 종료 시점은 모든 항공기가 착륙한 시점이며, 시간적 효율은 임무 종료 시점에 달려있다. 그 결과는 [Table 2]에 보인다. 영역 분배 과정에 이착륙 지점 및 속도가 반영이 되면, 미션 진행 시간은 358.1 s이며, 반영이 되지 않은 경우는 425.3 s가 걸린다. 알고리즘이 거리를 반영하여 탐색 영역에서 가장 먼 곳에서 출발하는 UAV1에 할당되는 지역 넓이를 거리에 반비례하게 적용, 해당 무인기의 비행 시간을 줄인다. 그리하여, 이착륙지점과 속도가 SE-cellular decomposition 과정에 반영이 되면, 동일한 경로 패턴 하에 탐색 종료 시점이 앞당겨지는 것을 확인하였다. 또한, exact cellular decomposition 방법을 사용하여 임무를 완료했을 때의 소요시간도 [Table 2]에 보여지며, 새로 제안된 방식의 탐색 시간이 24.49% 가량 짧다.

[Table 2]

Mission ending time comparison

[Fig. 7(a)]는 경로 최적화 과정을 거치지 않고, 같은 패턴으로만 경로 선택을 한 결과이며, [Fig. 7(b)]는 경로 후보군 U를 바탕으로 경로 최적 선택 과정을 거친 후에 최종적으로 선택된 경로를 보여준다. 항공기들은 전부 20 m/s의 속도로 비행을 하도록 설정하였다.

[Fig. 7]

(a) Path generated without optimal-path-selection process and (b) is path result under optimal-path-selection process

경로 후보군을 바탕으로 최적 경로를 선택하였을 때, 최적화 과정을 거치지 않았을 때보다 2.62% 가량 경로 길이가 줄어들게 되며 효율이 향상하게 되었다. 각 항공기의 경로 후보에 대한 비행 시간은 [Table 3]에 나와 있다. 최적 선택 과정을 거친 경로의 비행시간이 가장 짧다는 것을 보여준다.

[Table 3]

Generated path search time comparison

[Fig. 8]에서는 non-convex한 영역을 2대의 무인 항공기가 각각 다른 속도로 탐색하는 시나리오로 설정 후의 시뮬레이션 결과를 보여준다. UAV1은 44 m/s, UAV2는 20 m/s로 탐색을 하게 되며, 영역 분배는 속도에 비례하여 UAV1이 더욱 많은 영역을 탐색하도록 설정이 된 것을 볼 수 있다. Non-convex 영역에서의 문제는, 행 혹은 열이 분할되는 시나리오가 존재하는 것이다.

[Fig. 8]

(a) Path generated inside of non-convex area from ground control station linked to a flight control computer and (b) is path design utilizing the suggested algorithm positions

[Fig. 8(a)]의 경로처럼 비행 제어 컴퓨터와 연동되는 지상 관제 컨트롤에서 경로 설정을 하면, 비 탐색 지역을 여러 번 침범하며, 비효율성이 증가한다.

Non-convex 지역에 강건하다는 것은 비효율적 요소를 최소화하는 것으로, 개발된 경로 계획 전략의 시뮬레이션 결과인 [Fig. 8(b)]에서 증명이 된다. UAV1 영역이 분할될 때, 1개의 열이 2개로 분리된 현상이 발생한다. 이 상황에서 비 탐색 지역을 1회만 진입하여 효율이 극대화되었다. 이로써, 알고리즘이 non-convex 한 영역에 대하여 강건하다는 결론을 내릴 수 있다.

4. 결 론

무인항공기를 활용하여 넓은 지역을 감시 및 탐색 임무는, 무인항공기가 활용되는 대표적인 분야이다. 본 연구는 다수의 무인항공기를 활용하여 다각형 형태의 지정된 영역을 단시간에 효율적으로 탐색을 완료하는 것이 목적인 커버리지 경로 계획 알고리즘을 개발하였다.

개발된 알고리즘은 convex와 non-convex한 영역 모두에 적용 가능하며, 임무 영역을 무인항공기에 할당한 이후, 경로를 계획한다. 영역을 할당할 때, 무인기의 이륙, 착륙 지점 및 비행 속도를 고려하게 되며, 현재의 웨이포인트에서 가장 가까운 end point를 이어 나가는 방식으로 경로 생성 알고리즘을 제안하였다. 총 경로의 길이와 회전 수에 의거하여 최적 경로를 선택한다.

영역 분할시에 이착륙 지점, 속도를 고려하게 되면 탐색 시간이 감소하게 되고 경로의 길이와 회전수에 의거하여 경로 선택 최적화 과정을 거친다. 최적화 과정을 거칠 경우, 최적화되지 않은 경로에 비하여, 비행 동선 효율이 높아지는 결과가 나왔다. 지상 관제 센터로 생성되는 경로 및 제안된 알고리즘을 활용하여 non-convex 영역에 대한 경로 계획을 비교하여, non-convex 모양의 탐색지도 효율적으로 탐색이 가능하다는 것을 확인하였다.

Acknowledgments

This project was funded by LIG NEX1 (UC190053ID, 2.200913) under Data link and Ground Control Software Standardization for Small UAVs

References

• D. Murugan, A. Garg, and D. Singh, “Development of an Adaptive Approach for Precision Agriculture Monitoring with Drone and Satellite Data,” IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 10, no. 12, pp. 5322-5328, Dec., 2017. [https://doi.org/10.1109/JSTARS.2017.2746185]
• J. J. Roldán-Gómez, E. González-Gironda, and A. Barrientos, “A Survey on Robotic Technologies for Forest Firefighting: Applying Drone Swarms to Improve Firefighters’ Efficiency and Safety,” Applied Sciences, vol. 11, no. 1, pp. 363, Jan., 2021. [https://doi.org/10.3390/app11010363]
• G. Silano, T. Baca, R. Penicka, D. Liuzza, and M. Saska, “Power Line Inspection Tasks with Multi-Arial Robot Systems via Signal Temporal Logic Specifications,” IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 4169-4176, Apr., 2021. [https://doi.org/10.1109/LRA.2021.3068114]
• D. C. Schedl, I. Kurmi, and O. Bimber, “An Autonomous Drone for Search and Rescue in Forests using Airborne Optical Sectioning,” Science Robotics, vol. 6, no. 55, Jun., 2021. [https://doi.org/10.1126/scirobotics.abg1188]
• H. Choset, E. Acar, A. A. Rizzi, and J. Luntz, “Exact Cellular Decompositions in Terms of Critical Points of Morse Functions,” IEEE International Conference on Robotics and Automation (ICRA), San Francisco, USA, 2000. [https://doi.org/10.1109/ROBOT.2000.846365]
• Y. Bouzid, Y. Bestaoui, and H. Siguerdidjane, “Quadrotor-UAV Optimal Coverage Path Planning in Cluttered Environment with a Limited Onboard Energy,” IEEE International Workshop on Intelligent Robots and Systems (IROS), Vancouver, Canada, pp. 979~984, 2017. [https://doi.org/10.1109/IROS.2017.8202264]
• F. Balampanis, I. Maza, and A. Ollero, “Spiral-like Coverage Path Planning for Multiple Heterogeneous UAS Operating in Coastal Regions,” International Conference on Unmanned Aircraft Systems (ICUAS), Miami, USA, 2017. [https://doi.org/10.1109/ICUAS.2017.7991461]
• H. Choset and P. Pignon, “Coverage Path Planning: The Boustrophedon Cellular Decomposition,” Field and Service Robotics, Springer-Verlag London Limited, 1998, pp. 203-209. [https://doi.org/10.1007/978-1-4471-1273-0_32]
• T. M. Cabreira, P. R. Ferreira, C. D. Franco, and G. C. Buttazzo, “Grid-based Coverage Path Planning with Minimum Energy over Irregular-shaped Areas with UAVs,” International Conference on Unmanned Aircraft Systems (ICUAS), Atlanta, USA, 2019. [https://doi.org/10.1109/ICUAS.2019.8797937]
• C. Wu, C. Dai, X. Gong, Y. Liu, J. Wang, X. D. Gu, and C. C. L. Wang, “Energy-efficient Coverage Path Planning for General Terrain Surfaces,” IEEE Robotics and Automation Letters, vol. 4, no. 3, pp. 2584-2591, Jul., 2019. [https://doi.org/10.1109/LRA.2019.2899920]
• C. D. Franco and G. Buttazzo, “Energy-aware Coverage Path Planning of UAVs,” IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC), Vila Real, Portugal, 2015. [https://doi.org/10.1109/ICARSC.2015.17]
• L. H. Nam, L. Huang, X. J. Li, and J. F. Xu, “An Approach for Coverage Path Planning for UAVs,” International Workshop on Advanced Motion Control (AMC), Auckland, New Zealand, 2016. [https://doi.org/10.1109/AMC.2016.7496385]
• M. Torres, D. A. Pelta, J. L. Verdegay, and J. C. Torres, “Coverage Path Planning with Unmanned Aerial Vehicles for 3D Terrain Construction,” Expert Systems with Applications, vol. 55, no. 15, pp. 441-451, Aug., 2016. [https://doi.org/10.1016/j.eswa.2016.02.007]
• E. Gonzalez, O. Alvarez, Y. Diaz, C. Parra, and C. Bustacara, “BSA: A Complete Coverage Algorithm,” IEEE International Conference on Robotics and Automation (ICRA), Barcelona, Spain, 2005. [https://doi.org/10.1109/ROBOT.2005.1570413]
• Y. Hong, S. Jung, S. Kim, and J. Cha, “Autonomous Mission of Multi-UAV for Optimal Area Coverage,” Sensors, vol. 21, no. 7, Apr., 2021. [https://doi.org/10.3390/s21072482]