|
曝光台 注意防骗 网曝天猫店富美金盛家居专营店坑蒙拐骗欺诈消费者
为绕开这个计算难点以减低大型问题的求解难度，Rasmussen，S.J.等人提出了一种树搜索（tree search）算法对WASM问题进行处理，他们将组合优化问题以决策树（decision tree）的形式表达出来，然后一边通过最佳优先所搜（best-first search）在已搜索的可行解中不断降低解的上界，一边又在决策树上未评估的分支中通过欧氏距离确定解的下界以减少计算量，在这个定界的过程中，可行解的上下界范围不断缩小。从而避免确定性所搜算法遍历枚举（exhaustive enumeration）计算量过大的缺点，在处理小型问题时截止确定最优解；而大型问题时则如果在线使用能立即给出一个相对较好的可行解，如果离线使用则仍能找到问题的最优解。因而，该方法具有较好的灵活性。然而，尽管这种改进的确定性树搜索算法能在某些问题中取得好的效果，但其广泛适用性却可能经不住考验。
启发式算法（heuristics）在处理这类大型复杂的组合优化问题时，由于其启发式的随机特性，并不企图穷遍整个搜索空间，而在计算时间和解的最优性能之间达成某种妥协，从而可以再接受的时间和计算代价内获得较好的次有解。Rasmussen，S.J.等人早在2003年就对启发式算法和最优算法处理大型问题时的效果进行了比较，结果表明启发式算法具有明显的优势。因而，这种启发式的随机特性使得它们在处理大型复杂问题时具有天然的优势，今年来已经有大量的研究使用了这类算法。
GA作为一种典型的启发式算法，被研究人员广泛的用于多UAV协同任务规划问题研究中心。Shinma，T.等人把任务规划问题归纳成CMTAP模型之后，将该问题的解编码成矩阵的形式：以矩阵的列作为染色体的基因（gene），表示将某架UAV指派去对某个目标（target）上执行某项任务（task）；以矩阵为染色体（chromosome），表示CMTAP的一个可能解。通过对自然选择的过程的模型，首先构建一个初始化种群，然后通过杂交、变异、选择等过程，对染色体种群迭代演进，最终获得一个较好的可行解。尽管该解可能不是最优解，但能在可接受的时间内获得一个次优解，怎么都要比长时间等待计算最优解的结果来的好。随后Karaman，S.等人使用进程代数（process algebra）改进了GA的染色体编码和杂交、变异等遗传算子，从而进一步提高了GA再处理大中小型问题时的适用性。
PSO作为另一种启发式算法，有着与GA不同的演化策略，它模仿鸟群捕食行为，将可能解视作一个粒子（particle），被赋予一个速率在解空间中运动，根据其自身历史最佳位置和粒子群（particle swarm）整体的历史最佳位置，调整其运动速率，从而达到在解空间中寻优的目的。这个算法与GA相比，不需要构建大量个体组成的种群，概念简单，实现容易。
集中式控制方法经过多年的发展已经较为成熟，其全局特性较好，在处理强复杂耦合问题时，可以通观全局，获得较好的可行解，具有较大的优势。但其实时性、鲁棒性和容错性等方面的不足导致了它在动态、不确定性和实时性要求较高的应用中效果不佳。此时，需要寻求别的解决方法。
（2）分布式任务规划方法
很多是基于市场机制的合同网络协议。Smith，R.G.在1980年首次提出将合同网协议用于分布式问题求解。该方法的基本思想是将任务分配过程视为一个市场交易过程，通过“拍卖-竞标-中标”（auction-bid-award）这个市场竞拍机制实现分布式系统内部工作任务的指派和调整。当一个系统成员产生新任务时，如发现新目标，可以向系统中其他成员发布市场拍卖合约；其他成员则对该合约进行评估，如果可行则向拍卖者回复自己执行该合约的代价；合约拍卖者收到竞标者的价码后，进行评估，选择合适的执行者，进行任务指派。这样，一个基本的市场交易活动即大致完成。其原理简单直观，易于实现，且执行效率高，已在包括多个UAV协同决策与控制在内的多个领域被广泛研究和应用。
在合同网协议的基础上，研究人员进一步发展处更多的分布式方法。由于合同网只给出了协商的框架和协议，却反形式化的模型。有研究人员将一种描述离散事件动态系统的图形化工具——Petri引入到合同网的建模与分析中，使合同网协议更加的严格化，从而实现更好的系统协商效果。
分布式方法在近些年的发展中，越来越受到关注，已经有大量的方法被提出和应用，如协商一致理论、对策论、信息素、多智能体系统等等。这类方法由于其对动态不确定性问题的适用性发展迅速，目前正处于火热的研究中。
国内研究现状
今年来国内越来越多的研究人员参与到多无人机协同规划问题的研究中。如叶媛媛④详细分析了任务规划问题的理论和特性，以多目标优化理论为基础，建立多无人机协同任务规划的多目标证书规划模型，并对其进行求解；龙涛⑤提出一种有限中心的分布式控制体系，在合同网协议基础上提出多种类型合同和协商机制的分布式体系进行在线实时的任务重分配；柳林⑥在对分布式多机器人系统的研究中，总结了合同网拍卖机制的理论基础，基于合同网机制提出NeA-MRTA和NeA-MRTA算法进行简单任务动态分布式分配，针对复杂任务的动态分布式分配问题，则基于NeA-MRTA提出一种CA-MRTA算法进行处理，取得了比较好的效果。
具有里程碑意义的是，2013年，国内在多无人机协同决策与控制领域处于领先地位的国防科技大学沈林成教授团队归纳总结最新研究成果，出版了一本专著《多无人机自主协同控制理论与方法》⑦。这本专著分析总结了多无人机系统的理论和技术发展脉络，对包含多无人机协同任务分配、协同轨迹规划、协同目标状态估计、编队协同控制、多机协同自组织等在内的多个协同控制课题都进行了归纳与研究，提出多个方法解决对应的协同问题，并给出典型应用下多机协同控制问题的理论分析和方法描述。这本专著对国内的研究人员有很高的参考和指导价值。
注④ ：叶媛媛.多UCAV协同任务规划方法研究。长沙：国防科学技术大学，2005.
注⑤ ：龙涛.多UCAV协同任务控制中分布式任务分配与任务协调技术研究。长沙：国防科学技术大学，2006.
注⑥ ：柳林.多机器人系统任务分配及编队控制研究。国防科学技术大学，2006.
注⑦ ：沈林成，牛铁峰，朱华勇。多无人机自主协同控制理论与方法。北京：国防工业主板社。2013.
研究现状分析。综合国内外文献，大部分研究对基于多任务时序优先级约束的多无人机协同任务规划问题不够深入。该问题主要受如下因素影响：
（1） 多无人机系统的异构性，即机群由多种具有不同性能的无人机组成；
（2） 无人机机载资源（如弹药）的有限性，即无人机群仅懈怠了有限的资源执行任务；
（3） 多任务间的时序优先级约束，如对地面目标的确认/攻击/毁伤评估一体化任务中，必须对目标确认之后才能发起攻击，而毁伤评估则显然必须在攻击完成之后才能进行，这类时序约束带来的问题，如死锁问题，将会严重影响对多无人机协同的协同控制；
中国通航网 www.ga.cn
通航翻译 www.aviation.cn
本文链接地址：无人机集群技术国内外对比(3)
|
