運輸車輛機器人存取車路徑優化算法研究

陳寧，梁歡歡，孔祥希，胡立渝，韓吉

（南京農業大學工學院，南京 210000）

針對智能停車庫中的運輸車輛機器人AGV，首先根據停車場結構示意圖，對某一時刻停車場實際路網進行抽象，將要求的路徑優化問題轉化為最短路徑問題。與實際問題相結合確定停車場AGV 路徑優化的算法為Dijkstra 算法，最后通過MATLAB 軟件編程算法并進行求解，算出每個空閑車位相對應的最短的存取車路徑及距離總和，提高AGV存取車效率，節省時間。結果證明Dijkstra 算法在AGV 存取車路徑優化中的可行性和實用性。

智能停車庫；運輸車輛機器人；最短路徑；Dijkstra 算法

0 引言

隨著當今社會經濟的快速發展，全國汽車的保有量也在不斷上升。汽車的持有量急劇增長與停車位稀缺的矛盾亟需解決[1]。最直接的解決方法就是建立停車場，但相對應的停車場內部的車位更加擁堵，使得停車變成了候車過程久、停車過程亂、取車過程忙的現象。為了解決這種現象，建立一種高性能的智能化停車場成為一種必然趨勢。當前市面上應運而生了很多種類的智能停車庫，例如智能立體停車庫、半自動立體停車庫以及基于運輸車輛機器人的智能化停車庫等。基于AGV 的智能停車庫與別的類型停車庫相比，具有占地面積小、車位利用率高、性價比及可靠性高等特點[2]。在實際中調查中我們發現運輸車輛機器人AGV 在存取車路徑的選擇上還存在問題，大部分是依靠人工在后臺控制，并不能智能選擇最優路徑使得存取車路徑最短而減少工作耗時。解決運輸車輛機器人存取車路徑優化算法問題，是發展AGV 智能車庫的基礎。針對路徑優化問題，隨著算法的不斷發展，Dijkstra 算法、A*算法、遺傳算法以及蟻群算法等也被廣泛用于解決各領域路徑規劃問題[3]。

在分析了智能停車場的系統組成和運輸車輛機器人的工作原理后，本文著重研究運輸機器人的路徑優化問題，該問題的優化使得運輸機器人在較短的時間內走最短的存取雙向路線，即AGV 將待取車從取車車位運輸到出入口，再將待存車從出入口運輸到最近空車位。此優化方法將為我們節省更多的存取車時間，提高智能停車場的運行效率，減少運輸車輛機器人的耗能。針對智能停車庫中AGV 存取車路徑優化問題，建立模型車車場模型，本文研究了幾種算法后進行比較，最后選取較為適合的算法作為本文的主要研究算法，編寫程序進行求解，從而得出優化后的該選擇的路徑。

1 AGV在智能停車場的應用

本文所涉及的AGV 智能停車場系統主要包括機械系統、管理系統、監控系統及其他系統等如圖1所示。

智能停車場中，在正常的電磁導引系統環境和車載通訊系統環境下，AGV 處于待機狀態。當有車輛要求停車時，地面管理調度系統通過機載通訊系統向運輸車輛機器人下達作業指令，通過上位機系統比對停車場內車位、車輛停放信息，然后智能停車場管理系統的主控計算機通過算法可迅速得到最佳車位并進行路徑的規劃，車載計算器接受其他系統獲取到的環境信息和路徑信息以及上位機系統控制信號所規劃的路徑。在接受到運輸任務后，AGV 開始執行任務，驅動系統驅動AGV 運輸車輛實現AGV 的沿著所規劃的路徑進行運行，將車運送到所指定的位置。

圖1 智能停車場系統結構圖

運輸車輛機器人結構圖如圖2 所示。

圖2 停車AGV結構圖

2 問題描述與建模

2.1 問題描述

智能停車場系統通過檢測裝置來獲取車庫中停車位的占用情況，根據AGV 當前狀態，快速地為AGV 找到一個最佳車位并規劃出從當前車位到該車位的最優路徑，保證AGV 在較短時間內完成車輛存取車任務，以便提高運輸車輛機器人的運輸效率。

本文假定：①停車場的出口與入口在同一位置；②運輸車輛機器人完成存車命令后將在該車位處待機，等待下一命令；③行車道寬度滿足AGV 最大轉彎半徑，道路寬度需保證單個AGV 正常行駛；④忽略AGV 實際大小，把AGV 和停車位視為質點。

2.2 停車場抽象結構模型

假設停車位寬為3 米，長為6 米，行車道寬度為6米，這里將智能停車場中位置信息，例如空車位、交叉口、出入口等抽象為節點[4]。智能停車場入（出）口為S（1），交叉路口為2-10，當前空閑車位為P1-P10，表示可以用來存放車輛，其余的車位均已被占用。編號標記如圖3 所示。

圖3 停車場結構示意圖

以O 點為原點建立坐標系，把每個車位看作一個質點，每個質點的坐標為該車位中心點的坐標[5]，每個交叉路口點的坐標為該交叉路口中心點的坐標，圖中的入口、出口、有效停車位以及交叉路口的坐標就可以被確定如表1 所示。下一步的研究工作將以此模型為基礎，研究運輸車輛機器人最優路徑規劃算法問題。

表1 坐標點

2.3 最佳車位模型

根據上述可知，本文所研究的尋找最優路徑的問題就是運輸車輛機器人把待取車運送到出入口后，再將待存車運進停車場時，對余下的空車位按照設定的計算規則進行分析處理，得到一個最合適的停車位，并找到該車位的最短路徑。若某個空閑車位為Pi（i=1，2，...，n），運輸車輛機器人把某一固定車位的待取車運送到出入口的最短路徑為path（P，s），運輸機器人把待存車送到某空閑車位對應的入場過程的最短路徑為path（s，Pi）。

則運輸車輛機器人存取車過程對應的整個最短路徑長度為：

則最佳車位所對應的最短路徑的長度可表示為：

2.4 路網的構建

按照圖論[6，7]的構圖方法，某一時刻停車場路網是靜態的，結合上述停車場的結構示意圖和停車場內空閑車位的信息，可以把圖示停車場結構示意圖的構建成為一個帶權的有向圖，AGV 在停車場靜態路網里的存取車路徑優化問題就可轉換成求解帶權圖中任意指定的節點間到其他點的最短路徑問題。

停車場內路網有向圖可以用如下來表示：

圖中停車場內的出入口（S）、行車道交叉路口、空閑車位可以構成一個頂點集V，每一條路徑對應一條弧E，連接兩頂點之間的路徑長度看作為弧的權值，用W 表示，如果兩個頂點之間沒有連通的道路，那么權值可以用∞表示，所轉化成為的賦權圖如圖4 所示。

3 Dijkstra算法

有很多算法都可以用來求出在某個賦權有向圖中的任意兩個結點之間的最短路徑，如蟻群算法[8]、遺傳算法、Dijkstra[9]算法等。由于本文研究的是應用在停車場中最短路徑問題，所以賦權圖中的各條邊的權值均為非負，相對于其他算法而言，Dijkstra 算法更適用于此場景下最短路徑的問題研究。Dijkstra 算法由荷蘭E.W.Dijkstra 提出的一個典型的單源最短路徑算法，用于計算賦權圖上一個節點到其他所有節點的最短路徑。算法從起始點開逐個搜索下一鄰接點，直到搜索到終點為止。Dijkstra 是很具有代表性、經典的最短路徑算法，并且在實際中應用廣泛。1969年Zhan 等使用實際交通網絡測試了15 種不同的最短路徑算法，結果表明，Dijkstra 算法計算某一點到其他點的最短路徑最快捷[10]。

圖4 帶權有向圖

Dijkstra 算法思想為：設G=（V，E，W）是一個賦權有向圖，把有向圖中頂點集合V 分為兩組，第一組我們就稱它為A 集合，代表已經求出源點到該點的最短路的點的集合，開始時A 集合中只包含源點v0。另一個我們稱為B 集合，代表未求出源點到該點的最短路徑的點的集合。找出點集B 中最短路徑的頂點并將其加入到點集A 中，接著更新B 中的頂點及對應的最短路徑按，不斷進行以下操作，按照最短路徑長度遞增的順序逐漸把B 集合中的點加入到A 集合中，直到點集B中的點全部轉移到點集A 中。

算法步驟如下：

步驟1：初始化行駛的最短路徑集合A，最開始時集合A 只包含始點即出入口設為v0，除v0之外的其他頂點都在B 集合中。即A={v0}，B={其他頂點}；

步驟2：從集合B 中選取一個距離v0最小的頂點再將vk加入到集合A 中（該選定的距離就是v0到vk的最短路徑長度）。

步驟3：然后對B 中點到源點的距離進行一次更新，就是以vk為中間節點，修改A 中各頂點到源點的距離。如果經過vk，可以使v0到某個未訪問過的頂點距離變小，則修正該最小距離。

步驟4：重復步驟2 和3 直到所有頂點都包含在集合A 中。

4 MATLAB編程求解

根據上述算法步驟進行編程，在MATLAB 環境下實現Dijkstra 算法，驗證算法的合理性和正確性。以圖所示的停車場為實驗場景，假設H15 號（H 區從左往右第15 個車位）有一輛車需要取出，向AGV 運輸管理系統發送任務請求，運輸車輛機器人把H15 號的車運送到出入口，再將出入口的待存車運送到某一空車位。管理系統在收到任務后進行路徑的規劃，并將規劃的路徑下發給對應AGV，從H15 到達出入口路徑如圖5所示，經過路徑即為：H15---9---6---3---2---S（1），最短路徑為：97.5。

圖5 H15到達S的最短路徑及長度

采用本算法進行實驗可以求出AGV 從H15 到達出入口，再從出入口把待存車到達所有空閑車位的最短路徑，如表2 所示。

表2 最短路徑及總長

通過MATLAB 算法編程可以求解出每個空閑車位相對應的最短的存取車路徑及距離總和，驗證了算法在智能停車場環境中的可行性和準確性。這樣，管理系統在接受到運輸任務后，計算器運行編程好的Dijkstra 算法求出空閑車位中的最佳車位，指令AGV 的沿著所規劃的路徑進行運行，將車運快速準確地送到所指定的位置。實現了運輸車輛機器人存取車的高效有序，具有十分重要的意義。

5 結語

根據目前的現狀，本文根據智能車庫中運輸車輛機器人存取車路徑所存在的不足進行研究，對其路徑規劃算法展開研究。基于當前社會智能交通的發展和停車場的實際情況，建立了停車場結構模型，分析了停車場路網，并將路網抽象成帶權有向圖，將所求最優路徑問題轉化為了最短路徑問題。在對幾種最短算法分析比較后，確定了使用Dijkstra 算法進行課題的研究。通過Dijkstra 算法的理論知識和MATLAB 求解，幫助運輸車輛機器人找到了最佳車位，求出了各個車位分別對應的最短路徑及距離，使得運輸車輛機器人的系統得到優化，極大地縮短了AGV 的工作時間，改善了停車場內部的存取車運行效率，節約耗能和成本。