基于沖突搜索的多AGV路徑規(guī)劃

收稿日期：2023-06-28

基金項(xiàng)目：安陽市科技發(fā)展計(jì)劃（2022C01SF117）；安陽工學(xué)院科研基金（YPY2022011）

DOI：10.19850/j.cnki.2096-4706.2024.05.040

摘" 要：為實(shí)現(xiàn)倉儲(chǔ)環(huán)節(jié)的自動(dòng)化操作，對多AGV路徑規(guī)劃進(jìn)行了研究，使用柵格地圖法構(gòu)建地圖環(huán)境，以單路徑A*搜索算法為基礎(chǔ)，采用雙層路徑規(guī)劃的沖突搜索算法解決多AGV路徑?jīng)_突問題。具體實(shí)施方法是在高層進(jìn)行沖突檢測和添加約束，在底層使用A*算法進(jìn)行單路徑規(guī)劃。最后使用Python的matplotlib庫編程對路徑規(guī)劃算法進(jìn)行仿真。仿真結(jié)果表明，該課題所使用的規(guī)劃方法行之有效。

關(guān)鍵詞：路徑規(guī)劃；CBS算法；A*算法；AGV；柵格地圖

中圖分類號(hào)：TP18" " 文獻(xiàn)標(biāo)識(shí)碼：A" 文章編號(hào)：2096-4706（2024）05-0183-07

Multi-AGV Path Planning Based on Conflict Search

WEI Shengli， ZHANG Tao

（School of Computer Science and Information Engineering， Anyang Institute of Technology， Anyang" 455000， China）

Abstract： In order to achieve automated operations in the warehousing process， research is conducted on multi-AGV path planning. A grid map method is used to construct a map environment， and based on the single path A* search algorithm， a conflict search algorithm for dual layer path planning is adopted to solve the multi-AGV path conflict problem. The specific implementation method is to perform conflict detection and constraint addition at the upper level， and A* algorithm is used at the lower level for single path planning. Finally， it uses Python's matplotlib library programing to simulate the path planning algorithm. The simulation results indicate that the planning method used in this project is effective.

Keywords： path planning; CBS algorithm; A* algorithm; AGV; grid map

0" 引" 言

迅速增長的快遞業(yè)務(wù)對物流業(yè)提出了更高的要求，傳統(tǒng)的手工操作，難以滿足快速變化的市場需求[1]。為了解決倉儲(chǔ)環(huán)節(jié)的自動(dòng)化問題，通常采用自動(dòng)導(dǎo)引車（AGV）來實(shí)現(xiàn)高效快捷的快遞配送[2]，以達(dá)到自動(dòng)化、智能化和高度無人化操作[3]。而多AGV路徑規(guī)劃問題也就成為研究的重點(diǎn)。目前路徑規(guī)劃算法普遍基于A*算法，多路徑規(guī)劃基于沖突搜索的思想。李揚(yáng)在A*算法的基礎(chǔ)上提出了基于沖突搜索的多智能體路徑規(guī)劃算法[4]。宣志瑋等針對地形復(fù)雜的大型地圖，提出了CBS框架下面向復(fù)雜地圖的低拓展度A*算法[5]。官祥錦等采用切比雪夫距離對A*的啟發(fā)函數(shù)進(jìn)行加權(quán)，減少了搜索時(shí)間，并結(jié)合時(shí)間窗模型，有效解決了多AGV沖突問題[6]。周欣慈等提出了一種改進(jìn)的CBS算法對碼頭的AGV路徑規(guī)劃進(jìn)行了研究。其核心思想是結(jié)合二叉樹原理建立沖突樹來規(guī)避多AGV的沖突[7]。

在前人研究的基礎(chǔ)上，對多AGV路徑規(guī)劃問題進(jìn)行了研究。首先對單AGV路徑規(guī)劃問題進(jìn)行了分析，然后將其擴(kuò)展應(yīng)用到多AGV路徑規(guī)劃問題。使用了雙層路徑規(guī)劃算法以解決沖突問題，每個(gè)AGV都在底層搜索中找到最佳行駛路線，而把解決AGV路徑之間的沖突放在高層搜索中。

1" 地圖選擇與單AGV路徑規(guī)劃

AGV路徑規(guī)劃需要研究兩個(gè)重要問題：環(huán)境地圖建模方法和AGV路徑規(guī)劃算法。環(huán)境地圖能夠定量判斷所選擇的路徑規(guī)劃算法成本，路徑規(guī)劃算法求出最優(yōu)的行走路徑。單AGV路徑規(guī)劃是多AGV路徑規(guī)劃的前提。本節(jié)內(nèi)容介紹環(huán)境地圖建模方法和單AGV路徑規(guī)劃算法。

1.1" 環(huán)境地圖建模

環(huán)境地圖模型的準(zhǔn)確性和復(fù)雜程度會(huì)影響路徑規(guī)劃的決策效率和響應(yīng)速度[8]。常見的環(huán)境地圖建模方法包括可視地圖、拓?fù)涞貓D和柵格地圖。柵格圖法是近年來被廣泛采用的AGV環(huán)境模擬方法。如圖1所示，它將空間環(huán)境分成相同大小的格子，一些有障礙物的格子和其他開放的格子。柵格大小的選擇很重要，過小會(huì)增加內(nèi)存使用量，而過大會(huì)減少精度和影響路徑規(guī)劃。在柵格地圖上，起點(diǎn)到終點(diǎn)之間連續(xù)的可通行柵格構(gòu)成AGV的一條可行路徑。柵格圖法是一種簡單高效、易實(shí)現(xiàn)且易于觀察的建模方法，適用于復(fù)雜環(huán)境下的路徑規(guī)劃。因此，本文采用柵格法建立二維平面地圖模型，并通過算法實(shí)現(xiàn)AGV路徑規(guī)劃模擬。

圖1" 柵格圖模型

1.2" 單AGV路徑規(guī)劃算法

單AGV路徑規(guī)劃是多AGV路徑規(guī)劃的基礎(chǔ)。單AGV路徑規(guī)劃只考慮一臺(tái)AGV運(yùn)行時(shí)的最優(yōu)路徑，以達(dá)到有效、高效地執(zhí)行任務(wù)的目的。A*算法、Dijkstra算法和粒子群算法是研究應(yīng)用較多的路徑規(guī)劃算法[9]。

Dijkstra算法最開始主要用于求解有向圖的最短路徑問題，后來又被用作單源路徑規(guī)劃算法，對單AGV的路徑規(guī)劃研究具有重要意義。然而，它在實(shí)時(shí)路徑規(guī)劃時(shí)需要大量的計(jì)算量，這是它的主要缺陷。1968年，Nilsson等提出了A*算法。它是一種求解最短路徑的直接算法，也是其他許多啟發(fā)式算法的基礎(chǔ)。粒子群算法是一種基于群體智能的優(yōu)化算法，用于在搜索空間中尋找最優(yōu)解。粒子群算法簡單易實(shí)現(xiàn)，并行化效果較好并且全局收斂性較強(qiáng)。但在搜索過程中，粒子只能基于當(dāng)前狀態(tài)和歷史最優(yōu)狀態(tài)進(jìn)行更新，而無法引入其他信息來幫助搜索，容易陷入局部最優(yōu)解，并且種群的隨機(jī)初始化對迭代結(jié)果也有較大影響。

盡管Dijkstra算法在單個(gè)AGV路徑規(guī)劃問題中能夠找到最佳路徑，但是其運(yùn)行時(shí)間相對較長。粒子群算法容易陷入局部最優(yōu)解的困擾，并且其結(jié)果受到隨機(jī)性的影響程度相當(dāng)大。相對于其他算法而言，A*算法具有更高的搜索效率，更好的空間利用率和更廣的適用性，A*算法引入啟發(fā)式函數(shù)來指導(dǎo)搜索，估計(jì)其他位置到目標(biāo)位置的距離，并優(yōu)先探索離目標(biāo)節(jié)點(diǎn)近的節(jié)點(diǎn)，因此能夠更快地找到最短路徑。而且A*算法的啟發(fā)式函數(shù)可以根據(jù)具體問題進(jìn)行設(shè)計(jì)，因此在不同種類的圖中都可以使用。而Dijkstra算法和粒子群算法則只適用于特定類型的圖或問題。因此，我們選擇A*算法來解決該問題。

1.3" A*算法

1.3.1" A*算法模型

A*算法是一種啟發(fā)式搜索算法，常用于解決圖或網(wǎng)絡(luò)中的最短路徑問題。A*算法引入啟發(fā)函數(shù)用來指導(dǎo)搜索，該函數(shù)可以估計(jì)從當(dāng)前位置到目標(biāo)位置的距離[10]，其主要原理選擇成本最低的節(jié)點(diǎn)作為下一步移動(dòng)位置，并重復(fù)此步驟，直到找到目標(biāo)點(diǎn)或者確定無法到達(dá)目標(biāo)點(diǎn)為止。啟發(fā)函數(shù)表達(dá)式如式（1）：

f （n） = g （n） + h （n）" " " " " " " " " " " （1）

其中，n表示當(dāng)前位置，g （n）表示從起始位置到當(dāng)前位置n的實(shí)際距離，h （n）表示從當(dāng)前位置n到目標(biāo)位置的估計(jì)距離。f （n）表示總距離。在滿足可接受性條件下，A*算法能夠得到最優(yōu)解。

在式（1）中，由于距離函數(shù)g （n）已知，因此啟發(fā)式函數(shù)的選擇可以基于距離函數(shù)和問題特征進(jìn)行設(shè)計(jì)，以盡可能減少搜索空間和加速搜索過程。不同的啟發(fā)式函數(shù)可能導(dǎo)致最終評價(jià)目標(biāo)函數(shù)的結(jié)果不同。當(dāng)估計(jì)函數(shù)值h （n）如果設(shè)計(jì)的太高，雖然可以提高算法的搜索速度，但難以保證算法搜索的精度；而估計(jì)函數(shù)值h （n）如果設(shè)計(jì)的太低，雖然保證了算法的精度卻難以保證算法的運(yùn)算效率。A*算法常用的h （n）估計(jì)值函數(shù)有曼哈頓距離計(jì)算函數(shù)、歐式距離計(jì)算函數(shù)。

歐式距離的計(jì)算公式如式（2）：

（2）

曼哈頓距離的計(jì)算公式如式（3）：

（3）

在式（2）（3）中，（xn， yn）表示當(dāng)前位置，（xg， yg）表示目標(biāo)位置。

在柵格圖中，搜索最短路徑常用4鄰域搜索和8鄰域搜索。4鄰域搜索只考慮上下左右4個(gè)相鄰的柵格，而8鄰域搜索則考慮上下左右以及對角線方向上的8個(gè)相鄰的柵格[11]。AGV在倉儲(chǔ)中心一般只有橫平豎直的運(yùn)動(dòng)，不存在斜向移動(dòng)。因此這里只考慮4鄰域搜索，使用曼哈頓距離作為啟發(fā)函數(shù)。

1.3.2" A*算法具體流程

A*算法維護(hù)兩個(gè)列表：一個(gè)是OPEN列表，記錄待探索的節(jié)點(diǎn)；另一個(gè)是CLOSE列表，記錄已經(jīng)探索過的節(jié)點(diǎn)。首先將起始節(jié)點(diǎn)加入OPEN列表，并計(jì)算其估計(jì)代價(jià)。其基本步驟為：

1）初始化起點(diǎn)和終點(diǎn)節(jié)點(diǎn)以及起點(diǎn)的估價(jià)函數(shù)值（即起點(diǎn)到終點(diǎn)的最短距離）。尋找OPEN表中估值函數(shù)值最小的節(jié)點(diǎn)。

2）將起點(diǎn)加入一個(gè)開放列表（open list）中，該列表存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)。

3）從開放列表中選擇一個(gè)最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展。這里的“最優(yōu)”是指當(dāng)前已經(jīng)走過的路徑長度加上該節(jié)點(diǎn)到終點(diǎn)的估價(jià)函數(shù)值最小。

4）將該節(jié)點(diǎn)存入關(guān)閉列表（close list）中，該列表存儲(chǔ)已考查過的節(jié)點(diǎn)。

5）對該節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)進(jìn)行評估。如果鄰節(jié)點(diǎn)不可到達(dá)或已在關(guān)閉列表中，則不處理，否則計(jì)算每個(gè)鄰居節(jié)點(diǎn)的估價(jià)函數(shù)值，并記錄它們的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。

6）對于不在OPEN列表中的鄰居節(jié)點(diǎn)，將其加入OPEN列表，并將當(dāng)前節(jié)點(diǎn)設(shè)置為他的父節(jié)點(diǎn)。如果某個(gè)鄰居節(jié)點(diǎn)已經(jīng)在開放列表中且更新，則更新其父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)和路徑長度信息。

7）重復(fù)步驟3）-6），直到找到終點(diǎn)或者開放列表為空（表示無解）。

8）如果找到了終點(diǎn)，則按照每個(gè)節(jié)點(diǎn)的父子關(guān)系回溯路徑；否則輸出無解。A*算法流程如圖2所示。

圖2" A*算法流程

2" 多AGV路徑規(guī)劃

多AGV的路徑規(guī)劃問題在于協(xié)作完成任務(wù)并避免碰撞。本文采用基于沖突的搜索（CBS）算法解決多AGV的碰撞問題。

2.1" 多AGV路徑規(guī)劃問題模型

在多AGV路徑規(guī)劃問題中，假設(shè)有n個(gè)AGVA = {a1，a2，a3，…，an}和一個(gè)無向圖G = {V，E}，V表示地圖中的節(jié)點(diǎn)，E表示節(jié)點(diǎn)之間的邊。在地圖中指定一個(gè)起始點(diǎn)S = {s1，s2，s3，…，sn}和目標(biāo)點(diǎn)T = {t1，t2，t3，…，tn}。每個(gè)AGV的輸入是三元組〈G，si，ti〉，其中i = 1，…，n。時(shí)間被離散化后，在每個(gè)周期內(nèi)AGV可以完成一個(gè)動(dòng)作m，用映射m：V→V來表示m（v） = v'。這個(gè)動(dòng)作m使得AGV在一個(gè)周期內(nèi)完成從位置v到位置v'的轉(zhuǎn)換。動(dòng)作有兩種類型：等待和前進(jìn)。等待是指AGV在本周期內(nèi)在原位置不動(dòng)。前進(jìn)是指AGV從當(dāng)前位置v前進(jìn)到位置v'，即（v，v'） ∈ E。按照搜索算法最終會(huì)找到一條路徑π = {p1，p2，p3，…，pi}，其中p1，p2，p3，…，pi ∈ V。

2.2" 路徑?jīng)_突

在多AGV環(huán)境中，會(huì)發(fā)生不同類型的沖突。假設(shè)倉儲(chǔ)系統(tǒng)中所有AGV的勻速行駛，不會(huì)發(fā)生追趕沖突。本文主要考慮相向沖突和節(jié)點(diǎn)沖突兩種情況。相向沖突是指兩個(gè)AGV在相反的方向上移動(dòng)時(shí)發(fā)生的碰撞或阻塞情況，如圖3（a）所示。節(jié)點(diǎn)沖突則是指兩個(gè)或多個(gè)AGV在同一交叉路口或節(jié)點(diǎn)處互相阻塞的情況，如圖3（b）所示。這些沖突可能導(dǎo)致任務(wù)延遲、資源浪費(fèi)和系統(tǒng)效率降低等問題。

（a）相向沖突

（b）節(jié)點(diǎn)沖突

圖3" 路徑?jīng)_突

2.3" 基于沖突的搜索算法

基于沖突的搜索（CBS）算法[12]解決問題的思路是：不斷檢測是否存在沖突，如果存在沖突，則通過一定的規(guī)則解決沖突，直至解決所有的沖突問題。在算法的運(yùn)行過程中，首先在高層進(jìn)行沖突檢測和約束添加，然后再進(jìn)入底層進(jìn)行具體的操作。在底層中使用上一節(jié)介紹的A*算法為單個(gè)AGV尋找一條與新的限制條件相符的路徑。

CBS算法引進(jìn)約束概念，約束用c =（ai，s，t）來表示。其中t表示在某一時(shí)間點(diǎn)，對于AGVai而言，s位置被限制，無法經(jīng)過或停留在上面。向一個(gè)3×3的柵格地圖中添加一個(gè)約束c =（a1，[2，2]，2）如圖4所示。a1的起始節(jié)點(diǎn)為（3，1），目標(biāo)節(jié)點(diǎn)為（1，3），起初路徑規(guī)劃后a1有概率會(huì)途徑（2，2）節(jié)點(diǎn)位置（如圖4（a）所示）。然而，添加約束后，在t = 2時(shí)刻（2，2）位置不能通過。因此，算法將跳過該障礙物并重新規(guī)劃路徑以符合約束條件（如圖4（b）所示）。新路徑滿足約束條件。

（a）增加約束前" " " " " " " " " " （b）增加約束后

圖4" 約束產(chǎn)生影響

在高層搜索中，CBS算法搜索約束樹節(jié)點(diǎn)（CT Node），而這個(gè)節(jié)點(diǎn)CT是一棵二叉樹。高層設(shè)計(jì)了一個(gè)優(yōu)先級(jí)隊(duì)列OPENcbs，用于記錄待檢測的約束樹節(jié)點(diǎn)，節(jié)點(diǎn)的cost代表其解決方案的成本。每個(gè)約束樹節(jié)點(diǎn)N都含有三個(gè)數(shù)據(jù)字段。

N.constraints：一組約束，涵蓋了場景中所有AGV的限制條件。CT的根節(jié)點(diǎn)包含一個(gè)空的限制條件集合，而CT的子節(jié)點(diǎn)繼承其父節(jié)點(diǎn)的限制條件，并為一個(gè)AGV添加新的限制條件。

N.solution：路徑規(guī)劃的解，解中所有AGV的路徑符合約束樹節(jié)點(diǎn)的約束集。但可能存在潛在沖突，因此解不一定有效。

N.cost：該節(jié)點(diǎn)解的成本，即所有單AGV路徑成本的總和。

CBS算法的底層搜索算法是用來為每個(gè)AGV規(guī)劃的，本文采用A*算法，因?yàn)橄聦硬豢紤]沖突，所以所有單AGV路徑成本的總和最小。

在CBS算法中，首先需要?jiǎng)?chuàng)建一個(gè)根節(jié)點(diǎn)R作為約束樹的起點(diǎn)，該節(jié)點(diǎn)初始時(shí)沒有任何約束條件，其constraints屬性為空，但其solution屬性為下一層搜索中各個(gè)AGV路徑節(jié)點(diǎn)的集合，而cost屬性則為各AGV路徑的成本值之和。在初始解中，每個(gè)AGV的路徑規(guī)劃是相互獨(dú)立的，沒有考慮其他AGV路徑的影響。之后，算法從OPENcbs隊(duì)列中獲取節(jié)點(diǎn)，在獲取到的節(jié)點(diǎn)N中檢查其解是否存在沖突，沖突表現(xiàn)為四元組（ai，aj，s，t），在時(shí)刻t時(shí)，AGVai和aj在元素s處產(chǎn)生了沖突。如果發(fā)現(xiàn)沖突，算法會(huì)在該節(jié)點(diǎn)N的基礎(chǔ)上分解出兩個(gè)子節(jié)點(diǎn)N1和N2，然后將父節(jié)點(diǎn)的約束和值從屬性上復(fù)制到兩個(gè)子節(jié)點(diǎn)上。當(dāng)對節(jié)點(diǎn)N1添加約束c = （ai，s，t），這意味著ai在t時(shí)刻不能進(jìn)入s點(diǎn)，底層重新為ai規(guī)劃路徑，并使用高層搜索更新節(jié)點(diǎn)的cost屬性。

圖5給出了兩個(gè)AGV的路徑規(guī)劃，a1從（3，1）的起始位置出發(fā)，前往（1，3）的目標(biāo)位置，而a2則從（3，3）的起始位置出發(fā)，前往目標(biāo)（1，1）。在初始化階段，CBS算法上層創(chuàng)建一個(gè)空根節(jié)點(diǎn)，并把該節(jié)點(diǎn)放入到OPENcbs集合中。然后，主循環(huán)從OPENcbs中獲取根節(jié)點(diǎn)，并根據(jù)其中的解進(jìn)行沖突檢測。在節(jié)點(diǎn)（3，2），a1和a2發(fā)生沖突的事實(shí)在t = 2時(shí)刻發(fā)生。因此，算法上層會(huì)創(chuàng)建兩個(gè)子節(jié)點(diǎn)，這些子節(jié)點(diǎn)將繼承父節(jié)點(diǎn)的所有限制條件，同時(shí)加入新的約束條件。在接下來的操作中，底層為對應(yīng)的AGV路徑重新規(guī)劃，并將兩個(gè)子節(jié)點(diǎn)加入OPENcbs列表。在下一輪迭代中算法成功找到了無沖突路徑。虛線方框內(nèi)的解表示最佳路徑。

圖5" 求解兩個(gè)AGV路徑規(guī)劃問題的過程

3" 路徑規(guī)劃仿真

為檢驗(yàn)算法的有效性，使用Python的Matplotlib庫編程對路徑規(guī)劃算法進(jìn)行了仿真。

圖6展示了一個(gè)柵格地圖環(huán)境，該地圖有26行32列、共計(jì)832個(gè)柵格。周圍黑色障礙物代表墻壁。每個(gè)柵格形狀大小相同，AGV的直徑略小于柵格的邊長，每個(gè)柵格都有位置坐標(biāo)（x，y），從地圖左上角開始，x表示第幾行，y表示第幾列。AGV經(jīng)過一個(gè)柵格需要花費(fèi)一個(gè)單位時(shí)間。揀貨站占據(jù)4個(gè)柵格，補(bǔ)貨站占據(jù)4個(gè)柵格，貨架占據(jù)200個(gè)柵格。

圖6" 倉儲(chǔ)柵格地圖

3.1" 相向沖突仿真實(shí)驗(yàn)

假設(shè)兩輛AGV同時(shí)運(yùn)行，行駛路線如圖7所示。其中，AGV1從起點(diǎn)（12，3）到終點(diǎn)（12，19），AGV2從起點(diǎn)（12，32）到終點(diǎn)（12，13）。為避免與AGV2發(fā)生沖突，AGV1選擇繞道經(jīng)過柵格（11，17）（11，18）（11，19），而不是直接到達(dá)柵格（12，19）。通過CBS算法，確保二者不會(huì)在時(shí)間上同時(shí)到達(dá)任何一個(gè)柵格，避免了潛在碰撞沖突。

圖7" 雙AGV相向行駛路線圖

圖8展示了這兩輛AGV的三維時(shí)空圖。未使用CBS算法時(shí)，如圖8（a）所示，兩條路徑在（12，18，16）相交，說明在t = 16時(shí)刻發(fā)生了碰撞。使用CBS算法后，AGV1避開了柵格（12，18），行駛到了（11，17），避免了與AGV2相撞，如圖8（b）所示。原理為算法上層檢測到?jīng)_突（a1，a2，（12，18），16），施加新約束（a1，（12，18），16），下層重新規(guī)劃AGV1的路徑。這表明CBS算法可以有效解決相向沖突。

3.2" 節(jié)點(diǎn)沖突仿真

為了驗(yàn)證節(jié)點(diǎn)沖突，假設(shè)兩輛AGV垂直行駛，如圖9所示，AGV1從起點(diǎn)位置（12，3）到達(dá)終點(diǎn)位置（12，16），AGV2從起點(diǎn)位置（23，14）到達(dá)終點(diǎn)位置（8，16）。為避免在柵格（12，14）發(fā)生節(jié)點(diǎn)沖突，AGV1在行駛到柵格（12，13）（即S點(diǎn)）后停留一個(gè)單位時(shí)間，讓AVG2先行，隨后再前往柵格（12，14）。避開了與AGV2在柵格（12，14）發(fā)生節(jié)點(diǎn)沖突。

（a）算法使用前

（b）算法使用后

圖8" 雙AGV相向行駛時(shí)空圖

圖9" 雙AGV垂直行駛路線圖

圖10展示了節(jié)點(diǎn)沖突三維時(shí)空圖。未使用CBS算法時(shí)，t = 11時(shí)刻兩條路徑在（12，14，11）處相交，表明發(fā)生了沖突。使用CBS算法規(guī)劃后，兩條路徑?jīng)]有相交，AGV2的路徑不變，而AGV1在t = 10時(shí)后停止行駛，停留在柵格（12，13）上一個(gè)時(shí)間單位，讓AGV2先行，之后再繼續(xù)前進(jìn)，避免了相撞。原理為在上層檢測到（a1，a2，（12，14），11），通過添加新約束（a1，（12，14），11），使得在下層重新規(guī)劃路徑以滿足約束。結(jié)果表明，算法能夠有效解決路徑?jīng)_突。

（a）沒有采用算法的時(shí)空圖

（b）采用算法后的時(shí)空圖

圖10" 雙AGV垂直行駛時(shí)空圖

3.3" 多種沖突的情景

為了檢驗(yàn)算法在多種沖突情景下的效果，假設(shè)有8輛AGV同時(shí)運(yùn)行，各輛AGV的基本信息如表1所示。

表1" 各AGV對應(yīng)信息

AGV編號(hào) 起點(diǎn)坐標(biāo) 終點(diǎn)坐標(biāo)

1 （7，3） （6，25）

2 （12，3） （13，28）

3 （22，3） （21，22）

4 （26，20） （3，22）

5 （12，29） （26，19）

6 （17，32） （23，17）

7 （3，16） （16，11）

8 （2，6） （13，22）

圖11展示了未使用CBS算法時(shí)所有AGV的行駛軌跡，柵格地圖上的圓形代表每輛AGV的起點(diǎn)，方框代表終點(diǎn)，叉號(hào)代表該位置發(fā)生了沖突。

圖11" 算法使用前的多AGV路線圖

圖12展示了使用CBS算法后所有AGV的行駛軌跡，所有AGV沒有發(fā)生碰撞。

圖13展示了中8輛AGV行駛軌跡對應(yīng)的時(shí)空圖，共有5個(gè)相交點(diǎn)，分別對應(yīng)圖11中5個(gè)叉號(hào)，代表發(fā)生了5次沖突。通過圖13（a）可知，在t = 19時(shí)，1號(hào)和8號(hào)在坐標(biāo)（6，21）處發(fā)生碰撞；在t = 11時(shí)，2號(hào)和7號(hào)在坐標(biāo)（12，14）處發(fā)生碰撞；在t = 17時(shí)，3號(hào)和6號(hào)在坐標(biāo)（21，19）處發(fā)生碰撞；在t = 18時(shí)，3號(hào)和5號(hào)在坐標(biāo)（21，20）處發(fā)生碰撞；在t = 11.5時(shí)，4號(hào)和5號(hào)在坐標(biāo)（14，20）和坐標(biāo)（15，20）之間發(fā)生碰撞。

圖12" 算法使用后的多AGV路線圖

（a）算法使用前

（b）算法使用后

圖13" 多AGV三維時(shí)空圖

采用CBS算法規(guī)劃的AGV成功避免了5處沖突。圖13（b）展示了CBS算法規(guī)劃后的路徑，任意兩條路徑線段在時(shí)空中均沒有相交，說明路徑間無沖突。2、4、5和8號(hào)的AGV的路徑?jīng)]有變化，而1、3、5和7號(hào)AGV為避免沖突重新規(guī)劃了路徑。

通過CBS算法，上層檢測到5個(gè)沖突，分別為（a1，a8，（6，21），19）、（a2，a7，（12，14），11）、（a3，a6，（21，19），17）、（a3，a5，（21，20），18）和（a4，a5，[（14，20），（15，20）]，11.5），施加對應(yīng)的約束（a1，（6，21），19）、（a5，（21，20），18）、下層根據(jù)1、3、5和7號(hào)AGV新添加的約束為它們重新規(guī)劃了路徑。證明在存在多種沖突且AGV數(shù)量較多的情況下，使用CBS算法仍然能夠成功解決問題。

4" 結(jié)" 論

針對多AGV作業(yè)時(shí)遇到的各種沖突問題，采用一種雙層路徑規(guī)劃算法進(jìn)行解決。底層采用A*進(jìn)行路徑規(guī)劃，高層采用CBS進(jìn)行沖突監(jiān)測，實(shí)現(xiàn)了算法并對算法進(jìn)行驗(yàn)證。仿真結(jié)果證明了該算法的有效性。主要完成的工作有：

1）選用柵格法作為多AGV路徑規(guī)劃的地圖建模方法。

2）采用基于曼哈頓距離預(yù)估成本的A*算法實(shí)現(xiàn)了單AGV路徑規(guī)劃，為CBS算法奠定了基礎(chǔ)。

3）采用CBS算法解決節(jié)點(diǎn)沖突、相向沖突和多種沖突并存等問題。

4）使用Python語言實(shí)現(xiàn)了算法，對算法的有效性進(jìn)行了仿真。

參考文獻(xiàn)：

[1] 劉冠一.倉儲(chǔ)環(huán)境下智能移動(dòng)機(jī)器人路徑規(guī)劃研究 [D].北京：北京印刷學(xué)院，2021.

[2] KHIR R，ERERA A，TORIELLO A. Two-Stage Sort Planning for Express parcel Delivery [J].IISE Transactions，2021，53（12）：1353-1368.

[3] 郭超，陳香玲，郭鵬，等.基于時(shí)空A*算法的多AGV無沖突路徑規(guī)劃 [J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2022，31（4）：360-368.

[4] 李揚(yáng).基于沖突搜索的多智能體路徑規(guī)劃算法研究與優(yōu)化 [D].沈陽：沈陽化工大學(xué)，2021.

[5] 宣志瑋，毛劍琳，張凱翔.CBS框架下面向復(fù)雜地圖的低拓展度A*算法 [J].電子學(xué)報(bào)，2022，50（8）：1943-1950.

[6] 官祥錦，陳娟，張為民.基于改進(jìn)A*算法的多AGV路徑規(guī)劃研究 [J].航空制造技術(shù)，2023，66（5）：76–85+90.

[7] 周欣慈，朱瑾.基于改進(jìn)CBS算法的自動(dòng)化碼頭多AGV無沖突路徑規(guī)劃 [J].計(jì)算機(jī)應(yīng)用研究，2023，40（9）：2621-2625+2632.

[8] 陳香玲.電商物流分揀中心多AGV調(diào)度與路徑規(guī)劃研究 [D].成都：西南交通大學(xué)，2021.

[9] 劉恒麟.多AGV路徑規(guī)劃算法的研究與實(shí)現(xiàn) [D].南京：東南大學(xué)，2020.

[10] 張放.極限工況下自動(dòng)駕駛車輛的軌跡規(guī)劃與運(yùn)動(dòng)控制 [D].北京：清華大學(xué)，2018.

[11] 谷萬，徐振，郭帥.基于A*和改進(jìn)動(dòng)態(tài)窗口法的建筑移動(dòng)機(jī)器人路徑規(guī)劃 [J].工業(yè)控制計(jì)算機(jī)，2022，35（8）：87-90.

[12] SHARON G，STERN R，F(xiàn)ELNER A，et al. Conflict-based search for optimal multi-agent pathfinding [J].Artificial Intelligence，2015，219：40-66.

作者簡介：魏勝利（1974—），男，漢族，河南滑縣人，副教授，教研室主任，碩士研究生，主要研究方向：計(jì)算機(jī)控制、智能制造等。