動(dòng)態(tài)環(huán)境下多智能體協(xié)作學(xué)習(xí)方法的研究

摘 要:將預(yù)測(cè)分析技術(shù)和強(qiáng)化學(xué)習(xí)技術(shù)有機(jī)結(jié)合，使多Agent系統(tǒng)中的各Agent，不僅具有了高度反應(yīng)自適應(yīng)性，而且擁有了高效而準(zhǔn)確的預(yù)測(cè)分析能力;使Agent的行為更具有針對(duì)性，盡可能地減少錯(cuò)誤，保證學(xué)習(xí)的正確方向，提高Agent間進(jìn)行信息共享，融合單個(gè)Agent的Q值表。相當(dāng)于相同情況下增加了學(xué)習(xí)次數(shù)，不僅盡可能地消除策略中的冗余動(dòng)作，以高效的方式實(shí)現(xiàn)最終目標(biāo)，而且提高多Agent系統(tǒng)執(zhí)行效率和收斂速度及性能。本文提出了一種改進(jìn)的多Agent間協(xié)作學(xué)習(xí)方法，適用于環(huán)境不完備的復(fù)雜情況。以追捕問題作為仿真實(shí)驗(yàn)。結(jié)果表明所提方法能夠有效地促進(jìn)多智能體系統(tǒng)中各Agent間協(xié)作學(xué)習(xí)能力。

關(guān)鍵詞:多智能體系統(tǒng) 強(qiáng)化學(xué)習(xí) 協(xié)作學(xué)習(xí) 預(yù)測(cè)分析技術(shù) 追捕問題 黑板模型

中圖分類號(hào):TP18 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1674-098X(2011)03(c)-0253-02

1 引言

近年來，分布式人工智能研究者對(duì)多Agent協(xié)作完成任務(wù)的研究越來越多。這是因?yàn)殡S著計(jì)算機(jī)網(wǎng)絡(luò)，分布式計(jì)算技術(shù)等不斷發(fā)展和完善，所要研究的系統(tǒng)往往異常復(fù)雜龐大，并且呈現(xiàn)動(dòng)態(tài)多變的分布式特性，要解決問題單憑單Agent所擁有的有限的資源和能力是無法完成的，或者完成任務(wù)的效益不是理想的，同時(shí)，成本也很高。因此，對(duì)多Agent間的協(xié)作學(xué)習(xí)方法的研究是十分必要的，也是非常重要的，更是多Agent系統(tǒng)發(fā)展的必然趨勢(shì)。學(xué)習(xí)可以使多Agent能夠在開放、復(fù)雜、動(dòng)態(tài)的環(huán)境中提高自反應(yīng)適應(yīng)性，更是學(xué)習(xí)機(jī)制可能有效地實(shí)現(xiàn)多Agent間的協(xié)作。反之，為多Agent系統(tǒng)增加協(xié)作學(xué)習(xí)機(jī)制也能起到加速多Agent的學(xué)習(xí)進(jìn)程。本文以追捕問題為背景，采用協(xié)作機(jī)制和獨(dú)立強(qiáng)化學(xué)習(xí)技術(shù)來研究多Agent系統(tǒng)中的協(xié)作學(xué)習(xí)問題，結(jié)合預(yù)測(cè)分析技術(shù)和黑板模型使多Agent擁有了可預(yù)測(cè)的能力，和共享學(xué)習(xí)成果的平臺(tái)，從而達(dá)到了利用協(xié)作來改善學(xué)習(xí)效果的目的。

2 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是一種無人監(jiān)督的在線的機(jī)器學(xué)習(xí)方法，也稱為再勵(lì)學(xué)習(xí)或評(píng)價(jià)學(xué)習(xí)，使智能體能夠在環(huán)境模型未知的情況下利用環(huán)境獎(jiǎng)賞發(fā)現(xiàn)最優(yōu)的行為序列。其原理是:如果學(xué)習(xí)者即Agent的某個(gè)動(dòng)作策略導(dǎo)致環(huán)境正的獎(jiǎng)賞，那么Agent以后產(chǎn)生這個(gè)動(dòng)作策略的趨勢(shì)就會(huì)加強(qiáng);反之，Agent產(chǎn)生這個(gè)動(dòng)作策略的趨勢(shì)便會(huì)減弱。Agent算法是由Watkins于1989年提出的一種與環(huán)境無關(guān)的動(dòng)態(tài)差分強(qiáng)化學(xué)習(xí)算法，其本質(zhì)是MDP的一種變化形式。馬爾可夫決策過程是一個(gè)四元組MDP=(S，A，P，R)，其中:S是離散的狀態(tài)空間;A:是離散的動(dòng)作空間;P:S是表示環(huán)境狀態(tài)轉(zhuǎn)移概率函數(shù);R:是狀態(tài)-動(dòng)作對(duì)的獎(jiǎng)賞函數(shù)。

馬爾可夫決策過程的思想是，智能體每步可在有限的動(dòng)作集合中選取某一動(dòng)作，環(huán)境接受該動(dòng)作后狀態(tài)發(fā)生轉(zhuǎn)移，同時(shí)作出評(píng)價(jià)，Agent面臨的主要任務(wù)是決定一個(gè)最優(yōu)策略，使得最終總的折扣獎(jiǎng)賞信號(hào)期望值最大。

3 改進(jìn)的多Agent協(xié)作學(xué)習(xí)方法

3.1 算法思想

3.1.1 各Agent均采用獨(dú)立強(qiáng)化學(xué)習(xí)算法進(jìn)行學(xué)習(xí)

3.1.2 為了加快學(xué)習(xí)速度，提高學(xué)習(xí)效率。首先，各Agent在采取行為動(dòng)作之前，預(yù)測(cè)分析其他Agent的可能動(dòng)作和下一個(gè)時(shí)刻可能所處的狀態(tài)。其次，多Agent通過黑板模型進(jìn)行策略的共享。再次，利用融合算法對(duì)多個(gè)策略進(jìn)行融合來改進(jìn)策略，利用融合后的策略進(jìn)行再次學(xué)習(xí)。

3.2 算法描述

多Agent系統(tǒng)中，各個(gè)Agent處于同一個(gè)環(huán)境中獨(dú)立地執(zhí)行Q-learning.

3.2.1 對(duì)于在t+1時(shí)刻將到達(dá)的狀態(tài)的概率預(yù)測(cè)函數(shù)P的定義如下式:

(1)

任意時(shí)刻有:成立。

表示Agenti狀態(tài)集中的第k個(gè)狀態(tài)，st是時(shí)刻所有Agent的組合狀態(tài)，是預(yù)測(cè)學(xué)習(xí)模型的學(xué)習(xí)率，它在學(xué)習(xí)過程中是逐漸衰減的。

3.2.2 具體實(shí)現(xiàn)多Agent協(xié)作學(xué)習(xí)算法

Step1 t←0，隨機(jī)初始化每個(gè)智能體的Q(s，α);

Step2:對(duì)于每個(gè)智能體，執(zhí)行標(biāo)準(zhǔn)的Q-learning算法:

首先，觀察環(huán)境當(dāng)前狀態(tài)st;

其次，按如下公式Boltzmann機(jī)的方式選擇一個(gè)動(dòng)作αt并執(zhí)行;

最后，觀察環(huán)境的后繼狀態(tài)st+1并從環(huán)境中獲得強(qiáng)化信號(hào)rt;(4)根據(jù)此公式對(duì)(s，α)狀態(tài)-動(dòng)作對(duì)相應(yīng)的Q(st，αt)進(jìn)行更新;

Step3:如果t能被事先指定的F整除，則所有的Agent交換策略并融合;

Step4:t←t+1;

Step5:如果后繼狀態(tài)滿足結(jié)束條件，則結(jié)束;否則s←s＇轉(zhuǎn)Step2。在學(xué)習(xí)收斂之后，采用公式

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

以追捕問題對(duì)改進(jìn)多Agent協(xié)作學(xué)習(xí)方法改進(jìn)仿真實(shí)驗(yàn)，得出比傳統(tǒng)多Agent強(qiáng)化學(xué)習(xí)算法的有效性和其自身的收斂性。宏觀上把Agent分為獵人和獵物兩類。實(shí)驗(yàn)結(jié)果要使多個(gè)獵人通過協(xié)作采取有效的策略追捕并最終捕獲到獵物。采用有界柵格建模，在20×20追捕地圖中，實(shí)現(xiàn)四個(gè)獵人追捕一個(gè)獵物。用N=(N1，N2，N3，N4)表示四個(gè)獵人的集合，M表示獵物，初始狀態(tài)如圖1所示。獵人的目標(biāo)是在最少的步數(shù)內(nèi)成功捕獲獵物，即指在某一個(gè)時(shí)刻獵人們?cè)讷C物周圍分別占據(jù)了四個(gè)鄰近網(wǎng)格，如圖2所示。其中，N1，N2，N3，N4之間是相互協(xié)作關(guān)系，稱為協(xié)作團(tuán)隊(duì)，與獵物對(duì)抗。各獵人都執(zhí)行獨(dú)立強(qiáng)化學(xué)習(xí)，通過預(yù)測(cè)分析，感知、規(guī)劃、移動(dòng)，并與其他獵人進(jìn)行通信協(xié)商。而獵物的逃避策略是為向其最近的獵人的反方向逃跑。在每個(gè)狀態(tài)，各個(gè)Agent只能在水平和垂直方向移動(dòng)一個(gè)網(wǎng)格的位置。Agent不能越邊界方格，且任意兩個(gè)Agent均不能同時(shí)占據(jù)同一個(gè)網(wǎng)格，若出現(xiàn)此現(xiàn)象，則二者都將原地不動(dòng)。設(shè)Agent可視半徑為r，能夠看見區(qū)域內(nèi)所有網(wǎng)格為S=(2r+1)×(2r+1)。各個(gè)Agent分配唯一的ID，r=4，且交換頻率f=50Hz

(1)定義獵人的狀態(tài)值為獵人當(dāng)前狀態(tài)，與其目標(biāo)狀態(tài)的相對(duì)距離的平方，即

(2)動(dòng)作選擇策略，先對(duì)各個(gè)Q(st，αt)用Boltzmann機(jī)進(jìn)行非線性化，再采用輪盤賭算法進(jìn)行抉擇。對(duì)于動(dòng)作αi被選擇概率為

(4)

式中，T為退火溫度值，T越大。隨機(jī)性越強(qiáng)。

(3)獎(jiǎng)賞函數(shù):若獵人達(dá)到目標(biāo)位置時(shí)，獎(jiǎng)賞+300，靠近目標(biāo)時(shí)，獎(jiǎng)賞+100，位置未發(fā)生變化得到獎(jiǎng)賞0;獵人與獵物的距離反而增加時(shí)，獎(jiǎng)賞值為-1。在獨(dú)立學(xué)習(xí)過程中，每個(gè)Agent都有一份Q值表，每個(gè)Agent互斥獨(dú)立地修改各自的Q值表，經(jīng)過一定的學(xué)習(xí)步數(shù)后，所有的Agent采用黑板模型與融合算法共享各自的Q值表。

5 實(shí)驗(yàn)結(jié)果及其分析

將本文提出的多Agent協(xié)作學(xué)習(xí)算法和獨(dú)立強(qiáng)化學(xué)習(xí)算法來進(jìn)行比較試驗(yàn)。捕獲的平均成功概率和Q值的比較如圖3所示。從實(shí)驗(yàn)結(jié)果很明顯得出，協(xié)作學(xué)習(xí)與獨(dú)立學(xué)習(xí)相比，能夠更快地收斂于平穩(wěn)值。同時(shí)，多Agent之間進(jìn)行相互合作，如多Agent間通信機(jī)制，共享策略預(yù)測(cè)其他Agent的后繼狀態(tài)。

參考文獻(xiàn)

[1] 張汝波，顧國(guó)昌，劉照德，王醒策.強(qiáng)化學(xué)習(xí)理論、算法及應(yīng)用[J].控制理論與應(yīng)用，2000，17(5):637～642.

[2] 高陽(yáng)，陳世福，陸鑫.強(qiáng)化學(xué)習(xí)研究綜述[J].自動(dòng)化學(xué)報(bào)，2004，30(1):86～101.

[3]譚民，王碩，曹志強(qiáng).多機(jī)器人系統(tǒng)[M].北京:清華大學(xué)出版社，2005.

[5] 張維明，姚莉.智能協(xié)作信息技術(shù)[M].北京:電子工業(yè)出版社，2002.

[6] Sutton RS.Learning to predict by the methods of temporal difference[J].Machine Learning.1988(3):9～44.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文