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

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

任務(wù)

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

數(shù)據(jù)集

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

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

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

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

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

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

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

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

模型架構(gòu)

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

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

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

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

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

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

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

訓(xùn)練

在Google Colab 上對模型進行了大約 15 小時或 23 個周期的訓(xùn)練。使用的損失函數(shù)是均方誤差 (MSE)?？赡苡斜?MSE 更好的選擇，但我一直堅持使用它，因為它簡單易用。

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

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

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

卷積的一些問題

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

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

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

位置編碼

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

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

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

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

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

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

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

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

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

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

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

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

下面就是一些錯誤的圖：

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