野外搜救在时间上具有紧迫性。24小时内未获救的人员（特别是儿童），生存的几率由于失水、受伤、暴露于不利环境等可能而迅速降低。搜救的时间越长，搜救的区域就越得扩大，从而使得搜救成功变得越来越困难。

在野外搜救中，使用多无人机与使用人力或救援犬相比，具有成本较低、速度较快、对地形适应性较好等优点。

然而即使使用多无人机，仍存在搜救失败的可能[1]。与城市环境下搜救被困人员相比，野外搜救需要面对被搜救人员可移动、被搜救人员难以被跟踪、被观测等特殊的挑战。

出于上述原因，采用多无人机的野外搜救，所关注的主要问题一般不是如何最大化搜索范围，而是如何根据被搜救人员的可能位置进行搜索。这一任务可以细分成为以下两项子任务：

• 如何预测被搜救人员的位置；
• 如何根据预测的被搜救人员的位置，规划多无人机的搜索。

预测被搜救人员的野外位置

等概率曲线（Iso-Probability Curves）及相关的方法[2]，是近年来在野外搜救中采用较多的一类预测被搜救人员位置的方法。该方法的基本思路是：

• 以被搜救人员在野外的最后已知位置（例如停车位置、帐篷位置、被目击者看到的位置等）为中心，计算出自中心向外每个方向上（方向数量可以是8个、16个或者更多）被搜救人员移动距离的概率分布，其中，被搜救人员移动距离的概率分布根据时间推移、地形坡度、地形障碍、历史搜救数据中被搜救人员移动速度的统计分布、总结出的被搜救人员移动速度与地形坡度之间的关系、以及其它信息计算得出；
• 将向外辐射的各个方向上相同概率的点连接起来，形成等概率曲线；自中心向外，可以形成一系列大小不同的等概率曲线（形状类似于地理中的等高线）；
• 通过一系列的等概率曲线，可以得到在某一时间、任意方向上被搜救人员移动距离的估计的概率分布；
• 随着时间的推移，被搜救人员有可能继续移动，因此需要生成新的一系列等概率曲线。

另一类较新的预测方法[1][3]结合了上述等概率曲线方法中的部分思路，同时采用了Agent-Based概率模型。该类方法根据野外地形，模仿被搜救人员（也就是Agent）在野外的行动（例如向高处走、朝着一个方向走等行动），通过蒙特卡罗模拟，生成被搜救人员可能位置的时空分布。接下来就围绕近期发布的一篇论文[1]，介绍一下基于Agent-Based概率模型的预测方法。该论文在下文中简称“论文”。

基于Agent-Based概率模型的预测方法

在论文中，被搜救人员（也就是Agent）在野外的行动被定义为有以下几种：

1. 朝着任意方向随机活动；被搜救人员有可能迷失了方向，或者焦急紧张；
2. 朝着一个方向走；很多人走失后往往采用这种策略；
3. 沿着路径、山脊、河边等线形地形走；
4. 停留；走失人员可能会停下来休息，或者停下来制作标志，用以增加被发现的可能；
5. 向高处走；走失人员可能希望更好地观看地形；
6. 寻找原路返回。

在接下来的蒙特卡罗模拟中，被搜救人员在每个时间间隔，按照模拟中设置的概率，选择并从事上述六种行动中的一种行动。对于不同的被搜救人员，模拟中设置的行动概率可能会不同。

蒙特卡罗模拟中其它的一些设置和假设包括：

• 假设野外地形数据已知；论文的作者们为了进行数值实验（见本文末尾描述），使用了MATLAB的Automatic Terrain Generation包，并生成了数值实验用的三维地形数据和地形图；
• 被搜救人员在任意时刻的行进速度根据地形的坡度而调整；
• 同时进行1080个模拟，用以生成被搜救人员位置的时空分布；每个模拟在开始时，被赋予一个随机的“朝着一个方向走”的方向（以被搜救人员的最后已知位置为起点、向外辐射的方向）；
• 遇到坡度太陡、河流湖泊等难以穿越的地形时，被搜救人员选择一个最接近于当前方向、并且可以继续前行的方向；如果此时所有方向都无法继续前行，则选择沿着障碍的边缘行进。

下图是蒙特卡罗模拟产生的、被搜救人员在两个不同时间的可能位置分布。图中，绿色的点代表模拟产生的被搜救人员的可能位置，红色的点代表被搜救人员的最后已知位置（Last Known Position，简称LKP）。

当蒙特卡罗模拟产生了被搜救人员的可能位置之后，使用核密度估计（Kernel Density Estimation，简称KDE）可以生成被搜救人员位置的时空分布函数f(x,y,t)，其中，(x,y)表示地理位置。

与前述的等概率曲线（Iso-Probability Curves）方法相比，Agent-Based方法可以模拟出更贴近于实际的被搜救人员的行动轨迹和可能位置。例如在Agent-Based方法的模拟中，由于存在被搜救人员“向高处走”的行为，模拟中高出周围地势的地方成为了吸引被搜救人员的地方。

当地形较复杂时，Agent-Based方法具有更明显的优势。例如在下图所表示的模拟中，蓝色箭头的方向标出了一个坡度很陡的方向；以黄颜色标出的等概率曲线没有沿着蓝色箭头的方向进行扩展，意味着根据等概率曲线的方法，被搜救人员不会向蓝色箭头的方向行动；在以橘红色箭头和绿色的点标出的Agent-Based方法的预测中，可以看出被搜救人员具有向蓝色箭头方向绕行的可能。

多无人机野外搜索策略

预测了被搜救人员的可能位置之后，多无人机的协同搜索如何进行呢？

多无人机的协同搜索问题可以转化成为带约束的数学规划问题。接下来介绍一下论文中的有关思路。

数学规划问题的目标

根据Agent-Based概率模型产生的被搜救人员位置的时空分布函数f(x,y,t)，数学规划问题的目标是规划一系列的路径点wp₁^t、wp₂^t、.... ，使得无人机在经过wp₁^t、wp₂^t、.... 的路径中，发现被搜救人员的累积概率为最大。

值得一提的是，为了防止无人机只在一个发现目标概率高的地方飞行，论文中使用了Receding Horizon规划策略（一种根据不断变化的环境、不断重新规划的规划策略），通过不断设置新的前瞻点（Lookahead Point）来引导规划算法持续规划出新的路径。下图是论文中Receding Horizon规划策略的示意图，其中，虚线圆圈标出了对应于不同时间的前瞻点。

数学规划问题的约束条件

论文中提到的数学规划问题的约束条件包括以下几个。

对无人机之间距离的约束

控制多无人机可以采用地面集中控制，也可以采用分布式控制。地面集中控制意味着地面控制中心的作用非常关键。相比之下，分布式控制由于在容错、可扩展性等方面的优点，而得到了越来越多的重视。论文中采用的就是分布式控制。

多无人机集群依靠机载的通讯设备来保持通讯。由于机载通讯设备的最远通讯距离有限，而在野外搜救中，无人机搜索的地域可能很广，因此在论文中，仅要求每个无人机与距离最近的其它无人机保持通讯，这样就使得无人机不必局限在集群附近的一个较小的区域内，飞行具有更大的灵活性。

同时，任何两个无人机之间的距离也不能太近，以防止碰撞。汇总以上的要求，对于无人机i及其最近邻无人机j之间距离的约束可以是针对以下公式的约束：

其中，d_ij表示无人机i与其最近邻无人机j之间的距离，d_min表示两个无人机之间允许的最近距离，d_max表示两个无人机之间的最远通讯距离，其它符号均表示可调参数。对通讯范围内各无人机的上述公式求和、然后最小化，就可以作为一个软约束，来约束多无人机内部之间距离。

对无人机转弯角度的约束

为了保障无人机的平稳飞行，无人机的转弯角度需要约束在一定范围之内。如果无人机的当前位置用（x_i,y_i）来表示，那么这一约束就可以用以下的不等式来表示：

无人机之间的信息交换

搜救开始时，每个无人机都存有Agent-Based概率模型预测的、被搜救人员在各个时间的可能位置。在搜救过程中，每个无人机记录下各自查看过的被搜救人员的可能位置。当两个无人机处于通讯距离之内时，两个无人机将各自查看过的被搜救人员的可能位置进行交换。已经被一个无人机查看过的被搜救人员的可能位置就不再被其它无人机规划、并前往查看了。

动态分区

当多个无人机处于通讯距离之内时，可以根据各自的位置，动态地划分出各自负责的区域。随着各个无人机位置的变化，划分出的区域随着进行调整。例如下面的两张示意图都标有四个无人机的分区（其中，U₁到U₄代表无人机）；图（b）表示的是图（a）中的分区在20分钟后调整成的新的分区。

在以上的两张图中，U₁的分区是由两个边界所界定的：

• U₁与U₄的边界（图中以橘红色“1-4”标出）；
• U₁与U₂的边界（图中以橘红色“2-1”标出）。

这些分区是怎样划分出来的呢？对于无人机U_i来说，假设其位置为p_i，并且有N_Ui个无人机处于其通讯距离之内，那么U_i所负责的区域就是所有距离U_i更近的地点的集合，也就是以下公式中的Q：

这样分区，使得两个分区之间的边界不仅与连接两个无人机位置的连线相垂直、而且将连接两个无人机位置的连线二等分。

数学规划问题的求解

论文中提到了使用开源的数值优化软件CasADi[4]来求解数学规划问题。CasADi软件用于过程控制、机器人、航空航天等领域。该软件采用C++编写，可以通过Python、MATLAB、以及C++调用。

数值实验结果

为了验证论文中的Agent-Based概率模型、以及多无人机的野外搜索策略，论文的作者们进行了野外搜救的数值实验。实验中假设被搜救人员为1人；搜救时间限定为两小时；如果在限定的时间内未能找到被搜救人员，则认为搜救失败。

数值实验的结果表明，相对于等概率曲线（Iso-Probability Curves）方法等基准方法而言，采用论文中的Agent-Based概率模型和多无人机搜索策略，搜救的成功率更高，搜救的时长更短；当野外地形变得复杂时，上述的优势变得尤为明显。

参考文献

[1] Multi-UAV Search and Rescue in Wilderness Using Smart Agent-Based Probability Models.

https://arxiv.org/abs/2411.10148

论文许可协议：CC BY.

https://creativecommons.org/licenses/by/4.0/

[2] Target-Motion Prediction for Robotic Search and Rescue in Wilderness Environments.

http://cimlab.mie.utoronto.ca/wp-content/uploads/2016/11/Macwan-2011-Target-motion-prediction-for-robotic-search-and-rescue-in-wilderness-environments.pdf

[3] An agent‑based model reveals lost person behavior based on data from wilderness search and rescue.

https://www.nature.com/articles/s41598-022-09502-4

[4] CasADi – A Software Framework for Nonlinear Optimization and Optimal Control.

https://optimization-online.org/wp-content/uploads/2018/01/6420.pdf

封面图：Karl Greif、Unsplash