多機(jī)器人路徑規(guī)劃研究方法

摘 要：在查閱大量文獻(xiàn)的基礎(chǔ)上對多機(jī)器人路徑規(guī)劃的主要研究內(nèi)容和研究現(xiàn)狀進(jìn)行了分析和總結(jié)，討論了多機(jī)器人路徑規(guī)劃方法的評判標(biāo)準(zhǔn)，并闡述了研究遇到的瓶頸問題，展望了多機(jī)器人路徑規(guī)劃方法的發(fā)展趨勢。

關(guān)鍵詞：多機(jī)器人；路徑規(guī)劃；強化學(xué)習(xí)；評判準(zhǔn)則

中圖分類號：TP242 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)09-2566-04



Path planning research for multirobot



ZHANG Yaming，¹，LEI Xiaoyu¹，YANG Shengyue¹，F(xiàn)AN Xiaoping¹，QU Zhihua^1，2，JIA Zhanchao¹

（1.College of Information Science Engineering， Central South University， Changsha 410075， China；2.Dept. of Electrical Computer Engineering， University of Central Florida， Orlando， FL 32816， USA)

Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.

Key words:multirobot；path planning;reinforcement learning;evaluating criteria 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

v0→π₁→v₁→π₂→…→v^*→π^*→v^*

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

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

Sarsa算法： Q(s_t，a_t)←Q(s_t，a_t)+α[γ_t+1+γQ(s_t+1，a_t.+1)-Q(s_t，a_t)]Q^s′學(xué)習(xí)算法： Q^π(s，a)=∑P^α_ss′[R^a_ss′+γV^π(s′)]

近年來，基于強化學(xué)習(xí)的路徑規(guī)劃日益成為國內(nèi)外學(xué)者研究的熱點。M. J. Mataric^[12]首次把強化學(xué)習(xí)引入到多機(jī)器人環(huán)境中。而基于強化學(xué)習(xí)的多機(jī)器人路徑規(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ī)劃中，機(jī)器人的趨向目標(biāo)和避障行為密切相關(guān)，對反映各基本行為的再勵函數(shù)取加權(quán)和來表示總的再勵函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵函數(shù)設(shè)計得合理與否及其確切程度將影響再勵學(xué)習(xí)的收斂速度。王醒策等人^[14]在動態(tài)編隊的強化學(xué)習(xí)算法方面展開了研究。宋一然^[15]則提出了分段再勵函數(shù)的強化學(xué)習(xí)方法進(jìn)行路徑規(guī)劃。其缺點是學(xué)習(xí)次數(shù)較多、效率不高，當(dāng)機(jī)器人數(shù)目增加時，它有可能面臨維數(shù)災(zāi)難的困難。所以，基于強化學(xué)習(xí)的路徑規(guī)劃在多機(jī)器人環(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ī)劃思想的多機(jī)器人路徑規(guī)劃，把運籌學(xué)中的動態(tài)規(guī)劃思想與Dijkstra算法引入到多機(jī)器人的路徑規(guī)劃中，用動態(tài)規(guī)劃的基本思想來解決圖論中的費用流問題和路徑規(guī)劃中的層級動態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個機(jī)器人的鄰居是指在地理位置上分布在這個機(jī)器人周圍的其他機(jī)器人；與該機(jī)器人最近鄰的機(jī)器人為第一層鄰居，第一層鄰居的鄰居為該機(jī)器人的第二層鄰居， 依此類推。那么層級越高（即越近)的鄰居，它滿足協(xié)作要求的可能性越大。動態(tài)規(guī)劃算法實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，必須存儲產(chǎn)生過程中的各種狀態(tài)，其空間復(fù)雜度要大于其他算法，故動態(tài)規(guī)劃方法比較適合多機(jī)器人的全局路徑規(guī)劃。

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

2 多機(jī)器人避碰和避障

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

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

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

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

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

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

多機(jī)器人間典型的協(xié)調(diào)方法^[32]有合同網(wǎng)協(xié)議^[33]、黑板模型、結(jié)果共享的協(xié)同方法、市場機(jī)制。近年來強化學(xué)習(xí)在多機(jī)器人協(xié)作方面也得到很好的應(yīng)用，陳雪江^[32]在基于強化學(xué)習(xí)的多機(jī)器人協(xié)作方面展開了研究，提出了多智能體協(xié)作的兩層強化學(xué)習(xí)方法來求解在多智能體完全協(xié)作、有通信情況下的協(xié)作問題。其主要通過在單個智能體中構(gòu)筑兩層強化學(xué)習(xí)單元來實現(xiàn)：第一層強化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)智能體的聯(lián)合任務(wù)協(xié)作策略；第二層強化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)在本智能體看來是最有效的行動策略。陳偉等人^[34]提出基于多目標(biāo)決策理論的多機(jī)器人協(xié)調(diào)方法；通過對環(huán)境的拓?fù)浣＃瑥幕谛袨榈臋C(jī)器人學(xué)角度出發(fā)，對任務(wù)進(jìn)行分解并設(shè)計目標(biāo)行為，以多目標(biāo)行為決策理論作為決策支持，從而達(dá)到多機(jī)器人運動協(xié)調(diào)的目的。

4 多機(jī)器人路徑規(guī)劃方(算)法的判優(yōu)準(zhǔn)則

通常評價機(jī)器人路徑規(guī)劃方(算)法的標(biāo)準(zhǔn)文獻(xiàn)^[35]有正確性、時間/空間復(fù)雜度、并行性、可靠性、擴(kuò)展性、魯棒性和學(xué)習(xí)。而多機(jī)器人的路徑規(guī)劃除了以上一些衡量標(biāo)準(zhǔn)之外，還需要考慮整個系統(tǒng)的最優(yōu)化以及機(jī)器人間的協(xié)調(diào)性。

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

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

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

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

4)并行性 算法的并行性從算法設(shè)計、編寫程序、編譯和運行等多個不同的層次來體現(xiàn)。路徑規(guī)劃過程需要大量的計算，當(dāng)處理的環(huán)境比較復(fù)雜，機(jī)器人工作的環(huán)境過于緊湊，尤其是機(jī)器人數(shù)量很多時，算法的時間/空間復(fù)雜度勢必會成為算法效率的關(guān)鍵。因此，在算法設(shè)計和運行上的并行性是通?？紤]的方法。對多個機(jī)器人的路徑規(guī)劃盡量采用分布式多進(jìn)程的規(guī)劃機(jī)制，以實現(xiàn)每個機(jī)器人路徑規(guī)劃的并行性。

5)可靠性 把多個機(jī)器人及其工作環(huán)境看成是一個系統(tǒng)，多機(jī)器人處于它們各自的起始點時，稱該系統(tǒng)處于初始狀態(tài)；當(dāng)它們處于各自的目標(biāo)點時，稱該系統(tǒng)處于目標(biāo)狀態(tài)。多機(jī)器人的路徑規(guī)劃就是在該系統(tǒng)的這兩個狀態(tài)間建立一串合理的狀態(tài)變遷。這一狀態(tài)變遷過程可能會歷經(jīng)許多狀態(tài)，如果在狀態(tài)變遷過程中，路徑規(guī)劃算法控制不好各狀態(tài)間的轉(zhuǎn)移關(guān)系，就會導(dǎo)致系統(tǒng)紊亂，出現(xiàn)機(jī)器人間的碰撞、找不到路徑等惡性后果，使任務(wù)失敗。所以這就對算法的可靠性和完備性提出了挑戰(zhàn)。為了很好地克服這一困難，需要對系統(tǒng)的各種可能狀態(tài)建模，分析它們相互間的關(guān)系，建立有限狀態(tài)自動機(jī)模型或Petri網(wǎng)模型，并以此為指導(dǎo)，按照軟件工程的思想，構(gòu)造恰當(dāng)?shù)乃惴ㄝ斎雭韺λ惴ǖ目煽啃赃M(jìn)行檢驗。

6)可擴(kuò)展性 在多機(jī)器人的路徑規(guī)劃算法中，可擴(kuò)展性主要是指一種路徑規(guī)劃算法在邏輯上，或者說在實現(xiàn)上能否容易地從2D空間擴(kuò)展到3D空間，從低自由度擴(kuò)展到高自由度，從較少的機(jī)器人數(shù)到更多的機(jī)器人數(shù)?？蓴U(kuò)展性在各種路徑規(guī)劃算法之間沒有一種量的比較標(biāo)準(zhǔn)，只能從實際的具體情況出發(fā)、從對環(huán)境描述的適宜程度出發(fā)、從算法解決這一問題的復(fù)雜度出發(fā)、從算法本身的自適應(yīng)出發(fā)等來考慮。

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

8）最優(yōu)化 對動態(tài)環(huán)境有優(yōu)化反應(yīng)。由于有些應(yīng)用領(lǐng)域涉及的是動態(tài)的環(huán)境條件，具有根據(jù)條件優(yōu)化系統(tǒng)的反應(yīng)能力成為能否成功的關(guān)鍵。

5 結(jié)束語

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

總之，多機(jī)器人路徑規(guī)劃設(shè)計和實現(xiàn)是一項極其復(fù)雜的系統(tǒng)工程，展望其能在結(jié)合計算智能方法，如差分進(jìn)化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網(wǎng)絡(luò)、人工勢場的改進(jìn)、模擬退火和環(huán)境建模方法等方面取得新的突破。

參考文獻(xiàn)：

［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.

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

[3]譚民，王碩，曹志強.多機(jī)器人系統(tǒng)[M].北京：清華大學(xué)出版社，2005：6-81.

[4]薄喜柱，洪炳熔.動態(tài)環(huán)境下多移動機(jī)器人路徑規(guī)劃的一種新方法[J].機(jī)器人，2001，23（5）：407-410.

[5]顧國昌，李亞波.基于總體勢減小的動態(tài)調(diào)度技術(shù)解決多機(jī)器人的路徑規(guī)劃[J].機(jī)器人，2001，23（2）：171-174.

[6]孫樹棟，林茂.基于遺傳算法的多移動機(jī)器人協(xié)調(diào)路徑規(guī)劃[J].自動化學(xué)報，2000，26（5）：672-676.

[7]周明，孫樹棟，彭炎午.基于遺傳算法的多機(jī)器人系統(tǒng)集中協(xié)調(diào)式路徑規(guī)劃[J].航空學(xué)報，2000，21（2）：146-149.

[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.

[9]朱慶保.全局未知環(huán)境下多機(jī)器人運動螞蟻導(dǎo)航算法[J].軟件學(xué)報，2006，17（9）：1890-1898.

[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.

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

86-100.

[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.

[13]張芳，顏國正，林良明.基于再勵學(xué)習(xí)的多移動機(jī)器人協(xié)調(diào)避障路徑規(guī)劃方法[J].計算機(jī)工程與應(yīng)用，2003，39（3）：80-83.

[14]王醒策，張汝波，顧國昌.多機(jī)器人動態(tài)編隊的強化學(xué)習(xí)算法研究[J].計算機(jī)研究與發(fā)展，2003，40（10）：1444-1450.

[15]宋一然.基于強化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃方法[J].莆田學(xué)院學(xué)報，2006，13（2）：38-41.

[16]韓學(xué)東，洪炳熔.基于人工神經(jīng)網(wǎng)絡(luò)的多機(jī)器人協(xié)作學(xué)習(xí)研究[J].計算機(jī)工程與設(shè)計，2002，23（6）：1-3.

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

[18]孫茂相，周明，王艷紅，等.多移動機(jī)器人實時最優(yōu)運動規(guī)劃[J].控制與決策，1998，

13（2）：125-130.

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

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

[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.

[22]徐潼，唐振民.多機(jī)器人系統(tǒng)中的動態(tài)避碰規(guī)劃[J].計算機(jī)工程，2003，29(17):

79-81，104.

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

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

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

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

[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.

[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.

[29]薛宏濤，葉媛媛，沈林成，等.多智能體系統(tǒng)體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制研究綜述[J].機(jī)器人，2001，23（1）：85-90.

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

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

[32]陳雪江.基于強化學(xué)習(xí)的多機(jī)器人協(xié)作機(jī)制研究[D].杭州：浙江工業(yè)大學(xué)，2004.

[33]SMITH R.The contract net protocol:highlevel communication and control in a distributed problem solver[J].IEEE Trans on Computer，1980，C-29(12):1104-1113.

[34]陳偉，張銘鈞，孟憲松.基于多目標(biāo)決策理論的多機(jī)器人協(xié)調(diào)方法[J].哈爾濱工程大學(xué)學(xué)報，2003，24（3）：308-312.

[35]李亞波.多機(jī)器人的路徑規(guī)劃與協(xié)調(diào)[D].哈爾濱：哈爾濱工程大學(xué)，2000.