何倩倩， 張榮芬， 劉宇紅， 楊 宇， 彭 燕， 王曼曼

(貴州大學 大數據與信息工程學院，貴州 貴陽 550025)

0 引 言

隨著現代化商場規模日益擴大，人們在面對大型商場中各品牌店鋪數量增多、地形復雜且易迷路等問題時，人們很難快速地從各大商場中找到自己喜歡或欲到達的店鋪。目前，在導航方面，全球定位系統(GPS)定位導航室外精度為幾米，然而在室內GPS卻無法進行定位。傳統室內導航的方法運用黑線檢測導航、二維碼導航等技術，這些技術在改變和擴充路徑時都較麻煩且需要在地面鋪設引導線，這在實際場景中在實現與用戶體驗上都有很大的局限。

為此，學者們對相關技術展開了大量研究，伍洲等人[1]設計了上位機與DSP下位機的學習型智能規劃路徑機器人系統，黃超等人[2]采用射頻技術(RFID)進行定位，地磁感應電子羅盤相結合進行導航；Turk等人[3]對跟蹤特定地面的自主導航問題，采用彩色攝像機和激光測距儀完成通過路面跟蹤進行車輛自主導航。這些方法及系統對于實際操作、用戶體驗等方面都還有所欠缺。

本文設計了一種室內導購機器人自主導航系統。本系統采用優化的A*算法進行路徑規劃后導航。實驗表明系統能在突然有人出現時，能很好地避障且在較為復雜的室內環境中具有很好的實時性與魯棒性。

1 室內導購機器人系統的總體設計

系統由前端室內導購機器人和后端大數據云平臺組成。本系統采用樹莓派作為主控芯片，搭載雷達模塊、無線傳輸模塊、語音模塊、運動控制模塊等功能模塊完成對購物者引導至指定店鋪或推薦店鋪的功能。前端室內導購機器人實現語音交互、構建地圖、路徑規劃避障、智能導航等功能；后端在大數據云平臺上實現店鋪推薦功能。本系統的核心功能為：將語音識別所得推薦店鋪名或大數據云平臺處理所得推薦店鋪名與前端進行信息交互，從而引導購物者到達目的地。整體系統功能如圖1所示。

圖1 室內導購機器人功能框圖

本文主要完成導航系統中室內導購機器人地圖構建、路徑規劃、自主導航部分設計。室內導購機器人自主導航采用安裝Linux系統并配置ROS的樹莓派作為主控單元，采用思嵐v1激光雷達與慣性測量模組GY85對周圍信息感知后構建商鋪位置信息已知的二維柵格地圖；運用基于STM32芯片及外圍電路進行機器人的電機驅動。

2 室內導購機器人硬件系統設計

系統硬件設計包括安裝Linux系統并配置ROS(機器人操作系統)的樹莓派核心板和思嵐v1激光雷達及慣性測量模組GY85模塊。

2.1 主控單元模塊

考慮到系統的實時性及成本的原因，采用樹莓派核心板作為主控模塊。在此模塊上采用ROS進行開發，ROS采用分布式進程(即“節點”)框架進行設備控制[4]，通過不同節點的進程接收、發布、聚合各種信息，對機器人的運動操作和對各個部分功能單元所采集到的數據和信息匯總分析后，對機器人發出相應的控制指令。

2.2 激光雷達模塊

思嵐v1激光雷達獲取機器人周圍的環境信息。此雷達擁有360°掃描測距、12 m半徑的測量范圍，在系統中此雷達模塊用于感知機器人周圍環境信息并與GY85提供的數據信息進行融合，為機器人的決策規劃提供準確的環境信息和自身相對的位置信息，從而構建地圖。

3 室內導購機器人自主導航算法

系統主要分為地圖構建、路徑規劃等模塊組成。軟件設計主要以機器人前端作為服務端，大數據云平臺和TX2(NVIDIA Jetson TX2)作為客戶端進行交互。系統軟件設計框圖如圖2所示。

圖2 系統軟件框圖

軟件部分主要分為三個部分，大數據云平臺作為客戶端2與用戶交互得到目標店鋪；客戶端1與用戶語音交互得到目標店鋪；客戶端1與客戶端2設置標志位，確保機器人兩種方式用戶只能采取一種進行操作，并將最后的目標店鋪作為請求發送到服務端進行操作。服務端對客戶端發送的目標店鋪進行文件寫、讀操作，并對目標店鋪進行規劃路徑與導航，最終到達目的地。

3.1 先驗地圖構建

先驗地圖構建是機器人自主導航的基礎，本文需構建一個商鋪位置已知的地圖。通過激光雷達與GY85采集到的信息融合感知周圍環境信息，對信息進行處理后生成局部地圖，同時開啟地圖服務，移動機器人將局部地圖更新至全局地圖中，控制機器人移動到每個商鋪，將商鋪位置與朝向在代碼中定義，從而獲得商鋪在地圖中的位置，如此循環，直至全局地圖不再變化、所有商鋪商鋪位置信息已知時，所需地圖構建完成。

3.2 A*全局路徑規劃算法的優化

3.2.1 A*算法原理

A*是一種啟發式的路徑搜索算法，從起始位置開始，有限擴展從當前位置距離目標最近的路徑，一次擴展當前節點的8個方向的點[5,6]。該算法的基本原理如下：通過估價函數h(n)中包含的信息搜索目標所在方向算法路徑的形成

f(n)=g(n)+h(n)

(1)

式中h(n)小于實際代價，f(n)為起點經過狀態n到達終點的總代價，g(n)為路徑規劃的路徑代價，h(n)為到達目標的預測距離[7,8]。f(n)決定最短路徑，f(n)絕大部分取決于h(n)，A*得到代價最小路徑的前提是h(n)必須小于與目標的距離。如圖3所示，從Start出發，當前到達Middle點，目標為Goal點，g(n)為到Middle的路徑代價，h(n)為到達目標的預測距離，g(n)最小化能維持最小路徑距離，h(n)最小化能持續聚焦于尋找目標，兩者之和為找到的最佳搜索策略。

圖3 A*算法原理示意

A*找出代價最小的路徑的前提是所處環境為靜態環境。但在實際場景中，通常為較復雜的動態環境，此時對路徑規劃的要求較高，對于已構建好的地圖中出現新障礙物時，就對路徑規劃提出了較高要求。

3.2.2 A*算法的優化

為解決在機器人計算過程中對時間、空間要求較高的問題，本文在傳統A*算法基礎上加入逆向的A*算法遍歷，將A*算法同時從起始點與目標點同時出發，實現從目標點往目標點正向搜索和目標點往起始點的反向搜索。

傳統的A*算法創建2個表，open表也稱開啟列表，最初只有一個起始點，在后續節點擴展中會放入更多的節點，它是一個待檢查值的集合，close表也稱為關閉列表，列表中內容為存在已經檢查過的值的集合。從起始點進行節點擴展，對該節點周圍8個節點進行擴展，判斷8個方向的節點在open中是否存在(可通過的點)或為不可通行的點，若為不可通行的點，則將此點遺棄不做擴展。取其他節點作為父節點進行拓展，直至close中出現目標節點。

優化的A*算法主要思想是將傳統的僅從起始位置出發尋找最優路徑逼近終點優化為從起點向終點逼近的同時從終點向起點也逼近，這樣在一定條件下可以大大加快運行速度，提升系統的實時性。

該算法創建2個open列表，分別為open_a,open_b，3個close列表，分別為close_a,close_b,close_c。將起始點Start放入open_a,終點Goal放入open_b；open_a按照正向遍歷將滿足的節點放入close_a，open_b按照逆向遍歷將滿足的節點放入close_b，當close_a與close_b搜索到的節點為同一節點時，則從該節點出發分別向起點和終點回溯生成最優路徑，并將此路徑放入close_c，close_c為最優路徑集合。優化的A*算法流程圖如圖4所示，close_c表中的路徑即為最優路徑，在理想情況下，采用此方式使算法的速度相比與傳統算法將快1倍，保證了系統的實時性。

圖4 A*算法優化的流程

優化前后的時間對比如表1所示。表中數據記錄時間為從接收到指令開始處理到終點朝向店鋪時記錄的時間，不同的障礙物的復雜程度影響產生的效果也不一樣。

表1 算法優化對比

由表1可知，優化后的算法相比于優化前的算法，在無障礙環境下，平均時間提升了18 s左右，有障礙環境下，平均時間提升了32 s左右，保證了系統運行的實時性。

4 系統測試

本系統測試場景通過在實驗室搭建模擬環境，實驗室長約14 m，寬約8 m。實驗室內部有很多實驗桌模擬商場的店鋪及其他障礙物(包括箱子、椅子等等)。

首先，將機器人放置至模擬商場的該機器人的起始位置(設為Start)進行建圖，并將此位置作為模擬商場中機器人放置的起始位置，并設置好每個模擬店鋪的對應的機器人的位姿，構建已知商鋪位置的地圖及部分對應視角如圖5(a)所示。圖5(b)為機器人在當前環境地圖下的路徑規劃效果圖，由圖5(b)可知，路徑規劃會根據實際情況擇優選擇最短路徑。

圖5 模擬商場構建的地圖及路徑規劃路線效果

用戶通過與機器人語音交互或用掃描二維碼進入大數據云服務器平臺交互后獲得目標店鋪，機器人從起始位置出發至目標店鋪采用優化后的A*算法規劃全局路徑，提高了系統的實時性，機器人在自主移動的過程中進行局部路徑規劃來進行避障。圖6中先驗地圖路徑規劃可以避開先驗地圖中已存在的障礙物，在機器人遇到臨時障礙物時，機器人根據臨時障礙物調整路徑，從而避開障礙物，提高了系統的魯棒性。

圖6 遇到臨時障礙物時避障效果圖

5 結束語

本文完成了室內導購機器人地圖構建及路徑規劃及導航的軟件及硬件設計。采用激光雷達及GY85模塊獲取機器人的環境及狀態信息來進行建圖，引入A*算法并進行一定優化后進行定位并更新機器人位姿進行導航，實現了購物者通過本系統快速找到自己欲到達的理想目標店鋪。本系統在實體店中為廣大的購物者提供了方便，解決由于目前工作壓力大，網上購物無法確保質量而前往實體店購買時無法及時找到購物者欲到達的店鋪的問題。