多无人机协同覆盖路径规划的算法设计

摘要

伴随着无人机技术的不断发展，无人机受到研究人员越来越多的重视。由于能源约束以及问题规模等方面的因素，多无人机协同系统成为了主要的研究内容。无人机所执行的任务很大程度上都可以归类为扫描覆盖任务，为了提高任务完成效率往往需要进行路径规划方面的算法研究。针对上述情况，本文主要研究了基于多无人机协同系统的三种覆盖问题:矩形区域覆盖问题，多边形区域覆盖问题及离散点扫描问题。
　　首先，本文研究了面向矩形区域的多无人机协同覆盖路径规划问题。在对问题进行网格化处理之后，通过集中式控制无人机的移动方式，设出了一个最坏情况下近似比为2的集中式算法RCA，并且对算法的实际性能进行了实验模拟。
　　然后，通过对上述集中式算法规划的路径进行模拟，采用制定规则的方式，设计出了相应的分布式算法RDA。之后将这个分布式算法拓展到多边形区域，得到可以处理多边形区域的分布式覆盖算法PDA。实验模拟结果验证了两个分布式算法在减少无人机编队移动代价上的有效性。
　　最后，本文考虑更为一般化的场景，对于现实场景中的离散目标点的扫描问题进行建模。针对离散目标点的扫描任务设计了两种无人机编队扫描算法(中心扫描算法CSA与平行扫描算法PSA)，用以最小化无人机编队的扫描距离。两种算法均采用迭代扫描的思路扫描目标点的集合，通过构建凸包的方法对目标区域进行划分。实验结果验证了两种算法在最小化无人机编队移动距离方面的高效性能。

目录

声明

摘要

第一章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．3 研究目标

1．面向矩形区域的多无人机协同覆盖问题的集中式算法

2．面向多边形区域的多无人机协同覆盖问题的分布式算法

3．面向离散目标点的多无人机协同扫描算法

1．4 论文组织结构

第二章 面向矩形区域的集中式算法

2．1 系统模型与问题定义

2．2 矩形区域集中式算法RCA

2．2．1 算法整体思想

2．2．2 区域单向扫描算法

2．2．3 区域分块往返扫描算法

2．2．4 算法近似度分析

2．3 实验模拟与性能分析

2．4 本章小结

第三章 面向多边形区域的分布式算法

3．1 系统模型与问题定义

3．2 矩形区域分布式算法RDA

3．2．1 算法思路

3．2．2 矩形区域的分布式算法RDA

3．3 多边形区域分布式算法PDA

3．4 实验模拟与性能分析

3．5 本章小结

第四章 面向离散目标点的覆盖算法

4．1 系统模型与问题定义

4．2 中心扫描算法CSA

4．2．1 区域划分方案与整体扫描方案

4．2．2 单次迭代区域扫描算法CSTA

4．3 平行扫描算法PSA及最优解下界

4．3．1 平行扫描算法PSA

4．3．2 最优解下界分析

4．4 实验模拟与性能分析

4．5 本章小结

第五章 总结与展望

5．1 工作总结

5．2 工作展望

致谢

参考文献