基于AGV的智能停車庫調度系統設計

(北京星航機電裝備有限公司 裝備制造技術研發中心，北京 100074)

0 引言

無人搬運車(automated guided vehicle，AGV)，指裝備有電磁或光學等自動導引裝置[1]，能夠按照預先設定的路徑自動行駛的運輸車，自動化程度高，具有無人駕駛、安全可靠等特點，通常采用蓄電池來為其供電，并可通過電腦來控制其行進路線以及行為。與物料搬運中常用的其他運輸載體相比，AGV的活動區域不受場地、道路和空間的限制。因此，在智慧物流中，最能充分體現其靈活性和柔性，在無人狀態下完成物料的快速轉運。

所謂全方位移動，是指運動系統具有平面內三個自由度，即可同時獨立的在前后、左右和原地旋轉三個方向上運動[2]，并在保持自身位姿不變的情況下實現任意方向的移動。全方位運動機構運動靈活多變，克服了傳統運動機構不能橫向移動、回轉半徑達、運動不靈活的缺陷。

本文調度系統所控制的AGV亦具備全向移動特性，其采用麥克納姆輪先進技術，四輪獨立驅動，可利用不同的輪組轉速和轉向組合，以任意姿態在二維平面內移動，不需要車體做出任何轉動即可實現平面上任意方向移動，可在原地任意角度旋轉，且能夠沿著平面上連續軌跡走到要求的位置，能夠最大限度的滿足精確定位和高精度軌跡控制的要求。其憑借著全方位運動機構橫向移動以及零半徑旋轉的特性，可以靈活方便的穿梭于狹小的空間中。

調度系統作為AGV自動運輸系統的“大腦”，很大程度上決定了AGV自動運輸系統是否可以高效運行。隨著司機駕駛技術差導致的停車難、城市道路停車位緊張等問題的日益暴露，市場對無人智慧泊車系統的需求越來越強烈。本文基于全向移動的AGV對智慧泊車調度系統進行了詳細的研究，并在此基礎上，給出了各個核心模塊的設計與整體框架圖。

1 智慧泊車系統總體方案

1.1 智慧泊車系統組成

智慧泊車系統主要由AGV小車、導航系統、調度系統、其他輔助設備等部分組成。

AGV主要由車架、驅動機構、動力系統、控制系統、手動移動系統、安全防撞系統等六部分組成，見圖1。其中驅動機構是整車的驅動部件，系統采用四套獨立的麥克納姆輪系，通過四輪速度合成完成車輛的各種運動；動力系統是整車各種能源的供應源，由動力電池和電源變換管理模塊組成；控制系統是整車的中央處理系統，完成車輛的運動控制。控制系統中的遙控模塊用于遙控架車運動，由遙控接收器和遙控發射端組成；安全防撞系統主要用于障礙物檢測，防止車輛之間或者車輛與其他設施的碰撞。

圖1 AGV小車的結構架構圖

導航系統的主要用于引導AGV沿著提前設定的路徑行走，同時確定自身的位置，具體包括引導線路(磁釘、二維碼、激光反射板等)和定位標識。目前常用的導航方式有磁條導航、視覺導航、激光導航等。

調度系統作為整個系統的核心，主要由上位機服務器、調度管理軟件等組成。

其他輔助設備，主要包括AGV充電設備、無線通信設備等。整個智慧泊車調度系統的網絡架構如圖2所示。

圖2 智慧泊車系統網絡拓撲圖

1.2 智慧泊車調度系統總體設計

智慧泊車調度系統由后臺管理模塊、外部通訊模塊(消息子系統)、路徑規劃模塊、數據庫模塊、電子地圖模塊、行車引導模塊、前端監控模塊、任務調度模塊幾個模塊構成，系統結構如圖3所示。其中數據庫模塊和通訊模塊是其他模塊的基礎，而路徑規劃模塊則是整個智慧泊車調度系統的研究重點，也是本文的講述重點。

圖3 智慧泊車調度系統結構圖

1.3 數據庫模塊

數據庫模塊編程選用基于COM和面向對象的ADO接口，開發時需要庫文件msado15.dll的支持。

數據庫子系統為其他各軟件模塊提供數據庫訪問服務，讓各軟件系統與數據庫表的設計及讀寫實現細節相剝離，只關心數據讀寫內容即可。整個數據庫包含14張表結構，對表數據的操作全部封裝在iParkDB類中。所有調用該模塊的上層系統，都需要在應用程序初始化里邊添加COM初始化函數AfxOleInit()，以創建ADO連接。所有數據庫查詢都采用無緩沖模式，查詢結果以數據集的形式返回給上層調用系統后，立即關閉查詢結果集。同時，數據庫子系統作為底層接口，可能會被不同的線程同時訪問調用，因此在設計實現時增加了并發訪問機制來避免不同線程之間的干擾。具體的數據庫設計如圖4所示。

圖4 智慧泊車調度系統數據庫設計

1.4 通訊模塊

通訊模塊即消息子系統，該模塊為各軟件系統間的協同工作提供消息傳遞服務，將各軟件系統要傳遞的邏輯消息(數據內容)轉換物理消息(字節流)，通過socket接口進行傳遞。當用戶在人機交互一體機上按下存車或取車操作時，服務器端需要快速做出響應，因此服務器端與人機交互一體機(存/取車一體機)之間的消息傳遞采用UDP協議，允許網絡存在丟包現象。上層調用系統在設計實現時，對于超時未收到消息回復的情況，進行消息重發處理。消息傳遞流程如圖5所示。

圖5 消息子系統傳遞流程圖

由于停車位、充電位等資源為共享資源，在程序設計中需要為這些共享資源設置臨界區保護。

1.5 前端監控模塊

前端監控模塊實時監控停車場及各AGV狀態，便于管理人員掌握停車場車位情況和AGV的運行狀態，并在必要的時候進行人工路徑干預。系統初始從數據庫讀取電子地圖數據，畫出電子地圖，與AGV建立連接后，在地圖上實時更新各AGV的狀態。前端監控頁面如圖6所示。

圖6 前端監控頁面

1.6 后臺管理模塊

后臺管理模塊提供用戶管理、AGV資料管理、固定客戶管理、歷史數據管理、財務管理、系統參數配置等信息的增刪改查操作。該模塊與系統的其他模塊沒有交互，只是對數據庫中的數據進行管理和操作。當后臺管理軟件對數據庫中的數據進行讀操作時，數據從數據庫流向該模塊；當后臺管理軟件對數據庫中的數據進行寫操作時，數據從后臺管理軟件流向數據庫。

1.7 任務調度模塊

任務調度模塊的主要功能是當接收到存/取一體機發送過來的停車/取車消息時，生成相應的停車/取車任務。在本調度系統中，對于空閑車位和空閑AGV的分配原則為：優先選用距離入口最近的停車位，對于有雙排車位的情況，優先選擇外側停車位；分配AGV時，優先選擇距離停車位最近的空閑AGV。存/取車交互流程如圖7所示。

圖7 存/取車流程圖

1.8 行車引導模塊

行車引導模塊的主要功能是將路徑規劃算法計算出來的路徑轉化為AGV小車可識別的動作指令，完成AGV行車引導。調度系統將規劃好的整條路徑發送給AGV，如在AGV行駛過程中調度系統檢測到可能發生碰撞，則需要單獨向AGV發送禁行/通行指令。

AGV在行進過程中，遵循右側通行規則。車輛在路口轉彎或者出入庫時，會占用對向車道，此時后續車輛或對向車輛需等待避讓。同時，調度系統根據AGV車輛實時上報的狀態位姿信息，判斷AGV小車之間是否為爭奪同一資源出現死鎖現象，如出現死鎖，則需要鎖定系統進行解鎖。死鎖嚴重的情況下，則需要為AGV重新進行路徑規劃。

AGV小車采用Trio MC405控制器，調度系統與控制器之間通訊采用標準ModbusTCP協議，該協議穩定可靠，數據傳輸效率高。

2 系統路徑規劃問題分析

2.1 AGV系統的路徑規劃問題

AGV系統的路徑規劃問題研究的是在指定的AGV運行環境中按照某一性能指標搜索一條從起始點到目標點的最優或近似最優的路徑[3]，同時保證在行進過程中AGV之間無碰撞，無死鎖情況出現。

AGV的行走路徑規劃主要是通過地圖數據、任務參數和路徑規劃算法，獲得實際運行中最優的運行路徑，解決運行中可能出現的多個AGV路徑沖突、路徑重疊、時間浪費等問題。

AGV的路徑規劃問題，按照路徑規劃的目標范圍可分為全局路徑規劃和局部路徑規劃，按照地圖環境是否隨時間變化可分為靜態環境路徑規劃和動態環境路徑規劃，按照運行AGV的數量可分為單AGV路徑規劃和多AGV路徑規劃。在本調度系統中，各AGV在固定的區域內運行，所以本項目在路徑規劃目標范圍上屬于全局路徑規劃。地圖環境方面，由于目標運行環境是固定的停車場環境，故屬于靜態環境路徑規劃。在AGV運行數量上，屬于多AGV的路徑規劃。此外，當接收到新的停車/取車任務時，系統需要依據現有任務進展情況對新任務進行路徑計算，所以亦是動態路徑規劃問題。

綜上所述，智慧泊車調度系統的路徑規劃模塊主要解決的是全局規劃、靜態環境中的多AGV動態路徑規劃問題。在進行多AGV(多任務)路徑規劃時，除了獲得多個AGV的最短路徑之外，還需要避免沖突、優化總體運行時間，以最大化提高系統效率。

2.2 電子地圖建模

在AGV系統中，獲取系統環境信息是路徑規劃的先決條件[4]。路徑規劃問題的基礎，首先是將待搜尋最短路勁的物理空間轉化成計算機可以識別的電子地圖，以便能夠將位置數據傳遞給路徑規劃算法進行分析處理。電子地圖是真實環境在計算機中的展現，其中包含了各種道路節點、充電位、停車位、維修位等相關信息，這些信息是定位導航和路徑規劃的根本。對于已知的全局環境，AGV運行所需要的路徑信息按照特定的方式存儲在電子地圖中，AGV通過本身安裝的各種傳感器得到相關信息，通過定位系統將自身的位姿信息和全局坐標系匹配從而得到在電子地圖中的實時位置。

在本調度系統中，采用基于圖論的方法來進行電子地圖建模。在電子地圖中，環境中的關鍵位置(如停車位、充電位、車庫出入口等)使用節點來進行表示，節點之間的可行連線表示AGV可行走路徑[5]，即道路。基于該模型進行路徑規劃時，AGV的運行路線通過有序的節點集來表示，而節點之間的順序則指明了AGV的運行方向。

結合道路容納車輛的數量，路徑的行駛車道主要分為三種形式：單車道單向行駛、雙車道雙向行駛、單車道雙向行駛[6]。在本系統中，道路設計成雙車道雙向行駛模式，即兩個節點之間的路徑表示兩條行駛方向相反的平行車道。結構化的地圖由節點和邊組成，用G=(V,E,W)來表示，其中V表示所有節點的集合，E表示所有邊的集合，W表示邊的權值，即節點之間的距離，該值是進行路徑規劃時的關鍵數值。結構化地圖模型如圖8所示，圖例所示為雙車道雙向行駛。

圖8 結構化地圖模型

2.3 路徑規劃算法——改進A*算法

路徑規劃算法維護一個經過計算的運行中任務路徑數據，當獲得新的任務之后，進行一定的數據預處理，然后提交給核心的路徑規劃算法進行最短路徑計算。路徑規劃算法將新任務的數據與運行中任務的數據作為參數，加上任務優先級、交通規則定義、運行時間優化等，計算得出新的運行中任務路徑數據。該模塊的具體處理流程如圖9所示。

圖9 路徑規劃模塊處理流程圖

在本調度系統中，選用A*算法作為基礎算法來計算任務的最短路徑。A*算法是一種啟發式搜索算法，通過建立合適的估價函數，來獲得有利于問題求解的啟發信息，從而利用這些啟發信息區搜素最優路徑。該算法不用遍歷整個地圖，因此時間復雜度低。本調度系統地圖環境固定，且各個節點都有準確的坐標參數，所以可以方便的建立A*算法的估價函數。

A*算法的評價函數可以表示為：

f(x)=g(x)+h(x)

(1)

其中:g(x)表示起始點s到當前節點x的最短路徑代價函數值，h(x)表示當前節點x到目標節點t的最短路徑代價的啟發函數值，f(x)表示起始點s經過當前節點x到目標節點t的評價函數。在本調度系統開發實現中，使用兩節點之間的歐式距離來計算g(x)和h(x)。

除上述代價評估函數外，A*算法在代碼實現過程中需要用到open表和close表這兩個數據結構，其中open表中存放當前考慮的點及其周邊需要添加進來作為可能的路徑上的點，close表存放所有不需要再次檢查的節點。A*算法總結如下：

1)把起點加入open表。

2)重復如下過程：

(1)遍歷open表，查找F值最小的節點，把它作為當前要處理的節點，然后移到close表中；

(2)對當前節點的8個鄰居進行檢查，如果他是不可抵達的或者已經在close表中，忽略它，否則做如下操作：

①如果它不在open表中，把它加入open表，并且把當前節點設置為其父節點；

②如果它已經在open表中，檢查這條路徑(即經由當前節點到達該節點)是否更近，如果更近，把當前節點設置為其父節點，并重新計算它的G值和F值。如果open表是按照F值進行排序的，則改變后可能需要重新排序。

(3)遇到下面情況停止搜索：

①目標節點已經加入到open表中，此時路徑已經找到；

②查找目標節點失敗，并且open表為NULL，此時沒有路徑。

3)從目標節點開始沿著父節點進行追溯，直至起點，形成路徑。

因道路設計為雙車道雙向行駛模式，故AGV在轉彎時，需要提前橫移到道路中央，這就需要額外消耗時間，降低系統的運行效率，故當起點和終點一定的情況下，規劃的路徑AGV轉彎越少越好。傳統的A*算法在計算g(x)和h(x)并沒有考慮轉彎消耗，無法在兩種路徑間選取轉彎次數更少的路徑。針對此問題，對A*算法進行了改進，如規劃的路徑中AGV需要轉彎，則轉彎點的g(x)會增加轉彎代價。通過引入轉彎因子，改進后的A*算法可根據實際應用來調節轉彎對路徑規劃的影響，在不降低搜索效率的前提下，使得搜索出來的路徑轉彎次數最少。改進后的A*算法運行流程如圖10所示。

圖10 改進A*算法算法流程圖

2.4 沖突檢測

沖突和死鎖檢測是多AGV路徑規劃面臨和解決的一個重要問題。AGV在行走過程中，要實時檢測是否與其他AGV存在沖突，即空間沖突和時間沖突。所謂存在空間沖突，即當前AGV的運行路徑與其他AGV的運行路徑存在重疊；判斷是否存在時間沖突則需要檢測AGV在重疊路徑上是否存在時間上的重疊。如果空間沖突和時間沖突同時發生，則說明不同AGV之間會為爭奪同一路徑資源而產生死鎖。

在本調度系統中，為了解決AGV之間的沖突問題，對路徑對應任務分配了優先級順序，同時為每一個任務中的AGV關聯本體區域、已占用區域和擬占用區域，其中本體區域指AGV(帶托盤)所在區域；已占用區域指AGV本體進入轉彎區，則將轉彎區設為占用區；擬占用區域指AGV行進方向的若干米，設為擬占用區，若此擬占用區進入轉彎區，則將轉彎區也設為擬占用。若兩個AGV存在區域重疊，則區域優先級低的AGV要等待避讓。若沖突區域的優先級相同，則根據任務優先級，讓優先級低的任務避讓等待。距離終點越近，相應任務的優先級越高。

2.5 開發與運行環境

整個調度系統開發基于MS Windows7 Professional操作系統，開發語言為C++，采用C/S架構，IDE環境為VS2013或以上版本，數據庫平臺為SQL Server 2008。開發過程中運用了面向對象、模塊化以及多線程編程技術。

人機交互終端為一體機，集成打印與掃描功能；前端監控終端、后臺管理終端選用普通PC機。

2.6 實驗結果與分析

調度系統功能驗證采用雙向兩車道兩出入口，3臺AGV 、8個托盤、30個車位，AGV的定位精準度誤差控制在5 mm以內，行駛速度最高可達1.5 m/s。經過將近6個月的調試，平均存取車時間不超過90 s，基本驗證了調度系統各模塊功能設計的可行性。

受到現實條件的限制，不能進行真實的多AGV調度測試，利用多線程技術，編寫了仿真驗證程序，可同時驗證90臺AGV同時下線的情況，證明路徑規劃算法是可行的。但由于仿真狀態下為理想狀態，在實際調試時，路徑規劃算法還需根據具體應用環境進行完善。

3 單車獨占模式(單車道)與雙車共享模式(雙車道)比較

從經濟效益方面進行比較。單車獨占模式僅需要占用較少的場地面積進行道路鋪設，而雙車共享模式需要占用更多的場地面積以提供更寬的運行道路以滿足運行安全性。經實際停車位設計計算發現，單車獨占模式場地的有效利用率高出雙車獨占模式5%左右，并且單層面積越大，單車獨占模式的場地有效利用率提高越顯著。

從路徑規劃系統的性能方面進行比較。單車獨占模式僅提供較少的轉彎節點，且行車主路線、支線的總體節點較少，便于路徑規劃系統進行快速計算，同時路徑規劃算法的準確性也會更高，系統運行速度和穩定性較好。雙車共享模式中，道路中具有兩條并行行車主路線，在路徑規劃時會產生更多的可用路徑，同時轉彎節點并不在行車主路線之上，在進行路徑規劃時需要增加AGV平移運動；另一方面，雖然每個道路具有兩條行車主路線，但是一旦AGV在道路中間執行轉彎任務時，會同時阻塞兩條主路線，增加阻塞節點，轉彎完成后阻塞節點又立即消失，這種動態干擾增大了路徑規劃難度。

從系統運行效率方面進行比較。單車獨占模式在運行中可在主路線的轉彎點直接轉彎，節約了額外動作時間，但是多臺AGV進行會車避讓時，需要優先級較低的AGV進行額外移動(如提前進入支線)以避讓等待。雙車共享模式在運行中轉彎時需要從行車主路線上移動到轉彎點，增加了額外動作時間，且會同時堵塞兩條主路線(此時的堵塞狀態與單車獨占模式相近)，不過在多個AGV會車時只需要提前進行變道且并行移動，效率較高。兩種模式在運行效率方面的對比結果，需要根據實際運行過程中AGV各個動作的實際執行時間(直行、轉彎、橫移)以及系統的負載進行測算。

4 結束語

隨著企業信息化、自動化的快速發展，智慧物流成為一種必然趨勢，而AGV自動運輸系統正是這種趨勢的典型代表。本文基于正在實施的智能停車項目，對調度系統所涉及的電子地圖建模、路徑規劃算法、數據庫設計、行車引導、避障解鎖等模塊進行了詳細描述，同時提出了一種改進的A*算法，引入轉彎因子，使得在起點和目標點確定的情況下，AGV轉彎次數最少，行走路徑更平滑。多AGV路徑規劃是一個復雜的過程，在實際調試中，路徑規劃算法還需不斷改進和完善。