Ivan Kristianto Singgih. Agricultural Drone Zoning and Deployment Strategy with Multiple...| 66 Agricultural Drone Zoning and Deployment Strategy with Multiple Flights Considering Takeoff Point Reach Distance Minimization Ivan Kristianto Singgih Quantum Machine Learning Laboratory, School of Industrial Management Engineering, Korea University, Seoul, Republic of Korea. *Corresponding Email: 1ivanksinggih@gmail.com A B S T R A C T S A R T I C L E I N F O In the agricultural sector, drones are used to spray chemicals for the plants. A lawn mowing movement pattern is one of the widely used methods when deploying the drones because of its simplicity. A route planner determines some pre-set routes before making the drones to fly based on them. Each drone flight is limited by its battery level or level of spray liquids. To efficiently complete the spraying task, multiple drones need to be deployed simultaneously. In this study, we study a multiple drone zoning and deployment strategy that minimizes the cost to set up equipment at the takeoff points, e.g., between flights. We propose a method to set the flight starting points and directions appropriately, given various target areas to cover. This is the first study that discusses the spraying drone zoning and deployment plan while minimizing the number of takeoff points, which plays an important role in reducing the drone set up and deployment costs. The suggested procedure helps drone route planners to generate good routes within a short time. The generated routes could be used by the planner for their chemical spraying activity and could be used as initial input for their design, which can be improved with the planners’ experience. Our study shows that when generating an efficient route, we must consider the number of flight area levels, directions of the drone movements, the number of U-turns of the drones, and the start points of the drone flights. Article History: Received 18 Dec 2021 Revised 20 Dec 2021 Accepted 25 Dec 2021 Available online 26 Dec 2021 Aug 2018 __________________ Keywords: Drone, routing, rule, spraying, zone control. International Journal of Informatics, Information System and Computer Engineering International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 67 | International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 1. INTRODUCTION Drones is one of the most emerging technologies in Industry 4.0 era (Fernández-Caramés et al., 2019). They are used in various fields, including post- disaster observation (Singgih et al., 2020), last-mile delivery (Moadab et al., 2022), inspection (Nguyen et al., 2018), medical treatment (Pulver and Wei, 2018), etc. In agricultural field, drones are used for various purposes, including vegetation segmentation (Su et al., 2021), soil mapping, disease monitoring, estimating crop yield (Maddikunta et al., 2021), cultivation planning (Kakamoukas et al., 2022), etc. In contrast to manual work, using drones allows us to perform high- precision work within a short time. Such great precision is enabled Internet of Things and big data technology (Patrik et al., 2019; Sordan et al., 2022). Although the drone technology must still need to be supported with the establishment of internet connectivity for farmers to ensure the effective implementation of the technology (Mehrabi et al., 2021), currently, there is a quick development of the drone technology itself (Santangeli et al., 2020). In this study, we focus on drones that are used to spray chemicals on a large area (Figure 1). Before using the drones to spray chemicals on the plants, a drone route plan (Figure 2) is required (Hobby Hangar, 2022). To assess the novelty of our study, we conducted a literature review as follows. We start with (Chung et al. 2020). A drone routing problem can be classified into routing through target points and routing through target areas. In the first classification, the drones must visit all given target points (Coutinho et al., 2018; Gu et al., 2020), e.g., to conduct item delivery or observation from such points, while in the latter classification, the drones need to cover all target areas, e.g., when spraying chemicals on a target agriculture field (Faiçal et al., 2017). Our studied problem is classified as the latter one; thus, we review studies listed in Table 4 (drone routing problems with area coverage classification) from (Chung et al. 2020), specifically the ones marked with AG (agriculture) as the application area. To ensure that we cover papers published after (Chung et al. 2020), we also searched for papers citing (Chung et al. 2020). Among a total of 24 papers from both sources, we found five related papers to be compared with ours. The reasons for excluding other studies are because they study target point visiting problems or focus on the non-agriculture fields (e.g., traffic monitoring and delivery system). Comparisons between our study and those five related papers are presented in Table 1. Based on our knowledge, our study is the first one that considers drone zoning and routing when using multiple flights for agricultural purposes while minimizing the number of takeoff points. The drones’ lawn moving is a sweeping movement (Otto et al., 2018; Avellar et al., 2015). Such movements could be differentiated into (1) movements parallel to the longest side of the area and (2) movements perpendicular to the longest side of the area, as shown in Figure 3. Such lawn moving is preferred when the target search area is large, in contrast to spiral movement (Cabreira et al., 2019). Having such a simple movement pattern allows the planner to route the drones easily while ensuring high effectiveness in the drones’ movement. Our study focuses on proposing a certain simple movement to assist the route planner with their manual routing procedure. Also, our proposed movement strategy could be used as a Ivan Kristianto Singgih. Agricultural Drone Zoning and Deployment Strategy with Multiple...| 68 built-in route suggestion from the routing application that would be provided to the route planners for editing and approval. Given such a simple yet effective movement pattern, it would be easily understood by the route planners allowing them to conduct a better route optimization. Our study differs from previous studies by proposing a simple lawn moving pattern that considers the distances between each end point of a travel with the start point of the next travel (take off point). Such consideration is important because the drones would need their battery and chemical container to be replaced before continuing their next travel (Kim and Lim, 2018; Qin et a., 2021; Jorge et al., 2021). Minimizing the distances between take-off points minimizes the time required by the workers to pre-place the battery and chemical container replacements; thus, it significantly reduces the operational time and, in the end, reduces the cost and increases the benefit when using the drones. Figure 1. Chemical spraying drone Source: Ahmed et al. (2021) Figure 2. A pre-set drone route for chemical spraying on an agricultural area Source: Hobby Hangar (2022) Table 1. Comparison with Previous Studies Characteristics Drone Flight Routing Direction(s) Details on Routes Routing Objective(s) Moon and Shim (2009) Multiple Complex Exist Completion time Barrientos et al. (2011) Multiple Complex Exist Completion time Avellar et al. (2015) Multiple Lawn mowing (1 direction) Exist Completion time Barna et al. (2019) Single Lawn mowing (1 direction) Exist Captured photo quality 69 | International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 Tu et al. (2020) Multiple Lawn mowing (1 direction), grid Not exist Captured photo quality Our study Multiple Lawn mowing (2 directions) Exist Completion time, number of takeoff points (a) parallel to the longest side (b) perpendicular to the longest side Figure 3. Two types of lawn moving patterns of the drones When solving routing problems, various solution approaches could be used, e.g., mathematical models, exact heuristics, metaheuristics, simulation, and rule-based methods (Amarat and Zong, 2019; Erdelić and Carić, 2019; Moghdani et al., 2021). Lately, machine learning-based methods are also proposed by Arnold and (Sörensen, 2019) and Zhao, et al. 2021). Earlier methods (e.g., exact methods) produce better solution quality but require more computational effort. In contrast, rule- based methods are straightforward and can be applied more easily. Development of such rule-based methods is common for solving various combinatorial optimization problems, e.g., project scheduling (Chakrabortty et al., 2020), job dispatching (Ðurasević and Jakobović, 2020), and machine scheduling (Gil-Gala et al., 2019). Related to our problem, we develop a rule-based approach to provide drone route planners with the necessary insights for manually designing the routes. The structure of the whole paper is presented as follows: Section 2 explains the proposed routing procedure. Section 3 presents the numerical experiments and discussions. Finally, Section 4 concludes the study. 2. METHOD When operating the drones, we need to ensure real drone characteristics, e.g., the limitations on flight range (Otto et al., 2018) and limitations on weight to carry (Macrina et al., 2020). To ensure each drone to completes its tasks, we need to set up some locations within the working area of the drone with the equipment necessary to conduct the battery charging and chemical refuelling or replacement. When any drone requires a temporary landing, the required equipment must be Ivan Kristianto Singgih. Agricultural Drone Zoning and Deployment Strategy with Multiple...| 70 ready. Please note that after the landing, the drones would take off again after the landing to continue the spraying process. Therefore, we call the temporary landing points as take-off points as well. To ensure the readiness of the equipment, it is straightforward to minimize the distances between the take-off points. Such a distance minimization can also be found in truck routing problems in a truck-drone collaborative parcel delivery system (Wang et al., 2019). Such a take-off point distance minimization is equivalent to reducing the number of take-off points, which reduces the effort to transport and prepare the equipment for the landing drones. Our proposed drone zoning and deployment procedure is described in Algorithm 1. Algorithm 1. Drone zoning and deployment procedure 1: Calculate the number of required drone flights: " #_of_drone_flights=" ⌊"total grid area/max covered grid area per drone" ⌋ 2: Determine alternatives of identical drone flight area dimensions (length and width), which cover the whole spraying area 3: Define the possible drone flight start and end positions simultaneously while minimizing the total distances from the drone take-off points 4: Finalize the best drone deployment plan The end points for each drone movement are determined based on the size of the target area and the movement direction of the drones, as shown in Figure 3. As shown in Figure 3(a), when the number of U-turns of a drone is even, the drone travel will end at on the exact opposite side of the starting point. Meanwhile, when the number of U-turns of the drone is odd (Figure 3(b)), the drone travel will end at on the same side with as the starting point. Considering such a movement rule, we need to determine the movement direction of the drones based on the size of the target area. It will significantly affect the positions of the take-off points and determine the number of the take-off points. In general, minimizing the number of U-turns is preferred because travelling through the U-turn area causes a longer movement time due to the required deceleration and acceleration movements. However, allowing a decent number of U-turns should be acceptable, considering that making such decisions could reduce the number of take-off points. Please refer to the next section for examples and further analysis. 3. RESULT AND DISSCUSION For the numerical experiment, we consider two problem instances. Instance 1 considers a 200-grid area with 10 grid x 20 grid dimensions, while Instance 2 considers a 180-grid area with 15 grid x 12 grid dimensions. For Instances 1 and 2, the max grid area covered by a drone flight are 20 and 30 grid area, respectively. Considering various movement rules, we generate five and three drone deployment plans for Instances 1 and 2, as shown in Figures 4 and 5, respectively. We observe the drone flight area/drone movements on 71 | International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 horizontal and vertical locations/directions for simplicity. Please note that we refer to the horizontal or vertical directions when observing the target area from the top view. The results are produced using Algorithm 1. In Step 1, it is straightforward to determine the number of flights based on the drone’s limited flight time, which is determined by the limited battery or carried chemical. In Step 2, we define the same-shaped flight area for the drones. Currently, we consider the same shape to extract basic drone deployment and routing rules easily. To observe various routing alternatives in Steps 3 and 4, we test various drone movement strategies, e.g., (1) horizontal or vertical-directed movements and (2) starting points at the outer side or inner side of the target area. For a drone flight, the start point, and end point are labeled as “S” and “E”, respectively. A “takeoff point” consists of a maximum of 4 landing and takeoff points that are placed adjacently because we can place the equipment (recharged battery and refuel chemical tanks) in the center of those points. From this part of the manuscript, we will call each location as “a takeoff point”. We exclude the first start point and the last end point from the calculation for the number of takeoff points because we assume that each drone is ready with all required equipment when starting its first flight and at the end of its last flight, we do not need to rush with the drone last pickup process. As an example, in Figure 4(a), there are five takeoff points as follows: takeoff point 1 (E1, S2, E9, S10), takeoff point 2 (E2, S3, E8, S9), takeoff point 3 (E3, S4, E7, S8), takeoff point 4 (E4, S5, E6, S7), and takeoff point 5 (E5, S6). Different background colors for each takeoff point group are used to clearly present the results. (a) even horizontal flight area, vertical flight, odd U-turns, 5 takeoff points (BEST) Ivan Kristianto Singgih. Agricultural Drone Zoning and Deployment Strategy with Multiple...| 72 (b) even horizontal flight area, vertical flight, odd U-turns, 9 takeoff points (c) even horizontal flight area, horizontal flight, even U-turns, 7 takeoff points (d) odd horizontal flight area, horizontal flight, odd U-turns, 5 takeoff points 73 | International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 (e) even horizontal flight area, horizontal flight, no U-turns, 9 takeoff points Figure 4. Drone deployment alternatives for Instances 1 (a) odd horizontal flight area, vertical flight, odd U-turns, 5 takeoff points Ivan Kristianto Singgih. Agricultural Drone Zoning and Deployment Strategy with Multiple...| 74 (b) odd horizontal flight area, vertical flight, odd U-turns, 5 takeoff points (c) odd horizontal flight area, horizontal flight, even U-turns, 4 takeoff points (BEST) Figure 5. Drone deployment alternatives for Instances 2 The best routing alternatives (that reduces the number of take-off points) for Instances 1 and 2 are shown in Figures 4(a) and 5(c), respectively. Based on our observation, we conclude that a minimum number of take-off points can be produced by: (1) Generating an even number of flight area levels, then ensuring that the take-off points are grouped in the 75 | International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 middle of each adjacent two levels, as shown by Figure 4(a), which has two horizontal flight area levels. The take- off points can be accumulated in the middle of both horizontal levels because the number of U-turns is odd (which makes the drones return to the same middle side of the target area). (2) Generating an odd number of flight area levels, then setting the drones’ perpendicular movements from those levels, as shown by Figure 5(c), which has three horizontal flight area levels and a horizontal drone flight movement. In this example, the number of U-turns is even. If the number of U-turns is odd, then we would follow the same routing solution structure shown in Figure 4(a) by starting the drone movements from the middle part of two adjacent vertical flight area. In addition to the findings above, we also conclude that no U-turns do not minimize the number of take-off points because the start and end points are not adjacently placed. The findings in this study can be used as a good reference for drone flight planners when they predefine the flight routes (Ma et al., 2019). 4. CONCLUSION We study a multiple drone zoning and deployment problem. Our proposed method includes dividing the target area into zones, then determining detailed drone movement directions to minimize the effort of preparing battery and refueling chemicals for drones at the end of each flight. Some useful insights are listed to be used as recommendations for drone flight planners. For future research topics, we suggest allowing different drone flight area sizes to increase the flexibility of the drone movements and the effort for the equipment preparation. REFERENCES Ahmed, S., Qiu, B., Ahmad, F., Kong, C.-W., & Xin, H. (2021). A State-of-the-Art Analysis of Obstacle Avoidance Methods from the Perspective of an Agricultural Sprayer UAV’s Operation Scenario. Agronomy, 11, 1069. Amarat, S. B., & Zong, P. (2019). 3D Path Planning, Routing Algorithms and Routing Protocols for Unmanned Air Vehicles: A Review. Aircraft Engineering and Aerospace Technology, 91(9), 1245–1255. Arnold, F., & Sörensen, K. (2019). What Makes a VRP Solution Good? The Generation of Problem-Specific Knowledge for Heuristics. Computers & Operations Research, 106, 280–288. Avellar, G. S. C., Pereira, G. A. S., Pimenta, L. C. A., & Iscold, P. (2015). Multi-UAV Routing for Area Coverage and Remote Sensing with Minimum Time. Sensors, 15, 27783–27803. Ivan Kristianto Singgih. Agricultural Drone Zoning and Deployment Strategy with Multiple...| 76 Barna, R., Solymosi, K., & Stettner, E. (2019). Mathematical Analysis of Drone Flight Path. Journal of Agricultural Informatics, 10(2), 15–27. Barrientos, A., Colorado, J., del Cerro, J., Martinez, A., Rossi, C., Sanz, D., & Valente, J. (2011). Aerial Remote Sensing in Agriculture: A Practical Approach to Area Coverage and Path Planning for Fleetsof Mini Aerial Robots. Journal of Field Robotics, 28(5), 667–689. Cabreira, T. M., Brisolara, L. B., & Paulo R. Jr., F. (2019). Survey on Coverage Path Planning with Unmanned Aerial Vehicles. Drones, 3(1), 4. Chakrabortty, R. K., Rahman, H. F., & Ryan, M. J. (2020). Efficient Priority Rules for Project Scheduling Under Dynamic Environments: A Heuristic Approach. Computers & Industrial Engineering, 140, 106287. Chung, S. H., Sah, B., & Lee, J. (2020). Optimization for Drone and Drone-Truck Combined Operations: A Review of The State of the Art and Future Directions. Computers and Operations Research, 123, 105004. Coutinho, W. P., Battara, M., & Fliege, J. (2018). The Unmanned Aerial Vehicle Routing and Trajectory Optimisation Problem, A Taxonomic Review. Computers & Industrial Engineering, 120, 116–128. Ðurasević, M., & Jakobović, D. (2020). Comparison of Schedule Generation Schemes for Designing Dispatching Rules with Genetic Programming in the Unrelated Machines Environment. Applied Soft Computing Journal, 96, 106637. Erdelić, T., & Carić, T. (2019). A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches. Journal of Advanced Transportation, 5075671. Faiçal, B. S., Freitas, H., Gomes, P. H., Mano, L. Y., Pessin, G., de Carvalho, A. C. P. L. F., Krishnamachari, B., & Ueyama, J. (2017). An Adaptive Approach for UAV- based Pesticide Spraying in Dynamic Environments. Computers and Electronics in Agriculture, 138, 210–223. Fernández-Caramés, T. M., Blanco-Novoa, O., Froiz-Míguez, I., & Fraga-Lamas, P. (2019). Towards an Autonomous Industry 4.0 Warehouse: A UAV and Blockchain-Based System for Inventory and Traceability Applications in Big Data-Driven Supply Chain Management. Sensors, 19(10), 2394. Gil-Gala, F. J., Mencía, C., Sierra, M. R., & Varela, R. (2019). Evolving Priority Rules for On-Line Scheduling of Jobs on a Single Machine with Variable Capacity Over Time. Applied Soft Computing Journal, 85, 105782. 77 | International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 Gu, Q., Fan, T., Pan, F., & Zhang, C. (2020). A Vehicle-UAV Operation Scheme for Instant Delivery. Computers & Industrial Engineering, 149, 106809. Hobby Hangar. (2022). ALIGN RM41501XW M4 High-Performance Agricultural Drone. https://www.hobbyhangar.co.nz/align-rm41501xw-m4-high- performance-agricultural-drone. Jorge, H. G., de Santos, L. M. G., Álvarez, N. F., Sánchez, J. M., & Medina, F. N. (2021). Operational Study of Drone Spraying Application for the Disinfection of Surfaces against the COVID-19 Pandemic. Drones, 5(1), 18. Kakamoukas, G. A., Sarigiannidis, P. G., & Economides, A. A. (2022). FANETs in Agriculture - A Routing Protocol Survey. Internet of Things, 18, 100183. Kim, S. J., & Lim, G. J. (2018). A Hybrid Battery Charging Approach for Drone-Aided Border Surveillance Scheduling. Drones, 2(4), 38. Ma, F., Xu, Z., & Xiong, F. (2019). Research on Route Planning of Plant Protection UAV Based on Area Modular Division. 2019 11th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC) (p. 101–104). Macrina, G., Pugliese, L. D. P., Guerriero, F., & Laporte, G. (2020). Drone-aided Routing: A Literature Review. Transportation Research Part C, 120, 102762. Maddikunta, P. K. R., Hakak, S., Alazab, M., Bhattacharya, S., Gadekallu, T. R., Khan, W. Z., & Pham, Q.-V. (2021). Unmanned Aerial Vehicles in Smart Agriculture: Applications, Requirements, and Challenges. IEEE Sensors Journal, 21(16), 17608–17619. Mehrabi, Z., McDowell, M. J., Ricciardi, V., Levers, C., Martinez, J. D., Mehrabi, N., Wittman, H., Ramankutty, N., & Jarvis, A. (2021). The global divide in data- driven farming. Nature Sustainability, 4, 154–160. Moadab, A., Farajzadeh, F., & Valilai, O. F. (2022). Drone Routing Problem Model for Last-Mile Delivery using The Public Transportation Capacity as Moving Charging Stations. Scientific Reports, 12, 6361. Moghdani, R., Salimifard, K., Demir, E., & Benyettou, A. (2021). The Green Vehicle Routing Problem: A Systematic Literature Review. Journal of Cleaner Production, 279, 123691. Moon, S.-W., & Shim, H.-C. (2009). Study on Path Planning Algorithms for Unmanned Agricultural Helicopters in Complex Environment. International Journal of Aeronautical & Space Sciences, 10(2), 1–11. Ivan Kristianto Singgih. Agricultural Drone Zoning and Deployment Strategy with Multiple...| 78 Nguyen, V. N., Jenssen, R., & Roverso, D. (2018). Automatic Autonomous Vision- Based Power Line Inspection: A Review of Current Status and the Potential Role of Deep Learning. International Journal of Electrical Power & Energy Systems, 99, 107–120. Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018). Optimization Approaches for Civil Applications of Unmanned Aerial Vehicles (UAVs) or Aerial Drones: A Survey. Networks, 72(4), 411–458. Patrik, A., Utama, G., Gunawan, A. A. S., Chowanda, A., Suroso, J. S., Shofiyanto, R., & Budiharto, W. (2019). GNSS-based Navigation Systems of Autonomous Drone for Delivering Items. Journal of Big Data, 6, 53. Pergher, I., Frej, E. A., Roselli, L. R. P., & de Almeida, A. T. (2020). Integrating Simulation and FITradeoff Method for Scheduling Rules Selection in Job-Shop Production Systems. International Journal of Production Economics, 227, 107669. Pulver, A., & Wei, R. (2018). Optimizing the Spatial Location of Medical Drones. Applied Geography, 90, 9–16. Qin, Y., Kishk, M. A., & Alouini, M.-S. (2021). On the Influence of Charging Stations Spatial Distribution on Aerial Wireless Networks. IEEE Transactions on Green Communications and Networking, 5(3), 1395–1409. Santangeli, A., Chen, Y., Kluen, E., Chirumamilla, R., Tiainen, J., & Loehr, J. (2020). Integrating Drone‑Borne Thermal Imaging with Artifcial Intelligence to Locate Bird Nests on Agricultural Land. Scientific Reports, 10, 10993. Singgih, I. K., Lee, J., & Kim, B.-I. (2020). Node and Edge Drone Surveillance Problem with Consideration of Required Observation Quality and Battery Replacement. IEEE Access, 8, 44125–44139. Sordan, J. E., Oprime, P., Pimenta, M. L., Chiabert, P., & Lombardi, F. (2022). Industry 4.0: A Bibliometric Analysis in the Perspective of Operations Management. Operations and Supply Chain Management, 15(1), 93–104. Su, J., Yi, D., Su, B., Mi, Z., Liu, C., Hu, X., Xu, X., Guo, L., & Chen, W.-H. (2021). Aerial Visual Perception in Smart Farming: Field Study of Wheat Yellow Rust Monitoring. IEEE Transactions on Industrial Informatics, 17(3), 2242–2249. Tu, Y.-H., Phinn, S., Johansen, K., Robson, A., & Wu, D. (2020). Optimising Drone Flight Planning for Measuring Horticultural Tree Crop Structure. ISPRS Journal of Photogrammetry and Remote Sensing, 160, 83–96. 79 | International Journal of Informatics Information System and Computer Engineering 2(2) (2021) 66-79 Wang, D., Hu, P., Du, J., Zhou, P., Deng, T., & Hu, M. (2019). Routing and Scheduling for Hybrid Truck-Drone Collaborative Parcel Delivery with Independent and Truck-Carried Drones. IEEE Internet of Things Journal, 6(6), 10483–10495. Zhao, J., Mao, M., Zhao, X., & Zou, J. (2021). A Hybrid of Deep Reinforcement Learning and Local Search for the Vehicle Routing Problems. IEEE Transactions on Intelligent Transportation Systems, 22(11), 7208–7218.