无人机调度算法与平台的研究

曾 惜，杨金铎，王 冕，张 羿

（贵州电网有限责任公司 贵阳供电局，贵州 贵阳 550001）

0 引 言

当前无人机技术快速发展，为了更好地发挥无人机的优势并智能精准获取无人机工作区域的图像和视频，必须研究无人机群协同工作调度管理系统。无人机调度是指在多个任务和多个条件制约时，对多架无人机执行飞行任务的航线规划和调度[1-3]。合理安排无人机任务序列可以提高无人机执行任务的效率。随着无人机任务数量的增加和飞行环境的日益复杂，为无人机调度搭建管控平台并进行数学建模调度算法研究是非常重要的。

蚁群算法目前在无人机任务调度和规划中已得到广泛应用，其具有并行性和正反馈机制的特点，可以运用网络的启发信息得到收敛解。此外，蚁群算法可以很容易求解各种组合优化问题，为本文的无人机调度研究提供成熟的理论支持[4,5]。目前大多利用无人机地面站来对无人机进行控制，它能监视无人机的位置和状态等信息，并且能够发出控制无人机飞行与执行任务的命令。为了实现一个地面站同时控制多架无人机，需要设计一种可以进行远程管理与控制的调度平台。

1 无人机调度算法

1.1 无人机调度算法设计

在确定调度中心位置和执行任务点位置的前提下，将无人机派往任务点执行任务。在调度方案设计中，设定每个任务点的任务只能被一架无人机执行，每架无人机能够开展多个任务点的工作，但需要限制其飞行的距离。在飞行时应考虑执行任务的优先级、飞行区域地貌以及禁飞区域等事宜，最终的优化设计目的是让调度方案发挥最大的指挥执行效果[6]。

无人机调度结果的效益评价角度众多，文中主要根据无人机执行任务的效果收益和消耗代价进行评价，以收益尽可能大、付出代价尽可能小为目标。无人机调度算法求解的最终目标为无人机完成任务同时规划出执行的任务序列，令目标函数达到最大，其表达式为：

式中，w1为收益权重，w2为航程代价权重，w3为风险代价权重，R为收益效率，C1为航程代价，C2为风险代价[7]。

收益效率的计算公式为：

式中，xij为决策因子，rj为任务j的优先级，Pj为任务j被分配执行时任务的完成时效，lj为任务j的作业里程数，T为调度方案的总执行时间，V为常量[8]。

在调度中，同一个任务只能由一台无人机执行一次，无人机调度的约束条件公式为：

无人机正常工作时，会遇到众多不利于安全飞行的因素。如何消除不安全因素的威胁是亟待解决的问题，因此在方案制定时，在规划空间里要表示清楚所有存在的安全威胁，以获得威胁区信息，进一步分析得到最合适的路径。用圆形区域表示禁飞区等威胁区域，圆的半径r代表威胁源的影响距离，圆心O代表威胁源。离圆心越近，威胁越大，而且各个威胁区域之间互不干涉。模型图设计如图1所示。

图1 无人机威胁区域模型图

1.2 无人机调度求解

目前无人机调度求解主要有两种算法，分别是精确算法和启发式算法。由于精确算法是采用庞大的计算量来获得最优解，因此并不适用于无人机调度。而启发式算法可以解决计算量大的问题，非常适合用来求解调度问题。启发式算法的流程为先获取无人机调度的初始解，然后运用优化策略进行局部扰动，为了搜索获得更优的解，需经过多次循环，一直到搜索到最优解为止。由于蚁群算法具有组织性、鲁棒性以及正反馈机制优势，其在任务中可较快的搜索到更优解，因此主要针对蚁群算法展开研究。

1.2.1 蚁群算法概述

相关研究表明，蚂蚁能释放一种信息素。受信息素的吸引，蚂蚁可以发现一条蚁穴到食物的最短路径。这样蚂蚁往返的时间就会减少，同样的时间内，留在路径上的信息素会增加，较短路径上的蚂蚁也会随之增加。在正反馈的作用下，可确定出最优路径。对蚂蚁觅食过程的仿真模拟是该算法的核心，其关键是人工蚂蚁对已经访问的节点不会重复，还能根据反馈信息调整，意识性较强。

1.2.2 蚁群算法求解无人机调度问题

对于无人机调度，一只蚂蚁代表一个可行解。无人机从基地起飞，按照约束条件选择任务，完成首次任务后进行下一项任务，直至没有符合约束条件的任务为止，这样就得到了一个无人机的航线。再出动另一架无人机，重复上述步骤，完成所有的任务，就获得了一条完整的路径。选择任务点时，在任务点集allowk中放入符合约束条件的任务点，再从allowk中根据相应规则选择，规则如下。

首先，选择信息素矩阵τ，将τ=ones(n,n)初始化，n代表的是任务集合的总数。

其次，启发信息矩阵η，η中的元素为ηij=rj/dij，其中rj为任务j的优先级，dij为任务i到任务j的距离。

再次，在可选任务点集allowk中放入t时刻符合约束条件的任务点，求解t时刻对应的allowk中各任务点的状态转移概率P，公式为：

式中，α为信息素的重要度，β为可见度的重要度。

最后，按照伪随机比例规则，选择下一个要执行的任务点。

1.2.3 蚁群算法求解调度问题的算法步骤。

（1）将算法中的α、β信息素矩阵以及聚类算法与遗传算法的各个参数初始化，放置m只蚂蚁在无人机出发点[9]；

（2）任务j由无人机续航时间t、任务优先级以及禁飞区域等约束条件确定，将其放入可选任务集allow中；

（3）按照伪随机比例规则，进行下一个要执行的任务点；

（4）对还没有执行的任务点集合to_visit进行更新；

（5）若allow不为空，则跳至执行步骤（3），选择下一个任务点，否则执行下一步；

（6）若to_visit不为空、allow为空，表示尚有任务未被执行，但剩下的任务点均不符合约束条件，则返回步骤（2），直到to_visit为空后再进行下一步；

（7）记录每只蚂蚁所获得的调度路线和目标函数值，求得最优解；

（8）采用混合聚类技术判断，并依据蚂蚁状态对α、β值进行调整；

（9）迭代次数I加1；

（10）若I

2 无人机的管控平台

无人机管控平台设计时要思考各个方面的技术需求，当无人机接收到上传的航线信号后，开始起飞执行任务，平台需要对无人机的实时位置、飞行速度、航线、飞行姿态、电池的电压以及GPS状态等进行管控。为了同时管理大量无人机，需要在平台上进行注册。

无人机平台的需求包括两个方面。一是该平台可完成无人机注册，可查看无人机资料信息；二是该平台可实现航线任务的管理。通过无人机平台预先设定好航线，然后上传到无人机。当无人机执行任务时，平台可对无人机的航迹，飞行姿态、电池电压、GPS状态以及实时报警等信息进行实时监控，同时具备存储功能，可以记录飞行数据。为了实时播放和回放航拍视频，该平台需具备视频播放、可实现发送起飞或降落等指令的功能。

2.1 平台功能结构设计

根据无人机任务需求，从功能结构上将无人机管理控制平台划分为用户登录、无人机管理、航线管理、视频管理以及指令控制5个模块。

2.1 用户登录

用户登录模块是系统的首要环节，通过输入用户名和密码传输至后台服务器进行校对。

2.2 无人机管理

无人机管理模块主要包含无人机注册和信息查看，注册内容有名称、产品序列号、型号、身产日期以及管理人员信息等。无人机信息查看可以用表格的形式表示，可以对每条信息编辑或删除，并且可以查询出需要查找的无人机。

2.3 视频管理

视频管理包含实时视频管理与历史视频管理，可以切换1个画面、2个画面、4个画面、9个画面或者16个画面，可任意调取历史视频进行查看。

2.4 航线管理

航线管理有3个子模块，分别是预设航线、上传航线以及下载航线。通过在地图上画线，设定航线，可以进行保存和上传。通过蚁群算法求解无人机调度问题之后，获得无人机的调度路线，将路线描绘在地图上，形成无人机的航线。

2.5 指令控制

无人机控制指令有起飞、悬停、继续飞行、降落、返航以及巡航等，每个指令均是基于UDP协议的Socket通信进行的。UDP是通过在通信实例两端各搭建一个Socket对象实现收发数据报的。DatagramSocket对象是基于UDP协议的Socket，使用DatagramPacket可以代表DatagramSocket进行数据报的发送和接收[10,11]。

3 结 论

本文在无人机调度算法的研究中使用了蚁群算法，提高了算法的计算速度和搜索水平，实现无人机调度问题最优解。但是研究的调度问题是静态的，实际的任务点可能会出现动态变化，这也是未来需要深入研究的重要课题。此外，多种型号无人机的调度问题需要加入到约束条件中。未来需要加强对无人机调度与管控平台充分结合的研究，实现直接在平台中计算得到无人机调度方案，根据结果选取适合的航线，使无人机调度系统优势更加明显，能够更高效地完成任务。