重大裝備制造多機(jī)器人任務(wù)分配與運(yùn)動規(guī)劃技術(shù)研究綜述

張振國 毛建旭 譚浩然 王耀南 張雪波 江一鳴

飛機(jī)蒙皮、船舶艙體、高鐵車身等大型復(fù)雜部件高效高品質(zhì)制造是航空航天、海洋艦船、軌道交通等領(lǐng)域重大裝備發(fā)展的根基,是國家加快培育及發(fā)展的戰(zhàn)略性新興產(chǎn)業(yè),在引領(lǐng)國民經(jīng)濟(jì)發(fā)展、服務(wù)國家重大需求等過程中發(fā)揮著至關(guān)重要的作用[1].

如圖1 所示,大型復(fù)雜部件具有尺寸超大、工序繁多、結(jié)構(gòu)弱剛性、型面復(fù)雜等特點(diǎn)[2],其制造面臨規(guī)模大、任務(wù)多、精度高等難點(diǎn).近些年來,大型復(fù)雜部件制造已經(jīng)進(jìn)入初步發(fā)展階段,現(xiàn)有大型復(fù)雜部件制造模式主要依賴大量人工、專機(jī)設(shè)備、多機(jī)器人產(chǎn)線.人工加工存在一致性差、效率低下等問題,單機(jī)加工存在柔性不足、空間有限等問題,已經(jīng)成為大型復(fù)雜部件制造中迫切需要解決的難點(diǎn).而由多個(gè)單體機(jī)器人組成的多機(jī)器人制造系統(tǒng)能夠增加機(jī)器人作業(yè)的適應(yīng)能力與柔順程度,因此被廣泛應(yīng)用于加工、裝配等關(guān)鍵制造過程中.

圖1 重大裝備加工需求Fig.1 Major equipment processing needs

多機(jī)器人系統(tǒng)是機(jī)器人技術(shù)最廣泛的研究領(lǐng)域之一,相比于數(shù)控機(jī)床與單機(jī)器人,多機(jī)器人系統(tǒng)具有高效、靈活、魯棒性強(qiáng)、并行協(xié)調(diào)作業(yè)能力強(qiáng)等優(yōu)點(diǎn),能夠適應(yīng)復(fù)雜的制造環(huán)境[3]:

1) 高靈活性: 多機(jī)器人可以通過靈活協(xié)同作業(yè)解決復(fù)雜問題;

2) 高效性: 通過多機(jī)器人協(xié)同完成任務(wù)以提高作業(yè)效率;

3) 高魯棒性: 當(dāng)多個(gè)機(jī)器人完成一項(xiàng)任務(wù),其中一個(gè)機(jī)器人出現(xiàn)故障,其他機(jī)器人仍然可以完成這項(xiàng)任務(wù).

這些優(yōu)勢吸引了許多學(xué)術(shù)界和工業(yè)界的研究人員來調(diào)查多機(jī)器人在工業(yè)和商業(yè)重要領(lǐng)域的適用性,近年來多機(jī)器人系統(tǒng)一直出現(xiàn)在機(jī)器人領(lǐng)域的議程上.2011 年,哈佛大學(xué)研究出了一種低成本、適合大規(guī)模實(shí)驗(yàn)的多機(jī)器人系統(tǒng)Kilobot,并開展了多機(jī)器人組隊(duì)實(shí)驗(yàn)[4].Nature發(fā)文報(bào)導(dǎo)了一種自組織仿生多機(jī)器人,具有更強(qiáng)的可擴(kuò)展性和魯棒性[5].Science雜志上發(fā)表了多機(jī)器人智能強(qiáng)化學(xué)習(xí)的研究,可以在動態(tài)約束的環(huán)境下進(jìn)行強(qiáng)化學(xué)習(xí)[6].

但簡單地把多個(gè)機(jī)器人堆砌在一起,不但不能實(shí)現(xiàn)多機(jī)器人系統(tǒng)的優(yōu)勢,反而有可能由于其行為上的并行性和突發(fā)性、位置上的沖突性等,引起機(jī)器人之間的沖突與對抗,使得整體性能降低,導(dǎo)致大規(guī)模多機(jī)器人系統(tǒng)的整體優(yōu)勢無法充分發(fā)揮[7].因此需要研究多機(jī)器人在什么時(shí)刻、應(yīng)采取什么動作、調(diào)用多少機(jī)器人去實(shí)現(xiàn)多機(jī)器人之間的協(xié)作合作,即復(fù)雜環(huán)境下的多機(jī)器人任務(wù)分配與運(yùn)動規(guī)劃是決定多機(jī)器人良好合作基礎(chǔ)的決策中樞.

如圖2 所示,多機(jī)器人任務(wù)分配和運(yùn)動規(guī)劃以環(huán)境地圖信息為基礎(chǔ),為重大裝備大型復(fù)雜部件制造提供任務(wù)序列及運(yùn)動軌跡,在制造過程中占據(jù)著重要的作用,其與機(jī)器人數(shù)量、種類以及復(fù)雜的動態(tài)環(huán)境息息相關(guān),而分配和規(guī)劃過程中的計(jì)算量以及效率、安全性都十分重要.隨著科技的發(fā)展,多機(jī)器人任務(wù)分配與運(yùn)動規(guī)劃也逐步應(yīng)用到各行各業(yè).在增材制造領(lǐng)域,Zhang 等[8]建立可擴(kuò)展多機(jī)器人三維打印任務(wù)分配和路徑規(guī)劃框架,使機(jī)器人群能夠在整個(gè)建筑任務(wù)中打印任意的幾何圖形.在森林搜救領(lǐng)域,Foehn 等[9]通過引入沿軌跡公式優(yōu)化時(shí)間分配和軌跡規(guī)劃,完成飛行機(jī)器人群檢測、搜索和救援等任務(wù).在人機(jī)交互領(lǐng)域,Ali 等[10]提出了一種基于機(jī)器人-人體信任的異構(gòu)人機(jī)團(tuán)隊(duì)任務(wù)分配方法,以提高人機(jī)團(tuán)隊(duì)任務(wù)分配效率.協(xié)同加工領(lǐng)域,Suárez-Ruiz 等[11]使用Bi-RRT 軌跡規(guī)劃方法,完成對椅子完整的組裝.Li 等[12]通過使用基于強(qiáng)化學(xué)習(xí)的運(yùn)動規(guī)劃策略,完成機(jī)器人智能化烹飪?nèi)蝿?wù).

圖2 任務(wù)分配與運(yùn)動規(guī)劃在多機(jī)器人制造過程中的重要性Fig.2 The importance of task allocation and motion planning in multi-robot manufacturing

綜上所述,在大型制造場景下為提高多機(jī)器人制造效率,通常對多任務(wù)多工序同時(shí)進(jìn)行,然而多機(jī)器人同時(shí)段完成多個(gè)任務(wù)帶來嚴(yán)重的協(xié)同干涉問題,同時(shí)大型復(fù)雜部件高的精度需求為目前亟待解決的難題之一.因此面對大型復(fù)雜部件制造規(guī)模大、任務(wù)工序多、沖突干涉多、精度需求高等挑戰(zhàn),如何使用適合的任務(wù)分配和動態(tài)規(guī)劃方法,以提高多機(jī)器人制造過程中的作業(yè)效率、安全性、魯棒性是亟待解決的關(guān)鍵性問題.因此本文在多機(jī)器人大型復(fù)雜部件制造的背景下,首先對多機(jī)器人任務(wù)分配和動態(tài)規(guī)劃方法的重要性進(jìn)行分析,然后闡述了近些年來任務(wù)分配和動態(tài)規(guī)劃的方法,其次對復(fù)雜作業(yè)場景下大型部件多機(jī)器人制造任務(wù)分配和運(yùn)動規(guī)劃進(jìn)行了展望,在此基礎(chǔ)上給出了解決問題的新思路,最后對所研究內(nèi)容進(jìn)行總結(jié).

1 多機(jī)器人任務(wù)分配方法研究

如圖3 所示,多機(jī)器人任務(wù)分配過程可以表述為最優(yōu)分配問題,其目標(biāo)是給機(jī)器人分配任務(wù),同時(shí)在約束條件下優(yōu)化整體系統(tǒng)性能,實(shí)現(xiàn)整體執(zhí)行效果最佳,多機(jī)器人任務(wù)分配是協(xié)同作業(yè)最具挑戰(zhàn)性的問題之一[13].一方面,任務(wù)分配會直接影響到整個(gè)系統(tǒng)的效率;另一方面,當(dāng)其中一個(gè)機(jī)器人沒有完成任務(wù)時(shí),通過有效的協(xié)商分配使多機(jī)器人協(xié)作完成任務(wù)成為更多學(xué)者關(guān)注的問題[14].盡管現(xiàn)有研究存在大量的任務(wù)分配方法,但一些重要的方面至今仍很少受到關(guān)注,主要包括復(fù)雜動態(tài)環(huán)境下的任務(wù)分配、大范圍制造環(huán)境下區(qū)域劃分任務(wù)分配、跨區(qū)域任務(wù)分配和異構(gòu)機(jī)器人任務(wù)分配.本節(jié)的主要目的是全面回顧任務(wù)分配問題,以及解決這些問題的最新方法和未來的主要發(fā)展方向.目前,多機(jī)器人任務(wù)分配方法按照執(zhí)行模式可以分為集中式任務(wù)分配和分布式任務(wù)分配,按照方法分類包含基于線性規(guī)劃的任務(wù)分配、基于市場的任務(wù)分配、基于啟發(fā)式的任務(wù)分配及基于人工智能強(qiáng)化學(xué)習(xí)的任務(wù)分配等.

圖3 多機(jī)器人任務(wù)分配問題Fig.3 Task allocation problem of multi-robot

1.1 任務(wù)分配執(zhí)行模式

1.1.1 集中式任務(wù)分配

集中式方法是研究較多的一類方法,主要思想是采用一個(gè)中央處理中心進(jìn)行分配,并與所有其他服務(wù)器有通信渠道.如圖4 所示,該處理中心掌握全局信息,決定必須分配給其他服務(wù)器的任務(wù).在這些情況下,通常會考慮全局效用函數(shù)來與其他服務(wù)器進(jìn)行通信[15].如使用集中式任務(wù)分配方法進(jìn)行多機(jī)器人汽車制造與裝配工作[16]、多無人機(jī)環(huán)境檢測任務(wù)[17],降低任務(wù)交付與執(zhí)行過程中的延時(shí)等[18].

圖4 集中式任務(wù)分配系統(tǒng)Fig.4 Centralized task allocation system

集中式任務(wù)分配方法的優(yōu)點(diǎn)是使用較少的系統(tǒng)資源并具有較低的實(shí)現(xiàn)成本,同時(shí)避免了任務(wù)分配上的沖突,不需要共識階段,也可以找到分配問題的最佳解決方案.但是任務(wù)分配的計(jì)算復(fù)雜度會隨著問題規(guī)模增大而呈現(xiàn)指數(shù)上升,中央處理中心容易出現(xiàn)過載,其次集中式任務(wù)分配不能適應(yīng)動態(tài)環(huán)境,主要用于靜態(tài)任務(wù)分配,缺乏魯棒性,一旦中央處理中心出現(xiàn)故障,將導(dǎo)致整體性能惡化[19-20].常用的集中式任務(wù)分配方法包括線性規(guī)劃方法、啟發(fā)式方法、強(qiáng)化學(xué)習(xí)方法等.

1.1.2 分布式任務(wù)分配

分布式任務(wù)分配方法克服了集中式任務(wù)分配的缺點(diǎn),在過去幾年引起了研究人員的關(guān)注.如圖5 所示,分布式任務(wù)分配沒有中央處理中心,各個(gè)機(jī)器人對環(huán)境有本地感知,可以彼此相互交流和協(xié)商完成任務(wù),因此任務(wù)分配的決定在本地以分布式方式通過每個(gè)機(jī)器人本身的效用函數(shù)進(jìn)行[21].如使用分布式任務(wù)分配方法降低多機(jī)器人的任務(wù)消耗、減小分配時(shí)間[22-23],提高制造過程的可擴(kuò)展性、有效性[24].

圖5 分布式任務(wù)分配系統(tǒng)Fig.5 Distributed task allocation system

分布式任務(wù)分配方法具有強(qiáng)魯棒性的優(yōu)點(diǎn),部分機(jī)器人故障對整體性能的影響很小,且機(jī)器人之間的通信弱,多機(jī)器人呈現(xiàn)強(qiáng)可擴(kuò)展性.但是分布式任務(wù)分配缺乏全局信息,容易陷入局部最優(yōu);其次,任務(wù)分配決策過程中需要個(gè)體之間不斷交換信息,當(dāng)機(jī)器人規(guī)模較大時(shí)算法收斂速度較慢.現(xiàn)有的分布式任務(wù)分配方法主要包括啟發(fā)式方法、市場法等.

1.2 多機(jī)器人任務(wù)分配方法

1.2.1 基于線性規(guī)劃的任務(wù)分配方法

優(yōu)化是應(yīng)用數(shù)學(xué)的一個(gè)分支,目的是從一組可行解中找到問題的最優(yōu)解,這組可行解受到約束的限制,利用約束的限制定義問題的目標(biāo)函數(shù),定量描述了系統(tǒng)的目標(biāo)[25].基于優(yōu)化算法提高了在處理有噪聲輸入數(shù)據(jù)時(shí)的適應(yīng)性能,在未知空間中探索新區(qū)域方面具有更高的潛力[26].基于優(yōu)化的方法可以按照目標(biāo)類別分為確定性優(yōu)化和隨機(jī)優(yōu)化,線性規(guī)劃方法是確定性優(yōu)化之一,其思想是通過將實(shí)際的任務(wù)分配問題轉(zhuǎn)化為求解數(shù)學(xué)模型的問題,并利用線性規(guī)劃技術(shù)進(jìn)行求解.近些年來混合整數(shù)線性規(guī)劃(Mixed integer linear programming,MILP)由于其嚴(yán)謹(jǐn)性、靈活性和廣泛的建模能力,已成為分配問題最廣泛的方法之一[27].

基于MILP 的分配方法最初應(yīng)用于化學(xué)工程和運(yùn)籌學(xué)中,Reklaitis 等回顧了對于批處理操作的分配和規(guī)劃,重點(diǎn)關(guān)注任務(wù)分配的基本組成部分和可用的解決方法[28].在多機(jī)器人任務(wù)分配領(lǐng)域,Bererton 等采用線性規(guī)劃方法解決了多機(jī)器人協(xié)作探索中的任務(wù)分配問題[29].Schumacher 等為保證多機(jī)器人在有限時(shí)間內(nèi)解的存在,采用MILP 開發(fā)了一種最優(yōu)任務(wù)分配和定時(shí)方法,可用于以最優(yōu)方式將所有任務(wù)分配給具有涉及時(shí)間和任務(wù)順序約束的耦合任務(wù)的飛行器組[30].為解決任務(wù)分配極大極小問題,聶明泓等基于MILP 模型,提出一種矩陣算法,并與窮舉解及傳統(tǒng)MILP 解的計(jì)算復(fù)雜度進(jìn)行了比較,理論分析和數(shù)值試驗(yàn)表明矩陣作業(yè)法對極大極小和總體極小任務(wù)分配問題,都能有效地提供最優(yōu)解[31].為完成任務(wù)分配的周期時(shí)間最小化,?blad等設(shè)計(jì)了一種時(shí)空負(fù)載均衡與協(xié)調(diào)方案,使用MILP模型指導(dǎo)任務(wù)分配、序列和機(jī)器人運(yùn)動(路徑和速度)來防止機(jī)器人與機(jī)器人碰撞[32].

盡管基于線性規(guī)劃的任務(wù)分配方法可以獲得全局最優(yōu)解,但由于多機(jī)器人數(shù)量和任務(wù)眾多,求解時(shí)間隨著問題規(guī)模的增加呈指數(shù)增長,導(dǎo)致計(jì)算量增大、實(shí)時(shí)性差,在此情況下計(jì)算全局任務(wù)分配的最優(yōu)解比較困難.因此,近幾年來在多機(jī)制造領(lǐng)域常與其他方法一起使用.Spensieri 等結(jié)合混合整數(shù)線性規(guī)劃方法與基于市場廣義旅行推銷員問題方法,解決汽車制造站多個(gè)工業(yè)機(jī)器人協(xié)作任務(wù)分配問題,避免了多機(jī)器人任務(wù)沖突[16].針對外界威脅下的任務(wù)分配和操作順序規(guī)劃會降低性能和成功率問題,An 等通過采用MILP 和勢場法結(jié)合,提出了具有實(shí)時(shí)路徑規(guī)劃的任務(wù)分配方法,同時(shí)設(shè)計(jì)了任務(wù)選擇算法來補(bǔ)償修改后的次優(yōu)MILP 問題[33].考慮多個(gè)無人機(jī)環(huán)境檢測之間的任務(wù)分配問題,Hu等針對一組預(yù)定的地面目標(biāo)執(zhí)行攻擊任務(wù),將原始問題分解為三個(gè)級別的子問題: 目標(biāo)聚類、聚類分配和目標(biāo)分配,前兩個(gè)子問題分別采用聚類算法和整數(shù)線性規(guī)劃集中求解,第三個(gè)子問題采用混合整數(shù)線性規(guī)劃模型和改進(jìn)蟻群算法,以分布式和并行方式求解,仿真實(shí)驗(yàn)證明所提出的分層方法可以大大降低任務(wù)分配問題的計(jì)算復(fù)雜度[17].

如圖6 所示,基于MILP 的方法具有很高的嚴(yán)謹(jǐn)性,且可以獲得全局最優(yōu)解,但盡管如此,如何解決線性規(guī)劃算法計(jì)算量大、計(jì)算時(shí)間長仍是具有挑戰(zhàn)性的問題.

圖6 基于線性規(guī)劃的任務(wù)分配方法[16-17,33]Fig.6 Task allocation method based on linear programming[16-17,33]

1.2.2 基于啟發(fā)式的任務(wù)分配方法

啟發(fā)式方法是隨機(jī)優(yōu)化算法的一種,利用系統(tǒng)已有的經(jīng)驗(yàn)啟發(fā)選擇,保證空間搜索有效性,加快了算法收斂速度,可以快速找到近似最優(yōu)解.相比于線性規(guī)劃而言,啟發(fā)式搜索方法更適合大規(guī)模動態(tài)的應(yīng)用場景,按照優(yōu)化方法分為模擬退火算法、進(jìn)化算法以及群體智能算法等.

模擬退火算法是由Kirkpatrick 等提出的一種通用概率演算法,用來在一個(gè)大的搜尋空間內(nèi)找尋命題的最優(yōu)解[34].Wang 等采用多旅行商方法(Multiple travelling salesman problem,MTSP)優(yōu)化系統(tǒng)模型,在每個(gè)機(jī)器人搜索任務(wù)區(qū)域數(shù)量均衡的前提下建立目標(biāo)函數(shù),并使用分布式模擬退火方法來解決大場景下多機(jī)器人系統(tǒng)的分配問題[35].針對異構(gòu)分布式系統(tǒng)的任務(wù)分配問題,Attiya 等提出了一種新型模擬退火啟發(fā)式算法,建立了一個(gè)成本函數(shù)的可靠性分配模型,提高了系統(tǒng)可靠性[36].但是模擬退火法存在收斂速度慢,執(zhí)行時(shí)間長,算法性能與初始值有關(guān)及參數(shù)敏感等缺點(diǎn),在降溫時(shí)間設(shè)置過快的情況下,無法確保得出全局最優(yōu)解.

群體智能算法是一種生物啟發(fā)式算法,在自然界中,生物個(gè)體能從成群的行動中獲益.個(gè)體和集體行為模型表明,相互作用可以呈現(xiàn)出群體形態(tài),組成了能夠集體處理信息和提供決策的團(tuán)體.通過共享信息,群體可以比個(gè)體做出更好的決定,被稱為“群體智慧”[37].群體智能算法是一種新興的演化計(jì)算技術(shù),已引起越來越多研究者的關(guān)注,它與人工生命特別是進(jìn)化策略以及遺傳算法有著極為特殊的聯(lián)系.Li 等考慮智能倉庫系統(tǒng)任務(wù)分配問題,通過最小化最大完成時(shí)間來降低機(jī)器人的總成本,考慮聚合程度最小化所有訂單的運(yùn)輸協(xié)同效應(yīng)總和,提出了改進(jìn)的粒子群算法,有效解決訂單和任務(wù)的積壓,從而提高存儲系統(tǒng)的效率[38].Panerati 等提出了一種蜂群啟發(fā)式算法,其中分布式機(jī)器人導(dǎo)航控制器負(fù)責(zé)保證連接性和對多個(gè)任務(wù)的追求,全局任務(wù)分配控制器以最小的計(jì)算負(fù)載逼近最優(yōu)策略,解決多機(jī)器人多任務(wù)的空間覆蓋問題[39].利用機(jī)器人在空間中移動時(shí)交互過程將任務(wù)分配給每個(gè)機(jī)器人,Mayya 等基于蟻群算法建立一個(gè)分析模型來描述在密集的機(jī)器人群中發(fā)生的相遇,允許多機(jī)器人根據(jù)當(dāng)前分配與期望值的距離來調(diào)整任務(wù)之間的傳遞速度,最終促進(jìn)機(jī)器人不間斷地執(zhí)行任務(wù)[22].在車輪裝配過程中,Geetha 等為完成最佳公差分配,通過最小化制造成本(公差和質(zhì)量損失成本的總和)和機(jī)器閑置時(shí)間成本來分配組件公差,并開發(fā)了一種遺傳算法,用于分配組件的公差并確定分配的最佳產(chǎn)品序列[40].

如圖7 所示,啟發(fā)式算法保證了空間搜索的有效性,提升了算法的收斂速度,可以快速找到任務(wù)分配的近似最優(yōu)解.然而,啟發(fā)式算法在面臨復(fù)雜的搜索空間時(shí),無法保證搜索效率以及解的全局最優(yōu)性.同時(shí),群體智能方法利用個(gè)體之間的相互協(xié)作和信息分享求解優(yōu)化問題,具體閾值設(shè)置依賴具體任務(wù),通用性受到限制.

圖7 基于啟發(fā)式算法的任務(wù)分配[34,40]Fig.7 Task assignment based on heuristic algorithm[34,40]

1.2.3 基于市場的任務(wù)分配方法

在經(jīng)濟(jì)理論中,拍賣是由交易所的交易規(guī)則機(jī)制來定義、根據(jù)投標(biāo)人的出價(jià)和拍賣標(biāo)準(zhǔn)分配一組商品或服務(wù)的過程.基于拍賣的概念提出了一種協(xié)調(diào)機(jī)器人/代理之間活動的方法,即基于市場的任務(wù)分配方法.由于基于市場的分配方法滿足目標(biāo)函數(shù)的高效性、高魯棒性和可擴(kuò)展性,在機(jī)器人領(lǐng)域獲得了較大的關(guān)注.機(jī)器人團(tuán)體會根據(jù)自己的能力競標(biāo)任務(wù),尋求機(jī)器人效用優(yōu)化的目標(biāo)函數(shù),以執(zhí)行特定的任務(wù)[41].

為解決自動駕駛汽車的協(xié)調(diào)任務(wù)分配問題,Choi 等利用基于市場的分布式?jīng)Q策策略作為任務(wù)選擇的機(jī)制,并使用本地通信的共識例程作為沖突解決機(jī)制,使中標(biāo)值達(dá)成一致.在評分方案的合理假設(shè)下,所設(shè)計(jì)方法被證明能夠收斂到無沖突賦值,與現(xiàn)有的基于拍賣的任務(wù)分配算法相比,具有更好的收斂特性[42].考慮到機(jī)器人協(xié)作過程中能量消耗過快的因素,Wu 等設(shè)計(jì)一種基于基尼系數(shù)的任務(wù)分配方法,將市場分配機(jī)制融入到基于基尼系數(shù)的方法中,可以根據(jù)應(yīng)用環(huán)境減少同等任務(wù)完成次數(shù)時(shí)的資源消耗[43].針對通信范圍受限的動態(tài)環(huán)境中多無人機(jī)的任務(wù)分配問題,Oh 等提出了一種新型市場分布式任務(wù)分配方法,所提算法具有多項(xiàng)式時(shí)間復(fù)雜度,數(shù)值仿真結(jié)果表明在通信受限情況有效提高了算法的可擴(kuò)展性和有效性[24].為保證飛機(jī)裝配任務(wù)下有效使用協(xié)作機(jī)器人及無碰撞分配任務(wù),Tereshchuk 等利用工件幾何形狀和問題結(jié)構(gòu),在標(biāo)稱條件下生成平衡且無沖突的機(jī)器人分配計(jì)劃,隨后使用基于市場的優(yōu)化器來分配處理任務(wù)故障,以減小任務(wù)分配計(jì)算時(shí)間[23].為解決集裝箱的協(xié)同搬運(yùn)問題,Chen 等基于軌道式堆場起重機(jī)和AGV 分配一體化問題,提出了市場驅(qū)動方法,通過迭代調(diào)整每個(gè)子任務(wù)的原始成本和雙重成本,獲得具有成本效益的解決方案[44].

綜上所述,基于市場的任務(wù)分配方法具有良好的可靠性、可擴(kuò)展性,但在設(shè)計(jì)成本函數(shù)和收入函數(shù)時(shí)缺乏形式化.此外,談判協(xié)議、成本函數(shù)及引入相關(guān)的懲罰方案可能會使任務(wù)分配方法設(shè)計(jì)復(fù)雜化,從而導(dǎo)致過度的通信和計(jì)算,產(chǎn)生較差的解決方案.

1.2.4 基于學(xué)習(xí)的任務(wù)分配方法

在大型復(fù)雜部件制造過程中機(jī)器人種類多樣、任務(wù)繁瑣,難以預(yù)測機(jī)器人需要處理的未來干擾,尤其當(dāng)無法獲取環(huán)境的數(shù)學(xué)模型時(shí),實(shí)際應(yīng)用動態(tài)多變.為了解決該問題,機(jī)器人采用自身和其他機(jī)器人過去的信息,學(xué)習(xí)面對這種干擾,從而提高系統(tǒng)的魯棒性[45].近些年,隨著以深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)為代表的人工智能技術(shù)在越來越多領(lǐng)域取得突破,研究者嘗試將人工智能方法引入至多機(jī)器人任務(wù)分配問題.

強(qiáng)化學(xué)習(xí)是一種典型的機(jī)器學(xué)習(xí)技術(shù),中央處理中心利用過去的信息學(xué)習(xí)如何在不同的環(huán)境下行動.外部環(huán)境通常被描述為馬爾科夫決策過程(Markov decision processes,MDP),被中央處理中心優(yōu)化為成本函數(shù)或獎(jiǎng)勵(lì)函數(shù),從而讓機(jī)器人在環(huán)境中進(jìn)行學(xué)習(xí).Wilson 等將強(qiáng)化學(xué)習(xí)方法應(yīng)用到多任務(wù)分配問題中,使用分層貝葉斯無限混合模型對MDP 的分布進(jìn)行建模,分層貝葉斯框架提供了強(qiáng)大的先驗(yàn)條件,能夠根據(jù)過去的環(huán)境快速推斷新環(huán)境的特征,同時(shí)使用非參數(shù)模型快速適應(yīng)遇到的未知環(huán)境.在僅觀察少量任務(wù)時(shí),所提出方法可以顯著加快收斂到最優(yōu)任務(wù)分配策略的速度[46].為降低任務(wù)交付和執(zhí)行階段的延遲,Mai 等提出了一種進(jìn)化策略的強(qiáng)化學(xué)習(xí)方法,在云服務(wù)器之間進(jìn)行實(shí)時(shí)任務(wù)分配,以減少長期內(nèi)的總計(jì)算延遲,實(shí)驗(yàn)結(jié)果表明所提出的方法將延遲降低了約16.1%[18].為了將任務(wù)安排給合適的機(jī)器人以實(shí)現(xiàn)不同的目標(biāo),Sun 等首先通過深度學(xué)習(xí)模型門控循環(huán)單元預(yù)測即將到來的任務(wù)和機(jī)器人的種類、數(shù)量,然后研究了基于深度Q 網(wǎng)絡(luò) (Deep Q-network,DQN) 和雙DQN (Double deep Q-networks,DDQN) 的自適應(yīng)批處理策略,以解決任務(wù)分配的環(huán)境適應(yīng)和動態(tài)批處理問題[47].針對大規(guī)模、動態(tài)任務(wù)分配過程啟發(fā)式方法計(jì)算困難問題,Wang 等提出基于圖神經(jīng)網(wǎng)絡(luò)的分配方法,自動學(xué)習(xí)分配過程問題的特征,克服大規(guī)模任務(wù)分配的局限性,完成高質(zhì)量任務(wù)分配[48].Choudhury 等考慮在時(shí)間窗口約束和任務(wù)完成不確定性下將任務(wù)動態(tài)分配給多個(gè)機(jī)器人,提出了一種多機(jī)器人隨機(jī)沖突深度學(xué)習(xí)分配算法,提高了機(jī)器人數(shù)量的可擴(kuò)展性,并通過多臂傳送帶拾取和放置等任務(wù)驗(yàn)證了所提出方法的有效性[49].

如圖8 所示,機(jī)器學(xué)習(xí)模型具有泛化性和高魯棒性,可以很好地適應(yīng)高度動態(tài)的環(huán)境.但獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)困難、采樣效率堪憂等仍然是機(jī)器學(xué)習(xí)方法亟待解決的問題.因此,如何針對復(fù)雜作業(yè)場景多機(jī)器人任務(wù)分配設(shè)計(jì)高效的機(jī)器學(xué)習(xí)模型仍處在探索階段.

圖8 基于學(xué)習(xí)的任務(wù)分配方法[46-49]Fig.8 Task allocation method based on learning[46-49]

1.2.5 混合式任務(wù)分配算法

通常情況下,僅使用一種任務(wù)分配算法難以滿足復(fù)雜制造場景下多機(jī)器人任務(wù)分配的需求,因此需要兩種或以上的方法進(jìn)行結(jié)合使用.利用線性規(guī)劃算法高嚴(yán)謹(jǐn)性的優(yōu)勢,Spensieri 等與市場法結(jié)合完成汽車制造問題[16],An 等與勢場法結(jié)合補(bǔ)償陷入局部最優(yōu)問題[33],Hu 等與蟻群算法結(jié)合降低計(jì)算的復(fù)雜度[17].

Zhou 等考慮多機(jī)器人多工位協(xié)同點(diǎn)焊任務(wù)分配問題,構(gòu)建了一個(gè)通用優(yōu)化模型,以提高相關(guān)算法在實(shí)際應(yīng)用中的適應(yīng)性和可行性,使用通過迭代梯形加速和減速運(yùn)動的求解器來解決單機(jī)器人任務(wù)分配,在此基礎(chǔ)上采用針對機(jī)器人之間具有眾多約束條件的焊接任務(wù)分配問題,并結(jié)合遺傳算法迭代求解多任務(wù)焊接問題[50].Tereshchuk 等考慮多個(gè)協(xié)作的機(jī)器人機(jī)械手來組裝大型飛機(jī)結(jié)構(gòu)需要離散的如鉆孔和安裝緊固件的任務(wù),減少工具更換產(chǎn)生的大量時(shí)間成本,提出了一種混合式任務(wù)分配算法,首先調(diào)整基于迭代拍賣的方法,使用啟發(fā)式方法對優(yōu)先級關(guān)系進(jìn)行編碼,其次開發(fā)一種機(jī)器學(xué)習(xí)方法,根據(jù)問題特征自動選擇有效的分配啟發(fā)方法[51].考慮大型航天器復(fù)雜的內(nèi)部結(jié)構(gòu)問題,Liu 等提出一個(gè)沖突模型來描述特定任務(wù)的沖突約束,在每個(gè)工作區(qū)域中定義了干擾區(qū)域,開發(fā)一種結(jié)合啟發(fā)式與迭代本地搜索的快速施工啟發(fā)式方法,以最佳效率搜索任務(wù)進(jìn)度[52].Paiva 等提出了一種使用圖搜索算法、啟發(fā)式方法和機(jī)器學(xué)習(xí)方法結(jié)合來解決作業(yè)排序和工具切換問題[53].

如圖9 所示,混合式任務(wù)分配算法可以結(jié)合兩種方法的優(yōu)點(diǎn),完成更優(yōu)的任務(wù)分配效果,但是如何在不產(chǎn)生額外的損耗下體現(xiàn)兩種方法的優(yōu)勢還需要更多的研究.

圖9 基于混合算法的任務(wù)分配方法[50-53]Fig.9 Task allocation method based on hybrid algorithm[50-53]

1.3 復(fù)雜制造場景下多機(jī)器人任務(wù)分配

大型復(fù)雜部件制造場景具有制造規(guī)模大、任務(wù)工序多、沖突干涉多等難點(diǎn),需要將復(fù)雜作業(yè)場景進(jìn)行區(qū)域劃分避免多任務(wù)之間的干涉沖突.同時(shí)對每個(gè)區(qū)域內(nèi)的任務(wù)與多機(jī)器人進(jìn)行作業(yè)分配.當(dāng)所在區(qū)域需要其他區(qū)域協(xié)作時(shí),采用跨區(qū)域分配方法.

1.3.1 作業(yè)場景區(qū)域劃分方法

為了防止復(fù)雜制造場景下多機(jī)器人及多任務(wù)之間的干涉沖突,對作業(yè)區(qū)域進(jìn)行劃分,以保證高魯棒性的任務(wù)分配過程.如圖10 所示,Fung 等[54]為減少重復(fù)工作并減少每個(gè)機(jī)器人之間的干擾,提出了一種信息速率自適應(yīng)采樣方法,用于在環(huán)境中采集機(jī)器人任務(wù)與傳感器測量值,并根據(jù)探索區(qū)域所需的工作量劃分為不同的子區(qū)域.

圖10 不同數(shù)量機(jī)器人情況下區(qū)域劃分[54]Fig.10 Area division under different number of robots[54]

Shi 等[55]考慮了異構(gòu)機(jī)器人群對環(huán)境特征采樣和建模的影響,提出了一種環(huán)境分區(qū)方法,結(jié)合高斯過程模型學(xué)習(xí)框架,以高效和可擴(kuò)展的方式對環(huán)境進(jìn)行自適應(yīng)采樣和區(qū)域劃分建模,在空地協(xié)同下驗(yàn)證了所提方法的有效性.

1.3.2 基于復(fù)雜場景制造的任務(wù)分配方法

針對復(fù)雜制造場景任務(wù)工序多的特點(diǎn),為了將多任務(wù)工序準(zhǔn)確地分配給每一組機(jī)器人,以提高系統(tǒng)的可靠性和效率,完成多機(jī)器人高效高質(zhì)量作業(yè).如圖11 所示,Lopes 等[56]將焊接生產(chǎn)線任務(wù)分配問題建模成混合整數(shù)規(guī)劃模型,并使用求解器求解,此方法簡單精確、獲得了任務(wù)分配的全局最優(yōu)解.

圖11 復(fù)雜作業(yè)場景下多機(jī)器人任務(wù)分配[56,58]Fig.11 Multi-robot task allocation in complex operation scenarios[56,58]

Mitiche 等[57]提出了一種基于插入式的啟發(fā)式算法,解決了靜態(tài)時(shí)間擴(kuò)展多機(jī)器人的任務(wù)分配問題.Ham 等[58]使用大鄰域搜索算法解決了波音777 飛機(jī)裝配中的多機(jī)器人任務(wù)工作順序分配問題.Huang 等[59]采用基于Distributed-Q 算法的強(qiáng)化學(xué)習(xí)模型,解決了多機(jī)器人協(xié)同加工過程任務(wù)分配問題.Gil 等[60]采用分層強(qiáng)化學(xué)習(xí)解決了大規(guī)模復(fù)雜環(huán)境下的多機(jī)器人任務(wù)分配問題.

1.3.3 跨區(qū)域任務(wù)分配方法

復(fù)雜場景下多機(jī)器人協(xié)同作業(yè)過程中,當(dāng)本區(qū)域機(jī)器人無法滿足作業(yè)條件時(shí),采用跨區(qū)域任務(wù)分配策略.

如圖12 所示,Yu 等[61]考慮多機(jī)器人分配在空間和時(shí)間上的復(fù)雜性問題,基于新型染色體的編碼格式,提出了一種新型改進(jìn)遺傳算法,不僅可以完成多異構(gòu)無人機(jī)跨區(qū)域協(xié)調(diào)任務(wù)分配,而且考慮任務(wù)需求,將完成任務(wù)的機(jī)器人返回至適合的基地而不是必須返回至初始基地.Zhang 等[62]基于改進(jìn)貪婪算法,提出了一種基于在線分配模型的跨區(qū)域任務(wù)分配方法,并通過離線指導(dǎo)和在線分配策略來優(yōu)化任務(wù)分配流程,可以在同樣時(shí)間內(nèi)完成更多的任務(wù)以提高效率.

圖12 多機(jī)器人跨區(qū)域任務(wù)分配[61-62]Fig.12 Multi-robot cross-region task allocation[61-62]

如表1 所示,目前多機(jī)器人任務(wù)分配在制造領(lǐng)域得到了一定的研究進(jìn)展,在嚴(yán)謹(jǐn)性、魯棒性、收斂速度等方面取得了研究成果,但在模型設(shè)計(jì)復(fù)雜化、環(huán)境規(guī)模增大導(dǎo)致求解空間的復(fù)雜性、最優(yōu)性等方面還有待提高.對于復(fù)雜場景下多機(jī)器人制造任務(wù)分配還有一定程度的欠缺,尤其是作業(yè)場景區(qū)域劃分方法及跨區(qū)域任務(wù)分配方法,還需要進(jìn)一步的研究.

表1 任務(wù)分配方法分析Table 1 The analysis of task allocation

2 多機(jī)器人運(yùn)動規(guī)劃

在多機(jī)器人大型復(fù)雜部件制造過程中,需要不斷通過中央處理中心將機(jī)器人從起始位置移動到目標(biāo)位置,在此過程中,機(jī)器人必須始終能夠避開障礙物與其他機(jī)器人,以保持安全[63].

運(yùn)動規(guī)劃是指根據(jù)任務(wù)給定的起始狀態(tài)和目標(biāo)狀態(tài)機(jī)器人的運(yùn)動方程,建立滿足特定約束條件的數(shù)學(xué)函數(shù)路徑表達(dá)式,約束條件主要包括運(yùn)動學(xué)約束、動力學(xué)約束、路徑約束、障礙約束或能量約束等.運(yùn)動規(guī)劃包含路徑規(guī)劃和軌跡規(guī)劃,是機(jī)器人領(lǐng)域的研究熱點(diǎn)之一[64].路徑規(guī)劃的目的是尋找連接起始狀態(tài)和目標(biāo)狀態(tài)序列點(diǎn)的策略,使尋找到的序列點(diǎn)與障礙物之間的距離盡可能遠(yuǎn),同時(shí)到達(dá)目的地的路徑盡可能短.軌跡規(guī)劃是在路徑規(guī)劃的基礎(chǔ)上加入時(shí)間信息,使用時(shí)間二次積分多項(xiàng)式形式表示,通過對時(shí)間求一階與二階導(dǎo)數(shù)獲取機(jī)器人從初始狀態(tài)到目標(biāo)狀態(tài)的速度與加速度,使機(jī)器人的運(yùn)動曲線盡可能平滑、運(yùn)動時(shí)間盡可能短、運(yùn)動代價(jià)盡可能小.當(dāng)路徑規(guī)劃滿足機(jī)器人時(shí)間約束條件時(shí),路徑規(guī)劃即為軌跡規(guī)劃[65].

現(xiàn)有的研究在水下機(jī)器人[66-67]、爬壁機(jī)器人[68]及微型飛行器[69-70]等方面進(jìn)行了運(yùn)動規(guī)劃方法設(shè)計(jì)和驗(yàn)證,同時(shí)也采用不同的方法進(jìn)行呈現(xiàn),對機(jī)器人運(yùn)動規(guī)劃發(fā)展做出了很大的貢獻(xiàn).但是,上述研究僅對不同種類的單機(jī)器人進(jìn)行路徑規(guī)劃分析.如圖13 所示,大型復(fù)雜部件制造存在場景大、任務(wù)多、作業(yè)空間受限等特點(diǎn),運(yùn)動規(guī)劃在多機(jī)器人領(lǐng)域仍然具有較大的挑戰(zhàn),每個(gè)新機(jī)器人的增加引起的搜索空間指數(shù)增長為亟待解決的問題之一.目前,多機(jī)器人運(yùn)動規(guī)劃方法主要分為基于搜索的運(yùn)動規(guī)劃、基于勢場的運(yùn)動規(guī)劃、基于采樣的運(yùn)動規(guī)劃及基于人工智能的運(yùn)動規(guī)劃方法.

圖13 復(fù)雜場景下多機(jī)器人運(yùn)動規(guī)劃Fig.13 Motion planning of multi-robot in complex scenarios

2.1 多機(jī)器人運(yùn)動規(guī)劃方法

2.1.1 基于搜索的規(guī)劃算法

基于搜索的運(yùn)動規(guī)劃方法具有良好的穩(wěn)定性和精確性,是目前較為成熟且在移動機(jī)器人、游戲領(lǐng)域中廣泛應(yīng)用的一類運(yùn)動規(guī)劃方法.廣度優(yōu)先搜索算法、Dijkstra 算法、A* 算法、D* 算法(Dynamic A*)及沖突搜索算法等都是基于搜索法的優(yōu)秀代表.

廣度優(yōu)先搜索[71]能夠求得運(yùn)動規(guī)劃問題的最優(yōu)解,該算法采用以起始狀態(tài)為中心,逐步向外層層探索的策略,算法耗費(fèi)大量時(shí)間在探索無用區(qū)域,尋路效率較低.1995 年計(jì)算機(jī)學(xué)家Ng 等提出的Dijkstra 算法[72]是一種廣度優(yōu)先搜索與啟發(fā)式搜索相結(jié)合的貪心算法,首先計(jì)算出從初始位置到環(huán)境中每個(gè)位置的最短距離,然后將距離初始位置最近的點(diǎn)作為中繼點(diǎn),其次更新從初始位置到各個(gè)位置的最短距離,而后重復(fù)上述步驟直至遍歷環(huán)境中所有位置為中繼點(diǎn),Dijkstra 算法能獲得從初始位置到環(huán)境中任意位置的最短距離.但Dijkstra 算法保留了廣度優(yōu)先搜索需要通過大量計(jì)算才能尋得可行解的問題,效率較低.Hart 等提出的A* 算法[73]是一種基于Dijkstra 算法改進(jìn)優(yōu)先級排序的啟發(fā)式算法,算法將節(jié)點(diǎn)權(quán)重與到達(dá)目標(biāo)點(diǎn)的距離二者結(jié)合作為優(yōu)先級的排序規(guī)則,使得算法只需訪問較少的節(jié)點(diǎn)就能求得運(yùn)動規(guī)劃問題的最優(yōu)解.針對Dijkstra 算法及A* 算法僅適于環(huán)境已知的場景,Stentz 提出的D* 算法[74]可以適用于未知或動態(tài)變化的環(huán)境.D* 算法與A* 算法相反,從目標(biāo)位置開始進(jìn)行搜索,直至搜索到機(jī)器人初始位置為止.D*算法的核心是計(jì)算最優(yōu)路徑的過程狀態(tài)函數(shù)與應(yīng)對環(huán)境信息變化的代價(jià)修正函數(shù).當(dāng)計(jì)算的可行路徑出現(xiàn)新障礙物時(shí),D* 算法僅需處理其附近的節(jié)點(diǎn)并將產(chǎn)生的影響向機(jī)器人所在位置傳播,從而減少重規(guī)劃的計(jì)算量.基于D* 算法,Koenig 等提出的D* Lite 算法提升了運(yùn)動規(guī)劃的尋路效率[75-76],Ferguson 等提出的Field D* 算法能夠不受搜索方向的限制,使規(guī)劃路徑更加平滑[77].

近些年來,基于搜索的運(yùn)動規(guī)劃方法在多機(jī)器人作業(yè)過程中也得到了一定程度的發(fā)展,Ali 等使用A* 算法引入中央處理中心檢查全局路徑規(guī)劃器生成的所有路徑以避免碰撞,中央處理中心分析每個(gè)機(jī)器人的路徑數(shù)據(jù)及對其他機(jī)器人軌跡的影響,得出全局軌跡.當(dāng)機(jī)器人開始向目的地移動時(shí),中央處理中心會實(shí)時(shí)檢查其軌跡是否與其他機(jī)器人沖突,從而達(dá)到多機(jī)協(xié)同避障的目的[78].為了得到多機(jī)器人的高質(zhì)量無碰撞路徑,陳光友等提出一種基于改進(jìn)A* 算法和沖突協(xié)調(diào)策略的多機(jī)器人雙層規(guī)劃算法,在二維路徑基礎(chǔ)上引入時(shí)間維度,建立機(jī)器人路徑時(shí)間圖,預(yù)測機(jī)器人時(shí)間維度的沖突.通過沖突協(xié)調(diào)策略對機(jī)器人與機(jī)器人之間、機(jī)器人與動態(tài)障礙物之間產(chǎn)生的沖突進(jìn)行協(xié)調(diào)[79].Ren 等提出了一種基于多目標(biāo)路徑的D* 算法 (Multi-objective path-based D* lite,MOPBD*),利用基于路徑的擴(kuò)展策略計(jì)算主導(dǎo)解,并引入了MOPBD*的次優(yōu)變體,提高了動態(tài)環(huán)境下的搜索效率[80].為解決多機(jī)器人運(yùn)動規(guī)劃過程中的沖突碰撞及A* 算法尋路效率低的問題,Sharon 等提出了一種基于沖突的搜索算法(Conflict based search,CBS),是一種兩級算法,其中在高層對基于個(gè)體之間的沖突樹執(zhí)行搜索,沖突樹中每一個(gè)節(jié)點(diǎn)代表了一組運(yùn)動過程的約束,在低層執(zhí)行快速的單機(jī)搜索以滿足高層沖突樹節(jié)點(diǎn)施加的約束.通過兩級算法可以使CBS 算法比A* 算法具有更少的計(jì)算量,同時(shí)保持最優(yōu)性[81].但是其對節(jié)點(diǎn)判斷是否發(fā)生沖突時(shí),節(jié)點(diǎn)的分裂和重新規(guī)劃耗費(fèi)大量時(shí)間,Zhang 等提出了一種基于沖突的并行搜索算法,設(shè)計(jì)了與人腦、眼、腿對應(yīng)的全局路徑規(guī)劃、傳感器級路徑規(guī)劃和動作級路徑規(guī)劃,加快節(jié)點(diǎn)的展開速度[82].為完成順序裝配操作的多機(jī)器人抓取規(guī)劃,Dogar 等使用沖突搜索算法,將搜索表述為約束滿足問題(Constraint satisfaction problem,CSP),將CSP 劃分為獨(dú)立的較小問題以指數(shù)級的速度進(jìn)行解決[83].

如圖14 所示,基于搜索的運(yùn)動規(guī)劃方法的尋路效率依賴于環(huán)境地圖網(wǎng)格的劃分,但網(wǎng)格越多算法所需訪問的節(jié)點(diǎn)越多,算法尋路效率越低.基于搜索的運(yùn)動規(guī)劃方法的計(jì)算復(fù)雜度與運(yùn)動規(guī)劃問題所在空間維度呈指數(shù)相關(guān),因此,該類方法僅適用于低維空間的運(yùn)動規(guī)劃問題.

圖14 基于搜索的運(yùn)動規(guī)劃[78-82]Fig.14 Search-based motion planning[78-82]

2.1.2 基于勢場的規(guī)劃算法

基于勢場的運(yùn)動規(guī)劃方法通過構(gòu)建勢函數(shù)引導(dǎo)算法搜索可行路徑,無需對環(huán)境信息進(jìn)行精確探索.最早基于勢場的規(guī)劃算法可以追溯到1985 年Khatib 提出的人工勢場法,機(jī)器人在空間環(huán)境中的運(yùn)動受到虛擬人工力場的作用,目標(biāo)位置對機(jī)器人產(chǎn)生引力作用,障礙物對機(jī)器人產(chǎn)生斥力作用,在引力和斥力的共同作用下通過算法控制機(jī)器人的運(yùn)動從而到達(dá)目標(biāo)位置.

Liu 等提出一種與虛擬障礙物概念相結(jié)合[84]的勢場法,該算法通過計(jì)算中途點(diǎn)作為臨時(shí)目標(biāo)點(diǎn),以克服傳統(tǒng)人工勢場法容易陷入局部最優(yōu)的問題.石鴻雁等將混沌優(yōu)化算法與人工勢場法相結(jié)合,提出混沌人工勢場法,使機(jī)器人在動態(tài)環(huán)境中實(shí)時(shí)避障的同時(shí)不陷入局部最優(yōu)解,在距離較近但不相連的障礙物之間找到可行路徑[85].Scott 等提出一種新型勢函數(shù)形式[86],此勢函數(shù)包括用于避免關(guān)節(jié)限制的彈性勢、引導(dǎo)機(jī)械臂遠(yuǎn)離障礙物的排斥勢及防止機(jī)械臂陷入奇異狀態(tài)的位形勢,三個(gè)分量聯(lián)合建立機(jī)械臂避障的勢函數(shù),在此基礎(chǔ)上將相機(jī)視線遮擋部分視為虛擬障礙物,有效降低了機(jī)械臂在動態(tài)環(huán)境中因相機(jī)遮擋而導(dǎo)致的碰撞問題.Lee 等提出了一種NP-APF (New point-artificial potential field)運(yùn)動規(guī)劃算法[87],在機(jī)器人遇到障礙物時(shí)該算法首先選取一個(gè)合適的位置生成對機(jī)器人的吸引力,然后根據(jù)選取的位置優(yōu)化機(jī)器人所受合力的大小和方向,幫助機(jī)器人快速擺脫障礙物的約束,提高傳統(tǒng)人工勢場算法的規(guī)劃能力.韓偉等提出一種與模糊決策相結(jié)合的人工勢場法,可以自適應(yīng)調(diào)整機(jī)器人在虛擬人工勢場中所受到的合力大小和方向[88].Mamani 等將勢場法應(yīng)用在多移動差速式機(jī)器人中,提出了編隊(duì)控制要求清單,在此基礎(chǔ)上建立了基于勢場法的多機(jī)器人編隊(duì)控制模型[89].為完成從初始位置到目標(biāo)點(diǎn)的最佳路徑規(guī)劃,Pan 等提出了一種改進(jìn)人工勢函數(shù)的多機(jī)器人路徑規(guī)劃方法,通過引入旋轉(zhuǎn)勢場,可以使機(jī)器人有效逃離公共最小值和振蕩[90].Matoui 等使用改進(jìn)人工勢場方法,使用非最小速度算法處理最小局部問題,并且通過機(jī)器人之間的優(yōu)先級分配方法,解決了機(jī)器人在同一點(diǎn)通過的交叉問題.其次使用鄰域檢測技術(shù)來減少每個(gè)機(jī)器人的影響區(qū)域并優(yōu)化規(guī)劃計(jì)算時(shí)間[91].Wu等引入增益約束和隨機(jī)因子來改進(jìn)人工勢場法,抑制路徑振蕩同時(shí)避免局部最小值,并采用B 樣條曲線優(yōu)化對規(guī)劃路徑進(jìn)行平滑處理[92].

如圖15 所示,人工勢場法僅需計(jì)算機(jī)器人受到的合力大小和方向,減少了運(yùn)動規(guī)劃問題求解過程中產(chǎn)生的計(jì)算量.但該方法容易陷入局部最優(yōu)解及無法找到可行解,且基于勢場的運(yùn)動規(guī)劃方法仍面臨著最優(yōu)性與高維空間可拓展性之間的矛盾,僅適用于簡單二維平面環(huán)境中的運(yùn)動規(guī)劃問題.

圖15 基于人工勢場法的運(yùn)動規(guī)劃[88,91]Fig.15 Motion planning based on artificial potential field[88,91]

2.1.3 基于采樣的規(guī)劃算法

基于采樣的運(yùn)動規(guī)劃方法因其在多維空間中具有的顯著優(yōu)勢在運(yùn)動規(guī)劃領(lǐng)域得到了廣泛的關(guān)注[93],目前基于采樣的運(yùn)動規(guī)劃方法主要分為基于隨機(jī)搜索 (Probabilistic road maps,PRM) 算法的改進(jìn)型和基于快速探索隨機(jī)樹 (Rapidly-exploring random trees,RRT) 算法的改進(jìn)型等.

1996 年Kavraki 等提出的PRM 算法[94]被認(rèn)為是當(dāng)時(shí)最成功的解決高維空間復(fù)雜運(yùn)動規(guī)劃問題的方法,該算法的復(fù)雜度首先與尋找可行路徑的難易有關(guān),其次是空間大小和維度的影響.PRM 算法分為采樣和查詢兩個(gè)步驟,采樣過程通過在自由環(huán)境中進(jìn)行隨機(jī)均勻采樣,為每個(gè)采樣點(diǎn)搜索鄰居節(jié)點(diǎn),在此基礎(chǔ)上建立無碰撞連接概率路線圖,查詢過程通過使用搜索算法從路線圖中找到一條可行路徑.1998 年LaValle 等提出的RRT 算法是一種樹狀結(jié)構(gòu)的隨機(jī)采樣方法[95],該算法以運(yùn)動規(guī)劃問題的起始位置作為根節(jié)點(diǎn),通過隨機(jī)采樣增加節(jié)點(diǎn)分支,在自由環(huán)境中生成隨機(jī)搜索樹,當(dāng)隨機(jī)搜索樹分支拓展至目標(biāo)位置即可獲得從起始位置到目標(biāo)位置的運(yùn)動路徑.基于RRT 算法,王樂樂等提出一種改進(jìn)快速擴(kuò)展隨機(jī)樹的多機(jī)器人編隊(duì)路徑規(guī)劃算法,用于解決多機(jī)器人在復(fù)雜環(huán)境下的編隊(duì)路徑規(guī)劃問題.同時(shí)定義機(jī)器人之間的領(lǐng)航-跟隨結(jié)構(gòu),建立搜索樹擴(kuò)展方向與隊(duì)形方向之間的聯(lián)系解決規(guī)劃過程中編隊(duì)朝向變化問題[96].針對RRT 算法搜索區(qū)域受限、耗時(shí)較長、結(jié)果可行性較差等問題,陳錦濤等提出了一種RRT 森林算法,通過隨機(jī)選取根節(jié)點(diǎn)、生成隨機(jī)樹、連接合并隨機(jī)樹,使高層消防多無人機(jī)在復(fù)雜室內(nèi)環(huán)境下協(xié)同路徑規(guī)劃效率顯著提高.此外,采用兩次動態(tài)規(guī)劃以及改進(jìn)障礙物接近檢測方法,進(jìn)一步提高路徑的可行性[97].RRT 算法傾向于未探索區(qū)域擴(kuò)張,隨著搜索迭代次數(shù)增加,未探索區(qū)域減少,可以得出RRT 算法探索空間能力強(qiáng)、速度快.該算法概率完備且不最優(yōu),可以迅速找到可行路徑.但所尋找路徑通常不是最優(yōu)路徑且包含較多的棱角.

針對RRT 算法所規(guī)劃路徑不是最優(yōu)可行路徑的問題,2011 年Karaman 等在RRT 算法基礎(chǔ)上加入了重新布線函數(shù)和代價(jià)函數(shù),提出了一種RRT*算法[98].該算法改進(jìn)了RRT 算法父節(jié)點(diǎn)選擇方式,在最小代價(jià)函數(shù)值下選擇每一個(gè)節(jié)點(diǎn),因此當(dāng)采樣節(jié)點(diǎn)趨于無窮多時(shí),RRT* 算法計(jì)算的可行路徑必定收斂至最優(yōu)路徑.針對水下機(jī)器人海洋調(diào)查問題,Cui 等提出了一種多維RRT* 路徑規(guī)劃方法,通過最大化標(biāo)量場模型和觀測值之間的信息來確定水下機(jī)器人的采樣位置,以提高采取樣本的質(zhì)量[99].但是,RRT 算法與RRT* 算法都存在碰撞檢測計(jì)算的代價(jià)昂貴問題,將大量的計(jì)算時(shí)間都花費(fèi)在了碰撞檢測中[100-101],特別是在復(fù)雜且障礙物較多的環(huán)境中,算法效率大幅降低.

Janson 等提出的FMT* 算法(Fast marching tree*)[102]結(jié)合了PRM 算法和RRT 算法的優(yōu)點(diǎn),用于解決高維空間中的復(fù)雜運(yùn)動規(guī)劃問題.該算法在結(jié)構(gòu)上減少了大量重復(fù)的碰撞檢測,同時(shí)也減少了求解節(jié)點(diǎn)過程中需要調(diào)整參數(shù)的數(shù)量,FMT* 算法提高了多機(jī)器人收斂到最優(yōu)路徑的速度,同時(shí)減少了計(jì)算量.為了提高效率和可擴(kuò)展性,Le 等基于RRT 算法提出了一種協(xié)調(diào)擴(kuò)展搜索樹方法,首先開發(fā)了一種單機(jī)器人采樣方法跟蹤給定路線,然后設(shè)計(jì)路徑跟隨器確保每一個(gè)機(jī)器人跟隨給定路線同時(shí)避免與其他機(jī)器人相撞,且所提出方法可以解決機(jī)器人增加帶來的高位復(fù)合狀態(tài)空間問題,具有良好的可擴(kuò)展性[103].基于連續(xù)的多機(jī)器人采樣運(yùn)動規(guī)劃過程,Dayan 等通過張量積將多個(gè)機(jī)器人PRM圖構(gòu)建為張量路線圖,以支持在有限時(shí)間內(nèi)保證高質(zhì)量的解[104].

如圖16 所示,近年來PRM 算法和RRT 算法的改進(jìn)型不斷被提出,在機(jī)器人運(yùn)動規(guī)劃領(lǐng)域表現(xiàn)良好,同時(shí)具備避障性、概率完備性等理論支撐.但調(diào)節(jié)算法運(yùn)行時(shí)間與算法最優(yōu)性之間的矛盾、探索盲目性問題是基于采樣的規(guī)劃算法需要解決的問題.

圖16 基于采樣的運(yùn)動規(guī)劃[96,99,102]Fig.16 Motion planning based on sampling[96,99,102]

2.1.4 基于人工智能的規(guī)劃算法

隨著人工智能技術(shù)的發(fā)展,人工智能算法被逐漸應(yīng)用于多機(jī)器人運(yùn)動規(guī)劃問題中[105-106].常見的人工智能運(yùn)動規(guī)劃方法有遺傳算法、蟻群算法、粒子群算法、人工神經(jīng)網(wǎng)絡(luò)算法、機(jī)器學(xué)習(xí)算法等.

1975 年Bhaduri 提出的遺傳算法(Genetic algorithm,GA)[107]是一種模擬大自然生物進(jìn)化過程的最優(yōu)解搜索算法.該算法在運(yùn)動規(guī)劃問題中通過將可行路徑視為個(gè)體,每個(gè)種群包含的可行路徑條數(shù)為個(gè)體數(shù)量,每條可行路徑的路徑點(diǎn)個(gè)數(shù)為個(gè)體中染色體的數(shù)量.在迭代演化的過程中,借助遺傳算子進(jìn)行選擇、基因交叉、基因突變等操作,適應(yīng)度低的種群被淘汰,適應(yīng)度高的種群被保留,“優(yōu)勝劣汰”的競爭使得最終保留下來的路徑為算法尋得的最佳可行路徑.Nazarahari 等提出了一種增強(qiáng)遺傳算法 (Enhanced genetic algorithm,EGA) 來改善連續(xù)空間中的初始路徑,基于省時(shí)的確定性方案尋找可行的初始路徑,并保證找到一個(gè)可行的路徑(如果存在),同時(shí)EGA 算法利用五個(gè)定制的交叉和突變運(yùn)算符來改善初始路徑[108].但遺傳算法具有較高的隨機(jī)性,每次調(diào)用的運(yùn)行結(jié)果都不盡相同,甚至存在不收斂的可能.

1992 年Dorigo 等提出的蟻群算法(Ant colony algorithm,ACA)[109]是一種采用正反饋機(jī)制,模擬螞蟻尋找食物時(shí)根據(jù)同伴分泌的信息素逐漸發(fā)現(xiàn)最短路徑的仿生概率算法,其在搜索過程中不斷收斂直至逼近最優(yōu)可行路徑[110].Hasan 等將蟻群算法與D* 算法結(jié)合,考慮在自由空間中的動態(tài)障礙物,構(gòu)建概率函數(shù)選擇每個(gè)機(jī)器人的最佳路徑達(dá)到動態(tài)避障[111].

1995 年Kennedy 提出的粒子群優(yōu)化算法[112](Particle swarm optimization,PSO)是一種模擬鳥類捕食的優(yōu)化算法.該算法通過鳥類個(gè)體間的信息共享與相互協(xié)作,引領(lǐng)著群體演化至最優(yōu)可行解,粒子群優(yōu)化算法提高了復(fù)雜環(huán)境下最優(yōu)解的發(fā)現(xiàn)率.Wang 等提出了一種由連續(xù)粒子群算法和離散粒子群算法組成的混合粒子群算法,連續(xù)粒子群算法優(yōu)化期望編隊(duì)的中心位置和旋轉(zhuǎn)角度,離散粒子群算法用于優(yōu)化初始位置和目標(biāo)位置之間的匹配關(guān)系[113].針對未知環(huán)境下的多機(jī)器人目標(biāo)搜索問題,Dadgar 等提出一種基于粒子群優(yōu)化的分布式算法,避免陷入局部最優(yōu)[114].

人工神經(jīng)網(wǎng)絡(luò)在多機(jī)器人運(yùn)動規(guī)劃中,通過搭建、訓(xùn)練神經(jīng)網(wǎng)絡(luò)系統(tǒng)以逼近問題中的可行運(yùn)動路徑,并依照環(huán)境約束與機(jī)器人約束的變化不斷優(yōu)化所尋的運(yùn)動路徑[115-116].

2017 年P(guān)feiffer 等提出了一種基于監(jiān)督學(xué)習(xí)的運(yùn)動規(guī)劃方法,根據(jù)激光測距結(jié)果建立相對目標(biāo)位置的卷積神經(jīng)網(wǎng)絡(luò)(Convolutional neural networks,CNN)模型[117],但監(jiān)督學(xué)習(xí)的框架依賴于標(biāo)記的算法,對環(huán)境變化的泛化能力弱.強(qiáng)化學(xué)習(xí)通過代價(jià)迭代方式建立表格,用于存儲狀態(tài)到動作過程的映射,根據(jù)表格信息引導(dǎo)多機(jī)器人運(yùn)動到目標(biāo)位置.面對碰撞避免和輸入約束影響的在線多機(jī)器人時(shí)間最優(yōu)路徑規(guī)劃問題,He 等將人工勢場納入近似成本函數(shù)中,提出了一種積分強(qiáng)化學(xué)習(xí)方法,將具有輸入約束的有限視界最小時(shí)間能量問題轉(zhuǎn)換為近似無限視界最優(yōu)控制問題[118].但在障礙物信息變化的環(huán)境中需生成大量表格,耗費(fèi)內(nèi)存空間.Tai等將深度強(qiáng)化學(xué)習(xí)應(yīng)用于運(yùn)動規(guī)劃問題中,只需指定運(yùn)動規(guī)劃的目標(biāo),使其在仿真規(guī)劃場景中大量嘗試,不斷進(jìn)行學(xué)習(xí),根據(jù)獲得的獎(jiǎng)勵(lì)及懲罰自主迭代更新網(wǎng)絡(luò),從而求解出較好的可行路徑[119].針對傳統(tǒng)方法難以將其他移動機(jī)器人識別為障礙物或協(xié)作機(jī)器人的問題,Bae 等結(jié)合了CNN 網(wǎng)絡(luò)和深度強(qiáng)化學(xué)習(xí)算法,其中CNN 網(wǎng)絡(luò)使用環(huán)境的圖像信息分析確切的情況,同時(shí)機(jī)器人根據(jù)通過深度強(qiáng)化學(xué)習(xí)分析的情況進(jìn)行規(guī)劃[120].為解決鈑金鉆孔過程運(yùn)動規(guī)劃問題,Veeramani 等將最優(yōu)路徑識別問題建模為一個(gè)馬爾可夫決策問題,選擇了一種無模型的狀態(tài)-動作-獎(jiǎng)勵(lì)-狀態(tài)-動作策略時(shí)間差規(guī)劃算法,并基于路徑規(guī)劃問題的參數(shù)進(jìn)行了描述[121].

如圖17 所示,基于人工智能的運(yùn)動規(guī)劃方法通?？梢詫さ眠\(yùn)動規(guī)劃問題中的較優(yōu)解,但求解過程需花費(fèi)較多時(shí)間,效率較低.

圖17 基于人工智能的運(yùn)動規(guī)劃[108,114,120]Fig.17 Artificial intelligence-based motion planning[108,114,120]

2.1.5 基于混合算法的運(yùn)動規(guī)劃

有效地結(jié)合兩種或以上規(guī)劃算法,可以很大程度上提高計(jì)算效率.如圖18 所示,為完成多機(jī)器人點(diǎn)焊任務(wù),Pellegrinelli 等結(jié)合沖突搜索算法與市場法,為每個(gè)機(jī)器人設(shè)計(jì)無碰撞運(yùn)動路徑減少設(shè)計(jì)時(shí)間和設(shè)計(jì)失誤[122].Hartmann 等將優(yōu)化方法與基于采樣的雙向時(shí)空路徑規(guī)劃器相結(jié)合,共同求解操縱約束,使其能夠規(guī)劃到達(dá)時(shí)間未知的協(xié)作式多機(jī)器人操作[123].為解決柔性物體協(xié)同搬運(yùn)問題,Alonso-Mora 提出了一種混合集中/分布式方法,針對機(jī)械手設(shè)計(jì)低層規(guī)劃器,通過物體相互傳遞力來保持操縱和避免碰撞的保證,基于分布式反演水平規(guī)劃器設(shè)計(jì)局部控制算法,并包含避免碰撞和形狀維護(hù)的約束[124].為完成汽車生產(chǎn)過程中的去毛刺、切割和焊接等任務(wù),Touzani 等首先使用市場法對任務(wù)進(jìn)行排序,然后使用PRM 算法完成自動路徑規(guī)化[125].Han 等結(jié)合路徑多樣化和最優(yōu)子問題策略,提出了一種新的集中解耦算法,解決倉庫環(huán)境的一次性和動態(tài)最優(yōu)多機(jī)器人路徑規(guī)劃問題[126].為完成大規(guī)模自由曲面產(chǎn)品的光學(xué)檢測問題,Liu 等通過機(jī)器人坐標(biāo)空間動態(tài)搜索,考慮沖突機(jī)器人中探頭姿態(tài)或局部路徑的擾動,提出無碰撞路徑規(guī)劃和協(xié)調(diào)運(yùn)動規(guī)劃[127].Rigatos 采用分布式梯度算法和群體智能算法,解決多機(jī)器人協(xié)作自主裝配問題,從解空間中的不同點(diǎn)開始,并在向目標(biāo)位置移動時(shí)相互交互,可以在每個(gè)機(jī)器人的最佳先前移動和其鄰居的最佳先前移動定義的區(qū)域中迭代搜索[128].為完成自動化倉庫設(shè)置,Han 等結(jié)合路徑多樣化和最優(yōu)子問題解決方案數(shù)據(jù)庫,有效地利用整個(gè)工作空間進(jìn)行機(jī)器人旅行,而最佳子問題解決方案數(shù)據(jù)庫有助于快速解決局部路徑?jīng)_突[129].

圖18 基于混合算法的運(yùn)動規(guī)劃[122-129]Fig.18 Motion planning based on hybrid algorithm[122-129]

2.2 復(fù)雜作業(yè)場景下多機(jī)器人運(yùn)動規(guī)劃

面向復(fù)雜作業(yè)環(huán)境下多機(jī)器人協(xié)同加工過程,按照機(jī)器人結(jié)構(gòu)及作業(yè)環(huán)境的不同,主要分為移動端運(yùn)動規(guī)劃、作業(yè)端(末端執(zhí)行器作業(yè))運(yùn)動規(guī)劃.

2.2.1 多機(jī)器人移動端運(yùn)動規(guī)劃

復(fù)雜環(huán)境下高效的全局路徑規(guī)劃及動態(tài)沖突下局部路徑重規(guī)劃是多機(jī)器人移動端安全、穩(wěn)定運(yùn)動的前提.Li 等[130]首先利用增強(qiáng)沖突的搜索算法獲得每個(gè)機(jī)器人的離散路徑,根據(jù)離散路徑構(gòu)建針對靜態(tài)障礙物的安全廊道作為安全性硬約束,然后構(gòu)造涉及軌跡平滑性和多機(jī)間安全性的目標(biāo)函數(shù),利用模型預(yù)測算法進(jìn)行優(yōu)化求解獲得全局可行軌跡.Wagner 等[131]以A* 算法作為底層路徑規(guī)劃器為每個(gè)機(jī)器人單獨(dú)規(guī)劃最優(yōu)路徑,同時(shí)為每個(gè)節(jié)點(diǎn)維護(hù)碰撞集合和反向傳播集合,大大減少了A* 算法擴(kuò)展過程的節(jié)點(diǎn)數(shù).為應(yīng)對機(jī)器人數(shù)量較多時(shí),會出現(xiàn)由于過度避障導(dǎo)致的機(jī)器人抖動問題,Van 等[132]提出交互速度障礙算法為多機(jī)器人提供統(tǒng)一的決策行為,雖然解決了多機(jī)器人相遇時(shí)的抖動問題,但是多機(jī)器人規(guī)模增大時(shí)仍然無法避免碰撞,可擴(kuò)展性低.為改進(jìn)這一缺點(diǎn),Van 等[133]提出最佳相互避碰方法,利用有向平面分割空間將避碰問題轉(zhuǎn)換為線性規(guī)劃問題,提高了計(jì)算效率,并能夠?qū)ζ渌麢C(jī)器人的運(yùn)動進(jìn)行精準(zhǔn)的感知、相互協(xié)作產(chǎn)生無碰撞的運(yùn)動.Tordesillas 等[134]利用最小體積法構(gòu)建當(dāng)前機(jī)器人控制點(diǎn)的最小凸多面體,并且對動態(tài)障礙物或者其他機(jī)器人同樣建立凸多面體,進(jìn)而創(chuàng)建一個(gè)平面對兩種凸多面體進(jìn)行分離,通過將此平面作為安全性硬約束,建立目標(biāo)函數(shù)進(jìn)行求解,獲得無碰撞的軌跡.

如圖19 所示,Zhou 等[135]提出多目標(biāo)時(shí)空軌跡聯(lián)合優(yōu)化方法,構(gòu)建與時(shí)間以及軌跡平滑性相關(guān)的多目標(biāo)優(yōu)化函數(shù),在滿足動力學(xué)約束下求解獲取實(shí)時(shí)軌跡.

圖19 多機(jī)器人移動端運(yùn)動規(guī)劃[135]Fig.19 Motion planning of multi-robot mobile terminals[135]

2.2.2 多機(jī)器人作業(yè)端運(yùn)動規(guī)劃

多機(jī)器人作業(yè)端無干涉協(xié)同運(yùn)動是實(shí)現(xiàn)多機(jī)器人系統(tǒng)安全制造的前提.如圖20 所示,面向制造的機(jī)器人系統(tǒng)通常由移動端與作業(yè)端執(zhí)行器組成,作業(yè)端高自由度、規(guī)劃空間高維以及作業(yè)空間受限等對實(shí)現(xiàn)實(shí)時(shí)安全無干涉協(xié)同運(yùn)動規(guī)劃提出了挑戰(zhàn).Thakar 等[136]考慮到移動機(jī)械臂單元的高非線性、緊耦合性等問題,將其定義為非完整移動機(jī)械臂(Nonholonomic mobile manipulator,NMM),首先根據(jù)機(jī)器人周圍環(huán)境的信息,對機(jī)械手和目標(biāo)點(diǎn)的樣品進(jìn)行協(xié)調(diào)聚焦,其次考慮到NMM 的非全息約束,在兩個(gè)搜索樹之間建立連接的啟發(fā)式方法,從而提高路徑的計(jì)算速度和成功率.Tallamraju 等[137]提出了一種分層自適應(yīng)移動機(jī)械臂規(guī)劃器,對移動單元與作業(yè)單元進(jìn)行單獨(dú)規(guī)劃,并以概率地圖法規(guī)劃框架基礎(chǔ)上通過增加自適應(yīng)采樣策略,提高規(guī)劃效率.Pardi 等[138]考慮到移動作業(yè)機(jī)器人系統(tǒng)的非完整約束與運(yùn)動學(xué)約束,將約束受限下的路徑規(guī)劃表述為多目標(biāo)優(yōu)化問題,將由作業(yè)單元末端執(zhí)行器表面移動距離、可操作性以及移動單元運(yùn)行速度構(gòu)成的代價(jià)函數(shù)嵌入到RRT* 算法中實(shí)現(xiàn)任務(wù)空間下的路徑規(guī)劃.基于多機(jī)器人作業(yè)端協(xié)同搬運(yùn)運(yùn)動規(guī)劃,Tang 等[139]將多機(jī)器人協(xié)同運(yùn)輸系統(tǒng)視作環(huán)境中的一個(gè)虛擬矩形,提出了一種基于系統(tǒng)輪廓矩形變化的避障規(guī)劃方法,通過改變虛擬對象的移動方向和矩形寬度來適應(yīng)環(huán)境變化.面對存在未知軌跡障礙物環(huán)境下對移動機(jī)械臂運(yùn)動規(guī)劃問題,Vannoy 等[140]提出了一種可擴(kuò)展的實(shí)時(shí)自適應(yīng)運(yùn)動規(guī)劃方法,可實(shí)現(xiàn)實(shí)時(shí)同步的路徑和軌跡規(guī)劃,同時(shí)通過機(jī)器人配置變量的松散耦合,利用移動機(jī)械臂的冗余,實(shí)現(xiàn)避障和優(yōu)化目標(biāo).Bonilla 等[141]提出了一種多機(jī)器人作業(yè)端在與環(huán)境以及自身內(nèi)部進(jìn)行位置/力交互時(shí)的運(yùn)動規(guī)劃與控制集成方法.該方法設(shè)計(jì)了一個(gè)非交互式的控制器實(shí)現(xiàn)多機(jī)器人的解耦控制,通過放松幾何約束,采用一個(gè)狹窄的全維邊界層代替低維約束流形來解決受約束的運(yùn)動規(guī)劃問題.

圖20 非完整和任務(wù)約束下作業(yè)端路徑規(guī)劃[136-138]Fig.20 Path planning for operators under non-integrity and task constraints[136-138]

如表2 所示,目前多機(jī)器人運(yùn)動規(guī)劃在制造領(lǐng)域得到了一定的研究進(jìn)展,算法的最優(yōu)性、魯棒性及避碰、避障能力有了顯著的提升.但在復(fù)雜環(huán)境下、狹小空間下的解空間計(jì)算復(fù)雜性、尋路效率還有待提高,對目標(biāo)函數(shù)、人工智能算法的獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)還需要進(jìn)一步的研究.

表2 運(yùn)動規(guī)劃方法分析Table 2 The analysis of motion planning

3 展望

隨著重大裝備大型復(fù)雜部件制造的不斷發(fā)展,多機(jī)器人系統(tǒng)的應(yīng)用和研究為制造過程的效率和精度提供了重要的保障.但是針對復(fù)雜作業(yè)環(huán)境下多任務(wù)、多工序的作業(yè)需求,多機(jī)器人缺乏可擴(kuò)展性、任務(wù)協(xié)調(diào)性.集群機(jī)器人具有高柔性、智能化、可擴(kuò)展性、靈活性等優(yōu)勢,為大型復(fù)雜部件制造提供了新思路.在過去的一些算法研究中,集群機(jī)器人任務(wù)分配與運(yùn)動規(guī)劃已有部分進(jìn)展.Yang 等基于蟻群算法與響應(yīng)閾值模型,完成集群機(jī)器人任務(wù)分配,體現(xiàn)分布式算法的可擴(kuò)展性[142].Ghassemi 等考慮任務(wù)截止日期與機(jī)器人范圍和任務(wù)完成能力限制,并允許在動態(tài)任務(wù)空間下進(jìn)行異步?jīng)Q策,為不同的實(shí)際應(yīng)用(例如災(zāi)難響應(yīng)) 提供重要的解決方案[143].Vicmudo 等基于遺傳算法為每個(gè)機(jī)器人生成最短路徑,使其到達(dá)目標(biāo)點(diǎn)而集群機(jī)器人之間不會相互碰撞,通過仿真驗(yàn)證安全無碰撞路徑的有效性[144].Chella 等改進(jìn)蟻群算法,為集群機(jī)器人提出了一種基于量子的路徑規(guī)劃算法,量化輸入位置和獎(jiǎng)勵(lì)信息 (以機(jī)器人與目標(biāo)的接近程度來衡量) 和路徑規(guī)劃決策[145].但上述方法僅僅在仿真環(huán)境下驗(yàn)證,且使用局域網(wǎng)進(jìn)行算法設(shè)計(jì)很大程度上限制了集群機(jī)器人工作空間,同時(shí)通信過程中產(chǎn)生的時(shí)延、噪聲以及網(wǎng)絡(luò)波動影響了分配和規(guī)劃的效率與準(zhǔn)確性.因此復(fù)雜環(huán)境制造場景,如何將多機(jī)器人任務(wù)分配與運(yùn)動規(guī)劃算法應(yīng)用在集群機(jī)器人中,體現(xiàn)可擴(kuò)展性,在此基礎(chǔ)上向網(wǎng)絡(luò)化、智能化延伸,即云-邊-端網(wǎng)絡(luò)協(xié)同下的集群機(jī)器人任務(wù)分配與運(yùn)動規(guī)劃,為亟待解決的難題.盡管目前已有許多研究學(xué)者對集群機(jī)器人進(jìn)行了探索,結(jié)合表1 和表2 的分析,在大型復(fù)雜部件作業(yè)場景中仍然存在一部分問題亟待解決:

1) 制造環(huán)境的復(fù)雜性: 在大型復(fù)雜部件制造領(lǐng)域,部件具有尺寸大、剛度低、制造精度高、結(jié)構(gòu)復(fù)雜等特點(diǎn),生產(chǎn)環(huán)境往往復(fù)雜多變,從而引起集群機(jī)器人全局任務(wù)分配與運(yùn)動規(guī)劃困難.現(xiàn)有的方法在復(fù)雜場景下尋路效率低、隨機(jī)性高、成本函數(shù)設(shè)計(jì)復(fù)雜,因此探索大規(guī)模復(fù)雜環(huán)境下任務(wù)分配和運(yùn)動規(guī)劃方法是未來的研究方向之一.

2) 難以兼顧全局和局部: 復(fù)雜制造環(huán)境下僅采用某一種算法難以兼顧全局最優(yōu)性,若采用局部規(guī)劃分配算法將極大增加任務(wù)的復(fù)雜性.而兩種及以上的方法有效地結(jié)合可以滿足全局和局部的優(yōu)勢,因此在采用全局方法進(jìn)行任務(wù)分配規(guī)劃的基礎(chǔ)上結(jié)合局部規(guī)劃方法對部分復(fù)雜場景進(jìn)行實(shí)時(shí)動態(tài)規(guī)劃是未來研究方向之一.

3) 通信約束強(qiáng): 網(wǎng)絡(luò)化集群機(jī)器人制造過程中容易出現(xiàn)通信的不確定性,而當(dāng)前的部分方法如啟發(fā)式算法、A* 算法等對通信準(zhǔn)確程度具有較強(qiáng)的依賴性,且深度學(xué)習(xí)算法需要通過云服務(wù)器進(jìn)行大量的數(shù)據(jù)計(jì)算.因此需要對動態(tài)任務(wù)分配規(guī)劃技術(shù)進(jìn)行改進(jìn),以實(shí)現(xiàn)在部分時(shí)間段弱通信或通信受限場景下的魯棒性.

4) 沖突干涉問題: 復(fù)雜動態(tài)環(huán)境下集群機(jī)器人與動態(tài)障礙物以及集群機(jī)器人之間的相互移動都會影響全局運(yùn)動規(guī)劃過程,容易引起沖突干涉,因此亟待尋求解決高動態(tài)環(huán)境下沖突預(yù)測與動態(tài)避障方法.

5) 受限空間問題: 復(fù)雜場景下機(jī)器人作業(yè)端存在運(yùn)動空間狹小、規(guī)劃空間維度高、約束條件多等問題,因此進(jìn)行狹小空間下集群機(jī)器人無干涉協(xié)同運(yùn)動規(guī)劃方法設(shè)計(jì)是未來的研究方向之一.

如圖21 所示,與其他方法相比較,基于學(xué)習(xí)的方法具有強(qiáng)大的學(xué)習(xí)能力、高魯棒性、高適應(yīng)性等優(yōu)點(diǎn),結(jié)合現(xiàn)階段研究現(xiàn)狀及復(fù)雜制造場景下現(xiàn)階段亟待解決的問題,提出一種基于云-邊-端協(xié)同的任務(wù)分配與運(yùn)動規(guī)劃構(gòu)想.首先提出基于云邊協(xié)同的集群機(jī)器人高動態(tài)實(shí)時(shí)任務(wù)分配方法,采用整數(shù)線性規(guī)劃方法進(jìn)行智能化區(qū)域劃分與資源分配,并使用分層強(qiáng)化學(xué)習(xí)方法進(jìn)行區(qū)域內(nèi)任務(wù)分配,基于云邊協(xié)同進(jìn)行啟發(fā)式跨區(qū)域任務(wù)分配.然后提出邊端協(xié)同下移動端實(shí)時(shí)沖突預(yù)測與運(yùn)動規(guī)劃方法,使用基于知識復(fù)用方法進(jìn)行高效無沖突全局路徑規(guī)劃,針對高動態(tài)環(huán)境下沖突干涉問題,采用基于行為預(yù)測的局部運(yùn)動規(guī)劃方法.面向作業(yè)空間受限問題,提出集群機(jī)器人作業(yè)端無沖突協(xié)同運(yùn)動規(guī)劃,構(gòu)建末端執(zhí)行器自適應(yīng)安全域,并提出基于隨機(jī)采樣的實(shí)時(shí)避障軌跡規(guī)劃,提高動態(tài)環(huán)境的適應(yīng)能力.

圖21 復(fù)雜環(huán)境下集群機(jī)器人任務(wù)分配與運(yùn)動規(guī)劃技術(shù)路線Fig.21 Technical route of task allocation and motion planning for cluster robots in complex environment

4 結(jié)論

重大裝備大型復(fù)雜部件具有尺寸超大、工序繁多、型面復(fù)雜等特點(diǎn),其制造過程場景規(guī)模大、任務(wù)工序多、精度需求高,作業(yè)場景復(fù)雜.傳統(tǒng)的人工、單機(jī)制造面臨著效率低、柔性不足、一致性差、空間有限等問題,難以保障大型復(fù)雜部件制造的需求.多機(jī)器人具有高適應(yīng)性、高柔順性等優(yōu)點(diǎn),為大型復(fù)雜部件提供了良好的制造基礎(chǔ).先進(jìn)的任務(wù)分配和軌跡規(guī)劃方法是多機(jī)器人制造系統(tǒng)的決策中樞,其性能影響整個(gè)系統(tǒng)的運(yùn)行效率.

本文針對任務(wù)分配過程對線性規(guī)劃方法、基于市場的方法、啟發(fā)式算法及深度強(qiáng)化學(xué)習(xí)算法進(jìn)行了分析,同時(shí)針對運(yùn)動規(guī)劃對基于搜索的規(guī)劃方法、基于勢場的規(guī)劃方法、基于采樣的規(guī)劃方法及人工智能規(guī)劃方法進(jìn)行了描述.在此基礎(chǔ)上對算法產(chǎn)生的計(jì)算時(shí)間問題、可行解問題、維度問題及通信的魯棒性問題進(jìn)行了總結(jié).結(jié)合重大裝備制造復(fù)雜作業(yè)環(huán)境,對現(xiàn)有的方法存在的問題進(jìn)行了總結(jié),與其他方法相比較,基于學(xué)習(xí)的方法具有強(qiáng)大的學(xué)習(xí)能力、高魯棒性、高適應(yīng)性等優(yōu)點(diǎn),因此結(jié)合深度強(qiáng)化學(xué)習(xí)為基礎(chǔ)的混合算法提出了一種復(fù)雜場景下集群機(jī)器人協(xié)同制造的思路.綜上所述,結(jié)合深度強(qiáng)化學(xué)習(xí)與其他算法的混合分配規(guī)劃方法并應(yīng)用于集群機(jī)器人重大裝備制造中是未來的主要研究方向.