導語：多機器人路徑規劃分析論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

1多機器人路徑規劃方法

單個機器人的路徑規劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規劃側重考慮整個系統的最優路徑，如系統的總耗時間最少路徑或是系統總路徑最短等。從目前國內外的研究來看，在規劃多機器人路徑時，更多考慮的是多機器人之間的協調和合作式的路徑規劃。

目前國內外多機器人路徑規劃研究方法分為傳統方法、智能優化方法和其他方法三大類。其中傳統方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優化方法主要有遺傳算法、蟻群算法、免疫算法、神經網絡、強化學習等；其他方法主要有動態規劃、最優控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規劃方法擴展而來的。

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

2）智能優化方法多機器人路徑規劃的智能優化方（算）法是隨著近年來智能計算發展而產生的一些新方法。其相對于傳統方法更加智能化，且日益成為國內外研究的重點。

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

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

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

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

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

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

強化學習算法一般包含了兩個步驟：a）從當前學習循環的值函數確定新的行為策略；b）在新的行為策略指導下，通過所獲得的瞬時獎懲值對該策略進行評估。學習循環過程如下所示，直到值函數和策略收斂:

v0→π1→v1→π2→…→v*→π*→v*

目前比較常見的強化學習方法有：MonteCarlo方法、動態規劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學習算法以及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)]Qs′學習算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強化學習的路徑規劃日益成為國內外學者研究的熱點。M.J.Mataric[12]首次把強化學習引入到多機器人環境中。而基于強化學習的多機器人路徑規劃的優點主要體現在：無須建立精確的環境模型，簡化了智能體的編程；無須構建環境地圖；強化學習可以把路徑規劃、避碰、避障、協作等問題統一解決。

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

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

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

2多機器人避碰和避障

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

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

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

3多機器人協作和協調機制

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

目前已有的協調方式分為集中式、分布式和混合式三種。在集中式協調中，集中規劃器詳細地規劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規劃；而分布式協調規劃中，機器人之間進行合作，將一個任務分成多個子任務，根據各自的特點完成不同的子任務，從而共同完成總任務；混合式協調是集中式和分布式混合在一起的形式。

摘要：在查閱大量文獻的基礎上對多機器人路徑規劃的主要研究內容和研究現狀進行了分析和總結，討論了多機器人路徑規劃方法的評判標準，并闡述了研究遇到的瓶頸問題，展望了多機器人路徑規劃方法的發展趨勢。

關鍵詞：多機器人；路徑規劃；強化學習；評判準則

Abstract:Thispaperanalyzedandconcludedthemainmethodandcurrentresearchofthepathplanningresearchformultirobot.Thendiscussedthecriterionofpathplanningresearchformultirobotbasedlargeofliterature.Meanwhile,itexpoundedthebottleneckofthepathplanningresearchformultirobot，forecastedthefuturedevelopmentofmultirobotpathplanning.

Keywords:multirobot；pathplanning;reinforcementlearning;evaluatingcriteria

近年來，分布式人工智能(DAI)成為人工智能研究的一個重要分支。DAI研究大致可以分為DPS（distributedproblemsolving）和MAS（multiagentsystem）兩個方面。一些從事機器人學的研究人員受多智能體系統研究的啟發，將智能體概念應用于多機器人系統的研究中，將單個機器人視做一個能獨立執行特定任務的智能體，并把這種多機器人系統稱為多智能體機器人系統（MARS）。因此，本文中多機器人系統等同于多智能體機器人系統。目前，多機器人系統已經成為學術界研究的熱點,而路徑規劃研究又是其核心部分。

機器人路徑規劃問題可以建模為一個帶約束的優化問題，其包括地理環境信息建模、路徑規劃、定位和避障等任務，它是移動機器人導航與控制的基礎。單個移動機器人路徑規劃研究一直是機器人研究的重點，且已經有許多成果[1~3]，例如在靜態環境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓撲法、鏈接圖法、DempsterShafer證據理論建圖等；動態環境中常見的有粒子群算法、免疫算法、遺傳算法、神經網絡、蟻群算法、模擬退火算法、人工勢場法等。然而，多機器人路徑規劃研究比單個機器人路徑規劃要復雜得多，必須考慮多機器人系統中機器人之間的避碰機制、機器人之間的相互協作機制、通信機制等問題。

1多機器人路徑規劃方法

單個機器人的路徑規劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規劃側重考慮整個系統的最優路徑，如系統的總耗時間最少路徑或是系統總路徑最短等。從目前國內外的研究來看，在規劃多機器人路徑時，更多考慮的是多機器人之間的協調和合作式的路徑規劃。

目前國內外多機器人路徑規劃研究方法分為傳統方法、智能優化方法和其他方法三大類。其中傳統方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優化方法主要有遺傳算法、蟻群算法、免疫算法、神經網絡、強化學習等；其他方法主要有動態規劃、最優控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規劃方法擴展而來的。

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

2）智能優化方法多機器人路徑規劃的智能優化方（算）法是隨著近年來智能計算發展而產生的一些新方法。其相對于傳統方法更加智能化，且日益成為國內外研究的重點。

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

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

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

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

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

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

強化學習算法一般包含了兩個步驟：a）從當前學習循環的值函數確定新的行為策略；b）在新的行為策略指導下，通過所獲得的瞬時獎懲值對該策略進行評估。學習循環過程如下所示，直到值函數和策略收斂:

v0→π1→v1→π2→…→v*→π*→v*

目前比較常見的強化學習方法有：MonteCarlo方法、動態規劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學習算法以及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)]Qs′學習算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強化學習的路徑規劃日益成為國內外學者研究的熱點。M.J.Mataric[12]首次把強化學習引入到多機器人環境中。而基于強化學習的多機器人路徑規劃的優點主要體現在：無須建立精確的環境模型，簡化了智能體的編程；無須構建環境地圖；強化學習可以把路徑規劃、避碰、避障、協作等問題統一解決。

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

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

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

2多機器人避碰和避障

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

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

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

3多機器人協作和協調機制

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

目前已有的協調方式分為集中式、分布式和混合式三種。在集中式協調中，集中規劃器詳細地規劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規劃；而分布式協調規劃中，機器人之間進行合作，將一個任務分成多個子任務，根據各自的特點完成不同的子任務，從而共同完成總任務；混合式協調是集中式和分布式混合在一起的形式。

多機器人間典型的協調方法[32]有合同網協議[33]、黑板模型、結果共享的協同方法、市場機制。近年來強化學習在多機器人協作方面也得到很好的應用，陳雪江[32]在基于強化學習的多機器人協作方面展開了研究，提出了多智能體協作的兩層強化學習方法來求解在多智能體完全協作、有通信情況下的協作問題。其主要通過在單個智能體中構筑兩層強化學習單元來實現：第一層強化學習單元負責學習智能體的聯合任務協作策略；第二層強化學習單元負責學習在本智能體看來是最有效的行動策略。陳偉等人[34]提出基于多目標決策理論的多機器人協調方法；通過對環境的拓撲建模,從基于行為的機器人學角度出發,對任務進行分解并設計目標行為,以多目標行為決策理論作為決策支持,從而達到多機器人運動協調的目的。

4多機器人路徑規劃方(算)法的判優準則

通常評價機器人路徑規劃方(算)法的標準文獻[35]有正確性、時間/空間復雜度、并行性、可靠性、擴展性、魯棒性和學習。而多機器人的路徑規劃除了以上一些衡量標準之外，還需要考慮整個系統的最優化以及機器人間的協調性。

1)正確性是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數據后，算法經過有窮時間的計算能給出正確的答案。但在多機器人路徑規劃算法中，正確性主要指:路徑規劃算法要生成多個機器人協調運動的無碰安全路徑;這條路徑是優化的。

2)安全性一般指多機器人所生成的各路徑中節點與障礙物有一定的距離。但在實際的應用背景下，有人認為安全性可以從兩個方面來理解：a）狹義地講，它就是機器人在行走過程中所做的功。在一定的條件下，它與路徑長度準則是一致的。b）廣義地講，它是各種優化條件加權綜合而得到的結果。

3)復雜度一個算法的復雜性高低體現在該算法所需要的計算機資源的多少上面。所需要的資源越多，該算法的復雜性越高；反之，所需要的資源越少，該算法的復雜性就越低。算法的復雜性包括時間復雜度和空間復雜度。

在多機器人的路徑規劃算法中，算法的復雜度分析顯得尤為重要。一般地，單機器人路徑規劃算法的時空復雜度已經頗高，它們的數量級至少是O(n2)；多機器人的路徑規劃算法不僅是m-O(n2)(即m個機器人路徑規劃簡單地疊加)，它們之間還存在著對運動空間競爭的沖突，面對不斷變化的沖突的協調需要花費大量的時間和空間。通常多機器人的路徑規劃算法與機器人的個數呈指數關系O(km×n2)（k為常數）。這對多機器人路徑規劃算法的時間/空間復雜度控制是一個很嚴峻的考驗。

4)并行性算法的并行性從算法設計、編寫程序、編譯和運行等多個不同的層次來體現。路徑規劃過程需要大量的計算，當處理的環境比較復雜，機器人工作的環境過于緊湊，尤其是機器人數量很多時，算法的時間/空間復雜度勢必會成為算法效率的關鍵。因此，在算法設計和運行上的并行性是通常考慮的方法。對多個機器人的路徑規劃盡量采用分布式多進程的規劃機制，以實現每個機器人路徑規劃的并行性。

5)可靠性把多個機器人及其工作環境看成是一個系統，多機器人處于它們各自的起始點時，稱該系統處于初始狀態；當它們處于各自的目標點時，稱該系統處于目標狀態。多機器人的路徑規劃就是在該系統的這兩個狀態間建立一串合理的狀態變遷。這一狀態變遷過程可能會歷經許多狀態，如果在狀態變遷過程中，路徑規劃算法控制不好各狀態間的轉移關系，就會導致系統紊亂，出現機器人間的碰撞、找不到路徑等惡性后果，使任務失敗。所以這就對算法的可靠性和完備性提出了挑戰。為了很好地克服這一困難，需要對系統的各種可能狀態建模，分析它們相互間的關系，建立有限狀態自動機模型或Petri網模型，并以此為指導，按照軟件工程的思想，構造恰當的算法輸入來對算法的可靠性進行檢驗。

6)可擴展性在多機器人的路徑規劃算法中，可擴展性主要是指一種路徑規劃算法在邏輯上，或者說在實現上能否容易地從2D空間擴展到3D空間，從低自由度擴展到高自由度，從較少的機器人數到更多的機器人數。可擴展性在各種路徑規劃算法之間沒有一種量的比較標準，只能從實際的具體情況出發、從對環境描述的適宜程度出發、從算法解決這一問題的復雜度出發、從算法本身的自適應出發等來考慮。

7)魯棒性和學習魯棒性對于多機器人系統非常重要。因為許多應用，如路徑規劃要求連續的作業、系統中的單個機器人出現故障或被破壞，要求機器人利用剩余的資源仍然能夠完成任務。學習是在線適應特定的任務。雖然通用的系統非常有用，但將它用于特定應用上時，通常需要調整一些參數。具有在線調整相關參數的能力是非常吸引人的，這在將體系結構轉移到其他應用時可以節省許多工作。尤其是多機器人系統中機器人的自身學習和相互間的學習能夠大大提高整個系統的效率和系統的穩定性。

8）最優化對動態環境有優化反應。由于有些應用領域涉及的是動態的環境條件，具有根據條件優化系統的反應能力成為能否成功的關鍵。

5結束語

綜上所述，國內外研究者在多機器人路徑規劃取得了一些成果，但是在協作、學習、通信機制等方面仍面臨很大的困難和不足。如何進一步提高機器人間的協調性，增強機器人自身以及相互間的學習以提高多機器人系統的效率和魯棒性都有待深入研究。近年來無線通信技術得到長足發展,但在目前的技術條件下，在多機器人系統中實現所有機器人之間的點對點實時通信還有較大困難，這也是大多數多機器人系統仍然采用集中通信方式的主要原因。因此，如何降低多機器人系統對通信速度的依賴程度也是一個非常重要的問題。

總之,多機器人路徑規劃設計和實現是一項極其復雜的系統工程,展望其能在結合計算智能方法，如差分進化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網絡、人工勢場的改進、模擬退火和環境建模方法等方面取得新的突破。

參考文獻：

［1］WEISSG.Multiagentsystems:amodernapproachtodistributedmodernapproachtoartificialintelligence[M].Cambridge,Massachusetts：MITPress，1999：121-161.

[2]蔡自興，徐光祐.人工智能及其應用:研究生用書[M].3版.北京：清華大學出版社，2004：124-198.

[3]譚民,王碩,曹志強.多機器人系統[M].北京：清華大學出版社，2005：6-81.

[4]薄喜柱,洪炳熔.動態環境下多移動機器人路徑規劃的一種新方法[J].機器人，2001,23（5）：407-410.

[5]顧國昌,李亞波.基于總體勢減小的動態調度技術解決多機器人的路徑規劃[J].機器人，2001,23（2）：171-174.

[6]孫樹棟,林茂.基于遺傳算法的多移動機器人協調路徑規劃[J].自動化學報，2000,26（5）：672-676.

[7]周明,孫樹棟,彭炎午.基于遺傳算法的多機器人系統集中協調式路徑規劃[J].航空學報，2000,21（2）：146-149.

[8]CAIZixing,PENGZhihong.Cooperativecoevolutionaryadaptivegeneticalgorithminpathplanningofcooperativemultimobilerobotsystems[J].JournalofIntelligentandRoboticSystems:TheoryandApplications,2002,33(1):61-71.

[9]朱慶保.全局未知環境下多機器人運動螞蟻導航算法[J].軟件學報，2006,17（9）：1890-1898.

[10]SANDHOLMTW，CRITESRH.Multiagentreinforcementlearningintheiteratedprisoner’sdilemma[J].BioSystems，1996，37(1):147-166.

[11]高陽，陳世福，陸鑫.強化學習研究綜述[J].自動化學報，2004,30（1）：

86-100.

[12]MATARICMJ.Interactionandintelligentbehavior[D].Massachusetls:DepartmentofElectricalEngineeringandComputerScience,MIT,1994.

[13]張芳,顏國正,林良明.基于再勵學習的多移動機器人協調避障路徑規劃方法[J].計算機工程與應用，2003，39（3）：80-83.

[14]王醒策,張汝波,顧國昌.多機器人動態編隊的強化學習算法研究[J].計算機研究與發展，2003,40（10）：1444-1450.

[15]宋一然.基于強化學習的多機器人路徑規劃方法[J].莆田學院學報，2006,13（2）：38-41.

[16]韓學東,洪炳熔.基于人工神經網絡的多機器人協作學習研究[J].計算機工程與設計，2002,23（6）：1-3.

[17]唐振民,趙春霞,楊靜宇，等.基于動態規劃思想的多機器人路徑規劃[J].南京理工大學學報，2003,27（5）：610-615.

[18]孫茂相,周明,王艷紅,等.多移動機器人實時最優運動規劃[J].控制與決策，1998,

13（2）：125-130.

[19]焦立男,唐振民.基于局部傳感和通訊的多機器人運動規劃框架[J].計算機工程與應用，2007,43(17)：89-93.

[20]沈捷,費樹岷，鄭波.多移動機器人保持隊形路徑規劃[J].東南大學學報，2005,35(3):391-395.

[21]MANSORMA，MORRISAS.Pathplanninginunknownenvironmentwithobstaclesusingvirtualwindow[J].JournalofIntelligentandRoboticSystems，1999，24(3):235-251.

[22]徐潼，唐振民.多機器人系統中的動態避碰規劃[J].計算機工程，2003,29(17):

79-81,104.

[23]周明,孫茂相,尹朝萬，等.多移動機器人分布式智能避撞規劃系統[J].機器人，1999,21（2）：139-143.

[24]任炏,陳宗海.基于強化學習算法的多機器人系統的沖突消解的方法[J].控制與決策，2006,21(4):430-434,439.

[25]歐錦軍,朱楓.一種多移動機器人避碰規劃方法[J].機器人，2000,22(6):474-481.

[26]景興建,王越超,談大龍.基于人工協調場的多移動機器人實時協調避碰規劃[J].控制理論與應用，2004,21(5):757-764.

[27]PANAITL,LUKES.Cooperativemultiagentlearning:thestateoftheart[J].AutonomousAgentsandMultiAgentSystems,2005,11(3):387-434.

[28]TZAFESTASCS,PROKOPIOUPA,TZAFESTASSG.Pathplanningandcontrolofacooperativethreerobotsystemmanipulatinglargeobjects[J].JournalofIntelligentandRoboticSystems，1998,22(2):99-116.

[29]薛宏濤,葉媛媛,沈林成，等.多智能體系統體系結構及協調機制研究綜述[J].機器人，2001,23（1）：85-90.

[30]周風余,李貽斌,宋銳，等.基于混合式多智能體系統的協作多機器人系統研究[J].山東大學學報:工學版，2005,35(1):82-87.

[31]夏冰,張佐,張毅,等.基于多智能體系統的動態路徑選擇算法研究[J].公路交通科技，2003,20（1）：93-96.

[32]陳雪江.基于強化學習的多機器人協作機制研究[D].杭州：浙江工業大學，2004.

[33]SMITHR.Thecontractnetprotocol:highlevelcommunicationandcontrolinadistributedproblemsolver[J].IEEETransonComputer,1980，C-29(12):1104-1113.

[34]陳偉,張銘鈞,孟憲松.基于多目標決策理論的多機器人協調方法[J].哈爾濱工程大學學報，2003,24（3）：308-312.

[35]李亞波.多機器人的路徑規劃與協調[D].哈爾濱：哈爾濱工程大學，2000.

摘要：在查閱大量文獻的基礎上對多機器人路徑規劃的主要研究內容和研究現狀進行了分析和總結，討論了多機器人路徑規劃方法的評判標準，并闡述了研究遇到的瓶頸問題，展望了多機器人路徑規劃方法的發展趨勢。

關鍵詞：多機器人；路徑規劃；強化學習；評判準則

