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

徐 林，范昕煒

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

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

徐 林*，范昕煒

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

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

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

0 引言

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

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

1 改進遺傳算法

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

1.1 初始種群

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

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

1.1.2 基于Levenshtein距離優化初始種群

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

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

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

(1)

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

1.2 適應度函數

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

1.2.1 安全性評價因子

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

圖1 安全性評價因子函數圖像

(2)

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

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

1.2.2 平滑性評價因子

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

(3)

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

1.2.3 距離評價因子

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

(4)

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

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

(5)

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

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

1.3 遺傳算子與概率調整公式

1.3.1 選擇算子

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

(6)

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

1.3.2 交叉與變異算子

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

(7)

(8)

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

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

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

圖2 兩種均值的比較

1.3.3 平滑算子[13]

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

HLGA整體流程如圖3所示。

圖3 HLGA流程

2 模型建立

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

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

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

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

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

圖5 種群規模和進化代數關系

3 仿真結果及分析

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

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

表1 仿真實驗參數預設

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

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

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

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

圖6 餐廳服務機器人路徑規劃——Matlab仿真結果

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

4 結語

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

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].機械設計與制造,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] 王小平,曹立明.遺傳算法理論、應用與軟件實現[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].計算機與數字工程,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控制器優化設計[J].傳感技術學報,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].青島大學學報(工程技術版),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] 束磊.基于柵格地圖的月球車任務層路徑規劃及平滑處理[D].哈爾濱:哈爾濱工業大學,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。

國家公益性行業科研項目(201410028- 02)。

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

1001- 9081(2017)07- 1967- 05

10.11772/j.issn.1001- 9081.2017.07.1967