重大裝備制造多機器人任務分配與運動規劃技術研究綜述

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

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

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

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

多機器人系統是機器人技術最廣泛的研究領域之一,相比于數控機床與單機器人,多機器人系統具有高效、靈活、魯棒性強、并行協調作業能力強等優點,能夠適應復雜的制造環境[3]:

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

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

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

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

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

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

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

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

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

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

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

1.1 任務分配執行模式

1.1.1 集中式任務分配

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

圖4 集中式任務分配系統Fig.4 Centralized task allocation system

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

1.1.2 分布式任務分配

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

圖5 分布式任務分配系統Fig.5 Distributed task allocation system

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

1.2 多機器人任務分配方法

1.2.1 基于線性規劃的任務分配方法

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

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

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

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

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

1.2.2 基于啟發式的任務分配方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.5 混合式任務分配算法

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

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

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

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

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

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

1.3.1 作業場景區域劃分方法

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

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

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

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

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

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

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

1.3.3 跨區域任務分配方法

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

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

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

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

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

2 多機器人運動規劃

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

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

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

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

2.1 多機器人運動規劃方法

2.1.1 基于搜索的規劃算法

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

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

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

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

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

2.1.2 基于勢場的規劃算法

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

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

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

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

2.1.3 基于采樣的規劃算法

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

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

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

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

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

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

2.1.4 基于人工智能的規劃算法

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

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

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

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

人工神經網絡在多機器人運動規劃中,通過搭建、訓練神經網絡系統以逼近問題中的可行運動路徑,并依照環境約束與機器人約束的變化不斷優化所尋的運動路徑[115-116].

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

如圖17 所示,基于人工智能的運動規劃方法通?？梢詫さ眠\動規劃問題中的較優解,但求解過程需花費較多時間,效率較低.

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

2.1.5 基于混合算法的運動規劃

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

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

2.2 復雜作業場景下多機器人運動規劃

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

2.2.1 多機器人移動端運動規劃

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

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

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

2.2.2 多機器人作業端運動規劃

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

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

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

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

3 展望

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

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

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

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

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

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

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

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

4 結論

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

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