首页 >

基于含障碍物复杂地块凸划分优化的多无人机覆盖路径规划

薛镇涛,陈建,张自超,刘旭赞,苗宪盛,胡贵   

  1. 中国农业大学
  • 收稿日期:2021-06-21 修回日期:2021-09-24 出版日期:2021-10-09 发布日期:2021-10-09
  • 通讯作者: 陈建
  • 基金资助:
    国家重点研发计划

Convex decomposition optimizes multi-UAV coverage path planning in complex plots with obstacles

  • Received:2021-06-21 Revised:2021-09-24 Online:2021-10-09 Published:2021-10-09
  • Contact: Jian Chen

摘要: 全覆盖路径规划是无人系统路径规划的重要内容之一。伴随无人机技术的不断发展,无人机全覆盖路径规划在农业生产、城市管理、军事、地理测绘等领域中已有重要运用。而在无人机对于指定区域进行覆盖飞行时,往往会出现禁飞区和障碍物,若不进行路径规划,则会严重影响飞行安全和工作效率。为此,本文基于凸划分优化,提出了一种针对含有复杂障碍物的复杂地块的全覆盖路径规划方法,减少了覆盖路径长度,降低了覆盖路径总时间。复杂地块往往含有光滑曲线或崎岖的边界轮廓,本文首先采用改进Douglas-Peucker算法,将复杂的地块边界压缩为复杂多边形边界,再用凸凹点检验标记顶点凹凸性。之后通过旋转主线找出最短主线方向,再使用随机路标法(Probabilistic Road Maps)寻找最短的辅线,并采用四种凸划分策略对于复杂地块进行凸划分优化,使得无人机在全覆盖过程中路径更短,工作效率更高。最后,本文对测试地块进行计算机仿真,达到整体路径比67.6%的性能指标,并与其他凸划分优化算法在相同地图上进行比较,验证了本文算法在路径长度以及规划时间上相对更优。

关键词: 全覆盖路径规划, 多无人机, 复杂地块, 复杂障碍物, 凸划分优化, 改进Douglas-Peucker算法, 随机路标法

Abstract: Full coverage path planning is one of the important contents of intelligent path planning for agents. With the continuous development of UAV technology, UAV full coverage path planning has been importantly used in agricultural production, urban management, military, geographic surveying and other fields. When UAVs fly over designated areas, no-fly zones and obstacles will often appear. If path planning is not carried out, flight safety and work efficiency will be seriously af-fected. For this reason, based on convex decomposition optimization, this paper proposes a method to solve the full cov-erage path planning of complex plots with complex obstacles, which reduces the length of the coverage path and reduces the total time of the coverage path. Complex plots often have smooth curves or rugged boundary contours. This article first uses an improved Douglas-Peucker algorithm to compress the complex plot boundaries into complex polygonal boundaries, and then uses convex and concave points to test and mark the vertices. Afterwards, the direction of the shortest main line is found by rotating the main line, and then Probabilistic Road Maps is used to find the shortest auxiliary line, and four convex division strategies are used to optimize the convex division of the complex land, so that the UAV can be in the process of full coverage The path is shorter and the work efficiency is higher. Finally, this paper conducts computer simulation on the test plot to achieve an overall path-to-path ratio of 67.6%, and compares it with other convex partition optimization algorithms on the same map. The algorithm in this paper is relatively better in terms of path length and planning time.

Key words: Complete coverage path planning, Multi-UAVs, Complex plots, Complex obstacles, Convex partition optimization, Improved Douglas-Peucker algorithm, Probabilistic Roadmaps Method

中图分类号: