劉宇，趙懷慈，花海洋

1.中國科學院沈陽自動化研究所，沈陽 110016

2.中國科學院研究生院，北京 100039

3.中國科學院光電信息處理重點實驗室，沈陽 110016

4.遼寧省圖像理解與視覺計算重點實驗室，沈陽 110016

飛行試驗航路規(guī)劃方法研究與實現(xiàn)

劉宇1，2，3，4，趙懷慈1，3，4，花海洋1，3，4

1.中國科學院沈陽自動化研究所，沈陽 110016

2.中國科學院研究生院，北京 100039

3.中國科學院光電信息處理重點實驗室，沈陽 110016

4.遼寧省圖像理解與視覺計算重點實驗室，沈陽 110016

1 引言

掛飛試驗用于測試驗證某光電系統(tǒng)在空中對地面目標成像效果和對環(huán)境的適應能力。試驗時，觀測方位角與太陽方位角的相對關系對系統(tǒng)成像效果影響顯著，因此需要在特定觀測方位角與太陽方位角相對關系下進行試驗，試驗時航路能否滿足預先設定角度關系決定了試驗是否能夠達到預期效果。此外，試驗空域可能存在禁飛區(qū)，飛機飛行航路需要規(guī)避禁飛區(qū)；一次試驗需要對多個目標進行觀測，且一次試驗飛行時間、飛行距離有限，選取合適的目標試驗順序及目標間的航路，使得航程和試驗時間較短，對保證試驗的可行性有重要意義。

在文獻[1]中，航跡使用三維空間中一系列點表示，這種航跡表示方法是較常見的無人飛行器航跡表示方法，但該方法表示的航跡對于本文中有人駕駛情況過于復雜，難以在掛飛試驗中應用。本文采用了文獻[2]中航路表示方法，即使用順序相連的線段和弧表示航路。文獻[3]所研究的問題與本文中問題相似，并解決了目標點間路徑計算及目標點順序選取問題，但其不需考慮觀測點選取問題。由于掛飛試驗約束條件的特殊性，特別是與太陽方位角相關的觀測點選取問題，在其他文獻中并沒有涉及，因此需要在本文中提出解決方法。本文針對掛飛試驗實際問題，提出了一種飛行試驗航路規(guī)劃方法，該方法可以有效規(guī)劃出滿足試驗各種約束條件的航路，為試驗順利進行提供了保證。

2 問題描述

在一次光電系統(tǒng)掛飛試驗中，需要分別對多個地面目標進行觀測，以測試光電系統(tǒng)成像效果和環(huán)境適應能力。試驗前對每個目標都確定了觀測距離，允許的觀測角度范圍，觀測方位角與太陽方位角夾角范圍，試驗航路必須滿足這三項約束。在試驗空域內，可能存在多個禁飛區(qū)，飛行航路不能穿越禁飛區(qū)。飛機在飛行中，受物自身物理特性制約，不能以小于最小轉彎半徑進行轉彎。一次試驗的飛行時間有限，規(guī)劃航路不能超過飛機一次飛行的最大航程。以上是規(guī)劃試驗路徑時主要考慮的約束條件。

本文討論的航路規(guī)劃問題在本質上是一個多約束條件下的優(yōu)化求解問題，可表示為下式：

由于該問題約束較多且較復雜，無法直接求解，本文中采用搜索方法計算試驗航路。

整條試驗航路由多條子航路組成，每條子航路都由起始于前一目標點（第一條起始于機場除外），終止于當前目標點。子航路組成如圖1所示，圖中E點為觀測點，G點為目標，S點為當前起始點，每條子航路由自由航路和觀測段航路兩部分組成，其中觀測段航路是一條直線段，一端點為目標觀測點，另一端點為當前目標。目標觀測點位于以目標為中心觀測距離為半徑的圓上，需要滿足禁飛區(qū)約束、觀測角度范圍約束及觀測角度與太陽方位角夾角范圍約束；自由航路從起始點到目標觀測點，需要滿足禁飛區(qū)約束和最小轉彎半徑約束。

圖1 試驗航路示意圖

本文所要解決問題是如何在試驗的二維空域內規(guī)劃出一條滿足眾多約束條件且使航程較短的航路。

本文中將該問題可拆分為以下幾個子問題：

（1）求解滿足禁飛區(qū)約束的最短折線子航路。

（2）選取各目標觀測點，使得在滿足各項約束下子航路最短。

（3）確定較優(yōu)的目標觀測試驗順序，使得總航程較短。

（4）由折線航路生成滿足最小轉彎半徑約束的航路。

主要解決思路如下：

（1）在起始點、目標觀測點確定情況下，構造搜索空間，并在其中進行最短折線航路搜索。

（2）在觀測點所在圓上進行離散化處理，選擇滿足試驗各項約束且使得子航路最短的觀測點。

（3）使用搜索算法，搜索使得總航程最短的目標試驗順序。

（4）利用幾何法[2]在折線航路上計算滿足最小轉彎半徑的試驗航路。

3 優(yōu)化航路計算方法

3.1 可見性圖構建及兩點間最短折線路徑計算原理

穿行于一組互不相交的多邊形障礙物S之間，從Pstart通往Pgoal的任何一條最短路徑，都是一條多邊形路徑，其中所有的內部頂點都是S的頂點[4]。構建障礙物S以及起始點目標點的可見性圖Gvis(S*)。穿行于障礙物S之間，從Pstart通往Pgoal的任何一條最短路徑，必然是由可見性圖Gvis(S*)中的若干條弧聯(lián)接而成的[4]。構建可見性圖是在有多邊形障礙區(qū)域內搜索兩點間最短路徑的有效方法。這里使用Dijkstra算法在可見性圖中進行搜索求解，可得到起始點到目標點的最短路徑。Dijkstra算法將連通圖轉換，構造出以起始點為根節(jié)點的樹，起始點到某點最短路徑可直接從樹結構中得到。設障礙物總頂點數(shù)為V，則Dijkstra算法將花費O(V2)構建最短路徑樹Tall，并得到最短路徑。圖2為Pstart、Pgoal及一組多邊形障礙物繪制的可見性圖，圖中紅色多邊形為障礙物，Pstart為起點，Pgoal為終點，虛線表示兩點間直接可見，黑色實線為Pstart到Pgoal間最短路徑。

圖2 可見性圖及最短路徑示意圖

3.2 觀測點選取策略

觀測點選取是本文中要重點討論的問題之一。觀測點的選取直接關系到航路是否滿足試驗要求，并對總航程有較大的影響。目標的觀測距離是試驗前確定的，不考慮約束條件，可選以目標為中心觀測距離為半徑的圓上任意一點為觀測點。觀測點選取受禁飛區(qū)、目標允許觀測方向及觀測方位角與太陽方位角夾角度范圍約束限制。

本文將可能觀測點離散化處理，然后搜索求得最佳的觀測點。首先將以目標為中心觀測距離為半徑的圓進行離散化，得到N個可選觀測點。本文按照以下原則選取觀測點：

（1）觀測點不能在禁飛區(qū)內部，且觀測點至目標的線段不穿越禁飛區(qū)（觀測點與目標直接可見）。

（2）觀測點在目標的可觀測方向范圍內。

（3）根據(jù)得到的航路計算時間，搜索滿足此時飛機航路方向與陽光光線間的角度范圍的觀測點。

在搜索時，從滿足以上三條的可選觀測點中找到使路徑最短的觀測點。離散點數(shù)N直接關系到搜索算法的精度及時間消耗，越高的離散精度所得到的解精度越高，但耗費計算資源越大。

得到離散的可選觀測點后，計算每個可選觀測點到多邊形障礙頂點及目標點的可見性圖，再根據(jù)前面的最短路徑樹Tall可直接得到當前最佳的可選觀測點及前一目標到當前目標的最短折線路徑。圖3為目標點A離散化后的可選觀測點與多邊形障礙物頂點、目標點構成的可見性圖，圖中黑色實心矩形為目標，粗實線圍成的多邊形為障礙物，以目標點A為圓心的圓為可選觀測點所在圓，虛線表示兩點間直接可見。

圖3 目標點A的可選觀測點與頂點、目標點構成的可見性圖

3.3 目標順序搜索過程

如何確定目標順序使得到的路徑較短也是本文中要解決的問題。雖然一次試驗中，目標點個數(shù)通常不會超過10個，但由于求解某一確定順序下最短路徑的計算量也較大，因此完全遍歷方法所需時間也是不能夠接受的，并且完全遍歷計算量隨目標個數(shù)增多急劇增加，更不能保證以后處理略多目標情況下算法的可用性。這里選擇遺傳算法來進行順序求解。本文所要解決的問題中目標個數(shù)較小，屬于小規(guī)模組合優(yōu)化問題，較容易得到可接受的解。

遺傳算法需要確定如下問題：染色體編碼，適應度函數(shù)，父代選擇，交叉運算，變異運算。本文直接使用目標序號作為染色體編碼，如（5-1-7-8-9-4-6-2-3），這樣的編碼表示目標順序自然合理；使用當前順序下得到的折線路徑長度作為適應度函數(shù)評價標準，認為總長度越小的路徑順序越優(yōu)；每次從當前種群中選擇最優(yōu)的K個作為下一代的父代；交叉算法采用次序交叉；變異算子采用逆序和互換。計算結果表明，遺傳算法能夠得到滿足試驗要求的且較優(yōu)的目標遍歷順序。圖4為采用遺傳算法計算得到的折線航路，圖中以目標為圓心分布在同一個圓上的點為離散化后的可選觀測點，連接目標點觀測點及障礙物頂點的虛折線段表示計算得到的折線路徑。

圖4 計算得到的折線航路

3.4 滿足最小轉彎半徑約束航路計算方法

在生成的折線路徑基礎上使用幾何法生成滿足最小轉彎半徑約束的路徑，并且試驗中飛機高度、速度不發(fā)生變化，不用考慮飛機高度、速度變化問題。在文獻[2]中有如下結論：

結論1對于兩同方向的航路點，飛機按直線飛行時所飛過的距離最短。

結論2平面內，在某航路點上無人機改變方向的最短路徑是按最小轉彎圓運動。

由這兩條結論可知，滿足最小轉彎半徑約束且最短的航路由轉彎半徑為最小轉彎半徑的圓弧及直線段組成。

使用幾何法前需要確定飛機在各點的方向，確定方法如下：

（1）若該點為目標觀測點或目標點，則該點方向為觀測點目標點間線段方向，以保證觀測段為朝向目標的直線。

（2）若該點為中間節(jié)點且該點不在禁飛區(qū)附近，該點方向為前一點至后一點的矢量方向。這樣的方向能夠保證飛機在中間節(jié)點以較優(yōu)方式進行轉彎。

（3）若該點為中間節(jié)點且該點靠近禁飛區(qū)，則選擇與禁飛區(qū)邊緣平行方向作為飛機飛行方向以確保航路不與禁飛區(qū)相交。

確定飛機在各點方向后，使用幾何法可得到滿足最小轉彎半徑約束的飛行航路。圖5為最終計算所得的由弧和線段組成的，滿足所有試驗約束條件的航路。

圖5 由圓弧和線段構成的最終飛行航路

4 航路規(guī)劃應用實例

以一次掛飛試驗航路規(guī)劃過程為例，詳細試驗要求如下：

掛飛試驗時間為2011年11月24日9：00，觀測目標為四個目標，每個目標觀測兩次，每次觀測的參數(shù)不同，表1是試驗目標的各項參數(shù)。試驗載機飛行速度為150 km/h。

表1 目標實驗參數(shù)

規(guī)劃航路結果如圖6所示。圖6中實心矩形為目標，線路上空心圓形為觀測點，從圖中可以看出，計算得到的試驗航路滿足禁飛區(qū)約束，且保證了路線的優(yōu)化，滿足一次試驗的時間、航程要求；從表2中可知每個所選觀測點都滿足設定的觀測方向范圍約束和與太陽方位角夾角范圍約束，因此該航路完全符合試驗的各項要求。算例證明該航路規(guī)劃算法可以為掛飛試驗提供滿足各項約束的航路。

5 結論

本文針對光學系統(tǒng)掛飛試驗路徑規(guī)劃問題提出了一種有效的航路規(guī)劃算法。通過構造可見性圖形成搜索空間，使用Dijkstra算法求得兩點間最優(yōu)路徑段，離散化可選觀測點并搜索最適合的觀測點，使用遺傳算法搜索較優(yōu)的目標順序，最后使用幾何法得到滿足最小轉彎半徑約束的飛行路徑。計算結果表明，本文算法所得到的試驗航路能夠滿足試驗的各項約束，為光電系統(tǒng)掛飛試驗提供了有力的支持。

圖6 根據(jù)試驗條件規(guī)劃出的一條可行航路

表2 計算結果

[1]丁明躍.無人飛行器航跡規(guī)劃[M].北京：電子工業(yè)出版社，2009.

[2]王慶江，高曉光，符曉衛(wèi).無威脅情況下任意兩點間的無人機路徑規(guī)劃[J].系統(tǒng)工程與電子技術，2009，31（9）：2157-2162.

[3]Luo Quan，Liu Zhong，Qiao Shidong.A hybrid route planning algorithm of single aerial vehicle attacking multiple targets[C]//ProceedingsoftheNinthInternationalConference on Machine Learning and Cybernetics，2010：1532-1537.

[4]德貝爾赫.計算幾何——算法與應用[M].鄧俊輝，譯.2版.北京：清華大學出版社，2005.

[5]維斯.數(shù)據(jù)結構與算法分析——C語言描述[M].馮舜璽，譯.2 版.北京：機械工業(yè)出版社，2004.

[6]李敏強.遺傳算法的基本理論與應用[M].北京：科學出版社，2002.

LIU Yu1，2，3，4,ZHAO Huaici1，3，4,HUA Haiyang1，3，4

1.Shenyang Institute of Automation,Chinese Academy of Sciences,Shenyang 110016,China
2.Graduate School,Chinese Academy of Sciences,Beijing 100039,China
3.Key Lab of Opto-Electronic Information Processing,Chinese Academy of Sciences,Shenyang 110016,China
4.Key Lab of Image Understanding and Computer Vision,Liaoning Province,Shenyang 110016,China

Τhe flying test of an opto-electronic module has high demand to the aircraft route,and a route that satisfies the constraints of the test is the precondition to fulfill the objective of the test.According to this question,a search space construction method based on visibility graph is used here；the shortest polylines path between two targets is got by the Dijkstra algorithm；the GA algorithm is used to get an optimized order of targets；then the final route is got from the polylines path and minimum turning radius is satisfied.Τhe result shows that this route computing method can be well used to get an aircraft route which satisfies the constraints of the opto-electronic module test.

route planning;visibility graph;Dijkstra algorithm;combinational optimization;Genetic Algorithm（GA）

光電系統(tǒng)掛飛試驗對飛行航路有較高要求，一條能夠滿足試驗各項約束的航路是試驗按計劃完成的前提。針對該問題，提出了一種基于可見性圖的航路搜索空間構造方法；使用Dijkstra算法計算順序兩目標點間的折線路徑；使用遺傳算法計算代價最小的目標觀測順序；在得到的折線路徑上計算得到滿足最小轉彎半徑約束的航路。計算結果表明，這種航路算法能夠有效規(guī)劃出滿足掛飛試驗多約束條件的航路。

航路規(guī)劃；可見性圖；Dijkstra算法；組合優(yōu)化；遺傳算法

A

ΤP273.5

10.3778/j.issn.1002-8331.1201-0301

LIU Yu,ZHAO Huaici,HUA Haiyang.Research and implementation of route planning method for flying test.Computer Engineering and Applications,2013,49（21）：262-265.

劉宇（1987—），男，碩士在讀，主要研究領域為任務規(guī)劃及仿真；趙懷慈（1974—），男，博士，研究員；花海洋（1978—），男，助理研究員。E-mail：liuyu@sia.cn

2012-01-16

2012-02-27

1002-8331（2013）21-0262-04

CNKI出版日期：2012-06-01http://www.cnki.net/kcms/detail/11.2127.ΤP.20120601.1457.013.html