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

(北京物資學(xué)院 北京 101149)

引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(三)基于強(qiáng)化學(xué)習(xí)的多移動機(jī)器人路徑規(guī)劃方法

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

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

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

(四)展望

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

三、小結(jié)

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