基于matlab的AGV行駛地圖數據結構設計研究

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

（機械科學研究總院，北京 100044）

0 引言

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

AGV小車的核心技術包括導航技術、路徑規劃技術和導引控制技術。地圖數據是以上核心技術的基礎，因此對于地圖數據的存儲和利用吸引了越來越多科研人員的關注。

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

1 行駛空間的數據描述

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

其數據結構如表1所示。

表1 點的基本信息數據結構

線段是AGV小車的行駛路線，應記錄線段的線段號、起點、終點、行駛形式、線段長度和設計速度等信息，其數據結構如表2所示。

表2 線段的基本信息數據結構

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

表3 拓撲關系矩陣

點和線段之間的邏輯關系采用結構體的形式。根部是點號，一級支路是與點直接相連點的點號，二級支路是以根部為起點，一級支路為終點的線段，而且要區分正行和逆行。

圖1 AGV行駛地圖

2 外廓線的繪制和作用

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

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

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

圖2 線段外廓線干涉圖例

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

3 路徑搜索功能及實現

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

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

深度優先遍歷圖的方法是，從圖中某頂點A出發。

1）訪問頂點A；

2）依次從A的未被訪問的鄰接點出發，對圖進行深度優先搜索；直至圖中和A有路徑相通的頂點都被訪問；

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

深度優先搜索（DFS）的基本框架如下：

DFS（Node）

if(Node=目標點）

then//找到目標，結束

for eachnext∈d[Node]

doDFS(next);

end

3.2 線段可行鏈路搜索

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

3.3 根據終點朝向要求的鏈路篩選

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

4 地圖的屬性數據

在點和線段上還應預留好屬性位。可以用來標記以下信息：

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

2）線段上是否要加堵塞。由于再多車系統中會產生沖突型死鎖和資源型死鎖。在對應的入口線段上添加有條件的堵塞，避免此類死鎖發生。

3）標記小車動作。根據實際項目要求，某些點和線段上會有相關的動作或者輸出，可以通過在對應的點和線段上添加標記實現。

5 結論

物流自動化系統是一個新型的現代化高科技產業。AGV作為高性能工業機器人的典型產品。本文以《數據結構》[3]為基礎進行研究和開發，側重實用性，建立了行駛環境的電子地圖，實現了地圖數據的存儲和復雜網狀道路上單車所有可達路徑輸出，為AGV小車控制技術、車輛調度與系統優化提供了關鍵技術支持。

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

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

[3] 汪沁,奚李峰.數據結構[M].清華大學出版社:2009.