列車用送餐機器人路徑規劃研究及軟件設計

嚴文娟 費樹岷

摘 要：研究列車環境下送餐機器人路徑規劃與軟件控制方案，為更好地滿足實際需求，提出一種改進的蟻群算法，以加快收斂速度、縮短路徑長度及減少轉彎次數。實驗中根據當前環境構建柵格圖，通過編寫的路徑規劃程序計算起始位置到目標位置的路徑，完成當前環境下的路徑規劃。上位機軟件平臺采用C#語言編寫，主要包括運動控制、訂單管理、通訊傳輸等功能。實驗結果表明，與基本蟻群算法相比，改進蟻群算法具有更好的規劃效果，上位機軟件平臺與下位機可以實現有效的數據交換，并實現對送餐機器人的運動控制及系統管理等功能。

關鍵詞：送餐機器人;路徑規劃;C#;蟻群算法

DOI：10. 11907/rjdk. 182848 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP302文獻標識碼：A 文章編號：1672-7800（2019）009-0026-04

Path Planning and Software Design Based on Dining Robot on Trains

YAN Wen-juan，FEI Shu-min

（Automated Institute，Southeast University，Nanjing 210096，China）

Abstract：In this paper， the path planning and software control scheme of the dining robot in the train environment are studied. To meet the actual demand， an improved ant colony algorithm is proposed， which makes the algorithm improve the convergence speed， path length and turning times. In the experiment， the raster map is constructed according to the current environment， and the path planning program calculates the path of the starting position and the target position， and completes the path planning in the current environment. The PC software platform is written in C# language， which mainly includes motion control， order management， communication transmission and other functions. The experimental results show that compared with the basic ant colony algorithm， the improved ant colony algorithm has better planning effect， the upper computer software platform and the lower computer can realize effective data exchange， and the functions of control and management of the dining robot.

Key Words：dining robot; path planning; C#; ant colony algorithm

0 引言

送餐機器人作為一種服務型機器人，可為用戶提供更高效、便捷的服務[1]，因此越來越多的研究人員針對送餐機器人進行研究。國內外賣公司餓了么聯合萬科推出送餐機器人“萬小餓”，主要應用場景為住宅、辦公、商業等場所[2]，送餐人員進入建筑物后將食物放入送餐機器人，然后由送餐機器人將食物送至用戶指定位置;上海交通大學研發了一款在餐廳使用的送餐機器人，顧客到店后可以使用送餐機器人訂餐，機器人會自動完成送餐與取餐等工作[3];澳洲外賣披薩連鎖店達美樂（Domino）聯合澳洲Marathon Robotics公司研發出世界上第一個快遞機器人DRU（Domino's Robotic Unit），作為一個可以獨立送餐的機器人，其使用GPS（全球定位系統）導航，并配置激光避障設備，能夠勝任在城市街道上的送餐任務[4];英國外賣訂購網站Just Eat曾推出一款送餐機器人[5]，操作人員可通過智能手機APP控制機器人到達指定地點，用戶通過訂餐APP解鎖機器人獲取外賣。如今送餐機器人在各種場合出現得越來越頻繁，為人們生活帶來了便利。本文創新點在于通過改進路徑規劃算法，將送餐機器人運用于列車環境中，并設計上位機軟件系統，以方便管理員對送餐機器人進行管理。目前列車上通常是由列車員手動推送餐車進行送餐服務，本文提出的送餐機器人旨在改變當前的送餐方式，將工作人員從繁瑣的送餐工作中解放出來，并為乘客帶來更好的乘車體驗。乘客可通過手機APP與機器人操作面板完成訂餐，下單完成并確認后，送餐機器人可將食物送至指定位置。因此，送餐機器人行駛路線的合理性是確保高質量完成送餐任務的前提。

路徑規劃研究分為兩部分：環境信息獲取與算法實現[6]。列車環境參數主要參考和諧號動車組，每節車廂長約25m，主要分為8節和16節兩種車型。機器人相關路徑算法種類較多，主要包括Floyed算法、動態路徑規劃方法和蟻群算法等。Floyed算法實現過程簡單，但若兩點互為對方連接距離矩陣中的最小點，則可能出現死鎖現象，無法跳出局部最優[7];動態路徑規劃方法的最優解需要基于每個子問題的最優解[8]，以此獲取最優策略，其本質上采用的是迭代思想，所以當劃分情況增多、計算壓力太大則無法得出最優解;蟻群算法通過模擬蟻群覓食過程中信息素的變化，通過正反饋調控得出最佳覓食路徑。該算法易于與其它算法相結合進行優化，每次模擬得出的最優路徑不易陷入最優陷阱，所以該算法可以結合其它算法進行性能優化與功能擴展，例如加快收斂速度、實現動態避障功能等[9]。

利用C#語言優秀的封裝特性，自定義算法實現過程中所需的數據體成員和成員函數，并將環境地圖建模轉換成計算機可以理解的結構體，在此基礎上尋找最優路徑。

1 路徑規劃

1.1 基于柵格法的環境地圖建模

環境地圖建模方式主要有柵格法、可視圖法與拓撲法，其中柵格法是首先將機器人所處環境劃分為相同尺寸的網格[10-11]，其次按照物理空間標志出障礙物格子。如圖1所示，白色格子可以通行，黑色格子不能通行。特殊情況為：本文規定如果在機器人路徑選擇時發生了斜穿，則需要判斷當前位置到斜穿點兩邊是否是障礙柵格，如果是，該段路徑則是非法的。

1.2 蟻群算法思想

蟻群算法是由意大利學者DORIGO M等[12]于1991年根據螞蟻覓食特點首次提出的一種仿生算法，螞蟻在覓食時會在經過的路徑上留下一種隨時間推移不斷減少的信息素，后來的螞蟻可以接收到這種信息素，并根據信息素濃度選擇路徑，在迭代一段時間后算法收斂于最短路徑。

單只螞蟻行為需要依靠環境進行選擇，螞蟻個體的路徑轉移概率[pkij（t）]計算公式為[13]：

1.3 蟻群算法參數設置

公式（1）-（3）中出現的參數[14]對最優解與收斂速度影響很大。信息啟發因子[α]與收斂速度呈正相關關系，且[α]越大時，螞蟻在選擇路徑時則越容易選擇之前的路徑;期望啟發式因子[β]越小，將導致螞蟻陷入隨機搜索，越不容易找到最優解;信息素揮發因子[ρ]與收斂速度呈正相關關系，與全局搜索能力呈負相關關系。

在仿真實驗中，采用20*20的柵格地圖，參數默認值為：m=20，[α]=1，[β]=3，[ρ]=0.3。測試[α]、[β]、[ρ]對路徑長度的影響，每組進行10次仿真實驗，[α]取值為{0.1，0.5，1，1.5，2，2.5，3，3.5，4，4.5，5，5.5，6，6.5，7，7.5，8}，[β]取值為{0.1，0.5，1，1.5，2，2.5，3，3.5，4，4.5，5，5.5，6，6.5，7，7.5，8}，[ρ]取值為{0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8}。對每組進行10次模擬實驗，并對結果取平均，各參數與平均路徑長度之間的關系通過仿真實驗得出結論。實驗結果表明，當[α∈1，3.5]，[β∈1，3]，[ρ∈0.5，0.8]時，蟻群算法效果較好。

由于蟻群算法中各參數之間存在關聯性，通常根據實際情況，按照實驗結果選取合適的參數組合。通過仿真實驗，本文將參數設置為：[α]=1，[β]=2，[ρ]=0.5。

2 改進蟻群算法

2.1 能見度信息調整

能見度[η]反映了在路徑搜索過程中對路徑選擇的影響，一般將能見度[η]設置為[1Dij]或[1Dig]，其中[1Dij]表示相鄰節點距離，[1Dig]表示當前節點到目標節點之間距離。當[η]設置為[1Dij]或[1Dig]時，其對路徑選擇有不同傾向，分別表現為收斂路徑傾向于直線和斜線。為了防止因收斂路徑傾向的影響，在某些環境地圖中使算法效果變差，將能見度[η]設置為[1Dij*Dig]時可以平衡其對算法的影響。

2.2 螞蟻“夭折”策略改進

在基本蟻群算法中，當一組螞蟻在某個柵格點上計算下個路徑轉移的柵格點時，發現此時無路可走，尤其在U型柵格圖中容易出現該情況，基本蟻群算法則按照“夭折”策略，將該組螞蟻設置為死亡狀態，該組螞蟻信息素也將停止更新，并將該組螞蟻所在柵格點加入禁忌表中，以防其它組螞蟻進入該柵格點[15]。該策略解決了算法停滯問題，但需要強行將螞蟻設置為死亡，減少了螞蟻群體中繼續搜索路徑的螞蟻數量。

為解決該問題，本文針對螞蟻陷入無后繼路徑的情況時，將當前柵格點加入禁忌表，返回上一柵格點，重新按照路徑轉移策略計算新的柵格點，從而使該組螞蟻能跳出當前柵格點，并繼續進行路徑搜索，避免了在基本蟻群算法中因螞蟻死亡導致的路徑搜索能力下降。

2.3 直達判斷

在實際工作環境中，可通行的區域遠遠大于不可通行區域。在很多情況下，螞蟻當前位置與目標柵格之間的直線連接中并沒有障礙柵格阻擋，螞蟻可通過某個方向直達目標柵格。但根據蟻群算法路徑轉移公式中的轉移策略，蟻群算法在運行過程中，螞蟻無法判斷能否從當前柵格直達目標柵格。在圖4、圖5中，起始點坐標是（0，19），目標點坐標是（9，10），黑色柵格代表有障礙、不可通行的柵格，黑色直線表示蟻群算法計算出的路線。未加入直達判斷的蟻群算法中可能會出現圖4的情況，在加入直達判斷的算法中可以避免該情況出現（見圖5）。

2.4 實驗結果及分析

根據環境建立柵格地圖（見圖1），黑色柵格代表有障礙、不可通行，白色柵格代表可通過的柵格，起始點坐標是（0，19），目標坐標是（19，0）。兩組實驗各進行10次，并對結果取平均值。將基本蟻群算法與改進蟻群算法進行對比，結果如表1所示。

由實驗結果可知，相比于基本蟻群算法，改進蟻群算法的平均路徑長度和平均轉彎次數都得到了明顯優化，從而有效提高執行效率，降低送餐機器人行進過程中的誤差。

3 上位機軟件平臺設計

根據送餐機器人的功能需求設計合理、可靠的上位機軟件系統，系統采用C#語言編寫[16]。上位機軟件系統具備路徑規劃功能和設備管理功能，結合現有定位系統，完成上位機與下位機的通訊，并根據訂單需求規劃出合理路徑，管理員可以通過上位機軟件系統隨時了解送餐機器人運行情況。

下位機控制器選用英國Trio Motion公司開發的基于微處理技術的高密度數字運動控制器Trio MC4N，MC4N基于最新版532MHz ARM處理器[17-18]，支持MODBUS TCP/IP協議，在多軸設備中應用廣泛。C#是一種由微軟開發的面向對象編程語言，可運行于微軟的.NET Framework平臺上[19]。作為由C/C++衍生出來的編程語言，在繼承C/C++強大功能的同時，還在其基礎上實現了突破，對于大型與小型系統都可以勝任，且在設計程序界面時十分迅速、便利。C#由于具有易學易用的特點，可以在較短時間內幫助程序人員設計出界面友好、功能強大的軟件平臺。數據庫選擇SQL Server 2008，其是一個基于C/S模型的關系型數據庫，可以有效實現對數據的存儲與管理[20]。

3.1 數據庫模塊

數據庫模塊設計直接影響上位機軟件平臺的實現，本文針對自主送餐機器人的上位機進行數據庫設計。數據庫需要管理用戶信息、訂單信息、訂單完成情況等，并根據管理員需要，導出已完成的訂單信息。

3.2 服務器設計

服務器端處理與存儲環境信息，根據客戶端指令進行路徑規劃，并能實現與客戶端的通信，將路徑規劃結果傳輸給客戶端。

3.3 客戶端設計

客戶端通過MODBUS TCP/IP協議實現與下位機的通訊[21-22]，主要功能包括：設備連接、環境初始化、運動控制、訂單管理與訂單信息導出。客戶端根據機器人IP進行設備連接，并確定寄存器起始地址。根據服務器端對環境信息的處理，客戶端需要設定環境初始化信息，接收下位機采集的視頻信息，并根據路徑規劃結果對送餐機器人進行運動控制。送餐機器人控制界面如圖8所示。

4 結語

本文研究了列車環境下送餐機器人路徑規劃與軟件控制方案，本文設計的送餐機器人路徑規劃系統采用改進蟻群算法，該算法較傳統蟻群算法縮短了路徑長度，減少了轉彎次數，加快了算法收斂速度。實驗結果表明，改進后的路徑規劃算法性能得到了有效提升，上位機軟件系統可輔助管理人員隨時了解送餐機器人運行情況，并與其實現有效通訊。由于送餐機器人的工作環境路況比較單一，基于柵格地圖的路徑規劃系統對于環境相對固定的情況較為適用。實際運用過程中會出現多個機器人共同完成任務的情況，另外機器人在運行過程中可能會探測到動態障礙物，未來可對基于蟻群算法的任務調度與動態避障作進一步研究。

參考文獻：

[1] 盧川. 美國服務機器人技術路線圖（下）[J]. 機器人產業，2016（5）：86-97.

[2] 搜狐新聞. 餓了么攜手萬科再推出外賣機器人[EB/OL]. www.sohu.com/a/197675763_99983474.html，2017.

[3] YU Q X，YUAN C，FU ZH，et al. Research of the localization of ?restaurant service robot [J]. International Journal of Advanced Robotic Systems，2010， 7（3）： 227-238.

[4] 環球網. 全球首創！澳大利亞Domino推出送餐機器人，萌萌噠！[EB/OL].http：//www.huanqiu.com/www/mobilenews/hot/2016-03/873 8434.html.

[5] 搜狐新聞. 英食物外送機構將在歐洲四城市試用機器人送餐[EB/OL]. http：//www.sohu. com/a/102335913_162522.html.

[6] 王麗. 移動機器人路徑規劃方法研究[D]. 西安：西北工業大學，2007.

[7] 石為人，王楷. 基于Floyd算法的移動機器人最短路徑規劃研究[J]. 儀器儀表學報，2009，30（10）：2088-2092.

[8] 金小平，何克忠. 移動機器人的動態路徑規劃及控制[J]. 機器人，1990（6）：10-17.

[9] 王哲，孫樹棟，曹飛祥. 動態環境下移動機器人路徑規劃的改進蟻群算法[J]. 機械科學與技術，2013， 32（1）：48-52.

[10] 王娟娟，曹凱. 基于柵格法的機器人路徑規劃[J]. 農業裝備與車輛工程，2009（4）：14-17.

[11] 郝宗波，洪炳镕，黃慶成. 基于柵格地圖的機器人覆蓋路徑規劃研究[J]. 計算機應用研究，2007，24（10）：56-58.

[12] DORIGO M. Ant colony optimization[M]. California：Bradford Company，2004.

[13] 周磊. 改進蟻群算法在機器人路徑規劃中的應用研究[D]. 上海：華東理工大學，2013.

[14] 段海濱. 蟻群算法原理及其應用[M]. 北京：科學出版社， 2005.

[15] 鄭勇. 基于蟻群算法的移動機器人動態路徑規劃[D]. 成都：電子科技大學，2008.

[16] 譚東. C#開發數據應用程序的調試技巧[J]. 科技傳播，2010（9）： 110.

[17] 毛俊峰. 基于Trio控制器的焊接定位機器人控制系統研究[D]. 大連：大連交通大學，2011.

[18] TRIO MOTION TECHNOLOGY. Hardware reference manual V7.5.pdf[EB/OL]. http：//www.triomotion.cn/ tmt3/sitefiles/home.asp.

[19] 唐偉鋒. 淺談.NET環境下WinForm應用程序中的消息處理機制[J]. 信息與電腦：理論版，2011（2）：110.

[20] 陳文宇. 面向對象的關系數據庫設計[J]. 電子科技大學學報， 2002，31（1）：53-56.

[21] 潘悅. Modbus協議研究及其實驗系統的設計[D]. 哈爾濱：哈爾濱工業大學，2007.

[22] 潘洪躍. 基于MODBUS協議通信的設計與實現[J]. 計量技術， 2002（4）：35-36.

（責任編輯：黃 健）