運(yùn)動(dòng)學(xué)約束條件下多AUV任務(wù)分配算法

李 欣，朱大奇，徐珂昂

（上海海事大學(xué)水下機(jī)器人與智能系統(tǒng)實(shí)驗(yàn)室，上海201306）

運(yùn)動(dòng)學(xué)約束條件下多AUV任務(wù)分配算法

李 欣，朱大奇，徐珂昂

（上海海事大學(xué)水下機(jī)器人與智能系統(tǒng)實(shí)驗(yàn)室，上海201306）

針對運(yùn)動(dòng)學(xué)約束的自治水下機(jī)器人（AUV）任務(wù)分配與路徑規(guī)劃問題，本文以多個(gè)AUV組成的系統(tǒng)為研究對象，將Dubins Path算法與改進(jìn)的自組織映射（SOM）神經(jīng)網(wǎng)絡(luò)算法相結(jié)合，提出一種在運(yùn)動(dòng)學(xué)約束條件下多AUV任務(wù)分配與路徑規(guī)劃算法。通過SOM神經(jīng)網(wǎng)絡(luò)方法對多AUV進(jìn)行任務(wù)分配后，若存在運(yùn)動(dòng)學(xué)約束或障礙物而導(dǎo)致無法進(jìn)行Dubins路徑規(guī)劃時(shí)，則重新進(jìn)行任務(wù)分配，直到所有目標(biāo)點(diǎn)都有AUV到達(dá)。仿真結(jié)果表明該算法能夠有效完成運(yùn)動(dòng)學(xué)約束條件下多AUV的任務(wù)分配。

自治水下機(jī)器人；多任務(wù)分配；路徑規(guī)劃；自組織映射；Dubins Path；運(yùn)動(dòng)學(xué)約束；負(fù)載均衡

多自治水下機(jī)器人（autonomous underwater vehicle，AUV）系統(tǒng)的任務(wù)分配算法涵蓋兩方面:任務(wù)分配和路徑規(guī)劃，即指依據(jù)一定的算法控制一組AUV，各自沿著運(yùn)動(dòng)學(xué)約束條件下的優(yōu)化路徑到達(dá)目標(biāo)的技術(shù)。其中任務(wù)分配是指將任意數(shù)目的目標(biāo)分配給多AUV系統(tǒng)，在保證所有目標(biāo)被遍歷的前提下，整個(gè)多AUV系統(tǒng)的代價(jià)最?。?］。路徑規(guī)劃技術(shù)是指在全局任務(wù)分配后，針對單一AUV的路徑規(guī)劃方法。

任務(wù)分配算法的研究目前已經(jīng)有不少的理論和研究成果，市場機(jī)制［2-3］算法是解決多任務(wù)分配作業(yè)中最常見的方法；另一種常見任務(wù)分配算法就是蟻群算法［4］，主要研究動(dòng)態(tài)環(huán)境下多機(jī)器人系統(tǒng)在動(dòng)態(tài)環(huán)境下自主任務(wù)分配問題。在此基礎(chǔ)上文獻(xiàn)［5］進(jìn)一步提出了適合于大規(guī)模多機(jī)器人集群的任務(wù)分配算法。自組織神經(jīng)網(wǎng)絡(luò)算法也可以應(yīng)用于多任務(wù)分配，該算法是由Kohonen［6］于20世紀(jì)80年代提出的，文獻(xiàn)［7-9］將自組織神經(jīng)網(wǎng)絡(luò)應(yīng)用于多移動(dòng)機(jī)器人系統(tǒng)的任務(wù)分配與路徑規(guī)劃中。文獻(xiàn)［10］采用了自組織映射（self-organizing map，SOM）神經(jīng)網(wǎng)絡(luò)算法，提出了在二維海洋環(huán)境下的多AUV系統(tǒng)的動(dòng)態(tài)任務(wù)分配。在此基礎(chǔ)上文獻(xiàn)［11］進(jìn)一步將自組織映射（SOM）神經(jīng)網(wǎng)絡(luò)的多AUV多目標(biāo)分配策略推廣應(yīng)用到三維海洋環(huán)境中。雖然多任務(wù)分配問題已經(jīng)得到了廣泛的研究，但是，以往的研究均未考慮AUV水下運(yùn)動(dòng)學(xué)約束和障礙物問題。實(shí)際環(huán)境中的AUV水下任務(wù)分配與路徑規(guī)劃，不能忽略運(yùn)動(dòng)學(xué)約束和障礙物環(huán)境的實(shí)際存在，本文主要對此進(jìn)行深入研究。

路徑規(guī)劃則是AUV需要具備的智能行為之一。所謂路徑規(guī)劃，是在具有障礙物的環(huán)境中，AUV按照一定的評價(jià)標(biāo)準(zhǔn)，找到一條從起始狀態(tài)到達(dá)目標(biāo)狀態(tài)的無碰撞路徑［12-14］。傳統(tǒng)的路徑規(guī)劃方法主要有:可視圖法［15］、人工勢場法［16］、遺傳算法［17］、模糊邏輯法［18］等。這些路徑規(guī)劃方法都有各自的適用范圍，但是，AUV的水下運(yùn)動(dòng)具有局限性，它的轉(zhuǎn)向性能受到方向舵最大偏角的制約，因此其轉(zhuǎn)向時(shí)的最小轉(zhuǎn)向半徑為R，AUV的轉(zhuǎn)彎半徑無法比R更小，在運(yùn)動(dòng)上就受到約束，傳統(tǒng)的路徑規(guī)劃方法并沒有考慮這一點(diǎn)。能夠處理運(yùn)動(dòng)學(xué)約束的路徑規(guī)劃方法是Dubins路徑規(guī)劃方法［19］，該方法主要基于以下定理:在運(yùn)動(dòng)方向已知和轉(zhuǎn)向半徑最小的情況下，從初始向量到終止向量的最短的路徑是由直線和最小半徑轉(zhuǎn)向圓弧組成的。AUV在任務(wù)分配和路徑規(guī)劃時(shí)，采用最短路徑可以有效的節(jié)約能量。

本文研究二維環(huán)境中運(yùn)動(dòng)學(xué)約束條件下的多AUV系統(tǒng)的任務(wù)分配和路徑規(guī)劃問題，并考慮了障礙物等干擾因素。通過將Dubins Path算法與改進(jìn)的自組織特征映射（SOM）神經(jīng)網(wǎng)絡(luò)算法相結(jié)合，本文提出一種新型的任務(wù)分配與路徑規(guī)劃算法。

1 運(yùn)動(dòng)學(xué)約束下任務(wù)分配算法設(shè)計(jì)

本文針對多AUV、多目標(biāo)點(diǎn)，采用一種基于SOM神經(jīng)網(wǎng)絡(luò)和Dubins路徑的方法，處理多AUV系統(tǒng)的多任務(wù)分配及相應(yīng)的路徑規(guī)劃問題。在該方法中，AUV運(yùn)動(dòng)規(guī)劃集成在任務(wù)分配當(dāng)中，從而一旦總體任務(wù)給出，AUV就可以開始運(yùn)動(dòng)。此外，多AUV系統(tǒng)可以自動(dòng)安排總?cè)蝿?wù)，并根據(jù)環(huán)境的變化動(dòng)態(tài)實(shí)時(shí)調(diào)整運(yùn)動(dòng)規(guī)劃。

對于不考慮運(yùn)動(dòng)學(xué)約束的靜態(tài)多AUV任務(wù)分配與路徑規(guī)劃，AUV的路徑只是簡單的點(diǎn)對點(diǎn)的規(guī)劃，當(dāng)遇到障礙物直線路徑被阻斷時(shí)，則需要規(guī)劃曲線路徑甚至更換AUV去執(zhí)行任務(wù)。但是，在真實(shí)的水下工作空間內(nèi)，AUV不可能實(shí)現(xiàn)任意拐角轉(zhuǎn)向的任務(wù)。第一，AUV在運(yùn)動(dòng)過程中受到慣性的制約，導(dǎo)致其不可能在需要轉(zhuǎn)向時(shí)先緊急制動(dòng)停下來，然后再直線向目標(biāo)前進(jìn)。第二，對于某一個(gè)具體的水下AUV而言，巡航的過程中總是會受到方向舵最大偏角的制約?？紤]運(yùn)動(dòng)學(xué)限制的AUV路徑規(guī)劃算法的基本思想是:在有限的工作空間內(nèi)，將AUV和目標(biāo)點(diǎn)視為質(zhì)點(diǎn)，保持AUV運(yùn)動(dòng)速度不變，控制其沿著Dubins路徑到達(dá)目標(biāo)點(diǎn)。Dubins路徑算法是實(shí)現(xiàn)從一個(gè)向量到另外一個(gè)向量的最短的路徑，使一個(gè)向量經(jīng)過一定的平滑轉(zhuǎn)彎能夠與另一個(gè)向量方向一致。平滑轉(zhuǎn)彎曲線有很多種，但最小半徑圓弧轉(zhuǎn)彎是最短的路徑。用C表示圓弧，L表示直線，已經(jīng)證明，為保證最短路徑的要求，CLC路徑是一種理想的方式［20］。

1．1 SOM神經(jīng)網(wǎng)絡(luò)

SOM算法最大的特點(diǎn)之一就是能夠使相似輸入產(chǎn)生相似的輸出，輸入信號的特征越相近，輸出映射也越接近。SOM網(wǎng)絡(luò)由輸入層和輸出層組成，其中輸出層也即競爭層。輸入層通過權(quán)向量將外界信息匯集到輸出層各神經(jīng)元，競爭層負(fù)責(zé)對輸入模式進(jìn)行“比較”，“分析”，尋找規(guī)律，并歸類。如圖1所示，輸入層可以是一維的神經(jīng)元，競爭層可以是二維的神經(jīng)元，輸入層的神經(jīng)元和輸出層的神經(jīng)元有權(quán)值連接。

圖1 AUV編隊(duì)與虛擬結(jié)構(gòu)的位置關(guān)系Fig．1 Position relationship between AUV formation and virtual structure

由于自組織映射算法是一種無導(dǎo)師的聚類法，它能將任意維輸入模式在輸出層映射成一維或二維離散圖形，具有聚類功能、自組織功能、自學(xué)習(xí)功能。SOM神經(jīng)網(wǎng)絡(luò)采用的算法是在“勝者為王”（winnertake-all，WTA）學(xué)習(xí)規(guī)則基礎(chǔ)上加以改進(jìn)的。這種競爭學(xué)習(xí)規(guī)則的生理學(xué)基礎(chǔ)是神經(jīng)細(xì)胞的側(cè)抑制現(xiàn)象，當(dāng)一個(gè)神經(jīng)細(xì)胞興奮后，會對其周圍的神經(jīng)細(xì)胞產(chǎn)生抑制作用。

SOM神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)按如下步驟進(jìn)行:

1）初始化，即對輸出層各權(quán)向量賦值并進(jìn)行歸一化處理；

2）接受輸入，即從訓(xùn)練集中隨機(jī)取一個(gè)輸入模式并進(jìn)行歸一化處理；

3）尋找獲勝節(jié)點(diǎn)，按照競爭規(guī)則計(jì)算；

4）定義優(yōu)勝鄰域，確定t時(shí)刻的權(quán)值調(diào)整域，一般初始鄰域較大，訓(xùn)練過程中優(yōu)勝鄰域隨訓(xùn)練時(shí)間收縮；

5）調(diào)整權(quán)值，對優(yōu)勝鄰域內(nèi)的所有節(jié)點(diǎn)調(diào)整權(quán)值；

6）結(jié)束判定，當(dāng)學(xué)習(xí)率小于最小學(xué)習(xí)率時(shí)，訓(xùn)練結(jié)束，不滿足結(jié)束條件時(shí)，轉(zhuǎn)到2）繼續(xù)進(jìn)行。

1．2 SOM應(yīng)用于多AUV系統(tǒng)

假定在一個(gè)有限的工作區(qū)域內(nèi)分布著一組AUV，同時(shí)在此區(qū)域分布著任意數(shù)目的目標(biāo)。每個(gè)目標(biāo)都需要一個(gè)AUV在該點(diǎn)完成特定的任務(wù)。對于每個(gè)AUV來講，其代價(jià)是由從起始位置坐標(biāo)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置坐標(biāo)點(diǎn)所移動(dòng)的距離來衡量。總代價(jià)定義為所有單個(gè)AUV代價(jià)的總和。當(dāng)所有目標(biāo)點(diǎn)都被訪問過一次后，任務(wù)完成。這種訪問目標(biāo)點(diǎn)的過程與SOM算法是一致的［10］

本文采用有限的二維平面作為多AUV系統(tǒng)的工作空間。如圖2所示，在該工作空間內(nèi)，紅色的菱形代表AUV，綠色的圓點(diǎn)代表目標(biāo)，黑色的叉代表障礙物。假定所有AUV都是相同的，具備基本的導(dǎo)航、避障和位置識別功能。

圖2 多AUV系統(tǒng)的工作區(qū)域Fig．2 Workspace of multi-AUV system

在該工作空間內(nèi)，有4個(gè)AUV需要遍歷5個(gè)目標(biāo)，同時(shí)存在1個(gè)障礙物?；趦牲c(diǎn)之間直線最短的原理，認(rèn)為AUV的初始位置坐標(biāo)到目標(biāo)點(diǎn)的位置坐標(biāo)之間的直線為最優(yōu)路徑。

單純依靠目標(biāo)點(diǎn)坐標(biāo)與AUV坐標(biāo)最近原則分配任務(wù)，有時(shí)可能出現(xiàn)某個(gè)AUV被分配太多任務(wù)的現(xiàn)象，使其在動(dòng)力耗盡前還無法完全到達(dá)所有分配的目標(biāo)，而另外的AUV卻得不到任務(wù)目標(biāo)；以及由于障礙物而使一開始分配的任務(wù)在實(shí)際規(guī)劃路徑中無法完成。為了保證每個(gè)AUV攜帶的能源得到最大限度的利用，同時(shí)避免AUV在向目標(biāo)運(yùn)動(dòng)的過程中因?yàn)槟茉床蛔愣Ｖ?，所以在算法中要考慮AUV的負(fù)載均衡。假定，AUV具有相同的水下巡航能力且攜帶同樣的能源，所能行走的距離相同。在算法設(shè)計(jì)中，根據(jù)AUV個(gè)數(shù)，在分配任務(wù)前初始化矩陣，矩陣階數(shù)與AUV數(shù)量一致。在算法中，首先計(jì)算N=NT／NR，其中，NT是目標(biāo)點(diǎn)數(shù)量，NR是AUV數(shù)量，則任務(wù)負(fù)載的上限設(shè)置為

當(dāng)本次任務(wù)執(zhí)行后超過任務(wù)數(shù)量上限時(shí)，則不分配該任務(wù)給獲勝AUV，選擇次優(yōu)AUV執(zhí)行任務(wù)。將AUV系統(tǒng)的負(fù)載均衡考慮進(jìn)SOM任務(wù)分配算法是在文獻(xiàn)［10-11］的基礎(chǔ)上對傳統(tǒng)神經(jīng)網(wǎng)絡(luò)的有效改進(jìn)，使其更適合多AUV多任務(wù)分配的實(shí)際情況。

1．3 Dubins路徑規(guī)劃算法

實(shí)現(xiàn)二維環(huán)境下的多AUV系統(tǒng)的任務(wù)分配與路徑規(guī)劃主要運(yùn)用了兩個(gè)算法:改進(jìn)的自組織神經(jīng)網(wǎng)絡(luò)算法（SOM）和Dubins Path算法。其中，自組織神經(jīng)網(wǎng)絡(luò)算法用來實(shí)現(xiàn)多目標(biāo)的分配策略，包括神經(jīng)網(wǎng)絡(luò)的輸入層和輸出層定義、領(lǐng)域函數(shù)的確定以及權(quán)值的更新等幾個(gè)過程；Dubins Path算法用于實(shí)現(xiàn)運(yùn)動(dòng)學(xué)約束下AUV到目標(biāo)點(diǎn)的最短有效的路徑規(guī)劃。

對于具有初始和終止速度向量的AUV到目標(biāo)點(diǎn)的路徑規(guī)劃，設(shè)AUV最小轉(zhuǎn)向半徑為R，當(dāng)確定起始點(diǎn)和終止點(diǎn)后，對速度向量可以各做兩個(gè)切圓。起始向量的兩個(gè)圓和終止向量的兩個(gè)圓，兩兩組合后共有4種情況，而兩個(gè)相離的圓又可以做四條切線。相對于傳統(tǒng)的圓和直線，通過相切關(guān)系聯(lián)立方程組求解，求出四個(gè)解后判斷舍解，本文將采用更為簡便的旋轉(zhuǎn)與相似來進(jìn)行求解，使用這種求解方法將使本來需要通過討論來確定的切點(diǎn)的復(fù)雜情況變得極為簡單。文中以向量的起始方向開始畫圓，若畫圓軌跡為順時(shí)針則稱該圓為該向量的順時(shí)針圓，簡稱順圓，反之則稱為逆圓。圖3給出了兩個(gè)圓切線的的4種位置關(guān)系。

如圖4所示，由起始向量和終止向量，根據(jù)轉(zhuǎn)彎半徑R可以求出圓心點(diǎn)O1和點(diǎn)O2的坐標(biāo)，l2為圓O1、O2的切線，與圓O1相切于點(diǎn)E。過圓心O1、O2做l1，過O2做l4垂直于l2，其中l(wèi)4與圓的另一側(cè)交于點(diǎn)A。過點(diǎn)E和O1做l5垂直于l2，再過點(diǎn)O1做一條平行于X軸的l6。O1O2為圓心距，順時(shí)針旋轉(zhuǎn)到O1C處（逆時(shí)針旋轉(zhuǎn)亦可），過C作垂線交l6于點(diǎn)B，同時(shí)過點(diǎn)E作垂線交l6于D。O2的坐標(biāo)經(jīng)過旋轉(zhuǎn)到點(diǎn)C，其中旋轉(zhuǎn)角度為π／2，這樣點(diǎn)C的坐標(biāo)即可以求出，同時(shí)三角形ΔO1DE與三角形ΔO1BC相似，通過相似即可求出點(diǎn)E的坐標(biāo)，至此l2與圓O1的切點(diǎn)E坐標(biāo)已經(jīng)求出，類似的也可以求出l2與圓O2的切點(diǎn)。設(shè)l2與圓O1的切點(diǎn)坐標(biāo)為（xa，ya），l2與圓O2的切點(diǎn)坐標(biāo)為（xb，yb），圓心O1坐標(biāo)為（a1，b1），圓心O2坐標(biāo)為（a2，b2），則有:

式中:θ=π／2，φ=θ+π。另一側(cè)的外切線與圓O1和O2的切點(diǎn)亦可以通過這種方法求解。實(shí)際上即是第一種情況的鏡像對稱。設(shè)l3與圓O1的切點(diǎn)坐標(biāo)為（xc，yc），l3與圓O2的切點(diǎn)坐標(biāo)為（xd，yd），則有:

式中:θ=-π／2，φ=θ+π。通過比較兩種情況的θ角可以發(fā)現(xiàn)其互為相反數(shù)，這也體現(xiàn)了旋轉(zhuǎn)對稱的特性。內(nèi)切線的求解原理與外切線相同，限于篇幅在此不再贅述。

圖3 圓與切線的關(guān)系Fig．3 Circles and the corresponding tangents

圖5是Dubin路徑弧線規(guī)劃的求解，紅色的平箭頭向量為初始向量，綠色的凹箭頭向量為終止向量。切點(diǎn)為P1，P2，Q1，Q2。

當(dāng)初始向量在0到π之間，通過比較圓心O1和起點(diǎn)P1，若O1的橫坐標(biāo)大于P1的橫坐標(biāo)，則說明圓O1為順圓，反之則為逆圓。當(dāng)為順圓時(shí)，以P1為起點(diǎn)沿圓弧P1Q1順時(shí)針運(yùn)動(dòng)；當(dāng)為逆圓時(shí)，以P1為起點(diǎn)沿圓弧P1Q1逆時(shí)針運(yùn)動(dòng)。當(dāng)初始向量在π到2π之間，通過比較圓心O2和起點(diǎn)P2，若O2的橫坐標(biāo)大于P2的橫坐標(biāo)，則說明圓O1為逆圓，反之則為順圓。當(dāng)為順圓時(shí)，以P2為起點(diǎn)沿圓弧P2Q2順時(shí)針運(yùn)動(dòng)；當(dāng)為逆圓時(shí)，以P2為起點(diǎn)沿圓弧P2Q2逆時(shí)針運(yùn)動(dòng)。

當(dāng)終止向量在0到π之間，通過比較圓心O2和終點(diǎn)P2，若O2的橫坐標(biāo)大于P2的橫坐標(biāo)，則說明圓O2為順圓，反之則為逆圓。當(dāng)為順圓時(shí)，以Q2為起點(diǎn)沿圓弧Q2P2逆時(shí)針運(yùn)動(dòng)；當(dāng)為逆圓時(shí)，以P2為起點(diǎn)沿圓弧Q2P2順時(shí)針運(yùn)動(dòng)。當(dāng)終止向量在π到2π之間，通過比較圓心O1和P1，若O1的橫坐標(biāo)大于P1的橫坐標(biāo)，則說明圓O1為逆圓，反之則為順圓。當(dāng)為順圓時(shí)，以Q1為起點(diǎn)沿圓弧Q1P1逆時(shí)針運(yùn)動(dòng)；當(dāng)為逆圓時(shí)，以Q1為起點(diǎn)沿圓弧Q1P1順時(shí)針運(yùn)動(dòng)。程序總體算法流程圖如圖6所示。

圖5 Dubins Path弧線部分規(guī)劃Fig．5 The planning of arc part of Dubins Path

圖6 算法流程圖Fig．6 Flow chart of the algorithm

2 仿真驗(yàn)證

為了驗(yàn)證該算法在解決二維工作空間內(nèi)多AUV多任務(wù)分配與相應(yīng)路徑規(guī)劃問題的有效性，仿真在MATLAB R2011a上實(shí)現(xiàn)。

2．1 障礙物環(huán)境下的多任務(wù)分配與路徑規(guī)劃

如圖7（a）所示，在多AUV系統(tǒng)的工作空間內(nèi)，有4個(gè)AUV需要訪問隨機(jī)分布的6個(gè)目標(biāo)點(diǎn)，藍(lán)色的線表示向量的切圓，紅色的線表示AUV的運(yùn)動(dòng)軌跡，綠色點(diǎn)是目標(biāo)。AUV受到運(yùn)動(dòng)學(xué)約束，具有初始速度向量，其最小轉(zhuǎn)彎半徑為R，初始速度向量和終止任務(wù)向量是預(yù)先隨機(jī)設(shè)定的。在完成任務(wù)分配后，每個(gè)AUV都能沿著Dubins路徑到達(dá)離各自最近的目標(biāo)點(diǎn)，而Dubins路徑已經(jīng)證明是在運(yùn)動(dòng)學(xué)約束條件下的最優(yōu)路徑。在圖7（b）中，4個(gè)AUV和6個(gè)目標(biāo)點(diǎn)在工作空間內(nèi)位置不變，只是在進(jìn)行任務(wù)分配時(shí)，路線被障礙物擋住路徑無法規(guī)劃時(shí)，此時(shí)則算法不選用當(dāng)前獲勝神經(jīng)元，而是針對次優(yōu)神經(jīng)元進(jìn)行路線規(guī)劃，重新分配任務(wù)，最后路徑規(guī)劃成功。仿真結(jié)果證明，障礙物的情況下該算法是有效的。

2．2 特殊情況下的多任務(wù)分配

當(dāng)獲勝AUV與任務(wù)點(diǎn)之間距離小于兩倍最小轉(zhuǎn)彎半徑時(shí)，無法規(guī)劃出Dubins路徑，算法則不選用該AUV為當(dāng)前獲勝神經(jīng)元。如圖8（a）所示，在多AUV系統(tǒng)的工作空間內(nèi)，有5個(gè)AUV需要訪問隨機(jī)分布的6個(gè)目標(biāo)。不考慮運(yùn)動(dòng)學(xué)約束時(shí)，采用SOM方法任務(wù)分配完成后，每個(gè)AUV都能沿著最優(yōu)路徑到達(dá)離各自最近的目標(biāo)點(diǎn)。圖8（a）中的任務(wù)分配為直線路徑，其中藍(lán)色的線表示路徑軌跡。所有的路徑都是直線，每條路徑都是最優(yōu)的。但是在實(shí)際條件下，完全使用直線路徑是不能實(shí)現(xiàn)的。圖9（b）的仿真結(jié)果是運(yùn)動(dòng)學(xué)約束下的最優(yōu)任務(wù)分配和路徑規(guī)劃，其中虛線的圓表示向量切圓，紅色的線表示Dubins路徑軌跡。對比圖8（a）和圖8（b）可以發(fā)現(xiàn)，最上方的任務(wù)點(diǎn)附近存在1個(gè)AUV，在直線路徑規(guī)劃中其被選為獲勝AUV進(jìn)行路徑規(guī)劃，而在Dubins路徑中則沒有被選為獲勝AUV。這是因?yàn)樵谠撎厥馇樾蜗?，獲勝AUV與任務(wù)點(diǎn)之間距離小于兩倍最小轉(zhuǎn)彎半徑，無法規(guī)劃出Dubins路徑。算法選取次優(yōu)神經(jīng)元進(jìn)行任務(wù)分配并作路徑規(guī)劃。

2．3 需要任務(wù)負(fù)載均衡的多任務(wù)分配

如圖9（a）所示，在多AUV系統(tǒng)的工作空間內(nèi)，有2個(gè)AUV需要訪問隨機(jī)分布的6個(gè)目標(biāo)。在沒有任務(wù)負(fù)載設(shè)置的情況下進(jìn)行的任務(wù)分配和路徑規(guī)劃，其中一個(gè)AUV訪問4個(gè)目標(biāo)點(diǎn)，另一個(gè)AUV訪問2個(gè)目標(biāo)點(diǎn)。圖9（b）則是根據(jù)2．2節(jié)中的負(fù)載均衡方法進(jìn)行算法調(diào)整和參數(shù)設(shè)置，在任務(wù)負(fù)載NMAX=3時(shí)進(jìn)行任務(wù)分配和路徑規(guī)劃，2個(gè)AUV各自訪問了3個(gè)任務(wù)點(diǎn)，能源的消耗相對平衡，從而證明了該算法的有效性。

圖7 障礙物環(huán)境下的多任務(wù)分配仿真Fig．7 Simulation of task assignment in the obstacle environment

圖8 特殊情況下的多任務(wù)分配仿真Fig．8 Simulation of task assignment in the special situation

圖9 任務(wù)負(fù)載均衡下的多任務(wù)分配Fig．9 Task assignment under load balancing

3 結(jié)論

本文研究了二維工作空間中多AUV系統(tǒng)在速度和最小轉(zhuǎn)向半徑受約束的條件下的多任務(wù)分配。首先，本文將SOM神經(jīng)網(wǎng)絡(luò)算法思想應(yīng)用到多AUV任務(wù)分配過程中。在此基礎(chǔ)上，考慮到AUV的實(shí)際運(yùn)動(dòng)學(xué)特性，將Dubins路徑結(jié)合到多任務(wù)分配算法當(dāng)中，解決了運(yùn)動(dòng)學(xué)約束的問題。最后，通過仿真實(shí)驗(yàn)進(jìn)行驗(yàn)證，考慮了障礙物環(huán)境下的任務(wù)分配、獲勝AUV與任務(wù)點(diǎn)之間距離小于兩倍最小轉(zhuǎn)彎半徑時(shí)的特殊情況，以及任務(wù)負(fù)載均衡下的任務(wù)分配。仿真結(jié)果表明，本文所提出的算法在多AUV任務(wù)分配中具有一定的特點(diǎn)和優(yōu)勢，這是傳統(tǒng)的多任務(wù)分配算法不能實(shí)現(xiàn)的。盡管如此，本論文的研究還停留在理論層面，多AUV系統(tǒng)本身動(dòng)力學(xué)特性復(fù)雜，工作所在的水下環(huán)境復(fù)雜多變，存在海流的影響等不確定因素，這也是未來的研究方向。

參考文獻(xiàn)：

［1］LUO Lingzhi，CHAKRABORTY N，SYCARA K．Distributed algorithm design for multi-robot generalized task assignment problem［C］／／Proceedings of the IEEE／RSJ International Conference on Intelligent Robots and Systems．Tokyo，Japan，2013:4765-4771．

［2］SARIEL S，BALCH T，STACK J．Distributed multi-AUV coordination in naval mine countermeasure missions［R］．Atlanta，Georgia:Georgia Institute of Technology，2006: 25-31．

［3］AKKIRAJU R，KESKINOCAK P，MURTHY S，et al．An agent-based approach for scheduling multiple machines［J］．Applied intelligence，2001，14（2）:135-144．

［4］曹宗華，吳斌，黃玉清，等．基于改進(jìn)蟻群算法的多機(jī)器人任務(wù)分配［J］．組合機(jī)床與自動(dòng)化加工技術(shù)，2013（2）: 34-37．CAO Zonghua，WU Bing，HUANG Yuqing，et al．The multi-robot task allocation study based on improved ant colony algorithm［J］．Modular machine tool＆automatic manufacturing technique，2013（2）:34-37．

［5］劉淑華，張崳，吳洪巖，等．基于群體智能的多機(jī)器人任務(wù)分配［J］．吉林大學(xué)學(xué)報(bào):工學(xué)版，2010，40（1）:123-129．LIU Shuhua，ZHANG Yu，WU Hongyan，et al．Multi-robot task allocation based on swarm intelligence［J］．Journal of Jilin University:engineering and technology edition，2010，40（1）:123-129．

［6］KOHONEN T．Analysis of a simple self-organizing process［J］．Biological cybernetics，1982，44（2）:135-140．

［7］ZHU A，YANG S X．A neural network approach to dynamic task assignment of multirobots［J］．IEEE transactions on neural networks，2006，17（5）:1278-1287．

［8］ZHU Anmin，YANG S X．An improved SOM-based approach to dynamic task assignment of multi-robots［C］／／Proceedings of the 8th World Congress on Intelligent Control and Automation．Jinan，China:IEEE，2010:2168-2173．

［9］HUANG Huan，ZHU Daqi，DING Feng．Dynamic task assignment and path planning for multi-AUV system in variable ocean current environment and movable targets［J］．Journal of intelligent＆robotic systems，2014，74（3／4）:999-1012．

［10］朱大奇，李欣，顏明重．多自治水下機(jī)器人多任務(wù)分配的自組織算法［J］．控制與決策，2012，27（8）:1201-1205，1210．ZHU Daqi，LI Xin，YAN Mingzhong．Task assignment algorithm of multi-AUV based on self-organizing map［J］．Control and decision，2012，27（8）:1201-1205，1210．

［11］ZHU Daqi，HUANG Huan，YANG S Y．Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace［J］．IEEE transactions on cybernetics，2013，43（2）:504-514．

［12］JIANG Kaichun，SENEVIRATNE L D，EARLES S W E．A shortest path based path planning algorithm for nonholonomic mobile robots［J］．Journal of intelligent and robotic systems，1999，24（4）:347-366．

［13］MANSOR M A，MORRIS A S．Path planning in unknown environment with obstacles using virtual window［J］．Journal of intelligent and robotic systems，1999，24（3）:235-251．

［14］冷靜，劉健，徐紅麗．實(shí)時(shí)避碰的無人水面機(jī)器人在線路徑規(guī)劃方法［J］．智能系統(tǒng)學(xué)報(bào)，2015，10（3）:343-348．LENG Jing，LIU Jian，XU Hongli．Online path planning of an unmanned surface vehicle for real-time collision avoidance［J］．CAAI transactions on intelligent systems，2015，10（3）:343-348．

［15］陳超，唐堅(jiān)，靳祖光，等．一種基于可視圖法導(dǎo)盲機(jī)器人路徑規(guī)劃的研究［J］．機(jī)械科學(xué)與技術(shù)，2014，33（4）:490-495．CHEN Chao，TANG Jian，JIN Zuguang，et al．A path planning algorithm for seeing eye robots based on V-Graph［J］．Mechanical science and technology for aerospace engineering，2014，33（4）:490-495．

［16］KHATIB O．Real-time obstacle avoidance for manipulators and mobile robots［J］．Robotics research，1986，5（1）: 90-98．

［17］SUGIHARA K．GA-based on-line path planning for SAUVIM［M］／／DEL POBIL A P，MIRA J，ALI M．Tasks and Methods in Applied Artificial Intelligence:Lecture Notes in Artificial Intelligence．Berlin Heidelberg:Springer，1998: 329-338．

［18］LI T H S，CHIANG M S，JIAN S S．Motion planning of an autonomous mobile robot by integrating GAs and fuzzy logic control［C］／／Proceedings of the 9th IEEE International Conference on Fuzz Systems．San Antonio，TX，USA: IEEE，2000:933-936．

［19］吳友謙，裴海龍．基于Dubins曲線的無人直升機(jī)軌跡規(guī)劃［J］．計(jì)算機(jī)工程與技術(shù)，2011，32（4）:1426-1429，1448．WU Youqian，QIU Hailong．Trajectory planning for unmanned helicopter based on Dubins curves［J］．Computer engineering and design，2011，32（4）:1426-1429，1448．

［20］梁勇，張友安，雷軍委．一種基于Dubins路徑的在線快速航路規(guī)劃方法［J］．系統(tǒng)仿真學(xué)報(bào)，2013，25（S1）: 291-296．LIANG Yong，ZHANG You’an，LEI Junwei．New method of online fast path planning based Dubins path［J］．Journal of system simulation，2013，25（S1）:291-296．

Task assignment for a multi-AUV system under kinematic constraint

LI Xin，ZHU Daqi，XU Keang
（Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai 201306，China）

To solve the task assignment and path planning problems of a system with multiple autonomous underwater vehicles（AUVs），a multi-AUV task assignment algorithm under kinematic constraints is proposed，which combines the Dubins Path algorithm with an improved SOM（self-organizing map）neural network algorithm．The tasks were first assigned by the SOM neural network．If there were kinematic constraints or obstacles that led to the failure of Dubins path-planning，task re-assignment was implemented until the AUVs reached all the target points．Simulation results show that the algorithm can effectively accomplish task assignments for a multi-AUV system under kinematic constraints．

autonomous underwater vehicles（AUV）；multi-task assignment；path planning；self-organizing map；Dubins Path；kinematical constraints；workload balance

10．11990／jheu．201510019

http：／／www．cnki．net／kcms／detail／23．1390．u．20160928．0936．004．html

TP27

A

1006-7043（2016）12-1638-07

李欣，朱大奇，徐珂昂．運(yùn)動(dòng)學(xué)約束條件下多AUV任務(wù)分配算法［J］．哈爾濱工程大學(xué)學(xué)報(bào)，2016，37（12）:1638-1644．

2015-10-12．

2016-09-28．

國家自然科學(xué)基金項(xiàng)目（51279098）；上海市科委創(chuàng)新行動(dòng)計(jì)劃（14JC1402800，13510721400）．

李欣（1985-），男，工程師，博士研究生；

朱大奇（1964-），男，教授，博士生導(dǎo)師．

朱大奇，E-mail:zdq367＠aliyun．com．

LI Xin，ZHU Daqi，XU Keang．Task assignment for a multi-AUV system under kinematic constraint［J］．Journal of Harbin Engineering University，2016，37（12）:1638-1644．