改進(jìn)的進(jìn)化算法于服務(wù)機(jī)器人仿真賽中的應(yīng)用

李劍平，陳 瑋，陳樹(shù)斌

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

0 引 言

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

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

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

1 進(jìn)化算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法的改進(jìn)

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

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

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

step（getorput，objnum，objplace，inornot）

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

objnum 表示事件中涉及小物體的編號(hào)。

placenum 表示事件中涉及地點(diǎn)（大物體）的編號(hào)。

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

而編碼即是把任務(wù)目標(biāo)轉(zhuǎn)化為這種事件結(jié)構(gòu)，例如：Puton（green can，teapoy）.其中g(shù)reen can的編號(hào)為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)也可依照類(lèi)似規(guī)則轉(zhuǎn)化為事件結(jié)構(gòu)，于是規(guī)劃問(wèn)題轉(zhuǎn)化為對(duì)事件結(jié)構(gòu)的排序問(wèn)題。

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)生若干個(gè)初始個(gè)體，個(gè)體內(nèi)的事件結(jié)構(gòu)隨機(jī)排序，并經(jīng)過(guò)序列篩選（見(jiàn)2.4.1）作為進(jìn)化算法的初始種群μ。

2.3 交叉與變異

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

2.3.1 交叉進(jìn)化

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

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

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

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

2.3.2 變異進(jìn)化

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

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

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

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

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

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

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

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

2.4.1 序列的篩選

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

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

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

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

其中：S為該序列的代價(jià)值；

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

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

x為特殊情況代價(jià)變化。

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

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

2.5 種群的選擇

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

2.6 終止條件與解碼

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

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

表2 解碼范例

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

3 實(shí)驗(yàn)與結(jié)果

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

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

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

4 結(jié)束語(yǔ)

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

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

表3 實(shí)驗(yàn)結(jié)果

［1］RoboCup＠home Rule 2011［Z］.2011（in Chinese）.［2011中國(guó)服務(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］.合肥：中國(guó)科學(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)化算法收斂性分析與對(duì)比［J］.計(jì)算機(jī)學(xué)報(bào)，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ì)算機(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)化計(jì)算的行為模型自動(dòng)精化和排序?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.］