基于改進Dijkstra算法的防沖突最短路徑規(guī)劃研究

黃翼虎,于亞楠

(青島科技大學自動化與電子工程學院,山東 青島 266061)

0 引 言

在現(xiàn)代化戰(zhàn)爭時代，作戰(zhàn)環(huán)境以及作業(yè)任務(wù)的多樣化已經(jīng)使得單架無人機不能獨自應對嚴格多變的作戰(zhàn)需求，因此，實現(xiàn)多無人機合作完成作業(yè)任務(wù)已然逐漸成為了專家學者們的關(guān)注熱點[1-2]。無人機群要想實現(xiàn)協(xié)同合作來完成作業(yè)任務(wù)首先面臨的就是路徑規(guī)劃問題，只有為無人機規(guī)劃出最短且互不沖突的航線才能保證作業(yè)任務(wù)的順利完成。國內(nèi)外的研究人員針對此問題歸納總結(jié)了遺傳算法[3-4]、Dijkstra算法[5-7]、A*算法[8-9]、人工勢場算法[10-11]等多種算法。上述算法里，Dijkstra算法是在有權(quán)圖里搜尋最短路線已經(jīng)發(fā)展較為成熟的經(jīng)典算法，其采取的是貪婪搜索策略，由起始點開始逐步地向其他節(jié)點搜索，直至目標點停止，利用回溯數(shù)組進行節(jié)點回溯就必定能夠找出一條最短可行路線，由此在路徑規(guī)劃問題中被普遍使用[12-13]。

傳統(tǒng)Dijkstra算法在規(guī)劃多作業(yè)任務(wù)時，通過回溯數(shù)組僅僅可以給出各任務(wù)的一條最短可行路線，卻不能給出各任務(wù)包含總長度相等的全部最短可行路線，而且沒有把各任務(wù)在執(zhí)行過程中可能存在的路線沖突問題考慮在內(nèi)[14-15]。為解決多無人機在執(zhí)行作業(yè)任務(wù)時可能發(fā)生的沖突問題，本文在經(jīng)典Dijkstra算法執(zhí)行的過程中，通過引入變長回溯數(shù)組來改進其搜索方式，使其能夠回溯出各任務(wù)包含總長度相等的全部最短可行路線，再通過引入時間窗沖突判斷模型來解決路線沖突問題。應用Matlab來設(shè)計并編寫程序進行算法驗證，結(jié)果表明在規(guī)劃多作業(yè)任務(wù)時，引入變長回溯數(shù)組的改進Dijkstra算法能夠找出各任務(wù)存在的全部最短可行路線，時間窗沖突判斷模型可以有效地避免多任務(wù)執(zhí)行時的路線沖突問題并規(guī)劃出互不沖突的最短路線。

1 改進Dijkstra算法

1.1 相關(guān)概念

進行作業(yè)任務(wù)時的帶權(quán)路線圖表示為：

G=(N,E,W)

(1)

其中，N為帶權(quán)路線圖中n0,n1,…，nn全部可行航跡節(jié)點的集合；E為路線圖中e0,e1,…，en所有邊的集合；W為路線圖中w01,w02,…，wnn所有邊的權(quán)值集合，本文中特指為相鄰兩節(jié)點間的直線長度。

有權(quán)路線圖的數(shù)學表達式以鄰接矩陣A表示為：

(2)

其中，aij為節(jié)點ni和nj間的長度。若兩節(jié)點相鄰，其值為wij；若兩節(jié)點不相鄰，其值為∞；若i=j，其值為0。

1.2 改進Dijkstra算法步驟

經(jīng)典Dijkstra算法以廣度優(yōu)先思想從起始點開始逐步向外擴展直至搜索到全部節(jié)點結(jié)束，在遍歷節(jié)點的過程中，通過記錄距離該節(jié)點最近的前驅(qū)節(jié)點而后生成回溯向量[16-17]，憑借回溯向量找出一條由起始點至目標點最短距離的可行路線。但是經(jīng)典Dijkstra算法運行產(chǎn)生的回溯向量僅記錄各節(jié)點的一個前驅(qū)節(jié)點[18]，因此引入變長回溯數(shù)組來記錄各節(jié)點存在的全部前驅(qū)節(jié)點，以此得到各作業(yè)任務(wù)包含總長度相等的全部最短可行路線。為便于表述，定義下列變量符號：

1)A為作業(yè)任務(wù)的帶權(quán)路線圖的鄰接矩陣。

2)st為任務(wù)的起始節(jié)點。

3)e為任務(wù)的目標節(jié)點。

4)S為已經(jīng)明確路線的節(jié)點所組成的向量。

5)D為最短長度向量。D[i]代表由起始節(jié)點st遍歷至節(jié)點ni的最短總長度。

6)P為作業(yè)任務(wù)路線中各節(jié)點的變長回溯數(shù)組，P[i]表示為節(jié)點ni的所有前驅(qū)節(jié)點。

引入變長回溯數(shù)組改進Dijkstra算法搜索最短可行路線的步驟如下：

step1S和D初始化。此時S中只包含起始節(jié)點st，即S={st}，D[i]=ast,i,i=1,2,…，n。

step2從起始節(jié)點向外遍歷其他節(jié)點，找到節(jié)點nj，使得D[j]=minD,令S=S∪{nj}。

step3以節(jié)點nj為中心點向外遍歷，更改D中的最小值以及各節(jié)點的變長回溯數(shù)組。

即若：

D[j]+ajk

(3)

則將D更改為：

D[k]=D[j]+ajk

(4)

將P[k]存放的前驅(qū)節(jié)點全部清除，記節(jié)點k的前驅(qū)節(jié)點為j，將j存放到P[k]。

若：

D[j]+ajk=D[k]

(5)

則在原來P[k]存放前驅(qū)節(jié)點的基礎(chǔ)上，再將j存放到P[k]。

step4循環(huán)step2～step3，直到所有節(jié)點都被搜索。

引入變長回溯數(shù)組后，通過查詢回溯數(shù)組可得到所要執(zhí)行任務(wù)的總長度相等的全部最短可行路線，但是這不能保證各任務(wù)路線在執(zhí)行過程時不發(fā)生沖突矛盾。因此，為了得到各任務(wù)之間互不沖突的路線，引入了時間窗沖突檢測模型。

2 改進Dijkstra算法引入時間窗

2.1 時間窗

時間窗是一種用來表示在有權(quán)路線圖中執(zhí)行作業(yè)任務(wù)的何時處于何地的方法[19-20]。因為具備實現(xiàn)簡單和實用性強等特點，時間窗在路徑規(guī)劃問題中被普遍使用[21]。

本文建立時間窗模型的假設(shè)條件包括：

1)將無人機在移動過程中視作質(zhì)點，忽略其形狀和大小且都在同一高度上飛行。

2)帶權(quán)路線圖中節(jié)點之間為單行道，即同一時間段內(nèi)每條邊只允許一架無人機飛行，但可雙向通行，不計節(jié)點處的長度。

3)無人機以V0=1 m/s勻速移動，忽略其加減速及轉(zhuǎn)彎時所用的時間。

4)Administrator可以設(shè)定作業(yè)任務(wù)的優(yōu)先等級，一般默認為產(chǎn)生作業(yè)任務(wù)的時間序列[22]。

本文中時間窗具體指無人機在所規(guī)劃的航線上飛行時，到達航跡節(jié)點的具體時間點以及在節(jié)點之間所占用的時間區(qū)間。時間窗模型[23-24]如下：

TWn=[ti,ti+1],i=1,2,…,end

(6)

(7)

其中，TWn為第n架無人機執(zhí)行任務(wù)時的航線時間窗；ti和ti+1為該無人機到達航線中第i個和第i+1個航跡節(jié)點的時間點；D(i,i+1)為該無人機任務(wù)航線中第i個和第i+1個航跡節(jié)點間的長度。根據(jù)以上公式，可以得到該無人機從起始點至目標點所產(chǎn)生的時間窗。

多無人機發(fā)生航線沖突的本質(zhì)是多個任務(wù)在執(zhí)行過程中同時占用了同一節(jié)點或節(jié)點區(qū)間，時間窗能詳細反映無人機何時在何地的狀態(tài)信息[25-26]，為之后判別及解決航線沖突問題提供了前提條件。

2.2 改進Dijkstra算法引入時間窗模型步驟

為便于表述，引入以下字母符號：

1)to(i)為已完成的任務(wù)中i節(jié)點的占用時刻。

2)tn(i)為當前的任務(wù)在i節(jié)點的占用時刻。

3)starto(i,j)為已完成的任務(wù)中i-j節(jié)點區(qū)間的開始占用時刻。

4)startn(i,j)為當前的任務(wù)在i-j節(jié)點區(qū)間的開始占用時刻。

5)endo(i,j)為已完成的任務(wù)中i-j節(jié)點區(qū)間的結(jié)束占用時刻。

6)endn(i,j)為當前的任務(wù)在i-j節(jié)點區(qū)間的結(jié)束占用時刻。

改進Dijkstra算法引入時間窗沖突判斷模型的步驟如下：

step1根據(jù)作業(yè)任務(wù)的帶權(quán)路線圖生成鄰接矩陣，設(shè)定任務(wù)優(yōu)先等級并生成任務(wù)作業(yè)列表[27]。

step2運用改進Dijkstra算法對當前任務(wù)作業(yè)列表中還沒有執(zhí)行的優(yōu)先等級最高的任務(wù)進行規(guī)劃，生成該任務(wù)包含總長度相等的全部最短可行路線的時間窗。

step3依次判斷當前任務(wù)的所有最短可行路線與任務(wù)作業(yè)列表里已完成的所有任務(wù)路線是否存在相同的節(jié)點或節(jié)點區(qū)間，若存在則引入時間窗進行沖突判斷。

若存在相同節(jié)點i，節(jié)點i處時間窗滿足以下條件則無沖突：

to(i)≠tn(i)

(8)

若存在相同的i-j節(jié)點區(qū)間，i-j節(jié)點區(qū)間的時間窗滿足以下條件則無沖突：

Startn>Endo||Endn

(9)

step4在當前任務(wù)的所有最短路線依次執(zhí)行時間窗沖突檢測過程中，若發(fā)現(xiàn)一條最短路線無沖突則停止剩余最短路線的時間窗沖突檢測，將這條路線作為該任務(wù)的最短可行路線，跳轉(zhuǎn)到step6。若所有的最短路線都存在沖突，則將其中一條路線中的沖突節(jié)點臨時作為障礙節(jié)點處理，改變鄰接矩陣，轉(zhuǎn)到step5。

step5循環(huán)step2～step4，直至得到無沖突的最短路線，釋放臨時障礙節(jié)點，完成對當前任務(wù)的規(guī)劃。

step6循環(huán)step2～step5，直到任務(wù)列表中的作業(yè)任務(wù)全部規(guī)劃完成。每當無人機到達該任務(wù)航線的目標節(jié)點時，該任務(wù)在任務(wù)列表中自動消除[28]。

3 算法的驗證

3.1 作業(yè)任務(wù)描述

為驗證上述算法的可行性，結(jié)合實例應用Matlab進行算法驗證。執(zhí)行作業(yè)任務(wù)時的帶權(quán)路線圖如圖1所示。

圖1 帶權(quán)路線圖

圖1中包括8個節(jié)點，權(quán)值代表2個節(jié)點之間的直線距離，如節(jié)點1和節(jié)點2間的長度為20米。假設(shè)在t=0 s，t=10 s，t=20 s時刻依次生成Task1、Task2和Task3這3個作業(yè)任務(wù)，指定任務(wù)優(yōu)先等級Task1>Task2>Task3。作業(yè)任務(wù)包括：Task1起始節(jié)點為節(jié)點1，目標節(jié)點為節(jié)點6；Task2起始節(jié)點為節(jié)點6，目標節(jié)點為節(jié)點1；Task3起始節(jié)點為節(jié)點3，目標節(jié)點為節(jié)點8。其中U1、U2和U3為3架空閑的無人機，分別停在節(jié)點1、節(jié)點6和節(jié)點3。為了方便上述改進算法的驗證，假設(shè)作業(yè)任務(wù)生成時空閑的無人機U1、U2和U3均能被各個任務(wù)隨時調(diào)配使用。

3.2 方案驗證

根據(jù)圖1構(gòu)建8×8的鄰接矩陣A0：

運用改進Dijkstra算法對上述任務(wù)集合進行規(guī)劃,生成的變長回溯數(shù)組如表1所示。

表1 變長回溯數(shù)組

根據(jù)各任務(wù)生成的回溯數(shù)組，查詢到各任務(wù)包含總長度相等的全部最短可行路線如表2所示。

表2 Task1、Task2、Task3任務(wù)路線

由表2可知，運用改進Dijkstra算法對上述的3個作業(yè)任務(wù)規(guī)劃出來的可行路線結(jié)果為：Task1有2條最短路線，Task2有2條最短路線，Task3有1條最短路線。由于優(yōu)先等級Task1>Task2>Task3，Task1選擇其中1條最短路線1→4→7→6作為最終路線，則Task2第1條最短路線6→7→4→1和第2條最短路線6→5→2→1的任務(wù)路線時間窗分別與Task1任務(wù)路線時間窗做沖突檢測，結(jié)果如圖2所示。

圖2 Task1、Task2任務(wù)路線時間窗

由圖2中Task1和Task2任務(wù)路線的時間窗沖突檢測可知，Task2的第1條最短路線的時間窗與Task1路線的時間窗在20 s-50 s的時間區(qū)間內(nèi)同時占用了4-7節(jié)點區(qū)間，說明Task2的第1條最短路線與Task1的任務(wù)路線在4-7節(jié)點區(qū)間內(nèi)發(fā)生了區(qū)間類型沖突；Task2的第2條最短路線時間窗與Task1路線的時間窗不存在沖突，在算法執(zhí)行過程中，Task2選擇規(guī)劃的第2條最短路線6→5→2→1作為最終路線。

以上得到了Task1和Task2的任務(wù)路線，由表2可知，Task3只規(guī)劃出一條最短路線3→6→8，Task3與Task1、Task2任務(wù)路線的時間窗沖突檢測結(jié)果如圖3所示。

圖3 Task1、Task2、Task3任務(wù)路線時間窗

由圖3各任務(wù)路線的時間窗沖突檢測可知，Task3任務(wù)路線與Task1任務(wù)路線第60 s時在節(jié)點6處發(fā)生了節(jié)點沖突，由于任務(wù)優(yōu)先等級Task1>Task3且Task3沒有備用的最短路線可選，在算法執(zhí)行過程中，將節(jié)點6作為Task3的臨時障礙節(jié)點處理，即3-6節(jié)點區(qū)間視作為禁行區(qū)間，更改鄰接矩陣，將a36和a63改為∞，對Task3重新規(guī)劃路線，鄰接矩陣更改為A1。

更改鄰接矩陣后，Task3任務(wù)路線的變長回溯數(shù)組也跟隨發(fā)生改變，生成的變長回溯數(shù)組如表3所示。

表3 變長回溯數(shù)組

回溯數(shù)組的改變使規(guī)劃的路線發(fā)生相應的改變，根據(jù)生成的回溯數(shù)組，查詢到Task3任務(wù)的最短路線如表4所示。

表4 Task3任務(wù)路線

由表4可知，Task3更改為2條最短路線，第1條最短路線為3→4→7→6→8，第2條最短路線為3→2→5→8，Task3與Task1、Task2任務(wù)路線的時間窗沖突檢測結(jié)果如圖4所示。

圖4 Task1、Task2、Task3任務(wù)路線時間窗

由圖4可知，更改鄰接矩陣后，Task3的第1條路線與Task1和Task2的任務(wù)路線沒有發(fā)生沖突。由于第1條路線無沖突，算法執(zhí)行過程中不會再對第2條路線進行時間窗沖突檢測，因此Task3選擇規(guī)劃的第一條最短路線3→4→7→6→8作為最終路線。

通過對整個任務(wù)集合中的作業(yè)任務(wù)進行路線規(guī)劃，實驗結(jié)果可以看出，在保證各任務(wù)路線互不沖突的前提下，Task1與Task2都選擇了長度最短路線，Task3選擇了次優(yōu)路線，說明經(jīng)過算法改進后，在多無人機執(zhí)行作業(yè)任務(wù)時，能夠解決任務(wù)集合中可能面臨的路線沖突問題并規(guī)劃出各任務(wù)之間互不沖突的最短可行路線，對任務(wù)集合進行規(guī)劃的效率有了明顯提高。

4 結(jié)束語

面對經(jīng)典Dijkstra算法在進行多無人機執(zhí)行任務(wù)路線規(guī)劃時，其規(guī)劃的結(jié)果只能給出各任務(wù)的一條最短可行路線且不會考慮各任務(wù)執(zhí)行過程時可能存在的路線沖突問題，本文提出了一種改進Dijkstra算法的多無人機尋找防沖突最短路線算法。在由當前任務(wù)的起始點逐步向目標點搜尋的過程中，通過引入變長回溯數(shù)組來得到各任務(wù)包含總長度相等的全部最短路線，再引入時間窗沖突判斷模型從各任務(wù)的所有最短路線中找出互不沖突的可行路線，若所有路線都沖突，則將沖突節(jié)點臨時視作障礙點處理，通過改變鄰接矩陣得到回溯數(shù)組來重新查詢?nèi)蝿?wù)路線，再次引入時間窗沖突判斷模型來得到與其他任務(wù)互不沖突的可行路線。

仿真實驗表明該算法能夠規(guī)劃出各任務(wù)包含總長度相等的全部最短路線且能判斷出各任務(wù)路線之間是否存在沖突，能夠有效解決任務(wù)執(zhí)行時存在的節(jié)點類型沖突和區(qū)間類型沖突，當與所有最短路線都存在沖突時，還能為該任務(wù)規(guī)劃出次優(yōu)路線，對作業(yè)任務(wù)集合的規(guī)劃效率有著明顯提升。本文僅針對3個作業(yè)任務(wù)進行了仿真驗證，且同時也適用于多個任務(wù)的情況。