序論：好文章的創(chuàng)作是一個不斷探索和完善的過程，我們?yōu)槟扑]十篇路徑規(guī)劃典型算法范例，希望它們能助您一臂之力，提升您的閱讀品質(zhì)，帶來更深刻的閱讀感受。

篇（1）

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

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

根據(jù)機器人工作環(huán)境路徑規(guī)劃模型可分為兩種:基于模型的全局路徑規(guī)劃,這種情況的作業(yè)環(huán)境的全部信息為已知;基于傳感器的局部路徑規(guī)劃,作業(yè)環(huán)境信息全部未知或部分未知,又稱動態(tài)或在線路徑規(guī)劃。

1 全局路徑規(guī)劃

全局路徑規(guī)劃主要方法有:可視圖法、自由空間法、柵格法、拓撲法、神經(jīng)網(wǎng)絡法等。

1.1 可視圖法

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

1.2 拓撲法

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

1.3 柵格法

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

1.4 自由空間法

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

1.5 神經(jīng)網(wǎng)絡法

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

2 局部路徑規(guī)劃

局部路徑規(guī)劃包括人工勢場法、模糊邏輯算法、神經(jīng)網(wǎng)絡法、遺傳算法等。

2.1 人工勢場法

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

2.2 模糊邏輯算法

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

2.3 神經(jīng)網(wǎng)絡法

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

2.4 遺傳算法

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

3 移動機器人路徑規(guī)劃技術的發(fā)展展望

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

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

參考文獻

篇（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 引言

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

系統(tǒng)中的最短路徑問題的一個具體應用。

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

2 A*算法

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

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

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

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

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

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

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

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

具體實現(xiàn)如下：

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

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

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

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

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

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

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

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

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

根據(jù)步驟三，針對圖1，算法的具體實現(xiàn)如圖2。

4)重復第三步：

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

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

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

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

4 結語

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

參考文獻：

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

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

篇（3）

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

一、對最佳路徑的分析

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

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

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

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

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

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

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

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

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

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

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

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

總結

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

參考文獻

[1]鄧群，孫才新，周駁.采用動態(tài)規(guī)劃技術實現(xiàn)配電網(wǎng)恢復供電[J].重慶大學學報（自然科學版），2006，29（3）：40-44.

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

[3]鄧昆英，汪鳳嬌，饒杰等.智能配電網(wǎng)有功自治互動建模研究[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

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

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

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

1 環(huán)境模型描述

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

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

2 A*全局路徑規(guī)劃算法

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

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

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

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

Step1 把起始節(jié)點放入開啟列表.

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

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

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

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

3 改進的A*算法

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

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

圖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中的實線是在任意環(huán)境中A*算法規(guī)劃出的路徑1，由直線段L1 ，L2 和L3組成，本文方

法規(guī)劃出的路徑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*算法規(guī)劃出的路徑點，使得路徑更加平滑.而本文方法是先進行分割，再剔除冗余的路徑點.圖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*算法，本文方法得到的路徑也更加優(yōu)化.

4 實 驗

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

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

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

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

情形4 本文算法中存在一個分割步長k，這里將考察參數(shù)k對算法效果的影響.令環(huán)境障礙率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的矩形環(huán)境.起點（0.9 m，0.9 m），終點（2.7 m，6.3 m），機器人在起點的角度為90°.為了使用本文改進的A*算法進行路徑規(guī)劃，需要先建立環(huán)境的柵格模型，設置柵格元素為0.6 m×0.6 m的正方形，對實際障礙物進行膨化處理，映射成圖14的黑色柵格.分別采用A*算法、文獻[15]的平滑A*算法和本文算法進行移動機器人的路徑規(guī)劃.圖14的直線段La1a5，La5a11，La11a21，La21a27，La27a32，La32a44 和

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

5 結 論

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

參考文獻

[1] 席裕庚，張純剛.一類動態(tài)不確定環(huán)境下機器人的滾動路徑規(guī)劃[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] 張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)劃技術的現(xiàn)狀與展望[J].系統(tǒng)仿真學報，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] 朱大奇，顏明重.移動機器人路徑規(guī)劃技術綜述[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] 吳乙萬，黃智.基于動態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[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] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規(guī)劃算法[J].沈陽工業(yè)大學學報，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īng)網(wǎng)絡在移動機器人路徑規(guī)劃中的應用[J].系統(tǒng)仿真學報，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] 郝冬，劉斌.基于模糊邏輯行為融合路徑規(guī)劃方法[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]鄧高峰，張雪萍，劉彥萍.一種障礙環(huán)境下機器人路徑規(guī)劃的蟻群粒子群算法[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]吳憲祥，郭寶龍，王娟.基于粒子群三次樣條優(yōu)化的移動機器人路徑規(guī)劃算法[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]王雪松，高，程玉虎，等.知識引導遺傳算法實現(xiàn)機器人路徑規(guī)劃[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*算法的室內(nèi)移動機器人路徑規(guī)劃[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]王紅衛(wèi)，馬勇，謝勇，等.基于平滑A*算法的移動機器人路徑規(guī)劃[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

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

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

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

1 路徑規(guī)劃方法

1.1 相關研究

1) A*算法

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

2) 人工勢能法

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

1.2 路徑規(guī)劃方法描述

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

2 環(huán)境構造

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

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

3 數(shù)據(jù)的采集

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

4 實現(xiàn)過程

第1步:對環(huán)境信息進行數(shù)據(jù)采集并轉化成相應的平面坐標數(shù)據(jù)。

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

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

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

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

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

5 仿真結果及結論

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

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

6 總結

本文對多智能體在動態(tài)環(huán)境下路徑規(guī)劃技術進行了研究探索,提出了一種能夠?qū)⑷致窂揭?guī)劃方法和局部路徑規(guī)劃方法相結合,通過仿真取得了很好的結果,證明A*和人工勢場算法的結合可行。

參考文獻:

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

篇（6）

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

一、路徑規(guī)劃的意義

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

二、白車身焊接機器人焊接路徑規(guī)劃

（一）路徑規(guī)劃的基本任務

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

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

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

要想實現(xiàn)較低的制造成本就是最大化的利用現(xiàn)有資源，提高機器人的工作效率，縮短機器人工位的生產(chǎn)周期，減少機器人的使用數(shù)量。路徑規(guī)劃的重要方向就是提高生產(chǎn)率，保證生產(chǎn)環(huán)節(jié)的順利進行，縮短生產(chǎn)周期，提高生產(chǎn)率。

（二）路徑規(guī)劃

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

（三）遺傳算法

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

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

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

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

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

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

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

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

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

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

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

三、路徑規(guī)劃的仿真

（一）仿真系統(tǒng)的各要素

路徑仿真系統(tǒng)一般要具有以下幾個基本要素：

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

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

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

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

仿真系統(tǒng)中都要獲取軌跡行為，這些行為的獲取主要是根據(jù)時間的推移而產(chǎn)生的。

（二）仿真軟件的選擇

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

四、小結

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

參考文獻：

篇（7）

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

引言

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

一、儲位分配問題

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

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

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

二、訂單分批問題

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

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

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

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

三、揀選路徑問題

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

四、揀選作業(yè)系統(tǒng)仿真技術

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

參考文獻：

[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]陳璐，陸志強.自動化立體倉庫中的儲位分配及存取路徑優(yōu)化[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 引言

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

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

2 問題描述

本節(jié)分別描述了無人車路徑規(guī)劃問題和B樣條曲線。

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

路徑規(guī)劃得到的是一條從初始位置到目標位置的路徑，即二維平面內(nèi)一條從初始位置點到目標位置點的曲線，曲線上的每一個點表示車在行駛過程中的一個狀態(tài)。考慮到實現(xiàn)方便，本文將路徑描述成離散點序列[Sstart，S1，???，Sn，Sgoal]，如圖1所示，序列中每一個點[Si（xi，yi，θi）]表示車的一個狀態(tài)，其中[（xi，yi）]表示此時刻車輛的位置，[θi]表示車輛的航向，[Sstart]和[Sgoal]分別表示車輛的初始狀態(tài)和目標狀態(tài)。圖1中的圓[（xobs1，yobs1，robs1）]表示環(huán)境中的障礙物，[（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樣條曲線的次數(shù)，[t]為控制參數(shù)，其取值范圍為[[0，1]]，[Pi+k]為控制點，[Fk，n（t）]為B樣條基。依次連接全部[n]階B樣條曲線段就組成了整條B樣條曲線。

3 本文算法

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

3.1 基于B樣條曲線的路徑規(guī)劃方法

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

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

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

（a） 路徑簇

（b） 最大曲率約束

（c） 碰撞檢測

3.2 分步路徑規(guī)劃

本小節(jié)將以圖3所給定的場景為例，講述最優(yōu)路徑生成的過程。

3.2.1 路徑簇生成

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

3.2.3 最大曲率約束

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

3.2.4 碰撞檢測

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

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

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

3.2.2 最優(yōu)路徑

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

[traoptimal=arg mintraids] （3）

路徑最平滑可以抽象成優(yōu)化問題：

[traoptimal=arg mintraiκ2] （4）

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

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

4 結論

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

參考文獻：

篇（9）

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

0 前言

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

1 路徑規(guī)劃技術的作用

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

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

2 移動機器人路徑規(guī)劃技術綜述

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

2.1 局部路徑規(guī)劃方面

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

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

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

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

2.2 全局路徑規(guī)劃方面

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

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

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

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

3 結論

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

參考文獻：

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

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

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

篇（10）

一、庫存與配送系統(tǒng)聯(lián)合優(yōu)化研究分類

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

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

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

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

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

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

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

二、庫存與配送系統(tǒng)聯(lián)合優(yōu)化模型構建

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

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