徐 林，范昕煒

(中國計(jì)量大學(xué) 質(zhì)量與安全工程學(xué)院，杭州 310018) (*通信作者電子郵箱792243200@qq.com)

基于改進(jìn)遺傳算法的餐廳服務(wù)機(jī)器人路徑規(guī)劃

徐 林*，范昕煒

(中國計(jì)量大學(xué) 質(zhì)量與安全工程學(xué)院，杭州 310018) (*通信作者電子郵箱792243200@qq.com)

針對遺傳算法(GA)易產(chǎn)生早熟現(xiàn)象和收斂速度慢的問題，提出了一種基于傳統(tǒng)遺傳算法(TGA)的改進(jìn)遺傳算法——HLGA，用于實(shí)際餐廳服務(wù)機(jī)器人的路徑規(guī)劃。首先，通過基于編輯距離的相似度方法對擬隨機(jī)序列產(chǎn)生的初始種群進(jìn)行優(yōu)化；其次，采用自適應(yīng)算法的改進(jìn)交叉概率和變異概率調(diào)整公式，對選擇操作后的個(gè)體進(jìn)行交叉、變異操作；最后，計(jì)算具有安全性評價(jià)因子函數(shù)的個(gè)體適應(yīng)度值，進(jìn)一步對比、迭代得到全局最優(yōu)解。理論分析和Matlab仿真表明，與TGA和基于個(gè)體相似度改進(jìn)的自適應(yīng)遺傳算法(ISAGA)相比，HLGA的運(yùn)行時(shí)間分別縮短了6.92 s和1.79 s，且規(guī)劃的實(shí)際路徑更具有安全性和平滑性。實(shí)驗(yàn)結(jié)果表明HLGA在實(shí)際應(yīng)用中能有效提高路徑規(guī)劃質(zhì)量，同時(shí)縮小搜索空間、減少規(guī)劃時(shí)間。

遺傳算法；餐廳服務(wù)機(jī)器人；擬隨機(jī)序列；編輯距離；路徑規(guī)劃

0 引言

國際機(jī)器人聯(lián)合會(huì)指出，服務(wù)機(jī)器人是一種半自主或全自主工作的機(jī)器人，它能夠完成有益于人類健康的服務(wù)工作，但不包括從事生產(chǎn)的設(shè)備[1]。餐廳送餐機(jī)器人是服務(wù)機(jī)器人的一種。在此過程中,機(jī)器人以怎樣的路線行進(jìn)——路徑規(guī)劃(一種有目的性的自我移動(dòng)技術(shù))，已經(jīng)成為該領(lǐng)域的核心技術(shù)和研究熱點(diǎn)之一。它一般是指在某一具有障礙物的環(huán)境中尋找出移動(dòng)機(jī)器人由起點(diǎn)到終點(diǎn)的一條安全、節(jié)能或行程最短的最優(yōu)或次優(yōu)通路[2]。為此，文獻(xiàn)[3-5]提出了人工勢場法、可視圖法、人工神經(jīng)網(wǎng)絡(luò)等方法。然而，人工勢場法容易產(chǎn)生極小值點(diǎn)，導(dǎo)致移動(dòng)機(jī)器人按此路線行走時(shí)停滯不前，不易實(shí)現(xiàn)全局路徑規(guī)劃；可視圖法產(chǎn)生的規(guī)劃路徑復(fù)雜且效率不高；神經(jīng)網(wǎng)絡(luò)初始訓(xùn)練條件不易產(chǎn)生。通常情況下，機(jī)器人的路徑規(guī)劃都可以轉(zhuǎn)化為一個(gè)有約束的非線性優(yōu)化模型問題；針對這方面，遺傳算法(Genetic Algorithm, GA)汲取了仿生自尋優(yōu)的全局收斂、編碼操作和并行性計(jì)算等特點(diǎn)，在解決非線性問題上具有良好的適用性和魯棒性，加之其自身結(jié)構(gòu)的開放性且易與問題結(jié)合，近年來，已經(jīng)被廣泛應(yīng)用于復(fù)雜環(huán)境下的路徑規(guī)劃。而傳統(tǒng)的遺傳算法本身易早熟陷入局部最優(yōu)，算法運(yùn)行效率較低，不能保證對路徑規(guī)劃的可靠性及其運(yùn)行效率的要求。

為改善傳統(tǒng)遺傳算法(Traditional Genetic Algorithm, TGA)的這一缺陷，從而更好運(yùn)用到路徑規(guī)劃中去，本文結(jié)合實(shí)際餐廳內(nèi)部規(guī)律布局對其進(jìn)行有針對性的改進(jìn)和優(yōu)化，用于餐廳服務(wù)機(jī)器人的路徑規(guī)劃。基于此，本文在前人研究的基礎(chǔ)之上，針對TGA的不足和餐廳實(shí)際環(huán)境的特點(diǎn)，提出一種改進(jìn)遺傳算法——HLGA(Halton-Levenshtein Genetic Algorithm)的餐廳服務(wù)機(jī)器人路徑規(guī)劃方法。仿真結(jié)果表明該算法能在實(shí)際餐廳環(huán)境中快速找到存在的最優(yōu)路徑。

1 改進(jìn)遺傳算法

美國密執(zhí)安大學(xué)J.Holland教授最早提出遺傳算法，它是通過模擬自然界生物自然選擇和進(jìn)化而形成的一種全局優(yōu)化概率搜索的自適應(yīng)算法[6]。該算法需要的預(yù)設(shè)參數(shù)有種群規(guī)模、最大進(jìn)化代數(shù)、交叉和變異概率等；一般包括選擇、交叉、變異三個(gè)過程；通過不斷的迭代，最終得到問題最優(yōu)解。

1.1 初始種群

1.1.1 基于擬隨機(jī)序列的種群初始化

遺傳算法中，人工選擇初始種群費(fèi)時(shí)費(fèi)力；隨機(jī)選擇初始種群難以滿足路徑有目的性和無障礙性的要求，且易于生成非通路路徑個(gè)體，因此，本文利用擬隨機(jī)Halton序列[7-8]具有較隨機(jī)序列更高的均勻性、可以產(chǎn)生低差異度個(gè)體、獲取更多目標(biāo)信息、執(zhí)行簡單等特點(diǎn)來產(chǎn)生初始種群。

1.1.2 基于Levenshtein距離優(yōu)化初始種群

初始種群產(chǎn)生后，種群個(gè)體之間存在一定相似度。若相似度過大則會(huì)減弱種群多樣性，使算法易陷入局部最優(yōu)造成遺傳進(jìn)化停滯；反之則會(huì)增強(qiáng)種群多樣性，進(jìn)而使算法運(yùn)行時(shí)間過長，不利于實(shí)際問題的解決。本文采用編輯距離(又稱Levenshtein距離[9])對初始種群進(jìn)行個(gè)體的相似度優(yōu)化。

編輯距離是由俄國科學(xué)家Levenshtein提出用來計(jì)算兩字符串相互轉(zhuǎn)化所需最少刪除、替換和插入次數(shù)的一種算法。個(gè)體采用二進(jìn)制編碼，編碼后的不同個(gè)體可看作不同字符串。初始種群矩陣為I，隨機(jī)選擇兩個(gè)體Ii和Ij，相似度計(jì)算公式[10]如式(1)所示：

α=1-DIS/max(Leni,Lenj)

(1)

其中：α為兩個(gè)體相似度，取值范圍為[0,1]。兩字符串間的編輯距離(Distance, DIS)，max表示取兩字符串長度的較大者。

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

以安全性、路徑平滑性和最短距離作為規(guī)劃路徑的可行性評價(jià)因子，從而得到個(gè)體適應(yīng)度評價(jià)函數(shù)。

1.2.1 安全性評價(jià)因子

由已知的障礙物和柵格位置坐標(biāo)信息,可確定路徑點(diǎn)的位置距其周圍障礙物邊界距離的最小值di，由式(2)可得出安全性評價(jià)因子f1，如圖1所示。

圖1 安全性評價(jià)因子函數(shù)圖像

(2)

其中，安全距離(Safety distance,Sd)為0.5(柵格邊長的一半)，表示路徑點(diǎn)與障礙物的距離。

由圖1可知，當(dāng)安全距離小于設(shè)定值時(shí)，安全性評價(jià)因子函數(shù)的值迅速增大。反映到HLGA中表現(xiàn)為：相應(yīng)的個(gè)體適應(yīng)度函數(shù)值增大，被下一代選中的概率迅速下降。

1.2.2 平滑性評價(jià)因子

機(jī)器人移動(dòng)過程中，平滑路徑更易于其運(yùn)行且可減少能耗，加之服務(wù)機(jī)器人自身的物理特性，決定它在移動(dòng)過程中不能以較大角度進(jìn)行變向，因此需要加強(qiáng)所規(guī)劃路徑的平滑性——路徑轉(zhuǎn)向角盡可能小。如式(3)所示：

(3)

其中：a=(xi-xi-1,yi-yi-1)，b=(xi+1-xi,yi+1-yi)。

1.2.3 距離評價(jià)因子

機(jī)器人移動(dòng)過程中，規(guī)劃的路徑長度評價(jià)函數(shù)——各路徑點(diǎn)之間的歐氏距離總和，由式(4)確定：

(4)

為使參數(shù)易于調(diào)整，排除三項(xiàng)因子簡單求積引起的不穩(wěn)定因素，盡可能使函數(shù)簡單；先對三項(xiàng)因子歸一化處理，然后采用各因子乘積形式作為適應(yīng)度函數(shù)，如式(5)所示：

fitness=f1×f2/(num×π)×f3/dsum

(5)

其中，路徑的拐點(diǎn)總數(shù)(number,num)和由起點(diǎn)到終點(diǎn)與它們之間垂直交叉點(diǎn)的距離總和(distance sum,dsum)。

由式(5)可知，以fitness作為適應(yīng)度函數(shù)，安全性越高，路徑越平滑，路徑長度越短時(shí)適應(yīng)度函數(shù)值越小。

1.3 遺傳算子與概率調(diào)整公式

1.3.1 選擇算子

采用比例選擇算子，個(gè)體賭輪盤選擇方法向下一代進(jìn)化。第i個(gè)個(gè)體被選擇的概率P(Ii)由式(6)所示：

(6)

其中，fitness(Ii)表示第i個(gè)個(gè)體的適應(yīng)度值。

1.3.2 交叉與變異算子

對交叉、變異概率的選擇，謝鵬等[11]提出了能保證種群多樣性的自適應(yīng)選擇機(jī)制遺傳算法，但是這些方法都是依據(jù)個(gè)體適應(yīng)度與當(dāng)前代算術(shù)平均適應(yīng)度(Arithmetic mean,fa)的相對大小進(jìn)行判定。當(dāng)種群中有較多適應(yīng)度較小個(gè)體或是有較多適應(yīng)度較大個(gè)體時(shí)，fa就會(huì)變得更低或更高，那些略大于或略小于平均適應(yīng)度的個(gè)體，就變成了適應(yīng)度較高或較低的個(gè)體；加之fa只能大致衡量當(dāng)代進(jìn)化適應(yīng)度的相對狀況，并不能準(zhǔn)確衡量整個(gè)遺傳進(jìn)化過程中個(gè)體適應(yīng)度的相對大小，因此將fa作為判斷個(gè)體適應(yīng)度相對大小的標(biāo)準(zhǔn)具有一定缺陷?；趧⒔ㄎ牡萚12]提出的基于個(gè)體相似度改進(jìn)的自適應(yīng)遺傳算法(Adaptive Genetic Algorithm based on Improved individual Similarity， ISAGA)，改進(jìn)了交叉概率和變異概率的調(diào)整公式，如式(7)和(8)所示：

(7)

(8)

其中：Pc1/Pc2=0.9/0.6，Pm1/Pm2=0.5/0.1，fmax、fmin表示種群個(gè)體的最大、最小適應(yīng)度，兩交叉?zhèn)€體中較大適應(yīng)度(Cross individual fitness,fc)，變異個(gè)體適應(yīng)度(Mutate individual fitness,fm)。

如圖2所示，幾何均值(Geometric mean,fG)與fa的整體進(jìn)化趨勢基本相同，但是fG始終小于fa，這就使得將fG作為交叉概率和變異概率的依據(jù)時(shí)，更容易得到較小適應(yīng)度值的個(gè)體，提高算法收斂速度。

依據(jù)fG判斷個(gè)體適應(yīng)度的相對高低，可以從整個(gè)進(jìn)化過程中較為準(zhǔn)確的優(yōu)化每一代種群進(jìn)化，使得適應(yīng)度值相對較高的個(gè)體以較高概率進(jìn)行交叉，適應(yīng)度值相對較低的個(gè)體以較高概率進(jìn)行變異。最終，使種群更具多樣性，更好排除局部最優(yōu)達(dá)到全局最優(yōu)，進(jìn)而提高算法效率。

圖2 兩種均值的比較

1.3.3 平滑算子[13]

為保證機(jī)器人在較平滑路徑上移動(dòng)，添加平滑算子。首先計(jì)算所規(guī)劃路徑的拐角值并得到其fa，然后將大于均值的拐點(diǎn)附近等距離插入兩新路徑節(jié)點(diǎn)，且刪除原路徑節(jié)點(diǎn)。

HLGA整體流程如圖3所示。

圖3 HLGA流程

2 模型建立

以某餐廳實(shí)際布局位置原型圖11 m×11 m為例，如圖4所示，采用HLGA，對機(jī)器人的行走路徑進(jìn)行全局搜索，尋找出一條路徑相對較短、較平滑且安全性較高的最優(yōu)路徑。

假設(shè)機(jī)器人的工作空間可用二維平面圖表示(比例尺為1∶100)?？臻g中障礙物的位置和大小根據(jù)實(shí)際餐廳布局有規(guī)律的排列(不考慮其高度問題)，在機(jī)器人運(yùn)行過程中，障礙物結(jié)構(gòu)、體積及其位置信息均固定不變且已知。基于此，機(jī)器人的工作空間模型依據(jù)實(shí)際餐廳規(guī)模按比例確定仿真柵格地圖。

為使機(jī)器人在柵格中自由移動(dòng)，設(shè)定柵格尺寸略大于機(jī)器人的最大直徑且固定。工作空間中不含障礙物稱為分別代表障礙空間(餐廳的桌椅、吧臺(tái)和洗手間等)和自由空間，110號柵格代表餐廳服務(wù)機(jī)器人的起點(diǎn)(Start point， Sp)。

圖4 餐廳實(shí)際布局(局部)

如圖5所示，初始種群規(guī)?；蜻z傳進(jìn)化代數(shù)越大，算法收斂至全局最優(yōu)解的速率越快；然而，當(dāng)兩者至少有一個(gè)過大時(shí)，收斂速度與其呈現(xiàn)負(fù)相關(guān)關(guān)系；當(dāng)進(jìn)化代數(shù)為40，50，60時(shí)，可以得出對應(yīng)不同情況下的最優(yōu)點(diǎn)分別為(32，35.89)、(20，35.95)和(18，36.91)。綜合算法收斂速度和實(shí)際情況，HLGA的初始種群和最大遺傳進(jìn)化代數(shù)分別設(shè)定為20，50。以ISAGA的交叉和變異概率進(jìn)行對應(yīng)參數(shù)設(shè)定，進(jìn)一步設(shè)計(jì)仿真實(shí)驗(yàn)驗(yàn)證。

圖5 種群規(guī)模和進(jìn)化代數(shù)關(guān)系

3 仿真結(jié)果及分析

基于某餐廳實(shí)際布局圖建立的抽象柵格地圖模型，本文采用Matlab[14]進(jìn)行仿真實(shí)驗(yàn)。仿真過程以序號110為起點(diǎn)Sp，以序號21為終點(diǎn)(End point， Ep)。針對經(jīng)過實(shí)際餐廳環(huán)境下抽象形成的靜態(tài)障礙柵格地圖，分別利用TGA、ISAGA和HLGA，在同一環(huán)境下對餐廳服務(wù)機(jī)器人移動(dòng)路徑進(jìn)行由起點(diǎn)到終點(diǎn)的仿真規(guī)劃。3種算法的仿真實(shí)驗(yàn)預(yù)設(shè)參數(shù)如表1所示。

依據(jù)表1所示的參數(shù)預(yù)設(shè)值，在Matlab上運(yùn)行3種不同算法各100次后，選取效果較優(yōu)的路徑規(guī)劃仿真圖，如圖6所示；得到的路徑規(guī)劃圖的相關(guān)參數(shù)信息，如表2所示。

表1 仿真實(shí)驗(yàn)參數(shù)預(yù)設(shè)

表2 3種算法運(yùn)行效果對比

比較圖6中3種算法的路徑規(guī)劃仿真圖可知：在同一環(huán)境中進(jìn)行路徑規(guī)劃時(shí)，利用HLGA和ISAGA產(chǎn)生的路徑較短，且拐點(diǎn)總數(shù)較TGA明顯減少；與ISAGA相比，HLGA規(guī)劃方法產(chǎn)生的路徑更平滑、更具有安全性、拐點(diǎn)更少，因此，HLGA在規(guī)劃形成的路徑效果上優(yōu)于ISAGA和TGA，得到的移動(dòng)路徑也更適合于特定環(huán)境下的餐廳服務(wù)機(jī)器人的運(yùn)行。

從表2中比較可以得出：1)在規(guī)劃路徑的安全性上，只有HLGA表現(xiàn)為安全，原因在于該算法在適應(yīng)度函數(shù)中增加了安全性評價(jià)因子。2)在規(guī)劃路徑的長度上，HLGA在加強(qiáng)自身規(guī)劃路徑平滑性基礎(chǔ)之上，僅僅較ISAGA增加了0.17，由此所帶來的微小增大，較之TGA和ISAGA在規(guī)劃路徑平滑性方面的劣勢，完全可以忽略。3)在規(guī)劃運(yùn)行的時(shí)間上，HLGA較ISAGA減少1.79 s，較TGA減少6.92 s，明顯提高了算法的運(yùn)行速度，即縮短了路徑規(guī)劃的時(shí)間，原因在于該算法結(jié)合領(lǐng)域知識所設(shè)計(jì)的初始種群的產(chǎn)生以及對其優(yōu)化方法都降低了不行解的數(shù)量，從而提高了種群進(jìn)化速度，使算法更容易快速收斂至全局最優(yōu)解。4)當(dāng)忽略算法平滑性因子的影響時(shí)，利用HLGA和ISAGA產(chǎn)生的規(guī)劃路徑長度相等，均為16.24；而上述圖6(c)圖較之圖6(b)在規(guī)劃路徑的拐點(diǎn)數(shù)上小1，原因在于HLGA采用的自適應(yīng)交叉和變異概率調(diào)整公式將fG作為調(diào)整公式的標(biāo)準(zhǔn)，綜合了每代種群與整個(gè)遺傳進(jìn)化過程的整體性。

基于HLGA，在不同起點(diǎn)Sp，不同終點(diǎn)Ep和任意自由柵格的起點(diǎn)Sp、終點(diǎn)Ep的條件下進(jìn)行的路徑規(guī)劃均具有較優(yōu)效果，如圖7所示。經(jīng)以上實(shí)驗(yàn)比較分析可知，本文提出的HLGA是可行有效的，無論在運(yùn)行效率還是在路徑規(guī)劃的效果上均優(yōu)于ISAGA和TGA。

圖6 餐廳服務(wù)機(jī)器人路徑規(guī)劃——Matlab仿真結(jié)果

圖7 基于HLGA的餐廳服務(wù)機(jī)器人路徑規(guī)劃

4 結(jié)語

本文針對TGA易產(chǎn)生早熟且運(yùn)行速度慢的缺點(diǎn)，提出了HLGA。與TGA和ISAGA相比，HLGA在運(yùn)行時(shí)間上分別縮短了6.92 s和1.79 s；增加安全性因子，使規(guī)劃的路徑更具有安全性；調(diào)整交叉和變異概率公式，使算法更好、更快地收斂至全局最優(yōu)解；增加平滑算子，使規(guī)劃路徑更合理，可適當(dāng)減小機(jī)器能耗。通過以實(shí)際餐廳布局為環(huán)境模型進(jìn)行的仿真實(shí)驗(yàn)，確實(shí)提高了算法的效率和性能，使得本文提出的HLGA具有可行性，運(yùn)用到餐廳服務(wù)機(jī)器人路徑規(guī)劃上是有效的。后續(xù)工作重點(diǎn)是，在有動(dòng)態(tài)障礙物的環(huán)境中，餐廳服務(wù)機(jī)器人的路徑規(guī)劃及其算法研究。

References)

[1] SEUNGHWAN P, WONPIL Y, JAEIL C. A user reactivity research for improving performance of service robot[C]// Proceedings of the 8th International Conference on Ubiquitous Robots and Ambient Intelligence. Piscataway, NJ: IEEE, 2011: 753-755.

[2] 鄧志燕,陳熾坤.基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].機(jī)械設(shè)計(jì)與制造,2010,2(7):147-150.(DENG Z Y, CHEN C K. Path planning for moving robot based on improved genetic algorithm [J]. Mechanical Design and Manufacturing, 2010, 2(7): 147-150.)

[3] LI G H, TONG S G, CONG F Y. et al. Improved artificial potential field-based simultaneous forward search method for robot path planning in complex environment [C]// Proceedings of the 2015 IEEE/SICE International Symposium on System Integration. Piscataway, NJ: IEEE, 2015: 760-765.

[4] MA Y C, ZHENG G, PERRUQUETTI W. Cooperative path planning for mobile robots based on visibility graph [C]// Proceedings of the IEEE 32nd Chinese Control Conference. Piscataway, NJ: IEEE, 2013: 4915-4920.

[5] ZHANG H. A preliminary study on artificial neural network [C]// Proceedings of the 2011 International Conference on Information Technology and Artificial Intelligence Conference. Piscataway, NJ: IEEE, 2010: 336-338.

[6] 王小平,曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002:2-5.(WANG X P, CAO L M. Genetic Algorithm Theory, Application and Software Implementation [M].Xi’an: Xi’an Jiaotong University Press, 2002: 2-5.)

[7] ATANASSOV E, KARAIVANOVA A, GUROV T. Quasi-random approach in the grid application SALUTE [C]// PPAM 2009: Proceedings of the 8th International Conference Parallel Processing and Applied Mathematics. Berlin: Springer, 2010: 204-213.

[8] SCHLIER C. On scrambled Halton sequences [J]. Applied Numeri-cal Mathematics, 2008, 58(10): 1467-1478.

[9] LEVENSHTEIN V. Binary codes capable of correcting deletions, insertions and reversals [J]. Soviet Physics Doklady, 1996, 10(8): 707-710.

[10] 牛永潔,張成.多種字符串相似度算法的比較[J].計(jì)算機(jī)與數(shù)字工程,2012,40(3):14-16.(NIU Y J, ZHANG C. Comparison of multi-string similarity algorithms [J]. Computer and Digital Engineering, 2012, 40(3): 14-16.)

[11] 謝鵬,張紅梅.基于自適應(yīng)遺傳算法的EHA控制器優(yōu)化設(shè)計(jì)[J].傳感技術(shù)學(xué)報(bào),2016,29(6):909-914.(XIE P, ZHANG H M. Optimum design of electro-hydrostatic actuator controller based on adaptive genetic algorithm [J]. Chinese Journal of Sensors and Actuators, 2016, 29(6): 909-914.)

[12] 劉建文,丁潔玉,潘坤,等.基于個(gè)體相似度的改進(jìn)自適應(yīng)遺傳算法研究[J].青島大學(xué)學(xué)報(bào)(工程技術(shù)版),2016,31(1):16-19.(LIU J W, DING J Y, PAN K, et al. Improved adaptive genetic algorithm based on individual similarity [J]. Journal of Qingdao University (Engineering & Technology Edition), 2016, 31(1): 16-19.)

[13] 束磊.基于柵格地圖的月球車任務(wù)層路徑規(guī)劃及平滑處理[D].哈爾濱:哈爾濱工業(yè)大學(xué),2013:50-59.(SHU L. Mission-level path planning and smoothing of lunar rover based on grid map [D]. Harbin: Harbin Institute of Technology, 2013: 50-59.)

[14] 雷英杰,張善文.Matlab遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2014:62-94.(LEI Y J, ZHANG S W. Genetic Algorithm Toolbox and Application about Matlab [M]. Xi’an: Xidian University Press, 2014: 62-94.)

This work is partially supported by the National Public Welfare Industry Research Projects (201410028- 02).

XULin, born in 1990, M. S. candidate. His research interests include service robot, intelligent control, path planning.

FANXinwei, born in 1973, Ph. D., senior engineer. His research interests include robot, pattern recognition and intelligent control, data mining.

Pathplanningforrestaurantservicerobotbasedonimprovedgeneticalgorithm

XU Lin*, FAN Xinwei

(CollegeofQualityandSafetyEngineering,ChinaJiliangUniversity,HangzhouZhejiang310018,China)

Since the Genetic Algorithm (GA) is easy to produce premature phenomenon and has slow convergence rate, an improved GA based on Traditional GA (TGA), called HLGA (Halton-Levenshtein Genetic Algorithm), was proposed for path planning of real restaurant service robots. Firstly, the similarity method based on edit distance optimized the initial population of quasi-random sequence; secondly, the improved crossover probability and mutation probability adjustment formula based on the adaptive algorithm were adopted to cross and mutate the individuals after they had been selected. Finally, the individual fitness values of the safety evaluation factor functions were calculated, and the global optimal solution was obtained by comparison and iteration. Through theoretical analysis and Matlab simulation, the running time of HLGA was decreased by 6.92 seconds and 1.79 seconds compared with TGA and Adaptive Genetic Algorithm based on Improved independent Similarity (ISAGA), and the actual path of planning was more secure and smooth. The simulation results show that HLGA can effectively improve the quality of path planning in practical applications, meanwhile reduces the searching space and the planning time.

Genetic Algorithm (GA); restaurant service robot; quasi-random sequence; edit distance; path planning

TP249; TP18

:A

2017- 01- 09;

:2017- 03- 01。

國家公益性行業(yè)科研項(xiàng)目(201410028- 02)。

徐林(1990—)，男，安徽阜陽人，碩士研究生，主要研究方向：服務(wù)機(jī)器人、智能控制、路徑規(guī)劃； 范昕煒(1973—)，男，江西廣豐人，高級工程師，博士，主要研究方向：機(jī)器人、模式識別與智能控制、數(shù)據(jù)挖掘。

1001- 9081(2017)07- 1967- 05

10.11772/j.issn.1001- 9081.2017.07.1967