All Issue

2025 Vol.67, Issue 5 Preview Page
Comparative Analysis of an Optimal Path Planning Algorithm for Agricultural Multicopter Drones in Smart Pest Control Missions

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

Chi-Yong Ana
,
Seolmin Kimb
,
Seokho Songc
,
Jinki Parkd
,
Chulmin Songe†
안 치용a
,
김 설민b
,
송 석호c
,
박 진기d
,
송 철민e†
aMaster. Student, Department of Rural Engineering, Chungbuk National University
bMaster. Student, Department of Rural Engineering, Chungbuk National University
cDoctor. Student, Department of Rural Engineering, Chungbuk National University
dResearcher, Department of Upland Crop Research and Development, Nation Institute of Crop Science, Rural Development Administration
eAssociate Professor, Department of Rural Engineering, Chungbuk National university
†Corresponding author Tel.: 010-3117-3817, E-mail: song_c_m@chungbuk.ac.kr
2025. pp. 61-75
PDF XML Citation
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.

Keywords
path algorithm
precision agriculture
open field smart farm
autonomous
References

REFERENCES

1
H. C. An, R. Kleinberg and D. B. Shmoys, Journal of the ACM (JACM), Improving Christofides’ algorithm for the st path TSP, 62(5); 1-28 (2015)10.1145/2818310
2
A. Cavoukian, Privacy and drones: Unmanned aerial vehicles; 1-12, Canada. Information and Privacy Commissioner of Ontario. (2012)
3
H. J. Cho and K. M. Jeong, Journal of the Korea Convergence Society, A study on the connective validity of technology maturity and industry for core technologies based on 4th industrial revolution, 10(3); 49-57, (in Korean) (2019)10.15207/JKCS.2019.10.3.049
4
G. J. Choi and W. J. Jang, Korean Society of Transportation, A model for shortest path calculation on intermodal transportation network, 16(4); 167-186, (in Korean) (1998)
5
D. S. Choi, K. C. Ma, H. J. Kim, J. H. Lee, S. A. Oh and S. G. Kim, Korean Journal of Applied Entomology, Control standards of three major insect pests of Chinese cabbage (Brassica campestris) using drones for pesticide application, 57(4); 347-354, (in Korean) (2018)10.5656/KSAE.2018.09.0.031
6
H. Chung, J. H. Roh, J. W. Yang, H. K. Shim, D. G. Jeong, J. Y. Kim, J. Y. Shin, I. J. Kang and S. Heu, Research in Plant Disease, Rice blast populations isolated from the border area of North Korea, 25(4); 164-172, (in Korean) (2019)10.5423/RPD.2019.25.4.164
7
N. Christofides, Recherche Opérationnelle, The vehicle routing problem. Revue Française d’Automatique, Informatique, Recherche Opérationnelle, 10(V1); 55-70 (1976)10.1051/ro/197610v100551
8
E. W. Dijkstra, Numerische Mathematik, A note on two problems in connexion with graphs, 1; 269-271 (1959)10.1007/BF01386390
9
P. Finnegan, World civil unmanned aerial systems: 2019 market profile & forecast, Teal Group Corporation. (2019)
10
D. Floreano and R. J. Wood, Nature, Science, technology and the future of small autonomous drones, 521(7553); 460-466 (2015)10.1038/nature14542
11
P. K. Freeman and R. S. Freeland, Remote Sensing Applications, Society and Environment, Agricultural UAVs in the U.S.: Potential, policy, and hope, 2; 35-43 (2015)10.1016/j.rsase.2015.10.002
12
P. E. Hart, N. J. Nilsson and B. Raphael, IEEE Transactions on Systems Science and Cybernetics, A formal basis for the heuristic determination of minimum cost paths, 4(2); 100-107 (1968)10.1109/TSSC.1968.300136
13
C. Hierholzer and C. Wiener, Mathematische Annalen, Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, 6(1); 30-32 (1873)10.1007/bf01442866
14
V. Jarník, O jistém problému minimálním, (Z dopisu panu O. Borůvkovi) (1930)
15
H. I. Kang, B. Lee and K. Kim, IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial ApplicationPath planning algorithm using the particle swarm optimization and the improved Dijkstra algorithm, Vol. 2; 1002-1004, IEEE. (2008)10.1109/PACIIA.2008.376
16
H. Kim, Journal of the Institute of Electronics and Information Engineers, Research trends and challenges in optimal drone route planning, 61(7); 623-626, (in Korean) (2024)10.5573/ieie.2024.61.7.11
17
S. J. Kim and H. Yoe, The Journal of Korean Institute of Communications and Information Sciences, Trend and standardization of smart farm technology, 47(11); 1965-1973, (in Korean) (2022)10.7840/kics.2022.47.11.1965
18
S. Koenig and M. Likhachev, IEEE Transactions on Robotics, Fast replanning for navigation in unknown terrain, 21(3); 354-363 (2005)10.1109/TRO.2004.838026
19
S. Koenig, M. Likhachev, Y. Liu and D. Furcy, AI Magazine, Incremental heuristic search in AI, 25(2); 99-112 (2004)10.1609/aimag.v25i2.1763
20
T. Korkmaz and M. Krunz, Proceedings IEEE INFOCOM 2001Multi-constrained optimal path selection, Vol. 2; 834-843, IEEE. (2001)10.1109/INFCOM.2001.916274
21
A. Koubâa, H. Bennaceur, I. Chaari, S. Trigui, A. Ammar, M. F. Sriti, M. Alajlan, O. Cheikhrouhou and Y. Javed, Robot path planning and cooperation: Foundations, Algorithms and experimentations, Berlin. Springer. (2018)10.1007/978-3-319-77042-0
22
D. Kwon, W. G. Sang, S. Chang, W. Im, H. Bak, J. Lee and J. I. Cho, Korean Journal of Agricultural and Forest Meteorology, Estimation of rice canopy height using terrestrial laser scanner, 25(4); 387-397, (in Korean) (2021)10.5532/KJAFM.2023.25.4.387
23
J. D. Lee and C. M. Heo, Journal of Digital Convergence, The effect of technology acceptance factors on behavioral intention for agricultural drone service by mediating effect of perceived benefits, 18(8); 151-167, (in Korean) (2020)10.14400/JDC.2020.18.8.151
24
J. Y. Lee and B. M. Kim, Journal of the Korea Institute of Information and Communication Engineering, Growth environment monitoring system for open-field smart farms using big data model, 28(1); 47-53, (in Korean) (2024)10.6109/jkiice.2024.28.1.47
25
S. Lee, J. H. Park, E. Kim and W. Jang, Journal of Information Science Theory and Practice, Analysis of the present status and future prospects for smart agriculture technologies in South Korea using national R&D project data, 10(S); 112-122, (in Korean) (2022)10.1633/JISTaP.2022.10.S.11
26
S. Y. Lee, J. S. Park, C. R. Lee, L. Y. Choi, D. K. Favour, J. Y. Park and S. W. Hong, Journal of the Korean Society of Agricultural Engineers, Analysis of drone downwash and droplet deposition for improved aerial spraying efficiency in agriculture, 66(5); 51-65, (in Korean) (2024)10.5389/KSAE.2024.66.5.051
27
LG Economic Research Institute, Background and prospects of China’s agricultural rise, (in Korean) (2018)
28
J. T. Lim, Journal of Convergence for Information Technology, A study on the characteristic analysis of the pest control drones using smart operating mode, 9(10); 108-113, (in Korean) (2019)10.22156/CS4SMB.2019.9.10.108
29
D. Mandloi, R. Arya and A. K. Verma, International Journal of System Assurance Engineering and Management, Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3d environment, 12(5); 990-1000 (2021)10.1007/s13198-021-01186-9
30
Ministry of Agriculture, Food and Rural Affairs, Creating rural areas where everyone can live, work, and relax in 2024 (Press Release), (in Korean), Ministry of Agriculture, Food and Rural Affairs. (2024)
31
H. H. Noh, C. J. Kim, B. C. Moon, T. G. Kim, D. B. Kim, M. S. Oh, D. S. Choi, Y. Y. Kim, H. S. Song and K. S. Kyung, The Korean Society of Pesticide Science, Drift patterns of aerial spraying pesticide caused by formulations and nozzles, 24(3); 278-285, (in Korean) (2020)10.7585/kjps.2020.24.3.278
32
S. I. Oh, The Summer Conference of the Korean Institute of Broadcast and Media EngineersCase study civilian drone; 315-318, (in Korean) (2015)
33
P. Raja and S. Pugazhenthi, International Journal of Physical Sciences, Optimal path planning of mobile robots: A review, 7(9); 1314-1320 (2012)10.5897/IJPS11.1745
34
Rural Development Administration, Rural Development Administration accelerates research for commercialization of autonomous agricultural machinery (Press release), (in Korean) (2018-February-9)
35
J. H. Ryu, H. Y. Ahn and K. D. Lee, Korean Journal of Agricultural and Forest Meteorology, Utilization of weather, satellite and drone data to detect rice blast disease and track its propagation, 25(4); 245-257, (in Korean) (2023)10.5532/KJAFM.2023.25.4.245
36
W. G. Sang, J. H. Kim, J. K. Baek, D. Kwon, H. Y. Ban, J. I. Cho and M. C. Seo, Korean Journal of Agricultural and Forest Meteorology, Detection of drought stress in soybean plants using RGB-based vegetation indices, 23(4); 340-348, (in Korean) (2021)10.5532/KJAFM.2021.23.4.340
37
S. Song, H. Chung, K. H. Kim and K. T. Kim, Research in Plant Disease, Analysis of rice blast outbreaks in Korea through text mining, 28(3); 113-121, (in Korean) (2022)10.5423/RPD.2022.28.3.113
38
T. Qing, Z. Ruirui, C. Liping, X. Min, Y. Tongchuan and Z. Bin, International Journal of Agricultural and Biological Engineering, Droplets movement and deposition of an eight-rotor agricultural UAV in downwash flow field, 10(3); 47-56 (2017)10.3965j.ijabe.20171003.3075
39
D. Verscheure, B. Demeulenaere, J. Swevers, J. De Schutter and M. Diehl, IEEE Transactions on Automatic Control, Time-optimal path tracking for robots: A convex optimization approach, 54(10); 2318-2327 (2009)10.1109/TAC.2009.2028959
40
G. S. Yoo and C. M. Yeo, Korea Institute of S&T Evaluation and Planning, Smart agriculture. KISTEP Technology Trend Brief No. 2021-03, (in Korean) (2022)
Information
  • Publisher :The Korean Society of Agricultural Engineers
  • Publisher(Ko) :한국농공학회
  • Journal Title :Journal of Korean Society of Agricultural Engineers
  • Journal Title(Ko) :한국농공학회논문집
  • Volume : 67
  • No :5
  • Pages :61-75
  • Received Date : 2025-06-27
  • Revised Date : 2025-07-31
  • Accepted Date : 2025-08-01
  • DOI :https://doi.org/10.5389/KSAE.2025.67.5.061
Journal Informaiton Journal of Korean Society of Agricultural Engineers Journal of Korean Society of Agricultural Engineers
  • NRF
  • KOFST
  • crossref crossmark
  • crossref cited-by
  • crossref funder-registry
  • crosscheck
  • orcid
  • open access
Journal Informaiton Journal Informaiton - close