基于改進沖突搜索的智能車庫多AGV路徑規劃*

任明輝，梁 軍，陳 龍，張 春，王 云

（1.江蘇大學汽車工程研究院，鎮江 212013；2.寶勝系統集成科技股份有限公司，揚州 225800）

前言

近年來，基于自主引導車（automated guided vehicle，AGV）的智能車庫（robot-based intelligent garage，RIG）成為智能交通與智慧導航領域研究熱點。RIG 通過多AGV 搬運以實現車輛的存取過程，用戶僅需在RIG 擺渡區進行車輛交換［1］，提升了車輛停車便捷性，減少了停車場內部由于人為操作導致的沖突問題，提升車輛存取效率和車位供給量，是緩解城市“停車難”問題理想的停車方式。

RIG 兼具高效性和安全性的特點，通過RIG 停車管理系統為AGV 指派停車任務，并規劃無沖突路徑［2］，其中包含的多AGV 路徑規劃是一項至關重要的技術。目前，多AGV路徑規劃常用時間窗［3］、交通規則［4］等方式解決多AGV 存在的沖突問題，能夠滿足小規模AGV 系統的無沖突路徑規劃問題，但是無法滿足AGV規模逐漸龐大的智能車庫系統。

目前研究學者將多AGV 系統建模為多智能體路徑搜索（multi-agent path finding，MAPF）問題，將AGV 看作智能體來求解，在已知環境中為一組智能體搜尋無沖突路徑，同時最小化AGV 運行時間總和［5-6］。CBS（conflict-based search algorithm）算法是一種領先的兩級搜索算法，用于優化求解MAPF 問題，其核心思想是獨立地為每個智能體規劃一條路徑，然后通過分支解決智能體之間的沖突［7］。Boyarski 等［8］將增強、元代理和繞過沖突措施等改進的研究成果引入到CBS 算法中，能夠減少CBS 的運行時間，但是并未考慮到任務執行優先級和AGV 的實際沖突類型對CBS 的影響。Okoso 等［9］將CBS 算法應用到具有任務執行優先級的自主代客泊車系統，然而考慮的沖突類型和沖突解決措施相對簡單。RIG 屬于AGV 代客泊車系統，需要AGV 對車輛進行搬運，現有研究很少考慮到任務分配過程對多AGV路徑規劃的影響，且提出的沖突解決策略并不適用RIG環境。

針對具有任務執行優先級的RIG 系統，在分析RIG 實際沖突特點的基礎上，引入基于備用區域搜索策略和旁路規劃策略協同的沖突消解方法，提出了一種基于改進CBS 的路徑規劃算法，為RIG 規劃多AGV無沖突路徑。

1 RIG停車環境分析

1.1 RIG沖突類型分析

如圖1 所示，應用平行式車位布局的RIG 的車位布局方式與AGV 的運行方式息息相關，AGV 通常采用麥克納姆輪底盤，可以全向移動，能夠較為容易實現平行停車。在多AGV 搬運車輛任務過程中，AGV 間的沖突可分為對向沖突、交叉口沖突、停車沖突和跟隨沖突4 種類型。對向沖突通常出現在兩輛AGV相向通行同一AGV通道的情況，如圖2（a）所示，它是一種典型的死鎖現象，要求沖突的一方退出當前路徑才能解決沖突，而不能通過等待操作解決。鑒于AGV 運行特點，RIG 交叉口位置在同一時間步長內僅允許一輛車通行，當多輛AGV 同時通行交叉口時，交叉口沖突即會產生，這是RIG 中較為常見的沖突類型，如圖2（b）所示。在AGV 執行存取車任務進入或離開停位時，會占用AGV 通道并阻礙其他AGV 的正常通行，便會產生停車沖突，如圖2（c）所示。倘若一個AGV 占用另一個AGV 在上一時間步占用的節點，兩輛AGV 便會發生沖突，記為跟隨沖突，如圖2（d）所示。

圖1 RIG典型場景

圖2 多AGV典型沖突類型

1.2 RIG路徑規劃問題描述

面向RIG 的多AGV 路徑規劃可以描述為多智能體路徑搜索MAPF 問題，由無向圖G（V，E）（其中V表示頂點集，E表示邊集），一組負責執行停車任務的m個AGV 集A={a1，a2，…，am}以及一組待執行的實時停車任務T={τ1，τ2，…，τn}所構成。當ai被指派完成任務τk時，從初始停車位置oi出發，然后前往取車位置bk搬運車輛，最后達到車輛的目標停放位置gk。在RIG 中，AGV 的最大裝載車輛數為1，且每個任務僅由一輛AGV 執行。當停車任務數量大于AGV 數量時，多于AGV 數量的任務只能在RIG 外等待，并不會影響RIG 內的AGV 運行情況，故假定m=n。AGV 運動機構通常選擇麥克納姆輪機構，可實現全向移動，有前進（Ad）、后退（Re）、向左橫移（Lt）、向右橫移（Rt）以及原地等待（Wp）等操作，且在每個時間步長內，AGV 均執行移動或等待操作。MAPF 的目標就是以最小化AGV 運行時間總和（sum of costs，SoC）為目標，搜索滿足所有AGV 的無沖突路徑，其目標為尋找最優的集合π*使SoC最?。?0］：

2 RIG多AGV路徑規劃模型

針對RIG 中AGV 的任務執行優先級問題，提出了基于改進沖突搜索的路徑規劃模型（improved conflict-based search with priority，iCBS-pri）。該改進模型主要由任務分配（task allocation，TA）、單AGV 路徑規劃（path planning，PP）、多AGV 沖突檢測與解決（conflict detection and resolution，CDAR）3 個模塊組成，最終生成多AGV無沖突路徑集合π*，如圖3 所示。TA 將未分配任務分配給AGV，本文所提的TA 模塊的任務執行優先級不受任務分配過程中任務與AGV 的距離影響；PP 模塊是iCBS-pri下層搜索算法的主要內容，所提PP 模塊通過設置直線懲罰函數，減少路徑的轉彎次數對AGV 運行時間的影響，以提高AGV 任務完成效率，最小化AGV 的SoC為目標；CDAR模塊包括沖突檢測（conflict detection，CD）子模塊和沖突解決（conflict resolution，CR）子模塊。CD 子模塊根據RIG 實際情況，通過檢測參與沖突的AGV 運動狀態以此確定實際沖突類型；本文改進的CR 子模塊針對CD 子模塊檢測出的沖突類型，制定基于備用區域（spare zone，SZ）和旁路規劃（bypass，BP）的沖突解決策略，以規劃多AGV 無沖突路線。

2.1 TA模塊

TA 在MAPF 問題中起著重要作用，它涉及如何在任務集T中的待分配任務分配給AGV集A中AGV。TA 根據AGV 的初始位置和待分配任務的初始位置間的距離進行分配，以減少AGV的無效運行路徑，提升RIG的整體運行效率。同時，每個未分配的任務都與RIG 中任務執行優先級相關聯，任務執行優先級不受任務分配過程中任務與AGV 的距離影響，能夠以優先級排序的形式處理AGV間的沖突現象。

為提升停車場收益，停車會員收費是一項有效的措施［11］。在RIG 中，停車會員需要額外的費用，會員用戶停車任務也應具有更高的執行優先級。由于RIG 任務存在執行優先級，在CBS 設計時應充分考慮到優先級對整體規劃的影響，且在任務分配時不能影響任務原有的執行優先級。任務優先級pri={p1，p2，…，pn}是AGV 任務集T中任務執行次序的集合，如果，任務τk的優先級就比高［12］。通過給定任務優先級的集合pri，以piTi計算沖突過程中的時間成本消耗。具有優先級的MAPF 問題的目標就是尋找集合π*使SoC最?。?/p>

以AGV 的初始位置oi與未分配任務的初始位置bk間的距離為評定標準，將未分配任務分配至距離該任務最近的AGV。由于AGV 的數量有限，當任務的數量多于AGV的數量時，超出AGV數量的任務將等待第二次分配，并根據用戶類型賦予優先級系數。如下的TA算法闡述了任務分配的具體流程。

2.2 PP模塊

在RIG 中，將任務集T中的所有任務分配給AGV 集中的AGV 后，PP 模塊通過規劃無沖突路徑導航到指定位置，完成車輛存取任務。在車輛存取過程中，PP 規劃的無沖突路徑通常由兩部分組成：任務搬運路徑(oi→bk)和任務執行路徑(bk→gk)。由于AGV執行優先級由搬運任務決定，因此AGV在不同路段上具有的優先級可能有所不同，為簡化PP模塊的算法復雜性，PP 算法規劃每一部分的路徑，通過在改進的TA 算法中添加距離優先原則，AGV通常會繼續完成原先搬運任務。在PP 算法中，對單一AGV規劃最優路徑，而不考慮其他AGV的影響。

傳統A*算法是一種以此選取估計成本最小的節點作為下一步的搜索節點，接著重復此操作直至尋找到目標節點，能夠尋找到MAPF 問題的最優解，但是實際規劃的路徑往往會出現多個拐點［13］。在圖論中，拐點的個數并不會影響路徑的最優性，而在實際RIG環境中，AGV搬運車輛完成停車任務，屬于重載AGV，當AGV 遇到拐點時，AGV 會調節麥克納姆輪的速度在原地旋轉進行方向調整，以此完成轉彎動作，會耗費大量時間。因此在實際規劃AGV 路徑時，既要確保路徑最短，又要盡可能選擇拐點最少的路徑。

傳統A*算法的核心是通過指定的啟發函數對未遍歷的節點進行查詢，縮小搜索范圍，提升搜索速度，具體表達如下：

式中：f(n)表示從初始節點到目標節點的最低成本估計；g(n)為由初始節點到當前節點的實際成本；h(n)為當前節點到目標節點的估計成本，h(n)也就是啟發函數。由于RIG 環境較為規整，且AGV 僅在x軸或y軸方向行駛，為使規劃出的路徑最短，同時盡可能選擇拐點最少的路徑，因此選擇曼哈頓距離作為啟發函數，并在啟發式函數中加入懲罰函數o(n)，通過計算父節點和子節點的直線度決定懲罰函數值。

本文在選擇曼哈頓距離作為啟發函數，并在啟發式函數中加入懲罰函數o(n)的基礎上提出改進后的A*算法表達如下：

2.3 CDAR模塊

CDAR 模塊需要對各AGV 規劃路徑，各路徑之間難免存在沖突，針對此問題CDAR 模塊設計了CD子模塊和CR 子模塊來消解路徑沖突，CD 子模塊根據RIG 實際情況，通過檢測參與沖突的AGV 運動狀態以此確定實際沖突類型，CR 子模塊針對CD 子模塊檢測出的沖突類型，制定基于備用區域和旁路規劃的沖突解決策略，以規劃多AGV無沖突路線。

2.3.1 CD子模塊

PP算法為單個AGV規劃路徑，但是路徑間可能存在沖突現象，沖突檢測方法則須正確檢測AGV 間存在的所有沖突現象。在CBS 算法中，通過迭代時間步，分析所有AGV 的位置信息以此檢測沖突現象，主要有邊沖突、點沖突、交換沖突、跟隨沖突和循環沖突5種類型，如圖4所示。

圖4 MAPF問題中存在的主要沖突類型

在RIG 中，多AGV 沖突類型通常為對向沖突、交叉口沖突、停車沖突和跟隨沖突4 種類型，與MAPF 問題中的點沖突、交換沖突和跟隨沖突3種類型對應［14］，循環沖突出現頻率較低，而邊沖突在RIG中幾乎不會出現，因此通過檢測MAPF 中的沖突類型即可確定RIG 中的沖突現象。πi(t)、πj(t)分別表示ai和aj經過t個時間步長后的位置，并通過πi(t)、πj(t)來描述MAPF問題中存在的主要沖突類型。

（a）邊沖突：ai和aj在執行各自的搬運任務時，兩輛AGV 在同一時間步以相同的方向通行同一條邊(A，B)?E，可表示為πi(t)=πj(t) 且πi(t+1)=πj(t+1)，如圖4（a）所示。

（b）點沖突：ai和aj根據規劃路徑，兩輛AGV 在同一時間步占據同一個節點B?V，可表示為πi(t+1)=πj(t+1)，如圖4（b）所示。

（c）交換沖突：ai和aj按照既定的路徑，在同一時間步以相反的方向通行同一條邊(A，B)?E，并實現相互交換位置的效果，可表示為πi(t)=πj(t+1)且πi(t+1)=πj(t)，如圖4（c）所示。

（d）跟隨沖突：當ai計劃占用aj在上一個時間步占用的節點B?V，可表示為πi(t+1)=πj(t)，如圖4（d）所示。

（e）循環沖突：一組AGV 在同一時間步內，每個AGV 移動到之前被另一個AGV 占用的節點，形成一個“旋轉循環”的模式，可表示為πi(t+1)=πi+1(t)，πi+1(t+1)=πi+2(t)，…，πj-1(t+1)=πj(t) 且πj(t+1)=πi(t)，如圖4（e）所示。

2.3.2 CR子模塊

CR 子模塊是對檢測的沖突制定一組約束(N.constraints)，以成本(N.cost)最小化為目標，為所有AGV 規劃一組無沖突路徑(N.solution)，是CBS 上層搜索算法的關鍵部分（N表示約束樹上的節點）。CBS 上層搜索算法在約束樹(constraint tree，CT)上執行最佳的搜索策略，通過生成限制AGV 的約束集來迭代解決沖突現象。從只有一個約束集為空的初始根節點開始，調用CBS 下層搜索找到N.solution，下層搜索評估N.cost最低的節點，然后選擇最低的N.cost擴展CT 節點，然后CBS 下層搜索會選擇擴展的節點并在N.solution中識別一組沖突N.constraints。如果N.constraints為空，則CBS終止并返回N.solution，否則會隨機選擇一個要解決的沖突，根據沖突的類型施加約束，并添加到N.constraints中，同時CBS 下層搜索會重新規劃N.solution中的路徑以適應新添加的約束。以圖5為例，a1和a2搬運具有不同優先級的任務，調用下層路徑規劃算法得到兩條路徑，在A 點存在點沖突C=，通過拆分節點A以生成兩個子節點，每個節點均繼承A點的約束集，通過為每個節點添加約束a1或a2在初始位置等待并計算A.cost，可以獲得A.solution，其沖突解決措施為a1在初始位置等待1個時間步長。

圖5 基于CBS的沖突解決策略

在RIG中，所有車輛均需要AGV搬運，且AGV將車輛搬運至指定車位后立即返回指定的停放位置，故AGV有搬運狀態和非搬運狀態。由于路徑規劃算法是分段規劃，可以通過判斷AGV 的初始位置oi和須執行任務的初始位置bk間的距離來實現，即oi=bk時，AGV處于搬運狀態，設為hi=1，否則hi=0。

面對AGV 間的沖突，通常辦法是約束其中一輛AGV 使其等待，以此來實現沖突解決的目的。然而，對向沖突和循環沖突會使AGV 陷入死鎖現象，無法通過等待措施解決該類沖突現象，此時約束其中一輛AGV 退出當前路徑，本文提出的沖突解決措施主要有備用區域搜索(SZ)和旁路規劃(BP)［15］兩種策略。

SZ 策略通過為AGV 劃分周邊空閑區域作為避障區域，以實現沖突解決的目的，僅適用于兩輛AGV 沖突的類型［15-16］，也是RIG 中最為普遍的沖突類型。由RIG的布局特點可知，對于搬運狀態AGV，附近空閑車位可以作為AGV 的備用區域，而對于非搬運狀態AGV，所有車位可作為備用區域。然而，如何規劃備用區域是一個非常關鍵的問題。AGV在進入備用區域時須執行轉彎操作，根據沖突節點出現的時間步，提前為沖突AGV 劃分備用區域，常被設置為車位區域。如下SZ 算法闡述了備用區域搜索策略的具體流程。

BP 策略［17］是通過規劃其中一個AGV 的路徑，以繞過沖突減少CBS 搜索樹的節點數量。由于對AGV 路徑再規劃，RIG 中所有已知路徑均會受到影響，沖突節點的總數量(Number of Conflict，N.NC)可能會增加，會造成時間步長的顯著增加。相較于原始路徑πi，BP規劃出的新路徑π，i不能增加新的沖突節點，即N.NC(π，i) ≤N.NC(πi)，且滿足約束N.constraints。從保持路徑最優性的角度來看，在MAPF 問題中必須規劃一條有效的旁路，使SoC 最小。當處理節點N上的沖突C時，BP 通過以優先規劃N.NC最小的方式遍歷節點N的所有子節點ST(N)，即N′∈ST(N)且N.NC(π，i) ≤N.NC(πi)，然后判斷所規劃旁路的有效性（BP 算法第3 行），并生成有效旁路的所有節點的集合P。以兩個AGV參與的沖突為例，倘若第一個子節點判定旁路有效，則BP 不需要添加任何新的節點，也避免了調用其余子節點的底層搜索。

在RIG 環境中，停車沖突類型較為簡單，通常采用等待措施來解決，該方法就不再贅述。跟隨沖突類型是由于領航AGV 的停止而造成的跟隨AGV 與領航AGV 之間的沖突，領航AGV 在時間步長為t時可能存在多個沖突，因此，解決跟隨AGV 時，將跟隨AGV 解決沖突所需的時間步長計入到領航AGV，以盡可能避免跟隨AGV 和領航AGV 的避讓操作。對于對向沖突類型，屬于死鎖，本文針對此種沖突采取SZ 和BP 協同的方式來進行沖突解決，由于SZ 對整體規劃影響較小，在N.cost相同的情況下，優先選擇SZ，具有高優先級的AGV 具有優先通行權，降低了沖突產生的概率，會減少無關的搜索工作算法。本文采用的備用區域搜索策略和旁路規劃策略協同算法能夠提升任務規劃的成功率，由于搜索備用區域和有效旁路在一定程度上能夠幫助算法提前終止搜索或剔除無關搜索工作，從而進一步提升任務規劃成功率。如下iCBS-pri算法闡述了沖突解決的具體流程。

3 實驗驗證

3.1 實驗說明

通過構建典型RIG 場景的20×20 柵格地圖，每個柵格為邊長為1 個單位長度的正方形柵格，黑色和藍色柵格分別為已占用的停車位和空閑停車位，停車位容量為130，如圖6所示，左側為存車區域，右側為取車區域。通過隨機生成AGV 停車位置的方式重復進行實驗100 次，取其平均值作為實驗結果，并設定仿真時間為5 min。假設AGV 和任務數量相等，且設定存車任務和取車任務相等。在RIG 車位區域針對存車任務，當任務數量小于或等于存車區域車位數量時，在存車區域隨機生成任務初始位置，在RIG 的空閑車位區域隨機生成任務目標位置，而當任務數量大于存車區域車位數量時，超出存車區域車位的存車任務數量在下一個時間步隨機出現在存車區域的車位位置，任務目標位置仍隨機生成在RIG 的空閑車位區域。選取分配成功率、路徑長度與轉彎次數、沖突類型檢測準確率和任務執行成功率等作為評價指標。本文實驗是在Windows10 系統下進行，利用MATLAB 2022a 對算法關鍵組件進行仿真驗證，硬件配置為NVIDIA GeForce GTX1060，3 GB 顯存，Intel（R）Core（TM）i5-8400 CPU @2.80 GHz×6，16 GB RAM。

圖6 典型RIG場景柵格地圖

3.2 實驗驗證與結果分析

3.2.1 實驗一：任務分配算法實驗驗證

實驗驗證不同任務數量N的情況下，任務分配算法的有效性。選取任務分配成功率Sta、任務分配一致性Cta和任務平均分配時間Tta作為任務分配算法評價指標，以任務分配成功率Sta和任務分配一致性Cta表示任務分配算法的性能，Sta由成功分配的任務數Ns與任務總數N的比值得到，Cta表征任務的兩階段均由同一AGV執行的概率，由同一AGV執行的任務數量Nτ與任務總數N得到，即

任務分配算法實驗結果如表1 所示。不同任務數量N情況下任務分配成功率Sta總是為100%，因為任務數量和AGV 數量相等，且任務分配算法針對每一個未分配任務τk依據距離原則分配給最近的AGV(ai)。任務分配一致性Cta表征同一任務分配給同一AGV 的概率，當任務數量較少N≤10 時，Cta總是接近100%，而N＞10 時，由于超出存車區域的車位數量的車輛會在車位空閑時隨機生成，存在AGV到達任務初始位置時將該AGV 分配給新生成的存車任務的情況，因此隨著AGV 數量的增加，Cta呈現降低趨勢且最小為88.9%，從而平均分配時間成本總和Tta也在不斷增大。

表1 任務分配算法實驗結果

3.2.2 實驗二：單AGV路徑規劃算法實驗驗證

實驗驗證改進A*算法與傳統A*算法的性能對比，通過隨機生成AGV 停車位置的方式重復進行實驗100 次，取其平均值作為實驗結果，并設定仿真時間為5 min。選擇路徑平均長度Lpp和拐彎次數Ntpp作為路徑規劃算法的性能評價指標。具體的實驗結果如表2所示。

表2 路徑規劃算法實驗結果

由表2可知，與傳統的A*算法相比，添加直線懲罰函數的A*算法在平均路徑長度上優勢并不明顯，而平均拐點數量減少了2.29，拐點數量減少率達38.62%，說明其抑制拐點生成的效果較為明顯。

3.2.3 實驗三：iCBS-pri算法實驗驗證

實驗通過在CBS 算法中增加SZ 和BP 策略，驗證不同沖突消解策略在CBS算法中的作用。選取不同車位占有率(p=30%，60%，90%)下驗證iCBS 算法、CBS［10］算法、CBS+SZ［16］算法和CBS+BP 算法的性能，選擇任務規劃成功率和SoC 作為iCBS 算法的評價指標，并探討了50%任務具有執行優先級的情況下，優先級對iCBS-pri 算法性能的影響。圖7 展示了不同車位占有率(p=30%，60%，90%)以上4種算法隨著AGV 數量的增加，對應的任務規劃成功率Stp和SoC的實驗結果。任務規劃成功率Stp由成功規劃的任務數量Ntp與任務總數N的比值確定，表征系統在有限時間內的多AGV路徑規劃性能。

圖7 iCBS算法實驗結果

圖7 所示的實驗結果表明，隨著AGV 數量的增加，任務規劃成功率逐漸減小，而SoC 逐漸增加，這是由于AGV 數量的增加導致了路徑規劃問題的復雜性，進而使沖突現象明顯快速增加。增加BP策略的CBS 算法（CBS+BP）和增加SZ 策略的CBS 算法（CBS+SZ）任務規劃成功率明顯高于CBS 算法。在p=30%，AGV數量為12時，CBS算法的Stp僅為0.2，而CBS+SZ 算法和CBS+BP 算法的Stp分別達到0.8和0.92，主要是因為搜索備用區域和有效旁路能夠幫助算法提前終止搜索或剔除無關搜索工作，從而進一步提升任務規劃成功率。BP 策略在解決AGV之間的沖突時使用了有效旁路，而BP算法能夠保證AGV 路徑的完整性和最優性，因此添加BP 策略的CBS 算法與傳統CBS 算法具有相同的SoC，添加SZ策略的CBS 算法與iCBS 算法的SoC 相等。SZ 策略通過搜索附近的可用區域為AGV 規劃避讓空間，能夠增加路徑規劃的成功率。在p=60%，AGV 數量為12 時，CBS+SZ 算法的Stp仍達到0.45，但會增加CBS 算法的SoC。隨著車位占有率的增加，實驗中p由30%增加到90%，SZ 策略和BP 策略的可搜索范圍逐漸減少，對CBS的貢獻逐漸減少，因此各種算法的任務規劃成功率之間的差距逐漸減少，iCBS 算法的優越性逐漸降低。

優先級對iCBS 算法的影響如圖8 所示。iCBSpri算法的任務規劃成功率總是高于iCBS算法，是因為具有高優先級的AGV 具有優先通行權，降低了沖突產生的概率，減少了無關的搜索工作。而由于車位占有率的增加，優先級的影響逐漸減小，兩種算法的差距逐步減小，主要是因為具有任務優先級低的AGV 可選的避讓區域有限，導致AGV 間的沖突仍舊存在。

圖8 優先級對iCBS算法的影響

不同路徑規劃算法的運行時間如表3 所示。由數據可以看出，AGV 數量的不斷遞增，各算法求解運行需要更多的時間。由于BP 策略與停車位占有率無關，CBS 算法和 CBS+BP 算法的運行時間幾乎沒有變化。BP策略在AGV數量較小的情況下，由于BP 需要搜索路徑，會增加運行時間，但是在AGV 數量較多時，路徑搜索的時間相較于無效搜索和提前搜索終止帶來的優勢來說相對較小。相較于CBS算法，CBS+BP 算法在AGV 數量較多時的運行時間有較大提升。在停車位占有率較少的情況下，SZ 策略可以大幅消解路徑沖突，其搜索范圍較小，所以搜索時間花費較小，因此CBS+SZ 算法在AGV 數量較少時運行時間略大于CBS 算法，而在AGV 數量較多時CBS+SZ 算法的優勢較為明顯。然而，任務優先級能夠減少無效搜索過程，能夠減少節點拓展，iCBS-pri算法的運行時間相較于iCBS 有一定的減少。在停車位占有率較高時，SZ 策略成功率逐漸降低，且運行時間略有增加，CBS+BP 算法在運行時間方面比iCBS 算法有一定的優勢，結合圖7 展示的任務規劃成功率，CBS+BP 算法更適用于停車占有率較高的場景。

表3 不同路徑規劃方法的平均運行時間

4 結論

針對RIG 中具有任務執行優先級的多AGV 路徑規劃問題，提出了一種改進的基于搜索的沖突消解模型。根據RIG 中AGV 運行特點，創新性地提出備用區域搜索策略和旁路規劃策略相結合的CBS上層搜索算法，同時在下層搜索算法中添加直線懲罰函數，以減少路徑拐點對AGV 運行的影響，并在CBS算法基礎上提出基于iCBS-pri的多AGV路徑規劃算法，并驗證了iCBS-pri 算法在不同車位占有率的情況下具有較高的任務規劃成功率，且iCBS-pri算法在任務規劃成功率方面比iCBS 算法平均提升11.3%，算法平均運行時間提升5.93%，進一步提升了RIG 存取車效率。但研究以數值仿真驗證為主，仿真實驗場景設置相對理想，未來將通過獲取實際的停車AGV 的運行數據以及智能車庫的運行數據，設計更加貼近實際車庫環境的實驗場景來驗證和改進iCBS-pri算法以適用智能車庫運行場景。