Matching algorithm for plant protecting unmanned aerial vehicles and plant protecting jobs based on R-tree spatial index

Abstract: Compared with the traditional plant-protecting machine, plant protection unmanned aerial vehicle (UAV) has advantages of high efficiency, high performance, good precision and good spraying effect. Most importantly, the promotion of physical protection is very significant. In order to fully guarantee that the plant protecting assignments can be allocated scientifically and the plant protecting UAV resources can be deployed efficiently, as well as for meeting the needs of plant protecting spray jobs, a high efficient algorithm for matching UAVs with plant protecting jobs was designed, and a high effective plant protecting assignments scheduling system was developed. The system can not only provide the UAV users with appropriate matching plant protecting assignments, but also help to find the appropriate matching UAVs for the users who need to rent the specific UAVs to carry out plant protection spray. In this paper, the existing technologies were analyzed and compared to find out which one could be used to fulfill matching algorithm for UAVs and assignments, the features of plant protection assignment for UAV were clarified, and a matching algorithm for UAV and its plant protection assignment based on the R-tree spatial indexing was designed. The R-tree is a completely dynamic spatial index of data structure, and sub-algorithms such as node inserting, deleting and querying operations are mutually independent. The matching algorithm for plant protection assignment includes the algorithms of inserting plant protecting assignment into the R-tree, querying plant protection assignment from the R-tree, and deleting some assignment when it is finished or canceled. By using the matching algorithm, the plant protection assignment intelligent recommendation system was developed, and it mainly included the region querying function and intelligent recommendation function. The region search function allows UAV users to search all the plant protection assignments within the scope of any rectangle dragged on the map. Meanwhile the intelligent recommendation function based on the user's current location can recommend the UAV users with the plant protection assignments nearby which meet the UAV's spray features, and also can help the users who have the specific plant protecting assignment to find the right UAVs to rent. We built the entire system by using Django web framework and programmed with Python language and JavaScript language. The results of system test showed that the matching algorithm for UAVs and their plant protection assignments based on the R-tree could handle more than 2 000 concurrent requests at the same time even in a lower configuration server. The querying algorithm's response time was less than 1 ms when processing a single request. The test of plant protection job inserted into the R-tree in batches showed that inserting 1 000 jobs took less than 1 s, and thanking to the dynamic nature of the R-tree, we could read and write the R-tree at the same time, so the insertion of the R-tree did not affect the query operation. It illustrates that the algorithm is flexible, accurate, dynamic and highly efficient, and it can be used to match UAVs with the corresponding appropriate plant protecting assignments reasonably and intelligently.