路徑規劃典型算法匯總十篇

序論：好文章的創作是一個不斷探索和完善的過程，我們為您推薦十篇路徑規劃典型算法范例，希望它們能助您一臂之力，提升您的閱讀品質，帶來更深刻的閱讀感受。

篇（1）

中圖分類號 TP242 文獻標識碼 A 文章編號 1674-6708(2009)10-0067-02

路徑規劃是指機器人從起始點到目標點之間找到一條安全無碰的路徑,是機器人領域的重要課題。移動機器人技術研究中的一個重要領域是路徑規劃技術,它分為基于模型的環境已知的全局路徑規劃和基于傳感器的環境未知的局部路徑規劃。本文綜述了移動機器人路徑規劃的發展狀況,對移動機器人路徑規劃技術的發展趨勢進行了展望。

根據機器人工作環境路徑規劃模型可分為兩種:基于模型的全局路徑規劃,這種情況的作業環境的全部信息為已知;基于傳感器的局部路徑規劃,作業環境信息全部未知或部分未知,又稱動態或在線路徑規劃。

1 全局路徑規劃

全局路徑規劃主要方法有:可視圖法、自由空間法、柵格法、拓撲法、神經網絡法等。

1.1 可視圖法

可視圖法視移動機器人為一點,將機器人、目標點和多邊形障礙物的各頂點進行組合連接,并保證這些直線均不與障礙物相交,這就形成了一張圖,稱為可視圖。由于任意兩直線的頂點都是可見的,從起點沿著這些直線到達目標點的所有路徑均是運動物體的無碰路徑。搜索最優路徑的問題就轉化為從起點到目標點經過這些可視直線的最短距離問題。

1.2 拓撲法

拓撲法將規劃空間分割成具有拓撲特征的子空間,根據彼此連通性建立拓撲網絡,在網絡上尋找起始點到目標點的拓撲路徑,最終由拓撲路徑求出幾何路徑。拓撲法基本思想是降維法,即將在高維幾何空間中求路徑的問題轉化為低維拓撲空間中判別連通性的問題。

1.3 柵格法

柵格法將移動機器人工作環境分解成一系列具有二值信息的網格單元,多采用四叉樹或八叉樹表示,并通過優化算法完成路徑搜索,該法以柵格為單位記錄環境信息,有障礙物的地方累積值比較高,移動機器人就會采用優化算法避開。對柵格的改進采用以障礙物為單位記錄的信息量大大減少,克服了柵格法中環境存儲量大的問題。

1.4 自由空間法

自由空間法應用于移動機器人路徑規劃,采用預先定義的如廣義錐形和凸多邊形等基本形狀構造自由空間,并將自由空間表示為連通圖,通過搜索連通圖來進行路徑規劃。自由空間的構造方法是從障礙物的一個頂點開始,依次作其它頂點的鏈接線,刪除不必要的鏈接線,使得鏈接線與障礙物邊界所圍成的每一個自由空間都是面積最大的凸多邊形。連接各鏈接線的中點形成的網絡圖即為機器人可自由運動的路線。

1.5 神經網絡法

可視圖法缺乏靈活性,且不適用于圓形障礙物的路徑規劃問題。神經網絡法用于全局路徑規劃可以解決以上問題。算法定義了整條路徑的總能量函數,相應于路徑長度部分的能量和相應于碰撞函數部分的能量。由于整個能量是各個路徑點函數,因此通過移動每個路徑點,使其朝著能量減少的方向運動,最終便能獲得總能量最小的路徑。

2 局部路徑規劃

局部路徑規劃包括人工勢場法、模糊邏輯算法、神經網絡法、遺傳算法等。

2.1 人工勢場法

人工勢場法基本思想是將移動機器人在環境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產生斥力,目標點產生引力,引力和斥力周圍由一定的算法產生相應的勢,機器人在勢場中受到抽象力作用,抽象力使得機器人繞過障礙物。

2.2 模糊邏輯算法

模糊邏輯算法基于對駕駛員的工作過程觀察研究得出。駕駛員避碰動作并非對環境信息精確計算完成的,而是根據模糊的環境信息,通過查表得到規劃出的信息,完成局部路徑規劃。模糊邏輯算法的優點是克服了勢場法易產生的局部極小問題,對處理未知環境下的規劃問題顯示出很大優越性,對于解決用通常的定量方法來說是很復雜的問題或當外界只能提供定性近似的、不確定信息數據時非常有效。

2.3 神經網絡法

模糊控制算法有諸多優點,但也有固有缺陷:人的經驗不一定完備;輸入量增多時,推理規則或模糊表會急劇膨脹。神經網絡法則另辟蹊徑。路徑規劃是感知空間行為空間的一種映射,映射關系可用不同方法實現,很難用精確數學方程表示,但采用神經網絡易于表示,將傳感器數據作為網絡輸入,由人給定相應場合下期望運動方向角增量作為網絡輸出,由多個選定位姿下的一組數據構成原始樣本集,經過剔除重復或沖突樣本等加工處理,得到最終樣本集。

2.4 遺傳算法

遺傳算法以自然遺傳機制和自然選擇等生物進化理論為基礎,構造了一類隨機化搜索算法。利用選擇、交叉和變異編制控制機構的計算程序,在某種程度上對生物進化過程作數學方式的模擬,只要求適應度函數為正,不要求可導或連續,同時作為并行算法,其隱并行性適用于全局搜索。多數優化算法都是單點搜索,易于陷入局部最優,而遺傳算法卻是一種多點搜索算法,故更有可能搜索到全局最優解。

3 移動機器人路徑規劃技術的發展展望

隨著計算機、傳感器及控制技術的發展,特別是各種新算法不斷涌現,移動機器人路徑規劃技術已經取得了豐碩研究成果。從研究成果看,有以下趨勢:首先,移動機器人路徑規劃的性能指標要求不斷提高,這些性能指標包括實時性、安全性和可達性等;其次,多移動機器人系統的路徑規劃。協調路徑規劃已成為新的研究熱點。隨著應用不斷擴大,移動機器人工作環境復雜度和任務的加重,對其要求不再局限于單臺移動機器人。在動態環境中多移動機器人的合作與單個機器人路徑規劃要很好地統一;再次,多傳感器信息融合用于路徑規劃。移動機器人在動態環境中進行路徑規劃所需信息都是從傳感器得來。單傳感器難以保證輸入信息準確與可靠。此外基于功能/行為的移動機器人路徑規劃,這是研究的新動向之一。

總之,移動機器人的路徑規劃技術已經取得了豐碩成果,但各種方法各有優缺點,也沒有一種方法能適用于任何場合。在研究這一領域時,要結合以前的研究成果,把握發展趨勢,以實用性作為最終目的,這樣就能不斷推動其向前發展。

參考文獻

篇（2）

中圖分類號：TP306文獻標識碼：A文章編號：1009-3044(2008)21-30523-02

An Algorithm Based on Improved A* Restrictions on the Path to Search Regional Planning Approach

XU Zhan-peng, LIN Kai

(Qingdao Technical College Information Institute of Qingdao,Qingdao 266555,China)

Abstract: According to A* algorithm has been given an improved optimal path planning method, this algorithm in accordance with the actual situation of the road network of layered LO at the same time, according to the actual network topology of the region to search for reasonable Restrictions experiment proved that the algorithm in the path planning saving time

Key words: Path planning; Search region; A* algorithm

1 引言

路徑規劃是在車輛行駛前或行駛過程中尋找車輛從起始點到達目的地的最佳行車路線的過程[1], 它屬于智能交通

系統中的最短路徑問題的一個具體應用。

最短路徑規劃產生的路徑分為兩種：距離最短的路徑和時間最短路徑,其中前者相對比較易于實現，但是它容易忽略路徑的具體情況和行車實際環境以及人為因素。因為在實際車輛行駛中要求不但在此路徑上行車距離盡可能短，而且路徑的行車環境盡可能好，即盡量走道路較寬、路面質量較好、紅綠燈較少、紅綠燈設置間隔較大、車流量較小的路徑，避免走行車環境太差的路徑。作者針對最短路徑規劃存在的不足之處 ,根據已有A*算法，給出了一種改進的最優路徑規劃算法，此算法在根據道路的實際情況對路網進行分層的同時，根據實際路網的拓撲特性對搜索區域進行合理的限制。

2 A*算法

A*算法是人工智能中一種典型的啟發式搜索算法．也是路徑規劃算法中的常用算法，它通過選擇合適的估計函數，指導搜索朝著最有希望的方向前進．以期求得最優解限制搜索區域的多層最優路徑規劃算法，A*算法評價函數的定義為[2]：

f(n)=g(n)+h(n) （1）

f(n)是從初始點通過節點n 到達目標點的估價函數；

g(n)是在狀態空間中從初始節點到n節點的實際代價；

h(n)是從節點n到目標節點最佳路徑的估計代價。它決定了搜索的效率和可采納性。對于幾何路網來說，可以取兩點間歐氏距離（直線距離）作為估價值，即

其中，(xd,yd)、(xn,yn)分別為節點n 和目標節點在數字地圖中的坐標。由于估價值h(n)≤n 到目標節點的距離實際值，算法具有可采納性，能得到最優解。[3]

3 改進的A*算法球最短路徑

本文在三個方面對傳統的A*算法進行了更改：1)A*算法提到的權值會根據用戶的不同查詢條件來調用相對應的計算權值的公式；2) 添加了一個判斷過程。當查詢下一個臨近邊的時候首先查詢交通控制策略，判斷是否有管制信息并將相映的點從v中刪除；3) 減少路徑搜索的范圍，以出發點與目的地點連線的中間點為圓心，以兩點之間直線距離的二分之一再加上幾公里為半徑畫圓，在圓范圍內的路徑參加搜索，在圓范圍之外的路徑不參加搜索。

具體實現如下：

創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點，設各個點的權值（也稱為費用值）為g。遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,計算X的估價值[4]。

1)初始的OPEN表僅包含原節點．其費用值g為0，令CLOSED為空表，設其他節點的費用為∞ 。

2)若OPEN表為空．則宣告失敗：否則，選取OPEN表中所有的節點移至CLOSED表，將此CLOSED表作為新的OPEN表。重復第二步，直到深度達到4。

3)對第二步在深度4時形成的OPEN表進行操作，若OPEN表為空．則宣告失敗：否則，選取OPEN表中具有最小權值的節點，并叫做最佳節點NEXT．把NEXT從OPEN表移至CLOSED表．判斷此NEXT是否是一目標節點。若NEXT為目標節點．轉步驟3，若NEXT不是目標節點。則根據地圖數據庫包含的聯接路段屬性擴展并生成NEXT的后繼節點。對于每一個后繼節點n，進行下列過程：

①計算節點n的費用：g(n)= NEXT費用+從NEXT到n的費用

②如果n與OPEN表上的任一節點相同．判斷n是否具有最小的g值。若是最低的g值，用n的費用代替OPEN表中相同的節點費用。且建立匹配節點的后向指針指向NEXT

③如果n在CLOSED表中與一節點相匹配。檢查節點n是否具有最小的g值，如果n具有最小的g值，則用節點n的費用代替匹配節點的費用。并把匹配節點的后向指針指向NEXT。并把該匹配節點移到OPEN表

④如果n不在OPEN表。也不在CLOSED表上，則把n的后向指針指向NEXT。井把n放入OPEN表中。計算節點n的估價函數：f(n)=g(n)+h(n)

例如圖1，為帶權的有向圖。

根據步驟三，針對圖1，算法的具體實現如圖2。

4)重復第三步：

若在深度為7的搜索中找到目標結點且僅有一條路徑，則該路徑為最終路徑，返回；

若在若在深度為7的搜索中找到目標結點并且有多條路徑則回朔，比較找到的路徑費用，取權值最小的作為最終路徑；

若在在深度為7的搜索中未找到任何目標點則跳轉到第五步。

5)從深度為7的搜索中的所有的NEXT節點回朔，即從NEXT的后向指針一直到原節點遍歷節點，最后報告若干條路徑，比較個路徑費用，取費用最小的前100條路徑繼續重復第三步、第四步。由于h函數在滿足h下限得條件下，愈趨近于h效率愈高，因此實際應用中，我們取的是節點到目的點的直線距離保證滿足下限的情況下，盡可能的趨近h。

4 結語

實踐表明基于改進A*算法的限制搜索區域的路徑規劃方法不僅在進行路徑規劃時節省了時間，而且規劃后的路徑大部分道路位于高層路網上，路徑長度與最短路徑長度之比小于1.1,可以被人接受，是行車意義上的最優路徑。

參考文獻：

[1] 付夢印.限制搜索區域的距離最短路徑規劃算法[J].北京理工大學學報,2004(10).

[2] 趙亦林.車輛定位與導航系統[M].北京:電子工業出版社,1999:1-7.

篇（3）

當前，智能電網的發展在一定程度上帶動了電網技術的發展，并且成為了電網技術發展的重要方向。實際上，智能電網的重要組成部分在于智能配電網，智能配電網的主要特征為擁有完備的自愈能力，同時還能夠最大程度的減少電網故障給用戶帶來的影響。而配電網故障的恢復是智能配電網自愈功能實現的重要過程，配電網故障恢復問題主要指配電網發生故障以后，在故障定位與故障隔離的基礎之上，應用一定的故障恢復策略對其進行操作，從而確保供電的平穩與正常。

一、對最佳路徑的分析

配電網故障區域恢復供電的最佳路徑事實上是在故障情況下的配電網絡重構。主要的目的在于，能夠快速的將非故障區域供電恢復，與此同時，還能夠有效的滿足線路負載容量的要求以及線損最小等各個方面的條件。現階段，在配網自動化領域中研究最多的在于怎樣能夠快速的實現故障隔離以及快速的恢復費故障區域的供電技術方法，因此，在恢復路徑的最優化選擇方面出現了較多的研究。

一般而言，配電網故障區域恢復供電的路徑為多目標最佳路徑問題，現階段在最佳路徑問題的研究上較多的便是城市交通網絡中的最短路徑問題的研究。由于問題解決的思路存在著極大的不同點，因此最短路徑問題能夠被分為單元最短路徑算法與基于啟發式搜索最短路徑算法[1]。這與鄧群，孫才新，周駁仍凇恫捎枚態規劃技術實現配電網恢復供電》一文中的觀點極為相似。其中，單元最短路徑算法主要體現在幾個方面，即：

第一，在GIS空間查詢語言方面的最短路徑。該職工路徑的研究方法在當前還停留在理論研究方面，例如在MAX中定義了一套空間查詢語言，該套語言對其完備性給予了相關證明，同時通過舉證的方式，對范圍查詢與時態查詢等進行了應用分析。

雖然，對于GIS空間發展研究GeoSQL為一種有效的處理最短路徑的手段，但是GIS受到數據庫技術發展的制約與影響，導致實際的應用領域和背景的不同，使其和商用之間還有很長的一段距離。

第二，在功能模塊思想路徑方面，需要按照不同的分類方法實施，而單元最短路徑問題的算法能夠被分為很多種，例如神經網絡法與基于人工智能的啟發式搜索算法等，對于不同的背景應用需求和具體軟件應用的環境，各種算法在空間的復雜程度與時間的復雜程度等都有明顯的體現[2]，這與李振坤，周偉杰，錢嘯等在《有源配電網孤島恢復供電及黑啟動策略研究》一文中有著相似的觀點。并且各種算法在故障恢復方法中各具特色。

另外，啟發式搜索最短路徑算法也是一種有效的手段。基于啟發式方向策略最短路徑算法，其中包括空間有效方向的可控參數法，該方法能夠有效的調節相關系數，在有效方向上路徑無效的時候，能夠確保得到有效的路徑。

二、最佳路徑的選擇方法分析

事實上，配電網故障區域恢復供電的最佳路徑并不是簡單的路徑問題，而是多目標最佳路徑問題。為此，在研究配電網非故障區域恢復供電的最佳路徑過程中，需要對其展開綜合的分析。

首先，在多目標分析方面，通常在選擇配電網非故障區域恢復供電最佳路徑的時候，最為重視的目標為：

第一，在恢復供電路徑的過程中，饋線負荷不能過載，同時，還需要確保恢復區域的電壓質量能夠與實際規定的標準要求相吻合。當供電質量可靠性最高的時候，那么恢復的時間將會很短[3]；這與鄧昆英，汪鳳嬌，饒杰等在《智能配電網有功自治互動建模研究》一文中的觀點極為相似。另外，供電過程中，線損最低，證明開關拉合的次數最少，同時現場的操作點也會最少。

第二，在動態規劃技術恢復供電的最短路徑方面需要明確，動態規劃主要是運籌學的一個分支，它是求解決策過程的最優的數學方式。早在很久以前，就已經有研究人員對多階段過程轉化問題轉化為一系列的單階段問題，并且逐一進行求解，這標志著解決這類過程優化問題的新方法的創立，即動態規劃技術。

本文主要將一典型的復雜配電網絡作為研究例子，該連通系包括10個電源點，8個分支點，同時聯絡開關有16個。將其加入到配網潮流方向和典型的運動方式中，將聯絡開關和電源點作為定點，那么可以將其分為26個定點。盡管從數量上頂點比較多，但是由于存在著較為復雜的網絡關系，使得該問題成為一個極為簡單的最短路徑問題[4]。這與楊建在《配電網無功補償系統的關鍵技術研究》一文中的觀點有著相似之處。加之恢復路徑主要指費故障區域相關的聯絡開關與相應路由，為此我們可以將其理解為從不同電源點出發到各個聯絡開關的最短路徑問題，這樣一來，故障恢復工作的實施便簡單的多。

總結

本文主要從兩個方面左手，共同分析了采用動態規劃技術實現配電網恢復供電的方法與效果，一方面著手于最佳路徑的分析，另一方面著手于最佳路徑的選擇方法。從這兩個方面可以看出，利用動態規劃技術去實現配電網恢復供電是一種可行的方法。但是，受到歷史原因的影響，我國城市配電網絡還缺少標準的規范要求，導致配電網常常出現一些事故。因此，恢復配電網供電已經成為當務之急。隨著科技的發展，智能配電網已經被廣泛的應用在供電方面，這為平穩供電提供了一定的保障，同時也為恢復配電網故障供電創建了良好的環境與條件等。

參考文獻

[1]鄧群，孫才新，周駁.采用動態規劃技術實現配電網恢復供電[J].重慶大學學報（自然科學版），2006，29（3）：40-44.

[2]李振坤，周偉杰，錢嘯等.有源配電網孤島恢復供電及黑啟動策略研究[J].電工技術學報，2015，30（21）：67-75.

[3]鄧昆英，汪鳳嬌，饒杰等.智能配電網有功自治互動建模研究[J].機電工程技術，2014，（2）：4-7.

篇（4）

中圖分類號：TP391.4 文獻標志碼：A

Mobile Robot Path Planning Based on an Improved A* Algorithm SUN Wei1， LV Yunfeng1， TANG Hongwei1，2， XUE Min1

（1. College of Electrical and Information Engineering， Hunan University， Changsha 410082， China；

2. Department of Electrical Engineering， Shaoyang University， Shaoyang 422000， China）

Abstract：An improved A* algorithm was presented for global path planning of mobile robot. Firstly， the environment model was described using the grid method， and the preliminary path was obtained by traditional A* algorithm. Secondly， the path planned by A* method was flaw with much redundant points， large path length， and turning angle. The original path was partitioned by tiny step to obtain a series of path point. The finish point from the start point was connected by using straight line in sequence. To decrease the path length and turning angle， the path node can be removed if there are no obstacles on the line. The analysis and comparison between the proposed algorithm， traditional A* algorithm and another improved A* method were then given in the simulation experiment and physical experiments. Additionally， the merits of the proposed algorithm and other algorithms were compared when the obstacle rate， amount of task point， and step length were different. The experiment results show that the proposed algorithm effectively reduces the path length and turning angle.

Key words：mobile robot； path planning； A* algorithm； grid method

路徑規劃問題一直是智能機器人領域的一個研究岬.移動機器人路徑規劃是指機器人基于機載傳感器獲得的環境信息規劃出一條從起點到終點的無碰、安全的可行路徑，并在此基礎上盡可能地優化路徑[1].移動機器人路徑規劃主要解決以下三個問題：第一是規劃出的路徑能使機器人從起點運動到終點；第二是采用相應的算法使得機器人能夠避開環境中的障礙物；第三是在滿足前面兩點要求的基礎上，盡可能地優化機器人的運動軌跡，通常是以規劃出的路徑最短作為優化目標[2].根據機器人對環境信息的感知程度，路徑規劃問題分為全局路徑規劃和局部路徑規劃.前者是指機器人在擁有全部環境信息的基礎上進行的路徑規劃，又稱為離線路徑規劃；后者是指機器人在只有部分環境信息的基礎上進行的路徑規劃，又稱為在線路徑規劃[3].本文主要討論全局路徑規劃.

移動機器人路徑規劃的研究起始于20世紀70年代，到目前為止，已有大量的研究成果.針對全局路徑規劃，主要方法有可視圖法、拓撲學法、人工智能算法和柵格法[4].文獻[5]針對自由空間法當環境發生變化時，需要重新建立網絡連接模型，因而導致路徑規劃算法的環境適應性差和實時性不高的缺陷，提出了一種基于可視圖的全局路徑規劃算法，該方法是直接在環境地圖上進行路徑規劃，從而提高了算法的環境適應能力和實時性.神經網絡作為人工智能中一種重要的算法也被應用到了移動機器人路徑規劃領域，如文獻[6]，首先建立了一個障礙物罰函數的神經網絡模型，并得到了整條路徑的能量函數；然后求得該函數的極小值點，且應用了模擬退火算法避免陷入局部最優；最終對得到的路徑進行了優化，使得路徑更加平滑和安全.除此之外，學者們還采用其它的智能算法來解決移動機器人路徑規劃問題，如模糊邏輯[7-9]，蟻群算法[10]，粒子群優化[11]，遺傳算法[12-13]等.

柵格法是將機器人運動環境建立成一系列具有二值信息的網格模型，再用搜索算法獲取最優路徑.文獻[14]提出了一種改進的A*算法，解決了傳統A*算法得到的路徑包含過多冗余點問題，并得到機器人在拐點處的最小轉折角度.但該算法并沒有減小機器人的路徑長度和轉折角度.文獻[15]針對傳統A*算法得到的路徑折線多、累計轉折角度大的問題，提出了一種平滑A*算法，減少了不必要的路徑點并減小了路徑長度和轉折角度.但只是在原有的路徑點上進行處理，路徑長度和轉折角度的減少量有限.本文提出了另一種改進的A*算法，將進一步地減少移動機器人的總路徑長度和總轉折角度.

1 環境模型描述

眾所周知，移動機器人工作環境地圖建立是路徑規劃中十分重要的一步.地圖建立是指將各種傳感器獲得的環境信息進行融合并抽象成地圖模型[16].采用柵格單位描述二維環境信息非常簡單有效，應用廣泛.所以，本文也使用柵格法來建立移動機器人工作環境模型.如圖1所示，柵格法將機器人工作環境分割成一系列具有相同尺寸的柵格，并將這些柵格分成兩類：可通過柵格和不可通過柵格.圖1中，空白柵格表示可通過柵格，即移動機器人能自由通過的地方，黑色柵格表示不可通過柵格，即該柵格有靜態的障礙物.

為了方便研究又不失一般性，本出以下3點合理的假設：1）障礙物邊界是在實際邊界的基礎上加一個移動機器人安全距離得到的，這樣就可以將移動機器人看作是環境中的一個質點；2）在這有限的二維空間中，機器人的移動方向可以是任意的，并且不考慮高度的影響；3）在整個路徑規劃過程中，環境信息是不變的.圖1是一個10*10的移動機器人工作環境，S是機器人起點，D是終點.本文的工作就是找到一條從起點到終點的無碰的最優路徑.

2 A*全局路徑規劃算法

A*算法是一種典型的啟發式搜索方法.通過估價函數來引導和決定它的搜索方向.從起點開始搜索周圍的節點，由估價函數得到每個節點的價值，選擇價值最低的作為下一個擴展節點，循環重復這一過程直到搜索到終點，則停止搜索，獲得最終路徑.由于每一次都是以估價值最低的節點作為擴展節點，所以最終的路徑代價是最低的.估價函數由式（1）給出：

式中：g（n）是狀態空間中從起始節點到節點n的實際代價，h（n）是從節點n到終點的啟發式估計代價函數，本文采用曼哈頓距離作為啟發式函數[14].

xd是目標點的橫坐標，yd是目標點的縱坐標，xn是節點n的橫坐標，yn是節點n的縱坐標.

在A*算法搜索路徑的過程中，需要不斷地更新兩個列表，一個是開啟列表，另一個是關閉列表.開啟列表存儲的是所有的周圍節點.A*算法從開啟列表中選擇具有最小估價值的節點作為下一個擴展節點.關閉列表存儲的是所有經過的節點和環境中的障礙節點.應用A*算法進行路徑搜索的具體流程如下所述：

Step1 把起始節點放入開啟列表.

Step2 檢查開啟列表是否為空，如果為空，則表示搜索失敗；不為空，則執行Step3.

Step3 選取開啟列表中具有最低f（?）的節點作為當前擴展節點，對擴展節點的每個周圍節點作如下處理：①當該節點的周圍節點是障礙點或者是關閉列表中的節點，則沒有任何動作；②當該節點的周圍點不在開啟列表中，則把該節點的周圍節點添加進開啟列表中，并將當前擴展節點作為該節點的周圍節點的父節點，計算該節點的周圍節點的f（?）和g（?）；③當該節點的周圍節點在開啟列表中，如果以當前擴展節點作為父節點，該節點的周圍節點的g（?）比原來更低，則把當前擴展節點作為父節點，并重新計算該節點的周圍節點的f（?）和g（?）.否則，不作任何改變.

Step4 將當前擴展節點放入關閉列表中，并檢查終點是否在開啟列表中.如果不在開啟列表中，則跳回Step2繼續搜索；否則，最優路徑已經找到，結束搜索.

Step5 從終點開始，沿著每一個父節點移動，回到起始點，這就是最終的路徑.

3 改進的A*算法

采用A*算法進行移動機器人路徑規劃雖然能獲得一條安全無碰的路徑，但路徑點較多，折線多，導致路徑的總長度和總轉折角度較大.這在移動機器人實際應用中將消耗更多的能量和花費更多的r間.本文提出了一種改進的A*算法，能有效地減少路徑長度和轉折角度.

圖2的實線是在一個任意環境中A*算法規劃出的路徑，本文方法是在原路徑的基礎上，從起點開始以較小的步長分割原路徑，得到更多路徑點，如圖2的路徑點a1到a20.按照一定的規則剔除冗余路徑點，將剩余的路徑點按順序連接，最終獲得更加優化的路徑.

圖3是本文算法的流程圖，圖中符號的定義如下：

k為分割路徑的步長；c，m，i分別是當前路徑點下標、待連接路徑點下標和新路徑點下標；A為以步長k分割原始路徑得到的路徑點集合A={a1，a2，…，aN}，其中a1是起始點，aN是終點；ac為當前路徑點；am為當前待連接點；

lcm為連接ac與am的直線；lc，c+1為連接ac與ac+1的直線；B為新的路徑點集合，B={b1，b2，…，bs }.

注意，以步長k分割路徑是在原路徑的直線段進行的.例如，對圖4中A*算法得到的路徑進行分割，先進行直線段L1的分割，從起點開始依次得到路徑點a1，a2，…，a7，此時a8與原路徑點的距離小于步長k，則將原路徑點作為a8，并從路徑點a8開始重復上述過程，分割直線段L2和L3直到將終點作為路徑點a20時，分割過程結束.

圖4中的實線是在任意環境中A*算法規劃出的路徑1，由直線段L1 ，L2 和L3組成，本文方

法規劃出的路徑3由直線段La1a6，La6a9，La9a10和La10a20組成，其中Laiaj是指起點為ai，終點為aj的直線段.由圖4可以直觀地看出：路徑1的路徑長度明顯大于路徑3的路徑長度.另外，路徑1的總轉折角度：

路徑3的總轉折角度：

其中α2=∠ba6a9 ， β2=∠da9a10，γ1=∠ca10a20.而α1=α2+β2，β1=γ1+γ2，γ2=∠a15a20a10，則θ1=α1+β1=α2+β2+γ1+γ2=θ3+γ2.所以，θ1>θ3.相對于A*算法，本文方法縮短了總路徑長度，減小了總轉折角度.

文獻[15]提出的平滑A*算法直接地剔除A*算法規劃出的路徑點，使得路徑更加平滑.而本文方法是先進行分割，再剔除冗余的路徑點.圖4中直線段La1a8，La8a11和La11a20是文獻[15]中平滑A*算法得到的路徑2.顯然，路徑2的長度大于路徑3的長度.另外，路徑2的轉折角度：

其中α1=∠ba8a9，β3=∠a15a20a10，而α1=α2+β2，β3=γ1+γ3，γ3=∠a11a20a10，則θ2=α1+β3=α2+β2+γ1+γ3=θ3+γ3，所以θ2>θ3.相對于文獻[15]提出的平滑A*算法，本文方法得到的路徑也更加優化.

4 實 驗

為了驗證本文算法的可行性和有效性，進行了計算機仿真實驗和實物實驗.考察了不同情形下算法的性能，以下將從4個方面進行仿真實驗： 1）探究同樣的條件下本文算法與A*算法以及文獻[15]的平滑A*算法的性能；2）環境障礙率p對各算法的影響；3）不同目標點數n下算法的優劣；4）本文算法在不同的分割步長k下的效果.以下的4種情形都是在邊長為200個單位的正方形環境下進行實驗，將實驗環境分割成20*20個柵格元素，每個元素是邊長為10個單位的正方形柵格.將實驗環境分割成20*20個柵格元素，每個元素是邊長為10個單位的正方形柵格.

情形1 環境障礙率（障礙柵格數量占總柵格數量的比例）p=30%，取本文算法的分割步長k=0.1，目標數n=1即只有一個終點，起點是（4，4），終點是（198，198），機器人在起點的角度為90°.進行了50次實驗，圖5和圖6是不同算法規劃出的路徑長度和轉折角度，表1是3種算法50次實驗的各項平均值比較.從實驗結果中可以看出，本文提出的改進A*算法相對于A* 算法和文獻[15]的平滑A* 算法，有效地減少了路徑長度和轉折角度.注意，雖然環境障礙率都是30%，但障礙柵格是隨機分布的，這就導致了不同的環境復雜度，所以同樣的算法和實驗條件在不同的實驗次數下卻有不同的實驗結果.

情形2 考察在不同的環境障礙率下，各個算法的性能.令分割步長k=0.1，目標數n為1，起點（4，4）、終點（198，198），機器人在起點的角度為90°.分別在環境障礙率為10%，20%，30%，40%，50%時，進行了50次實驗，并求得不同障礙率下路徑長度的均值和轉折角度的均值，實驗結果如圖7、圖8所示.可以看出，一方面當環境障礙率增大時，各個算法得到的路徑長度和轉折角度也在不斷增大.這是因為環境障礙率一定程度上代表了環境的復雜度，當環境越復雜時，那么規劃的路徑長度和轉折角度也就越大；另一方面，在圖7和圖8中，方框內的數據是本文算法相對于A*算法路徑長度和轉折角度的減少量.當環境障礙率越大時，路徑長度和轉折角度的減少量也不斷增大，這說明相對于A*算法，本文方法更加適合在障礙物較多的環境中使用.

情形3 在移動機器人的工作空間中可能存在多個任務點，這就意味著環境中會有多個不同的終點.這里將研究當機器人有多個任務點時，各個路徑規劃算法的優劣性.這里做以下兩點規定：1）對環境中的任務點進行了編號，任務點1，（198，198）；任務點2，（4，198）；任務點3，（95，95）；任務點4，（198，4）.2）當機器人有n個任務需要執行時，它的執行順序是由任務點1遞增至任務點n.取障礙率p=30%，分割步長k=0.1，分別在n等于1，2，3，4時，進行了50次實驗，并求得路徑長度和轉折角度的均值，實驗結果如圖9和圖10所示，圖中方框內的數據是本文算法相對于A*算法路徑長度和轉折角度的減少量.顯而易見，當機器人的任務點越多，本文算法相對于A*算法規劃的路徑長度和轉折角度的減少量越大.

情形4 本文算法中存在一個分割步長k，這里將考察參數k對算法效果的影響.令環境障礙率p=30%，僅有一個任務點（198，198），起點是（4，4），機器人在起點的角度為90°.在不同的分割步長下進行了50實驗，并求出相應的均值，驗結果如圖11和圖12所示.可以得出這樣的結論：當分割步長越小時，本文算法得到的路徑長度和轉折角度也越小.顯然，這是因為分割步長越小，路徑分割得越精細，路徑長度和轉折角度也就相應減小.

在實物實驗中，本文采用的移動機器人是Turtlebot2，移動底座的最大移動速度：0.7 m/s，最大角速度：180°/s.采用ThinkPad E450C筆記本電腦作為移動機器人的控制器.移動機器人的實際運動空間如圖13所示，是3.6 m×6.6 m的矩形環境.起點（0.9 m，0.9 m），終點（2.7 m，6.3 m），機器人在起點的角度為90°.為了使用本文改進的A*算法進行路徑規劃，需要先建立環境的柵格模型，設置柵格元素為0.6 m×0.6 m的正方形，對實際障礙物進行膨化處理，映射成圖14的黑色柵格.分別采用A*算法、文獻[15]的平滑A*算法和本文算法進行移動機器人的路徑規劃.圖14的直線段La1a5，La5a11，La11a21，La21a27，La27a32，La32a44 和

La44a53是A*算法規劃出的路徑；文獻[15]中平滑A*算法得到的路徑是直線段La1a5，La5a11，La11a21，La21a27，La27a32和La32a53；直線段La1a8，La8a24，La24a25，La25a35和La35a53是本文算法得到的結果.由于移動機器人的運動總是存在外界干擾和運動精度等因素，其運動的實際路徑長度與轉折角度總是比規劃的路徑長度和轉折角度要稍稍大一些，如表2所示.但無論是規劃的路徑長度和轉折角度，還是移動機器人實際運動的路徑長度和轉折角度，本文算法得到的實驗結果都比A*算法和文獻[15]平滑A*算法更加優化.

5 結 論

采用A*算法進行移動機器人路徑規劃，可以得到一條從起點連接終點的無碰安全路徑，但路徑的冗余點較多，路徑長度和轉折角度較大.針對這些問題，本文提出了一種改進A*算法，能有效地減少路徑冗余點和減小路徑長度及轉折角度.并且，分析比較了不同的環境障礙率、任務點數量、分割步長對算法性能的影響.一方面，相對于A*算法，本文方法更加適合多任務點，高障礙率環境下的移踴器人路徑規劃；另一方面，采用較小的分割步長可使得規劃出的路徑更加優化.

參考文獻

[1] 席裕庚，張純剛.一類動態不確定環境下機器人的滾動路徑規劃[J].自動化學報，2002，28（2）： 161-175.

XI Yugeng， ZHANG Chungang.Rolling path planning of mobile robot in a kind of dynamic uncertain environment[J]. Acta Automatica Sinica， 2002，28（2）：161-175.（In Chinese）

[2] 張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005， 17（2）： 439-443.

ZHANG Handong， ZHENG Rui， CEN Yuwan. Present situation and future development of mobile robot path planning technology[J]. Journal of System Simulation， 2005，17（2）：439-443.（In Chinese）

[3] 朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010， 25（7）： 961-967.

ZHU Daqi， YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision， 2010，25（7）：961-967.（In Chinese）

[4] 吳乙萬，黃智.基于動態虛擬障礙物的智能車輛局部路徑規劃方法[J].湖南大學學報：自然科學版，2013，40（1）： 33-37.

WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University：Natural Sciences， 2013，40（1）：33-37.（In Chinese）

[5] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規劃算法[J].沈陽工業大學學報，2009，31（2）： 225-229.

YANG Huaiqing， XIAO Xinggui， YAO Dong. A V-graph based global path planning algorithm for mobile robot[J]. Journal of Shenyang University of Technology， 2009，31（2）：225-229.（In Chinese）

[6] 梁瑾，宋科璞.神經網絡在移動機器人路徑規劃中的應用[J].系統仿真學報，2010，22（增刊1）： 269-272.

LIANG Jin， SONG Kepu. The application of neural network in mobile robot path planning[J]. Journal of System Simulation， 2010，22（s1）：269-272.（In Chinese）

[7] 郝冬，劉斌.基于模糊邏輯行為融合路徑規劃方法[J].計算機工程與設計，2009，30（3）： 660-663.

HAO Dong， LIU Bin. Behavior fusion path planning method for mobile robot based on fuzzy logic[J]. Computer Engineering and Design， 2010，30（3）：660-663.（In Chinese）

[8] ARPINO C P， MELENDEZ W M， GUZMAN J， et al. Fuzzylogic based speed planning for autonomous navigationunder velocity field control[C]//2009 IEEE Int Conf on Mechatronics. Malaga， 2009： 201-212.

[9] ZOUMPONOS G T， ASPRAGATHOS N A. Fuzzy logic pathplanning for the robotic placement of fabrics on a worktable[J]. Robotics and Computer Integrated Manufacturing， 2008， 24 （2）： 174-186.

[10]鄧高峰，張雪萍，劉彥萍.一種障礙環境下機器人路徑規劃的蟻群粒子群算法[J].控制理論與應用，2009，26（8）： 879-883.

DENG Gaofeng， ZHANG Xueping， LIU Yanping. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J]. Control Theory & Applications， 2009，26（8）：879-883.（In Chinese）

[11]吳憲祥，郭寶龍，王娟.基于粒子群三次樣條優化的移動機器人路徑規劃算法[J].機器人，2009，31（6）： 556-560.

WU Xianxiang， GUO Baolong， WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. ROBOT， 2009，31（6）：556-560.（In Chinese）

[12]王雪松，高，程玉虎，等.知識引導遺傳算法實現機器人路徑規劃[J].控制與決策，2009，24（7）： 1043-1049.

WANG Xuesong， GAO Yang， CHENG Yuhu， et al. Knowledge-guided genetic algorithm for path planning of robot[J]. Control and Decision， 2009，24（7）：1043-1049.（In Chinese）

[13]THEODORE M， KAVEH A， ROGER L W. Genetic algorithms for autonomous robot navigation[J]. IEEE In Strumentation and Measurement Magazine， 2007，12（1）： 26-31.

[14]王殿君.基于改進A*算法的室內移動機器人路徑規劃[J].清華大學學報：自然科學版，2012， 52（8）： 1085-1089.

WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University：Science and Technology，2012，52（8）：1085-1089.（In Chinese）

[15]王紅衛，馬勇，謝勇，等.基于平滑A*算法的移動機器人路徑規劃[J].同濟大學學報：自然科學版，2010，38（11）： 1647-1651.

篇（5）

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)16-4487-03

Research on Path Planning for Mobile Multi-Agent

CHEN Cui-li, GAO Zhen-wei

(Henan Normal University, Xinxiang 453007,China)

Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.

Key words: mobile Multi-Agent; global path; local path

在移動智能體相關技術研究中,路徑規劃技術是一個重要研究領域。移動智能體路徑規劃問題是指在有障礙的環境中,尋找一條智能體從起始點到目標點的運動路徑,使智能體在運動過程中安全、無碰撞地繞過所有的障礙物。這不同于用動態規劃等方法求得最短路徑,而是指移動智能體能對靜態及動態環境下做出綜合性判斷,進行智能決策。在以往的研究中,移動智能體路徑規劃方法大體上可以分為三種類型:其一是基于環境模型的路徑規劃,它能處理完全已知的環境下的路路徑規劃。而當環境變化時(出現移動障礙物)時,此方法效果較差,具體方法有:A*方法、可視圖法、柵格化和拓撲圖法等;其二是基于傳感器信息的局部路徑規劃方法,其具體的方法有:人工勢場法、模糊邏輯法和遺傳算法等;其三是基于行為的導航行為單元,如跟蹤和避碰等,這些單元彼此協調工作,完成總體導航任務。隨著計算機、傳感器及控制技術的發展,特別是各種新算法不斷涌現,移動機器人路徑規劃技術已經取得了豐碩研究成果。

一個好的路徑規劃方法需要滿足如下性能[1]:合理性、完備性、最優性、適時、環境變化適應性和滿足約束。有些方法沒有高深的理論,但計算簡單,實時性、安全性好,就有存在的空間。如何使性能指標更好是各種算法研究的一個重要方向。

在未知的(或部分已知的),動態的非結構的環境下,多智能體利用傳統的路徑規劃方法很難滿足前面的性能要求,本文提出了一種將全局路徑規劃方法和局部規劃方法相結合,將基于反應的行為規劃和基于慎思的行為規劃相結合的路徑規劃方法,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。

1 路徑規劃方法

1.1 相關研究

1) A*算法

在最佳優先搜索的研究中,最廣范圍應有的方法為A*搜索,其基本思想[2]是:它把到達節點的代價g(n)和從該節點到目標節點的代價h(n)結合起來對節點進行評價:f(n) = g(n) + h(n)(1)。A*算法用于移動多智能體的路徑規劃時,多智能體分別按照已知的地圖規劃出一條路徑,然后沿著這條生成路徑運動,但智能體傳感探測到的環境信息和原來的環境信息不一致時,智能體重新規劃從當前位置到目標點的路徑。如此循環直至智能體到達目標點或者發現目標點不可達[3]。重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且由于采用A*方法規劃出的最優路徑并沒有考慮到機器人的運動學約束,即使機器人可以采用A*方法規劃出一條最優路徑,機器人也未必可以沿著這條路徑運動。

2) 人工勢能法

人工勢能法由 Khatib 提出的一種虛擬力法[4]。人工勢場方法結構簡單,便于低層的實時控制,在實時避障和平滑的軌跡控制方面得到了廣泛的應用,但根據人工勢場方法原理可知,引力勢場的范圍比較大,而斥力的作用范圍只能局部的,當智能體和障礙物超過障礙物影響范圍的時候,智能體就不受來自障礙物引起的排斥勢場的影響。所以,勢場法只能解決局部空間的避障問題,他缺乏所在的全局信息,,這樣就造成產生局部最優解不能進行整體規劃,智能于局部最小點的時候,智能體容易產生振蕩和停滯不前。

1.2 路徑規劃方法描述

鑒于A*算法全局路徑搜索的全局性與改進人工勢場算法局部路徑搜索的靈活性,通過一定的方法把兩者結合起來,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。由于A*方法采用柵格表示地圖,柵格粒度越小,障礙物的表示也就越精確,但是同時算法搜索的范圍會按指數增加。采用改進人工勢場的局部路徑規劃方法對A*方法進行優化,可以有效增大A*方法的柵格粒度,達到降低A*方法運算量的目的。

2 環境構造

目前主要有三種比較典型的環境建模方法:構型空間法、自由空間法和柵格法,本文仿真實驗采用的環境建模方法是柵格法,柵格法將機器人路徑規劃的環境劃分成二維網格,每格為一個單元,并假設障礙的位置和大小已知,且在機器人運動過程中不會發生變化。柵格法中的網格單元共有三種類型,即障礙網格、自由網格和機器人所在網格。目前常用的柵格表示方法有兩種,即直角坐標法和序號法。這兩種表示方法本質上是一樣的,每個單元格都與(x, y)一一對應。本文采用序號法表示柵格,設柵格的中心點坐標為柵格的直角坐標,則每個柵格編號都與其直角坐標一一對應,地圖中任意一點(x,y)與柵格編號N的映射關系為:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x軸的取值范圍,Gs表示柵格尺寸的大小,INT函數表示取整,而柵格中心點的坐標為(xG,yG),它與柵格編號N之間的關系為:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符號%表示取余操作。本文中根據機器人的尺寸來確定柵格的粒度,假設一個柵格能容納一個智能體,這里選擇柵格的大小為40cm×40cm[5]。本文的仿真環境為800cm×800cm,柵格號N=0~399,機器人的初始位置的柵格號為N=42,目標位置的柵格號為N=314。在Visual Studio 2005中進行仿真,仿真結果如圖1所示,長方形和橢圓圖形代表障礙物柵格,小圓圈所代表的柵格為機器人的起始柵格和目標柵格,剩下的是自由柵格。在路徑規劃中機器人可以選擇自由柵格作為它的路徑點。

建立柵格后,對柵格進行初始化。設置變量G_Obstacle為0表示自由柵格,G_Obstacle為1表示障礙網格包括機器人柵格。若障礙物或智能體占當前位置柵格面積大于1/3則設置變量G_Obstacle為1.

3 數據的采集

對于簡單地形,我們將實際地形就行考察并進行測量、量化,轉化為平面坐標數據最后轉換相應的柵格編號。對于復雜地形在沒有航攝資料的情況下,本實驗以地圖為數據源的DTM數據獲取方法在,可利用已有的地形圖采集地形數據,用手扶跟蹤式數字化儀將平面圖形轉化為平面坐標數據,最后轉換相應的柵格編號。

4 實現過程

第1步:對環境信息進行數據采集并轉化成相應的平面坐標數據。

第2步:確定各個智能體的初始位置和目標位置。

第3步:建立柵格,對柵格進行初始化。

第4步:智能體S(i)首先根據已知信息規劃出各自的一條目標序列S(i)n。

第5步:智能體S(i)利用測試傳感器探測到臨界危險區L范圍內的信息與原有信息是否一致,當智能體利用傳感器探測到臨界危險區L范圍內的信息與原有信息一致時,利用改進后的人工勢能算法搜索相鄰目標點之間的軌跡,否則智能體搜索從當前序列點S(i)n到S(i)n+4路徑。定義臨界危險區L、目標序列點S(i)n(n>=1)。

第6步:智能體一旦移動到達目標柵格,則程序終止;否則返回第5步。系統的工作流程如圖2所示。

5 仿真結果及結論

在Visual Studio 2005平臺上進行了仿真,,首先根據已知環境信息,進行數據采集量化并進行柵格化處理,設置障礙和智能體的大小及位置(為了簡單化,本實驗所有障礙都設置為圓形),再進行初始化操作,采用0、1二元信息數組存儲柵格化的地形。

智能體運用A*算法進行全局路徑規劃,圖3顯示兩個智能體的運動過程,顯然兩個智能體的路徑相交可能會發生碰撞,智能體為了避免碰撞應重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且顯然只用A*算法規劃出二維路徑點序列,相鄰兩點之間的夾角一定是π/4的整倍數,機器人很難按照所生成的序列點運動。智能體采用改進后的人工勢場進行目標序列點之間的局部路徑規劃,圖4顯示智能體的運動過程。顯然智能體的整條運動軌跡顯得比較平滑同時又實現實時避障的目的。

6 總結

本文對多智能體在動態環境下路徑規劃技術進行了研究探索,提出了一種能夠將全局路徑規劃方法和局部路徑規劃方法相結合,通過仿真取得了很好的結果,證明A*和人工勢場算法的結合可行。

參考文獻:

[1] 劉華軍,楊靜宇,陸建峰,等.移動機器人運動規劃研究綜述[J].中國工程科學,2006,8(1):85-94.

篇（6）

我國目前白車身焊接機器人焊接路徑規劃方面仍處于落后水平，相關路徑規劃也極為不完善，機器人工作的過程中經常出現作業順序不合理的狀況，導致生產周期增長，影響整個焊接線路的發展。所以如何制定出一條合理的路徑規劃是當前首要目標，本文立足實際就針對這個問題提出一些有效性策略。

一、路徑規劃的意義

白車身焊接機器人焊接中制定出一條合理的路徑規劃可以有效縮短機器人生產時間，進而縮短整個工期，提高整個生產效率，某種程度上降低了生產成本。另一方面，白車身焊接機器人焊接路徑規劃具有一定的典型性，在自動駕駛、服務機器人、挖掘機器人等路徑規劃研究方面具有重要的借鑒意義，具有較高的社會價值和經濟價值。

二、白車身焊接機器人焊接路徑規劃

（一）路徑規劃的基本任務

現代化工業生產的主要目標是為了獲得較高的制造質量、取得較高的生產率，而付出較低的生產成本，這是現代企業提高自身競爭力的重要手段，也是路徑規劃中的主要任務之一，而在路徑規劃的過程中要想保證焊接質量主要取決于以下兩點：

第一，最大程度的使用機器人工位。使用機器人工位能夠有效降低工人的勞動強度，減少人為錯誤幾率，提高焊接的準確性，保證焊接的順利進行，從而保證焊接的穩定性。

第二，要完成所有的焊接點，保證焊接的工藝參數。

要想實現較低的制造成本就是最大化的利用現有資源，提高機器人的工作效率，縮短機器人工位的生產周期，減少機器人的使用數量。路徑規劃的重要方向就是提高生產率，保證生產環節的順利進行，縮短生產周期，提高生產率。

（二）路徑規劃

白車身焊接機器人焊接路徑規劃主要有兩個分支，一是改變工藝參數，使用新的工藝方法和輔助設備。二是要提高分配的合理性、提高焊接順序的合理性，提高合理性的目標是為了減少機器人工位的生產周期。第二個分支實現的途徑主要是通過提高機器人焊接路徑的合理性，從而提高單個機器人的生產效率，最終縮短整個生產周期。

（三）遺傳算法

遺傳算法是進化算法中產生最早、應用最廣泛的一種基本算法，在工程技術和經濟管理領域都有廣泛的應用。遺傳算法有群體搜索和遺傳算子兩個基本特征，所謂的群體搜索打破了領域的限制，使信息可以廣泛分布于整個空間。而遺傳算子就是使染色體進行隨機操作，以降低人機交互的依賴。兩個特征保證了遺傳算法具有最優的搜索能力、最簡明的操作能力以及信息處理的隱秘能力。

白車身焊接路徑規劃主要問題如下：

第一，白車身中所需要焊接的焊接點眾多。

第二，在生產的過程中常常追求沒有意義的高精度。

第三，在解答相關問題時需要運用數學方法。

第四，因為方案最終應用于企業，所以數學方法最好要簡潔明了，便于學習。

綜上，在路徑研究時需要運用遺傳算法，主要優勢在于：

第一，遺傳算法的計算步驟比較簡單明了，在實際操作時便于學習和使用。在計算時大大減少了計算量，從而節約時間。

第二，能夠在很大程度上優化焊接作業順序，減輕焊接的工作量。

第三，減少定量分析與定性分析的工作量。

第四，能夠很好的掌控全局，在全局中找到最優解。

三、路徑規劃的仿真

（一）仿真系統的各要素

路徑仿真系統一般要具有以下幾個基本要素：

第一，對仿真問題的描述。模型和仿真運行控制共同組成了一個仿真系統，而一個特定的模型又是由一個參數和一組參數值構成。例如白車身點焊機器人焊接路徑的參數模型一般包括家具模型、機器人模型、側圍模型，在這基礎之上還加入了具體的參數值，就形成了特定的模型。

第二，行為產生器。模型確定以后就要對模型進行試驗，這是一套試驗的軟件，行為產生器可以生成一組根據時間變化的數據，這類數據是仿真的物資基礎。

第三，模型行為及對行為的處理。

模型行為可以大致分為三種：軌跡行為、結構行為以及點行為。

仿真系統中都要獲取軌跡行為，這些行為的獲取主要是根據時間的推移而產生的。

（二）仿真軟件的選擇

一個完善的機器人仿真系統可以依據機器人的運動學、動力學、行為軌跡等多項內容進行仿真計算，并可以根據機器人的實際操作內容進行仿真操作過程，并不依賴于真正的機器人。但目前最主要的工作是對機器人的路徑規劃做一個仿真方案，而不是設計出一個機器人的仿真系統。在進行機器人路徑規劃時需要一定的條件，在現實生活中可以有多個選擇，最好的選擇就是使用一些類似CAR這種專業軟件，如果條件不允許可以選擇VC++或者使用CATIA等軟件進行仿真。VC++自主編寫的優點在于針對性比較強，在做路徑時可以考慮多方面因素，然而缺點是不能建立詳細的三維模型，在實際操作時不能全方面的展現白車身焊接工位情況，且工作量較大。CATIA與VC++相比最大的優勢就是可以建立詳細的三維模型，能夠全方位展現工位情況，仿真軌跡最為真實，在仿真過程中還可以檢查是否干涉。而缺點也是比較明顯的，在仿真的過程中不能將動力學和控制算法考慮在內。

四、小結

白車身主要是以鋼結構為主的支架，是汽車中重要組成部分。而車身制造是整個環節中比較復雜又極為重要的一環，影響整個汽車的質量。我國研究白車身焊接機器人焊接路徑仍處于落后階段，為了提高綜合競爭力需要加大技術投資，提高我國白車身制造綜合競爭。

參考文獻：

篇（7）

中圖分類號：F715.6 文獻標識碼：A 文章編號：1001-828X（2014）010-00-01

引言

對于B2C企業配送中心而言，揀選作業占配送中心作業總量的60%[1]。鑒于B2C企業多品種、小批量、多頻次、快速響應的客戶需求，如何提高配送中心的作業效率，從揀選作業入手效果更佳。縱觀揀選作業的研究大多集中于以下幾個方面：一是儲位分配問題；二是訂單分批問題；三是揀選路徑優化問題。

一、儲位分配問題

貨物儲位分配是指按照節約揀貨時間、減少揀貨路徑、提高空間利用率等目標，將商品合理放置在合適的儲位。合理的儲位分配是提高配送中心出入庫作業效率和降低搬運成本的有效途經。

1.確立貨位分配目標，建立貨位分配模型、使用算法進行優化研究。Ene Seval等人使用改進的數學模型和隨機進化優化算法，并分兩階段來設計儲位分配和揀選系統[1]。Park Changkyu等人聚焦于平面儲位分配問題，采用改進的遺傳算法，并建立數學模型進行了實證研究[2]。陳璐等人提出了一個混合整數規劃模型對該問題進行優化建模，設計開發了一個基于有向連接圖的優化算法對儲位分配問題求初始解，并用禁忌搜索算法進行改進[3]。吳迪等人以最小化系統總成本及最大化時間滿意度為目標建立雙目標非線性整數約束規劃模型，并提出了基于精英重組的混合多目標進化算法，在此基礎上進行關鍵參數敏感度分析，得出雙目標比單目標模型得出的儲位分配結果更優[4]。

2.基于研究數據的關聯性，解決儲位分配問題。Glock Christoph 等人根據比較數據研究，提出不同的存儲位置分配策略，并提出容易在實踐中使用的啟發式算法[5]。Chiang David等人提出一種數據挖掘的基礎存儲分配方法，在有空貨架時為新產品找到最優存儲分配，對未賦值的存儲位置通過應用關聯規則挖掘來解決存儲分配問題[6]。王成林等人基于區域關聯度的儲位規劃方法，對儲位管理的關聯度進行了定義和分析[7]。張志勇等人討論了利用Apriori算法對倉儲管理系統的大規模業務數據進行強關聯挖掘，并結合IQ分析來分配貨物的儲位[8]。

二、訂單分批問題

訂單分批是指將多張客戶訂單合并生成一個批次揀貨單，并對該批次揀貨單進行揀貨作業，貨物揀選完成后，再將揀選品按照原始訂單進行分揀。其目的在于減少揀貨人員尋找儲位時間、縮短揀貨人員的行走距離、提高揀貨效率。國內學者李詩珍通過仿真發現訂單分批策略對減少作業總時間影響最大。訂單分批問題，作為NP難題，針對配送中心訂單分批問題的研究可以分為以下兩類。

1.基于訂單相似度分批，指訂單是按照待揀品項所在的儲存位置相似或者相近進行分批。伍經緯[9]通過對比訂單分批的MAA，FIFS，GSM，COG，GS等五種算法，得出在S型路徑下，MAA算法更有效。李詩珍[10]以最小化訂單揀選行走距離為目標建立了訂單分批模型，并通過以計算訂單相似度為核心步驟的種籽算法以及其他與其原理相類似的節約算法、包絡算法、基于聚類分析的啟發式算法等對模型進行求解與實證分析，并分別對不分批、先到先服務分批、聚類分批下的行走距離進行計算與比較。國外的眾多學者對于不同的揀貨系統分別提出了不同的種子算法、節約算法等，但本質上都是種子算法。De Koster[11]在多貨架矩形系統中結合揀選路徑與分批數量，通過仿真模擬得出最簡單的分批方法都比先進先出分批方法好，S型路徑下揀選設備能與種子算法高效率結合。

2.基于時間窗分批，指在考慮客戶的等待時間以及訂單處理時間的同時，以最小化訂單總時間為目標來決定時間窗大小，也就是將確定或不定的某一時間段的訂單作為一個批次進行揀選，總作業時間除以時窗值，即得到分批次數。馬士華 在解決配送中心揀貨作業中問題中引入延遲制造思想，提出基于時間延遲的動態時窗分批策略，該策略可以消除目前揀貨系統存在的等待時間和閑忙不均的現象，實現揀貨作業的高效率。對于隨即訂單到達的情況，很多學者將可變時間窗固定分批批量問題處理為隨機服務隊列模型。De Koster[11]提出輪換檢測動態模型，將分批、揀選、分類看作串聯隊列，從而實現優化平均揀選作業時間的目的。Won在處理基于客戶響應時間的訂單分批問題時，以最優化顧客響應時間為目標，提出SBJ和JBP算法以降低訂單揀選時間來提高效率。

此外，國內外學者也提出采用遺傳算法、啟發式算法等來求解訂單分批問題。

三、揀選路徑問題

揀選作業路徑優化的目的是為了減少行走距離與縮短揀貨時間，以實現揀選效率的最大化。目前，大多數B2C企業采用固定矩形貨架的人工揀貨或自動化倉庫。路徑優化問題屬于一類特殊的旅行商問題（TSP），對于揀選路徑問題的優化算法主要有啟發式算法、神經網絡算法、彈性算法，以及近年發展迅速的遺傳算法、模擬退貨算法、禁忌搜索算法等智能算法。人工揀貨作業常采用啟發式揀貨策略，即穿越策略、中點策略、最大間隙策略、混合策略等。對于B2C企業而言，特別是訂單數量多，訂購數量少的電商而言，通常采用最簡單的S型路徑，揀貨人員從貨架巷道的一端進入，從兩邊貨架上揀取貨品，然后轉彎進入下一巷道，直至貨品揀取完成。

四、揀選作業系統仿真技術

揀貨作業問題不僅包括以上三個問題，還包括人員配置、設備選擇、流程優化等很多問題，揀貨作業系統作為配送中心的核心子系統，它的優化與改進對配送中心效率的提高意義重大。配送中心是典型的現代機械電子相結合的系統，也是典型的隨機型離散事件系統，其復雜性與系統性可通過仿真的方法進行設計與優化。目前，物流系統仿真技術已經越來越多的被運用到決策中去，物流系統仿真軟件也有了更多的選擇性。二維平面式動畫表現形式（2D）的有ARENA、Em-Plant、WITNESS、EXTEND，三維立體（3D）的有Flexsim、Automod、RalC、WITNESS等。本質上，物流仿真軟件的建模大同小異，都是通過實體的組合來建模，參數的控制來調節，目標的設定來實現，并通過對結果的分析發現瓶頸和做進一步的優化調整。

參考文獻：

[1]Ene Seval，Ozturk Nursel. Storage location assignment and order picking optimization in the automotive industry[J]. International Journal of Advanced Manufacturing Technology，2012，60：787-797.

[2]Park Changkyu，Seo Junyong.Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers & Industrial Engineering，2009，57（3）：1062-1071.

[3]陳璐，陸志強.自動化立體倉庫中的儲位分配及存取路徑優化[J].管理工程學報，2012，26（1）：42-47.

篇（8）

中圖分類號：TP181 文獻標識碼：A 文章編號：1009-3044（2016）26-0235-03

B-spline Curve based Trajectory Planning for Autonomous Vehicles

QU Pan-rang，LI Lin ， REN Xiao-kun ，JING Li-xiong

（Institute of Aeronautics Computing Technique Research， Xi’an 710065， China）

Abstract：Path planning is an important research topic in the field of the unmanned vehicle motion planning， and it directly affects the performance of unmanned vehicles in a complex traffic environment. Taking the requirement for smoothness into account， this paper proposed a method based on B-spline curve and built a planning model which can be divided into four steps， including path clusters， constraint of maximal curvature， collision detection and optimal path. This method works efficiently and simulation results show efficiency of the method.

Key words：B-spline curve； autonomous vehicle； path planning； collide detection； constraint of maximal curvature

1 引言

近年來，無人駕駛技術備受關注，各大研究機構和企業爭相推出各自的無人駕駛平臺。無人車作為未來智能交通的主要主體也逐漸融入到我們的日常生活中，比如自主巡航[1]和自動泊車等等。然而，為了使其更好地服務于我們，需要進一步提高其智能化水平，而路徑規劃作為連接環境感知和運動規劃的橋梁，是無人車智能化水平的重要體現[2]。

由于受到自身動力學和運動學模型的約束，車輛的路徑規劃問題除過要嚴格滿足端點狀態約束之外，還要求其中間狀態滿足運動系統的微分約束。由于實現簡單，并且高階多項式曲線能夠很好地滿足運動系統的微分約束，生成高階平滑的路徑，所以很多路徑規劃系統選擇使用基于多項式曲線的方法生成路徑。B樣條曲線是一種典型的多項式曲線，且因為其所有的中間狀態均是由控制點加權生成，所以其能夠完全滿足端點狀態約束。綜合考慮無人車路徑規劃的要求和實現復雜度，在僅已知初始位姿和目標位姿的情況下，本文選擇B樣條曲線生成路徑，重點講述分步規劃模型，即路徑簇生成、最大曲率約束、碰撞檢測以及最優評價四個過程，并通過Matlab仿真對本文方法進行了驗證。

2 問題描述

本節分別描述了無人車路徑規劃問題和B樣條曲線。

2.1 路徑規劃問題描述

路徑規劃得到的是一條從初始位置到目標位置的路徑，即二維平面內一條從初始位置點到目標位置點的曲線，曲線上的每一個點表示車在行駛過程中的一個狀態。考慮到實現方便，本文將路徑描述成離散點序列[Sstart，S1，???，Sn，Sgoal]，如圖1所示，序列中每一個點[Si（xi，yi，θi）]表示車的一個狀態，其中[（xi，yi）]表示此時刻車輛的位置，[θi]表示車輛的航向，[Sstart]和[Sgoal]分別表示車輛的初始狀態和目標狀態。圖1中的圓[（xobs1，yobs1，robs1）]表示環境中的障礙物，[（xobs1，yobs1）]表示障礙物的位置信息，[robs1]表示障礙物的半徑。

2.2 B樣條曲線

如果給定[m+n+1]個控制點[Pi（i=0，1，???，m+n）]，就可以構造[m+1]段[n]次B樣條曲線，其可以表示為公式1：

[Pi，n（t）=k=0nPi+k?Fk，n（t） ，t∈[0，1]Fk，n（t）=1n！j=0n-k（-1）j?Cjn+1?（t+n-k-j）n ， t∈[0，1] ， k∈0，1，???，n] （1）

其中，[Pi，n（t）]表示第[i]個[n]次B樣條曲線片段，[n]表示B樣條曲線的次數，[t]為控制參數，其取值范圍為[[0，1]]，[Pi+k]為控制點，[Fk，n（t）]為B樣條基。依次連接全部[n]階B樣條曲線段就組成了整條B樣條曲線。

3 本文算法

本節重點講述基于B樣條曲線的路徑規劃方法和基于該方法生成路徑的過程。

3.1 基于B樣條曲線的路徑規劃方法

選擇三階B樣條曲線生成幾何路徑，即每四個控制點生成一個路徑片段，然后通過片段的拼接就可以實現從初始狀態到目標狀態的路徑規劃，下面著重講述基于六控制點的三階B樣條曲線生成滿足車輛端點位姿約束路徑的方法，如圖2所示。

l 依據初始狀態選擇控制點[P0，P1，P2]。當[P0，P1，P2]三個控制點共線，并且[P1]為線段[P0P2]的中點時，生成的B樣條曲線與線段[P0P2]相切于點[P1]。所以選擇無人車的初始位置為控制點[P1]，將控制點[P0]和[P2]選在初始航向角[θstart]所在直線上，并關于控制點[P1]對稱。如是，即能滿足車輛的初始位姿約束；

l 依據目標狀態選擇控制點[P3，P4，P5]。當[P3，P4，P5]三個控制點共線，并且[P4]為線段[P3P5]的中點時，生成的B樣條曲線與線段[P3P5]相切與點[P4]。所以選擇無人車的目標位置為控制點[P3]，將控制點[P3]和[P5]選在目標航向角[θgoal]所在的直線上，并關于控制點[P3]對稱。如是，即能滿足車輛的目標位姿約束。

（a） 路徑簇

（b） 最大曲率約束

（c） 碰撞檢測

3.2 分步路徑規劃

本小節將以圖3所給定的場景為例，講述最優路徑生成的過程。

3.2.1 路徑簇生成

在選定控制點[P1]和[P4]之后，通過選擇不同的控制點[P2]和[P3]，從而得到多組控制點，進而得到多條路徑。將控制點選擇的極限定為線段[P1P2]、[P3P4]與[P1P4]相等，但是[P1P2]和[P3P4]不能出現交叉。將這個范圍等間隔量化，各取四個點，共組成16組控制點，得到16條路徑，如圖3（a）中的藍色曲線所示。

3.2.3 最大曲率約束

理論上，車輛的最小轉彎半徑[Rmin=Lsin（θmax）]是其本身屬性[3]，只取決于車輛的軸距[L]和最大前輪轉角[θmax]。那么，車輛可行駛路徑的最大曲率[κmax=1Rmin]也是固定的，假設無人車可行駛路徑的最大曲率[κmax=16]，以此為約束條件，在路徑簇中選擇滿足最大曲率約束的路徑，如圖3（b）所示，圖中綠色曲線表示不滿足最大曲率約束的路徑。

3.2.4 碰撞檢測

碰撞檢測的目的是保證車輛在規劃路徑上行駛而不與障礙物發生碰撞。采取的碰撞檢測的方法很簡單，因為環境中的障礙物采用圓來描述，所以只要判斷路徑上每一點到圓心的距離與障礙物半徑的關系，就能確定其是否發生碰撞。由兩點間距離公式：

[d=（x1-x2）2+（y1-y2）2] （2）

如果[d]大于障礙物半徑，則不發生碰撞；如果[d]小于障礙物半徑，則發生碰撞。圖3（c）中的藍色曲線表示既滿足最大曲率約束，又不與障礙物碰撞的路徑。

3.2.2 最優路徑

路徑要求的側重點不同，優化的目標函數也可以有多種選擇，常用的目標函數有最短和最平滑等。其中，路徑最短可以抽象成優化問題：

[traoptimal=arg mintraids] （3）

路徑最平滑可以抽象成優化問題：

[traoptimal=arg mintraiκ2] （4）

式中，[traoptimal]為最優路徑，[traids]為第[i]條路徑的長度，[traiκ2]為第[i]條路徑上所有點處的曲率平方之和。圖3（d）中的紅色曲線即為得到的最短可行駛路徑。

如是，就能得到滿足車輛運動學約束，并且無碰撞的最優路徑。

4 結論

本文選擇使用B樣條曲線解決無人車路徑規劃問題，并建立了基于B樣條曲線的分步規劃模型。仿真結果表明，使用基于B樣條曲線的路徑規劃方法能夠很好地解決簡單障礙物場景中無人車的路徑規劃問題，并且因為路徑生成過程簡單，所以該方法常常表現得十分高效，能夠完全滿足無人車路徑規劃系統對算法實時性的要求。

參考文獻：

篇（9）

DOI：10.16640/ki.37-1222/t.2016.21.135

0 前言

移動機器人的實現涉及自動控制、智能、機械等多種學科。它通常被應用在醫療領域、工業領域等方面。從整體角度來講，移動機器人的應用促進了生產效率的顯著提升。路徑規劃技術是移動機器人的關鍵技術之一，研究該技術具有一定的現實意義。

1 路徑規劃技術的作用

將路徑規劃技術應用在移動機器人中，能夠產生的作用主要包含以下幾種：

（1）運動方面。路徑規劃技術的主要作用是其能夠保證移動機器人完成從起點到終點的運動。（2）障礙物方面。設計移動機器人的最終目的是將其應用在實際環境中，在實際環境下，移動機器人的運行路線中可能存在一定數量的障礙物，為了保證最終目的地的順利達到，需要利用路徑規劃技術實現對障礙物的有效避開[1]。（3）運行軌跡方面。對于移動機器人而言，除了實現障礙物躲避、達到最終目的地這兩種作用之外，應用路徑規劃技術還可以產生一定的優化運行軌跡作用。在移動機器人的使用過程中，在路徑規劃技術的作用下，機器人可以完成對最佳運行路線的判斷，進而更好地完成相應任務。

2 移動機器人路徑規劃技術綜述

移動機器人的路徑規劃技術主要包含以下幾種：

2.1 局部路徑規劃方面

在局部路徑規劃方面，能夠被應用在移動機器人中的技術主要包含以下幾種：

（1）神經網絡路徑規劃技術。從本質上講，可以將移動機器人的路徑規劃看成是空間到行為空間感知過程的一種映射，因此，可以利用神經網絡的方式將其表現出來。就神經網絡路徑規劃技術而言，首先需要將相關傳感器數據當成網絡輸入，并將網絡輸出看成是某固定場合中期望運動方向角增量。在這種情況下，原始樣本集則可以用不同選定位置對應的數據代替。為了保證樣本集數據的有效性，需要將原始樣本集中的沖突樣本數據以及重復樣本數據剔除掉。對最終樣本集應用模糊規則，實現神經網絡的有效訓練。當典型樣本學習完成之后，移動機器人對規則的掌握水平發生了顯著提升，進而使得移動機器人在產生智能性能的基礎上，順利完成相應運動[2]。

（2）人工勢場路徑規劃技術。這種規劃技術是指，將移動機器人在實際環境中的運動過程當成其在虛擬人工受力場中的一種運動。在虛擬人工受力場中，目標終點會對移動機器人產生一定的引力，而該受力場中的障礙物則會對其產生一定的斥力。在某固定算法的作用下，這兩種不同的作用力會產生相應的勢，進而形成勢場。當移動機器人在該場中運動時，勢場中的抽象力會作用在移動機器人上，使得其完成對障礙物的有效避開。在人工勢場路徑規劃技術的實際應用過程中，由于結構簡單等因素的影響，移動機器人在到達終點之前可能會停留在局部最優點位置上。對此，需要從數學的角度出發，對勢場方程進行重新定義，通過這種方式排除勢場中的局部極值，繼而保證移動機器人運動的順利進行[3]。

（3）遺傳路徑規劃技術。這種路徑規劃技術建立在自然遺傳機制等理論的基礎上。這種技術通過變異、選擇以及交叉對控制機構的正確計算程序進行合理編制，進而實現數學方式基礎上生物進化過程的合理模擬。當移動機器人的適應度函數為正數時，允許適應度函數具有不連續或不可導特點。由于這種路徑規劃技術不涉及梯度信息，因此其能夠更好地解決移動機器人在實際運動過程中遇到的問題。遺傳路徑規劃技術的應用優勢在于，它能夠實現跟蹤與規劃的同時進行，因此，遺傳路徑規劃技術通常被應用在具有時變特點的未知環境中。

2.2 全局路徑規劃方面

在該方面，可以被應用在移動機器人中的技術主要包含以下幾種：

（1）柵格路徑規劃技術。這種技術是指，在將實際工作環境分成許多包含二值信息的網格單元的基礎上，應用優化算法完成最佳路徑的規劃搜索。在這種規劃技術中，其網格單元通常是由八叉樹或者四叉樹的方式表示出來。在該技術的應用中，柵格的作用是完成相關環境信息的記錄。如果柵格中某位置的累計值相對較低，代表移動機器人可以從該位置通過；如果柵格中某個位置的累計值相對較高，則表示該位置存在障礙物，此時，移動機器人需要利用優化算法將該障礙物避開[4]。

（2）可視圖路徑規劃技術。這種路徑規劃技術是指，將整個移動機器人看成一個點，然后分別將其與障礙物以及目標終點連接起來，上述連線要求為保證所連直線不會碰觸障礙物。當所有連線都連完之后，即完成了一整張可視圖。在該可視圖中，由于起點到目標終點之間的連線都不涉及障礙物，因此上述所有連線都屬于有效直線。在這種情況下，需要解決的問題主要是從這些連線中找出一條距離最短的連線。對此，需要應用優化算法將可視圖中距離較長的連線刪除，這種處理方式能夠有效提升移動機器人的搜索時間。

（3）拓撲路徑規劃技術。這種規劃技術是指，將移動機器人的移動范圍，即規劃區域分成多個具有拓撲特征的子空間，然后利用不同子空間之間的連通性完成拓撲網絡的構建。當該網絡構建完成后，直接從網絡中找出能夠使得機器人順利從起點移動到終點的拓撲路徑，將所得的拓撲路徑作為參考依據完成幾何路徑的計算。這種規劃技術的劣勢主要表現為其拓撲網絡的構建過程較為復雜。但這種規劃技術可以實現移動機器人搜索空間的有效縮小[5]。

3 結論

路徑規劃技術主要分為局部規劃和全局規劃兩方面。這兩方面分別包含人工勢場路徑規劃技術以及神經網絡路徑規劃技術等。應用這些規劃技術之后，移動機器人可以在避開障礙物的基礎上，順利完成起點到終點最優運行軌跡的運動。

參考文獻：

[1]朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010（07）：961-967.

[2]張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005（02）：439-443.

[3]鮑慶勇，李舜酩，沈`，門秀花.自主移動機器人局部路徑規劃綜述[J].傳感器與微系統，2009（09）：1-4+11.

篇（10）

一、庫存與配送系統聯合優化研究分類

1.聯合優化思路。在庫存與配送聯合優化研究提出之前，大多學者都是單獨對企業庫存與配送進行研究的，比如考慮輸入輸出對動態庫存進行研究，單獨進行配送線路規劃，動態庫存管理研究中輸入輸出是已知的，沒有考慮輸入輸出受企業采購過程中供應商配送的影響，而單獨的運輸線路規劃問題則沒有考慮庫存內部動態管理，因此，對庫存與配送系統聯合優化研究很有必要，目前該類研究大致可以分為以下類型：

一類研究基于供應鏈整體成本，構建模型求得整體的訂貨量與配送策略。此類研究綜合考慮了供應鏈各節點企業的三大成本“庫存、采購與運輸”，基于各方需求統一確定，互相了解需求，并且不允許缺貨情況的發生，運輸服務統一由第三方提供，構建的目標優化模型以生產商的生產成本、零售商的采購、庫存成本，以及運輸服務提供方的運輸成本，以此求得最優解。但是該類研究沒有考慮供應鏈參與各方的合作情況，各方對于利益的分配、成本的分攤機制沒有考慮，容易造成分配不均而產生摩擦。

另外一類研究則是是由供應商主導庫存配送，考慮一個供應商對多個零售商的庫存-配送進行管理，構建模型對各獨立零售商的庫存進行管理，基于各地庫存對時間、數量的需求，以自身成本最小為目標，進行路線規劃，及時給零售商補貨。供應商管理庫存與前一類研究不同，兩類研究均從總體成本最優角度出發，但是前一類研究沒有厘清供應鏈中各企業角色，及相應的職責，此類研究確定了供應商管理庫存，則明確了研究的類型，對于成本分配問題有了較好的解決。通過建立合理的數學算法可以對基于庫存考慮的線路規劃問題求得最優解，通過供應鏈各節點的協同配合促進運作效率，各方均獲得最大收益，為實際供應鏈運作提供參考。

2.算法研究分類。庫存-配送系統可以視為庫存-路徑問題的升級版，但是本質考慮的重點仍然是供應鏈各方庫存保有量、采購量、采購周期，與運輸路徑選擇之間的合理調節。對于庫存-路徑問題的算法研究較多，我們可以借鑒其相關算法應用于庫存-配送系統研究。

（1）啟發式算法。運用啟發式算法對庫存-路徑問題進行求解的研究比較普遍，如蟻群算法、鄰域搜索算法、禁忌搜索算法、模擬退火算法、遺傳算法及人工神經網絡等智能算法都或多或少有應用于庫存-路徑研究領域，其中遺傳算法有較好的收斂性，能較快地達到全局最優解，并且有優勝劣汰的算法規則，最多地被運用或改進后運用于庫存-路徑求解。

（2）C-W節約算法。C-W算法是解決旅行商提出的，基于節約的理念，適用于物流單元間流量較為穩定，變化不大的問題，是一種較為簡潔實用的算法。由供應商主導庫存，為多個零售商供貨可以解決信息不對稱造成的庫存過度配置，配送次數多配送量過大的情形，可以達到配送次數最少，配送量最經濟（供應商、零售商采用最佳采購量）的效果，此時配送路線上配送較為穩定，配送變化不會太大，不會因為市場需求變動過大而引起配送問題，因為供應商對零售商的庫存需求情況十分了解。因此C-W算法比較適合研究庫存-路徑問題，多數學者采用遺傳算法或其他優化算法是都會結合C-W算法特點進行研究。

（3）其他算法。除運籌學領域優化算法、智能算法與C-W算法這幾類典型的庫存-路徑求解算法之外，一些學者還采用概率論領域的馬爾科夫決策過程研究隨機需求下的庫存-路徑算法，也有學者采用分散決策算法（DDA decentralized decision algorithm）以求解分散決策情形下的庫存與運輸問題）。

二、庫存與配送系統聯合優化模型構建

庫存與配送系統聯合優化是促進供應鏈一體化的有效手段，本文基于供應商統一管理庫存構建一個供應商對多個零售商配送的簡單兩級供應鏈模型。

1.模型假設。（1）各零售商需求確定，且均與供應商形成直接連接網絡；（2）零售商不允許缺貨，不考慮提前期；（3）運輸費用與距離成正比；（4）一個運輸車輛一天只做一次配送，在不超過運輸車輛的滿載負荷前提下可以為多個零售商配送；（5）多個零售商的不同貨物可以拼車運貨，這一點由供應商統一管理庫存，統一配送可以比較好地解決。