基于沖突避讓的多智能體有效旁路規(guī)劃

關(guān)鍵詞：基于沖突搜索；狹窄路段；有效旁路；多智能體路徑規(guī)劃；臨時(shí)等待位置；次優(yōu)路徑中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2025）07-024-2103-06doi：10.19734/j.issn.1001-3695.2024.11.0469

Abstract：Tosolvetheproblemthatmultipleagents innarrowenvironmentcannotavoidtheconflictonkeychannels，which leads to thelow eficiencyof multi-agent path finding，this paper proposed an effective bypassplanning algorithm basedon fieldofviewconflictsearch.Intheupperlayerof theconflict-basedsearchalgorithmframework，thefieldofviewrepresented thecommunicationrangeof theagent.Byscanning the multi-value decision diagramof allagents inthecommunicationrange of theagent，thealgorithm determinedwhether therewasacompetion forsharedresources betweentheagents，leading to conflicts.Themulti-valueddecisionbacktrackingconflictavoidance strategyresolvedtheconflictsbetween multipleagentson thecriticalchannel.Byscanning the multi-valueddecision diagram，theagentobstructingthecritical channelcould find the suboptimalpathorthetemporarywaiting positionasaneffetivebypasstoavoidthecollsion.Theresultsofdifferentscaleand structure maptestshow thatmuli-valued decision backtracking conflictavoidance strategycan effectivelyreducetheoccurrenceof conflictbetwenagents.Intherandom-64-64-10and maze-128-128-10mapenviroments，theaveragesuccessrateof pathfinding for multiple agents improves by 10% and 15.2% ，respectively，compared with CBS-BP，proving that this algorithm effectively avoids conflicts and increases pathfinding success rates.

Key words：conflict-based search；narrowsection；efectivebypass；multi-agentpath planning；temporary waiting position; suboptimal path

0 引言

多智能體路徑規(guī)劃（multi-agentpath finding，MAPF）作為智能體領(lǐng)域的研究熱點(diǎn)，受到國內(nèi)外學(xué)者廣泛關(guān)注[1-3]。近幾年，移動(dòng)智能體在各行各業(yè)得到了廣泛應(yīng)用，例如自動(dòng)物流倉儲(chǔ)系統(tǒng)[4.5]、自動(dòng)駕駛汽車[6、搜索營救[7]等。

MAPF主要目的是保證多個(gè)智能體在躲避環(huán)境中的靜態(tài)障礙物的基礎(chǔ)上，互相不發(fā)生碰撞，且都能找到一條從不同起始點(diǎn)到各自目標(biāo)點(diǎn)的最優(yōu)路徑。由于其NP-hard[8]的復(fù)雜性，多個(gè)智能體在尋路過程中，隨著智能體數(shù)量的增加，或路徑規(guī)劃場景較復(fù)雜時(shí)，求解空間激增，擴(kuò)展節(jié)點(diǎn)較多，導(dǎo)致智能體之間的沖突加劇，路徑求解效率低。近年來，由于基于沖突搜索（conflict-basedsearch，CBS）算法的兩層結(jié)構(gòu)更容易與各種算法結(jié)合，所以提出了很多關(guān)于CBS算法的改進(jìn)算法解決MAPF問題，包括層次合成的CBS算法（hierarchicalcompositionCBS，HCCBS）[9]、彈性的 ECBS 算法（flexible ECBS，F(xiàn)ECBS）[1]、自適應(yīng)特定于agent的次優(yōu)CBS算法（adaptiveagent-specific suboptimal bounding approach，ABS-ECBS）[11]、顯示估計(jì)的 CBS 算法（explicit estimation CBS，EECBS）[12]等。

A^* 算法是尋找最優(yōu)路徑的經(jīng)典算法[13]。溫惠英等人[14]通過在 A^* 算法中引入負(fù)載因子，使規(guī)劃路徑避開擁堵點(diǎn)，實(shí)現(xiàn)道路負(fù)載均衡。在多智能體路徑規(guī)劃的眾多問題中，智能體之間沖突的檢測與解決是一個(gè)主要問題。宣志瑋等人[1在CBS的上層算法 A^* 基礎(chǔ)上作出改進(jìn)，但當(dāng)場景較大時(shí)，沖突數(shù)量驟增，拓展節(jié)點(diǎn)隨之增多，增加了A*算法的計(jì)算量，導(dǎo)致路徑求解效率很低[16]。王卓然等人[17]提出了一種基于神經(jīng)網(wǎng)絡(luò)的RankNet算法對(duì)沖突進(jìn)行選擇，但其只提高了CBS選擇沖突的效率，沒有實(shí)現(xiàn)兩個(gè)智能體路徑信息互享，無法避免沖突的發(fā)生。文獻(xiàn)[18＼～20]通過在多值決策圖的基礎(chǔ)上加入互斥傳播來獲取成對(duì)智能體的可達(dá)性信息，以此來檢測智能體之間的沖突。在此基礎(chǔ)上，文獻(xiàn)[21，22]提出沖突優(yōu)先級(jí)來提高智能體之間的沖突消解效率。

在MAPF中如果只是對(duì)沖突選擇和沖突消解進(jìn)行改進(jìn)，而不是從根本上規(guī)避沖突的發(fā)生，會(huì)導(dǎo)致擴(kuò)展節(jié)點(diǎn)增多，求解空間激增，智能體尋路效率低下。楊鄒等人[23]引入跳點(diǎn)搜索結(jié)合沖突概率反饋，減少機(jī)器人之間的沖突，但狹窄環(huán)境下的沖突不能得到有效減少。而狹窄空間下的沖突不能得到有效解決，會(huì)增加智能體之間的局部沖突，甚至導(dǎo)致死鎖，使智能體尋路效率低，找不到目標(biāo)點(diǎn)。本文針對(duì)狹窄空間下多個(gè)智能體需要通過關(guān)鍵通道才能找到最優(yōu)路徑，導(dǎo)致智能之間發(fā)生局部沖突的概率增加這個(gè)問題，提出了基于視場的沖突搜索有效旁路規(guī)劃（effective bypassplanning for conflict search based on field ofview，EBPCS-FOV）算法。通過視場實(shí)現(xiàn)智能體之間的通信，為占據(jù)關(guān)鍵通道的智能體搜索有效旁路來確保其他智能體通過關(guān)鍵通道時(shí)沒有阻礙，保證其順利通過，進(jìn)而提高智能體尋路效率。

1 問題定義

1.1 多智能體路徑規(guī)劃

MAPF問題可以被定義為 n 個(gè)智能體在無向圖 ξ_{G=（ξV，E）} 中尋找一條無碰撞的路徑，其中 V 是頂點(diǎn)集合， E 是連接頂點(diǎn)之間邊的集合。每個(gè)智能體都有各自的起始位置和目標(biāo)位置。在每個(gè)時(shí)間步，智能體可以移動(dòng)到?jīng)]有障礙物的位置或在原地等待，且其需要在不發(fā)生任何碰撞的基礎(chǔ)上從起始位置到達(dá)目標(biāo)位置。

1.2 狹窄環(huán)境定義

狹窄環(huán)境是路徑規(guī)劃領(lǐng)域常見的地形，當(dāng)多個(gè)智能體都需要通過狹窄的關(guān)鍵通道才能找到最優(yōu)路徑時(shí)，就會(huì)導(dǎo)致智能體之間發(fā)生局部沖突的概率大幅增加，降低智能體尋路效率。

圖1表示關(guān)鍵通道上的兩種沖突類型，虛線框部分表示關(guān)鍵通道。圖1（a）所示三個(gè)智能體都必須經(jīng)過此通道才是到達(dá)目標(biāo)點(diǎn)的最優(yōu)路徑;圖1（b）所示智能體1的目標(biāo)點(diǎn)占據(jù)了關(guān)鍵通道，阻礙其他智能體通往終點(diǎn)。這兩種情況都會(huì)導(dǎo)致局部沖突加劇，智能體尋路效率低下。

2基于視場的沖突搜索旁路規(guī)劃算法

多個(gè)智能體路徑規(guī)劃過程中，經(jīng)常需要通過狹窄環(huán)境下的關(guān)鍵通道，這會(huì)造成阻塞，導(dǎo)致智能體之間局部沖突加劇，算法搜索效率低。圖2是幾種典型的關(guān)鍵通道上的沖突，這幾類沖突若不能檢測并解決，可能會(huì)因?yàn)樗惴ㄋ阉鲿r(shí)間過長導(dǎo)致尋路失敗。

當(dāng)兩個(gè)智能體同時(shí)間段經(jīng)過同一走廊，朝著相反方向前進(jìn)時(shí)就會(huì)發(fā)生走廊沖突；兩個(gè)智能體的起始點(diǎn)和目標(biāo)點(diǎn)互換，即同一時(shí)間段走相反的路徑，就會(huì)發(fā)生交換沖突；距離目標(biāo)較遠(yuǎn)的智能體需要經(jīng)過距離目標(biāo)較近智能體的目標(biāo)點(diǎn)才能到達(dá)自已的目標(biāo)點(diǎn)時(shí)，就會(huì)發(fā)生目標(biāo)沖突，其中，圖2（c）表示有旁路可選的情況，圖2（d）表示無旁路可選，只能找臨時(shí)?？奎c(diǎn)的情況。

2.1基于沖突搜索算法框架

CBS是一種兩級(jí)路徑搜索算法，下層進(jìn)行路徑搜索，為智能體尋找最優(yōu)路徑。若多個(gè)智能體的最優(yōu)路徑互相沖突，則調(diào)用上層算法，構(gòu)建二叉約束樹（constrainttree，CT），通過添加約束條件解決沖突。

在CBS算法中， N_sol 中包含了所有智能體的路徑集合，N_conf 中包含了 N_sol 的全部沖突。元組 a_i，a_j，v，t 表示智能體a_i 和 a_j 在 Φ_t 時(shí)刻位于同一個(gè)頂點(diǎn) 處，如果智能體 a_i 在 χ_t 時(shí)刻的約束條件是 a_i，v，t ，代表其在 χ_t 時(shí)刻占據(jù)頂點(diǎn) ，以此避免沖突。如圖3所示，智能體1、2的最短路徑在 t=1 時(shí)刻都占據(jù)b1頂點(diǎn)，因此通過添加約束對(duì)CT節(jié)點(diǎn)進(jìn)行擴(kuò)展，避免發(fā)生沖突。如圖4所示，分別為兩個(gè)智能體制定約束條件，實(shí)現(xiàn)兩個(gè)智能體最優(yōu)無沖突路徑的規(guī)劃。

2.2關(guān)鍵通道沖突檢測策略

針對(duì)多智能體在狹窄環(huán)境關(guān)鍵通道上的沖突，CBS算法通過二叉樹分支進(jìn)行沖突檢測，當(dāng)二叉樹規(guī)模龐大時(shí)，智能體尋路效率低下。針對(duì)該問題，本文提出基于視場的多值決策沖突檢測策略。用多值決策圖（multi-valuedecisiondiagram，MDD）表示智能體所有可行的路徑集合，在MDD基礎(chǔ)上引人視場表示智能體通信范圍，實(shí)現(xiàn)智能體之間的通信，減少?zèng)_突的數(shù)量，避免二叉樹分支，可以有效提高算法的求解效率。

2.2.1路徑存儲(chǔ)策略

傳統(tǒng)CBS算法解決的沖突是從 N_conf 中隨機(jī)選的，不能識(shí)別出智能體之間的所有沖突，可能面臨兩個(gè)智能體之間有源源不斷沖突出現(xiàn)的問題，因此在CBS的基礎(chǔ)上引入MDD。

MDD是一個(gè)有向無環(huán)圖，圖中每一個(gè)節(jié)點(diǎn)代表智能體在柵格圖中可行的節(jié)點(diǎn)。柵格圖中每個(gè)智能體都有自己的MDD，一個(gè)智能體的MDD就代表該智能體在滿足約束條件下所有可能的路徑集合。

智能體可行節(jié)點(diǎn)的探索采用以智能體當(dāng)前位置為中心，上、下、左、右四個(gè)方向的四領(lǐng)域搜索策略。如圖5所示，以智能體1為中心，箭頭代表智能體1搜索可行節(jié)點(diǎn)的四個(gè)方向。圖6展示了智能體通往目標(biāo)點(diǎn)的所有可行節(jié)點(diǎn)，其中智能體1的目標(biāo)位置占據(jù)了關(guān)鍵通道，導(dǎo)致智能體2、3無法到達(dá)目標(biāo)點(diǎn)，所以圖中MDD1在到達(dá)目標(biāo)點(diǎn)之后依舊進(jìn)行了可行節(jié)點(diǎn)的探索，以確保智能體2、3可以到達(dá)目標(biāo)點(diǎn)。

算法1是以MDD形式存儲(chǔ)每個(gè)智能體路徑的偽代碼。

算法1 MDD存儲(chǔ)智能體路徑

a）創(chuàng)建根節(jié)點(diǎn)。首先，通過調(diào)用MDDNode類創(chuàng)建根節(jié)點(diǎn)。根節(jié)點(diǎn)-root包含了問題地圖、智能體的目標(biāo)和起始狀態(tài)信息。

b）初始化數(shù)據(jù)結(jié)構(gòu)。使用self.-nodes存儲(chǔ)所有節(jié)點(diǎn)，將根節(jié)點(diǎn)-root添加到-nodes中。同時(shí)，使用MDDQueue類管理待處理的節(jié)點(diǎn)，將根節(jié)點(diǎn)添加到frontier中。

c）循環(huán)擴(kuò)展節(jié)點(diǎn)。使用while循環(huán)處理frontier中的節(jié)點(diǎn)，直到frontier為空為止。

d）時(shí)間步排序。每次從frontier中取出一個(gè)節(jié)點(diǎn)cur-node，并根據(jù)時(shí)間步進(jìn)行排序，以時(shí)間步較小的節(jié)點(diǎn)優(yōu)先。

e）判斷時(shí)間步是否超過最大時(shí)間成本。如果當(dāng)前節(jié)點(diǎn)的時(shí)間步超過了預(yù)設(shè)的最大成本-cost，則返回true，表示構(gòu)建過程需要提前終止。

f）達(dá)到目標(biāo)時(shí)間步。如果當(dāng)前節(jié)點(diǎn)的時(shí)間步等于-costcur，則進(jìn)行目標(biāo)測試。如果當(dāng)前節(jié)點(diǎn)滿足目標(biāo)測試條件-node.goal，則將該節(jié)點(diǎn)標(biāo)記為-test，并調(diào)用-goal-nodebuild-children-descendant（cur-node）構(gòu)建其后代節(jié)點(diǎn)。

g）擴(kuò)展節(jié)點(diǎn)。對(duì)當(dāng)前節(jié)點(diǎn)cur-node進(jìn)行擴(kuò)展，生成其可能的后繼節(jié)點(diǎn)expanded-nodes。

h）處理擴(kuò)展節(jié)點(diǎn)。從上、下、左、右四個(gè)維度遍歷，除去障礙物，遍歷擴(kuò)展得到的每個(gè)節(jié)點(diǎn)node。

如果self.-nodes中已包含該節(jié)點(diǎn)node，則將當(dāng)前節(jié)點(diǎn)cur-node添加為其父節(jié)點(diǎn)；

否則，將該節(jié)點(diǎn)node添加到frontier中，并將其加入self.-nodes。

i）返回結(jié)果。如果成功找到滿足條件的路徑，則返回true；否則，

返回1。

其中，時(shí)間步表示智能體到達(dá)目標(biāo)點(diǎn)需要的時(shí)間長度；最大時(shí)間成本表示智能體到達(dá)目標(biāo)點(diǎn)需要的最大時(shí)間長度；MDDQueue類是以隊(duì)列的形式遍歷frontier中存儲(chǔ)的節(jié)點(diǎn)；目標(biāo)測試條件-node.goal是當(dāng)智能體到達(dá)目標(biāo)節(jié)點(diǎn)的時(shí)間步長與-costcur表示到達(dá)目標(biāo)點(diǎn)需要的時(shí)間步長相等時(shí)，說明智能體順利到達(dá)目標(biāo)點(diǎn)，即通過測試。擴(kuò)展節(jié)點(diǎn)是為了讓到達(dá)目標(biāo)點(diǎn)但擋在關(guān)鍵通道上的智能體尋找臨時(shí)停靠點(diǎn)時(shí)遍歷的。

2.2.2智能體通信策略

在狹窄環(huán)境中，不是所有的沖突都是點(diǎn)沖突，如圖6中的陰影部分，智能體1與2、3之間如果不能實(shí)現(xiàn)通信，就會(huì)增加智能體的尋路代價(jià)，甚至尋路失敗。對(duì)此，在MDD的基礎(chǔ)上引用視場來模擬智能體可以觀察到的環(huán)境范圍，智能體的視場大小決定了智能體的通信范圍和感知能力。

視場采用以智能體為中心的 5×5 正方形區(qū)域，在感知范圍內(nèi)，掃描到有其他智能體存在，就遍歷感知范圍內(nèi)所有智能體的MDD，實(shí)現(xiàn)通信范圍內(nèi)智能體之間信息共享。圖7中各個(gè)顏色的框代表相同顏色智能體的通信范圍。在 t=0 時(shí)刻，智能體1、2在對(duì)方的通信范圍內(nèi)，可以實(shí)現(xiàn)通信，但不能與智能體3實(shí)現(xiàn)通信，但當(dāng)智能體3與1、2都需要通過圖中用紅色方框表示的關(guān)鍵區(qū)域時(shí)（見電子版），可以確保它們之間實(shí)現(xiàn)通信。

2.3多值決策回溯沖突規(guī)避策略

為盡量減少狹窄環(huán)境下關(guān)鍵通道中智能體之間沖突數(shù)量，提出了多值決策回溯沖突規(guī)避策略。若智能體有其他可選路徑，則為其搜索一條不影響其他智能體最優(yōu)路徑的有效旁路，且該有效旁路為最優(yōu)或次優(yōu)路徑；若智能體無其他路徑可選，則為關(guān)鍵通道上的智能體選擇臨時(shí)?？奎c(diǎn)，使所有智能體都能到達(dá)目標(biāo)點(diǎn)。

2.3.1次優(yōu)路徑的選取策略

狹窄環(huán)境下智能體在經(jīng)過關(guān)鍵通道時(shí)會(huì)發(fā)生沖突，為了規(guī)避此沖突，需要在不影響其他智能體最優(yōu)路徑的前提下，判斷發(fā)生沖突的智能體是否有其他最優(yōu)路徑可行，若沒有，要在保證避免沖突的前提下為智能體尋找一個(gè)次優(yōu)路徑。

通過遍歷發(fā)生沖突智能體的MDD節(jié)點(diǎn)，觀察是否有其他最優(yōu)路徑，若沒有，選擇一條次優(yōu)路徑。圖8所示為圖2（c）的MDD，從圖中深色區(qū)域可以看出智能體1、2的最優(yōu)路徑是重合的，且智能體1在到達(dá)目標(biāo)點(diǎn)d3之后停在了智能體2通往目標(biāo)點(diǎn)的關(guān)鍵通道上，遍歷兩個(gè)智能體的MDD，發(fā)現(xiàn)智能體1沒有其他最優(yōu)路徑，即為智能體2找到一條次優(yōu)路徑，兩個(gè)智能體都可以順利到達(dá)目標(biāo)點(diǎn)。

2.3.2臨時(shí)?？奎c(diǎn)的選取策略

狹窄環(huán)境下，關(guān)鍵通道中發(fā)生沖突的智能體可能沒有其他次優(yōu)路徑，如果不能規(guī)避這種沖突，可能會(huì)導(dǎo)致死鎖，智能體最終因超時(shí)尋路失敗。因此，在不影響其他智能體最優(yōu)路徑的前提下，需要為擋在關(guān)鍵通道上的智能體搜索一個(gè)不影響其他智能體路徑的臨時(shí)?？奎c(diǎn)，以保證所有智能體都能順利到達(dá)目標(biāo)點(diǎn)。

圖2（d）中兩個(gè)智能體的MDD如圖9所示。兩個(gè)智能體的最短路徑都要經(jīng)過b2-c2-d2這三個(gè)節(jié)點(diǎn)，智能體1到目標(biāo)點(diǎn)d2后擋住了智能體2前往目標(biāo)點(diǎn)e2的唯一通道，遍歷兩個(gè)智能體的MDD，如圖9（a）所示，兩個(gè)智能體都沒有到達(dá)目標(biāo)點(diǎn)的其他路徑，即需要遍歷智能體1的MDD節(jié)點(diǎn)，為智能體1找一個(gè)臨時(shí)停靠點(diǎn)進(jìn)行避讓，停靠時(shí)間由智能體2通過關(guān)鍵通道的時(shí)間決定。首先彈出節(jié)點(diǎn)a2，在時(shí)間段[0，1]上智能體1和2之間存在lt;1，2，[a2，b2]，[0，1]gt;沖突，a2節(jié)點(diǎn)舍棄，繼而彈出c1節(jié)點(diǎn)，c1節(jié)點(diǎn)對(duì)智能體2的最優(yōu)路徑?jīng)]有影響，選定c2節(jié)點(diǎn)作為智能體1的臨時(shí)?？奎c(diǎn)，重新為智能體1規(guī)劃路徑。如圖9（b）所示，智能體1在 t=2 時(shí)刻在臨時(shí)?？奎c(diǎn)c1處進(jìn)行避讓，讓智能體2優(yōu)先通過節(jié)點(diǎn)c2，完成兩個(gè)智能體的路徑規(guī)劃。

2.3.3避免死鎖的等待策略

狹窄環(huán)境下，關(guān)鍵通道作為智能體到達(dá)目標(biāo)點(diǎn)的唯一通道，如果多個(gè)智能體同時(shí)通過且目標(biāo)點(diǎn)位于相反的位置，智能體之間容易產(chǎn)生死鎖。為了規(guī)避這種沖突，讓其中一個(gè)智能體執(zhí)行等待策略。在保證一個(gè)智能體按原先規(guī)劃好的最優(yōu)路徑行駛的前提下，其他智能體等待爭奪共享資源的時(shí)間步長，如果等待時(shí)間超過了這個(gè)時(shí)間閾值，就給全部智能體重新規(guī)劃路徑。

發(fā)生沖突的智能體在關(guān)鍵通道中無其他可選路徑和臨時(shí)停靠點(diǎn)可以躲避，如圖2（a）所示的沖突。通過掃描圖中智能體的MDD，如圖10所示，深色節(jié)點(diǎn)a1-b1-c1-d1是兩個(gè)智能體通往目標(biāo)的必經(jīng)之路，這段資源就是兩個(gè)智能體的共享資源。智能體在時(shí)間 t=1，2，3，4 這四個(gè)時(shí)間步進(jìn)行共享資源的爭奪，解決辦法就是讓智能體1在 t=0 時(shí)刻在a2處等待爭奪資源時(shí)間步長，即智能體1在等到 t=5 時(shí)刻才可以開始前往目標(biāo)點(diǎn)。

2.3.4實(shí)驗(yàn)示例及有效旁路規(guī)劃算法

圖11是一個(gè)多智能體路徑規(guī)劃示例，在 5×5 的柵格圖中，深色區(qū)域?yàn)檎系K物，標(biāo)有數(shù)字的圓圈代表智能體的起始位置，相同顏色的圓圈分別代表智能體的目標(biāo)位置。

t=0 時(shí)，智能體1、2、3分別位于起始位置d1、d0、a3，智能體2的目標(biāo)位置c3擋住了智能體1通往目標(biāo)位置d3的唯一通道，所以在 t=1 時(shí)，智能體2向右行駛了一格到了e0位置。t=3，t=4 時(shí)智能體1、2分別擋住了智能體3通往目標(biāo)點(diǎn)的唯一通路，所以在時(shí)間段[3，4]，智能體3在臨時(shí)?？奎c(diǎn)b1處等待， t=5 時(shí)，智能體1和2通過關(guān)鍵位置b0，完成所有智能體的路徑規(guī)劃。

為了對(duì)多值決策沖突規(guī)避策略中智能體如何尋找有效旁路有更直觀的了解，用算法2進(jìn)行補(bǔ)充說明。

算法2有效旁路規(guī)劃

a）get-paths中存儲(chǔ)了智能體的路徑集合，get-cost記錄智能體尋找到的最優(yōu)路徑代價(jià)，使用detect-collision判斷兩個(gè)智能體是否有共享資源的競爭；

如果成功找到路徑，返回true，否則，進(jìn)入下一步判斷。

b）掃描frontier，從智能體在經(jīng)過共享資源時(shí)間步之前的擴(kuò)展節(jié)點(diǎn)中搜索其他可選節(jié)點(diǎn)，判斷智能體是否有可替代的最優(yōu)路徑，即-cost相同的路徑；

如果成功找到路徑，返回true，

否則，判斷共享資源時(shí)間步之前的擴(kuò)展節(jié)點(diǎn)是否有后續(xù)節(jié)點(diǎn)，可以使智能體到達(dá)目標(biāo)點(diǎn)；

如果成功找到路徑，返回true，

否則，判斷共享資源時(shí)間步之前的擴(kuò)展節(jié)點(diǎn)是否有不影響另一個(gè)智能體前進(jìn)的節(jié)點(diǎn)，供智能體暫時(shí)躲避；

如果成功找到路徑，返回true，

否則，判斷共享資源時(shí)間步之間的擴(kuò)展節(jié)點(diǎn)是否有不影響另一個(gè)智能體前進(jìn)的節(jié)點(diǎn)，供智能體暫時(shí)躲避；

如果成功找到路徑，返回true，否則，智能體智能原地等待共享資源時(shí)間步長度的時(shí)間步長；

如果成功找到路徑，返回true，否則，為智能體重新規(guī)劃；

若找到，則跳轉(zhuǎn)至步驟c）；否則，跳轉(zhuǎn)至步驟d）。

c）搜索結(jié)束，為智能體成功找到無沖突路徑。

d）搜索結(jié)束，尋路失敗。

其中，最優(yōu)路徑代價(jià)表示智能體到達(dá)目標(biāo)點(diǎn)的最優(yōu)路徑所經(jīng)過的柵格數(shù)量；當(dāng)兩個(gè)智能體在同一時(shí)間經(jīng)過同一路徑，這段路徑就稱為共享資源；共享資源時(shí)間步表示一個(gè)智能體經(jīng)過這段共享資源需要的時(shí)間步長；-cost表示智能體到達(dá)目標(biāo)點(diǎn)的最優(yōu)路徑所需要的路徑代價(jià)。

3實(shí)驗(yàn)仿真與分析

為了驗(yàn)證所提算法的有效性，實(shí)驗(yàn)采用不同類型的地圖進(jìn)行性能測試。仿真實(shí)驗(yàn)在 Intel^B CoreTM i5-8300H CPU @ （202.30GHz，8GB 的PC機(jī)上以Python程序運(yùn)行。選用的地圖為四連通的二維柵格地圖，其中柵格單元的大小剛好被單個(gè)智能體占用。假設(shè)智能體保持一個(gè)單位時(shí)間運(yùn)行一個(gè)柵格勻速運(yùn)動(dòng)，規(guī)定運(yùn)行時(shí)間為 10min ，超出運(yùn)行時(shí)間為尋路失敗。

3.1固定任務(wù)的多個(gè)智能體路徑求解

第一部分實(shí)驗(yàn)采用 10×10 的四聯(lián)通柵格地圖，如圖12所示，圓形代表智能體起始位置，方框代表智能體終點(diǎn)位置，共包含了10個(gè)智能體，陰影區(qū)域代表障礙物，空白區(qū)域代表智能體運(yùn)行通道。從圖中可以看出，智能體2、5、7的目標(biāo)位置停留在關(guān)鍵通道上，智能體9、10必須要經(jīng)過唯一的關(guān)鍵通道才能到達(dá)目標(biāo)點(diǎn)。在這種情況下，隨著關(guān)鍵通道上智能體數(shù)量的增加，智能體之間的沖突會(huì)逐漸加劇。

在圖12所示的地圖上，將本文算法EBPCS-FOV與CBS、CBS-BP進(jìn)行了對(duì)比。當(dāng)沒有智能體2、5時(shí)，結(jié)果如表1所示，本文算法加入視場實(shí)現(xiàn)智能體7、8之間的通信，可以更快實(shí)現(xiàn)約束，找到最優(yōu)路徑。加入智能體2之后，智能體2的目標(biāo)位置占據(jù)了智能體1到達(dá)目標(biāo)點(diǎn)的關(guān)鍵通道，從表2看出，本文在通信的基礎(chǔ)上，為關(guān)鍵通道上的智能體找到臨時(shí)停靠點(diǎn)，減少了CT分支和運(yùn)行時(shí)間。加入智能體5之后，智能體5的目標(biāo)點(diǎn)在智能體3、4通往目標(biāo)點(diǎn)的關(guān)鍵通道上，且智能體3、4需要交換順序才能到達(dá)各自的目標(biāo)點(diǎn)，加劇了智能體之間的沖突，運(yùn)行結(jié)果如表3所示。本文通過引入臨時(shí)停靠點(diǎn)和等待策略實(shí)現(xiàn)了多智能體路徑規(guī)劃，CBS-BP與CBS均不能在規(guī)定時(shí)間內(nèi)完成所有智能體的路徑規(guī)劃。本文算法通過視場實(shí)現(xiàn)了智能體之間的通信，避免智能體探索無效路徑，減少了路徑代價(jià)；加入臨時(shí)?？奎c(diǎn)和等待策略，減少了智能體之間沖突的發(fā)生，使CT數(shù)減少，縮短了運(yùn)行時(shí)間。

表1占據(jù)1個(gè)關(guān)鍵通道的求解結(jié)果

其中，運(yùn)行時(shí)間表示智能體找到最優(yōu)路徑的時(shí)間；CT數(shù)表示智能體尋路時(shí)的二叉樹分支數(shù)；路徑代價(jià)表示智能體從起始點(diǎn)到目標(biāo)點(diǎn)經(jīng)過的柵格數(shù)量。

3.2基準(zhǔn)環(huán)境下多個(gè)智能體路徑求解

為了驗(yàn)證復(fù)雜環(huán)境下EBPCS-FOV的有效性，采用基準(zhǔn)地圖[24]進(jìn)行了進(jìn)一步實(shí)驗(yàn)。如圖13所示，分別采用maze-128-128-10迷宮地圖和random-64-64-10隨機(jī)地圖，對(duì)不同數(shù)量的智能體，進(jìn)行25次不同起始點(diǎn)到目標(biāo)點(diǎn)的路徑搜索并取平均值，分別使用CBS-BP和EBPCS-FOV算法進(jìn)行測試。

在圖14（a）的實(shí)驗(yàn)地圖中，共采用了6組實(shí)驗(yàn)數(shù)據(jù)，可以看出，智能體隨機(jī)分布在地圖各處。當(dāng)智能體數(shù)量較少時(shí)，智能體之間發(fā)生的沖突數(shù)量較少，智能體尋路運(yùn)行時(shí)間和產(chǎn)生的CT分支數(shù)也都比較少，尋路成功率高。隨著智能體數(shù)量的增加，EBPCS-FOV通過視場實(shí)現(xiàn)智能體之間的通信，并加入有效旁路以及臨時(shí)?？奎c(diǎn)策略為狹窄環(huán)境下關(guān)鍵通道中的智能體找到有效的旁路，有效減少了智能體之間沖突數(shù)量，避免CT分支，提高了智能體尋路的成功率。如圖15所示，random-64-64-10和maze-128-128-10地圖中平均成功率相較于CBS-BP分別提高了 10% 和 15.2% ，相較于CBS分別提高了 15.3% 和26.4% ，如圖16（a）17（a）所示，減少了CT分支數(shù)和運(yùn)行時(shí)間。

圖13（b）所示的地圖中，共設(shè)置了5組實(shí)驗(yàn)數(shù)據(jù)，圖14（b）為智能體在地圖中運(yùn)行的結(jié)果。從圖16（b）17（b）可以看出，智能體數(shù)量較少時(shí)，CBS-BP和EBPCS-FOV的運(yùn)行時(shí)間和CT分支數(shù)沒有太大的區(qū)別，當(dāng)智能體數(shù)量超過20個(gè)時(shí)，EBPCS-FOV所提出的有效旁路以及避讓策略可以有效減少CT分支數(shù)和運(yùn)行時(shí)間，智能體之間的沖突有效解決使得成功率也有所提升。

4結(jié)束語

在狹窄路段環(huán)境中，多個(gè)智能體無法規(guī)避關(guān)鍵通道上的沖突，導(dǎo)致智能體尋路效率低，提出了基于視場的沖突搜索有效旁路規(guī)劃算法。在MDD基礎(chǔ)上引入視場實(shí)現(xiàn)智能體之間的通信，通過MDD為阻礙關(guān)鍵通道的智能體找到次優(yōu)路徑或臨時(shí)等待位置作為有效的旁路進(jìn)行避讓，提高了狹窄環(huán)境下多個(gè)智能體在關(guān)鍵通道中的尋路效率，可用于多個(gè)智能體在復(fù)雜環(huán)境下運(yùn)送貨物的場景。未來將考慮在實(shí)際應(yīng)用場景中進(jìn)行多智能體路徑規(guī)劃的研究。

參考文獻(xiàn)：

[1]王子晗，童向榮．基于沖突搜索的多智能體路徑規(guī)劃研究進(jìn)展 [J]．計(jì)算機(jī)科學(xué)，2023，50（6）：358-368．（Wang Zihan，Tong Xiangrong.Research progress of multi-agent path finding based on conflict-based search algorithms [J]. Computer Science，2023， 50（6）：358-368.）

[2]Wen Licheng，Liu Yong，Li Hongliang. CL-MAPF：multi-agent path finding for car-like robots with kinematic and spatiotemporal constraints[J].Robotics and Autonomous Systems，2022，150： 103997.

[3]LamE，Le Bodic P，Harabor D，etal.Branch-and-cut-and-price for multi-agent path finding[J].Computers amp; Operations Research，2022，144：105809.

[4]Li Jiaoyang，TinkaA，Kiesel S，etal.Lifelong multi-agent path findinginlarge-scalewarehouses[C]//ProcofAAAIConferenceon Artificial Intelligence.2021：11272-11281.

[5]Hu Hongtao，Yang Xurui，Xiao Shichang，et al．Anti-conflict AGV path planning in automated container terminals based on multi-agent reinforcement learning[J].International Journal of Production Research，2023，61（1）：65-80.

[6]Yin Hesheng，Pei Shuo，Xu Lei，et al.Review of research on multirobot visual simultaneous localization and mapping[J].Journal of Mechanical Engineering，2022，58（11）：11-36.

[7]Jiao Lei，Peng Zhihong，Xi Lele，et al.Multi-agent coverage path planning via proximity interaction and cooperation [J]. IEEE Sensors Journal，2022，22（6）：6196-6207.

[8]Zhang Han，Yao Mingze，Liu Ziang，et al.A hierarchical approach tomulti-agent path finding[C]//Proc of International Symposium on Combinatorial Search．2021：209-211.

[9]LeeH，MotesJ，Morales M，et al.Parallel hierarchical composition conflict-based search for optimal multi-agent pathfinding[J].IEEE Robotics and Automation Letters，2021，6（4）：7001-7008.

[10]Chan SH，Li Jiaoyang，Gange G，et al.ECBS with flex distribution for bounded-suboptimal multi-agent path finding[C]//Proc of International Symposium on Combinatorial Search，2021：159-161.

[11]Rahman M，Alam M A，Islam M M，et al.An adaptive agent-specific sub-optimal bounding approach for multi-agent path finding [J]. IEEEAccess，2022，10：22226-22237.

[12]Li Jiaoyang，Ruml W，Koenig S.EECBS：a bounded-suboptimal search formulti-agentpath finding[C]//Procof AAAI Conference onArtificial Intelligence.2021：12353-12362.

[13］戴天倫，李博涵，臧亞磊，等.PORP：面向無人駕駛的路徑規(guī)劃 并行優(yōu)化策略[J]．浙江大學(xué)學(xué)報(bào)：工學(xué)版，2022，56（2）：329- 337.（Dai Tianlun，Li Bohan， Zang Yalei，etal.PORP：paralel optimization strategy of route planning for self-driving vehicles [J]. Joumal of Zhejiang University：Engineering Science，2022， 56（2）：329-337.）

[14］溫惠英，元昱青，林譯峰．考慮道路負(fù)載均衡的碼頭多AGV無 沖突路徑規(guī)劃［J]．華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2023， 51（10）： 1-10.（Wen Huiying，Yuan Yuqing，Lin Yifeng. Conflictfree path planning for multi-AGVs in automated terminals considering road load balancing[J]．Journal of South China University of Technology：Natural Science Edition，2023，51（10）：1-10.）

[15］宣志瑋，毛劍琳，張凱翔.CBS框架下面向復(fù)雜地圖的低拓展度 A^* 算法[J]．電子學(xué)報(bào)，2022，50（8）：1943-1950.（Xuan Zhiwei，Mao Jianlin，Zhang Kaixiang.Low-expansion A^* algorithm based on CBS framework for complex map[J].Acta Electronica Sinica，2022，50（8）：1943-1950.）

[16］遲勝凱，謝永芳，陳曉方，等．基于障礙物代價(jià)勢(shì)場的移動(dòng)機(jī)器 人避障算法[J]．北京航空航天大學(xué)學(xué)報(bào)，2022，48（11）：2289- 2303.（Chi Shengkai， Xie Yongfang， Chen Xiaofang，et al. Obstacle avoidance method of mobile robot based on obstacle cost potential field [J]. Journal of Beijing University of Aeronautics and Astronautics，2022，48（11）： 2289-20303.）

[17］王卓然，文家燕，謝廣明，等．基于改進(jìn)CBS算法的多智能體路 徑規(guī)劃[J]．智能系統(tǒng)學(xué)報(bào)，2023，18（6）：1336-1343.（Wang Zhuoran，Wen Jiayan，Xie Guangming，et al.Multi-agent path planning based on improved CBS algorithm[J]. CAAl Trans on Inteligent Systems，2023，18（6）：1336-1343.）

[18］岳榮康，丁行，江海，等．基于互斥鎖傳播的多智能體路徑規(guī)劃 算法［J]．計(jì)算機(jī)工程，2023，49（12）：103-110，120.（Yue Rongkang，Ding Hang，Jiang Hai，et al.Multi-agent pathfinding algorithm based on mutex propagation[J].Computer Engineering， 2023，49（12）：103-110，120.）

[19]Li Jiaoyang，Harabor D， Stuckey PJ，et al.Pairwise symmetryreasoning for multi-agentpath findingsearch[J]．Artificial Inteligence，2021，301：103574.

[20] Zhang Han，Li Jiaoyang，Surynek P，et al. Multi-agent path finding with mutex propagation[J].Artificial Intelligence，2022，311：103766.

[21］張洪琳，吳耀華，胡金昌，等．一種基于改進(jìn)沖突搜索的多機(jī)器 人路徑規(guī)劃算法[J].控制與決策，2023，38（5）：1327-1335. （Zhang Honglin，Wu Yaohua，Hu Jinchang，et al.A multi-robot path finding algorithm based on improved conflict search[J].Control and Decision，2023，38（5）：1327-1335.）

[22］閆星宇，王妮婭，毛劍琳，等．基于沖突優(yōu)先級(jí)變次優(yōu)因子的 EECBS 多機(jī)器人路徑規(guī)劃[J]．系統(tǒng)仿真學(xué)報(bào)，2024，36（11）： 2662-2673.（Yan Xingyu，Wang Niya，Mao Jianlin，et al. EECBS multi-robot path planning based on conflict priority changing suboptimal factor[J].Journal of System Simulation，2024，36（11）： 2662-2673.）

［23］楊鄒，毛劍琳，李大焱，等．基于沖突概率反饋的CBS分層多機(jī) 器人路徑規(guī)劃[J/OL]．計(jì)算機(jī)集成制造系統(tǒng)．（2023-07-31）. https：//kns.cnki.net/kcms/detail/11.5946.TP.20230728.1657. 004.html.（Yang Zou，Mao Jianlin，Li Dayan，et al.CBS hierarchical multi-robot path planning based on conflict probability feedback [J/OL]. Computer Integrated Manufacturing Systems.（2023- 07-31）．https：//kns.cnki. net/kcms/detail/11.5946.TP. 20230728.1657.004.html.）

[24] Stern R，Sturtevant N，F(xiàn)elner A，et al.Multi-agent pathfinding：definitions，variants，and benchmarks [C]//Proc of International Symposium on Combinatorial Search. 2019： 151-158.