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

0 引言

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

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

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

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

1 智慧泊車系統(tǒng)總體方案

1.1 智慧泊車系統(tǒng)組成

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

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

圖1 AGV小車的結構架構圖

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

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

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

圖2 智慧泊車系統(tǒng)網(wǎng)絡拓撲圖

1.2 智慧泊車調度系統(tǒng)總體設計

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

圖3 智慧泊車調度系統(tǒng)結構圖

1.3 數(shù)據(jù)庫模塊

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

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

圖4 智慧泊車調度系統(tǒng)數(shù)據(jù)庫設計

1.4 通訊模塊

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

圖5 消息子系統(tǒng)傳遞流程圖

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

1.5 前端監(jiān)控模塊

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

圖6 前端監(jiān)控頁面

1.6 后臺管理模塊

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

1.7 任務調度模塊

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

圖7 存/取車流程圖

1.8 行車引導模塊

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

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

AGV小車采用Trio MC405控制器，調度系統(tǒng)與控制器之間通訊采用標準ModbusTCP協(xié)議，該協(xié)議穩(wěn)定可靠，數(shù)據(jù)傳輸效率高。

2 系統(tǒng)路徑規(guī)劃問題分析

2.1 AGV系統(tǒng)的路徑規(guī)劃問題

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

AGV的行走路徑規(guī)劃主要是通過地圖數(shù)據(jù)、任務參數(shù)和路徑規(guī)劃算法，獲得實際運行中最優(yōu)的運行路徑，解決運行中可能出現(xiàn)的多個AGV路徑?jīng)_突、路徑重疊、時間浪費等問題。

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

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

2.2 電子地圖建模

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

在本調度系統(tǒng)中，采用基于圖論的方法來進行電子地圖建模。在電子地圖中，環(huán)境中的關鍵位置(如停車位、充電位、車庫出入口等)使用節(jié)點來進行表示，節(jié)點之間的可行連線表示AGV可行走路徑[5]，即道路?；谠撃Ｐ瓦M行路徑規(guī)劃時，AGV的運行路線通過有序的節(jié)點集來表示，而節(jié)點之間的順序則指明了AGV的運行方向。

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

圖8 結構化地圖模型

2.3 路徑規(guī)劃算法——改進A*算法

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

圖9 路徑規(guī)劃模塊處理流程圖

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

A*算法的評價函數(shù)可以表示為：

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

(1)

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

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

1)把起點加入open表。

2)重復如下過程：

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

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

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

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

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

①目標節(jié)點已經(jīng)加入到open表中，此時路徑已經(jīng)找到；

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

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

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

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

2.4 沖突檢測

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

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

2.5 開發(fā)與運行環(huán)境

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

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

2.6 實驗結果與分析

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

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

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

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

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

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

4 結束語

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