无人机组群巡检灭火系统设计【毕业论文+CAD图纸全套】

买文档就送您 纸全套， Q 号交流 401339828 或 11970985 本科毕业设计 题 目： 无人机组群巡检灭火系统设计 学 院： 机电工程学院 专 业： 机械设计制造及其自动化 姓 名： 学 号： 指导教师： 2016 年 5 月 28 日 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 摘 要 随着无人机执行任务的环境日益复杂，任务类型日益多样，无人机己经开始 从单架次独立任务的方式向着多架次、多类型的机群作战方向发展。通过对多无 人机协同任务分配的研究，可以使系统完成的任务类型更为多样，同时任务完成 的质量和效率也获得较大程度的提高。 本文研究了集中式多类型无人机编队任务分配方法。集中式指的是任务分配 过程中，无人机处于从属地位，不具有自主能力，完全受控制站中人的控制。多 类型指的是无人机类型和执行能力的不同。 本文首先介绍了无人机的应用现状，讨论了几种任务分配算法 ，分析了他们 的优缺点。其次，在静态环境下基于平面网格坐标系，建立了一个多无人机任务 分配数学模型，设计了一种有人参与的静态分配算法。然后利用了一个无人机森林灭火的实例，通过 后，在动态环境中，根据无人机状态改变和任务改变两种情况，对动态任务进行了动态重分配。 关键字 :无人机；任务分配；静态分配；动态重分配 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 1 of AV AV of of of of in AV to in is in a do of in AV to of of of s in a on we up a a an of of by to or to in 文档就送您 纸全套， Q 号交流 401339828 或 11970985 2 目 录 第一章 绪论 . 37 务分配的研究背景 . 37 内外无人机应用现状 . 37 用在军事上 . 37 用在自 然灾害的防护上 . 37 文的主要内容 . 37 文组织结构 . 37 第二章 无人机任务分配问题研究现状及发展趋势 . 37 人机任务分配问题的定义及解决步骤 . 37 务分配问题的定义 . 37 务分配问题的描述 . 37 决 务分配问题的步骤 . 37 人机任务分配控制方法 . 37 中式控制 . 37 布式控制 . 37 人机任务分配模型分类 . 37 旅 行商问题模型 . 37 用分配问题模型 . 37 辆路径问题模型 . 37 合整数线性规划模型 . 37 用模型 . 37 态任务分配算法 . 37 算法 . 37 场类算法 . 37 化理论算法 . 37 态环境中多任务重分配算法 . 37 同网算法 . 37 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 3 卖算法 . 37 类算法 . 37 第三章 静态环境下无人机任务分配 . 37 务分配场景和限制条件 . 37 务分配的场景 . 37 务分配限制条件 . 37 无人机任务分配的数学模型 . 37 人机任务集描述 . 37 面网格坐标系 . 37 第四章 动态环境下无人机任务分配 . 37 态任务重分配 . 37 态任务重分配的触发条件 . 37 务动态再分配采用的策略 . 37 务重分配的流程 . 37 务动态再分配需要考虑的因素 . 37 务改变时的任务动态再分配算法 . 37 人机状态改变时的任务再分配 . 37 结 论 . 36 参考文献 . 36 致 谢 . 37 第一章绪论 务分配的研究背景 无人机 (指由远程遥控或自主控制操作的无 人驾驶的飞机。采用无人驾驶的方式使飞机摆脱了驾驶员自身生理条件的限制， 能够完成一般飞机不能完成的任务。无人机具有重量轻、维护成本低、机动性能 高等明显优势，同时无人驾驶的方式使操作人员远离危险的任务环境，极大地降 低了操作人员的危险程度。 同 任务规划是现代战争中提出的新课题。随着无人机的出现，利用无 人机执行任务逐步成为了现实，目前 同任务规划得到了越来越多的关注， 因为尽管单无人机可以无需合作完成某个环境的搜索，但是一个更有效的搜索需 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 4 要合作来减少重复覆盖，通常多无人机任务规划可以分成两大部分 :上层的任务 分配 (下层的路径规划 (任务分 配考虑各种约束条件，以总体任务有效达成为目标，将具体目标和行动任务分配 给各机，而各机根据分配的任务再 进行具体的作战路径规划。路径规划的功能是 在满足如最大线性速度、最大转角速度、操作的安全性、时间和环境变量等自身 或外部限制的前提下在一系列位置之间设计或生成路径。本文我们主要讨论 务分配问题。 1. 2 国内外无人机应用现状 1. 2. 人作战飞机 (的是无人机携带武器或者弹药，可对地面目标进行攻击 和轰炸。在军事发达国家，尤其美国、英国以及法国对无 人作战机研究深入，美 国对于无人机任务分配问题在军事上的研究最为深入，在上世纪 70 年代就开始对 无人机任务分配问题进行描述并进行实际应用。在越南战争，海湾战争以及北约空 袭南斯拉夫等过往战争中，无人机经常用于执行一些人不能完成的军事任务。在这 些战争中虽然无人机不是主要执行任务的飞机，但它却成了决定战争导向的决定 因素之一。由于无人机的无人驾驶特点，可以被派往危险的环境中执行一些人不能 执行的任务，因而成为重要的军事力量受各国关住。无人机可以用来完成对战场实 时的侦察和监视、对目标位置的确定、任务目标的评估 、电子对抗等。无人机最 早的开发是在第一次世界大战之后。到了第二次世界大战后，很多军事实力较强的 国家将退役下来的飞机进行改装，使人与飞机脱离，这样就促成了近代无人机的 发展。随着信息化技术的发展，无人机在执行侦察任务的过程中的作用越来越明 显。例如，在越南战争期间，美国就大量使用无人机对价值较高的军事设施和通信 设施进行预先侦察。无人机不仅仅应用于侦察，还应用在具体的作战任务执行中。 在对阿富汗的战争中，美国“捕食者”无人机首次发射“海尔法”导弹击中地面 目标，打破了无人机传统的作战保障角色，使之成为一 种作战兵器 1982 年以色列 航空工业公司首创的无人机能进行侦察、信息收集、跟踪和相互通讯等。 1991 年， 海湾战争中，美国军方己经推出了特别设计的，具有雷达系统的小型无人机为诱 饵，这种无人机在其它国家也进行了一些研究。无人机在海湾战争之后很快的发 展起来并在很多任务中应用。以美国为首的西方国家要为了增加对实现无人机在 战争的作用，将最新的高科技技术应用到无人机的研究和开发当中去，不仅增加无 人机飞行时间，提高了图像，文字等信息的传输速度，还考虑了无人机具体的避开 危险区域能力，以顺利完成任务。 和美国等西方国家相比，我国的无人机研究水平差距还是很大。虽然国内从 80 年代末开始，对路径规划问题进行过许多研究，发表了许多论文，但大多数的 文献仅仅是对单无人机所进行的路径规划问题的研究，目的是避开无人机在飞行 过程中遇到的危险区域，很少有关于无人机任务分配问题解答的研究成果。当前 我们国家无人机反的研究还处在起步阶段。由于我国的无人机功能简单，自主能 力较差，需要地面控制站进行任务分配的规划。而当前的无人机发展趋势是无人 机的智能化，将无人机看成一个个智能体，我国在这方面的研究成果很少。功能 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 5 上也只能进 行简单的图像，数字传输，任务分配、路径规划的能力很差。尚不具 备执行复杂战术任务的能力。近年来我国的国防科技大学、西北工业大学等高等 院校和科研单位在无人机任务分配问题上也进行了一些理论分析和实际问题的研 究，可以说取得了不错的成就。但从现阶段己经得到的理论和实际成果来看，目 前我国对无人机任务分配问题的研究还处有很多不足和局限。例如无人机的自主 性较差，无人机的决策大都是由地面控制站决定的。对于无人机所处的动态环境 考虑不足，无人机的尺寸、时间窗函数等考虑较少。 2. 2 应用在自然灾害的防护上 和平和发展当今世界的两大主题，所以无人机的应用也由军用慢慢转向民用。 其中最主要的民用用途是在自然灾害的防护上。 2001 年以来，世界各国都在大力 发展各种用途的无人飞行器。目前世界上 32 个国家己研制出了多种无人机。美国、 以色列、俄罗斯、北约等国家非常重视多用途无人机的研制、生产和应用。森林 火灾的现场温度高，对飞机的抗热性能高。现场的烟尘大，能见度不高，尽管有 人飞机能飞至火场上课，飞机中的人也不能清除地了解火场当前的具体情况。这 时无人机的优势就体现出来，通过在无人机上配置摄像机和数字图像传输设备， 可轻易完成对火场的侦察，灭火和灭火评估。美国航天局最新研制的无人灭火机 “工 这款无人灭火机由“捕食者 B ()改进而来。“捕食者 B”原本是美国空军用于战时监视和侦察的，现在它的改进版“工 用作另 一个领域，那就是森林灭火。在火场中，由于火势的动态性和不确定性以及协同 控制的复杂性，使得任务开始后出现许多无法预料的情况，必须根据火场火势和 编队状态的变化快速调整 队的任务计划，通过动态重调度实现任务的重分 配。 我国也有无人机应用在灾害防护上的 实例 实例描述了无人机在国内地震 中的应用。重大自然灾害如地震、水灾、冰雪等具有突发性强、灾害范围广、破 坏性大特点，往往会造成重灾区信息通讯中断和道路交通破坏，灾情信息不畅将 导致抢险救灾盲目部署，继而造成更大的损失和次生灾害。 2008 年汉川 8.。 级地震，极重灾区北川县城出现大范围建筑物倒塌和重大人员伤亡，通讯和交通 系统遭到毁灭性破坏，传出特大灾情己是震后的第 2 天，在亲历和目睹汉川地震 抢险救灾过程之后，全社会己经取得共识，通过各种手段有效获取灾情是开展重 大自然灾害抢险救灾首要问题。汉川 地震之后，在我国有一些单位应用无人机获 取遥感图像，进行震害分析，做出了探索性工作。无人机组定位于获取高分辨率 图像，进行灾害识别并直接应用于抢险救灾。无人机组在北川县曲山镇等地进行 了地震灾区实验，并在 2010 年玉树地震抢险救灾工作中成功实现了高原灾区首次 航空摄影，获取的高清影像为划分灾区范围提供了重要的依据。本文我们着重讨 论无人机在森林还火灾中的应用。 1. 3 论文的主要内容 无人机如何在复杂的环境中顺利地完成所需执行的任务，并且能够使得任务 执行的效率最高，收获的利益最大，付出的代价最小 ，是多无人机任务分配所要 考虑的问题。本文的主要工作是通过对各种任务分配算法的研究，引出了一种有 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 6 人参与的多无人机任务分配算法并进行了理论研究和仿真分析。主要步骤是 :首先 建立了一个任务分配在森林火灾防护的应用场景，设置了关于实际问题的限制条 件，然后建立了一个基于六元组的任务描述，使用了平面网格坐标系对任务分配 问题进行建模，在以上的基础了最后利用了一个无人机森林灭火的实例，通过 真结合算法说明了该算法的可行性和实用性。因为无人机任务分配所 处环境是动态的，所以对动态环境下无人机任务重分配问 题也进行了一些算法研 究和实例分析。 1. 4 论文组织结构 本文主要介绍多无人机的任务分配算法，在介绍了传统的任务分配的算法的 基础上，分析了它们的优缺点，引出了一种有人参与的多无人机任务分配算法， 为无人机的任务分配算法提供了新的思想。并结合了一个无人机在森林灭火中的 应用实例，利用 行仿真研究。 第一章 :绪论。介绍了论文选题的背景，国内外无人机任务分配的应用现状。 简述了论文的主要内容以及论文的组织结构。 第二章 :无人机任务分配的现状及发展趋势。首先给出了无人机任 务分配问 题的定义并对无人机任务分配问题进行了描述。其次，说明了解决任务分配问题 的基本步骤，包括任务分配数学模型的建立和具体算法的设计。然后介绍了任务 分配的体系结构和当前几种任务分配模型，接着介绍了几种静态任务分配算法和 动态任务分配算法并分析了它们的优缺点。最后指出了当前无人机任务分配方法 研究存在的一些问题。 第三章 :讨论了静态环境下无人机任务分配问题。首先建立了一个无人机森 林灭火的应用场景，设置了一些限制条件。在此场景下设计了一个六元组的任务 描述并使用平面网格坐标系完成了对任务分配问题 数学模型的建立。其次，设计 了一种有人参与的多无人机任务静态分配算法。最后应用一个无人机森林灭火的 实例，通过 真分析，验证了该算法的可行性和实用性。 第四章 :讨论了动态环境下无人机任务分配问题。介绍了动态任务再分配的 触发条件，动态任务重分配采用的策略以及任务动态再分配需要考虑的因素。分 别考虑任务改变、无人机状态改变这两种触发条件，设计了两种新的动态任务再 分配算法。结合第三章的无人机森林灭火的实例，通过 真分析，验证了 这两个算法的可行性和实用性。 第五章 :总结 与展望。总结了本文的主要研究工作，指出了论文中的不足之 处，并对今后的工作提出若干自己的想法。 第二章无人机任务分配问题研究现状及发展趋势 2. 1 无人机任务分配问题的定义及解决步骤 2. 1. 1 务分配问题的定义 务分配问题可以定义为 :在己经完成 队分组的基础上，基于一定 的环境和任务要求，为编队中的 配一个或多个有序任务，以便在完成最大 可能任务的同时，使得 队的整体效率最高。 我们结合图 2. 1 这个简单的例子来直观地了解任务分配问题的具体含义 :首 先设置了任务集和无人机集 :其中包含了四个待执行任务，无人机编队由两架无 人机组成。然后设计具体的路径和任务执行顺序来完成所设定的四个任务。图中 每个带箭头直线上的数字表示无人机在该段航路上所花费的时间，四个任务用四 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 7 个圆圈来表示。圆圈中上半部分的数字表示的无人机任务集中任务的序号，下半 部分的数字表示完成这个任务需要的具体时间。最后虚实线表示的是任务分配的 具体的方案。无人机分别沿着制定的虚线完成四个所设定的任务，通过这种方法， 花费时间要明显小于单架无人机。 2. 1. 2 务分配问题的描述 给定一个 队 U，它包含数目为 N 二的无人机， v 一 . . 简化 问题，假设 队在一个二维空间执行任务，在任意时刻 t，无人机 U，的位置为 (tt)。每个 假设为质点。同时，在任务区域内包含有限数目的待 执行任务，组成一个任务集 T 一仁 . . N:为任务的数量，包含唯一的任务 应水平位置为 (对了 )但不同的任务允许有相同的水平位置 23。在任务分配 前，以上的信息都是己知的。 务分配的结果是为编队中的任一无人机 U，分 配一条任务执行路线 P，有 : x ,y , xM ,yM)， (2 一 ) 其中， (O,0)表示无人机 U，的出发位置，也就是说，对应无人机 U; 需要市。定一个有序任务集。 ;一 .,界。 。 任务分配的一般原则如下 : (1)优先分配价值高的一般原则 ; (2)将目标分配给对其最有利的 (3)在尽可能短的时间内尽可能多地访问目标，并保证 队飞 行总路线 最短 ; (4)参与任务的各 任务负载尽可能均衡。 2. 1. 3 解决 务分配问题的步骤 无人机任务分配方法的求解主要分为两方面 :任务分配模型的建立以及具体 的任务分配算法的设计 : (1) 务分配的数学模型的建立 要对无人机进行数学建模，首先要对无人机所处的空间环境进行描述和表达。 通常我们以一个二维或者三维的变量来定义一个无人机和目标点的位置，为简便， 一般采用二维变量。得到了无人机和目标点的位置，就能得到任一无人机的任务 执行路线。然后我们设计一个 二值决策变量，如果无人机完成某个任务，二值变 量就为 1，如果不完成那个任务，二值变量就为 0。然后要设定无人机任务分配的 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 8 约束条件，如无人机最大航程、任务时间窗约束、任务执行的先后顺序、无人机 的载荷等。 (2) 务分配算法的设计 完成了对无人机任务分配的数学建模，我们就要来设计具体的算法。设计算 法我们首先要根据以往的算法和基本概念提出算法得出的理论依据，然后决定算 法的搜索策略，以较快较好为准则，确定算法的搜索策略。因为无人机分配问题 要用计算机进行运算仿真，必须对算法进行编码 ，所以得设计算法的编码和解码 方式。还应设计一个评价函数，来评价任务分配方案的好坏，我们称其为适应度 函数。适应度函数要考虑的实际因素主要包括 :任务完成的时间最短，任务分配 方案得到的收益最高以及无人机消耗能力最小。最后，我们还要对算法进行性能 分析，包括算法能否得到最优任务分配方案，算法的效率以及算法的实时性。 2. 2 无人机任务分配控制方法 由于无人机执行任务环境是动态的，不是固定不变的，所以无人机的任务分 配控制方法也应该根据不同的任务环境而区别对待。无人机任务分配控制方法选 取对无人机执行任 务的效率和质量有很大关系。任务分配控制方法的选取应该考 虑以下几个因素 :任务完成的快速性，任务的实时性，任务分配的计算时间和计 算复杂度，抗干扰能力等。无人机任务分配控制方法主要可以分为集中式控制 28 (及分布式控制 (两种。 2. 2. 1 集中式控制 在集中式控制方法中，由地面控制站中的操作人员制定任务分配方案和无人机 具体的飞行航路，无人机本身不具备决策能力，完全按照地面控制站发出的任务 指令和航路执行任务。图 2. 2 表示了集中式体系结构图 28: 在这种控制方式下，各无人机之间的协同控制存在以下问题 : (1)实时性差 因为无人机本身不具备决策能力，所以地面控制站中的操作人员要根据无人 机编队通过数据传输返回的无人机状态信息，任务状态信息以所处的环境信息等， 对任务分配问题进行具体的决策。无人机编队与地面控制站保持着联系，当返回 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 9 的数据量很大时，有可能地面控制站收到的信息是不全的或者是错误的，导致决 策错误。地面控制综合这些信息速度较慢，导致决策较慢，实时 性差。 (2)计算时间长，算法复杂度高 对于集中式控制方法，地面控制站对所有的无人机传来的数据信息进行总结 和分析，信息都集中在任务控制站中，解决问题的具体计算过程复杂，计算信息 多，导致完成任务分配的计算时间很长。对于多类型任务的无人机编队，例如无 人机编队中无人机能够执行任务种类的不同，无人机执行任务能力不同，此时更 凸显了这个问题的严重。 (3)抗干扰能力较差 由于地面控制站往往只有一个，如果在具体任务执行过程中，地面控制因为 某些特定因素遭到毁坏甚至瘫痪，将造 成的损失是巨大的。同时无人机编队中的 无人机失效或者发现新的任务目标，在原有基础上的再分配也是很相当复杂的。 布式控制 区别于集中式控制方法，分布式控制方法中无人机编队中或者无人机编队之 间的无人机是具有独自决策能力的智能体，它们具有很强的协同能力和自治性。 无人机之间以数据链技术为支撑，对无人机所处环境，任务目标集信息，无人机 状态信息进行交互，综合考虑各种因素，提出具体的解决任务分配问题的方案和 具体步骤。较之于集中式控制方法，无人机个体在分布式控制方法下具有较强的 实时性，抗干扰能 力，计算量小，计算复杂度小等优点。当前，分布式控制方法 主要可以分为两种 :完全分布式控制方法和部分分布式控制方法。 (1)完全分布式控制 完全分布式控制方法是一种依靠无人机的自主性和相互协作的一种方法，由 于无人机任务分配问题的复杂性，该方法相当于将复杂的问题分解成为一个个相 对简单的小问题，对每架无人机进行任务分配，接着就是将各个无人机的信息进 行交互，对任务进行整体求解。如图 2. 3 所示，完全分布式控制方法中我们把无 人机看成具有决策能力的智能体，这样无人机任务分配问题就转化成为各个智能 体之间任务的分配和决策。在这种结构中，无人机相对于集中式控制有很强的自 主性，能够对任务集信息和自身的信息进行采集和分析，并进行决策，在特定的 情况下通过数据链与其它无人机进行数据交互，协作完成所需执行的任务。 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 10 图 全分布式控制结构图 这种控制方法中，无人机编队内各个无人机对所得到的信息进行相互的共享， 得到所有的关于任务执行的信息，最后整理分析所得到的信息对无人机编队中的 每一架任务分配任务集。由于无人机编队中有多 架无人机，在执行任务中可能发 生交叉冲突，即碰撞冲突，所以需要对它们进行考虑并消除。同时在这种控制方 法中，无人机之间是通过数据链技术进行任务集数据的传输和共享，为的是更好 的具有任务决策的实时性，所以数据量是相当大的，将随着编队内无人机的数量 呈指数增长。所以应用这种控制方法，编队内无人机的个数受到了很大的限制。 (2)部分分布式控制 部分分布式控制方法吸取了无人机任务分配控制方法中集中式控制和完全分 布式控制方法各自的优势，对于解决多类型无人机编队任务分配问题更为合理。 经过对集中式控制 方法和分布式控制方法的比较，我们得出分布是控制方法是一 种实时性较强的方法，能够快速的对任务信息进行采集和分析，得到解决任务分 配问题的具体方案，获得的方案往往是局部最优的，但不能得到全局最优方案。 而集中式控制方法恰恰相反，由于所有信息都要返回地面控制站进行汇总，所有 能够进行全面而详细的规划，从而获得的方案一般都是全局最优方案，但是实时 性就很差啦。当前，国内外很多院校和科研机构对集中式控制和分布式控制方法 结合的问题进行了理论分析和实际验证，对两种方法进行了整合，得到了部分分 布式控制方法，结构图如图 2. 4 所示。 在部分分布式控制方法中，地面控制站中的操作人员对无人机返回的信息进 行归纳和分析，在静态环境下给无人机编队中的每架无人机都设计了初始任务分 配方案。在动态环境下，例如无人机状态的改变，任务的改变将导致任务的再分 配。此时，无人机编队中的无人机发挥自己的自主性，重新对任务目标信息采集 并分析，在编队中与其它无人机进行信息的共享和交互。地面控制站中的操作人 员在某些特定的时候对无人机编队发送任务指令，大部分时候依靠的是无人机编 队自身的协同分配。主要既提高了实时性，又大大减小了 地面工作站的任务量， 得到的任务分配方案也是相对合理的。部分分布是控制方法对集中式控制和分布 式控制方法进行取长补短，体现了人们的智慧，具有较强的实际应用意义。 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 11 2. 3 无人机任务分配模型分类 根据任务分配建模分类，现阶段的模型主要有多旅行商问题 2(模型，通用分配问题 3(型，车辆路径问题 4(型，混合整 数 线 性 规 划 s,6,s,9( 型以及 型。 2. 3. 1 多旅行商问题模型 通常，我们所说的旅行商问题是一个 全问题，具的定义如下 :假设有 a 个旅行商人，方个城市，每个旅行商人都要沿着城市之间的道路访问其中的一些城 市，最后所有的旅行商人都要返回初始的 城市，限制每个城市都要被访问并且有 且仅有一次，问题所要达到的目的是在完成对所有城市访问的同时，总距离最短、 完成任务时间最短、消耗最小、收益最大等。把旅行上问题模型应用到无人机任 务分配中去，我们假设有一个二架无人机的无人机编队，有二个目标任务的任务 集，无人机编队从同一个基地出发，沿着预先设定的飞行航路，完成所有的任务， 每个任务只能被完成一次，最后考虑无人机的总航程，无人机完成任务的时间， 无人机消耗的能力，完成任务的价值利益等。 2. 3. 2 通用分配问题模型 通用分配问题模型考虑将二个任务分配给二 个单体，每个任务只能给一个单 体并且单体的资源受到限制。相当于二个任务分配给 给一个无人机执行并且无人机的资源，如最大任务数， 二个无人机，每个任务只能 最大航程受到限制。 2. 3. 3 车辆路径问题模型 我们对车辆路径模型进行如下描述 :假设有二辆货车，每辆车的负载能力不 同，它们从同一个基地出发，为二个目标点输送货物，每个目标点需要送达的货 物数量不同。最后，所有货车回到出发点。车辆路径问题模型 考虑送达的时 间，货物送达的消耗，完成输送的价值等，并保证所有的货物安全送达。 2. 3. 4 混合整数线性规划模型 混合整数线性利用线性化函数建立模型，模型描述简洁、直接，有助于提高 无人机任务执行效率和生存能力，达到了任务分配的目的和初衷而且可以通过对 约束条件的修正来满足实际问题需要，但是模型规模不能过大。问题规模过大将 导致计算量指数型增长，任务分配的实时性得不到保证。 2. 3. 5 用模型 随着无人机能力不断增强，无人机执行任务的复杂程度也随之增强，不同任 务之间存在着复杂的时序以及时间约束。对于这一类复杂的任务集合，目前大多 数任务分配模型无法对其进行有效的描 述。一种 型川被引出，这种模型 充分考虑一组无人机完成一系列针对地面目标的连贯任务，包括任务目标的识别、 攻击、毁伤评估等。 2. 4 静态任务分配算法 在静态环境中，无人机和任务都是确定的，不发生改变。在这样的条件下， 多无人机任务分配的算法主要有 :群算法，市场机制算法和进化算法。 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 12 2. 4. 1 群算法 群算法主要模仿自然界中各种生物的群体化行为，例如虫群 12和羊群。我们 通过对虫群群体化行为就行具体的研究分析，从而来简单说明群算法的具体特点 : 所谓的昆虫群的群体行动指的是昆 虫个体根据一些规律进行个别的运动，从而导 致整个群体显现出一种运动规则，在运动中昆虫主要遵循三个准则 :第一，实时 监测与邻近个体距离，防止产生交叉冲突，即防止和其它个体产生碰撞 ;第二， 采集邻近个体的信息，如速度，位置等 ;第三，保证和其它昆虫的距离，不能太 远，而脱离群体。昆虫以上的这些行为都是个体的行为，不是群体的运动，不过 所有的个体都执行这些准则，就会产生整体的运动趋势。群算法中目前为止最为 经典就是蚁群算法 13,14,15,16 (, 1991 年，意大利科 学家 先在其发表的研究成果中提到了蚁群算法。蚁群算法遵循的基本规 则是 :模仿生物界中蚂蚁群体寻找食物的行为，蚂蚁在寻找食物的时候，一般都 能够在经过的路径上分泌并留下特定的激素。蚂蚁个体往复的在路径上留下激素， 激素的浓度在较好的路径上积累，浓度变大，从而使后来的蚂蚁能快速的找到食 物所在的位置。一种改进的蚁群算法川，该蚁群算法基于蚁群中各种类型蚂蚁的 分工机制，相对于多子蚁群算法有效地提高了算法的优化能力。图 2. 5 可简单说 明蚁群算法的基本原理。 支路二 (蚁穴 )a (食物 )b 支路一 群算法原理图 如图所示， a 点表示的是蚂蚁的巢穴位置，别点表示的是食物的位置，有两条 路径在巢穴和食物之间。假定有两组数目相同的蚂蚁同时由 a 点出发，沿着两条 路径分别向着方点前进，刚开始沿着两条路径的概率是相等的，均为二分之一， 设定蚂蚁爬行的速度相同，蚂蚁单位时间分泌的激素量相同。蚂蚁就这样往复的 在这两条路径上来回搬运食物，但是由于路径二明显长于路径一，所以路径二上 的激素的浓度将会明显小于路径一 上的激素的浓度。由于路径二的上的激素浓度 较大，蚂蚁就会越来越偏向于向路径二前进，这样在路径一上留下来的激素也越 来越多，激素的浓度不断增加，直到最后，几乎所有蚂蚁都会沿着路径一前进去 寻找食物，这样大大提高了蚂蚁搬运食物的效率。 除了蚁群算法，常见的群算法还有 出的粒子群算法 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 13 2, 13(最初是模仿鸟群觅食而设计的，在 法中，每个任务分配方案都是“粒子”，所有的粒子都有适应值函数决定的适应值。 法的基本流程为 : (1)初始化一群大小为二的粒子，包括他的位置和速度。 (2)设计适应度函数并评价每个粒子的适应度大小 (3)对每个粒子将其适应度大小与历史极值尸作比较，如果比历史极值好， 便将它作为新的 4)对每个粒子，将适应值与尸作比较，如果较好，将它作为新的尸 (5)根据迭代公式，变化粒子的位置和速度。 (6)如达到结束条件 (有足够好的适应值或者达到预设的迭代次数 )则结束， 否则返回步骤 (2)0 (7)算法 结束。 群算法作为一类典型的解决静态任务分配的方法，有其自身独特的地方。相 对于其它任务分配算法，有很多的优点，但是万事都有利有弊，群算法在存在优 势的同时还存在许多的不足之处。我们对先前研究的蚁群算法和粒子群算法进行 分析，结合国内外对群算法在无人机任务分配中的应用实例和理论研究，总结归 纳出群算法具体有以下四个优势 : (1)随机性强。 (2)可以对较大规模的实际问题进行求解。 (3)逻辑简单，适用于简单的任务判断。 (4)在搜索过程中消耗的能力少。 四个缺点 : (1)实时性差，很难确定具体时间。 (2)理论依据不够充分。 (3)得到的解不一定是最优的。 (4)对于多类型的无人机不适用。 群算法依据的是生物种群中生物个体的运动，每个生物个体的形态结构和具 体能力基本是一样的，近乎相同，所以具有很强的随机性。在对于考虑无人机类 型单一的任务分配问题时是有优势的。但是当无人机的类型多样时，如无人机的 能力和性能的不同，群算法不能区别各个无人机，从而不能合理的对任务进行分 配。其次，群算法的基础是由生物 种群中的个体行动，但是任务分配的最终解决 方案是由生物种群的整体运动趋势得来的。所以个体数目的多少对算法没有很大 的影响，即可以对较大规模的实际任务分配问题进行求解，这又是它的一个优势。 另外，群算法的搜索方式是随机搜索，以粒子群算法为例，其搜索空间是不确定 的，我们知道粒子群中的粒子是朝着一个方向移动，但是没有准确的理论依据， 这是这类算法最重要的缺点。并且由于随机搜索的方法通常得到的是局部最优解， 对于全局最优解往往很难得到，容易“早熟”。所以我们在群算法搜索过程中引 入正反馈机制，大大提高了算法的收敛 速度。 场类算法 市场类算法 1819,20,21是另一大类静态任务分配算法。它来源于市资本主义社 会市场经济体制。市场中有许许多多的客户，每个客户依据自己的投资能力和预 期效益而对市场中的项目进行投资，个别的客户个体无法改变整个市场的走势， 买文档就送您 纸全套， Q 号交流 401339828 或 11970985 14 但是把所有的客户看作一个统一的大集合，就可以通过投资对整个的市场的走势 产生决定性的作用，即市场的发展或者是市场的消退。市场类算法把市场中的每 个客户可以看作智能体，在无人机的任务分配方法研究中得到了很广泛的应用。 绍了一种 包含谈判机制的市场类算法，无人机通过数据链技术相互传递信息， 协商得出任务分配方案。在该类算法中，每架无人机完成一个任务都会产生收益， 但是执行时会消耗无人机的能力。得到与损失的差额就是无人机完成任务的利益， 每架无人机都为了利益最大化而执行任务。 通过对大量对市场类算法在无人机任务分配方法求解的理论研究和实际应用 中，我们总结归纳了市场类算法的主要优点。 1)确保了每架无人机收获的利益和消耗的能力相差不大。 (2)无人机的类型可以不同。 (3)大大减少了无人机 在空间内搜索的时间。 因为市场中每个单体所追求的是个体的利益，所以对于个体而言不仅要考虑 完成任务获得的收益，还要考虑自身的执行能力，也就是所谓的本钱。无人机在 任务分配过程中，要考虑无人机本身执行任务的能力，包括航程，航速和负载载 荷等，这就保证了资源的均衡。其次考虑到市场中各个客户的不同，符合无人机 任务分配的实际问题，因为往往无人机的类型都是不一样的。最后，由于市场类 方法，只考虑个体的收益最大，而不是考虑整体的收益最大，不需要对所有的情 况进行全面的考虑，从而减少了空间中搜索的时间。但是由于 市场中的盲目性， 往往不能得到最佳的分配方案。 2. 4. 3 进化理论算法 最后一大类静态任务分配算法是进化理论算法，该算法的理论依据是仿照自 然界中生物种群进化，以优胜劣汰的进化原则，将相对优秀的生物个体保留下来， 而相对差点的个体剔除出种群。遗传算法是这一大类算法中使用最多，最为有名 的算法。 1975 年，美国密歇根大学的教授首次在研究成果中提到了遗传算法