動態環境中的多機器人協同搬運

曹 潔，朱寧寧

蘭州理工大學 計算機與通信學院，蘭州 730050

動態環境中的多機器人協同搬運

曹 潔，朱寧寧

蘭州理工大學 計算機與通信學院，蘭州 730050

1 引言

多機器人系統是一個集環境感知、動態決策、行為執行等多功能的復雜系統。隨著多機器人在工業生產、醫療服務、航空航天等方面的應用，多機器人協作成為機器人學研究的熱點。而多機器人協同搬運問題無論是在理論層面還是在應用上都有著非常廣闊的研究價值，一方面在真實的物理世界中，單個機器人通常無法完成很多任務，另一方面，它也是研究多機器人協同任務的一個重要平臺[1]。

針對多機器人的避障問題，已經提出了很多的方法，如模擬市場法、柵格法和基于行為的控制方法等。基于行為的控制方法由著名人工智能專家R.Brooks首先提出來，較于傳統方法，具有魯棒性好、快速性[2]等優點而得到廣泛關注。由于多機器人工作環境的易變性和不可預見性，需要多機器人盡可能的適應環境，以提高學習和決策能力。Q學習[3-4]無需建立環境模型，且可在線學習，被用于多機器人避障問題中，但是，并不十分理想。這是因為隨著多機器人數量增加，學習空間也快速增大，造成了學習速度非常緩慢，且環境信息不完備時，聯合學習模型也難以適用。有學者將Q學習中的“狀態-動作對”替換為“條件-行為對”，雖具有一定的有效性，但還是無法克服此問題；分布式兩層強化學習算法也被用于多機器人協作中，實驗驗證了其實際功能，但仍無法較大地減小存儲空間；將基于動作預測的強化學習算法用于多機器人協同搬運問題會大大促進協作性能，缺點是在環境信息較少或者機器人存在自私目標的情況下難以適用。Q學習是通過獎勵值來強化正確的行為，它是一種數值分析方法，此方法忽略了多機器人的推理能力，而引入BDI模型能夠有效解決Q學習推理能力較弱的弊端[5-6]，因此本文中的多機器人采用基于BDI模型的獨立強化學習，使得多機器人學習過程不僅擁有強化學習的自適應性和高度反應性，而且擁有了推理功能。

本論文的創新點有：（1）本文將強化學習算法、BDI模型、基于行為的協同方法三者結合運用于多機器人協同搬運問題，并從仿真實驗看，取得了較好的效果。（2）本文采用強化學習的評價函數是隨多機器人系統位置及離最近障礙物距離而變化的，評價函數可實時更新，并將其與基于強化學習的行為權重相結合，都使得本實驗取得良好仿真效果。

2 Q(λ)學習算法

馬爾可夫決策過程[7]中，多機器人所處的環境狀態表示為狀態集合動作集合描述為多機器人在狀態st下，選擇動作at并且執行。同時，狀態轉換為st+1，然后從環境中得到了強化信號rt。

Q學習是一類被廣泛應用的強化學習算法[8]，它用函數Q(x，a )表達與各個狀態相對應的動作的評估。其表達式為：

由于強化學習系統的目的是使得總的獎勵值達到最大，因此，用可得：

在時刻t，多機器人根據當前的狀態選擇一個動作a，然后，根據以下表達式更新Q值：

3 基于強化學習的BDI協作模型

“信念-愿望-意向”（BDI）多機器人系統根據內部的心智狀態產生動作進而影響周圍環境。BDI多機器人系統有3個主要心智狀態：信念（belief），愿望（desire）和意向（intention），分別代表多機器人所具有的信息、動機和決策。而在多機器人BDI模型中，信念代表多機器人對當前的環境與自身可能要采取的行為估計；愿望代表多機器人對未來環境與自身可能要采取行為的喜好；意向代表多機器人為了達到某個目的做出的承諾。

BDI Robot的求解意見過程驅動手段-目的的推理，同時還需要滿足幾個其他的約束：產生的意見必須和Robot當前的信念及意圖一致；其次，應能識別環境變化的趨勢，提供Robot獲得意圖的新方法或者新的可能性。一個BDI Robot慎思過程用過濾函數表示，過濾函數根據Robot當前的意圖、信念和愿望來刷新Robot的意圖。它需要丟棄無法完成的或者已經無意義的意圖，為不能實現的意圖選擇新的實現方法及意圖。

在多機器人系統體系結構中可由E（環境）引起最初的變化。當環境變化時，機器人將收到新的信息來更新自身的bel（信念）。通過環境感知函數sence，機器人可感知到環境的變化。每當環境發生變化，機器人將及時更新自身的bel（信念）以滿足新的變化的要求。機器人的bel是在開放的環境下，處于動態變化之中。Bel變化將引起des（愿望）變動，des變動會影響int（意向）的選擇及要采取的行為，最終影響整個環境發生變化。機器人的變動為一種鏈式反應，E變化引起bel、des和int變化，最終又影響到E。

此動態模型的具體定義：

（4）感知函數sence：ρ(bel)×e→ρ(bel)，該函數跟據當前對環境的感知和信念確定新的信念集合。

（5）意見函數opinion：ρ(bel)×ρ(int)→ρ(des)，該函數跟據當前環境的感知和意圖的執行確定一個新目標。

（6）過濾函數filter：ρ(bel)×ρ(des)×ρ(int)→ρ(int)，該函數依據Robot當前的意圖、信念及愿望更新Robot的意圖。

（7）行為函數action：Roti×ρ(int)→Roti×E，若i=j為內部行為，若i≠j，則為外部行為。

{S，G，R，B，D，I，λ}中，S為離散的狀態空間，G為協同求解的目標，R為多機器人的集合，B為多機器人的信念集合，D為多機器人的愿望集合，I為多機器人的意圖集合，λ={λ1，λ2，…，λn}為多機器人問題求解時的價值系數集合，λ∈(0，1)。通常情況下，由于每個Robot都是依據自身的局部規劃來進行局部求解，卻不考慮其他Robot的動作規劃，因此Robot之間必然會存在意圖沖突，從而使式（8）成立：

意圖是多機器人系統的內部動力，而不穩定性主要源于意圖沖突。由動力學理論，系統的運動總趨向穩定平衡態而遠離不穩定平衡態。針對多機器人系統，不管是協作還是沖突，最終總要達到某個穩定點或平衡點。如果將系統內的多機器人分為兩部分：意圖有沖突的Robot與意圖無沖突的Robot，則可把系統看作雙矩陣對策系統。依據Nash定理，它必然存在混合策略平衡。若假定所有Robot學習同一個Nash平衡，這將使得每一個Robot的選擇能夠最優地響應其他Robot的選擇，因此式（9）得以成立：

這樣在系統中，所有Robot能夠追求共同最優解，即追求最大限度地實現整體聯合意圖。

信息完備時，聯合學習模型能有效實現多機器人協作，但當機器人得不到完整信息時，此方法難以使用。在信息不完備的情況下，多機器人采用獨立學習的方式。機器人不知道其他機器人的行為策略，每個機器人進行獨立學習，它依據自身得到的獎勵維護狀態動作對的Q值表，每一Q值表示某個優化策略在此狀態動作對的獎勵值。已有文獻[9]證明了信息不完備時采用此規則進行獨立強化學習能使得多機器人協作決策過程得以收斂。多機器人之間不能交互行為策略時，某一狀態，多機器人依據Q值表執行動作，且根據反饋得到的獎勵值更新Q值表。

BDI模型通過形式化心智成分和邏輯推理實現多機器人行為的自主性和理性，強化學習通過感知環境狀態和得到的獎勵值學習系統的最優行為策略。單獨使用符號推理的邏輯方法無法使得效用最佳，而數值分析的強化學習也忽略了推理的環節，對于多機器人系統來說，既需要對于環境信息推理，又要經過學習不斷地強化正確行為使之得到最大的收益，因此，將強化學習和BDI模型結合起來研究多機器人協作問題。

3.1 基于權重的行為機制

搬運物體分為兩個部分：（1）躲避障礙物；（2）向目標區域前進。在整個多機器人的協同搬運中，都是由這兩個行為組成，但是，每個行為重要性是不同的。描述為：

其中，Weightavoid和Weightbin是躲避障礙物和向目標區域前進的權重。MS-AVOID-OBSTACLES、MS-MOVE-TO-OBJECTBIN分別代表躲避障礙物、向目標區域前進兩個行為。

3.2 基于強化學習的行為權重

多機器人協同搬運過程中，不同的行為具有各自的權重，且在不相同的環境中各行為的重要性也有區別，為了能夠使得行為權重依據環境自動進行調整，采取了強化學習自動學習理想的權重組合，以使得機器人能夠像人類一樣的學習，完成協同搬運過程。

學習初期，各行為權重都設有初始值，學習過程中，根據環境反饋的信息，運用評價函數r對權重評價，當完成一次協同搬運后，此權重就會被重新進行計算：

若完成協同搬運過程，則r為正，就使得當前權重值增大；當未完成時，r為負值，使得當前權重值減小。評價函數定義為：

式中，xavg表示在tmin時間間隔內，多機器人系統的位置；xt表示最近障礙物的位置；a是安全閾值。

3.3 距離最近原則的多機器人協同搬運

距離最近原則即為在全部協同搬運的多機器人中，選擇距離障礙物最近的機器人作為主機器人，由其發出指令進而控制其他的機器人執行動作。如式（12）。在搬運過程中，設離障礙物最近的作為主機器人，指揮其他從機器人行動。

其中，Rmain為主機器人，Rn為n號機器人，DistanceRmin為機器人距離障礙物最近的距離，DistanceRn為機器人N到障礙物的距離。

4 仿真實驗

4.1 實驗場景

為了驗證將BDI模型和強化學習相結合引入多機器人協同搬運過程的有效性，在仿真環境下對其進行驗證。四個機器人站在兩兩互成90°角的等分點上抬著圓桶在如圖所示的障礙物環境中，將圓桶搬運至目的地，本次實驗任務假定該物體是密度分布均勻的，實驗環境如圖1所示，實心物體代表障礙物，空心圓代表整個多機器人系統及圓桶的出發地。

圖1 障礙物、目標區域位置設置

其中，出發地內圓桶與四個機器人的位置分布放大圖如圖2所示，虛線代表出發地，空心圓代表圓桶，四個實心圓分別代表四個機器人。

圖2 出發地內四個機器人與圓桶的位置放大圖

4.2 強化學習單元

（1）評價函數的表示

在多機器人協同搬運過程中，各子行為初始權重分別設置為Weightavoid=1，Weightbin=1，各權重相應的強化學習評價函數如下：

（2）狀態空間的表示

多機器人系統的狀態空間S：

其中，dl是多機器人系統左側距障礙物的距離，df是多機器人系統前方距障礙物的距離，dr是多機器人系統右側距障礙物的距離，dg是多機器人系統與目標點之間的距離，

θ是多機器人系統當前方向與目標點的夾角。用這5個量作為狀態空間的5個維度，多機器人系統和障礙物的距離定義

（3）動作空間的表示

多機器人系統的動作空間A：

其中，a1為機器人轉動+15°同時前進；a2為機器人轉動-15°同時前進；a3為機器人轉動+10°同時前進；a4為機器人轉動-10°同時前進；a5為機器人前進。

t時刻多機器人系統的狀態St為一個五維向量：

4.3 動作選擇策略

學習的初始階段，因其Q值是隨機初始化，所以不具任何意義。為了探索到全部可能的動作，引入Boltzmann分布實現初始階段動作的隨機選擇，某個動作被選擇的概率為：

圖3 機器人、障礙物和目標點的位置圖

式中，T為虛擬溫度，隨著溫度增加，選擇的隨機性也加強。

隨著學習的進程，Q值慢慢趨向于所期望的狀態-動作值，此時，根據貪婪策略選擇動作，即選擇最大的Q值對應著的動作。

為了顯示出強化學習算法與BDI模型結合的有效性及優越性，共進行了三次實驗：

（1）原始強化學習算法用于多機器人協同搬運，如圖4所示。

圖4 原始強化學習算法用于多機器人協同搬運軌跡圖（多次學習后）

（2）強化學習與BDI模型用于多機器人搬運（學習初期），如圖5所示。

圖5 強化學習與BDI模型用于多機器人搬運軌跡圖（學習初期）

（3）強化學習與BDI模型用于多機器人協同搬運，如圖6所示。

圖6 強化學習與BDI模型用于多機器人協同搬運軌跡圖

并且，比較了強化學習-BDI模型結合與原始強化學習算法的循環次數與成功次數的效果，如圖7所示。

圖7 循環次數與成功次數的仿真結果

4.4 實驗結果與分析

由圖4和圖7可以看出，原始強化學習算法在多機器人協同搬運過程中，經過較多次學習，機器人還是總與障礙物相撞，這是因為強化學習算法存儲空間很大，學習速度很慢，并且不具備推理能力，在環境信息不完備的情況下，聯合學習模型難以適用；將BDI模型與強化學習結合起來用于多機器人協同搬運時，多機器人系統在一個存在隨機設置障礙物的環境中運行，在初始階段，由于多機器人處于隨機選擇動作的階段，因此運行中路線不平滑；但是經過多次學習后，多機器人能夠實現在躲避障礙物的條件下順利到達目標區域，并且運行軌跡比較平滑。隨著學習的持續，運行效果也越來越好。這是因為BDI模型的引入能夠有效解決強化學習推理能力弱的問題。

5 結束語

將多機器人系統的獨立強化學習與BDI模型相結合，使得多機器人系統不僅具有強化學習的自適應性和高度反應性，而且也擁有了BDI模型的推理能力，這就使只用數值分析卻忽略推理環節的強化學習方法結合了邏輯推理方法。在使用此方法后，有效地減少了多機器人系統與障礙物發生碰撞的次數，增大了實現協同搬運的成功率，具有良好的學習效果。仿真結果也表明了此方法的有效性，可以滿足多機器人系統的要求。本文主要是把此方法用在靜障礙物的情形下，今后的工作是把此方法應用到更為復雜的環境中，實現更多的功能。

[1]Bauer A，Wollherr D，Buss M.Human-robot collaboration：a survey[J].International Journal of Humanoid Robotics，2008，5（1）：47-66.

[2]Jan G E，Chang K Y，Parberry I.Optimal path planning for mobile robotnavigation[J].IEEE-ASME Transactionson Mechatronics，2008，13（4）：451-460.

[3]Busoniu L，Babuska R，De Schutter B.A comprehensive survey ofmultiagentreinforcementlearning[J].IEEE Transactions on Systems，Man and Cybernetics，2008，38（2）：156-172.

[4]Hwang K S，Ko Y C，Alouini M S.Performance analysis of incremental opportunistic relaying over identically and nonidentically distributed cooperative paths[J].IEEE Trans on Wireless Commun，2009，8（4）：1953-1961.

[5]樸松昊，孫立寧，鐘秋波.動態環境下的多智能體機器人協作模型[J].華中科技大學學報，2008，36（10）：39-52.

[6]樊建，鄭昌陸，費敏銳.基于角色變換和強化學習的多機器人協同仿真[J].系統仿真學報，2009，21（21）：6964-6967.

[7]顏振亞，鄭寶玉，林志偉.無線傳感器網絡中機會協作傳輸及其性能研究[J].電子與信息學報，2009，31（1）：215-218.

[8]Gosavi A.Reinforcement learning：a tutorial survey and recent advances[J].INFORMS Journal on Computing，2009，21（2）：178-192.

[9]Juang C F，Hsu C H.Reinforcement interval type-2 fuzzy controller design by online rule generation and Q-value-aided antcolony optimization[J].IEEE Transon Systems，Man and Cybernetics Part B，2009，39（6）：1528-1542.

CAO Jie,ZHU Ningning

College of Computer and Communication,Lanzhou University of Technology,Lanzhou 730050,China

In the multi-robot cooperative carrying process,traditional reinforcement learning only uses numerical analysis and ignored reasoning approach.To solve this problem,independence reinforcement learning for multi-robot combines with Belief-Desire-Intention（BDI）model,which makes reinforcement learning link logical reasoning capabilities.And the distance nearest principle is employed which means that the nearest robot ranged from obstacles is the leader robot to control other robots move.Evaluation function which changes with the location of multi-robot and the barriers is proposed,and it combines with the behavior weight based on reinforcement learning which becomes more and more optimized through constantly interacting with the environment.Simulation results show that this method is feasible,and the cooperative carrying process can be successfully achieved. Key words：multi-robot;reinforcement learning;cooperative carrying;obstacle avoidance

在多機器人協同搬運過程中，針對傳統的強化學習算法僅使用數值分析卻忽略了推理環節的問題，將多機器人的獨立強化學習與“信念-愿望-意向”（BDI）模型相結合，使得多機器人系統擁有了邏輯推理能力，并且，采用距離最近原則將離障礙物最近的機器人作為主機器人，并指揮從機器人運動，提出隨多機器人系統位置及最近障礙物位置變化的評價函數，同時將其與基于強化學習的行為權重結合運用，在多機器人通過與環境不斷交互中，使行為權重逐漸趨向最佳。仿真實驗表明，該方法可行，能夠成功實現協同搬運過程。

多機器人；強化學習；協同搬運；避障

A

TP242

10.3778/j.issn.1002-8331.1202-0215

CAO Jie,ZHU Ningning.Multi-robot cooperative carrying in dynamic environment.Computer Engineering and Applications,2013,49（23）：252-256.

曹潔（1966—），女，博士生導師，教授，主要研究領域為智能交通系統、信息融合理論及應用；朱寧寧（1986—），女，碩士。E-mail：307516638@qq.com

2012-02-13

2012-03-23

1002-8331（2013）23-0252-05

CNKI出版日期：2012-06-15 http://www.cnki.net/kcms/detail/11.2127.TP.20120615.1726.038.html