基于虛擬結構優化模型的多機器人編隊形成方法

芮可人 王麗華 謝能剛

摘 ?要：虛擬結構法可以使多機器人保持高精度的隊形編隊，本文提出一種基于進化算法的虛擬結構優化模型，以虛擬隊形中心坐標和第一個預定節點的方向角為設計變量，通過進化迭代得到最優的期望隊形和各機器人與固定節點的分配方法。仿真結果表明，該方法能夠讓多機器人形成期望的正n邊形編隊和直線型編隊。

關鍵詞：多機器人編隊;虛擬結構;進化算法

中圖分類號：TP242.6 ? ? 文獻標識碼：A 文章編號：2096-4706（2019）18-0056-03

Abstract：The virtual structure approach can guarantee the high-precision formation of multi-robots. This paper proposes a virtual structure optimization model based on evolutionary algorithm. The center coordinates of the virtual formation and the orientation angle of the first predetermined node are used as the design variables. The evolutionary iteration yields the optimal expected formation and the allocation method between robot and fixed node. The simulations demonstrate that this approach is capable of achieving regular n polygon formation and linear formation for multi-robot.

Keywords：multi-robot formation;virtual structure;evolutionary algorithm

0 ?引 ?言

機器人編隊是多機器人協作的基礎，編隊體現了機器人通過傳感器感知外部環境，并依靠這些信息完成機器人之間、機器人與外部環境之間的互動能力。這些互動使得機器人之間保持固定的方位和距離，從而讓整個機器人編隊形成一個整體。目前采用較多的編隊算法有：領航跟隨法[1]、虛擬結構法、人工勢場法和基于行為法等。其中虛擬結構法可以滿足精度較高的隊形控制要求，其基本思想是將一隊機器人看作剛體結構中的質點，在剛體運動過程中，質點的相對位置保持固定，即多機器人編隊在運動過程中保持固定隊形。此前，M.Anthony和Kar-Han Tan提出虛擬結構的概念，結合機器人運動學給出機器人保持結構隊形行進的控制律。Magnus Egerstedt和Xiaoming Hu結合虛擬領航法和虛擬結構法，通過機器人分別跟蹤自身的參考點，將機器人協調問題解耦為一個路徑規劃問題和一個跟蹤問題。Norman和Hugh采用虛擬結構法和同步技術相結合研究飛行器的隊形控制問題，增強了隊形控制能力和效率。Wei Ren提出一種分布式虛擬結構的多飛行器編隊算法，相鄰飛行器之間通過通信得到同步協調向量并據此得到在虛擬結構中的對應位置。在目前的文獻資料中，一般在多機器人分布的區域內隨機指定一個點或者以初始分布的形心作為期望隊形的中心點，并以此中心點生成虛擬結構。本文采取進化算法優化虛擬結構，得到期望隊形中心點的最優位置和各機器人與固定節點的分配方法。

1 ?多機器人形成期望編隊的計算模型

1.1 ?共同知識

（1）任一機器人都知道其他機器人的位置（通過感知和通訊手段獲得）。

（2）所有機器人都知道期望的編隊隊形。

（3）所有機器人都知道編隊規則。

1.2 ?基于虛擬結構優化模型的編隊規則

1.2.1 ?優化模型

假設參與編隊的機器人數量為n，n個機器人的初始位置分別為（x0i，y0i）（i=1，2，…，n）。期望隊形取兩種：邊長為d的正n邊形和間距為d的直線隊形。

2 ?仿真實驗

為了驗證本文算法的有效性，設計了以下仿真實驗：機器人隨機分布在仿真環境為30×30的矩形區域內，任務要求多移動機器人在工作環境中通過進化算法得到期望隊形位置和最佳分配策略。進化算法的參數：種群數量L=1000，最大進化代數kmax=120，收斂判定小數ε=0.0001，正n邊形的邊長d=6。

2.1 ?期望隊形為正n邊形

機器人數量為5時，圖3為優化的迭代過程，可以看到，隨著進化代數的增加，目標函數值形成的柱體高度減小，位置下降，這表示隊形中心位置坐標（xc，yc）和第一個預定點的方向角φ逐漸趨于最優值。根據進化算法得到的最優值，依次生成最優隊形的節點以及各節點與各機器人之間的對應關系，如圖4所示，實心三角形符號▲表示進化過程終止時最優的隊形中心位置?！鸨硎緳C器人的初始位置，*表示機器人期望隊形固定節點的位置，相同顏色的○和*表示每個機器人所對應的隊形點。

2.2 ?期望隊形為直線隊形

以n=5的直線隊伍為例，隊形中相鄰機器人的間距d=5，圖5表示優化的迭代過程，圖6為最終的直線隊形及各節點與各機器人之間的對應關系。

3 ?結 ?論

本文針對多機器人編隊任務，提出采用進化算法得到最優虛擬隊形中心位置和第一個隊形點的方位角，根據隊形的形成規則得到隊形固定節點。仿真結果表明，算法可以得到最后的收斂解。同時本文提出一種機器人到達固定節點的分配方法，使得每個機器人到達其預定節點所移動的距離盡可能相等且保證整個機器人系統運動的距離較短。

參考文獻：

[1] 董勝龍，陳衛東，席裕庚.多移動機器人編隊的分布式控制系統 [J].機器人，2000，22（6）：433-438.

[2] 謝能剛，孫林松，方浩.基于進化策略的拱壩體型優化設計 [J].水利水運工程學報，2006.3（1）：24-29.

作者簡介：芮可人（1993.08-），男，漢族，安徽安慶人，碩士研究生，研究方向：移動機器人算法。