[發明專利]一種面向不確定任務時間的自主水下航行器航路規劃方法

有效

• 申請號: 201210099784.9
• 申請日: 2012-04-06
• 公開（公告）號: CN102679982A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 彭星光;嚴衛生;宋保維;劉明雍;張福斌;高劍;崔榮鑫;張立川
• 申請（專利權）人: 西北工業大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 王鮮凱

技術領域

本發明屬于AUV任務分配與航路規劃領域，涉及一種面向不確定任務時間的自主水下航行器航路規劃方法。?

背景技術

AUV在通常需要在較大范圍內執行觀測等任務，這些任務點所需的任務時間往往只能通過事先估計得知。因此，在執行多點任務時，必須在規劃航行器到達任務點先后序列的同時，考慮各任務點所需時間的不確定性，以及受航行器的最大工作時間約束所導致的返航和充電時間，使整個任務過程所需的時間最少。?

近年來，在AUV的航路規劃研究領域，已取得一些研究成果，但對于具有不確定任務時間的AUV多航路點航路規劃的研究，國內外研究并未發現。?

發明內容

為了避免現有技術的不足之處，本發明提出一種面向不確定任務時間的自主水下航行器航路規劃方法，針對航路規劃問題的啟發式遺傳操作，以提高航路規劃結果的性能。?

一種面向不確定任務時間的自主水下航行器航路規劃方法，其特征在于步驟如下：?

步驟1：對航路規劃問題進行編碼得到規模為N的種群，所述的編碼方式為：航路規劃問題的每個可行解的編碼由為多個子編碼序列表示，每個子編碼序列代表1個AUV的航路點順序，子編碼序列的數量代表航行完所有航路點所需的AUV數量；所述子編碼序列的產生方法：隨機產生N_V個的[1，N_V]正整數，作為每個航行器所需航行的航路點數量；所述N_V為參與任務的AUV數量；?

步驟2評估種群適應度：對每條航路序列的代價f_i重復計算N_RSM次，每次計算時各航路點的具體觀測時間由其概率分布隨機生成，然后用這N_RSM次計算結果的期望值作為該航路的估計代價；對編隊中所有AUV的航路進行估計后即可得到該個體的適應度估計值?

其中：?(i＝1，...N_V)，L為航路的長度，V為航行器的速度；?

步驟3從當前種群中選出N個優良個體：當前種群中每個個體被選中的概率等于其適應度與種群個體適應度之和的比值，隨機產生[0，1]之間的隨機數，若該數大于比值則選中該個體，否則不選；?

步驟4對優良個體以概率p_c進行交叉操作：首先分別從N個優良個體中選出兩條代價最小的航路，然后將兩條航路進行交換并作為它們的第一條航路；?

如果個體中只有一條航路時則用該航路中隨機選出的一個片段與另一個個體中的最佳航路進行航路交換，具體交換方式為：一個新航路點D插入距它最近的航路點之前或之后，新航路點D將插入到原航路A-B-C-A中，距D最近的點為B，得到插入結果：A-D-B-C-A或A-B-D-C-A；若Dis(A，D)+Dis(B，C)大于Dis(A，B)+Dis(D，C)則選擇后者，反之選擇前者，其中Dis(C₁，C₂)代表C₁和C₂間的距離；?

步驟5：對交叉后的優良個體以概率p_m進行變異操作，以如下任意一種方式進行啟發式變異操作：?

1)啟發式局部交換：每次交換的兩條航路隨機確定，將每個航路中的一個隨機選出的片段交換到另一個航路中去，按照INM方法將該片段中的每個點插入到另一個航路中，同時保證在每次啟發式局部交換過程中相同兩條航路之間不會發生兩次交換操作；?

2)啟發式最短航路合并：在個體中尋找兩個最短航路，并將其中一條以INM方法插入到另一條航路中，將二者合并；?

3)啟發式最長航路拆分：將個體中代價最大的航路從一隨機點拆分成兩條航路，新拆分出的航路以INM方法插入一條空航路中；?

步驟6：循環步驟2～5N_t次，得到最優個體；?

步驟7：對最優個體按照步驟1中的編碼規則進行解碼，得到每個AUV的規劃航路。?

本發明提出的一種面向不確定任務時間的自主水下航行器航路規劃方法，可用于對多個AUV的航路進行規劃，實現多AUV系統的協同航路規劃，能夠保證規劃結果?的全局最優性，且具有使用方便，通用性強的特點；也可應用于對機器人、無人飛行器等的航路規劃。?

附圖說明

圖1：本發明的編碼方式的示意圖；?

圖2：本發明啟發式遺傳操作中所使用的插入最近點(INM)方法的示意圖；?

圖3：本發明可行解評價算法的偽代碼?

具體實施方式