1. 연구 대상 설정

드론은 법률적으로 항공안전법 제2조제3호에 따라 ‘초경량비행장치’에 해당되나, 일상에의 드론이라고 함은 무인항공기 (unmanned aerial vehicle, UAV)를 의미한다고 할 수 있다 (Cavoukian, 2012; Floreano and Wood, 2015). 무인항공기는 비행체의 형태에 따라 고정익 (fixed wing), 회전익 (rotary wing), 가변로터 (tilt rotor), 동축반전 (co axial) 및 멀티콥터 (multi copter) 등으로 구분된다. 그러나 농업 분야에서는 멀티콥터가 가장 많이 사용되고 있는데, 이는 멀티콥터가 수직 이착륙, 호버링 (hovering), 저속비행 및 정밀 제어가 가능하고, 장애물이 많은 환경에서의 기동성, 페이로드 (payload) 및 안전성과 신뢰성 등의 장점을 가지기 때문이다. 특히 멀티콥터는 경지면적이 작고, 산악지역이 많은 지역에 적합하다는 특징과 방제 임무에 소요되는 인력과 시간을 획기적으로 단축할 수 있으며 (Qing et al., 2017), 작업자가 경작지 안으로 들어가지 않고 공중으로 접근하여 방제하기 때문에 농약 노출과 작물 훼손을 최소화할 수 있다는 장점 (Choi et al., 2018)이 있다. 또한 멀티콥터는 무인헬기보다 운용 비용이 적게 소요되며, 대규모 경작지에서도 적용할 수 있는 장점이 있어, 농업용 멀티콥터는 급속도로 보급되고 있는 상황이다 (Noh et al., 2020). 이에 본 연구에서도 농업 현장에서 가장 많이 사용하는 멀티콥터를 연구대상은 설정하고 멀티콥터에 최적경로를 산정할 수 있는 4개의 알고리즘을 적용하였다.

2. 최적경로 알고리즘 설계

최적경로 알고리즘은 문제 유형 (problem type), 환경 특성 (environment), 알고리즘 접근 방법 (optimality) 및 탐색 전략 (Search strategy) 등의 기준으로 분류할 수 있다. 이와 관련된 최적경로 알고리즘으로 Dijkstra, A^*(A-star), D^*Lite 및 Christofides 알고리즘을 제시할 수 있는데, 이들은 최적경로 문제 해결을 위한 전통적인 알고리즘으로 알려져 있다. 이들을 각 기준으로 분류하면, 문제 유형 기준에서 단일 출발점 최단 경로 문제 (single-source shortest path)로 분류되는 알고리즘은 Dijkstra, A^* 및 D^*Lite 알고리즘이, 외판원 문제 (traveling salesman problem, TSP)로는 Christofides 알고리즘이 포함된다. 환경 특성 기준에서 정적 (static) 환경으로 분류되는 알고리즘은 Dijkstra, A^* 및 Christofides 알고리즘이 포함되며, 동적 (dynamic) 환경에는 D^*Lite 알고리즘이 속한다. 알고리즘 접근 방법 기준으로 정확 해법 (exact algorithms)으로 분류되는 알고리즘은 Dijkstra, A^* 및 D^*Lite 알고리즘이 포함되며, 근사해법 (approximation algorithms)으로 분류되는 알고리즘에는 Christofides 알고리즘이 포함된다. 탐색 전략 기준으로는 그래프 탐색 기반 (Graph Search) 및 조합 최적화 기반 (Combinatorial Optimization)으로 구분되는데, 이는 Dijkstra, A^* 및 D^*Lite 알고리즘과 Christofides 알고리즘이 각각 포함된다 (Table 1).

본 연구에서는 최적경로를 도출하기 위한 알고리즘으로 앞서 언급한 Dijkstra, A^*(A-star), D^*Lite 및 Christofides 알고리즘을 채택하였으며, 각각의 알고리즘을 설계한 방법은 다음과 같이 나타냈다.

가. Dijkstra 알고리즘

Dijkstra 알고리즘 (Dijkstra, 1959)은 가중치가 있는 그래프에서 한 노드로부터 모든 다음 노드까지의 최단 경로 (one-to-all)를 찾는 방법론으로 설명할 수 있으며, 이러한 경우에서 최적경로 탐색에 가장 효율적인 알고리즘으로 알려져 있다 (Choi and Jang, 1998). 이 알고리즘을 이해하기 위해서는 먼저 핵심 개념을 정의해야 한다.

⦁D(v): 현재 반복 단계에서 출발 노드로부터 목적지 노드 v까지의 최소 비용 경로

⦁p(v): 출발점에서 v로 가는 현재 최소 비용 경로상에서 v의 이전 노드 (v의 인접 노드)

⦁N’: 출발점으로부터의 최소 비용 경로가 확정적으로 결정된 노드들의 부분집합

본 연구에서 수행한 Dijkstra 알고리즘의 수행과정을 의사코드 (pseudo code)로 표현하면 Fig. 1과 같이 나타낼 수 있다.

Fig. 1

Dijkstra algorithm pseudo code in this study

본 과업에서의 Dijkstra 알고리즘 수행과정은 크게 3단계로 구분할 수 있는데, 먼저 1단계에서는 초기화 작업으로, Fig. 1의 1~9행과 같이 확정된 노드 집합 N’를 시작 노드 u로 설정하고 (N’ = {u}), 모든 노드 v에 대하여 v가 u의 인접 노드인 경우는 D(v) = c (u, v)로(직접 연결 비용), v가 u의 인접 노드가 아닌 경우에는 D(v) = ∞로 설정하도록 하였다. 2단계에서는 10~18행과 같이 반복 수행 단계로 최소 비용 노드 선택 (D(w) 값이 최소인 노드 w), 노드 집합 업데이트 (선택된 노드 w를 N’에 추가) 및 거릿값 갱신 (D(v) = min(D(v), D(w) + c(w, v))로 업데이트)를 반복 수행하도록 계획하였다. 3단계는 종료 단계로 14~17행과 같이 모든 노드가 N’에 포함되면 (N’ = N) 알고리즘이 완료되며, 각 노드까지의 최단 거리가 확정되도록 하였다. 이러한 과정을 통해 Dijkstra 알고리즘은 시작점에서 모든 다른 노드까지의 최단 경로를 체계적으로 찾아내는 기능을 가지게 된다.

나. A* 알고리즘

A^* 알고리즘은 가장 일반적으로 사용되는 그래프 탐색 기반 경로 계획 알고리즘으로, Hart et al. (1968)이 Dijkstra 알고리즘을 확장한 형태로 제안하였다. A^* 알고리즘은 휴리스틱 (heuristic) 값을 포함하여 Dijkstra 알고리즘과 비교하여 더 나은 계산 시간 성능을 제공한다는 장점이 있다 (Koubâa et al.,, 2018). A^* 알고리즘에서 출발 노드 (node)에서 목표 노드까지의 최단 경로를 찾는 과정은 상수 f값에 의존한다. f값은 시작 노드에서 현재 노드까지 이동하는 비용 (f_value)으로, f_value = g_value + g_f× h_value 와 같이 평가한다.

여기서, g_value는 시작 노드에서 현재 노드까지의 총 이동 비용을, g_f는 동점 상황에서 알고리즘 성능을 향상시키기 위해 휴리스틱 값에 곱해지는 상수를, h_value는 현재 노드에서 목표 노드까지의 추정 이동 비용을 나타낸다. 본 연구에서 수행한 A^* 알고리즘의 의사코드는 Fig. 2와 같이 나타냈다.

Fig. 2

A^*(A-star) algorithm pseudo code in this study

Fig. 2의 1~3행은 초기화 단계로, 먼저 맵 크기, 장애물 좌표, 시작 노드 (P_start)와 목표 노드 (P_target)의 좌표, 그리고 이득 인수 ()를 포함한 매개변수들을 초기화하도록 하였다. 시작 노드를 첫 번째 항목으로 하여 OpenList를 생성하고, 비어있는 ClosedList를 생성하도록 한다. 3~18행은 메인 탐색 루프로, OpenList가 비어있지 않고 목표에 도달하지 않은 동안 다음 과정을 반복하도록 설계하였다. OpenList에서 가장 낮은 f값을 가진 노드를 찾아 현재 노드 (P_current)로 설정하도록 하였으며, 5~6행은 목표 도달을 확인하는 부분으로 현재 노드가 목표 노드와 같다면 경로를 찾은 것이므로 탐색을 중단하도록 하였다. 7행은 현재 노드를 처리하는 부분으로 현재 OpenList에서 노드를 제거하고 ClosedList에 추가하고, 8~18행은 인접 노드 탐색 및 처리를 수행하는 영역으로 현재 노드의 모든 인접 노드 (P_adj)에 대해 다음을 수행하도록 하였다. 먼저 해당 인접 노드가 맵상에 존재하는지 확인하고, 이후 현재 노드에서 인접 노드까지의 g 값과 인접 노드에서 목표까지의 거리를 합한 인접 노드 비용을 계산하도록 하였다. 11~13행은 OpenList 내 노드를 처리하는 부분으로 인접 노드가 이미 OpenList에 있고 새로 계산된 인접 노드 비용이 기존 g 값보다 작다면, 해당 노드를 OpenList에서 제거하도록 하였다. 14~16행은 ClosedList 내 노드를 처리하는 영역으로, 인접 노드가 ClosedList에 있고 새로 계산된 인접 노드 비용이 기존 g 값보다 작다면, 해당 노드를 ClosedList에서 OpenList로 이동시키도록 하였다. 17~18행은 새 노드를 추가하도록 하고, 인접 노드가 두 리스트 모두에 없다면, 해당 노드를 OpenList에 추가하도록 하였다. 이러한 과정을 통해 A^* 알고리즘은 시작점에서 목표점까지의 최적경로를 체계적으로 탐색하여 결과를 도출하도록 설계하였다.

여기서, OpenList는 경로 탐색 과정에서 앞으로 방문해야 할 노드들의 목록을 의미하며, 아직 탐색되지 않았지만 후보가 되는 노드들도 여기에 포함된다. ClosedList는 이미 방문하여 처리가 완료된 노드들의 목록을 의미하는데, 한번 ClosedList에 추가된 노드는 일반적으로 다시 고려되지 않도록 설정하였다. P_target은 경로 탐색의 최종 도착지가 되는 노드로, (x_t, y_t)의 2차원 좌표로 표현되고, P_source는 경로 탐색이 시작되는 지점의 노드로, (x_s, y_s)의 2차원 좌표로 나타내다. P_current는 OpenList에 있는 노드들 중에서 가장 낮은 f 값을 가진 노드를 의미하며, 현재 처리 중인 노드의 좌표를 나타낸다. P_adj는 현재 노드와 직접적으로 연결되어 있는 주변 노드들의 좌표를 보여준다.

다. D*Lite 알고리즘

D^*Lite (Koenig and Likhachev, 2005) 알고리즘은 그리드 맵 (grid map) 기반의 동적 환경에서 효율적인 경로 재계획을 위해 설계된 증분 탐색 알고리즘이다. D^*Lite 알고리즘은 도착점 (target)으로부터 그리드 셀 (grid cell)을 하나씩 확장 (cell expansion: target으로부터 grid까지의 경로 비용 계산)하여 출발점 (start)까지 경로를 산출하면 경로 탐색을 종료하도록 설계한다 (Koenig et al., 2004). 이때 cell 간의 확장 순서는 target으로부터 cell까지의 현재의 경로 비용과 함께 start까지 남은 경로 비용의 어림값 (Hart et al., 1968)에 대한 통합 비용이 적은 순으로 정하며, D^*Lite 알고리즘은 동적 변화 환경에서 경로 계획 및 경로의 재계획을 효율적으로 탐색하여 start와 target 간의 최적경로를 생성한다. 이러한 과정을 통해 D^*Lite 알고리즘은 환경이 변화했을 때 전체 경로를 다시 계산하지 않고, 영향받는 노드들만 효율적으로 업데이트하여 새로운 최적경로를 신속하게 찾을 수 있는데, 이는 D^*Lite 알고리즘의 가장 큰 장점으로 평가된다. 이에, 본 연구에서 수행한 D^*Lite 알고리즘의 의사코드는 Fig. 3과 같이 나타냈다.

Fig. 3

D^*Lite algorithm pseudo code in this study

Fig. 3의 1~10행은 시작점과 목표점을 그리드 좌표로 변환하고, 목표 노드의 rhs 값을 0으로 설정하여, 다른 모든 노드의 g값을 무한대로 초기화하도록 하였다. 5~7행은 CalculateKey 함수로, 각 노드의 우선순위를 결정하는 핵심 함수로 설계하였는데, 여기서 탐색 효율성을 높이고 일관성을 유지하기 위해 g값과 rhs 값 중 작은 값에 휴리스틱 거리와 km 거리를 더한 쌍을 반환하도록 설계하였다. 9~20행은 UpdateVertex 함수로, 노드의 rhs 값을 인접 노드들의 최소 비용으로 재계산하도록 하였는데, 이때 불필요한 계산을 방지하여 알고리즘의 효율성을 향상시키기 위해 g값과 rhs 값이 일치하지 않을 때만 해당 노드를 OpenList에 유지하도록 하였다. 21~37행의 ComputeShortestPath 함수는 시작 노드의 key 값이 OpenList의 최상위 key보다 크거나 시작 노드의 g 값과 rhs 값이 일치하지 않는 동안에만 반복 수행하도록 설계하였다. 40~48행은 시작점에서 목표점까지 각 단계에서 가장 낮은 비용을 가진 인접 노드를 선택하여 경로를 생성하도록 하였다.

라. Christofides 알고리즘

Chrisofides 알고리즘 (Christofides, 1976)은 앞서 언급한 바와 같이, 문제 해결 방법 중 TSP에 대한 동적 환경 기반의 1.5 근사해법으로, 이론적으로 보장된 성능비를 가진 가장 우수한 TSP 근사 알고리즘 중 하나이다 (An et al., 2015). Christofides 알고리즘을 간단히 설명하면 외판원이 모든 도시를 한 번씩 방문하고 돌아오는 최단 경로를 찾는 문제를 해결하는 방법으로 설명할 수 있다. Christofides 알고리즘은 먼저 모든 도시를 최소 비용으로 연결하는 최소신장트리 (minimum spanning tree, MST)를 만든 다음, 홀수 개의 연결선을 가진 도시들을 짝지어 추가로 연결하여 모든 도시의 연결선 개수를 짝수로 만든다. 이렇게 만든 그래프에서 모든 연결선을 지나는 순회 경로를 찾은 후, 중복으로 방문하는 도시들을 건너뛰어 각 도시를 정확히 한 번씩만 방문하는 최종 경로를 완성하는 방법을 제시하는 구조를 가진다. 이러한 방법론을 이용하여 본 연구에서 수행한 Christofides 알고리즘의 의사코드는 Fig. 4와 같다.

Fig. 4

Christofides algorithm pseudo code in this study

Fig. 4의 1~5행은 거리 행렬 구성 및 MST를 생성하는 단계로, 먼저 모든 웨이포인트 간의 거리 행렬을 구성하고, Prim 알고리즘 (Jarník, 1930)을 사용하여 MST를 생성하도록 설계하였다. 참고로 이 단계에서는 모든 노드들이 최소 비용으로 연결하는 트리 구조가 된다. 6~12행은 홀수 차수 노드 (odd-degree nodes)를 처리하는 과정으로 MST에서 각 노드의 차수를 계산하여 홀수 차수를 가진 노드들을 식별하도록 한다. 오일러 경로 (Eulerian path)가 존재하려면 모든 노드의 차수가 짝수 (even)여야 하므로, 이들 홀수 차수 노드들에 대해 최소가중완벽매칭 (minimum weight perfect matching)법을 수행하여 추가적인 엣지 (edge)들을 연결하도록 구성하였다. 13~24행은 오일러 경로 생성 및 변환을 수행하는 단계로, MST와 매칭 엣지들을 결합하여 모든 노드의 차수가 짝수인 오일러 그래프를 생성하도록 하였다. Hierholzer 알고리즘 (Hierholzer and Wiener, 1873)을 통해 오일러 경로를 찾은 후, 중복 방문된 노드들을 제거하여 해밀턴 경로 (Hamiltonian path)로 변환하고, 필요에 따라 시작점으로 돌아가는 경로를 추가하였다. 25~29행은 실제 경로를 생성하는 영역을 마지막으로 해밀턴 경로의 각 노드 간 연결을 실제 이동 가능한 경로로 변환하여 완전한 순회 경로를 생성하도록 하였다.

3. 최적경로 알고리즘 실험환경 및 성능평가 방법

본 연구에서 각 알고리즘의 성능을 평가하기 위해, 장애물이 없는 120 m × 60 m인 가상의 노지 공간 (2차 평면)에서 드론이 비행하는 것으로 계획하였다. 또한 이 드론의 임무는 기준점 (0 m, 0 m)에서 출발하여 임의로 제시된 모든 병충해 발생 지점 (target)을 방문하고 다시 기준점으로 복귀하는 것으로 설정하였다. 여기서 장애물이 없는 조건으로 실험공간을 설정한 이유는 각 알고리즘의 최적경로 도출에 있어서 가장 기본적 수행 능력을 평가함에 있다.

이를 위해 본 연구에서는 Fig. 5와 같이 Streamlit (Snowflake Inc., 2025)을 기반한 시뮬레이터를 구축하였으며, 각 알고리즘과 지점수를 변경하면서 알고리즘 평가를 수행하였다. 여기서 시뮬레이터는 Fig. 5의 (a)~(f)와 같이 크게 6개 영역으로 구분하였다. Fig. 5(a)는 시뮬레이션의 조건을 설정하는 영역으로 시뮬레이션의 시작, 중지 및 리셋 기능과 방문 지점 수 및 위치 (군집형 및 분산형)를 발생할 수 있는 기능 등을 포함하고 있다. Fig. 5(b)는 알고리즘을 선택할 수 있는 기능을, Fig. 5(c)는 알고리즘의 계산 현황을 모니터링 할 수 있는 영역으로 구현하였다. Fig. 5(d)는 드론이 각 알고리즘에 의해 도출된 경로를 비행하면서 손실되는 에너지를 모니터링 할 수 있는 영역이며, Fig. 5(e)는 각 알고리즘의 성능평가를 위한 항목이 표현되는 영역으로 구성하였다. 끝으로 Fig. 5(f)는 무작위로 발생된 타겟과 알고리즘별로 도출된 최적경로로 드론이 이동하는 것을 모니터링 할 수 있도록 하였다.

Fig. 5

Optimal path simulator of this study using Streamlit; (a) simulation condition configuration, (b) algorithm selection, (c) algorithms calculation status, (d) algorithm efficiency graph, (e) metrics of algorithm, (f) optimal path result area

최적경로의 성능평가 실험은 각 알고리즘의 성능을 단계적으로 평가하기 위해 전체 24개의 시나리오로 구성하였다. 단계적 실험의 구성은 방문 지점 수 (number of target)는 50개부터 150개까지 50개 단위로 증가시키되, 각 지점의 위치 (distribution pattern)는 분산 (scattered)형 및 군집형 (clustered)으로 무작위로 발생하도록 하였다 (Table 1). 단, 군집형에서 군집의 개수는 4개~5개로 군집될 수 있도록 설계하였으며, 가상공간의 환경조건 (environment)은 장애물이 없는 개방형 (open)으로 설정하였다. 또한 드론의 종류에 따라 실험 결과가 각기 상이하게 나타날 수 있기 때문에 드론의 제원을 고려하지 않았다.

각 알고리즘을 평가하는 지표는 드론의 에너지 소비율 (energy consumption ratio), 총 이동거리 (distance), 시뮬레이션 실행 (simulation time) 및 알고리즘에 의한 최적경로 생성 시간 (path calculation time) 등으로 4개 항목으로 설정하였으며, 방법은 다음과 같다.

먼저, 에너지 소비율은 식 (1)과 같이 속도와 시간 간격을 기반으로 산정하도록 설정하였다. 식 (1)의 , 및 는 각각 에너지 소비율 (%), 시간당 () 에너지 소비량 및 드론의 최대 베터리 용량을 나타낸다. 또한 , , 및 는 각각 기본 전력 소비 (호버링 전력), 추진에 필요한 전력, 고도 변화에 필요한 전력 및 가속/감속에 필요한 전력을 의미한다. 드론의 제원에 따라 각각 결과가 달라 질 수 있기 때문에 본 연구에서는 시뮬레이션 실행 시 는 100으로, , , 및 는 각각 0.1, 1, 0 및 1로 간단히 설정하였다. 이와 함께, 및 는 시간 변화 및 에너지 효율 계수를 나타내는데, 본 연구에서는 이를 각각, 0.1 및 1로 설정하였다.

평가 지표 중 가장 핵심이라고 할 수 있는 총 이동거리는 시간 간격에 따른 웨이포인트 (드론의 이동 궤적)의 좌표를 중심으로 식 (2)와 같이 유클리드 거리로 계산하도록 설정하였다. 식 (2)에서 은 총 이동거리를, 는 시간 간격에 따른 이동거리를 의미한다. 또한, 와 는 시간 간격마다 드론의 위치 (좌표 또는 순서쌍)를 나타낸다.

나머지 평가 지표로 시뮬레이션 실행 시간 ()은 시뮬레이션 시작부터 종료까지의 시간 누적으로 산정하였으며, 최적경로 생성 시간 ()도 알고리즘 계산시간의 누적으로 나타냈다.

알고리즘의 성능평가 방법은 앞서 언급한 네 개의 평가 지표를 이용하였다. 이에 대한 방법은 크게 두 가지 방법으로 설계하였는데, 첫 번째 방법은 정규화 점수 (normalization score)를 이용하여 실험 조건별 알고리즘의 성능을 네 개의 평가 지표로 판단하는 방법이다. 이는 식 (3)과 같이 나타낼 수 있는데, 여기서 는 정규화 점수를 나타내는데, 이는 알고리즘별 네 개의 평가 지표 (, , , 및 )를 각각 산정하는 것을 의미한다.

두 번째 방법은 가중합 (weighted sum model, WSM) 방식에 기반한 종합 평가 방법이다. 이는 식 (4)와 같이 식 (3)에 의해 산정된 정규화 점수에 가중치를 곱하여 종합점수를 계산하는 방법으로 설명할 수 있다. 여기서 는 종합점수를 나타내며, , , 및 는 각 정규화 점수에 대한 가중치를 의미하는데, 본 연구에서는 모두 동일한 조건으로 0.25로 설정하였다. 이는 본 연구에서 선정한 4개의 평가 지표가 알고리즘을 평가하는데 동일한 영향력을 가진다는 가정에 의한 것을 의미한다.

1. 최적경로 알고리즘 성능평가 결과

본 장에서는 드론 최적경로 시뮬레이터에 의한 주요 결과를 나타내고자 하였으나, 본 연구에서 수행한 결과를 모두 도시화하기에 분량이 많아 주요 결과만을 제시하였다. 최적경로에 관한 결과는 Fig. 6부터 Fig. 9까지 나타냈는데, Fig. 6과 7은 각각 50개 및 100개의 무작위 분산형 방제 지점에 대한 주요 최적경로 알고리즘 결과를 보여주며, Fig. 8과 9는 각각 50개 및 100개의 무작위 군집형 방제 지점에 대한 주요 최적경로 알고리즘 결과를 보여준다.

Fig. 6

Result of optimal path calculation for scattered 50 points

Fig. 7

Result of optimal path calculation for scattered 150 points

Fig. 8

Result of optimal path calculation for clustered 50 points

Fig. 9

Result of optimal path calculation for clustered 150 points

먼저, Fig. 6은 50개의 무작위 분산형 방제 지점에 대한 최적경로 알고리즘 결과 중 가장 두드러지게 나타난 A^* (Fig. 6(a))와 Christofides (Fig. 6(b))의 최적경로 결과를 보여준다. A^*와 Christofides의 최적경로 결과는 서로 유사하게 닮은 것으로 보이는데, A^*와 Christofides의 최적경로는 방제 지점을 직접 이동 (타켓 간 직선적 움직임)하려는 경향을 보이는 특징을 가지는 것으로 나타났다. 이는 좌표축을 기준으로 한 평행 선형 이동이 아닌 타겟 간의 직선 이동을 나타냄으로 드론의 이동 효율성이 높을 수 있다는 가능성을 추정할 수 있다.

Fig. 7은 150개의 무작위 분산형 방제 지점에 대한 4개의 최적경로 알고리즘 결과 중 Dijkstra (Fig. 7(a)) 및 Christofides(Fig. 7(b))의 최적경로 결과를 보여준다. 이들의 결과는 매우 다른 경로로 드론이 이동하는 것을 나타내는데, Dijkstra의 최적경로 결과가 Christofides에 비해 복잡한 경로로 이동하는 결과를 보여준다. 특히 Christofides의 최적경로 결과는 간결하고 목적지를 항해 집중적으로 이동하는 경향을 보이고 있으며, 150개 지점이 확장된 상황에도 전체 면적을 효과적으로 운용하는 특징을 나타내고 있다.

Fig. 8은 50개의 무작위 군집형 방제 지점에 대한 주요 최적경로 알고리즘 결과를 나타냈다. 여기서 A^* (Fig. 8(a)) 및 Christofides (Fig. 8(b))의 최적경로 결과가 상이하게 나타났는데, 군집형 방제 지점 내부를 살펴보면 A* 최적경로는 시작점으로부터 가장 가까운 군집을 방문하여 해당 군집 내의 타겟을 집중하여 이동한 후 해당 군집에사 가장 가까운 군집을 방문하는 양상으로 보였다. 그러나, Christofide의 최적경로 결과는 군집을 기준으로 타겟을 방문하는 것이 아닌, 드론이 이동하는 데에 있어 전체적인 공간 활용 효율성을 높이는 타겟 중심 이동 경향을 보이고 있다. 즉, Christofide의 최적경로는 각각의 군집 내에서의 경로가 복잡하게 나타나, 공간적 집중성을 처리하는 방법에 차이 있는 것으로 판단된다.

Fig. 9는 150개의 무작위 군집형 방제 지점에 대한 주요 최적경로 알고리즘 결과를 보여준다. Dijkstra (Fig. 9(a)) 알고리즘의 최적경로는 드론이 우측 상단으로 먼저 이동하여, 원점으로 돌아오는 방향성을 나타냈으나, Christofides (Fig. 9(b))의 최적경로는 지점 간의 이동을 최대한 직선적으로 이동하는 움직임이 나타났으나, Christofides의 최적경로는 Fig. 8(b)의 결과와 같이 가장 가까운 타겟을 먼저 방문하려고 하는 경향성이 강함을 나타낸다. 이를 통해 Christofides는 본 연구에서 이용한 타 알고리즘과는 달리 TSP를 해결하는 방법론 때문에 전체 경로 길이를 최소화하면서 가까운 타겟을 우선적으로 연결하려고 하는 경향이 두드러지게 나타남을 알 수 있었으며, 이는 방제 지점이 밀집된 상황에서 더욱 효율적인 경로 탐색을 가능하게 하는 장점으로 작용할 수 있음을 보여준다.

본 연구에서 제시한 실험 조건에 따른 각각의 결과를 Table 2에 나타냈다. 먼저, 50개의 무작위 분산형 조건에서 실험 결과를 살펴보면, A^*가 모든 성능평가 지표에서 가장 우수한 성능을 보인 것으로 나타났다. 또한, Dijkstra 및 D^*Lite의 에너지 소비율 (40.7% 및 40.7%) 및 총 이동거리 (625.6 m 및 625.4 m)가 같거나 유사하게 나타났으나, 최적경로 생성 시간 부분에서는 Dijkstra가 더 효율적인 것으로 보였다. Christofides의 경우는 최적경로 계산시간이 0.01초로 가장 빨랐으나, 에너지 소모량 및 총 이동거리 및 모의 실행 시간 등의 평가 지표에서는 가장 낮은 성능을 보였다. 이를 통해 가장 단순한 Dijkstra가 가장 효과적인 것으로 판단할 수 있다. 100개의 무작위 분산형 조건에서는 Dijkstra가 가장 긴 경로 거리 (920.2 m)를 기록하였으며, 가장 높은 에너지 소비율 (59.9%)과 시뮬레이션 시간 (291.7초)이 나타나 효율성이 가장 낮은 것으로 나타났다. 또한 경로 계산시간도 54.66초로 비교적 긴 시간을 소요한 것으로 보였다. A^*가 Dijkstra보다 다소 개선된 성능을 보이며, D^*Lite는 Dijkstra와 유사한 경로 거리를 도출했으나, 경로 계산에 가장 많은 시간 (355.75초)이 소요된 것으로 나타났다. Christofides는 가장 짧은 경로 거리 (775.5 m)와 최소 에너지 소비율 (50.4%)을 보였으며, 시뮬레이션 시간도 가장 짧게 나타났다. 특히, 경로 계산시간은 0.02초로, 다른 알고리즘에 비해 가장 빠른 것으로 나타났다. 150개의 무작위 분산형 조건에서는 A^*는 경로 계산시간을 제외하고 모든 성능지표가 가장 낮게 나타났다. D^*Lite는 Dijkstra와 유사한 에너지 소비율 (64.6%), 총 이동거리, 및 시뮬레이션 시간 등이 유사하게 나타났으나, 경로 계산시간이 매우 높게 나타났다. 반면에 Christofides는 모든 성능지표에서 가장 우수한 알고리즘으로 보였다. 이를 통해 분산형 지점수가 작을 경우는 A^*가, 많을 경우에는 Christofides가 적합한 것으로 판단할 수 있다.

다음으로, 50개의 무작위 군집형 조건에서 실험 결과를 살펴보면, A^*가 경로계산 시간을 제외한 모든 성능지표에서 가장 우수한 결과를 도출했다. 여기서 경로계산 시간은 Christofides가 가장 낮게 나타났으나, A^*와 1.68 sec. 차이로 큰 차이가 나타나지 않았다. 이를 근거로 할 때, A^*가 50개의 무작위 군집형 조건에서 실험에서는 가장 우수한 성능을 가지는 것으로 판단할 수 있다. 또한, 100개의 무작위 군집형 조건에서는 A^*의 경로 계산시간에서는 Christofides보다 10배 차이가 있으나, 에너지 소비율, 총 이동거리 및 시뮬레이션 시간 등의 평가 지표에서 모두 우수한 것으로 나타나 비교적 우수한 알고리즘으로 평가할 수 있다. 또한, Dijkstra, D*Lite 및 Christofides의 에너지 소비율, 총 이동거리 및 시뮬레이션 시간 등의 평가 지표가 모두 유사하게 나타났으나, 이 중에서도 경로 계산시간이 매우 낮게 나타나 3개 알고리즘 중 Christofides가 가장 우수한 것으로 판단할 수 있다. 다음으로, 150개의 무작위 군집형 조건에서는 Christofides가 모든 성능지표에 대해 가장 우수한 결과를 보였으며, A^*의 모든 성능지표가 차순위로 나타났다. 이를 통해 분산형과 같이 군집형의 경우에도 지점수가 작을 경우는 A^*가, 많을 경우에는 Christofides가 드론 운영에 적합한 알고리즘으로 판단할 수 있다.

2. 최적경로 알고리즘별 종합 평가 결과

본 연구에서 구현한 드론 최적경로 시뮬레이터에서 50, 100 및 150개의 방제 지점을 방문하는 최적경로를 도출하고 이에 대한 네 개의 평가 지표인 에너지 소비율 (), 총 이동거리 (), 시뮬레이션 시간 () 및 최적경로 계산 시간 ()에 대한 평가를 수행하였다. 이를 위해 시뮬레이션 조건별 성능지표 평가 결과와 식 (3)을 이용하여 정규화 점수 도출하였으며, 이를 Fig. 10과 같이 히트맵으로 나타냈다. 이 방법은 최고 성능을 보인 알고리즘을 100점, 최저 성능을 보인 알고리즘을 0점으로 산정할 수 있고 그 사이에 있는 알고리즘은 선형적으로 분포한다는 특징을 가진다. 이 때문에, 결과 해석이 지나친 상태평가로 판단될 수 있으나, 평가 대상 간 순위나 우수성이 명확히 드러낼 수 있다는 장점이 있어 본 연구에 반영하였다.

Fig. 10

Heat map for each optimal path calculation for clustered 150 points

Fig. 10(a)는 분산형 방제 지점에 대한 정규화 점수의 변화를 보여주는데, A^*는 50개 방제 지점을 방문할 경우 모든 지표에서 균형 잡힌 우수한 성능을 보이는 것으로 나타났으나, 방제 지점수가 증가할수록 성능이 악화하는 양상을 보였다. Dijkstra 및 D^*Lite의 경우도 50개 방제 지점일 경우 양호한 성능을 나타냈으나, 100개 방제 지점일 때 성능이 가장 좋지 않은 결과를 보였다. Christofides의 경우 50개의 방제 지점을 제외하고 100개 및 150개에서 모두 우수한 결과를 보이는 것으로 나타났다. 이를 통해 방제 지점이 분산형으로 나타났을 때, 지점수가 적을 경우에는 A^*가, 지점수가 많을 경우에는 Christofides가 적합한 것으로 판단할 수 있다.

Fig. 10(b)는 군집형 방제 지점에 대한 정규화 점수의 변화를 보여준다. 여기에서도 분산형과 마찬가지로 A^*는 50개 방제 지점을 방문할 경우 모든 지표에서 균형 잡힌 우수한 성능을 보이는 것으로 나타났으며, 100개 지점에서도 유사한 우수성을 보였다. 다만, 150개 방제 지점에서는 성능이 다소 낮아지는 경향을 보였으나, 분산형에 대비해 양호한 수준인 것으로 생각할 수 있다. Dijkstra 및 D^*Lite의 경우도 50개 방제 지점일 경우 양호한 성능을 보였으나, 100개 및 150개 방제 지점일 때 성능이 매우 낮게 나타나는 것을 확인할 수 있다. Christofides의 경우 50개 및 100개의 방제 지점에서 가장 낮거나 낮은 성능을 보였으며 150개에서 매우 우수한 결과를 보이는 것으로 나타났다. 이를 통해 방제 지점이 분산형으로 나타났을 때와 마찬가지로 군집형에서도 지점수가 적을 경우에는 A^*를, 지점수가 많을 경우에는 Christofides가 적합한 것으로 판단할 수 있다.

각 알고리즘의 종합 평가를 수행하고자, Fig. 10의 결과와 식 (4)를 이용하여 종합 평가점수를 Fig. 11과 같이 나타냈다. Fig. 11(a)는 분산형 조건에서의 방제 지점수에 따른 네 개의 알고리즘에 대한 종합 평가점수를 나타내는데, A^*가 99.2점으로 가장 높은 성능을 보였고, Dijkstra는 63.7점으로 차순으로 나타났다. D^*Lite 및 Christofides는 각각 43.5점과 25.0점으로 상대적으로 낮은 점수를 보였다. 방제 지점 수가 100개와 150개로 증가함에 따라, Christofides가 두 경우 모두에서 최대 점수 (100.0)를 유지하는 것으로 나타나 뛰어난 확장성과 성능을 가지는 것으로 판단된다. 반면, Dijkstra, A^*, 및 D^*Lite는 방제 지점수의 증가에 따라 급격한 성능 저하를 보였는데, 특히 D^*Lite는 100개 지점에서 1.5점, 150개 지점에서 15.1점으로 매우 낮은 점수를 기록한 것으로 나타났다. Fig. 11(b)는 군집형 조건에서의 방제 지점수에 따른 각 알고리즘의 종합 평가점수를 나타낸다. 방제 지점수가 50개일 경우, A^*는 93.8점, Dijkstra는 88.7점으로 높은 성능을 보였으며, D^*Lite도 69.6점으로 양호한 결과를 보였다. 이와 달리 Christofides는 25.0점으로 가장 낮은 것으로 나타났다. 방제 지점 개수가 100개일 경우에는 Christofides가 다시 99.1점으로 매우 우수한 성능을 보였으며, Dijkstra와 A^*는 각각 30.6점으로 중간 수준의 성능을 나타냈다. D^*Lite는 8.2점으로 낮은 성능을 기록하였다. 방제 지점수가 150개일 경우, Christofides가 100.0점으로 최고의 성능을 유지한 반면에 A^*는 74.5점으로 양호한 성능을 유지하였다. Dijkstra는 21.0점, D^*Lite는 0.0점으로 큰 성능 저하를 보였다.

Fig. 11

Result of optimal path calculation for clustered 150 points

이를 통해 Christofides는 지점 수가 많고 분포가 복잡한 환경에서도 안정적인 성능을 보여주며, 전체적으로 가장 우수한 알고리즘으로 평가할 수 있다고 판단된다. 또한 A^*는 소규모 및 밀집된 환경에서 효과적이며, 중간 규모의 문제에서도 일정 수준 이상의 성능을 유지하는 결과를 보였다. Dijkstra는 비교적 간단하고 안정적인 알고리즘으로 설명할 수 있지만, 방제 지점수가 증가하거나 복잡도가 높을 경우, 성능이 크게 저하되는 것으로 나타났다. D^*Lite는 전체적으로 성능 편차가 크고, 특히 복잡한 환경에서 매우 낮은 점수를 기록하여 실용성에 한계가 있음을 보였다. 이러한 결과는 공간적 분포와 문제 규모에 따라 최적경로 알고리즘을 선택하는 것이 중요하다는 것을 의미하고, 본 논문에서 설계한 실험 조건에서는 네 개의 알고리즘 중 Christofides가 대규모 최적화 문제에 적합한 알고리즘임을 확인할 수 있었다.

다만, Fig. 11의 결과는 앞서 언급한 식 (4)에 의한 것으로, 평가 결과가 매우 상대적 점수로 극단적 평가로 이어질 수밖에 없는 한계가 존재한다. 이는 식 (4)에서 사용된 4개 성능지표에 대한 가중치를 모두 0.25로 획일적으로 적용했기 때문으로 판단된다. 이러한 방법은 간혹 순위 기반의 상대평가로 작용하여 절대적인 성능을 반영하기에는 어렵다는 단점이 있다. 또한, 4개 성능지표에 대한 지표 선정의 타당성, 정량적 중요도 및 성능 반영 비율 등이 반영되지 않았기 때문에 점수의 왜곡 또는 성능 판단의 오판이 발생할 수 있다는 부분도 가지고 있어 가중치의 조정이 요구된다. 그럼에도 이러한 방법은 직관적 비교에 유용하고 서로 다른 척도를 가지는 평가항목을 통합시켜 종합 평가가 가능하다는 장점이 있기 때문에 본 연구에 적용하였다는 것을 밝히고자 한다. 이에 더하여 향후 연구에서는 다양한 평가 지표의 선정, 드론 운영에 대한 지표의 영향력, 기상 조건, 드론의 스펙 및 현장의 환경 조건 등에 따라 알고리즘의 성능이 달라질 수 있다는 점을 고려하여 본 연구의 한계를 극복하고자 한다. 나아가, 실제 농업 환경과 유사한 공간적 및 물리적 조건을 반영하여 드론을 운용하는 경우, 그 효율성을 평가할 수 있도록 하는 후속 연구를 진행하고자 한다.