A binary gridding path-planning method for plant-protecting UAVs on irregular fields

XU Wang-ying,YU Xiao-bing#,XUE Xin-yu

1 School of Management Science and Engineering,Nanjing University of Information Science & Technology,Nanjing 214000,P.R.China

2 Nanjing Institute of Agricultural Mechanization,Ministry of Agriculture and Rural Affairs,Nanjing 214000,P.R.China

Abstract

The use of plant-protecting unmanned aerial vehicles (UAVs) for pesticide spraying is an essential operation in modern agriculture.The balance between reducing pesticide consumption and energy consumption is a significant focus of current research in the path-planning of plant-protecting UAVs.In this study,we proposed a binarization multi-objective model for the irregular field area,specifically an improved non-dominated sorting genetic algorithm–II based on the knee point and plane measurement (KPPM-NSGA-ii).The binarization multi-objective model is applied to convex polygons,concave polygons and fields with complex terrain.The experiments demonstrated that the proposed KPPM-NSGA-ii can obtain better results than the unplanned path method whether the optimization of pesticide consumption or energy consumption is preferred.Hence,the proposed algorithm can save energy and pesticide usage and improve the efficiency in practical applications.

Keywords: plant-protecting UAV,path-planning,multi-objective optimization,gridization,Pareto optimal

1.Introduction

Pests and diseases have always been among the major factors hindering agricultural development.Traditional pest control methods are usually based on spraying pesticides.However,in the face of complex terrain,manual spraying often has problems such as logistical difficulty,high work intensity,high manual demand,and wasting of pesticides (Luanetal.2021).With the continuing development of technology,the use of plantprotecting unmanned aerial vehicles (UAVs) for aerial operations has gradually emerged.The use of UAVs for spraying operations has achieved good results in pest control,and it has gradually become one of the essential means of pest control because of its low manual demand,precisely controllable spraying accuracy,uniform spraying volume,and easy operation.The effective operating surface widths of plant-protecting UAVs can typically reach 4–6 m,and they can spray 8 to 10 acres per hour,saving nearly two-thirds of the time of manual pesticide spraying operations (Wang and Gao 2015).The UAV is capable of uniformly spraying foggy pesticides onto the leaves and stalks,and the front and back of the crop.The UAV saves time and effort and has good atomization,high pesticide utilization,and better results than the traditional manual spraying method (Wangetal.2017).It not only avoids crop death caused by heavy or missed spraying during manual spray applications but also significantly reduces the harm caused by pesticide application to the human body.In the process of UAV operation,the most important part is planning the path.Typically,a variety of conditions need to be considered,including weather and temperature conditions and the operational path-planning.

Studies conducted on plant-protecting UAVs have been dominated by full-coverage path-planning.In many cases,the object of agricultural path-planning is a regular boundary field.Conesa-Munozetal.(2016) fused the simulated annealing (SA) algorithm for fullcoverage path-planning of multi-operation UAVs.Jietal.(2019) used the gridding method to plan full-coverage navigation routes with the objectives of using the shortest total range,payload,and safe operation.Considering some of the irregular obstacles in China’s typical farmland environment,Liuetal.(2018) proposed a multi-obstacle area avoidance algorithm to improve the applicability of the autonomous operation mode of plant-protecting UAVs.These refinements realized the cooperative operation of multiple plant-protecting UAVs and improved operational efficiency (Pingetal.2020).

The above-mentioned studies all focused on cases with regular boundaries.This approach is suitable for regular fields that have limited irregularities of their boundaries.However,many fields are irregular.Therefore,it is of practical significance and importance to study the path operational method of plant-protecting UAVs on irregular fields.This study proposes a multi-objective UAV pathplanning model for irregular fields.A binary model is created to streamline the process and facilitate handling.The pesticide consumption and energy consumption are both considered in this model,and a higher quality solution is obtained through the innovative non-dominated sorting genetic algorithm based on knee point and plane measurement (KPPM-NSGA-ii).

Currently,there are two methods to solve multiobjective optimization problems (Tanetal.2002).The first is to transform the multiple objectives into a singleobjective problem by assigning weights so that the transformed objective function becomes a single objective optimization problem.For example,a path-planning model was established based on a digital map,which introduced virtual terrain,and eliminated many search spaces from 3D to 2D (Qietal.2010).Then the improved heuristic A＊ algorithm was applied to solve the 3D pathplanning problem.The advantage of this method is that the optimization process is simple,and only the global minimum needs to be found.However,the definitions of weighting and the objective function depend on prior knowledge and the judgments of decision-makers.The second method is to search for the optimal solution to multi-objective problems,and then find the non-dominated solutions in a given region.For example,a multi-objective plant-protecting UAV model was established to maximize total income and minimize total operation time (Caoetal.2019).An order priority path-planning algorithm based on the non-dominated sorting genetic algorithm-II (NSGA-ii) was proposed to solve the model.The direct multi-objective optimization method is not affected by the preferences of decision-makers,and it can intuitively reflect the distribution of current solutions.However,finding the best solution among the possible Pareto solutions still requires decision-making.No matter which solution is closer to the objective function,it will cause the loss of the other objective functions (Hornetal.1994).To resolve this issue,the proposed approach chooses feasible solutions under the different priorities of the two objective functions.Each solution in the different priorities has different tendencies,and it also shows the exploration and exploitation of the algorithm.

Based on these considerations,a binarized gridding model is proposed for irregular field path-planning and an improved multi-objective algorithm is developed to solve the model.Energy consumption and pesticide consumption are used as the two objective functions of the UAV path-planning.To solve the model,the knee point is introduced into the algorithm.The knee point has the largest marginal effect on the Pareto Fronts (PF) (Das 1999).In unbiased decision-making,a knee point is often considered the best solution,so the knee point is therefore passed on to the next generation as key information to improve the PF coverage.Moreover,in the multi-objective iterative process,the points with maximum plane measurements to enter the next generation cycle are the key to determining the performance of the algorithm (Chen and Zhang 2004).Therefore,a multiobjective optimization algorithm based on knee points and plane measurement is proposed in this paper.The NSGA-ii is a classical algorithm with relatively low complexity and higher accuracy (Debetal.2002),so the KPPM-NSGA-ii algorithm is proposed in this study to solve the UAV binary plant-protecting path-planning model.The proposed KPPM-NSGA-ii possesses higher accuracy and lower energy and pesticide consumption values than the traditional method.

The article is organized into five sections.Section 2 shows the methodology,including the model building and the method for solving the model.Section 3 shows the experimental results,in which three cases with different field shapes are used to demonstrate the performance of the NSGA-ii and KPPM-NSGA-ii algorithms.Section 4 compares the two proposed algorithms with unplanned paths method.Section 5 concludes the whole paper.

2.Methodology

2.1.Model building

In general,UAV path-planning is modeled based on various conditions,such as the shape of the field,weather,and temperature.Considering the complexity of the problem and the computational power of the algorithm,path modeling is performed only for complete fields in a two-dimensional plane.A complete two-dimensional field can be approximated by one of two major types: the convex polygon field or the concave polygon field.Solving a convex polygon field is much less difficult than a concave polygon field.Therefore,most of the existing plant-protecting UAV path-planning problems are for convex polygons.In this section,a binarized gridding model is constructed to solve the problem of fields with different shapes.

Selection of the operation methodCurrently,there are two types of UAV operational methods.One is the reciprocating method,and the other is the internal and external spiral method.Different operational methods correspond to different operational effects.Therefore,it is necessary to analyze and compare the effects to develop a more suitable operational method for plant-protecting UAVs.

AppendixA shows the diagrams of the reciprocating and the internal and external spiral operational methods.The UAV travels along a specific straight line to the bottom of the operation area boundary,turns,and then continues along another straight line parallel to the previous one.The distance between the two straight lines is the spray widthdof the UAV.The above process is repeated until the entire field is covered.The inner spiral method starts from a boundary line of the covered area.It follows the inner spiral of equal height along the outer contour line of the area in a clockwise or counterclockwise direction as shown in Appendix B.Therefore,any operating route is parallel to a boundary line of the coverage area,and the adjacent parallel operating paths are equally spaced.The spaces between parallel operating paths are equal to the operating widthd.The outer spiral method can be regarded as the inverse process of the inner spiral method.

However,since the plant-protecting UAV does not spray when it turns corners,the use of inner spiral method may result in the repetition and deficiency.Appendix C shows that if the UAV starts the inner spiral operation along the longitudinal direction,patches of missed and repeated coverage will be generated at each turning point.Therefore,it is more appropriate to use the reciprocating method for the plant-protecting UAV.

Binarized mesh modeling methodAppendix D shows a schematic diagram of the binarized mesh modeling process.In the figure,αis the heading angle,the green grid is the effective grid and ABCDE is the randomly generated convex polygon.The specific modeling method is as follows.

(1) Based on the generated random polygon,establish a rectangular coordinate system with the coordinate values of each vertex of the polygon asPA,PB,PC,PD,andPE.

(2) Use the heading angle as the rotation angle,recreate a new rectangular coordinate systemx′o′y′,and update the coordinates of each angle.SupposePis a vertex of the polygon with the original coordinates of (xp,yp),then the coordinates ofPafter rotating the coordinate axis are:

(4) The point confirmed by the minimum values of thex′andy′axes is the starting point of the grid.The spray widthdis the width of the grid.The grid is formed based on the starting point and the grid width.

(5) Define all internal grids surrounded by edge grids as effective grids (including the edge grids themselves).Export all edge grids,assign a value of “1” to each edge grid and “0” to the other grids,and generate a binary output matrix.Find all columns of the binary matrix with a value of “1” and record them.

(6) Multiply the number of effective grids by the width of the spray to obtain the effective path length of each row.

(7) Based on the existing edge-grid binarization matrix,calculate the total path length to obtain the overall energy and pesticide consumption.

Fig.1 shows the path-planning route after binarized network modeling,whereαis the UAV heading angle.The effective path length is the sum of the path lengths parallel to the grid,and it is proportional to the pesticide consumption.The total path length is the sum of the effective path length and the steering length,and it is proportional to the energy consumption.Therefore,“effective path length” and “total path length” are used to represent “pesticide consumption” and “energy consumption”,respectively.

Fig.1 The binarized grid method model for path-planning.UAV,unmanned aerial vehicle.

The pseudo-code of the binarized grid method model is shown in Algorithm 1.

Path-planning functionsThe path-planning model of the UAV should follow the rules of less waste,shorter distance,less energy consumption,and other regulations for operational planning.These rules can be reflected by the two indicators of energy and pesticide consumption.Generally,the plant-protecting UAV advances at a uniform speed and does not spray during the turns.Pesticide and energy consumption are assumed to be proportional to effective path length and total path length,respectively.The expressions of pesticide and energy consumption are shown in eq.(2).

?Algorithm1 Pseudo-code of the binary grid method Input: Independent variable heading angle α,the width of the spray d,coordinates of several vertices of the polygon P1,P2,…,Pn 1Determine the new axis position using heading angle α 2Determine the new position of each vertex of the polygon P1′,P2′,…,Pn′ according to eq.(1)3Find the maximum and minimum values of all vertices in the new axis xmax,xmin,ymax and ymin.These four values are also the maximum and minimum values in the grid 4Divide the grid according to the spray width d 5Obtain the number of rows and columns of the binarization matrix,denoted as m and n,respectively,according to the number of divided grids 6Find all the grids that the outer contour of a polygon passes through,which are the edge grids 7Assign all edge grids values of “1” and the rest of the grids values of “0” 8Record the binarized grid matrix as A 9For i=1: m in A 10Record the number of columns with “1” in row i of matrix A 11Find the maximum and minimum values of the rows,and the grid between them is the effective grid 12Use storage to record the positions of the effective grids.13End 14Calculate the effective path length and total path length using the number of effective grids 15Output: Effective path length F1 and total path length F2

whereF1(x) andF2(x) are the functions of pesticide and energy consumption,respectively,xiis the independent variable of the two dimensions,including heading angleαand spay widthd,c1andc2are the positive correlation coefficients with constant consumption values,L(xi) denotes the effective path length of each row,nrepresents the number of rows after gridization,andS(xi) denotes the distance flown by the UAV from theith row of the grid to the (i+1)th row.

Since a priori knowledge of energy and pesticide consumption is not available when making decisions,and both the effective path length and the total path length have the same units,it is advisable to take bothc1andc2as 1,which can fairly and effectively reflect the two objective function values.Hence,the improved cost functionF(x) is expressed in eq.(3).

whereF(x) is the total objective cost function andM1,M2,...,Mnrepresent the number of effective grids in each row,dis the width of the UAV spray pattern,nis the number of grid rows andS12,S23,...,S(n–1)nare the steering lengths between rows.

Since the independent variable has a complex mapping relationship with the total objective cost functionF(x),Fig.2 shows the transformation process.

Fig.2 The mapping relationship between x and F(x).

Moreover,the concept of redundant spraying rate is also introduced.Fig.1 shows that there are more spraying areas during rasterization,which leads to wasting of pesticides.A numerical analysis of the excess spray rate in each case is conducted.The repeated spraying rate can show the optimization ability of the algorithm for the objective function.The redundant spraying rate is expressed in eq.(4).

whereF1(x) denotes the effective path length of each row andnrepresents the number of grid rows.The objective function of pesticide consumption is calculated in both cases and multiplied by the raster widthdto obtain the spray area of the pesticide.

2.2.Model solving method

In most cases,a single objective evaluation function is used to evaluate the plant-protecting UAV path-planning model,such as only the pesticide consumption,the energy consumption rate,or the area coverage rate (Huang 2001; Chenetal.2021).Some studies have also combined both metrics to reset the cost function.However,the cost function requires the decision maker to have sufficient prior knowledge and experience to decide the weight assignment for each indicator.In this study,a multi-objective algorithm is proposed to solve the multi-objective path-planning problem without requiring prior knowledge and experience.Energy and pesticide consumption are taken as the two objective functions to be optimized by the multi-objective optimization method.

Multi-objective optimizationThe constrained multiobjective optimization problem (CMOPs) is to find the minimum/maximum value of the objective function that satisfies the conditions in a given environment.There are three elements in the optimization problem,including the objective function,the parameter values,and the constraints.Multi-objective optimization is based on an optimization problem with more than one objective function.Therefore,it is often impossible to find a globally optimal solution that satisfies each objective function due to the conflicts or mutual influences among the multiple objective functions.The multi-objective problem model is mathematically expressed by eq.(5).

wherex1,x2,...,xnare the feasible solutions in the feasible region Φ,f1(x),f2(x),...,fn(x) are some objective functions,andxdminandxdmaxare the upper and lower bounds of the independent variable functionsxin each dimension,respectively,whilegi(x) andhi(x) are called the inequality and the equation constraints,respectively.CMOPs always need to deal with constraint violations,which are described in single scalars,such as:

Suppose that there are any two solutionsx1,x2∈Φ,x1dominatex2iffi(x1)≤fi(x2) for eachi∈{1,...,n} andfj(x1)＜fj(x2) for at least onej∈{1,...,n},which is denoted asx1＜x2.For a solutionx＊∈Φ,if there is no other solution in Φ dominatingx＊,thenx＊is called a Pareto optimal solution.A set including all of the Pareto optimal solutions is called a Pareto set (PS).The relationship between PS and PF can be expressed as:

Fig.3 depicts the relationship between the Pareto solution and the other solutions.The curves formed by A,B,C,and D are called PF,and they do not dominate each other; while E,F,G,and H are feasible solutions,but they are not optimal choices and are dominated by at least one point on PF.

Fig.3 Solutions on Pareto and non-Pareto front.

NSGA-ii algorithmSrinivas and Deb (1994) proposed a NSGA algorithm for solving the multi-objective problem.Debetal.(2002) proposed an improved version of the NSGA algorithm called NSGA-ii,which had significantly improved computational complexity and congestion.The NSGA-ii algorithm includes the following five steps.

(1) Generate the initial populationPtusing a genetic algorithm.

(2) Perform mutation operations on individuals of the population to produce offspringQtand combine them with the parentPtto form a new populationRt.

(3) Derive the Pareto solutions and retain the PF according to the non-dominated ranking of the populations.

(4) In the case where the number of retained individuals exceeds the number of populations,calculate the crowding distance for a few individuals located at the end of the PF.The individuals with larger crowding distances enter the next generation iteration.

(5) The retained individuals generate new populations ofPt+1and participate in the next step of evolution.

Appendix E shows the flow chart of the NSGA-ii algorithm when solving a multi-oective optimization problem.

KPPM-NSGA-ii algorithmThe optimization capabilities of NSGA-ii seem insufficient for minimizing transmission losses.Therefore,this study enhances the NSGA-ii algorithm,mainly by improving the local search process.The classical NSGA-ii algorithm updates the nextgeneration population based on random evolution,while the enhanced KPPM-NSGA-ii algorithm uses gridded knee points and plane distance measurement to update the positions.The gridded knee points and the plane distance measurement techniques are described below.

Definition 1: Knee pointsA knee point is the point on the PF where marginal utility is maximized.Around the knee point,a change in one objective function often leads to significant changes in other objective functions (Das 1999).Therefore,the knee point is often considered the most attractive point for decision-makers without reference to decision weights.

The knee point has been defined differently in various studies (Wuetal.2021).Since this study involves two objective functions that can be measured geometrically on PF,the method of the farthest distance from the feasible solution to the line joining the two solutions at the boundary is used to determine the knee point.This method is one of the mainstream methods for detecting knee points and has been used in various algorithms (Zhangetal.2015; Jiangetal.2020; Wuetal2021).It has low computational complexity and is robust to knee point detection.

Assume that the two extreme points of the PF aremandn,then connectingmandnis the line ofL,and the formula ofLcan be given by two points.The distance from each point on PF toLis calculated separately.The distance from the pointp(xp,yp) on PF toLis shown in eq.(8).

wherea,b,andcare the coefficients of the lineL.

Definition 2: Plane measurement techniquePlane measurement is a method that combines mathematics and geometry.It utilizes two objective functions to calculate the distance between populations.The plane measurement between candidate solutions is used to determine the performance of those solutions so that the superior solution can be selected as the parent and entered into the iterative process.

Distance measurements have been used in many algorithms.For example,Yesilbuetal.(2013) improved K-nearest neighbors (K-NN) classification using various distance measurements,including Euclidean distance,Manhattan distance,and Minkowski distance measurements,and successfully predicted wind speed parameters.Chen and Zhang (2004) introduced Euclidean distance in a class of clustering algorithms and updated the objective function based on the distance data obtained in order to improve the noise and outlier robustness of the clustering algorithm.Since there are only two objective functions in this study,the Pareto solution is represented by a planar twodimensional function.Then the plane measurement uses a combination of numerical and morphological methods,thus significantly reducing the complexity of the algorithm.Therefore,the crowding distance calculated during the non-dominated ranking of the previous algorithm is directly utilized as the data for the plane measurement.This method avoids secondary computations and increases the computational speed of the algorithm while improving the accuracy of algorithm optimization.During the local exploration,the information for the gridded knee points and maximum crowding distance points are directly used to improve the efficiency of the algorithm.

The crowding distance is the Manhattan distance between a Pareto solution and its two closest solutions.When the two solutions are close to each other they convey much less information than two solutions that are farther apart (Debetal2002).The crowding distance is interpreted as the similarity between the two solutions.If the retained solutions are highly similar,they tend to fall into a local optimum at an early stage.Therefore,individuals with large crowding distances need to be retained in order to maintain the diversity of the population and increase the breadth of the exploration.The crowding distances of adjacent solutions are calculated by eq.(9).

wheredidenotes the crowding distance ofith first candidate solution,andfm(ui) theith individual value in the population of themth objective function,whilefm(umax) andfm(umax) are the maximum and minimum fitness values of the current iterative population in themth objective function,respectively.

Definition 3: GriddingGridding is a common optimization method.It is possible for gridding to operate separately on a specific part of the front surface by slicing the entire PF on a grid and controlling the iterative process in each grid,which increases the flexibility of the algorithm during the iteration process and facilitates the comparison and superposition calculation of the objective function in the iteration (Kong and Bin 2007).

In the process of improvement,grid-wise slicing of the PF is performed first and then the maximum crowding distance solution and the knee point within that grid are solved separately for each grid.Since these two solutions are usually considered to carry the most information of the present generation,the two solutions are added during the evolution.This difference operation guides the direction of the next generation of iterations.The above evolutionary concept is shown in eq.(10).

Appendix F shows a schematic diagram of the gridding knee point and plane distance measurement techniques.

Based on the NSGA-ii algorithm,this study improves the generation of offspring during the iteration,and the improved offspring population will carry more valid information to continue the iteration.The pseudo-code of the proposed KPPM-NSGA-ii algorithm is shown in Algorithm 2.

Algorithm 2: Pseudo-code of the proposed KPPM-NSGA-ii Input: Popsize,Dimension,xmin,xmax,Gmax,and the number of grids: p 1Initialize populations based on upper and lower bounds 2Randomly generate the population x1,x2,...,xn and calculate the two fitness values for the population using eq.(3)3Perform fast non-dominated sorting of the existing populations 4For t=1:Gmax 5Perform gridding of the existing populations according to the number of grids 6Calculate the fitness of x1,x2,...,xn by eq.(3)7For ii=1:p 8Find the pth maximum crowding distance point and knee point in the offspring using eqs.(8) and (9),respectively 9Generate the offspring using eq.(10)10End 11Boundary condition treatment of populations 12t=t+1 13End 14Output: A PF consisting of Pareto solutions

3.Results

The traditional gridization method can only solve the path-planning problem for simple convex polygonal field blocks.However,the binarized field marginal method can transform the grid into a binary matrix when facing complex boundary shapes of fields,which significantly reduces the complexity of the problem.The binarized field marginal method is applicable for both convex and concave polygonal fields.To validate the effectiveness of the proposed method,three experiments were conducted.The heading angle and the spray width variables were used as the optimization objectives to control the space of the feasible domain.Then the optimal values within the feasible solution range were determined using the Pareto search method,in which the ranges for the heading angle and the UAV spray width were considered to be [0°,180°] and [1 m,6 m],respectively.

3.1.Plant-protecting UAV path-planning method in the convex polygon field

A convex pentagonal irregular field was randomly generated by MATLAB Software,as shown in Appendix G.The coordinates of the five vertices are [0,0],[100,0],[140,60],[70,80] and [20,70],whereαis the heading angle in the range of [0°,180°].The heading angle is determined when the UAV enters the field.The heading angleαand spray widthdare used as the optimization objectives for multi-objective problems.

To verify the benefits of using the proposed algorithm to plan the path,the concept of unplanned paths was introduced.An unplanned path is defined as a parallel path entering along any side of the field,and it also adopts the method of the reciprocating type.The total path length and the effective path length are the energy and pesticide consumption indexes,respectively.Refer to Appendix H for the route.Appendix I shows the matrix of a convex polygon field after binarization,and Fig.4 shows the PF of the convex polygon fields generated by the KPPM-NSGA-ii and the NSGA-ii algorithms.Table 1 shows the Pareto solutions of the two algorithms in the convex polygon field.

Table 1 Effective solutions obtained by the two algorithms for the convex polygon field

Fig.4 Pareto solution distributions by the two multi-objective algorithms in the convex polygon field.A,Pareto solution distribution by the KPPM-NSGA-ii algorithm.B,Pareto solution distribution by the NSGA-ii algorithm.

The data in Fig.4 and Table 1 show that several valid solutions derived by the proposed KPPM-NSGA-ii algorithm consistently dominate the solutions obtained by the NSGA-ii algorithm in the convex polygon field.Although the solutions obtained by the NSGA-ii algorithm are more evenly distributed,all eight solutions obtained by the KPPM-NSGA-ii algorithm have smaller values than those obtained by the NSGA-ii algorithm.Thus,the proposed KPPM-NSGA-ii algorithm has a better search capability than the NSGA-ii algorithm.

3.2.Plant-protecting UAV path-planning method in the concave polygon field

A concave heptagonal irregular field was randomly generated.The coordinates of the seven vertices are [0,0],[80,0],[60,30],[80,60],[20,80],[10,60],and [–10,30].The total path length and the effective path length are considered as the energy and pesticide consumption indexes for the multi-objective optimization search.Appendices J and K illustrate the simulation roadmaps generated by the planned and unplanned methods.Appendix L shows the schematic diagram of the binarized grid matrix generated by the KPPM-NSGA-ii algorithm.

Fig.5 shows the Pareto solutions generated by the KPPM-NSGA-ii and the NSGA-ii algorithms for the optimal solution of the concave polygon field.Table 2 shows all the Pareto solutions of the two algorithms in the concave polygon field.The results show that the NSGA-ii algorithm has more uniform solutions,but the proposed KPPMNSGA-ii algorithm finds more suitable Pareto solutions.The NSGA-ii algorithm finds only four Pareto solutions,while the proposed KPPM-NSGA-ii algorithm finds nine Pareto solutions,reflecting the multi-objective function exploration capability of the KPPM-NSGA-ii algorithm.When the proposed KPPM-NSGA-ii algorithm dominates the NSGAii algorithm by one solution,the energy and pesticide consumption values of the KPPM-NSGA-ii algorithm are 727.3662 and 851.1580,respectively,while the corresponding values of the NSGA-ii algorithm are 730.8159 and 855.1949,respectively,so the differences between them are 3.45 and 4.03.When the NSGA-ii algorithm dominates the KPPM-NSGA-ii algorithm by one solution,the energy and pesticide consumption values of the KPPMNSGA-ii algorithm are 674.9904 and 973.7264,respectively,while the corresponding values of the NSGA-ii algorithm are 674.9716 and 973.6993,respectively.The differences between the two algorithms in this case are almost 0.Therefore,the proposed KPPM-NSGA-ii algorithm has a better mining capability than the NSGA-ii algorithm.

Table 2 Effective solutions obtained by the two algorithms for the concave polygon field

Fig.5 Pareto solution distributions by the two multi-objective algorithms in the concave polygon field.A,Pareto solution distribution by the KPPM-NSGA-ii algorithm.B,Pareto solution distribution by the NSGA-ii algorithm.

3.3.Plant-protecting UAV path-planning method in the complex terrain field

In practice,the shape of farmland is generally complex and diverse.In this case,a complex terrain field was randomly generated as shown in Appendix M.The vertices of the field are (20,0),(100,0),(140,20),(100,20),(140,40),(100,40),(140,60),(100,60),(140,80),(0,80),(20,60),(0,60),(20,40),(0,40),(20,20),and (0,20).The total area of the field amounts to 8.8×103m2.The width of each grid is [2,6].Appendix N shows the binarized gridding model of this terrain field.

The Pareto solutions generated by the KPPMNSGA-ii and the NSGA-ii algorithms are shown in Fig.6 for the optimal solution of the complex terrain field.Table 3 shows all the Pareto solutions found by the two algorithms.In this experiment,the KPPM-NSGA-ii algorithm finds seven Pareto solutions while the NSGA-ii algorithm finds three Pareto solutions.In addition to the fact that the NSGA-ii algorithm finds fewer feasible solutions than the proposed KPPM-NSGA-ii algorithm,the quality of the solutions is inferior to those of the KPPMNSGA-ii algorithm as well.Table 3 shows that the KPPMNSGA-ii algorithm has three solutions that are superior to the NSGA-ii algorithm,while the NSGA-ii algorithm has no solution that is better than the KPPM-NSGA-ii algorithm.

Table 3 Effective solutions obtained by the two algorithms for the complex terrain field

Fig.6 Pareto solution distributions by the two multi-objective algorithms in the complex terrain field.A,Pareto solution distribution by the KPPM-NSGA-ii algorithm.B,Pareto solution distribution by the NSGA-ii algorithm.

4.Discussion

To better demonstrate the differences between algorithmplanned and unplanned UAV path-planning,we compared the two algorithms with unplanned paths.Note that in the no-algorithm-planned case,the UAV operates on a path based on the boundaries of irregular fields.Therefore,the heading angle isα=0° and the spray width takes the maximum value of 6.

4.1.Comparison of the path-planning method in the convex polygon field

In Fig.7,the minimum points on the energy and pesticide consumption objective functions are compared when the energy and pesticide consumptions take precedence,respectively.The KPPM-NSGA-ii algorithm obtains a smaller energy consumption value than the NSGA-ii algorithm in the energy consumption priority and a smaller pesticide consumption value than the NSGA-ii algorithm.When energy demand takes precedence,the unplanned path method consumes 448.096 and 413.759 more energy than the KPPM NSGA-ii and NSGA-ii algorithms,respectively.When the pesticide consumption requirement is minimal,the unplanned path operation requires 550.2 and 547.24 more in pesticide consumption than the KPPM-NSGA-ii and NSGA-ii algorithms,respectively.In the case of pesticide consumption priority,both the pesticide and energy consumption values obtained by the KPPM-NSGA-ii algorithm are smaller than those obtained by the NSGA-ii algorithm.Furthermore,the energy consumption values obtained by the unplanned path operation are smaller than those obtained by the NSGA-ii algorithm in Fig.7-B.However,the minimum pesticide consumption value is the priority goal in this case,so the NSGA-ii algorithm is considered to perform better than the unplanned one.The experiments in these two cases show that the proposed KPPM-NSGA-ii algorithm has a stronger boundary mining capability at the feasible domain boundary.

Fig.7 Comparison of the objective functions in the convex polygon field.A,comparison of energy consumption priority.B,comparison of pesticide consumption priority.

Table 4 lists the repeated spraying rates with and without planning in the convex polygon field.The waste rate of the pesticide consumption priority is lower than that of the energy consumption priority because only the number of effective grids is considered in the pesticide consumption priority.The interval length between grids will be considered for energy consumption,and the spraying area is proportional to the effective grid length when pesticide consumption is preferred.Table 4 shows that the operational methods of unplanned routes require more energy or pesticide consumption than the operational methods of planned routes.When energy demand is prioritized,the unplanned route method has a waste rate that is 4.5% higher than the KPPM-NSGA-ii algorithm.The NSGA-ii algorithm waste rate is 0.31% greater than the KPPM-NSGA-ii algorithm.When pesticide consumption is the lowest,the waste rate of the unplanned path operation is 20.32% greater than the KPPM-NSGA-ii algorithm.The NSGA-ii algorithm waste rate is 4.68% greater than the KPPM-NSGA-ii algorithm.

Table 4 Repeat spray rate and area of different path-planning methods in the convex polygon field

4.2.Comparison of the path-planning method in the concave polygon field

The energy and pesticide consumption of the planned and unplanned paths were compared.The proposed KPPM-NSGA-ii algorithm and the classic NSGA-ii algorithm were used in the planned path-planning to reveal the differences between several situations.The experimental results are shown in Fig.8.In the case of no path-planning,the UAV operates on the path based on the boundary of the irregular area.Therefore,the heading angle is set asα=0°,and the spray width takes the maximum value of 6.

Fig.8 Comparison of the objective functions in the concave polygon field.A,comparison of energy consumption priority.B,comparison of pesticide consumption priority.

Fig.8-A compares the two algorithms in the case of energy consumption priority.The KPPM-NSGA-ii algorithm obtains smaller energy and pesticide consumption values than the NSGA-II algorithm.In the case of pesticide consumption priority,the NSGA-II algorithm obtains slightly smaller pesticide and energy consumption values than the KPPM-NSGA-ii algorithm.However,the KPPM-NSGA-ii and NSGA-II algorithms perform similarly in terms of energy consumption priority.The experimental results in the two different cases show that the KPPM-NSGA-ii algorithm has a stronger boundary mining ability at the feasible domain boundary.

The unplanned path operation approach has greater energy and pesticide consumption than the path that is planned using the algorithm.When minimizing energy consumption is the priority,the unplanned path approach has energy consumption values that are 283.21 and 279.19 greater than the KPPM-NSGA-ii and NSGA-ii algorithms,respectively.When minimizing pesticide consumption is the priority,the unplanned path approach has pesticide consumption values that are 357.01 and 357.03 greater than the KPPM-NSGA-ii and NSGA-ii algorithms,respectively.Overall,using algorithms for UAV operational path-planning is reasonable and practical.

The data in Table 5 show that the unplanned routes require more energy or pesticide consumption than the planned routes.The waste rate of the pesticide consumption priority is lower than that of the energy consumption priority because the pesticide consumption priority only considers the number of effective grids.The interval length between grids will be considered only for energy consumption.When energy demand is prioritized,the unplanned route method has a waste rate that is 2.45% higher than the KPPM-NSGA-ii algorithm,while the repeated spraying rates of the NSGA-ii algorithm and KPPM-NSGA-ii algorithms are equal.When pesticide consumption is the lowest,the waste rate of the unplanned path operation is 21.16% greater than the KPPM-NSGA-ii algorithm.The NSGA-ii algorithm waste rate is 1.98% greater than the KPPM-NSGA-ii algorithm.

Table 5 Repeat spray rate and area of different path-planning methods in the concave polygon field

4.3.Comparison of the path-planning method in the complex terrain field

Fig.9 shows the path-planning results of each algorithm under complex terrain.Similar to Section 4.2,the results of the planned and unplanned paths were compared to assess whether the algorithm planning is better than the unplanned path.

Fig.9 Comparison of the objective functions in the complex terrain field.A,comparison of energy consumption priority.B,comparison of pesticide consumption priority.

Two extreme points from all Pareto solutions were selected for comparison.The KPPM-NSGA-ii algorithm achieves the minimum value with energy consumption as the preferential objective.With pesticide consumption as the priority objective,the KPPM-NSGA-ii algorithm still achieves the optimum value.However,note that when energy consumption is prioritized,the pesticide consumption of the unscheduled path reaches a minimum,and it is worth noting that the energy consumption is prioritized in this case.The energy consumption value of the unplanned path is greater than that of the KPPMNSGA-ii algorithm by 200,demonstrating that this method is inferior to the KPPM-NSGA-ii algorithm.Therefore,the KPPM-NSGA-ii algorithm performs better for the pathplanning problem in a complex topographic situation.

Table 6 lists the repeated spraying rates with and without planning in the complex terrain field.The spray waste rate illustrates the optimization power of the algorithm.The better the algorithm’s optimization ability,the shorter the path length and the lower the waste rate.The KPPM-NSGA-II algorithm achieves the lowest waste rates under the different prioritization goals.In particular,comparing the waste rate of the unplanned path with that of the KPPM-NSGA-ii algorithm,the KPPM-NSGA-ii algorithm saves nearly 1×103m2.

Table 6 Repeat spray rate (%) of different path-planning methods in the complex terrain field

5.Conclusion

We have developed a flexible binarized grid model for pesticide spray path-planning for plant-protecting UAVs.There are three main contributions of this study.

(1) A binarized gridding model is proposed.The grid matrix expresses the relationships between the grid and the boundaries of the field,and can be used to calculate various indicators of UAV operations.This model can be used to study the flight paths not only for regular fields but also for complex fields.

(2) An improved multi-objective optimization algorithm based on the knee point and plane measurement techniques is proposed.This algorithm is validated on the proposed model,which significantly improves the performance of UAVs.

(3) Comparative experiments using two different field shapes are carried out.Three experiments demonstrated that the improved KPPM-NSGA-ii algorithm works better and has higher accuracy than the NSGA-ii algorithm.

At present,this algorithm model can only solve the path-planning problem for complete irregular field blocks.In future work,UAV path-planning for discrete field blocks will be incorporated.

Acknowledgements

This research was funded by the National Natural Science Foundation of China (72274099 and 71974100),the Humanities and Social Sciences Fund of the Ministry of Education,China (22YJC630144),the Major Project of Philosophy and Social Science Research in Colleges and Universities in Jiangsu Province,China (2019SJZDA039) and the Postgraduate Research & Practice Innovation Program of Jiangsu Province,China (KYCX22_1244).

Declaration of competing interest

The authors declare that they have no conflict of interest.

Appendicesassociated with this paper are available on https://doi.org/10.1016/j.jia.2023.02.029