基于時(shí)間窗模型的雙向機(jī)器人路徑規(guī)劃方法

王 琛，茅 健

上海工程技術(shù)大學(xué) 機(jī)械與汽車工程學(xué)院，上海 201620

提起搬運(yùn)設(shè)備，一般人首先想到的無非是叉車、卡車等傳統(tǒng)的搬運(yùn)設(shè)備。隨著智能化與自動(dòng)化的發(fā)展，制造業(yè)對(duì)自動(dòng)化智能化的需求漸增，對(duì)提高制造系統(tǒng)的物流效率，進(jìn)而提高整個(gè)生產(chǎn)系統(tǒng)的生產(chǎn)效率需求更為強(qiáng)烈，機(jī)器人搬運(yùn)車應(yīng)運(yùn)而生[1]。雙驅(qū)雙向機(jī)器人不僅速度快、精度高、可靠性高、操作維護(hù)方便，并且沿預(yù)定軌跡行駛，因而被廣泛使用[2]。物流配送系統(tǒng)優(yōu)化主要是進(jìn)行配送車輛的合理調(diào)度[3]。優(yōu)化后的配送路徑不僅大大提高了企業(yè)倉(cāng)儲(chǔ)的運(yùn)行效率，而且將人們從繁重的體力勞動(dòng)中解放出來，同時(shí)也避免了安全事故的發(fā)生[4]。

宋宇、王志明[5]將RRT算法用于柵格環(huán)境下產(chǎn)生初始路徑，其次提出一種新的插入算子，最后進(jìn)行路徑優(yōu)化。黨宏社、孫心妍[6]采用遺傳算法進(jìn)行機(jī)器人路徑規(guī)劃，并加入物料類型選擇的循環(huán)套，通過多次實(shí)驗(yàn)確定最合理的控制參數(shù)，從而產(chǎn)生機(jī)器人運(yùn)輸多種類型物料的最優(yōu)路徑結(jié)果。李天童、寧平凡等[7]在傳統(tǒng)的障礙物柵格地圖中疊加了環(huán)境安全信息，構(gòu)建了融合信息柵格地圖，提出了一種改進(jìn)的遺傳路徑規(guī)劃算法。以上算法都是針對(duì)單機(jī)器人路徑規(guī)劃。

通常在實(shí)際生產(chǎn)時(shí)，需要多臺(tái)機(jī)器人同時(shí)進(jìn)行貨物運(yùn)輸[8]。因?yàn)槭艿娇臻g和場(chǎng)地的影響，多機(jī)器人不能自由的穿越障礙物，所以多機(jī)器人路徑規(guī)劃就成為眾多挑戰(zhàn)中的一個(gè)[9]。通常所遇到的算法主要有A*算法[10-11]、遺傳算法[12-13]、模擬退火算法[14]、Dijkstra算法[15]等。孟祥忠、劉健等[16]將時(shí)間窗算法和Dijkstra算法相結(jié)合，依次規(guī)劃各機(jī)器人的路徑，并采用實(shí)時(shí)更新位置信息和時(shí)間窗排布的方法對(duì)沖突路段進(jìn)行路徑動(dòng)態(tài)規(guī)劃。雖然能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。袁洋、葉峰等[17]摒棄了傳統(tǒng)A*算法只考慮單一運(yùn)行路程的評(píng)價(jià)函數(shù)，引入了運(yùn)行路程結(jié)合區(qū)域負(fù)載作為新評(píng)價(jià)函數(shù)的方式。在幾乎不增大運(yùn)行路程的前提下，實(shí)現(xiàn)了機(jī)器人運(yùn)行路網(wǎng)的區(qū)域負(fù)載均衡。齊權(quán)、張新敏[18]在分析影響柔性生產(chǎn)車間內(nèi)機(jī)器人運(yùn)行效率因素的基礎(chǔ)上，建立了多機(jī)器人路徑優(yōu)化數(shù)學(xué)模型，并提出一種兩階段的路徑規(guī)劃方法。孫煒等[19]以路徑分割成節(jié)點(diǎn)的方法對(duì)A*算法進(jìn)行改進(jìn)，雖然可以獲得比遺傳算法更快的解決方案，但很容易陷入一些局部極小值，而遺傳算法總是可以達(dá)到全局最優(yōu)或近似全局最優(yōu)。

對(duì)于多臺(tái)機(jī)器人同時(shí)行駛，不僅要使每臺(tái)機(jī)器人行駛路徑最短，用時(shí)最少，還要能夠保證機(jī)器人之間的協(xié)作問題[20]。針對(duì)以上問題，提出了一種改進(jìn)的遺傳算法。在初始化總?cè)簳r(shí)，盡可能使隨機(jī)生成的路徑較短，通過選擇中點(diǎn)的相鄰點(diǎn)擴(kuò)大選擇范圍確保線路連續(xù)。種群適應(yīng)度函數(shù)保證機(jī)器人路徑最短和改進(jìn)路徑平滑度防止轉(zhuǎn)向次數(shù)過多。為了防止遺傳算法陷入局部最優(yōu)解，通過輪盤賭的方法確保一部分非最優(yōu)個(gè)體。在改進(jìn)后的遺傳算法基礎(chǔ)上，對(duì)車輛沖突類型進(jìn)行分類處理，明確辨別方法。根據(jù)優(yōu)先級(jí)順序，并結(jié)合提出的時(shí)間窗模型，制定對(duì)應(yīng)的協(xié)調(diào)方案，以實(shí)現(xiàn)多機(jī)器人物流系統(tǒng)總時(shí)間最少為目標(biāo)的多機(jī)器人路徑規(guī)劃系統(tǒng)。

1 時(shí)間窗模型說明

為防止單車道雙向機(jī)器人系統(tǒng)中的沖突，有必要確定每個(gè)正在運(yùn)行的機(jī)器人占據(jù)路段的時(shí)間段，即機(jī)器人系統(tǒng)路徑規(guī)劃的時(shí)間窗口。它的真正含義是從進(jìn)入某個(gè)路徑到離開該路徑的時(shí)間段，在此期間，機(jī)器人有權(quán)延特定方向使用該路徑。在機(jī)器人路徑規(guī)劃中，時(shí)間窗算法由于其簡(jiǎn)單性和實(shí)用性而被廣泛使用。

建立模型的前提條件：

（1）機(jī)器人可以在每個(gè)路線上沿兩個(gè)方向行駛；

（2）在路徑的特定狀態(tài)下，機(jī)器人以恒定速度行駛；

（3）為避免碰撞，沿同一方向行駛的機(jī)器人通過一定的安全措施確定機(jī)器人之間的間隔距離；

（4）忽略通過交叉點(diǎn)后的減速時(shí)間和加速時(shí)間；

（5）忽略機(jī)器人從等候站返回路徑的時(shí)間；

（6）任務(wù)期間忽略機(jī)器人的裝卸時(shí)間；

（7）任務(wù)的優(yōu)先級(jí)可以預(yù)先設(shè)置，通常情況下優(yōu)先級(jí)設(shè)置順序?yàn)槿蝿?wù)調(diào)度順序。

基于以上假設(shè)，多機(jī)器人路徑規(guī)劃系統(tǒng)的時(shí)間窗口公式：

時(shí)間窗口代表一段時(shí)間段及機(jī)器人從進(jìn)入路段到離開路段這段時(shí)間。根據(jù)市面上一些常見的設(shè)備如圖1，確定下列相關(guān)參數(shù)：r為彎曲路段上的轉(zhuǎn)彎半徑，取2 m；vz1為空載機(jī)器人在直線路段的速度，通常取3 m/s；vz2為空載機(jī)器人在彎曲路段的速度，通常取1.5 m/s；vl1為運(yùn)貨機(jī)器人在直線路段的速度，通常取2 m/s；vl2為運(yùn)貨機(jī)器人在彎曲路段的速度，通常取1 m/s；ljk表示jk路段的直線距離；表示jk路段的第m個(gè)時(shí)間窗口；表示jk路段的第m個(gè)時(shí)間窗口的開始時(shí)間；表示jk路段的第m個(gè)時(shí)間窗口的結(jié)束時(shí)間。

圖1 機(jī)器人Fig.1 Robot

2 基于時(shí)間窗的算法流程

2.1 建立模型

根據(jù)上述的條件，定義機(jī)器人物流規(guī)劃系統(tǒng)不能只依據(jù)最短路徑。機(jī)器人物流規(guī)劃系統(tǒng)的最終目標(biāo)是系統(tǒng)所有機(jī)器人完成規(guī)定任務(wù)的時(shí)間最少。它的目標(biāo)函數(shù)是：

它的約束函數(shù)是：

參數(shù)說明：n表示倉(cāng)儲(chǔ)系統(tǒng)中存在的機(jī)器人數(shù)；tti表示第i臺(tái)機(jī)器人執(zhí)行系統(tǒng)任務(wù)所需的時(shí)間；tci表示第i臺(tái)向系統(tǒng)輸入任務(wù)到開始執(zhí)行規(guī)定任務(wù)所花費(fèi)的最少時(shí)間；表示在時(shí)間窗內(nèi)在路段jk上的機(jī)器人數(shù)；表示在時(shí)間窗內(nèi)在路段kj上的機(jī)器人數(shù)。

公式的含義：式（3）表示執(zhí)行任務(wù)的機(jī)器人不大于物流系統(tǒng)中的機(jī)器人數(shù)；式（4）和（5）表示在時(shí)間窗內(nèi)在路段jk上的機(jī)器人數(shù)；式（6）表示路徑總數(shù)大于物流系統(tǒng)中機(jī)器人數(shù)；式（7）表示在時(shí)間窗內(nèi)在路段jk上不存在沿相反方向行駛的機(jī)器人。

2.2 優(yōu)化后的遺傳算法

遺傳算法是一種智能優(yōu)化算法，主要用來解決優(yōu)化問題，其主要步驟為種群初始化、適應(yīng)度函數(shù)計(jì)算、選擇、交叉和變異。應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃時(shí)其主要步驟，流程圖如圖2所示。下面將對(duì)每步的方法做詳細(xì)介紹。

圖2 遺傳算法流程圖Fig.2 Flow chart of genetic algorithm

2.2.1 建立柵格地圖

在對(duì)機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，需要先建立地圖。本文通過柵格法建立空間地圖模型，柵格越密集，空間中各種環(huán)境信息表示越精確。

2.2.2 初始化種群

初始化種群要求隨機(jī)產(chǎn)生多條可行路徑，可行路徑表示不與障礙物柵格相碰撞的路徑?？尚新窂降漠a(chǎn)生分為兩個(gè)主要步驟。

首先產(chǎn)生一條間斷路徑。機(jī)器人每次行走一個(gè)柵格，因此每一行或者每一列至少有一個(gè)柵格在可行路徑中。所以初始化時(shí)先按順序在每一行或每一列隨機(jī)取出一個(gè)無障礙柵格，形成一條間斷的路徑。

第二步是將間斷的路徑連接為連續(xù)路徑。在這一步中首先從第一個(gè)柵格開始判斷相鄰的兩個(gè)柵格是否為連續(xù)柵格，柵格是否連續(xù)的判斷方法為：S=max{abs(xi+1-xi),abs(yi+1-yi)}。若S等于1則說明兩個(gè)相鄰柵格連續(xù)，反之不連續(xù)。

對(duì)于不連續(xù)的柵格取兩個(gè)柵格的中點(diǎn)柵格，中點(diǎn)柵格的坐標(biāo)計(jì)算為：

若中點(diǎn)柵格為障礙物柵格，則取相鄰柵格。如果相鄰柵格是障礙物柵格，則刪除這條路徑。如果中點(diǎn)柵格或者相鄰柵格為無障礙柵格且不在路徑中則插入路徑中，繼續(xù)判斷新插入的柵格和新插入的柵格的前一個(gè)柵格是否連續(xù)，若不連續(xù)則循環(huán)以上步驟，直到兩個(gè)柵格連續(xù)。當(dāng)兩個(gè)柵格連續(xù)后取下一個(gè)柵格，循環(huán)以上步驟，直到整條路徑連續(xù)。初始化一條路徑的流程圖如圖3所示。

圖3 初始化種群Fig.3 Initialized population

2.2.3 種群適應(yīng)度

適應(yīng)度函數(shù)分成兩部分，分別用來判斷路徑的長(zhǎng)短和平滑程度。路徑長(zhǎng)度的計(jì)算相對(duì)簡(jiǎn)單，公式如下：

要求的是機(jī)器人的路徑最短，而選擇方式采用的是輪盤賭的方式，所以適應(yīng)度函數(shù)的第一部分為：

機(jī)器人由于運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)的約束，行進(jìn)時(shí)拐彎不宜過大，并且相對(duì)平滑的路徑有利于機(jī)器人的行駛，因此產(chǎn)生的路徑有平滑度的要求。路徑之間的夾角越大，用來表示路徑夾角的三個(gè)點(diǎn)之間的距離就越大，路徑也就越平滑，計(jì)算公式如下：

d2的值可對(duì)應(yīng)路徑中連續(xù)三點(diǎn)的夾角的情況分別為180°和直角，其中180°的三點(diǎn)成一直線，平滑度最好，直角次之。對(duì)除直線外情況給予懲罰30，可以根據(jù)實(shí)際情況改動(dòng)懲罰的大小。懲罰之和的倒數(shù)即為適應(yīng)度函數(shù)的第二部分fit2。

適應(yīng)度函數(shù)的兩部分需要取一個(gè)權(quán)重，權(quán)重公式如下：

根據(jù)路徑長(zhǎng)度和平滑度之間的權(quán)重選擇參數(shù)a和b。

2.2.4 選擇方法

選擇方法采用簡(jiǎn)單的基于概率的輪盤賭方法。首先計(jì)算出所有個(gè)體的適應(yīng)度函數(shù)的和，再計(jì)算每一個(gè)個(gè)體所占的比率，計(jì)算公式如下：

然后根據(jù)每個(gè)個(gè)體的概率，以輪盤賭的方式選擇出下一代個(gè)體。為了防止遺傳算法陷入局部最優(yōu)解，通過輪盤賭的方法確保一部分非最優(yōu)個(gè)體。

2.2.5 交叉

首先需要確定一個(gè)交叉概率Pc，產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)，并和交叉概率Pc比較，若小于Pc則進(jìn)行交叉操作。交叉方式采用的是單點(diǎn)交叉的方式，具體的交叉操作是找出兩條路徑中所有相同的點(diǎn)，然后隨機(jī)選擇其中的一個(gè)點(diǎn)，將之后的路徑進(jìn)行交叉操作。具體的流程圖如圖4所示。

2.2.6 變異

首先需要確定一個(gè)變異概率Pm，產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)，并和變異概率Pm比較，若小于Pm則進(jìn)行變異操作。變異方法是隨機(jī)選取路徑中除起點(diǎn)和終點(diǎn)以外的兩個(gè)柵格，將這兩個(gè)點(diǎn)進(jìn)行連續(xù)操作。此時(shí)有可能無法產(chǎn)生連續(xù)的路徑，則需要重新選擇兩個(gè)柵格執(zhí)行以上操作，直到完成變異操作。具體的流程圖如圖5所示。

圖4 交叉操作流程圖Fig.4 Crossover operation flow chart

圖5 變異操作流程圖Fig.5 Mutation operation flow chart

2.2.7 算法說明

在Matlab 2018a，i7-9700KF的CPU環(huán)境下進(jìn)行仿真。改進(jìn)遺傳算法的平均計(jì)算時(shí)間與路徑長(zhǎng)度之間的關(guān)系，如表1所示。

2.3 基于時(shí)間窗的算法流程

當(dāng)系統(tǒng)中輸入任務(wù)時(shí)，機(jī)器人路徑規(guī)劃系統(tǒng)都會(huì)根據(jù)任務(wù)設(shè)定的優(yōu)先級(jí)對(duì)整體任務(wù)進(jìn)行規(guī)劃。該算法流程是：

表1 時(shí)間與路徑長(zhǎng)度之間的關(guān)系Table 1 Relationship between time and path length

（1）向系統(tǒng)中導(dǎo)入任務(wù)列表。

（2）找出優(yōu)先級(jí)順序與時(shí)間順序相符的任務(wù)和優(yōu)先級(jí)順序與時(shí)間順序不相符的任務(wù)。

（3）優(yōu)先級(jí)較高的任務(wù)在執(zhí)行完當(dāng)前任務(wù)是否能參與次一級(jí)任務(wù)從當(dāng)前?？奎c(diǎn)到達(dá)任務(wù)出發(fā)點(diǎn)的運(yùn)行。時(shí)間順序較早的任務(wù)在執(zhí)行完當(dāng)前任務(wù)是否能參與優(yōu)先級(jí)較高任務(wù)從當(dāng)前?？奎c(diǎn)到達(dá)任務(wù)出發(fā)點(diǎn)的運(yùn)行。

（4）明確各個(gè)機(jī)器人的任務(wù)分配，根據(jù)優(yōu)化后的遺傳算法確定運(yùn)輸線路。

（5）在步驟（4）的基礎(chǔ)上，判斷各個(gè)任務(wù)從開始到結(jié)束的運(yùn)輸線路是否存在重合的節(jié)點(diǎn)。如果存在，根據(jù)重合節(jié)點(diǎn)數(shù)判斷沖突的類型，如果不存在，跳轉(zhuǎn)到步驟（8）。

（6）如果機(jī)器人在同一條線路上重合的節(jié)點(diǎn)數(shù)等于1表明可能存在交叉沖突。交叉沖突如圖6所示。通過機(jī)器人通過交叉節(jié)點(diǎn)的時(shí)間判斷是否存在交叉沖突。如果存在交叉沖突，次優(yōu)先級(jí)任務(wù)選擇等待和重新規(guī)劃路徑，通過比較選擇較好的方案。

圖6 交叉沖突Fig.6 Cross conflict

（7）如果機(jī)器人在同一條線路上重合的節(jié)點(diǎn)數(shù)大于等于2且順序相同表明可能存在同向沖突，同向沖突如圖7所示。判斷所容納的數(shù)量是否小于道路承受能力，來確定是否存在同向沖突。任務(wù)，時(shí)間成本太高，對(duì)優(yōu)先級(jí)高的任務(wù)進(jìn)行線路規(guī)劃，路徑增加則放棄當(dāng)前新路徑。以上情況都不滿足，再次對(duì)優(yōu)先級(jí)低的任務(wù)選擇等待和重新進(jìn)行路徑規(guī)劃，選擇出最優(yōu)路徑。

圖7 同向沖突Fig.7 Co-direction conflict

（8）如果機(jī)器人在同一條線路上重合的節(jié)點(diǎn)數(shù)大于等于2且順序相反表明可能存在相向沖突，相向沖突如圖8所示。通過機(jī)器人通過相向沖突節(jié)點(diǎn)的時(shí)間判斷是否存在交叉沖突。如果存在交叉沖突，依照任務(wù)的優(yōu)先級(jí)從低到高的順序，選擇等待和重新規(guī)劃優(yōu)先級(jí)低的

圖8 相向沖突Fig.8 Opposing conflict

（9）得出最優(yōu)路徑。

3 對(duì)基于時(shí)間窗的算法進(jìn)行驗(yàn)證計(jì)算

3.1 情景說明

隨著貨物數(shù)量的爆炸性增長(zhǎng)和用工成本的不斷增加，更高效的倉(cāng)儲(chǔ)和物流系統(tǒng)就成為越來越多企業(yè)的首選?，F(xiàn)在簡(jiǎn)化了一個(gè)大型倉(cāng)庫(kù)，如圖9所示。

圖9 倉(cāng)庫(kù)作業(yè)的路網(wǎng)結(jié)構(gòu)和作業(yè)站點(diǎn)Fig.9 Road network structure and operation sites

任務(wù)1、任務(wù)2、任務(wù)3和任務(wù)4是4個(gè)即將輸入系統(tǒng)任務(wù)，具體任務(wù)為見表2，優(yōu)先級(jí)數(shù)字越小優(yōu)先級(jí)越高。物流系統(tǒng)中有4臺(tái)機(jī)器人分別是機(jī)器人1、機(jī)器人2、機(jī)器人3和機(jī)器人4。當(dāng)前處于空載空閑狀態(tài)，?？奎c(diǎn)分別是在9、4、15和55號(hào)站點(diǎn)等待系統(tǒng)調(diào)用。

表2 機(jī)器人系統(tǒng)作業(yè)任務(wù)表Table 2 Task list of robot system

3.2 最優(yōu)路徑計(jì)算

3.2.1 最優(yōu)任務(wù)分配和確定運(yùn)輸線路

根據(jù)遺傳算法，可以計(jì)算出機(jī)器人到起點(diǎn)的相應(yīng)最短路徑以及最短的行駛時(shí)間。通過比較確定任務(wù)分配的機(jī)器人，在此基礎(chǔ)上計(jì)算完成任務(wù)所需的時(shí)間。

分別計(jì)算任務(wù)1、任務(wù)2、任務(wù)3和任務(wù)4調(diào)用機(jī)器人到達(dá)各自任務(wù)起點(diǎn)的路徑，如表3～6所示。

表3 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)11的優(yōu)化路徑Table 3 Optimized path of robots 1，2，3，4 to point 11

表4 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)13的優(yōu)化路徑Table 4 Optimized path of robots 1，2，3，4 to point 13

表5 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)19的優(yōu)化路徑Table 5 Optimized path of robots 1，2，3，4 to point 19

表6 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)54的優(yōu)化路徑Table 6 Optimized path of robots 1，2，3，4 to point 54

執(zhí)行任務(wù)1時(shí)，分別計(jì)算機(jī)器人1、機(jī)器人2、機(jī)器人3、機(jī)器人4到達(dá)起點(diǎn)11的時(shí)間。因?yàn)闄C(jī)器人1執(zhí)行任務(wù)1任務(wù)所花費(fèi)的時(shí)間最少，所以選擇機(jī)器人1執(zhí)行任務(wù)1。

使用機(jī)器人1計(jì)算任務(wù)2時(shí)，機(jī)器人1已經(jīng)完成任務(wù)1，因此需要從308.04 s開始計(jì)算。通過對(duì)比發(fā)現(xiàn)機(jī)器人2到達(dá)起始點(diǎn)13的時(shí)間所花費(fèi)的時(shí)間最少，因此選擇機(jī)器人2執(zhí)行Task2任務(wù)。

機(jī)器人1和機(jī)器人2必須先完成任務(wù)1和任務(wù)2，才能夠執(zhí)行任務(wù)3。任務(wù)3的優(yōu)先級(jí)高于任務(wù)4，任務(wù)4的開始執(zhí)行時(shí)間早于任務(wù)3。分別計(jì)算機(jī)器人1、機(jī)器人2、機(jī)器人3、機(jī)器人4到達(dá)任務(wù)3起始點(diǎn)19的時(shí)間，機(jī)器人3所花費(fèi)的時(shí)間最少。在上述基礎(chǔ)上，執(zhí)行任務(wù)4。當(dāng)執(zhí)行完任務(wù)4，機(jī)器人4到達(dá)起始點(diǎn)19的時(shí)間大于機(jī)器人3到達(dá)任務(wù)3起始點(diǎn)19所花費(fèi)的時(shí)間。選擇機(jī)器人3執(zhí)行任務(wù)3。

最優(yōu)任務(wù)分配：任務(wù)1選擇機(jī)器人1；任務(wù)2選擇機(jī)器人2；任務(wù)3選擇機(jī)器人3；任務(wù)4選擇機(jī)器人4。它們到達(dá)起始點(diǎn)的路徑分別是9-10-11、4-14-13、15-14-19和55-54。運(yùn)輸線路：任務(wù)1的運(yùn)輸線路：9-10-11-12-13-14-19-24-25-26-27-28；任務(wù)2的運(yùn)輸線路：4-14-13-12-18-22-33-38；任務(wù)3的運(yùn)輸線路：15-14-19-24-25-35-34；任務(wù)4的運(yùn)輸線路：55-54-53-46-40-36-27-26。

3.2.2 當(dāng)前線路時(shí)間窗

系統(tǒng)當(dāng)前線路時(shí)間窗結(jié)果如表7～10所示。

表7 機(jī)器人1執(zhí)行任務(wù)1的優(yōu)化路徑Table 7 Optimized path of robot 1 to perform task 1

表8 機(jī)器人2執(zhí)行任務(wù)2的優(yōu)化路徑Table 8 Optimized path of robot 2 to perform task 2

表9 機(jī)器人3執(zhí)行任務(wù)3的優(yōu)化路徑Table 9 Optimized path of robot 3 to perform task 3

表10 機(jī)器人4執(zhí)行任務(wù)4的優(yōu)化路徑Table 10 Optimized path of robot 4 to perform task 4

3.2.3 優(yōu)化當(dāng)前線路時(shí)間窗沖突

分析任務(wù)發(fā)生沖突的時(shí)間窗詳細(xì)情況如下：

（1）任務(wù)1

機(jī)器人1與機(jī)器人2：

機(jī)器人1與機(jī)器人3：

機(jī)器人1與機(jī)器人4：

（2）任務(wù)2

機(jī)器人2與機(jī)器人1：

（3）任務(wù)3

機(jī)器人3與機(jī)器人1：

（4）任務(wù)4：

機(jī)器人4與機(jī)器人1：

在路徑12-13和13-14上，機(jī)器人1和機(jī)器人2某一時(shí)間段內(nèi)沿相反方向行駛。機(jī)器人1和機(jī)器人3在路徑14-19、19-24和24-25上沿相同方向行駛。機(jī)器人1和機(jī)器人4沿相反方向行駛。

解決線路沖突的方法主要有以下兩種：避讓和嘗試新的線路，通過嘗試兩種可能方案，選擇花費(fèi)時(shí)間較短的作為最優(yōu)方案。

（1）避讓

當(dāng)機(jī)器人1按照任務(wù)1規(guī)劃的線路行駛和機(jī)器人2按照任務(wù)2規(guī)劃的線路行駛時(shí)，在節(jié)點(diǎn)12-13-14處產(chǎn)生碰撞。為避免該碰撞，將如任務(wù)2的時(shí)間節(jié)點(diǎn)后移動(dòng)，至少需要推遲的時(shí)間是100 s。

（2）嘗試新的線路

路徑的發(fā)生沖突時(shí)，依照任務(wù)的優(yōu)先級(jí)從低到高的順序，重新規(guī)劃優(yōu)先級(jí)低的任務(wù)，路徑增加則放棄當(dāng)前新路徑，對(duì)優(yōu)先級(jí)高的任務(wù)進(jìn)行線路規(guī)劃，路徑增加則放棄當(dāng)前新路徑。以上情況都不滿足，再次對(duì)優(yōu)先級(jí)低的任務(wù)重新進(jìn)行路徑規(guī)劃。對(duì)比新路徑和在當(dāng)前路徑基礎(chǔ)上進(jìn)行避讓，選擇出最優(yōu)路徑。

任務(wù)2的優(yōu)先級(jí)低于任務(wù)1，因此重新對(duì)任務(wù)2進(jìn)行線路規(guī)劃。新路徑大于原路徑，轉(zhuǎn)而尋找任務(wù)1的新路徑。結(jié)果如下：任務(wù)1的路徑是9-10-11-12-18-22-23-24-25-26-27-28；任務(wù)2的路徑是4-14-13-12-18-22-33-38。機(jī)器人1和機(jī)器人2在執(zhí)行任務(wù)1和任務(wù)2時(shí)，避免了在線路12-13-14沖突。

對(duì)于26-27路徑的沖突，因任務(wù)4優(yōu)先級(jí)更低，對(duì)任務(wù)4重新進(jìn)行路徑規(guī)劃，見表11。運(yùn)輸路徑是55-54-53-52-45-39-35-25-26，所花費(fèi)時(shí)間310.61 s。在原路徑基礎(chǔ)上進(jìn)行等待，生成的路徑是55-54-53-46-40-36（等待）-27-26，所花費(fèi)時(shí)間260.61 s。在解決了沖突后，任務(wù)1和4的時(shí)間窗口如表12和13所示。

表11 機(jī)器人4執(zhí)行任務(wù)4重新進(jìn)行路徑規(guī)劃Table 11 Robot 4 performing task 4 and re-planning path

表12 任務(wù)1最優(yōu)路徑（優(yōu)化后）Table 12 Optimal path of task 1（Optimized）

表13 任務(wù)4最優(yōu)路徑（優(yōu)化后）Table 13 Optimal path of task 4（Optimized）

機(jī)器人4的等待時(shí)間：280.32-246.61+2=35.71 s。

新路徑的可能沖突的時(shí)間窗詳細(xì)分析：

（1）任務(wù)1

機(jī)器人1與機(jī)器人2：

機(jī)器人1與機(jī)器人3：

機(jī)器人1與機(jī)器人4：

（2）任務(wù)2

機(jī)器人2與機(jī)器人1：

（3）任務(wù)3

機(jī)器人3與機(jī)器人1：

（4）任務(wù)4

機(jī)器人4與機(jī)器人1：

任務(wù)1和任務(wù)4的新路徑所花費(fèi)的時(shí)間增多，分別是310.32-308.04=2.28 s，320.61-306.32=14.29 s。

任務(wù)1重新規(guī)劃路徑增加的2.28 s在可接受范圍內(nèi)，如果任務(wù)1不重新規(guī)劃，任務(wù)2將會(huì)推遲100 s。任務(wù)4重新規(guī)劃路徑增加的15.9 s大于推遲時(shí)間窗的11.5 s，故對(duì)任務(wù)4使用等待的方法來避免沖突。

4 結(jié)束語

通過對(duì)單車道雙向多機(jī)器人路徑規(guī)劃問題進(jìn)行研究，提出了一種基于時(shí)間窗的算法流程，同時(shí)通過一個(gè)模型進(jìn)行驗(yàn)證證明了算法流程的有效性。為多機(jī)器人協(xié)同作業(yè)，提供了新的選擇。未來將進(jìn)一步對(duì)多機(jī)器人協(xié)同作業(yè)進(jìn)行研究，為了進(jìn)一步提高效率可以讓各機(jī)器人預(yù)先出發(fā)，從而為執(zhí)行任務(wù)進(jìn)一步節(jié)約時(shí)間。以及不同性能的雙車道雙向機(jī)器人以及機(jī)器人在交叉路口相遇，在保證安全的前提下如何避障。