楊月全 韓飛 金露 倪春波 曹志強(qiáng) 張?zhí)炱?/p>

(1揚(yáng)州大學(xué)信息工程學(xué)院，揚(yáng)州 225009)(2中國(guó)科學(xué)院自動(dòng)化研究所復(fù)雜系統(tǒng)管理與控制國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190)

多機(jī)器人系統(tǒng)已成為當(dāng)前國(guó)內(nèi)外機(jī)器人領(lǐng)域研究的熱點(diǎn).由于機(jī)器人所面臨的環(huán)境往往是未知的、動(dòng)態(tài)的，因而通過(guò)人為的規(guī)劃來(lái)解決多機(jī)器人系統(tǒng)中所遇到的一切問(wèn)題是不現(xiàn)實(shí)的.在這種情況下，學(xué)習(xí)能力為機(jī)器人克服這些困難提供了行之有效的方法.機(jī)器人的學(xué)習(xí)可主要通過(guò)以下方式進(jìn)行［1］:借助于自身的各種傳感器，機(jī)器人可以在與環(huán)境的不斷交互中獲取知識(shí)；借助一些領(lǐng)域知識(shí)、先驗(yàn)知識(shí)來(lái)縮短學(xué)習(xí)時(shí)間；通過(guò)與其他機(jī)器人共享知識(shí)促進(jìn)彼此的技能；模擬進(jìn)化的有關(guān)思想來(lái)對(duì)自身的參數(shù)進(jìn)行優(yōu)化.

增強(qiáng)學(xué)習(xí)是一種以環(huán)境反饋?zhàn)鳛檩斎氲臋C(jī)器學(xué)習(xí)方法［2］.文獻(xiàn)［3］提出了一種新的多智能體Q學(xué)習(xí)算法，通過(guò)對(duì)聯(lián)合動(dòng)作的統(tǒng)計(jì)來(lái)學(xué)習(xí)其他智能體的行為策略，并利用智能體策略向量的全概率分布保證了對(duì)聯(lián)合最優(yōu)動(dòng)作的選擇.文獻(xiàn)［4-6］引入能體現(xiàn)人的經(jīng)驗(yàn)的模糊推理規(guī)則來(lái)改進(jìn)機(jī)器人學(xué)習(xí).文獻(xiàn)［7］提出了連續(xù)狀態(tài)空間中 kNN-TD算法，從狀態(tài)分類(lèi)的角度來(lái)加快學(xué)習(xí)速度.文獻(xiàn)［8］提出了一種未知環(huán)境下基于有先驗(yàn)知識(shí)的滾動(dòng)Q學(xué)習(xí)算法.文獻(xiàn)［9-10］基于TD算法，提出了快速?gòu)?qiáng)化學(xué)習(xí)方法和自然梯度強(qiáng)化學(xué)習(xí)算法.在此基礎(chǔ)上，基于局部加權(quán) kNN-TD 算法［7，11-14］，本文提出了多機(jī)器人系統(tǒng)的無(wú)時(shí)滯異步的互增強(qiáng)學(xué)習(xí)策略.在全局通信和局部通信情況下，機(jī)器人通過(guò)比較自身和通信范圍內(nèi)的機(jī)器人Q值表，進(jìn)行選擇最優(yōu)動(dòng)作，實(shí)現(xiàn)無(wú)時(shí)滯條件下的多機(jī)器人系統(tǒng)的異步的交互增強(qiáng)學(xué)習(xí).最后，仿真實(shí)驗(yàn)進(jìn)一步驗(yàn)證了所提方法的可行性和有效性.

1 局部加權(quán)kNN-TD算法［14］

設(shè)機(jī)器人狀態(tài)為 s=［sd，sg］=［ρ1，ρ2，…，ρ12，sg］，其中 sd=［ρ1，ρ2，…，ρ12］表示環(huán)境信息，sg為目標(biāo)位置信息，ρ表示相應(yīng)傳感器工作區(qū)域范圍內(nèi)是否存在障礙，當(dāng)在范圍l0內(nèi)探測(cè)到障礙時(shí)，取值1；否則，取值0.建立以機(jī)器人為原點(diǎn)、前進(jìn)方向?yàn)閤軸正向、逆時(shí)針旋轉(zhuǎn)90°方向?yàn)閥軸正向的坐標(biāo)系.設(shè)機(jī)器人所處位置為(xp，yp)，其方向角為θp，目標(biāo)點(diǎn)位置為(xg，yg).得到目標(biāo)相對(duì)于機(jī)器人的位置(x'g，y'g)為

則機(jī)器人指向目標(biāo)點(diǎn)的方向角θg=atan(y'g/x'g).由于機(jī)器人的狀態(tài)數(shù)目過(guò)大，學(xué)習(xí)耗時(shí)很大，為此引入kNN-TD算法［7］.根據(jù)機(jī)器人前后左右的各部分狀態(tài)對(duì)其影響各不相同，將環(huán)境信息劃分為4 個(gè)部分，并配以不同的權(quán)重 ηp，p=1，2，3，4.對(duì)于目標(biāo)位置信息sg相同的狀態(tài)si和sj，定義其距離函數(shù)為

式中，di，j表示狀態(tài) si，sj的環(huán)境信息狀態(tài)的差別.選取最小的前k個(gè)di，j的狀態(tài)為狀態(tài)si的近鄰，記為knn(si)；同時(shí)易得其每一個(gè)近鄰的權(quán)值為ωi，j=1/(1+).在此基礎(chǔ)上，可求得狀態(tài) sj是狀態(tài)si近鄰的概率為

設(shè)si∈S，am∈A，其中 S為狀態(tài)集，A為動(dòng)作集，knn(si)表示狀態(tài) si的 k 近鄰集，Q(si，am)表示狀態(tài)si下動(dòng)作am的Q值.考慮近鄰的影響，定義Qknn(si)(si，am)為狀態(tài)si在選擇動(dòng)作am時(shí)近鄰集knn(si)的Q值期望，其可表示為

在初始階段，采取基于模擬退火的動(dòng)作選擇機(jī)制策略.狀態(tài)si的每一個(gè)動(dòng)作被選的概率如下:

式中，T為退火溫度，取值逐漸減小，T的大小決定了隨機(jī)性的程度，T越大，隨機(jī)性越大，反之越小.隨著學(xué)習(xí)的進(jìn)行，動(dòng)作選擇機(jī)制換為貪婪策略，即

考慮機(jī)器人在狀態(tài)si下執(zhí)行選擇動(dòng)作am，并轉(zhuǎn)移到一個(gè)新的狀態(tài)sk，并獲得獎(jiǎng)賞 r.利用近鄰集Q值函數(shù)［7］，得到狀態(tài)si下的Q值函數(shù)更新規(guī)則

式中，α∈(0，1)為學(xué)習(xí)率；δ為 TD 誤差.基于 TD算法，這里采用無(wú)策略(off policy)法，δ可表示為

2 基于全局通信條件的異步互增強(qiáng)學(xué)習(xí)

考慮傳統(tǒng)增強(qiáng)學(xué)習(xí)過(guò)程中，每個(gè)機(jī)器人都有其獨(dú)立的Q值表，Q值表更新由其自身反饋而決定.在全局通信條件下，機(jī)器人通過(guò)比較自身和通信范圍內(nèi)的機(jī)器人Q值表，進(jìn)行選擇最優(yōu)動(dòng)作.設(shè)未知環(huán)境中存在N個(gè)機(jī)器人，機(jī)器人間可實(shí)現(xiàn)無(wú)時(shí)滯通信，記為 Φ={Rbb=1，2，…，N}.確定機(jī)器人Rb的Q值更新規(guī)則為

由局部加權(quán)kNN-TD算法，可得到機(jī)器人Rb的狀態(tài)si下的Q值函數(shù)更新規(guī)則

和其近鄰集knn(si)中狀態(tài)sj的Q值函數(shù)更新規(guī)則

式中，α∈(0，1)為學(xué)習(xí)率；δ為 TD 誤差.δ可表示為

由此可得，機(jī)器人Rb在狀態(tài)sk的取動(dòng)作am時(shí)的近鄰集knn(sk)的最大Q值期望為

3 基于局部通信條件下的異步互增強(qiáng)學(xué)習(xí)

在大多數(shù)實(shí)際環(huán)境中，一方面通訊往往非全局的，另一方面隨著機(jī)器人數(shù)目增加，共享全局信息會(huì)增加計(jì)算量，且大量的數(shù)據(jù)通訊會(huì)造成信息堵塞.因而單體機(jī)器人往往只能與周?chē)欢ǚ秶鷥?nèi)的機(jī)器人進(jìn)行資源共享.考慮在局部通信條件下多機(jī)器人增強(qiáng)學(xué)習(xí)問(wèn)題，設(shè)單體機(jī)器人通訊半徑為c.設(shè)在t時(shí)刻，機(jī)器人Rb為中心的通訊范圍內(nèi)存在M個(gè)機(jī)器人，記為Φb={Rbb=1，2，…，M}，并設(shè)機(jī)器人間實(shí)現(xiàn)無(wú)時(shí)滯通信.則可設(shè)計(jì)機(jī)器人Rb的Q值更新規(guī)則為

不難得到機(jī)器人Rb的狀態(tài)si下的Q值函數(shù)更新規(guī)則與式(12)相同；另外，其近鄰集knn(si)中狀態(tài)sj的Q值函數(shù)更新規(guī)則與式(13)相同.這里，可進(jìn)一步得到δ為

由此可得，機(jī)器人Rb在狀態(tài)sk的取動(dòng)作am時(shí)的近鄰集knn(sk)的Q值期望為

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

為驗(yàn)證本文算法的有效性，將3個(gè)機(jī)器人R1，R2，R3放置于未知環(huán)境中，并設(shè)置參數(shù)如下:近鄰個(gè)數(shù)k=12，傳感器探測(cè)范圍l0=3，環(huán)境狀態(tài)各部分權(quán)重 η1=5，η2=10，η3=5，η4=1，學(xué)習(xí)率 α =0.4，折扣因子γ=0.5，如圖1所示.

圖1 多機(jī)器人學(xué)習(xí)環(huán)境

實(shí)驗(yàn)1 在全局通信的情況下，學(xué)習(xí)是分別給定機(jī)器人目標(biāo)位置，讓其自主運(yùn)動(dòng)，每個(gè)學(xué)習(xí)階段運(yùn)動(dòng)200步，經(jīng)過(guò)近40次的學(xué)習(xí)后，機(jī)器人R1，R2，R3能較好地運(yùn)動(dòng)到目標(biāo)點(diǎn).由于本實(shí)驗(yàn)中機(jī)器人的狀態(tài)數(shù)目過(guò)于龐大(212×12)，要達(dá)到最優(yōu)的學(xué)習(xí)效果還需數(shù)以億次的學(xué)習(xí)；但本算法只通過(guò)約8000步學(xué)習(xí)即取得了較好的學(xué)習(xí)結(jié)果，實(shí)驗(yàn)表明基于局部加權(quán)kNN-TD算法的全局通信條件下的多機(jī)器人互增強(qiáng)學(xué)習(xí)效果較優(yōu)，如圖2所示.

實(shí)驗(yàn)2 在局部通信的情況下，設(shè)機(jī)器人的通信半徑c=5.在局部通信下，雖然機(jī)器人的學(xué)習(xí)比全局通信條件下慢，但從仿真實(shí)驗(yàn)可以看出，機(jī)器人仍可較快地完成學(xué)習(xí)任務(wù)，如圖3所示.

圖2 全局通信條件下的異步互增強(qiáng)學(xué)習(xí)測(cè)試

圖3 局部通信條件下的異步互增強(qiáng)學(xué)習(xí)測(cè)試

5 結(jié)語(yǔ)

針對(duì)多機(jī)器人系統(tǒng)的增強(qiáng)學(xué)習(xí)問(wèn)題，首先基于環(huán)境感測(cè)和任務(wù)信息狀態(tài)，提出了k近鄰狀態(tài)選擇方案；在此基礎(chǔ)上，分別給出了全局通信和局部通信條件下的基于局部加權(quán)kNN-TD的多機(jī)器人系統(tǒng)的無(wú)時(shí)滯異步的互增強(qiáng)學(xué)習(xí)策略.下一步的主要工作是進(jìn)一步完善異步的交互學(xué)習(xí)策略，并進(jìn)行相關(guān)學(xué)習(xí)算法的性能比較研究；在此基礎(chǔ)上，對(duì)多機(jī)器人系統(tǒng)的增強(qiáng)學(xué)習(xí)算法的收斂性分析進(jìn)行研究.

References)

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

［2］高陽(yáng)，陳世福，陸鑫.強(qiáng)化學(xué)習(xí)研究綜述［J］.自動(dòng)化學(xué)報(bào)，2004，30(1):86-100.Gao Yang，Chen Shifu，Lu Xin.Research on reinforcement learning technology:a review［J］.Acta Automatica Sinica，2004，30(1):86-100.(in Chinese)

［3］郭銳，吳敏，彭軍，等.一種新的多智能體Q學(xué)習(xí)算法［J］.自動(dòng)化學(xué)報(bào)，2007，33(4):367-372.Guo Rui，Wu Min，Peng Jun，et al.A new Q learning algorithm for multi-agent systems［J］.Acta Automatica Sinica，2007，33(4):367-372.(in Chinese)

［4］張汝波，施洋.基于模糊Q學(xué)習(xí)的多機(jī)器人系統(tǒng)研究［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2005，26(4):477-481.Zhang Rubo，Shi Yang.Research on multi-robot system based on fuzzy Q-learning［J］.Journal of Harbin Engineering University，2005，26(4):477-481.(in Chinese)

［5］Desouky S F，Schwartz H M.Schwartz.Q(λ)-learning fuzzy logic controller for a multi-robot system［C］//IEEE International Conference on Systems，Man and Cybernetics.Istanbul，Turkey，2010:4075-4080.

［6］Hu Zhaohui，Zhao Dongbiao.Reinforcement learning for multi-agent patrol policy［C］//The 9th IEEE International Conference on Cognitive Informatics.Beijing，China，2010:530-535.

［7］Martin J A H，de Lope J，Maravall D.Robust high performance reinforcement learning through weighted k-nearest neighbors［J］.Neurocomputing，2011，74(8):1251-1259.

［8］胡俊，朱慶保.未知環(huán)境下基于有先驗(yàn)知識(shí)的滾動(dòng)Q學(xué)習(xí)機(jī)器人路徑規(guī)劃［J］.控制與決策，2010，25(9):1364-1368.Hu Jun，Zhu Qingbao.Path planning of robot for unknown environment based on prior knowledge rolling Q-learning［J］.Control and Decision，2010，25(9):1364-1368.(in Chinese)

［9］童亮，陸際聯(lián)，龔建偉.一種快速?gòu)?qiáng)化學(xué)習(xí)方法研究［J］.北京理工大學(xué)學(xué)報(bào)，2005，25(4):328-331.Tong Liang，Lu Jilian，Gong Jianwei.Research on fast reinforcement learning［J］.Transactions of Beijing Institute of Technology，2005，25(4):328-331.(in Chinese)

［10］陳圣磊，谷瑞軍，陳耿，等.基于TD(λ)的自然梯度強(qiáng)化學(xué)習(xí)算法［J］.計(jì)算機(jī)科學(xué)，2010，37(12):186-189.Chen Shenglei，Gu Ruijun，Chen Geng，et al.Natural gradient reinforcement learning algorithm with TD(λ)［J］.Computer Science，2010，37(12):186-189.(in Chinese)

［11］A k-NN based perception scheme for reinforcement learning［J］.Lecture notes in Computer Science，2007，4739:138-145.

［12］Martin J A H，de Lope J.Ex＜α＞:an effective algorithm for continuous actions reinforcement learning problems［C］//The 35th IEEE Annual Conf on Industrial Electronics Society.Oporto，Portugal，2009:2063-2068.

［13］Martin J A H，de Lope J，Maravall D.The kNN-TD reinforcement learning algorithm［J］.Lecture Notes in Computer Science，2009，5901:305-314.

［14］韓飛，金露，楊月全，等.基于局部加權(quán)kNN-TD增強(qiáng)學(xué)習(xí)的機(jī)器人運(yùn)動(dòng)控制［C］//第十屆全球智能控制與自動(dòng)化大會(huì).北京，2012.(待發(fā)表)Han Fei，Jin Lu，Yang Yuequan，et al.Research on robot motion control based on local weighted kNN-TD reinforcement learning［C］//The 10th World Congress on Intelligent Control and Automation.Beijing，2012.(to appear)