基于A*算法的自動(dòng)尋路避障小車送餐系統(tǒng)

袁薪凱，晏林沖，方明輝，曹夢(mèng)祥，崔永利，王 浩

（1.哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150040；2.哈爾濱北方防務(wù)裝備股份有限公司，黑龍江 哈爾濱 150080）

近年來隨著經(jīng)濟(jì)的發(fā)展、人們生活水平質(zhì)量的提高，我國的餐飲業(yè)快速蓬勃發(fā)展，目前餐飲市場(chǎng)規(guī)模龐大、經(jīng)營企業(yè)數(shù)量眾多，但是與此同時(shí)，餐飲業(yè)也面臨著巨大的挑戰(zhàn)，日益上升的勞動(dòng)力成本、更好的服務(wù)體驗(yàn)要求，使很多餐飲企業(yè)的生產(chǎn)經(jīng)營面臨著巨大壓力，如圖1、圖2 所示。與此同時(shí)，隨著人工智能、互聯(lián)網(wǎng)、5G、大數(shù)據(jù)等技術(shù)的不斷創(chuàng)新與發(fā)展，極大地提高了餐飲企業(yè)的生產(chǎn)和經(jīng)營效率，推動(dòng)了餐飲行業(yè)的迭代升級(jí)。

圖1 餐企客流同比下降分布圖[1]

圖2 餐企面臨最大困難分布圖[1]

通過研發(fā)餐廳智能機(jī)器人，以機(jī)器人替代傳統(tǒng)人工服務(wù)員的點(diǎn)餐、送餐、結(jié)賬等服務(wù)，以提升餐飲企業(yè)的生產(chǎn)和經(jīng)營效率、降低勞動(dòng)力成本，從而幫助餐飲企業(yè)減輕經(jīng)營成本負(fù)擔(dān)，通過壓縮成本提升餐飲企業(yè)的盈利水平和能力，增強(qiáng)餐飲企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力。從而幫助餐飲企業(yè)壓縮經(jīng)營成本，以獲得更高的經(jīng)濟(jì)收益，提高利潤(rùn)水平在行業(yè)中擁有更好的產(chǎn)品競(jìng)爭(zhēng)力與產(chǎn)品優(yōu)勢(shì)。

同時(shí)，在新冠肺炎疫情的大背景下，雖然全民疫苗接種正在持續(xù)推進(jìn)中，但我們對(duì)病毒的認(rèn)知并不全面，零接觸仍然是有必要的，在這種形式下，“智能服務(wù)機(jī)器人+餐飲”的模式無疑成為非常好的選擇，這種以機(jī)器替代人工模式的應(yīng)用可以實(shí)現(xiàn)真正的用餐零接觸，可以做到讓顧客用餐安心，接觸放心，有助于疫情防護(hù)，保障消費(fèi)者餐飲安全。

1 系統(tǒng)的功能描述

1.1 總體概述

項(xiàng)目將研發(fā)設(shè)計(jì)一款餐廳智能機(jī)器人并投入量產(chǎn)和銷售。餐廳智能機(jī)器人可以履行餐廳服務(wù)員的基本職能，為用餐者提供點(diǎn)餐、送餐以及收銀等服務(wù)。用餐者來到餐廳后，機(jī)器人會(huì)自動(dòng)前往用餐者的餐位，為其提供語音智能服務(wù)，而用餐者聽到機(jī)器人的語音提示后，可以利用手機(jī)掃碼進(jìn)行點(diǎn)餐，點(diǎn)餐后機(jī)器人將前往取餐口為用餐者取餐，并準(zhǔn)確送達(dá)到用餐者的餐位。

1.2 自助送餐功能

通過調(diào)試硬件，協(xié)調(diào)運(yùn)作舵機(jī)，就可以實(shí)現(xiàn)對(duì)機(jī)械臂的精確控制，從而通過機(jī)械臂完成抓取食物的操作。通過機(jī)器人的攝像頭識(shí)別功能，可以自動(dòng)建模完成三維地圖的繪制，之后機(jī)器人可自動(dòng)規(guī)劃路線前往指定的桌號(hào)，從而實(shí)現(xiàn)機(jī)器人定向無人送餐的功能。

1.3 手機(jī)用戶端功能

用餐者通過掃描二維碼可以獲得餐廳內(nèi)的菜單信息，并可以自主下單、加餐和付款，下單完成后點(diǎn)菜數(shù)據(jù)可通過局域網(wǎng)，以規(guī)定的端口規(guī)則傳輸要打印的數(shù)據(jù)，并對(duì)數(shù)據(jù)解包打印訂單，以便后廚按需出菜。

1.4 定時(shí)消毒功能

通過設(shè)計(jì)好的定時(shí)程序，結(jié)合安裝在機(jī)器人上部的噴灑頭和消毒液存儲(chǔ)箱，配合使用機(jī)器人的攝像頭模塊產(chǎn)生的三維地圖，機(jī)器人則可定時(shí)完成對(duì)餐廳內(nèi)部的消毒工作。

2 整體設(shè)計(jì)

2.1 軟件部分

軟件部分主要分為機(jī)器人系統(tǒng)和用戶系統(tǒng)。在機(jī)器人系統(tǒng)中，機(jī)器人的軟件構(gòu)建于ROS 之上，對(duì)于機(jī)器人來說，軟件是一個(gè)整體，各部分的依賴程度都比較高，其所運(yùn)用的主要程序包含有底層驅(qū)動(dòng)，導(dǎo)航算法，Slam 算法，定時(shí)程序，利用這些可以實(shí)現(xiàn)機(jī)器人的尋路，送餐，定時(shí)消毒的功能；在用戶系統(tǒng)中，用戶通過掃描二維碼可以獲得餐廳內(nèi)的菜單信息，并可以自主下單，加餐和付款，用戶下單完成后點(diǎn)菜數(shù)據(jù)可通過局域網(wǎng)，以規(guī)定的端口規(guī)則傳輸要打印的數(shù)據(jù)，并對(duì)數(shù)據(jù)解包打印訂單，以便后廚按需出菜。

2.2 硬件部分

由于需要實(shí)現(xiàn)機(jī)器人的送餐，點(diǎn)餐以及自動(dòng)識(shí)別桌號(hào)，項(xiàng)目采用可自主移動(dòng)機(jī)器人，并且通過內(nèi)部的各個(gè)模塊協(xié)調(diào)配合，來實(shí)現(xiàn)機(jī)器人的精準(zhǔn)定路線移動(dòng)；同時(shí)，利用自主移動(dòng)機(jī)器人的機(jī)械臂來實(shí)現(xiàn)對(duì)食物的抓取，使其可以平穩(wěn)的運(yùn)送到顧客手中，并且安全地放在桌面上。硬件結(jié)構(gòu)如圖3 所示。

圖3 硬件結(jié)構(gòu)圖

（1）機(jī)器人包含一個(gè)工業(yè)級(jí)處理器，具有功耗低，抗干擾能力強(qiáng)，穩(wěn)定性高，處理速度快的特點(diǎn)，可以保證機(jī)器人的各個(gè)模塊正常運(yùn)行。

（2）機(jī)器人底盤為四輪式底盤，通過前半部分的2個(gè)主動(dòng)輪提供動(dòng)力前進(jìn)和產(chǎn)生差速控制變相和轉(zhuǎn)彎，同時(shí)后半部分擁有2 個(gè)萬向輪作為從動(dòng)輪，同時(shí)底盤配有兩個(gè)電機(jī)增加配重提供穩(wěn)定性，從而保證其轉(zhuǎn)彎角度的準(zhǔn)確性，同時(shí)大大提升了底盤的承重能力，還提升了機(jī)器人移動(dòng)速度。同時(shí)輪子使用不易打滑的橡膠材質(zhì)再次保證了運(yùn)行的精準(zhǔn)和穩(wěn)定。

（3）機(jī)器人包含一個(gè)1080P USB 攝像頭及深度視覺攝像頭，利用機(jī)器人平臺(tái)上的攝像頭可以實(shí)時(shí)運(yùn)行DSO 進(jìn)行三維建模，建立出周圍環(huán)境的三維地圖。此外，機(jī)器人還可以利用kinect 驅(qū)動(dòng)，通過其發(fā)布的點(diǎn)云將image_pipeline 轉(zhuǎn)換成障礙物柵格分布圖；之后底盤導(dǎo)航程序會(huì)自動(dòng)處理分析障礙物分布圖；最后根據(jù)rivz 發(fā)布的目標(biāo)導(dǎo)航點(diǎn)自主移動(dòng)。

（4）機(jī)器人具備慣性導(dǎo)航功能，可利用機(jī)器人自身佩戴的慣性傳感器（加速度和陀螺儀）和底盤編碼器信息進(jìn)行定位和移動(dòng)。

（5）機(jī)器人具有1 套自由度機(jī)械臂，由4 部分組成，分別是支架，舵機(jī)，控制器和電源，由STM32 核心控制，搭配ROS 進(jìn)行使用，抓取重量最大可達(dá)1 kg，利用機(jī)械臂可以實(shí)現(xiàn)對(duì)食物的抓取操作。

（6）機(jī)器人可搭載消毒用噴霧頭和消毒液存儲(chǔ)箱，可將消毒液進(jìn)行霧化后均勻的噴灑到餐廳的各個(gè)角落，實(shí)現(xiàn)無死角覆蓋。

整體結(jié)構(gòu)如圖4 所示。

圖4 整體結(jié)構(gòu)圖

3 使用A*算法的最優(yōu)路徑規(guī)劃算法的總體概要設(shè)計(jì)

3.1 A*及A 尋路算法

A*算法是彼得·哈特在A 算法上的改進(jìn)，證明了估價(jià)函數(shù)滿足條件是一定可以得到最優(yōu)解。估價(jià)函數(shù)滿足一定限制條件的算法稱為A*算法。它主要是推導(dǎo)出最短路徑的、最有效的、最直接的搜索方式，它同時(shí)也能解決實(shí)際問題中的搜索問題。

公式表示為：f*（n）=g*（n）+h*（n）

其中f*（n）是從初始狀態(tài)到n 狀態(tài)的最小代價(jià)估計(jì)，g*（n）是從初始狀態(tài)到n 狀態(tài)的最小代價(jià)，h*（n）（也被稱為啟發(fā)函數(shù)）是從n 狀態(tài)到最終狀態(tài)的最小估計(jì)代價(jià)。

（對(duì)于本項(xiàng)目?jī)?nèi)容，狀態(tài)即為路徑節(jié)點(diǎn)，代價(jià)估計(jì)就是點(diǎn)與點(diǎn)實(shí)際距離）

3.2 算法流程描述

（1）設(shè)置一個(gè)open 列表以及close 列表，open 列表代表可能要走的狀態(tài)，close 列表代表已經(jīng)走過的狀態(tài)。

（2）先把尋路源頭放入open 列表中。

（3）檢查open 列表，把f*（x）最小的狀態(tài)x 找出來，將之移除open 列表，放入close 表。

（4）然后判斷close 表中最小的狀態(tài)x 是否是目的地，若不是目的地則跳到第5 步，若是目的地，則從目標(biāo)節(jié)點(diǎn)一直回溯上去，直到尋路源頭，這時(shí)整條回溯路徑即為最短路徑。

（5）找出剛才最小狀態(tài)的所有相鄰狀態(tài)，將這些相鄰的但是未被遍歷過的（即未被放入過open 列表的）狀態(tài)k 放入open 列表，完成后跳轉(zhuǎn)到第三步。

3.3 啟發(fā)函數(shù)（即h*（n））

A*尋路算法中一個(gè)重要的子函數(shù)是啟發(fā)函數(shù)，主流的啟發(fā)函數(shù)有3 種，他們?cè)贏*尋路算法中所產(chǎn)生的效果有著很大不同，但是作用和功能都相同。

（1）曼哈頓式如圖5（a）。

（2）三角式如圖5（b）。

（3）對(duì)角式如圖5（c）。

圖5 3 種啟發(fā)函數(shù)對(duì)比[2]

3.4 啟發(fā)函數(shù)分析

如果不考慮g*（n）或者其遠(yuǎn)遠(yuǎn)小于h*（n），那么該算法就是最佳優(yōu)先搜索，將失去精準(zhǔn)度；如果相反不考慮h*（n）或者其遠(yuǎn)遠(yuǎn)小于g*（n）時(shí)，那么該算法就是迪杰斯特拉算法，將消耗大量時(shí)間。只有均衡兩者關(guān)系才能體現(xiàn)A*算法的優(yōu)越性。

如果只能有4 個(gè)方向可以走，那么曼哈頓是不錯(cuò)的方案，其公式為

D*（|startX-endX|+|startY-endY|）。

詳情如圖6（a）所示。

如果你的地圖允許對(duì)角線移動(dòng)，那么三角式是更好的方案，其公式為

D*max（|n.X-goal.X|，|n.Y-goal.Y|）。

詳情如圖6（b）所示。

如果你的單元可以往任意方向移動(dòng)（而不是沿著柵格的方向移動(dòng)），那么對(duì)角線式（即歐幾里得距離）是更好的方案，其公式為

詳情如圖6（c）所示。

圖6 3 種啟發(fā)函數(shù)方案對(duì)比

D 為每走一步需要消耗的代價(jià)。

由于本項(xiàng)目小車靈活性可自由移動(dòng)，故而本方案選擇對(duì)角式啟發(fā)函數(shù)最好。

4 基于激光雷達(dá)的自動(dòng)避障設(shè)計(jì)

激光雷達(dá)在智能機(jī)器人的研發(fā)、生產(chǎn)過程中，作為智能機(jī)器人感知傳感器，充當(dāng)“機(jī)器之眼”關(guān)鍵角色，在智能機(jī)器人系統(tǒng)里是核心感知傳感器。見表1。

表1 傳感器及其詳情

激光雷達(dá)系統(tǒng)按以下流程實(shí)現(xiàn)目標(biāo)監(jiān)測(cè)、導(dǎo)航定位和提取信息功能的工作。

（1）目標(biāo)識(shí)別。

（2）環(huán)境感知。

（3）目標(biāo)數(shù)據(jù)預(yù)處理。

（4）數(shù)據(jù)可視化。

（5）濾波處理。

（6）點(diǎn)云構(gòu)建深度圖像。

（7）點(diǎn)云關(guān)鍵點(diǎn)。

（8）特征提取。

通過激光雷達(dá)技術(shù)與人工智能機(jī)器人技術(shù)的巧妙結(jié)合，成功讓激光雷達(dá)系統(tǒng)組合成為智能機(jī)器人的眼睛，現(xiàn)如今已成為行業(yè)發(fā)展的關(guān)注熱點(diǎn)，目前激光雷達(dá)結(jié)合SLAM 算法應(yīng)用于智能機(jī)器人視覺系統(tǒng)，已經(jīng)為智能機(jī)器人在自主定位、增量式建圖和路徑規(guī)劃方面提供了良好的保障[3]。

5 結(jié)束語

餐廳智能機(jī)器人具有豐富的功能，迅捷的自動(dòng)尋路功能，優(yōu)良的自動(dòng)避障技術(shù)，使其能夠在用餐高峰期及時(shí)地招待用餐者，很好地滿足用餐者的服務(wù)需求，為消費(fèi)者帶來良好的用餐體驗(yàn)。餐廳智能機(jī)器人的推廣應(yīng)用，將有助于整個(gè)餐飲行業(yè)服務(wù)質(zhì)量和服務(wù)水平的提升。