基于运货无人机复用的大规模城市感知的算法设计与实现

作     者：周彦霖 

作者单位：重庆大学 

学位级别：硕士

导师姓名：向朝参

授予年度：2022年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 082503[工学-航空宇航制造工程] 0835[工学-软件工程] 0825[工学-航空宇航科学与技术] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：城市感知 移动群智感知 无人机 能量利用效率 任务分配 

摘      要：城市感知获取城市的数据,并根据作出相应的调整,能够极大提高城市效率并改善人们的生活。当前城市感知的研究大多基于车辆,但是车辆受到道路交通的极大限制。与之相比,无人机具备三维空间运动能力,具有巨大优势,也因此受到快递运输的青睐。运货无人机数量的快速增长,令其成为一种潜在资源。同时,无人机能够适配各种传感器,可以用来收集感知数据。如果对运货无人机进行大规模的有效利用,能够使其在大规模低成本城市感知领域展现非凡的价值。与此同时,与车辆感知相比,无人机受到电池容量的极大限制,因此还需要对能耗进行合理的规划,才能有效利用这一新兴的工具。通过众包的方式,复用现有的运货无人机这一可观的资源,可以节省大量的无人机部署和维护费用。此时,除了能耗以外,还需进一步考虑如何平衡运货无人机本身的运货任务以及感知任务之间的关系。基于这一想法,本文开创性地提出通过复用现有的大量运货无人机来进行城市感知,填补了相应研究领域的空白。通过研究分析无人机飞行、感知过程,以及无人机载重的相关性,本文构建了一个综合考虑路径选择、感知时间分配、载重分配的联合优化问题,即在无人机电池容量和感知预算约束下,实现运货收益和感知收益的最大化。通过数学分析发现,这是一个混合整数非线性规划问题(MINLP),属于经典的NP-hard问题。由于问题非常复杂,本文首先提出目标函数等价转化策略Alg.1对问题进行解耦。对转化问题的目标函数和约束条件进行深入的数学分析发现,这是一个受划分拟阵约束的子模优化问题。在这一基础上,本文提出近似最优算法RT-Drone和RTW-Drone,主要包括目标函数等价转化策略,局部搜索策略,以及迭代联合优化策略。然后,本文通过深入的理论分析,阐述了所提算法的原理,并证明了在无人机固定重量情况下,RT-Drone能够在多项式时间复杂度O((IJ)2K lg(K))内获得1/(4+ε)的近似最优解(其中ε为任意小的正数);并且证明了在可调节载重的情况下,RTW-Drone算法能在多项式时间复杂度O(N(IJ)6K lg(IJ)lg K)内收敛。最后,本文进行了大量基于实际数据集的大规模仿真,并搭建一台四旋翼无人机,进行了一系列小规模的实地实验,实验结果表明所提算法不仅能提高124.7%的运货收益和感知收益,还能提高72.2%的能量利用率。