基于地圖分解AGV全局路徑規(guī)劃新方法

關鍵詞：地圖分解；A*算法；麥克納姆輪；路徑優(yōu)化；全局路徑規(guī)劃 中圖分類號：TP242 文獻標志碼：A 文章編號：1001-3695（2025）08-015-2355-09 doi： 10.19734/j.issn.1001-3695.2024.12.0527

New approach to global path planning for AGV based on map decomposition

Wang Hanga?，Huang Xixiab，Liang Donga （a.InstituteofLgticsSieeamp;Engneing，bKeyLbatoryofspoIdustryfrineechologamp;ontrolEngeringh hai Maritime University，Shanghai ，China）

Abstract：Toaddress the issues of excessivenode traversal，poorpath smoohness，and longsearch time intraditional A^* algorithmsforautomated guidedvehicle（AGV）path planning inlarge-scalescenarios，thispaperproposedathree-layerblock search A^* algorithm（Blocks- ?A^? ）and developed a Mecanum-wheel AGV to resolve kinematic constraints.The Blocks-A* algorithmdecomposedthemapinto largerregions（blocks），replacing node-level searches with block-leveloperations.Firstly， it divided free spaceandrestricted space basedon priormap information，partitions free space intotriangles，performed node equivalence for these triangles，and constructed adjacency matrices. Secondly，the Blocks-A algorithm calculated the optimal blockchanneltogeneratesuboptimalpathsusingmidpointsofadjacentrangleboundaries.Thirdly，itappliedlinearprogamming or quadraticprogrammingoptimizationmodels according to specificscenarios togenerate thefinaloptimalpath.Experimentalesultsdemonstratethattheproposedalgorithmsignificantlyreduces traversednodes inlarge-scaleenvironments，improves pathsmoothnesstobetter meetAGVmotionrequirements，and enhances search eficiency.This method isspecifically applicable to large-scale path planning problems.

Key words：map decomposition；A* algorithm； Mecanum-wheel；path optimization； global path planning

0 引言

AGV作為智能物流和智能制造系統(tǒng)中的核心組成部分，近年來在多樣化應用場景和復雜實際需求驅動下得到了廣泛部署和發(fā)展，被應用于超大型電商與倉儲物流中心、國際港口自動化、汽車制造超級工廠和航空樞紐等大型場景下貨物運輸，例如京東“亞洲一號\"智能物流園，Tesla超級工廠“無軌化生產(chǎn)線”以及上海洋山港碼頭[1]。傳統(tǒng)的AGV機動性較差，其搭載的普通輪子只能進行前后施力，因此難以在不改變車頭朝向的情況下實現(xiàn)左右平移和小角度的轉向。裝載麥克納姆輪的AGV作為全方位移動平臺，可實現(xiàn)車輛在不改變機體朝向的情況下進行全方位運動，包括前進、后退、側向移動以及繞任意半徑的旋轉[2.3]。路徑規(guī)劃研究中通常將運動體簡化為質點模型，忽略實際的運動學約束。麥克納姆輪憑借其獨特的運動結構[4]，能夠有效應對運動學約束問題，尤其在路徑規(guī)劃中處理極端拐點時展現(xiàn)出優(yōu)異性能。

全局路徑規(guī)劃是一種用于機器人、自動導引車和無人機等系統(tǒng)的技術，旨在從起始位置找到一條通往目標位置的最優(yōu)路徑，同時避開障礙物并滿足特定的約束條件[5]。全局路徑規(guī)劃算法主要包括基于柵格的路徑規(guī)劃算法（ A^* 算法[6]Dijkstra算法[]）基于圖的路徑規(guī)劃算法（PRM算法[8]，RRT算法等采樣算法）基于線性約束條件下線性目標函數(shù)極值的數(shù)學優(yōu)化模型，如線性規(guī)劃（linear programming，LP）和二次規(guī)劃（quadraticprogramming，QP），多用于無人機路徑規(guī)劃問題[10]。目前，大多數(shù)全局路徑規(guī)劃算法的研究模型主要基于小規(guī)模地圖構建，大型場景中高效處理不斷擴展的搜索空間并求解最優(yōu)路徑的問題，仍處于探索與突破階段。

為解決大型場景下的路徑規(guī)劃問題，眾多學者對適用性較高的 A^* 尋路算法進行改進。趙曉等人[11]將 A^* 算法和跳點搜索算法相結合，通過減少遍歷列表中的節(jié)點數(shù)，使得改進后的A*算法尋路速度提升了 200% ；虞立斌等人[1]將 A^* 算法的八鄰域拓展增加為十二鄰域拓展并采用改進的雙向搜索機制，搜索速度得到了明顯的提升。Li等人[13]提出在應對大任務空間路徑規(guī)劃將雙向交替搜索（BAS）策略引人 A^* 算法中，減少冗余節(jié)點。林桂娟等人[14]提出了大型復雜場景下基于全局信息關鍵點提取的跳點搜索算法并考慮了U型陷阱的解決策略，提升了路徑搜索的效率。但隨著地圖規(guī)模的進一步增大，單純從減少冗余節(jié)點和拓寬鄰域搜索范圍來改進A*算法，并不能根本上解決因地圖較大帶來的遍歷節(jié)點過多導致的內(nèi)存開銷大這一問題。

因此，在大型地圖路徑規(guī)劃中，通過對地圖進行預處理，隨后采用全局路徑規(guī)劃算法獲得次優(yōu)路徑，最后結合優(yōu)化算法進一步生成最優(yōu)路徑。此方法的核心思路在于通過合理的地圖預處理降低復雜度，為后續(xù)路徑優(yōu)化奠定基礎。目前，多采用單元分解法的方式降低大型地圖的復雜程度，單元分解方法包括MAKLINK圖論[15]、Boustrophedon分解[16]、四叉樹法[17]和Morse分解[18]。李軍濤等人[19]提出了改進融合APF算法的RRT*算法，能夠有效解決船舶在海洋等大場景環(huán)境下的路徑規(guī)劃問題。Meysami等人[20]提出將大型環(huán)境劃分為多個規(guī)則的瓦片子區(qū)域，創(chuàng)建一個大型的合成地圖數(shù)據(jù)庫，并通過卷積神經(jīng)網(wǎng)絡（CNN）模型來預測每個瓦片的最佳表示方法，最后使用 A^* 算法在混合網(wǎng)格地圖上進行路徑搜索。Zhang等人[21]使用網(wǎng)格方法將游戲地圖劃分為相同大小的矩形網(wǎng)格，提出了基于區(qū)域搜索的改進 A^* 算法，有效解決了傳統(tǒng) A^* 算法中的路徑彎曲和耗時問題，但未涉及路徑的進一步優(yōu)化。江純興等人[22]使用廣義維諾圖（GVG）從環(huán)境地圖中構建拓撲圖，結合 A^* 算法進行尋路，通過并行搜索子區(qū)域內(nèi)的路徑減少搜索空間和時間，并利用VSO算法平滑路徑、減少路徑長度和提升路徑質量。武星等人[23]運用Delaunay三角剖分、對偶Voronoi圖構造及無向圖鄰接矩陣變換等方法，將柵格地圖變換為Voronoi骨架圖，隨后基于骨架頂點使用 A^* 算法進行全局路徑規(guī)劃。Mac等人[24]提出結合三角分解和Dijkstra算法的方法，并利用約束多目標粒子群優(yōu)化算法優(yōu)化路徑的長度和平滑度，生成最優(yōu)路徑。文獻[25，26]采用MAKLINK圖理論建立自由空間模型，結合Dijkstra算法與蟻群算法或改進模擬退火算法與遺傳算法的混合算法生成最優(yōu)路徑。MAKLINK圖分解存在單元形狀不規(guī)則的問題，無法應對多連通凹多邊形障礙物的情況。Li等人[27]引入了凹面多邊形凸分解法，克服了自由空間法的局限性，并通過人工蜂群算法（ABC）在復雜地圖中尋找全局最優(yōu)路徑。然而，上述研究未驗證在地圖規(guī)模和環(huán)境復雜度增大情況下算法的有效性，且智能種群優(yōu)化算法常存在收斂速度慢、易陷入局部最優(yōu)和參數(shù)敏感性高等問題。

基于以上文獻研究，針對大場景下A*算法的弊端，本文提出分層的Blocks-A*算法，將地圖分解、路徑搜索算法和路徑優(yōu)化三者結合，并構建了基于麥克納姆輪的全方位移動平臺AGV模型。首先，將地圖中所有無障礙物區(qū)域劃分為三角形，確定起始節(jié)點和終止節(jié)點，將所有三角形進行節(jié)點等效化，節(jié)點的位置為三角形質心處的坐標，完成地圖的預處理環(huán)節(jié)。然后，采用Blocks-A*算法查找從起始點到終止點的所有等效節(jié)點，并存儲節(jié)點對應的三角形信息，構建基于三角形連接關系的通道（即最優(yōu)塊通道），次優(yōu)路徑通過連接相鄰三角形邊界的中點生成。最后，利用線性規(guī)劃LP或二次規(guī)劃QP優(yōu)化模型生成最優(yōu)路徑，其中LP適用于簡單的線性優(yōu)化問題，QP則用于處理復雜環(huán)境中的路徑優(yōu)化。

綜上，本文對于AGV路徑規(guī)劃問題的主要貢獻有：

a）構建了搭載麥克納姆輪的全方位移動平臺的AGV模型，靈活處理路徑生成過程中的極端拐點，提高了AGV環(huán)境的適應能力;b）利用Delaunay三角剖分的數(shù)學理論提出了三角分解的地圖分解算法，提出了基于三角分解的Blocks-A*算法，三角分解算法相比于其他單元分解方法能夠得到更穩(wěn)定的結構；c）實現(xiàn)了啟發(fā)式搜索算法和線性優(yōu)化模型的融合，通過改變地圖規(guī)模驗證了本文算法的有效性，相比智能種群優(yōu)化算法，該方法具有更高的求解效率和更好的全局最優(yōu)性。

1全方位移動平臺模型構建

全方位移動平臺指的是四輪均搭載麥克納姆輪的AGV，采用四驅的動力系統(tǒng)，每個麥克納姆輪由直流電機獨立驅動，四輪之間的速度和方向相互獨立不受影響。麥克納姆輪旋轉過程中，地面施加在輥子上的摩擦力可以分解為軸向力和圓周力，其中圓周力使輥子繞自身軸芯旋轉，四個麥克納姆輪上各輥子所受的軸向力生成合力以驅動麥克納姆輪移動平臺。

圖1中的斜線表示麥克納姆輪輥子的安裝方式， α 表示輪輻軸線和輥子軸線的安裝夾角， α=45^° 。將AGV等效為矩形，取其幾何中心點 o 作為平臺的中心，并作為全局坐標系XOY的原點。以右上角麥克納姆輪為研究對象， O₁ 作為麥克納姆輪的中心點構建 X₁O₁Y₁ 局部坐標系， V_i?ωi?R 分別表示麥克納姆輪輥子的線速度、角速度和麥克納姆輪和半徑（ i=1，2，3 ，4）。 L₁，L₂ 分別表示麥克納姆輪中心點到全局坐標系 X 軸和 Y 軸的直線距離 ，L₃ 為平臺的寬度， V_x，V_y，ω 分別表示AGV處于o 點的實際運行速度在 X 軸和 Y 軸的分量以及此點角速度。在速度轉換過程中忽略機械特性所帶來的系統(tǒng)誤差，通過以上參數(shù)構建出基于麥克納姆輪的全方位移動平臺的逆運動學模型[28]：

將式（1）進行逆變換，測量每個麥克納姆輪的角速度 ω_i 求解以 o 點為中心的全方位移動平臺的線速度和角速度，逆變換得前向運動學模型：

圖1麥克納姆輪AGV運動學模型Fig.1Mecanum-wheel AGV kinematic modeling

通過獨立控制四個驅動電機的角速度，麥克納姆輪實現(xiàn)了平臺的全方位移動能力，從而有效應對路徑規(guī)劃中極端拐點的問題，該模型避免了依賴于傳統(tǒng)的極端拐點消除方法，為路徑優(yōu)化問題提供了新的研究思路。

2基于三角分解的地圖預處理

2.1 地圖分解算法對比

目前國內(nèi)外主流的地圖分解方法包括Boustrophedon分解、四叉樹法、MAKLINK圖論分解、三角分解等，但各有局限性，如圖2所示。

圖2地圖分解方法

如表1所示，Boustrophedon分解生成的梯形單元僅適用于簡單凸障礙物場景，無法處理多連通凹多邊形障礙物，并且當障礙物頂點密集時，分解出的單元呈細長狀會導致路徑折點較多；四叉樹法通過遞歸分割生成矩形單元，但在復雜障礙物邊界處單元數(shù)量激增，導致搜索效率下降，不適用于路徑規(guī)劃研究；MAKLINK圖論分解生成不規(guī)則多邊形單元，路徑連貫性較差。相比之下，本文采用的三角分解方法通過Delaunay三角剖分生成穩(wěn)定的三角形，能有效適應復雜障礙物環(huán)境，同時減少冗余單元數(shù)量，有利于后續(xù)塊搜索和路徑優(yōu)化。

表1不同地圖分解方法特性

Tab.1 Characteristics of different map decomposition method

2.2三角分解算法問題定義

地圖預處理先定義整個地圖區(qū)域為狀態(tài)空間 S_all 。其中，不含障礙物的區(qū)域被稱為自由空間 S_free ，其余區(qū)域定義為限制空間 S_limit 。AGV在 S_free 中可自由運動，不受障礙物的約束，在S_limit 內(nèi)，由于存在障礙物，AGV無法通行。

分解的三角形只形成于 S_free ，將 S_free 劃分為若干個三角形t_i，S_limit 由若干個多邊形障礙物 O_j 組成。起始節(jié)點為 N_start ，終止節(jié)點為 N_goal，N_start 和 N_goal 是在路徑規(guī)劃過程中預先設定的節(jié)點。因此，地圖預處理定義的各個區(qū)域和節(jié)點關系如下：

2.3三角分解算法實現(xiàn)

a）初始化環(huán)境和障礙物，定義環(huán)境邊界和障礙物位置，將障礙物頂點信息以矩陣形式存儲于頂點矩陣 X 中，并按順序排列形成障礙物多邊形。

b）采用Delaunay三角剖分對環(huán)境中的自由空間進行分解，該剖分在考慮障礙物邊界的約束下生成不重疊的三角形單元。

c）通過檢查每個三角形的質心是否位于障礙物內(nèi)或環(huán)境邊界之外，從而剔除不滿足條件的三角形，僅保留位于自由空間 S_free 內(nèi)的有效三角形單元。

d）將篩選出的有效三角形存儲在三角形矩陣 c 中，并生成鄰接矩陣adj，adj用于標記三角形單元之間的相鄰關系。相鄰三角形通過共用兩個頂點進行識別，最終返回有效的三角形單元矩陣和鄰接矩陣。

在 10m×20m 簡單地圖中進行地圖分解的示意，得到S_free={t_1，t₂，…，t₁₅} 1 S_limit={O₁，O₂} ，如圖3（a）所示。為了進一步驗證分解的效果，接著將地圖規(guī)模擴大至 50m×100m 和100m×200m ，驗證復雜情況下地圖的分解效果，得到兩組數(shù)據(jù)。第一組數(shù)據(jù) S_free={t₁，t₂，…，t₃₂} S_limit={O₁，…，O_s} ；第二組數(shù)據(jù) S_free={t₁，t₂，…，t₆₃} S_limit={O₁，…，O₁₀} 。不同環(huán)境三角分解效果對比如圖3（b）（c）所示，隨著障礙物數(shù)量的增加以及地圖規(guī)模的擴大，分解出的三角塊仍然能保持較高的質量，并且三角塊的數(shù)量波動較小。

2.4三角形節(jié)點化等效

在自由空間中將三角形 t_i 等效成節(jié)點 N_k（k=1，…，i） ，取t_i 的質心位置作為 N_κ 的坐標，質心計算公式如下：

其中： （x_Nk，y_Nk） 為等效化后的三角形質心的坐標， （x_ij，y_ij） 為三角形 t_i 的三個頂點的坐標。通過將所有等效化節(jié)點 N_k 相連可構建如圖4所示的路徑規(guī)劃通道網(wǎng)絡圖。

圖3地圖預處理示意圖

圖4等效化節(jié)點通道網(wǎng)絡

Fig.4Equivalent node channel network

當兩個三角形共享一條公共邊界時，將這兩個三角形定義為鄰接三角形，并將其共享邊界的等效化節(jié)點定義為鄰接節(jié)點。基于鄰接節(jié)點的連接關系，可進一步構建鄰接矩陣，描述節(jié)點之間的相鄰關系。

鄰接矩陣 adj_[n×n] 用于表示節(jié)點之間的連通關系，其中 n 表示三角形的個數(shù)，設置鄰接節(jié)點之間連通的代價為1（可通行），非鄰接節(jié)點之間連通的代價為 ∞ （不可通行），構建鄰接矩陣表達式如下：

其中： adj[i][j] 表示鄰接矩陣中節(jié)點 N_i 和 N_j 之間的代價值； E 表示路徑規(guī)劃過程中當前節(jié)點周圍鄰接節(jié)點的集合，由圖4可知集合 E 最多包含三個元素。

圖5表示地圖分解后的某一局部區(qū)域，構建出通過三角形等效化節(jié)點后的鄰接矩陣 adj_[5×5] 。假設當前路徑搜索到三角形 t₃ 位置，則可以通過三角形 t₃ 對應的等效化節(jié)點 N₃ 確定與該位置相連的可通行節(jié)點。該位置在矩陣中對應第三行（列），存在 t₂ 和 t₄ 兩個可通行的位置，通行代價值為adj[3][2]，adj[3][4]，根據(jù)總代價值選擇最佳通道位置。

Fig.5Partial decomposition diagramandadjacencymatrix

3 Blocks-A*算法搜索次優(yōu)路徑

基于塊搜索的 A^* （Blocks- ?A^* ）算法是一種改進的全局路徑規(guī)劃方法，相較于傳統(tǒng) A^* 算法，其主要優(yōu)勢在于提高了搜索效率，減少了遍歷節(jié)點數(shù)量，特別適用于大場景的路徑規(guī)劃任務。Blocks-A*算法的基本原理在于將地圖預處理分解得到的三角形代替?zhèn)鹘y(tǒng) A^* 算法的遍歷節(jié)點。算法通過在三角形單元之間執(zhí)行 A^* 搜索，尋找與路徑相關的三角形塊，從而實現(xiàn)地圖的離散化表達。基于這些離散化的節(jié)點構建連續(xù)的塊通道，最終形成基于邊界線中點的次優(yōu)路徑，此方法通過減少搜索空間來提高路徑規(guī)劃的計算效率。

3.1傳統(tǒng) A^* 算法

傳統(tǒng)的 A^* 算法是一種基于柵格的路徑搜索算法，融合了最佳優(yōu)先搜索算法和Dijkstra算法的特點，并通過啟發(fā)式函數(shù)引導搜索過程。其基本原理如下：首先初始化包含起始節(jié)點的開放列表openlist和關閉列表 closedlist 在路徑搜索過程中，為AGV的每一步運動設定代價值，通過鄰域搜索的方式將搜索到的點加入openlist中。隨后，從openlist中選擇代價值最小的節(jié)點作為下一步的擴展節(jié)點，并將當前節(jié)點移入closedlist。該過程不斷重復，沿著朝向目標節(jié)點的方向逐步擴展，直至找到從起點到目標點的所有路徑節(jié)點，生成最短路徑。評判路徑優(yōu)劣的指標包括路徑長度、路徑搜索時間、搜索中遍歷的節(jié)點數(shù)量等。

A^* 算法的評估函數(shù)表示形式如下：

圖5局部分解圖及其鄰接矩陣

其中 用于評估節(jié)點的優(yōu)先級； g（n） 表示起始節(jié)點到當前節(jié)點的實際代價值； h（n） 用于估計當前節(jié)點到終止節(jié)點的代價值。 f（n） 的變化是 A^* 算法改進的關鍵，因為代價評估函數(shù)直接影響著算法運行效率和規(guī)劃的路徑優(yōu)劣。常用的兩點之間的移動代價函數(shù)有曼哈頓距離和歐幾里德距離，本文采用歐幾里德距離作為移動代價函數(shù)。

曼哈頓距離：

D_Manhattan=∣x₂-x₁∣+∣y₂-y₁∣

歐幾里德距離：

由于傳統(tǒng) A^* 算法自身的局限性，在大規(guī)模地圖中，即使調整啟發(fā)式評估函數(shù)或改進搜索方式，算法的節(jié)點遍歷數(shù)量仍會呈指數(shù)級增長，從而導致openlist和closedlist積累大量余節(jié)點，增加了不必要的搜索開銷，計算復雜度顯著提升，進而延長路徑搜索的時間，限制了 A^* 算法在大場景中的實時性與高效性。

3.2Blocks-A*最優(yōu)塊通道的實現(xiàn)

通過地圖預處理和三角形節(jié)點等效化，應用Blocks ?A^* 算法搜索從起始節(jié)點至終止節(jié)點的最優(yōu)塊通道，圖6為最優(yōu)塊通道的實現(xiàn)示意圖。

圖6（a）中為塊搜索的實現(xiàn)過程圖，Blocks-A*通過等效節(jié)點的方式遍歷鄰接的三角塊，從起始節(jié)點 N_start 出發(fā)一直遍歷到終止節(jié)點 N_goal 結束，圖中綠色塊為可行通道或起始節(jié)點所在通道，黃色三角塊表示開放列表openlist中待訪問通道，灰色三角塊代表closedlist關閉列表中的已訪問通道，紅色為終止節(jié)點所在通道（見電子版）。圖6（b）為通過Blocks-A*算法尋找到符合要求的三角塊，將所有符合要求的三角塊連接在一起，形成如圖所示的最優(yōu)塊通道。

程序流程如圖7所示，以下為最優(yōu)塊通道的實現(xiàn)步驟：

a）初始化列表openlist和 closedlist ，分別用于存儲待訪問的鄰接節(jié)點和已訪問的節(jié)點對應的塊。

b）首先檢查起始節(jié)點和終止節(jié)點是否位于同一個三角形塊內(nèi)。若滿足該條件，則直接輸出路徑，無須進一步搜索：否則，將起始節(jié)點加入openlist，作為搜索過程的起點。

c）若openlist為空，則算法終止。

d）基于鄰接矩陣信息，將起始節(jié)點周圍鄰接節(jié)點 N_k 加入到openlist，并遍歷openlist中的所有元素，根據(jù)評估函數(shù) f（n） 的最小值選取子鄰接節(jié)點，將當前鄰接節(jié)點移出openlist加入到closed list 列表中。

e）將上一點作為父鄰接節(jié)點，接著搜索周圍的鄰接節(jié)點N_k ，更新 h（n）Ω_?g（n） 的值。

f）重復步驟c） ～e ），朝著終止節(jié)點 N_goal 的方向，直到終止節(jié)點加入到openlist中，openlist為空，算法終止，形成最優(yōu)塊。

3.3基于中點的次優(yōu)路徑

選取 20m×20m 的地圖進行初步理論驗證，基于Blocks-A^* 算法獲得最優(yōu)塊通道，選取相鄰三角形邊界的中點 m_i 作為路徑點，并依次連接起始節(jié)點至終止節(jié)點的各路徑點，從而構建次優(yōu)路徑的節(jié)點集合 {M_i} 。

圖7最優(yōu)塊通道生成流程

次優(yōu)路徑軌跡如圖8所示，本文的路徑規(guī)劃是以搭載麥克納姆輪的全方位平臺AGV當作質點為前提，考慮AGV的實際尺寸，為確保AGV與障礙物之間的安全距離，在圖8中設置膨脹后的障礙物，膨脹尺寸如式（9）所示。

圖8次優(yōu)路徑Fig.8Suboptimal path

4路徑優(yōu)化

目前研究的路徑優(yōu)化多依賴于群智能優(yōu)化算法，這些方法雖能處理非線性約束問題，但其固有缺陷顯著。群智能優(yōu)化算法需多次迭代生成種群；計算成本隨問題規(guī)模指數(shù)增長，隨機搜索機制導致解的質量不穩(wěn)定；算法性能高度依賴超參數(shù)調優(yōu)（如交叉率、變異率），參數(shù)敏感性高，不再適用于處理大型地圖路徑優(yōu)化問題[29，30]

因此，采用線性規(guī)劃（LP）和二次規(guī)劃（QP）對次優(yōu)路徑進行優(yōu)化處理。與群智能優(yōu)化算法相比，LP和QP方法能夠保證求得全局最優(yōu)解，數(shù)學模型結構相對簡潔，且約束條件和目標函數(shù)的定義更加直觀。此外，該方法具備明確的收斂標準和終正條件，求解過程可預測，因而在路徑優(yōu)化問題中展現(xiàn)出良好的性能與可靠性。

4.1線性規(guī)劃LP生成最優(yōu)軌跡

線性規(guī)劃是數(shù)學規(guī)劃的一個重要分支，也是解決最優(yōu)化問題的關鍵方法。用線性規(guī)劃方法求解最優(yōu)路徑問題，需要構建決策變量 x_n ，目標函數(shù) Max （or Min ） Z 以及約束條件s.t.線性規(guī)劃LP數(shù)學模型一般形式：

線性規(guī)劃求最優(yōu)路徑中每一段路徑之和的最小值，采用如下標準式：

MinZ=c^Tx

其中： c=[c₁，c₂，…，c_n]^T 為目標函數(shù)的系數(shù)矩陣，也稱為價值向量； 為決策變量組成的向量; A= （a_ij）_m×n 為約束條件的系數(shù)矩陣； b=[b₁，b₂，…，b_m]^T 為約束條件的常數(shù)向量。利用單純形法，在滿足約束條件的情況下獲得可行解，最后通過目標函數(shù)達到總路徑長度最短的路徑點的集合，即可得到最優(yōu)解。

將次優(yōu)路徑的中點集合 {M_i} 通過線性規(guī)劃后得到的優(yōu)化節(jié)點集合定義為 {P_i}_J'i 表示鄰接三角形公共邊界線的點，也是在這條邊界線段中點的優(yōu)化點，因此 p_i 滿足如下位置約束：

圖9為路徑部分截取，優(yōu)化后的點 p_i（x，y） 受邊界線段兩個端點 P_i1（p_i1（x），p_i1（y） 和 P_i2（p_i2（x） p_i2（y） ）的坐標限制。

圖9路徑節(jié)點約束關系 Fig.9Path node constraint relationships

線性規(guī)劃優(yōu)化算法需針對起始節(jié)點與終止節(jié)點所在三角塊的位置進行分類處理：

圖10（a）表示起始節(jié)點 N_start（x_start，y_start ）和終止節(jié)點 N_goal 號 （x_goal，y_goal） 經(jīng)過三角分解后位于同一個三角形中，在這種特定情況下，直接連接起始節(jié)點 N_start 和終止節(jié)點 N_goal ，無須構造約束條件進行線性規(guī)劃來優(yōu)化路徑。此時，直接計算路徑長度 L

圖 10（b） 表示起始節(jié)點 N_start 和終止節(jié)點 N_goal 分別處于任意兩個鄰接三角形中，此情形應考慮兩類子情況;連接 N_start 和 N_goal 形成路徑，若這條路徑未穿過限制空間 S_limit ，則按照圖10（a）情況處理;否則，需要優(yōu)化唯一的路徑中點。定義第一段（ m₁ ）和最后一段（ ?m₁N_goal? 在 x 和 y 方向上的約束條件，并添加到約束矩陣 A 和向量 中，最后求解唯一最優(yōu)節(jié)點 p₁ 。

圖10（c）表示典型情況，起始節(jié)點 N_start 和終止節(jié)點 N_goal 均不位于任意兩個鄰接三角形中。在此情況下，處理方法與前述第二種情況相似，除了處理起始節(jié)點到第一段及終止節(jié)點到最后一段的約束條件外，還需構造中間段的約束條件。所有約束條件添加至約束矩陣 A 和向量 中，最終得出最優(yōu)節(jié)點集合{P_i} 。

在設計優(yōu)化算法過程中，決策變量取路徑點的坐標，對每個坐標中的 x，y 變量分別進行處理，并被單獨設定為決策變量。約束條件根據(jù)式（13）構建，以確保每個優(yōu)化后的點的 x，y 坐標符合邊界線段的約束。目標函數(shù)通過計算每段路徑的歐幾里德距離，以求得各段長度的總和，從而使其值達到最小化。優(yōu)化后的路徑節(jié)點集合為 {P_i} ，優(yōu)化后的路徑如圖11所示。

圖11LP最優(yōu)路徑

Fig.11LP optimal path

與基于中點形成的次優(yōu)路徑相比，優(yōu)化后的路徑長度得到明顯縮短，且路徑平滑度得到明顯提升。搜索的時間略有增加，但相較于總體規(guī)劃時間，該時間增加可忽略不計。例如，圖示中點 p₇ 屬于極端拐點，本文采用的基于麥克納姆輪的全向移動平臺AGV能夠在該位置實現(xiàn)原地 90^° 轉向，無須通過圓弧型的局部優(yōu)化，從而進一步縮短路徑長度。

4.2二次規(guī)劃QP生成最優(yōu)軌跡

在生成次優(yōu)路徑后，可通過二次規(guī)劃模型對路徑進一步優(yōu)化。二次規(guī)劃QP是優(yōu)化問題的一種特殊形式，其目標函數(shù)為二次形式，約束條件為線性表達。二次規(guī)劃優(yōu)化問題的標準式為

式（15）中定義的 參數(shù)代表的含義均與線性規(guī)劃LP定義的參數(shù)含義相同。約束條件保持與線性規(guī)劃相同；目標函數(shù)增加了一個二次項 表示對稱的正定矩陣，這里定義正定矩陣 中元素是路徑節(jié)點之間距離和彎曲程度的組合，反映了路徑的平滑性和長度最小化的優(yōu)化目標。二次項使得目標函數(shù)的曲面呈現(xiàn)為一個拋物面，優(yōu)化問題具有唯一的最優(yōu)解。

線性規(guī)劃是二次規(guī)劃的特例，當二次規(guī)劃問題中的正定矩陣 為零矩陣時， 劃問題。線性規(guī)劃可以被看作是二次規(guī)劃的一種特殊情況，因此QP比LP更具靈活性，能夠處理更多復雜的實際問題。

通過二次規(guī)劃QP優(yōu)化路徑可以得到最優(yōu)節(jié)點集合 {Q_i} ，優(yōu)化后的路徑如圖12所示。

圖12QP最優(yōu)路徑Fig.12QP optimal path

4.3 LP和QP優(yōu)化模型對比

本研究同時采用了線性規(guī)劃LP和二次規(guī)劃QP對Blocks-A^* 算法生成的次優(yōu)路徑進行優(yōu)化。鑒于LP較高的計算效率與實現(xiàn)的簡便性，其適合于快速求解路徑優(yōu)化問題。LP在搜索時間和路徑長度上表現(xiàn)良好，然而，優(yōu)化后的路徑存在少量的極端拐點。相比之下，QP方法通過構建兼顧路徑平滑性與路徑長度最小化的目標函數(shù)，顯著提升了路徑的平滑性和整體質量，優(yōu)化結果更加符合實際應用需求，但計算復雜性較高。

因此，在具體場景中選擇適當?shù)膬?yōu)化方法需綜合考慮應用需求與計算資源。LP方法適用于問題規(guī)模較小或網(wǎng)格分辨率較高的場景，因其計算效率較高但在路徑細化方面存在不足。而QP方法適用于要求更高、路徑質量或復雜度更高的模型優(yōu)化，盡管其計算開銷較大，但能夠提供更為優(yōu)質且符合實際需求的路徑規(guī)劃結果。

5 仿真實驗分析

5.1 實驗設置

為驗證所提算法在不同條件下的性能表現(xiàn)，本文設計了多種規(guī)模的測試環(huán)境，分別在中小型地圖：地圖一（ 50m×50m ，地圖二（ 100m×100m ）；大型地圖，即地圖三（ 200m×200m ）和地圖四（ 500m×500m ）中進行對比實驗，通過增加障礙物數(shù)量提升地圖的復雜性，以全面評估所提算法的有效性和通用性。設置了五組不同算法的在測試環(huán)境下的仿真對比實驗，分別為：結合線性規(guī)劃優(yōu)化的Blocks- ?A^* 算法（Blocks ?A^*+LP ）；結合二次規(guī)劃優(yōu)化的Blocks-A*算法（ Blocks-A^*+QP） ;文獻[16］中的Boustrophedon算法；傳統(tǒng) A^* 算法（網(wǎng)格分辨率設置為1 m×1?m， ；文獻19中的 RRT^?+APF 算法。

對比實驗采用路徑總長度、算法搜索時間和遍歷節(jié)點數(shù)量作為路徑規(guī)劃有效性的評價指標。使用不同復雜場景下的地圖來驗證算法的通用性，比較本文提出的Blocks -AΩ^?Σ+LP 算法和Blocks ?A^*+QP 算法與文獻［16］中Boustrophedon分解算法、傳統(tǒng) A^* 算法和RRT* +APF 算法在不同環(huán)境中的性能表現(xiàn)，實驗結果如圖 13～16 所示。

圖14地圖二中不同算法仿真路徑規(guī)劃圖

Fig.14Simulation of different algorithmsfor path planningin map 2

圖16地圖四不同算法仿真路徑規(guī)劃圖

Fig.16Simulation ofdifferent algorithmsforpath planningin map 4

5.2 實驗結果

通過對不同環(huán)境下仿真路徑規(guī)劃結果的分析可知，BlocksA^*+LP 算法在中小規(guī)模地圖上表現(xiàn)出色，能夠有效完成路徑規(guī)劃任務。Blocks-A Φ^*+QP 算法在優(yōu)化模型增加能反映路徑節(jié)點之間距離和彎曲程度的組合正定矩陣 后，在路徑平滑度方面顯著優(yōu)于其他三種算法，并且生成的路徑長度最短，適用于大場景路徑規(guī)劃需求。基于Boustrophedon算法分解單元數(shù)量少于三角分解，具有較高的計算和存儲效率，但Boustrophedon分解的形狀受到限制，其分解精度不如三角分解，在處理復雜邊界和不規(guī)則地形時，該算法忽略地圖的局部細節(jié)，導致路徑不夠精確。Boustrophedon算法盡管在路徑長度上表現(xiàn)良好，但生成的路徑曲折并且存在大量的拐點，不符合AGV運動學約束。 RRT^?+APF 解決了傳統(tǒng) A^* 算法在大型地圖上因遍歷節(jié)點多導致的搜索時間長的問題，同時融合的人工勢場法使得隨機搜索樹算法的收斂性更強，能夠適應大型地圖下的路徑規(guī)劃問題，但隨機搜索樹算法生成的路徑平滑性差且路徑較長，不適合AGV在實際場景下的運行和作業(yè)。因此本文提出的基于地圖三角分解的算法適合對路徑精度和平滑度要求較高的場景，尤其是在處理大型的復雜地形和不規(guī)則地圖時，具有更優(yōu)的性能表現(xiàn)。

中小型地圖仿真參數(shù)如表2所示，由數(shù)據(jù)分析可知本文提出的Blocks- A^*+LP 和Blocks- A^*+QP 性能指標明顯優(yōu)于對比的Boustrophedon、傳統(tǒng) A^* 和RRT* + APF算法。

表2中小型地圖參數(shù)對比

Tab.2Comparison of small and medium map parameters

從搜索時間的角度進行分析，在中小型地圖（ 50m×50m 100m×100m 中， Blocks-A^*+LP 采用了線性規(guī)劃的優(yōu)化模型，顯示出顯著的搜索時間優(yōu)勢。與Blo 、Boustro-phedon、傳統(tǒng) A^* 和 RRT^?+APF 相比， Blocks-A^*+LP 算法在地圖一中的搜索時間減少了 49.0% ， 30.6% 95.3% 96.4% ：在地圖二中減少了 10.0% 38.6% 99.0% 98.8% 。從路徑長度的角度進行分析，Blocks-A* +LP 和Blocks-A*+QP是在傳統(tǒng) A^* 算法的基礎上實現(xiàn)的，因此在中小型地圖中路徑長度相近，這三種算法比Boustrophedon和 RRT* +APF 算法在路徑長度上平均縮短了 6.1% 和 8.6% 。

大型地圖仿真參數(shù)對比如表3所示。從搜索時間的角度進行分析，在大型地圖 （200m×200m，500m×500m） 中，Blocks-A Φ^*+QP 算法采用二次規(guī)劃的優(yōu)化模型，展現(xiàn)出在處理復雜場景中的顯著優(yōu)勢。隨著地圖復雜度的增加，與Blocks-A* +LP 、Boustrophedon、傳統(tǒng) A^* 和 RRT^?+APF 相比，Blocks-A^*+QP 算法在地圖三中，搜索時間分別減少了 19.2% ，44.0% ，99. 6% ？ 98.8% ；在地圖四中，搜索時間分別減少了39.3% 29.5% ， 99.97% ， 99.36% 。在路徑長度方面，Blocks-A^?+QP 算法表現(xiàn)最優(yōu)，與Blocks- ?A^?+LP 、Boustrophedon、傳統(tǒng) A^* 和 RRT^?+APF 相比，Blocks-A* +QP 算法在地圖三中，路徑長度分別縮短了 3.9% ， 6.4% . 0.8% ， 10.6% ;在地圖四中，路徑長度分別縮短了 8.3% ·34.2% 0.9% ， 19.3% 。

表3大型地圖參數(shù)對比

Tab.3Comparison of big map parameters

從遍歷節(jié)點數(shù)上分析，隨著地圖規(guī)模的增大， A^* 算法的遍歷節(jié)點數(shù)呈指數(shù)增長，這也是其計算耗時較長的主要原因，Blocks-A ^?+QP 算法無須構建柵格地圖，因此無遍歷節(jié)點，采用向空間中隨機拋點的方式來延伸根節(jié)點進行搜索路徑。而基于地圖分解的三種算法遍歷節(jié)點數(shù)基本保持穩(wěn)定，未出現(xiàn)顯著波動，且搜索時間都控制在毫秒級別，不受地圖規(guī)模的顯著影響。這一特點凸顯了基于地圖分解的路徑規(guī)劃算法在大規(guī)模場景中的優(yōu)越性。

5.3 實驗總結

綜上所述，本文提出的兩種優(yōu)化算法均展現(xiàn)出良好的路徑規(guī)劃性能。Blocks- A^*+LP 算法在中小型地圖中搜索時間快、路徑較短、響應迅速、靈活性較強。然而，在大型地圖中，其性能有所下降，路徑呈現(xiàn)直角化。為解決此問題，本文進一步提出了Blocks- ??A+QP 算法，通過對比分析，驗證了Blocks- ??A+QP 算法在復雜環(huán)境和大型地圖中的優(yōu)越性。本文算法能夠根據(jù)地圖規(guī)模和復雜程度靈活選擇優(yōu)化方法，有效提升了在不同場景下的尋路性能，較傳統(tǒng) A^* 算法在路徑規(guī)劃上有顯著改進。Boustrophedon分解算法在多邊形障礙物頂點密集時，生成的梯形單元通常呈現(xiàn)細長形態(tài)，導致路徑精度和魯棒性顯著低于三角形分解算法，難以有效應對大型復雜地圖的路徑規(guī)劃需求。RRT^?+APF 算法具備快速性和高收斂性的特點，但形成的路徑不平滑且不是最短路徑。

6結束語

針對大場景下的路徑規(guī)劃，傳統(tǒng)的路徑搜索算法存在難以應對高分辨率地圖、規(guī)劃時間長、遍歷節(jié)點呈指數(shù)倍增長等問題。本研究跳出搜索算法本身的局限性，不再單一追求對于冗余點去除和擴寬多鄰域搜索等方式，而是通過地圖分解方法降低地圖的復雜程度來提高算法搜索效率。

本研究提出了分層式結構的路徑規(guī)劃算法，該方法結合三角單元分解法、 ?A^* 算法、LP和QP路徑優(yōu)化模型，構建了三層結構的Blocks-A*算法。與其他單元分解算法相比，三角單元分解算法能夠生成更加穩(wěn)定的單元塊，通過將單元塊等效為區(qū)域節(jié)點，解決了 A^* 算法在大場景下中遍歷節(jié)點數(shù)量龐大的問題。在生成次優(yōu)路徑后，采用LP和QP優(yōu)化模型進一步提升路徑的平滑度和收斂速度。從實驗驗證中可知，Blocks-A*算法在路徑搜索時間、路徑成本等性能指標上表現(xiàn)出顯著優(yōu)勢，為大地圖下的路徑規(guī)劃問題提供了新的研究方法。此外，基于麥克納姆輪的全方位移動平臺的AGV模型在解決運動學約束方面具有良好的特性，使得該AGV模型能靈活應對復雜多變的環(huán)境。然而，Blocks-A*算法未在真實大場景下進行地圖分解的實驗驗證，對于構建的麥克納姆輪全方位移動平臺在路徑極端拐點的處理上還需進一步分析其資源消耗情況。在未來，將進一步分析Blocks-A*與其他全局路徑優(yōu)化算法結合的效果，同時考慮局部避障算法的融合。

參考文獻：

[1]Wang Wenyuan，PengYun，Xu Xinglu，et al.Smart container port development：recent technologies and research advances [J]. Intelligent Transportation Infrastructure，2023，123（9）：liad022.

[2]黃群軍，謝志江．改進 A^* 算法的麥克納姆輪AGV路徑規(guī)劃［J/ OL].機械科學與技術．（2022-09-14）[2025-03-11]．https：// doi. org/10. 13433/j ：cnki.1003-8728.20200189.（Huang Qunjun，Xie Zhijiang.Improved A* algorithm for Mcnamm round AGV path planning[J/OL].Mechanical Science and Technology for Aerospace Engineering.（2022-09-14）[2025-03-11]. https：// doi.org/10.13433/j.cnki.1003-8728．20200189.）

[3]李金芝，張志安，程志，等．基于全向移動平臺的多機器人編隊 控制研究[J]．計算機仿真，2021，38（2）：326-330，398．（Li Jinzhi，Zhang Zhi’an，Cheng Zhi，et al.Research on multi-robot formation control based on omnidirectional mobileplatform[J]. Computer Simulation，2021，38（2）：326-330，398.）

[4]．陳博翁，范傳康，賀驥．基于麥克納姆輪的全方位移動平臺關鍵 技術研究[J].東方電氣評論，2013，27（4）：7-11.（ChenBoweng，F(xiàn)an Chuankang，HeJi.Key technology research about omnidirectional mobile platform based on Mecanum wheel[J]. Dongfang Electric Review，2013，27（4）：7-11.）

[5]王梓強，胡曉光，李曉筱，等．移動機器人全局路徑規(guī)劃算法綜 述［J]．計算機科學，2021，48（10）：19-29.（Wang Ziqiang，Hu Xiaoguang，Li Xiaoxiao，et al. Overview of global path planningalgorithms for mobile robots[J].Computer Science，2021，48（10）： 19-29.）

[6]HartPE，NilssonNJ，RaphaelB.A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Trans on Systems Science and Cybernetics，1968，4（2）：100-107.

[7]Dijkstra E W.A note on two problems in connexion with graphs[J]. Numerische Mathematik，1959，1（1）：269-271.

[8]KavrakiLE，SvestkaP，LatombeJC，etal.Probabilisticroadmaps for path planning in high-dimensional configuration spaces[J].IEEE Trans on Robotics and Automation，1996，12（4）：566-580.

[9]LaValle S.Rapidly-exploring random trees：a new tool for path planning，Research Report 9811[R].1998.

[10]Peng Chaoda，Qiu Shaojian.A decomposition-based constrained multi-objective evolutionary algorithm with alocal infeasibility utilization mechanism for UAV path planning[J].Applied Soft Computing，2022，118：108495.

[11]趙曉，王錚，黃程侃，等．基于改進 A^* 算法的移動機器人路徑 規(guī)劃［J]．機器人，2018，40（6）：903-910.（Zhao Xiao，Wang Zheng，Huang Chengkan，et al.Mobile robot path planning based on an improved algorithm[J].Robot，2018，40（6）：903-910.）

[12]虞立斌，張億，黃磊，等．雙向 A^* 路徑規(guī)劃算法的鄰域改進方 法研究[J].小型微型計算機系統(tǒng)，2025，46（6）：1312-1318. （YuLibin，ZhangYi，HuangLei，etal.Research on neighborhood improvement method of bidirectional A^* path planning algorithm [J]．Journal of Chinese Computer Systems，2025，46（6）： 1312-1318.）

[13]Li Changgeng，Huang Xia，Ding Jun，etal.Global path planning based on a bidirectional alternating search A^* algorithm for mobile robots[J].Computersamp; Industrial Engineering，2022，168： 108123.

[14］林桂娟，李子涵，王宇．基于全局關鍵點提取的改進 A^* 算法全 局路徑規(guī)劃研究［J]．系統(tǒng)仿真學報，2025，37（3）：667-678. （Lin Guijuan，Li Zihan，Wang Yu.Research on improved A^* algorithm path planningbased on global keypoint extraction [J].Journal of System Simulation，2025，37（3）：667-678.）

[15]Hao Yanling，Shen Zhifeng，Zhao Yuxin.Path planning for aircraft based on MAKLINK graph theory and multi colonyant algorithm [C]//Proc of International Joint Conference on Computational Sciencesand Optimization.Piscataway，NJ：IEEE Press，20O9：232-235.

[16] Choset H. Coverage of known spaces：the Boustrophedon cellular decomposition[J].Autonomous Robots，2000，9（3）：247-253.

[17]Samet H.The quadtree and related hierarchical data structures[J]. ACM Computing Surveys，1984，16（2）：187-260.

[18]AcarEU，Choset H，RizziAA，etal.Morse decompositionsfor coverage tasks [J].The International Journal of Robotics Research，2002，21（4）：331-344.

[19]李軍濤，陳璐瑤，侯星星，等.基于改進APF-RRT算法的無人艇 航跡規(guī)劃[J/OL].復雜系統(tǒng)與復雜性科學.2024.（2024-12- 27）．https：//kns.cnki.net/kcms/detail/37.1402.n.20241225. 1731.004.html．（Li Juntao，Chen Luyao，Hou Xingxing，et al. Path planning of unmanned boat based on improved APF-RRT algorithm[J/OL]. Complex Systems and Complexity Science. 2024.（2024-12-27）. htps：//kns.cnki. net/kcms/detail/37. 1402.n.20241225.1731.004.html.）

[20]MeysamiA，KelouwaniS，CuilliereJC，etal.Anefficientindoor largemap global path planning forrobot navigation[J].Expert SystemswithApplications，2024，248：123388.

[21] Zhang Cheng，Ao Lei， Yang Junsheng，et al. An improved A^* algorithmapplyingtopath planning of games[JJ.Journal ot Pnysics： Conference Series，2020，1631（1）：012068.

[22］江純興，吳鋒．結合維諾區(qū)域分割和路徑優(yōu)化的路徑規(guī)劃算法 [J]．計算機工程與應用，2024，60（10）：311-319．（Jiang Chunxing，Wu Feng. Path planning with Voronoi region segmentation and path optimization[J].Computer Engineeringand Applications，2024，60（10）：311-319.）

[23]武星，李楊志，臧鐵鋼，等．基于Voronoi骨架的移動機器人融合 路徑規(guī)劃[J]．機械工程學報，2025，61（5）：165-177．（Wu Xing，Li Yangzhi，Zang Tiegang，et al.Combined path planning based on Voronoi skeleton for mobile robots[J].Journal of Mechanical Engineering，2025，61（5）：165-177.）

[24]MacTT，CopotC，TranDT，etal.Ahierarchical globalpathplanningapproach for mobile robots based on multi-objectiveparticle swarm optimization[J].Applied Soft Computing，2017，59：68-76.

[25]Tan Guanzheng，He Huan，Aaron S.Global optimal path planning for mobile robot based on improved Dijkstra algorithm and ant system algorithm[J]. Journal of Central South University of Technology，2006，13（1）：80-86.

[26]Liang Yuming，Xu Lihong.Global path planning for mobile robot based genetic algorithm and modified simulated annealing algorithm [C]//Proc of the1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation.New York：ACM Press，2009：303-308.

[27]Li Zhaoying，Zhang Zhao，Liu Hao，et al．A new path planning method based on concave polygon convex decomposition and artificial bee colony algorithm[J]. International Journal of Advanced Robotic Systems，2020，17（1）：894787.

[28］黃曉宇．麥克納姆輪AGV路徑規(guī)劃與軌跡跟蹤算法研究［D]. 杭州：浙江科技學院，2022.（Huang Xiaoyu.Research on path planning and trajectory tracking algorithm of mcnamun wheel AGV [D].Hangzhou：Zhejiang Universityof Science amp; Technology， 2022.）

[29]Liu Lixing，Wang Xu，Yang Xin，et al.Path planning techniques for mobile robots： review and prospect [J]. Expert Systems with Applications，2023，227：120254.

[30]RafaiANA，AdzharN，JainiNI.Areview on path planning and obstacle avoidancealgorithms for autonomousmobilerobots [J]. Journal of Robotics，2022，2022（1）：2538220.