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

篇（1）

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

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

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

1 全局路徑規(guī)劃

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

1.1 可視圖法

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

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法,即將在高維幾何空間中求路徑的問(wèn)題轉(zhuǎn)化為低維拓?fù)淇臻g中判別連通性的問(wèn)題。

1.3 柵格法

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

1.4 自由空間法

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

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

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

2 局部路徑規(guī)劃

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

2.1 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法基本思想是將移動(dòng)機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一種虛擬人工受力場(chǎng)中的運(yùn)動(dòng)。障礙物對(duì)移動(dòng)機(jī)器人產(chǎn)生斥力,目標(biāo)點(diǎn)產(chǎn)生引力,引力和斥力周?chē)梢欢ǖ乃惴óa(chǎn)生相應(yīng)的勢(shì),機(jī)器人在勢(shì)場(chǎng)中受到抽象力作用,抽象力使得機(jī)器人繞過(guò)障礙物。

2.2 模糊邏輯算法

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

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

模糊控制算法有諸多優(yōu)點(diǎn),但也有固有缺陷:人的經(jīng)驗(yàn)不一定完備;輸入量增多時(shí),推理規(guī)則或模糊表會(huì)急劇膨脹。神經(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)場(chǎng)合下期望運(yùn)動(dòng)方向角增量作為網(wǎng)絡(luò)輸出,由多個(gè)選定位姿下的一組數(shù)據(jù)構(gòu)成原始樣本集,經(jīng)過(guò)剔除重復(fù)或沖突樣本等加工處理,得到最終樣本集。

2.4 遺傳算法

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

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

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

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

參考文獻(xiàn)

篇（2）

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

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

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

2 A*算法

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

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

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

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

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

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

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

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

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

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

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

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

3)對(duì)第二步在深度4時(shí)形成的OPEN表進(jìn)行操作，若OPEN表為空．則宣告失?。悍駝t，選取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ù)庫(kù)包含的聯(lián)接路段屬性擴(kuò)展并生成NEXT的后繼節(jié)點(diǎn)。對(duì)于每一個(gè)后繼節(jié)點(diǎn)n，進(jìn)行下列過(guò)程：

①計(jì)算節(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表中。計(jì)算節(jié)點(diǎn)n的估價(jià)函數(shù)：f(n)=g(n)+h(n)

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

根據(jù)步驟三，針對(duì)圖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)，最后報(bào)告若干條路徑，比較個(gè)路徑費(fèi)用，取費(fèi)用最小的前100條路徑繼續(xù)重復(fù)第三步、第四步。由于h函數(shù)在滿(mǎn)足h下限得條件下，愈趨近于h效率愈高，因此實(shí)際應(yīng)用中，我們?nèi)〉氖枪?jié)點(diǎn)到目的點(diǎn)的直線距離保證滿(mǎn)足下限的情況下，盡可能的趨近h。

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

篇（3）

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

一、對(duì)最佳路徑的分析

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

本文主要從兩個(gè)方面左手，共同分析了采用動(dòng)態(tài)規(guī)劃技術(shù)實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電的方法與效果，一方面著手于最佳路徑的分析，另一方面著手于最佳路徑的選擇方法。從這兩個(gè)方面可以看出，利用動(dòng)態(tài)規(guī)劃技術(shù)去實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電是一種可行的方法。但是，受到歷史原因的影響，我國(guó)城市配電網(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)供電提供了一定的保障，同時(shí)也為恢復(fù)配電網(wǎng)故障供電創(chuàng)建了良好的環(huán)境與條件等。

參考文獻(xiàn)

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

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

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

篇（4）

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

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

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

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

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

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

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

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

式中：g（n）是狀態(tài)空間中從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)，h（n）是從節(jié)點(diǎn)n到終點(diǎn)的啟發(fā)式估計(jì)代價(jià)函數(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ò)程中，需要不斷地更新兩個(gè)列表，一個(gè)是開(kāi)啟列表，另一個(gè)是關(guān)閉列表.開(kāi)啟列表存儲(chǔ)的是所有的周?chē)?jié)點(diǎn).A*算法從開(kāi)啟列表中選擇具有最小估價(jià)值的節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn).關(guān)閉列表存儲(chǔ)的是所有經(jīng)過(guò)的節(jié)點(diǎn)和環(huán)境中的障礙節(jié)點(diǎn).應(yīng)用A*算法進(jìn)行路徑搜索的具體流程如下所述：

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

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

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

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

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

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

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

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

圖3是本文算法的流程圖，圖中符號(hào)的定義如下：

k為分割路徑的步長(zhǎng)；c，m，i分別是當(dāng)前路徑點(diǎn)下標(biāo)、待連接路徑點(diǎn)下標(biāo)和新路徑點(diǎn)下標(biāo)；A為以步長(zhǎng)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 }.

注意，以步長(zhǎng)k分割路徑是在原路徑的直線段進(jìn)行的.例如，對(duì)圖4中A*算法得到的路徑進(jìn)行分割，先進(jìn)行直線段L1的分割，從起點(diǎn)開(kāi)始依次得到路徑點(diǎn)a1，a2，…，a7，此時(shí)a8與原路徑點(diǎn)的距離小于步長(zhǎng)k，則將原路徑點(diǎn)作為a8，并從路徑點(diǎn)a8開(kāi)始重復(fù)上述過(guò)程，分割直線段L2和L3直到將終點(diǎn)作為路徑點(diǎn)a20時(shí)，分割過(guò)程結(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的路徑長(zhǎng)度明顯大于路徑3的路徑長(zhǎng)度.另外，路徑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.相對(duì)于A*算法，本文方法縮短了總路徑長(zhǎng)度，減小了總轉(zhuǎn)折角度.

文獻(xiàn)[15]提出的平滑A*算法直接地剔除A*算法規(guī)劃出的路徑點(diǎn)，使得路徑更加平滑.而本文方法是先進(jìn)行分割，再剔除冗余的路徑點(diǎn).圖4中直線段La1a8，La8a11和La11a20是文獻(xiàn)[15]中平滑A*算法得到的路徑2.顯然，路徑2的長(zhǎng)度大于路徑3的長(zhǎng)度.另外，路徑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.相對(duì)于文獻(xiàn)[15]提出的平滑A*算法，本文方法得到的路徑也更加優(yōu)化.

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

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

情形1 環(huán)境障礙率（障礙柵格數(shù)量占總柵格數(shù)量的比例）p=30%，取本文算法的分割步長(zhǎng)k=0.1，目標(biāo)數(shù)n=1即只有一個(gè)終點(diǎn)，起點(diǎn)是（4，4），終點(diǎn)是（198，198），機(jī)器人在起點(diǎn)的角度為90°.進(jìn)行了50次實(shí)驗(yàn)，圖5和圖6是不同算法規(guī)劃出的路徑長(zhǎng)度和轉(zhuǎn)折角度，表1是3種算法50次實(shí)驗(yàn)的各項(xiàng)平均值比較.從實(shí)驗(yàn)結(jié)果中可以看出，本文提出的改進(jìn)A*算法相對(duì)于A* 算法和文獻(xiàn)[15]的平滑A* 算法，有效地減少了路徑長(zhǎng)度和轉(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)境障礙率下，各個(gè)算法的性能.令分割步長(zhǎng)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%時(shí)，進(jìn)行了50次實(shí)驗(yàn)，并求得不同障礙率下路徑長(zhǎng)度的均值和轉(zhuǎn)折角度的均值，實(shí)驗(yàn)結(jié)果如圖7、圖8所示.可以看出，一方面當(dāng)環(huán)境障礙率增大時(shí)，各個(gè)算法得到的路徑長(zhǎng)度和轉(zhuǎn)折角度也在不斷增大.這是因?yàn)榄h(huán)境障礙率一定程度上代表了環(huán)境的復(fù)雜度，當(dāng)環(huán)境越復(fù)雜時(shí)，那么規(guī)劃的路徑長(zhǎng)度和轉(zhuǎn)折角度也就越大；另一方面，在圖7和圖8中，方框內(nèi)的數(shù)據(jù)是本文算法相對(duì)于A*算法路徑長(zhǎng)度和轉(zhuǎn)折角度的減少量.當(dāng)環(huán)境障礙率越大時(shí)，路徑長(zhǎng)度和轉(zhuǎn)折角度的減少量也不斷增大，這說(shuō)明相對(duì)于A*算法，本文方法更加適合在障礙物較多的環(huán)境中使用.

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

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

在實(shí)物實(shí)驗(yàn)中，本文采用的移動(dòng)機(jī)器人是Turtlebot2，移動(dòng)底座的最大移動(dòng)速度：0.7 m/s，最大角速度：180°/s.采用ThinkPad E450C筆記本電腦作為移動(dòng)機(jī)器人的控制器.移動(dòng)機(jī)器人的實(shí)際運(yùn)動(dòng)空間如圖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的正方形，對(duì)實(shí)際障礙物進(jìn)行膨化處理，映射成圖14的黑色柵格.分別采用A*算法、文獻(xiàn)[15]的平滑A*算法和本文算法進(jìn)行移動(dòng)機(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é)果.由于移動(dòng)機(jī)器人的運(yùn)動(dòng)總是存在外界干擾和運(yùn)動(dòng)精度等因素，其運(yùn)動(dòng)的實(shí)際路徑長(zhǎng)度與轉(zhuǎn)折角度總是比規(guī)劃的路徑長(zhǎng)度和轉(zhuǎn)折角度要稍稍大一些，如表2所示.但無(wú)論是規(guī)劃的路徑長(zhǎng)度和轉(zhuǎn)折角度，還是移動(dòng)機(jī)器人實(shí)際運(yùn)動(dòng)的路徑長(zhǎng)度和轉(zhuǎn)折角度，本文算法得到的實(shí)驗(yàn)結(jié)果都比A*算法和文獻(xiàn)[15]平滑A*算法更加優(yōu)化.

5 結(jié) 論

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

參考文獻(xiàn)

[1] 席裕庚，張純剛.一類(lèi)動(dòng)態(tài)不確定環(huán)境下機(jī)器人的滾動(dòng)路徑規(guī)劃[J].自動(dòng)化學(xué)報(bào)，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] 張捍東，鄭睿，岑豫皖.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報(bào)，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] 朱大奇，顏明重.移動(dòng)機(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] 吳乙萬(wàn)，黃智.基于動(dòng)態(tài)虛擬障礙物的智能車(chē)輛局部路徑規(guī)劃方法[J].湖南大學(xué)學(xué)報(bào)：自然科學(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áng)工業(yè)大學(xué)學(xué)報(bào)，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ò)在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，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ì)算機(jī)工程與設(shè)計(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)境下機(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)化的移動(dòng)機(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]王雪松，高，程玉虎，等.知識(shí)引導(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)移動(dòng)機(jī)器人路徑規(guī)劃[J].清華大學(xué)學(xué)報(bào)：自然科學(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*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（11）： 1647-1651.

篇（5）

中圖分類(lèi)號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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

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

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

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

1 路徑規(guī)劃方法

1.1 相關(guān)研究

1) A*算法

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

2) 人工勢(shì)能法

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

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

鑒于A*算法全局路徑搜索的全局性與改進(jìn)人工勢(shì)場(chǎng)算法局部路徑搜索的靈活性,通過(guò)一定的方法把兩者結(jié)合起來(lái),其思路如下:多智能體分別采用A*算法進(jìn)行全局路徑規(guī)劃,各自生成到達(dá)目標(biāo)點(diǎn)的子目錄節(jié)點(diǎn)序列,同時(shí)采用改進(jìn)的人工勢(shì)能對(duì)子目錄節(jié)點(diǎn)序列中相鄰節(jié)點(diǎn)進(jìn)行路徑的平滑和優(yōu)化處理,該方法不但能夠充分利用已知環(huán)境信息生成全局最優(yōu)路徑,而且還能及時(shí)處理所遇到的隨機(jī)障礙(其它智能體)信息,從而提高了多智能體整體的路徑規(guī)劃的性能。由于A*方法采用柵格表示地圖,柵格粒度越小,障礙物的表示也就越精確,但是同時(shí)算法搜索的范圍會(huì)按指數(shù)增加。采用改進(jìn)人工勢(shì)場(chǎng)的局部路徑規(guī)劃方法對(duì)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)格,每格為一個(gè)單元,并假設(shè)障礙的位置和大小已知,且在機(jī)器人運(yùn)動(dòng)過(guò)程中不會(huì)發(fā)生變化。柵格法中的網(wǎng)格單元共有三種類(lèi)型,即障礙網(wǎng)格、自由網(wǎng)格和機(jī)器人所在網(wǎng)格。目前常用的柵格表示方法有兩種,即直角坐標(biāo)法和序號(hào)法。這兩種表示方法本質(zhì)上是一樣的,每個(gè)單元格都與(x, y)一一對(duì)應(yīng)。本文采用序號(hào)法表示柵格,設(shè)柵格的中心點(diǎn)坐標(biāo)為柵格的直角坐標(biāo),則每個(gè)柵格編號(hào)都與其直角坐標(biāo)一一對(duì)應(yīng),地圖中任意一點(diǎn)(x,y)與柵格編號(hào)N的映射關(guān)系為:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x軸的取值范圍,Gs表示柵格尺寸的大小,INT函數(shù)表示取整,而柵格中心點(diǎn)的坐標(biāo)為(xG,yG),它與柵格編號(hào)N之間的關(guān)系為:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符號(hào)%表示取余操作。本文中根據(jù)機(jī)器人的尺寸來(lái)確定柵格的粒度,假設(shè)一個(gè)柵格能容納一個(gè)智能體,這里選擇柵格的大小為40cm×40cm[5]。本文的仿真環(huán)境為800cm×800cm,柵格號(hào)N=0~399,機(jī)器人的初始位置的柵格號(hào)為N=42,目標(biāo)位置的柵格號(hào)為N=314。在Visual Studio 2005中進(jìn)行仿真,仿真結(jié)果如圖1所示,長(zhǎng)方形和橢圓圖形代表障礙物柵格,小圓圈所代表的柵格為機(jī)器人的起始柵格和目標(biāo)柵格,剩下的是自由柵格。在路徑規(guī)劃中機(jī)器人可以選擇自由柵格作為它的路徑點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

6 總結(jié)

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

參考文獻(xiàn):

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

篇（6）

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

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

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

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

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

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

第一，最大程度的使用機(jī)器人工位。使用機(jī)器人工位能夠有效降低工人的勞動(dòng)強(qiáng)度，減少人為錯(cuò)誤幾率，提高焊接的準(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ī)劃

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

（三）遺傳算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第三，模型行為及對(duì)行為的處理。

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

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

（二）仿真軟件的選擇

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

四、小結(jié)

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

參考文獻(xiàn)：

篇（7）

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

引言

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

一、儲(chǔ)位分配問(wèn)題

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

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

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

二、訂單分批問(wèn)題

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

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

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

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

三、揀選路徑問(wèn)題

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

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

揀貨作業(yè)問(wèn)題不僅包括以上三個(gè)問(wèn)題，還包括人員配置、設(shè)備選擇、流程優(yōu)化等很多問(wèn)題，揀貨作業(yè)系統(tǒng)作為配送中心的核心子系統(tǒng)，它的優(yōu)化與改進(jìn)對(duì)配送中心效率的提高意義重大。配送中心是典型的現(xiàn)代機(jī)械電子相結(jié)合的系統(tǒng)，也是典型的隨機(jī)型離散事件系統(tǒng)，其復(fù)雜性與系統(tǒng)性可通過(guò)仿真的方法進(jìn)行設(shè)計(jì)與優(yōu)化。目前，物流系統(tǒng)仿真技術(shù)已經(jīng)越來(lái)越多的被運(yùn)用到?jīng)Q策中去，物流系統(tǒng)仿真軟件也有了更多的選擇性。二維平面式動(dòng)畫(huà)表現(xiàn)形式（2D）的有ARENA、Em-Plant、WITNESS、EXTEND，三維立體（3D）的有Flexsim、Automod、RalC、WITNESS等。本質(zhì)上，物流仿真軟件的建模大同小異，都是通過(guò)實(shí)體的組合來(lái)建模，參數(shù)的控制來(lái)調(diào)節(jié)，目標(biāo)的設(shè)定來(lái)實(shí)現(xiàn)，并通過(guò)對(duì)結(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).自動(dòng)化立體倉(cāng)庫(kù)中的儲(chǔ)位分配及存取路徑優(yōu)化[J].管理工程學(xué)報(bào)，2012，26（1）：42-47.

篇（8）

中圖分類(lèi)號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

2 問(wèn)題描述

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

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

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

2.2 B樣條曲線

如果給定[m+n+1]個(gè)控制點(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]個(gè)[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ī)劃方法和基于該方法生成路徑的過(guò)程。

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

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

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

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

（a） 路徑簇

（b） 最大曲率約束

（c） 碰撞檢測(cè)

3.2 分步路徑規(guī)劃

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

3.2.1 路徑簇生成

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

3.2.3 最大曲率約束

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

3.2.4 碰撞檢測(cè)

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

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

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

3.2.2 最優(yōu)路徑

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

[traoptimal=arg mintraids] （3）

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

[traoptimal=arg mintraiκ2] （4）

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

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

4 結(jié)論

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

參考文獻(xiàn)：

篇（9）

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

0 前言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

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

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

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

篇（10）

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

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

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

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

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

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

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

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

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

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

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