邱源　邱勝海

摘 要：該文研究了制造車(chē)間物料搬運(yùn)機(jī)器人行走路徑圖建模的過(guò)程及使用Dijkstra算法求解最短路徑方法，描述了物料搬運(yùn)機(jī)器人的構(gòu)成及行走原理，結(jié)合一個(gè)具體的曲軸零件加工車(chē)間機(jī)床設(shè)備布局，用圖數(shù)據(jù)庫(kù)進(jìn)行行走路徑圖建模，并應(yīng)用Dijkstra算法實(shí)現(xiàn)了圖路徑搜索，實(shí)踐表明圖數(shù)據(jù)庫(kù)建模具有簡(jiǎn)單性和易學(xué)性，對(duì)解決復(fù)雜機(jī)器人的行走路徑建模提供一種新的解決方案。

關(guān)鍵詞：搬運(yùn)機(jī)器人 行走路徑 圖數(shù)據(jù)庫(kù)建模 Dijkstra算法

中圖分類(lèi)號(hào)：TP319 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2017）02（b）-0255-02

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

1 搬運(yùn)機(jī)器人簡(jiǎn)述

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

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

2 行走路徑圖建模

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

2.1 圖數(shù)據(jù)庫(kù)建模元素

圖數(shù)據(jù)庫(kù)模型是一種用有向圖的方式建模，并將數(shù)據(jù)儲(chǔ)存在圖中的數(shù)據(jù)結(jié)構(gòu)[9]。圖數(shù)據(jù)庫(kù)可在圖模型的任意兩個(gè)節(jié)點(diǎn)間進(jìn)行最短路徑的計(jì)算。圖數(shù)據(jù)庫(kù)的模型一般用圓圈加一個(gè)方框表示節(jié)點(diǎn)，方框中用文字描述節(jié)點(diǎn)的標(biāo)簽，用帶箭頭的線段表示關(guān)系，關(guān)系名稱(chēng)寫(xiě)在線段的兩側(cè)，節(jié)點(diǎn)和關(guān)系一般都具有屬性，屬性用來(lái)描述節(jié)點(diǎn)或關(guān)系的特征，如機(jī)床表示節(jié)點(diǎn)，機(jī)床有機(jī)床型號(hào)、名稱(chēng)、加工零件、制造日期等屬性。

在制造車(chē)間中，常見(jiàn)的對(duì)象有車(chē)床、銑床、鏜床、裝卸站等設(shè)備，在圖模型中這些實(shí)體用節(jié)點(diǎn)表示，如果設(shè)備之間存在有加工工藝順序嚴(yán)格約束關(guān)系，則用帶箭頭的線段表示從一臺(tái)設(shè)備到另一臺(tái)設(shè)備，其中箭尾表示源設(shè)備，箭頭表示目標(biāo)設(shè)備，如果兩個(gè)設(shè)備之間互通，則用無(wú)箭頭線段描述，圖模型是由有單向關(guān)系的多節(jié)點(diǎn)、有雙向關(guān)系的多節(jié)點(diǎn)及有多個(gè)匯聚和分支關(guān)系的多節(jié)點(diǎn)等四種基本類(lèi)型組成，一個(gè)復(fù)雜的圖模型基本上由這四種基本元素組合構(gòu)成。

2.2 機(jī)器人行走路徑圖建模

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 姬東.圖論最短路徑問(wèn)題在消防選址中的應(yīng)用[J].武警學(xué)院學(xué)報(bào)，2009，25（12）：10-12.

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

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

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