스마트 방제 임무 수행을 위한 농업용 멀티콥터 드론의 최적경로 알고리즘 비교 분

Abstract

In this study, a drone-based optimal path simulator was developed to evaluate four path finding algorithms—Dijkstra, A*, D* Lite, and Christofides—for agricultural pest control missions. The simulator was tested under two spatial distribution conditions (scattered and clustered) with varying numbers of target points (50, 100, and 150). Each algorithm was assessed using four performance metrics: energy consumption, total travel distance, simulation time, and path computation time. A weighted scoring system was applied to derive a comprehensive performance score. The simulation results showed that the Christofides algorithm consistently outperformed other algorithms in large-scale and complex environments, achieving perfect scores in scenarios with 100 and 150 target points, regardless of distribution type. The A* algorithm exhibited balanced and effective performance in small-scale or clustered environments, particularly with 50 target points, and maintained moderate performance at medium scale. These findings highlight the importance of algorithm selection based on both spatial distribution and problem scale. The Christofides algorithm is recommended for large-scale optimization tasks, while A* is suitable for small-scale or dense environments.