1 队伍介绍

队伍名称：酒后写诗

队伍成员：陈权、林望黎、黄章炜

队伍名次：3 / 1646

2 问题简介

这个问题说起来其实挺简单（但实现起来困难重重），就是提供了气象局得到的10个模型的预测数据（准确率为90%~95%之间），然后让我们用这些预测数据去预测每个坐标在每个时刻的天气状况，并以该天气状况为依据，给无人机规划飞行路径。若无人机所处位置的即时风速大于等于15或者降雨量大于等于4，则认为无人机坠毁。

天池官方原文介绍在这里。

英文报告在这里。

顺便推广一下我正在建设当中的个人博客网站，此篇的原文地址~

解决方案的源代码地址

3 解决方案

这个问题主要可以概括为两个方面——预测和路径规划。

3.1 预测

预测方面可以有两种做法——分类和回归。那么用哪种呢？

分类的话对之后的路径规划会造成两点麻烦：

• 无法得到安全系数。比如风速是14.9的和风速是8.0的情况都会被认为是安全区域，每个坐标在每个时刻的安全系数无法确定。这会导致无人机在有安全系数很高的路径可以选择的情况下，选择了危险系数高的路径。

• 样本不均匀。训练集中某几天的绝大多数区域都是风速大于15的，这会导致负样本远远大于正样本，造成样本量不均匀的问题。

相对而言，回归可以较好地解决这两个问题。

因此，我们选择了回归作为预测的方案。

3.2 路径规划

这是一个发挥想象力的地方，没有固定的章法。我们查找过相关的文献，无果。询问过可能知道这方面知识的人，无果。所以，我们干脆就靠自己想来实现这个算法了~

这里路径规划的难点在于这是一幅随时间变化而变化的动态地图，动态地图很难处理，有的可能说在z方向加一个维度来实现，做一幅三维的立体图，在三维的方向上这个图就是静态的了。也有的说可以用强化学习，这方便我们不太了解，但是个人觉得会非常耗时，耗资源，效率也不一定高，能用固定算法就用固定算法吧~

不同于以上两者，我们选择了一个更为简单的方案，直接在二维图上构造局部静态图，并在每次移动到指定位置后更新地图，以此来应变地图的动态变化。以静制动~相对于三维图来说，直接在二维图上找路径更便于可视化，相对于强化学习来说，我们的方法更为直观、快捷。后文中将细说。

不管是什么方法，能找到路径的就是好方法~

3.3 难点

预测难吗？不难，说实话，直接用求平均的方法都能找到许多路径。

找路径难吗？不算难，只要前期稍微花些功夫，我相信这对绝大多数的队伍来说都不是难题。

那么，这个问题难在哪里？难在预测和路径规划相结合！这么说吧，在这个问题这里，预测的准确率高不一定是好事（当然预测的准确率低一定是坏事）。如果一个实际值为15.1的即时风速，一种方案预测成了14.9，另一种方案预测成了16.0。哪种好？16.0的好。我们希望采取宁大勿小的原则。宁可错杀一千，不能放过一个！一条路径上，只要有一个点超出阈值了，无人机就直接坠毁了。花费时间相同的路径多的是，这种接近阈值的地方，我们宁可当成危险区域。

当然，错杀的也不能太多，不然路径就找都找不到了~

因此，我们认为题目中的“优化”二字，更多的是指安全系数的优化，其次才是消耗时间的优化。

我们用了stacking时取max的方法来解决这个问题，关于这点会在下面再详细地说。

4 预测模型

预测，最终要的就是特征要好。有句话说，“特征找不好，调参调到老”，我认为后面还应该加一句“调到老也调不好”。

本题所给的原始数据已经是比较好的特征了，直接拿来用Lightgbm或者Xgboost来训练一下做预测就可以得到一个比较好的结果了。像复赛时间那么紧张，我们是先拿原始数据特征来训练模型，得到一幅初步的地图的。

然后，由于风速和降雨量即是空间上的矢量，有是时间上的矢量，我们便把周围的天气情况和前后时间的天气情况都利用了起来。

最后，我们认为不同的模型可能在不同时间段的准确率是不一样的，于是就把时间作为哑变量加到了特征当中。

总之，我们用到的特征有：

• 原始数据特征
• 周围天气特征（上下左右）
• 前后时间天气特征（前一个小时和后一个小时）
• 时间特征（离散特征）

由于数据量比较大，把这些特征都加进去，我们自己的这种低配笔记本基本是跑不动了。没关系，sampling就可以了，经实验，准确率并不会下降多少。

在训练之前，我们还用类似箱线图的方法，将异常值做了替换。

在训练模型的方法上，我们又分为了全部数据训练和交叉融合训练。

所谓全部数据训练就是把5天的数据揉在一起，做shuffle，然后分70%的训练集和30%的验证集训练。

所谓交叉融合训练，有点像交叉验证，但又不是交叉验证，我给幅图大家就明白了。

图1 交叉融合模型训练图

这5个模型的参数是可以不一样的，训练出5个模型之后，再做了stacking，这里我们遵循宁大勿小的原则，取了所有结果中的最大值。

用全部数据训练的地图噪点会比较多，而用交叉融合的地图会相对干净一些。原因是我们利用的是树模型，前者树的叶子多，后者树的叶子少。实践证明，后者更符合我们的需求。

在复赛中我们训练了如下几种模型

表1 模型训练结果表

其中，temporal features为前一个小时和后一个小时的天气特征。

总而言之，就是要训练出多幅地图，然后再不同地图上找安全路径，如果有某条路径在各种地图上都是安全的，那么这条路径能通过的概率就很高了。

在用来训练的算法上，在此题中我们认为Lightgbm要优于Xgboost。Lightgbm采用了直方图的计算方式，虽然准确度上没有Xgboost高，但速度真的快，比Xgboost至少快出5倍以上。而且本题并不是比谁预测的准，相反我们希望预测值比真实值稍微大一些，因此，Lightgbm是最佳选择。

5 路径规划模型

根据预测模型，我们可以得到一个 (548, 421, 18) 的地图，这样的地图比较难处理。我们把它转化一下。

给定了一个起始点和出发时间，由于无人机只能向上下左右四个方向移动，我们可以根据所得到的 (548, 421, 18) 的地图利用bfs画出一幅 (548, 421)的地图。

图2 安全系数示例图1

图中，颜色代表了到达从绿点出发，用最短的时间到达某点时的安全系数，蓝色为危险区，红色为安全区，颜色越深越安全。这幅图严格保证了无人机从绿点出发，走到图上红色区域任意一个位置的时间间隔为 2 * (abs(x - start_x) + abs(y - start_y))，也就是我们平常所说的曼哈顿距离的两倍。

这样一来，任意指定一个目标点，我们就可以构造一幅从起始点到目标点的有向有权图，每两点之间的权值即是安全系数值（由风速和降雨量决定），这样一幅局部的静态图就可以用Dijkstra算法秒算最安全的路径，对真的是秒算。在计算的过程中，可以适当的降低阈值，使得路径不经过一些较危险的点。

如果我们所希望到达的目标点不在红色区域内，那么我们就要往周围绕一下，即找一个引导点，再把引导点当成起始点继续搜索。引导点一般在起始点和目标点所组成的黄色区域之外，在黄色区域内找了也白找，这个大家可以体会一下。

我们设计了一个专门用来寻找引导点的程序，一个设置一些参数之后可以自动找，是一个dfs内嵌套了bfs的程序。另一个是利用django设计的一个网页，可手动点击地图查找。

比如图2中的蓝点是在蓝色区域的，无法直接到达，那么我们就找了一个引导点。得到了下图3所示的地图。

图3 安全系数示例图2

深绿点即为引导点，从图中可见，绿点经过一个引导点的引导即可到达蓝点。
接下来把两段路径组合起来即可。

我们的算法不仅可以正向寻找路径，还可以逆向寻找路径，原理类似，不再赘述。

寻找引导点是本算法最为繁琐的步骤，可以限定时间，以路径中的最大安全系数最小作为优化目标进行优化寻找。后期仍有许多可以改进的地方。

我们有一个更为大胆的想法，就是使得路径由胖瘦之分，寻找最胖的一条，并以中心线为最终路径。这个以后有时间再来实践一下，相信是件非常有趣的事情。

总之，我们在寻找路径时，我们在保证路径安全系数较高的情况下，再去优化消耗时间的问题。这些都可以通过我们模型中的各个超参数做调整。

6 其它的比赛经验

相信参加了复赛的选手都有体会，复赛中最难的地方就在于如何设计提交路径的策略。如果一下子交一大堆路径上去，其中有个几条没过，线下的可能性组合是多的可怕的~也就是说胡乱提交的话，根本不知道哪条路径过了，哪条路径没过。

我们队在赛前的确考虑过这一点，但在比赛中发现形势比想象的严峻的多。即使提交的每条路径时间长短都不一样，仍旧会有多种组合。于是，我们就写了一个输入为线上得分，输出为线下可能的路径组合的小程序，在线下模拟几条可能坠毁的线路坠毁的情况，尽可能保证各种情况下都能区分出坠毁的路径。

那么如何修改耗时？我们的超参数中有一个是可以设置停留时间的。假设达到目的地时为12:30，由于天气情况在一个小时内时不会发生变化的，于是我们就可以将倒数第2个点停留0~28分钟。

当然，也有失手的时候，有些提交的确是没法区分。这个时候，我们可以在下一次提交时，保留这次绝大多数的路径，然后将两次提交结果做对比（甚至是三次结果做对比），这样也是可以推导出坠毁的路径的。

总之，这是一次非常规套路的算法比赛，这让我们这些只有低配硬件的算法爱好者也有一展身手的机会，希望天池多办些可以发挥创造力的比赛~

如果有任何问题，可以联系我~