基于matlab的AGV行駛地圖數(shù)據(jù)結(jié)構(gòu)設(shè)計研究

凌忠奇，武啟平，金亞萍，趙 瑋，牛海頤

（機械科學(xué)研究總院，北京 100044）

0 引言

AGV是Automatic Guided Vehicles 的簡稱，屬于輪式移動機器人（WMR――Wheeled Mobile Robot）的范疇。根據(jù)美國物流協(xié)會定義，AGV是指裝備有電磁或光學(xué)自動導(dǎo)引裝置，能夠沿規(guī)定的導(dǎo)引路徑行駛，具有安全保護(hù)以及各種移載功能的運輸車。隨著科學(xué)的發(fā)展和技術(shù)的不斷進(jìn)步，物流系統(tǒng)越來越朝著智能化的方向發(fā)展。AGV系統(tǒng)在企業(yè)自動化生產(chǎn)過程和計算機綜合生產(chǎn)系統(tǒng)(CIMS)中，尤其是高度自動化的煙草、汽車、民航、鋼鐵、郵政、印鈔等行業(yè)，高度清潔的電子、醫(yī)藥、食品等行業(yè)，冷凍、核材料、感光材料等特種行業(yè)有著廣闊的應(yīng)用前景[1]。因為具有較高的柔性、能夠?qū)崟r監(jiān)視和控制、安全可靠和維護(hù)方便等特點，是現(xiàn)代物流系統(tǒng)的關(guān)鍵裝備，也是現(xiàn)代物流自動化的關(guān)鍵橋梁。

AGV小車的核心技術(shù)包括導(dǎo)航技術(shù)、路徑規(guī)劃技術(shù)和導(dǎo)引控制技術(shù)。地圖數(shù)據(jù)是以上核心技術(shù)的基礎(chǔ)，因此對于地圖數(shù)據(jù)的存儲和利用吸引了越來越多科研人員的關(guān)注。

根據(jù)機器人對環(huán)境信息獲取的程度不同，路徑規(guī)劃可分為兩種類型：環(huán)境信息完全知道的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃。環(huán)境信息完全知道的全局路徑規(guī)劃，適用于靜態(tài)環(huán)境，路徑是離線規(guī)劃的；環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃是通過傳感器在線地對機器人的工作環(huán)境進(jìn)行探測，獲取障礙物的位置、形狀和尺寸等信息來完成規(guī)劃的，路徑是在線規(guī)劃的[2]。

1 行駛空間的數(shù)據(jù)描述

要實現(xiàn)AGV小車在場地內(nèi)沿固定路線行走，就要對小車的行駛空間做數(shù)學(xué)的區(qū)分，標(biāo)記固定的行駛路線。整個地圖由點和線段組成，點的兩端是線段，線段的兩端是點。點作為AGV小車的正常情況下最小的停靠單元。在點上可以供AGV小車實現(xiàn)預(yù)設(shè)的動作。在AGV小車有行走請求時，采用申請線段的方式，如果申請通過，小車向前行進(jìn)，否則原地等待。

其數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1 點的基本信息數(shù)據(jù)結(jié)構(gòu)

線段是AGV小車的行駛路線，應(yīng)記錄線段的線段號、起點、終點、行駛形式、線段長度和設(shè)計速度等信息，其數(shù)據(jù)結(jié)構(gòu)如表2所示。

表2 線段的基本信息數(shù)據(jù)結(jié)構(gòu)

點和點之間由線段做作為連接，可以有連接關(guān)系矩陣表示。其中縱向表頭是起點點號，橫向表頭是終點點號。點和本身用0表示，有邏輯連接用10表示，無邏輯連接用inf（無窮大）表示。以八個點為例，表示形式如表3所示。

表3 拓?fù)潢P(guān)系矩陣

點和線段之間的邏輯關(guān)系采用結(jié)構(gòu)體的形式。根部是點號，一級支路是與點直接相連點的點號，二級支路是以根部為起點，一級支路為終點的線段，而且要區(qū)分正行和逆行。

圖1 AGV行駛地圖

2 外廓線的繪制和作用

外廓線是指AGV小車沿著路線行駛，外輪廓所掃過的區(qū)域。這個區(qū)域的形狀與AGV小車外形尺寸、主動輪的個數(shù)及位置相關(guān)。根據(jù)外廓線的形狀可以得到AGV小車線路之間的干涉關(guān)系表格，作為考慮小車外輪廓條件下避碰的基礎(chǔ)依據(jù)。

外廓線的形成方式是將線段分成若干小點，每個點顯示出AGV小車走在上面的外輪廓和角度，用疊加的的方式得到行走在整條線段上的外廓線。

外廓線是考慮小車外輪廓條件下避碰的必要數(shù)據(jù)。根據(jù)檢測外廓線的相互關(guān)系，可以得到線路行走的相互干涉區(qū)域，形成線段分配相互影響的邏輯。如圖2所示。

圖2 線段外廓線干涉圖例

A小車預(yù)設(shè)路徑是線段6—7—4，B小車預(yù)設(shè)路徑是線段1—2—3—4，但明顯7號線段和2、3、4號線段有干涉。當(dāng)A小車通過對7號線段的占用時，B小車將停在2號線段的起點，等待A小車離開干涉線段再向前行進(jìn)。

3 路徑搜索功能及實現(xiàn)

AGV小車要實現(xiàn)自動行走就必須有小車從起點到終點的完整形式路徑。同時，在多車系統(tǒng)中，并非所有車輛沿著各自的最短路徑行進(jìn)就能夠使系統(tǒng)效率達(dá)到最高。還應(yīng)輸出所有可達(dá)的路徑，為車輛調(diào)度和系統(tǒng)優(yōu)化提供基礎(chǔ)。由于同向行駛的兩點之間的可以是正行也可以是逆行，分別對應(yīng)不同的線段號。因此所得的結(jié)果應(yīng)是結(jié)合小車此時的位置、初始朝向和目標(biāo)地終點朝向要求篩選出來的合理的線段鏈路序號。本文路勁搜素采用深度搜索算法，主要分成點的鏈路搜索、線段可行鏈路搜索和根據(jù)終點朝向要求的鏈路篩選。

3.1 采用深度搜索得出點之間的可行鏈路

深度優(yōu)先遍歷圖的方法是，從圖中某頂點A出發(fā)。

1）訪問頂點A；

2）依次從A的未被訪問的鄰接點出發(fā)，對圖進(jìn)行深度優(yōu)先搜索；直至圖中和A有路徑相通的頂點都被訪問；

3）遍歷所有點，直至所有點都作為搜索的起點訪問過為止。

深度優(yōu)先搜索（DFS）的基本框架如下：

DFS（Node）

if(Node=目標(biāo)點）

then//找到目標(biāo)，結(jié)束

for eachnext∈d[Node]

doDFS(next);

end

3.2 線段可行鏈路搜索

根據(jù)已有點的鏈路，搜索兩點間的可行線路，根據(jù)小車初始的朝向選擇可以行走的線段ID，在沒有調(diào)頭信號時，小車保持原來朝向，選擇線段；當(dāng)遇到調(diào)頭信號，并且滿足調(diào)頭條件時，更改小車朝向，根據(jù)新朝向選取合適的線段，直到到達(dá)目的地，輸出結(jié)果。

3.3 根據(jù)終點朝向要求的鏈路篩選

有些點充當(dāng)了站臺的作用，可以在該點上實現(xiàn)取卸貨動作。但是由于物理空間的要求，對朝向有固定要求。在所有可行的線段鏈路中，取到達(dá)終點前的最后一條線段的朝向作為選擇對象，如果滿足進(jìn)站朝向要求，則保留；如果不滿足則舍去。

4 地圖的屬性數(shù)據(jù)

在點和線段上還應(yīng)預(yù)留好屬性位。可以用來標(biāo)記以下信息：

1）此點是否可以停靠。由于多車系統(tǒng)中點位置選取不當(dāng)可能會導(dǎo)致系統(tǒng)正常資源不能激發(fā)，從而使局部達(dá)到資源容量最大化，導(dǎo)致死鎖。解決此問題可以把導(dǎo)致資源不能激發(fā)的點標(biāo)記為不可停靠。

2）線段上是否要加堵塞。由于再多車系統(tǒng)中會產(chǎn)生沖突型死鎖和資源型死鎖。在對應(yīng)的入口線段上添加有條件的堵塞，避免此類死鎖發(fā)生。

3）標(biāo)記小車動作。根據(jù)實際項目要求，某些點和線段上會有相關(guān)的動作或者輸出，可以通過在對應(yīng)的點和線段上添加標(biāo)記實現(xiàn)。

5 結(jié)論

物流自動化系統(tǒng)是一個新型的現(xiàn)代化高科技產(chǎn)業(yè)。AGV作為高性能工業(yè)機器人的典型產(chǎn)品。本文以《數(shù)據(jù)結(jié)構(gòu)》[3]為基礎(chǔ)進(jìn)行研究和開發(fā)，側(cè)重實用性，建立了行駛環(huán)境的電子地圖，實現(xiàn)了地圖數(shù)據(jù)的存儲和復(fù)雜網(wǎng)狀道路上單車所有可達(dá)路徑輸出，為AGV小車控制技術(shù)、車輛調(diào)度與系統(tǒng)優(yōu)化提供了關(guān)鍵技術(shù)支持。

[1] 引入AGV提升競爭力——訪機科發(fā)展公司智能輸送事業(yè)部總經(jīng)理武啟平[J].物流技術(shù)與應(yīng)用.2005,(7):81-83.

[2] 李磊,葉濤,等,移動機器人技術(shù)研究現(xiàn)狀與未來[J].機器人,2002,24(9).

[3] 汪沁,奚李峰.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社:2009.