搬運機器人行走路徑圖建模及搜索算法

邱源　邱勝海

摘 要：該文研究了制造車間物料搬運機器人行走路徑圖建模的過程及使用Dijkstra算法求解最短路徑方法，描述了物料搬運機器人的構成及行走原理，結合一個具體的曲軸零件加工車間機床設備布局，用圖數據庫進行行走路徑圖建模，并應用Dijkstra算法實現了圖路徑搜索，實踐表明圖數據庫建模具有簡單性和易學性，對解決復雜機器人的行走路徑建模提供一種新的解決方案。

關鍵詞：搬運機器人 行走路徑 圖數據庫建模 Dijkstra算法

中圖分類號：TP319 文獻標識碼：A 文章編號：1672-3791（2017）02（b）-0255-02

近年來，為了適應激烈的市場競爭，各制造企業(yè)紛紛購置高水平的數控加工設備、物料搬運機器人等輔助設備來提升產品的生產效率，使得各制造企業(yè)的物料自動化的程度不斷提升，這有助于我國實施“中國制造2025”。據資料統(tǒng)計：在物料的整個生產過程中，用于加工與檢驗環(huán)節(jié)的時間僅占5%，而其余95%的時間則處于儲存、裝卸、輸送和等待狀態(tài)，而制造成本的20%～40%直接與物流環(huán)節(jié)的流通時間相關[1]。物料搬運機器人作為物料運輸自動化的重要設備在國外應用比較廣泛，尤其在歐美等發(fā)達國家，發(fā)展迅速，應用廣泛，而亞洲日本韓國的發(fā)展技術水平、裝備數量及自動化程度等已經達到標準化、系列化生產的程度。在我國，由于勞動力成本低和工廠自動化程度低等因素，研究起步慢，近年來，隨著市場的需求提高，我國在物料搬運設備的設計制造等方面的投入逐步提高[2]。許多學者在機器人的路徑規(guī)劃研究中提出了先進算法，如在全局路徑規(guī)劃中常用的算法有圖論算法、A*啟發(fā)式算法、最短路徑算法等；局部路徑規(guī)劃中常用的算法有遺傳算法[3-4]、蟻群算法等，該文結合最短路徑算法對搬運機器人的全局路徑進行建模及搜索應用。

1 搬運機器人簡述

物料搬運機器人是制造車間物流系統(tǒng)的重要組成部分，是配置有電磁感應或光學感應等自動導引裝置，能夠沿事先設計的路徑行走，具有安全保護以及各種裝卸功能的自動設備，且大多數以輪式行走為主，比步行、爬行等非輪式的移動機器人行動更快捷、工作效率更高，且結構簡單。近年來，技術相對成熟的RFID技術應用在機器人上降低了成本，并使得路徑規(guī)劃更柔性。常見的物料搬運機器人是由車架、蓄電池（含充電裝置）、控制單元、驅動單元、轉向裝置（腳輪，可雙向行走）、傳感引導裝置（導航傳感器、地標傳感器、地板磁條等）以及物料裝卸裝置等構成。

其行走原理描述為：搬運機器人通過控制單元接收到控制計算機的行走到某目標點命令時，先將自己的位置狀態(tài)發(fā)送至控制計算機，由控制中心計算機根據事先設置的路徑搜索目標點的位置，計算并發(fā)出機器人需要前進還是后退的命令，由機器人控制單元接收命令通過驅動單元控制自己前進或后退，機器人的運動方向由導航傳感器與地板磁條相配合，當轉彎時，由腳輪旋轉控制，當通過某個機床設備時，地標傳感器檢測到該設備，并將測到的設備信息發(fā)送給控制計算機，判斷如果不是目標設備，則通知機器人繼續(xù)前進，如果是目標設備，則通知機器人停止運行，準備裝卸物料。

2 行走路徑圖建模

制造車間中的搬運機器人行走路徑與設備的布局關系密集，既要保持設備的物流高效通暢，又要保持搬運的安全性，其路徑規(guī)劃是指在具有障礙物的車間環(huán)境中，根據工藝路線，按照一定的評價標準（如行走路徑最短、轉彎次數最少等），尋找一條從起點到目標點的最優(yōu)路徑。設施初始布局可以采用SLP方法進行設計[5]，一般采用兩種路徑設計方法：第一種是考慮二維平面圖規(guī)劃，另一種采用傳感器規(guī)劃，該文以前者為例進行詳細的描述。

2.1 圖數據庫建模元素

圖數據庫模型是一種用有向圖的方式建模，并將數據儲存在圖中的數據結構[9]。圖數據庫可在圖模型的任意兩個節(jié)點間進行最短路徑的計算。圖數據庫的模型一般用圓圈加一個方框表示節(jié)點，方框中用文字描述節(jié)點的標簽，用帶箭頭的線段表示關系，關系名稱寫在線段的兩側，節(jié)點和關系一般都具有屬性，屬性用來描述節(jié)點或關系的特征，如機床表示節(jié)點，機床有機床型號、名稱、加工零件、制造日期等屬性。

在制造車間中，常見的對象有車床、銑床、鏜床、裝卸站等設備，在圖模型中這些實體用節(jié)點表示，如果設備之間存在有加工工藝順序嚴格約束關系，則用帶箭頭的線段表示從一臺設備到另一臺設備，其中箭尾表示源設備，箭頭表示目標設備，如果兩個設備之間互通，則用無箭頭線段描述，圖模型是由有單向關系的多節(jié)點、有雙向關系的多節(jié)點及有多個匯聚和分支關系的多節(jié)點等四種基本類型組成，一個復雜的圖模型基本上由這四種基本元素組合構成。

2.2 機器人行走路徑圖建模

該文在文獻[6]提供的某車間設施規(guī)劃方案II的基礎上進行行走路徑設計，設計原則為：根據車間設備的分布情況，按照物流通道劃分為若干行走路線，在設備之間有雙向可達通道，則在圖模型中繪制2個設備節(jié)點之間的雙向聯系，否則為單向聯系；在十字、T字及L字交叉路口的行走軌跡規(guī)定則按照交通行走規(guī)則制訂。

2.3 使用Dijkstra算法求解模型最短路徑

Dijkstra算法是經典的以寬度優(yōu)先搜索最短路徑問題的算法，該算法可以搜索指定任意節(jié)點到其他各個節(jié)點間的最短路徑，限于篇幅，略去算法步驟。

3 結語

該文研究了制造車間物料搬運機器人行走路徑圖建模的過程及使用Dijkstra算法求解最短路徑方法。圖數據庫建模不但能減少多種因素對算法的影響，而且使搜索算法具有準確性和簡單性。此外通過建立圖數據庫模型，將各個設備信息儲存在數據庫中，能減少模型后期維護的工作量。限于水平，該文只研究單個搬運機器人的路徑模型建模及搜索算法，進一步需要研究多個搬運機器人的行走路徑規(guī)劃及調度算法。

參考文獻

[1] 董鵬.制造業(yè)內部物流痛點與突破點[J].建設機械技術與管理，2015（11）：96-97.

[2] 劉洪偉，齊二石.基礎工業(yè)工程[M].化學工業(yè)出版社，2011.

[3] 姬東.圖論最短路徑問題在消防選址中的應用[J].武警學院學報，2009，25（12）：10-12.

[4] 夏謙，雷勇，葉小勇.遺傳算法在AGV全局路徑優(yōu)化中的應用[J].四川大學學報：自然科學版，2008，45（5）：1129-1136.

[5] 方慶琯，王轉.現代物流設施與規(guī)劃[M].2版.機械工業(yè)出版社，2013.

[6] 邱勝海，樊樹海，高成沖，等.CIMS 環(huán)境下車間設施規(guī)劃方案綜合評價方法研究[J].現代制造工程，2014（4）：1-6.