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

1、張亞鳴雷小宇楊勝躍樊曉平瞿志華賈占朝摘要：在查閱大量文獻(xiàn)的基礎(chǔ)上對(duì)多機(jī)器人路徑規(guī)劃的主要研究?jī)?nèi)容和研究現(xiàn)狀進(jìn)行了分析和總結(jié)，討論了多機(jī)器人路徑規(guī)劃方法的評(píng)判標(biāo)準(zhǔn)，并闡述了研究遇到的瓶頸問題，展望了多機(jī)器人路徑規(guī)劃方法的發(fā)展趨勢(shì)。關(guān)鍵詞：多機(jī)器人；路徑規(guī)劃；強(qiáng)化學(xué)習(xí)；評(píng)判準(zhǔn)則Abstract:Thispaperanalyzedandconcludedthemainmethodandcurrentresearchofthepathplanningresearchformultirobot.Thendiscussedthecriterionofpathplanningresearchformulti

2、cibDtbasedlargeofliteatue.Meanwhile,itexpoundedthebottleneckofthepathplanningresearchformultirobot,forecastedthefuturedevelopmentofmultirobotpathplanning.Keywords:multirobot；pathplanning;reinforcementlearning;evaluatingcriteria近年來，分布式人工智能（DAI）成為人工智能研究白一個(gè)重要分支。DAI研究大致可以分為DPS（distributedproblemsolving）

3、和MAS（multiagentsystem）兩個(gè)方面。一些從事機(jī)器人學(xué)的研究人員受多智能體系統(tǒng)研究的啟發(fā)，將智能體概念應(yīng)用于多機(jī)器人系統(tǒng)的研究中，將單個(gè)機(jī)器人視做一個(gè)能獨(dú)立執(zhí)行特定任務(wù)的智能體，并把這種多機(jī)器人系統(tǒng)稱為多智能體機(jī)器人系統(tǒng)（MARS）。因此，本文中多機(jī)器人系統(tǒng)等同于多智能體機(jī)器人系統(tǒng)。目前，多機(jī)器人系統(tǒng)已經(jīng)成為學(xué)術(shù)界研究的熱點(diǎn)，而路徑規(guī)劃研究又是其核心部分。機(jī)器人路徑規(guī)劃問題可以建模為一個(gè)帶約束的優(yōu)化問題，具包括地理環(huán)境信息建模、路徑規(guī)劃、定位和避障等任務(wù)，它是移動(dòng)機(jī)器人導(dǎo)航與控制的基礎(chǔ)。單個(gè)移動(dòng)機(jī)器人路徑規(guī)劃研究一直是機(jī)器人研究的重點(diǎn)，且已經(jīng)有許多成果1-3,例如在靜態(tài)環(huán)境中常

4、見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓?fù)浞?、鏈接圖法、DempsterShafer證據(jù)理論建圖等；動(dòng)態(tài)環(huán)境中常見的有粒子群算法、免疫算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法、模擬退火算法、人工勢(shì)場(chǎng)法等。然而，多機(jī)器人路徑規(guī)劃研究比單個(gè)機(jī)器人路徑規(guī)劃要復(fù)雜得多，必須考慮多機(jī)器人系統(tǒng)中機(jī)器人之間的避碰機(jī)制、機(jī)器人之間的相互協(xié)作機(jī)制、通信機(jī)制等問題。1多機(jī)器人路徑規(guī)劃方法單個(gè)機(jī)器人的路徑規(guī)劃是找出從起始點(diǎn)至終點(diǎn)的一條最短無碰路徑。多個(gè)機(jī)器人的路徑規(guī)劃側(cè)重考慮整個(gè)系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時(shí)間最少路徑或是系統(tǒng)總路徑最短等。從目前國(guó)內(nèi)外的研究來看，在規(guī)劃多機(jī)器人路徑時(shí)

5、，更多考慮的是多機(jī)器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。目前國(guó)內(nèi)外多機(jī)器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢(shì)場(chǎng)方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)、強(qiáng)化學(xué)習(xí)等；其他方法主要有動(dòng)態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個(gè)機(jī)器人路徑規(guī)劃方法擴(kuò)展而來的。1）傳統(tǒng)方法多機(jī)器人路徑規(guī)劃傳統(tǒng)方法的特點(diǎn)主要體現(xiàn)在基于圖論的基礎(chǔ)上。方法一般都是先將環(huán)境構(gòu)建成一個(gè)圖，然后再?gòu)膱D中尋找最優(yōu)的路徑。具優(yōu)點(diǎn)是比較簡(jiǎn)單，比較容易實(shí)現(xiàn)；缺點(diǎn)是得到的路徑有可能不是

6、最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人4提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢(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ǎn)生相應(yīng)的勢(shì)，機(jī)器人在勢(shì)場(chǎng)中受到抽象力作用才由象力使得機(jī)器人繞過障礙物。其優(yōu)點(diǎn)是適合未知環(huán)境下的規(guī)劃，不會(huì)出現(xiàn)維數(shù)爆炸問題；但是人工勢(shì)場(chǎng)法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國(guó)昌等人5提出了引用總體勢(shì)減小的動(dòng)態(tài)調(diào)度技術(shù)的多機(jī)器人路徑規(guī)劃，較好地解決了這個(gè)問題。2）智能優(yōu)化方法多機(jī)器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨

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

8、人6,7在這方面較早地展開了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來規(guī)劃多機(jī)器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒有得到很好的解決；且規(guī)劃只能保證找到一個(gè)比較滿意的解，在求解全局最優(yōu)解時(shí)仍有局限。文獻(xiàn)8中提出的一種基于定長(zhǎng)十進(jìn)編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長(zhǎng)編碼機(jī)制及定長(zhǎng)二進(jìn)制編碼機(jī)制需特殊遺傳操作算子和特殊解碼的缺陷，使得算法更加簡(jiǎn)單有效。智能計(jì)算的另一種常見的方法一一蟻群算法屬于隨機(jī)搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運(yùn)動(dòng)過程來實(shí)現(xiàn)尋優(yōu)，通過螞蟻群體中各個(gè)體之間的相互作用，分布、并行地解決組合優(yōu)化

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

10、映射的學(xué)習(xí)，使得行為從環(huán)境中獲得積累獎(jiǎng)賞值最大。其原理如圖1所示。強(qiáng)化學(xué)習(xí)算法一般包含了兩個(gè)步驟：a)從當(dāng)前學(xué)習(xí)循環(huán)的值函數(shù)確定新的行為策略；b)在新的行為策略指導(dǎo)下，通過所獲得的瞬時(shí)獎(jiǎng)懲值對(duì)該策略進(jìn)行評(píng)估。學(xué)習(xí)循環(huán)過程如下所示，直到值函數(shù)和策略收斂：vOnHvHn2->,vn*->v*目前比較常見的強(qiáng)化學(xué)習(xí)方法有：MonteCarlo方法、動(dòng)態(tài)規(guī)劃方法、TD(時(shí)間差分)方法。其中TD算法包含Sarsa算法、Q學(xué)習(xí)算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為TD(0)策略：V(si)V(si)+%丫i+1+-V(SV(si+1)Sarsa算法：Q(st,at)Q(st,at

11、)+a丫t+1+丫Q(t+1,at.+S/學(xué)習(xí)算法：Q兀(s,a)=12PzecRsass，+yVxs)近年來，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃日益成為國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)。M.J.Mataric12首次把強(qiáng)化學(xué)習(xí)引入到多機(jī)器人環(huán)境中。而基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃的優(yōu)點(diǎn)主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡(jiǎn)化了智能體的編程；無須構(gòu)建環(huán)境地圖；強(qiáng)化學(xué)習(xí)可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。張芳等人13提出了基于再激勵(lì)協(xié)調(diào)避障路徑規(guī)劃方法，把再勵(lì)函數(shù)設(shè)計(jì)為基于行為分解的無模型非均勻結(jié)構(gòu)，新的再勵(lì)函數(shù)結(jié)構(gòu)使得學(xué)習(xí)速度得以提高且有較好的魯棒性。同時(shí)，證明了在路徑規(guī)劃中，機(jī)器人的趨向目標(biāo)和避障行為密

12、切相關(guān)，對(duì)反映各基本行為的再勵(lì)函數(shù)取加權(quán)和來表示總的再勵(lì)函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵(lì)函數(shù)設(shè)計(jì)得合理與否及其確切程度將影響再勵(lì)學(xué)習(xí)的收斂速度。王醒策等人14在動(dòng)態(tài)編隊(duì)的強(qiáng)化學(xué)習(xí)算法方面展開了研究。宋一然15則提出了分段再勵(lì)函數(shù)的強(qiáng)化學(xué)習(xí)方法進(jìn)行路徑規(guī)劃。具缺點(diǎn)是學(xué)習(xí)次數(shù)較多、效率不高，當(dāng)機(jī)器人數(shù)目增加時(shí)，它有可能面臨維數(shù)災(zāi)難的困難。所以，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃在多機(jī)器人環(huán)境下的學(xué)習(xí)將變得比較困難，需要對(duì)傳統(tǒng)的強(qiáng)化學(xué)習(xí)加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)16等。3）其他方法除了以上國(guó)內(nèi)外幾種比較常見且研究較多的方法外，還有唐振民等人17提出的基于動(dòng)態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃，把運(yùn)

13、籌學(xué)中的動(dòng)態(tài)規(guī)劃思想與Dijkstra算法引入到多機(jī)器人的路徑規(guī)劃中，用動(dòng)態(tài)規(guī)劃的基本思想來解決圖論中的費(fèi)用流問題和路徑規(guī)劃中的層級(jí)動(dòng)態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個(gè)機(jī)器人的鄰居是指在地理位置上分布在這個(gè)機(jī)器人周圍的其他機(jī)器人；與該機(jī)器人最近鄰的機(jī)器人為第一層鄰居，第一層鄰居的鄰居為該機(jī)器人的第二層鄰居，依此類推。那么層級(jí)越高（即越近）的鄰居，它滿足協(xié)作要求的可能性越大。動(dòng)態(tài)規(guī)劃算法實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，必須存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，其空間復(fù)雜度要大于其他算法，故動(dòng)態(tài)規(guī)劃方法比較適合多機(jī)器人的全局路徑規(guī)劃。孫茂相等人18提出了最優(yōu)控制與智能決策相結(jié)

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

15、。其算法重點(diǎn)為避障機(jī)器人進(jìn)入避障狀態(tài)暫時(shí)脫離隊(duì)列，并以虛擬機(jī)器人代替避障機(jī)器人。2多機(jī)器人避碰和避障避障和避碰是多機(jī)器人路徑規(guī)劃研究中需要考慮的重點(diǎn)問題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見的多機(jī)器人避障方法21有主從控制法、動(dòng)態(tài)優(yōu)先法（建立在機(jī)器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢(shì)場(chǎng)的方法等。目前國(guó)內(nèi)外對(duì)于多機(jī)器人避障展開的研究還不是很多，比較典型的有徐潼等人22以Th.Fraichard的思想為基礎(chǔ)，擴(kuò)充并完善了路徑/速度分解方案來協(xié)調(diào)多機(jī)器人，設(shè)立集中管理agent進(jìn)行整體規(guī)劃，為每個(gè)機(jī)器人規(guī)劃路

16、徑；并根據(jù)優(yōu)先級(jí)規(guī)則對(duì)運(yùn)動(dòng)特征進(jìn)行分布式規(guī)劃以避免機(jī)器人間的沖突。周明等人23提出分布式智能避撞規(guī)劃系統(tǒng)，將原來比較復(fù)雜的大系統(tǒng)轉(zhuǎn)換為相對(duì)簡(jiǎn)單的子系統(tǒng)問題，由各智能機(jī)器人依據(jù)任務(wù)要求和環(huán)境變化，獨(dú)立調(diào)整自身運(yùn)動(dòng)狀態(tài)，完成任務(wù)的分布式智能決策體系結(jié)構(gòu)。任炎等人24提出了基于過程獎(jiǎng)賞和優(yōu)先掃除的強(qiáng)化學(xué)習(xí)多機(jī)器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少?zèng)_突，避免死鎖，提高了系統(tǒng)整體性能。歐錦軍等人25提出了通過調(diào)整機(jī)器人的運(yùn)動(dòng)速度實(shí)現(xiàn)多機(jī)器人避碰，將避碰問題轉(zhuǎn)換為高維線性空間的優(yōu)化問題，并進(jìn)一步將其轉(zhuǎn)換為線性方程的求解。該方法的缺點(diǎn)是系統(tǒng)的復(fù)雜度較高、計(jì)算量太大。人工勢(shì)場(chǎng)方法的特點(diǎn)是計(jì)算簡(jiǎn)潔、實(shí)時(shí)性強(qiáng)、便于數(shù)學(xué)描述，且適合于多自由度機(jī)器人環(huán)境，但容易產(chǎn)生抖動(dòng)和陷入局部極小。為了克服其缺點(diǎn)，景興建等人26提出了人工協(xié)調(diào)場(chǎng)的方法，在傳統(tǒng)排斥力場(chǎng)中增加一個(gè)協(xié)調(diào)力，并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機(jī)器人的運(yùn)動(dòng)狀態(tài)和運(yùn)動(dòng)要求結(jié)合起來，有效地保證機(jī)器人的安全性，提高機(jī)器人在復(fù)雜動(dòng)態(tài)環(huán)境下行為決策的準(zhǔn)確性和魯棒性。3多機(jī)器人協(xié)作和協(xié)調(diào)機(jī)制多機(jī)器人間的運(yùn)動(dòng)協(xié)調(diào)2731是多機(jī)器人路徑規(guī)劃的關(guān)鍵，也是多機(jī)器人與單機(jī)器人路徑規(guī)劃相區(qū)別的根本所在。多機(jī)器人系統(tǒng)在復(fù)雜動(dòng)態(tài)實(shí)時(shí)環(huán)境下，由于