多無人機協同搜索區域分割與覆蓋

于駟男，周銳*，夏潔，車軍

(1.北京航空航天大學 飛行器控制一體化技術重點實驗室，北京100191;2.中航工業 西安飛行自動控制研究所，西安710065)

多機協同搜索是無人機協同的重要任務之一，覆蓋搜索要求無人機在一定的約束條件下能夠將待搜索區域無遺漏地遍歷搜索.

目前，國內外對于單無人機覆蓋搜索有較多研究，常見的搜索策略有隨機搜索、平行搜索、網格搜索等［1］，文獻［2-3］都對單機覆蓋的搜索策略和方向進行了闡述，文獻［4］應用A*算法對無人機的搜索偵查路徑進行了規劃.但是單機受傳感器探測范圍、飛行時間、燃油量等限制，在許多情況下難以實現有效搜索，而多無人機協同搜索就可以滿足更多的搜索任務需求.多機協同搜索的本質也是一種路徑規劃問題，其重點在數學建模、環境表示和規劃算法［5］.針對這3點展開的研究是非常豐富的.文獻［6］使用高斯混合模型解決無人機啟發式覆蓋搜索問題;文獻［7］仿照生物信息素設計了基于數字信息素的搜索方法;文獻［8］提出了道路網絡中多機搜索策略及實時路徑規劃方案;文獻［9］應用分層模糊推理評估無人機性能、分配任務;文獻［10］提出了對運動目標適用的編隊覆蓋搜索方法.這些方法都較為復雜，并會產生較多的重復搜索.多機搜索與單機搜索的一個差異在于多機之間需要進行通信，文獻［11］探討了信息融合與通信延時對多機協同搜索的影響，這也是近幾年研究的熱點.

將多無人機搜索區域進行分割后，每個子區域內只有一架無人機，問題就簡化為子區域內的單機覆蓋搜索.在無人機搜索領域，如文獻［12-13］中所述應用Voronoi圖對搜索區域進行分割的方法非常普遍，但這種分割非常復雜，并且帶有不確定性，對無人機的自主性要求也較高.

本文詳細分析了無人機覆蓋搜索路徑，借鑒并完善文獻［14］的思路對凸多邊形搜索區域進行分割，根據無人機的特點評估分割結果，并仿真驗證了方法的實用性.

1 搜索策略的確定

無人機搜索傳感器探測區域如圖1所示.不考慮無人機姿態角變化，傳感器高度h處的探測范圍是一半徑為R=h·tanθ的圓［4］.

圖1 傳感器探測范圍示意圖［4］Fig.1 Detection range of sensor［4］

覆蓋搜索最常用的策略之一是平行搜索，因無人機的搜索軌跡呈平行線而得名［15］.與機器人覆蓋搜索不同，無人機存在最小轉彎半徑約束，需要在待搜索區域外部進行轉彎飛行.這一段飛行相對搜索區域是沒用的，如能減少搜索轉彎次數，就可減少飛行路程、搜索時間和油耗.如圖2所示，若按左圖搜索，總路程為27.708 0單位長度，而按右圖搜索，總路程只有21.2832單位長度.所以對某覆蓋搜索區域，要確定一個搜索方向，使得沿此方向搜索的轉彎次數盡量少.

圖2 搜索方向對總路程的影響Fig.2 Effect of search direction on search distance

由于無人機的探測范圍半徑R在飛行高度和探測器角度恒定時為定值，若搜索區域的寬度是L，轉彎次數的計算方法是

由此可見，計算出搜索區域的最小寬度Lmin，即可保證搜索過程中擁有最少轉彎次數.

這里引用文獻［16］對最小寬度Lmin的定義:在平面上做兩條相距足夠遠的平行線，當平行線逐漸向其中心靠攏與凸多邊形相交時即刻停止，兩平行線之間的距離就定義為凸多邊形的寬度.所有跨度中的最小值稱為凸多邊形的最小寬度.

如圖3所示，Lmin即為多邊形ABCDE的最小寬度，其對應頂點為A，對應邊為CD.

圖3 多邊形的最小寬度Fig.3 The minimal width of polygon

2 平行搜索路徑分析

2.1 搜索起始點的選取

為了簡化問題，可先將搜索區域旋轉至一個便于分析搜索路徑的方向.設多邊形頂點序列為V，可取最小寬度對應的邊ViVi+1為x軸，該邊一端點Vi或Vi+1為原點.原點并不一定是搜索起始點.如圖4所示，細實線表示搜索邊界，粗實線表示平行航路以及在搜索區域外部的延長線，虛線表示無人機的傳感器探測邊界以及在搜索區域外部的延長線.若選擇搜索區域頂點，即起始點1作為搜索起始點，則會出現遺漏區域，若選擇圖起始點2作為搜索起始點就可以避免遺漏.

所以搜索起始點的選取方法為:在第1條探測邊界與搜索邊界交點和搜索邊界頂點中，選擇橫坐標較小的點.

圖4 起始點的選取Fig.4 Selection of the beginning point

2.2 轉彎關鍵點的確定

先假設最小轉彎半徑r與探測范圍半徑R相等.如圖5所示，搜索邊界左側為搜索區域內部.稱開始調頭的點A為“調頭點”，調頭結束的點B為“結束點”.

觀察圖6所示的情況，當搜索邊界斜率較大時，若所有的調頭點和結束點都處在邊界上，就可能出現遺漏的情況.為了防止遺漏區域的產生，調頭點與結束點不能簡單地在搜索邊界上選取.

圖5 調頭點與結束點Fig.5 Turn start point and turn end point

圖6 遺漏區域的產生Fig.6 Omission area

首先定義相對方向相同和相對方向相反:無人機在掉頭點的行進方向(沿x軸正向取“+”，負向取“－”)與其所處搜索邊界的斜率符號相同，則稱相對方向相同，否則稱相對方向相反.

如圖7所示，根據搜索方向的不同分為4種情況(Ⅰ～Ⅳ)進行討論.情況Ⅱ和Ⅲ中相對方向相同，調頭點在搜索邊界上，結束點的橫坐標應等于后一條探測邊界(虛線)與搜索邊界交點的橫坐標(豎直實線所示).情況Ⅰ和Ⅳ中相對方向相反，結束點在搜索邊界上，調頭點的橫坐標應等于前一條探測邊界與搜索邊界交點的橫坐標.

所以轉彎關鍵點的確定方法為:當飛行方向為x軸正(負)方向時，搜索邊界與當前直線航路的交點、與當前探測上邊界的交點、與當前下邊界的交點，這3個點的橫坐標最大(小)值應該被選取為調頭點或結束點的橫坐標.需要注意的是，沿x軸正向(負向)飛行的結束點的橫坐標最大(最小)不能大于(小于)航路與搜索邊界交點的橫坐標，同理沿x軸正向(負向)飛行的調頭點的橫坐標最小(最大)不能小于(大于)航路與搜索邊界交點的橫坐標，否則就取該交點的橫坐標.

圖7 調頭點與結束點的選取Fig.7 Selection of turn start point and turn end point

2.3 最小轉彎半徑對路徑的影響

無人機在搜索區域外的航路可認為是在最小轉彎半徑約束下，從調頭點至結束點的最短路徑問題.由最小轉彎半徑r和無人機探測區域半徑R的關系，分為兩種情況.

1)r＜R時的情況.

給定調頭點A和結束點B，實際轉彎路徑為圖8中粗實線所示.無人機航跡是兩段圓心角分別為π/2+α和β的圓弧和一條直線段組成的.圖8所示為飛行方向為x軸正向的兩種情況，區別在于航跡經過兩段圓弧的順序.飛行方向為負時有類似的結果.

圖8 r＜R時的轉彎航路Fig.8 Turning route when r＜ R

2)r≥R時的情況.

當r≥R時，無人機航跡是由兩段圓心角分別為3π/2－β和α的圓弧組成的.圖9中粗實線所示為飛行方向為x軸正向的兩種臨界情況，即A與B的橫坐標恰好滿足:

圖9 r≥R時臨界情況的轉彎航路Fig.9 Critical situation of turning route when r≥R

在式(2)不成立時，需補充一段直線航路.圖9(a)情況對應圖10(a)，若結束點橫坐標小于臨界結束點B橫坐標(B1)，則先按臨界情況(虛線)轉彎，到達B點后，再直線行進一段長度為ΔS1的線段;若結束點橫坐標大于臨界結束點B橫坐標(B2)，則先行進一段長度為ΔS2的線段到達A2點，然后再進行轉彎.圖 9(b)的情況對應圖10(b)，有著類似的結果.結束點與臨界結束點之間的距離ΔS由式(3)計算.

圖10 r≥R時非臨界情況的轉彎航路Fiig.10 Non-critical situation of turning route when r≥R

2.4 搜索終點的確定

搜索終點本質是調頭點，只是不再進行轉彎.所以可得出與2.2節類似的結論，當飛行方向為x軸正(負)向時，搜索邊界與當前直線航路的交點、與當前探測上邊界的交點、與當前下邊界的交點，這3個點的橫坐標最大(小)值應該被選取為搜索終點的橫坐標.

圖11所示是飛行方向沿x軸正向時的搜索終點情況.當飛行方向沿x軸負方向時，得到的結論是一致的.

圖11 搜索終點的選取Fig.11 Selection of the ending point

3 搜索區域分割

3.1 凸多邊形分割算法

設凸多邊形搜索區域P頂點序列V(P)按逆時針排列.區域內有N架無人機執行搜索任務，每架無人機負責搜索的面積各不相同.多邊形P中無人機的數量用s(P)表示，無人機位置、搜索面積等用S(P)表示.區域分割的目的是用N－1條線段，將P分割成N個子多邊形，每個子多邊形中包含一架無人機，且該子多邊形的面積等于其包含無人機需要搜索的面積［14］.

若在第1步分割后，分開的兩部分各包含n1和n2架無人機，且n1≠1或n2≠1，下面分割哪個多邊形，在文獻［14］中并未提及.解決這個問題可以借鑒廣度搜索的思想，使用一個初值為V(P)的隊列，標志位為1.然后將每一次分割過后s(P)≠1的多邊形頂點序列放入隊列尾部，標志位向后移動一位，最終可實現將 P分割成 N部分.

3.2 選擇分割方案

對凸多邊形區域應用上述算法分割，當頂點次序不同時(即改變初始頂點V1，其他頂點逆時針順次排序)，分割結果也不同.即對凸M多邊形，用一條線段將其分割成兩部分會有M種結果.如圖12所示，要把S1(30%)和S2(70%)分割開，分別以4個頂點作為 V1，有4種分割結果.

圖12 頂點序列順序不同時的分割結果Fig.12 Decomposition results under different orders of vertices

對有k架無人機的搜索區域，每架無人機在各自搜索子區域內的轉彎次數為ni，則總轉彎次數為

結合第1節的論證，將全部無人機的總轉彎次數作為分割結果的評判標準.在若干種分割結果中，選取N值最小的作為最終的分割結果.

3.3 從初始位置到搜索起始點的路徑

將搜索區域分割后，無人機所在的初始位置很可能不在2.1節所討論的搜索起始點上，所以在搜索開始前，要先將無人機從初始位置移動到搜索起始點.設無人機初始位置與搜索起始點的間距為D，這個過程受最小轉彎半徑r的限制，路徑可能出現D＞r或D≤r兩種情況.

1)D＞r情況.

如圖13所示，從初始位置S沿直線移動到切點B，然后按最小轉彎半徑飛至A點，即可開始平行搜索.切點B可由以下方程組求解:

然后通過B點坐標可求得圓心角θ，進而航路得以解算.

圖13 D＞r時的起始路徑Fig.13 Initial route when D ＞ r

2)D≤r情況

如圖14所示.無人機先按最小轉彎半徑沿圓周運動，再經一段直線到達搜索起始點.當yS＞yO時，如S1位置所示，B1坐標與θ值可用下式計算:

圖14 D≤r時的起始路徑Fig.14 Initial route when D≤r

當yS＜yO時，如S2位置所示，B2坐標也由式(6)計算，θ的計算公式為

4 仿真結果

仿真算例1:設3架無人機覆蓋搜索某隨機生成的五邊形區域.搜索區域頂點坐標序列為

無人機坐標序列為

設搜索面積百分比分別為20%，30%，50%，最小轉彎半徑r分別為1，2，3，探測范圍半徑R均為2.順次變換頂點V1的位置，有5種分割方式，選取總轉彎次數最少的一種，總轉彎次數為16次，如圖15所示.覆蓋搜索結果如圖16所示.仿真算例2:設4架無人機覆蓋搜索某正六邊形區域.搜索區域頂點坐標序列為

圖15 包含3架無人機的隨機五邊形搜索區域及分割結果Fig.15 A random pentagon search area including 3 UAVs and decomposition result

圖16 3架無人機對隨機五邊形搜索區域的覆蓋結果Fig.16 Coverage result of 3 UAVs in a random pentagon search area

無人機坐標序列為

設搜索面積百分比分別為10%，20%，30%，40%，最小轉彎半徑 r分別為 1，2，2，4，探測范圍半徑R均為2.順次變換頂點V1的位置，有6種分割方式，選取總轉彎次數最少的一種，總轉彎次數為24次，如圖17所示.無人機覆蓋搜索結果如圖18所示.

圖17 包含4架無人機的正六邊形搜索區域及其分割結果Fig.17 A regular hexagon search area including 4 UAVs and the decomposition result

圖18 4架無人機對正六邊形搜索區域的覆蓋結果Fig.18 Coverage result of 4 UAVs in a regular hexagon search area

5 結論

1)本文對多無人機在凸多邊形搜索區域內的覆蓋協同搜索問題進行了研究.通過一種凸多邊形分割算法，將待搜索區域分割成為若干子區域，把多無人機協同搜索問題轉化為子區域內的單機覆蓋搜索問題.這種分割方法基于無人機的初始位置和負責搜索的面積大小，可以有針對性地對不同無人機制定搜索方案.這種分割方法可以給出多種分割結果，以全部無人機的總轉彎次數最少作為評估準則，轉彎次數最少即為飛行路程最短，從而得到最優的分割結果.

2)本文使用Z字形平行搜索策略，可以實現搜索區域的無遺漏覆蓋.為了確保這一點，對搜索路徑中各關鍵點進行了分析，詳細討論了搜索起始點、轉彎關鍵點、搜索終點的選取.并且針對飛行器最小轉彎半徑對飛行的影響，具體討論、計算了各種參數條件下的路徑.并將多機協同的強耦合任務轉為弱耦合任務，在無遺漏覆蓋的基礎上降低重復搜索，提高了搜索效率.通過仿真結果驗證了方法的有效性.

3)在今后的研究中還可以進一步驗證螺旋狀平行搜索、間隔平行搜索等策略對飛行路程的影響.另外如果地形起伏較大，還需要考慮地面高度對搜索的影響.

References)

［1］ George J，Sujit P B，Sousa J B.Search strategies for multiple UAV search and destroy missions［J］.Journal of Intelligent ＆Robotic Systems，2011，61(1-4):355-367.

［2］ Huang W H.Optimal line-sweep-based decompositions for coverage algorithms［C］//Proceedings of the IEEE International Conference on Robotics and Automation.Seoul:IEEE，2001，1:27-32.

［3］ Araujo J F，Sujit P B，Sousa J B.Multiple UAV area decomposition and coverage［C］//Computational Intelligence for Security and Defense Applications(CISDA).Singapore:IEEE，2013:30-37.

［4］ 李子文，夏潔.無人偵察機路徑規劃方法研究［J］.系統仿真學報，2008，20(z1):490-494.Li Z W，Xia J.Reconnaissance path planning for UAV［J］.Journal of System Simulation，2008，20(z1):490-494(in Chinese).

［5］ 袁利平，夏潔，陳宗基.多無人機協同路徑規劃研究綜述［J］.飛行力學，2009，27(5):1-5.Yuan L P，Xia J，Chen Z J.Survey on multiple UAV cooperatice path planning research［J］.Flight Dynamics，2009，27(5):1-5(in Chinese).

［6］ Lin L，Goodrich M A.Hierarchical heuristic search using a Gaussian mixture model for UAV coverage planning［J］.IEEE Transactions on Cybernetics，2014，44(12):2532-2544.

［7］ 沈東，魏瑞軒，茹常劍.基于數字信息素的無人機集群搜索控制方法［J］.系統工程與電子技術，2013，35(3):591-596.Shen D，Wei R X，Ru C J.Digital-pheromone-based control method for UAV swarm search［J］.Systems Engineering and E-lectronics，2013，35(3):591-596(in Chinese).

［8］ Dille M，Singh S.Efficient aerial coverage search in road networks［C］//AIAA Guidance，Navigation，and Control(GNC)Conference.Reston，VA:AIAA，2013:1-20.

［9］ 彭輝，沈林成，霍霄華.多UAV協同區域覆蓋搜索研究［J］.系統仿真學報，2007，19(11):2472-2476.Peng H，Shen L C，Huo X H.Research on multiple UAV cooperative area coverage searching［J］.Journal of System Simulation，2007，19(11):2472-2476(in Chinese).

［10］ 軒永波，黃長強，吳文超，等.運動目標的多無人機編隊覆蓋搜索決策［J］.系統工程與電子技術，2013，35(3):539-544.Xuan Y B，Huang C Q，Wu W C，et al.Coverage search strategies for moving targets using multiple unmanned aerial vehicle teams［J］.Systems Engineering and Electronics，2013，35(3):539-544(in Chinese).

［11］ Mirzaei M，Gordon B W，Rabbath C A，et al.Cooperative multi-UAV search problem with communication delay［C］//AIAA Guidance，Navigation，and Control Conference.Toronto，Ontario Canada:AIAA，2010，8420:1-11.

［12］ Pehlivanoglu Y V.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV［J］.Aerospace Science and Technology，2012，16(1):47-55.

［13］ Guruprasad K R，Ghose D.Automated multi-agent search using centroidal voronoi configuration［J］.IEEE Transactions on Automation Science and Engineering，2011，8(2):420-423.

［14］ Hert S，Lumelsky V.Polygon area decomposition for multiplerobot workspace division［J］.International Journal of Computational Geometry ＆ Applications，1998，8(4):437-466.

［15］ Bolonkin A，Cloutier J R.Search and attack strategies［C］//2005 AIAA Guidance，Navigation，and Control Conference and Exhibit.Rhode Island:AIAA，2005:1-12.

［16］ 陳海，王新民，焦裕松，等.一種凸多邊形區域的無人機覆蓋航跡規劃算法［J］.航空學報，2010，31(9):1802-1807.Chen H，Wang X M，Jiao Y S，et al.An algorithm of coverage flight path planning for UAVs in convex polygon areas［J］.Chinese Journal of Aeronautics，2010，31(9):1802-1807(in Chinese).