复杂边界田块旋翼无人机自主作业路径规划

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

针对农用无人机复杂边界田块下的作业问题,提出一种对田块边界形状具有普适性意义的旋翼无人机作业路径规划算法,以快速获得凸多边形、凹多边形、带孔洞多边形甚至多个多边形形式的复杂边界田块情形下的飞行作业轨迹。首先,基于田块边界多边形顶点数据的存储规则,采用多边形分组法,区分所属不同田块的多边形,建立按区域即田块为单元进行航线计算的基础;针对单田块的内、外边界多边形,采用活性边表法实现单个多边形扫描线填充的快速求交解算,得到初始扫描线,再对处于同一航向位置上的内、外多边形两类扫描线组采用线段布尔运算“减法”操作处理,获得预设航向条件下的作业航线;以最小航线间转移路径总长度为优化目标,引入贪婪算法、凸多边形最小跨度法和步进旋转法,综合进行航线排序优化和航向优化,获得不考虑障碍物条件下的完整作业路径。为进一步扩大算法的应用范围,假设田块边界上存在障碍物,且高度大于作业高度,继续增加转移过程的安全性判断及处理算法。针对假想田块和实际田块边界的多组算法仿真试验结果表明,所设计的算法可处理各种复杂边界类型的田块;在不考虑障碍物影响时算法耗时15 ms^19.2 s;相比于只进行航线排序优化的情况,同时进行航向和航线排序优化后,航线间转移路径总长度下降了23.04%~45.98%;而考虑障碍物影响时处理耗时也在离线应用的可接受范围内。该算法的通用性、可靠性、效率和优化效果均可满足各种复杂边界二维田块无障碍物和有障碍物条件下的农用无人机作业的相关要求。

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 15 ms to 19.2 s,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.