一種動(dòng)態(tài)環(huán)境下多Agent的協(xié)作方法

吳坤，劉瑋*，李爽，王晶

1.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北武漢 430205；

2.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室（武漢工程大學(xué)），湖北武漢 430205

一種動(dòng)態(tài)環(huán)境下多Agent的協(xié)作方法

吳坤1，2，劉瑋1，2*，李爽1，2，王晶1，2

1.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北武漢 430205；

2.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室（武漢工程大學(xué)），湖北武漢 430205

對(duì)動(dòng)態(tài)環(huán)境下多Agent系統(tǒng)中Agent的協(xié)作問(wèn)題進(jìn)行了研究，提出了一種基于連續(xù)規(guī)劃的動(dòng)態(tài)環(huán)境下多Agent協(xié)作方法.首先，在MA-PDDL的語(yǔ)法上進(jìn)行了改進(jìn)，通過(guò)一個(gè)自定義的函數(shù)使其能夠描述連續(xù)規(guī)劃方法；然后，提出了一種基于擴(kuò)展的MA-PDDL的連續(xù)規(guī)劃算法，能夠處理動(dòng)態(tài)環(huán)境在系統(tǒng)中所造成的不確定性；最后，實(shí)現(xiàn)了擴(kuò)展的MA-PDDL的解析方法，解析的結(jié)果能夠用于模擬Agent執(zhí)行任務(wù)的過(guò)程.選取了醫(yī)療垃圾無(wú)人運(yùn)輸場(chǎng)景進(jìn)行實(shí)驗(yàn)，成功模擬了整個(gè)實(shí)驗(yàn)場(chǎng)景的運(yùn)行過(guò)程，驗(yàn)證了方法的可行性.

動(dòng)態(tài)環(huán)境；MAS；多Agent協(xié)作；連續(xù)規(guī)劃；MA-PDDL

多Agent系統(tǒng)（multi-agent system，MAS）是分布式人工智能領(lǐng)域研究的熱點(diǎn)之一，已經(jīng)成為分布式人工智能研究的一個(gè)重要分支，關(guān)于Agent的協(xié)作問(wèn)題一直是MAS研究的核心問(wèn)題.

傳統(tǒng)領(lǐng)域關(guān)于多Agent協(xié)作問(wèn)題的研究是建立在MAS的環(huán)境不變或者可預(yù)測(cè)的基礎(chǔ)之上，例如經(jīng)典合同網(wǎng)協(xié)議（contract net protocol，CNP）［1］、組織結(jié)構(gòu)協(xié)作［2］、黑板模型［3］等.但是MAS的環(huán)境從封閉到開(kāi)放，從可預(yù)知到不確定的變化，要求多Agent的協(xié)作方法必須能夠適用于動(dòng)態(tài)環(huán)境下的MAS，上述方法均無(wú)法解決實(shí)際問(wèn)題，因此關(guān)于動(dòng)態(tài)環(huán)境下的多Agent協(xié)作方法研究就顯得非常的重要.

近幾年研究人員已經(jīng)開(kāi)始嘗試解決動(dòng)態(tài)環(huán)境下MAS中的Agent協(xié)作問(wèn)題.其中一類(lèi)研究是在傳統(tǒng)方法的基礎(chǔ)上進(jìn)行改進(jìn)，例如林琳和劉鋒［4］在合同網(wǎng)的投標(biāo)過(guò)程中引入了信任度、感知系數(shù)和活躍度等智能參數(shù)，在熟人庫(kù)（acquaintance）中進(jìn)行招標(biāo)，通過(guò)公共消息黑板發(fā)布標(biāo)書(shū)讓Agent主動(dòng)接受任務(wù)，引入了一個(gè)評(píng)估函數(shù)定期對(duì)Agent進(jìn)行評(píng)估，更新其能力以及管理Agent對(duì)其的信任度.該方法雖然具有一定的靈活性并且可以提高效率，但是由于動(dòng)態(tài)環(huán)境的實(shí)時(shí)變化，導(dǎo)致系統(tǒng)更新過(guò)于頻繁以至于增大系統(tǒng)壓力，而更新太慢又可能導(dǎo)致信息沒(méi)有同步而發(fā)生錯(cuò)誤.另一類(lèi)方法是和人工智能相結(jié)合，例如唐賢倫等［5］提出了基于改進(jìn)蟻群算法的多Agent協(xié)作策略解決了在未知環(huán)境下的多Agent協(xié)作問(wèn)題，首先由Agent在未知環(huán)境下對(duì)任務(wù)進(jìn)行搜尋，然后將收集到的信息通過(guò)黑板模型進(jìn)行信息共享，最終完成所有的任務(wù).該方法在可預(yù)測(cè)的未知環(huán)境下是可行的，但是如果環(huán)境會(huì)動(dòng)態(tài)變化且無(wú)法預(yù)知?jiǎng)t不再適用了.

智能規(guī)劃（AI planning）是用人工智能理論與技術(shù)自動(dòng)或半自動(dòng)地生成一組動(dòng)作序列，用以實(shí)現(xiàn)期望的目標(biāo)［6］.近年來(lái)，有關(guān)智能規(guī)劃的研究在問(wèn)題描述和問(wèn)題求解兩方面得到了新的突破，使得智能規(guī)劃已成為一個(gè)熱門(mén)的人工智能研究領(lǐng)域.由于智能規(guī)劃的研究對(duì)象和研究方法的轉(zhuǎn)變，極大地?cái)U(kuò)展了智能規(guī)劃的應(yīng)用領(lǐng)域，在太空飛船［7］、衛(wèi)星［8］、智能機(jī)器人［9-11］等眾多領(lǐng)域都有著十分廣泛的應(yīng)用.

使用智能規(guī)劃來(lái)解決Agent協(xié)作問(wèn)題時(shí)具有專(zhuān)門(mén)的規(guī)劃語(yǔ)言.最早的規(guī)劃語(yǔ)言是STRIPS［13］，由Richard Fikes和Nils J.Nilsson在1971年提出，他們?cè)诨谶壿嫷囊?guī)劃問(wèn)題表示上引入了過(guò)程化表示和語(yǔ)義，隨后發(fā)展成為經(jīng)典規(guī)劃中最主要的描述語(yǔ)言，幾乎所有的規(guī)劃系統(tǒng)都采用STRIPS語(yǔ)言或其一個(gè)變種來(lái)描述規(guī)劃問(wèn)題.1998年，McDer-mott提出了規(guī)劃領(lǐng)域定義語(yǔ)言（planning domain definition language，PDDL）［14］，并逐漸成為國(guó)際智能規(guī)劃比賽IPC公認(rèn)的標(biāo)準(zhǔn).

隨著MAS的廣泛應(yīng)用與研究，關(guān)于多Agent的規(guī)劃語(yǔ)言也得到了快速的發(fā)展，出現(xiàn)了大量的多Agent規(guī)劃語(yǔ)言，多Agent規(guī)劃領(lǐng)域定義語(yǔ)言（multi-agent PDDL，MA-PDDL）就是其中的一種. MA-PDDL是由Kovacs［15］在2012年提出來(lái)的，主要針對(duì)PDDL3.1的巴科斯范式（Backus-Naur Form，BNF）作了如下擴(kuò)展：在requirements中加入了multi-agent的依賴(lài)，使PDDL3.1能夠支持多Agent規(guī)劃；在動(dòng)作的定義中引入了Agent參數(shù)，當(dāng)一個(gè)動(dòng)作需要另一個(gè)Agent動(dòng)作的效果時(shí)，可以直接將協(xié)作動(dòng)作以參數(shù)的形式引用到當(dāng)前的動(dòng)作中，這樣就可以靈活的描述多個(gè)Agent之間的協(xié)作以及動(dòng)作之間的相互影響；在問(wèn)題的定義中引入了goal參數(shù)，多個(gè)Agent可以有相同的goal，要實(shí)現(xiàn)這些goal就必須要這些Agent一起協(xié)作完成，這樣就可以描述多Agent之間的協(xié)作問(wèn)題了.但是由于PD-DL3.1中假設(shè)環(huán)境是靜態(tài)的而且是完全可觀(guān)察的，所以MA-PDDL也存在這種假設(shè)，因此MA-PDDL雖然能夠描述多Agent的協(xié)作問(wèn)題，但是不能直接應(yīng)用于動(dòng)態(tài)環(huán)境下的MAS中.

總的來(lái)說(shuō)，目前缺乏一種有效可行的方法來(lái)解決動(dòng)態(tài)環(huán)境下的多Agent協(xié)作問(wèn)題，針對(duì)這一現(xiàn)狀，本文對(duì)動(dòng)態(tài)環(huán)境下的MAS中Agent協(xié)作問(wèn)題進(jìn)行了研究，提出了一種基于連續(xù)規(guī)劃的多Agent協(xié)作方法.對(duì)MA-PDDL進(jìn)行了改進(jìn)，在語(yǔ)言中加入了連續(xù)規(guī)劃元素，使其能夠通過(guò)連續(xù)規(guī)劃算法解決動(dòng)態(tài)環(huán)境下的多Agent協(xié)作問(wèn)題，避免了傳統(tǒng)方法下任務(wù)執(zhí)行過(guò)程中環(huán)境發(fā)生改變而導(dǎo)致任務(wù)失敗的情況.

1 研究基礎(chǔ)

1.1 智能規(guī)劃

智能規(guī)劃問(wèn)題可表示為一個(gè)五元組＜S，S0，G，A，Γ＞，其中S是所有可能的狀態(tài)集合，S0?S表示世界的初始狀態(tài)，G?S表示規(guī)劃系統(tǒng)希望實(shí)現(xiàn)的目標(biāo)狀態(tài)，A表示進(jìn)行狀態(tài)之間轉(zhuǎn)換所需的動(dòng)作集合，狀態(tài)轉(zhuǎn)移關(guān)系Γ?S×A×S定義了每個(gè)動(dòng)作執(zhí)行時(shí)的先決條件和效果［12］.采用智能規(guī)劃方法來(lái)解決問(wèn)題的過(guò)程就是在A集合中找到一組動(dòng)作序列，使得當(dāng)前系統(tǒng)的狀態(tài)由S0變?yōu)镚.假設(shè)完成一個(gè)任務(wù)需要兩個(gè)動(dòng)作，用智能規(guī)劃來(lái)解決問(wèn)題的示意圖如圖1所示.

圖1 智能規(guī)劃示意圖Fig.1Schematic diagram of intelligent planning

1.2 規(guī)劃語(yǔ)言

使用規(guī)劃語(yǔ)言對(duì)智能規(guī)劃問(wèn)題進(jìn)行描述時(shí)通常包括領(lǐng)域描述和問(wèn)題描述，其中領(lǐng)域描述主要是定義整個(gè)領(lǐng)域當(dāng)中的參數(shù)，以及領(lǐng)域中的對(duì)象可以執(zhí)行的動(dòng)作，用以反映整個(gè)領(lǐng)域的行為.而問(wèn)題描述則包括規(guī)劃的對(duì)象、系統(tǒng)初始狀態(tài)和目標(biāo)狀態(tài)，是對(duì)實(shí)際規(guī)劃的問(wèn)題進(jìn)行描述.

定義1多Agent規(guī)劃的領(lǐng)域描述是一個(gè)四元組D=＜O，V，F(xiàn)，A＞，其中O表示系統(tǒng)中所有的對(duì)象集合，可以是Agent，也可以是其他的普通對(duì)象；V表示系統(tǒng)中涉及到的所有狀態(tài)變量的集合，即用來(lái)描述整個(gè)領(lǐng)域狀態(tài)的變量，一般用邏輯謂詞來(lái)描述；F表示函數(shù)的集合；A表示動(dòng)作的集合.

定義2動(dòng)作a是一個(gè)三元組＜Ag，P，E＞，a∈A，P∈V，E∈V.其中Ag為執(zhí)行動(dòng)作的Agent，P是動(dòng)作執(zhí)行的前提條件，E是動(dòng)作執(zhí)行之后所產(chǎn)生的效果.一個(gè)動(dòng)作a＜ag，p，e＞表示一個(gè)Agent（ag）在系統(tǒng)狀態(tài)為p的情況下，執(zhí)行動(dòng)作a之后系統(tǒng)狀態(tài)變?yōu)閑.

定義3問(wèn)題描述為Q=＜I，G＞，I為系統(tǒng)的初始狀態(tài)，G為需要達(dá)到的目標(biāo)狀態(tài).若經(jīng)過(guò)一系列的規(guī)劃動(dòng)作之后，系統(tǒng)狀態(tài)變?yōu)镚，則表示該問(wèn)題已經(jīng)被解決了.

1.3 連續(xù)規(guī)劃

在傳統(tǒng)的規(guī)劃方法中，規(guī)劃者必須考慮整個(gè)系統(tǒng)中可能出現(xiàn)的所有情況，規(guī)劃出Agent相應(yīng)的動(dòng)作，同時(shí)設(shè)定Agent從開(kāi)始到結(jié)束都對(duì)整個(gè)系統(tǒng)有著完整的正確的知識(shí)，且動(dòng)作一定會(huì)產(chǎn)生預(yù)期的效果.這種方法對(duì)于環(huán)境相對(duì)穩(wěn)定，Agent獨(dú)立完成任務(wù)且各Agent之間沒(méi)有相互影響的系統(tǒng)來(lái)說(shuō)是可行的，但是對(duì)于動(dòng)態(tài)環(huán)境中Agent的動(dòng)作會(huì)對(duì)其他Agent產(chǎn)生影響的系統(tǒng)來(lái)說(shuō)是行不通的.

為了解決多Agent在動(dòng)態(tài)環(huán)境下的規(guī)劃問(wèn)題，Brenner和Nebel［16］提出了連續(xù)規(guī)劃算法.與傳統(tǒng)的規(guī)劃方法不同，連續(xù)規(guī)劃并不需要事先考慮所有的可能事件，而是由Agent自己決定如何去實(shí)現(xiàn)他們的目標(biāo)，換句話(huà)說(shuō)就是Agent在完成目標(biāo)任務(wù)的過(guò)程中可以自己規(guī)劃自己的行動(dòng).

連續(xù)規(guī)劃方法的核心思想就是當(dāng)Agent對(duì)周?chē)h(huán)境未知或者掌握的知識(shí)不足以完成規(guī)劃的動(dòng)作時(shí)，Agent可以延遲規(guī)劃動(dòng)作的執(zhí)行，然后通過(guò)自身的感知能力或者通過(guò)與其他Agent通信，獲取更加準(zhǔn)確的信息，不斷地更新知識(shí)直到Agent有足夠的知識(shí)來(lái)完成接下來(lái)的規(guī)劃任務(wù)，如圖2所示.與圖1相比，圖2中加入了一個(gè)重新規(guī)劃步驟，需要注意的是這里并不是簡(jiǎn)單的循環(huán)執(zhí)行動(dòng)作Action1，而是通過(guò)系統(tǒng)環(huán)境重新規(guī)劃出一條新的動(dòng)作序列來(lái)完成后面的工作.

圖2 連續(xù)規(guī)劃示意圖Fig.2Schematic diagram of continual planning

例如讓一個(gè)自動(dòng)導(dǎo)引車(chē)（automated guided vehicle，AGV）將一件貨物M從A點(diǎn)運(yùn)送到B點(diǎn)，通過(guò)規(guī)劃方法來(lái)解決這個(gè)問(wèn)題可能需要執(zhí)行以下幾個(gè)動(dòng)作：①AGV移動(dòng)到A點(diǎn)；②裝上貨物M；③AGV帶著貨物M從A點(diǎn)移動(dòng)到B點(diǎn)；④卸下貨物M.在傳統(tǒng)規(guī)劃方法中，以上幾個(gè)動(dòng)作均被認(rèn)為是瞬間完成，但是在現(xiàn)實(shí)中這些動(dòng)作都是需要一段時(shí)間才能完成.假如在AGV帶著M從A點(diǎn)移動(dòng)到B點(diǎn)的過(guò)程中，原本規(guī)劃的行動(dòng)路線(xiàn)由于突發(fā)情況無(wú)法通過(guò)，該規(guī)劃則會(huì)陷入死鎖，最終導(dǎo)致任務(wù)無(wú)法完成.通過(guò)連續(xù)規(guī)劃方法能夠避免這種情況的發(fā)生：當(dāng)AGV在移動(dòng)過(guò)程中發(fā)現(xiàn)道路不通即動(dòng)作③無(wú)法完成時(shí)，則會(huì)停下來(lái)感知周?chē)沫h(huán)境，并與其他的AGV進(jìn)行通信來(lái)了解最新的環(huán)境知識(shí)，然后重新規(guī)劃一條移動(dòng)路徑繼續(xù)完成動(dòng)作③和動(dòng)作④.

2 基于連續(xù)規(guī)劃的MA-PDDL

2.1 規(guī)劃過(guò)程描述

使用基于連續(xù)規(guī)劃的MA-PDDL來(lái)解決MAS中的多Agent協(xié)作問(wèn)題一般包括如下5個(gè)步驟：

步驟1通過(guò)多Agent領(lǐng)域描述語(yǔ)言描述多Agent系統(tǒng)的當(dāng)前環(huán)境；

步驟2接收用戶(hù)輸入的待解決問(wèn)題，并通過(guò)多Agent領(lǐng)域描述語(yǔ)言進(jìn)行描述；

步驟3根據(jù)描述后的多Agent系統(tǒng)的當(dāng)前環(huán)境和待解決問(wèn)題，規(guī)劃出一條最優(yōu)解決方案，該最優(yōu)方案包括需要執(zhí)行的若干個(gè)動(dòng)作，將若干個(gè)動(dòng)作分別分配給多Agent系統(tǒng)中能夠執(zhí)行相應(yīng)動(dòng)作的Agent；

步驟4多Agent系統(tǒng)中具有執(zhí)行任務(wù)的各Agent根據(jù)該最優(yōu)方案依次完成分配給自己的所有動(dòng)作，當(dāng)確定當(dāng)前動(dòng)作正常完成時(shí)，各Agent繼續(xù)下一個(gè)動(dòng)作，直到完成所有動(dòng)作，問(wèn)題得到解決；

步驟5當(dāng)確定當(dāng)前動(dòng)作無(wú)法完成時(shí)，停止各Agent當(dāng)前動(dòng)作，通過(guò)Agent的感知功能對(duì)多Agent系統(tǒng)的當(dāng)前環(huán)境進(jìn)行重新感知，并通過(guò)多Agent領(lǐng)域描述語(yǔ)言進(jìn)行重新描述，隨后轉(zhuǎn)至步驟3.

2.2 語(yǔ)法描述

為了在MA-PDDL中使用連續(xù)規(guī)劃算法，對(duì)MA-PDDL的動(dòng)作進(jìn)行了如下定義.

為了實(shí)現(xiàn)整個(gè)多Agent系統(tǒng)的自適應(yīng)性，保證Agent在動(dòng)態(tài)環(huán)境下也能正常完成任務(wù)，我們?cè)谠瓉?lái)的動(dòng)作定義中加入了replan這個(gè)子動(dòng)作.其工作原理如下：事先定義一個(gè)觸發(fā)replan的條件，Agent在每次執(zhí)行動(dòng)作之前判斷當(dāng)前環(huán)境是否滿(mǎn)足該條件，一旦滿(mǎn)足條件就會(huì)暫停當(dāng)前動(dòng)作的執(zhí)行，然后通過(guò)自身的感知能力或者與其他Agent通信來(lái)更新對(duì)系統(tǒng)環(huán)境的知識(shí)，最后重新規(guī)劃出一條解決問(wèn)題的執(zhí)行方案.如果不滿(mǎn)足該條件則正常執(zhí)行動(dòng)作，若因?yàn)橄到y(tǒng)環(huán)境發(fā)生了改變而導(dǎo)致動(dòng)作無(wú)法執(zhí)行或者動(dòng)作執(zhí)行失敗時(shí)，在系統(tǒng)中設(shè)置該觸發(fā)條件.

使用MA-PDDL對(duì)上文中的動(dòng)作③進(jìn)行描述，其程序如下.

其中manager是一個(gè)決策Agent，可以根據(jù)當(dāng)前系統(tǒng)的環(huán)境規(guī)劃出一條最優(yōu)路徑.當(dāng)agv要從A點(diǎn)移動(dòng)到B點(diǎn)時(shí)，必須先選出一條最優(yōu)路徑，此時(shí)需要與manager協(xié)作才能完成，采用MA-PDDL可以很方便的描述這種協(xié)作關(guān)系.

如果manager規(guī)劃完路徑，agv在執(zhí)行動(dòng)作的過(guò)程中環(huán)境發(fā)生了變化，例如路徑被堵塞了，那么該動(dòng)作就無(wú)法完成.使用加入連續(xù)規(guī)劃的MA-PDDL對(duì)該動(dòng)作進(jìn)行描述，其程序如下.

以上描述在原有的基礎(chǔ)上加入了：replan，該方法的觸發(fā)條件是isDone？false.默認(rèn)情況下該條件是isDone？true，當(dāng)動(dòng)作執(zhí)行失敗時(shí)將該條件設(shè)置為isDone？false，滿(mǎn)足該條件表示move動(dòng)作無(wú)法完成，系統(tǒng)無(wú)法達(dá)到預(yù)期效果，此時(shí)Agent會(huì)暫停后續(xù)動(dòng)作的執(zhí)行，然后重新獲取當(dāng)前系統(tǒng)環(huán)境進(jìn)行重新規(guī)劃.

2.3 方法的實(shí)現(xiàn)

方法的具體實(shí)現(xiàn)過(guò)程如圖3所示，主要包括以下幾個(gè)步驟：

圖3 方法的實(shí)現(xiàn)過(guò)程Fig.3Realization process of method

步驟1使用改進(jìn)后的語(yǔ)言將MAS的領(lǐng)域知識(shí)和需要解決的問(wèn)題描述出來(lái)作為輸入；

步驟2將領(lǐng)域描述Domain轉(zhuǎn)換為傳統(tǒng)的PD-DL和一個(gè)描述Action與Agent關(guān)系的文件，將問(wèn)題描述Problem轉(zhuǎn)換為目標(biāo)狀態(tài)文件Goal和當(dāng)前環(huán)境文件cur_env；

步驟3根據(jù)當(dāng)前環(huán)境、目標(biāo)狀態(tài)和MAS的領(lǐng)域描述規(guī)劃出一條最優(yōu)解決方案，即一系列需要執(zhí)行的動(dòng)作；

步驟4根據(jù)動(dòng)作在Action-Agent關(guān)系文件中找出一個(gè)或多個(gè)Agent來(lái)執(zhí)行動(dòng)作，每次執(zhí)行動(dòng)作之前都檢查一次當(dāng)前系統(tǒng)的環(huán)境是否發(fā)生了改變：系統(tǒng)環(huán)境沒(méi)有變化，滿(mǎn)足動(dòng)作的前提條件，正常執(zhí)行該動(dòng)作，完成之后繼續(xù)執(zhí)行下一個(gè)動(dòng)作；系統(tǒng)環(huán)境發(fā)生了變化，不再滿(mǎn)足動(dòng)作的前提條件，終止該動(dòng)作的執(zhí)行，更新描述當(dāng)前系統(tǒng)環(huán)境的文件，跳轉(zhuǎn)到步驟3.

3 場(chǎng)景建模

醫(yī)院中的醫(yī)療垃圾往往具有傳染性，對(duì)人體有很大的危害，使用人工進(jìn)行運(yùn)輸存在著極大的安全風(fēng)險(xiǎn)，使用AGV來(lái)運(yùn)輸則可以避免這種風(fēng)險(xiǎn)，而且還可以免去很多人工勞動(dòng).Savant Automation公司在2015年提出了一個(gè)醫(yī)院自動(dòng)運(yùn)輸車(chē)系統(tǒng)（automated hospital cart transportation system）［17］，在該系統(tǒng)中AGV被用來(lái)運(yùn)輸食物、醫(yī)療器械以及醫(yī)療垃圾等，并且已經(jīng)投入生產(chǎn)和使用.本文的實(shí)驗(yàn)就是以上述系統(tǒng)為基礎(chǔ)，使用了一個(gè)特定的場(chǎng)景進(jìn)行建模，最后通過(guò)模擬運(yùn)行進(jìn)行實(shí)驗(yàn).

在模型中使用Cart存放醫(yī)療垃圾，所有的Cart均放置于相應(yīng)的Pickup上，每個(gè)Pickup上都有一個(gè)射頻識(shí)別標(biāo)簽（Radio Frequency Indentification，RFID）用來(lái)讀取Cart的重量、位置等信息，通過(guò)AGV將Cart從Pickup處運(yùn)送到指定地點(diǎn).整個(gè)場(chǎng)景可以看作是一個(gè)多Agent系統(tǒng)，里面包括三種不同的Agent，分別是Cart-sensor、AGV以及decision agent.其中Cart-sensor固定在Pickup處，通過(guò)讀取Pickup上面的RFID獲取Cart的重量和位置等信息，發(fā)布任務(wù)；AGV是專(zhuān)門(mén)用來(lái)運(yùn)輸Cart的小車(chē)，具有不同載重量；decision agent可以根據(jù)當(dāng)前環(huán)境來(lái)選擇最適合的AGV來(lái)執(zhí)行，同時(shí)可以為AGV規(guī)劃出一條最優(yōu)的移動(dòng)路線(xiàn).

整個(gè)實(shí)驗(yàn)場(chǎng)景如圖4所示，Pickup-Location表示Pickup的位置，也是Cart的存放地點(diǎn)；Charge-Location為AGV充電的地方；Destination為 Cart被運(yùn)輸?shù)哪康牡兀籖oad為AGV運(yùn)行的軌跡，表示AGV可達(dá)的路徑；Wall為AGV不可達(dá)的地點(diǎn)，可視為障礙物.

圖4 實(shí)驗(yàn)仿真場(chǎng)景Fig.4Experiment scenario

使用定義1對(duì)領(lǐng)域進(jìn)行描述如下.

O是系統(tǒng)中的對(duì)象集合，有decision_agent，AGV，Cart_sensor，cart，pickup和location等6個(gè)對(duì)象；V是系統(tǒng)中的狀態(tài)變量集合，samePosition用來(lái)描述2個(gè)對(duì)象在同一個(gè)位置，on用來(lái)描述cart在pickup中，in用來(lái)描述cart在AGV小車(chē)上，ready用來(lái)描述pickup、AGV以及目的地的位置是否確定，available用來(lái)描述是否發(fā)布任務(wù)，isDone用來(lái)描述動(dòng)作是否正常完成，pathReady用來(lái)描述行動(dòng)路徑是否規(guī)劃完成；需要用到的函數(shù)包括distance和loadage，前者是求兩點(diǎn)之間的距離，后者是求AGV的載重量，兩個(gè)函數(shù)都是用來(lái)選擇最佳執(zhí)行AGV的；A是系統(tǒng)中所有Agent能夠完成的動(dòng)作的集合，包括DetectCart、ReadTag等9個(gè)動(dòng)作.

使用定義2對(duì)領(lǐng)域中的動(dòng)作進(jìn)行描述如下.

每個(gè)動(dòng)作包含3個(gè)參數(shù)：第1個(gè)參數(shù)表示執(zhí)行該動(dòng)作的Agent，第2個(gè)參數(shù)是執(zhí)行該動(dòng)作的前提條件，是一個(gè)狀態(tài)變量的集合，第3個(gè)參數(shù)是執(zhí)行完該動(dòng)作產(chǎn)生的影響，也是一個(gè)狀態(tài)變量的集合.例如DetectCart=＜Cart_sensor，＜o(jì)n（cart，pick-up）＞，＜ready（pickup）＞＞，表示當(dāng)cart在pickup中時(shí)，Cart_sensor會(huì)執(zhí)行動(dòng)作DetectCart，成功執(zhí)行完該動(dòng)作之后，pickup的位置信息就確定了.在整個(gè)系統(tǒng)中，Cart_sensor可以執(zhí)行3個(gè)動(dòng)作，deci-sion_agent可以執(zhí)行2個(gè)動(dòng)作，AGV可以執(zhí)行4個(gè)動(dòng)作.

整個(gè)系統(tǒng)的初始狀態(tài)是cart被放置到pickup中，需要完成的任務(wù)是將cart運(yùn)送到專(zhuān)門(mén)的垃圾處理點(diǎn)，使用定義3對(duì)問(wèn)題進(jìn)行描述如下所示.

實(shí)驗(yàn)場(chǎng)景中一共有12個(gè)pickup分別位于不同的地方，有兩個(gè)載重量為20 kg的AGV和兩個(gè)載重量為50 kg的AGV，50 kg載重量的AGV能耗更大，同時(shí)能耗也跟運(yùn)輸距離成正比，需要選擇一種能耗最小的方案來(lái)完成任務(wù).

使用java語(yǔ)言對(duì)MA-PDDL和改進(jìn)的MA-PDDL進(jìn)行解析，分別在靜態(tài)環(huán)境以及動(dòng)態(tài)環(huán)境這兩種情況下進(jìn)行實(shí)驗(yàn)，通過(guò)語(yǔ)句描述來(lái)代替具體的Agent執(zhí)行動(dòng)作，最后通過(guò)控制臺(tái)打印出Agent的動(dòng)作序列，其運(yùn)行結(jié)果摘錄如圖5和圖6所示.

圖5 靜態(tài)環(huán)境下運(yùn)行的結(jié)果Fig.5Results in static environment

圖6 動(dòng)態(tài)環(huán)境下運(yùn)行的結(jié)果Fig.6Results in dynamic environment

圖5和圖6中左邊是MA-PDDL的運(yùn)行結(jié)果，右邊是改進(jìn)的MA-PDDL的運(yùn)行結(jié)果.可以看到，在靜態(tài)環(huán)境下，兩種方法都可以解決問(wèn)題.但是如果在動(dòng)態(tài)環(huán)境下，MA-PDDL會(huì)停止運(yùn)行，最終導(dǎo)致任務(wù)無(wú)法完成，而基于連續(xù)規(guī)劃的MA-PDDL會(huì)通過(guò)重新規(guī)劃找到一條新的解決方案，直到問(wèn)題得到解決.

原系統(tǒng)中，當(dāng)AGV在執(zhí)行動(dòng)作的過(guò)程中環(huán)境發(fā)生改變時(shí)，系統(tǒng)采取的策略是暫停動(dòng)作的執(zhí)行，AGV在原地等待直到系統(tǒng)環(huán)境恢復(fù)預(yù)期情況.如果系統(tǒng)環(huán)境的改變是長(zhǎng)時(shí)間的或者是永久的，那么AGV完成任務(wù)的效率就會(huì)變低，甚至需要人工的參與才能完成任務(wù).實(shí)驗(yàn)結(jié)果顯示，本文提出的方法是可以解決問(wèn)題的，而且可以避免上述情況的發(fā)生，這也證明了在動(dòng)態(tài)環(huán)境下，本文方法與傳統(tǒng)方法相比更有優(yōu)勢(shì).

4 結(jié)語(yǔ)

MA-PDDL在處理動(dòng)態(tài)環(huán)境下的多Agent協(xié)作問(wèn)題時(shí)，可能會(huì)出現(xiàn)環(huán)境突然發(fā)生改變而導(dǎo)致任務(wù)無(wú)法完成的情況，針對(duì)這一現(xiàn)狀，提出了一種基于MA-PDDL的連續(xù)規(guī)劃方法.對(duì)MA-PDDL進(jìn)行了改進(jìn)，在語(yǔ)言中加入了連續(xù)規(guī)劃元素，使其能夠通過(guò)連續(xù)規(guī)劃算法解決動(dòng)態(tài)環(huán)境下的多Agent協(xié)作問(wèn)題，避免了上述情況的發(fā)生.最后提出了一種改進(jìn)語(yǔ)言的解析方法，實(shí)驗(yàn)成功模擬了醫(yī)療垃圾無(wú)人運(yùn)輸場(chǎng)景的運(yùn)行過(guò)程，實(shí)現(xiàn)了動(dòng)態(tài)環(huán)境下的多Agent協(xié)作.

改進(jìn)之后方法雖然能夠解決問(wèn)題，但是在時(shí)間上卻比MA-PDDL方法消耗更多，因?yàn)楦倪M(jìn)方法在每個(gè)動(dòng)作執(zhí)行前都會(huì)同步一次系統(tǒng)環(huán)境，這個(gè)是需要花費(fèi)時(shí)間的，在之后的研究中將會(huì)考慮將算法進(jìn)行優(yōu)化，爭(zhēng)取在時(shí)間上的消耗達(dá)到最小.

［1］SMITH R G.The contract net protocol：high-level communication and control in a distributed problem solver［J］.IEEE Transactions on Computers，1980，29（12）：1104-1113.

［2］JENNINGS N R.Commitments and conventions：the foundation of coordination in multi-agent systems［J］. Knowledge Engineering Review，1993，8（3）：223-250.

［3］NII P.The blackboard model of problem solving［J］.AI Magazine，1986，7（2）：38-53.

［4］林琳，劉鋒.基于改進(jìn)合同網(wǎng)協(xié)議的多Agent協(xié)作模型［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20（3）：71-75.

LIN L，LIU F.A multi-agent cooperation model based onimprovedcontractnetprotocol［J］.Computer Technology and Development，2010，20（3）：71-75.

［5］唐賢倫，李亞楠，樊崢.未知環(huán)境中多Agent自主協(xié)作規(guī)劃策略［J］.系統(tǒng)工程與電子技術(shù)，2013，35（2）：345-349.

TANG X L，LI Y N，F(xiàn)AN Z.Multi-agent autonomous cooperation planning strategy in unknown environment［J］.System Engineering and Electronics，2013，35（2）：345-349.

［6］宋涇舸，查建中，陸一平.智能規(guī)劃研究綜述——一個(gè)面向應(yīng)用的視角［J］.智能系統(tǒng)學(xué)報(bào)，2007，2（2）：18-25.

SONG J G，CHA J Z，LU Y P.Survey on AI planning research——anapplication-orientedperspective［J］. CAAI Transactions on Intelligent Systems，2007，2（2）：18-25.

［7］CHIEN S，KNIGHT R，STECHERT A，et al.Integrated planning and execution for autonomous spacecraft［J］. IEEE Aerospace and Electronic Systems Magazine，2009，24（1）：23-30.

［8］IZZO D，PETTAZZI L.Autonomous and distributed motion planning for satellite swarm［J］.Journal of Guidance Control and Dynamics，2015，30（2）：449-459.

［9］張彥鐸，李哲靖，魯統(tǒng)偉.機(jī)器人世界杯足球錦標(biāo)賽中多機(jī)器人對(duì)目標(biāo)協(xié)同定位算法的改進(jìn)［J］.武漢工程大學(xué)學(xué)報(bào)，2013，35（2）：69-73.

ZHANG Y D，LI Z J，LU T W.Improvements of collaborative localization algorithm of multi-robot on target in ROBOCUP［J］.Journal of Wuhan Institute of Technology，2013，35（2）：69-73.

［10］魯統(tǒng)偉，林芹，李熹，等.記憶運(yùn)動(dòng)方向的機(jī)器人避障算法［J］.武漢工程大學(xué)學(xué)報(bào)，2013，35（4）：66-71.

LU T W，LIN Q，LI X，et al.Obstacle avoidance algorithm of robot based on recording move direction［J］.Journal of Wuhan Institute of Technology，2013，35（4）：66-71.

［11］張彥鐸，葛林鳳.一種新的基于MMAS的機(jī)器人路徑規(guī)劃方法［J］.武漢工程大學(xué)學(xué)報(bào)，2009，31（5）：76-79.

ZHANG Y D，GE L F.A novel method for robot's path planningbasedonandmax-minant system［J］. Journal of Wuhan Institute of Technology，2009，31（5）：76-79.

［12］林川.基于PDDL的Web服務(wù)自動(dòng)組合的描述［J］.計(jì)算機(jī)應(yīng)用與軟件，2008，25（1）：138-139.

LINC.Describitionofautomaticwebservices compositionbasedonPDDL［J］.Computer Applications and Software，2008，25（1）：138-139.

［13］FIKES R E，NILSSON N J.Strips：a new approach to the application of theorem proving to problem solving［J］.Artificial intelligence，1971，2：608-620.

［14］MALIK G,HOWE A,KNOBLOCK C,et al.PDDL-the planning domain definition language,Technical Report CVC TR-98-003/DCS TR-1165[R].Connecticut:Yale Center for Computational Vision and Control,1998.

［15］KOVACS D L.A multi-agent extension of PDDL3.1［C］//TheAssociationfortheAdvancementof ArtificialIntelligence（AAAI）.Workshoponthe InternationalPlanningCompetition，ICAPS-2012. Atibaia：AAAI Press，2012：19-27.

［16］BRENNER M，NEBEL B.Continual planning and actingindynamicmultiagentenvironments［J］. Autonomous Agents and Multi-agent Systems，2009，19（3）：297-331.

［17］SAVANT AUTOMATION.Automated hospital cart transportationsystem［EB/OL］.（2015-06-15）［2017-04-10］.http：//www.agvsystems.com/hospitalcarts.

本文編輯：陳小平

A Multi-Agent Cooperation Method in Dynamic Environment

WU Kun1，2，LIU Wei1，2*，LI Shuang1，2，WANG Jing1，2
1.School of Computer Science and Engineering，Wuhan Institute of Technology，Wuhan 430205，China；
2.Hubei Key Laboratory of Intelligent Robot（Wuhan Institute of Technology），Wuhan 430205，China

A multi-agent cooperation method was proposed based on multi-agent system continual planning in dynamic environment.First，the Multi-Agent Planning Domain Definition Language（MA-PDDL）was extended for describing the continual planning method by a user-defined function.Then，a continual planning algorithm based on extended MA-PDDL was proposed to deal with the uncertainty.Finally，a parsing method of the extended MA-PDDL was implemented，which simulated how agents execute tasks.The method successfully simulates the execution process of automated cart transportation in hospital，which validates its feasibility.

dynamicenvironment；multi-agentsystem；multi-agentcooperation；continualplanning；MA-PDDL

TP242

A

10.3969/j.issn.1674-2869.2017.02.015

1674-2869（2017）02-0186-07

2016-12-14

國(guó)家自然科學(xué)基金（61502355）；國(guó)家測(cè)繪局測(cè)繪地理信息公益性行業(yè)科研專(zhuān)項(xiàng)（201412014）；湖北省自然科學(xué)基金（2013CF125）；武漢工程大學(xué)科學(xué)研究基金（K201475）

吳坤，碩士研究生.E-mail：kris_wu@foxmaill.com

*通訊作者：劉瑋，博士，副教授.E-mail：liuwei@wit.edu.cn

吳坤，劉瑋，李爽，等.一種動(dòng)態(tài)環(huán)境下多Agent的協(xié)作方法［J］.武漢工程大學(xué)學(xué)報(bào)，2017，39（2）：186-192.

WU K，LIU W，LI S，et al.A multi-agent cooperation method in dynamic environment［J］.Journal of Wuhan Institute of Technology，2017，39（2）：186-192.