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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、四個(gè)指標(biāo)綜合，得到綜合評(píng)價(jià)指標(biāo)為2.2MAV巡航靜態(tài)方案求解 MAV巡航可以分為靜態(tài)巡航和動(dòng)態(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)控，而動(dòng)態(tài)監(jiān)控是指所有MAV按照一定的計(jì)劃在城市內(nèi)動(dòng)態(tài)的巡航。動(dòng)態(tài)巡航方案可以看做是由一個(gè)時(shí)間序列上多個(gè)靜態(tài)巡航方案組成的。本文引入時(shí)間片段疊加模型來(lái)從靜態(tài)方案構(gòu)造動(dòng)態(tài)方案。模型的主要思想為：求解出一系列的滿(mǎn)足基本條件的靜態(tài)解，將這些靜態(tài)解看做是一個(gè)一個(gè)的切片，通過(guò)構(gòu)建合理地組合模型將這些切片堆砌起來(lái)形成最終的動(dòng)態(tài)解。 首先定義：若在城市交通圖中節(jié)點(diǎn)上空有MAV，則記，否則為0，若MA

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

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

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

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

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

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

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