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

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

中圖分類號:TP18 文獻標識碼:A 文章編號:1674-098X(2011)03(c)-0253-02

1 引言

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

2 強化學(xué)習(xí)

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

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

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

3.1 算法思想

3.1.1 各Agent均采用獨立強化學(xué)習(xí)算法進行學(xué)習(xí)

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

3.2 算法描述

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

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

(1)

任意時刻有:成立。

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

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

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

Step2:對于每個智能體，執(zhí)行標準的Q-learning算法:

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

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

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

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

Step4:t←t+1;

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

4 仿真實驗

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

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

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

(4)

式中，T為退火溫度值，T越大。隨機性越強。

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

5 實驗結(jié)果及其分析

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

參考文獻

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

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

[3]譚民，王碩，曹志強.多機器人系統(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)容請以PDF格式閱讀原文