多移動機器人系統(tǒng)協(xié)調(diào)控制算法設(shè)計

查延麟

（1.中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所，上海200050；2.上?？萍即髮W(xué)信息學(xué)院，上海201210；3.中國科學(xué)院大學(xué)北京100049）

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

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

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

1 問題描述

本文考慮如下由p個移動機器人構(gòu)成的多機器人系統(tǒng)，每個機器人的動力方程記作

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

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

除此之外，我們還假設(shè)每個機器人都可以在任何一個系統(tǒng)狀態(tài)下被停下來，即：

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

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

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

本文的目標是結(jié)合區(qū)間算術(shù)去計算Xp，以及利用量化通信方法以較低的傳輸負載獲取Cp，設(shè)計針對多移動機器人系統(tǒng)的魯棒分布式模型預(yù)測控制算法，來實現(xiàn)對這一系統(tǒng)的協(xié)調(diào)控制。

2 區(qū)間算術(shù)

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

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

并且相應(yīng)地，負區(qū)間-X被定義為：

并導(dǎo)出減法Z=X-Y為:

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

以及除法

當且僅當0?Y。

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

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

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

3 量化通信

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

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

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

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

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

圖1 網(wǎng)格化的可達集

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

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

4 魯棒分布式模型預(yù)測控制算法

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

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

2）設(shè)定預(yù)測時間窗N

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

5）設(shè)定當前時刻n=1；

6）每個機器人p依次接收被占據(jù)的網(wǎng)格信息ip；

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

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

9）設(shè)定當前時刻n=n+1，跳轉(zhuǎn)至步驟6）。

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

5 案例研究：四機器人路口調(diào)度

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

以及目標函數(shù):

這里，我們設(shè)定預(yù)測窗口長度為N=4，網(wǎng)格尺寸c=0.5(m)。

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

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

這一案例的數(shù)值仿真由Julia編程語言實現(xiàn)，并采用COBYLA[18]作為優(yōu)化求解器。仿真結(jié)果如圖2所示。

圖2 四機器人運動路徑

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

6 結(jié)論

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