基于flocking的多智能體群集與避障算法研究與仿真*

劉 嬋，朱永川，白 園，何健輝

（中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引 言

隨著人工智能和智能體技術(shù)的發(fā)展和社會(huì)需求的進(jìn)一步提高，多智能體技術(shù)研究成為熱點(diǎn)問題。多智能體系統(tǒng)不是單個(gè)智能體的簡單堆砌，而是多個(gè)智能體的協(xié)同組合，不僅有效地避免了單個(gè)智能體的不足，同時(shí)充分發(fā)揮了智能體群體的優(yōu)勢。與單智能體相比，多智能體系統(tǒng)具有適合完成復(fù)雜任務(wù)、功能分布化、體系生存率、高效費(fèi)比等優(yōu)勢。多智能體系統(tǒng)可以應(yīng)用于星球探索、海洋勘探、無人機(jī)群、無人艇群、無人坦克群等領(lǐng)域，且能產(chǎn)生巨大的效益[1-2]。

多智能體運(yùn)動(dòng)規(guī)劃問題逐漸成為智能體中研究的熱點(diǎn)問題。多智能體運(yùn)動(dòng)規(guī)劃主要包括路徑規(guī)劃、編隊(duì)控制和避障避碰三種控制行為。1986年，Reynolds最早提出了模仿動(dòng)物聚集行為的計(jì)算機(jī)模型，由三條基本規(guī)則構(gòu)成，即聚集（Flock Centering）、結(jié)對(duì)（Velocity Matching）、避撞（Collision Avoidance）[2]。2006年 R. Olfati-Saber提 出 基 于flocking的多智能體動(dòng)態(tài)系統(tǒng)理論及算法，并提出了三種群集算法：（1）不存在目標(biāo)時(shí)的群集算法；（2）存在追蹤目標(biāo)時(shí)的群集算法；（3）多障礙情況下的群集算法[3]。在此之后，許多學(xué)者對(duì)flocking算法進(jìn)行了研究，包括該算法碰撞避免算法、離散時(shí)間算法、參數(shù)設(shè)置與優(yōu)化等[4-7]。

本文主要介紹了基于分布式flocking的群集控制模式，根據(jù)Reynolds提出的三條規(guī)則，以及人工勢場群集算法，實(shí)現(xiàn)了多智能體系統(tǒng)的集結(jié)與共識(shí)，使多智能體在運(yùn)動(dòng)過程中保持一致性，并為系統(tǒng)提供冗余性和結(jié)構(gòu)的靈活性；同時(shí)對(duì)多智能體的避障控制和目標(biāo)點(diǎn)控制開展了進(jìn)一步的研究，解決群集避障問題，使得群體能夠平滑地繞過靜動(dòng)態(tài)障礙物，在復(fù)雜環(huán)境下成功抵達(dá)任務(wù)目標(biāo)區(qū)域；最后仿真結(jié)果顯示多智能體能集結(jié)，并達(dá)成共識(shí)，最終越過障礙物抵達(dá)目標(biāo)節(jié)點(diǎn)，驗(yàn)證了該算法的合理性和有效性。

1 多智能體群集與避障算法研究

采用分散控制的策略，將多智能體群體運(yùn)動(dòng)的總控制律分成三個(gè)子控制律，即編隊(duì)控制、避障控制、目標(biāo)控制，分別研究了多智能體運(yùn)動(dòng)中智能體之間位置和速度的協(xié)調(diào)、躲避障礙物和向目標(biāo)點(diǎn)移動(dòng)的控制，如圖1所示。

圖1 智能體集群運(yùn)動(dòng)模型

1.1 多智能體群集運(yùn)動(dòng)基本模型

根據(jù)圖1所示的多智能體運(yùn)動(dòng)模型，假設(shè)第i個(gè)α-智能體的控制律為μi，則

式中，μiα為編隊(duì)控制律，μiβ為避障控制律，μiγ為目標(biāo)點(diǎn)移動(dòng)控制律，第i個(gè)α-智能體的控制示意圖如圖2所示。其中三角形區(qū)域?yàn)棣?智能體的目標(biāo)區(qū)域，rβ為α-智能體的感知距離，dβ為β-智能體的影響距離，rα為α-智能體的通信距離，dα為α-智能體的安全距離，α-智能體的屬性為[pi,vi]，β- 智能體的屬性為 [p^i,k,v^i,k]，μi1α和μi2α為第i個(gè)α-智能體的編隊(duì)控制律，μiβ為第i個(gè)α-智能體的避障控制律，μiγ為第i個(gè)α-智能體的目標(biāo)點(diǎn)控制律。

圖2 第i個(gè)α-智能體的控制示意圖

1.2 多智能體群集控制與共識(shí)算法研究

考慮由N個(gè)α-智能體組成的智能群體，其動(dòng)態(tài)方程為：

第i個(gè)α-智能體的鄰接節(jié)點(diǎn)集合用Ni表示，則定義：

α-智能體的鄰接矩陣用A=[aij]表示，其中對(duì)于否則，aij=0。

為了構(gòu)建群集運(yùn)動(dòng)的一個(gè)光滑集成勢場以及構(gòu)建一個(gè)鄰接網(wǎng)絡(luò)的空間鄰接矩陣，定義一個(gè)叫做σ范式的非負(fù)地圖。

并用沖擊函數(shù)來構(gòu)建光滑勢場函數(shù)以及光滑鄰接矩陣，選擇沖擊函數(shù)如下：

其中，h∈(0,1)。用這個(gè)沖擊函數(shù)，可以定義空間鄰接矩陣A(p)：

當(dāng)?shù)趇個(gè)α-智能體與鄰接節(jié)點(diǎn)保持距離dα?xí)r，認(rèn)為其幾何結(jié)構(gòu)處于穩(wěn)定狀態(tài)，即

α-智能體群體之間根據(jù)Reynolds提出的聚集行為三條基本規(guī)則，避撞、結(jié)對(duì)、聚集，構(gòu)建一個(gè)光滑的成對(duì)勢場，描述了任意兩個(gè)α-智能體之間內(nèi)部的運(yùn)動(dòng)規(guī)則。

其中，

其中，

當(dāng)α-智能體群體根據(jù)該算法進(jìn)行群集控制時(shí)，需要判定該群體是否達(dá)成了共識(shí)。我們可以參考Reynolds提出的聚集行為基本規(guī)則，獲得智能體群體共識(shí)條件：

（1）根據(jù)鄰接矩陣，利用連通圖檢測網(wǎng)絡(luò)連通情況，若連通最大分量為M，則需M=N；

（4）存在k0∈N，對(duì)于所有的k≥k0和所有的i∈I，maxj∈I{i}||pj(k)-pi(k)||≤dc，其中dc為智能體之間的最大距離；

（5）存在k0∈N，對(duì)于所有的k≥k0和所有的i∈I，minj∈I{i}||pj(k)-pi(k)||≈dα，其中dα為智能體之間的安全距離。

當(dāng)多智能體達(dá)到以上條件時(shí)，認(rèn)為該群體已達(dá)成共識(shí)。

1.3 多智能體群集避障控制算法研究

對(duì)于中心位置位于pk，半徑為Rk的β-智能體障礙物Ok，dβ為該智能體的影響距離。表示第k個(gè)β-智能體的位置表示第k個(gè)β-智能體的速度向量。假設(shè)，場景內(nèi)共有k個(gè)β-智能體障礙物，第i個(gè)α-智能體能夠感應(yīng)到的β-智能體障礙物集合用表示，則定義：

其中，Iβ={1,2,…,K}

相對(duì)第i個(gè)α-智能體，對(duì)于β-智能體障礙物的位置和速度可由下式確定：

式中，

其中，I為單位矩陣。

定義影響矩陣B(p)：

針對(duì)第i個(gè)α-智能體，與β-智能體障礙物的斥力關(guān)系如下：

其中，

式中，c1β，c2β為加權(quán)系數(shù)。

1.4 目標(biāo)點(diǎn)控制器設(shè)計(jì)

根據(jù)人工勢場的特點(diǎn)，綜合考慮位置矢量和速度矢量帶來的影響，針對(duì)第i個(gè)α-智能體，設(shè)計(jì)目標(biāo)點(diǎn)控制律為：

其中，目標(biāo)點(diǎn)γ的屬性為表示γ目標(biāo)點(diǎn)的位置矢量表示γ目標(biāo)點(diǎn)的速度矢量為加權(quán)系數(shù)。

2 多智能體群集與避障算法仿真

本節(jié)主要是通過MATLAB仿真實(shí)現(xiàn)基于flocking的多智能體群集控制與共識(shí)、避障控制，以及任務(wù)目標(biāo)區(qū)域抵達(dá)的功能。該算法的參數(shù)設(shè)置比較關(guān)鍵，在此，設(shè)置參數(shù)dα=22.5，rα=1.2dα；dβ=56.25，rβ=2.5dβ；ε=0.2；Ts=0.05。

2.1 多智能體群集控制與共識(shí)算法仿真

假設(shè)α-智能體群體個(gè)數(shù)為50，在[-200 m,200 m]范圍內(nèi)進(jìn)行多智能體位置隨機(jī)初始化，在[-2 m/s,2 m/s]范圍內(nèi)進(jìn)行智能體速度隨機(jī)初始化。則在不同時(shí)刻，α-智能體群體的仿真變化如圖3所示。

圖3 50個(gè)α-智能體群體控制與共識(shí)算法仿真

如圖3所示，圖3（a）表示t0時(shí)刻，50個(gè)α-智能體群體隨機(jī)分布的初始位置；圖3（b）表示t1時(shí)刻，已有一小部分團(tuán)體達(dá)成共識(shí)；圖3（c）表示t2時(shí)刻，已有大部分智能體達(dá)成共識(shí)；圖3（d）表示50個(gè)α-智能體群體已達(dá)成共識(shí)，組成分布式集群。

隨機(jī)分布的多智能體達(dá)成共識(shí)，構(gòu)成智能體群集，智能體之間的相干性如下式所示，

其中，N表示智能體數(shù)量，ψscal(t)表示智能體之間的相干性，當(dāng)ψscal(t)≈1時(shí)，表示在理想的集群狀態(tài)；當(dāng)ψscal(t)≈0時(shí)，在無序狀態(tài)或者智能體群集懸停狀態(tài)。

每一時(shí)刻智能體之間的相干性變化曲線圖如圖4所示。曲線很快趨于1附近波動(dòng)，說明50個(gè)智能體的速度趨于一致性。

2.2 多智能體群集避障控制與目標(biāo)區(qū)域抵達(dá)功能測試

假設(shè)50個(gè)已達(dá)成共識(shí)的多智能體群集在設(shè)定場景下進(jìn)行避障功能和目標(biāo)區(qū)域抵達(dá)功能測試，測試結(jié)果如圖5所示。

圖4 相干性變化曲線圖

圖5 多智能體群集避障控制與目標(biāo)區(qū)域抵達(dá)功能測試

如圖5所示，圖5（a）表示t0時(shí)刻，50架智能體集群的初始位置，以及障礙物的分布情況；圖5（b）-（e）表示t1-t4時(shí)刻，智能體根據(jù)當(dāng)前態(tài)勢順利繞過障礙物，繼續(xù)往目標(biāo)點(diǎn)飛行；圖5（f）表示t5時(shí)刻，智能體繞過障礙物之后，都朝目標(biāo)點(diǎn)飛行，最終又達(dá)成共識(shí)，組成集群，并成功抵達(dá)任務(wù)目標(biāo)區(qū)域。

3 結(jié) 語

本文主要介紹了基于分布式flocking的群集控制模式，根據(jù)多智能體之間的分離性、隊(duì)列性和凝聚性，實(shí)現(xiàn)了多智能體系統(tǒng)的集結(jié)與共識(shí)，并對(duì)多智能體的避障控制和目標(biāo)點(diǎn)控制開展了進(jìn)一步的研究，最后通過仿真驗(yàn)證了該算法的合理性和有效性，對(duì)多智能體群集運(yùn)動(dòng)研究具有重要的理論指導(dǎo)意義。