何舟，張瑞杰，劉苗，古嬋

(陜西科技大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710021)

0 引 言

消防機(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é)同工作時間最短的路徑，確保救援的高效性。

1 Petri網(wǎng)基礎(chǔ)

一個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)系。

2 消防機(jī)器人協(xié)同任務(wù)分配及路徑規(guī)劃

2.1 工作環(huá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)模型

2.2 消防機(jī)器人協(xié)同工作

本文將消防機(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)該一致。

3 整數(shù)線性規(guī)劃模型的建立

3.1 模型的條件

(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ī)器人在一個房間中。

3.2 模型的建立過程

為實現(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步的時刻。

4 試驗結(jié)果

基于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)路徑

5 結(jié)束語

結(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)路徑，確保了救援的高效性。