查延麟

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以及除法

當(dāng)且僅當(dāng)0?Y。

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

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

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

3 量化通信

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

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

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

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

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

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

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

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

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

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

1）設(shè)定全部p個(gè)機(jī)器人的可行的初始點(diǎn)；

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

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

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

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

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

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

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

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

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

本文考慮平面移動(dòng)的四機(jī)器人的路口調(diào)度問(wèn)題，其中路口區(qū)域?yàn)閄p?[-6(m),6(m)]2，控制集和不確定量集分別

以及目標(biāo)函數(shù):

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

此外，我們?cè)O(shè)定每個(gè)機(jī)器人各自的出發(fā)點(diǎn)和目標(biāo)位置如表1所示。

表1 機(jī)器人初始位置和目標(biāo)位置

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

圖2 四機(jī)器人運(yùn)動(dòng)路徑

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

6 結(jié)論

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