本文將介紹CNN應(yīng)用于解決簡單的二維路徑規(guī)劃問題。

卷積神經(jīng)網(wǎng)絡(luò)(CNN)是解決圖像分類、分割、目標(biāo)檢測等任務(wù)的流行模型。本文將CNN應(yīng)用于解決簡單的二維路徑規(guī)劃問題。主要使用Python, PyTorch, NumPy和OpenCV。

任務(wù)

簡單地說，給定一個(gè)網(wǎng)格圖，二維路徑規(guī)劃就是尋找從給定起點(diǎn)到所需目標(biāo)位置（目標(biāo)）的最短路徑。機(jī)器人技術(shù)是路徑規(guī)劃至關(guān)重要的主要領(lǐng)域之一。A、D、D* lite 和相關(guān)變體等算法就是為解決此類問題而開發(fā)的。如今強(qiáng)化學(xué)習(xí)被廣泛用于解決這一問題。本文將嘗試僅使用卷積神經(jīng)網(wǎng)絡(luò)來解決簡單的路徑規(guī)劃實(shí)例。

數(shù)據(jù)集

我們的主要問題是（在機(jī)器學(xué)習(xí)中一如既往）在哪里可以找到數(shù)據(jù)。雖然沒有現(xiàn)成的數(shù)據(jù)集可用，但是我們可以通過制作隨機(jī)二維地圖創(chuàng)建自己的路徑規(guī)劃數(shù)據(jù)集。創(chuàng)建地圖的過程非常簡單：

從一個(gè) 100x100 像素的方形空矩陣 M 開始。

對(duì)于矩陣中的每一項(xiàng)（像素），從0到1均勻分布抽取一個(gè)隨機(jī)數(shù)r。如果 r > diff，則將該像素設(shè)置為 1；否則，將其設(shè)置為 0。這里的 diff 是一個(gè)參數(shù)，表示像素成為障礙物（即無法穿越的位置）的概率，它與在該地圖上找到可行路徑的難度成正比。

然后讓我們利用形態(tài)學(xué)來獲得更類似于真實(shí)占用網(wǎng)格地圖的“塊狀”效果。通過改變形態(tài)結(jié)構(gòu)元素的大小和 diff 參數(shù)，能夠生成具有不同難度級(jí)別的地圖。

對(duì)于每張地圖需要選擇 2 個(gè)不同的位置：起點(diǎn) (s) 和終點(diǎn) (g)。該選擇同樣是隨意的，但這次必須確保 s 和 g 之間的歐幾里得距離大于給定閾值（使實(shí)例具有挑戰(zhàn)性）。

最后需要找到從 s 到 g 的最短路徑。這是我們訓(xùn)練的目標(biāo)。所以可以直接使用了流行的 D* lite 算法。

我們生成的數(shù)據(jù)集包含大約 230k 個(gè)樣本（170k 用于訓(xùn)練，50k 用于測試，15k 用于驗(yàn)證）。數(shù)據(jù)量很大，所以我使用 Boost c++ 庫將自定義的 D* lite 重寫為 python 擴(kuò)展模塊。使用這個(gè)模塊，生成超過 10k 個(gè)樣本/小時(shí)，而使用純 python 實(shí)現(xiàn)，速率約為 1k 個(gè)樣本/小時(shí)（i7–6500U 8GB 內(nèi)存）。自定義 D* lite 實(shí)現(xiàn)的代碼會(huì)在文末提供。

然后就是對(duì)數(shù)據(jù)做一些簡單的檢查，比如刪掉余弦相似度很高，起點(diǎn)和終點(diǎn)坐標(biāo)太近的地圖。數(shù)據(jù)和代碼也都會(huì)在文末提供。

模型架構(gòu)

模型是經(jīng)典的編碼器-解碼器架構(gòu)，將 20 個(gè)卷積層分為 3 個(gè)卷積塊（編碼部分），然后是另外 3 個(gè)轉(zhuǎn)置卷積塊（解碼部分）。每個(gè)塊由 3 個(gè) 3x3 卷積層組成，每個(gè)層之間有BN和 ReLU 激活。最后，還有另外 2 個(gè) conv 層，加上輸出層。編碼器的目標(biāo)是找出輸入壓縮后的相關(guān)表示。解碼器部分將嘗試重建相同的輸入映射，但這次嵌入的有用信息應(yīng)該有助于找到從 s 到 g 的最佳路徑。

該網(wǎng)絡(luò)的輸入是：

map：一個(gè) [n, 3, 100, 100] 張量，表示占用網(wǎng)格圖。n 是批量大小。這里的通道數(shù)是 3 而不是簡單的 1。稍后會(huì)詳細(xì)介紹。

start: 一個(gè) [n, 2] 張量，包含每個(gè)地圖中起點(diǎn) s 的坐標(biāo)

goal：一個(gè)[n, 2]張量，包含每個(gè)地圖中目標(biāo)點(diǎn)g的坐標(biāo)

網(wǎng)絡(luò)的輸出層應(yīng)用 sigmoid 函數(shù)，有效地提供了一個(gè)“分?jǐn)?shù)圖”，其中每個(gè)項(xiàng)目的值都在 0 和 1 之間，與屬于從 s 到 g 的最短路徑的概率成正比。然后可以通過從 s 開始并迭代地選擇當(dāng)前 8 鄰域中得分最高的點(diǎn)來重建路徑。一旦找到與 g 具有相同坐標(biāo)的點(diǎn)，該過程就會(huì)結(jié)束。為了提高效率，我為此使用了雙向搜索算法。

在模型的編碼器和解碼器塊之間，我還插入了 2 個(gè)跳過連接。該模型現(xiàn)在非常類似于 U-Net 的架構(gòu)。跳過連接將給定隱藏層的輸出注入網(wǎng)絡(luò)中更深的其他層。在我們的任務(wù)中關(guān)心的細(xì)節(jié)是 s、g 的確切位置，以及我們?cè)谲壽E中必須避開的所有障礙物。所以加入跳過鏈接大大提高了效果。

訓(xùn)練

在Google Colab 上對(duì)模型進(jìn)行了大約 15 小時(shí)或 23 個(gè)周期的訓(xùn)練。使用的損失函數(shù)是均方誤差 (MSE)?？赡苡斜?MSE 更好的選擇，但我一直堅(jiān)持使用它，因?yàn)樗唵我子谩?/p>

學(xué)習(xí)率最初使用 CosineAnnealingWithWarmRestarts 調(diào)度程序設(shè)置為 0.001（略微修改以降低每次重啟后的最大學(xué)習(xí)率）。批量大小設(shè)置為 160。

我嘗試對(duì)輸入圖應(yīng)用高斯模糊，并在第一個(gè)卷積層應(yīng)用一個(gè)小的 dropout。這些技術(shù)都沒有帶來任何相關(guān)效果，所以我最終放棄了它們。

下面是訓(xùn)練后模型原始輸出的可視化。

卷積的一些問題

起初使用輸入是一個(gè)形狀為 [n, 1, 100, 100]（加上起始位置和目標(biāo)位置）的張量。但無法獲得任何令人滿意的結(jié)果。重建的路徑只是完全偏離目標(biāo)位置并穿過障礙物的隨機(jī)軌跡。

卷積算子的一個(gè)關(guān)鍵特征是它是位置不變的。卷積濾波器學(xué)習(xí)的實(shí)際上是一種特定的像素模式，這種像素模式在它所訓(xùn)練的數(shù)據(jù)分布中反復(fù)出現(xiàn)。例如下面的圖案可以表示角或垂直邊緣。

無論過濾器學(xué)習(xí)什么模式，關(guān)鍵的問題是它學(xué)會(huì)獨(dú)立于圖像中的位置來識(shí)別它。對(duì)于像圖像分類這樣的任務(wù)來說，這無疑是一個(gè)理想的特性，因?yàn)樵谶@些任務(wù)中，表征目標(biāo)類的模式可能出現(xiàn)在圖像的任何地方。但在我們的情況下，位置是至關(guān)重要的!我們需要這個(gè)網(wǎng)絡(luò)非常清楚的知道軌跡從哪里開始，從哪里結(jié)束。

位置編碼

位置編碼是一種通過將數(shù)據(jù)嵌入(通常是簡單的和)到數(shù)據(jù)本身中來注入關(guān)于數(shù)據(jù)位置的信息的技術(shù)。它通常應(yīng)用于自然語言處理(NLP)中，使模型意識(shí)到句子中單詞的位置。我想這樣的東西對(duì)我們的任務(wù)也有幫助。

我通過在輸入占用圖中添加這樣的位置編碼進(jìn)行了一些實(shí)驗(yàn)，但效果并不好。可能是因?yàn)橥ㄟ^添加關(guān)于地圖上每個(gè)可能位置的信息，違背了卷積的位置不變性，所以濾波器現(xiàn)在是無用的。

所以這里基于對(duì)路徑規(guī)劃的觀察，我們對(duì)絕對(duì)位置不感興趣，而只對(duì)相對(duì)范圍感興趣。也就是說，我們感興趣的是占用圖中每個(gè)單元格相對(duì)于起點(diǎn)s和目標(biāo)點(diǎn)g的位置。例如，以坐標(biāo)(x, y)為單元格。我并不真正關(guān)心(x, y)是否等于(45,89)還是(0,5)。我們關(guān)心的是(x, y)距離s 34格，距離g15格。

所以我為每個(gè)占用網(wǎng)格圖創(chuàng)建2個(gè)額外的通道，現(xiàn)在它的形狀為[3,100,100] 。第一個(gè)通道是圖像。第二個(gè)通道表示一個(gè)位置編碼，它為每個(gè)像素分配一個(gè)相對(duì)于起始位置的值。第三通道則是相對(duì)于結(jié)束位置的值。這樣的編碼是通過分別從以s和g為中心的二維高斯函數(shù)創(chuàng)建2個(gè)特征映射來實(shí)現(xiàn)的。Sigma被選為核大小的五分之一(通常在高斯濾波器中)。在我們的例子中是20，地圖大小是100。

在注入關(guān)于期望的軌跡起始和最終位置的有用信息的同時(shí)，我們還部分地保留了與過濾器位置不變性的一致性?？蓪W(xué)習(xí)的模式現(xiàn)在只依賴于相對(duì)于給定點(diǎn)的距離，而不是地圖上每個(gè)可能的位置。距離s或g相同距離的2個(gè)相等的圖案現(xiàn)在將觸發(fā)相同的過濾器激活。經(jīng)過實(shí)驗(yàn)這個(gè)小技巧在收斂訓(xùn)練中非常有效。

結(jié)果和結(jié)論

通過測試了超過 51103 個(gè)樣本的訓(xùn)練模型。

95% 的總測試樣本能夠使用雙向搜索提供解決方案。也就是說，該算法使用模型給出的得分圖可以在 48556 個(gè)樣本中找到從 s 到 g 的路徑，而對(duì)于其余 2547 個(gè)樣本則無法找到。

總測試樣本的 87% 提供了有效的解決方案。也就是說從 s 到 g 的軌跡不穿越任何障礙物（該值不考慮 1 個(gè)單元格的障礙物邊緣約束）。

在有效樣本上，真實(shí)路徑與模型提供的解決方案之間的平均誤差為 33 個(gè)單元格。考慮到地圖是 100x100 單元格，這是相當(dāng)高的。錯(cuò)誤范圍從最小 0（即，在 2491 個(gè)樣本中的真實(shí)路徑被“完美”的重建了）到最大……745 個(gè)單元（這個(gè)肯定還有一些問題）。

下面可以看看我們測試集中的一些結(jié)果。圖像的左側(cè)描述了訓(xùn)練過的網(wǎng)絡(luò)提供的解決方案，而右側(cè)顯示了D* lite算法的解決方案。

我們網(wǎng)絡(luò)提供的解決方案比D* lite給出的解決方案短：

下面就是一些錯(cuò)誤的圖：

看著應(yīng)該是感受野不太大，所以在感受野的區(qū)域內(nèi)沒有找到任何的邊緣，這個(gè)可能還要再改進(jìn)模型。