基于完善交通信息收集的UAV路徑規(guī)劃

王冬冬，何勝學(xué)，路 揚(yáng)

（上海理工大學(xué)管理學(xué)院，上海 200093）

0 引言

實(shí)時、準(zhǔn)確的交通信息是實(shí)施交通管理和控制的基礎(chǔ)。目前交通信息采集主要依賴于配備在固定位置的各類固定型交通信息檢測器，如固定線圈、紅外和視頻檢測器等。受經(jīng)濟(jì)預(yù)算的限制，部分城市路段沒有布置固定型交通信息檢測器，無法獲取有效的交通信息。作為新時代的產(chǎn)物，無人機(jī)（Unmanned Aerial Vehicle，簡稱UAV）已經(jīng)廣泛應(yīng)用于交通信息收集、緊急救援、電力巡檢等各領(lǐng)域[1-4]。針對現(xiàn)有交通巡檢設(shè)備巡檢效率低、靈活性差等問題，提出使用無人機(jī)收集完善交通信息的方法[5]。然而，因受電池容量的限制，無人機(jī)的飛行時間有限，研究無人機(jī)的最佳飛行路徑就變得非常重要和有意義。

目前國內(nèi)外對無人機(jī)路徑規(guī)劃方面的研究主要涉及算法研究，確定最佳的無人機(jī)數(shù)量以及使用有限數(shù)量的無人機(jī)巡視盡可能多的目標(biāo)等。Kim等對用于交通道路巡查的無人機(jī)自動控制算法進(jìn)行研究，通過UAV人工視覺系統(tǒng)（Artificial Vision Sys?tem，簡稱AVS）分析應(yīng)急和異常交通情況，提供車輛跟蹤和速度檢測問題的解決方案[6]。Karakaya研究使用有限數(shù)量的無人機(jī)進(jìn)行路徑優(yōu)化，在考慮飛行范圍的基礎(chǔ)上盡可能多地覆蓋目標(biāo)，并通過改進(jìn)后的最大最小螞蟻算法（MAX-MIN Ant System，簡稱MMAS）進(jìn)行求解[7]。Huang等提出一種多UAV協(xié)同路徑規(guī)劃方法,通過蟻群優(yōu)化算法獲得UAV的初始路徑，并通過K-means方法獲得更多的可飛行路徑[8]。Avellar等在無人機(jī)數(shù)量有限的條件下，確定最佳的無人機(jī)數(shù)量，并給出使所有無人機(jī)覆蓋時間最短的方法[9]。Niu等提出使用無人機(jī)作為一種移動型交通檢測器對高速公路進(jìn)行巡視，在總飛行時間最短的情況下盡可能多地巡視未布設(shè)固定型交通檢測器路段[10]。劉曉鋒等對無人機(jī)用于交通事件監(jiān)測、交通信息采集進(jìn)行了研究[11-13]。劉曉鋒等在無人機(jī)數(shù)量有限，不足以對所有目標(biāo)進(jìn)行偵察的前提下，建立了以巡航總距離最短且巡視目標(biāo)盡可能多為目的的優(yōu)化模型，并使用遺傳算法進(jìn)行求解[11]。上述研究雖然對未布設(shè)固定型交通檢測器的路段進(jìn)行信息收集，但沒有考慮到收集信息的準(zhǔn)確性以及利用無人機(jī)資源的合理性。

本文擬通過時空網(wǎng)絡(luò)，建立以總飛行時間最短和最大單機(jī)飛行時間最短為目標(biāo)的多目標(biāo)模型，優(yōu)化巡視路徑，并通過添加巡視次數(shù)和巡視時間間隔使收集到的信息更加符合實(shí)際需要。

1 時空網(wǎng)絡(luò)介紹

為細(xì)致刻畫無人機(jī)在路網(wǎng)巡視過程中的動態(tài)飛行特征，將動態(tài)的路網(wǎng)巡視過程轉(zhuǎn)化為靜態(tài)的無人機(jī)飛行軌跡，在此引入時空網(wǎng)絡(luò)作為研究框架[14-15]。將普通的原始路網(wǎng)拓展為時空路網(wǎng)后一般網(wǎng)絡(luò)規(guī)模都比較大，問題的求解有一定難度?？紤]到本文主要研究UAV的路徑規(guī)劃問題，為降低求解難度，假設(shè)無人機(jī)的飛行速度固定，且不考慮無人機(jī)轉(zhuǎn)彎的時耗。圖1所示為原始路網(wǎng)到時空路網(wǎng)的具體轉(zhuǎn)化過程。首先，根據(jù)所有路段的行程時間確定時空路網(wǎng)的單位時長，確保所有路段的行程時間都是單位時長的整數(shù)倍。然后，根據(jù)完成任務(wù)所需的路段行程時間，將原始路網(wǎng)中所有節(jié)點(diǎn)復(fù)制n份。最后，進(jìn)行時空路段的連接，依據(jù)原始路段添加相應(yīng)的時空路段，即無人機(jī)從一個節(jié)點(diǎn)前往另一個節(jié)點(diǎn)的過程，在時空路網(wǎng)中用運(yùn)行弧表示。

圖1中，線型1表示運(yùn)行弧，代表無人機(jī)所有可能飛行的路徑；線型2連接位于相鄰時刻的同一節(jié)點(diǎn)，表示無人機(jī)在一個節(jié)點(diǎn)等待一個分段時長，即隨著時間的變化，無人機(jī)的空間位置未發(fā)生變化。有向?qū)嵕€（線型3）給出了一個無人機(jī)在時空路網(wǎng)中的運(yùn)行軌跡：無人機(jī)p在t=0時刻從節(jié)點(diǎn)a出發(fā)開始巡邏任務(wù)，在下一時刻到達(dá)節(jié)點(diǎn)b，然后經(jīng)過節(jié)點(diǎn)b在t=3時刻到達(dá)節(jié)點(diǎn)c，最后從節(jié)點(diǎn)c按照原路返回，在t=6時刻經(jīng)節(jié)點(diǎn)b回到節(jié)點(diǎn)a。因本研究不考慮無人機(jī)的等待行為，故對于等待弧不予考慮。

圖1 一個簡單原始路網(wǎng)的時空網(wǎng)絡(luò)圖

2 模型構(gòu)建

2.1 目標(biāo)函數(shù)的建立

合理的飛行路徑應(yīng)要求所有無人機(jī)在滿足飛行特性約束和巡視任務(wù)約束的前提下，總飛行代價最小。這里考慮的飛行代價包括無人機(jī)的總飛行時間和完成任務(wù)的時間跨度，其飛行代價分別用式（1）和式（2）表示為：

式（1）中：f1表示無人機(jī)的總飛行時間（min）；m,n表示節(jié)點(diǎn)號；Nm表示所有與節(jié)點(diǎn)m直接相連的節(jié)點(diǎn)的集合；P表示無人機(jī)的集合，p表示其中一架無人機(jī)；tm,n表示節(jié)點(diǎn)m到節(jié)點(diǎn)n所在道路的路段行程時間（min），有tm,n=tn,m，其中某一時刻用t表示；xpm,t,n是一個0-1變量，表示無人機(jī)p是否在t時刻進(jìn)行從節(jié)點(diǎn)m到節(jié)點(diǎn)n的巡視。當(dāng)xpm,t,n=1時，代表無人機(jī)p在t時刻進(jìn)行從m點(diǎn)到n點(diǎn)的巡視；xpm,t,n=0則表明不進(jìn)行。

式（2）中：f2表示最大單機(jī)飛行時間（min）；Z為新引入的參數(shù)，表示任意單架無人機(jī)的飛行時間上限（min），有

傳統(tǒng)求解多目標(biāo)問題的方法主要通過對多個目標(biāo)賦予不同的權(quán)重系數(shù)，然后通過線性組合將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題。這種方法便于通過調(diào)整權(quán)重系數(shù)得到想要的結(jié)果，也有利于問題的分析。在使用這種平均加權(quán)因子的方法計算模型之前，需要先用公式（3）和公式（4）對兩個目標(biāo)進(jìn)行歸一化處理：

最終的目標(biāo)函數(shù)值計算如下：

式（3）～式（5）中：Tpperfect表示遍歷整個路網(wǎng)所需要的單機(jī)飛行時間（min）；表示遍歷整個路網(wǎng)所需要的總飛行時間（min）；g1,g2分別表示目標(biāo)f1和目標(biāo)f2歸一化后的值；w1,w2是無人機(jī)飛行代價的權(quán)重系數(shù)，分別表示無人機(jī)的總飛行時間最少和最大單機(jī)飛行時間最少的重要程度，且滿足w1+w2=1，w1,w2∈[0,1]；g表示多目標(biāo)歸一化后考慮權(quán)重系數(shù)的和，g值越小越好。

2.2 約束條件的建立

為保證所收集交通信息的準(zhǔn)確性和巡視路徑的合理性，模型需要考慮單路段的巡視次數(shù)、巡視時間間隔、節(jié)點(diǎn)流量守恒以及單架無人機(jī)的最大飛行時間約束。

首先，考慮單路段的巡視次數(shù)，要求每條路段(m,n)至少巡視Rm,n次，即：

式（6）中：M,N表示路網(wǎng)中所有路段起點(diǎn)和終點(diǎn)的集合；(M,N)表示所有路段的集合，且(m,n)∈(M,N)；Rm,n表示路段(m,n)的最少巡視次數(shù)（次）。

接著，考慮單路段的巡視時間間隔約束，要求單路段在最小巡視時間間隔內(nèi)至多被巡視一次，即：

式（7）中：Δt表示單路段的最小巡視時間間隔（min）；T表示時空路網(wǎng)中所有時間的集合（min），有t∈T；(M,T,N)表示時空路網(wǎng)中所有時空路段的集合，即任意時刻所有路段的集合，有

隨后，考慮節(jié)點(diǎn)的流量守恒。在任意時刻，無人機(jī)進(jìn)入某一結(jié)點(diǎn)的次數(shù)加（減）無人機(jī)從該結(jié)點(diǎn)加載進(jìn)入（離開）時空路網(wǎng)的次數(shù)等于無人機(jī)離開該結(jié)點(diǎn)的次數(shù)。對應(yīng)的流量守恒約束如下：

式（8）中：引入整數(shù)變量rp n,t，表示無人機(jī)p是否

在t時刻從節(jié)點(diǎn)n加載進(jìn)入或離開時空路網(wǎng)。當(dāng)時，表示無人機(jī)p在t時刻從節(jié)點(diǎn)n加載進(jìn)入時空路網(wǎng)；當(dāng)時，表示無人機(jī)p在t時刻從節(jié)點(diǎn)n離開時空路網(wǎng)；表示其他情況；(N,T)表示所有節(jié)點(diǎn)在時空路網(wǎng)中的集合，即任意時刻所有節(jié)點(diǎn)的集合，有

最后，每架無人機(jī)的巡視時間都應(yīng)小于等于其最大續(xù)航時間，即：

式（9）中：Tp表示無人機(jī)p的最大飛行時間（min）。

若要求無人機(jī)在最短時間內(nèi)完成全部的交通信息收集任務(wù)，還需添加如下約束：

以式（5）為目標(biāo)、式（6）～式（10）為約束的多UAV交通信息收集路徑規(guī)劃模型是一個大規(guī)模線性整數(shù)規(guī)劃模型。求解這類問題的經(jīng)典方法主要有分支定界法[16]和割平面法，也可以使用經(jīng)典的啟發(fā)式方法，如遺傳算法[17]、模擬退火算法[18]和粒子群算法等求解模型。其中部分較成熟的算法已經(jīng)在一些商業(yè)軟件當(dāng)中得到應(yīng)用，并且有著較好的求解效率。本文將使用商用軟件Lingo對模型進(jìn)行求解。

3 算例分析和驗(yàn)證

3.1 算例分析

圖2所示交通網(wǎng)絡(luò)由10個節(jié)點(diǎn)和36條路段組成。節(jié)點(diǎn)間的路段行程時間標(biāo)注在路段上方，選擇1min作為一個單位時長。使用2架無人機(jī)對該網(wǎng)絡(luò)進(jìn)行信息收集。無人機(jī)在起飛前分別位于節(jié)點(diǎn)3和節(jié)點(diǎn)8的基站位置，完成巡視任務(wù)后分別回到起飛的基站位置。圖中（1,3），（2,5），（4,7），（6,7）所在路段不能收集到有效的交通信息，需要使用無人機(jī)對以上各路段至少巡視兩次，且巡視時間間隔應(yīng)大于上述路段最大行程時間的2倍。

圖2 路網(wǎng)示意圖

首先根據(jù)圖2在Lingo中建立原始路網(wǎng)，并根據(jù)圖1所示的方法在原始路網(wǎng)的基礎(chǔ)上增加一個時間維度，完成原始路網(wǎng)到時空路網(wǎng)的轉(zhuǎn)化。然后根據(jù)上文提到的目標(biāo)和任務(wù)約束建立目標(biāo)函數(shù)和約束條件，要求兩架無人機(jī)分別從節(jié)點(diǎn)3和節(jié)點(diǎn)8起飛，巡視結(jié)束后回到起飛位置。運(yùn)算程序，得到所有xpm,t,n=1的量。對同一架無人機(jī)p而言，將所有的xpm,t,n=1按照時間順序排列，即可得到無人機(jī)p在時空網(wǎng)絡(luò)中的運(yùn)行軌跡。最后，將無人機(jī)在時空網(wǎng)絡(luò)中所經(jīng)過的時空節(jié)點(diǎn)按順序?qū)?yīng)到原始節(jié)點(diǎn)，得到的原始節(jié)點(diǎn)順序就是無人機(jī)的實(shí)際飛行路徑。

下面對算例進(jìn)行運(yùn)算。首先給予雙目標(biāo)相等的權(quán)重，令w1=w2=0.5，得到無人機(jī)在時空路網(wǎng)中的具體運(yùn)行軌跡，如表1所示。

表1 時空路網(wǎng)運(yùn)行軌跡

由表1可知，2架無人機(jī)分別在t=0時刻從節(jié)點(diǎn)3和節(jié)點(diǎn)8起飛，并分別在14min和23min回到基站。無人機(jī)的總飛行時間為37min，最大單機(jī)飛行時間為23min。兩架無人機(jī)的單機(jī)飛行時間差距懸殊，沒有做到合理分配續(xù)航時間。因此需要進(jìn)一步增大w2，要求整個交通信息收集任務(wù)在最短的時間內(nèi)完成。依次改變w1和w2的值，得到2架無人機(jī)的飛行時間以及目標(biāo)函數(shù)值的大小，如表2所示。其中UAV-1和UAV-2分別表示兩架無人機(jī)的飛行時間，g表示雙目標(biāo)歸一化后考慮權(quán)重系數(shù)的和。

表2 情景分析

分析表2中的結(jié)果，當(dāng)w1≤0.4時，2架無人機(jī)的總飛行時間變?yōu)?1min，最大單機(jī)飛行時間為21min，即整個飛行任務(wù)最短在21min內(nèi)完成。對比表1，無人機(jī)的總飛行時間增加了9.76%，最大單機(jī)飛行時間減少了8.70%。隨著權(quán)重w1的增加，第一目標(biāo)所占的比重增大，無人機(jī)的總飛行時間逐漸縮短，最大單機(jī)飛行時間逐漸延長。當(dāng)w1所占比重足夠大時，系統(tǒng)僅使用1架無人機(jī)進(jìn)行巡視，對應(yīng)的總飛行時間最短，單架無人機(jī)的飛行時間為34min。如果僅考慮總目標(biāo)函數(shù)最小，使用1架無人機(jī)的巡視效果最優(yōu)，對應(yīng)的飛行路徑為3-1-2-5-4-6-7-4-6-7-4-5-2-1-3。通過Lingo軟件，該算例的運(yùn)算時間小于10s。

3.2 算例驗(yàn)證

為進(jìn)一步驗(yàn)證本模型和方法的有效性，這里選擇Sioux-Fall城市路網(wǎng)進(jìn)行驗(yàn)證，如圖3所示。Sioux-Fall城市路網(wǎng)被廣泛應(yīng)用于交通領(lǐng)域，該路網(wǎng)由24個節(jié)點(diǎn)和76條路段組成，基站位于節(jié)點(diǎn)4和節(jié)點(diǎn)19。有2架無人機(jī)分別從基站起飛，巡視結(jié)束后回到起飛位置，其中（4,5），（7,8），（9,14），（10,11），（11,16），（19,20）需要巡視2次，且巡視時間間隔不低于6 min。

給予雙目標(biāo)相等的權(quán)重，重復(fù)上述方法，在Lingo中建立時空路網(wǎng)，得到無人機(jī)的飛行路徑（UAV-1：4-5-7-8-9-14-13-15-18-17-20-19-16-11-10-3-4；UAV-2：19-16-11-10-3-4-5-7-8-9-14-13-12-17-20-19）。2架無人機(jī)在t=0時刻分別從節(jié)點(diǎn)4和節(jié)點(diǎn)19起飛，在t=28時刻同時回到起飛位置，整個任務(wù)在28min內(nèi)完成。通過Lin?go軟件，該算例的運(yùn)算時間不超過30min。

圖3 Sioux-Fall城市路網(wǎng)

Lingo軟件的運(yùn)算時間直接與時空網(wǎng)絡(luò)的規(guī)模相關(guān)，它求解線性規(guī)劃問題采用的是一種精確搜索方法，因此計算時間會隨著時空網(wǎng)絡(luò)規(guī)模的增大而呈指數(shù)增加。對于由24個節(jié)點(diǎn)、76條路段組成的Sioux-Fall城市路網(wǎng)，依然能夠在30min內(nèi)得到最優(yōu)解，因此本文提出的模型和方法可以解決無人機(jī)在大規(guī)模路網(wǎng)的路徑規(guī)劃問題。

4 結(jié)語

針對部分路段由于固定型交通信息檢測器布設(shè)不足或因后期損毀導(dǎo)致無法獲取有效交通信息的問題，提出使用無人機(jī)對該路段進(jìn)行巡視以完善交通信息的方法。為保證收集信息的準(zhǔn)確性，要求無人機(jī)多次巡視該路段，并且一段時間內(nèi)至多巡視一次。由于時空網(wǎng)絡(luò)的時間拓?fù)涮匦阅軌蜉^好地表達(dá)巡視次數(shù)和時間間隔約束問題，本文以時空網(wǎng)絡(luò)作為研究框架，建立了以總飛行時間最短和最大單機(jī)飛行時間最短為目標(biāo)的多目標(biāo)模型。算例分析表明，本文所建模型能夠求出最佳的無人機(jī)數(shù)量和相應(yīng)的巡視路徑，證實(shí)了模型的有效性。不過，本文假設(shè)無人機(jī)飛行速度固定，沒有考慮無人機(jī)轉(zhuǎn)彎時的加速度變化和時間消耗，接下來將進(jìn)一步研究考慮航跡的UAV路徑規(guī)劃問題。