何舟,張瑞杰,劉苗,古嬋
(陜西科技大學(xué) 機(jī)電工程學(xué)院,陜西 西安 710021)
消防機(jī)器人作為一種具有滅火救援功能的特種機(jī)器人,可以代替人類到較為危險的環(huán)境中展開工作[1]。因此,如何規(guī)劃其路徑軌跡并高效協(xié)同完成相應(yīng)任務(wù)已經(jīng)逐漸成為機(jī)器人協(xié)同工作的研究熱點。
文獻(xiàn)[2]提出了一種有限概率狀態(tài)模型,并結(jié)合Petri網(wǎng)采用一種在線策略隨時調(diào)整偏離軌跡的機(jī)器人,適合于具有更為復(fù)雜任務(wù)的機(jī)器人系統(tǒng)。文獻(xiàn)[3]采用布爾規(guī)范將多機(jī)器人任務(wù)進(jìn)行描述,將布爾任務(wù)轉(zhuǎn)化成整數(shù)線性規(guī)劃問題來求解,最終得到滿足任務(wù)的最短軌跡?,F(xiàn)有文獻(xiàn)主要是對單個或多個獨立的機(jī)器人采用如遺傳算法[4]、蟻群算法[5]和粒子群算法[6]等進(jìn)行路徑優(yōu)化。文獻(xiàn)[7]提出一種基于動態(tài)慣性權(quán)重的改進(jìn)粒子群算法,可以在較復(fù)雜的環(huán)境下規(guī)劃出一條平滑安全無碰撞路徑。文獻(xiàn)[8]在傳統(tǒng)蟻群算法的基礎(chǔ)上引入信息素的模糊控制更新方式,對狀態(tài)轉(zhuǎn)移概率函數(shù)進(jìn)行改進(jìn),有效減少了迭代的次數(shù)并且得到消防機(jī)器人更優(yōu)的路徑。
目前,越來越多的消防機(jī)器人已應(yīng)用到各種危險場合,消防機(jī)器人的廣泛應(yīng)用對其路徑規(guī)劃能力提出了更高的要求[9]。本文提出了一種基于Petri網(wǎng)的任務(wù)分配及最優(yōu)路徑規(guī)劃方法。通過構(gòu)建Petri網(wǎng)模型對消防機(jī)器人工作環(huán)境進(jìn)行描述,在此基礎(chǔ)上通過求解整數(shù)線性規(guī)劃獲得消防機(jī)器人協(xié)同工作時間最短的路徑,確保救援的高效性。
一個Petri網(wǎng)可定義為一個四元組N=(P,T,F(xiàn),W),其中:P={p1,p2,...,pn}為n個庫所的集合;T={t1,t2,…,tm}為m個變遷的集合;F?(P×T)∪(T×P),稱為有向弧的集合;W為F→N,稱為網(wǎng)N的權(quán)函數(shù),N={0,1,2,…}。W(p,t)為從p到t的權(quán)值,W(t,p)為從t到p的權(quán)值。
(1)
式(1)稱為Petri網(wǎng)的狀態(tài)方程,表示標(biāo)識和變遷序列中變遷出現(xiàn)次數(shù)的關(guān)系。
本文參考文獻(xiàn)[10]的室內(nèi)仿真環(huán)境,如圖1所示,對其進(jìn)行區(qū)域劃分和調(diào)整后得到圖2所示的消防機(jī)器人工作環(huán)境。各機(jī)器人既可以和中央通信也可以互相通信,圖2的工作空間被劃分成若干個小房間,房間與房間之間通過雙向門連接,實現(xiàn)雙向移動。這樣任務(wù)分配的問題就轉(zhuǎn)變成控制指定功能和數(shù)量的機(jī)器人到達(dá)指定的房間完成相應(yīng)的任務(wù)。
圖1 多機(jī)器人室內(nèi)救援環(huán)境
圖2 消防機(jī)器人工作環(huán)境
圖1中存在兩個機(jī)器人、障礙物以及不可通行的墻壁,其利用2個機(jī)器人同時進(jìn)行掃描工作,實現(xiàn)對該環(huán)境的地圖構(gòu)建,從而指引救援人員實施救援工作。
圖2的每個區(qū)域Ri被認(rèn)為是一個庫所,記做pi(i=1,2,…,n);機(jī)器人從區(qū)域Ri到達(dá)區(qū)域Rj通過變遷tk(k=1,2,…,m)來表示。因此,圖2的Petri網(wǎng)模型如圖3所示。
圖3 消防機(jī)器人工作的Petri網(wǎng)模型
本文將消防機(jī)器人工作環(huán)境分為:公共區(qū)域、專屬區(qū)域、協(xié)同區(qū)域、避障區(qū)域和終點區(qū)域。公共區(qū)域是所有機(jī)器人都可以進(jìn)行訪問的區(qū)域;不同類型的機(jī)器人有各自的專屬區(qū)域,該區(qū)域只能由對應(yīng)機(jī)器人訪問;協(xié)同區(qū)域是多機(jī)器人共同執(zhí)行任務(wù)的區(qū)域;避障區(qū)域是任何機(jī)器人都無法訪問的地方;終點區(qū)域是機(jī)器人最終到達(dá)的位置。
由于基本Petri網(wǎng)里面的資源是相同的,當(dāng)某個變遷觸發(fā)時,對應(yīng)的具體是哪個機(jī)器人進(jìn)行移動并不能很好地區(qū)分開來。如果要在基本Petri網(wǎng)中對資源進(jìn)行區(qū)分,就需要為每一個機(jī)器人單獨建立一個基本Petri網(wǎng)模型。當(dāng)環(huán)境中的機(jī)器人數(shù)量很多時,模型的規(guī)模會大幅增加,不便于表示和分析??紤]到每個機(jī)器人的工作環(huán)境模型是相同的,本文將同一工作環(huán)境下不同種類的機(jī)器人的路徑使用不同的線型進(jìn)行區(qū)分,并將每種類型的機(jī)器人路徑分成H步計算,以此來解決區(qū)分機(jī)器人所帶來的基本Petri網(wǎng)規(guī)模膨脹問題。
假設(shè)圖1的工作環(huán)境有3種不同類型的消防機(jī)器人,記為r1、r2、r3?,F(xiàn)有3個專屬任務(wù)和1個協(xié)同任務(wù)需要這3個機(jī)器人完成:
專屬任務(wù)1:需要在p10處由r1類型的機(jī)器人獨立完成。
專屬任務(wù)2:需要在p30處由r2類型的機(jī)器人獨立完成。
專屬任務(wù)3:需要在p19處由r3類型的機(jī)器人獨立完成。
協(xié)同任務(wù):需要在p12處由r2和r3類型的機(jī)器人共同完成。
機(jī)器人從一個區(qū)域移動到另一個區(qū)域記作一步,且所有機(jī)器人的初始位置均在區(qū)域R1中。假設(shè)機(jī)器人從R1出發(fā),移動到終點區(qū)域共需要H步。r1、r2、r3的公共區(qū)域是R3、R4和R28,避障區(qū)域是R5和R9,終點區(qū)域是R29、R32。由于消防機(jī)器人工作的特殊性,到達(dá)R12的機(jī)器人的時間應(yīng)該一致。
(1)消防機(jī)器人總數(shù)量為K。
(2)機(jī)器人完成任務(wù)的最大步數(shù)為H。
(3)消防機(jī)器人的公共區(qū)域為Ic,專屬區(qū)域為Ie,協(xié)同工作區(qū)域是Ix,終點區(qū)域是If,禁行區(qū)域是Ia。
(4)消防機(jī)器人在專屬區(qū)域工作的機(jī)器人集合為Eti即完成專屬任務(wù)i的機(jī)器人集合,其中:i=1,2,…,n。協(xié)同區(qū)域的機(jī)器人集合為Ex。
(5)消防機(jī)器人的運行環(huán)境較為寬松,允許多個機(jī)器人在一個房間中。
為實現(xiàn)高效救援工作,本文以消防機(jī)器人的工作時間最短為優(yōu)化目標(biāo)。在Petri網(wǎng)中,令f=[f(t1),f(t2),…,f(tm)]∈Nm,給每個變遷賦值一定的時間。優(yōu)化目標(biāo)函數(shù)式(2)使所有機(jī)器人工作總時間最短:
(2)
消防機(jī)器人r在第h步的位置變化可由狀態(tài)方程(1)得式(3):
(3)
消防機(jī)器人r在第h步變遷使能后庫所內(nèi)的托肯數(shù)非負(fù),則有式(4):
(4)
機(jī)器人r第h步只能到達(dá)一個位置,即第h步最多只會觸發(fā)一個變遷,則有式(5):
(5)
公共區(qū)域作為所有消防機(jī)器人都可以訪問的區(qū)域,應(yīng)保證至少有一個機(jī)器人對其進(jìn)行訪問,則有式(6)和式(7):
(6)
(7)
式中:vRj=[vRj(p1),…,vRj(pn)]是一個包含n個元素的向量,每個元素vRj(pi)是一個0~1變量。當(dāng)機(jī)器人訪問區(qū)域Rj的時候,該向量只有第j個元素為1,即:
(8)
消防機(jī)器人的專屬區(qū)域只能由對應(yīng)類型的機(jī)器人進(jìn)行訪問和工作,其他類型機(jī)器人不能到達(dá)該區(qū)域,應(yīng)滿足式(9)和式(10)。
(9)
(10)
消防機(jī)器人的協(xié)同區(qū)域,除了對應(yīng)的機(jī)器人進(jìn)行訪問外,其他機(jī)器人不能到達(dá)該區(qū)域,應(yīng)滿足式(11)和式(12):
(11)
(12)
消防機(jī)器人至少會到達(dá)一個停止區(qū)域,式(13)到式(16)滿足該目標(biāo)。
vRj×Mr,H-1≤zj,r×H,?Rj∈If
(13)
1-vRj×Mr,H≤zj,r×H,?Rj∈If
(14)
zj,1+zj,2+…+zj,k≤K,?Rj∈If
(15)
(16)
式中:H為一個足夠大的數(shù);zj,r(r=1,…,K)為一個0-1變量,表示機(jī)器人r是否訪問區(qū)域Rj,即:
(17)
消防機(jī)器人應(yīng)避免到達(dá)障礙區(qū)域,應(yīng)滿足式(18):
(18)
消防機(jī)器人的時刻描述:
(19)
τr,0=0
(20)
式中:τr,0為機(jī)器人的初始時刻;τr,h為機(jī)器人第h步的時刻。
基于3.2小節(jié)所建立的模型,其中,K=3,H=10,f=1,Ic={R3,R4,R28};If={R29,R32};Ie={R10,R30,R19};Ia={R5,R9};Ix={R12};Ex={r2,r3};Et1={r1};Et2={r2};Et3={r3}。MATLAB仿真得到如下結(jié)果:
r1軌跡:R1→R3→R4→R10→R11→R14→R18→R26→R27→R28→R32
r2軌跡:R1→R3→R11→R12→R13→R14→R18→R26→R30→R29
r3軌跡:R1→R3→R11→R12→R13→R14→R19→R22→R25→R29
滿足所有消防機(jī)器人完成對應(yīng)任務(wù)的路徑如圖4所示,且工作時間最短為28 s。
圖4 消防機(jī)器人最優(yōu)路徑
結(jié)合消防機(jī)器人工作環(huán)境的Petri網(wǎng)模型,本文提出了一種基于Petri網(wǎng)特性的整數(shù)線性規(guī)劃方法。通過將消防機(jī)器人的工作環(huán)境劃分為公共區(qū)域、專屬區(qū)域、協(xié)同區(qū)域、避障區(qū)域和終點區(qū)域,實現(xiàn)了機(jī)器人的任務(wù)分配。在此基礎(chǔ)上,本文將對應(yīng)的任務(wù)需求轉(zhuǎn)換為具有Petri網(wǎng)特性的整數(shù)線性規(guī)劃模型,然后利用MATLAB仿真獲得消防機(jī)器人工作效率最高的最優(yōu)路徑。經(jīng)驗證,本文提出的整數(shù)線性規(guī)劃方法具有可行性且計算效率高,能夠獲得消防機(jī)器人完成救援工作的全局最優(yōu)路徑,確保了救援的高效性。