路徑規(guī)劃典型算法匯總十篇

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

篇（1）

中圖分類號 TP242 文獻(xiàn)標(biāo)識碼 A 文章編號 1674-6708(2009)10-0067-02

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

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

1 全局路徑規(guī)劃

全局路徑規(guī)劃主要方法有:可視圖法、自由空間法、柵格法、拓?fù)浞ā⑸窠?jīng)網(wǎng)絡(luò)法等。

1.1 可視圖法

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

1.2 拓?fù)浞?/p>

拓?fù)浞▽⒁?guī)劃空間分割成具有拓?fù)涮卣鞯淖涌臻g,根據(jù)彼此連通性建立拓?fù)渚W(wǎng)絡(luò),在網(wǎng)絡(luò)上尋找起始點(diǎn)到目標(biāo)點(diǎn)的拓?fù)渎窂?最終由拓?fù)渎窂角蟪鰩缀温窂健Ｍ負(fù)浞ɑ舅枷胧墙稻S法,即將在高維幾何空間中求路徑的問題轉(zhuǎn)化為低維拓?fù)淇臻g中判別連通性的問題。

1.3 柵格法

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

1.4 自由空間法

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

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

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

2 局部路徑規(guī)劃

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

2.1 人工勢場法

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

2.2 模糊邏輯算法

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

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

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

2.4 遺傳算法

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

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

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

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

參考文獻(xiàn)

篇（2）

中圖分類號：TP306文獻(xiàn)標(biāo)識碼：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ī)劃是在車輛行駛前或行駛過程中尋找車輛從起始點(diǎn)到達(dá)目的地的最佳行車路線的過程[1], 它屬于智能交通

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

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

2 A*算法

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

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

f(n)是從初始點(diǎn)通過節(jié)點(diǎn)n 到達(dá)目標(biāo)點(diǎn)的估價函數(shù)；

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

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

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

3 改進(jìn)的A*算法球最短路徑

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

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

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

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

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

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

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

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

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

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

例如圖1，為帶權(quán)的有向圖。

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

4)重復(fù)第三步：

若在深度為7的搜索中找到目標(biāo)結(jié)點(diǎn)且僅有一條路徑，則該路徑為最終路徑，返回；

若在若在深度為7的搜索中找到目標(biāo)結(jié)點(diǎn)并且有多條路徑則回朔，比較找到的路徑費(fèi)用，取權(quán)值最小的作為最終路徑；

若在在深度為7的搜索中未找到任何目標(biāo)點(diǎn)則跳轉(zhuǎn)到第五步。

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

篇（3）

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

一、對最佳路徑的分析

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

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

參考文獻(xiàn)

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

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

[3]鄧?yán)ビⅲ豇P嬌，饒杰等.智能配電網(wǎng)有功自治互動建模研究[J].機(jī)電工程技術(shù)，2014，（2）：4-7.

篇（4）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 改進(jìn)的A*算法

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

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

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

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

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

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

圖4中的實(shí)線是在任意環(huán)境中A*算法規(guī)劃出的路徑1，由直線段L1 ，L2 和L3組成，本文方

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

路徑3的總轉(zhuǎn)折角度：

其中α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*算法，本文方法縮短了總路徑長度，減小了總轉(zhuǎn)折角度.

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

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

4 實(shí) 驗(yàn)

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

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

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

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

情形4 本文算法中存在一個分割步長k，這里將考察參數(shù)k對算法效果的影響.令環(huán)境障礙率p=30%，僅有一個任務(wù)點(diǎn)（198，198），起點(diǎn)是（4，4），機(jī)器人在起點(diǎn)的角度為90°.在不同的分割步長下進(jìn)行了50實(shí)驗(yàn)，并求出相應(yīng)的均值，驗(yàn)結(jié)果如圖11和圖12所示.可以得出這樣的結(jié)論：當(dāng)分割步長越小時，本文算法得到的路徑長度和轉(zhuǎn)折角度也越小.顯然，這是因?yàn)榉指畈介L越小，路徑分割得越精細(xì)，路徑長度和轉(zhuǎn)折角度也就相應(yīng)減小.

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

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

5 結(jié) 論

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

參考文獻(xiàn)

[1] 席裕庚，張純剛.一類動態(tài)不確定環(huán)境下機(jī)器人的滾動路徑規(guī)劃[J].自動化學(xué)報，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ī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報，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ī)器人路徑規(guī)劃技術(shù)綜述[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].湖南大學(xué)學(xué)報：自然科學(xué)版，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ī)器人全局路徑規(guī)劃算法[J].沈陽工業(yè)大學(xué)學(xué)報，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)絡(luò)在移動機(jī)器人路徑規(guī)劃中的應(yīng)用[J].系統(tǒng)仿真學(xué)報，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].計算機(jī)工程與設(shè)計，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)境下機(jī)器人路徑規(guī)劃的蟻群粒子群算法[J].控制理論與應(yīng)用，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)化的移動機(jī)器人路徑規(guī)劃算法[J].機(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]王雪松，高，程玉虎，等.知識引導(dǎo)遺傳算法實(shí)現(xiàn)機(jī)器人路徑規(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]王殿君.基于改進(jìn)A*算法的室內(nèi)移動機(jī)器人路徑規(guī)劃[J].清華大學(xué)學(xué)報：自然科學(xué)版，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*算法的移動機(jī)器人路徑規(guī)劃[J].同濟(jì)大學(xué)學(xué)報：自然科學(xué)版，2010，38（11）： 1647-1651.

篇（5）

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

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

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

1 路徑規(guī)劃方法

1.1 相關(guān)研究

1) A*算法

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

2) 人工勢能法

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

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

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

2 環(huán)境構(gòu)造

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

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

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

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

4 實(shí)現(xiàn)過程

第1步:對環(huán)境信息進(jìn)行數(shù)據(jù)采集并轉(zhuǎn)化成相應(yīng)的平面坐標(biāo)數(shù)據(jù)。

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

第3步:建立柵格,對柵格進(jìn)行初始化。

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

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

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

5 仿真結(jié)果及結(jié)論

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

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

6 總結(jié)

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

參考文獻(xiàn):

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

篇（6）

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

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

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

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

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

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

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

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

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

（二）路徑規(guī)劃

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

（三）遺傳算法

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

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

第一，白車身中所需要焊接的焊接點(diǎn)眾多。

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

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

第四，因?yàn)榉桨缸罱K應(yīng)用于企業(yè)，所以數(shù)學(xué)方法最好要簡潔明了，便于學(xué)習(xí)。

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

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

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

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

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

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

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

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

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

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

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

模型行為可以大致分為三種：軌跡行為、結(jié)構(gòu)行為以及點(diǎn)行為。

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

（二）仿真軟件的選擇

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

四、小結(jié)

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

參考文獻(xiàn)：

篇（7）

中圖分類號：F715.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1001-828X（2014）010-00-01

引言

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

一、儲位分配問題

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

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

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

二、訂單分批問題

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

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

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

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

三、揀選路徑問題

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

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

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

參考文獻(xiàn)：

[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]陳璐，陸志強(qiáng).自動化立體倉庫中的儲位分配及存取路徑優(yōu)化[J].管理工程學(xué)報，2012，26（1）：42-47.

篇（8）

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：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 引言

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

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

2 問題描述

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

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

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

2.2 B樣條曲線

如果給定[m+n+1]個控制點(diǎn)[Pi（i=0，1，???，m+n）]，就可以構(gòu)造[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]為控制點(diǎn)，[Fk，n（t）]為B樣條基。依次連接全部[n]階B樣條曲線段就組成了整條B樣條曲線。

3 本文算法

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

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

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

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

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

（a） 路徑簇

（b） 最大曲率約束

（c） 碰撞檢測

3.2 分步路徑規(guī)劃

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

3.2.1 路徑簇生成

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

3.2.3 最大曲率約束

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

3.2.4 碰撞檢測

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

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

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

3.2.2 最優(yōu)路徑

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

[traoptimal=arg mintraids] （3）

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

[traoptimal=arg mintraiκ2] （4）

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

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

4 結(jié)論

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

參考文獻(xiàn)：

篇（9）

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

0 前言

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

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

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

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

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

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

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

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

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

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

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

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

在該方面，可以被應(yīng)用在移動機(jī)器人中的技術(shù)主要包含以下幾種：

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

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

（3）拓?fù)渎窂揭?guī)劃技術(shù)。這種規(guī)劃技術(shù)是指，將移動機(jī)器人的移動范圍，即規(guī)劃區(qū)域分成多個具有拓?fù)涮卣鞯淖涌臻g，然后利用不同子空間之間的連通性完成拓?fù)渚W(wǎng)絡(luò)的構(gòu)建。當(dāng)該網(wǎng)絡(luò)構(gòu)建完成后，直接從網(wǎng)絡(luò)中找出能夠使得機(jī)器人順利從起點(diǎn)移動到終點(diǎn)的拓?fù)渎窂剑瑢⑺玫耐負(fù)渎窂阶鳛閰⒖家罁?jù)完成幾何路徑的計算。這種規(guī)劃技術(shù)的劣勢主要表現(xiàn)為其拓?fù)渚W(wǎng)絡(luò)的構(gòu)建過程較為復(fù)雜。但這種規(guī)劃技術(shù)可以實(shí)現(xiàn)移動機(jī)器人搜索空間的有效縮小[5]。

3 結(jié)論

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

參考文獻(xiàn)：

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

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

[3]鮑慶勇，李舜酩，沈`，門秀花.自主移動機(jī)器人局部路徑規(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)化研究提出之前，大多學(xué)者都是單獨(dú)對企業(yè)庫存與配送進(jìn)行研究的，比如考慮輸入輸出對動態(tài)庫存進(jìn)行研究，單獨(dú)進(jìn)行配送線路規(guī)劃，動態(tài)庫存管理研究中輸入輸出是已知的，沒有考慮輸入輸出受企業(yè)采購過程中供應(yīng)商配送的影響，而單獨(dú)的運(yùn)輸線路規(guī)劃問題則沒有考慮庫存內(nèi)部動態(tài)管理，因此，對庫存與配送系統(tǒng)聯(lián)合優(yōu)化研究很有必要，目前該類研究大致可以分為以下類型：

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

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

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

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

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

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

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

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

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