1多機器人路徑規(guī)劃方法

　　單個機器人的路徑規(guī)劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規(guī)劃側(cè)重考慮整個系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時間最少路徑或是系統(tǒng)總路徑最短等。從目前國內(nèi)外的研究來看，在規(guī)劃多機器人路徑時，更多考慮的是多機器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

　　目前國內(nèi)外多機器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)、強化學(xué)習(xí)等；其他方法主要有動態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規(guī)劃方法擴展而來的。

　　1）傳統(tǒng)方法多機器人路徑規(guī)劃傳統(tǒng)方法的特點主要體現(xiàn)在基于圖論的基礎(chǔ)上。方法一般都是先將環(huán)境構(gòu)建成一個圖，然后再從圖中尋找最優(yōu)的路徑。其優(yōu)點是比較簡單，比較容易實現(xiàn)；缺點是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機器人在環(huán)境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產(chǎn)生斥力，目標(biāo)點產(chǎn)生引力，引力和斥力周圍由一定的算法產(chǎn)生相應(yīng)的勢，機器人在勢場中受到抽象力作用,抽象力使得機器人繞過障礙物。其優(yōu)點是適合未知環(huán)境下的規(guī)劃，不會出現(xiàn)維數(shù)爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態(tài)調(diào)度技術(shù)的多機器人路徑規(guī)劃，較好地解決了這個問題。

　　2）智能優(yōu)化方法多機器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來智能計算發(fā)展而產(chǎn)生的一些新方法。其相對于傳統(tǒng)方法更加智能化，且日益成為國內(nèi)外研究的重點。

　　遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進化的概率優(yōu)化方法，適用于處理傳統(tǒng)搜索算法難以解決的復(fù)雜和非線性問題，如多機器的路徑規(guī)劃問題。在路徑規(guī)劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構(gòu)建成一個路徑節(jié)點鏈接網(wǎng)，將路徑個體表達為路徑中一系列中途節(jié)點，并轉(zhuǎn)換為二進制串；然后進行遺傳操作（如選擇、交叉、復(fù)制、變異），經(jīng)過N次進化，輸出當(dāng)前的最優(yōu)個體即機器人的最優(yōu)路徑。遺傳算法的缺點是運算速度不快，進化眾多的規(guī)劃要占據(jù)很大的存儲空間和運算時間；優(yōu)點是有效避免了局部極小值問題，且計算量較小。

　　孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來規(guī)劃多機器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒有得到很好的解決；且規(guī)劃只能保證找到一個比較滿意的解，在求解全局最優(yōu)解時仍有局限。

　　文獻[8]中提出的一種基于定長十進編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機制及定長二進制編碼機制需特殊遺傳操作算子和特殊解碼的缺陷,使得算法更加簡單有效。

　　智能計算的另一種常見的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動過程來實現(xiàn)尋優(yōu)，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優(yōu)化問題。該算法同樣比較適合解決多機器人的路徑規(guī)劃問題。

　　朱慶保[9]提出了在全局未知環(huán)境下多機器人運動螞蟻導(dǎo)航算法。該方法將全局目標(biāo)點映射到機器人視野域邊界附近作為局部導(dǎo)航子目標(biāo)，再由兩組螞蟻相互協(xié)作完成機器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎(chǔ)上進行與其他機器人的碰撞預(yù)測與避碰規(guī)劃。因此，機器人的前進路徑不斷被動態(tài)修改，從而在每條局部優(yōu)化路徑引導(dǎo)下，使機器人沿一條全局優(yōu)化的路徑到達目標(biāo)點。但其不足是在動態(tài)不確定的環(huán)境中路徑規(guī)劃時間開銷劇增，而且機器人缺乏必要的學(xué)習(xí)，以至于整個機器人系統(tǒng)路徑難以是最優(yōu)路徑。

　　強化學(xué)習(xí)[10，11](又稱再激勵學(xué)習(xí))是一種重要的機器學(xué)習(xí)方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，使得行為從環(huán)境中獲得積累獎賞值最大。其原理如圖1所示。

　　強化學(xué)習(xí)算法一般包含了兩個步驟：a）從當(dāng)前學(xué)習(xí)循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導(dǎo)下，通過所獲得的瞬時獎懲值對該策略進行評估。學(xué)習(xí)循環(huán)過程如下所示，直到值函數(shù)和策略收斂:

　　玽0→π1→v1→π2→…→v*→π*→v*

　　目前比較常見的強化學(xué)習(xí)方法有：MonteCarlo方法、動態(tài)規(guī)劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學(xué)習(xí)算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

　　TD（0）策略：V(si)←V(si)+α[γi+1+γV(si+1)-V(si)]

　　Sarsa算法：Q(st,at)←Q(st,at)+α[γt+1+γQ(st+1,at.+1)-Q(st,at)]玅s′學(xué)習(xí)算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]

　　近年來，基于強化學(xué)習(xí)的路徑規(guī)劃日益成為國內(nèi)外學(xué)者研究的熱點。M.J.Mataric[12]首次把強化學(xué)習(xí)引入到多機器人環(huán)境中。而基于強化學(xué)習(xí)的多機器人路徑規(guī)劃的優(yōu)點主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡化了智能體的編程；無須構(gòu)建環(huán)境地圖；強化學(xué)習(xí)可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。

　　張芳等人[13]提出了基于再激勵協(xié)調(diào)避障路徑規(guī)劃方法，把再勵函數(shù)設(shè)計為基于行為分解的無模型非均勻結(jié)構(gòu)，新的再勵函數(shù)結(jié)構(gòu)使得學(xué)習(xí)速度得以提高且有較好的魯棒性。同時，證明了在路徑規(guī)劃中，機器人的趨向目標(biāo)和避障行為密切相關(guān)，對反映各基本行為的再勵函數(shù)取加權(quán)和來表示總的再勵函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵函數(shù)設(shè)計得合理與否及其確切程度將影響再勵學(xué)習(xí)的收斂速度。王醒策等人[14]在動態(tài)編隊的強化學(xué)習(xí)算法方面展開了研究。宋一然[15]則提出了分段再勵函數(shù)的強化學(xué)習(xí)方法進行路徑規(guī)劃。其缺點是學(xué)習(xí)次數(shù)較多、效率不高，當(dāng)機器人數(shù)目增加時，它有可能面臨維數(shù)災(zāi)難的困難。所以，基于強化學(xué)習(xí)的路徑規(guī)劃在多機器人環(huán)境下的學(xué)習(xí)將變得比較困難，需要對傳統(tǒng)的強化學(xué)習(xí)加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡(luò)的強化學(xué)習(xí)[16]等。

　　3)其他方法除了以上國內(nèi)外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃，把運籌學(xué)中的動態(tài)規(guī)劃思想與Dijkstra算法引入到多機器人的路徑規(guī)劃中，用動態(tài)規(guī)劃的基本思想來解決圖論中的費用流問題和路徑規(guī)劃中的層級動態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個機器人的鄰居是指在地理位置上分布在這個機器人周圍的其他機器人；與該機器人最近鄰的機器人為第一層鄰居,第一層鄰居的鄰居為該機器人的第二層鄰居,依此類推。那么層級越高（即越近)的鄰居,它滿足協(xié)作要求的可能性越大。動態(tài)規(guī)劃算法實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，必須存儲產(chǎn)生過程中的各種狀態(tài)，其空間復(fù)雜度要大于其他算法，故動態(tài)規(guī)劃方法比較適合多機器人的全局路徑規(guī)劃。

　　孫茂相等人[18]提出了最優(yōu)控制與智能決策相結(jié)合的多移動機器人路徑規(guī)劃方法。其首先構(gòu)造一個以各機器人最優(yōu)運動狀態(tài)數(shù)據(jù)庫為核心的實時專家系統(tǒng),在離線狀態(tài)下完成;然后各機器人在此專家系統(tǒng)的支持下,以最優(yōu)規(guī)劃策略為基礎(chǔ),采用速度遷移算法,自主決定其控制。該方法擁有較好的穩(wěn)定性與復(fù)雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動規(guī)劃框架較好地解決了多機器人路徑規(guī)劃在局部在線規(guī)劃的系統(tǒng)框架問題。沈捷等人[20]提出了保持隊形的多移動機器人路徑規(guī)劃。以基于行為的導(dǎo)航算法為基礎(chǔ),把機器人隊列的運動過程劃分為正常運動、避障和恢復(fù)隊形三個階段。在避障階段,引入虛擬機器人使隊形保持部分完整;當(dāng)隊形被嚴(yán)重打亂時,規(guī)劃機器人的局部目標(biāo)位姿使隊列快速恢復(fù)隊形。其算法重點為避障機器人進入避障狀態(tài),暫時脫離隊列,并以虛擬機器人代替避障機器人。

　　2多機器人避碰和避障

　　避障和避碰是多機器人路徑規(guī)劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見的多機器人避障方法[21]有主從控制法、動態(tài)優(yōu)先法（建立在機器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢場的方法等。

　　目前國內(nèi)外對于多機器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎(chǔ)，擴充并完善了路徑/速度分解方案來協(xié)調(diào)多機器人,設(shè)立集中管理゛gent進行整體規(guī)劃，為每個機器人規(guī)劃路徑；并根據(jù)優(yōu)先級規(guī)則對運動特征進行分布式規(guī)劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規(guī)劃系統(tǒng)，將原來比較復(fù)雜的大系統(tǒng)轉(zhuǎn)換為相對簡單的子系統(tǒng)問題,由各智能機器人依據(jù)任務(wù)要求和環(huán)境變化,獨立調(diào)整自身運動狀態(tài),完成任務(wù)的分布式智能決策體系結(jié)構(gòu)。任炏等人[24]提出了基于過程獎賞和優(yōu)先掃除的強化學(xué)習(xí)多機器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少沖突,避免死鎖,提高了系統(tǒng)整體性能。歐錦軍等人琜25]提出了通過調(diào)整機器人的運動速度實現(xiàn)多機器人避碰，將避碰問題轉(zhuǎn)換為高維線性空間的優(yōu)化問題,并進一步將其轉(zhuǎn)換為線性方程的求解。該方法的缺點是系統(tǒng)的復(fù)雜度較高、計算量太大。

　　人工勢場方法的特點是計算簡潔、實時性強、便于數(shù)學(xué)描述，且適合于多自由度機器人環(huán)境，但容易產(chǎn)生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協(xié)調(diào)場的方法，在傳統(tǒng)排斥力場中增加一個協(xié)調(diào)力,并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機器人的運動狀態(tài)和運動要求結(jié)合起來，有效地保證機器人的安全性，提高機器人在復(fù)雜動態(tài)環(huán)境下行為決策的準(zhǔn)確性和魯棒性。

　　3多機器人協(xié)作和協(xié)調(diào)機制

　　多機器人間的運動協(xié)調(diào)[27~31]是多機器人路徑規(guī)劃的關(guān)鍵，也是多機器人與單機器人路徑規(guī)劃相區(qū)別的根本所在。多機器人系統(tǒng)在復(fù)雜動態(tài)實時環(huán)境下，由于受到時間、資源及任務(wù)要求的約束，需要在有限時間、資源的情況下進行資源分配、任務(wù)調(diào)配、沖突解決等協(xié)調(diào)合作問題，而機器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務(wù)的關(guān)鍵。

　　目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細(xì)地規(guī)劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機器人之間進行合作，將一個任務(wù)分成多個子任務(wù)，根據(jù)各自的特點完成不同的子任務(wù)，從而共同完成總?cè)蝿?wù)；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

來源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問題，請聯(lián)系我們及時刪除。

《多機器人路徑實踐論文》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請保留原作者信息,謝謝!
鏈接地址：http://www.seogis.com/gongwen/132527.html

• 上一篇：萊菔子的藥理作用分析論文
• 下一篇：讓公開課在冷場中綻放精彩論文