Path Planning for Autonomous Operation of Drone in Fields with Complex Boundaries

Abstract:

In order to deal with the complexity of field boundaries for the agricultural drone application, an operation path planning algorithm with boundary universality was proposed and implemented for rotor based unmanned aircraft systems (UAS) to quickly obtain the flight trajectory for fields of all kinds of boundaries, including convex polygon, concave polygon, or even polygon with holes and multiple polygons. Firstly, the storage rule of vertex data of boundary polygon of field was specified, and the polygon of different fields was distinguished based on the polygon grouping method of the region representation rule, and the path planning was performed according to each field block individually. Secondly, operation route was obtained based on the scanning and filling lines of the polygon. For a single field block with a given flight direction, the initial scanning lines for both outer and inner boundary polygons were figured out quickly by using the active edge table method, and then the logic Boolean operation of “subtraction” was applied to the two sets of scanning lines. Then the route was optimized for high efficiency with the minimum energy and time. Taking the minimum interroute jump distance as the optimization target, introducing “greedy algorithm”, “convex polygon minimum span method” and “step rotation method”, by using the greedy algorithm to address the route sequencing optimization which can be formulated as travelling salesman problem (TSP). The direction optimization was dealt with the convex polygon minimum span method or the step rotation method selectively according to different characteristics of the field boundary. Furthermore, the safety judgment and processing algorithm for the transfer process between different routes were proposed and implemented in order to expand the application scenarios as multiple fields with obstacles whose height influence cannot be ignored. Based on multiple sets of algorithms tests and simulation using both imaginary plots and actual plot boundaries, the results showed that the designed algorithm can process fields of various types of complex boundary with high operational reliability and fast processing speed. The processing time varied from 15ms to 19.2s, and the inter-route transfer distance optimization effect varied from 23.04% to 45.98% when ignoring the obstacles’ influence. And the consumed times were also acceptable when considering height influence of obstacles. The versatility, reliability, efficiency and optimization effect of the algorithm can meet the relevant requirements of agricultural drone operations in fields of all kinds of complex boundaries.