基于Floyd算法的無人駕駛汽車路徑規劃模型

吳梓喬，蘇越

（長安大學汽車學院，陜西 西安 710064）

前言

近些年來，隨著互聯網產業的迅速發展，傳統的以人為主導操縱汽車的理念受到了極大沖擊，汽車的智能化發展已成為時代需求，汽車與互聯網的緊密結合已成為一個無法避免的趨勢。其中，無人駕駛技術便是最耀眼也是相對較為成熟的一個代表，自從1970年于美國提出無人駕駛的概念后，研發進展十分迅速，各項試驗都取得了矚目的成就。但是與此同時，無人駕駛技術仍有不少問題亟待解決。其中，如何在沒有駕駛員操縱的條件下，自動尋找最佳的行駛路徑到達目的地，便是一個較為突出的問題，無論是對于無人駕駛進行的可行性還是經濟性，這都是一個需要克服的問題。

1 駕駛路徑規劃

1.1 路徑設計

在一般情況下，為了找到一條符合實際情況的最佳路徑，我們需要綜合行駛距離、道路質量、交通狀況等多類因素進行綜合考慮。這類問題屬于多目標優化問題的一種，在復雜的道路情況下很難建立一個合適的模型來綜合考慮所有的變量。因此，從簡化問題的角度上出發，可以選取其中最為重要的一個因素來進行考慮，將該問題轉換為單目標優化。顯然，若要尋找一個最能體現最佳的變量，無論是從成本還是從所需的時間上來綜合考慮，走最短的路徑是最佳的。因此可以將駕駛路徑理解為行走最短路徑，解決方案即為尋找最短路徑。

常用的路徑規劃算法有Dijkstra算法、Floyd算法、SPFA算法、最佳優先算法（BFS）、A*算法。考慮到Floyd算法適用范圍的廣泛性，以及在稠密圖上，運行效率要高于執行V次Dijkstra算法，也要高于執行V次SPFA算法。因此，本文主要討論以Floyd算法為基礎的無人駕駛汽車路徑規劃。

1.2 Floyd算法

Floyd算法是一種利用動態規劃的思想來尋求加權圖中任意節點之間的最短路徑的算法[1]，與Dijkstra算法相似，但時間復雜度要高于Dijkstra算法。Floyd算法可以解決正確處理有向圖的最短路徑問題，允許圖中帶有負權值的邊，但不允許包含帶有負權值邊組成的回路[2]。對于在以距離為變量的背景下，該方案完全可以適用。

2 路徑規劃模型

2.1 模型的建立

假設在一個環境中，一共有n個路口，每一個路口都與數量不定的其余路口相連接，在這里引入兩個概念，一個是距離矩陣D，一個是路徑矩陣P，二者都是n×n的矩陣。

距離矩陣 D中的 d(i,j)表示 i,j路口間的距離，其中i=(1,2,3,...,n)，j=(1,2,3,...,n)：

路徑矩陣P中的path(i,j)代表i通往j經過的路口, 其中i=(1,2,3,...,n)，j=(1,2,3,...,n)：

從對路徑矩陣P的分析中可以發現，現有的路徑方案僅有直通的兩個路口，i→j，并沒有一個中間的過渡路口，顯然這是不成立的。因此，必須要至少引入一個過渡路口 k，即 i→k→j才引入了中轉。在沒引入一個新的路口后，刷新原有的路徑矩陣D與距離矩陣P的信息，如此迭代n次后，便得到了最終的任意兩點間最短間距以及方案。

因此，Floyd算法一共分為以下幾個步驟：

第一步：根據已有數據得到初始距離矩陣D與路徑矩陣P，其中 d(i,j)為已知 i與 j路口最短距離，path(i,j)為從 i→j經過的路口；

第二步：更新矩陣信息。引入新的路口k，如果d(i,k)+d(k,j)＜d(i,j)，則 d(i,j)= d(i,k)+d(k,j),path(i,j)=path(i,k)；

第三步：如果d(i,j)＜0，則停止，否則k=k+1后返回第二步繼續進行迭代，直至k=n。

2.2 Floyd算法利用matlab的求解[3]

以如下路況為例說明：

圖1 路徑選擇模型

初步計算得到初始距離矩陣D與路徑矩陣P：

引入新的路口k，利用matlab采用三層循環結構進行迭代處理：

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j)＜D(i,j)

D(i,j)=D(i,k)+D(k,j);

path(i,j)=path(i,k);

end

end

end

end

最終得到起始點到目標點的最短距離為19，途中經歷的路徑為1→3→4→5→7。

2.3 模型評價

該模型在僅考慮行駛距離的條件下具有很高的參考價值，在每一次計算中都可以得到一個確定的結果，自動規劃出最短路徑以及行駛方案，計算效率相對較高。此外，該模型也有較為靈活的一點，在某條道路封閉后，

初始條件改變下，可以將這條道路與其余路口的距離定義為∞，重新計算，規劃處新路線，符合實際情況。

但與此同時，該模型的弊端也非常明顯，在路徑選擇時，無法綜合考慮其他的因素，僅能單方面的考慮行駛的距離，無法給出一個理想最佳的路徑，不可以單一地應用在路徑規劃上。

3 小結

本文利用了Floyd算法，以matlab進行求解線路求解為例，描述了無人駕駛汽車的路徑規劃上，以行駛距離最短為目標的路徑。在一定程度上，具有可觀的參考價值。但是無法綜合更多的因素進行考慮，在實際生活中還無法直接應用，只能作為一定意義上的參考。

無人駕駛技術應用于實際生活中還有很長的一段路要走。在接下來的發展中，關于其路徑規劃問題，未來的發展必須要結合實際中的多類情況來進行綜合處理，進行多目標優化計算。

參考文獻

[1] 張熙.基于網絡測量的互聯網路由優化系統的設計與實現[D].北京郵電大學,2014.

[2] 石松.基于城市路網的浮動車數據處理與應用[D].北京郵電大學,2015.

[3] 王海英,黃強,李傳濤,褚寶增.圖論算法及其 MATLAB實現[M].北京航空航天大學出版社,2010,22.