曼哈頓無人飛機(jī)交通監(jiān)控部署

1、曼哈頓無人飛機(jī)交通監(jiān)控部署摘要本文討論分析了曼哈頓城市MAV交通監(jiān)控部署問題，分別在四種不同的情況下求解出了最優(yōu)巡航方案。 在Task1中，首先選取區(qū)域交通路口為節(jié)點，給出MAV的監(jiān)控路段和節(jié)點選擇方法; 然后討論在無續(xù)航里程約束條件下，將MAV監(jiān)控問題轉(zhuǎn)化為TSP問題，并運用模擬退火算法予以求解; 而在有續(xù)航里程約束條件下，運用 Kmeans聚類方法，將監(jiān)控區(qū)域劃分成若干子區(qū)，進(jìn)而將該問題轉(zhuǎn)化為無續(xù)航里程約束的MAV監(jiān)控部署問題，最后對上城區(qū)的監(jiān)控進(jìn)行實證分析，給出了最優(yōu)部署方案。 在Task2中，在Task 1的基礎(chǔ)上求解在30%的MAV無法使用的情況下如何實現(xiàn)巡航監(jiān)控。首先將正常監(jiān)控區(qū)域

2、簡化為其質(zhì)心，比較無法正常巡航區(qū)域內(nèi)的節(jié)點與各個質(zhì)心的距離，對這些節(jié)點進(jìn)行重新分配；然后在重新劃分的區(qū)域內(nèi)仍舊將問題轉(zhuǎn)化為TSP問題；最后運用Task1中的模型進(jìn)行求解。 在Task3中，首先根據(jù)與主干道相交道路的數(shù)量確定其權(quán)值；然后建立加權(quán)歐氏距離的K-means聚類模型進(jìn)行聚類，對區(qū)域內(nèi)的交通路口進(jìn)行劃分；最后在每一個監(jiān)控子區(qū)內(nèi)，又是一個TSP問題，同樣用模擬退火算法可以求解最佳的巡航路徑。在Task4中，根據(jù)題目要求參與MAV巡航部署的和沒有參與的人都不能確切知道MAV的巡航方案，即MAV的巡航方案具有一定的動態(tài)性（隨機(jī)性）。本文首先確定巡航應(yīng)當(dāng)滿足的條件以及方案評價體系；然后通過隨機(jī)貪

3、心算法求解足夠多的可行靜態(tài)解，最后引入時間切片疊加的思維，在靜態(tài)解的基礎(chǔ)上應(yīng)用深度優(yōu)先搜索算法，將求解動態(tài)巡航問題轉(zhuǎn)化為在有向連通圖中尋找使目標(biāo)函數(shù)達(dá)到最大的約束環(huán)路問題，最終求得動態(tài)MAV巡航方案。關(guān)鍵詞：MAV巡航 TSP問題 時間切片 加權(quán)K-means聚類1、 問題重述2、 模型假設(shè)1. 假設(shè)MAV的巡航速度100Km/h；2. 假設(shè)MAV可以急轉(zhuǎn)彎；3、 模型建立與求解Task 1 基于旅行商模型的MAV監(jiān)控部署1、 問題分析MAV需要對整個曼哈頓的交通進(jìn)行監(jiān)控，主要是對區(qū)域的路段進(jìn)行監(jiān)控，尤其是十字路口。根據(jù)監(jiān)控歷程是否超出飛機(jī)飛行距離，提出無人飛機(jī)在有無續(xù)航里程約束條件下的交通監(jiān)

4、控部署方法。本文選取區(qū)域十字路口為節(jié)點，給出MAV的監(jiān)控路段和節(jié)點的選擇方法; 在無續(xù)航里程約束條件下，將無人飛機(jī)的交通監(jiān)控問題轉(zhuǎn)化為旅行商問題，并運用模擬退火算法予以求解; 在有續(xù)航里程約束條件下，運用 Kmeans聚類方法，將無人飛機(jī)的監(jiān)控區(qū)域劃分成若干子監(jiān)控區(qū)，從而將該問題轉(zhuǎn)化為無續(xù)航里程約束的無人飛機(jī)交通監(jiān)控部署問題。2、 模型建立2.1 監(jiān)控節(jié)點和監(jiān)控路段的選擇根據(jù)道路的交通安全水平評價，本文將MAV的交通監(jiān)控對象分為節(jié)點和路段二類。目前，國內(nèi)外對道路的交通安全狀況進(jìn)行了深入研究，得到了道路交通事故發(fā)生分布的一般特征。發(fā)現(xiàn)交通事故多發(fā)生于交通路口等地方。因此，本文選擇交通路口作為監(jiān)控

5、節(jié)點。監(jiān)控路段的選擇，區(qū)域內(nèi)的所有交通道路均為監(jiān)控路段，路段長度的計算采用定長法，即不考慮各個道路的交通量、限速、道路質(zhì)量，僅考慮道路的實際長度。2.2無里程約束的無人飛機(jī)路線規(guī)劃當(dāng)無人飛機(jī)的飛行距離很長時可不考慮其飛行里程的約束，在確定其監(jiān)控對象后，規(guī)劃其飛行路線: 無人飛機(jī)從基地出發(fā)，遍歷這些節(jié)點、路段，然后再飛回基地，在此過程中，無人飛機(jī)將實時監(jiān)控圖像傳回交通監(jiān)控中心。該問題類似 于旅行商問題，即無人飛機(jī)從基地出發(fā)，遍歷每個節(jié)點、路段，且只經(jīng)過一次，路徑的選擇目標(biāo)是要求無人飛機(jī)的巡航路徑最短。本文將路段抽象成為具有一定里程的節(jié)點，進(jìn)行數(shù)學(xué)建模，如圖1所示。監(jiān)控路段 監(jiān)控節(jié)點 MAV巡航路

6、徑圖1 監(jiān)控路段抽象為節(jié)點示意圖 假設(shè)監(jiān)控網(wǎng)絡(luò)中有個交通監(jiān)控對象，是第個和第個監(jiān)控對象之間的距離，無人飛機(jī)的巡航路線規(guī)劃模型為:其中： 目標(biāo)函數(shù)是使MAV的總巡航距離最短，公式(1)保證無人飛機(jī)僅到達(dá)監(jiān)控對象一次; 公式（2）保證無人飛機(jī)僅離開監(jiān)控對象一次。無里程約束的無人飛機(jī)路線規(guī)劃問題類似于旅行商問題，該問題屬于NP完全問題。2.3 有里程約束的監(jiān)控小區(qū)劃分當(dāng)無人飛機(jī)的飛行距離有限且監(jiān)控范圍較大時，所需的無人飛機(jī)巡航里程可能超過其最大飛行里程，且監(jiān)控時間較長，此時需要考慮無人飛機(jī)監(jiān)控小區(qū)的劃分，配置多架無人飛機(jī)進(jìn)行交通監(jiān)控。通過監(jiān)控小區(qū)的劃分，一方面可滿足無人飛機(jī)的最大飛行里程要求，另一方

7、面可縮小單架次無人飛機(jī)的監(jiān)控范圍，提高交通監(jiān)控的響應(yīng)速度，從而將有里程約束的問題轉(zhuǎn)換成為無里程約束問題。無人飛機(jī)監(jiān)控小區(qū)劃分的方法為: 根據(jù)無人飛機(jī)監(jiān)控點、路段的空間分布，對監(jiān)控對象進(jìn)行聚類，實現(xiàn)監(jiān)控小區(qū)劃分。在監(jiān)控小區(qū)劃分的過程中，不斷增加監(jiān)控小區(qū)數(shù)量，保證每一監(jiān)控小區(qū)有一架無人飛機(jī)進(jìn)行交通監(jiān)控.設(shè)有監(jiān)控對象其中每個監(jiān)控對象有2個空間坐標(biāo)，即:；引入K means方法將監(jiān)控對象劃入若干小區(qū)內(nèi)?？紤]到曼哈頓地區(qū)道路交通監(jiān)控對象在空間上的分布特征，以及無人飛機(jī)的最大飛行里程的限制，監(jiān)控小區(qū)數(shù)量的劃分上限設(shè)，其中表示向上取整。2.4部署方案的評價將無人飛機(jī)監(jiān)控區(qū)域劃分成為不同的偵察子區(qū)域，并在每個

8、子區(qū)域部署一架無人飛機(jī)，則不同的子區(qū)域劃分對應(yīng)著不同的無人飛機(jī)偵察代價，因此，本文提出2個指標(biāo)評價無人飛機(jī)的部署效果。（1） 總巡航距離：（2） 監(jiān)控時間標(biāo)準(zhǔn)差：其中；為劃分的子區(qū)域數(shù)量; 為無人飛機(jī)在第個子區(qū)域的巡航距離;為無人飛機(jī)在第個子區(qū)域的巡航時間。指標(biāo)1表示所有的無人飛機(jī)巡航距離之和; 指標(biāo)2表示所有無人飛機(jī)巡航時間的標(biāo)準(zhǔn)差; 這2個指標(biāo)用于衡量部署無人飛機(jī)的成本和使用協(xié)同性。從直觀上講，無人飛機(jī)的數(shù)量越多，則平均監(jiān)控時間變短，交通監(jiān)控的響應(yīng)速度就越快，同時無人飛機(jī)的購置成本也在增加。另一方面，部署多架無人飛機(jī)后，總巡航距離和監(jiān)控時間的協(xié)調(diào)性會發(fā)生動態(tài)的變化，此時需要根據(jù)交通監(jiān)控的需

9、求做出權(quán)衡。3、 模型求解 經(jīng)查閱，整個曼哈頓地區(qū)屬于有續(xù)航差約束的情景，由于總巡航距離較長，監(jiān)控時間將會較長，且超出許多無人飛機(jī)的最大飛行距離，因此可進(jìn)行監(jiān)控小區(qū)的劃分，在此，本文以曼哈頓上城區(qū)進(jìn)行實證分析。 上城區(qū)的交通道路如圖2，其中代表城市的交通道路，代表交通路口。圖2 曼哈頓上城區(qū)城市交通圖結(jié)合該區(qū)域交通道路特征，建立平面直角坐標(biāo)系。讀取各個節(jié)點的坐標(biāo)。運用Kmeans聚類方法將該路網(wǎng)劃分為27 個監(jiān)控小區(qū)。表1給出了劃分結(jié)果。表1 運用Kmeans聚類方法將該路網(wǎng)劃分為27 個監(jiān)控小區(qū)數(shù)目12345678910111213141516171819202122232425262728

10、293031234567 運用Kmeans聚類方法將該路網(wǎng)劃分為27 個監(jiān)控小區(qū)每個小區(qū)配置一架無人飛機(jī)(假設(shè)巡航速度為100 km/h，則最大續(xù)航里程為500 km) ，每個小區(qū)內(nèi)的無人飛機(jī)監(jiān)控問題轉(zhuǎn)化為無續(xù)航里程約束的TSP 問題，并用模擬退火算法求解，不同UAV 監(jiān)控小區(qū)的無人飛機(jī)總巡航距離、監(jiān)控時間對比情況如圖3所示。圖3不同MAV監(jiān)控小區(qū)監(jiān)控時間（單位：h）與總的巡航距離對比圖（單位Km）由圖3可知，隨著無人飛機(jī)監(jiān)控小區(qū)數(shù)量的增多，總巡航距離呈動態(tài)變化，劃分為1個監(jiān)控小區(qū)時總巡航距離最小，為760 km; 劃分為6個監(jiān)控小區(qū)時總巡航距離最大，為881 km。由圖3可知，平均監(jiān)控時間隨

11、著小區(qū)數(shù)量的增加而下降，劃分為2個監(jiān)控小區(qū)時平均監(jiān)控時間為1.8 h，劃分為7 個監(jiān)控小區(qū)時平均監(jiān)控時間為0.3 h，監(jiān)控的響應(yīng)速度大為提高。同時通過計算得到，監(jiān)控時間的標(biāo)準(zhǔn)差隨著小區(qū)數(shù)量的增加而動態(tài)變化，劃分為3個監(jiān)控小區(qū)時標(biāo)準(zhǔn)差最大，為0. 74 h，各小區(qū)的無人飛機(jī)監(jiān)控協(xié)調(diào)最差，劃分為6 個監(jiān)控小區(qū)時標(biāo)準(zhǔn)差最小，為0. 13 h，此時各小區(qū)的無人飛機(jī)監(jiān)控協(xié)調(diào)最好。 綜合以上分析，在曼哈頓上城區(qū)劃分6個監(jiān)控子區(qū)域最為合適，滿足題中所要求城市每個角落保持在15分鐘內(nèi)被監(jiān)控，同時監(jiān)控時間的標(biāo)準(zhǔn)差最小，所有MAV的協(xié)調(diào)性最高。至此，在各個子區(qū)域則轉(zhuǎn)化成為一個TSP（旅行商）問題。在MATLAB

12、中運用模擬退火算法求解無人飛機(jī)最短巡航距離。模擬退火算法的參數(shù)設(shè)置為: 初始溫度為10000 ，冷卻速度為0. 99，最大迭代次數(shù)為10000 次。此時的監(jiān)控小區(qū)劃分及無人飛機(jī)的飛行路徑如圖4所示。當(dāng)需要進(jìn)一步提高無人飛機(jī)的監(jiān)控響應(yīng)速度時，則需要繼續(xù)增加無人飛機(jī)的監(jiān)控小區(qū)并配置更多的無人飛機(jī)。圖4 6 監(jiān)控小區(qū)及無人飛機(jī)飛行路徑 基于此，本文求解出了曼哈頓上城區(qū)飛機(jī)監(jiān)控部署方案，用同樣的方法可以確定其他區(qū)域的MAV部署。其他區(qū)域的監(jiān)控部署見附錄1。Task 2 基于最短距離的節(jié)點劃分模型1、 問題分析在Task 1中將城市交通的有歷程約束的巡航轉(zhuǎn)化為無里程約束巡航，本文繼續(xù)以上城區(qū)進(jìn)行實證分析

13、，求解在30%的MAV無法使用過的情況下如何實現(xiàn)巡航監(jiān)控。將正常監(jiān)控區(qū)域簡化一點，即其質(zhì)心，比較無法正常巡航區(qū)域內(nèi)的交點與各個質(zhì)心的距離，對于某一節(jié)點而言，將其劃入與質(zhì)心的距離最短的質(zhì)心所代表的區(qū)域，對于距離相等的節(jié)點，先將該節(jié)點歸入對應(yīng)的多個區(qū)域，通過計算多個區(qū)域的巡航時間，若存在某一加入該節(jié)點后的某一區(qū)域巡航時間比其他區(qū)域巡航時間段，則該節(jié)點應(yīng)該歸入巡航時間短的區(qū)域。本文以區(qū)域3、區(qū)域4無法正常巡航進(jìn)行實證分析。2、模型建立與求解設(shè)可以正常巡航的的區(qū)域為,將該區(qū)域簡化為質(zhì)點記，記無法正常巡航區(qū)域內(nèi)的各個節(jié)點的坐標(biāo)，。計算得到質(zhì)心、節(jié)點坐標(biāo)如圖5。圖5 正常巡航區(qū)域的質(zhì)心坐標(biāo)與無法正常巡航區(qū)

14、域內(nèi)的節(jié)點坐標(biāo)根據(jù)已知條件，可以計算出這些無法正常巡航區(qū)域內(nèi)的各個節(jié)點與正常巡航區(qū)域中心坐標(biāo)的距離 根據(jù)中計算的各個節(jié)點到質(zhì)心的距離，各個節(jié)點的劃分區(qū)域如表2所示。表2 無法正常巡航區(qū)域內(nèi)的各節(jié)點重新劃分后的所屬區(qū)域情況區(qū)域編號所包含節(jié)點11,12,13,148，9,1018,17,22，15,16,24,23根據(jù)表2中各正常巡航區(qū)域重新劃入的節(jié)點，將問題再次轉(zhuǎn)化為旅行商問題，在各個重新劃分的子區(qū)域內(nèi)運用模擬退火算法求解出MAV的最佳巡航路徑。如圖6所示。圖6 重新規(guī)劃后的監(jiān)控小區(qū)及無人飛機(jī)飛行路徑 最后可以得出當(dāng)區(qū)域3、區(qū)域4無法正常巡航時剩余的MAV巡航范圍及路徑。當(dāng)遇到某一個節(jié)點到多個質(zhì)

15、心的距離相等時，先將該節(jié)點劃分到各個質(zhì)心所代表的區(qū)域，然后用同樣的方法求出解，最后比較巡航時間，將節(jié)點歸入巡航時間最短的質(zhì)心所代表的區(qū)域。 同理，可以用同樣的方法確定曼哈頓其他區(qū)域的交通在緊急狀況下MAV的部署方案。根據(jù)不用的緊急情況確定不同的部署方案，進(jìn)而可以確定在此情況下MAV的巡航監(jiān)控范圍。Task 3 基于交通道路加權(quán)的MAV巡航改進(jìn)模型1、 問題分析盡管所有地區(qū)都是平等的，但是有些地區(qū)更為重要。城市的交通主干道總是和一些較小的道路縱橫交錯，一條主干道與其他道路相交的越多則一定程度上表明該條主干道上的交通量越大，即具有較高密度的亂穿馬路的人，因此這些地區(qū)應(yīng)該加強(qiáng)巡邏，同時對于一些交通量

16、少的交通主干道，則可以適當(dāng)減少巡航監(jiān)控的頻率。由此可以根據(jù)與主干道相交道路的數(shù)量確定其權(quán)值，在確定權(quán)值以后，建立加權(quán)歐幾里得距離K-means聚類模型進(jìn)行聚類對區(qū)域內(nèi)的交通路口進(jìn)行劃分，在每一個監(jiān)控子區(qū)內(nèi)，則又是一個旅行商的問題，同樣用模擬退火算法可以求解最佳的巡航路徑。2、 模型建立于求解2.1 基于加權(quán)的歐氏距離K-means聚類模型交通道路的加權(quán)根據(jù)上文分析，本文將主干道與其相交的道路數(shù)目作為該條道路的權(quán)，如圖7，與主干道相交的道路有，由此確定主干道的權(quán)為7。 表示交通路口，表示主干道圖7 道路的加權(quán)示意圖 以此方法可以得到其他道路的權(quán)值。本文選取上城區(qū)的交通道路進(jìn)行實證分析，以此闡明如

17、何基于交通道路加權(quán)的MAV巡航改進(jìn)模型。圖8給出了曼哈頓上城區(qū)的各條道路的加權(quán)值。圖8 曼哈頓上城區(qū)的各條道路加權(quán)值交通路口的加權(quán)歐幾里得距離在圖論中通常二點之間的距離進(jìn)行比較，一般情況下歐氏距離計算式為：其中的坐標(biāo)。而本題涉及到加權(quán)，即對每個變量賦予權(quán)重，那么加權(quán)的歐幾里得距離為其中是節(jié)點所連接道路的權(quán)。在進(jìn)行聚類時合理地運用加權(quán)歐氏距離，對改進(jìn)聚類結(jié)果能起到較好的效果。 一下是基于加權(quán)歐幾里得距離的K-means聚類算法的一般過程： 算法輸入：聚類個數(shù)，以及個節(jié)點集合； 算法輸出：滿足方差最小的標(biāo)準(zhǔn)的個聚類； 算法步驟：（1） 從個節(jié)點對象中任意選擇個對象作為初始聚類中心；（2） 根據(jù)每個

18、聚類中所有對象的均值（中心對象），計算樣本集中每個對象與這些中心對象的加權(quán)歐幾里得距離，病根據(jù)最小的加權(quán)歐氏距離重新對相應(yīng)對象進(jìn)行劃分；（3） 重新計算每個（有變化）聚類的均值（中心對象）；（4） 循環(huán)執(zhí)行（2），（3），直到每個聚類不再發(fā)生變化為止。 根據(jù)以上對算法的設(shè)計和對曼哈頓城市交通圖的分析，借助MATLAB進(jìn)行計算，最終求的在加權(quán)情況下，上城區(qū)監(jiān)控區(qū)域的劃分。表9給出了輸出的監(jiān)控區(qū)域劃分結(jié)果。表3 基于加權(quán)歐氏距離的K-means節(jié)點聚類劃分?jǐn)?shù)目12345678910111213141516171819202122232425262728293031234562.2 基于TSP的MA

19、V巡航部署模型運用Kmeans聚類方法將該路網(wǎng)劃分為26 個監(jiān)控小區(qū)每個小區(qū)配置一架無人飛機(jī)(假設(shè)巡航速度為100 km/h，則最大續(xù)航里程為500 km) ，每個小區(qū)內(nèi)的無人飛機(jī)監(jiān)控問題轉(zhuǎn)化為無續(xù)航里程約束的TSP 問題，并用模擬退火算法求解，得到在各個子區(qū)的巡航軌跡。在得到各個子區(qū)巡航軌跡只有，根據(jù)中提出的對不同巡航路徑的評價指標(biāo)，即無人飛機(jī)總巡航距離、監(jiān)控時間，對各個不同情況進(jìn)行評價分析，以找出最為合理地子區(qū)劃分。表給出了相關(guān)結(jié)果。表10不同監(jiān)控子區(qū)的的評價分析監(jiān)控子區(qū)數(shù)目23456最大巡航時間1.8h1.6h0.66h0.66h0.31h最小巡航時間1.6h0.66h0.42h0.08

20、h0.07h總巡航距離760Km820Km 820Km800Km860Km監(jiān)控時間標(biāo)準(zhǔn)差0.58h0.74h0.44h0.29h0.15h根據(jù)題目要求，城市的部分地區(qū)有較高密度的亂穿馬路者，這些地區(qū)應(yīng)該在每5分鐘巡航一次，而另一些地區(qū)則只需要每隔20分鐘巡航一次，因此各個監(jiān)控子區(qū)的最大巡航時間應(yīng)該小于20分鐘，最小巡航時間應(yīng)該小于5分鐘，由表3可以看出，符合這一條件至少需要將上城區(qū)劃分為6個子監(jiān)控區(qū)，而且在劃分為6個子區(qū)時所有MAV的總巡航距離最大，這意味著MAV監(jiān)視的范圍就越大，同時6個子區(qū)的監(jiān)控時間標(biāo)準(zhǔn)差最小，也就是說在此情況下，所有MAV的協(xié)調(diào)性最好，綜合分析，將監(jiān)控區(qū)域劃分為6個子區(qū)已

21、經(jīng)符合題目要求，如果再多劃分一個子區(qū)勢必增加一架MAV，繼而增加監(jiān)控成本。圖9給出了，上城區(qū)6個子監(jiān)控區(qū)的劃分以及各個子區(qū)域的MAV巡航軌跡。圖9 6個子監(jiān)控區(qū)的劃分以及各個子區(qū)域的MAV巡航軌跡最后，運用同樣的方法可以將整個曼哈頓進(jìn)行監(jiān)控子區(qū)的劃分，在各個子區(qū)均看做是TSP問題。TASK 4 基于時間切片疊加的MAV動態(tài)部署模型1 問題分析題目要求從MAV的角度考慮，做到對每個人都公平，即參與MAV巡航部署的和沒有參與的人都不能確切知道MAV的巡航方案，這就要求MAV的巡航方案具有一定的隨機(jī)性。使所有人都無法掌握MAV的巡航規(guī)律。該問題可以理解為求解MAV的動態(tài)巡航方案問題。本文通過一些必要

22、簡化首先確定巡航發(fā)難應(yīng)當(dāng)滿足的條件以及方案的評價體系，通過隨機(jī)貪心算法求解足夠多的可行靜態(tài)解，并引入時間片疊加的思維在靜態(tài)解的基礎(chǔ)上應(yīng)用深度優(yōu)先搜索算法，將求解動態(tài)巡航問題轉(zhuǎn)化為在有向連通圖中尋找使目標(biāo)函數(shù)達(dá)到最大的約束環(huán)路問題，最終求得動態(tài)MAV巡航方案。2 模型建立于求解2 模型建立于求解2.1 MAV巡航方案評價體系的建立為了巡航方案的優(yōu)化選擇，本文定義4個評價巡航方案的指標(biāo)，分別為抵達(dá)第個交通路口的平均時間，最大巡航死角時間，巡航合理性，整個巡航方案的巡航總里程。MAV抵達(dá)交通路口的平均時間：假設(shè)在所有交通路口為，現(xiàn)在要求向派遣一架MAV，距離該點最近的MAV設(shè)為，之間的距離為，MAV

23、趕往該節(jié)點的速度為，則平均時間可以表示為；最大巡航死角時間：本文定義某個節(jié)點的巡航死角時間為在巡航過程中沒有處在監(jiān)控范圍內(nèi)的時間之和，則最大巡航死角時間從整體上體現(xiàn)了MAV對城市內(nèi)各條街道的覆蓋情況，為了避免出現(xiàn)巡航死角時間，應(yīng)該是巡航的盡可能地尋遍城市的各個交通路口，以體現(xiàn)巡航的全面性和整體性。巡航合理性：在不同權(quán)重的地區(qū)，MAV的配置應(yīng)該與權(quán)重相適應(yīng)，第個交通路口的權(quán)為，記整個巡航方案中單位時間內(nèi)第個交通路口出現(xiàn)MAV數(shù)量的平均值為故有：則的定義為其中，。 總巡航距離：某一部署方案所有MAV巡航距離的總和。記單個MAV巡航距離為則總巡航里程為：將上述四個指標(biāo)分別用如下方法進(jìn)行標(biāo)準(zhǔn)化：最后將

24、四個指標(biāo)綜合，得到綜合評價指標(biāo)為2.2MAV巡航靜態(tài)方案求解 MAV巡航可以分為靜態(tài)巡航和動態(tài)巡航二種情況，靜態(tài)方案可以理解為MAV在各自的監(jiān)控區(qū)域進(jìn)行監(jiān)控，即可以認(rèn)為負(fù)責(zé)監(jiān)控該區(qū)域的MAV繞著該區(qū)域的質(zhì)心進(jìn)行監(jiān)控，而動態(tài)監(jiān)控是指所有MAV按照一定的計劃在城市內(nèi)動態(tài)的巡航。動態(tài)巡航方案可以看做是由一個時間序列上多個靜態(tài)巡航方案組成的。本文引入時間片段疊加模型來從靜態(tài)方案構(gòu)造動態(tài)方案。模型的主要思想為：求解出一系列的滿足基本條件的靜態(tài)解，將這些靜態(tài)解看做是一個一個的切片，通過構(gòu)建合理地組合模型將這些切片堆砌起來形成最終的動態(tài)解。 首先定義：若在城市交通圖中節(jié)點上空有MAV，則記，否則為0，若MA

25、V可以再要求時間內(nèi)從節(jié)點到節(jié)點則記，否則為0，若點在某一MAV監(jiān)控范圍內(nèi)，則，否則為0.之間的關(guān)系可以表示為：即若巡航方案要求達(dá)到的覆蓋率為，交通路口數(shù)為，則靜態(tài)模型可以表示為：這是一個0-1規(guī)劃問題，可以使用隨機(jī)貪心算法求解。2.3 時間切片疊加算法的MAV動態(tài)巡航求解 事實上，MAV的動態(tài)巡航過程可以看做是連續(xù)時間點上靜態(tài)方案的疊加，即動態(tài)巡航的MAV部署在每一刻都可以看作是一個滿足基本條件的靜態(tài)配置，而動態(tài)巡航過程正是由這些時間切片堆疊起來的，因此，我們引入時間片度疊加的思想，利用大量滿足基本條件的靜態(tài)解為基礎(chǔ)，以評價指標(biāo)函數(shù)為目標(biāo)函數(shù)求動態(tài)部署方案。圖10是該思想的示意圖，每一層代表一

26、個時間點MAV的配置情況。圖10 時間切片疊加算法示意圖在用之前所述的靜態(tài)求解模型生成大量可行解的基礎(chǔ)上，時間切片疊加模型的核心問題是要在備選的靜態(tài)中選擇正確的時間切片并給出正確的時間疊加順序。 首先，對于給定的兩個靜態(tài)解，本文給出一個標(biāo)準(zhǔn)來確定他們之間是否能夠作為相鄰的時間切片，為了描述靜態(tài)解之間的差異程度，本文定義了兩個靜態(tài)解之間的距離，如果兩個靜態(tài)解具有相同的節(jié)點數(shù)和MAV數(shù)，同一個MAV在兩個方案之間會有一定的距離，即定義為所有MAV的距離中的最大值，可以確定出一個閾值，當(dāng)時，認(rèn)為對應(yīng)的兩個方案是可以作為連續(xù)時間片的。在此基礎(chǔ)上，我們可以建立一個加權(quán)的無向連通圖模型來描述動態(tài)巡航方案求

27、解問題如圖11所示。其中每個節(jié)點表示一個由之前模型生成的備選靜態(tài)方案，另一條邊的權(quán)重表示對應(yīng)兩個方案之間的距離，如果能從圖中找到一個有向回路，且回路中每兩個相鄰節(jié)點都滿足時，即找到了一個可行的動態(tài)方案，也就是說，所有可行的方案均可以為該連通圖中的一個“連續(xù)”的回路所表示.例如, 假如為100m，下圖中有4個備選靜態(tài)方案構(gòu)成的連通圖, 則下圖中紅色回路即表示一個動態(tài)解方案, 在該方案中, 所有車輛依次在靜態(tài)方案中的對應(yīng)位置上。圖11 由靜態(tài)方案求解動態(tài)方案示意圖對于可行的動態(tài)方案, 顯然綜合評價指標(biāo)的值越大, 該巡邏方案越優(yōu)秀. 因此我們以綜合評價指標(biāo)為目標(biāo)函數(shù), 根據(jù)以上思想, 時間片疊加算法

28、可以轉(zhuǎn)化為在一個有向圖中尋找一個帶約束回路使綜合評價指標(biāo)函數(shù)達(dá)到最大的組合模型, 描述如下：給定閾值和無向圖，為頂點集,為邊集, 每個頂點用"表示, 含義為一個靜態(tài)解，表示兩個靜態(tài)解之間的距離, 則有，表示從到轉(zhuǎn)移的評價值(此處為兩靜態(tài)解內(nèi)所有MAV移動距離之和).經(jīng)過定性分析可以發(fā)現(xiàn), 若使得評價函數(shù)達(dá)到最大, 則在求解過程中需要滿足方案中所有MAV移動距離之和盡可能大. 則間題可以轉(zhuǎn)化為: 求解中較大回路，其中，且最大化。綜合上述分析，求求解動態(tài)解過程已經(jīng)轉(zhuǎn)化為無向圖求最大(較大) 環(huán)的問題.廣泛使用的圖的深度優(yōu)先遍歷即可在很短的時間內(nèi)求得間題的解,這里我們采用之前部分提出的綜合

29、評價指標(biāo)作為目標(biāo)函數(shù).該算法思想描述如下: 假設(shè)給定圖的初態(tài)是所有頂點均未曾訪問過. 在中任選一頂點為初始出發(fā)點(源點), 則深度優(yōu)先遍歷可定義如下:首先訪問出發(fā)點,并將其標(biāo)記為已訪問過;然后依次從出發(fā)搜索的每個鄰接點。若未曾訪問過, 則以為新的出發(fā)點繼續(xù)進(jìn)行深度優(yōu)先遍歷, 直至圖中所有和源點有路徑相通的頂點(亦稱為從源點可達(dá)的頂點) 均已被訪問為止;若曾被訪問過, 則找到一個環(huán), 這個環(huán)由和在遍歷樹中的公共祖先出發(fā)分別到和路徑上所有的邊以及邊組成.若此時圖中仍有未訪問的頂點, 則另選一個尚未訪問的頂點作為新的源點重復(fù)上述過程, 直至圖中所有頂點均已被訪問為止。 2.4 模型檢驗與評價本文繼續(xù)

30、選取曼哈頓上城區(qū)的交通圖進(jìn)行實證分析。設(shè)方案滿足的設(shè)方案需滿足的條件為在任一時刻, 地圖上90%的區(qū)域必須分別在最近的MAV控制區(qū)內(nèi),控制區(qū)的范圍為附近MAV15分鐘內(nèi)能夠到達(dá). 我們使用時間片疊加算法求出了巡邏方案,結(jié)果顯示, 該地區(qū)巡邏需要5架MAV。 同理，運用時間切片疊加法可以求解出曼哈頓其他地區(qū)的MAV動態(tài)部署方案。4、 模型優(yōu)缺點分析在Task1中，本文選取區(qū)域十字路口為節(jié)點，給出MAV的監(jiān)控路段和節(jié)點的選擇方法; 在無續(xù)航里程約束條件下，將無人飛機(jī)的交通監(jiān)控問題轉(zhuǎn)化為旅行商問題，并運用模擬退火算法予以求解; 在有續(xù)航里程約束條件下，運用 Kmeans聚類方法，將無人飛機(jī)的監(jiān)控區(qū)域

31、劃分成若干子監(jiān)控區(qū)，從而將該問題轉(zhuǎn)化為無續(xù)航里程約束的無人飛機(jī)交通監(jiān)控部署問題。但是本文僅實現(xiàn)了對各個交通路口進(jìn)行監(jiān)控，而對交通道路的監(jiān)控有待進(jìn)一步完善。在Task2中，本文基于Task 1中將城市交通的有歷程約束的巡航轉(zhuǎn)化為無里程約束巡航的方法，繼續(xù)以上城區(qū)進(jìn)行實證分析，求解在30%的MAV無法使用過的情況下如何實現(xiàn)巡航監(jiān)控。將正常監(jiān)控區(qū)域簡化一點，即其質(zhì)心，比較無法正常巡航區(qū)域內(nèi)的交點與各個質(zhì)心的距離，對于某一節(jié)點而言，將其劃入與質(zhì)心的距離最短的質(zhì)心所代表的區(qū)域，對于距離相等的節(jié)點，先將該節(jié)點歸入對應(yīng)的多個區(qū)域，通過計算多個區(qū)域的巡航時間，若存在某一加入該節(jié)點后的某一區(qū)域巡航時間比其他區(qū)域巡航時間段，則該節(jié)點應(yīng)該歸入巡航時間短的區(qū)域。模型缺點在于本文將所有正常巡航的區(qū)域簡化為質(zhì)心，從而導(dǎo)致模型結(jié)果誤差較大；在轉(zhuǎn)化為TSP問題求解時認(rèn)為每個節(jié)點都是等權(quán)的，存在一定的不合理性。在Task3中，根據(jù)與主干道相交道路的數(shù)量確定其權(quán)值，在確定權(quán)值以后，建立加權(quán)歐幾里得距離K-means聚類模型進(jìn)行聚類，對區(qū)域內(nèi)的交通路口進(jìn)行劃分，在每一個監(jiān)控子區(qū)內(nèi)，則又是一個旅行商的問題，同樣用模擬退火算法可以求解最佳的巡航路徑。但是同樣僅實現(xiàn)了對各個交通路