1 隊伍介紹

隊伍名稱：酒后寫詩

隊伍成員：陳權、林望黎、黃章煒

隊伍名次：3 / 1646

2 問題簡介

這個問題說起來其實挺簡單（但實現(xiàn)起來困難重重），就是提供了氣象局得到的10個模型的預測數(shù)據(jù)（準確率為90%~95%之間），然后讓我們用這些預測數(shù)據(jù)去預測每個坐標在每個時刻的天氣狀況，并以該天氣狀況為依據(jù)，給無人機規(guī)劃飛行路徑。若無人機所處位置的即時風速大于等于15或者降雨量大于等于4，則認為無人機墜毀。

天池官方原文介紹在這里。

英文報告在這里。

順便推廣一下我正在建設當中的個人博客網(wǎng)站，此篇的原文地址~

解決方案的源代碼地址

3 解決方案

這個問題主要可以概括為兩個方面——預測和路徑規(guī)劃。

3.1 預測

預測方面可以有兩種做法——分類和回歸。那么用哪種呢？

分類的話對之后的路徑規(guī)劃會造成兩點麻煩：

• 無法得到安全系數(shù)。比如風速是14.9的和風速是8.0的情況都會被認為是安全區(qū)域，每個坐標在每個時刻的安全系數(shù)無法確定。這會導致無人機在有安全系數(shù)很高的路徑可以選擇的情況下，選擇了危險系數(shù)高的路徑。

• 樣本不均勻。訓練集中某幾天的絕大多數(shù)區(qū)域都是風速大于15的，這會導致負樣本遠遠大于正樣本，造成樣本量不均勻的問題。

相對而言，回歸可以較好地解決這兩個問題。

因此，我們選擇了回歸作為預測的方案。

3.2 路徑規(guī)劃

這是一個發(fā)揮想象力的地方，沒有固定的章法。我們查找過相關的文獻，無果。詢問過可能知道這方面知識的人，無果。所以，我們干脆就靠自己想來實現(xiàn)這個算法了~

這里路徑規(guī)劃的難點在于這是一幅隨時間變化而變化的動態(tài)地圖，動態(tài)地圖很難處理，有的可能說在z方向加一個維度來實現(xiàn)，做一幅三維的立體圖，在三維的方向上這個圖就是靜態(tài)的了。也有的說可以用強化學習，這方便我們不太了解，但是個人覺得會非常耗時，耗資源，效率也不一定高，能用固定算法就用固定算法吧~

不同于以上兩者，我們選擇了一個更為簡單的方案，直接在二維圖上構(gòu)造局部靜態(tài)圖，并在每次移動到指定位置后更新地圖，以此來應變地圖的動態(tài)變化。以靜制動~相對于三維圖來說，直接在二維圖上找路徑更便于可視化，相對于強化學習來說，我們的方法更為直觀、快捷。后文中將細說。

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

3.3 難點

預測難嗎？不難，說實話，直接用求平均的方法都能找到許多路徑。

找路徑難嗎？不算難，只要前期稍微花些功夫，我相信這對絕大多數(shù)的隊伍來說都不是難題。

那么，這個問題難在哪里？難在預測和路徑規(guī)劃相結(jié)合！這么說吧，在這個問題這里，預測的準確率高不一定是好事（當然預測的準確率低一定是壞事）。如果一個實際值為15.1的即時風速，一種方案預測成了14.9，另一種方案預測成了16.0。哪種好？16.0的好。我們希望采取寧大勿小的原則。寧可錯殺一千，不能放過一個！一條路徑上，只要有一個點超出閾值了，無人機就直接墜毀了。花費時間相同的路徑多的是，這種接近閾值的地方，我們寧可當成危險區(qū)域。

當然，錯殺的也不能太多，不然路徑就找都找不到了~

因此，我們認為題目中的“優(yōu)化”二字，更多的是指安全系數(shù)的優(yōu)化，其次才是消耗時間的優(yōu)化。

我們用了stacking時取max的方法來解決這個問題，關于這點會在下面再詳細地說。

4 預測模型

預測，最終要的就是特征要好。有句話說，“特征找不好，調(diào)參調(diào)到老”，我認為后面還應該加一句“調(diào)到老也調(diào)不好”。

本題所給的原始數(shù)據(jù)已經(jīng)是比較好的特征了，直接拿來用Lightgbm或者Xgboost來訓練一下做預測就可以得到一個比較好的結(jié)果了。像復賽時間那么緊張，我們是先拿原始數(shù)據(jù)特征來訓練模型，得到一幅初步的地圖的。

然后，由于風速和降雨量即是空間上的矢量，有是時間上的矢量，我們便把周圍的天氣情況和前后時間的天氣情況都利用了起來。

最后，我們認為不同的模型可能在不同時間段的準確率是不一樣的，于是就把時間作為啞變量加到了特征當中。

總之，我們用到的特征有：

• 原始數(shù)據(jù)特征
• 周圍天氣特征（上下左右）
• 前后時間天氣特征（前一個小時和后一個小時）
• 時間特征（離散特征）

由于數(shù)據(jù)量比較大，把這些特征都加進去，我們自己的這種低配筆記本基本是跑不動了。沒關系，sampling就可以了，經(jīng)實驗，準確率并不會下降多少。

在訓練之前，我們還用類似箱線圖的方法，將異常值做了替換。

在訓練模型的方法上，我們又分為了全部數(shù)據(jù)訓練和交叉融合訓練。

所謂全部數(shù)據(jù)訓練就是把5天的數(shù)據(jù)揉在一起，做shuffle，然后分70%的訓練集和30%的驗證集訓練。

所謂交叉融合訓練，有點像交叉驗證，但又不是交叉驗證，我給幅圖大家就明白了。

圖1 交叉融合模型訓練圖

這5個模型的參數(shù)是可以不一樣的，訓練出5個模型之后，再做了stacking，這里我們遵循寧大勿小的原則，取了所有結(jié)果中的最大值。

用全部數(shù)據(jù)訓練的地圖噪點會比較多，而用交叉融合的地圖會相對干凈一些。原因是我們利用的是樹模型，前者樹的葉子多，后者樹的葉子少。實踐證明，后者更符合我們的需求。

在復賽中我們訓練了如下幾種模型

表1 模型訓練結(jié)果表

其中，temporal features為前一個小時和后一個小時的天氣特征。

總而言之，就是要訓練出多幅地圖，然后再不同地圖上找安全路徑，如果有某條路徑在各種地圖上都是安全的，那么這條路徑能通過的概率就很高了。

在用來訓練的算法上，在此題中我們認為Lightgbm要優(yōu)于Xgboost。Lightgbm采用了直方圖的計算方式，雖然準確度上沒有Xgboost高，但速度真的快，比Xgboost至少快出5倍以上。而且本題并不是比誰預測的準，相反我們希望預測值比真實值稍微大一些，因此，Lightgbm是最佳選擇。

5 路徑規(guī)劃模型

根據(jù)預測模型，我們可以得到一個 (548, 421, 18) 的地圖，這樣的地圖比較難處理。我們把它轉(zhuǎn)化一下。

給定了一個起始點和出發(fā)時間，由于無人機只能向上下左右四個方向移動，我們可以根據(jù)所得到的 (548, 421, 18) 的地圖利用bfs畫出一幅 (548, 421)的地圖。

圖2 安全系數(shù)示例圖1

圖中，顏色代表了到達從綠點出發(fā)，用最短的時間到達某點時的安全系數(shù)，藍色為危險區(qū)，紅色為安全區(qū)，顏色越深越安全。這幅圖嚴格保證了無人機從綠點出發(fā)，走到圖上紅色區(qū)域任意一個位置的時間間隔為 2 * (abs(x - start_x) + abs(y - start_y))，也就是我們平常所說的曼哈頓距離的兩倍。

這樣一來，任意指定一個目標點，我們就可以構(gòu)造一幅從起始點到目標點的有向有權圖，每兩點之間的權值即是安全系數(shù)值（由風速和降雨量決定），這樣一幅局部的靜態(tài)圖就可以用Dijkstra算法秒算最安全的路徑，對真的是秒算。在計算的過程中，可以適當?shù)慕档烷撝?#xff0c;使得路徑不經(jīng)過一些較危險的點。

如果我們所希望到達的目標點不在紅色區(qū)域內(nèi)，那么我們就要往周圍繞一下，即找一個引導點，再把引導點當成起始點繼續(xù)搜索。引導點一般在起始點和目標點所組成的黃色區(qū)域之外，在黃色區(qū)域內(nèi)找了也白找，這個大家可以體會一下。

我們設計了一個專門用來尋找引導點的程序，一個設置一些參數(shù)之后可以自動找，是一個dfs內(nèi)嵌套了bfs的程序。另一個是利用django設計的一個網(wǎng)頁，可手動點擊地圖查找。

比如圖2中的藍點是在藍色區(qū)域的，無法直接到達，那么我們就找了一個引導點。得到了下圖3所示的地圖。

圖3 安全系數(shù)示例圖2

深綠點即為引導點，從圖中可見，綠點經(jīng)過一個引導點的引導即可到達藍點。
接下來把兩段路徑組合起來即可。

我們的算法不僅可以正向?qū)ふ衣窂?#xff0c;還可以逆向?qū)ふ衣窂?#xff0c;原理類似，不再贅述。

尋找引導點是本算法最為繁瑣的步驟，可以限定時間，以路徑中的最大安全系數(shù)最小作為優(yōu)化目標進行優(yōu)化尋找。后期仍有許多可以改進的地方。

我們有一個更為大膽的想法，就是使得路徑由胖瘦之分，尋找最胖的一條，并以中心線為最終路徑。這個以后有時間再來實踐一下，相信是件非常有趣的事情。

總之，我們在尋找路徑時，我們在保證路徑安全系數(shù)較高的情況下，再去優(yōu)化消耗時間的問題。這些都可以通過我們模型中的各個超參數(shù)做調(diào)整。

6 其它的比賽經(jīng)驗

相信參加了復賽的選手都有體會，復賽中最難的地方就在于如何設計提交路徑的策略。如果一下子交一大堆路徑上去，其中有個幾條沒過，線下的可能性組合是多的可怕的~也就是說胡亂提交的話，根本不知道哪條路徑過了，哪條路徑?jīng)]過。

我們隊在賽前的確考慮過這一點，但在比賽中發(fā)現(xiàn)形勢比想象的嚴峻的多。即使提交的每條路徑時間長短都不一樣，仍舊會有多種組合。于是，我們就寫了一個輸入為線上得分，輸出為線下可能的路徑組合的小程序，在線下模擬幾條可能墜毀的線路墜毀的情況，盡可能保證各種情況下都能區(qū)分出墜毀的路徑。

那么如何修改耗時？我們的超參數(shù)中有一個是可以設置停留時間的。假設達到目的地時為12:30，由于天氣情況在一個小時內(nèi)時不會發(fā)生變化的，于是我們就可以將倒數(shù)第2個點停留0~28分鐘。

當然，也有失手的時候，有些提交的確是沒法區(qū)分。這個時候，我們可以在下一次提交時，保留這次絕大多數(shù)的路徑，然后將兩次提交結(jié)果做對比（甚至是三次結(jié)果做對比），這樣也是可以推導出墜毀的路徑的。

總之，這是一次非常規(guī)套路的算法比賽，這讓我們這些只有低配硬件的算法愛好者也有一展身手的機會，希望天池多辦些可以發(fā)揮創(chuàng)造力的比賽~

如果有任何問題，可以聯(lián)系我~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的气象数据领航无人飞行器线路优化大赛解决方案（3rd place）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。