人机协同搜救优化问题的计算求解研究

郑宇军，杨 潇，杜怡辰，江勋林

(1.杭州师范大学 信息科学与技术学院，浙江 杭州 311121；2.中国人民解放军陆军步兵学院 工程技术与应用系，江西 南昌 330100)

同各种自然和人为灾难抗争是人类社会的一个永恒课题。在发生严重伤亡的灾害中，生命搜救是第一要务。应急搜救能力是灾害应急管理中的一项核心能力，是处置应急突发事件、维护社会安全稳定的重要基石[1-2]。在刚刚过去的2021年，就有甘肃白银马拉松事故、云南哀牢山地质人员失联、山东烟台海域“天丰369”货船沉没等事件中的搜救行动牵动了亿万国人的心。从技术发展的角度来看，人类社会的搜救能力的进步主要经历了4个阶段：

(1)人类社会中早期，应急搜救主要依赖人力(包括人类驯养的一些动物)进行。搜救能力主要取决于社会所能组织的人力资源，以及管理者和搜救人员自身的经验和水平[3]。在面临地震、洪水等重大灾害时，早期社会往往难以组织起大规模有效的应急搜救行动，这是历史上很多灾害造成巨大伤亡的重要原因。

(2)进入工业革命以来，使用蒸汽和电力等能源的运输、探测、挖掘等装备在应急搜救中得到广泛应用。这些机械化装备极大提高了搜救的能力和效率，同时也给管理决策者带来了新的挑战，即要对人力和各类装备进行科学的规划调度；此外，救援人员使用装备的技术水平也在很大程度上影响了搜救能力[4]。

(3)进入信息技术革命以来，人们对灾情、环境、任务、资源等数据和信息进行采集、处理、利用的手段大大丰富。例如可通过卫星快速获取灾害现场遥感影像，通过手机实时获取被困人员定位并与被困人员进行通信，通过信息管理系统全方位掌握救援人力和资源数据等，这些都能为管理决策者提供重要支持，从而极大提高任务决策的效率和可信性。但这同时也对灾害数据分析处理能力和任务规划调度能力提出了更高的要求。特别是在发生大规模灾害时，往往需要对多地区、多部门救援力量和资源进行统筹调度，并在救援过程中进行充分的数据共享和信息交换。该问题引起了国内外管理者和研究人员的广泛重视[5-7]。

(4)伴随着新一代技术革命，大数据支持下的无人智能技术得到飞速发展，无人机、无人艇、地面搜救机器人、水下搜救机器人等自主智能装备为应急搜救提供了全新的手段，并在大量实际应急搜救行动中取得了很好的效果[8]。回顾2008年汶川地震，由于灾区通信中断、大量台站被破坏，一线灾情无法及时被送出，最终是数百名空降兵“舍命一搏”高空跳伞进入灾区，才打通与外界的联系通道；而到了六年后的鲁甸地震，4个无人机组在第一时间进入灾区并传回高分辨率影像图，被认为是我国无人机救灾应用的历史性时刻。当然，智能机器人同样需要对其行动路线和任务进行合理的规划和调度，特别是多机器人的协同调度具有很高的难度[9]。

近年来，机器人搜索方法研究引起了广泛的兴趣。这些方法可以分为局部搜索和全局搜索两大类。局部搜索方法主要规划机器人当前或未来有限时间段内的动作，常用的算法有梯度下降算法[10]、贪婪算法[11]、特定边界搜索算法[12-13]，以及这些算法的混合形式[14-15]。全局搜索方法则针对某个全局目标函数(如最终搜索成功概率或预期搜索完成时间)来预先规划完整的搜索路径，常用的算法有优度比搜索[16]、Monte Carlo树搜索[17]、扩展邻域搜索[18]等问题特定的启发式搜索算法，以及遗传算法[19]、细菌觅食算法[20]、差分进化[21]、蚁群优化[22，23]、粒子群优化[24]等元启发式搜索算法。陈佳[25]等人研究了无人驾驶救助船路径规划算法，在Dijkstra最短路径算法的基础上使用蚁群优化算法进行路径规划。Mendonca[26]等研究了海难幸存者搜救中的无人艇与无人机协作调度方法。Wang[27]等研究了海上搜救无人机通过深度学习进行目标定位和搜索的方法，通过假设生成和验证来提高对幸存者的识别精度。Wang[28]等提出了一种无人机搜索未知目标的超启发式算法，其中即考虑了每个待搜索区域中的目标存在概率，也考虑了无人机在不同搜索模式下的搜索成功概率。Hong[29]等将该问题扩展到多无人机场景，并提出一种融合自适应局部搜索的文化基因算法来求解该问题。Du[30]等研究了一个景区失踪游客的无人机搜索问题，提出了基于地理位置及时空关系的目标概率估计方法，并设计了无人机路径规划的进化算法。

但在很多复杂任务场景中，智能机器仍无法完全取代人的作用。例如在地震被困人员搜救中，无人机可用于快速寻找被困者，随后还需要救援人员帮助其脱困并进行急救治疗。人机之间的高效智能协同是提高此类任务能力的关键。但目前对人机协同搜救方法的研究还很有限。Liu[31]研究了一种基于贝叶斯推理的分配算法，用于将待搜索区域合理划分并分配给人和无人机进行搜索。Hong[32]等研究了一种基于强化学习的控制方法，用于简化搜救过程中人对机器的控制操作。还有一些研究[33]关注如何提高人机交互体验。但这些研究都并未体现真正意义上人机协同的内在需求[34]。未来复杂的搜救任务不仅需要先进的智能机器人，更需要人机之间的高效智能协同来提高搜救能力。近年来，本团队在长期研究应急搜救调度方法及其实践应用的基础上，开展了人机协同搜救调度方法的探索性研究[35-36]，一方面体现机器人对提升任务能力的巨大作用，另一方面关注人在任务中不可替代的环节，从搜救任务的内在需求出发，通过人机协同优化调度，突破任务性能瓶颈，从根本上提升任务能力。

本文考虑的场景是：在指定区域内，多个人工搜索队与机器人协同搜救某个目标，如果人工搜索队发现目标，则任务完成；如果机器人首先发现目标，则还需要人工搜索队到达目标位置方能完成任务。若是机器人首先发现目标，接下来的目标行为可分为3种模式：(1)目标静止等待救援；(2)目标主动向人工搜索队靠拢；(3)目标逃避搜索。针对每种模式，分别构建问题的优化模型，以任务完成的期望时间最小化作为目标函数。为了优化目标函数，人工搜索队的动作路径和机器人的动作路径之间需要进行有效协同：如果人和机器人过于分散，发现目标的时间可能较早，但机器人发现目标后，人工搜索队可能需要很长的时间才能到达目标位置；反之，如果人和机器人过于靠近，机器人发现目标后人工搜索队可以很快到达目标位置，但发现目标的时间可能较长。因此问题的决策需要在上述两种情况之间取得一个较好的平衡。本文设计了进化算法与局部搜索相结合的混合优化算法，对3种模式下的人机搜救行动进行协同优化调度。最后，基于我国南方山区及丘陵等典型地貌构建搜救问题测试实例，计算实验的结果验证了本文所提模型及算法的有效性。

1 人机协同搜救优化问题的典型数学模型

1.1 目标被发现后保持静止的模型

图1 不同搜索模式示意图

搜救任务有两个关键时间点，一是目标被发现的时间，这里记为T；二是人工搜索队接触到目标的时间，这里记为T*。如果是人工搜索队首先发现目标，此时有T=T*，任务完成；当机器人首先发现目标时，距离目标最近的人工搜索队将从T时刻开始赶往目标所在地，此时有T

先考虑目标被发现的时间。如果目标被人工搜索队发现，时间记为Th；如果目标被机器人发现，时间记为Tu。初始时发现目标的概率为0，则有：

P(Th=0)=0，

(1)

P(Tu=0)=0.

(2)

在搜索行动中，一般同一时刻同一区域最多只有一个搜索单位(人工搜索队或机器人)对其执行搜索操作，故不同搜索单位发现目标的事件是相互独立的。人工搜索队在任一时刻t>0发现目标的概率公式可展开为

(3)

其中

(4)

对应的，机器人在任一时刻t>0发现目标的概率公式可展开为

(5)

其中

(6)

(7)

(8)

其中

(9)

式(9)等号右侧if分支条件表示机器人在t′时刻发现目标，而后最近的人工搜索队使用(t-t′)的时间段赶到目标位置。

(10)

即使只考虑人工搜索队或只考虑无人机，其搜索路径规划可视为经典的车辆路径规划问题，该问题已知为NP难题[37]。本问题在人机各自路径规划的基础上还考虑人机之间的协同，其复杂度高于车辆路径规划问题。

1.2 目标被发现后向人工搜索队靠拢的模型

图2 目标被发现后向人工搜索队靠拢示意图

(11)

若是目标所在区域不能完全自由行动，则要找出其可以行动的路径，并计算人工搜索队到目标最短路径距离来替换式(11)中的右侧的分子项。

(12)

该条件的判断比1.1节模型中的条件判断更为复杂，因此问题复杂度也更高，同样属于NP难题。

1.3 目标被发现后逃避搜救的模型

(13)

再根据一元二次方程求根公式可得Δt(j*)。实际计算中，选取三个可能的目标移动方向，即与机器人方向一致，以及与机器人方向垂直(夹角为90°或270°)，对三个θ角度分别计算Δt(j*)值，并以三者的平均值作为Δt(j*)的最终估值。

图3 目标被发现后逃避搜索示意图

若是目标所在区域不能完全自由行动，则可以对其可能选择的各条移动路径分别计算Δt(j*)，在以这些结果的作为Δt(j*)的最终估值。

最后将Δt(j*)的最终估值代入式(12)，计算任务完成时间的概率分布。该问题同样也属于NP难题。

2 人机协同搜救优化问题的混合进化算法

上述问题属于复杂的路径规划问题，问题解空间随着搜索区域数量和搜索单位数量的增加而呈爆炸性增长，传统精确优化算法难以有效应对[37]。特别的，上述问题的目标函数需要基于时间变化不断推演，计算量很大；而问题的优化目标是基于概率估计的期望值，没有必要追求绝对最优解。因此，这里提出一种混合进化算法来求解上述问题。算法首先生成一个种群的初始解，而后对种群进行迭代进化。在每次迭代时，对每个解首先进行变异操作；如果变异解优于原始解，则替换原始解；否则再对该解进行迁移操作。算法还对找到的较优解进行局部搜索，以提高解的精度。算法的基本流程如图4所示。下面分别介绍算法各部分操作的实现过程。

图4 求解人机协同搜救优化问题的启发式算法流程

2.1 初始解生成

问题的每个解z的编码由n1个人工搜索队的动作路径{x1，x2，…，xn1}和n2个机器人的动作路径{y1，y2，…，yn2}组成。设算法种群大小为N，初始种群中包含N-2个随机生成的解，以及2个采用不同贪心策略得到的解。注意无论采用哪种方式，人工搜索队的路径必须由相邻的子区域构成，机器人则视行动方式决定其路径是否要由相邻的子区域构成(如地面机器人需要；无人机不需要，它可以快速飞往一个远处的子区域进行搜索)。随机生成解时，通过随机选择尚未分配的可行子区域并随机设置搜索模式来逐步构造每条路径。采用第一种贪心策略构造路径时，每次在尚未分配的可行子区域集合中选取目标发现概率p(i，t)ph(i，k1，t)或p(i，t)pu(i，k2，t)与预期搜索时间th(i，k1)或tu(i，k2)的比值最大的一个子区域并设置相应的搜索模式。采用第二种贪心策略构造路径时，先对机器人采用第一种贪心策略构造路径，而后再对人工搜索队构造路径，每次在尚未分配的可行子区域集合中选取与机器人最接近的一个子区域，以便于在机器人发现目标后快速到达目标位置。

2.2 变异操作

变异操作的方式是将解中的一部分路径进行重新配置，从而提高种群的多样性。这里采用一种自适应的变异操作，每个解变异的程度与解的适应度成反比：较优的解变异度较小，即在较小范围内搜索；较差的解变异度较大，即在较大范围内搜索。每个解z的变异度通过其变异率ν(z)来控制，其初始值统一设为0.5；在每次迭代后，解的变异率根据其目标函数值f(z)按下式进行更新：

v(z)=v(z)·α-(fmax-f(z)+ε)/(fmax-fmin+ε)，

(14)

其中fmax和fmin分别代表种群中解的目标函数值的最大值和最小值，α是一个大于1的常数，ε为一个极小的正数以避免发生除以0的情况。该公式借鉴的是水波优化启发式算法的波长控制方程[38]，它使得变异率随迭代次数不断减小，即算法早期侧重于全局搜索、后期侧重于局部搜索；而且解越优、变异率减小得越快、局部搜索也越明显。这样能够在局部搜索和全局搜索间达到一个较好的平衡。

对每个解z进行变异操作的具体步骤如下：

(1)设置一个空的待变异路径集Pz；

(2)对解中的每个路径xj或yj，以ν(z)的概率加入Pz；

(3)对Pz中的所有路径进行子区域重新随机分配和搜索模式重新随机设置，Pz以外的路径保持不变。

2.3 迁移操作

当变异操作未能改进z时，算法对其进行迁移操作，该操作和遗传算法中的杂交操作思想类似，但它不是对两个解进行组合，而是使当前解向种群中的其它优秀解进行学习，以求提高解的质量。和变异操作的变异率控制类似，每个解z的迁移操作通过一个迁移率μ(z)来控制，其计算公式如下：

μ(z)=(f(z)-fmin+ε)/(fmax-fmin+ε).

(15)

式(15)借鉴的是生物地理学优化启发式算法的迁移率计算方程[39]，它使得较差的解具有较大的迁移率，从而更多地向其余解学习；较优的解具有较小的迁移率，从而改变较小。这也能够促进局部搜索和全局搜索间的平衡。

2.3.1 人工搜索队动作路径迁移

2.3.2 机器人动作路径迁移

(3)对yj中的子区域进行重排序，每次选择距机器人最近的子区域加入到路径中。

迁移操作后，如出现某些子区域未被搜索或被重复搜索的情况，如果对每个出现在多条路径中的子区域a，使其只保留在目标发现概率与预期搜索时间的比值最大的一条路径中；对每个未被搜索的子区域a，尝试将其插入到每条现有路径中，最后选择插入后任务完成时间最早的那条路径。

2.4 增强局部搜索

每当算法通过变异操作或迁移操作找到一个新的当前最优解z*，则对其进行增强局部搜索来提高解的质量。具体操作方式是对其每条动作路径上的每个区域，尝试改变搜索模式k为k±1(但不超过预定上下限)，如目标函数得以改进则保留新模式。

算法1给出了整个算法的伪代码，其中随机函数rand()用于生成[0，1]之间的一个随机数，算法的终止条件通常是迭代次数或目标函数估值次数到达指定上限。人机协同搜救优化问题的启发式求解算法框架如图5所示。

图5 人机协同搜救优化问题的启发式求解算法框架

3 计算实验

计算实验基于四川达州山区和江西东北部丘陵地区两种实际地形。对每种地形分别设置两个不同大小的搜索区域(山区搜索面积分别为9.1 km2和21.2 km2，丘陵地区搜索面积分别为15.6 km2和53 km2，划分的子区域数m分别为18、45、29和105)，并分别模拟地震人员失踪(目标不能移动)、游客受伤失联(目标可移动配合搜救)、逃犯逃跑(目标逃避搜索)3种场景模型，根据实际地貌气候等信息进行概率估计。搜救行动所允许的最大时间tmax设置为5 min。每个场景以不同数量的人工搜索队和无人机为搜索单位(n1×n2分别为2×2，4×3，10×5)构造3个测试实例，共计36个测试实例。在这些问题实例上，将本文所提方法与以下6个方法进行比较：

(1)由当地应急管理工作人员基于经验制定搜救方案；

(2)基于贝叶斯概率的贪心(Greedy)算法[40]，它总是在未分配的子区域中选择目标存在概率最大的子区域分配给最近的搜索单位空闲无人机；

(3)基于部分可观察马尔科夫决策过程(Partially observable Markov decision procedure，POMDP)的启发式算法[41]，它通过在每个时间片内最大化期望发现概率来决定各个搜索单位的行动；

(4)一种鸽群启发的粒子群优化(Pigeon-inspired particle swarm optimization，P-PSO)算法[42]来求解本文的优化模型；

(5)一种蚁群优化(Ant colony optimization，ACO)算法来求解本文的优化模型；

(6)一种自适应大规模邻域搜索(Adaptive large neighborhood search，ALNS)算法来求解本文的优化模型。

开展算法比较实验之前，先选择不同规模的3个测试实例，在其上对包含控制参数的P-PSO、ACO、ALNS及本文算法这4个元启发式算法进行参数调整，使得算法参数设置在这3个实例上达到最佳平均性能。通过测试调参，PSO、ACO、ALNS和本文算法的种群大小分别设为35、50、45和60。之后，采用调整好的参数，所有算法在36个测试实例上进行比较实验。元启发式算法的终止条件均设为对目标函数的估值次数达到100mn1n2，以保证算法比较的公平性。对具有随机性的启发式算法，每种算法在每个测试实例上重复运行30次；鉴于搜救任务的紧迫性，每个算法单次求解问题的CPU运行时间不超过15min。计算实验环境配置为i9-10885 CPU，GeForce 1650Ti GPU，32GB DDR4内存及2TB SSD硬盘。由于目标搜索和发现存在概率估计，对算法求得的每个解(搜救方案)，在对应测试实例上进行500次蒙特卡洛仿真，分别统计发现目标和成功救援目标的时间的中位数。

图6(a)和图6(b)分别给出了第一类场景(目标被发现后保持静止)的测试实例上各个算法得到的目标发现时间和搜救完成(即人工救援队到达目标位置)时间。从结果中可以发现，在前几个搜索区域不大、任务时间不长的较简单测试实例上，各个方法得到的目标发现时间相差不大，有时候人工决策、Greedy和POMDP方法得到的目标发现时间甚至优于其余4个启发式进化算法；但在搜救任务完成时间上，求解本文优化模型的4个启发式算法性能几乎在所有测试实例上的结果都明显优势前3个方法，这主要是因为Greedy和POMDP方法都是以尽早发现目标为求解方向，没有对无人机发现目标后人工搜索队赶往目标位置所需的时间进行有效优化；人工决策方法也难以合理预测和控制这项时间要素。而本文优化模型对该时间要素进行了合理建模，以搜救完成时间最小化为目标函数，能够有效地引导求解方向，从而在结果解中体现良好的人机协同控制。特别的，当搜索区域较大时，由于无人机速度快、设备精度高，其早于人工搜索队发现目标的可能性也很大，因此启发式算法的性能优势也就更为明显。

图6 第1类场景模型的比较实验结果

比较4个启发式算法，它们在前几个较简单测试实例的性能差别并不明显；但随着测试实例规模的增加，算法之间体现出了性能差距。其中P-PSO较简单测试实例上的性能最差，这主要是因为该算法向当前全局最优和个体历史最优学习的策略使其容易过早收敛。在其余大部分测试实例上，ALNS表现的性能较差，这说明在大规模解空间搜索时，ALNS的邻域搜索机制不如其它的进化搜索机制高效。在所有方法中，本文提出的混合进化算法表现出了最优的性能，而且性能优势随着问题规模的增长而更加明显，这验证了本文设计的变异、迁移和增强局部搜索算子的组合能够高效地搜索问题解空间。此外，在后几个大规模问题实例上，启发式算法得到的目标发现时间也优于前3个方法，这也进一步说明了启发式进化算法针对较大解空间的搜索能力是远高于人工决策方法和简单构造式求解策略的。

图7(a)和图7(b)分别给出了第2类场景(目标被发现后向人工搜索队靠拢)的测试实例上各个算法得到的目标发现时间和搜救完成时间。在这类测试实例上，各个算法求得的目标发现时间和前一类差别不大。但由于目标被发现后会主动向人工搜索队靠近，因此各个算法求得的搜索完成时间相比前一类测试实例有明显提前。在7个比较算法中，4个启发式算法的搜索完成时间提前相对于前3个算法更为明显，这验证了本文提出了第2个优化模型能够有效刻画目标向人工搜索队靠近的行为特征。同样，在各个比较算法中，本文所提的启发式进化算法展现了最好的性能，说明该算法的搜索机制针对第2类问题解空间的搜索也很高效。

图7 第2类场景模型的比较实验结果

图8(a)和图8(b)分别给出了第3类场景(目标逃避搜索)的测试实例上各个算法得到的目标发现时间和搜救完成时间。在这类测试实例上，各个算法求得的目标发现时间和搜索完成时间相比第1类都有增加，而且搜索完成时间的增加更为明显。在各个比较算法中，启发式算法的搜索完成时间的增幅小于前3个算法，这验证了本文的第3个优化模型能够有效刻画目标逃避搜索的行为特征。类似的，本文所提的算法的性能在这类测试实例上的表现仍是最好的，验证了算法搜索机制针对第3类问题解空间搜索的效率。

图8 第3类场景模型的比较实验结果

4 结束语

很多应急搜救任务都需要人与智能机器人的协同来提高任务完成效率，但现有的人机协同搜救方法研究还很有限。本文通过对3类典型人机协同搜救场景及其需求的分析，针对目标被发现后的不同行为模式，构建了3个不同的优化模型，并设计启发式进化算法来有效求解这些优化问题。计算实验结果验证了本文所提模型及算法的有效性。

本文模型需要已知搜索区域中的目标存在概率及搜索过程中的目标发现概率。这些概率可基于搜索区域的地形地貌、气候、目标初始位置及行为特征等信息对进行估计，对此已开展了初步研究并取得了一定的效果。在更复杂的实际应用中，目标的行为特征可能具有很多的不确定性。下一步拟开展多学科交叉研究，对灾害被困人员、野外失踪人员、逃犯等典型搜救目标的心理行为和行动特征进行更为深入的分析和更为充分的建模，对其在不同环境下的行为模式进行更为合理和准确的推演，以进一步提高搜救行动的效率和准确性。