考慮故障因素的多機(jī)器人動(dòng)態(tài)任務(wù)分配及路徑規(guī)劃

Multi-root dynmic tsk lloction nd pth plnning considering fult fctors

He Zhou'?，He Pengyang（a.Colegeoficalamp;tllallEiUesiegy，Xi'an 710021，China）

Abstract：Toaddress therobustness problem of multiplerobots incomplex tasks，，this paper proposedacoupled task llcationand path planning method to adressthetrajectoryrequirementsundersuchtasks.Firstly，the Dijkstraalgorithmpreprocesed the shortestpathsand distances between task grids inenvironments.Secondly，whenthecentral controlermonitored the robotenteringthedangerzoneandfailure，itwasresponsibleforreal-timetask assignmentandenvironmentupdates toensuretask completion.Inaddition，it proposedanimproved northern goshawkoptimizationalgorithm（INGO）withlocaladjustment strategies inconjunction withaneighbourhoodsearchtoimprovethesolutionquality，andanauctionmethod incorporatingmarginalcosthandledtherootfailurereassignmentproblem.Finally，itconductedrandomtestsunderdiferentmapsizes and numbers of tasks. In 1OO-grid environment，the proposed method saved 19.63% of the total traveled distance compared to the auction method，andthesolutiontime wasshorter thanthatoftheothermethods.Theresultsdemonstratethatthe method beterbalances the travellingdistanceand solution time，whilealsooutperforming existing methods interms ofscalabilityand system robustness.

Key words：multi-robot system；task planning；system robustness； robot failure；path planning

0引言

多機(jī)器人系統(tǒng)（multi-robotsystem，MRS），由于其相對(duì)于單機(jī)器人系統(tǒng)在工作效率、靈活性等方面的優(yōu)勢(shì)而受到廣泛關(guān)注[1，2]。目前MRS已被廣泛應(yīng)用于倉(cāng)儲(chǔ)、救援、巡檢監(jiān)測(cè)等領(lǐng)域[3-5]。作為MRS 的核心，任務(wù)分配和路徑規(guī)劃等問(wèn)題已受到廣泛關(guān)注。將系統(tǒng)的高級(jí)任務(wù)分解成子任務(wù)再分配給機(jī)器人的過(guò)程稱為多機(jī)器人任務(wù)分配（multi-robottaskallocation，MRTA）。在大多數(shù)MRTA問(wèn)題中，僅考慮避開(kāi)障礙物的同時(shí)最小化系統(tǒng)的目標(biāo)函數(shù)，如移動(dòng)距離、求解時(shí)間等[6＼～8]?，F(xiàn)實(shí)中，機(jī)器人對(duì)環(huán)境的感知可能是不準(zhǔn)確的，會(huì)存在一定的危險(xiǎn)性，從而對(duì)機(jī)器人產(chǎn)生影響，因此動(dòng)態(tài)任務(wù)分配問(wèn)題就變得具有挑戰(zhàn)性。Dai等人[9研究了MRTA下的軍事對(duì)抗問(wèn)題，機(jī)器人收到任務(wù)指令后，對(duì)環(huán)境搜索的同時(shí)要摧毀隱藏在環(huán)境中的目標(biāo)，而目標(biāo)也可能對(duì)機(jī)器人造成損壞，系統(tǒng)需要重新考慮下發(fā)任務(wù)，并開(kāi)發(fā)出基于競(jìng)拍、空缺鏈和DeepQ-leaming的方法。

針對(duì)在執(zhí)行任務(wù)過(guò)程中機(jī)器人損壞的情況，Huang等人[1]在有限個(gè)機(jī)器人損壞的假設(shè)下，通過(guò)構(gòu)建過(guò)渡系統(tǒng)和自動(dòng)機(jī)，提出一種有效的任務(wù)分配策略，在滿足故障機(jī)器人數(shù)量上限的情況下，保證任務(wù)的魯棒性要求。進(jìn)一步考慮到運(yùn)動(dòng)不確定的情況，Cai等人[]將機(jī)器人的運(yùn)動(dòng)建模為具有未知轉(zhuǎn)移概率的馬爾可夫決策過(guò)程，結(jié)合強(qiáng)化學(xué)習(xí)方法，提出一種最大化概率滿足任務(wù)的策略。

近幾年，隨著問(wèn)題的日益復(fù)雜，點(diǎn)對(duì)點(diǎn)的單機(jī)器人規(guī)劃方法早已無(wú)法支持多機(jī)器人系統(tǒng)對(duì)復(fù)雜行為的需求[12.13]，具有高規(guī)格MRS的任務(wù)分配已經(jīng)成為重要的研究課題。線性時(shí)序邏輯和布爾規(guī)范這類形式化的方法被用于描述高規(guī)格的復(fù)雜任務(wù)[14-17]。線性時(shí)序邏輯描述下的 MRS更多關(guān)注的是任務(wù)的滿足情況。李保羅等人[18]針對(duì)復(fù)雜環(huán)境下巡回任務(wù)的要求，使用線性時(shí)序邏輯描述任務(wù)，將其轉(zhuǎn)換為自動(dòng)機(jī)，并開(kāi)發(fā)出一種安全強(qiáng)化學(xué)習(xí)算法，但其構(gòu)建過(guò)程較為復(fù)雜，不適合在大地圖中應(yīng)用。當(dāng)不需要考慮無(wú)限巡回時(shí)，可使用布爾規(guī)范簡(jiǎn)潔地描述復(fù)雜任務(wù)。Mahulea等人[19]利用 Petri 網(wǎng)對(duì)MRS建模，使用布爾規(guī)范進(jìn)行任務(wù)描述，并結(jié)合整數(shù)線性規(guī)劃求解最優(yōu)路徑，但該方法隨任務(wù)和機(jī)器人數(shù)量的遞增會(huì)導(dǎo)致?tīng)顟B(tài)爆炸。針對(duì)以上問(wèn)題，Shi等人[20]結(jié)合模擬退火算法，有效解決了大規(guī)模地圖中路徑規(guī)劃的問(wèn)題。進(jìn)一步地，何舟等人[21]考慮了布爾任務(wù)的時(shí)間窗要求，提出一種融合 A^* 算法和回退機(jī)制的改進(jìn)蟻群算法來(lái)為MRS規(guī)劃路徑，但是上述研究均沒(méi)有考慮機(jī)器人故障的情況。

基于此，本文提出一種考慮故障因素的多機(jī)器人任務(wù)分配及路徑規(guī)劃方法。首先，使用Dijkstra算法計(jì)算任務(wù)柵格間的最短路徑和距離；然后，提出一種改進(jìn)北方蒼鷹優(yōu)化算法為MRS分配任務(wù)；控制器負(fù)責(zé)實(shí)時(shí)更新環(huán)境，并以拍賣的形式處理故障后的任務(wù)。通過(guò)仿真，證明本文方法在考慮機(jī)器人故障的因素下，能有效解決復(fù)雜任務(wù)分配和路徑規(guī)劃問(wèn)題。

1問(wèn)題描述和假設(shè)

1.1 問(wèn)題假設(shè)

1）機(jī)器人假設(shè)

集合 R={r₁，r₂，…，r_k} 表示MRS具有 k 個(gè)執(zhí)行復(fù)雜任務(wù)能力的機(jī)器人（所有機(jī)器人完全相同），機(jī)器人的速度為1，一次可執(zhí)行多個(gè)任務(wù)，且不考慮機(jī)器人能源問(wèn)題。

2）任務(wù)假設(shè)

考慮的任務(wù)包括途徑任務(wù)和終點(diǎn)任務(wù)，終點(diǎn)任務(wù)需要在途徑任務(wù)完成后執(zhí)行，每個(gè)任務(wù)只需要任意一個(gè)機(jī)器人執(zhí)行，并且同一任務(wù)可以在對(duì)應(yīng)任務(wù)區(qū)域內(nèi)的任意一個(gè)位置完成。

3）環(huán)境假設(shè)

機(jī)器人對(duì)任務(wù)區(qū)域的位置分布已知，但任務(wù)區(qū)域附近隨機(jī)分布著一些危險(xiǎn)區(qū)域，機(jī)器人對(duì)危險(xiǎn)區(qū)域沒(méi)有先驗(yàn)的信息，在進(jìn)入危險(xiǎn)區(qū)域后，服從一定概率分布使機(jī)器人故障。

4）故障假設(shè)

機(jī)器人故障是屬于MRS魯棒性的一類問(wèn)題，本文考慮機(jī)器人故障后是不可修復(fù)的。

1.2 環(huán)境建模

環(huán)境建模是將機(jī)器人真實(shí)運(yùn)行的三維場(chǎng)景抽象為二維的數(shù)字地圖，來(lái)模擬機(jī)器人工作的過(guò)程，常見(jiàn)的環(huán)境建模方法包括可視圖法、三角分割法和柵格法等。其中，柵格法因其簡(jiǎn)單有效且對(duì)環(huán)境適應(yīng)性強(qiáng)的特點(diǎn)，特別適用于機(jī)器人執(zhí)行的復(fù)雜任務(wù)環(huán)境。因此，在本文的研究中，選擇柵格法進(jìn)行環(huán)境建模。

本文將MRS運(yùn)行的真實(shí)環(huán)境柵格劃分為 n 個(gè)尺寸相等的小柵格，用集合 C={c₁，c₂，…，c_n} 表示。柵格環(huán)境中機(jī)器人只在水平方向上移動(dòng)，并且相鄰柵格之間的距離為1。如對(duì)圖1（a）一真實(shí)的三維環(huán)境柵格劃分后，可得到圖1（b）的柵格地圖。

1.3 預(yù)處理方法

Dijkstra算法作為一種常見(jiàn)的圖搜索算法，可以得到最優(yōu)路徑。因此，本節(jié)使用Dijkstra算法計(jì)算任務(wù)區(qū)域內(nèi)不同柵格

c_i 和 c_j 之間的最短路徑 L（c_i，c_j） 和最短距離 D（c_i，c_j） 。首先構(gòu)建鄰接矩陣 M 存儲(chǔ)相鄰柵格間的距離 d_i，j，M 為一個(gè) n 維方陣：

其中： d_i，j=1（c_i 與 c_j 相鄰， i≠j） d_i，j=∞ （ c_i 與 c_j 不相鄰， i≠ j） 。最后通過(guò)Dijkstra算法將得到的最短路和距離分別存儲(chǔ)在集合 L 和 D 中。

1.4布爾規(guī)范的任務(wù)描述

本文考慮的復(fù)雜任務(wù)由布爾規(guī)范進(jìn)行描述，T，={（cs，r₁），（c_s2，r₂），…，（c_sk，r_k）| 為 MRS 的初始柵格集合，其中（ {c_si ，r_i ）為機(jī)器人 i 對(duì)應(yīng)的初始位置 為危險(xiǎn)區(qū)域所包含的柵格集合， c′_i∈C ;將環(huán)境中的任務(wù)區(qū)域劃分為 ，其中 表示途徑任務(wù)區(qū)域集合 表示終點(diǎn)任務(wù)區(qū)域集合，每一個(gè)途徑任務(wù)區(qū)域 和終點(diǎn)任務(wù)區(qū)域 π_i（i=1，…，q） 由一個(gè)或多個(gè)表示相同任務(wù)的柵格組成， .II_i∈C，π_i∈CP_t= {π₁，π₂，…，π_p} 和 P_f={π₁，π₂，…，π_q} 為布爾規(guī)范原子命題的有限集合， ??π_i 表示途徑任務(wù)區(qū)域 π_i 需要在機(jī)器人軌跡中被訪問(wèn)， π_i 表示機(jī)器人沿軌跡需要最后停留在終點(diǎn)區(qū)域 π_i 。布爾規(guī)范可用于描述包含“與”、“或”、“非”邏輯的復(fù)雜任務(wù)，其中原子命題通過(guò)聯(lián)結(jié)詞 Λ （合?。?、 V （析取） （否定）連接，復(fù)雜任務(wù)由布爾規(guī)范公式 φ 進(jìn)行描述：

φ=T∧U∧A

a）子規(guī)范 T 表述為途徑任務(wù)的邏輯要求：

其中 表示沿機(jī)器人軌跡需要至少訪問(wèn)一次 P_t 中原子命題對(duì)應(yīng)的一個(gè)任務(wù)區(qū)域； P_T=∪_i=1^mP_ti 為途徑任務(wù)柵格集合；（204號(hào) P_Δti={c|c∈∪_πΔτiII} 為原子命題 中對(duì)應(yīng)的任務(wù)柵格集合。

b）子規(guī)范 U 表述為禁止區(qū)域的邏輯要求：

其中： P_u∈P_t 表示沿機(jī)器人軌跡需要始終避開(kāi) P_u 中原子命題對(duì)應(yīng)的區(qū)域。 為需要避開(kāi)的柵格集合。

c）子規(guī)范 A 表述為終點(diǎn)任務(wù)區(qū)域的邏輯要求：

其中： Σ_：Paj∈Pf 表示沿機(jī)器人軌跡需要最終停留在 P_aj 中原子命題對(duì)應(yīng)的區(qū)域。 P_A=?_j=1^gP_aj 為終點(diǎn)任務(wù)柵格集合，其中 P_aj= （204號(hào) {c|c∈∪_π∈PajII} 表示原子命題 II∈P_aj 中對(duì)應(yīng)的任務(wù)柵格集合。

在圖2給出的示例中，地圖環(huán)境由36個(gè)柵格組成， C= {c₁，…，c₃₆} ，機(jī)器人初始位置柵格集合 T_s={（c₁₅，r₁） ， c₁₆ ，r₂），（c₂₁，r₃）} ，危險(xiǎn)區(qū)域柵格集合 T_d={c₁₇，c₃₃} 。途徑任務(wù)區(qū)域集合 Ω_t={I₁，II₂，II₃，II₄，II₅，II₆} ，終點(diǎn)任務(wù)區(qū)域集合 。其中 Π₁={c₆，c₁₂}，Π₂={c₂₅，c₃₁} 分別表示途中的橙色和藍(lán)色區(qū)域， 和 Π₄={c₃₅} 表示圖中的粉色區(qū)域 II₅={c₂₃，c₂₄} 和 表示圖中的灰色區(qū)域， π₁= {c₁，c₂，c₃} 表示圖中的綠色區(qū)域。原子命題集合 ，H₂，H₃，H₄，H₅，H₆} ， P_f={π₁} 。

子規(guī)范 表示機(jī)器人在移動(dòng)過(guò)程中沿軌跡需要訪問(wèn)這些區(qū)域執(zhí)行任務(wù)。

子規(guī)范 （ ），表示由已知信息，這些區(qū)域無(wú)法通過(guò)，為保證安全，機(jī)器人在移動(dòng)過(guò)程中沿軌跡需要始終避開(kāi) 和 π₆ 區(qū)域。

子規(guī)范 A=π₁ ，表示在考慮MRS魯棒性前提下，至少需要有一個(gè)機(jī)器人能執(zhí)行完所有任務(wù)，到達(dá)終點(diǎn)區(qū)域 π₁ 。

最后給出示例中MRS的布爾規(guī)范 φ 為

表示至少有一個(gè)機(jī)器人沿軌跡需要訪問(wèn)橙色區(qū)域 和紫色區(qū)域 ，至少訪問(wèn)一個(gè)粉色區(qū)域 或 π_* ，最后需要至少一個(gè)機(jī)器人停留在綠色區(qū)域 π₁ ，并且始終避開(kāi)灰色區(qū)域 和 π₆ （見(jiàn)電子版），進(jìn)入危險(xiǎn)區(qū)域的機(jī)器人則有一定的故障概率。

2 任務(wù)編碼與解碼

在MRS中，任務(wù)由中央控制器以編碼的形式下發(fā)，解碼后機(jī)器人獲得對(duì)任務(wù)柵格的訪問(wèn)序列，最后根據(jù)預(yù)處理方法得到每個(gè)機(jī)器人對(duì)應(yīng)柵格序列的詳細(xì)路徑。

1）編碼

編碼 Code=[?C_t，?C_f] 中的 C_t 和 C_f 分別用于存儲(chǔ)MRS中途徑任務(wù)和終點(diǎn)任務(wù)的信息。其中C，=[t，，t1，2，，1，m1，0，…，t_i，1，t_i，2，…，t_i，ni，0，…，t_k，1，t_k，2，…，t_k，nk，0] 是一個(gè) （m+k） （204維的非負(fù)整數(shù)行向量，表示機(jī)器人需要沿軌跡訪問(wèn)布爾子規(guī)范T 給出的 m 個(gè)表示不同途徑任務(wù)的區(qū)域， k 個(gè)0作為 k 個(gè)機(jī)器人分配任務(wù)結(jié)束的標(biāo)識(shí)， C_t 中的每一個(gè) t_i，j 對(duì)應(yīng)唯一的單元格Ctj∈Pr。Cf=[f1f，，]是一個(gè)k維的非負(fù)整數(shù)行向量，表示執(zhí)行完任務(wù)的機(jī)器人沿軌跡最終停留在對(duì)應(yīng)的終點(diǎn)任務(wù)柵格上， C_f 中的每一個(gè) f_j 都唯一對(duì)應(yīng)一個(gè)終點(diǎn)任務(wù)柵格

2）解碼

途徑任務(wù) C_t 的解碼，對(duì)第i-1個(gè)與第 i 個(gè)0之間的正整數(shù) t_i，1，t_i，2，…，t_i，ni ，可以解碼為第 i 個(gè)機(jī)器人沿軌跡依次訪問(wèn)柵格 c_ti，1，c_ti，2，…，c_ti，ni 的序列。對(duì)于終點(diǎn)任務(wù) C_f 的解碼，第 χ_i 個(gè)正整數(shù) f_j 可以解碼為第 i 個(gè)機(jī)器人沿軌跡最終停留在終點(diǎn)柵格 c_fj 上。因此，從解碼后的MRS 任務(wù)集合 T_E=∪_i=1^kT_i 中可得到每個(gè)機(jī)器人沿軌跡需要依次訪問(wèn)的柵格序列Ti =cti，，c_ti，2，…，c_ti，ni，c_fj（i=1，…，k）

若編碼 Code 中， C_t=[35，0，6，0，31，0] 和 ，解碼后可得到每個(gè)機(jī)器人訪問(wèn)的柵格序列，T=C35，c1，T=c₆，c₃，T₃=c₃₁，c₂，T₁ 表示機(jī)器人 r₁ 從初始柵格 c₁₅ 位置開(kāi)始，沿軌跡首先訪問(wèn)粉色區(qū)域包含的柵格 c₃₅ ，最后停留在綠色區(qū)域包含的柵格 c₁ 上。具體過(guò)程可參考文獻(xiàn)［20]。

3任務(wù)分配策略

本章針對(duì)故障因素下MRS的復(fù)雜任務(wù)分配問(wèn)題，開(kāi)發(fā)出一種結(jié)合改進(jìn)北方蒼鷹優(yōu)化算法和拍賣方法的分配策略，在有效應(yīng)對(duì)故障問(wèn)題的同時(shí)，均衡考慮MRS的移動(dòng)距離和求解時(shí)間。首先，對(duì)任務(wù)編碼后，使用北方蒼鷹優(yōu)化算法迭代更新得到一個(gè)較優(yōu)的任務(wù)編碼，進(jìn)一步提出一種局部調(diào)整策略提高任務(wù)編碼的質(zhì)量。解碼后，結(jié)合預(yù)處理方法，求解出從初始位置柵格依次到各任務(wù)柵格之間的最短路徑。此后，中央控制器實(shí)時(shí)更新任務(wù)的完成情況，監(jiān)測(cè)到機(jī)器人故障后，以拍賣的形式下發(fā)任務(wù)，來(lái)應(yīng)對(duì)機(jī)器人故障后的任務(wù)重分配問(wèn)題。

3.1改進(jìn)北方蒼鷹優(yōu)化算法的任務(wù)分配策略

北方蒼鷹優(yōu)化算法（northern goshawk optimization，NGO）具有收斂速度快、魯棒性好的特點(diǎn)，算法主要由初始化、識(shí)別階段和追擊階段三個(gè)部分組成。識(shí)別階段為算法對(duì)搜索空間進(jìn)行勘探，盡可能找到每一個(gè)有希望存在全局最優(yōu)解的區(qū)域，追擊階段為在有可能找到最優(yōu)解的區(qū)域內(nèi)繼續(xù)尋找最優(yōu)解。

a）初始化，集合 X=[X₁，X₂，…，X_N] 為種群中的 N 個(gè)個(gè)體，每個(gè)個(gè)體X對(duì)應(yīng)一組任務(wù)編碼，集合F（X）=[Fx，，F(xiàn)xF_XN] 為對(duì)應(yīng)的目標(biāo)函數(shù)，目標(biāo)函數(shù)的定義如式（7）所示。

為所有機(jī)器人訪問(wèn)任務(wù)柵格的最短距離之和。

優(yōu)化過(guò)程使用編碼中 t_i，j 和 f_j 對(duì)應(yīng)的代價(jià)估值計(jì)算更新，定義為 k 個(gè)機(jī)器人初始位置柵格到任務(wù)柵格歐氏距離的均值：

其中： g_i，j 和 h_j 分別為途徑任務(wù)柵格和終點(diǎn)任務(wù)柵格對(duì)應(yīng)的代價(jià)估值； x 和 y 分別為對(duì)應(yīng)柵格在地圖的橫縱坐標(biāo)。更新過(guò)程如圖3所示。

b）在識(shí)別階段，通常是隨機(jī)選擇一個(gè)體作為參考個(gè)體進(jìn)行更新，該方法雖然可以加快算法收斂，但也會(huì)產(chǎn)生算法的盲目性，在本問(wèn)題中考慮一種最佳值引導(dǎo)策略，即把當(dāng)前迭代中目標(biāo)函數(shù)最小的個(gè)體 X_N^best 作為參考個(gè)體，目標(biāo)函數(shù)滿足 F_X^bestlt; F_Xi ，根據(jù)式（9）進(jìn)行更新：

x_i，j^newl=x_i，j+r×（b_i，j-I×x_i，j）

其中 ：x_i，j 為 X_i 中第 i 個(gè)機(jī)器人第 j 個(gè)正整數(shù) t_i，j 的代價(jià)估值； b_i，j 為 X_N^best 中第 i 個(gè)機(jī)器人第 j 個(gè)正整數(shù) t^′_i，j 的代價(jià)估值； r 為[0，1]的隨機(jī)數(shù)； I 在1和2間隨機(jī)取值； x_i，j^new1 為識(shí)別階段后的代價(jià)值。

c）在追擊階段，針對(duì)NGO算法在迭代后期易陷入局部最優(yōu)的問(wèn)題，利用柯西分布函數(shù)在原點(diǎn)處峰值較小，兩端處分布較長(zhǎng)的特性，將柯西變異因子融入到算法中，以在更新后的蒼鷹個(gè)體附近生成一定擾動(dòng)來(lái)增強(qiáng)算法跳出局部最優(yōu)值的能力，從而提升算法的全局搜索性能。計(jì)算公式如下：

x_i，j^new2=x_i，j+R×（2×r-1）×x_i，j×δ_i

其中： R 為蒼鷹的狩獵半徑，在算法迭代過(guò)程中逐漸減小，以縮小目標(biāo)的范圍，使算法盡早收斂，如下所示。

其中 ：t 為當(dāng)前迭代次數(shù)； T 為總迭代次數(shù)。描述的柯西分布如下：

擾動(dòng)值 δ_i 由柯西分布的逆變換采樣公式得到，如下所示：

δ_i=x₀+γ×tan（π×（μ-0.5））

其中： Ψ_x0 和 γ 分別決定柯西分布的中心和寬度 Π_iμ∈[0，1] 。

d）為進(jìn)一步提高求解質(zhì)量，本文在算法更新中提出一種局部調(diào)整策略，對(duì)迭代中每一個(gè)個(gè)體隨機(jī)選擇兩個(gè)位置進(jìn)行2-opt操作，算法結(jié)束后對(duì)最優(yōu)個(gè)體再進(jìn)行有限次多點(diǎn)重插值操作，即迭代過(guò)程中增加算法的搜索空間，迭代后對(duì)最優(yōu)個(gè)體再進(jìn)一步優(yōu)化，其中單次進(jìn)行2-opt操作的算法復(fù)雜度為O（1） ，在 N 個(gè)蒼鷹個(gè)體下，迭代 T 次的總復(fù)雜度為 O（T×N） ，可在較少的算法求解時(shí)間下探索更大的解空間。

2-opt操作為在更新后的 C_ι 和 C_f 中分別隨機(jī)選擇兩個(gè)正整數(shù)進(jìn)行倒序。多點(diǎn)重插值操作為算法結(jié)束后在最優(yōu)編碼的C_t 中隨機(jī)選擇兩個(gè) t_i，j ，對(duì)應(yīng)的柵格為 c_ti，j∈P_ti ，將其替換為 P_ti 中任意一表示相同任務(wù)的柵格 ，具體過(guò)程如圖4所示。

若編碼 Code=[35，0，6，0，31，0][1，3，2] ，選擇 C_t 中的35和 31，C_f 中的1和2進(jìn)行2-opt操作，得到 Code^′=[31，0，6，0right] 35，0][2，3，1]。若 Code^′ 為最優(yōu)編碼，選擇 C_t 中的31和6重插值，31和6對(duì)應(yīng)的柵格分別為c3∈P和6∈P，其中Pt={c₂₅，c₃₁} P_t1={c₆，c₁₂} ，若重插值操作分別選擇了 P_t2 中的 c₂₅ 和 P_t1 中的 c₁₂ ，更新后的最優(yōu)編碼 Code^best=[25，0，12，0，35，0] （204號(hào)[2，3，1]，如算法1所示。

算法1任務(wù)分配算法

輸入：隨機(jī)生成的 N 個(gè)個(gè)體 X ，最大迭代數(shù) T

輸出：最優(yōu)編碼 X^best ，全局任務(wù) T_E 。

初始化：選擇當(dāng)前迭代中 X_N^best 開(kāi)始迭代， t=0 0

while t （2號(hào)for 1：j do由式（8）和（9）得到 x_i，j^new2 排序后輸出當(dāng)前迭代的最優(yōu)個(gè)體；end進(jìn)行 2-opt操作得到 X_N^newl ：三 F（X_N^new1）N^best） thenupdate X_N^best=X_N^new1;// 局部?jī)?yōu)化endendt=t+1

end

進(jìn)行 k 次多點(diǎn)重插值操作；

for 1：k do對(duì) X_N^best 重插值后得到 X_N^new2 11 提高迭代后解的質(zhì)量證 F（X_N^new2）N^best）then （20update X^best=X_N^new2 end

end

對(duì) X^best 解碼，得到MRS任務(wù) T_E

3.2 動(dòng)態(tài)任務(wù)分配策略

在控制器監(jiān)測(cè)下，機(jī)器人每成功訪問(wèn)一個(gè)任務(wù)柵格，就將該柵格從 T_i 中移除，添加到已完成任務(wù)集合 T_?D 中，直到子任務(wù)序列 T_i=O ，表示該機(jī)器人已完成對(duì)所有任務(wù)柵格的訪問(wèn)。

T_f 為故障的機(jī)器人集合，監(jiān)測(cè)到機(jī)器人 i 進(jìn)入危險(xiǎn)區(qū)域 T_d 故障后，控制器需要檢查該機(jī)器人的子任務(wù)序列是否滿足 T_i= ? ，若滿足，則后續(xù)只監(jiān)測(cè)其他機(jī)器人的運(yùn)行狀態(tài)。當(dāng)監(jiān)測(cè)到T_i=? ，需要重新分配剩余任務(wù)。將 ?_i=1^kT_i 中的任務(wù)柵格添加到待訪問(wèn)柵格 中，并對(duì)機(jī)器人進(jìn)行更新 T_s^new= ，具體過(guò)程如算法2所示。

算法2故障控制算法

輸入：算法1得到的任務(wù) T_E ，初始集合 T_s 。

輸出：已訪問(wèn)柵格 T_p ，待訪問(wèn)柵格 T_U ，機(jī)器人集合 T_s^new 號(hào)

初始化： T_D=O，T_s^new=T_s ，機(jī)器人 i 從 T_E 中得到子任務(wù)序列 T_i

控制器開(kāi)始工作。

while T_U≠O doif T_f≠? thenfor T_i∈T_E，i=1，…，k do將 T_i 中已訪問(wèn)柵格添加到 T_p 將 T_i 中未訪問(wèn)柵格添加到 T_U endupdate end道 T_s^new=? then機(jī)器人全部故障，無(wú)法完成任務(wù)end

在圖2的示例中，若經(jīng)過(guò)算法更新，得到了最優(yōu)編碼Code^best=[25，0，12，0，35，0][2，3，1] ，解碼得到機(jī)器人3的子任務(wù)序列 T₃=c₃₅，c₁ 。時(shí)刻 在訪問(wèn)粉色區(qū)域柵格 c₃₅ 時(shí)進(jìn)入危險(xiǎn)區(qū)域柵格 c₃₃ 發(fā)生故障，導(dǎo)致該任務(wù)未完成， T₃≠? 。需要重新考慮將訪問(wèn)柵格 c₃₄ 的任務(wù)分配給其他機(jī)器人，已故障機(jī)器人的終點(diǎn)任務(wù)不再考慮。控制器對(duì)環(huán)境更新后， T_p= D，T_U={c₂₅，c₁₂，c₃₅，c₂，c₃} ，剩余機(jī)器人及更新后的位置 T_s^new= （204號(hào) {（c₂₀，r₁），（c₁₁，r₂）} ，如圖5所示。

3.3基于競(jìng)拍的重分配策略

機(jī)器人故障后，控制器將剩余任務(wù)柵格以拍賣的形式進(jìn)行分配，具體步驟如下：

a）更新剩余機(jī)器人集合 T_s^new ，更新當(dāng)前待分配的任務(wù)柵格T_U ，初始化競(jìng)價(jià)為0。

b）計(jì)算機(jī)器人所在柵格到 T_v 中各個(gè)任務(wù)柵格的歐氏距離，作為第一輪的競(jìng)價(jià)，出價(jià)最低的機(jī)器人得到對(duì)應(yīng)的任務(wù)柵格，當(dāng)具有相同的最小競(jìng)價(jià)時(shí)，優(yōu)先分配機(jī)器人的序號(hào)。

c）為保證MRS的總路徑最小，每個(gè)機(jī)器人在新一輪競(jìng)拍中必須考慮前幾輪已經(jīng)分配到柵格的積累競(jìng)價(jià)，競(jìng)拍到任務(wù)柵格的機(jī)器人在新一輪競(jìng)拍中的競(jìng)價(jià)需要實(shí)時(shí)更新。

d）重復(fù)上述步驟c），直到所有途徑任務(wù)柵格分配完，再對(duì)終點(diǎn)任務(wù)柵格進(jìn)行競(jìng)拍，在競(jìng)拍終點(diǎn)任務(wù)柵格之前，其競(jìng)價(jià)設(shè)置為 ∞ 。

e）競(jìng)拍到剩余任務(wù)柵格 ?_i=1^k′T_Uⁱ 后，機(jī)器人按照子任務(wù)序列 T_Uⁱ 依次訪問(wèn)任務(wù)柵格。

f若后續(xù)仍有機(jī)器人故障，只需將該機(jī)器人要訪問(wèn)的任務(wù)

柵格 c_new 交由其他正常機(jī)器人執(zhí)行，具體考慮在原序列 T_Uⁱ 中的哪個(gè)位置會(huì)使得機(jī)器人的邊際成本最小，而不再需要對(duì)所有任務(wù)柵格重新考慮，邊際成本為

ΔT=min_ck∈TUⁱ?cost_E¹+cost_E²-cost_E³∣

cost_E¹=（c_k，c_new），cost_E²=（c_new，c_k+1），cost_E³=（c_k，c_k+1）

g^? 調(diào)用預(yù)處理的結(jié)果得到重分配后MRS的最短路徑和距離。

在圖5中， _r3 故障后， r₁ 和 r₂ 分別位于柵格 c₂₀ 和 c₁₁ 的位置，剩余待訪問(wèn)柵格 T_U={c₂₅，c₁₂，c₃₅，c₂，c₃} ，第一輪的競(jìng)價(jià)如表1所示。

目前最小競(jìng)價(jià)為1.0，因此在第一輪競(jìng)拍中， r₂ 競(jìng)拍到了c₁₂ 處的任務(wù)，將其添加到 r₂ 的任務(wù)柵格集合 T_U² 中，并將 c₁₂ 從T_U 中剔除，具體過(guò)程如圖6所示。

在第一輪競(jìng)拍中 r₂ 已競(jìng)拍到 c₁₂ 處的任務(wù)，在下一輪競(jìng)標(biāo)中， r₂ 需要更新到 c₁₂ 的位置。目前由于 r₁ 沒(méi)有競(jìng)拍到任務(wù)，仍然從初始競(jìng)拍位置開(kāi)始。第三輪后， r₁ 競(jìng)拍到 c₂₅ 和 c₃₅ 處的任務(wù)， r₂ 競(jìng)拍到 c₁₂ 處的任務(wù)。接著對(duì)終點(diǎn)任務(wù)柵格競(jìng)拍，每個(gè)機(jī)器人只對(duì)應(yīng)一個(gè)終點(diǎn)柵格， r₁ 和 r₂ 分別競(jìng)拍到的終點(diǎn)任務(wù)柵格為 c₂ 和 c₃ ，最后 r₁ 和 r₂ 的子任務(wù)序列為 T_U¹={c₂₅，c₃₅，c₂} 和 。

若在時(shí)刻 t，r₂ 在執(zhí)行 c₁₂ 處的任務(wù)途中也發(fā)生故障。對(duì)r₁，c₁₂ 處的搜救任務(wù)為新加入的任務(wù)，若重新考慮訪問(wèn)順序，共有3！種分配情況，為節(jié)省算力，對(duì)已經(jīng)分配的柵格順序不再改變，只需要將 c₁₂ 插入到 r₁ 已有的序列，如圖7所示。

只考慮柵格 c₁₂ 的位置，共有三種情況，分別為 {c₁₂，c₂₅ ，c₃₅}，{c₂₅，c₁₂，c₃₅} 和 {c₂₅，c₃₅，c₁₂} ，通過(guò)式（13）得到 r₁ 的最優(yōu)柵格序列為 {c₂₅，c₃₅，c₁₂} ，完成任務(wù)后，最后訪問(wèn)終點(diǎn)柵格 c₂ 。本節(jié)任務(wù)分配策略的流程如圖8所示。

本節(jié)提出的任務(wù)分配策略具有良好的動(dòng)態(tài)性和自適應(yīng)能力。動(dòng)態(tài)性方面，控制器實(shí)時(shí)監(jiān)測(cè)機(jī)器人的狀態(tài)，故障后以拍賣的方式將剩余任務(wù)重分配，確保任務(wù)完成。自適應(yīng)能力方面，可通過(guò)任務(wù)環(huán)境的變化來(lái)調(diào)整分配方案，機(jī)器人故障后通過(guò)計(jì)算邊際成本優(yōu)先訪問(wèn)滿足任務(wù)序列整體代價(jià)最小的任務(wù)。

4實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證本文方法在考慮機(jī)器人故障因素下的有效性，本章開(kāi)展多組仿真實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果和現(xiàn)有方法進(jìn)行對(duì)比。實(shí)驗(yàn)均在Windows11操作系統(tǒng)、處理器 Intel^°ledast CoreTMi5-10210UCPU、主頻 1.6GHz 雙核、8GB內(nèi)存的計(jì)算機(jī)上進(jìn)行，所有實(shí)驗(yàn)均通過(guò)Python 實(shí)現(xiàn)。

首先對(duì)一現(xiàn)實(shí)中的火災(zāi)環(huán)境進(jìn)行仿真，火警中心接到一居民家中發(fā)生火災(zāi)，需要派遣機(jī)器人前去執(zhí)行滅火、人員搜救和閥門關(guān)閉的任務(wù)。柵格劃分后，環(huán)境由100個(gè)柵格組成， C= {c₁，c₂，…，c₁₀₀} ，集合 T_s={（c₉₈，r₁），（c₉₉，r₂），（c₅₀，r₃）} 表示派遣的3個(gè)機(jī)器人分別從柵格 c₉₈，c₉₉ 和 c₅₀ 的位置進(jìn)人居民家中。危險(xiǎn)區(qū)域柵格為 T_d={c₃₃，c₃₇，c₄₆，c₆₄，c₇₁} 。途徑任務(wù)區(qū)域 π₁₃，π₁₄} ，終點(diǎn)任務(wù)區(qū)域 ，任務(wù)區(qū)域所包含的柵格如表2所示。

根據(jù)對(duì)居民家中進(jìn)行火災(zāi)救援的任務(wù)要求，控制器為MRS下發(fā)了如下的布爾規(guī)范：

φ=φ₁∧φ₂∧φ₃

φ₁=II₁∧III₂∧III₃∧II₄∧（II₅∨II₆）

φ₂=II₇∧II₈∧II₉∧II₁₀

即機(jī)器人在執(zhí)行任務(wù)過(guò)程中，沿軌跡需要訪問(wèn)紫色區(qū)域 、綠色區(qū)域 、黃色區(qū)域 、橙色區(qū)域 Π₄ ，執(zhí)行被困人員的搜救任務(wù)，訪問(wèn)粉色區(qū)域 ，執(zhí)行滅火任務(wù)，隨機(jī)至少訪問(wèn)一個(gè)藍(lán)色區(qū)域 π_s 或 π₆ （見(jiàn)電子版），執(zhí)行關(guān)閉閥門的任務(wù)?？紤]到任務(wù)的完成性，最后至少保證一個(gè)機(jī)器人到達(dá)安全區(qū)域 π₁ 向指揮部匯報(bào)任務(wù)進(jìn)展。綜合考慮機(jī)器人故障的情況，本文方法得到每個(gè)機(jī)器人的柵格序列如表3所示，對(duì)應(yīng)機(jī)器人的具體路徑如圖9所示。

開(kāi)始執(zhí)行前，控制器為每個(gè)機(jī)器人分發(fā)的子任務(wù)序列分別為 T₁=c₈₆，c₉₂，c₆₃，c₂₁，T₂=c₆₈，c₅₆，c₄₁，c₁，T₃=c₂₉，c₁₇，c₁₄，c₁₁° 在 t=8 時(shí)刻， r₂ 在執(zhí)行衛(wèi)生間 c₄₁ 處關(guān)閉閥門的任務(wù)途中，進(jìn)入柵格 c₄₆ 遭到損壞。此時(shí) r₁ 完成了 c₈₆ 處的滅火任務(wù)和臥室 c₉₂ 處的搜救任務(wù)， r₃ 完成廚房 c₂₉ 處的搜救任務(wù)和 c₁₇ 處的滅火任務(wù)。此時(shí) T_D={c₈₆，c₉₂，c₆₈，c₂₉，c₁₇}，T_U={c₆₃，c₄₁，c₁₄，c₂₁，c₁₁}， 控制器將剩余柵格重分配后， r₁ 需要依次執(zhí)行 c₆₃ 處的滅火任務(wù)和衛(wèi)生間 c₄₁ 處關(guān)閉閥門的任務(wù)， r₃ 則繼續(xù)執(zhí)行客廳 c₁₄ 處的搜救任務(wù)，任務(wù)完成后，分別到達(dá)安全位置 c₂₁ 和 c₁₁ 處。所有路徑都始終避開(kāi)了禁止區(qū)域，同時(shí)滿足了布爾規(guī)范的任務(wù)要求。為進(jìn)一步驗(yàn)證本文方法的有效性和可擴(kuò)展性，通過(guò)設(shè)置不同地圖規(guī)模和任務(wù)數(shù)量，進(jìn)行一系列仿真實(shí)驗(yàn)來(lái)比較本文方法和文獻(xiàn)[20]以及其他方法的求解效果。首先，在不同地圖規(guī)模下，對(duì)隨機(jī)生成的示例運(yùn)行10次，記錄下平均移動(dòng)距離和求解時(shí)間，對(duì)文獻(xiàn)20測(cè)試了不同領(lǐng)域搜索次數(shù) K 下的求解結(jié)果（ 和500），如圖10、11所示。

（a）不同任務(wù)數(shù)量下各方法 （b）不同任務(wù)數(shù)量下各方法移動(dòng)距離對(duì)比 求解時(shí)間對(duì)比

表4展示了不同地圖大小下，本文方法和其他方法的求解結(jié)果對(duì)比。本文方法在滿足布爾任務(wù)的要求下，所需的平均移動(dòng)距離均優(yōu)于其他方法，文獻(xiàn)[20]隨著 K 值的增加，求解質(zhì)量也在提高，但是算法的求解時(shí)間呈爆炸性增長(zhǎng)，遠(yuǎn)高于本文方法，而基于拍賣的方法雖然求解時(shí)間較短，但是求解的路徑結(jié)果最差，而且當(dāng)機(jī)器人位置分布較為密集時(shí)，部分機(jī)器人可能會(huì)分配不到任務(wù)，從而導(dǎo)致個(gè)別機(jī)器人的負(fù)載過(guò)大。

表5展示了在900個(gè)柵格的地圖中，在不同任務(wù)數(shù)量下的求解結(jié)果對(duì)比，隨著任務(wù)數(shù)量的增加，各種方法的求解時(shí)間明顯變長(zhǎng)，基于拍賣的方法雖然求解時(shí)間較短，但是其求解的結(jié)果較差，而基于智能算法的方法在機(jī)器人故障后需要對(duì)剩余任務(wù)重新編碼迭代求解，使得計(jì)算變得復(fù)雜，顯著增加求解時(shí)間，本文方法綜合了平均移動(dòng)距離和求解時(shí)間的考慮，效果較好。

5結(jié)束語(yǔ)

本文研究了考慮故障因素下的多機(jī)器人動(dòng)態(tài)任務(wù)分配及路徑規(guī)劃問(wèn)題，所提方法在確保機(jī)器人故障后仍能完成全局任務(wù)。通過(guò)多組仿真結(jié)果對(duì)比，證明本文方法在求解質(zhì)量和求解效率方面均優(yōu)于現(xiàn)有方法，并在實(shí)際的火災(zāi)救援場(chǎng)景中進(jìn)行仿真實(shí)驗(yàn)，證明了本文方法的可擴(kuò)展性。最后，本文考慮的是理想環(huán)境下的路徑規(guī)劃，現(xiàn)實(shí)中由于傳感器的誤差可能會(huì)存在環(huán)境不確定的情況，后續(xù)工作會(huì)進(jìn)一步加入不確定環(huán)境中路徑規(guī)劃的考慮。

參考文獻(xiàn)：

[1]JiangYichuan，Hu Jing，Liu Donghui.Decisionmaking of networked multi-agent systems for interaction structures[J].IEEE Trans on Systems，Man，and Cybernetics-PartA：Systemsand Humans，2011，41（6）：1107-1121.

[2]Chakraa H，GuerinF，LeclercqE，etal.Optimization techniques for multi-robot task allocation problems：review on the state-of-the-art [J].Roboticsand Autonomous Systems，2023，168：104492.

[3]Cai Kai. Warehouse automation by logistic robotic networks：a cyberphysical control approach[J].Frontiers of Information Technologyamp;Electronic Engineering，2020，21（5）：693-704.

[4].MishraB，GargD，NarangP，etal.Drone-surveillance for search and rescue in natural disaster[J].Computer Communications， 2020，156（2）：1-10.

[5]Almadhoun R，Taha T，Seneviratne L，et al.A survey on inspecting 第42卷 structures using robotic systems [J]. International Journal of Advanced Robotic Systems，2016，13（6）1-18.

[6]湯偉，趙靜，古嬋．基于自動(dòng)機(jī)的迷宮路徑規(guī)劃求解算法優(yōu)化 [J]．南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2021，41（5）：92-100. （Tang Wei， Zhao Jing，Gu Chan. Optimization algorithm for maze path planning and solving based on automata[J]. Journal of Nanjing University of Posts and Telecommunications： Natural Science Edition，2021，41（5）：92-100.）

[7]Miao Changwei， Chen Guangzhu， Yan Chengliang，et al.Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers amp; Industrial Engineering，2021，156： 107230.

[8]He Zhou，Dong Yuying，Ren Gongchang，et al.Path planning for automated guided vehicle systems with time constraints using timed Petri nets[J].Measurement and Control，2020，53（9-10）： 2030-2040.

[9]Dai Wei，Lu Huimin，Xiao Junhao，et al.Multi-robot dynamic task allocation for explorationand destruction[J]. Journal of Intelligent amp; Robotic Systems，2020，98（2）： 455-479.

[10]Huang Feifei，Yin Xiang，Li Shaoyuan.Failure-robust multi-robot tasks planning under linear temporal logic specifications [C]//Proc of the13th Asian Control Conference.Piscataway，NJ：IEEEPress， 2022： 1052-1059.

[11]Cai Mingyu，Xiao Shaoping，LiBaoluo，etal.Reinforcementlearning based temporal logic control with maximum probabilistic satisfaction[C]//Proc of IEEE International Conference on Robotics and Automation.Piscataway，NJ： IEEE Press，2O21：806-812.

[12]姜佩賀，王敬，桑忠啟，等．改進(jìn) A^* 與DWA的室內(nèi)服務(wù)機(jī)器人 路徑規(guī)劃研究［J]．計(jì)算機(jī)工程與應(yīng)用，2024，60（15）：327- 335.（Jiang Peie，Wang Jing，Sang Zhongqi，etal.Researchonindoor service robot path planning based on improved A^* and DWA [J].Computer Engineering and Applications，2024，60（15）： 327-335. ）

[13]沈克宇，游志宇，劉永鑫，等．基于改進(jìn) A^* 算法的移動(dòng)機(jī)器人 路徑規(guī)劃［J]．計(jì)算機(jī)應(yīng)用研究，2023，40（1）：75-79.（Shen Keyu，You Zhiyu，Liu Yongxin，et al.Mobile robot planning based on improved A^* algorithm[J].Application Research of Computers，2023，40（1）：75-79.）

[14]Yu Xinyi， Yin Xiang，Li Shaoyuan，et al. Security-preserving multiagent coordination for complex temporal logic tasks[J]. Control EngineeringPractice，2022，123：105130.

[15]Xie Yifan，Yin Xiang，Li Shaoyuan，etal. Secure-by-construction controller synthesis for stochastic systems under linear temporal logic specifications [C]//Proc of the 6Oth IEEE Conference on Decision and Control. Piscataway，NJ： IEEE Press，2021：7015-7021.

[16]Zhang Hongbin，Luo Jiliang，Long Jinjun，et al．Multi-robot path planning using Petri nets[M]//Verification and Evaluation of Computer and Communication Systems.Cham：Springer，2020：15-26.

[17]Mahulea C，Kloetzer M.Robot planning based on Boolean specifications using Petri net models[J]. IEEE Trans on Automatic Control，2018，63（7） ： 2218-2225.

[18］李保羅，蔡明鈺，闕震．線性時(shí)序邏輯引導(dǎo)的安全強(qiáng)化學(xué)習(xí) [J]．控制與決策，2023，38（7）：1835-1844.（Li Baoluo，Cai Mingyu，Kan Zhen.Linear temporal logic guided safe reinforcement learning［J].Control and Decision，2023，38（7）：1835-1844.）

[19]Mahulea C，Kloetzer M，Lesage JJ. Multi-robot path planning with Booleanspecificationsand collision avoidance[J].IFACPapersOnLine，2020，53（4）： 101-108.

[20]Shi Weijie，He Zhou，Tang Wei，etal.Path planning of multi-robot systems with Boolean specifications based on simulated annealing [J].IEEE Robotics and Automation Letters，2022，7（3）： 6091-6098.

[21］何舟，劉思羽．帶時(shí)間窗的多機(jī)器人系統(tǒng)復(fù)雜任務(wù)路徑規(guī)劃 [J]．南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2024，44（2）：83-90. （He Zhou，Liu Siyu.Path planning for multi-robot systems with complex tasks and time windows [J]. Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition，2024， 44（2）： 83-90.）