基于组合拍卖的协同多目标攻击空战决策算法

书书书　第３１卷　第７期航　空　学　报Ｖｏｌ．３１Ｎｏ．７　２０１０年　　７月ＡＣＴＡＡＥＲＯＮＡＵＴＩＣＡＥＴＡＳＴＲＯＮＡＵＴＩＣＡＳＩＮＩＣＡＪｕｌｙ　２０１０收稿日期：２００９０７０７；修订日期：２００９０９１８基金项目：国防“十一五”预研项目通讯作者：张选平Ｅｍａｉｌ：[e-mail]　　文章编号：１０００６８９３（２０１０）０７１４３３１２基于组合拍卖的协同多目标攻击空战决策算法刘波１，张选平１，王瑞１，覃征１，２（１．西安交通大学电子与信息工程学院，陕西西安　７１００４９）（２．清华大学计算机科学与技术系，北京　１０００８４）犃犻狉犆狅犿犫犪狋犇犲犮犻狊犻狅狀犕犪犽犻狀犵犳狅狉犆狅狅狉犱犻狀犪狋犲犱犕狌犾狋犻狆犾犲犜犪狉犵犲狋犃狋狋犪犮犽犝狊犻狀犵犆狅犿犫犻狀犪狋狅狉犻犪犾犃狌犮狋犻狅狀ＬｉｕＢｏ１，ＺｈａｎｇＸｕａｎｐｉｎｇ１，ＷａｎｇＲｕｉ１，ＱｉｎＺｈｅｎｇ１，２（１．ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　７１００４９，Ｃｈｉｎａ）（２．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８４，Ｃｈｉｎａ）摘　要：针对多战机通过数据链共享信息、协同作战中的多目标分配问题，提出一种基于组合拍卖的协同多目标分配算法。改进并扩展了组合拍卖ＣＡＢＯＢ算法，重新设计了投标元组格式，增设了投标底价和任务上限对投标人的任务完成能力进行预审核，完善了算法的实用性；采用动态价格进行投标排序将算法扩展为非０１投标，解决因不能共享投标而无法协同攻击的问题；在此基础上，设计了新的期望贡献值上界的计算方法，改进了启发式剪枝规则，加快算法计算过程。仿真实验表明，所提算法与现有的几种算法相比在求解质量、稳定性和可扩展性上都有明显提高。关键词：空战决策；组合拍卖；协同工作；目标分配；启发式方法；超视距空战中图分类号：Ｖ２４７；Ｅ８３７　　　文献标识码：Ａ犃犫狊狋狉犪犮狋：Ｔｈｅａｉｍｏｆｔｈｉｓｓｔｕｄｙｉｓｔｏｐｒｏｖｉｄｅａｓｏｌｕｔｉｏｎｔｏａｉｒｃｏｍｂａｔｄｅｃｉｓｉｏｎｍａｋｉｎｇｆｏｒｃｏｏｒｄｉｎａｔｅｄｍｕｌｔｉｐｌｅｔａｒｇｅｔａｓｓｉｇｎｍｅｎｔｓｏｆｍｕｌｔｉｆｉｇｈｔｅｒｓｗｈｉｃｈｕｓｅｔｈｅｔａｃｔｉｃａｌｄｉｇｉｔａｌｉｎｆｏｒｍａｔｉｏｎｌｉｎｋｓｔｏｓｈａｒｅａｎｄｅｘｃｈａｎｇｅｃｏｍｂａｔｉｎｆｏｒｍａｔｉｏｎ．Ｂａｓｅｄｏｎｃｏｍｂｉｎａｔｏｒｉａｌａｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｓ（ＣＡＢＯＢ），ａｎｅｗａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．Ｔｏｍａｋｅｔｈｅａｌｇｏｒｉｔｈｍｍｏｒｅａｐｐｌｉｃａｂｌｅ，ａｎｅｗｂｉｄｔｕｐｌｅｉｓｄｅｓｉｇｎｅｄ；ｔｈｅｒｅｓｅｒｖｅｐｒｉｃｅａｎｄｔｈｅｕｐｐｅｒｂｏｕｎｄｏｆｔｈｅｍｉｓｓｉｏｎａｒｅｓｅｔｗｈｉｃｈａｒｅｕｓｅｄｔｏｐｒｅｃｈｅｃｋｔｈｅａｂｉｌｉｔｙｏｆｔｈｅｂｉｄｄｅｒｔｏａｃｃｏｍｐｌｉｓｈｔｈｅｍｉｓｓｉｏｎ．Ｉｎｏｒｄｅｒｔｏａｃｈｉｅｖｅａｃｏｏｒｄｉｎａｔｅｄａｔｔａｃｋ，ｔｈｅｄｙｎａｍｉｃｂｉｄｄｉｎｇｒａｎｋｉｓｕｓｅｄｔｏｉｍｐｒｏｖｅｔｈｅａｌｇｏｒｉｔｈｍｓｏｉｔｃａｎｓｕｐｐｏｒｔｔｈｅｂｉｄｄｅｒｓｉｎｓｈａｒｉｎｇｔｈｅｉｔｅｍｓ．Ａｎｄａｎｅｗｈｅｕｒｉｓｔｉｃｍｅｔｈｏｄｔｏｃｏｍｐｕｔｅｔｈｅｕｐｐｅｒｂｏｕｎｄｏｆｔｈｅｅｘｐｅｃｔｅｄｃｏｎｔｒｉｂｕｔｉｏｎｖａｌｕｅｉｓｐｒｏｐｏｓｅｄｔｏｓｐｅｅｄｕｐｔｈｅｃｏｍｐｕｔａｔｉｏｎ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｐｒｏｖｉｄｅｓｂｅｔｔｅｒｓｏｌｕｔｉｏｎｓｔｈａｎｃｏｎｖｅｎｔｉｏｎａｌｍｅｔｈｏｄｓ．Ｉｎａｄｄｉｔｉｏｎ，ｉｔａｌｓｏｐｏｓｓｅｓｓｅｓｂｅｔｔｅｒｓｔａｂｉｌｉｔｙａｎｄｓｃａｌａｂｉｌｉｔｙ．犓犲狔狑狅狉犱狊：ｄｅｃｉｓｉｏｎｍａｋｉｎｇ；ｃｏｍｂｉｎａｔｏｒｉａｌａｕｃｔｉｏｎ；ｃｏｏｒｄｉｎａｔｅｄｗｏｒｋ；ｔａｒｇｅｔａｓｓｉｇｎｍｅｎｔ；ｈｅｕｒｉｓｔｉｃｓ；ｂｅｙｏｎｄｖｉｓｕａｌｒａｎｇｅａｉｒｔｏａｉｒｃｏｍｂａｔ　　分布式网络化作战环境下，战机利用数据链共享战场态势，协同完成复杂任务是个重要的研究内容［１］。多目标分配是其中一个关键问题，包括有人战机／无人作战飞机（ＵｎｍａｎｎｅｄＣｏｍｂａｔＡｅｒｉａｌＶｅｈｉｃｌｅ，ＵＣＡＶ）混合目标分配和ＵＡＶ／ＵＣＡＶ目标（任务）分配，目的是确定多战机在一个决策时间片或一个时间序列中的任务（集），使战机间形成协同，以最小的代价达到最优的作战效能。这是个具有约束条件的组合优化问题，属ＮＰｈａｒｄ问题。解决思路是：首先建立协同任务模型，然后对模型进行优化求解，得出目标分配方案用于决策或辅助决策。在应用中常根据问题特征附加约束条件以简化模型，例如文献［２］以目标的价值毁伤（ＴＶＤ）、ＵＣＡＶ的损耗（ＵＣＡＶＡｔｔｒｉｔｉｏｎ）和执行任务预计消耗时间（ＴＥＴ）为主要指标建立多ＵＣＡＶ的任务分配模型。求解方法可分为集中式和分布式。集中式方法针对协同任务模型，采用神经网络、遗传算法（ＧＡ）、蚁群、粒子群等仿生算法和混合整数线性规划（ＭＩＬＰ）等规划方法，找出满足约束条件的最优或近优分配方案，进行多目标分配，这与数据链组网／退网时间较长且战机计算能力和智能性较差的场景相适应。例如：文献［３］首先计算协同优先权，然后通过神经网络和自组织特征映照（ＳＯＦＭ）网络训练形成分配方案；文献　　　　　　航　空　学　报第３１卷［４］通过确定战机犻攻击当前最大优势的敌机为“好”基因，然后在遗传中保留“好”基因改进遗传算法，得出分配方案，并与标准的遗传算法作了对比；基于用于解决广域目标搜索与摧毁（ＷＡＳＤ）任务的ＭＩＬＰ［５］，文献［６］扩展ＭＩＬＰ用于解决多ＵＡＶ对敌防空压制（ＳＥＡＤ）任务；文献［７］在ＭＩＬＰ基础上采用ＧＡ解决多目标分配中的非线性代价函数问题；文献［８］扩展了上述ＧＡ用于解决出现突发威胁的ＳＥＡＤ任务中的任务分配问题，并在此基础上提出一种并行的ＧＡ［９］提高性能；文献［１０］通过建立多目标整数规划数学模型，提出一种混合ＧＡ计算分配方案，并利用约束作为启发信息提高算法性能；文献［１１］采用ＧＡ改进多ＵＡＶ协同跟踪移动目标的规划问题；为提高算法的收敛速度，文献［１２］提出在蚁群算法中加入启发式信息进行局部改进的启发式蚁群算法得出分配方案；文献［１３］提出一种基于粒子群优化算法（ＰＳＯ）及ＰＳＯＧＡ的火力优化算法解决多批目标的防空火力分配问题。分布式方法针对协同任务模型，多采用合同网、拍卖算法等基于市场机制的算法，将各武器作战平台（战机或ＵＣＡＶ）定义为Ａｇｅｎｔ，参与协同作战的Ａｇｅｎｔ基于自主计算，根据自身能力及可获取的信息投标已划分的目标（集），由市场机制确定最优的分配方案，这与新型数据链和战机具有较强信息（文本和多媒体）交互能力和一定智能性的场景相适应。例如：文献［１４］采用分布协同拍卖算法解决具有时间约束的任务分配，通过建立一个拍卖队列依次拍卖目标，在时间约束下求出“较好”的近优解分配方案；文献［１５］通过扩展正向／逆向拍卖算法找出初始的近优分配方案，并通过链接局部的、通信代价低的Ａｇｅｎｔ间任务交换解决动态性问题；同样，为解决系统运行中动态性带来的任务更新问题，文献［１６］采用合同网解决多ＵＣＡＶ协同中的分布式任务分配，在此基础上，文献［１７］提出条件合同机制，文献［１８］提出合同网与部分全局规划结合扩展合同网协议，解决具有时间约束的协同任务的协调；为解决系统中存在的通信受限和信息不完整，文献［１９］提出一种协商模式解决未知区域目标搜索和打击的目标分配，在此基础上，文献［２０］和文献［２１］分别提出一种分布式拍卖方案和分布式顺序拍卖方案解决由于受限带来的任务分配冲突；文献［２２］提出一种分布式任务协商（ＤＴＣ）算法解决间歇性和异步通信应用。集中式方法关注算法本身对建模后的组合优化问题的求解能力，逻辑结构简单，中心节点汇总全部信息，计算出目标（任务）分配方案后进行分配。优点是对参与协同的节点的计算能力和智能性几乎没有限制，且中心计算对战机间的协同类型［２３］和协同关系不敏感：协同的同步性要求和协同的线性／非线性关系仅需在任务模型中考虑，个体不需考虑；缺点是通信线路依赖，对复杂问题的建模较困难，系统可扩展性和鲁棒性差。集中式方法适用于参与协同的节点较少，问题比较明确且环境变化速度较为缓慢的应用场景。分布式方法基于分布式网络化（网络中心战）作战实际武器部署的分布式特征，构建基于分布式体系结构的复杂问题求解模型。其优点是无中心依赖，可扩展性和鲁棒性强，求解能力也有一定优势；缺点是对Ａｇｅｎｔ（战机／ＵＣＡＶ）节点的信息交互和智能性有一定要求，且较难处理多战机以非线性协同完成具有同步性要求的侦察或攻击任务。当前分布式研究集中在战机／ＵＣＡＶ在一个决策时间片的单目标或一个较大时间尺度内的目标集［１７１９，２４２５］分配，属于一对一或一对多的目标分配（拍卖），即一架战机／ＵＣＡＶ分配一个或多个任务，较少研究多对多的目标分配，尤其是有同步性要求的协同侦察或攻击。分布式方法适用环境变化较快、节点众多且动态变化的场景。上述方法均不能直接应用于分布式网络化作战环境下多战机协同攻击多目标的场景，如有人战机及其他作战平台组成的混合编队对某一空域出现威胁的协同打击。１　协同多目标分配问题与建模１１　多战机协同多目标分配问题根据攻击目标特征的不同，战机／ＵＣＡＶ的目标分配问题分为对地攻击和对空攻击。协同对地攻击或对地防空火力压制，通过前期侦察和部署，目标分配时可设作战环境（含目标集）完全可感知或环境变化速度远低于战机／ＵＣＡＶ对环境变化的适应速度，目标集为静态或低速移动目标，环境状态对目标分配的影响较小。基于数据链，战机／ＵＣＡＶ通过预编程进行部署，目标分配在此情况下按照预先设定的算法得出的方案完成，为提高系统的鲁棒性，会增加冲突消解表和规则集使战机／ＵＣＡＶ在一定范围内具有一定的智能性和自适应性。在此情况下，构建目标４３４１　第７期刘波等：基于组合拍卖的协同多目标攻击空战决策算法　　　　　分配模型的主要因素是总油耗（或距离代价，也可映射为时间代价）。考虑到采用航迹规划对非目标的威胁集进行避让，通信代价、风险代价、性能等有时也作为目标分配时的影响因素。如文献［１８］以时间和风险代价为主要因素构建目标分配模型。此时，目标分配是构建一个决策时间片内多战机／ＵＣＡＶ完成任务集的最优航迹，以最短的距离和适当的执行顺序覆盖目标集，协同方式也以打击／确认、协同跟踪跨区目标等为主，系统模型的时间尺度较大。多战机协同对空攻击包括攻击高机动目标、消除突发威胁、拦截高威胁移动目标等，环境与竞争对手的变化速度较快，环境状态对目标分配有较大影响。在此高对抗环境构建协同工作模型，对战机的智能性和通信、数据处理有较高要求。首先，根据要求与约束条件确定衡量性能的时间尺度，一般而言，高对抗环境下时间尺度较小。然后，确定目标分配模型需考虑的因素：在小尺度情况下，包括双方的性能、速度、攻击角度、距离及可能出现的干扰等；一个完整的战斗过程还需根据态势确定攻击波次、作战顺序等；对于协同攻击，异构作战武器间协同方式也需作为建模考虑因素。如文献［１２］以战机与目标的距离、离轴角、速度为主要因素建模。此时，目标分配是构建一个决策时间片内（小时间尺度）的目标分配模型，将多战机可攻击区域内的目标集分配给战机，实现最优攻击效能。分布式网络化作战环境下，战机在目标分配方面的协同方式主要是多对多的武器协同，有时间同步攻击要求。ＵＣＡＶ与有人战机组成混合编队参与空战涉及部署、控制等的时间同步性规划问题，本文暂不予关注。本文研究