基于人机协作的无人集群搜索方法研究

   无人技术的快速发展使得无人集群逐渐成为人类的合作伙伴。人机交互系统[1]是由指挥员与机器人组成的复杂系统，他们相互协作以实现一个共同的目标。本文聚焦人机交互的一个子类，即指挥员与无人集群协作搜索问题。无人集群是由多个无人平台组成的群体，如无人机集群、无人车集群[2-4]。在无人集群自动规划领域，无人平台会根据其当前状态和附近环境，与相邻无人平台相互交互以及自己的局部控制规则进行自动规划。人机交互系统在未知远程环境和高度非结构化的任务中具有卓越性能，能够减少人员工作量，完成单个无人平台无法完成的任务，且具有更高的故障鲁棒性和可扩展性。现如今，人机交互的性质也发生了变化，由单人与单无人平台协作逐渐发展为多人与单无人平台交互、多人与多无人平台交互、单人与多无人平台交互[6]。一般根据自动化层级来描述机器人自主程度[7]，10级表示机器人具有完全自主能力，而1级表示人类需要操控所有行动。现有机器人技术远未达到10级，因此仍需要人为干预来完成复杂任务，例如进行更高级的推理和决策。

   一些学者对人与无人集群协作问题进行过研究。Aamodh提出了一种协作框架，在框架中指挥员能够控制集群的形状和编成[8]。Shishir研究表明适当的人与无人集群协作可以使无人集群受益，从而能够更好地达成目标[9]。指挥员与无人集群协作方式很多，其中一种是指挥员向无人集群提供辅助消息。在很多情况下指挥员能够根据经验或其他消息途径为无人集群提供消息，消息可能降低信息的不确定性，从而降低无人集群决策的复杂度，进而提高系统整体性能。事实上，从指挥员获得所需信息的最直接方法是遇到情况直接询问。假设无人集群具备较高自主能力，能够自己完成任务，偶尔会得到指挥员的支持。指挥员作为消息提供者，主要提供信息状态和决策行动2种方式。作为信息状态提供者，常见的问题框架是HOP-POMDP(human observation provider partially observable markov decision process)[10]。HOP-POMDP考虑了Agent在规划决策时能够咨询指挥员，通过咨询获得必要信息，但指挥员可能提供非完整信息，且不一定能实时响应。作为决策行动提供者，常见的框架为MU-POMDP(model uncertainty partially observable markov decision process)[11]。MU-POMDP考虑了转移函数、观测概率和回报值不确定的规划过程，Agent向指挥员询问一系列“是/否”问题或者描述行动列表，然后由指挥员确定采用何种行动。上述问题模型与本文提出的问题框架有所不同，因而其求解算法无法有效地应用于提出的搜索问题。

    人与无人集群协作决策可以抽象为一种方案空间探索问题。假设存在很多备选目标区域，无人集群选择其中若干区域进行搜索，方案可以认为是无人平台搜索一个目标区域的过程，所有方案的集合称为方案空间。方案空间越大，越有可能包含最有价值的目标。对于方案空间搜索问题，通常将其抽象为一种目标优化问题。根据目标的数量，可以将优化问题分为单目标优化和多目标优化。为了便于分析，多个目标可以整合为单个目标。现有研究中，每个方案的回报值是确定的，可以直接得到而无需经过复杂计算。目前普遍采用帕累托最优方法，如NSGA-II(non dominated sorting genetic algorithm II)和NSGA-III(non dominated sorting genetic algorithm III) [12-13]，以及这些算法的扩展算法。这些算法适用于输入输出关系确定的问题中，但难以有效解决本文的问题框架，即无人集群的行动可能产生大量的、甚至无穷多的不同数值的搜索问题。指挥员首先需要确定拟探索方案的先后顺序，然后在已搜索的方案中选择最有价值的若干方案。换句话说，问题的目标是寻找到最优搜索路径，以保证在有限时间和资源内寻找到最优方案。该问题类似于旅行商问题[14-15]，最优搜索路径的计算复杂度为O(n22n)O(n22n)，其中n表示方案空间中的方案数；但又不同于旅行商问题，本文考虑的路径优选问题中每种方案的价值服从某种分布，准确的价值在方案被探索之前是未知的。考虑到搜索目标需要耗费一定代价，搜索路径根据需求长度可调。Blanco等[16]提出了一种搜索算法，决策者通过花费一定代价以获取未知方案的信息，并提出了停止搜索的条件。Weitzman[17]提出了一种基于评判指标的顺序搜索问题，不过该方法适用于选择一个最优方案的情景。Chen等[18]提出了一种用于人工辅助机器人决策的最优搜索算法，同样该方法只能选取一种最优方案，无法解决本文提出的问题。

   本文考虑的场景是假设具有高度自主性的无人集群在人工干预下对敌方目标区域进行探测，以求在大范围环境中寻找到若干最有价值的区域。由于先期情报不准，无法确定高价值目标具体位置。此外，派遣无人集群执行任务时需要一些代价，一方面需要耗费燃料，另一方面有可能被对手击毁。因此，需要无人集群通过搜索判断不同区域的价值，以便为下一步行动提供支撑。因指挥员能够获取额外的信息以弥补无人集群的不足，即指挥员可以减少无人集群搜索过程的不确定因素，所以在很多情况下，人工干预的无人集群规划是十分必要的[5]。但是指挥员的精力和能力是有限的，难以实时操控每个无人平台，因而无法同时为所有无人平台分析和处理数据。

   鉴于此，本文聚焦于如何以有限的代价和资源寻找到最有价值的目标。高价值目标可以指指挥所、火炮阵地、机场等指挥员感兴趣的事物。本文弱化了实际应用背景，以便提出的问题框架以及求解算法具有一般性。指挥员与无人集群协作搜索问题面临三方面挑战：①各个区域具有不确定性。在派遣无人集群前往目标区域探测之前需要收集先验知识，如卫星图像。先验知识一方面具有不确定性，另一方面能够作为启发式信息辅助决策；②派遣无人集群前往目标区域探测需要花费代价，如油耗、损坏等。因而指挥员需要决定是继续探测下一个地区，还是停止搜索并选择已探测的最有价值的区域；③进行探测的手段很多，例如，无人机实地抵近侦察，或者回传高空侦察数据以寻求人工分析，因此指挥员应权衡不同行动的效用和成本。

   本节给出了人与无人集群协作搜索问题的概念定义，并将该问题抽象为一种动态规划问题。

   把地理环境划分为若干区域，无人集群需要在这些区域中找到高价值目标，如果包含的高价值目标越多，则这片区域就越有价值。无人集群的目标是以尽可能少的代价找到价值尽可能高的若干区域。假设每个区域的价值是独立的，在被无人集群探测之前具体数值是未知的。

   定义1(搜索价值)：搜索价值是指无人集群探索某个区域的必要性综合度量。

   搜索价值由目标的重要程度决定，目标越重要，该目标所具备的价值就越大，探索这片区域的价值也就越高。考虑到先验态势信息的不准确性，每片区域的价值事先是不确定的。假设不同区域的价值是相互独立的。对于区域u∈Uu∈U，其价值xuxu服从概率分布Fu(xu)Fu(xu)，其中U表示所有备选区域，或称为方案空间。无人集群可以采用抵近侦察或者高空侦察的方式获取信息。其中，抵近侦察能够获取区域的确切价值，高空侦察数据需要成功咨询指挥员后才可能获得确切价值。另外，不同行动耗费的成本是不一致的，比如抵近侦察就存在被击落的风险，而高空侦察则不易被击落。

   定义2(搜索代价)：搜索代价是指无人集群探索某个区域时的成本综合度量。

   派遣无人集群前往目标地点搜索是需要耗费成本的，记为c∈R+c∈R+。假设采用不同行动搜索不同区域的代价是已知且相互独立的。那么，无人集群在考虑进一步探索时，需要权衡搜索价值和搜索代价的关系，即回报值。回报值可以认为是净效益，本文无人集群的目标是使回报值最大化。

   定义3(回报值)：回报值是搜索价值与探索成本之差。

   每个区域的状态分为状态未知、状态已知和状态分析3类，如图1所示。状态未知是指该区域还未被无人集群探索，确切价值尚不可知；状态已知是指该区域已经被无人集群探测过，已经查明了确切价值；状态分析是指该地区正在被无人集探测，无人集群正向指挥员请求数据分析。可以采用多种手段进行探测，不失一般性，无人集群主要有2种手段：①无人集群前往目标区域u进行抵近侦察，采用多个视角和多种传感器收集和处理数据，记为a'uau'；②无人集群前往目标区域u进行高空侦察，并请求指挥员进行数据分析，记为a′′uau″。所有行动集合记为A={a'u,a′′u|u∈U}A={au',au″|u∈U}。

图1   方案状态转移关系

Fig. 1   Scheme state transition relationship

人与无人集群协作搜索被形式化建模为一类多Agent系统动态规划问题，其中无人平台被抽象为Agent，每个区域被称为一个方案。将备选方案集合记为u∈Uu∈U，将其分为2个互斥集合：①不断增加的已探索方案集合I∈UI∈U；②未探索方案集合I¯∈UI¯∈U，I⋃I¯=UI⋃I¯=U，I⋂I¯=∅I⋂I¯=∅。每个Agent在决策时，可以选择是否从集合I¯I¯中选择一个未探索方案进行探索，此时可以采用抵近侦察和咨询指挥员两种方式获得确切回报值；或者该Agent停止探索并从集合II中选择一个已探索方案作为最终方案。设定整个集群一共选取|K|K个方案，每个Agent只能选择一个最有价值的方案，使探索价值最大化：

求解问题的充分统计量记为(I¯,y)(I¯,y)，称为系统状态。系统状态分为2部分：未探索方案信息I¯I¯和已探索方案集合y={y1,y2,⋯,y|I|}y={y1,y2,⋯,yI}。将Agent系统多动态规划问题转化为系统状态评估函数。

定义4(系统状态评估函数)。系统状态评估函数为当已知价值集合为y且未探索方案集合为I¯I¯时，执行最优策略能够获得的期望回报值，记为ψ(I¯,y)ψ(I¯,y)。

由于每个方案探索价值和探索成本是独立的，因此集群的期望回报值可以分解为每个Agent的期望回报值。

式中：ψk(I¯k,yk)ψk(I¯k,yk)为第k个Agent的子系统状态评估函数。对于任意2个Agent w,v∈Kw,v∈K所选择的方案yˆw,yˆvŷw,ŷv，有yˆw≠yˆvŷw≠ŷv，表示每个Agent选择不同的方案。每个Agent都有局部方案空间，不同Agent的方案空间可能交叉Uw⋂Uv≠∅Uw⋂Uv≠∅，也可能不交叉Uw⋂Uv=∅Uw⋂Uv=∅。对于每个子集I¯kI¯k和价值集合ykyk，子系统状态评估函数ψk(I¯k,yk)ψk(I¯k,yk)需要满足式(3)所示的迭代关系。不失一般性，本文以Agent k∈Kk∈K为例进行说明，其中K表示无人集群索引集合。

  式中：ψ'k(I¯,yk)ψ'k(I¯,yk)为Agent k执行抵近侦察行动后的系统状态评估函数；ψ′′k(I¯,yk)ψ″k(I¯,yk)为Agent k执行询问指挥员行动(记为a'a')后的系统状态评估函数；p为指挥员响应并成功分析出该方案价值(记为a′′a″ )的概率；c'i,c′′ici',ci″为对于方案i，Agent执行行动a'a'和行动a′′a″所耗费的成本。当系统状态为(I¯k,yk)(I¯k,yk)时，Agent k需要确定是停止搜索并从集合ykyk选择最大价值yˆkŷk，或是在比较行动a'iai'和行动a′′iai″效果后继续探索未知方案i。

   通过上述定义，本文将人与无人集群协作搜索问题建模为一种动态规划问题。该问题特点是递归计算，因此难以直接求解状态评估函数。

  本节提出了一种基于顺次分配的动态规划(sequential allocation based dynamic planning，SADP)算法，通过决策指标与采样值之间的大小关系来选择行动。

  对于每个方案i，执行行动a'iai'和行动a′′iai″的决策指标分别记为d'idi'和d′′idi″。决策指标是继续探索与停止探索的综合度量。

  参考文献[18]，可以解算式(6)得到：

  根据系统状态ψ(I¯,y)ψ(I¯,y)和指标集合{c'i,c′′i/p|i∈I¯}{ci',ci″/p|i∈I¯}，可以设计一种简单但最优的搜索规则，分为判断规则和选择规则。判断规则是指如果Agent要进一步探索未知方案，则选择决策指标最大的未知方案，同时选择对应的行动；停止规则是指如果当前最大价值大于所有未知方案的决策指标时，则停止搜索并选择具有最大价值的方案作为最终方案。

   通过该规则，复杂的系统状态函数计算问题就转化为简单的指标判断问题，且每个指标的计算都是独立的，不受其他方案价值概率分布的影响。

    在探索程序中，首先根据式(6)和(7)计算所有方案所有行动的决策指标，并保存至集合ππ中。其次嵌套遍历所有Agent k∈Kk∈K和每个Agent的未知方案空间UkUk。在嵌套遍历中，应先找出集合ππ中最大指标 d* d*，以及对应的方案i*i*、行动a*a*和代价c*c*。为了便于描述，指标集合是以全集为基础计数，而不以每个Agent的局部集合计数，即π={d'i,d′′i |i∈I¯}π={di',di″ |i∈I¯}。如果最大采样价值大于最大决策指标yˆk≥d*ŷk≥d*，则停止搜索并返回最大采用价值yˆkŷk、最终方案iˆkîk和累积搜索代价；反之则进入仿真程序G，获取是否咨询成功s∈{True, False}s∈{True, False}以及采样价值x。如果获得确切采样价值，那么更新集合IkIk、I¯kI¯k、πkπk和累积搜索代价cc。

  算法1：探索程序

在仿真程序G中，如果采取行动a′′a″，则将生成的随机数r与咨询成功率p对比，以判断能否咨询成功。另外，符号“~”表示采样，x∼Fi(xi)x∼Fi(xi)表示对概率分布Fi(xi)Fi(xi)进行一次采样。

算法2：仿真程序

本节设计了3个典型场景用以评估算法对于方案空间可扩展性的适应程度。一般而言，咨询代价小于抵近侦察代价c′′i<c'i,i∈Ici″<ci',i∈I，但是咨询次数未知。设定所有搜索价值函数服从独立的均匀分布，即Fi(xi)∼U(ai,bi)Fi(xi)∼U(ai,bi)，ai∼U(1 000,1 500)ai∼U1 000,1 500，bi∼bi∼U(1 500,2 000)U1 500,2 000，i∈Ii∈I；设定搜索代价也服从独立的均匀分布，即c'i∼U(10, 20)ci'∼U10, 20，c′′i∼U(3, 4)ci″∼U3, 4，i∈Ii∈I；咨询成功概率为p={0,0.1,0.2,⋯,1}p=0,0.1,0.2,⋯,1时，无人集群选取|K|=9K=9个方案，每个场景独立重复运行1 000次仿真。评估3个场景下算法的性能指标：

场景A1：方案空间大小为|I|=50I=50。

场景A2：方案空间大小为|I|=500I=500。

场景A3：方案空间大小为|I|=5 000I=5 000。

场景A1仿真结果如图2所示。实验结果表明在这些场景中SADP回报值远高于FEA和TEA的回报值，SADP运行时间略高于FEA和TEA，FEA和TEA探索次数非常接近，随着p的增加，SADP探索次数波动增长。当p≥0.3p≥0.3时，SADP咨询次数大于FEA和TEA咨询次数。

图2   场景A1仿真结果

Fig. 2   Simulation results in scenario A1

图3   场景A2仿真结果

Fig. 3   Simulation results in scenario A2

图4   场景A3仿真结果

Fig. 4   Simulation results in scenario A3

设定所有搜索价值函数服从独立的均匀分布，即Fi(xi)∼U(ai,bi)Fi(xi)∼U(ai,bi)，ai∼U(1 000,1 500)ai∼U(1 000,1 500)，bi∼Ubi∼U(1 500,2 000)(1 500,2 000)，i∈Ii∈I；设定搜索代价也服从独立的均匀分布，即c'i∼U(10,20)ci'∼U(10,20)，c′′i∼U(3,4)ci″∼U(3,4)，i∈Ii∈I。此外，咨询成功概率设为p=0.3p=0.3，方案空间大小设为5 000，无人集群选取|K|={1,3,⋯,19}K=1,3,⋯,19个方案时的回报值、运行时间、搜索次数、咨询次数4项性能指标。每个场景独立重复运行1 000次仿真。

场景B仿真结果如图5所示。实验结果表明随着|K|K的增加，所有算法的回报值、运行时间、搜索次数、咨询次数都逐渐增加。此外在这些场景中，SADP回报值、运行时间、搜索次数、咨询次数高于TEA，而TEA又高于FEA。

图5   场景B仿真结果

Fig. 5   Simulation results in scenario B

   本节设置若干场景，但实验结果具有一些共性。比如在场景A中，随着变量p的增加，回报值略有增加，而运行时间会逐渐减少。这是因为p的增加会减少咨询次数并降低期望咨询代价，从而提高期望回报值。值得说明的是，p=0.3是SADP算法的拐点，当p<0.3时，其回报值、运行时间、探索次数、咨询次数都处于低位，而当p=0.3时有明显的提高。这与实验参数设置有很大关系，当p=0.3时，行动a'a'的代价c'c'基本上大于行动a′′a″的代价c'/pc'/p，因此Agent将采用咨询指挥员而不是采用抵近侦察行动。此时即便搜索路径不变，代价值也会降低，回报值增加，咨询次数增加。进一步，代价c的变化会影响决策指标d的变化，从而影响搜索顺序以及何时停止搜索。决策指标d具有期望回报值类似的意义，c与d呈负相关，如果c越小，则d越大。对于场景B，随着变量|K|K增加各项指标随之增加。很显然毕竟选择的方案多了，而每个方案回报值为正，所以回报值肯定增加。同样，运行时间、搜索次数、咨询次数也会增加。