李劍平，陳 瑋，陳樹斌

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

0 引 言

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

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

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

1 進(jìn)化算法

1.1 進(jìn)化算法簡介

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

1.2 進(jìn)化算法一般步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法的改進(jìn)

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

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

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

step（getorput，objnum，objplace，inornot）

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

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

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

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

而編碼即是把任務(wù)目標(biāo)轉(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）.其他目標(biāo)也可依照類似規(guī)則轉(zhuǎn)化為事件結(jié)構(gòu)，于是規(guī)劃問題轉(zhuǎn)化為對事件結(jié)構(gòu)的排序問題。

2.2 生成初始種群

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

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

2.3 交叉與變異

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

2.3.1 交叉進(jìn)化

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

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

圖1 交叉進(jìn)化圖例

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

2.3.2 變異進(jìn)化

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

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

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

圖2 變異進(jìn)化圖例

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

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

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

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

2.4.1 序列的篩選

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

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

2.4.2 適應(yīng)度函數(shù)

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

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

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

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

x為特殊情況代價變化。

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

由此方法計算出的代價值與適應(yīng)度成負(fù)相關(guān)，相關(guān)使用和操作也與適應(yīng)度相反。

2.5 種群的選擇

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

2.6 終止條件與解碼

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

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

表2 解碼范例

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

3 實驗與結(jié)果

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

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

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

4 結(jié)束語

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

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

表3 實驗結(jié)果

［1］RoboCup＠home Rule 2011［Z］.2011（in Chinese）.［2011中國服務(wù)機(jī)器人大賽仿真比賽規(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效率的若干途徑及服務(wù)機(jī)器人上應(yīng)用［D］.合肥：中國科學(xué)技術(shù)大學(xué)，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）.［黃翰，林智勇.基于關(guān)系模型的進(jìn)化算法收斂性分析與對比［J］.計算機(jī)學(xué)報，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ìn)化算法［J］.計算機(jī)工程與應(yīng)用，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）.［王帥強(qiáng).基于進(jìn)化計算的行為模型自動精化和排序?qū)W習(xí)方法的研究［D］.濟(jì)南：山東大學(xué)，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ìn)化算法研究進(jìn)展［J］.控制與決策，2007，22（7）：721－729.］