多醫(yī)用配送機(jī)器人系統(tǒng)實(shí)時(shí)路徑規(guī)劃方法研究

董鈺穎， 楊雷恒

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

0 引言

經(jīng)過長(zhǎng)期科學(xué)研究，自主移動(dòng)機(jī)器人技術(shù)已經(jīng)較為成熟，并應(yīng)用于航空航天、水下探測(cè)、服務(wù)、物流配送等不同領(lǐng)域中[1-3]。2019年12月COVID-19世界范圍內(nèi)蔓延后，各國醫(yī)療服務(wù)缺口懸殊的問題日益凸顯，為了保證醫(yī)護(hù)工作者的生命安全，減輕其工作負(fù)擔(dān)，引入專用的醫(yī)用配送機(jī)器人完成物品配送成為大眾翹首以盼的技術(shù)革新[4]。

為了保證醫(yī)用配送機(jī)器人按照任務(wù)要求實(shí)現(xiàn)自主移動(dòng)，準(zhǔn)確完成物品配送任務(wù)，路徑規(guī)劃技術(shù)是關(guān)鍵技術(shù)之一。它不僅在一定程度上代表移動(dòng)機(jī)器人智能化程度的高低，更是其完成更高層任務(wù)的基石。由于日常配送任務(wù)繁重同時(shí)具有時(shí)間限制，單一機(jī)器人難以完成所有配送任務(wù)，需要多輛機(jī)器人協(xié)同完成[5-6]。

1 多醫(yī)用配送機(jī)器人系統(tǒng)協(xié)同路徑規(guī)劃問題概述

1.1 多醫(yī)用配送機(jī)器人系統(tǒng)日常工作特點(diǎn)分析

根據(jù)實(shí)地調(diào)研可知，醫(yī)用配送機(jī)器人工作任務(wù)繁重，單一機(jī)器人難以在規(guī)定時(shí)間范圍內(nèi)完成所有的配送任務(wù)，需要多輛機(jī)器人協(xié)同完成。總結(jié)來說，多機(jī)器人系統(tǒng)存在如下優(yōu)點(diǎn)。

(1) 系統(tǒng)工作效率高，多輛機(jī)器人系統(tǒng)可以將復(fù)雜繁重的配送任務(wù)分布給多輛機(jī)器人協(xié)同完成，較單輛機(jī)器人執(zhí)行任務(wù)而言工作效率更高，配送任務(wù)能夠更快的被執(zhí)行。

(2) 系統(tǒng)穩(wěn)定性強(qiáng)，多輛機(jī)器人協(xié)同執(zhí)行任務(wù)能夠提高系統(tǒng)的穩(wěn)定性。當(dāng)系統(tǒng)中某輛機(jī)器人發(fā)生故障時(shí)，通過任務(wù)重新分配給其他機(jī)器人能夠保證所有任務(wù)能夠按照要求完成。

(3) 經(jīng)濟(jì)性能好，多輛機(jī)器人協(xié)同完成任務(wù)能夠有效地減輕機(jī)器人的工作負(fù)擔(dān)，能夠減輕每輛機(jī)器人的損耗，從而減少機(jī)器人的維修費(fèi)用。

1.2 多配送機(jī)器人系統(tǒng)控制方法

多機(jī)協(xié)同路徑規(guī)劃問題不僅是機(jī)器人數(shù)量增加的問題，需要在整體上綜合考慮機(jī)器人的任務(wù)分配、路徑規(guī)劃以及碰撞避免[7]。為了解決上述問題，需要中央控制系統(tǒng)作為多機(jī)器人系統(tǒng)的上位機(jī)，通過其建立起機(jī)器人之間、每輛機(jī)器人的通信關(guān)系，將獨(dú)立的機(jī)器人緊密聯(lián)系起來。目前，多機(jī)器人協(xié)同路徑規(guī)劃算法框架分為集中式控制框架以及分布式控制框架。

(1) 基于集中式控制框架多機(jī)器人路徑規(guī)劃算法

每輛機(jī)器人只與系統(tǒng)中央控制器建立通信，機(jī)器人之間不能直接通信。該方法優(yōu)點(diǎn)是部署簡(jiǎn)單，統(tǒng)籌規(guī)劃較大程度避免局部最優(yōu)的問題。在目前研究中，有部分研究者在考慮時(shí)域和空域的同時(shí)引入時(shí)間窗的概念進(jìn)行動(dòng)態(tài)無碰撞路徑規(guī)劃方法探究。文獻(xiàn)[8]提出了一種基于時(shí)間窗動(dòng)態(tài)無碰撞的多AGV路徑規(guī)劃方法，一定程度上解決了多輛小車運(yùn)行過程中的碰撞與死鎖問題。Mahulea等[9]提出了一種基于Petri網(wǎng)的整數(shù)線性規(guī)劃模型求解機(jī)器人最短路徑的方法，將布爾邏輯描述的任務(wù)約束轉(zhuǎn)化成一系列線性約束并整合成一個(gè)整數(shù)線性規(guī)劃模型，通過模型求解計(jì)算出機(jī)器人的最優(yōu)軌跡。文獻(xiàn)[10]通過在整數(shù)規(guī)劃模型中加入時(shí)間窗約束保證了所有的任務(wù)在規(guī)定的時(shí)間范圍內(nèi)被有效完成。上述方法均存在當(dāng)機(jī)器人數(shù)量增大時(shí)，中央控制器的計(jì)算量呈指數(shù)增長(zhǎng)的問題，對(duì)于實(shí)際環(huán)境中大規(guī)模機(jī)器人路徑規(guī)劃問題，該方法無法實(shí)現(xiàn)最優(yōu)解的求解。

(2) 基于分布式控制框架多機(jī)器人路徑規(guī)劃算法

每個(gè)機(jī)器人根據(jù)自身所配備傳感器采集的信息單獨(dú)規(guī)劃自己的路徑和運(yùn)動(dòng)。在運(yùn)動(dòng)過程中，機(jī)器人之間不直接進(jìn)行通信，具有系統(tǒng)靈活、魯棒性好的優(yōu)點(diǎn)。但是該方法仍存在缺乏全局的控制，無法保證所規(guī)劃的路徑為最優(yōu)軌跡的缺點(diǎn)。

2 一種多醫(yī)用配送機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法

通過對(duì)多醫(yī)用配送機(jī)器人的任務(wù)特點(diǎn)、技術(shù)要求以及研究現(xiàn)狀進(jìn)行分析，本文結(jié)合集中控制式和分布控制式算法的優(yōu)點(diǎn)，提出了一種高效率的實(shí)時(shí)路徑規(guī)劃策略。

2.1 基于滾動(dòng)時(shí)域的實(shí)時(shí)在線路徑規(guī)劃策略

(1) 方法概述

根據(jù)實(shí)際配送中，醫(yī)院道路通行情況不斷變化，為了應(yīng)對(duì)突發(fā)擁擠導(dǎo)致任務(wù)停滯的情況發(fā)生，本文設(shè)計(jì)了一種基于滾動(dòng)時(shí)域[11]的周期性路徑規(guī)劃策略，主要實(shí)施過程如圖1所示。

圖1 基于滾動(dòng)時(shí)域的多配送機(jī)器人系統(tǒng)總體控制框架

所謂滾動(dòng)時(shí)域，即在系統(tǒng)中引入計(jì)時(shí)器，同時(shí)將計(jì)時(shí)器所記錄機(jī)器人的工作時(shí)間劃分為若干時(shí)域。每一時(shí)域初，中央控制器根據(jù)監(jiān)控系統(tǒng)實(shí)時(shí)反饋的道路通行情況和機(jī)器人所在位置重新分析每輛機(jī)器人接下來的最優(yōu)軌跡，并下達(dá)給機(jī)器人們。機(jī)器人按照規(guī)定的路徑執(zhí)行任務(wù)直到該時(shí)域結(jié)束，并進(jìn)入到下一時(shí)域初的軌跡更新中，時(shí)域不斷滾動(dòng)，直到所有任務(wù)都被按時(shí)完成。

(2) 具體實(shí)施過程

首先在離線全局規(guī)劃最初階段，所有機(jī)器人處于靜止?fàn)顟B(tài)，所有道路均處于暢通狀態(tài)。機(jī)器人開始按照離線規(guī)劃的軌跡運(yùn)行，同時(shí)將計(jì)時(shí)器所記錄的機(jī)器人執(zhí)行任務(wù)過程的工作時(shí)間劃分成若干個(gè)時(shí)域；每時(shí)域末，監(jiān)控系統(tǒng)向中央控制系統(tǒng)反饋機(jī)器人所處位置以及此時(shí)工作環(huán)境中各道路的實(shí)時(shí)通行情況，并將此作為下一時(shí)域的初始條件，判斷在當(dāng)前道路通行情況下未完成的任務(wù)是否能夠按時(shí)完成。若能，則機(jī)器人按照原路徑軌跡執(zhí)行任務(wù)；若不能，則根據(jù)機(jī)器人當(dāng)前所在位置以及未完成任務(wù)所在區(qū)域再次進(jìn)行規(guī)劃直到所有配送任務(wù)均被完成。具體在線路徑再規(guī)劃策略如圖2所示。

圖2 在線路徑再規(guī)劃策略

2.2 實(shí)時(shí)沖突避免策略

由于醫(yī)院中各工作區(qū)域的實(shí)時(shí)接納量隨著人流量影響而不斷變化，可能導(dǎo)致原本容量充足的區(qū)域不允許機(jī)器人同時(shí)通過。對(duì)于上述問題，本文提出了一種基于滾動(dòng)時(shí)域的出發(fā)時(shí)間安排策略，在每時(shí)域初根據(jù)工作環(huán)境中機(jī)器人的實(shí)際容納量設(shè)置機(jī)器人的出發(fā)時(shí)間，避免機(jī)器人們同時(shí)經(jīng)過沖撞區(qū)域，從而避免沖撞發(fā)生。具體實(shí)施方法如下。

(1)

如果2輛機(jī)器人q和α在運(yùn)行過程中都會(huì)經(jīng)過區(qū)域pc，當(dāng)2輛機(jī)器人經(jīng)過該區(qū)域的時(shí)間存在如圖3所示的重合時(shí)間域時(shí)，2輛機(jī)器人將因同一時(shí)段處于區(qū)域pc發(fā)生碰撞。

(a)

(b)

(c)

(d)圖3 產(chǎn)生沖撞的時(shí)間域

通過上述發(fā)生碰撞的四種情況分析可知，只要避免機(jī)器人在重合的時(shí)間域內(nèi)經(jīng)過容量有限的區(qū)域才能避免碰撞的發(fā)生，因此，機(jī)器人經(jīng)過容量有限區(qū)域的時(shí)間域需要滿足如下不等式：

min (y1+y2)

3 總結(jié)

在本文中，考慮到實(shí)際工作環(huán)境道路信息動(dòng)態(tài)變化的特點(diǎn)提出了基于滾動(dòng)時(shí)域的離線-在線兩階段的實(shí)時(shí)路徑規(guī)劃方法。通過滾動(dòng)時(shí)域?qū)崟r(shí)反饋道路的通行情況更新道路環(huán)境信息，不斷地調(diào)整機(jī)器人的運(yùn)行軌跡，防止機(jī)器人因道路突發(fā)擁堵陷入死鎖狀態(tài)的情況發(fā)生，保證了所有的任務(wù)能夠按時(shí)完成。對(duì)于環(huán)境中出現(xiàn)空間超負(fù)荷而不允許機(jī)器人同時(shí)經(jīng)過的區(qū)域，提出了一種啟動(dòng)時(shí)間調(diào)整策略合理規(guī)劃?rùn)C(jī)器人啟動(dòng)時(shí)間，錯(cuò)開機(jī)器人通過該區(qū)域的時(shí)間，從而實(shí)現(xiàn)避免沖撞，為多機(jī)器人協(xié)同實(shí)時(shí)路徑規(guī)劃提供了有效的解決方法。