賀薈霖

（西南交通大學電氣工程學院，成都 611756）

0 引言

覆蓋問題是研究多智能體系統(tǒng)的重要課題之一，在搜救、清掃、耕種等領域都有著很大的應用價值。覆蓋問題理論上需采用移動機器人或是固定傳感器，通過物理接觸或者傳感器感知的方式來遍歷目標區(qū)域，盡可能滿足重復率、完整率、資源消耗這三方面的優(yōu)化目標[1]。多智能體覆蓋問題主要研究如何有效組織多個智能體進行通信、任務分配和協(xié)調(diào)工作。文獻[1]系統(tǒng)闡述了多機器人覆蓋問題的定義、分類和應用，指出了該領域前沿的研究和發(fā)展方向；文獻[2]提出一種新的方法來規(guī)劃移動機器人的覆蓋路徑，從點的覆蓋引申到區(qū)域的覆蓋最終實現(xiàn)工作區(qū)的全覆蓋；文獻[3]針對移動傳感網(wǎng)絡提出了一種自適應控制率來保證避障的同時完成覆蓋任務。

本文主要采用強化學習算法實現(xiàn)未知環(huán)境下的多智能體覆蓋問題，傳統(tǒng)強化學習算法的策略搜索方法采用盲目性搜索方式，智能體通過無限次地對策略進行遍歷而學習到最優(yōu)策略，但因此導致了學習速度慢和計算資源消耗大的問題[4]。目前，啟發(fā)式搜索與強化學習算法已經(jīng)得到了一定的結合，成為一種重要的加速學習的手段，比如文獻[5]采用啟發(fā)函數(shù)H來指導智能體的動作選擇，首先提出一種啟發(fā)式強化學習算法（Heuristically Accelerated Q-Learning，HAQL）來加速 Q學習收斂，該算法將學習過程分為結構提取和反向傳播啟發(fā)兩個階段，有效加速了強化學習的學習速度。因此，有必要進一步研究啟發(fā)式強化學習在多智能體覆蓋問題方面的應用，以加快多智能體覆蓋問題的收斂速度。

1 強化學習算法

Q學習算法作為一種常用的強化學習算法，采用評估函數(shù)Qt(st,at)表示在狀態(tài)st下，執(zhí)行動作at，該狀態(tài)-動作對得到的最大的累積折扣回報。該函數(shù)有界且迭代逼近Q值，每個狀態(tài)-動作對作為策略都會被訪問有限次。Q值更新規(guī)則為：

上式中s表示當前狀態(tài)，a表示在狀態(tài)s下采取的動作，r表示得到的立即回報，s'為新的狀態(tài)，γ為折扣因子（0<γ<1），α為學習率（α>0）。Q學習的動作選擇策略一般采用ε-貪婪策略：

上式中q表示分布于[0,1]的隨機數(shù)，ε表示探索率，ε越大選擇隨機探索動作的概率越大，arandom表示當前狀態(tài)下可選動作集合中的一個隨機動作。

2 多智能體啟發(fā)式強化學習算法設計

鑒于智能體需要迭代估算Q值，策略范圍越大就需要越久的時間來試錯式地探索狀態(tài)-動作空間，多智能體強化學習在每個狀態(tài)下將各智能體選擇的動作作為一個聯(lián)合動作考慮，使得學習過程更加復雜，耗時更久，因此可引入啟發(fā)式搜索來加速強化學習收斂。啟發(fā)式強化學習算法在多智能體強化學習過程中采用一個啟發(fā)函數(shù)H:S×→R來影響聯(lián)合動作，指導動作選擇[6]。Ht（st）表示在狀態(tài)st下執(zhí)行聯(lián)合動作→的重要性。因此動作選擇策略在式（2）的基礎上添加了啟發(fā)函數(shù)的影響，調(diào)整為：

其中ξ為衡量啟發(fā)函數(shù)重要性的實變量。啟發(fā)函數(shù)的定義為：

其中η為一個較小的實數(shù)，πH表示在啟發(fā)函數(shù)指導下的聯(lián)合動作。

啟發(fā)函數(shù)的先驗知識來源可以是多樣的，傳統(tǒng)的HAQL算法先驗知識來源于多智能體自身的學習經(jīng)驗，學習過程分為兩個階段，第一階段稱為結構提取，在智能體與環(huán)境的交互初始階段，通過探索標記智能體每個動作得到的結果，從而獲取一定的環(huán)境結構信息，得到狀態(tài)轉移概率的粗略估計；第二階段稱為啟發(fā)式反向傳播，在已獲得的結構信息基礎上從終態(tài)出發(fā)反向傳播，給出到達這些狀態(tài)的正確的策略，由此構建啟發(fā)函數(shù)，根據(jù)啟發(fā)的指導進行迭代收斂。

3 基于HAQL的多智能體覆蓋算法設計

多智能體覆蓋問題的研究主要在于其路徑規(guī)劃算法上，不同的覆蓋算法對多智能體的通信方式和環(huán)境地圖有著不同的要求。對于完全通信的多智能體系統(tǒng)，在未知環(huán)境中的覆蓋問題，采用啟發(fā)式強化學習的方式實現(xiàn)覆蓋任務，可以用一個四元組模型M=來描述該學習過程，其中：

S，表示智能體所處環(huán)境的所有可能狀態(tài)的集合，它是一個表示環(huán)境狀態(tài)的有限集，采用柵格地圖表示環(huán)境信息，將環(huán)境分解為小柵格，柵格狀態(tài)分為占用（有障礙物）、未占用（無障礙物）、興趣點（需遍歷的目標點）三種情況，將地圖狀態(tài)存入二維數(shù)組；

Ai，表示智能體i能夠執(zhí)行的所有可能動作的集合，每個機器人可選的動作包括上、下、左、右4種，則n個智能體組成的聯(lián)合動作有4n種，標記為A=A1×…×An；

T，表示狀態(tài)轉移函數(shù)，T(s'|s,a)為智能體在狀態(tài)s下采取動作a，可能轉移到狀態(tài)s’的概率；

R，表示回報函數(shù)，表示為S×A→R，是當在狀態(tài)s下采取動作a所獲得的即時回報值R（s,a）；

由模型可知，多智能體覆蓋問題的強化學習包括環(huán)境模型狀態(tài)表示、動作策略、狀態(tài)轉移和獎懲分配等基本要素，智能體在學習覆蓋過程中不斷與環(huán)境進行交互，所有狀態(tài)轉移組成的序列即為智能體的運動軌跡。對多智能體覆蓋問題而言，狀態(tài)轉移過程非常復雜，計算量大且收斂速度慢，因此引入啟發(fā)式搜索在一定程度上約束策略搜索范圍，指導智能體進行動作選擇，以加速學習過程。構建啟發(fā)函數(shù)所需的先驗知識由智能體事先對環(huán)境進行結構提取而得到，基于HAQL的多智能體覆蓋算法流程圖見圖1中，算法分為結構提取和反向傳播啟發(fā)兩個階段。

圖1 基于HAQL的多智能體覆蓋算法流程圖

4 仿真結果

為驗證本文提出的基于HAQL的多智能體覆蓋算法的可行性和有效性，在MATLAB仿真環(huán)境中構建如圖2所示覆蓋地圖。在一個10×10的格子世界中，黑色柵格表示邊界及障礙物（不可達），其他柵格均可達，其中藍色柵格表示需要遍歷的興趣點，紅、綠柵格分別表示兩個智能體的固定起點位置。兩智能體的任務是執(zhí)行聯(lián)合動作尋找合適的策略最終成功遍歷四個興趣點。

圖2 多智能體覆蓋仿真環(huán)境

對智能體而言，環(huán)境的邊界、障礙和興趣點的位置事先均未知，需要在探索的過程中不斷學習環(huán)境信息。智能體執(zhí)行動作到達興趣點時獲得回報值100，遇到邊界、障礙或其他智能體時獲得回報值-1，到達其余位置時回報值為0。若一次任務執(zhí)行步數(shù)超過500步還未遍歷全部興趣點則認為覆蓋失敗，開始新一幕實驗。實驗相關參數(shù)設置如表1所示。

表1 仿真實驗參數(shù)設置表

基于HAQL的多智能體覆蓋算法可以在經(jīng)過一定學習幕數(shù)后達到收斂，圖3給出了算法收斂后其中一幕覆蓋任務的完成情況，圖中紅色與綠色的線段分別反映了兩智能體在此次覆蓋過程中走過的路徑，可以看出多智能體通過聯(lián)合動作選擇成功地遍歷到四個興趣點，成功完成了覆蓋任務。

針對相同的多智能體覆蓋仿真環(huán)境，分別采用傳統(tǒng)的Q學習算法和啟發(fā)式的HAQL算法進行實驗，實驗主要從覆蓋問題收斂速度和達到收斂后完成實驗所需步數(shù)的角度考察實驗效果。實驗結果有著明顯不同的學習表現(xiàn)，算法對比圖如圖4所示。橫軸表示學習幕數(shù)，縱軸表示每一幕學習完成覆蓋任務所需步數(shù)。實際實驗步數(shù)對比和擬合曲線對比均可明顯看出兩種算法在經(jīng)過一定的學習幕后都能收斂到穩(wěn)定的策略，即步數(shù)。實驗設置HAQL算法在前20幕進行結構提取，此時的動作選擇策略與Q學習相同，在第21幕時根據(jù)已獲知的環(huán)境信息構建啟發(fā)函數(shù)，在啟發(fā)函數(shù)的指導下進行動作選擇，因此在21幕后學習步數(shù)驟降，有效加速了強化學習進程，更快地達到覆蓋問題的收斂，并在達到收斂后與Q學習算法有著不相上下的覆蓋效果，即最終收斂步數(shù)相似。

圖3 基于HAQL的多智能體覆蓋結果

圖4 多智能體覆蓋算法對比圖

通過10次實驗取平均收斂幕和收斂步數(shù)，對比結果如表2所示，收斂幕表示從該幕起算法達到收斂，反映學習速度；收斂步數(shù)表示學習收斂后平均完成一次覆蓋任務所需步數(shù)，反映學習策略。從數(shù)據(jù)的角度可以明顯看出HAQL算法優(yōu)化了強化學習進程收斂速度的同時，保持了收斂后與Q學習算法相近的覆蓋效果。

表2 兩種學習算法效果數(shù)據(jù)對比

5 結語

本文提出了一種基于啟發(fā)式強化學習的多智能體覆蓋算法，在傳統(tǒng)強化學習算法中引入啟發(fā)函數(shù)指導多智能體聯(lián)合動作的選擇，先驗知識來源于智能體自身對環(huán)境的結構提取，通過仿真實驗對比驗證了算法在多智能體覆蓋問題中能有效加速強化學習進程且不影響最終收斂后的覆蓋效果，成功降低了覆蓋問題的資源消耗。

[1]蔡自興,崔益安.多機器人覆蓋技術研究進展[J].控制與決策,2008,23（5）：481-486.

[2]Bretl T,Hutchinson S.Robust Coverage by a Mobile Robot of a Planar Workspace[R].Karlsruhe,Germany,IEEE International Conference on Robotics and Automation（ICRA）,2013.

[3]Hussein I,Stipanovic D M.Effective Coverage Control for Mobile Sensor Networks With Guaranteed Collision Avoidance[J].IEEE Transactions On Control Systems Technology,2007,15（4）：642-657.

[4]Wiering M,Otterlo V M.Reinforcement Learning:State-of-the-art[M].New Yord：Springer,2012：27-34.

[5]Bianchi R A C,Ribeiro C H C,Costa A H R.Heuristically Accelerated Q-Learning:a New Approach to Speed Up Reinforcement Learning[C].SBIA.2004:245-254.

[6]Bianchi R A C,Martins M F,Ribeiro C H C,et al.Heuristically-Accelerated Multiagent Reinforcement Learning[J].IEEE Transactions on Cybernetics,2014,44（2）:252-265.