一種基于π—MaxQ學(xué)習(xí)的多機(jī)器人協(xié)作方法
2013-01-01 00:00:00柯文德洪炳镕崔剛蔡則蘇
智能計(jì)算機(jī)與應(yīng)用 2013年3期
摘 要： 針對(duì)多機(jī)器人協(xié)作中存在的并發(fā)性較少、協(xié)商通信的實(shí)時(shí)性與高效性較差以及問題學(xué)習(xí)空間維數(shù)災(zāi)難等問題，提出一種基于π-MaxQ學(xué)習(xí)的多機(jī)器人主體協(xié)作方法。定義了機(jī)器人的公共知識(shí)、信念、目標(biāo)、意圖、承諾、信任、知識(shí)更新等心智狀態(tài)，擴(kuò)充了基于心智狀態(tài)的KQML（Knowledge Query and Manipulation Language）通信原語，并基于MaxQ方法構(gòu)建了聯(lián)合獎(jiǎng)勵(lì)函數(shù)。實(shí)驗(yàn)證明了方法的有效性。
關(guān)鍵詞： 多機(jī)器人； 協(xié)作； 分層學(xué)習(xí)； 心智
中圖分類號(hào)： TP24 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-2163（2013）03-0014-04
A Cooperative Method for Multi Robots based on π-MaxQ
KE Wende1，2 ，HONG Bingrong1 ， CUI Gang1，CAI Zesu1
（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001 China；
2 Department of Computer Science， Guangdong University of Petrochemical Technology， Maoming Guangdong 525000， China）
Abstract： Aimed to the problem in which there exist the little concurrency， low real time and efficiency， and the curse of dimensionality in multi robots’ cooperation， a cooperative method for multi robots based on π-MaxQ is proposed in the paper. Firstly， the mental states such as common knowledge， belief， goal， intention， promise， trust， knowledge update， etc.， are defined. Secondly， the KQML communication primitives based on the mental states are expanded. Thirdly， the confederative rewarding function based on MaxQ is constructed. The experiments proves the validity of the proposed method.
Key words： Multi Robots； Cooperation； Hierarchical Learning； Mental
0 引 言
現(xiàn)如今，多機(jī)器人主體任務(wù)協(xié)作問題是機(jī)器人學(xué)與人工智能的研究熱點(diǎn)，其研究主要體現(xiàn)在兩方面。一是研究多主體行為的方法和協(xié)作技術(shù)，例如博弈論、經(jīng)典力學(xué)理論等，但該方法僅滿足特定協(xié)作環(huán)境，當(dāng)主體數(shù)量、結(jié)構(gòu)、通信關(guān)系發(fā)生變化時(shí)，協(xié)作機(jī)制容易失效；二是側(cè)重于對(duì)問題的規(guī)劃以及求解過程，研究靜態(tài)或動(dòng)態(tài)環(huán)境下的主體心智變化，即信念、愿望、意圖等，以環(huán)境促使心智變化，主動(dòng)實(shí)現(xiàn)協(xié)作目標(biāo)，由于該方法較為實(shí)用靈活，受到了研究者們的廣泛關(guān)注[1]。傳統(tǒng)的基于心智模型的協(xié)作任務(wù)容易導(dǎo)致空間沖突、時(shí)間沖突與資源沖突，為實(shí)現(xiàn)協(xié)作任務(wù)最優(yōu)，研究者們多采用強(qiáng)化學(xué)習(xí)進(jìn)行解決，例如，文獻(xiàn)[2]面向智能主體基本心智行為，采用強(qiáng)化學(xué)習(xí)的多步收益最大預(yù)測(cè)特性，求解整體效果最優(yōu)；文獻(xiàn)[3]建立足球機(jī)器人雙層協(xié)作模型，并采用模糊強(qiáng)化學(xué)習(xí)思想判斷機(jī)器人當(dāng)前心智狀態(tài)以提高學(xué)習(xí)效果；文獻(xiàn)[4]分析了多機(jī)器人動(dòng)態(tài)環(huán)境特性，采用強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)協(xié)作追捕，等等。
以上研究取得了相關(guān)成果，但仍存在一些問題：
（1）多采用非邏輯因子描述多機(jī)器人協(xié)作，較少體現(xiàn)出協(xié)作并發(fā)性；
（2）未能考慮多機(jī)器人協(xié)商通信的實(shí)時(shí)性與高效性；
（3）當(dāng)問題空間增大時(shí)，學(xué)習(xí)過程出現(xiàn)維數(shù)災(zāi)難，計(jì)算復(fù)雜度增大，收斂性降低。
為解決這些問題，提高多主體協(xié)作效果，并基于文獻(xiàn)[5]已做研究的基礎(chǔ)上，本文在分層強(qiáng)化學(xué)習(xí)中引入π演算的多任務(wù)并發(fā)特性，定義機(jī)器人公共知識(shí)、信念、目標(biāo)、意圖、承諾、信任等心智模型，擴(kuò)充KQML通信原語以描述機(jī)器人主體通信進(jìn)程，使多機(jī)器人主體協(xié)作過程具備了數(shù)理分析與心智推理的特點(diǎn)，取得了理想科研效果。
1 多機(jī)器人主體系統(tǒng)
多機(jī)器人主體系統(tǒng)實(shí)現(xiàn)了物理上的分布性和邏輯上的分散性，其結(jié)構(gòu)如圖1所示。
由圖1可知，多機(jī)器人主體系統(tǒng)結(jié)構(gòu)中各部分的功能分析如下：
（1）心智狀態(tài)描述多機(jī)器人主體的理性行為，可以與其它機(jī)器人主體及環(huán)境進(jìn)行信息交互，并根據(jù)環(huán)境變化及協(xié)作要求，自主修改內(nèi)部狀態(tài)，其信念為機(jī)器人主體對(duì)工作環(huán)境的基本認(rèn)知，進(jìn)而由此產(chǎn)生愿望，判斷未來環(huán)境場(chǎng)景，其行為能力可受意圖控制，體現(xiàn)出有限形式的承諾；
圖1 多機(jī)器人主體系統(tǒng)結(jié)構(gòu)
Fig. 1 Architecture of multi robots第3期 柯文德，等：一種基于π-MaxQ學(xué)習(xí)的多機(jī)器人協(xié)作方法 智能計(jì)算機(jī)與應(yīng)用 第3卷
（2）學(xué)習(xí)模塊基于分層強(qiáng)化學(xué)習(xí)MaxQ方法，通過將問題空間分層與降維，在子空間內(nèi)實(shí)現(xiàn)策略學(xué)習(xí)與復(fù)用，提高了策略搜索速率；
（3）知識(shí)庫包含機(jī)器人主體對(duì)自身、世界、以及其它主體的描述；
（4）通信線程負(fù)責(zé)主體間的動(dòng)作與世界信息傳輸，滿足通信語言KQML的規(guī)范中消息傳輸約定，在理想情況下，要求無通信延遲并遵循消息隊(duì)列，實(shí)現(xiàn)其順序發(fā)送與接收。
2 分層強(qiáng)化學(xué)習(xí)MaxQ方法
分層強(qiáng)化學(xué)習(xí)通過擴(kuò)展經(jīng)典MDP（Markov Decision Process），以變量描述執(zhí)行動(dòng)作的若干時(shí)間步，從而形成半馬爾科夫決策過程（Semi Markov Decision Process， SMDP），[6-7]使智能主體同時(shí)遵循決策的順序性與時(shí)間性，由此實(shí)現(xiàn)多時(shí)間步的動(dòng)作建模。現(xiàn)給出SMDP定義為[8]：
定義1 5元組，SMDP=
在SMDP下的Bellman最優(yōu)值函數(shù)與最優(yōu)動(dòng)作-狀態(tài)對(duì)函數(shù)分別為：[9]
（3）
MaxQ方法構(gòu)建起問題空間的分層結(jié)構(gòu)任務(wù)圖，對(duì)MDP與策略π分解，獲取子任務(wù)集T={T0.T1，……Tn}與對(duì)應(yīng)子策略集π={π0，π1，……πn}。集合T中的子任務(wù)定義為3元組Ti=<πi，Ei，ri>，其中，子策略πi對(duì)應(yīng)Ti，終止謂詞Ei劃分激活狀態(tài)集Si與結(jié)束狀態(tài)集Li，且Si與Li受Ti約束，偽獎(jiǎng)勵(lì)函數(shù)ri在學(xué)習(xí)過程中對(duì)Li分配獎(jiǎng)勵(lì)值。在其后的任務(wù)圖中，T0為根節(jié)點(diǎn)子任務(wù)，執(zhí)行節(jié)點(diǎn)Ti可通過調(diào)用執(zhí)行其它子任務(wù)節(jié)點(diǎn)或基本動(dòng)作而完成構(gòu)建，同時(shí)上層節(jié)點(diǎn)將依照相應(yīng)策略選擇后繼節(jié)點(diǎn)以形成動(dòng)作執(zhí)行路徑，并由各層中對(duì)該層的動(dòng)作選擇來施加必要的約束。
3 基于機(jī)器人心智狀態(tài)協(xié)作的MaxQ學(xué)習(xí)
在多機(jī)器人系統(tǒng)中，通過機(jī)器人心智狀態(tài)演算實(shí)現(xiàn)機(jī)器人行為的理性和自主性，而分層強(qiáng)化學(xué)習(xí)則通過機(jī)器人主體來感知外部環(huán)境與其它主體、執(zhí)行策略以獲取獎(jiǎng)勵(lì)，通過對(duì)環(huán)境信息進(jìn)行推理與搜索以實(shí)現(xiàn)策略最優(yōu)，最后再通過子任務(wù)空間中的學(xué)習(xí)，以不斷增強(qiáng)行為效果并獲取最大收益。
3.1 心智狀態(tài)
機(jī)器人主體具備有限理性，即一定程度的自主能力與心智態(tài)度，同時(shí)也具有并發(fā)性行為特征。這一特性就決定了多機(jī)器人主體通信進(jìn)程的演算可由π演算實(shí)現(xiàn)[10-11]，該演算方式正可有效體現(xiàn)動(dòng)態(tài)結(jié)構(gòu)的進(jìn)程內(nèi)以及進(jìn)程間的良好交互效果。π演算中，多機(jī)器人系統(tǒng)由若干個(gè)相互并行的通信和動(dòng)作進(jìn)程組成，進(jìn)程間通過互補(bǔ)鏈路進(jìn)行通信，通信內(nèi)容包含知識(shí)、信念、愿望、意圖、及目標(biāo)等，對(duì)其中各部分的定義形式分列如下：
（1）公共知識(shí)（Common knowledge）：機(jī)器人執(zhí)行言語行為后，相信所關(guān)聯(lián)句子真實(shí)性，將其用公式表示，即為：
（4）
其中，機(jī)器人a在t時(shí)刻執(zhí)行言語行為，關(guān)聯(lián)得出新的句子Γ，成為多機(jī)器人系統(tǒng)的公共知識(shí)。
（2）信念（BEL）：機(jī)器人通過環(huán)境接口En-interfacei獲取外部信息后，判斷某狀態(tài)是否會(huì)出現(xiàn)，將其用公式表示，即為：
（5）
（3）目標(biāo)（Goal）：機(jī)器人通過環(huán)境接口En-interfacei獲取外部信息后，判斷其狀態(tài)滿足目標(biāo)狀態(tài)，將其用公式表示，即為：
（6）
（4）意圖（Intention）：機(jī)器人通過環(huán)境接口En-interfacei獲取當(dāng)前狀態(tài)意圖，并請(qǐng)求執(zhí)行該意圖關(guān)聯(lián)的行為，將其用公式表示，即為：
（7）
（5）承諾（Promise）：多機(jī)器人判斷個(gè)體無法獨(dú)立完成目標(biāo)時(shí)，聯(lián)合意圖后作出共同承諾，并各自在子范圍內(nèi)完成相應(yīng)任務(wù)，將其用公式表示，即為：
（8）
（6）信任（Trust）：參與協(xié)作的機(jī)器人彼此信任，并相信對(duì)方具備獨(dú)立完成相關(guān)子任務(wù)的能力，同時(shí)承諾建立協(xié)作后采取行動(dòng)，將其用公式表示，即為：
（9）
（7）知識(shí)更新（Knowledge Update）：機(jī)器人在t時(shí)刻完成協(xié)作后，通過環(huán)境接口En-interfacei獲得新知識(shí)并更新到公共知識(shí)庫，將其用公式表示，即為：
（10）
3.2 基于心智演算的KQML通信線程描述
KQML主體通信語言是基于言語行為理論（speech act）而開發(fā)形成，可將通信視為物理上的行動(dòng)[12-14]，在π-MaxQ的KQML通信語義中，A為Source，即發(fā)起協(xié)商的機(jī)器人，B為Destination，即接收協(xié)商任務(wù)指派的機(jī)器人。現(xiàn)對(duì)通信中各主要線程的描述如下。
（1）Assigning-role：Source（消息源）要求Destination（消息終點(diǎn)）轉(zhuǎn)變角色，對(duì)應(yīng)通信原語為：
Assigning-role （ABWANT（AKNOW
（BINT（BTASK））））
（11）
Precondition：INT（ATASK），ANT（BKNOW（BTASK））；
Post condition： KNOW（AKNOW（BTASK）），NOW（BINT（BTASK））
其中，A、B分別為Source與Destination，WANT描述意圖，KNOW描述能力獲知。
（2）Forming-team：Source要求Destination到達(dá)預(yù)定地點(diǎn)，形成目標(biāo)隊(duì)形，對(duì)應(yīng)通信原語為：
Forming-team（ABWANT（AKNOW（BBEL
（BTASK））））
（12）
Precondition： INT（ATASK），WANT（BKNOW（BTASK））
Post condition：KNOW（AKNOW（BTASK）），NOW（BBEL（BTASK））
（3） Reporting-conflict：Source向Destination傳遞沖突地點(diǎn)，對(duì)應(yīng)通信原語為：
Reporting-conflict（ABWANT（AKNOW（BTASK）））
（13）
Precondition：WANT（ATASK），NOW（BTASK）
Post condition：KNOW（ATASK），NOW（BTASK）
（4） Tracking：Source通知Destination跟蹤移動(dòng)目標(biāo)，對(duì)應(yīng)通信原語為：
（5） Updating-location：Destination跟蹤目標(biāo)并返回目標(biāo)位置信息，對(duì)應(yīng)通信原語為：
3.3 基于心智狀態(tài)的MaxQ學(xué)習(xí)
設(shè)在離散時(shí)間SMDP下的子任務(wù)Ti狀態(tài)集與子節(jié)點(diǎn)動(dòng)作分別為Si與Ta，即時(shí)獎(jiǎng)賞ri（s，a）=Vπ（a，s），其中，Vπ（i，s）描述從s′開始執(zhí)行Ti的期望獎(jiǎng)賞值，該值可通過Ti的分層策略π的投射函數(shù)獲得，則式（1）、（2）的期望獎(jiǎng)賞值函數(shù)與狀態(tài)動(dòng)作值函數(shù)bellman的方程分別為：
由上式可知，完成函數(shù)Gπ（i，a，s）=∑s′，σPπi（s′，σ|s，a）γσQπ（i，s′，π（s′））。
若從根節(jié)點(diǎn)T0的s狀態(tài)開始，反復(fù)遞歸執(zhí)行上層子任務(wù)策略選擇下層子任務(wù)的過程直到最終基本動(dòng)作，則投射值函數(shù)為：
多機(jī)器人主體判斷環(huán)境信息完備性以決定聯(lián)合學(xué)習(xí)或者獨(dú)立學(xué)習(xí)，并在各層中由行為回報(bào)更新狀態(tài)-行為對(duì)的值，當(dāng)?shù)竭_(dá)協(xié)作目標(biāo)狀態(tài)時(shí)，偽獎(jiǎng)勵(lì)函數(shù)ri對(duì)Li分配正值，否則為負(fù)值，當(dāng)所有子任務(wù)結(jié)束后，計(jì)算ri累計(jì)和。在多機(jī)器人主體協(xié)作系統(tǒng)中，單個(gè)機(jī)器人根據(jù)狀態(tài)-行為對(duì)搜索具有最大投影值函數(shù)的行動(dòng)策略，并在每個(gè)分層空間內(nèi)實(shí)現(xiàn)各自的Nash平衡，使協(xié)作決策收斂[15]，由此則使得對(duì)大規(guī)模問題空間內(nèi)的整體策略搜索獲得了實(shí)現(xiàn)。
在π-MaxQ心智模型中，協(xié)作成功與失敗的獎(jiǎng)勵(lì)值分別為μ與-μ，獎(jiǎng)勵(lì)函數(shù)r∈[-1，1]，閾值為0.09μ。定義機(jī)器人向分配任務(wù)的目標(biāo)位置移動(dòng)時(shí)的獎(jiǎng)勵(lì)函數(shù)為：
（19）
其中，α為獎(jiǎng)勵(lì)系數(shù)，xg（t）為t時(shí)刻目標(biāo)坐標(biāo)，x（t）為t時(shí)刻機(jī)器人位置，σ為閾值距離，當(dāng)機(jī)器人與足球的有效距離達(dá)到閾值以內(nèi)時(shí)，機(jī)器人得到獎(jiǎng)勵(lì)。
定義機(jī)器人將球傳給隊(duì)員的獎(jiǎng)勵(lì)函數(shù)如下：
（20）
其中，x0i（t）為對(duì)方機(jī)器人。
綜合上面兩式，定義聯(lián)合獎(jiǎng)勵(lì)函數(shù)為
（21）
其中，k1、k2為加權(quán)系數(shù)，且α1，α20，α1+α2=1。
4 實(shí)驗(yàn)驗(yàn)證
多機(jī)器人系統(tǒng)由Mini Robot與Mos2007仿人機(jī)器人組成，Mini Robot機(jī)器人的協(xié)作目標(biāo)是突破對(duì)方防守并將足球踢到對(duì)方半場(chǎng)，協(xié)商項(xiàng)為{tracking， accept， update-location， refuse}。仿真中，選取通信工具為JDK1.1.8與JKQML，對(duì)Mini Robot 仿人機(jī)器人通信線程進(jìn)行KQML原語擴(kuò)充部分為：
（tracking
：source Mini-1
：destination Mini-3
：content（Opponent-Mos-1（geoloc long 39w 1at 50 n） （detect-time 5S））
：reply-with id1
：language kif
：ontology geo-model3）
/////////////////////////////////////////////////
（accept
：source Mini-3
：destination Mini-1
：content（Opponent-Mos-2）
：inreplyto id1
：langu age kif
：ontology geo-mode2）
Mini Robot機(jī)器人的心智狀態(tài)受其目標(biāo)位置影響，當(dāng)未到達(dá)對(duì)方半場(chǎng)區(qū)域時(shí)，增大Belief、Goal、 Intention狀態(tài)值， 減少Knowledge狀態(tài)值，提高主動(dòng)進(jìn)攻心智，機(jī)器人根據(jù)KQML通信執(zhí)行協(xié)商項(xiàng)內(nèi)容，向目標(biāo)位置移動(dòng)以獲取更大的正獎(jiǎng)勵(lì)，并在協(xié)商過程中進(jìn)行學(xué)習(xí)。圖2所示即為Mini Robot一次成功突破Mos2007機(jī)器人并將足球踢到對(duì)方半場(chǎng)，圖3則比較了基于π協(xié)作演算的Q學(xué)習(xí)、改進(jìn)π-Q學(xué)習(xí)算法以及本文提出的π-MaxQ方法的成功次數(shù)。由圖3可知，π-MaxQ學(xué)習(xí)算法成功次數(shù)最高。
圖2 仿人機(jī)器人平臺(tái)上一次成功的協(xié)作突破踢球
Fig.2 A successful cooperative process of kicking
ball by humanoid robots
圖3 學(xué)習(xí)方法比較
Fig. 3 Comparison between learning algorithms
5 結(jié)束語
本文在多機(jī)器人主體協(xié)作的MaxQ學(xué)習(xí)方法中引入π心智演算過程，構(gòu)建起具有學(xué)習(xí)與通信能力的機(jī)器人心智狀態(tài)模型，對(duì)機(jī)器人主體的公共知識(shí)、信念、目標(biāo)、意圖、承諾、信任、知識(shí)更新等進(jìn)行了定義，并構(gòu)建起多機(jī)器人主體協(xié)商模型。實(shí)驗(yàn)表明該模型較好地提高了任務(wù)協(xié)商及協(xié)作的成功率。
參考文獻(xiàn)：
[1]李超明，蘇開樂.一個(gè)基于智能的MAS模型及其方法論[J].計(jì)算機(jī)研究與發(fā)展，2007 （6）：980-989.
[2]郭銳，吳敏，彭軍，等.一種新的多智能體Q學(xué)習(xí)算法[J].自動(dòng)化學(xué)報(bào)， 2007， 33（4）： 367-372.
[3]曹衛(wèi)華， 徐凌云， 吳敏. 模糊Q學(xué)習(xí)的足球機(jī)器人雙層協(xié)作模型[J]. 智能系統(tǒng)學(xué)報(bào)， 2008， 3（3）：234-238.
[4]樸松昊， 孫立寧， 鐘秋波， 等. 動(dòng)態(tài)環(huán)境下的多智能體機(jī)器人協(xié)作模型[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版， 2008， 36（增刊Ⅰ）： 39-41， 52.
[5]柯文德， 樸松昊， 彭志平， 等. 一種基于π演算的足球機(jī)器人協(xié)作Q學(xué)習(xí)方法[J]. 計(jì)算機(jī)應(yīng)用， 2011， 31（3）：654-656， 669.
[6]HENGST B. Discovering hierarchy in reinforcement learning[D]. Sydney University of Ne South Wales， 2003.
[7] UTHER W T R. Tree based hierarchical reinforcement learning[D]. Pittsburg： Camegie Mellon University， 2002.
[8]沈晶，劉海波，張汝波，等. 基于半馬爾可夫?qū)Σ叩亩鄼C(jī)器人分層強(qiáng)化學(xué)習(xí)[J]. 山東大學(xué)學(xué)報(bào)：工學(xué)版， 2010， 40（4）： 1-7.
[9]沈晶. 分層強(qiáng)化學(xué)習(xí)方法研究[D]. 哈爾濱：哈爾濱工程大學(xué)， 2006.
[10]史忠植. 智能主體及其應(yīng)用[M]. 北京：科學(xué)出版社，2000.
[11]于振華， 蔡遠(yuǎn)利， 徐海平. 基于π網(wǎng)的多Agent系統(tǒng)建模與分析[J]. 系統(tǒng)工程理論與實(shí)踐， 2007，7： 77-84.
[12]AUSTIN J L.How to do things with words[M].0xford：Oxford Univ.Press，1962.
[13]劉淑華，田彥濤，劉金芳.擴(kuò)展KQML在多移動(dòng)機(jī)器人仿真系統(tǒng)中的應(yīng)用[J].吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，23（5）：500—505.
[14]康輝， 曾瑩瑩， 劉志勇. 基于PI-演算的移動(dòng)通信服務(wù)研究與建模[J]. 通信學(xué)報(bào)， 2009， 30（4）： 11-16.
[15]HARMATI I， SKRZYPCZYK K. Robot team coordination for target tracking using fuzzy logic controller in game theoretic framework[J]. Robotics and Autonomous Systems， 2009， 57： 75-86.
