一種健康管理機(jī)器人協(xié)同任務(wù)分配方法

魯婷婷，馮彥翔，閆振龍

(1.西安交通大學(xué) 體育中心，陜西 西安 710049；2.西安交通大學(xué) 自動(dòng)化科學(xué)與工程學(xué)院 電信學(xué)部，陜西 西安 710049)

0 引言

隨著人口老齡化的不斷發(fā)展，老年人健康管理服務(wù)在社區(qū)基本公共衛(wèi)生服務(wù)中所占比重越來(lái)越大。健康管理或護(hù)理型機(jī)器人的出現(xiàn)，為社區(qū)老年人的健康管理提供了一個(gè)靈活便捷的平臺(tái)。機(jī)器人可以幫助實(shí)現(xiàn)家庭陪伴、生活護(hù)理、老年人搬運(yùn)、殘障護(hù)理以及慢性病管理等任務(wù)[1]。社區(qū)經(jīng)常需要多個(gè)護(hù)理機(jī)器人組成多機(jī)器人系統(tǒng)(Multi-robot Systems)，協(xié)同完成社區(qū)老年人健康管理服務(wù)。其中，多機(jī)器人任務(wù)分配(Multi-robot Task Allocation Problem，MTAP)近年來(lái)已成為機(jī)器人協(xié)同規(guī)劃領(lǐng)域需要解決的關(guān)鍵問(wèn)題[2]。

多機(jī)器人協(xié)同任務(wù)分配問(wèn)題是指：綜合考慮時(shí)間和資源等約束，將任務(wù)分配給機(jī)器人，機(jī)器人之間進(jìn)行協(xié)同配合，使得整個(gè)系統(tǒng)消耗的成本最低，執(zhí)行任務(wù)效率最高[3]。這本質(zhì)上是一個(gè)NP-hard問(wèn)題[4]，通常采用多旅行商問(wèn)題[5]、車輛路徑方法[6]和混合整數(shù)線性規(guī)劃方法[7]。一般有2類方法解決多機(jī)器人任務(wù)分配問(wèn)題：分布式和集中式[8-9]。雖然分布式分配算法能處理任務(wù)動(dòng)態(tài)加入/撤銷等事件，但是算法穩(wěn)定性嚴(yán)重依賴通信拓?fù)涞馁|(zhì)量，且分配結(jié)果質(zhì)量不高，因此主要采用集中式方法實(shí)現(xiàn)多機(jī)器人健康管理協(xié)同任務(wù)分配[10]。

集中式方法包括最優(yōu)化方法和啟發(fā)式方法。最優(yōu)化方法能得到理論最優(yōu)解，比如混合整數(shù)線性規(guī)劃算法[9]，但難以解決大規(guī)模問(wèn)題。啟發(fā)式方法在處理MTAP時(shí)沒(méi)有遍歷整個(gè)搜索空間，而在計(jì)算時(shí)間和解的最優(yōu)性間達(dá)成某種妥協(xié)，從而在可接受的時(shí)間和計(jì)算代價(jià)內(nèi)獲得較好的次優(yōu)解[11]。例如，通過(guò)對(duì)粒子個(gè)體位置和最優(yōu)位置的記憶與學(xué)習(xí)，粒子群算法在解空間中向著最優(yōu)方向快速運(yùn)動(dòng)[12]，但其精細(xì)搜索能力不強(qiáng)，全局搜索能力差[13]。蟻群算法利用隱式通信進(jìn)行信息共享，在未知環(huán)境中通過(guò)群體信息積累實(shí)現(xiàn)解的智能自組織搜索[14]，但是蟻群系統(tǒng)容易出現(xiàn)停滯現(xiàn)象[15]。遺傳算法作為一種典型的群體智能算法，構(gòu)建一個(gè)初始化種群，然后通過(guò)交叉、變異和選擇等過(guò)程，對(duì)染色體種群迭代演進(jìn)，最終獲得一個(gè)較好的可行解[16-17]。但是傳統(tǒng)的遺傳算法往往是單一任務(wù)的規(guī)劃優(yōu)化，對(duì)于復(fù)雜場(chǎng)景不能獲得準(zhǔn)確的解[18-20]。

本文針對(duì)任務(wù)需要多個(gè)機(jī)器人協(xié)同完成的場(chǎng)景，結(jié)合任務(wù)的時(shí)間窗等約束，提出了一種綜合考慮任務(wù)收益和代價(jià)的改進(jìn)遺傳算法，用于求解社區(qū)老年人健康管理中的MTAP問(wèn)題。提出了雙染色體表征個(gè)體，有效地?cái)U(kuò)展搜索空間，提高了算法的全局搜索能力，能夠快速地尋找到適應(yīng)度較好的個(gè)體。最后進(jìn)行了數(shù)字仿真實(shí)驗(yàn)，驗(yàn)證了提出的改進(jìn)型遺傳算法的有效性，實(shí)驗(yàn)結(jié)果也明顯優(yōu)于現(xiàn)有的傳統(tǒng)遺傳算法。

1 數(shù)學(xué)模型

1.1 問(wèn)題描述

社區(qū)中有多臺(tái)護(hù)理機(jī)器人協(xié)同執(zhí)行多個(gè)健康管理任務(wù)。共有Nv臺(tái)護(hù)理機(jī)器人V={V1,V2,V3,…,VNv}以及Nt個(gè)護(hù)理任務(wù)M={M1,M2,M3,…,MNt}。護(hù)理機(jī)器人數(shù)目遠(yuǎn)小于任務(wù)數(shù)。初始時(shí)，護(hù)理機(jī)器人和任務(wù)分別位于社區(qū)中不同的位置。一項(xiàng)護(hù)理任務(wù)Mj需要Γ(Mj) ≥ 1臺(tái)護(hù)理機(jī)器人協(xié)同完成。比如對(duì)于行動(dòng)不便的老人的一項(xiàng)護(hù)理任務(wù)，需要移動(dòng)護(hù)理機(jī)器人和搬運(yùn)機(jī)器人協(xié)同完成。每個(gè)任務(wù)Mj具有一個(gè)執(zhí)行時(shí)間窗[X(Mj),Y(Mj)]，如果Mj的開(kāi)始執(zhí)行時(shí)間小于X(Mj)或者大于Y(Mj)，則會(huì)產(chǎn)生一定的時(shí)間偏差代價(jià)。此處的時(shí)間窗約束屬于“軟約束”，即不一定需要任務(wù)分配解遵循，但有可能造成執(zhí)行任務(wù)失敗。

為了方便描述任務(wù)分配，引入任務(wù)決策0-1變量xij，其中xij=1表示護(hù)理機(jī)器人Vi執(zhí)行任務(wù)Mj，xij=0表示不執(zhí)行。

1.2 約束條件

(1) 多機(jī)協(xié)同約束。對(duì)于一個(gè)任務(wù)Mj，需要由Γ(Mi)臺(tái)護(hù)理機(jī)器人協(xié)同執(zhí)行：

(1)

(2) 任務(wù)能力約束?？紤]電池能源約束，每臺(tái)護(hù)理機(jī)器人的執(zhí)行能力有限：

(2)

式中，Wi為護(hù)理機(jī)器人Vi能夠執(zhí)行的最大任務(wù)數(shù)。

1.3 代價(jià)函數(shù)和任務(wù)函數(shù)

選取護(hù)理機(jī)器人的行程代價(jià)、時(shí)間偏差代價(jià)和任務(wù)收益作為衡量指標(biāo)。

(1) 行程代價(jià)。行程代價(jià)Li為護(hù)理機(jī)器人Vi從初始點(diǎn)Ai出發(fā)，依次遍歷任務(wù)序列Mi中的每一個(gè)任務(wù)，最后返回Ai的距離：

(3)

式中，Dis{·}表示2個(gè)任務(wù)點(diǎn)或任務(wù)點(diǎn)與護(hù)理機(jī)器人初始點(diǎn)之間的距離。

(2) 時(shí)間偏差代價(jià)。令機(jī)器人Vi到達(dá)任務(wù)Mj的時(shí)間為(Vi,Mj)。若Mj?Φi,則(Vi,Mj)=0。假設(shè)只有所有執(zhí)行任務(wù)Mj的護(hù)理機(jī)器人都到現(xiàn)場(chǎng)，才可以執(zhí)行Mj，因此Mj的開(kāi)始執(zhí)行時(shí)間S(Mj)=max{α(Vi,Mj)|Mj∈Φi}。根據(jù)時(shí)間窗約束，如果S(Mj)Y(Mj)，都會(huì)產(chǎn)生時(shí)間偏差代價(jià)TDj：

(4)

(3) 受益收益。任務(wù)收益Gi是指護(hù)理機(jī)器人Vi在完成任務(wù)序列Φi，之后獲得的受益：

(5)

式中，Pij表示Vi成功執(zhí)行任務(wù)Mj的概率；Vaj表示完成Mj的受益。此處Pi和Vaj都是根據(jù)經(jīng)驗(yàn)人為設(shè)定的參數(shù)。

(4) 優(yōu)化目標(biāo)。護(hù)理機(jī)器人行程越短，能源消耗越少；在預(yù)定時(shí)間窗內(nèi)執(zhí)行任務(wù)，預(yù)期任務(wù)效率更好；受益收益越大，執(zhí)行任務(wù)的效果更好。因此，綜合考慮行程代價(jià)、時(shí)間偏差代價(jià)和任務(wù)收益，本文設(shè)定的優(yōu)化目標(biāo)為：

(6)

上述目標(biāo)函數(shù)J越大，表示解的質(zhì)量越好。式中，雖然“行程代價(jià)”“時(shí)間偏差代價(jià)”和“任務(wù)受益”3部分的量綱沒(méi)有統(tǒng)一歸化，但是對(duì)應(yīng)的一些參數(shù)(比如任務(wù)受益和成功概率)是根據(jù)經(jīng)驗(yàn)人為設(shè)定，具有一定的可驗(yàn)性。得到的結(jié)果經(jīng)過(guò)一系列人為檢驗(yàn)，可證明其合理性，因此建立的模型仍然是有效的。

最終MTAP的數(shù)學(xué)函數(shù)如下：

s.t.xij∈{0,1},?Vi∈V,?Mj∈M

(7)

2 基于改進(jìn)遺傳算法的任務(wù)分配方法

多類型護(hù)理機(jī)器人和任務(wù)時(shí)間窗的出現(xiàn)，會(huì)影響染色體解的質(zhì)量。本文提出一種雙染色體的表征方法，分別表示任務(wù)序列和護(hù)理機(jī)器人序列。

2.1 編碼和解碼

例1：護(hù)理機(jī)器人集合為V={V1,V2,V3}，最大執(zhí)行任務(wù)數(shù)分別為W1=W3=4，W2=3。社區(qū)共有6項(xiàng)護(hù)理任務(wù)，M={M1,M2,…,M6}。Γ(M2)=Γ(M4)=Γ(M5)=2，其余任務(wù)Γ(Mi)=1。個(gè)體π1如圖1所示，對(duì)該染色體進(jìn)行解碼，得到的護(hù)理機(jī)器人任務(wù)分配方案為Φ1=，Φ2=，Φ3=。

圖1 個(gè)體π1的2條染色體編碼Fig.1 Two chromosome codes of individual π1

觀察這一組方案，可知任務(wù)序列Φ2中任務(wù)M4出現(xiàn)2次，違背條件(1)；同時(shí)，Φ2含有4個(gè)任務(wù)，超過(guò)機(jī)器人V2的最大執(zhí)行任務(wù)數(shù)目，不滿足條件(2)。

為了讓任務(wù)分配方案滿足(1)和(2)，染色體編碼seqt和seqv必須滿足以下3個(gè)條件：

①seqv中每個(gè)機(jī)器人Vi∈V出現(xiàn)的次數(shù)必須要小于等于Wi；

②seqt每種任務(wù)Mj∈M出現(xiàn)的次數(shù)等于(Mj)；

③ 每個(gè)護(hù)理機(jī)器人Vi∈V的任務(wù)序列Φi不含有重復(fù)任務(wù)，即當(dāng)seqv(i)=seqv(j)時(shí)，seqt(i)≠seqt(j)；

當(dāng)個(gè)體π={seqt,seqv}不滿足上述3個(gè)條件時(shí)，需要對(duì)π進(jìn)行修正。首先，令X={Vi|在seqv上Vi出現(xiàn)次數(shù)大于Wi}和Y={Vi|在seqv上Vi出現(xiàn)次數(shù)小于Wi}。在seqv上將屬于X的元素替換成Y中的元素，同時(shí)更新集合X和Y。通過(guò)反復(fù)迭代，直至滿足約束條件①。然后 ，令S={Mj|在seqt上任務(wù)Mj出現(xiàn)次數(shù)大于Γ(Mj)}和C={Mj|在seqt上任務(wù)Mj出現(xiàn)次數(shù)小于Γ(Mj)}，在seqt上將S的元素替換成C中的元素，每次替換都更新X和Y。通過(guò)反復(fù)迭代，滿足約束條件②。最后，為了避免將一個(gè)任務(wù)分配給同一機(jī)器人，遍歷seqv，修改部分seqt的基因使得滿足約束條件③。

經(jīng)過(guò)上述過(guò)程使得個(gè)體滿足了所有的約束條件，但是因?yàn)槿蝿?wù)可能需要多臺(tái)機(jī)器人同時(shí)執(zhí)行，機(jī)器人可能會(huì)陷入循環(huán)等待，即出現(xiàn)死鎖現(xiàn)象。比如例1中的個(gè)體π1經(jīng)修正后如圖2所示，相應(yīng)的任務(wù)分配方案為：Φ′1=，Φ′2=，Φ′3=。不難發(fā)現(xiàn)，V1需要等待V2執(zhí)行M2之后才能執(zhí)行任務(wù)M5，V2需要等待V1執(zhí)行任務(wù)M2,M5之后才能執(zhí)行任務(wù)M4，2臺(tái)機(jī)器人此時(shí)陷入了循環(huán)等待。

圖2 修正后的個(gè)體π1Fig.2 The modified individual π1

可構(gòu)建一幅有向圖G=(M,E)來(lái)描述死鎖現(xiàn)象，其中M是所有需執(zhí)行的任務(wù)，弧線(Mi,Mj)∈E表示存在一臺(tái)機(jī)器人先執(zhí)行任務(wù)Mi，緊接著執(zhí)行任務(wù)Mj。有向圖中的有向環(huán)表示死鎖，根據(jù)文獻(xiàn)[21]中的算法進(jìn)行死鎖的檢測(cè)和修復(fù)。比如，例1修正后的個(gè)體π1的有向圖如圖3所示。其中，圖3(a)中紅色虛線框所標(biāo)注有向環(huán)對(duì)應(yīng)著死鎖的出現(xiàn)。將弧線(M4,M2)改變方向，從而打破有向環(huán)的封閉，避免死鎖。修改后的有向圖為圖3(b)。這種基于有向圖的死鎖修正僅僅改變弧線的方向，即改變某個(gè)機(jī)器人的執(zhí)行任務(wù)順序。因此經(jīng)過(guò)修正后的任務(wù)分配方案仍滿足式(2)和式(3)。最終修改后無(wú)死鎖的任務(wù)分配方案為：Φ″1=，Φ″2=，Φ″3=。

(a) 含死鎖有向圖G

(b) 無(wú)死鎖有向圖G圖3 任務(wù)分配方案的有向圖Fig.3 Directed graph of task assignment scheme

種群中的每個(gè)個(gè)體經(jīng)過(guò)解碼和修正，最終得到一組符合所有約束條件且無(wú)死鎖的新個(gè)體。

2.2 適應(yīng)度計(jì)算

個(gè)體的適應(yīng)度決定了個(gè)體的優(yōu)劣性以及其在迭代過(guò)程中是否可以被保留。對(duì)于一個(gè)個(gè)體π={seqt,seqv}，將其解碼為一組任務(wù)分配方案，該方案在滿足約束條件且無(wú)死鎖下，根據(jù)式(7)，其適應(yīng)度F為：

(8)

F(π)越大，表示個(gè)體越能適應(yīng)環(huán)境，在迭代過(guò)程中被保留的概率越大。

2.3 選擇操作

種群規(guī)模為P，通過(guò)輪盤賭規(guī)則和代溝選擇參數(shù)Pgap(0

2.4 交叉和變異操作

本文中，每個(gè)個(gè)體π={seqt,seqv}包含2條編碼信息，每一條編碼的交叉方法為均勻交叉方法。具體操作流程為：

① 隨機(jī)產(chǎn)生一條長(zhǎng)度為Na的二進(jìn)制編碼的屏蔽字C，即C=c1c2…cNa，其中ci取0或1；

② 選取2個(gè)父代個(gè)體π1={seqt1,seqv1}和π2={seqt2,seqv2}。按照如下規(guī)則生成2個(gè)新的子代個(gè)體π′1={seq′t1,seq′v1}和π′2={seq′t2,seq′v2}：若ci=0，則seq′t1(i)=seqt1(i)，seq′t2(i)=seqt2(i)；若ci=1，則seq′t1(i)=seqt2(i)，seq′t2(i)=seqt1(i)。同理，可生成新個(gè)體的編碼seq′v1和seq′v2。

變異的目的是增加種群的多樣性。每個(gè)個(gè)體的每一條染色體使用基因逆轉(zhuǎn)進(jìn)行變異操作。具體操作流程為：

① 選取個(gè)體π1的一條編碼seqt1或seqv1，此處選取seqt1；

② 隨機(jī)選取seqt1上的2個(gè)基因位點(diǎn)seqt1(i)，seqt1(j)，顛倒2位點(diǎn)間基因片段的前后順序，得到新的編碼seq′t1；

③ 如果適應(yīng)度F(π′1)>F(π1)，則接受變異，反之不接受變異。

反復(fù)迭代上述交叉和變異操作，最終確定新的變異個(gè)體。

2.5 算法整體流程

基于改進(jìn)遺傳算法的多護(hù)理機(jī)器人協(xié)同任務(wù)分配算法步驟如下：

步驟1：初始化算法參數(shù)，包括代溝選擇參數(shù)Pgap、交叉概率Pc、變異概率Pm、種群規(guī)模P、遺傳迭代次數(shù)R。

步驟2：初始化種群。種群每個(gè)個(gè)體隨機(jī)初始化，符合編碼和解碼需求。

步驟3：選擇操作。根據(jù)適應(yīng)度，利用輪盤賭規(guī)則，選取P×Pgap個(gè)體進(jìn)行交叉、變異操作；剩余P×(1-Pgap)直接保留至子代種群。

步驟4：交叉操作。對(duì)步驟3中被選中的個(gè)體，結(jié)合交叉概率Pc，對(duì)被選擇的個(gè)體的2條染色體分別進(jìn)行均勻交叉，生成新個(gè)體。

步驟5：變異操作。對(duì)步驟4生成的新個(gè)體，結(jié)合變異概率Pm，對(duì)進(jìn)一步被選擇的個(gè)體進(jìn)行變異操作，通過(guò)基因逆轉(zhuǎn)生成新個(gè)體。

步驟6：生成子代種群。經(jīng)過(guò)步驟3～5后生成的P×Pgap個(gè)體，與步驟2剩余的P×(1-Pgap)個(gè)體共同構(gòu)成子代種群。

步驟7：對(duì)種群重復(fù)步驟3～6，直到達(dá)到遺傳迭代次數(shù)R。輸出最后一代種群的適應(yīng)度最低的個(gè)體，將該個(gè)體解碼得到最優(yōu)的任務(wù)分配方案。

3 實(shí)驗(yàn)分析

3.1 算法設(shè)計(jì)

假設(shè)所有護(hù)理機(jī)器人勻速行駛，每個(gè)任務(wù)具有不同的執(zhí)行時(shí)間窗口和執(zhí)行時(shí)間。實(shí)驗(yàn)由小規(guī)模和大規(guī)模2組算例組成。每種算例對(duì)應(yīng)的護(hù)理機(jī)器人數(shù)Nv、任務(wù)數(shù)Nt和機(jī)器人最大執(zhí)行任務(wù)數(shù)W如表1所示。小規(guī)模算例共有Nv×Nt×W=8種組合，對(duì)于每個(gè)組合，隨機(jī)生成5組機(jī)器人和任務(wù)的坐標(biāo)點(diǎn)、相應(yīng)任務(wù)執(zhí)行時(shí)間和時(shí)間窗約束，因此共有5×8=40個(gè)小規(guī)模算例。同理可知，有8種大規(guī)模算例，每種隨機(jī)產(chǎn)生5組數(shù)據(jù)，共有5×8=40個(gè)大規(guī)模算例。本文實(shí)驗(yàn)的運(yùn)行環(huán)境為Intel Core i9-9900K 2.5 GHz CPU,32 GB內(nèi)存,Windows10 操作系統(tǒng)。

表1 算例規(guī)格說(shuō)明Tab.1 The specification of calculation examples

在Matlab2021a上通過(guò)與傳統(tǒng)遺傳算法(GA)[22]進(jìn)行對(duì)比，驗(yàn)證本文提出的改進(jìn)遺傳算法(MGA)的有效性和優(yōu)越性。本文對(duì)每一個(gè)算例運(yùn)行20次，盡可能地消除隨機(jī)性帶來(lái)的誤差。所有算法采用相對(duì)偏差RE作為性能指標(biāo)：

RE=(FVa-FVb)/FVb，

(9)

式中，F(xiàn)Va表示某一種算法對(duì)于一個(gè)算例的適應(yīng)度值；FVb表示所有算法在所有算例上的最優(yōu)適應(yīng)度值。

3.2 參數(shù)標(biāo)定

MGA有4個(gè)參數(shù)，分別是Pgap，Pc，Pm和P，令所有算法中的迭代次數(shù)R=800,本文采用Taguchi[23]正交實(shí)驗(yàn)方法進(jìn)行標(biāo)定。

首先，設(shè)定每個(gè)參數(shù)具有4個(gè)因子水平，如表2所示。

表2 各參數(shù)因子水平Tab.2 The factor level of each parameter

然后，根據(jù)參數(shù)和參數(shù)因子水平數(shù)構(gòu)建正交表L16(44)，結(jié)果如表3所示，具有16種不同參數(shù)因子水平組合。由于3.1節(jié)中設(shè)定了2種算例規(guī)模，因此本節(jié)的參數(shù)標(biāo)定方法分別對(duì)規(guī)模Nv×Nt×W為{3,6,3},{10,30,4}兩種算例進(jìn)行參數(shù)標(biāo)定。

表3 正交表L16(44)和標(biāo)定結(jié)果Tab.3 The orthogonal table L16(44) and calibration results

參數(shù)標(biāo)定的統(tǒng)計(jì)結(jié)果如表4所示。對(duì)于不同規(guī)模算例，參數(shù)的優(yōu)先級(jí)具有一定的差別。具體來(lái)說(shuō)，對(duì)于小規(guī)模算例，代溝選擇參數(shù)Pgap為最重要的參數(shù)，種群規(guī)模P其次，之后為交叉概率Pc和變異概率Pm。對(duì)于大規(guī)模算例，代溝選擇參數(shù)Pgap和種群規(guī)模P依舊為最重要的2個(gè)參數(shù)，但此時(shí)變異概率Pm的重要性超過(guò)交叉概率Pc。因此，剩余仿真實(shí)驗(yàn)中針對(duì)小規(guī)模和大規(guī)模實(shí)驗(yàn)算例所選的參數(shù)集合{Pgap,Pc,Pm,P}分別為{0.5,0.5,0.6,50}和{0.5,0.5,0.4,50}。

表4 統(tǒng)計(jì)分析與建議參數(shù)值Tab.4 The statistical analysis and recommended parameter values

3.3 性能對(duì)比

基于提出的2種規(guī)模的算例，采用3.2節(jié)計(jì)算的各項(xiàng)參數(shù)，分析對(duì)比MGA和GA的實(shí)驗(yàn)結(jié)果和性能。算法實(shí)驗(yàn)結(jié)果對(duì)比圖如圖4所示，不同算法對(duì)于不同規(guī)模的比較結(jié)果如表5所示。

表5 不同算法對(duì)于不同規(guī)模的比較結(jié)果Tab.5 The comparison results of different algorithms for different scales

(a) 平均相對(duì)偏差

(b) 平均運(yùn)行時(shí)間折線圖圖4 算法實(shí)驗(yàn)結(jié)果對(duì)比Fig.4 The comparison of algorithm experimental results

由表5可以看出，由于小規(guī)模算例的解空間小，算法GA和MGA均可取得較好的解。隨著算例規(guī)模的增大，解空間也隨之增加，GA存在陷入局部收斂問(wèn)題，而本文所提的MGA通過(guò)所設(shè)計(jì)的交叉變異操作具有跳出局部收斂的能力，因此取得解的質(zhì)量比GA更好。運(yùn)行時(shí)間的統(tǒng)計(jì)表明，MGA的運(yùn)行時(shí)間與GA無(wú)明顯區(qū)別。因此上述實(shí)驗(yàn)結(jié)果表明，本文所提出的MGA在保證優(yōu)化速度的同時(shí)，可獲得更好的任務(wù)分配解，性能顯著優(yōu)于GA。

實(shí)際上，GA是構(gòu)建含有任務(wù)序列的單條染色體，且變異操作修改較少的基因點(diǎn)位，而MGA是構(gòu)建含有機(jī)器人序列和任務(wù)序列的2條染色體，變異操作選擇部分基因位逆序。2條染色體的進(jìn)化、含逆序的變異等給在種群中出現(xiàn)適應(yīng)度更低的個(gè)體和快速收斂提供更大的可能性。

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

本文研究老年社區(qū)多護(hù)理機(jī)器人協(xié)同任務(wù)分配問(wèn)題?？紤]行程代價(jià)、時(shí)間偏差代價(jià)和任務(wù)收益，建立了多護(hù)理機(jī)器人協(xié)同任務(wù)分配模型。提出了一種基于改進(jìn)型遺傳算法的多機(jī)器人任務(wù)分配方法。為了提高解空間搜索能力，每條染色體包括2條編碼信息，分別對(duì)應(yīng)任務(wù)執(zhí)行信息和機(jī)器人分配信息。利用圖論思想檢測(cè)和修復(fù)可能出現(xiàn)的死鎖，保證最后的任務(wù)分配解是無(wú)死鎖的。最后，仿真實(shí)驗(yàn)驗(yàn)證了提出的改進(jìn)型遺傳任務(wù)分配算法的有效性和可行性。