張延年,吳 昊,張 云

(南京交通職業(yè)技術(shù)學(xué)院電子信息工程學(xué)院,南京 211188)

0 引言

因自動化程度高、柔性強等,移動機器人已在工業(yè)、農(nóng)業(yè)、醫(yī)療業(yè)等領(lǐng)域廣泛應(yīng)用。例如,在工廠,移動機器人能夠自動地搬運物料[1],其已成為智能制造車間的主要運載工具。如何使移動機器人有序移動,并快速地完成任務(wù)是當(dāng)前移動機器人領(lǐng)域的核心問題之一。而規(guī)劃移動機器人的路徑是解決該問題的關(guān)鍵因素。

在基于移動機器人的應(yīng)用中,移動機器人需要完成特定任務(wù)[2-3]。這些任務(wù)分布在特定的位置上,本文將這些位置稱為任務(wù)點。由于移動機器人有一定的視覺或者感測能力,其可能需要移動至特定的位置點(以下簡稱服務(wù)點),才能使這些任務(wù)點在其感測范圍內(nèi),進(jìn)而才能完成這些任務(wù)。因此,移動機器人的路徑是由這些服務(wù)點構(gòu)成。移動機器人通過遍歷至每個服務(wù)點,使任務(wù)點在其覆蓋范圍內(nèi),進(jìn)而完成預(yù)定的任務(wù)。

然而,在給定任務(wù)點的前提下,建立服務(wù)點,進(jìn)而規(guī)劃路徑是一項挑戰(zhàn)性工作。規(guī)劃路徑時必須要考慮到路徑長度。路徑長度直接影響了移動機器人完成任務(wù)的時間,即工作效率問題。因此,路徑規(guī)劃問題成為移動機器人領(lǐng)域的研究熱點,促使了研究人員對其深入研究。解瑞云等[4]提出基于多策略改進(jìn)鼠群算法的路徑規(guī)劃算法,其利用改進(jìn)的鼠群優(yōu)化算法求解最短路徑。

除了考慮路徑長度外,規(guī)劃路徑時還需考慮移動機器人的能效問題[5]。在真實應(yīng)用環(huán)境中,多數(shù)移動機器人是依電池供電工作。移動機器人移動一定距離后,需充電,否則無法工作。因此,如果路徑中兩個服務(wù)點間距離超過續(xù)航距離,則移動機器人必須充電后才能完成下一個任務(wù)。而現(xiàn)有的多數(shù)文獻(xiàn)在規(guī)劃移動機器人路徑時,并沒有考慮到移動機器人的充電問題,也沒有考慮充電站的位置。

為了彌補上述不足,提出基于任務(wù)點全覆蓋的能效路徑規(guī)劃(full coverage of mission location-based energy efficiency path planning,FCPP)算法。FCPP算法在規(guī)劃移動機器人路徑時不僅考慮路徑長度,還考慮了充電站位置,使機器人能快速地完成各任務(wù)。仿真結(jié)果表明,提出的FCPP算法縮短了路徑,減少了移動機器人完成工作的時間。

1 系統(tǒng)模型及問題概述

1.1 系統(tǒng)模型

在方形環(huán)境區(qū)域Θ=×內(nèi)部署n個任務(wù)點,它們構(gòu)成任務(wù)集K={pi|1≤i≤n}。以圖1為例,圖1中的紅色方形表示任務(wù)點。移動機器人裝備了傳感器,其感測半徑r。移動機器人依據(jù)特定路線服務(wù)這些任務(wù)點。如果某個任務(wù)點在移動機器人當(dāng)前位置的感測范圍內(nèi),移動機器人就在當(dāng)前位置為執(zhí)行該任務(wù)[6]。此外,某些任務(wù)點可能有多次被移動機器人服務(wù)的機會。

圖1 系統(tǒng)模型

考慮到真實的應(yīng)用場景,移動機器人需在特定的位置開始(始點)移動,為n個任務(wù)點服務(wù)后,又返回至始點。因此,移動機器人的每條路徑都是首尾相接的閉合曲線。用s表示始點,以圖1為例。圖1中黑顏色的折線表示移動機器人的路徑,其從s開始,至s結(jié)束。

移動機器人由電池供電。每次充滿電后,續(xù)航距離為B。因此,移動機器人完成移動了距離B后,需移動至充電站充電。據(jù)此,假定在區(qū)域內(nèi)存在k個充電站,它們充電站集C={ci|1≤i≤k}。圖1標(biāo)記“×”表示充電站。移動機器人依據(jù)其充電需要,可以反復(fù)、多次充電。此外,本文不考慮移動機器人的充電時間。

為了服務(wù)這些任務(wù)點,移動機器人需要移動到多個特定的位置點。將這些點稱為服務(wù)點。每條路徑都遍歷這些服務(wù)點。令L表示這些服務(wù)點集,它們構(gòu)成服務(wù)點集L={vi|1≤i≤m},其中m表示服務(wù)點數(shù)。仍以圖1為例,圖1中的黑顏色實心圓點表示服務(wù)點。當(dāng)兩個連續(xù)服務(wù)點間距離大于B時,移動機器人就需在途中充電。

1.2 問題概述

對于任意一條路徑T,路徑從始點s開始,遍布L中每個點再返回始點s,且路徑T中連續(xù)的兩個服務(wù)點間距離不超過B,使保持移動機器人的電量不耗盡。本文需要解決的問題是:在滿足兩個條件的基礎(chǔ)上,最小化中路徑T的長度|T|。這兩個條件是:①移動機器人完成所有任務(wù);②兩個連續(xù)服務(wù)點間距離不超過B。

路徑長度等于路徑中每連續(xù)兩個服務(wù)點間歐式距離之和。|T|越小表明移動機器人所移動距離越短,所消耗的能量就越少。

因此,FCPP算法需要解決的問題就是:①如何依據(jù)任務(wù)點構(gòu)建服務(wù)點。所構(gòu)建的服務(wù)點必保證每個任務(wù)點都被服務(wù);②構(gòu)建移動機器人路徑,使路徑最短,且路徑中任意兩個連續(xù)的服務(wù)點間距離不超過B。

2 FCPP算法

FCPP算法旨在保證每個任務(wù)點被服務(wù)的基礎(chǔ)上,尋找服務(wù)點;然后再依據(jù)這些服務(wù)點構(gòu)建能耗最低的路徑。

2.1 基于區(qū)域覆蓋法的服務(wù)點的構(gòu)建

區(qū)域覆蓋(geometric covering,GC)法是利用最少的全等副本(congruent copy,CC)覆蓋給定的區(qū)域目標(biāo)。令X表示區(qū)域目標(biāo)集。Q表示CC的形狀。當(dāng)利用GC法構(gòu)建服務(wù)點時,則X←K,且Q則是半徑為r的圓盤(移動機器人的感測區(qū)域)。當(dāng)移動機器人位于圓盤中心,其能夠為圓盤內(nèi)所有點服務(wù)。

因此,利用GC法構(gòu)建服務(wù)點等價于尋找最少數(shù)量的圓盤,使這些圓盤聯(lián)合覆蓋K集內(nèi)每個任務(wù)點。該問題屬典型的單圓盤覆蓋問題(unit disk cover,UDC)[7]。UDC問題假定r=1,即一個單位。由于很容易對r進(jìn)行擴(kuò)展,設(shè)置r=1并不影響求解UDC問題。

圖2 網(wǎng)格化示例

最后,將所構(gòu)建的圓盤的中心點作為服務(wù)點,將這些點加入L,進(jìn)而構(gòu)成L集。利用區(qū)域覆蓋法構(gòu)建服務(wù)點的過程如算法1所示。

令D表示建立的圓盤集。最初集D為空集,即D=?。對于K中任意一點p,先估計其屬哪個網(wǎng)格,如表1所示。

表1 基于區(qū)域覆蓋法的服務(wù)點構(gòu)建算法

然后,再確認(rèn)已建立的圓盤{D(i-1,j),D(i+1,j),D(i,j-1),D(i,j+1)}是否已覆蓋點p。如果已覆蓋,就繼續(xù)為下一點構(gòu)建圓盤。否則,就用D(i,j)覆蓋點p,即將D(i,j)加入D中,如步驟4所示。

再進(jìn)入步驟5,計算D中每個圓盤的中心,并將圓心作為移動機器人的服務(wù)點,即L=L∪O(i,j),其中O(i,j)表示D(i,j)的中心。

2.2 基于Christofides算法的路徑構(gòu)建

依據(jù)2.1節(jié)所述,利用算法1構(gòu)建服務(wù)點,完成服務(wù)點集L的構(gòu)建。接下來,需要解決的問題是:依據(jù)這些服務(wù)點和始點,形成最小權(quán)重的閉合路徑。每條路徑從始點s開始,遍歷L中每個服務(wù)點且只遍歷一次,然后再返至始點s。換而言之,在L∪{s}上建立最小權(quán)重路徑。這屬典型的行商問題(traveling salesman problem,TSP)[8-9]。

TSP問題的輸入圖G是完備的。該圖G是依據(jù)輸入點集構(gòu)建的。此外,圖G中的邊滿足三角不等式規(guī)則,即對于G中任意3條邊(u,v),(v,w),(u,w),它們的權(quán)重滿足:

weight[(u,v)]+weight[(v,w)]>weight[(u,w)]

(1)

式中:weight[·]表示邊的權(quán)重。

本文中輸入圖G是在L∪{s}上構(gòu)建的完備圖,邊(u,v)的權(quán)重等于節(jié)點u,v間的歐式距離,其中點u,v屬于L∪{s},即u,v∈L∪{s}。

由于TSP問題是NP問題[10]。本文采用Christofides算法求解[11]。Christofides算法主要是由求解最小生成樹(minimum spanning tree,MST)、最小完美匹配和形成歐拉回路3個階段構(gòu)成。在求解時,先生成最小生成樹,然后,Christofides算法再使用最小完美匹配法得到最小匹配圖,最后利用歐拉回路法構(gòu)建一條TSP問題的近似解。求解步驟如表2所示。

表2 基于Christofides算法

2.3 基于啟發(fā)式A*的能效路徑的建立

從第2.2節(jié)可知,2.2節(jié)在構(gòu)建路徑時,并沒有考慮移動機器人的充電站位置,也沒有考慮到充電點。為了保證移動機器人在移動過程不耗盡電量,在構(gòu)建路徑時考慮充電點位置。即路徑中連續(xù)的兩個點間距離不超過B。具體而言,假定u,v表示路徑T中連續(xù)的兩個點,從點u至點v間距離可能超過B,移動機器人可能需要往返充電點。

利用文獻(xiàn)[12]所述的啟發(fā)式A*法在圖Ge上構(gòu)建路徑,使路徑T中兩個連續(xù)點間距離不超過B。具體過程如表3所示。啟發(fā)式A*法的具體過程可參見文獻(xiàn)[12-13]。令Te表示由算法3輸出的路徑,其表示滿足路徑中連續(xù)兩個點間距離不超過B的約束條件。

表3 Compute-ETOUR算法

3 性能分析

3.1 仿真環(huán)境

3.2 構(gòu)建服務(wù)點集L所需的運行時間

圖3給出了利用算法1構(gòu)建服務(wù)點集L所需的運行時間和產(chǎn)生的圓盤數(shù),其中n從100至1000變化。

(a) 運行時間 (b) 圓盤數(shù)圖3 構(gòu)建服務(wù)點集所需的運行時間和產(chǎn)生的圓盤數(shù)

從圖3a可知,運行時間隨服務(wù)點數(shù)n增加而上升,且呈近似線性關(guān)系。這符合邏輯。服務(wù)點數(shù)越多,所需的圓盤數(shù)越多,如圖3b所示。圖3b證實了圓盤數(shù)隨服務(wù)點數(shù)n增加而上升的結(jié)果。例如,當(dāng)n=400時,產(chǎn)生的圓盤數(shù)約240個。當(dāng)n增加至800時,產(chǎn)生的圓盤數(shù)上升至360個。

3.3 構(gòu)建能效路徑所消耗的時間

圖4 構(gòu)建能效路徑所消耗的時間

觀察圖4可得3條結(jié)論:①不論B值為何值和多少個充電站數(shù),消耗時間均隨n值增加而上升;②在同等條件下,充電站數(shù)越多,消耗時間越多;③B值越大,消耗時間也越多。

出現(xiàn)結(jié)論①的原因在于:n值越大,所產(chǎn)生的圓盤數(shù)越多(可見圖3b)。因此,所產(chǎn)生的服務(wù)點數(shù)也增加,即|L|值變大,利用啟發(fā)式A*法構(gòu)建Te時所需計算的位置點就隨之增加,這就提升了運算時間,最終增加了消耗時間。

出現(xiàn)結(jié)論②的原因在于:充電站數(shù)越多,圖Ge的尺寸就越大。利用啟發(fā)式A*法構(gòu)建Te時所需考慮的點數(shù)和邊數(shù)就越多,最終也增加了運算時間。

出現(xiàn)結(jié)論③的原因在于:B值越大,圖Ge中共享邊中的點數(shù)越多,使Ge越密集,最終也增加了運算時間。

3.4 路徑長度

圖5 路徑長度

此外,B值越大,路徑長度隨|C|變化的波動更小。同時,觀察圖5可知,當(dāng)n值越大時,|C|=5%×n與|C|=7%×n間的路徑長度的差距越小。原因在于:n值越大,所需的圓盤數(shù)越多,參與構(gòu)建能效路徑的點就越多。由于服務(wù)點為均勻分布,能效路徑中兩個連續(xù)點間的距離就縮小,最終導(dǎo)致路徑變短,它們受充電站數(shù)的影響就變小。

4 結(jié)束語

本文提出一種任務(wù)點全覆蓋的能效路徑規(guī)劃算法。該算法假定移動機器人具有固定的感測范圍。移動機器人以遍歷最少的服務(wù)點覆蓋所有任務(wù)點。FCPP算法依據(jù)任務(wù)點,并利用區(qū)域覆蓋法構(gòu)建圓盤,再將圓盤的中心作為移動機器人的服務(wù)點。然后,再利用Christofides算法建立路徑。考慮到移動機器人是由電池供電,其電量有限。移動機器人在沿著路徑移動中可能需要充電。為了使移動機器人的電量不耗盡,路徑中任意兩個連續(xù)服務(wù)點間距離不超過續(xù)航距離。仿真結(jié)果表明,提出的FCPP算法能夠快速地覆蓋所有任務(wù)點。這說明利用GC法構(gòu)建服務(wù)點集,再通過Christofides算法規(guī)劃路徑,可有效地縮短移動路徑,提高了完成任務(wù)效率。