張延年,吳 昊,張 云

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

0 引言

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

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

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

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

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

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

1.1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

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

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

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

1.2 問(wèn)題概述

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

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

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

2 FCPP算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

表2 基于Christofides算法

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

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

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

表3 Compute-ETOUR算法

3 性能分析

3.1 仿真環(huán)境

3.2 構(gòu)建服務(wù)點(diǎn)集L所需的運(yùn)行時(shí)間

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

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

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

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

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

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

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

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

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

3.4 路徑長(zhǎng)度

圖5 路徑長(zhǎng)度

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

4 結(jié)束語(yǔ)

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