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

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

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

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

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

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

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

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

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

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

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

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

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

1 多機器人任務分配方法研究

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

圖3 多機器人任務分配問題Fig.3 Task allocation problem of multi-robot

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

1.1.1 集中式任務分配

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

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

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

1.1.2 分布式任務分配

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

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

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

1.2 多機器人任務分配方法

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

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

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

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

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

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

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

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

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

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

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

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

1.2.3 基于市場的任務分配方法

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

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

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

1.2.4 基于學習的任務分配方法

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

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

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

圖8 基于學習的任務分配方法[46-49]Fig.8 Task allocation method based on learning[46-49]

1.2.5 混合式任務分配算法

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

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

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

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

1.3 復雜制造場景下多機器人任務分配

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

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

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

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

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

1.3.2 基于復雜場景制造的任務分配方法

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

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

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

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

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

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

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

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

表1 任務分配方法分析Table 1 The analysis of task allocation

2 多機器人運動規(guī)劃

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

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

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

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

2.1 多機器人運動規(guī)劃方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如圖17 所示,基于人工智能的運動規(guī)劃方法通常可以尋得運動規(guī)劃問題中的較優(yōu)解,但求解過程需花費較多時間,效率較低.

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

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

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

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

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

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

2.2.1 多機器人移動端運動規(guī)劃

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

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

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

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

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

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

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

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

3 展望

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

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

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

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

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

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

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

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

4 結論

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

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