董鈺穎,楊雷恒

(西安航空職業(yè)技術(shù)學(xué)院 航空維修工程學(xué)院，陜西 西安 710089)

1 引言

新型冠狀病毒爆發(fā)以來，大量醫(yī)護人員奔赴一線開展疫情防控工作。但是在治療病人的過程中，醫(yī)護人員被傳染的情況時有發(fā)生。利用移動機器人代替醫(yī)護人員進入醫(yī)院病房、手術(shù)室等區(qū)域完成物品配送工作，既能減少醫(yī)護人員交叉感染的風險，又能夠在一定程度上減輕醫(yī)護人員繁重的工作負擔。目前，世界上很多國家開始將移動機器人應(yīng)用到醫(yī)院環(huán)境中，并取得了一定的成果[1]。隨著任務(wù)規(guī)模的不斷增大，單一的機器人難以完成復(fù)雜任務(wù)，因此多機器人系統(tǒng)協(xié)同工作模式應(yīng)運而生。較單一機器人而言，多機器人系統(tǒng)在環(huán)境自適應(yīng)性、任務(wù)適用性、經(jīng)濟性、安全性及魯棒性等多方面具有顯著的優(yōu)勢[2-5]。多機器人系統(tǒng)協(xié)同路徑規(guī)劃問題的求解不僅僅是單機器人路徑規(guī)劃問題的簡單疊加，還需要從全局的角度將不同任務(wù)分配給各輛機器人并規(guī)劃出機器人執(zhí)行各自任務(wù)的最優(yōu)路徑軌跡。

機器人在工作環(huán)境中的不同區(qū)域的移動過程可以看作是一個離散事件[6]，Petri網(wǎng)是一個針對離散事件系統(tǒng)典型的建模方法。Mahulea和Kloetzer[7]提出了一種基于Petri網(wǎng)的整數(shù)線性規(guī)劃模型求解機器人最短路徑的方法，將布爾邏輯描述的任務(wù)約束轉(zhuǎn)化成一系列線性約束并整合成一個整數(shù)線性規(guī)劃模型，通過模型求解計算出機器人的最優(yōu)軌跡。馬小軍、芮峰等人[8]在文獻[7]的基礎(chǔ)上，通過著色Petri 網(wǎng)研究了不同種類的機器人在同一工作區(qū)域協(xié)同執(zhí)行任務(wù)的路徑規(guī)劃問題。本文根據(jù)醫(yī)院物品配送的實際需求，將配送任務(wù)的時效性、機器人最大載貨量等限制因素考慮在內(nèi)，提出了一種基于Petri網(wǎng)的多機器人系統(tǒng)協(xié)同路徑規(guī)劃方法。通過所提出的路徑規(guī)劃方法，能夠有效快速地為每輛機器人獲得符合任務(wù)需要的最優(yōu)路徑軌跡。

2 機器人工作環(huán)境建模與協(xié)同規(guī)劃

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

作為一種數(shù)形結(jié)合的系統(tǒng)描述和分析工具，Petri 網(wǎng)是一個四元組N=(P，T，F(xiàn)，W)，其中，P={p1，p2，…，pm}是m個庫所的集合；T={t1，t2，…，tn}是n個變遷的集合[8]；F(P×T)(T×P)表示網(wǎng)結(jié)構(gòu)中有向弧的集合；W：(P×T)(T×P)→N為Petri網(wǎng)的權(quán)函數(shù)；(N，M0)稱為一個標識網(wǎng)，其中M0是Petri 網(wǎng)的初始標識；庫所中的標識叫做托肯(token)，表示庫所中的資源數(shù)量；令x PT，是Petri網(wǎng)中所有節(jié)點的集合。其中，前置集x，記作x={y PT|(y，x)F}，后置集x，記作x={y PT|(x，y)F} 。

Petri 網(wǎng)的幾何結(jié)構(gòu)能夠通過關(guān)聯(lián)矩陣C表示出來，它是一個n*m維的矩陣，其中，n表示網(wǎng)結(jié)構(gòu)中有n個庫所，m表示網(wǎng)結(jié)構(gòu)中有m個變遷。其中，Pre：m*n→N，Post：m*n→N分別為PN的輸入、輸出函數(shù)矩陣，即Pre=W(p，t)，Post=W(t，p)，則有

Petri 網(wǎng)N 的某個標識狀態(tài)M'是從初始狀態(tài)M0觸發(fā)一系列變遷∑={σ1，σ2，…，σh}產(chǎn)生的，即M0[∑＞M'。系統(tǒng)上述的運行關(guān)系可由包含初始狀態(tài)的狀態(tài)方程表示：

式(2)中的∑表示發(fā)射變遷序列的計數(shù)向量，即網(wǎng)系統(tǒng)每一次觸發(fā)所發(fā)射變遷的集合。

2.2 工作環(huán)境建模

通過某醫(yī)院實地調(diào)研可知，該醫(yī)院的住院大樓一共有十層，其中一樓為綜合治療區(qū)域，二樓到十樓為專治科室，其中一層為一個科室，每個科室設(shè)有兩個電梯間、一個護士站以及17個病房，每個病房中有4個床位供病人居住。醫(yī)院設(shè)有草藥、西藥、顆粒藥以及湯藥四個藥房，分別位于地下一層以及一樓大廳。由于住院部各科室內(nèi)部環(huán)境布局類似，為了簡化描述，以二樓內(nèi)科科室和三樓骨科科室為例，將機器人工作區(qū)域模塊化處理，介紹醫(yī)院各功能區(qū)的位置分布情況，環(huán)境分布如圖1所示。

圖1 醫(yī)用配送機器人工作環(huán)境

根據(jù)圖1所示的區(qū)域簡圖建立Petri網(wǎng)模型：按照藥房、病房、護士站、電梯間等區(qū)域的位置分布，將內(nèi)部走廊劃分成若干小區(qū)域，其中每個小區(qū)域?qū)?yīng)為一個庫所；只有聯(lián)通區(qū)域之間可以進行位移，區(qū)域的聯(lián)通關(guān)系通過在兩區(qū)域之間添加變遷表示，位移的過程可以通過觸發(fā)變遷表示。由于醫(yī)院是一個三維環(huán)境，機器人在執(zhí)行任務(wù)過程中需要經(jīng)過不同樓層，因此將機器人在不同樓層的移動過程通過觸發(fā)連接在對應(yīng)樓層電梯間的變遷實現(xiàn)。根據(jù)上述描述，建立Petri 網(wǎng)模型如圖2所示，模型中一共有73個庫所，162個變遷。其中紅色區(qū)域為科室電梯間，藍色區(qū)域為護士站，綠色區(qū)域為藥房位置。

圖2 醫(yī)院工作環(huán)境的Petri網(wǎng)模型

為了實時監(jiān)控機器人移動過程中距離、時間和載貨量的變化情況，在相鄰區(qū)域之間加權(quán)如下信息：

(1)di，j表示區(qū)域i到區(qū)域j的歐幾里得距離，將距離信息di，j加權(quán)在對應(yīng)的變遷上，表示機器人從區(qū)域pi移動到區(qū)域pj所增加的里程，通過對醫(yī)院實際道路情況進行調(diào)研，加權(quán)對應(yīng)變遷的距離信息具體如下：

表1 醫(yī)院環(huán)境中各小區(qū)域之間的距離信息

(2)bi，j表示機器人從區(qū)域i到區(qū)域j增加的載貨量，即區(qū)域j對應(yīng)任務(wù)的需求量qj，qj＞0 表示區(qū)域j為收貨點，qj＜0 表示區(qū)域j為送貨點，將區(qū)域j的需求量qj加權(quán)在對應(yīng)庫所pj的所有輸入變遷ti，j上(i=1，2，…，73，i≠j)，表示機器人到任務(wù)區(qū)域j執(zhí)行任務(wù)后增加的載貨量；

(3)δi，j表示機器人從區(qū)域i移動到區(qū)域j需要的時間，將時間信息δi，j加權(quán)在對應(yīng)變遷ti，j上，表示機器人從區(qū)域i移動到區(qū)域j的時間，機器人在相鄰區(qū)域的通行時間根據(jù)道路實際距離、機器人行駛速度而定；

2.3 機器人系統(tǒng)協(xié)同路徑規(guī)劃任務(wù)描述

實際的物品配送工作十分繁重，需要多輛機器人協(xié)同完成。本文根據(jù)醫(yī)院實際的環(huán)境情況以及物品配送的實際要求，將機器人的工作任務(wù)進行如下設(shè)定：

(1)每個配送任務(wù)都位于固定的區(qū)域，其中可能存在一些任務(wù)具有時間約束，需要對機器人系統(tǒng)進行任務(wù)分配，保證有機器人根據(jù)配送要求按時到達任務(wù)所在的區(qū)域才能完成配送任務(wù)；

(2)醫(yī)院中存在一些禁止通行的區(qū)域，機器人們在執(zhí)行各自任務(wù)的過程中需要避開這些區(qū)域。此外，機器人在執(zhí)行完成各自任務(wù)之后需要就近回到規(guī)定休息區(qū)域補充電量，獲得繼續(xù)完成任務(wù)的能量；

3 基于Petri網(wǎng)的整數(shù)線性規(guī)劃模型

3.1 基本假設(shè)

1)醫(yī)用配送機器人型號一定，故額定速度一定，機器人總數(shù)量為K；

2)機器人工作環(huán)境是靜態(tài)的、恒定的，各分區(qū)區(qū)域之間的距離已知，各道路始終處于暢通狀態(tài)，機器人均按照額定速度進行工作；

3)在初始狀態(tài)，系統(tǒng)中處于空閑狀態(tài)機器人的位置已知；

4)工作環(huán)境中禁行區(qū)域位置已知，機器人補充電量的休息區(qū)域已知；

5)任務(wù)區(qū)域位置已知，需求量已知，需求時間窗約束已知；

6)假設(shè)所有配送機器人不存在技術(shù)方面的問題，執(zhí)行任務(wù)前已儲存足夠的電量完成所分配的配送任務(wù)；

7)所有工作區(qū)域空間充足，允許多輛機器人同時經(jīng)過同一區(qū)域；

8)一輛配送機器人可以為多個任務(wù)區(qū)域執(zhí)行任務(wù)；

9)每個任務(wù)區(qū)域可以允許多輛機器人經(jīng)過，但是只需要一輛機器人執(zhí)行任務(wù)；

3.2 參變量定義

根據(jù)上述問題的描述和基本假設(shè)，現(xiàn)進行如下的變量和參數(shù)符號定義，如表2所示。

表2 符號含義

3.3 模型的建立過程

多機器人系統(tǒng)執(zhí)行任務(wù)的過程可能存在前后順序關(guān)系，由于實際的一些配送任務(wù)存在一定的時間約束，只有當機器人在規(guī)定的時間范圍內(nèi)到達對應(yīng)任務(wù)區(qū)域執(zhí)行任務(wù)才能認為該任務(wù)被完成。否則，就算有機器人到達任務(wù)區(qū)域執(zhí)行相應(yīng)任務(wù)但是沒有在規(guī)定的時間范圍內(nèi)也會被認作任務(wù)執(zhí)行無效。如何根據(jù)任務(wù)區(qū)域以及需求時間給每輛機器人提供執(zhí)行任務(wù)的路徑軌跡，保證機器人系統(tǒng)的總工作軌跡是滿足任務(wù)要求最短路徑軌跡。根據(jù)上述目標，建立如下路徑規(guī)劃模型。以多機器人系統(tǒng)總路徑軌跡最短為目標函數(shù)：

式(2)為任務(wù)區(qū)域約束，即每個任務(wù)區(qū)域都需要至少一輛機器人到達并執(zhí)行配送任務(wù)；

式(3)為禁行區(qū)域約束，即機器人們在執(zhí)行任務(wù)過程中禁止經(jīng)過禁行區(qū)域；

式(4)保證機器人們在完成全部任務(wù)后就近到休息區(qū)域補充電量，每個休息區(qū)域中可容納至少一輛機器人補充電量；

其中，引入0-1二值變量yki和xijk

4 實驗結(jié)果

基于3．3節(jié)所建立的模型，在某醫(yī)院實際環(huán)境對機器人系統(tǒng)進行仿真驗證，某天上午七點，系統(tǒng)中有兩輛空閑機器人停留在休息區(qū)域p64，此時系統(tǒng)接收到如下任務(wù)指令：

該任務(wù)描述為：機器人系統(tǒng)接受到任務(wù)指令后需立即派出空閑機器人從休息區(qū)域p64出發(fā)進行藥物配送工作，機器人需要在[7：00，7：15]范圍內(nèi)到達顆粒藥房p67、西藥藥房p68、中藥藥房p69、湯藥藥房p73中取藥，其中顆粒藥的取藥量為兩個單位、西藥的取藥量為五個單位、中藥的取藥量為八個單位、湯藥的取藥量為九個單位；取藥完成后需要在[7：20，7：45]范圍內(nèi)到達病房p54、p34、p3、p4、p15、p64中為病人配送需要的藥物，病房p54的需藥量為十個單位，病房p34的需藥量為五個單位，病房p3的需藥量為三個單位，病房P4的需藥量為四個單位，病房p15的需藥量為兩個單位；當機器人們完成所有的配送任務(wù)，必須返回休息區(qū)域p64中補充電量。機器人進行取藥和送藥的過程均在藥房和科室醫(yī)護人員的協(xié)助下進行藥品的核對與分裝。

通過Matlab 軟件對所提出的模型進行仿真，計算出機器人們執(zhí)行任務(wù)的路徑軌跡，仿真結(jié)果如下：

機器人1 的路徑軌跡：p64(0)→p65(2)→p66(2．5)→p69(3)→p66(8．5)→p65(9)→p68(9．5)→p65(15)→p63(15．1)→p67(15．6)→p63(20．1)→p61(21．1)→p52(26．1)→p42(28．4)→p43(28．46)→p44(28．52)→p34(28．82)→p44(31．12)→p54(31．42)→p44(33．72)→p43(33．78)→p42(33．84)→p52(34．14)→p61(39．14)→p63(40．14)→p65(40．24)→p64(42．24)

機器人2 的路徑軌跡：p64(0)→p65(2)→p63(2．1)→p61(3．1)→p70(8．1)→p72(10．1)→p73(10．6)→p72(16．1)→p70(18．1)→p12(26．1)→p22(28．4)→p23(28．26)→p24(28．46)→p4(28．82)→p24(31．12)→p25(31．18)→p15(31．48)→p25(33．78)→p24(33．84)→p23(33．9)→p3(34．2)→p23(36．5)→p22(36．56)→p12(36．86)→p61(43．86)→p63(44．86)→p65(44．96)→p64(46．96)

如上可知，機器人們在任務(wù)規(guī)定的時間范圍內(nèi)到達任務(wù)區(qū)域進行配送服務(wù)，在機器人執(zhí)行任務(wù)的過程中均未超過機器人的額定載貨量。機器人們的總移動距離為750m。

5 結(jié)束語

根據(jù)醫(yī)院當前物品配送任務(wù)繁重的現(xiàn)狀，本文提出了一種對醫(yī)院工作環(huán)境建立Petri 網(wǎng)模型的建模方法，并基于Petri 網(wǎng)特性提出一個整數(shù)線性規(guī)劃方法，本方法能夠?qū)C器人進行合理的任務(wù)分配并規(guī)劃出最優(yōu)的路徑軌跡。通過提出的模型能夠保證機器人根據(jù)環(huán)境要求在不經(jīng)過禁行區(qū)域的同時到達任務(wù)區(qū)域執(zhí)行任務(wù)并最終回到休息區(qū)域，該方法通過MATLAB仿真獲得了驗證，根據(jù)仿真結(jié)果可知本文所提路徑規(guī)劃方法能夠為多機器人系統(tǒng)規(guī)劃出不碰撞的最短路徑軌跡，同時保證所有的任務(wù)都能在規(guī)定時間范圍內(nèi)完成，證明本文提出的方法可行且計算效率高，能夠有效解決醫(yī)院目前急需解決的配送任務(wù)，為減輕醫(yī)護人員的工作負擔提供了一個有效的思路。