李劍平，陳 瑋，陳樹斌

（廣東工業(yè)大學 自動化學院，廣東 廣州 510006）

0 引 言

家庭服務機器人仿真比賽立足于探索服務機器人的高層功能的，目前主要包括人機對話、自動規(guī)劃和推理等。將服務機器人實體抽象為3D 仿真機器人，并通過建立仿真的室內(nèi)環(huán)境為測試環(huán)境，將人機交流抽象為自然語言或命令語言表達的任務描述，將機器人對環(huán)境的感知數(shù)據(jù)抽象為文件格式的場景描述，從而便于研究服務機器人的高層功能［1］。在比賽當中要求求解程序?qū)Ρ荣惼脚_提出的問題，根據(jù)其場景描述、任務描述、補充信息、約束信息等，在規(guī)定時間內(nèi)自動規(guī)劃生成完成該任務的原子行動序列，比賽平臺將根據(jù)這些行動序列的性能給求解程序打分［2］。

在家庭服務機器人仿真比賽中，每次任務會有多個目標，機器人通過達到各個目標來達到服務效果，從而獲得比賽的分數(shù)。而完成同樣的任務可以有多種的方式，完成的順序不限，且可以在完成一個目標的過程中穿插完成其他目標。所以這就對機器人的規(guī)劃提出了要求，即如何用最少的動作，最簡潔的方式來完成任務，從而讓服務機器人的服務更加智能化，進而在比賽中取得更高的分數(shù)。

各參賽隊伍的規(guī)劃方式有很多種，如A＊算法、ASP回答集編程、貪心算法等等。這些算法各有優(yōu)劣，A＊算法基于整個場景的狀態(tài)轉(zhuǎn)換計算，計算速度良好、可以得到較優(yōu)的規(guī)劃，但其占用系統(tǒng)資源多，且不能良好地處理物品選擇問題；ASP 回答集編程利用窮舉法并加以篩選，規(guī)劃較為完善，但處理較長的任務時計算時間過長，有時不能在比賽規(guī)定時間范圍內(nèi)完成規(guī)劃；貪心算法雖然計算速度快，但容易陷入局部最優(yōu)值，不能得到全局最優(yōu)解，規(guī)劃效果差。

1 進化算法

1.1 進化算法簡介

進化算法（evolutionary algorithm，EA）是一類隨機優(yōu)化算法，其中包括遺傳算法（GA）、進化策略（ES）和進化規(guī)劃（EP）等。它們利用某些啟發(fā)式規(guī)則進行優(yōu)化，其思想根源來自于進化論［3］。國內(nèi)外許多大學及科研機構(gòu)的研究人員正在努力從事這方面的研究，而對進化算法的改進也層出不窮，如混合混沌進化算法［4］、動態(tài)位置可變進化算法［5］、多智能體混合進化算法［6］等等。

1.2 進化算法一般步驟

（1）進行編碼，將待解決的問題轉(zhuǎn)化為進化算法便于計算的形式；

（2）產(chǎn)生初始種群；

（3）進行交叉、變異等計算產(chǎn)生新的個體；

（4）使用適應度函數(shù)對種群內(nèi)的個體進行評價；

（5）選擇種群中優(yōu)化程度更高的個體作為新一代種群；

（6）若未達到穩(wěn)定的最優(yōu)解則返回第三步再次進化；

（7）得到最優(yōu)解后解碼輸出結(jié)果。

1.3 新結(jié)構(gòu)建立的必要性

為了使家庭服務機器人的規(guī)劃問題轉(zhuǎn)化為便于進化算法的計算，需要找到一個合適的結(jié)構(gòu)作來描述機器人的任務，從而以之作為基礎進行規(guī)劃。

在家庭服務機器人仿真比賽中，任務的目標多種多樣，為達到目標所需做出的動作也有很多的變化，下面給出某一個任務的例子和可能用來完成任務的一種方法，見表1。

表1 機器人規(guī)劃范例

例中目標數(shù)量為6，若以目標為規(guī)劃基礎，對其進行排序規(guī)劃，其情況種類較少，且不能在完成某個目標過程中穿插完成其他目標，因而規(guī)劃效果不佳。而動作輸出的條數(shù)和內(nèi)容都不定，且動作較多，計算復雜度高，也不適合作為規(guī)劃的基礎。

可見，基于目標的規(guī)劃或者基于動作的規(guī)劃效果和效率不會很高，因此本文將引入一個介于兩者之間的新的結(jié)構(gòu)，作為規(guī)劃的基礎。這個結(jié)構(gòu)需要達到歸一化的效果，并能完整地表示任務中的信息，且有一定的操作空間，便于對其進行評價，適合以進化算法進行優(yōu)化，最終還能方便地解析成動作序列。

2 算法的改進

本文利用傳統(tǒng)的進化算法進行改進，根據(jù)比賽需求建立新的編碼方式，采用獨特的交叉變異方法，使其在家庭服務機器人的行動規(guī)劃中發(fā)揮效用。

2.1 事件結(jié)構(gòu)與編碼

本文把所有類型的目標都轉(zhuǎn)化為若干個四位結(jié)構(gòu)，稱為事件或step。其結(jié)構(gòu)如下：

step（getorput，objnum，objplace，inornot）

其中：getorput表示事件類型是一個拿取或放下小物體、又或與小物體無關的事件。

objnum 表示事件中涉及小物體的編號。

placenum 表示事件中涉及地點（大物體）的編號。

inornot表示是否存在一些內(nèi)部包含的狀態(tài)。

而編碼即是把任務目標轉(zhuǎn)化為這種事件結(jié)構(gòu)，例如：Puton（green can，teapoy）.其中g(shù)reen can的編號為17，初始位置為3，且在大物體內(nèi)部，teapoy位置為7的話。那么其即可轉(zhuǎn)化為兩條事件結(jié)構(gòu)即step0（getorput＝1，objnum＝17，placenum＝3，inornot＝1），step1（getorput＝－1，objnum＝17，placenum＝7，inornot＝0）.其他目標也可依照類似規(guī)則轉(zhuǎn)化為事件結(jié)構(gòu)，于是規(guī)劃問題轉(zhuǎn)化為對事件結(jié)構(gòu)的排序問題。

2.2 生成初始種群

傳統(tǒng)進化算法的初始種群產(chǎn)生方法為隨機產(chǎn)生，但這樣并不能保證全面性，特別是在家庭服務機器人仿真比賽中，需要規(guī)劃的參數(shù)較多，不僅是事件結(jié)構(gòu)的順序，物品選擇方面也需要利用進化算法進行規(guī)劃，所以盡量在初始種群保持一定的全面性。

因此，本文采用了條件隨機生成的方式。在每種可能的物品選擇情況下，隨機產(chǎn)生若干個初始個體，個體內(nèi)的事件結(jié)構(gòu)隨機排序，并經(jīng)過序列篩選（見2.4.1）作為進化算法的初始種群μ。

2.3 交叉與變異

交叉和變異是進化算法中種群進化的重要方式，通過交叉、變異計算，產(chǎn)生新的種群，從而豐富種群的多樣性，探索更優(yōu)化的策略。通常進化算法中的交叉操作，是隨機取兩個染色體進行單點交叉操作［7］，而變異操作是指對個體編碼串隨機指定某一位或某幾位基因作變異運算［8］。

2.3.1 交叉進化

為了解決排序問題，本文把傳統(tǒng)的異體同位交叉轉(zhuǎn)化成為自體異位交叉的模式，即在進行交叉進化時，個體中的任意m個事件對以交叉概率p進行位置互換，從而產(chǎn)生新的個體。其中交叉事件對個數(shù)m和交叉概率p與當前個體的適應度有關。即

式中：p——單對事件發(fā)生交叉的概率；μ——交叉率，取值和進化速度及穩(wěn)定性有關；S——該個體的代價值；n——一個個體中事件的個數(shù)。

圖1 交叉進化圖例

發(fā)生交叉進化的概率p 與交叉率μ和代價值S 正相關，與事件個數(shù)n 負相關。由于代價值S 與優(yōu)化程度負相關，即代價值S 越小則說明該個體的優(yōu)化程度越高，需要發(fā)生交叉的概率則越小，反之亦然。而代價值S的計算與事件個數(shù)n 有關，因而加入n 以消除事件數(shù)量對交叉發(fā)生概率的影響。交叉率μ的值越大則進化速度越快，同時穩(wěn)定性降低，反之則進化速度降低，但穩(wěn)定性增強，需根據(jù)情況進行選擇。

2.3.2 變異進化

物品選擇是機器人規(guī)劃中十分重要的一點，也是家庭服務機器人仿真比賽中必須考慮的部分。利用進化算法的變異進化可以有效地解決物品選擇的問題，當然也需要對其進行一定程度的改變。

由于是用于物品選擇，所以變異的參數(shù)以objnum為線索，其變異的范圍也是限定的，為可以完成目標的同類物品，其發(fā)生變異的概率為q。當某條事件的objnum 改變時，該事件內(nèi)的placenum和inornot 也依照情況根據(jù)小物體的狀況而變化。且當仍有其他事件涉及同樣的小物體時，該事件的小物體也隨之而改變，即相當于一種成對變異的效果

式中：q——單個事件發(fā)生變異的概率；θ——變異率，取值和進化速度及穩(wěn)定性有關；k［t］——目標小物體的可選擇個數(shù)；S——該個體的代價值；n——一個個體中事件的個數(shù)。

圖2 變異進化圖例

在公式中，θ、S、n的意義和選擇與交叉進化時相似，而k［t］則表示了該事件所用來完成的目標涉及的小物體的可選擇數(shù)量。當可選擇數(shù)量越多時，即k［t］越大時，需對變異進化進行促進，因而q越大，反之亦然。

由于交叉進化有可能會產(chǎn)生不能正確完成任務的事件序列，這部分序列會在序列的篩選中被刪除，因而要產(chǎn)生較多的下一代種群以備選擇，需要進行兩次獨立的進化產(chǎn)生2μ個子代種群，則整體種群數(shù)量變?yōu)?μ。

2.4 適應度函數(shù)與選擇

適應度函數(shù)是進化算法非常重要的組成部分，整個進化算法就是在適應度函數(shù)的引導下進行的，適應度函數(shù)對個體的評價直接影響了選擇，從而決定了整個群體的進化方向［9］。

2.4.1 序列的篩選

由于機器人的能力限制，以及一些動作之間固有的邏輯關系，通過隨機生成或經(jīng)過進化的事件序列并不都是合法的，其中很大一部分會與規(guī)則或邏輯沖突。這部分序列是不能正確地完成任務的，對其進行適應度評價也毫無意義，因而要在評價前將其從種群中移除。

如：規(guī)則規(guī)定機器人同時只能攜帶兩個或兩個以下的小物體，因而違反此規(guī)定的事件序列視為違規(guī)，應予以刪除；當事件序列中涉及對同一物體的拿取事件和放下事件時，邏輯上拿取事件必須出現(xiàn)在放下事件之前，否則視為不合邏輯，應予以刪除。以及諸如此類其他違反規(guī)則或邏輯的事件序列都刪除處理，并且每次進化一代之后都進行一次序列的篩選。

2.4.2 適應度函數(shù)

本方法適應度函數(shù)采取代價累加的方式計算，根據(jù)事件結(jié)構(gòu)的內(nèi)容、機器人的狀態(tài)、場景狀態(tài)、需要維持的約束等等，結(jié)合類似罰函數(shù)的方法，計算出完成任務所需付出的代價（S）［10］。計算得出的代價值越高，則說明適應度越低，相反代價值越低，說明適應度越高。代價值計算具體公式如下

其中：S為該序列的代價值；

n為該序列包含的事件個數(shù)；

m、a、c為移動、動作、約束的代價權(quán)值；

x為特殊情況代價變化。

公式中的m、a、c權(quán)值是根據(jù)比賽規(guī)則對移動、動作、約束的評分系統(tǒng)而設定的，分別設為3、1、5。αi表示該事件是否有進行移動的需求，其為0或1二值，與機器人的當前位置和事件發(fā)生地點有關；βi 表示為完成該事件所需做出動作的復雜度，與事件的內(nèi)容、機器人的狀態(tài)、環(huán)境狀態(tài)有關，是強非線性的映射關系；γi表示本次事件違反約束的量，需要根據(jù)事件本身的內(nèi)容和約束列表得出。變量x為某些特殊情況對整體代價值的影響，例如事件結(jié)束時機器人狀態(tài)剛好位于goto任務目標地點等等。

由此方法計算出的代價值與適應度成負相關，相關使用和操作也與適應度相反。

2.5 種群的選擇

依照此規(guī)則對種群中每個個體進行計算以測試新種群，選擇其中w 值最高的μ個個體作為下一代的初始種群。

2.6 終止條件與解碼

本算法利用代價計算函數(shù)作為終止條件，當連續(xù)三代種群最低代價相同時，即視為達到相對最優(yōu)解，隨即終止進化，當前種群中的最佳個體作為規(guī)劃結(jié)果。

當進化過程結(jié)束，選出了相對最優(yōu)解之后，即進入解碼過程。將排好序的事件結(jié)構(gòu)結(jié)合機器人狀態(tài)、場景狀態(tài)等，轉(zhuǎn)化成機器人最終執(zhí)行的動作序列，見表2。

表2 解碼范例

至此，整個機器人規(guī)劃過程結(jié)束。

3 實驗與結(jié)果

實驗素材為2011中國服務機器人大賽指令語言仿真組和自然語言仿真組比賽用題，每組包含兩個階段（stage），每個階段50個任務，每個任務包含若干個目標和約束等，算法應用于我校GDUT＿TiJi隊，并取8個其他學校參賽隊為參照系，各參賽隊采用A＊算法、ASP 回答集編程等完全獨立的方法。其中stage1只包含目標，而stage2包含目標及約束，更為復雜，對規(guī)劃的要求更高。實驗結(jié)果包含整組題目的對照情況，以及對具體單個題目比較的統(tǒng)計數(shù)據(jù)。

表3中score為各隊單個階段得分，higher為該隊單題得分超過我隊的題目數(shù)，lower為該隊單題得分低于我隊的題目數(shù)，different為單個階段得分差，rank為該隊在比賽中的排名。

由實驗結(jié)果可以看出，該結(jié)構(gòu)算法在家庭服務機器人仿真比賽中應用良好，得分高于其他隊的題目很多，而得分低于其他隊的題目則相對較少，且在狀況更復雜的第二階段能取得更好的成績，成功達到規(guī)劃效果。使用這個方法，我校GDUT＿TiJi隊在2012中國服務機器人大賽中取得了指令語言組季軍、自然語言組亞軍的成績，再一次證明了這個方法的實用性。

4 結(jié)束語

本方法提出了事件結(jié)構(gòu)描述家庭服務機器人的任務，構(gòu)建了一種代價函數(shù)還對機器人的行動進行評價，且改進了進化算法的進化方式以適應這種事件結(jié)構(gòu)。并通過實驗和比賽也驗證了這個方法的穩(wěn)定性和有效性。

其算法還有很多方面有待進一步探討，比如事件結(jié)構(gòu)的細化優(yōu)化、參數(shù)的選取、加入啟發(fā)式搜索方法等等，需要在今后的研究中繼續(xù)探索。

表3 實驗結(jié)果

［1］RoboCup＠home Rule 2011［Z］.2011（in Chinese）.［2011中國服務機器人大賽仿真比賽規(guī)則［Z］.2011.］

［2］JI Jianmin.Several ways of improve the ASP efficiency and application on service robot［D］.Hefei：University of Science and Technology of China，2010（in Chinese）.［吉建民.提高ASP效率的若干途徑及服務機器人上應用［D］.合肥：中國科學技術(shù)大學，2010.］

［3］HUANG Han，LIN Zhiyong.Convergence analysis and comparison of evolutionary algorithms based on relation model［J］.Chinese Journal of Computers，2011，34（5）：801－811（in Chinese）.［黃翰，林智勇.基于關系模型的進化算法收斂性分析與對比［J］.計算機學報，2011，34（5）：801－811.］

［4］HAO C Y M Z C.A hybrid chaotic quantum evolutionary algorithm［J］.Intelligent Computing and Intelligent Systems，2010：771－776.

［5］Woldesenbet Y G Y G G.Dynamic evolutionary algorithm with variable relocation［J］.Evolutionary Computation，2009.13（3）：500－513.

［6］ZHENG X G J.Multi－agent based hybrid evolutionary algorithm［J］.Natural Computation，2011（2）：1106－1110.

［7］DENG Zexi，CAO Dunqian.New differential evolution algorithm［J］.Computer Engineering and Applications，2008，44（24）：40－42（in Chinese）.［鄧澤喜，曹敦虔.一種新的差分進化算法［J］.計算機工程與應用，2008，44（24）：40－42.］

［8］WANG Shuaiqiang.A novel method for behavioral model refinement and learning to rank based on evolutionary algorithm［D］.Jinan：Shandong University，2009（in Chinese）.［王帥強.基于進化計算的行為模型自動精化和排序?qū)W習方法的研究［D］.濟南：山東大學，2009.］

［9］Majig M A，F(xiàn)ukushima M.Adaptive fitness function for evolutionary algorithm and its applications［C］／／International Conference on Informatics Education and Research for Knowledge－Circulating Society，2008：119－124.

［10］LIU Bo，WANG Ling.Advances in differential evolution［J］.Control and Decision，2007，22（7）：721－729（in Chinese）.［劉波，王凌.差分進化算法研究進展［J］.控制與決策，2007，22（7）：721－729.］