徐 林，范昕煒

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

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

徐 林*，范昕煒

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

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

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

0 引言

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

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

1 改進遺傳算法

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

1.1 初始種群

1.1.1 基于擬隨機序列的種群初始化

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

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

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

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

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

(1)

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

1.2 適應度函數(shù)

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

1.2.1 安全性評價因子

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

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

(2)

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

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

1.2.2 平滑性評價因子

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

(3)

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

1.2.3 距離評價因子

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

(4)

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

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

(5)

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

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

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

1.3.1 選擇算子

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

(6)

其中，fitness(Ii)表示第i個個體的適應度值。

1.3.2 交叉與變異算子

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

(7)

(8)

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

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

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

圖2 兩種均值的比較

1.3.3 平滑算子[13]

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

HLGA整體流程如圖3所示。

圖3 HLGA流程

2 模型建立

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

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

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

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

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

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

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

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

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

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

表2 3種算法運行效果對比

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

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

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

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

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

4 結(jié)語

本文針對TGA易產(chǎn)生早熟且運行速度慢的缺點，提出了HLGA。與TGA和ISAGA相比，HLGA在運行時間上分別縮短了6.92 s和1.79 s；增加安全性因子，使規(guī)劃的路徑更具有安全性；調(diào)整交叉和變異概率公式，使算法更好、更快地收斂至全局最優(yōu)解；增加平滑算子，使規(guī)劃路徑更合理，可適當減小機器能耗。通過以實際餐廳布局為環(huán)境模型進行的仿真實驗，確實提高了算法的效率和性能，使得本文提出的HLGA具有可行性，運用到餐廳服務機器人路徑規(guī)劃上是有效的。后續(xù)工作重點是，在有動態(tài)障礙物的環(huán)境中，餐廳服務機器人的路徑規(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] 鄧志燕,陳熾坤.基于改進遺傳算法的移動機器人路徑規(guī)劃研究[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] 王小平,曹立明.遺傳算法理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,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].計算機與數(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] 謝鵬,張紅梅.基于自適應遺傳算法的EHA控制器優(yōu)化設計[J].傳感技術(shù)學報,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] 劉建文,丁潔玉,潘坤,等.基于個體相似度的改進自適應遺傳算法研究[J].青島大學學報(工程技術(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] 束磊.基于柵格地圖的月球車任務層路徑規(guī)劃及平滑處理[D].哈爾濱:哈爾濱工業(yè)大學,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遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,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è)科研項目(201410028- 02)。

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

1001- 9081(2017)07- 1967- 05

10.11772/j.issn.1001- 9081.2017.07.1967