多無人機高速公路巡邏任務規(guī)劃方法

項 芮，朱默寧,3*，徐 麗

(1.合肥工業(yè)大學 管理學院，安徽 合肥 230009；2.安徽有云智能科技有限公司，安徽 合肥 230088；3.智能互聯系統安徽省實驗室，安徽 合肥 230009)

0 引言

近年來，全國高速公路的通車里程迅速增長，導致交通管理短缺與人力需求增長的矛盾日益凸顯[1-2]。目前，交通主管部門通常采用常規(guī)人工巡邏和固定攝像頭等方式獲取高速公路的實時信息。然而，現有的高速公路巡邏方式存在著里程長、盲區(qū)多、效率低的缺點，比如固定攝像頭無法實現全路段覆蓋，常規(guī)的人工巡邏需要占用本已十分有限的道路資源，且難以快速到達事故現場并獲取實時的事故信息。一旦高速公路上發(fā)生交通事故等緊急事件，易導致長時間堵車，交警難以快速到達現場進行指揮，若處置不當很容易引發(fā)二次事故[3]。無法及時到達現場進行路段指揮工作給應急管理工作帶來了極大的困難。因此，如何滿足當前日漸增長的高速公路交通管理需求是高速公路巡邏的一大難題。

無人機是一種環(huán)境適應性和可擴展性較強的傳感平臺[4]，具有遠程自主飛行、道路抓拍、定點懸停和實時語音通信等功能，被廣泛應用于交通巡邏領域[5]。相較于常規(guī)的人工巡邏，使用無人機巡邏高速公路具有以下的明顯優(yōu)勢：不受交通流量影響，不會占用道路資源，且能夠實時回傳道路現場的視頻和圖像,有利于道路管理部門通盤指揮和疏導交通[6]。通過無人機實時傳輸視頻、圖像和語音等信息可以讓交警快速勘察現場情況，提高巡檢過程的安全性。無人機還可攜帶喊話器來指揮交通實現短時間內恢復通車，可以加速現場撤離，降低警力投入。綜上所述，以無人機編隊高速公路巡邏為導向的巡邏模式可以有效提升路況信息服務水平和快速處理高速公路突發(fā)事件。在實際應用中，當面對若干不同類型的巡邏任務時，如何規(guī)劃無人機編隊的巡邏路徑，使得巡邏效益最大化，成為亟待解決的問題之一。

本文面向城市高速公路交通巡邏場景，研究了無人機編隊的任務規(guī)劃問題。城市高速公路的巡邏指揮任務主要包括事故多發(fā)點巡邏、電子眼盲區(qū)巡邏和道路堵塞疏導等，其中一部分任務可以由無人機完成。對無人機進行巡邏任務規(guī)劃的過程可以描述為：先將日常巡邏任務抽象成若干個需要無人機遍歷的點目標，將需要進行交通指揮的任務路段抽象成若干個線目標；然后將這些點目標和線目標分派給不同的無人機，通過優(yōu)化無人機的巡邏路徑，以最小的總成本遍歷所有的任務目標。為了解決本文提出的無人機編隊高速巡邏任務，引入旅行商問題(Travelling Salesman Problem，TSP)模型，將問題抽象為無人機編隊從多個停機坪出發(fā)，完成對指定任務目標的遍歷后返回出發(fā)停機坪的問題。該問題可以看作多站點TSP和固定終點旅行商問題的結合，即多站點固定終點的多旅行商問題(Multi-Depot Fixed Destination Multi Travelling Salesman Problem，MD-FD-MTSP)模型。

TSP已被證明是非確定性多項式難(Non-Deterministic Polynomial Hard，NP-Hard)問題，本文所研究的MD-FD-MTSP是TSP的變體問題，所以也是NP-Hard問題。遺傳算法及其混合算法是解決TSP及其變體問題最先進的啟發(fā)式算法之一，并被廣泛應用于工程實踐中[7]。因此，根據多無人機高速巡邏任務的特點，針對MD-FD-MTSP模型設計了改進的單親遺傳算法(Improved Partheno-Genetic Algorithm，IPGA)，得到每架無人機的可飛路徑，并通過對比實驗展示了算法的性能。

1 相關工作

1.1 無人機道路巡檢

近些年，國內外諸多學者對無人機在交通巡邏領域上的應用進行了深入研究。一些學者[8-9]提出了基于無人機巡檢的城市交通流狀況的評價方法，并分析了無人機數量和城市中汽車數量的變化對于算法求解效率的影響。相關研究[10-11]利用無人機獲取中國主要十字路口的監(jiān)控錄像，基于路網搜索路徑規(guī)劃算法解決無人機自主搜索任務的任務規(guī)劃問題。為了更高效地利用無人機所采集的影像數據，有學者[12-13]對如何基于無人機圖像自動提取高精度的道路信息進行了研究。

1.2 多旅行商問題

多旅行商問題(Multiple Traveling Salesman Problem,MTSP)是TSP的推廣，在TSP的解決方案中使用了1個以上的旅行商[14]。MTSP同樣屬于NP-Hard問題,通常被定義為：給定m位旅行商從n個城市集合中的1個城市出發(fā)，各自訪問其中一定數量的城市后回到出發(fā)城市，且每個城市只需要被訪問一次[15]。目標為找到距離或時間等代價最小的任務分配方案以及訪問次序。

文獻[16]將MTSP分為以下2種類型：開放路徑旅行商問題和封閉路徑旅行商問題。本文研究的問題屬于封閉路徑旅行商問題的一種變體：m架無人機從m個不同停機坪出發(fā)，訪問一定數量的任務目標，使得每個任務目標必須被1架無人機訪問且只能訪問1次，最后返回出發(fā)的停機坪。

1.3 啟發(fā)式求解算法

目前應用于解決MTSP的相關算法主要有精確算法和啟發(fā)式算法。盡管精確算法有著嚴格的數學理論支持，但隨著算例規(guī)模的擴大，精確算法難以高效地求解MTSP。因此學者們逐漸傾向于采用啟發(fā)式算法或元啟發(fā)算法求解MTSP[17]，如粒子群算法[18]、蟻群算法[19]和遺傳算法[20]。Laporte[21]提出了遺傳算法，一些學者[22-24]利用遺傳算法求解了多機協同偵察問題，并將其建模為MTSP。遺傳算法因其良好的全局搜索能力而被廣泛用于解決工程中的優(yōu)化問題。一般的遺傳算法主要通過交叉算子獲得新的個體。然而，2個相同的個體不能通過交叉獲得新的個體導致算法陷入局部最優(yōu)[25]。因此，一般的遺傳算法需要足夠的初始種群多樣性，否則算法會陷入局部最優(yōu)，無法在找到全局最優(yōu)方案之前產生新個體。而大量的初始種群必然會降低算法的計算效率。單親遺傳算法(Partheno-Genetic Algorithm,PGA)是一種沒有交叉操作的特殊遺傳算法[26]。有學者[22]提出了2種PGA，以解決多起點、封閉路徑的MTSP，并將PGA與粒子群優(yōu)化算法和入侵雜草優(yōu)化算法進行了比較，證明了PGA的計算效率更高，且不會破壞父代染色體的基因組合。

2 問題描述

本文所研究的多無人機高速巡邏任務規(guī)劃問題以高速公路為應用背景。無人機的巡邏任務分為2類：一類將任務抽象成點目標，無人機只要飛過任務點上方即視為完成了巡邏任務；另一類將任務抽象為線目標，無人機需攜帶喊話器對高速公路的某一路段進行指揮。假設停機坪的數量不少于無人機的數量，每架無人機選擇1個停機坪出發(fā)，訪問若干任務點或任務路段后返回各自出發(fā)的停機坪。每個任務點或任務路段只需要訪問1次，要求所有無人機的巡邏路徑總長度最短。將多無人機高速巡邏任務規(guī)劃問題建模為MD-FD-MTSP模型，即K架無人機從不同的停機坪出發(fā)，共同完成由Z個點目標和W個線目標組成的任務集合，最后返回各自停機坪。

2.1 無人機

2.2 異構巡邏任務描述

在無人機執(zhí)行高速巡邏任務過程中，由于無人機的續(xù)航能力有限，執(zhí)行完異構巡邏任務的無人機需降落在原停機坪補充電量。考慮到操作的安全性和便捷性，本文規(guī)定每個停機坪至多只能安排1架無人機起飛和降落。

2.3 高速道路路網描述

由于點目標與線目標分布在城市高速公路路網中，且無人機編隊需沿著路網執(zhí)行任務。用連通圖G=(V,E)來表示高速公路路網，其中，點集合V={V0,V1,…,VN}表示道路之間的交叉點，交叉點的數量為N。無人機在飛行過程中需要不斷做出決策，將每次決策的出發(fā)點記作VS={V0,V1,…,VV-1}，將每次決策的目標節(jié)點記作VE={V1,V2,…,VV}，其中V0等價于VV。無人機巡檢的任務路段即為連通圖G的邊集合E={eij=(Vi,Vj)}的子集，每條邊的長度為dij，路網中共有M條邊。

表1列出了本文所用到的相關集合、參數和變量。

2.4 數學模型

針對MD-FD-MTSP，以所有無人機巡邏路徑的總長度最小作為優(yōu)化目標，建立如下數學模型：

(1)

約束條件為：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(1)的目標函數表示多無人機執(zhí)行巡邏任務的總路程長度最小化；式(2)保證路網中所有節(jié)點的流量守恒，即入度等于出度；式(3)和式(4)保證1個停機坪有且僅有1架無人機進行起降；式(5)為無人機的續(xù)航能力約束；式(6)保證每個線目標被且僅被1架無人機訪問1次；式(7)保證每個點目標被且僅被1架無人機訪問1次；式(8)是所有決策變量的取值。

3 改進的單親遺傳算法

IPGA的主要思想是：將待求解問題的解決方案轉換為編碼的形式，首先隨機生成種群規(guī)模大小的個體作為父代，基于適應度函數評估每一個個體的適應度；選擇出適應度較高的一些個體執(zhí)行單親遺傳操作,生成和父代種群數量相同的子代種群；對子代種群進行新一輪的迭代，周而復始,達到預先設定的迭代次數為止[22]。圖1給出了IPGA流程。

圖1 IPGA流程Fig.1 Flow chart of IPGA

IPGA的偽代碼如下：

改進的單親遺傳算法(IPGA)輸入:待求解的MD-FD-MTSP輸出:OptPath,算法求得的任務規(guī)劃方案開始種群初始化(詳見3.3)適應度評價(詳見3.2)While 不滿足算法結束條件 單親遺傳操作(詳見3.4) 種群更新(詳見3.5)EndwhileIPGA所求得的最佳任務分配方案

3.1 染色體編碼方式

本文采用基于巡邏任務序號的整數編碼加設置斷點的方式對染色體進行編碼，即用2個向量表示1條染色體，其中，向量1是所有目標編號的1個隨機排列，向量2是隨機設置的斷點位置。1條染色體代表MTSP的1個可行路徑規(guī)劃方案。現有3架無人機和5個任務點，3條任務路段編碼方式如圖2所示。

圖2 IPGA染色體編碼示意Fig.2 Schematic diagram of IPGA chromosome coding

圖2所示的染色體表示的無人機編隊巡邏路徑方案可描述為：第1架無人機從停機坪出發(fā)，依次巡邏編號為8的點任務和端點為3,4的線任務后返回其出發(fā)的停機坪；第2架無人機從停機坪出發(fā)，依次巡邏編號為1，2的點任務后返回其出發(fā)的停機坪；第3架無人機從停機坪出發(fā)，依次巡邏端點為9,10的線任務,編號為10的點任務，端點為5,6的線任務和編號為7的點任務后返回其出發(fā)的停機坪。圖2所示的染色體編碼的巡邏方案示意圖如圖3所示。

圖3 巡邏方案示意Fig.3 Schematic diagram of patrol scheme

3.2 適應度評價

多無人機高速巡邏任務分配方案的優(yōu)劣可以由適應度值來衡量，方案越優(yōu)則其適應度值越大。所以選擇MD-FD-MTSP的目標函數作為IPGA的適應度函數，所有無人機的路徑長度之和越小，則其適應度值越大。

3.3 種群初始化

種群初始化步驟如下：

① 將異構巡邏任務集合中的編號隨機排列得到一個序列H，其中線任務用線段兩端的端點表示；

② 根據無人機數量K隨機設置K-1個中斷點，從而將序列H分成K段，確定每個無人機應該執(zhí)行的巡邏任務；

③ 根據預設的種群規(guī)模分別重復步驟①～②并存入矩陣，得到初始種群。

3.4 單親遺傳操作

交換算子：隨機選取3個基因位s，t和p，將s和t基因位上的編號進行交換，然后將交換后的s和t之間的基因片段插入到基因位p的前面。具體過程如圖4所示。

圖4 交換算子示意Fig.4 Schematic diagram of SwapInsert operator

反轉算子：隨機選取3個基因位s，t和p，將s和t基因位之間的目標編號進行反轉，然后將反轉后的s和t之間的基因片段插入到基因位p的前面。具體過程如圖5所示。

圖5 反轉算子示意Fig.5 Schematic diagram of FlipInsert operator

左旋算子：隨機選取3個基因位s，t和p，將s和t基因位之間的目標編號全部向左移動1位，最前面一位的目標編號移動到最后面一位，然后將左旋后的s和t之間的基因片段插入到基因位p的前面。具體過程如圖6所示。

圖6 左旋算子示意Fig.6 Schematic diagram of LslideInsert operator

右旋算子：隨機選取3個基因位s，t和p，將s和t基因位之間的目標編號全部向右移動1位，最后面一位的目標編號移動到最前面一位，然后將右旋后的s和t之間的基因片段插入到基因位p的前面。具體過程如圖7所示。

3.5 更新操作

為了避免在迭代后期陷入局部最優(yōu)，需要將子代種群中一定比例的個體替換為父代種群中的精英個體。所需替代的染色體數量Nr由種群規(guī)模Np和預設的代溝Gap共同決定，計算公式為：Nr=Np*(1-Gap)，比如Gap取值為0.8。具體操作如下：將父代種群中的個體按照適應度值大小排序，選擇排名前20%的父代染色體替換子代種群適應度值排名后20%的染色體，得到的新種群將作為下一輪迭代的父代種群。

4 實驗與分析

算法編碼采用Python語言，實驗均在Inter(R)Core(TM)i5-7200U CPU@2.50 GHz 2.71 GHz、內存8 GB的x64 Windows10臺式計算機上進行。為了展示IPGA的性能，本文設計了2組數值實驗。在第1組數值實驗中，使用IPGA對文獻[27]的TSP基準實例進行求解并對比，以驗證算法的正確性。在第2組數值實驗中，通過改造文獻[27]中的基準實例生成了12組測試實例，然后使用IPGA算法進行求解，得到每架無人機的路徑規(guī)劃方案并進行了相關分析。

4.1 數值實驗1

4.1.1 實驗數據

在MD-FD-TSP中，若假設無人機數量為1，且不考慮無人機續(xù)航能力約束時，可以轉換為TSP。“Sioux Falls”路網包含24個節(jié)點、38條雙向路段，如圖8所示，每個圓圈中的序號為路網交叉點的編號，每條邊上的數值為邊的長度。

圖8 Sioux Falls路網示意Fig.8 Schematic diagram of Sioux Falls network

本文基于文獻[27]的TSP基準實例進行數值實驗，其中點任務和線任務的具體編號如表2所示。

表2 TSP基準實例Tab.2 Benchmark example of TSP

4.1.2 數值實驗結果與分析

為了驗證本文所提出模型和算法的正確性，基于表2中的9組TSP基準實例，使用IPGA進行求解，每個實例在同一實驗條件下運行5次，并將5次中的最優(yōu)方案記錄在表3中，其中，第1列是實例的編號，第2列記錄了文獻[27]所求得的最優(yōu)解路徑長度，使用IPGA求得的路徑方案及其對應的無人機巡檢路徑和路徑長度記錄在第3列。為了更直觀地展示實驗結果，將T22-1實例的最優(yōu)路徑用圖9進行展示。

表3 基于TSP標準實例數據集的對比實驗結果Tab.3 Comparative experimental results of TSP benchmark data set

圖9 T22-1實例的任務規(guī)劃方案示意Fig.9 Path planning result of T22-1

圖9所展示路徑規(guī)劃方案可以描述為：無人機從藍色圓圈標注的0號節(jié)點處出發(fā)，沿著綠色箭頭方向依次經過路網節(jié)點2和3，接著開始執(zhí)行端點標號為(3，4)的線任務；繼而經過路網節(jié)點8，9和14，開始依次執(zhí)行以紅色圓圈標注的點任務21和20。完成對點任務20的巡邏后，無人機開始沿著箭頭方向返回，到達9號節(jié)點后，無人機將會向右飛行以執(zhí)行端點標號為(15，7)的線任務。至此，無人機已完成對所有任務的巡邏，并沿著箭頭方向返回藍色圓圈標注的停機坪。

從表3可以看出，IPGA求解方案的總路徑長與文獻[27]所求解的最佳方案的總路徑長度一致，說明IPGA可以正確地求解基于點任務和線任務混合的TSP。

4.2 數值實驗2

4.2.1 實驗數據

由于本文所提出的多無人機高速巡邏路徑規(guī)劃問題的特征與文獻[27]中的基準實例有一定的差異，即多無人機以總飛行路程最短為目標，從固定位置出發(fā)且每架停機坪限停1架無人機，故本文根據高速公路巡邏任務路段問題的特征構造了以下數據集。假設同1架無人機2個方向的旅行路程相等。表4給出了12組異構巡邏任務設置情況的數據集，每組數據集有不同數量以及位置的線任務和點任務。通過計算，對于這12組異構巡邏任務，表5記錄了IPGA求解不同實例數據集的任務規(guī)劃方案。

表4 異構巡邏任務測試集Tab.4 Test set of heterogeneous patrol task

4.2.2 數值實驗結果與分析

使用IPGA對表4中12組實例進行求解，每個實例在同一實驗條件下運行5次，將5次中求得的最優(yōu)方案及其對應的路徑長度記錄在表5中。為了更直觀地展示實驗結果，將T1-1實例的最優(yōu)路徑用圖10進行展示。

表5 12組數據集求解結果Tab.5 Solution results of 12 groups of data set

圖10 T1-1實例的任務規(guī)劃方案示意Fig.10 Path planning result of T1-1

圖10所示的T1-1實例的路徑規(guī)劃方案可以描述為：第1架無人機從標號為0的停機坪出發(fā)，沿著綠色箭頭方向依次執(zhí)行編號為2和3的點任務。完成對端點為(10，11)的線任務的巡邏后，沿著綠色箭頭方向返回編號為0的停機坪。在第1架無人機執(zhí)行任務的同時，第2架無人機從編號為1的停機坪出發(fā)，首先執(zhí)行編號為5的點任務，經過路網節(jié)點7后，依次執(zhí)行編號為15和17的點任務。完成對端點為(6，7)的線任務巡邏后沿著紫色箭頭方向返回編號為1的停機坪。

這12組實例分別改變了無人機的位置、數量和點線任務的位置和數量。IPGA在實驗過程中的求解速度較快。結合表5和圖10所給出的路徑規(guī)劃結果可知，求解多無人機任務規(guī)劃方案是合理的，而且當巡邏任務不均勻地聚集在路網中時，為保證總路徑長度最短，更容易出現無人機工作強度不均衡的問題，如T1-3和T2-3。因此，在實際應用中可以適當拉開停機坪之間的距離，從而使得停機坪盡量均勻地分布在任務比較聚集的地方，以便提升任務完成效率。

5 結束語

本文研究了多無人機執(zhí)行高速公路巡邏任務的規(guī)劃方法，構建了一種基于多旅行商問題的數學模型，并設計了一種IPGA。通過基于Sioux Falls路網的TSP實例，驗證了IPGA的求解能力。在后續(xù)研究中可以將無人機的異構性引入模型中，比如續(xù)航能力和飛行速度不同的無人機協同執(zhí)行異構巡邏任務，并進一步分析不同類型無人機適合的場景。