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

(北京物資學院 北京 101149)

引言

近年來隨著電子商務和物聯(lián)網(wǎng)技術的快速發(fā)展，使得物流業(yè)變得越來越智能化。與此同時，由于電商平臺企業(yè)的物流業(yè)務呈現(xiàn)出多品類、高頻次、小批量的特點，京東、亞馬遜等電商企業(yè)將智能化的移動機器人投入到倉儲作業(yè)的運營中，用來提升揀選效率，降低揀選成本。然而如何對多個移動機器人進行路徑規(guī)劃，實現(xiàn)作業(yè)的高效協(xié)同是目前亟待解決的問題[1]。

一、多移動機器人路徑規(guī)劃問題

路徑規(guī)劃問題[2]簡言之就是讓機器人遵照某種性能指標(例如距離，時間等)作出從初始環(huán)境到達目標環(huán)境的最優(yōu)的路徑。路徑規(guī)劃的結果評價標準體現(xiàn)在三個方面：機器人可執(zhí)行路線是否存在；遇到?jīng)_突時，機器人是否能夠完成無碰撞路徑；機器人執(zhí)行的路徑是否為最優(yōu)路徑。

多移動機器人路徑規(guī)劃問題(Multi-Robot Path Finding，MRPF)是指，在同時存在靜態(tài)和動態(tài)障礙物的工作空間中，為每臺機器人都規(guī)劃出一條從起點到目標點的最優(yōu)路徑，令所有機器人的完成任務時間最短。同時還要保證機器人與障礙物之間、機器人與機器人之間不發(fā)生碰撞。

二、多移動機器人路徑規(guī)劃方法研究

目前國內外相關學者對多移動機器人路徑規(guī)劃方法進行了許多相關的研究，主要可以分為三類：解耦的MRPF方法、耦合的MRPF方法、基于強化學習的MRPF方法。

(一)基于解耦的多移動機器人路徑規(guī)劃方法

基于解耦的多機器人路徑規(guī)劃方法主要步驟分為兩個階段：第一階段，為每個機器人計算一條無碰撞路徑，不考慮環(huán)境中其它機器人的運動，可以使用單機器人路徑規(guī)劃算法，如Dijistra算法、A*算法或智能優(yōu)化算法等；第二階段，利用交通規(guī)則解決移動機器人間的沖突問題。

基于解耦的多移動機器人路徑規(guī)劃方法的優(yōu)點是：計算復雜性低、魯棒性好。其缺陷在于當場景中機器人數(shù)量較大時，極易產(chǎn)生沖突和擁堵，造成復雜的路徑再規(guī)劃問題。

相關的研究有：Khorshid[3]等針對解耦算法無法保證最優(yōu)解及完備解方面，提出了一種樹搜索GTD(Graph-to-Tree Decompositon)算法以保證解的完備。沈博聞[4]在其研究中將物流機器人所承擔的物流任務進行分解后，考慮其路徑代價與時間代價的基礎上修正A*算法，實現(xiàn)特殊環(huán)境特殊道路規(guī)則約束下的倉儲機器人路徑規(guī)劃。

(二)基于耦合的多機器人路徑規(guī)劃方法

基于耦合的多機器人路徑規(guī)劃即在有限時間步內，每一個機器人搜索一條與其它機器人無沖突路徑，且需要保證所有機器人路徑代價之和最小。其多將路網(wǎng)抽象為圖結構，能夠實現(xiàn)移動機器人間的“緊密協(xié)調和最優(yōu)協(xié)調”，規(guī)劃的路徑通常是最優(yōu)(次優(yōu))及完備的解。

基于耦合的多移動機器人路徑規(guī)劃優(yōu)點是：能夠保障找到最優(yōu)解(次優(yōu)解)或完備解，且當存在較多的機器人時，其路徑規(guī)劃已經(jīng)考慮多機器人之間的無沖突問題，避免了復雜的路徑再次規(guī)劃問題。缺點是當隨著機器人數(shù)量的增加，機器人運動的狀態(tài)空間復雜度呈指數(shù)級增長，其解的復雜程度較高，難以滿足實時應用需要。

相關的研究有：Sharon[5]提出了一種基于CBS(Conflict-Based Search)算法,采用了兩階段搜索算法以降低算法復雜性，CBS算法類似多數(shù)耦合方法，能夠保證最優(yōu)解，與其它耦合算法進行比較，CBS算法針對狹窄空間應用效果較好。泰應鵬[6]提出一種基于時間窗模型的動態(tài)路徑規(guī)劃方法，以實現(xiàn)多AGV的動態(tài)路徑規(guī)劃。通過對時間窗的排布和更新解決了多AGV在路徑規(guī)劃中的碰撞沖突問題，并通過動態(tài)更改道路權重,重新對路徑進行規(guī)劃,實現(xiàn)了實時避障。

(三)基于強化學習的多移動機器人路徑規(guī)劃方法

強化學習中的Q-Learning算法因無需環(huán)境的先驗知識，并且不依賴于模型直接利用與環(huán)境交互獲得的數(shù)據(jù)改善自身的行為，該算法更具有通用性，逐漸成為路徑規(guī)劃領域的重要研究熱點。強化學習的目標是要通過獎賞與懲罰來對當前的問題得到一個最好的解決策略，對好的策略進行獎賞，對壞的策略進行懲罰，不斷的強化這個過程，最終得到一個最好的策略。

基于強化學習的多移動機器人路徑規(guī)劃優(yōu)點是：不需要精確的環(huán)境模型，具有較好的魯棒性；具有強大的自適應性與學習能力。缺點是該方法中的某些算法更適合用來解決中等規(guī)模的強化學習問題，例如Q-Learning算法。因此需要根據(jù)實際情況來選擇合適的算法。

相關的研究有：鄭延斌等[7]提出了一種基于分層強化學習及人工勢場的多Agent路徑規(guī)劃算法，首先將多Agent的運行環(huán)境虛擬為一個人工勢能場，根據(jù)先驗知識確定每點的勢能值，它代表最優(yōu)策略可獲得的最大回報，其次利用分層強化學習方法的無環(huán)境模型學習進行策略更新。王毅然等[8]以復雜任務下多個智能體路徑規(guī)劃問題為研究對象，提出一種基于強化學習的多Agent路徑規(guī)劃方法。該方法采用無模型的在線Q學習算法，多個Agent不斷重復“探索-學習-利用”過程，積累歷史經(jīng)驗評估動作策略并優(yōu)化決策，完成未知環(huán)境下的多Agent的路徑規(guī)劃任務。

(四)展望

本文對多移動機器人路徑規(guī)劃方法進行了總結，列舉了三種方法的國內外研究文獻，分析了各自的優(yōu)缺點，基于以上分析可以發(fā)現(xiàn)，基于強化學習的多移動機器人路徑規(guī)劃研究方法因具有較好的魯棒性、強大的自適應性與學習能力，更可能被廣泛的應用，與此同時，將深度學習和強化學習結合進行多機器人路徑規(guī)劃研究已成為新的發(fā)展趨勢。

三、小結

本文首先對路徑規(guī)劃問題以及多移動機器人路徑規(guī)劃問題進行簡要說明，接著總結了多移動機器人路徑規(guī)劃方法，主要分為基于解耦的MRPF方法和基于耦合的MRPF方法，以及基于強化學習的MRPF方法，對其優(yōu)缺點以及相關研究進行介紹，最后對多移動機器人路徑規(guī)劃研究提出展望。