多機器人路徑實(shí)踐論文
1多機器人路徑規劃方法
單個(gè)機器人的路徑規劃是找出從起始點(diǎn)至終點(diǎn)的一條最短無(wú)碰路徑。多個(gè)機器人的路徑規劃側重考慮整個(gè)系統的最優(yōu)路徑，如系統的總耗時(shí)間最少路徑或是系統總路徑最短等。從目前國內外的研究來(lái)看，在規劃多機器人路徑時(shí)，更多考慮的是多機器人之間的協(xié)調和合作式的路徑規劃。
目前國內外多機器人路徑規劃研究方法分為傳統方法、智能優(yōu)化方法和其他方法三大類(lèi)。其中傳統方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場(chǎng)方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò )、強化學(xué)習等；其他方法主要有動(dòng)態(tài)規劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個(gè)機器人路徑規劃方法擴展而來(lái)的。
1）傳統方法多機器人路徑規劃傳統方法的特點(diǎn)主要體現在基于圖論的基礎上。方法一般都是先將環(huán)境構建成一個(gè)圖，然后再從圖中尋找最優(yōu)的路徑。其優(yōu)點(diǎn)是比較簡(jiǎn)單，比較容易實(shí)現；缺點(diǎn)是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規劃方法的基本思想就是基于柵格類(lèi)的環(huán)境表示和障礙地圖的。而人工勢場(chǎng)方法的基本思想是將移動(dòng)機器人在環(huán)境中的運動(dòng)視為一種虛擬人工受力場(chǎng)中的運動(dòng)。障礙物對移動(dòng)機器人產(chǎn)生斥力，目標點(diǎn)產(chǎn)生引力，引力和斥力周?chē)梢欢ǖ乃惴óa(chǎn)生相應的勢，機器人在勢場(chǎng)中受到抽象力作用,抽象力使得機器人繞過(guò)障礙物。其優(yōu)點(diǎn)是適合未知環(huán)境下的規劃，不會(huì )出現維數爆炸問(wèn)題；但是人工勢場(chǎng)法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動(dòng)態(tài)調度技術(shù)的多機器人路徑規劃，較好地解決了這個(gè)問(wèn)題。
2）智能優(yōu)化方法多機器人路徑規劃的智能優(yōu)化方（算）法是隨著(zhù)近年來(lái)智能計算發(fā)展而產(chǎn)生的一些新方法。其相對于傳統方法更加智能化，且日益成為國內外研究的重點(diǎn)。
遺傳算法是近年來(lái)計算智能研究的熱點(diǎn)，作為一種基于群體進(jìn)化的概率優(yōu)化方法，適用于處理傳統搜索算法難以解決的復雜和非線(xiàn)性問(wèn)題，如多機器的路徑規劃問(wèn)題。在路徑規劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構建成一個(gè)路徑節點(diǎn)鏈接網(wǎng)，將路徑個(gè)體表達為路徑中一系列中途節點(diǎn)，并轉換為二進(jìn)制串；然后進(jìn)行遺傳操作（如選擇、交叉、復制、變異），經(jīng)過(guò)N次進(jìn)化，輸出當前的最優(yōu)個(gè)體即機器人的最優(yōu)路徑。遺傳算法的缺點(diǎn)是運算速度不快，進(jìn)化眾多的規劃要占據很大的存儲空間和運算時(shí)間；優(yōu)點(diǎn)是有效避免了局部極小值問(wèn)題，且計算量較小。
孫樹(shù)棟等人[6，7]在這方面較早地展開(kāi)了研究，提出的基于集中協(xié)調思想的一種混合遺傳算法來(lái)規劃多機器人路徑方法較好地解決了避障問(wèn)題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規劃沒(méi)有得到很好的解決；且規劃只能保證找到一個(gè)比較滿(mǎn)意的解，在求解全局最優(yōu)解時(shí)仍有局限。
文獻[8]中提出的一種基于定長(cháng)十進(jìn)編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長(cháng)編碼機制及定長(cháng)二進(jìn)制編碼機制需特殊遺傳操作算子和特殊解碼的缺陷,使得算法更加簡(jiǎn)單有效。
智能計算的另一種常見(jiàn)的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動(dòng)過(guò)程來(lái)實(shí)現尋優(yōu)，通過(guò)螞蟻群體中各個(gè)體之間的相互作用，分布、并行地解決組合優(yōu)化問(wèn)題。該算法同樣比較適合解決多機器人的路徑規劃問(wèn)題。
朱慶保[9]提出了在全局未知環(huán)境下多機器人運動(dòng)螞蟻導航算法。該方法將全局目標點(diǎn)映射到機器人視野域邊界附近作為局部導航子目標，再由兩組螞蟻相互協(xié)作完成機器人視野域內局部最優(yōu)路徑的搜索，然后在此基礎上進(jìn)行與其他機器人的碰撞預測與避碰規劃。因此，機器人的前進(jìn)路徑不斷被動(dòng)態(tài)修改，從而在每條局部?jì)?yōu)化路徑引導下，使機器人沿一條全局優(yōu)化的路徑到達目標點(diǎn)。但其不足是在動(dòng)態(tài)不確定的環(huán)境中路徑規劃時(shí)間開(kāi)銷(xiāo)劇增，而且機器人缺乏必要的學(xué)習，以至于整個(gè)機器人系統路徑難以是最優(yōu)路徑。
強化學(xué)習[10，11](又稱(chēng)再激勵學(xué)習)是一種重要的機器學(xué)習方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學(xué)習，使得行為從環(huán)境中獲得積累獎賞值最大。其原理如圖1所示。
強化學(xué)習算法一般包含了兩個(gè)步驟：a）從當前學(xué)習循環(huán)的值函數確定新的行為策略；b）在新的行為策略指導下，通過(guò)所獲得的瞬時(shí)獎懲值對該策略進(jìn)行評估。學(xué)習循環(huán)過(guò)程如下所示，直到值函數和策略收斂:
玽0→π1→v1→π2→…→v*→π*→v*
目前比較常見(jiàn)的強化學(xué)習方法有：MonteCarlo方法、動(dòng)態(tài)規劃方法、TD（時(shí)間差分）方法。其中TD算法包含Sarsa算法、Q學(xué)習算法以及Dyna-Q算法等。其Q值函數迭代公式分別為
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é)習算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]
近年來(lái)，基于強化學(xué)習的路徑規劃日益成為國內外學(xué)者研究的熱點(diǎn)。M.J.Mataric[12]首次把強化學(xué)習引入到多機器人環(huán)境中。而基于強化學(xué)習的多機器人路徑規劃的優(yōu)點(diǎn)主要體現在：無(wú)須建立精確的環(huán)境模型，簡(jiǎn)化了智能體的編程；無(wú)須構建環(huán)境地圖；強化學(xué)習可以把路徑規劃、避碰、避障、協(xié)作等問(wèn)題統一解決。
張芳等人[13]提出了基于再激勵協(xié)調避障路徑規劃方法，把再勵函數設計為基于行為分解的無(wú)模型非均勻結構，新的再勵函數結構使得學(xué)習速度得以提高且有較好的魯棒性。同時(shí)，證明了在路徑規劃中，機器人的趨向目標和避障行為密切相關(guān)，對反映各基本行為的再勵函數取加權和來(lái)表示總的再勵函數要優(yōu)于取直接和的表示方式，也反映了再勵函數設計得合理與否及其確切程度將影響再勵學(xué)習的收斂速度。王醒策等人[14]在動(dòng)態(tài)編隊的`強化學(xué)習算法方面展開(kāi)了研究。宋一然[15]則提出了分段再勵函數的強化學(xué)習方法進(jìn)行路徑規劃。其缺點(diǎn)是學(xué)習次數較多、效率不高，當機器人數目增加時(shí)，它有可能面臨維數災難的困難。所以，基于強化學(xué)習的路徑規劃在多機器人環(huán)境下的學(xué)習將變得比較困難，需要對傳統的強化學(xué)習加以?xún)?yōu)化，如基于人工神經(jīng)網(wǎng)絡(luò )的強化學(xué)習[16]等。
3)其他方法除了以上國內外幾種比較常見(jiàn)且研究較多的方法外，還有唐振民等人[17]提出的基于動(dòng)態(tài)規劃思想的多機器人路徑規劃，把運籌學(xué)中的動(dòng)態(tài)規劃思想與Dijkstra算法引入到多機器人的路徑規劃中，用動(dòng)態(tài)規劃的基本思想來(lái)解決圖論中的費用流問(wèn)題和路徑規劃中的層級動(dòng)態(tài)聯(lián)盟問(wèn)題。其選擇距離鄰近法作為聯(lián)盟參考依據。一個(gè)機器人的鄰居是指在地理位置上分布在這個(gè)機器人周?chē)钠渌麢C器人；與該機器人最近鄰的機器人為第一層鄰居,第一層鄰居的鄰居為該機器人的第二層鄰居,依此類(lèi)推。那么層級越高（即越近)的鄰居,它滿(mǎn)足協(xié)作要求的可能性越大。動(dòng)態(tài)規劃算法實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現的過(guò)程中，必須存儲產(chǎn)生過(guò)程中的各種狀態(tài)，其空間復雜度要大于其他算法，故動(dòng)態(tài)規劃方法比較適合多機器人的全局路徑規劃。
孫茂相等人[18]提出了最優(yōu)控制與智能決策相結合的多移動(dòng)機器人路徑規劃方法。其首先構造一個(gè)以各機器人最優(yōu)運動(dòng)狀態(tài)數據庫為核心的實(shí)時(shí)專(zhuān)家系統,在離線(xiàn)狀態(tài)下完成;然后各機器人在此專(zhuān)家系統的支持下,以最優(yōu)規劃策略為基礎,采用速度遷移算法,自主決定其控制。該方法擁有較好的穩定性與復雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動(dòng)規劃框架較好地解決了多機器人路徑規劃在局部在線(xiàn)規劃的系統框架問(wèn)題。沈捷等人[20]提出了保持隊形的多移動(dòng)機器人路徑規劃。以基于行為的導航算法為基礎,把機器人隊列的運動(dòng)過(guò)程劃分為正常運動(dòng)、避障和恢復隊形三個(gè)階段。在避障階段,引入虛擬機器人使隊形保持部分完整;當隊形被嚴重打亂時(shí),規劃機器人的局部目標位姿使隊列快速恢復隊形。其算法重點(diǎn)為避障機器人進(jìn)入避障狀態(tài),暫時(shí)脫離隊列,并以虛擬機器人代替避障機器人。
2多機器人避碰和避障
避障和避碰是多機器人路徑規劃研究中需要考慮的重點(diǎn)問(wèn)題之一。避障和避碰主要討論的內容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規劃中常見(jiàn)的多機器人避障方法[21]有主從控制法、動(dòng)態(tài)優(yōu)先法（建立在機器人之間的通信協(xié)商上）、交通規則法、速率調整法，以及障礙物膨脹法、基于人工勢場(chǎng)的方法等。
目前國內外對于多機器人避障展開(kāi)的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎，擴充并完善了路徑/速度分解方案來(lái)協(xié)調多機器人,設立集中管理゛gent進(jìn)行整體規劃，為每個(gè)機器人規劃路徑；并根據優(yōu)先級規則對運動(dòng)特征進(jìn)行分布式規劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規劃系統，將原來(lái)比較復雜的大系統轉換為相對簡(jiǎn)單的子系統問(wèn)題,由各智能機器人依據任務(wù)要求和環(huán)境變化,獨立調整自身運動(dòng)狀態(tài),完成任務(wù)的分布式智能決策體系結構。任炏等人[24]提出了基于過(guò)程獎賞和優(yōu)先掃除的強化學(xué)習多機器人系統的沖突消解方法。該算法能夠顯著(zhù)減少沖突,避免死鎖,提高了系統整體性能。歐錦軍等人琜25]提出了通過(guò)調整機器人的運動(dòng)速度實(shí)現多機器人避碰，將避碰問(wèn)題轉換為高維線(xiàn)性空間的優(yōu)化問(wèn)題,并進(jìn)一步將其轉換為線(xiàn)性方程的求解。該方法的缺點(diǎn)是系統的復雜度較高、計算量太大。
人工勢場(chǎng)方法的特點(diǎn)是計算簡(jiǎn)潔、實(shí)時(shí)性強、便于數學(xué)描述，且適合于多自由度機器人環(huán)境，但容易產(chǎn)生抖動(dòng)和陷入局部極小。為了克服其缺點(diǎn)，景興建等人[26]提出了人工協(xié)調場(chǎng)的方法，在傳統排斥力場(chǎng)中增加一個(gè)協(xié)調力,并將吸引力、排斥力和協(xié)調力與局部環(huán)境下機器人的運動(dòng)狀態(tài)和運動(dòng)要求結合起來(lái)，有效地保證機器人的安全性，提高機器人在復雜動(dòng)態(tài)環(huán)境下行為決策的準確性和魯棒性。
3多機器人協(xié)作和協(xié)調機制
多機器人間的運動(dòng)協(xié)調[27~31]是多機器人路徑規劃的關(guān)鍵，也是多機器人與單機器人路徑規劃相區別的根本所在。多機器人系統在復雜動(dòng)態(tài)實(shí)時(shí)環(huán)境下，由于受到時(shí)間、資源及任務(wù)要求的約束，需要在有限時(shí)間、資源的情況下進(jìn)行資源分配、任務(wù)調配、沖突解決等協(xié)調合作問(wèn)題，而機器人間的協(xié)調與協(xié)作，能夠大大地提高整個(gè)系統的效率和魯棒性，成為系統完成控制或解決任務(wù)的關(guān)鍵。
目前已有的協(xié)調方式分為集中式、分布式和混合式三種。在集中式協(xié)調中，集中規劃器詳細地規劃出每個(gè)機器人的動(dòng)作，通常的做法是將多個(gè)機器人看做一個(gè)多自由度的機器人進(jìn)行規劃；而分布式協(xié)調規劃中，機器人之間進(jìn)行合作，將一個(gè)任務(wù)分成多個(gè)子任務(wù)，根據各自的特點(diǎn)完成不同的子任務(wù)，從而共同完成總任務(wù)；混合式協(xié)調是集中式和分布式混合在一起的形式。
【多機器人路徑實(shí)踐論文】相關(guān)文章：
智能客服機器人運營(yíng)實(shí)踐的論文05-11
智能電網(wǎng)節能減排實(shí)踐路徑探索論文04-26
分析教育理論向實(shí)踐轉化的現實(shí)路徑的論文03-30
多實(shí)踐才能出真知議論文10-07
休閑農業(yè)發(fā)展路徑論文02-08