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

吳梓喬，蘇越

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

前言

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

1 駕駛路徑規(guī)劃

1.1 路徑設(shè)計

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

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

1.2 Floyd算法

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

2 路徑規(guī)劃模型

2.1 模型的建立

假設(shè)在一個環(huán)境中，一共有n個路口，每一個路口都與數(shù)量不定的其余路口相連接，在這里引入兩個概念，一個是距離矩陣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經(jīng)過的路口, 其中i=(1,2,3,...,n)，j=(1,2,3,...,n)：

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

因此，F(xiàn)loyd算法一共分為以下幾個步驟：

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

第二步：更新矩陣信息。引入新的路口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后返回第二步繼續(xù)進行迭代，直至k=n。

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

以如下路況為例說明：

圖1 路徑選擇模型

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

引入新的路口k，利用matlab采用三層循環(huán)結(jié)構(gòu)進行迭代處理：

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，途中經(jīng)歷的路徑為1→3→4→5→7。

2.3 模型評價

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

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

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

3 小結(jié)

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

無人駕駛技術(shù)應(yīng)用于實際生活中還有很長的一段路要走。在接下來的發(fā)展中，關(guān)于其路徑規(guī)劃問題，未來的發(fā)展必須要結(jié)合實際中的多類情況來進行綜合處理，進行多目標優(yōu)化計算。

參考文獻

[1] 張熙.基于網(wǎng)絡(luò)測量的互聯(lián)網(wǎng)路由優(yōu)化系統(tǒng)的設(shè)計與實現(xiàn)[D].北京郵電大學,2014.

[2] 石松.基于城市路網(wǎng)的浮動車數(shù)據(jù)處理與應(yīng)用[D].北京郵電大學,2015.

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