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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

圖1 AGV行駛地圖

2 外廓線的繪制和作用

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

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

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

圖2 線段外廓線干涉圖例

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

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

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

3.1 采用深度搜索得出點(diǎn)之間的可行鏈路

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

1）訪問頂點(diǎn)A；

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

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

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

DFS（Node）

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

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

for eachnext∈d[Node]

doDFS(next);

end

3.2 線段可行鏈路搜索

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

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

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

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

在點(diǎn)和線段上還應(yīng)預(yù)留好屬性位?？梢杂脕順?biāo)記以下信息：

1）此點(diǎn)是否可以?？俊Ｓ捎诙嘬囅到y(tǒng)中點(diǎn)位置選取不當(dāng)可能會(huì)導(dǎo)致系統(tǒng)正常資源不能激發(fā)，從而使局部達(dá)到資源容量最大化，導(dǎo)致死鎖。解決此問題可以把導(dǎo)致資源不能激發(fā)的點(diǎn)標(biāo)記為不可停靠。

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

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

5 結(jié)論

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

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

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

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