王世進 段永瑞

同濟大學,上海,200092

0 引言

生產(chǎn)控制系統(tǒng)的體系結構用于確立控制系統(tǒng)內實體的決策功能分配方式及這些實體間的相互關系,并由此建立一種用于協(xié)調不同決策實施過程的機制?？刂企w系結構是整個系統(tǒng)邏輯活動的支柱(backbone)[1]。設計具有適應性的體系結構,是車間控制系統(tǒng)在實現(xiàn)與上下層信息系統(tǒng)集成的同時,能對動態(tài)變化的車間外部需求和內部環(huán)境實現(xiàn)敏捷應變的基礎和關鍵,因此具有重要的研究意義。在過去的40多年中,圍繞著可靠性、可擴展性和適應性等要求,學術界和企業(yè)界對制造控制系統(tǒng)體系結構展開了大量研究,控制體系結構也不斷發(fā)展,經(jīng)歷了集中式、遞階式、混合式和異構式4種形式的變遷[2]。近些年來,結合遞階式結構合理層次性和異構式結構自適應性的混合式結構日益受到重視。根據(jù)結構中異構與遞階程度的不同,混合式控制體系結構有多種不同形式,具有一定的靈活性,但在如何降低控制體系結構設計難度,實現(xiàn)車間生產(chǎn)動態(tài)適應性優(yōu)化協(xié)調控制方面還存在許多值得進一步研究的問題。

近年來,基于Agent(或Holon)的混合式控制體系結構得到了廣泛研究[3-7],這是由于Agent(或Holon)潛在的自治性、交互性、反應性和主動性等屬性與制造環(huán)境中多個相互關聯(lián)的獨立系統(tǒng)之間信息和決策邏輯/地理上分布的性質非常適合[3]?；贏gent的混合式控制體系結構的基本思路是將整個系統(tǒng)分割成各個獨立的自治Agent,從而將傳統(tǒng)的集中決策與控制分散到眾多的自治Agent上進行,具有異構式控制的特點;同時建立Agent之間的協(xié)調機制,協(xié)調Agent之間的行為,實現(xiàn)共同的優(yōu)化目標,又具有遞階式控制的特點。因此,基于Agent的混合式體系結構得到了研究者的廣泛青睞。如PROSA體系結構(product—resource—order—staff architecture)[4]、適應性生產(chǎn)控制系統(tǒng)(adaptive production control system,APCS)體系結構[5]、引入中介Agent的MetaMorph體系結構[6];Sunderesh等[7]設計的結合靜態(tài)層次結構和實時任務分配機制的混合式控制體系模型等。

各種基于Agent的混合式控制體系結構的決策協(xié)商機制一般都采用合同網(wǎng)協(xié)議或其改進形式,但采用優(yōu)化和學習機制以減小協(xié)商通信負荷和提高協(xié)商效率的研究尚不多見。鑒于此,本文提出內嵌結合投標和示例學習協(xié)商機制的混合式控制體系結構,為進一步改進協(xié)商和控制性能打下了基礎。

1 基于Agent的車間控制系統(tǒng)適應性控制結構模型

提出的車間控制結構模型如圖1所示。映射車間中不同的資源或功能,模型由系統(tǒng)優(yōu)化Agent、單元協(xié)調Agent和單實體Agent(包括產(chǎn)品Agent、資源 Agent)形成三層遞階結構,允許同層Agent之間及不同層 Agent之間的交互。模型以同層Agent之間的自由協(xié)商交互為主,上層Agent根據(jù)上層性能指標為下層Agent之間的協(xié)商提供一定的協(xié)商輔助和決策參考,避免由于自由協(xié)商引起的系統(tǒng)混亂或不穩(wěn)定狀態(tài)。各Agent可位于對應的物理實體上,也可位于獨立的計算機系統(tǒng)上。其相關結構和功能描述如下:

(1)產(chǎn)品 Agent。產(chǎn)品 Agent由系統(tǒng)優(yōu)化Agent根據(jù)車間加工任務生成,對應系統(tǒng)的加工訂單作業(yè)。其基本功能包括:確定加工序列;推算工序的最遲開始時間tLS;評價標書,選擇最好的標書,確定工序加工分配。產(chǎn)品Agent包括標識碼(唯一)、權重、下達時間tR,交貨期 tD、可選工藝路線、狀態(tài)信息、協(xié)商協(xié)議庫等信息。當產(chǎn)品Agent中的狀態(tài)信息表示產(chǎn)品或作業(yè)已經(jīng)完成時,由系統(tǒng)Agent注銷該Agent。

(2)資源Agent。資源Agent建模和封裝車間內的加工資源。除表示機床外,也可以表示工作站、機器人、人、自動導向小車(automated guided vehicles,AGV)、傳送帶等。資源Agent根據(jù)自身加工能力、運行狀態(tài)和產(chǎn)品 Agent要求,與其他資源Agent協(xié)商確定產(chǎn)品Agent的加工。資源Agent對所獲得的加工任務進行局部調度,并根據(jù)車間實時情況對調度進行動態(tài)調整。資源Agent中存儲的信息包括兩部分:一是對應物理資源的加工與工藝的能力數(shù)據(jù)庫,這些數(shù)據(jù)較為穩(wěn)定;二是各個物理資源的狀態(tài)數(shù)據(jù)庫,包括運行狀態(tài)數(shù)據(jù)、負荷狀態(tài)數(shù)據(jù)、資源Agent的計劃和調度數(shù)據(jù)等。其內部結構(圖2)包括等待序列、協(xié)商協(xié)議模塊、調度模塊、學習模塊、調度結果以及能力數(shù)據(jù)庫、狀態(tài)數(shù)據(jù)庫、調度算法庫和熟悉資源Agent庫。當接收到產(chǎn)品Agent的加工請求后,資源Agent將加工請求放入?yún)f(xié)商等待序列中,根據(jù)權重程度依次排序,同時由該產(chǎn)品Agent中的工序路線信息,更新資源Agent對該產(chǎn)品Agent的熟悉資源Agent庫。資源Agent與產(chǎn)品Agent就要加工的工序用基于招投標機制和示例學習方法的協(xié)商機制進行協(xié)商。在能力數(shù)據(jù)庫、狀態(tài)數(shù)據(jù)庫所提供信息的輔助下,通過協(xié)商協(xié)議模塊與產(chǎn)品Agent或其他資源Agent進行協(xié)商。調度模塊確定資源上的優(yōu)化調度,產(chǎn)生的調度結果作為指令發(fā)送給資源實體。學習模塊可以容納如Q—學習等強化學習方法以提高資源Agent的動態(tài)調度能力。

(3)系統(tǒng)優(yōu)化Agent。系統(tǒng)優(yōu)化Agent負責與車間外部的聯(lián)系,主要接收車間上層指令,把車間信息反饋給上層信息系統(tǒng),方便車間與制造系統(tǒng)中其他信息系統(tǒng)的集成等;同時監(jiān)控車間內各Agent的狀態(tài);動態(tài)生成和注銷資源Agent、產(chǎn)品Agent。其結構主要包括元數(shù)據(jù)轉換模塊、系統(tǒng)橋接模塊、車間狀態(tài)監(jiān)控模塊、系統(tǒng)性能指標庫和協(xié)調模塊等。

(4)單元協(xié)調Agent[1]。單元協(xié)調Agent表示資源Agent和產(chǎn)品Agent以邏輯方式組成的單元,實現(xiàn)產(chǎn)品任務或特定作業(yè)的加工。該Agent主要負責與其他單元協(xié)調Agent單元的生產(chǎn)任務協(xié)調,輔助產(chǎn)品Agent就具體的工序加工任務與資源Agent的協(xié)商。其結構主要包括單元性能指標庫、控制模塊、推理工具和協(xié)商模塊等。

2 基于投標和示例學習的協(xié)商機制

Agent之間的協(xié)商過程取決于協(xié)商機制。Agent協(xié)商機制是一組用來組織和約束Agent之間對話序列和決策的規(guī)則集。現(xiàn)有的各種制造控制系統(tǒng),在定義各 Agent之間協(xié)調和合作關系時,幾乎都是采用合同網(wǎng)協(xié)議或其改進形式[3,5-6]。但是傳統(tǒng)的合同網(wǎng)協(xié)議僅僅規(guī)定工作過程,本身沒有優(yōu)化能力,而且當系統(tǒng)中Agent數(shù)量較多時,合同網(wǎng)協(xié)議過程中的招投標通信將大幅增加系統(tǒng)的網(wǎng)絡通信負荷,而各種改進合同網(wǎng)協(xié)議在實現(xiàn)上有一定的難度。為此,以合同網(wǎng)協(xié)議中最核心的投標(bidding)過程為基礎,結合調度算法和基于示例學習方法,提出一種新的協(xié)商機制,目的是在易于實現(xiàn)和減小通信負荷的前提下,能應對車間可能出現(xiàn)的各種擾動情況(如機床故障、急單進入等),從而提高協(xié)商效率和性能。圖3是協(xié)商機制的統(tǒng)一建模語言(unified modeling language,UM L)活動圖,即整體活動流程。圖3中tC為系統(tǒng)當前時間,t為系統(tǒng)中任意兩Agent間一次通信所耗費的最長時間,tEF為工序的最早完成時間,tij為產(chǎn)品Agent i和資源Agent j之間的一次通信時間,K為產(chǎn)品Agent欲發(fā)送投標請求的資源 Agent數(shù),避免以廣播方式發(fā)送投標請求。該協(xié)商機制的整體思路是:當一產(chǎn)品Agent工序的最遲開始時間tLS＞2t+tC(即產(chǎn)品Agent的交貨期比較緊)時,采用基于示例學習方法直接確定工序加工任務的分配計劃,以提高協(xié)商效率,降低通信負荷;否則,就采用完整的投標協(xié)商機制。

2.1 時間約束算法(算法1)

該算法主要用來確定產(chǎn)品Agent所表示的各作業(yè)工序的計劃下達時間tR、交貨期tD和最遲開始時間tLS,具體算法如下:

其中,Pi為產(chǎn)品Agent i(i為作業(yè)總數(shù),i=1,2,…,n)所表示的作業(yè);in為Pi的工序總數(shù);Oij(j=1,2,…,in)為Pi的其中一道工序;M(Oij)表示能加工工序Oij的機床集(由資源Agent映射);tP(Oij,Ml)為工序Oij在機床Ml(l∈M(Oij))的加工時間。

每道工序等待機床投標的時間確定為tLS(Oij)—tR(Oij)—t。一旦等待時間結束,產(chǎn)品Agent就選擇具有 min(tij+tEF)的機床,即min(tij+tEF)是產(chǎn)品Agent i的目標。在具體情況下,根據(jù)訂單的不同需求,通過評價和選擇邏輯,Agent可以動態(tài)改變目標,如采用加工成本盡可能小和總通過時間最小[3]。如果有兩臺以上機床具有相同的最小值,則進一步選擇當前負荷小的一臺。

2.2 資源調度模塊(算法2)

該算法主要用于確定資源Agent所表示資源(主要是機床)的優(yōu)化調度。每個資源Agent都有自己的目標,根據(jù)該目標評估選擇產(chǎn)品Agent的投標。本文定義資源Agent的目標是機床利用率和工序最小平均延誤的權重和。該目標可以表示為

這里,w1＞0,w2＞0,w1+w2=1,如果tD(Oij)—(tS(Oij,Ml)+tP(Oij,Ml))＞0,則 w2=0。其中,~L、~Uml為接收到新投標請求前的機床負載和利用率;tC(Oij,Ml)為工序Oij在機床Ml上的加工結束時間;tS(Oij,Ml)為工序Oij在機床Ml的開始加工時間。

在接收到新招標時,設Tl為在機床Ml上已經(jīng)安排加工的工序集,Ol為其中的一道工序,tS(Ol)、tC(Ol)分別為Ol的開始加工時間和結束時間,則資源調度模塊具體算法可以描述如下:

(1)確定 T1={Ol|?Ol∈ Tl,且Ol為Oij在工藝路線上的前面工序},T2={Ol|Ol∈Tl,tC(Ol,Ml)＜tR(Oij,Ml)}。

(2)初定 tS(Oij,Ml)=max(tC(Ol),tR(Oij)),Ol∈T1∪T2。

(3)當tS(Oij,Ml)≤tC(Tl)時,①確定T3={Ol|?Ol∈(Tl—T1∪ T2),tS(Oij,Ml)＜tS(Ol)＜tC(Oij,Ml)or tS(Oij,Ml)＜tC(Ol)＜tC(Oij,Ml)};②如果 T3=?,計算Gml,否則,向后移動工序Oij,改變tS(Oij,Ml)。

(4)比較得到的各個Gml,選擇具有最小Gml的tS(Oij,Ml)。

確定工序的開始加工時間后,生成標書,確定tEF(Oij,Ml)=tS(Oij,Ml)+tP(Oij,Ml)和機床負載。當同時接收到多個產(chǎn)品Agent的投標請求時,機床分別比較接收各個工序可能獲得的目標值,如果各個工序的開始加工時間合理,則全部接收;如果選擇多個工序存在沖突,就選擇具有最大目標值的工序,并返回該工序的最早結束時間和接收后的機床負載,同時拒絕其他產(chǎn)品Agent的請求。

2.3 基于示例的學習方法(IBL算法)

為了減小通信負荷,引入了基于示例學習(instance based learning,IBL)的機制?；谑纠龑W習是一種基于記憶的機器學習方法。k近鄰方法(k—nearest neighbour,kNN)是這種學習方法的典型代表[8],該方法的基本思想是找出新示例的k個近鄰,看這k個近鄰中多數(shù)屬于哪一類就把該新示例歸為那一類。該方法具有學習速度快、學習結果易理解以及具有較高預測準確性等特點[8]。Deshpande等[9]把kNN方法與合同網(wǎng)機制結合用在虛擬的分布式醫(yī)院系統(tǒng)的資源共享上,并通過仿真示例驗證了其有效性。本文提出的是基于示例的學習方法。

工序分配的示例歷史庫存儲在系統(tǒng)優(yōu)化Agent中。隨著新的訂單不斷進入,車間中工序分配示例將不斷增加。為了減小數(shù)據(jù)庫的存儲負荷,系統(tǒng)優(yōu)化Agent采用先進先出的循環(huán)隊列存儲歷史示例。循環(huán)隊列的長度為l,l可以固定不變,也可以根據(jù)車間情況實時調整。這樣,歷史示例表示為HI={I1,I2,…Il}。一個工序的分配情況是否可以作為歷史示例,需要根據(jù)實際加工延誤確定。如果系統(tǒng)優(yōu)化Agent監(jiān)測到工序加工的實際情況是tC(Oij,Ml)—tD(Oij)＞θ(θ為系統(tǒng)的延誤限定參數(shù)),則認為實際加工延誤,不能加入示例歷史庫;反之,就插到歷史示例循環(huán)隊列的末尾,作為新的歷史示例,同時舊的示例自動從循環(huán)隊列中刪除。

2.4 擾動情況的協(xié)商方法

當一臺機床發(fā)生故障時,原先計劃在該機床上加工的工序需要重調度。表示故障機床的資源Agent在警示故障后就被系統(tǒng)優(yōu)化Agent注銷。原先分配在故障機床上的工序及其受影響的后續(xù)工序都根據(jù)圖3所示(灰色部分)協(xié)商機制進行重調度,分配到其他可選機床上;如果工序沒有其他機床可選,則工序所屬產(chǎn)品將一直延誤等待直到機床恢復正常才重新開始加工;如果工序加工過程中,機床發(fā)生故障而且工序加工不允許中斷,則工序所屬產(chǎn)品取消。異常情況下的重調度由單元協(xié)調Agent負責,利用過濾定向搜索(filtered—beam—search based algorithm)算法[10]實現(xiàn)。

以機床故障為例(圖3中灰色部分),由于加工不允許中斷,已開始加工但尚未完成的工序將不納入重調度范圍,確定這些工序所在機床的繼續(xù)占用時間為t0+Δtk(k=1,2,3,…,M),其中Δtk為工序在機床Mk上的剩余加工時間;在t0時刻空閑的機床的剩余加工時間Δ tk=0。動態(tài)調度決策器把這些信息轉換成瞬時靜態(tài)調度問題模型,并激活過濾定向搜索算法進行調度。得到的新調度銜接原有的舊調度,銜接時確定各機床的最早開始時間為max((t0+Δ t),(t0+Δtk));其中,Δt為應用算法計算新調度所需的時間,它與算法效率有關。Δt越小,動態(tài)調度效率越高。

3 原型系統(tǒng)設計

為了驗證控制結構模型的可行性和協(xié)商過程,利用JADE[11]構建了原型系統(tǒng)。

3.1 原型系統(tǒng)軟件體系結構模型

如圖4所示,結構從下到上分為4層,分別是提供網(wǎng)絡通信的底層網(wǎng)絡協(xié)議層,提供軟件運行環(huán)境和數(shù)據(jù)訪問環(huán)境的操作系統(tǒng)、數(shù)據(jù)庫層,提供JADE運行環(huán)境和Agent之間消息通信服務的Java虛擬機、網(wǎng)絡協(xié)議堆棧(remote method invocation over the internet inter—ORB protocol,RMI/IIOP)層及基于JADE(Java Agent development framework)平臺的控制系統(tǒng)應用層。

結構模型中所涉及的各實體Agent用Java語言在JADE平臺上開發(fā),位于不同的容器內,容器可位于網(wǎng)絡內不同PC上。容器分為主容器和Agent容器。主容器內包括黃頁目錄管理器(directory facilitator,DF)和Agent管理系統(tǒng)(agent management system,AMS)。每個Agent都必須在Agent管理系統(tǒng)上注冊并獲得Agent唯一標識名才能運行。黃頁目錄管理器為各Agent提供服務注冊、服務查詢等功能。系統(tǒng)優(yōu)化Agent位于主容器內,其他Agent可位于主容器內,也可位于Agent容器內(不同的Agent容器可以位于不同電腦上)。各個Agent異構分布,通過消息傳遞系統(tǒng)(message transport service,MTS)相互合作協(xié)商完成控制任務。

3.2 包圖設計

圖5是原型系統(tǒng)包圖的核心部分,主要描述了領域層和技術服務層中的包以及包所含的各個類。領域層內的包集中表示車間調度功能,包括單元協(xié)調包、系統(tǒng)優(yōu)化包、產(chǎn)品包、資源包和包含各核心算法的啟發(fā)式算法包。技術服務層描述JADE庫的包和類,主要包括描述Agent界面的jade.gui包,描述Agent命名的jade.lang.ad包,描述Agent行為的jade.core.behaviours包以及描述Agent交互協(xié)議的jade.proto包等。兩個層次包和類之間的相互關系(主要是依賴和泛化關系)也在圖5中進行了表述。

3.3 仿真界面

JADE平臺上開發(fā)的Agent,相互交互之前必須在Agent管理系統(tǒng)上注冊。注冊后,由遠程監(jiān)控Agent(remote monitoring agent,RMA)實時管理。本文仿真設計了產(chǎn)品Agent、系統(tǒng)優(yōu)化Agent和3個單元協(xié)調Agent的簡單系統(tǒng),其仿真界面如圖6所示。3個單元協(xié)調Agent分別位于網(wǎng)絡的 3臺不同電腦上(電腦名分別是wsjwangjing、yjb、iem —zbh),系統(tǒng)優(yōu)化 Agent和產(chǎn)品Agent位于wsjwangjing電腦的主容器內。得到的RMA界面如圖6a所示,3個單元協(xié)調Agent分別為CCA—WSJ、CCA—YJB和CCA—WHT。系統(tǒng)優(yōu)化Agent的界面和單元協(xié)調Agent的界面分別如圖6b和圖6c所示。系統(tǒng)優(yōu)化Agent通過產(chǎn)品(作業(yè))控制樹管理作業(yè)招標,定義和設定當前作業(yè)的招標參數(shù),并顯示當前作業(yè)的調度信息。單元協(xié)調Agent主要接收作業(yè)招標,對當前作業(yè)招標進行評估并作出決策,以及實現(xiàn)單元內產(chǎn)品Agent(作業(yè))和資源Agent的實時調度結果。

4 結束語

提出了一種基于Agent的適應性混合式車間控制系統(tǒng)體系結構。為了提高Agent之間的協(xié)商效率和性能,減小通信負荷,應對車間可能出現(xiàn)的各種擾動情況,設計了基于投標機制和示例學習的協(xié)商機制,并重點分析了協(xié)商機制的4個核心算法(時間約束算法、資源調度模塊、IBL算法和擾動情況算法)。最后,在JADE環(huán)境中構建了原型系統(tǒng),分析了軟件體系結構、包圖和仿真界面。提出的混合式控制體系結構為進一步改進協(xié)商和控制性能打下了基礎。

[1]Heikkila T,Kollingbaum M,Valckenaers P,et al.An Agent Architecture for M anufacturing Control:Manage[J].Computers in Industry,2001,46(3):315-331.

[2]周炳海,王東,奚立峰,等.基于 Agent的制造單元混合式控制系統(tǒng)研究[J].計算機集成制造系統(tǒng)—CIMS,2004,10(3):292-297.

[3]Chan F T S,Zhang J.A Multi—agent—based Agile Shop Floor Control System[J].International Journal of Advanced Manufacturing Technology,2002,19(10):764-774.

[4]Brussel H V,Wyns J,Valckernaers P,et al.Reference Architecture for Holonic Manufacturing Systems:PROSA[J].Computer in Industry,1998,37(3):255-274.

[5]Ottaway T A,Burns J R.An Adaptive Production Control System Utilizing Agent Technology[J].International Journal of Production Research,2000,38(4):721-737.

[6]Maturana F,Shen W,Norrie D H.Metamorph:An Adaptive Agent—based Architecture for Intelligent Manufacturing[J].International Journal of Production Research,1999,37(10):2159-2173.

[7]Sunderesh S H,Robert J G,Byung—In K,et al.Intelligent Agent Based Framework for Manufacturing Systems Control[J].IEEE Transactions on Systems,Man,and Cybernetics—Part A:Systems and Humans,2002,32(5):560-571.

[8]Aha D W,Kibler D,Albert M K.Instance—based Learning Algorithms[J].Machine Learning,1991,6(2):37-66.

[9]Deshpande U,Gupta A,Basu A.Performance Enhancement of a Contract Net Protocol Based System Through Instance—based Learning[J].IEEE Transactions on System,Man,and Cybernetics—Part B:Cybernetics,2005,35(2):345-358.

[10]Wang Shijin,Xi Lifeng,Zhou Binghai.Filtered—Beam—Search—Based Algorithm for Dynamic Rescheduling in FMS[J].Robotics and Computer—Integrated Manufacturing,2007,23(4):457-468.

[11]Bellifemine F,Caire G,Poggi A,et al.JADE:a Software Framework for Developing Multi—agent Applications.Lessons Learned[J].Information and Software Technology,2008,50(1/2):10-21.