数学建模

摘要
The utilization of the 搜查机 would reach maximization if we can establish a rational 搜查方案。我们的思路是将这个问题分为四个步骤，1、建立飞机坠毁地点的概率模型。2、建立搜索模型。3、用计算机模拟规划路线进行飞行器搜素。4.将飞行器搜索的反馈结果作为依据，更新我们的概率模型

对于第一步骤，失联之后的飞机成随机行走。分为三个状态，包括巡航飞行，坠毁中，和海平面漂移阶段。随着时间成柏松分布的概率发生爆炸/坠毁事件,我们用蒙特卡洛法进行计算机模拟了108个粒子的运动，模拟出了飞机坠毁的概率云。
对于第二步骤，建立搜索模型，我们想到了势场法、单元法进行建模。由于时间限制的关系，我们只对单元法进行了建模、求解。运用了一种泡泡分割空间的算法和蚁群算法法建立了搜索模型。
对于第三步骤，需要有待实际飞行
对于第四步骤，我们使用残骸的可能历史作为依据，将可能的飞行器解体爆炸位置找出，并且对这些概率点进行更精细模拟来获得更新的概率分布，重新规划路线，重复二到四步。

如此，我们获得了一套完整的工具链用于海上失事飞机的搜寻。

失恋后飞行器的概率估计

我们认为失联之后的飞机成随机行走。分为三个状态，包括巡航飞行，坠毁中，和海平面漂移阶段。

飞机失联后可以认为在巡航高度开始随机行走，随着时间成柏松分布的概率发生爆炸/坠毁事件，爆炸时分为加速和恒定速度两个阶段，坠毁时我们认为飞机的每个碎片无论大小都有相同的空气动力学属性，坠毁到海面后随洋流漂移。

我们假设飞机在t时刻，在时空中(x,y,z,t)点出现的概率为$$\psi (x,y,z,t)$$,在t时刻有归一化

$$!\int \psi(x,y,z,t)dx dy dz = 1$$

我们的第一步目标是，使用合适的形式来表示该概率分布，我们注意到无伦爆炸前后在我们的假设中飞行器的每一个碎片具有相同的物理属性，也就是说在我们的假设中对于任意飞机上的残骸中的某一点出现在某些地方的概率表示都有相同的数学形式。联系到现在量子力学的原子轨道实际上是一个概率云，即电子存在波函数$$\psi(\vec r,t)$$不为0的任何一点，但是仅仅当我们探测他的时候我们可以得到粒子的位置，同样的，我们可以反过来用粒子的出现来代替本问题中飞行器的位置。

于是我们可以用粒子的集合来代表飞行器的出现位置概率分布，设粒子出现的概率为$$\phi $$，在经过相同的物理变化的情况下，我们可以认为 $$\phi = \psi (x,y,z,t)$$，也就是，用粒子出现在某点的概率来表示飞行器出现在该点的概率。

模拟过程中我才用了Julia作为编程语言，使用蒙特卡洛方法，模拟了$$10^8$$个概率粒子的运动

模拟的算法

• 生成一堆粒子，产生于飞行器失联点，位置，速度，高度，航向与原飞行器保持一致
• 对粒子进行跌代，迭代过程中粒子包括三个状态：飞行，坠落，漂流。
  1. 如果粒子处于飞行状态，以一定的概率发生转向，另外以一定的概率爆炸坠落。
     2.如果粒子处于坠落状态，受到力运动，加速方程由下面的受力分析给出，直到落到洋面转化为漂流状态
     3.如果粒子处于漂流状态，则随洋面漂移，漂移的速度这里我们简化为匀速，如果有足够的时间可以引入来自 http://www.ccpo.odu.edu/POMWEB/userinfo.htm的数据

-迭代一定时间后可以获得粒子基本上都坠落入海洋

程序实现，使用Julia语言，利用并行for实现高效率运算，我们为之制作了一个前端，使用html5+javascript+webgl的模式，前台后台的代码使用websocket通信，下面的演示图皆基于此

下坠的受力分析

搜寻算法

适用于我们问题的流行的路径规划模型包括使用物理学原理基于势场的算法基于空间分割的单元法，在这里我们分别使用两种方法进行计算给出结果。
我们涉及到的问题是，已知概率分布，如何让不同性能的飞行器，对应了不同的探测距离和航程以及起降机场。覆盖尽可能多的粒子数。

（见附图）

势场法

对于我们的问题来说，势场法的优点和缺点都是显然的，一方面来说我们可以将粒子作为一个个势场的源头，通过空间插值和平滑的方法来构建出空间中的势场分布，然后使用基于变分的方法来规划路径，获得路径上最大的探测效率，缺点是在多探测飞机规划的时候我们需要一些trick，使得每架飞行器的轨迹不重复，比如引入飞行器飞过后的负势能，显然这对计算量的要求极高。

算法设计和泛函求解的算法

在设计势场法时，我们定义每个粒子对空间的在自己的坐标上势能增加一个定值c1，然后，将空间平滑化，于是我们的问题转化为求数条曲线，每个曲线会对空间中势能造成一个升高（距离曲线b的范围内升高c2，b的取值为传感器的探测距离）。

在这里，求解路径的算法我们可以选择极其暴力的随机行走或者连续化的蚁群算法，就不展开讨论了。

算法实现

单元法

单元法的主旨是将空间剖分为网格，通过粒子的分布来设计一条路径，使得我们的探测器在尽可能短的航程内路过尽可能的粒子，其问题也是显而易见的，对于空间的粗糙剖分很容易引发大量的问题，但是，我们注意到一个有趣的现象是我们的概率分布以粒子给出，这样，我们可以先明确第一个问题，测用最少的给定半径的测量圆（对应于飞行器的探测距离）覆盖所有粒子。

这样，空间转化为一个带权值的无向图（图：粒子的空间结构），我们的任务是在给定的总路程情况下寻找一条路径使得路过的所有权值点之和最大，同时需要注意的是，如果一架探测飞机路过了空间结构图中的某点，那么对于其他飞行器来说，这个路径点的权值点应该消失。

明确了我们需要优化的问题之后，我们可以设计出一种改进型蚁群算法

单元法实现：空间分割

空间的泡泡分割－－一种奇怪的聚类算法
假想有一堆泡泡，他们已经达到了爆破的临界体积，那么当两个泡泡非常接近的时候可能发生爆炸－－爆炸的结果是剩下相同体积的一个泡泡。另一个结果是因为互相距离远的时候而互相推移

我们将待搜索的粒子点集合每个作为一个泡泡的圆心，构建出一群泡泡，然后让其发生迭代，每次规则如下

两个泡泡的距离小于泡泡极限半径的时候，以概率$$1-\frac{r}{R}^2$$的概率发生爆炸,如果不爆炸，则被互相推移距离的1/10。
当一个原始点不被任何一个泡泡所覆盖的时候，则在该点形成一个新的泡泡。

这样，我们的泡泡就会以尽量少的数量均匀的覆盖空间我们的粒子，且每个粒子都会被覆盖住。

用泡泡对空间形成分割之后，我们可以将空间转化为一张无向有权图，每个点有自己的权值，我们的目标是在给定的距离内路过尽可能多的点。

蚁群算法

我们设定，代表某种探测飞机$$P_k$$的蚂蚁分为ab两种，他们都从机场出发，前往被剖分所代表的图的分为一点，再每次迭代过程中，我们的蚂蚁都会将一部分信息素遗留给环境，直到他们走完相当于探测飞机航程一半的路程时他们就会死掉，又或者蚂蚁$$P_ka$$遇到了蚂蚁$$P_kb$$的信息素，那么他会不丢失信息素的存活下去。设蚂蚁初始携带的信息素为$$Info_full$$

蚂蚁每次选择路径遵循以下原则：优先选择已有同飞行器下另一半信息素的节点；其次是以一定概率，绕过包含自己信息素和其他飞行器信息素的节点，同时也以一定概率开拓新的疆土。知道回答原点或者死亡。
对于第k架飞机的a型蚂蚁，从i点到j点未归一化的选择概率由下面的公式给出
其中value 和区域粒子数呈线性关系,$$max(Info_{other})$$为除该蚂蚁外最大的某飞行器携带的蚂蚁信息素（包含a/b）。
$$!P^{ka}_{i,j}= (Info_{full}-Info^b) \cdot 100; if (Info^b>0)$$
$$!P^{ka}_{i,j}= value (2 \cdot Info_{full}-(Info_b+max(Info_{other}))) ;if (Info^b=0)$$

$$!P^{kb}_{i,j}= (Info_{full}-Info^b) \cdot 100; if (Info^a>0)$$
$$!P^{kb}_{i,j}= value (2 \cdot Info_{full}-(Info_b+max(Info_{other}))) ;if (Info^a=0)$$

我们可以用俄罗斯赌盘来实现这个概率分布。

这样，每种飞行器下所属的ab两种蚂蚁会在图上的某点相遇，并最终收敛成一条完整的路径。我们使用含有$$Pk$$信息素的子图，并且抽取收敛的回路，即可以得到飞行器最后的路径规划

这部分代码实现了一部分，但是由于时间限制＝＝

另一个问题，如何根据一片残骸找到更多的残骸

我们认为，在前面一直研究的粒子分布代表的概率图$$\phi(\vec r,t)$$中，跌落在每个区域的粒子不仅仅代表了，一个飞行器出现在该地的概率，同时也代表了飞行器的某一种历史。

前面我们已经研究了如果求得粒子表示的飞行器残骸分布，研究了如何设计一个路线去搜寻给定的概率分布，那么下面我们面临的问题是，当我们找到第一片残骸之后，确认飞机已经殉难，我们该怎么找到更多的残骸

如图，我们的探测飞行器在地面上的一点发现了残骸，而残骸附近有我们的算法估算出来的三个代表概率的粒子

我们可以通过粒子的历史轨迹，来看该粒子代表的飞行器概率是在哪一个时刻发生爆炸下坠的，如图绿线圈出的部分，那么我们重新要做的就是在绿线圈出的部分添加新的粒子，使得该部分的概率增加，重新模拟在分裂点之后的概率分布，这里我们可以看到由青色的线引出，紫色的区域获得新的概率，这样，我们可以获得一个新的概率分布图来表示粒子的着重出现。

每次发现新的飞行器残骸，我们可以迭代此过程，逐步求精，获得最后的解。

如图，是发现了一个飞行器残骸后追溯回去的概率分布

这样，我们的模型可以根据每次搜查的结果，更新自身，获得更精确的概率分布

总结

我们的算法包括了一下几步，构成了一套完整的搜查工具链使用蒙特卡洛来获得粒子统计表示的空间概率分布，同时进行实时的三维显示，其次，使用协同路径规划算法为探测飞机设计飞行路线的规划，再有，通过找到的碎片来更新空间概率分布，重新进行路径规划，进而完整的形成一套海上失事飞机的搜救工具链。