多移動機器人系統協調控制算法設計

查延麟

（1.中國科學院上海微系統與信息技術研究所，上海200050；2.上海科技大學信息學院，上海201210；3.中國科學院大學北京100049）

隨著機器人技術的快速發展，移動機器人控制和路勁規劃問題是當前的熱門研究方向之一[1-3]。同時，多移動機器人協作控制問題也逐漸引起了越來越多學者的關注[4-6]。當前已經有很多方法可以實現對此類系統的控制[7-8]，其中，分布式模型預測控制（Distributed Model Predictive Control，DMPC）是一個熱門的研究方向[9-11]。通過對每個子系統未來狀態的預測并進行規劃，分布式模型預測控制方法得以在不引發機器人之間的沖突的前提下，引導每個機器人完成各自指定的任務。

為了協調多個機器人，機器人之間需要進行通信以避免沖突，而潛在的通信延遲和數據包丟失會導致包括機器人碰撞在內的惡劣后果[13-14]。為了處理這類問題，文獻[15]提出了一種量化通信方案。這個方案通過把通信信息量化為整數，以降低信息準確度為代價降低了傳輸負載。除此之外，機器人系統中存在的其他不確定因素也需要被納入考慮。一類被稱為集合計算的方法可以實現對系統不確定性的建模和處理[16-17]。

文中結合量化通信和集合計算方法，提出了基于DMPC的魯棒多機器人協調方案。這一方法不僅降低了傳輸負載，同時通過把包括網絡延遲，傳感器測量噪聲在內的不確定因素納入了考慮，保證了多移動機器人系統的魯棒性。

1 問題描述

本文考慮如下由p個移動機器人構成的多機器人系統，每個機器人的動力方程記作

這里xp∈XXp表示機器人的狀態量；up∈UUp表示機器人的控制量；wp∈WWp表示機器人的不確定參數；fp:Xp×UUp→XXp以及Gp:Xp×UUp→XXp×WWp為李普希茨連續（Lipschitz-continuous）函數；集合Xp∈?nx,Up∈?nu,Wp∈?nw分別表示機器人可能的狀態集、控制集、以及不確定集；nx,nu,nw分別為狀態量，控制量和不確定量的維數。

我們把機器人前k時刻的狀態序列記作xp(?)=(xp(0),…,xp(k))，把控制序列記做up(?)=(up(1),…,up(k))，以及不確定參數序列記做wp(?)=(wp(1),…,wp(k))。同時，為了研究最糟參數情況下的系統行為，我們定義，對于給定初始狀態和控制序列up(?)，機器人在第n時刻所有可能的系統狀態構成可達集Xp?XXp：

除此之外，我們還假設每個機器人都可以在任何一個系統狀態下被停下來，即：

以及所有的機器人都在共同的物理空間中運動，這樣每個機器人的狀態量之間都存在有耦合約束條件。為了避免違背這些約束條件，實現整個多機器人系統的協調工作，我們采用分布式模型預測控制策略，來對整個多機器人系統進行規劃和控制。

具體而言，我們考慮以下魯棒分布式模型預測控制問題

其中目標函數lp:XXp×UUp→?正定且滿足

本文的目標是結合區間算術去計算Xp，以及利用量化通信方法以較低的傳輸負載獲取Cp，設計針對多移動機器人系統的魯棒分布式模型預測控制算法，來實現對這一系統的協調控制。

2 區間算術

為了求解魯棒模型預測控制問題（1），我們利用區間算術（Interval Arithmetic，IA）方法計算可達集Xp。區間算術是定義在區間集合II? XX上的一元或二元運算。對于區間集合II的元素，其中上界和下界滿足，它們把這一區間參數化成為兩個系數，我們用表示區間X。兩個區間X,Y之間的加法被閔可夫斯基和定義為：

即Z=X+Y被自然地定義為：

并且相應地，負區間-X被定義為：

并導出減法Z=X-Y為:

類似地，乘法Z=X×Y被定義為

以及除法

當且僅當0?Y。

由此，如式（4）～（7）所示，區間之間的四則運算被自然地定義為其參數之間的運算。此外，基本初等函數（冪、指、對、三角函數）也可以被擴展到區間集合上，詳見文獻[16]。

由于初等函數是由基本初等函數和四則運算的有限次復合得到，因此基于式（4）～（7）所定義的四則運算以及文獻[16]中的基本初等函數，區間算術方法可以用來計算或逼近標量值初等函數的值域。

這樣，若函數fp,Gp的每一個分量都是初等函數，機器人p的可達集Xp可以由區間算術的方法來迭代地逼近：

3 量化通信

為了降低通信負載，我們引入量化通信方法。具體而言，我們把機器人的狀態空間XX網格化。我們定義量化函數q:X→?nx，把任意一個物理位置x∈XX映射為它所在的網格索引G∈?nx。

利用量化函數q，我們可以定義每個機器人有待廣播的信息為:

即每個機器人在時刻n向其他的機器人廣播自己未來N步內將要經過的格子及相應的時刻Ip(n)。我們把機器人p所接收到的廣播信息：

稱為“被預定的格子”。這些“被預定的格子”構成了魯棒分布式模型預測控制問題（3）中的耦合約束項CP。

利用量化函數，每個機器人在第n步時把預測到未來第k步的可達集Xp(k),k∈{0 ,1,…,N}量化為Xp(k)所占據的全部格子的上下界。并把這上下界和相應的每一個時刻k打包作為廣播信息Ip發送給其他機器人，如圖1所示。

圖1 網格化的可達集

圖1實線所圍成的區域是機器人p預測的第k步可達集Xp，虛線所圍成的區域是由區間算術計算出的對Xp的逼近，深色和全部陰影區域分別是被量化的Xp和，格子(2 ,2)和(1 5 ,8)以及時刻k被打包封裝進待廣播的數據Ip。

由此可見，利用區間算術和量化通信方法，不僅每個機器人的不確定因素所導致的全部可能結果被作為可達集考慮在內，并且這些可達集被以極低的傳輸負載廣播給其他的機器人。

4 魯棒分布式模型預測控制算法

結合區間算術和量化通信，我們提出針對多移動機器人系統的魯棒分布式模型預測控制算法（RobustDistributedModelPredictiveControl，RDMPC），其步驟可總結如下：

1）設定全部p個機器人的可行的初始點；

2）設定預測時間窗N

4）所有機器人依次廣播Ip(0)；

5）設定當前時刻n=1；

6）每個機器人p依次接收被占據的網格信息ip；

7）利用區間算術和優化問題求解器，每個機器人近似求解魯棒模型預測控制問題（3），獲得控制序列up(?)；

8）每個機器人依次執行up(0)，并廣播Ip(n)；

9）設定當前時刻n=n+1，跳轉至步驟6）。

當假設（2）成立，求解問題（3）可以得到至少一個可行解，這一可行解使得機器人維持上一狀態不變，由此可以得出，這一算法總能找到可行解。詳細證明過程類似于文獻[14]，它證明了這一算法對于相對應的標稱系統（nominal system）的可解性。

5 案例研究：四機器人路口調度

本文考慮平面移動的四機器人的路口調度問題，其中路口區域為Xp?[-6(m),6(m)]2，控制集和不確定量集分別

以及目標函數:

這里，我們設定預測窗口長度為N=4，網格尺寸c=0.5(m)。

此外，我們設定每個機器人各自的出發點和目標位置如表1所示。

表1 機器人初始位置和目標位置

這一案例的數值仿真由Julia編程語言實現，并采用COBYLA[18]作為優化求解器。仿真結果如圖2所示。

圖2 四機器人運動路徑

在圖2中，四條深淺不一帶圓點的實線表示4個機器人的運動軌跡，陰影區域表示每個機器人預定的格子。所有被同一個機器人預定的格子構成一個管形區域，包含了這個機器人所有可能的軌跡。從圖上我們可以看出，在時刻n=8之前，每個機器人都距離其他機器人較遠，不需要考慮避開其他機器人，也就因此分別朝著他們的目標點直線前進；從時刻n=9到時刻n=10，這些機器人在區域的中央部分相遇，部分機器人自發的停下來以讓其他的機器人通過。這是由于當預測窗口N不夠長，機器人不足以在規劃出能直接繞開其他機器人的路徑。從時刻n=11以后，全部的4個機器人保持直線運動直到他們接近到目標點附近（在預測窗口之內可以到達目標點），朝向目標點運動并抵達。這里，機器人繞開彼此后，先保持直線運動而不是朝向目標點運動的原因是，因為控制量的約束是，即取|up,1|=|up,2|=0.5(m/s)可以最小化目標函數lp；而隨后，當機器人可以在一個預測窗口內到達目標點時，只有朝向目標點運動才能最小化目標函數。由此，這一案例驗證了RDMPC算法的有效性。

6 結論

本文針對多機器人協調問題，提出了一種結合了區間算術和量化通信的魯棒分布式模型預測控制策略。這一方法首先利用區間算數，將每一個機器人不確定因素分別考慮在內，預測每一個機器人所有可能的軌跡，保證了多機器人系統的魯棒性。其次，利用量化通信，把待傳送的機器人位置數據網格化為格子的索引，大大降低了機器人之間的通信負載，并以四機器人路口調度問題為例，驗證了RDMPC算法的有效性。