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

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

前言

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

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

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

針對具有任務(wù)執(zhí)行優(yōu)先級的RIG 系統(tǒng)，在分析RIG 實際沖突特點的基礎(chǔ)上，引入基于備用區(qū)域搜索策略和旁路規(guī)劃策略協(xié)同的沖突消解方法，提出了一種基于改進CBS 的路徑規(guī)劃算法，為RIG 規(guī)劃多AGV無沖突路徑。

1 RIG停車環(huán)境分析

1.1 RIG沖突類型分析

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

圖1 RIG典型場景

圖2 多AGV典型沖突類型

1.2 RIG路徑規(guī)劃問題描述

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

2 RIG多AGV路徑規(guī)劃模型

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

2.1 TA模塊

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

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

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

2.2 PP模塊

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

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

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

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

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

2.3 CDAR模塊

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

2.3.1 CD子模塊

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

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

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

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

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

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

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

（e）循環(huán)沖突：一組AGV 在同一時間步內(nèi)，每個AGV 移動到之前被另一個AGV 占用的節(jié)點，形成一個“旋轉(zhuǎn)循環(huán)”的模式，可表示為π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 規(guī)劃一組無沖突路徑(N.solution)，是CBS 上層搜索算法的關(guān)鍵部分（N表示約束樹上的節(jié)點）。CBS 上層搜索算法在約束樹(constraint tree，CT)上執(zhí)行最佳的搜索策略，通過生成限制AGV 的約束集來迭代解決沖突現(xiàn)象。從只有一個約束集為空的初始根節(jié)點開始，調(diào)用CBS 下層搜索找到N.solution，下層搜索評估N.cost最低的節(jié)點，然后選擇最低的N.cost擴展CT 節(jié)點，然后CBS 下層搜索會選擇擴展的節(jié)點并在N.solution中識別一組沖突N.constraints。如果N.constraints為空，則CBS終止并返回N.solution，否則會隨機選擇一個要解決的沖突，根據(jù)沖突的類型施加約束，并添加到N.constraints中，同時CBS 下層搜索會重新規(guī)劃N.solution中的路徑以適應新添加的約束。以圖5為例，a1和a2搬運具有不同優(yōu)先級的任務(wù)，調(diào)用下層路徑規(guī)劃算法得到兩條路徑，在A 點存在點沖突C=，通過拆分節(jié)點A以生成兩個子節(jié)點，每個節(jié)點均繼承A點的約束集，通過為每個節(jié)點添加約束a1或a2在初始位置等待并計算A.cost，可以獲得A.solution，其沖突解決措施為a1在初始位置等待1個時間步長。

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

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

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

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

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

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

3 實驗驗證

3.1 實驗說明

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

圖6 典型RIG場景柵格地圖

3.2 實驗驗證與結(jié)果分析

3.2.1 實驗一：任務(wù)分配算法實驗驗證

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

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

表1 任務(wù)分配算法實驗結(jié)果

3.2.2 實驗二：單AGV路徑規(guī)劃算法實驗驗證

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

表2 路徑規(guī)劃算法實驗結(jié)果

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

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

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

圖7 iCBS算法實驗結(jié)果

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

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

圖8 優(yōu)先級對iCBS算法的影響

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

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

4 結(jié)論

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