張忠藝，徐冬梅

（上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620）

0 引言

為了優(yōu)化特定的目標(biāo)功能，調(diào)度可以定義為“如何根據(jù)時(shí)間來(lái)調(diào)度機(jī)器和資源”[1]。由于現(xiàn)代生產(chǎn)調(diào)度具有復(fù)雜性，特別是不確定性、動(dòng)態(tài)性、復(fù)雜性等因素的綜合作用，使得現(xiàn)代制造系統(tǒng)的調(diào)度更加困難，導(dǎo)致生產(chǎn)任務(wù)動(dòng)態(tài)變化的運(yùn)行環(huán)境不確定性增加，要求調(diào)度系統(tǒng)具有較強(qiáng)的自適應(yīng)性、魯棒性和可擴(kuò)展性。

針對(duì)制造業(yè)的多智能體系統(tǒng)的分析方法主要有頻域法和Lyapunov函數(shù)法。頻率域法適用于單輸入單輸出系統(tǒng)，利用穩(wěn)定性準(zhǔn)則可確定系統(tǒng)上界的時(shí)延[2]；對(duì)一般線性系統(tǒng)來(lái)說(shuō)，Lyapunov函數(shù)法更適合[3]。Lyapunov方法是用來(lái)分析系統(tǒng)的穩(wěn)定性的時(shí)間域方法。其具體步驟是構(gòu)造Lyapunov Krasovskii和Lyapunov Razumikhin函數(shù)，通過(guò)建立的Lyapunov函數(shù)，得到系統(tǒng)的時(shí)滯在一定范圍內(nèi)波動(dòng)的一致性充分條件，大部分文獻(xiàn)都要求解時(shí)滯上界。系統(tǒng)理想的通信方式是無(wú)延遲，時(shí)間域法將一致性問(wèn)題轉(zhuǎn)化為系統(tǒng)誤差的漸近穩(wěn)定問(wèn)題，建立Lyapunov函數(shù)的線性矩陣不等式，得到系統(tǒng)的控制參數(shù)和控制條件。這種方法的研究對(duì)象大多是針對(duì)一級(jí)或二級(jí)多智能體系統(tǒng)，而對(duì)制造部門而言，其研究對(duì)象多是常階線性時(shí)變系統(tǒng)，該方法在應(yīng)用過(guò)程中較為困難。針對(duì)這一問(wèn)題，針對(duì)制造業(yè)多智能系統(tǒng)，提出了基于PID的一致性分析方法，通過(guò)狀態(tài)分解把一致性問(wèn)題轉(zhuǎn)化為降階系統(tǒng)的穩(wěn)定性問(wèn)題，給出了系統(tǒng)一致性的充要條件，最后通過(guò)實(shí)驗(yàn)驗(yàn)證了所提方法的有效性。

1 制造業(yè)多智能體系統(tǒng)分析

多代理系統(tǒng)理論是分布式人工智能領(lǐng)域的一個(gè)重要研究方向，其基本思想是將一個(gè)大型的復(fù)雜系統(tǒng)轉(zhuǎn)化為能夠相互交流、相互協(xié)調(diào)的小型自治系統(tǒng)。制造業(yè)多智能體系統(tǒng)模型如圖1所示。

圖1 制造業(yè)多智能體系統(tǒng)模型

由圖1可知，制造業(yè)多智能體系統(tǒng)由車間調(diào)度agent、任務(wù)分配agent、車間資源agent和拍賣agent四個(gè)agent組成。將調(diào)度任務(wù)輸入系統(tǒng)后，制造業(yè)多智能體系統(tǒng)通過(guò)上述四個(gè)agent協(xié)同完成任務(wù)后輸出相應(yīng)的調(diào)度結(jié)果[4]。

1）車間調(diào)度agent

車間調(diào)度agent用來(lái)接收外部過(guò)程輸入，判斷任務(wù)是否能夠完成，如有可能，車間調(diào)度代理將直接向任務(wù)代理分配操作，并安排最終輸出作業(yè)[5]。

2）任務(wù)分配agent

任務(wù)分配agent用來(lái)將車間調(diào)度agent接收任務(wù)的流程分解成子任務(wù)，每個(gè)任務(wù)的處理時(shí)間和成本在車間調(diào)度agent中進(jìn)行查詢，并通過(guò)拍賣代理協(xié)調(diào)任務(wù)之間的沖突[6]。

3）車間資源agent

車間資源agent為所有可在現(xiàn)場(chǎng)執(zhí)行的資源和任務(wù)提供信息，幫助拍賣agent提出最終工作計(jì)劃建議[7]。

4）拍賣agent

拍賣智能體用于處理制造業(yè)調(diào)度系統(tǒng)中加工工序、任務(wù)處理的沖突，因此拍賣agent也是制造業(yè)調(diào)度系統(tǒng)的核心。制造業(yè)調(diào)度系統(tǒng)是通過(guò)合理安排每項(xiàng)調(diào)度任務(wù)，實(shí)現(xiàn)總損耗最小、加工時(shí)間最短等最佳目標(biāo)。根據(jù)拍賣協(xié)議，以目標(biāo)參考變量為基礎(chǔ)對(duì)拍賣任務(wù)進(jìn)行排序，以獲得最優(yōu)的拍賣結(jié)果[8]。

2 預(yù)備知識(shí)

多智能體系統(tǒng)的研究中，通常將各智能體視為一個(gè)節(jié)點(diǎn)，結(jié)合PID法可簡(jiǎn)化整個(gè)系統(tǒng)：

對(duì)由各個(gè)代理構(gòu)成的多代理系統(tǒng)，可用圖G={V，ε}表示其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。拓?fù)鋵W(xué)中的節(jié)點(diǎn)用非空的有限集合N={N1，N2，…，Nn}來(lái)表示，拓?fù)渲械拿織l邊用一對(duì)節(jié)點(diǎn)表示[9]。

在有向圖中，定義一對(duì)節(jié)點(diǎn)（Ni，Nj）的邊即代理可以接收節(jié)點(diǎn)狀態(tài)信息；而在無(wú)向圖中，定義一對(duì)節(jié)點(diǎn)（Ni，Nj）的邊即智能體i、j可以互相接收并發(fā)送狀態(tài)信息，其他可通過(guò)定義的邊連接的節(jié)點(diǎn)稱為區(qū)域節(jié)點(diǎn)[10]。

為更直觀地了解PID控制與多智能體系統(tǒng)的關(guān)系，需要對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行鄰接矩陣描述[11]。鄰接矩陣定義如下：

其中：

在有向圖中，當(dāng)aij=1時(shí)，連接兩個(gè)節(jié)點(diǎn)Ni與Nj時(shí)，智能體j能夠接收代理的狀態(tài)信息，但是智能體i代理不能接收[12]。當(dāng)aij=0時(shí)，兩個(gè)節(jié)點(diǎn)Ni與Nj之間沒(méi)有連接時(shí)，智能體i和智能體j之間均無(wú)法接收代理的狀態(tài)信息；

在無(wú)向圖中，當(dāng)aij=1時(shí)，連接兩個(gè)節(jié)點(diǎn)Ni與Nj時(shí)，智能體i和智能體j之間可以自由接收各自狀態(tài)信息；當(dāng)aij=0時(shí)，兩個(gè)節(jié)點(diǎn)Ni與Nj之間沒(méi)有連接時(shí)，智能體i和智能體j之間無(wú)法接收對(duì)方狀態(tài)信息。因此可以看出，無(wú)向網(wǎng)拓?fù)涞泥徑泳仃囀菍?duì)稱的，而有向網(wǎng)拓?fù)鋭t不一定對(duì)稱[13]。

實(shí)現(xiàn)PID控制前需要了解強(qiáng)連通圖、生成樹和有結(jié)點(diǎn)有向圖等概念知識(shí)，有向圖包含有向生成樹，即通過(guò)有向路徑中至少一個(gè)節(jié)點(diǎn)可以遍歷所有其他節(jié)點(diǎn)。對(duì)于無(wú)向圖，如果是連通圖則包含無(wú)向生成樹，如果是強(qiáng)連通圖則被定義為任意兩個(gè)結(jié)點(diǎn)之間的雙向路徑[14]。因此有向圖中存在有向生成樹并不一定意味著圖是強(qiáng)連通的，但是有向生成樹是存在于強(qiáng)連通圖中的。

3 基于PID控制的一致性分析

3.1 PID參數(shù)設(shè)計(jì)

在系統(tǒng)不穩(wěn)定的情況下，PID參數(shù)設(shè)計(jì)過(guò)程中，首先需要滿足式(1)；然后利用LMI工具箱結(jié)合定理1求解制造業(yè)調(diào)度系統(tǒng)所需要的增益矩陣K1和K2。根據(jù)制造業(yè)調(diào)度系統(tǒng)所處條件的不同，PID參數(shù)設(shè)計(jì)過(guò)程中存在以下兩種情況：

1）若無(wú)噪音，則該系統(tǒng)為穩(wěn)定系統(tǒng)，即各agent應(yīng)一致振動(dòng)。采用遺傳算法求解PID參數(shù)，以跟蹤誤差、上升時(shí)間和控制能量作為系統(tǒng)優(yōu)化指標(biāo)。在此基礎(chǔ)上，選取了一個(gè)基于經(jīng)驗(yàn)的PID調(diào)整參數(shù)，并將其剩余參數(shù)等調(diào)整參數(shù)與原始數(shù)據(jù)進(jìn)行比較，從而確定最優(yōu)調(diào)整參數(shù)，從而使系統(tǒng)具有較好的收斂性能[15]。

2）假設(shè)制造業(yè)調(diào)度系統(tǒng)存在隨機(jī)噪聲，證明了系統(tǒng)處于不穩(wěn)定狀態(tài)，然后用PID參數(shù)選取適當(dāng)?shù)慕?jīng)驗(yàn)值，并將PID控制與純比例控制相比較，說(shuō)明PID控制對(duì)系統(tǒng)噪聲的具有抑制作用。

3.2 一致性分析

圖2是包含6個(gè)節(jié)點(diǎn)的有向圖，第1節(jié)是根節(jié)點(diǎn)，從區(qū)段1開始，其可以指向其他五個(gè)節(jié)點(diǎn)，其中有一個(gè)樹是由其直接生成的。但是節(jié)點(diǎn)2、3、4、5、6不能通過(guò)有向路徑遍歷其他所有節(jié)點(diǎn)，因此圖中沒(méi)有實(shí)現(xiàn)強(qiáng)連通。

定理1：當(dāng)有向圖存在有向生成樹時(shí)，其對(duì)應(yīng)的PID控制矩陣只是零特征值，其他非零特征值均位于右半平面。

定理2：若圖中僅存在一棵生成樹，則圖中所對(duì)應(yīng)的多主體系統(tǒng)將逐漸收斂。

通過(guò)以上定理可知，相應(yīng)的PID控制矩陣具有唯一的零特征值，其特征值對(duì)應(yīng)的特征向量為0，其他非零特征值放置在右平面上，即特征值的實(shí)部為正。

圖2 含有六個(gè)節(jié)點(diǎn)的有向圖

由于PID控制矩陣L存在唯一一個(gè)零特征值，故Rank（L）=n-1。網(wǎng)絡(luò)拓?fù)涞拇鷶?shù)連通度是PID控制矩陣的最小非零特征值λ2（L）。

最小非零特征值λ2（L）與算法收斂速度成正比例關(guān)系，當(dāng)λ2（L）變大，則說(shuō)明算法收斂速度也隨之變快；當(dāng)系統(tǒng)出現(xiàn)時(shí)滯問(wèn)題時(shí)，需要將最小非零特征值λ2（L）與時(shí)滯大小對(duì)比，由此避免時(shí)滯給系統(tǒng)運(yùn)行帶來(lái)的干擾。圖3為含有四個(gè)節(jié)點(diǎn)的有向圖。

圖3 含有四個(gè)節(jié)點(diǎn)的有向圖

圖3的四個(gè)節(jié)點(diǎn)有向圖中對(duì)應(yīng)的鄰接矩陣的入度Q與出度W為：

結(jié)合式(3)、式(4)，構(gòu)建PID控制矩陣為：

根據(jù)式(5)的PID控制矩陣，可確定特征值為，λ1=0，λ1=λ3=1，λ4=2。

定理1驗(yàn)證：通過(guò)極點(diǎn)配置智能體系統(tǒng)矩陣，確定PID參數(shù)，通過(guò)求解不等式，確定增益矩陣K1，驗(yàn)證結(jié)果如圖4所示。

圖4 定理1驗(yàn)證結(jié)果

由圖4可知，雖然在不同PID控制矩陣的特征值下，多智能體系統(tǒng)狀態(tài)沒(méi)有趨近于0，但最終趨近于一致，使用PID控制方法可以快速消除系統(tǒng)余差，加快系統(tǒng)一致性收斂。

定理2驗(yàn)證：假設(shè)系統(tǒng)存在噪聲，在該情況下確定PID參數(shù)，通過(guò)求解不等式，確定增益矩陣K2，驗(yàn)證結(jié)果如圖5所示。

圖5 定理2驗(yàn)證結(jié)果

由圖5可知，在制造系統(tǒng)存在隨機(jī)干擾噪聲的情況下，采用PID控制方法，可以迅速消除系統(tǒng)余差，實(shí)現(xiàn)系統(tǒng)一致性。

4 實(shí)驗(yàn)

為了驗(yàn)證基于PID的制造業(yè)多智能體系統(tǒng)一致性分析合理性，進(jìn)行實(shí)驗(yàn)驗(yàn)證分析。

4.1 智能體車間調(diào)度設(shè)置

如圖6所示為多智能體車間調(diào)度過(guò)程示意圖。

圖6 多智能體車間調(diào)度過(guò)程

如圖6所示，多智能體車間調(diào)度過(guò)程主要有5個(gè)步驟：

1）車間調(diào)度代理接收處理任務(wù)，由程序模塊判斷是否可以完成任務(wù)。不能完成任務(wù)時(shí)輸出“工序超限”命令，可以完成任務(wù)時(shí)則向代理傳送工序通知任務(wù)；

2）任務(wù)分配代理將接收到的工序分解成若干個(gè)子任務(wù)，并向車間資源代理查詢其消耗、工時(shí)、成本、廢物處理等任務(wù)；

3）車間資源代理向拍賣代理傳遞任務(wù)細(xì)節(jié)；

4）任務(wù)管理通過(guò)信息將所收到的任務(wù)傳送給拍賣代理，二是拍賣代理能夠協(xié)調(diào)任務(wù)沖突；

5）拍賣行根據(jù)預(yù)定的目標(biāo)函數(shù)協(xié)調(diào)需要拍賣的沖突，比如在最短處理時(shí)間等情況下，協(xié)調(diào)的結(jié)果將作為任務(wù)分配給單個(gè)智能體。

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

制造業(yè)多智能體相應(yīng)的接近中心性和最小-最大距離中心性如表1所示。

表1 制造業(yè)多智能體相關(guān)參數(shù)

在表1所示的相關(guān)參數(shù)下，分別使用頻域法、Lyapunov函數(shù)法和基于PID分析方法對(duì)系統(tǒng)狀態(tài)軌跡一致性進(jìn)行驗(yàn)證，對(duì)比結(jié)果如圖7所示。

圖7 不同方法系統(tǒng)狀態(tài)軌跡一致性驗(yàn)證分析

由圖7可知，使用頻域法6個(gè)智能體系統(tǒng)狀態(tài)軌跡在10s時(shí)間內(nèi)，曲線稍有收斂，但在15s以內(nèi)收斂逐漸停止，達(dá)不到一致性效果；使用Lyapunov函數(shù)法6個(gè)智能體系統(tǒng)狀態(tài)軌跡在10s時(shí)間內(nèi)，曲線相較于頻域法收斂程度更高，但在15s以內(nèi)依舊達(dá)不到一致性效果；使用基于PID分析方法6個(gè)智能體系統(tǒng)狀態(tài)軌跡在10s時(shí)間內(nèi)，曲線收斂速度較快，在15s以內(nèi)能夠達(dá)到一致性效果。由此證明，所提方法收斂性較好，能夠達(dá)到系統(tǒng)多智能體一致性效果。

5 結(jié)語(yǔ)

為了解決任意階線性連續(xù)時(shí)間多智能體系統(tǒng)中所存在的不足，提出基于PID的制造業(yè)多智能體系統(tǒng)一致性分析。首先將系統(tǒng)一致性問(wèn)題轉(zhuǎn)化，然后通過(guò)PID控制矩陣給出制造業(yè)多智能體系統(tǒng)在有向圖拓?fù)渲写嬖谖ㄒ蝗挚蛇_(dá)節(jié)點(diǎn)這一充分條件，以達(dá)到一致性。通過(guò)實(shí)驗(yàn)可以得出所提方法有著良好的可行性及有效性，但是由于實(shí)驗(yàn)的智能體數(shù)量較少，未來(lái)隨著數(shù)量增加算法會(huì)越來(lái)越多，需要進(jìn)行更深層次的研究。