嚴(yán)文娟 費(fèi)樹岷

摘 要：研究列車環(huán)境下送餐機(jī)器人路徑規(guī)劃與軟件控制方案，為更好地滿足實(shí)際需求，提出一種改進(jìn)的蟻群算法，以加快收斂速度、縮短路徑長(zhǎng)度及減少轉(zhuǎn)彎次數(shù)。實(shí)驗(yàn)中根據(jù)當(dāng)前環(huán)境構(gòu)建柵格圖，通過(guò)編寫的路徑規(guī)劃程序計(jì)算起始位置到目標(biāo)位置的路徑，完成當(dāng)前環(huán)境下的路徑規(guī)劃。上位機(jī)軟件平臺(tái)采用C#語(yǔ)言編寫，主要包括運(yùn)動(dòng)控制、訂單管理、通訊傳輸?shù)裙δ堋?shí)驗(yàn)結(jié)果表明，與基本蟻群算法相比，改進(jìn)蟻群算法具有更好的規(guī)劃效果，上位機(jī)軟件平臺(tái)與下位機(jī)可以實(shí)現(xiàn)有效的數(shù)據(jù)交換，并實(shí)現(xiàn)對(duì)送餐機(jī)器人的運(yùn)動(dòng)控制及系統(tǒng)管理等功能。

關(guān)鍵詞：送餐機(jī)器人;路徑規(guī)劃;C#;蟻群算法

DOI：10. 11907/rjdk. 182848 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP302文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2019）009-0026-04

Path Planning and Software Design Based on Dining Robot on Trains

YAN Wen-juan，F(xiàn)EI 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 引言

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

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

利用C#語(yǔ)言優(yōu)秀的封裝特性，自定義算法實(shí)現(xiàn)過(guò)程中所需的數(shù)據(jù)體成員和成員函數(shù)，并將環(huán)境地圖建模轉(zhuǎn)換成計(jì)算機(jī)可以理解的結(jié)構(gòu)體，在此基礎(chǔ)上尋找最優(yōu)路徑。

1 路徑規(guī)劃

1.1 基于柵格法的環(huán)境地圖建模

環(huán)境地圖建模方式主要有柵格法、可視圖法與拓?fù)浞ǎ渲袞鸥穹ㄊ鞘紫葘C(jī)器人所處環(huán)境劃分為相同尺寸的網(wǎng)格[10-11]，其次按照物理空間標(biāo)志出障礙物格子。如圖1所示，白色格子可以通行，黑色格子不能通行。特殊情況為：本文規(guī)定如果在機(jī)器人路徑選擇時(shí)發(fā)生了斜穿，則需要判斷當(dāng)前位置到斜穿點(diǎn)兩邊是否是障礙柵格，如果是，該段路徑則是非法的。

1.2 蟻群算法思想

蟻群算法是由意大利學(xué)者DORIGO M等[12]于1991年根據(jù)螞蟻覓食特點(diǎn)首次提出的一種仿生算法，螞蟻在覓食時(shí)會(huì)在經(jīng)過(guò)的路徑上留下一種隨時(shí)間推移不斷減少的信息素，后來(lái)的螞蟻可以接收到這種信息素，并根據(jù)信息素濃度選擇路徑，在迭代一段時(shí)間后算法收斂于最短路徑。

單只螞蟻行為需要依靠環(huán)境進(jìn)行選擇，螞蟻個(gè)體的路徑轉(zhuǎn)移概率[pkij（t）]計(jì)算公式為[13]：

1.3 蟻群算法參數(shù)設(shè)置

公式（1）-（3）中出現(xiàn)的參數(shù)[14]對(duì)最優(yōu)解與收斂速度影響很大。信息啟發(fā)因子[α]與收斂速度呈正相關(guān)關(guān)系，且[α]越大時(shí)，螞蟻在選擇路徑時(shí)則越容易選擇之前的路徑;期望啟發(fā)式因子[β]越小，將導(dǎo)致螞蟻陷入隨機(jī)搜索，越不容易找到最優(yōu)解;信息素?fù)]發(fā)因子[ρ]與收斂速度呈正相關(guān)關(guān)系，與全局搜索能力呈負(fù)相關(guān)關(guān)系。

在仿真實(shí)驗(yàn)中，采用20*20的柵格地圖，參數(shù)默認(rèn)值為：m=20，[α]=1，[β]=3，[ρ]=0.3。測(cè)試[α]、[β]、[ρ]對(duì)路徑長(zhǎng)度的影響，每組進(jìn)行10次仿真實(shí)驗(yàn)，[α]取值為{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}。對(duì)每組進(jìn)行10次模擬實(shí)驗(yàn)，并對(duì)結(jié)果取平均，各參數(shù)與平均路徑長(zhǎng)度之間的關(guān)系通過(guò)仿真實(shí)驗(yàn)得出結(jié)論。實(shí)驗(yàn)結(jié)果表明，當(dāng)[α∈1，3.5]，[β∈1，3]，[ρ∈0.5，0.8]時(shí)，蟻群算法效果較好。

由于蟻群算法中各參數(shù)之間存在關(guān)聯(lián)性，通常根據(jù)實(shí)際情況，按照實(shí)驗(yàn)結(jié)果選取合適的參數(shù)組合。通過(guò)仿真實(shí)驗(yàn)，本文將參數(shù)設(shè)置為：[α]=1，[β]=2，[ρ]=0.5。

2 改進(jìn)蟻群算法

2.1 能見度信息調(diào)整

能見度[η]反映了在路徑搜索過(guò)程中對(duì)路徑選擇的影響，一般將能見度[η]設(shè)置為[1Dij]或[1Dig]，其中[1Dij]表示相鄰節(jié)點(diǎn)距離，[1Dig]表示當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間距離。當(dāng)[η]設(shè)置為[1Dij]或[1Dig]時(shí)，其對(duì)路徑選擇有不同傾向，分別表現(xiàn)為收斂路徑傾向于直線和斜線。為了防止因收斂路徑傾向的影響，在某些環(huán)境地圖中使算法效果變差，將能見度[η]設(shè)置為[1Dij*Dig]時(shí)可以平衡其對(duì)算法的影響。

2.2 螞蟻“夭折”策略改進(jìn)

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

為解決該問(wèn)題，本文針對(duì)螞蟻陷入無(wú)后繼路徑的情況時(shí)，將當(dāng)前柵格點(diǎn)加入禁忌表，返回上一柵格點(diǎn)，重新按照路徑轉(zhuǎn)移策略計(jì)算新的柵格點(diǎn)，從而使該組螞蟻能跳出當(dāng)前柵格點(diǎn)，并繼續(xù)進(jìn)行路徑搜索，避免了在基本蟻群算法中因螞蟻死亡導(dǎo)致的路徑搜索能力下降。

2.3 直達(dá)判斷

在實(shí)際工作環(huán)境中，可通行的區(qū)域遠(yuǎn)遠(yuǎn)大于不可通行區(qū)域。在很多情況下，螞蟻當(dāng)前位置與目標(biāo)柵格之間的直線連接中并沒(méi)有障礙柵格阻擋，螞蟻可通過(guò)某個(gè)方向直達(dá)目標(biāo)柵格。但根據(jù)蟻群算法路徑轉(zhuǎn)移公式中的轉(zhuǎn)移策略，蟻群算法在運(yùn)行過(guò)程中，螞蟻無(wú)法判斷能否從當(dāng)前柵格直達(dá)目標(biāo)柵格。在圖4、圖5中，起始點(diǎn)坐標(biāo)是（0，19），目標(biāo)點(diǎn)坐標(biāo)是（9，10），黑色柵格代表有障礙、不可通行的柵格，黑色直線表示蟻群算法計(jì)算出的路線。未加入直達(dá)判斷的蟻群算法中可能會(huì)出現(xiàn)圖4的情況，在加入直達(dá)判斷的算法中可以避免該情況出現(xiàn)（見圖5）。

2.4 實(shí)驗(yàn)結(jié)果及分析

根據(jù)環(huán)境建立柵格地圖（見圖1），黑色柵格代表有障礙、不可通行，白色柵格代表可通過(guò)的柵格，起始點(diǎn)坐標(biāo)是（0，19），目標(biāo)坐標(biāo)是（19，0）。兩組實(shí)驗(yàn)各進(jìn)行10次，并對(duì)結(jié)果取平均值。將基本蟻群算法與改進(jìn)蟻群算法進(jìn)行對(duì)比，結(jié)果如表1所示。

由實(shí)驗(yàn)結(jié)果可知，相比于基本蟻群算法，改進(jìn)蟻群算法的平均路徑長(zhǎng)度和平均轉(zhuǎn)彎次數(shù)都得到了明顯優(yōu)化，從而有效提高執(zhí)行效率，降低送餐機(jī)器人行進(jìn)過(guò)程中的誤差。

3 上位機(jī)軟件平臺(tái)設(shè)計(jì)

根據(jù)送餐機(jī)器人的功能需求設(shè)計(jì)合理、可靠的上位機(jī)軟件系統(tǒng)，系統(tǒng)采用C#語(yǔ)言編寫[16]。上位機(jī)軟件系統(tǒng)具備路徑規(guī)劃功能和設(shè)備管理功能，結(jié)合現(xiàn)有定位系統(tǒng)，完成上位機(jī)與下位機(jī)的通訊，并根據(jù)訂單需求規(guī)劃出合理路徑，管理員可以通過(guò)上位機(jī)軟件系統(tǒng)隨時(shí)了解送餐機(jī)器人運(yùn)行情況。

下位機(jī)控制器選用英國(guó)Trio Motion公司開發(fā)的基于微處理技術(shù)的高密度數(shù)字運(yùn)動(dòng)控制器Trio MC4N，MC4N基于最新版532MHz ARM處理器[17-18]，支持MODBUS TCP/IP協(xié)議，在多軸設(shè)備中應(yīng)用廣泛。C#是一種由微軟開發(fā)的面向?qū)ο缶幊陶Z(yǔ)言，可運(yùn)行于微軟的.NET Framework平臺(tái)上[19]。作為由C/C++衍生出來(lái)的編程語(yǔ)言，在繼承C/C++強(qiáng)大功能的同時(shí)，還在其基礎(chǔ)上實(shí)現(xiàn)了突破，對(duì)于大型與小型系統(tǒng)都可以勝任，且在設(shè)計(jì)程序界面時(shí)十分迅速、便利。C#由于具有易學(xué)易用的特點(diǎn)，可以在較短時(shí)間內(nèi)幫助程序人員設(shè)計(jì)出界面友好、功能強(qiáng)大的軟件平臺(tái)。數(shù)據(jù)庫(kù)選擇SQL Server 2008，其是一個(gè)基于C/S模型的關(guān)系型數(shù)據(jù)庫(kù)，可以有效實(shí)現(xiàn)對(duì)數(shù)據(jù)的存儲(chǔ)與管理[20]。

3.1 數(shù)據(jù)庫(kù)模塊

數(shù)據(jù)庫(kù)模塊設(shè)計(jì)直接影響上位機(jī)軟件平臺(tái)的實(shí)現(xiàn)，本文針對(duì)自主送餐機(jī)器人的上位機(jī)進(jìn)行數(shù)據(jù)庫(kù)設(shè)計(jì)。數(shù)據(jù)庫(kù)需要管理用戶信息、訂單信息、訂單完成情況等，并根據(jù)管理員需要，導(dǎo)出已完成的訂單信息。

3.2 服務(wù)器設(shè)計(jì)

服務(wù)器端處理與存儲(chǔ)環(huán)境信息，根據(jù)客戶端指令進(jìn)行路徑規(guī)劃，并能實(shí)現(xiàn)與客戶端的通信，將路徑規(guī)劃結(jié)果傳輸給客戶端。

3.3 客戶端設(shè)計(jì)

客戶端通過(guò)MODBUS TCP/IP協(xié)議實(shí)現(xiàn)與下位機(jī)的通訊[21-22]，主要功能包括：設(shè)備連接、環(huán)境初始化、運(yùn)動(dòng)控制、訂單管理與訂單信息導(dǎo)出?？蛻舳烁鶕?jù)機(jī)器人IP進(jìn)行設(shè)備連接，并確定寄存器起始地址。根據(jù)服務(wù)器端對(duì)環(huán)境信息的處理，客戶端需要設(shè)定環(huán)境初始化信息，接收下位機(jī)采集的視頻信息，并根據(jù)路徑規(guī)劃結(jié)果對(duì)送餐機(jī)器人進(jìn)行運(yùn)動(dòng)控制。送餐機(jī)器人控制界面如圖8所示。

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 盧川. 美國(guó)服務(wù)機(jī)器人技術(shù)路線圖（下）[J]. 機(jī)器人產(chǎn)業(yè)，2016（5）：86-97.

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

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

[4] 環(huán)球網(wǎng). 全球首創(chuàng)！澳大利亞Domino推出送餐機(jī)器人，萌萌噠！[EB/OL].http：//www.huanqiu.com/www/mobilenews/hot/2016-03/873 8434.html.

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

[6] 王麗. 移動(dòng)機(jī)器人路徑規(guī)劃方法研究[D]. 西安：西北工業(yè)大學(xué)，2007.

[7] 石為人，王楷. 基于Floyd算法的移動(dòng)機(jī)器人最短路徑規(guī)劃研究[J]. 儀器儀表學(xué)報(bào)，2009，30（10）：2088-2092.

[8] 金小平，何克忠. 移動(dòng)機(jī)器人的動(dòng)態(tài)路徑規(guī)劃及控制[J]. 機(jī)器人，1990（6）：10-17.

[9] 王哲，孫樹棟，曹飛祥. 動(dòng)態(tài)環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃的改進(jìn)蟻群算法[J]. 機(jī)械科學(xué)與技術(shù)，2013， 32（1）：48-52.

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

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

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

[13] 周磊. 改進(jìn)蟻群算法在機(jī)器人路徑規(guī)劃中的應(yīng)用研究[D]. 上海：華東理工大學(xué)，2013.

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

[15] 鄭勇. 基于蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃[D]. 成都：電子科技大學(xué)，2008.

[16] 譚東. C#開發(fā)數(shù)據(jù)應(yīng)用程序的調(diào)試技巧[J]. 科技傳播，2010（9）： 110.

[17] 毛俊峰. 基于Trio控制器的焊接定位機(jī)器人控制系統(tǒng)研究[D]. 大連：大連交通大學(xué)，2011.

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

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

[20] 陳文宇. 面向?qū)ο蟮年P(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)[J]. 電子科技大學(xué)學(xué)報(bào)， 2002，31（1）：53-56.

[21] 潘悅. Modbus協(xié)議研究及其實(shí)驗(yàn)系統(tǒng)的設(shè)計(jì)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2007.

[22] 潘洪躍. 基于MODBUS協(xié)議通信的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)量技術(shù)， 2002（4）：35-36.

（責(zé)任編輯：黃 ?。?/p>