運動學約束條件下多AUV任務分配算法

李 欣，朱大奇，徐珂昂

（上海海事大學水下機器人與智能系統實驗室，上海201306）

運動學約束條件下多AUV任務分配算法

李 欣，朱大奇，徐珂昂

（上海海事大學水下機器人與智能系統實驗室，上海201306）

針對運動學約束的自治水下機器人（AUV）任務分配與路徑規劃問題，本文以多個AUV組成的系統為研究對象，將Dubins Path算法與改進的自組織映射（SOM）神經網絡算法相結合，提出一種在運動學約束條件下多AUV任務分配與路徑規劃算法。通過SOM神經網絡方法對多AUV進行任務分配后，若存在運動學約束或障礙物而導致無法進行Dubins路徑規劃時，則重新進行任務分配，直到所有目標點都有AUV到達。仿真結果表明該算法能夠有效完成運動學約束條件下多AUV的任務分配。

自治水下機器人；多任務分配；路徑規劃；自組織映射；Dubins Path；運動學約束；負載均衡

多自治水下機器人（autonomous underwater vehicle，AUV）系統的任務分配算法涵蓋兩方面:任務分配和路徑規劃，即指依據一定的算法控制一組AUV，各自沿著運動學約束條件下的優化路徑到達目標的技術。其中任務分配是指將任意數目的目標分配給多AUV系統，在保證所有目標被遍歷的前提下，整個多AUV系統的代價最小［1］。路徑規劃技術是指在全局任務分配后，針對單一AUV的路徑規劃方法。

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

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

本文研究二維環境中運動學約束條件下的多AUV系統的任務分配和路徑規劃問題，并考慮了障礙物等干擾因素。通過將Dubins Path算法與改進的自組織特征映射（SOM）神經網絡算法相結合，本文提出一種新型的任務分配與路徑規劃算法。

1 運動學約束下任務分配算法設計

本文針對多AUV、多目標點，采用一種基于SOM神經網絡和Dubins路徑的方法，處理多AUV系統的多任務分配及相應的路徑規劃問題。在該方法中，AUV運動規劃集成在任務分配當中，從而一旦總體任務給出，AUV就可以開始運動。此外，多AUV系統可以自動安排總任務，并根據環境的變化動態實時調整運動規劃。

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

1．1 SOM神經網絡

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

圖1 AUV編隊與虛擬結構的位置關系Fig．1 Position relationship between AUV formation and virtual structure

由于自組織映射算法是一種無導師的聚類法，它能將任意維輸入模式在輸出層映射成一維或二維離散圖形，具有聚類功能、自組織功能、自學習功能。SOM神經網絡采用的算法是在“勝者為王”（winnertake-all，WTA）學習規則基礎上加以改進的。這種競爭學習規則的生理學基礎是神經細胞的側抑制現象，當一個神經細胞興奮后，會對其周圍的神經細胞產生抑制作用。

SOM神經網絡的學習按如下步驟進行:

1）初始化，即對輸出層各權向量賦值并進行歸一化處理；

2）接受輸入，即從訓練集中隨機取一個輸入模式并進行歸一化處理；

3）尋找獲勝節點，按照競爭規則計算；

4）定義優勝鄰域，確定t時刻的權值調整域，一般初始鄰域較大，訓練過程中優勝鄰域隨訓練時間收縮；

5）調整權值，對優勝鄰域內的所有節點調整權值；

6）結束判定，當學習率小于最小學習率時，訓練結束，不滿足結束條件時，轉到2）繼續進行。

1．2 SOM應用于多AUV系統

假定在一個有限的工作區域內分布著一組AUV，同時在此區域分布著任意數目的目標。每個目標都需要一個AUV在該點完成特定的任務。對于每個AUV來講，其代價是由從起始位置坐標點運動到目標位置坐標點所移動的距離來衡量。總代價定義為所有單個AUV代價的總和。當所有目標點都被訪問過一次后，任務完成。這種訪問目標點的過程與SOM算法是一致的［10］

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

圖2 多AUV系統的工作區域Fig．2 Workspace of multi-AUV system

在該工作空間內，有4個AUV需要遍歷5個目標，同時存在1個障礙物。基于兩點之間直線最短的原理，認為AUV的初始位置坐標到目標點的位置坐標之間的直線為最優路徑。

單純依靠目標點坐標與AUV坐標最近原則分配任務，有時可能出現某個AUV被分配太多任務的現象，使其在動力耗盡前還無法完全到達所有分配的目標，而另外的AUV卻得不到任務目標；以及由于障礙物而使一開始分配的任務在實際規劃路徑中無法完成。為了保證每個AUV攜帶的能源得到最大限度的利用，同時避免AUV在向目標運動的過程中因為能源不足而停止，所以在算法中要考慮AUV的負載均衡。假定，AUV具有相同的水下巡航能力且攜帶同樣的能源，所能行走的距離相同。在算法設計中，根據AUV個數，在分配任務前初始化矩陣，矩陣階數與AUV數量一致。在算法中，首先計算N=NT／NR，其中，NT是目標點數量，NR是AUV數量，則任務負載的上限設置為

當本次任務執行后超過任務數量上限時，則不分配該任務給獲勝AUV，選擇次優AUV執行任務。將AUV系統的負載均衡考慮進SOM任務分配算法是在文獻［10-11］的基礎上對傳統神經網絡的有效改進，使其更適合多AUV多任務分配的實際情況。

1．3 Dubins路徑規劃算法

實現二維環境下的多AUV系統的任務分配與路徑規劃主要運用了兩個算法:改進的自組織神經網絡算法（SOM）和Dubins Path算法。其中，自組織神經網絡算法用來實現多目標的分配策略，包括神經網絡的輸入層和輸出層定義、領域函數的確定以及權值的更新等幾個過程；Dubins Path算法用于實現運動學約束下AUV到目標點的最短有效的路徑規劃。

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

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

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

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

圖3 圓與切線的關系Fig．3 Circles and the corresponding tangents

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

當初始向量在0到π之間，通過比較圓心O1和起點P1，若O1的橫坐標大于P1的橫坐標，則說明圓O1為順圓，反之則為逆圓。當為順圓時，以P1為起點沿圓弧P1Q1順時針運動；當為逆圓時，以P1為起點沿圓弧P1Q1逆時針運動。當初始向量在π到2π之間，通過比較圓心O2和起點P2，若O2的橫坐標大于P2的橫坐標，則說明圓O1為逆圓，反之則為順圓。當為順圓時，以P2為起點沿圓弧P2Q2順時針運動；當為逆圓時，以P2為起點沿圓弧P2Q2逆時針運動。

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

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

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

2 仿真驗證

為了驗證該算法在解決二維工作空間內多AUV多任務分配與相應路徑規劃問題的有效性，仿真在MATLAB R2011a上實現。

2．1 障礙物環境下的多任務分配與路徑規劃

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

2．2 特殊情況下的多任務分配

當獲勝AUV與任務點之間距離小于兩倍最小轉彎半徑時，無法規劃出Dubins路徑，算法則不選用該AUV為當前獲勝神經元。如圖8（a）所示，在多AUV系統的工作空間內，有5個AUV需要訪問隨機分布的6個目標。不考慮運動學約束時，采用SOM方法任務分配完成后，每個AUV都能沿著最優路徑到達離各自最近的目標點。圖8（a）中的任務分配為直線路徑，其中藍色的線表示路徑軌跡。所有的路徑都是直線，每條路徑都是最優的。但是在實際條件下，完全使用直線路徑是不能實現的。圖9（b）的仿真結果是運動學約束下的最優任務分配和路徑規劃，其中虛線的圓表示向量切圓，紅色的線表示Dubins路徑軌跡。對比圖8（a）和圖8（b）可以發現，最上方的任務點附近存在1個AUV，在直線路徑規劃中其被選為獲勝AUV進行路徑規劃，而在Dubins路徑中則沒有被選為獲勝AUV。這是因為在該特殊情形下，獲勝AUV與任務點之間距離小于兩倍最小轉彎半徑，無法規劃出Dubins路徑。算法選取次優神經元進行任務分配并作路徑規劃。

2．3 需要任務負載均衡的多任務分配

如圖9（a）所示，在多AUV系統的工作空間內，有2個AUV需要訪問隨機分布的6個目標。在沒有任務負載設置的情況下進行的任務分配和路徑規劃，其中一個AUV訪問4個目標點，另一個AUV訪問2個目標點。圖9（b）則是根據2．2節中的負載均衡方法進行算法調整和參數設置，在任務負載NMAX=3時進行任務分配和路徑規劃，2個AUV各自訪問了3個任務點，能源的消耗相對平衡，從而證明了該算法的有效性。

圖7 障礙物環境下的多任務分配仿真Fig．7 Simulation of task assignment in the obstacle environment

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

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

3 結論

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

參考文獻：

［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］．組合機床與自動化加工技術，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］．吉林大學學報:工學版，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］．控制與決策，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］冷靜，劉健，徐紅麗．實時避碰的無人水面機器人在線路徑規劃方法［J］．智能系統學報，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］陳超，唐堅，靳祖光，等．一種基于可視圖法導盲機器人路徑規劃的研究［J］．機械科學與技術，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］．計算機工程與技術，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路徑的在線快速航路規劃方法［J］．系統仿真學報，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

李欣，朱大奇，徐珂昂．運動學約束條件下多AUV任務分配算法［J］．哈爾濱工程大學學報，2016，37（12）:1638-1644．

2015-10-12．

2016-09-28．

國家自然科學基金項目（51279098）；上海市科委創新行動計劃（14JC1402800，13510721400）．

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

朱大奇（1964-），男，教授，博士生導師．

朱大奇，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．