許元云，何 明，劉錦濤，周 波，楊 鋮

中國(guó)人民解放軍陸軍工程大學(xué) 指揮控制工程學(xué)院，南京 210007

1 引言

動(dòng)物集群經(jīng)常表現(xiàn)出有趣的集體行為[1]：它們?cè)谟邢迺r(shí)間內(nèi)建立有序的結(jié)構(gòu)而不會(huì)發(fā)生碰撞，也可以對(duì)環(huán)境變化迅速做出反應(yīng)，例如突然出現(xiàn)捕食者或障礙物。這些生物行為非常復(fù)雜，相關(guān)研究人員通過(guò)引入多智能體，并用抽象的數(shù)學(xué)形式模擬這些動(dòng)物行為。多智能體不光用于解釋這些行為，同時(shí)由于其擴(kuò)展性強(qiáng)、適應(yīng)性強(qiáng)、復(fù)雜性低等優(yōu)點(diǎn)，廣泛應(yīng)用于航天航空控制、交通控制和能源控制等領(lǐng)域[2]。

通常，復(fù)雜網(wǎng)絡(luò)可能包含大量節(jié)點(diǎn)，通過(guò)在網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)上添加控制器來(lái)同步復(fù)雜網(wǎng)絡(luò)既不實(shí)際也不經(jīng)濟(jì)，解決該問(wèn)題的有效方法是僅在一小部分網(wǎng)絡(luò)節(jié)點(diǎn)上添加控制器，這種方法稱為牽制控制。由于牽制控制的優(yōu)越性，文獻(xiàn)[3-4]就多智能體牽制控制進(jìn)行了深入的研究。

避障是多智能體能夠適應(yīng)復(fù)雜環(huán)境并順利完成任務(wù)的必要條件之一。目前多智能體避障算法包括人工勢(shì)力場(chǎng)法[5-6]、模糊控制法[7]、幾何法[8]和強(qiáng)化學(xué)習(xí)[9]等，人工勢(shì)場(chǎng)法在障礙物和智能體之間建立排斥力場(chǎng)來(lái)避免智能體與障礙物的碰撞，這種方法簡(jiǎn)單靈活，通常比其他避障方法更高效[10]，最早由Khatib[5]引入到機(jī)器人避障中。Olfati-Saber 算法[6]中的β-智能體是一個(gè)典型的基于人工勢(shì)力場(chǎng)的多智能體避障算法，這個(gè)算法有兩個(gè)部分構(gòu)成，距離項(xiàng)部分是構(gòu)建排斥力場(chǎng)來(lái)避免智能體與障礙物之間的碰撞，速度項(xiàng)部分是引導(dǎo)智能體沿著障礙物切線方向運(yùn)動(dòng)。Sakai等人[11]不區(qū)分障礙物和智能體，將感知的對(duì)象全都視為障礙物，使用β-智能體完成了蜂擁控制和避障，劉嬋等人[12]介紹了Olfati-Saber 算法，并在多障礙物環(huán)境中進(jìn)行了實(shí)驗(yàn)仿真。同其他人工勢(shì)力場(chǎng)法一樣，β-智能體也存在局部最小值問(wèn)題和非最佳路徑問(wèn)題，后續(xù)的改進(jìn)主要集中在這兩點(diǎn)。在避免陷入最小極值點(diǎn)方面，Li等人[13]提出了一種新穎的障礙物幾何表示規(guī)則以填充障礙物的非凸區(qū)域，高晶英[14]構(gòu)建了兩個(gè)β-智能體，其中一個(gè)與障礙物平面切線方向垂直，避免陷入最小值，Wu等人[15]將使用流體力場(chǎng)替代了智能體與障礙物之間的人工勢(shì)力場(chǎng)。為解決非最佳路徑問(wèn)題，Hu等人[16]結(jié)合空間幾何知識(shí)，確定圓錐體的最短路徑為β-智能體軌跡從而實(shí)現(xiàn)圓錐體障礙物的快速避障，Wang 等人[17]結(jié)合幾何法的碰撞錐檢測(cè)方法[18-19]，根據(jù)α-智能體、β-智能體和γ-智能體三者的速度和位置關(guān)系確定單個(gè)智能體的速度大小和方向，使得智能體能夠快速通過(guò)障礙物，但注意到此方法未涉及智能體之間的避免碰撞問(wèn)題，Zhao等人[20]通過(guò)智能體與其鄰接節(jié)點(diǎn)交互障礙物信息，將局部避障算法改進(jìn)為全局避障算法，有效地避免了局部最小值問(wèn)題，同時(shí)更好地實(shí)現(xiàn)了多智能體的一致性，但算法復(fù)雜度有所增加。

本文基于Olfati-Saber 算法提出了一種多智能體自適應(yīng)避障控制算法，算法基于角度比較的碰撞錐檢測(cè)方法引出智能體的避障系數(shù)，并結(jié)合牽制控制輸入完成多智能體的快速避障。證明了在本算法作用下所有智能體最終會(huì)避開(kāi)障礙，避免碰撞并最終達(dá)到一致。仿真實(shí)驗(yàn)表明在圓形障礙物和墻形障礙物環(huán)境中基于本算法多智能體避障所用時(shí)間較少，驗(yàn)證了本算法的有效性。

2 多智能體建模和障礙物表示

考慮m個(gè)智能體工作在n維歐幾里德空間上，它們的動(dòng)力學(xué)方程可以寫為：

其中，qi,pi,ui∈?n表示多智能體i的位置向量、速度向量和加速度向量。

t時(shí)刻多智能體構(gòu)成的無(wú)向圖G(t)由節(jié)點(diǎn)和邊組成，其中節(jié)點(diǎn)集合表示為V={1 ,2,…,m} ，邊的集合表示為設(shè)r是α-智能體的感知半徑，期望距離為dα，則多智能體的鄰域?yàn)椋?/p>

參照文獻(xiàn)[6]，定義β-智能體構(gòu)成的集合為V′={1 ′,2′,…,m′} ，則β-智能體鄰域?yàn)椋?/p>

其中，r′是α-智能體感知β-智能體的距離，期望距離為dβ，這里假設(shè)r=r′。

圓形障礙物的β-智能體如圖1（a）所示，其數(shù)學(xué)定義為：

其中，yk,Rk分別是障礙物的圓心位置和半徑；μ=。

墻形障礙物的β-智能體如圖1（b）所示，其數(shù)學(xué)定義為：

其中，yk是一個(gè)固定點(diǎn)，這里假設(shè)為墻形障礙物線段的中心，ak是墻形障礙物的單位法向量。

圖1 β-智能體示意圖

3 自適應(yīng)快速避障控制算法

3.1 問(wèn)題提出與算法設(shè)計(jì)

一個(gè)基于Olfati-Saber算法的避障實(shí)例如圖2所示，可以看出當(dāng)整個(gè)網(wǎng)絡(luò)經(jīng)過(guò)半圓后時(shí)在β-智能體的速度項(xiàng)作用下仍然繞著圓運(yùn)動(dòng)，這增加了智能體繞過(guò)障礙物的時(shí)間，降低了多智能體的避障效率。為避免這類現(xiàn)象的發(fā)生，提出一種自適應(yīng)避障系數(shù)gi(t),gi(t)在智能體遇到障礙物以后調(diào)節(jié)智能體是否受到β-智能體速度項(xiàng)的影響，再結(jié)合牽制控制輸入完成多智能體的避障。

圖2 一個(gè)多智能體避障實(shí)例

3.2 避障系數(shù)

避障系數(shù)gi(t)的取值根據(jù)碰撞錐檢測(cè)方法來(lái)確定，本文通過(guò)角度比較來(lái)完成碰撞錐檢測(cè)。當(dāng)智能體的速度和碰撞錐相交時(shí)，首要任務(wù)是避開(kāi)障礙物，需要β-智能體速度項(xiàng)的引導(dǎo)；當(dāng)智能體運(yùn)動(dòng)到速度方向和碰撞錐不相交時(shí)，需要考慮多智能體的一致性問(wèn)題，而β-智能體速度項(xiàng)與智能體的平均速度、虛擬領(lǐng)導(dǎo)者速度都無(wú)關(guān)，此時(shí)可以通過(guò)調(diào)節(jié)gi(t)排除β-智能體速度項(xiàng)的影響。

圓形障礙物環(huán)境中的碰撞錐如圖3（a）紅色區(qū)域所示，由對(duì)稱性θ角可表示為：

當(dāng)智能體感知到墻形障礙物時(shí)，由于墻形障礙物邊緣的存在，墻形障礙物環(huán)境中的碰撞錐是可能是三角和長(zhǎng)方形、兩個(gè)三角形或者兩個(gè)長(zhǎng)方體的組合，這取決于智能體i能否感知到障礙物邊緣。如圖3（b）所示，設(shè)點(diǎn)O1和O2是墻型障礙物的兩個(gè)端點(diǎn)，則θ角可表示為：

其中，j=1,2。

圖3 單個(gè)障礙物環(huán)境中智能體的碰撞錐

智能體速度pi和智能體指向圓心的向量的夾角φ滿足：

避障系數(shù)gi(t)為：

3.3 算法設(shè)計(jì)和一致性證明

結(jié)合文獻(xiàn)[6]和避障系數(shù)gi(t)，定義ui(t)如下：

其中，(t)實(shí)現(xiàn)多智能體聚合、分離和速度對(duì)齊三個(gè)規(guī)則，(t)用于避障，(t)接收虛擬領(lǐng)導(dǎo)者信息，數(shù)學(xué)定義為：

其中，qγ(t),pγ(t)∈?n代表虛擬領(lǐng)導(dǎo)者的位置向量和速度向量，這里虛擬領(lǐng)導(dǎo)者為常速虛擬領(lǐng)導(dǎo)者；gi(t)只作用于(t)的速度項(xiàng)，(t)的位置項(xiàng)用于保持障礙物與智能體的距離；hi(t)值的選取采用度中心性選擇，具體選擇方法同文獻(xiàn)[4]；勢(shì)能方程ψα、ψβ和速度交互矩陣{aij}、{ai,k} 的定義同文獻(xiàn)[6]。

整個(gè)避障控制算法流程如圖4 所示，其中Δt是時(shí)間步長(zhǎng)，一般較小，T是算法終止時(shí)間，一般根據(jù)終止條件來(lái)確定合適的值。

圖4 避障控制算法流程圖

定理1多智能體運(yùn)動(dòng)方程如公式（1）所示，控制輸入如公式（10）所示，初始能量Q0是一個(gè)有限值，則在圓形障礙物和墻形障礙物中所有智能體最終會(huì)避開(kāi)障礙，避免碰撞并趨于一致。

證明多智能體的總能量由總勢(shì)能和總動(dòng)能構(gòu)成，設(shè)q?i(t)=qi(t)-qγ(t),p?i(t)=pi(t)-pγ,q?ij(t)=qi(t)-qj(t),根據(jù)公式（1）、（10），總能量Q(t)為：

其中：

Q(t)對(duì)時(shí)間t求導(dǎo)得到：

代入公式（10）～（13），化簡(jiǎn)得到：

初始能量Q0是一個(gè)有限值，由公式（14）、（15）可知，均是有限量，由此可以推得也是有限量。根據(jù)LaSalle 定理，多智能體最終會(huì)趨于的一致性狀態(tài)。

由公式（17）可得Q˙(t)=0 的充分必要條件為：

即對(duì)于所有的智能體都有：

由于圓形障礙物的β-智能體速度一直變化，墻形障礙物β-智能體方向與γ-智能體方向不同（如果相同，則智能體不會(huì)碰到障礙物），Q˙(t)=0 成立的充分必要條件是gi(t)≡0，即所有的智能體都不在障礙物環(huán)境的危險(xiǎn)區(qū)域中。

由pj(t)=pi(t)，則qj(t)-qi(t)為一個(gè)恒定的值，由公式（20）可知qi,k(t)-qi(t)也為一個(gè)恒定的值，可以得到pi,k(t)=pi(t)，從上文可知，β-智能體沿著障礙物表面移動(dòng)，速度不會(huì)始終與虛擬領(lǐng)導(dǎo)者的速度保持一致，故所有智能體不會(huì)感知到障礙物，即最終避開(kāi)了障礙物。

初始能量Q0是一個(gè)有限值，由文獻(xiàn)[3]，多智能體之間不會(huì)發(fā)生碰撞。

4 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)研究多智能體在常速虛擬領(lǐng)導(dǎo)者的作用下避開(kāi)圓形障礙物和墻型障礙物。

4.1 圓形障礙物的避障實(shí)驗(yàn)

多智能體由區(qū)域區(qū)間為[0 ,50]×[0 , 50]、速度區(qū)間為[-1,1]×[-1,1]隨機(jī)生成的10個(gè)智能體構(gòu)成，通信距離r=r′=6，理想距離dα=dβ=5。

一組多智能體如圖5（a）所示，其中藍(lán)點(diǎn)和紅色箭頭分別表示智能體位置和速度，黑圈表示該節(jié)點(diǎn)為牽制節(jié)點(diǎn)，紅色五角星表示虛擬領(lǐng)導(dǎo)者，位置向量為(2 5,25 )，速度向量為(0.5,0.5 )，圓形障礙物的半徑為20，圓心位于(1 00,100 )，采樣時(shí)間 Δt=0.1 s。圖5（b）為多智能體在[1 0 0 s,350 s]時(shí)間段內(nèi)的運(yùn)動(dòng)軌跡，可以看出多智能體最終成功避開(kāi)圓形障礙物，并且在繞過(guò)了半圓后沒(méi)有像圖1一樣繞著圓周運(yùn)動(dòng)，而是朝著虛擬領(lǐng)導(dǎo)者的方向運(yùn)動(dòng)。

圖5 一組多智能體自適應(yīng)避障實(shí)驗(yàn)

圖6 多智能體速度差異

圖7是避障過(guò)程中智能體與障礙物的距離差異，其中未遇到障礙物時(shí)設(shè)置距離為6。從圖7 可以看出，多智能體在避障過(guò)程中只有5個(gè)智能體感知到障礙物，遇到障礙物時(shí)這些智能體在輸入控制的作用下避免了與障礙物的碰撞，同時(shí)其他智能體通過(guò)智能體之間的相互作用繞開(kāi)了障礙物。

圖7 多智能體與障礙物的距離差異

隨機(jī)選取20組智能體開(kāi)展避障實(shí)驗(yàn)。設(shè)多智能體避障所用時(shí)間為多智能體遇到障礙物到所有智能體離開(kāi)障礙物的時(shí)間間隔。圖8 是Olfati-Saber 算法和本文所提算法避障所用時(shí)間的比較，可以看出在圓形障礙物中本文所提算法避障所用時(shí)間較少，驗(yàn)證了算法的有效性。

圖8 圓形障礙物中兩種算法避障所用時(shí)間的比較

4.2 墻形障礙物的避障實(shí)驗(yàn)

多智能體和虛擬領(lǐng)導(dǎo)者的設(shè)置同3.1 節(jié)，墻型障礙物的中點(diǎn)為(1 00,100 )，長(zhǎng)度為20，法向量為(3,2)（未與虛擬領(lǐng)導(dǎo)者的速度平行是避免多智能體陷入最小值）。圖9 為一組多智能體在時(shí)間段[1 0 0 s,235 s]的軌跡，可以看出圖9（a）采用Olfati-Saber算法部分智能體在235 s未通過(guò)障礙物，而圖9（b）采用本文所提算法所有智能體都通過(guò)了障礙物。

圖9 墻形障礙物中兩種算法下多智能體的運(yùn)動(dòng)軌跡

隨機(jī)選取20組多智能體開(kāi)展避障實(shí)驗(yàn)。從圖10可以在看出在墻形障礙物中本文所提算法避障所用時(shí)間較少，驗(yàn)證了算法的有效性。

圖10 圓形障礙物中兩種算法避障所用時(shí)間的比較

5 結(jié)束語(yǔ)

本文提出了一種多智能體避障控制算法，本算法由避障系數(shù)和牽制控制輸入構(gòu)成，能夠使多智能體避開(kāi)障礙，避免碰撞并最終達(dá)到一致。通過(guò)在圓形和墻形障礙物中的多智能體避障實(shí)驗(yàn)驗(yàn)證了該算法能夠快速避障。下一步將主要就非光滑障礙物、多個(gè)障礙物和運(yùn)動(dòng)障礙物的避障問(wèn)題以及避障算法的局部最小值問(wèn)題進(jìn)行深入研究。