毕业设计（论文）-无人机组群巡检灭火系统设计（全套图纸三维）(21页).doc

-毕业设计（论文）-无人机组群巡检灭火系统设计（全套图纸三维）-第 14 页本科毕业设计 题 目： 无人机组群巡检灭火系统设计 学 院： 机电工程学院 专 业： 机械设计制造及其自动化 姓 名： 学 号： 指导教师： 2016年5月28日摘 要 随着无人机执行任务的环境日益复杂，任务类型日益多样，无人机己经开始从单架次独立任务的方式向着多架次、多类型的机群作战方向发展。通过对多无人机协同任务分配的研究，可以使系统完成的任务类型更为多样，同时任务完成的质量和效率也获得较大程度的提高。 本文研究了集中式多类型无人机编队任务分配方法。集中式指的是任务分配过程中，无人机处于从属地位，不具有自主能力，完全受控制站中人的控制。多类型指的是无人机类型和执行能力的不同。 本文首先介绍了无人机的应用现状，讨论了几种任务分配算法，分析了他们的优缺点。其次，在静态环境下基于平面网格坐标系，建立了一个多无人机任务分配数学模型，设计了一种有人参与的静态分配算法。然后利用了一个无人机森林灭火的实例，通过MATLAB仿真和分析说明了算法的可行性和实用性。最后，在动态环境中，根据无人机状态改变和任务改变两种情况，对动态任务进行了动态重分配。关键字:无人机；任务分配；静态分配；动态重分配全套图纸，加153893706Abstract With the increasingly complex environment, the missions of the UAV grow variously. The operational manner of UAV changes from the independence towards the multi-way, more types of UAV. through the research of the assignation of the multi-type UAV, you can make the types of completed tasks more diversely and the quality and efficiency improved greatly. This paper addresses the problem of task allocation in the centralized and multi-type UAV fleets. Centralized refers to in the task allocation process, UAV is in asubordinate position, UAV do not have independent ability, completely under controlof human in control base. Multi-type UAV refers to the different abilities of UAV. First of all, this paper introduces the present situation of the applications of UAV,discussed some kinds of task allocation algorithms and analyzed their advantages anddisadvantages. What's more, in a static environment, based on the planar grid coordinate system, we set up a multi-UAV task allocation mathematical model and designed a Static allocation algorithm with humans attended. Then use an example of forest outfire to Show the feasibility and practicability of the algorithm by the simulation analysis of Matlab. Finally, according to two situations: UAV changed or tasks changed, the task allocation changes to dynamic redistribution, in dynamic environment.Keywords: UAV ；Task allocation ；Static allocation ；Dynamic redistribution目 录第一章 绪论1 1.1任务分配的研究背景2 1.2国内外无人机应用现状2 1.2.1应用在军事上2 1.2.2应用在自然灾害的防护上3 1.3论文的主要内容4第二章 无人机任务分配问题研究现状及发展趋势4 2.1无人机任务分配问题的定义及解决步骤4 2.1.1 UAV任务分配问题的定义5 2.1.2 UAV任务分配问题的描述5 2.1.3解决UAV任务分配问题的步骤5 2.2无人机任务分配控制方法5 2.2.1集中式控制5 2.2.2分布式控制6 2.3无人机任务分配模型分类7 2.3.1多旅行商问题模型7 2.3.2通用分配问题模型8 2.3.3车辆路径问题模型8 2.3.4混合整数线性规划模型9 2.3.5 CMTAP通用模型9 2.4静态任务分配算法10 2.4.1群算法10 2.4.2市场类算法11 2.4.3进化理论算法11 2.5动态环境中多任务重分配算法11 2.5.1合同网算法11 2.5.2拍卖算法12 2.5.3聚类算法12第三章 静态环境下无人机任务分配12 3.1任务分配场景和限制条件13 3.1.1任务分配的场景14 3.1.2任务分配限制条件14 3.2多无人机任务分配的数学模型14 3.2.1无人机任务集描述15 3.2.2平面网格坐标系16第四章 动态环境下无人机任务分配17 4.1动态任务重分配18 4.1.1动态任务重分配的触发条件18 4.1.2任务动态再分配采用的策略19 4.1.3任务重分配的流程21结 论23参考文献24致 谢25第一章 绪论1.1任务分配的研究背景 无人机(Uninhabited Aerial Vehicle, UAV)是指由远程遥控或自主控制操作的无人驾驶的飞机。采用无人驾驶的方式使飞机摆脱了驾驶员自身生理条件的限制，能够完成一般飞机不能完成的任务。无人机具有重量轻、维护成本低、机动性能高等明显优势，同时无人驾驶的方式使操作人员远离危险的任务环境，极大地降低了操作人员的危险程度。 UAV协同任务规划是现代战争中提出的新课题。随着无人机的出现，利用无人机执行任务逐步成为了现实，目前UAV协同任务规划得到了越来越多的关注，因为尽管单无人机可以无需合作完成某个环境的搜索，但是一个更有效的搜索需要合作来减少重复覆盖，通常多无人机任务规划可以分成两大部分:上层的任务分配(Task Assignment or Task Allocation)和下层的路径规划(Path Planning)，任务分配考虑各种约束条件，以总体任务有效达成为目标，将具体目标和行动任务分配给各机，而各机根据分配的任务再进行具体的作战路径规划。路径规划的功能是在满足如最大线性速度、最大转角速度、操作的安全性、时间和环境变量等自身或外部限制的前提下在一系列位置之间设计或生成路径。本文我们主要讨论UAV任务分配问题。1.2国内外无人机应用现状1.2.1应用在军事上 UAV任务规划技术主要还是应用在军事上。无人作战飞机(Uninhabited CombatAerial Vehicle, UCAV)指的是无人机携带武器或者弹药，可对地面目标进行攻击和轰炸。在军事发达国家，尤其美国、英国以及法国对无人作战机研究深入，美国对于无人机任务分配问题在军事上的研究最为深入，在上世纪70年代就开始对无人机任务分配问题进行描述并进行实际应用。在越南战争，海湾战争以及北约空袭南斯拉夫等过往战争中，无人机经常用于执行一些人不能完成的军事任务。在这些争中虽然无人机不是主要执行任务的飞机，但它却成了决定战争导向的决定因素之一。由于无人机的无人驾驶特点，可以被派往危险的环境中执行一些人不能执行的任务，因而成为重要的军事力量受各国关住。无人机可以用来完成对战场实时的侦察和监视、对目标位置的确定、任务目标的评估、电子对抗等。无人机最早的开发是在第一次世界大战之后。和美国等西方国家相比，我国的无人机研究水平差距还是很大。虽然国内从80年代末开始，对路径规划问题进行过许多研究，发表了许多论文，但大多数的文献仅仅是对单无人机所进行的路径规划问题的研究，目的是避开无人机在飞行过程中遇到的危险区域，很少有关于无人机任务分配问题解答的研究成果。当前我们国家无人机反的研究还处在起步阶段。由于我国的无人机功能简单，自主能力较差，需要地面控制站进行任务分配的规划。而当前的无人机发展趋势是无人机的智能化，将无人机看成一个个智能体，我国在这方面的研究成果很少。功能上也只能进行简单的图像，数字传输，任务分配、路径规划的能力很差。尚不具备执行复杂战术任务的能力。近年来我国的国防科技大学、西北工业大学等高等院校和科研单位在无人机任务分配问题上也进行了一些理论分析和实际问题的研究，可以说取得了不错的成就。但从现阶段己经得到的理论和实际成果来看，目前我国对无人机任务分配问题的研究还处有很多不足和局限。例如无人机的自主性较差，无人机的决策大都是由地面控制站决定的。对于无人机所处的动态环境考虑不足，无人机的尺寸、时间窗函数等考虑较少。2.2应用在自然灾害的防护上 和平和发展当今世界的两大主题，所以无人机的应用也由军用慢慢转向民用。其中最主要的民用用途是在自然灾害的防护上。2001年以来，世界各国都在大力发展各种用途的无人飞行器。目前世界上32个国家己研制出了多种无人机。美国、以色列、俄罗斯、北约等国家非常重视多用途无人机的研制、生产和应用。森林火灾的现场温度高，对飞机的抗热性能高。现场的烟尘大，能见度不高，尽管有人飞机能飞至火场上课，飞机中的人也不能清除地了解火场当前的具体情况。这时无人机的优势就体现出来，通过在无人机上配置摄像机和数字图像传输设备，可轻易完成对火场的侦察，灭火和灭火评估。美国航天局最新研制的无人灭火机“工khana"。这款无人灭火机由“捕食者B" (Predator B)改进而来。“捕食者B”原本是美国空军用于战时监视和侦察的，现在它的改进版“工khana”被用作另一个领域，那就是森林灭火。在火场中，由于火势的动态性和不确定性以及协同控制的复杂性，使得任务开始后出现许多无法预料的情况，必须根据火场火势和编队状态的变化快速调整UAV编队的任务计划，通过动态重调度实现任务的重分配。1.3论文的主要内容 无人机如何在复杂的环境中顺利地完成所需执行的任务，并且能够使得任务执行的效率最高，收获的利益最大，付出的代价最小，是多无人机任务分配所要考虑的问题。本文的主要工作是通过对各种任务分配算法的研究，引出了一种有人参与的多无人机任务分配算法并进行了理论研究和仿真分析。主要步骤是:首先建立了一个任务分配在森林火灾防护的应用场景，设置了关于实际问题的限制条件，然后建立了一个基于六元组的任务描述，使用了平面网格坐标系对任务分配问题进行建模，在以上的基础了最后利用了一个无人机森林灭火的实例，通过MATLAB仿真结合算法说明了该算法的可行性和实用性。因为无人机任务分配所处环境是动态的，所以对动态环境下无人机任务重分配问题也进行了一些算法研究和实例分析。第二章 无人机任务分配问题研究现状及发展趋势2.1无人机任务分配问题的定义及解决步骤2.1.1 UAV任务分配问题的定义 UAV任务分配问题可以定义为:在己经完成UAV编队分组的基础上，基于一定的环境和任务要求，为编队中的UAV分配一个或多个有序任务，以便在完成最大可能任务的同时，使得UAV编队的整体效率最高。 我们结合图2. 1这个简单的例子来直观地了解任务分配问题的具体含义:首先设置了任务集和无人机集:其中包含了四个待执行任务，无人机编队由两架无人机组成。然后设计具体的路径和任务执行顺序来完成所设定的四个任务。图中每个带箭头直线上的数字表示无人机在该段航路上所花费的时间，四个任务用四个圆圈来表示。圆圈中上半部分的数字表示的无人机任务集中任务的序号，下半部分的数字表示完成这个任务需要的具体时间。最后虚实线表示的是任务分配的具体的方案。无人机分别沿着制定的虚线完成四个所设定的任务，通过这种方法，花费时间要明显小于单架无人机。2.1.2 UAV任务分配问题的描述 给定一个UAV编队U，它包含数目为N二的无人机。2.1.3解决UAV任务分配问题的步骤 无人机任务分配方法的求解主要分为两方面:任务分配模型的建立以及具体的任务分配算法的设计: (1) UAV任务分配的数学模型的建立 要对无人机进行数学建模，首先要对无人机所处的空间环境进行描述和表达。通常我们以一个二维或者三维的变量来定义一个无人机和目标点的位置，为简便，一般采用二维变量。得到了无人机和目标点的位置，就能得到任一无人机的任务执行路线。然后我们设计一个二值决策变量，如果无人机完成某个任务，二值变量就为1，如果不完成那个任务，二值变量就为0。然后要设定无人机任务分配的约束条件，如无人机最大航程、任务时间窗约束、任务执行的先后顺序、无人机的载荷等。2.2无人机任务分配控制方法 由于无人机执行任务环境是动态的，不是固定不变的，所以无人机的任务分配控制方法也应该根据不同的任务环境而区别对待。无人机任务分配控制方法选取对无人机执行任务的效率和质量有很大关系。任务分配控制方法的选取应该考虑以下几个因素:任务完成的快速性，任务的实时性，任务分配的计算时间和计算复杂度，抗干扰能力等。无人机任务分配控制方法主要可以分为集中式控制(Centralized Control)以及分布式控制(Distributed Control)这两种。2.2.1集中式控制 在集中式控制方法中，由地面控制站中的操作人员制定任务分配方案和无人机具体的飞行航路，无人机本身不具备决策能力，完全按照地面控制站发出的任务指令和航路执行任务。图2.2表示了集中式体系结构图:2.2.2分布式控制 区别于集中式控制方法，分布式控制方法中无人机编队中或者无人机编队之间的无人机是具有独自决策能力的智能体，它们具有很强的协同能力和自治性。无人机之间以数据链技术为支撑，对无人机所处环境，任务目标集信息，无人机状态信息进行交互，综合考虑各种因素，提出具体的解决任务分配问题的方案和具体步骤。较之于集中式控制方法，无人机个体在分布式控制方法下具有较强的实时性，抗干扰能力，计算量小，计算复杂度小等优点。当前，分布式控制方法主要可以分为两种:完全分布式控制方法和部分分布式控制方法。 (1)完全分布式控制 完全分布式控制方法是一种依靠无人机的自主性和相互协作的一种方法，由于无人机任务分配问题的复杂性，该方法相当于将复杂的问题分解成为一个个相对简单的小问题，对每架无人机进行任务分配，接着就是将各个无人机的信息进行交互，对任务进行整体求解。如图2. 3所示，完全分布式控制方法中我们把无人机看成具有决策能力的智能体，这样无人机任务分配问题就转化成为各个智能体之间任务的分配和决策。在这种结构中，无人机相对于集中式控制有很强的自主性，能够对任务集信息和自身的信息进行采集和分析，并进行决策，在特定的情况下通过数据链与其它无人机进行数据交互，协作完成所需执行的任务。 图2.3完全分布式控制结构图 这种控制方法中，无人机编队内各个无人机对所得到的信息进行相互的共享，得到所有的关于任务执行的信息，最后整理分析所得到的信息对无人机编队中的每一架任务分配任务集。由于无人机编队中有多架无人机，在执行任务中可能发生交叉冲突，即碰撞冲突，所以需要对它们进行考虑并消除。同时在这种控制方法中，无人机之间是通过数据链技术进行任务集数据的传输和共享，为的是更好的具有任务决策的实时性，所以数据量是相当大的，将随着编队内无人机的数量呈指数增长。所以应用这种控制方法，编队内无人机的个数受到了很大的限制。 (2)部分分布式控制 部分分布式控制方法吸取了无人机任务分配控制方法中集中式控制和完全分布式控制方法各自的优势，对于解决多类型无人机编队任务分配问题更为合理。经过对集中式控制方法和分布式控制方法的比较，我们得出分布是控制方法是一种实时性较强的方法，能够快速的对任务信息进行采集和分析，得到解决任务分配问题的具体方案，获得的方案往往是局部最优的，但不能得到全局最优方案。而集中式控制方法恰恰相反，由于所有信息都要返回地面控制站进行汇总，所有能够进行全面而详细的规划，从而获得的方案一般都是全局最优方案，但是实时性就很差啦。当前，国内外很多院校和科研机构对集中式控制和分布式控制方法结合的问题进行了理论分析和实际验证，对两种方法进行了整合，得到了部分分布式控制方法，结构图如图2. 4所示。2.3无人机任务分配模型分类 根据任务分配建模分类，现阶段的模型主要有多旅行商问题2(MultipleTraveling Sa-lesman Problem, MTSP)模型，通用分配问题3(Generalized AssignmentProblem, GAP)模型，车辆路径问题4(Vehicle Routing Problem, VRP)模型，混合整数线性规划s,6,s,9(Mixed Integer Linear Programming, MILP)模型以及CMTAP(Cooperative Multiple Task Assignment Problem)模型。2.3.1多旅行商问题模型 通常，我们所说的旅行商问题是一个NP完全问题，具的定义如下:假设有a个旅行商人，方个城市，每个旅行商人都要沿着城市之间的道路访问其中的一些城市，最后所有的旅行商人都要返回初始的城市，限制每个城市都要被访问并且有且仅有一次，问题所要达到的目的是在完成对所有城市访问的同时，总距离最短、完成任务时间最短、消耗最小、收益最大等。把旅行上问题模型应用到无人机任务分配中去，我们假设有一个二架无人机的无人机编队，有二个目标任务的任务集，无人机编队从同一个基地出发，沿着预先设定的飞行航路，完成所有的任务，每个任务只能被完成一次，最后考虑无人机的总航程，无人机完成任务的时间，无人机消耗的能力，完成任务的价值利益等。2.3.2通用分配问题模型 通用分配问题模型考虑将二个任务分配给二个单体，每个任务只能给一个单体并且单体的资源受到限制。相当于二个任务分配给给一个无人机执行并且无人机的资源，如最大任务数，二个无人机，每个任务只能最大航程受到限制。2.3 3车辆路径问题模型 我们对车辆路径模型进行如下描述:假设有二辆货车，每辆车的负载能力不同，它们从同一个基地出发，为二个目标点输送货物，每个目标点需要送达的货物数量不同。最后，所有货车回到出发点。车辆路径问题模型yo要考虑送达的时间，货物送达的消耗，完成输送的价值等，并保证所有的货物安全送达。2.3.4混合整数线性规划模型 混合整数线性利用线性化函数建立模型，模型描述简洁、直接，有助于提高无人机任务执行效率和生存能力，达到了任务分配的目的和初衷而且可以通过对约束条件的修正来满足实际问题需要，但是模型规模不能过大。问题规模过大将导致计算量指数型增长，任务分配的实时性得不到保证。2.3.5 CMTAP通用模型 随着无人机能力不断增强，无人机执行任务的复杂程度也随之增强，不同任务之间存在着复杂的时序以及时间约束。对于这一类复杂的任务集合，目前大多数任务分配模型无法对其进行有效的描述。一种CMTAP模型川被引出，这种模型充分考虑一组无人机完成一系列针对地面目标的连贯任务，包括任务目标的识别、攻击、毁伤评估等。2.4静态任务分配算法 在静态环境中，无人机和任务都是确定的，不发生改变。在这样的条件下，多无人机任务分配的算法主要有:群算法，市场机制算法和进化算法。2.4.1群算法 群算法主要模仿自然界中各种生物的群体化行为，例如虫群12和羊群。我们通过对虫群群体化行为就行具体的研究分析，从而来简单说明群算法的具体特点:所谓的昆虫群的群体行动指的是昆虫个体根据一些规律进行个别的运动，从而导致整个群体显现出一种运动规则，在运动中昆虫主要遵循三个准则:第一，实时监测邻近个体距离，防止产生交叉冲突，即防止和其它个体产生碰撞;第二，采集邻近个体的信息，如速度，位置等;第三，保证和其它昆虫的距离，不能太远，而脱离群体。昆虫以上的这些行为都是个体的行为，不是群体的运动，不过所有的个体都执行这些准则，就会产生整体的运动趋势。群算法中目前为止最为经典就是蚁群算法13,14,15,16 (Ant Colony Optimization) , 1991年，意大利科学家Dorigo首先在其发表的研究成果中提到了蚁群算法。图2.5可简单说明蚁群算法的基本原理。 2.5蚁群算法原理图 如图所示，a点表示的是蚂蚁的巢穴位置，别点表示的是食物的位置，有两条路径在巢穴和食物之间。假定有两组数目相同的蚂蚁同时由a点出发，沿着两条路径分别向着方点前进，刚开始沿着两条路径的概率是相等的，均为二分之一，设定蚂蚁爬行的速度相同，蚂蚁单位时间分泌的激素量相同。蚂蚁就这样往复的在这两条路径上来回搬运食物，但是由于路径二明显长于路径一，所以路径二上的激素的浓度将会明显小于路径一上的激素的浓度。由于路径二的上的激素浓度较大，蚂蚁就会越来越偏向于向路径二前进，这样在路径一上留下来的激素也越来越多，激素的浓度不断增加，直到最后，几乎所有蚂蚁都会沿着路径一前进去寻找食物，这样大大提高了蚂蚁搬运食物的效率。2.4.2市场类算法 市场中有许许多多的客户，每个客户依据自己的投资能力和预期效益而对市场中的项目进行投资，个别的客户个体无法改变整个市场的走势，但是把所有的客户看作一个统一的大集合，就可以通过投资对整个的市场的走势产生决定性的作用，即市场的发展或者是市场的消退。市场类算法把市场中的每个客户可以看作智能体，在无人机的任务分配方法研究中得到了很广泛的应用。Czil介绍了一种包含谈判机制的市场类算法，无人机通过数据链技术相互传递信息，协商得出任务分配方案。在该类算法中，每架无人机完成一个任务都会产生收益，但是执行时会消耗无人机的能力。得到与损失的差额就是无人机完成任务的利益，每架无人机都为了利益最大化而执行任务。2.4.3进化理论算法 最后一大类静态任务分配算法是进化理论算法，该算法的理论依据是仿照自然界中生物种群进化，以优胜劣汰的进化原则，将相对优秀的生物个体保留下来，而相对差点的个体剔除出种群。遗传算法是这一大类算法中使用最多，最为有名的算法。1975年，美国密歇根大学的教授首次在研究成果中提到了遗传算法，之后，全世界很多国家的科研工作者对遗传算法进行了理论研究和实际应用。遗传算法仿照生物进化理论，才有染色体编码方式进行任务分配方法的最优化选择。遗传算法以决策变量的编码作为运算对象，传统的优化算法往往直接采用决策变量的实际值，这是它的一个很大的特点。基于UAV多任务协同分配问题特定染色体编码方式，遗传算法采用两种进化操作:选择操作和交叉操作。有研究者在传统的遗传算法中使用邻域搜索算法m。基于邻域搜索原理，运用对称群结构描述UAV任务分配的搜索空间，运用右乘运算构造搜索邻域，结禁忌搜索。相对于传统遗传算法、爬山能力强和全局迭代寻优，易找到全局最优点，实现了基于对称群计算的UAV任务分配算法。 基于UAV任务分配问题特定的染色体编码方式和适应度函数，本文采用如下的进化操作: (1)选择操作 进化算法的选择是建立在对个体适应度的评价基础之上的，本文采用经典的比例选择算子来实现该操作来实现该操作。比例选择是一种有退还的随机采样方法，其基本思想是:每个个体中被选的概率与其适应度大小成正比，其具体的执行过程如下 a.计算出种群中每一个个体的评价函数的值的，得到它们的总和; b.分别计算总裙子个体评价函数值的相对值，即各个个体被选中作为父代遗传到下一子代的概率; c.再使用类似赌博轮盘的操作(即产生0-1之间的随机数)，从而分别确定每个个体被选中遗传到下一代的概率。 (2)交叉操作 本文采用的交叉操作使用的是EA-PMX算法中的PMX交叉算子。UAV任务分配问题对交叉算子的设计要求是:对任意两条染色体进行交叉操作后，能得到两天新的，且具有实际意义的染色体序列。部分交叉映射(Partially MappedCrossover, PMX)算子是一种常见的交叉算子。PMX算子的主要思想是:整个交叉过程分两步完成，首先对个体编码进行常规的双点交叉操作，然后根据交叉区域内各基因值得映射关系来修改交叉区域之外的各基因座的基因值，按照染色体的编码，种群中的任一染色体表示为T=(tl,tZ,.tn)。2.5动态环境中多任务重分配算法 在具体环境中，由于环境的动态性和不确定性以及协同控制的复杂性，使得任务开始后会出现许多无法预料的情况，因此，必须根据战场态势和编队状态的变化快速调整UAV编队的任务计划，通过动态重调度实现UAV之间的任务重分配，以真正适应复杂的作战环境。因此，我们更多的使用到的是动态分配算法。UAV任务再分配的一般策略整个编队的完全再分配局部调整分组基础上的再分配。动态任务分配算法主要有:合同网算法、拍卖算法、聚类算法。2.5.1合同网算法 为了更好的解释合同网的概念，我们首先简要介绍下什么是Agent智能体)。通常我们认为:Agent主要应用于动态环境中，他具有先进的设备，如传感器，高性能机载电脑，先进的导航系统等，实时获取自身的状态信息，如形态，位置，负载等;任务集信息，如目标位置，目标数量，任务目标价值以及周围的环境信息。通过对这些信息的总结，分析，与其他无人机进行信息共享交互，制定出任务分配方案并执行。它具有高度的自治性和行动力，在分布式控制中被广泛地应用。合同网一般有三大类任务执行角色:招标者，投标者，中标者。 我们对合同网的一般理解为:首先是任务招标者有任务需要其他任务执行者的能力来完成所需完成的任务，因此招标者就会向投标者通过信息交互发布任务请求，即所谓的招标行为;接着收到任务信息的投标者们先是评估自己的执行能力和想要得到的收益，给出自己的投标值，即所谓的投标行为;最后招标者，整理分析投标者给出的投标值，遴选出最适合完成任务的投标者作为中标者。如下图表示了一个合同网方法的简单框图: 图2.7 我们将合同网算法的具体步骤总结如下: (1)招标者传送任务信息给投标者，包括任务数量，任务完成期限等; (2)投标者对招标者传送的任务信息实时监测，并对自己感兴趣的任务进行投标成为投标者; (3)管理Agent在一定的时间段内对所收集的应标进行评估，根据评估结果 向其满意的投标者分配任务; (4)任务执行Agent确认该任务分配者提出的合同完成分配，形成承诺监督关系。2.5.2拍卖算法 拍卖算法ass是在动态环境中分布式控制方法分配任务方法的又一种重要方法。拍卖法算法模拟具体的拍卖过程，在拍卖过程中各个智能体计算每一个任务的收益，消耗的能力，评价函数等。拍卖算法首先给出一个拍卖的具体先后次序，各个智能体按照次序去完成自己拍卖得到的任务集，最后得到整体的任务分配方案。在智能体能力范围和约束条件之内，拍卖法重新给出一个拍卖次序进行又一次的拍卖，根据评价函数评价新方案和旧方案，将较优的方案留下来，如此周而往复，得到较好的解。 对于动态环境无人机任务分配方法中，我们主要关心的还是算法的实时性，算法的实时性不是说完成任务的时间越短越好，而是当任务环境改变的时候，包括任务集的改变和无人机集的改变，能够快速的给出新的分配方案。而拍卖算法恰恰具有这种能力。2.5.3聚类算法 聚类算法22,23主要研究的是如何根据目标位置、功能等属性值将其分若干类别，以揭示目标之间的相互关系和差别，使得一个类别中的对象样本有较高的相似度，而不同类别中对象样本的属性值差别较大。 聚类的定义如下: 给定一组数据D，把它划分为若干聚类或者称为簇 C, C2., CkI Ci(2-4) 使得不同聚类中的数据尽可能的不相似而通一聚类中的数据尽可能地相似。K均值算法(也称K-means算法)是一种最常用的动态聚类算法，它是一种基于划分的迭代算法，在求解过程中，通过反复修改分类来达到最满意的聚类结果;该算法的基本思想是:首先以一些初始点为聚类中心，对样本集进行初始分类;判定分类结果是否能使一个确定的准则函数取得极值:如能，聚类算法结束;如不能，改变聚类中心，重新进行分类，并重复判定，所使用的准则一般是误差平方和准则。24是一种基于ISODATA约束聚类。ISODATA算法是动态聚类的一种。动态聚类的特点在于，聚类过程通过不断地迭代来完成，且在迭代中通常允许样本从一个聚合类中转移到另一个聚类中。ISODATA聚类的基本思想是，假定样本集中的全体样本分为m类，并选定K为初始聚类中心，然后根据最小距离原则将每个样本分配到某一类中，之后不断迭代，计算各类的聚类中心，并以新的聚类中心调整聚类情况，并在迭代过程中，根据聚类情况自动地进行类的合并和分裂。经典K均值算法介绍 K均值算法(也称K-means算法)是一种最常用的动态聚类算法，它是一种基于划分的迭代算法，在求解过程中，通过反复修改分类来达到最满意的聚类结果;第三章 静态环境下无人机任务分配 对于给定任务和现有的无人机资源，确定参与执行任务的侦察无人机、灭火无人机的数量，组成无人机编队。无人机的任务分配可以定义为，基于一定的环境知识(例如，任务目标位置、威肋、区域位置等)和任务要求，为编队中的各架无人机分配一个或一组有序的任务集(或目标、空间位置)，以便在完成最大任务的同时，使无人机编队的整体效率达到最优。无人机任务分配问题的解是任务区域各任务(或目标位置)的一个排列。由于其明显的优化组合特征，求解无人机任务分配的有效方法是设计出能在合理的计算时间内找到最优或近似最优解的启发式算法。 静态环境指的是无人机集，任务目标集以及任务环境都保持不变。在这种情况下，我们对无人机任务分配问题进行研究。3.1任务分配场景和限制条件3.1.1任务分配的场景 由于无人机在自然灾害中的应用越来越广泛，本文设定的任务分配场景就是多无人机协同森林灭火。在一个二维空间平面中，含有N1架侦察机和NZ架灭火机的小型无人机(每架无人机只能执行一种任务，侦察或灭火)编队对M处静止目标，假定目标对无人机无威肋、，进行“侦察一灭火一灭火评估”。3.1.2任务分配限制条件 在3.1.1无人机任务分配的场景下，并考虑实际情况，我们设定了以下限制条件: (1)每架无人机只能执行单一任务，任务包括侦察(监视)或灭火; (2)无人机与地面控制站通过无线数据链路进行信息交互，无人机之间无通信联系; (3)各架无人机的任务分配和再分配由地面控制站执行，有人参与方式; (4)各架无人机的航线规划由地面控制站执行，并将含有时间信息，任务信息等的各航线点坐标发送给无人机，无人机严格按此航线飞行和执行任务;3.2多无人机任务分配的数学模型3.2.1无人机任务集描述 无人机任务集TS可以用以下一个6元组来描述: TS=(ID, Act, Location, Min, Max/duration, State(3一1) 在以上任务集当中:ID表示无人机的标识符，采用前缀+数字方式来标识编队中的每一架无人机。前缀R表示侦察机，F表示灭火机。数字表示序号。例如R1表示1号侦察机，F2表示2号灭火机，依此类推; Act表示无人机执行的动作，包括: (1)起飞(Take-off:无人机在时间窗口Min, Max起飞并到达指定位置Location ; (2)着陆CLand):无人机在时间窗口Min, Max返航至指定位置Location并着陆;3.2.2平面网格坐标系 设置一个Lx X Ly尺寸的平面网格，其中包含无人机编队的整个飞行区域和待灭火的目标。并假设 (1)在任意的时刻t，如果某个网格被填空，表示无人机可以安全地飞临其位置。 (2)在任意的时刻t，如果某个网格被填黑，表示无人机在其位置受到威胁，无人机规划航线应避免穿过该网格。例如，如图1所示，网格(2, 4 )被填黑，网格(2,4 )位置是一个危险位置。第四章 动态环境下无人机任务分配 由于实际的环境是动态的，无人机，任务目标，和周围环境都会发生改变，所以我们在无人机静态任务分配的基础上，需要对动态环境下无人机任务重新分配进行研究，无人机任务重分配，主要考虑的是任务重分配的“实时性”。4.1动态任务重分配4.1.1动态任务重分配的触发条件 任务分配使得编队中的每架无人机分配到一个有序任务集，它们通过在时间和空间上的协调，共同配合完成任务。随着任务的执行，战场环境以及无人机编队的状态可能发生改变，如: (1)任务改变 无人机编队