許　爍，王　陽，孫成愷

(1.上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院，上海200072; 2.上海市智能制造及機(jī)器人重點(diǎn)實(shí)驗(yàn)室，上海200072)

?

模塊化可重構(gòu)服務(wù)機(jī)器人群的任務(wù)規(guī)劃

許爍1，2，王陽1，孫成愷1

(1.上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院，上海200072; 2.上海市智能制造及機(jī)器人重點(diǎn)實(shí)驗(yàn)室，上海200072)

摘要：對(duì)模塊化可重構(gòu)服務(wù)機(jī)器人群在醫(yī)院中應(yīng)用所產(chǎn)生的任務(wù)規(guī)劃問題進(jìn)行了分析和建模，提煉出一個(gè)多目標(biāo)、多約束的多維組合優(yōu)化問題.設(shè)計(jì)了改進(jìn)二進(jìn)制蜜蜂算法(IBBA)進(jìn)行組合方案尋優(yōu).作為一種啟發(fā)式群智能優(yōu)化算法，其特點(diǎn)在于:(1)全局搜索和局部搜索的功能劃分明確且并行實(shí)施;(2)在基本算法框架中融入了組合方案的表示與進(jìn)化方法、多目標(biāo)處理方法、約束處理方法等要素;(3)在算法原型的基礎(chǔ)上改進(jìn)了局部搜索策略.針對(duì)一個(gè)實(shí)際算例進(jìn)行了優(yōu)化計(jì)算，算法在可行性、穩(wěn)定性、計(jì)算結(jié)果質(zhì)量、計(jì)算效率、單目標(biāo)優(yōu)化等方面取得了較好表現(xiàn)，并從算法機(jī)制中得到了合理解釋.擴(kuò)展了模塊化可重構(gòu)機(jī)器人的研究范疇，為多目標(biāo)、多約束的多維組合優(yōu)化問題提出了通用的建模方法和優(yōu)化算法.

關(guān)鍵詞：模塊化可重構(gòu)機(jī)器人;機(jī)器人群;多維分配問題;組合優(yōu)化問題;改進(jìn)二進(jìn)制蜜蜂算法

1　引言

與傳統(tǒng)機(jī)器人相比，模塊化可重構(gòu)機(jī)器人(Modular and Reconfigurable Robot，MRR)在提高工作柔性、降低設(shè)備成本等方面具有明顯優(yōu)勢(shì)，因此在生產(chǎn)、生活中獲得了日益廣泛的應(yīng)用，其研究領(lǐng)域也不斷擴(kuò)展［1］.

模塊化可重構(gòu)機(jī)器人的研究目前主要集中在以下幾個(gè)方面:

(1)模塊設(shè)計(jì).例如，文獻(xiàn)［2］為行走、連桿、關(guān)節(jié)、執(zhí)行等子系統(tǒng)配置了不同結(jié)構(gòu)、不同尺寸的模塊，使操作者能夠根據(jù)工作要求選擇合適的模塊組合成所需要的機(jī)器人構(gòu)形.文獻(xiàn)［3］提出設(shè)計(jì)一種可獨(dú)立運(yùn)動(dòng)、具有豐富連接面、結(jié)構(gòu)簡(jiǎn)單的單元模塊.

(2)構(gòu)形設(shè)計(jì)與辨識(shí).“構(gòu)形設(shè)計(jì)”指根據(jù)具體任務(wù)確定機(jī)器人的最佳構(gòu)形，包括構(gòu)形的表達(dá)、設(shè)計(jì)、評(píng)價(jià)、優(yōu)化等內(nèi)容［4，5］.當(dāng)模塊重新組合后對(duì)新的構(gòu)形進(jìn)行識(shí)別即“構(gòu)形辨識(shí)”.例如，文獻(xiàn)［6］提出一種基于上層數(shù)據(jù)庫與底層接口電路相結(jié)合的構(gòu)形在線自主辨識(shí)方法，分三步完成關(guān)節(jié)模塊類型與數(shù)量辨識(shí)、關(guān)節(jié)模塊排序辨識(shí)和連桿模塊類型辨識(shí).

(3)運(yùn)動(dòng)學(xué)建模與求解，包括正運(yùn)動(dòng)學(xué)［7～9］和逆運(yùn)動(dòng)學(xué)［8～10］.例如，文獻(xiàn)［9］利用D-H方法建立了子機(jī)器人的運(yùn)動(dòng)學(xué)模型，并給出了運(yùn)動(dòng)學(xué)正解;同時(shí)，綜合運(yùn)用代數(shù)法、幾何法原理和空間投影關(guān)系，結(jié)合子機(jī)器人的結(jié)構(gòu)特殊性，推導(dǎo)出運(yùn)動(dòng)學(xué)逆解，從而得到工作空間內(nèi)全部的解.

(4)運(yùn)動(dòng)規(guī)劃與控制.例如，上述文獻(xiàn)［9］在運(yùn)動(dòng)學(xué)建模的基礎(chǔ)上，通過考慮可重構(gòu)機(jī)器人結(jié)構(gòu)間的約束關(guān)系，提出了一種適合該結(jié)構(gòu)的軌跡規(guī)劃方法.文獻(xiàn)［11］在每個(gè)模塊關(guān)節(jié)處設(shè)置了一個(gè)制動(dòng)器和嵌入式彈簧，通過對(duì)這些制動(dòng)器和彈簧進(jìn)行協(xié)調(diào)控制提高了機(jī)器人的承載性能.

顯然，上述研究均將機(jī)器人承擔(dān)的工作任務(wù)已知作為前提條件.但是，對(duì)于模塊化可重構(gòu)機(jī)器人群一類的多agent系統(tǒng)(一例為歐盟第六框架項(xiàng)目IWARD［12］)，這個(gè)前提條件并不成立，反之需要在線對(duì)各個(gè)agent進(jìn)行任務(wù)分配.因此，模塊化可重構(gòu)機(jī)器人群的“構(gòu)形設(shè)計(jì)”問題實(shí)際上擴(kuò)展為任務(wù)分配與構(gòu)形設(shè)計(jì)相結(jié)合的綜合性問題.

在IWARD項(xiàng)目中，一組模塊化可重構(gòu)服務(wù)機(jī)器人在醫(yī)院執(zhí)行引導(dǎo)、監(jiān)控、配送、清掃等四類輔助任務(wù)，要求系統(tǒng)自主地將這些任務(wù)合理分配給各個(gè)機(jī)器人，同時(shí)要求機(jī)器人有相應(yīng)的構(gòu)形(即在機(jī)器人平臺(tái)上預(yù)先搭載相應(yīng)類型的任務(wù)模塊)與之匹配.此外，醫(yī)院里還設(shè)置了一定數(shù)量的?？空竟C(jī)器人停放和充電，因此還需要為機(jī)器人群分配?？空?文獻(xiàn)［13，14］對(duì)這個(gè)二維組合優(yōu)化問題進(jìn)行了研究.但是，由于沒有明確各項(xiàng)任務(wù)的執(zhí)行時(shí)間，從而導(dǎo)致計(jì)算得到的任務(wù)分配方案無法實(shí)際執(zhí)行.

鑒于此，本文將該問題進(jìn)一步擴(kuò)展為模塊化可重構(gòu)服務(wù)機(jī)器人群的任務(wù)規(guī)劃問題，在向各個(gè)機(jī)器人分配任務(wù)(模塊)和?？空镜耐瑫r(shí)確定各項(xiàng)任務(wù)的執(zhí)行時(shí)間，即增加一維將任務(wù)向時(shí)間域的分配.問題的改變將會(huì)對(duì)優(yōu)化目標(biāo)、約束條件和算法機(jī)制產(chǎn)生顯著影響.

2　問題分析與建模

2.1問題分析

設(shè)定該問題中有M個(gè)常規(guī)任務(wù)、R個(gè)機(jī)器人平臺(tái)和H個(gè)?？空荆渲?，引導(dǎo)、監(jiān)控、配送、清掃四類常規(guī)任務(wù)數(shù)分別為M1、M2、M3、M4.此處，“常規(guī)任務(wù)”指可以預(yù)知數(shù)量并提前規(guī)劃的任務(wù)，如常規(guī)清掃、定期監(jiān)控、定時(shí)送藥等.除此之外，醫(yī)院中還可能會(huì)有一些不可預(yù)測(cè)的任務(wù)發(fā)生，如新入院病人引導(dǎo)、緊急事件處理等.因此，機(jī)器人群任務(wù)規(guī)劃的目標(biāo)是，一方面合理安排常規(guī)任務(wù)，另一方面最大限度地保留應(yīng)對(duì)不可預(yù)測(cè)任務(wù)的能力.

在問題解決過程中必須滿足以下約束條件:

(1)每項(xiàng)常規(guī)任務(wù)必須分配且只能分配給一個(gè)機(jī)器人;

(2)每個(gè)機(jī)器人必須分配且只能分配到一個(gè)停靠站;

(3)每個(gè)機(jī)器人能夠搭載的任務(wù)模塊數(shù)量有限;

(4)每個(gè)機(jī)器人不得重復(fù)搭載同類任務(wù)模塊;

(5)每項(xiàng)常規(guī)任務(wù)的開始執(zhí)行時(shí)間限制在給定區(qū)間內(nèi);

(6)每個(gè)機(jī)器人承擔(dān)的各項(xiàng)常規(guī)任務(wù)不能存在時(shí)間沖突;

(7)每個(gè)機(jī)器人能夠承擔(dān)的工作量有限;

(8)每類任務(wù)模塊的數(shù)量有限;

(9)每個(gè)?？空镜娜萘坑邢?

綜上所述，這個(gè)模塊化可重構(gòu)服務(wù)機(jī)器人群的任務(wù)規(guī)劃問題可以提煉為一個(gè)兩目標(biāo)、多約束的三維組合優(yōu)化問題.

2.2解的定義

定義一個(gè)M×R的矩陣MR，用于記錄常規(guī)任務(wù)向機(jī)器人分配的情況.其中，M行代表M項(xiàng)常規(guī)任務(wù)，R列代表R個(gè)機(jī)器人;每行中有且只有一個(gè)元素值為1，其余元素值為0，從而滿足“每項(xiàng)常規(guī)任務(wù)必須分配且只能分配給一個(gè)機(jī)器人”的約束條件.類似地，定義一個(gè)R×H的矩陣RH，用于記錄機(jī)器人向?？空痉峙涞那闆r，每行中有且只有一個(gè)元素值為1，其余元素值為0，從而滿足“每個(gè)機(jī)器人必須分配且只能分配到一個(gè)停靠站”的約束條件.定義一個(gè)M元素的數(shù)組st，用于記錄各項(xiàng)常規(guī)任務(wù)開始執(zhí)行的時(shí)間，并分別用M元素?cái)?shù)組stup和stdown定義其上下閾值.

將MR、RH和st的集合定義為問題的一個(gè)解.

2.3優(yōu)化目標(biāo)建模

將第一個(gè)優(yōu)化目標(biāo)設(shè)定為，在保證M項(xiàng)常規(guī)任務(wù)均能夠完成的前提下，使機(jī)器人群的總工作量最小.機(jī)器人群的總常規(guī)工作量由完成這M項(xiàng)常規(guī)任務(wù)所消耗的工作量以及搭載相應(yīng)任務(wù)模塊所消耗的工作量等兩部分構(gòu)成.

由于機(jī)器人?？空九c任務(wù)發(fā)生地點(diǎn)之間的距離影響機(jī)器人執(zhí)行該任務(wù)所消耗的工作量，因此定義一個(gè)M×H的矩陣TH，用于記錄機(jī)器人從不同?？空境霭l(fā)執(zhí)行各項(xiàng)常規(guī)任務(wù)的工作量.根據(jù)矩陣MR、RH和TH計(jì)算第i個(gè)機(jī)器人執(zhí)行常規(guī)任務(wù)所消耗的工作量為

定義一個(gè)M×4的矩陣MT，用于記錄各項(xiàng)常規(guī)任務(wù)的類型，即機(jī)器人執(zhí)行該任務(wù)所需任務(wù)模塊的類型.定義一個(gè)4元素的數(shù)組tm，用于記錄機(jī)器人搭載各類任務(wù)模塊所消耗的工作量.根據(jù)MR、MT和tm計(jì)算機(jī)器人i搭載任務(wù)模塊所消耗的工作量為

式中，符號(hào)函數(shù)sign(·)用于將非零正數(shù)賦值為1，表示機(jī)器人i無論承擔(dān)幾項(xiàng)同類型任務(wù)，都只需配置1個(gè)該類型的任務(wù)模塊，從而滿足約束4.在式(7)和式(15)中，sign(·)函數(shù)也起到同樣的作用.

根據(jù)式(1)和式(2)求得機(jī)器人i的總常規(guī)工作量w(i)以及機(jī)器人群的總常規(guī)工作量tw分別為

第一個(gè)優(yōu)化目標(biāo)可定量表示為tw的最小化:

將第二個(gè)優(yōu)化目標(biāo)設(shè)定為，在保證M項(xiàng)常規(guī)任務(wù)均能夠完成的前提下，使機(jī)器人群處理不可預(yù)測(cè)任務(wù)的能力最強(qiáng).

針對(duì)每個(gè)機(jī)器人定義一個(gè)4×1440的后備能力矩陣MRC，元素值為1或0，用于表示該機(jī)器人在各個(gè)時(shí)間點(diǎn)(以分鐘為單位)處理四類不可預(yù)測(cè)任務(wù)的能力.鑒于處理某類不可預(yù)測(cè)任務(wù)必須同時(shí)滿足有空閑的機(jī)器人、該機(jī)器人搭載了相應(yīng)類型的任務(wù)模塊以及該機(jī)器人有足夠的剩余能量等3個(gè)必要條件，機(jī)器人i的MRC矩陣計(jì)算過程如下:

(1)將MRC矩陣中全部元素賦值為1.

(2)由MR矩陣得到機(jī)器人i分配到的常規(guī)任務(wù)，由MT矩陣得到這些任務(wù)的類型，從而得到機(jī)器人i上搭載的任務(wù)模塊類型.如果機(jī)器人i沒有搭載某類任務(wù)模塊，則將MRC矩陣相應(yīng)行中的全部元素賦值為0，表示機(jī)器人i在任何時(shí)刻均無法執(zhí)行該類不可預(yù)測(cè)任務(wù).

(3)根據(jù)式(3)中機(jī)器人i的總常規(guī)工作量w(i)，求出其執(zhí)行常規(guī)任務(wù)之后的剩余能量rt(i)= wl(i)-w(i).式中，wl(i)表示機(jī)器人i的最大能量.根據(jù)MT 和TH矩陣計(jì)算四類常規(guī)任務(wù)的平均工作量，用它代表同類不可預(yù)測(cè)任務(wù)的平均工作量，記錄在一個(gè)4元素的平均工作量數(shù)組aw中.如果剩余能量rt(i)小于aw中的某個(gè)元素值，則表明機(jī)器人i由于能量不足在任何時(shí)刻均無法執(zhí)行該類不可預(yù)測(cè)任務(wù)，從而將MRC矩陣相應(yīng)行中的全部元素賦值為0.

(4)根據(jù)MR、RH、st和TH計(jì)算機(jī)器人i執(zhí)行各項(xiàng)常規(guī)任務(wù)所占用的時(shí)間區(qū)間，將MRC矩陣中的相應(yīng)元素賦值為0，表示不可預(yù)測(cè)任務(wù)不能與常規(guī)任務(wù)發(fā)生時(shí)間沖突.

(5)將MRC矩陣中執(zhí)行各項(xiàng)常規(guī)任務(wù)所占用時(shí)間區(qū)間之前的相應(yīng)aw(j)(j = 1，2，3，4)范圍內(nèi)的元素賦值為0，同樣表示不可預(yù)測(cè)任務(wù)不能與常規(guī)任務(wù)發(fā)生時(shí)間沖突.

將R個(gè)機(jī)器人的后備能力矩陣MRC相加得到機(jī)器人群的后備能力矩陣MTRC.對(duì)MTRC按行求平均值，得到一個(gè)4元素的數(shù)組an，各元素分別表示機(jī)器人群在各個(gè)時(shí)刻可執(zhí)行該類不可預(yù)測(cè)任務(wù)的平均數(shù).分別用機(jī)器人總數(shù)R減去an中的各個(gè)元素值，得到4元素?cái)?shù)組lc，表示機(jī)器人群由于執(zhí)行常規(guī)任務(wù)而損失的對(duì)各類不可預(yù)測(cè)任務(wù)的處理能力.將第二個(gè)優(yōu)化目標(biāo)定量表示為lc中最大元素值的最小化:

式中，函數(shù)max(·)用于求數(shù)組中的最大元素值.

有必要指出的是，規(guī)劃方案對(duì)上述兩個(gè)優(yōu)化目標(biāo)的影響有些方面相同，有些方面相反.例如，減小各機(jī)器人的常規(guī)工作量能夠同時(shí)改善這兩個(gè)優(yōu)化目標(biāo);但是，增加機(jī)器人群使用的任務(wù)模塊數(shù)量，雖然有利于改善第二個(gè)目標(biāo)，卻會(huì)導(dǎo)致第一個(gè)目標(biāo)的惡化.這說明無法找到任何一種規(guī)劃方案使這兩個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)，反之要尋找一組對(duì)這兩個(gè)目標(biāo)而言的非支配解.

2.4約束建模

約束1和約束2已分別在MR和RH矩陣的建模過程中予以體現(xiàn)，見2.2節(jié).約束4已在優(yōu)化目標(biāo)函數(shù)的建模過程中予以體現(xiàn)，見2.3節(jié).

約束3要求各個(gè)機(jī)器人搭載的任務(wù)模塊的數(shù)量均不超過其最大容量，結(jié)合約束4，即要求搭載的任務(wù)模塊的種類不超過最大容量.以機(jī)器人i為例，根據(jù)MT 和MR矩陣計(jì)算其搭載的任務(wù)模塊的種類為

相應(yīng)的約束為

式中，tl(i)表示機(jī)器人i能夠搭載的任務(wù)模塊的最大容量.

約束5要求將每項(xiàng)常規(guī)任務(wù)的開始執(zhí)行時(shí)間限制在給定區(qū)間內(nèi).以任務(wù)k為例，定量表示為

式中，st(k)、stup(k)和stdown(k)分別表示任務(wù)k的開始執(zhí)行時(shí)間及其上下閾值，均已在2.2節(jié)中定義.

約束6要求每個(gè)機(jī)器人承擔(dān)的各項(xiàng)常規(guī)任務(wù)的執(zhí)行區(qū)間不能重疊.以機(jī)器人i為例，它執(zhí)行任務(wù)k所用的工作量和開始執(zhí)行時(shí)間分別為

將ST矩陣各行中的元素進(jìn)行升序排列，相應(yīng)調(diào)整Wmi矩陣各行中的元素順序.構(gòu)造R×M的矩陣OLC，將第一列元素賦值為0，其余元素賦值如下

進(jìn)一步可求重疊約束數(shù)組ocl，用于統(tǒng)計(jì)OLC矩陣第i行元素中負(fù)數(shù)的個(gè)數(shù)，即機(jī)器人i各項(xiàng)常規(guī)任務(wù)的執(zhí)行區(qū)間發(fā)生重疊的數(shù)量.

約束7要求每個(gè)機(jī)器人的常規(guī)工作量均不超過其最大能量.以機(jī)器人i為例，定量表示為

式中，w(i)和wl(i)分別表示機(jī)器人i的常規(guī)工作量和最大能量，均已在2.3節(jié)中定義.

約束8要求機(jī)器人群執(zhí)行常規(guī)任務(wù)所需要的各類任務(wù)模塊的數(shù)量均不超過其最大備份數(shù)量.如式(15)所示，根據(jù)MT和MR矩陣計(jì)算機(jī)器人群執(zhí)行第j類常規(guī)任務(wù)所需要的任務(wù)模塊的數(shù)量m(j)，則約束8可由式(16)定量表示

式中，ml(j)表示第j類任務(wù)模塊的最大備份數(shù)量.

約束9要求各個(gè)停靠站分配的機(jī)器人的數(shù)量均不超過其最大容量.以?？空緇為例，定量表示為

式中，v(l)和vl(l)分別表示向停靠站l分配機(jī)器人的數(shù)量及其最大容量.

將約束違反總數(shù)sv定義為約束3、約束5、約束6、約束7、約束8和約束9的違反數(shù)量之和，用于比較不可行解的優(yōu)劣，見3.2節(jié).數(shù)學(xué)建模如下

R

式中，stv、sstv、solv、swv、smv和svv分別表示機(jī)器人搭載任務(wù)模塊數(shù)量、任務(wù)開始執(zhí)行時(shí)間、任務(wù)執(zhí)行區(qū)間重疊、機(jī)器人能量、任務(wù)模塊數(shù)量和?？空救萘康燃s束的違反數(shù)量.

3　改進(jìn)二進(jìn)制蜜蜂算法

3.1算法思想

本文提出一種新型的蜜蜂算法——改進(jìn)二進(jìn)制蜜蜂算法(Improved Binary Bees Algorithm，IBBA)作為基本算法框架，協(xié)調(diào)全局搜索和局部搜索，進(jìn)行啟發(fā)式群智能尋優(yōu).同時(shí)，將組合方案的表示與進(jìn)化方法、多目標(biāo)處理方法、約束處理方法等要素融入改進(jìn)二進(jìn)制蜜蜂算法基本框架，用以求解第2節(jié)中提出的多目標(biāo)、多約束的多維組合優(yōu)化問題.

作為一種仿生算法，蜜蜂算法(及其各種變式)的尋優(yōu)過程模仿了蜂群中偵察蜂和工蜂分工合作的覓食機(jī)理［15，16］，由并行實(shí)施的全局搜索和局部搜索構(gòu)成，兩者具有明確的功能劃分——全局搜索算子負(fù)責(zé)隨機(jī)探索(exploration)，局部搜索算子負(fù)責(zé)對(duì)精英個(gè)體鄰域進(jìn)行深度發(fā)掘(exploitation).

文獻(xiàn)［13，14］設(shè)計(jì)了二進(jìn)制蜜蜂算法(BBA)解決機(jī)器人群的任務(wù)分配問題，從而將蜜蜂算法的應(yīng)用領(lǐng)域擴(kuò)展到多維組合優(yōu)化問題.通過與主流的NSGA-II算法和SPEA2算法的對(duì)比試驗(yàn)，一方面證明了“功能劃分、并行搜索”機(jī)制的可行性和優(yōu)勢(shì)，但另一方面也表現(xiàn)出，其采用的“Hamming鄰域”范圍內(nèi)的局部搜索策略(即僅允許在MR或RH矩陣中改變1個(gè)“1”位位置)約束過于苛刻，對(duì)局部搜索效果和計(jì)算量產(chǎn)生了不利影響.因此，有必要對(duì)該策略進(jìn)行調(diào)整.同時(shí)，隨著問題復(fù)雜度的增大、非支配解數(shù)量的增多、局部搜索范圍適度擴(kuò)大，為避免局部搜索力量過于分散，應(yīng)對(duì)精英解(局部搜索中心)的選擇提出更加合理有效的策略.本文提出的改進(jìn)二進(jìn)制蜜蜂算法將著眼于解決這兩個(gè)問題.

3.2算法流程

改進(jìn)二進(jìn)制蜜蜂算法的算法流程如圖1所示，每次循環(huán)均由全局搜索、精英選擇和局部搜索三部分組成.“全局搜索”指在解空間中隨機(jī)搜索新的組合方案.它采取有指導(dǎo)的隨機(jī)搜索策略，為了避免在相同區(qū)域進(jìn)行重復(fù)隨機(jī)搜索，根據(jù)搜索歷史計(jì)算本次全局搜索在解空間中的分布概率，進(jìn)而通過賭輪盤的方法隨機(jī)確定組合方案.

精英選擇在目標(biāo)函數(shù)空間中進(jìn)行，參與對(duì)象包括上一次的非支配解、上一次的局部搜索解和本次的全局搜索解，依次進(jìn)行約束處理、非支配排序和基于均勻度的多樣性保留等三步篩選.其中，約束處理算子采取的策略是，優(yōu)先保留可行解，當(dāng)可行解數(shù)量不足時(shí)，保留約束違反總數(shù)sv較小的不可行解.非支配排序算子采取的策略是，僅保留Pareto Front上的非支配解.多樣性保留算子采取的策略是，一方面直接保留單目標(biāo)最優(yōu)的兩個(gè)解，即Pareto Front的兩個(gè)端點(diǎn);另一方面通過擁擠距離循環(huán)排序選擇，保留在目標(biāo)函數(shù)空間中密度較低、多樣性較顯著的部分非支配解.所謂“擁擠距離循環(huán)排序選擇”指反復(fù)執(zhí)行計(jì)算擁擠距離和排除擁擠距離最小解的步驟，直至剩余解的數(shù)量或其在目標(biāo)函數(shù)空間中的分布均勻度符合要求.與擁擠距離一次性排序選擇的傳統(tǒng)方法［14，17］相比，本方法能夠避免相鄰較近的非支配解子集被同時(shí)排除的問題，從而能夠更好地保留解的多樣性.

“局部搜索”指在解空間中對(duì)挑選出的精英方案進(jìn)行微調(diào).參照文獻(xiàn)［18］中針對(duì)函數(shù)優(yōu)化問題提出的自適應(yīng)策略，根據(jù)最優(yōu)解的來源和進(jìn)化效率動(dòng)態(tài)調(diào)整局部搜索范圍(即MR、RH和st中“1”位改變的數(shù)量).在此范圍內(nèi)，以挑選出的精英解為中心進(jìn)行隨機(jī)調(diào)整.

4　試驗(yàn)

4.1試驗(yàn)條件

硬件配置主要包括，Intel+CoreTMi3處理器、2.00G內(nèi)存.

軟件配置主要包括，32位Windows7操作系統(tǒng)、MATLAB R2008a版本.

程序代碼未進(jìn)行優(yōu)化.

程序終止條件為，Pareto Front穩(wěn)定10次.

4.2試驗(yàn)參數(shù)

根據(jù)對(duì)某醫(yī)院實(shí)際情況的調(diào)查，將本算例中的參數(shù)設(shè)置如下:

4.3求解示例

本試驗(yàn)的目的在于，利用3.2節(jié)中提出的改進(jìn)二進(jìn)制蜜蜂算法對(duì)本算例進(jìn)行優(yōu)化計(jì)算，檢驗(yàn)算法可行性，并分析目標(biāo)函數(shù)空間和解空間中解的含義.

在目標(biāo)函數(shù)空間中最終計(jì)算得到的Pareto Front如圖2所示，包括5個(gè)非支配解.方案1表示機(jī)器人群的總常規(guī)工作量最小，但處理不可預(yù)測(cè)任務(wù)的能力最弱;相反，方案5表示機(jī)器人群處理不可預(yù)測(cè)任務(wù)的能力最強(qiáng)，但總常規(guī)工作量最大;中間三個(gè)解在不同程度上對(duì)兩個(gè)優(yōu)化目標(biāo)進(jìn)行平衡.

上述每個(gè)非支配解都對(duì)應(yīng)解空間中的一種或多種分配方案.以方案4為例，其分配方案如表1所示，從中可得MR、RH和st的值.

4.4擁擠距離循環(huán)選擇法示例

本試驗(yàn)的目的在于，演示擁擠距離循環(huán)選擇法的工作過程，并與一次性排序選擇法進(jìn)行對(duì)比評(píng)價(jià).

圖3所示為優(yōu)化計(jì)算過程中出現(xiàn)的一組(8個(gè))非支配解，它們的歸一化擁擠距離如表2所示(其中，單目標(biāo)最優(yōu)的兩個(gè)解直接保留，無需計(jì)算擁擠距離).在第一次循環(huán)中排除擁擠距離最小的解2，剩余7個(gè)解的分布如圖4所示.重新計(jì)算它們之間的擁擠距離，結(jié)果如表3所示.排除擁擠距離最小的解6后，剩余6個(gè)解的分布如圖5所示，它們歸一化擁擠距離的標(biāo)準(zhǔn)差/均值為0.05/0.59.

若采用擁擠距離一次性排序選擇法處理圖3中的這組非支配解，則根據(jù)表2中的數(shù)據(jù)，將排除擁擠距離最小的解2和解3.剩余6個(gè)解的分布如圖6所示，它們歸一化擁擠距離的標(biāo)準(zhǔn)差/均值為0.22/0.53，分布均勻度明顯不及圖5中的結(jié)果.

4.5算法性能比較

本組試驗(yàn)的目的在于，對(duì)改進(jìn)二進(jìn)制蜜蜂算法(IBBA)在計(jì)算結(jié)果質(zhì)量、計(jì)算效率和單目標(biāo)優(yōu)化等方面的表現(xiàn)進(jìn)行評(píng)估.各項(xiàng)試驗(yàn)均采用文獻(xiàn)［14］中提出的二進(jìn)制蜜蜂算法原型(BBA)作為對(duì)比算法，均進(jìn)行10次重復(fù)計(jì)算以增加結(jié)果的可靠性.

表1　分配方案4在解空間中的情況

表2　第一次循環(huán)選擇時(shí)的非支配解的擁擠距離

表3　第二次循環(huán)選擇時(shí)的非支配解的擁擠距離

4.5.1計(jì)算結(jié)果質(zhì)量

采用S指標(biāo)和C指標(biāo)［19］定量評(píng)估IBBA和BBA的計(jì)算結(jié)果質(zhì)量.S(A)表示算法A的支配區(qū)域，C(A，B)表示算法B的非支配解被算法A的非支配解弱支配的比例.如果S(A)- S(B)大于0，C(A，B)近似等于1，C(B，A)近似等于0，則可判斷算法A計(jì)算結(jié)果的質(zhì)量?jī)?yōu)于算法B，反之亦然.由于IBBA和BBA各進(jìn)行10次計(jì)算，因此兩者在S指標(biāo)和C指標(biāo)上均有100組數(shù)據(jù)，以其統(tǒng)計(jì)結(jié)果作為質(zhì)量評(píng)價(jià)依據(jù).

表4記錄了IBBA和BBA的100組S指標(biāo)差的統(tǒng)計(jì)結(jié)果，包括正數(shù)百分比、最大值、最小值和平均值.IBBA在以下三個(gè)方面表現(xiàn)出對(duì)BBA的優(yōu)勢(shì):(1)S指標(biāo)差在大多數(shù)情況下為正數(shù)(83%);(2)最大值大于最小值的絕對(duì)值;(3)平均值為正數(shù).

表4　S指標(biāo)差的統(tǒng)計(jì)結(jié)果

表5記錄了IBBA和BBA的100組C指標(biāo)的統(tǒng)計(jì)結(jié)果，包括發(fā)生整組非支配解被完全弱支配的百分比以及C指標(biāo)的最大值、最小值和平均值.IBBA再次表現(xiàn)出優(yōu)勢(shì):(1)在100組計(jì)算結(jié)果中，BBA的一組非支配解被IBBA的一組非支配解完全弱支配的情況發(fā)生了7次，反之則沒有發(fā)生;(2)C(IBBA，BBA)的平均值遠(yuǎn)大于C(BAA，IBBA)的平均值.

表5　C指標(biāo)的統(tǒng)計(jì)結(jié)果

4.5.2計(jì)算效率

采用迭代計(jì)算過程中累計(jì)產(chǎn)生的解的數(shù)量作為計(jì)算效率的評(píng)估指標(biāo).10次試驗(yàn)的統(tǒng)計(jì)結(jié)果如表6所示，IBBA解的數(shù)量比BBA平均少12.7%，計(jì)算效率優(yōu)勢(shì)明顯.原因如下:根據(jù)4.4節(jié)中的試驗(yàn)結(jié)果，IBBA采用擁擠距離循環(huán)選擇法避免了相鄰較近的非支配解子集被同時(shí)排除的問題，使保留下來的精英解在目標(biāo)函數(shù)空間中分布得比較均勻.可以合理地預(yù)見，其在解空間中也分布得比較均勻.因此，以這些精英解為中心進(jìn)行局部搜索，既能夠避免由于它們距離太近而導(dǎo)致的對(duì)所在鄰域過度搜索的問題，又能夠避免由于同一鄰域內(nèi)的非支配解全部被排除而導(dǎo)致無法對(duì)該鄰域進(jìn)行搜索的問題，從而能夠在解空間中合理分配局部搜索的計(jì)算資源.這有利于提高計(jì)算效率.此外，IBBA根據(jù)最優(yōu)解的來源和進(jìn)化效率自適應(yīng)調(diào)節(jié)局部搜索的鄰域范圍，從而能夠在保證計(jì)算精度(局部搜索的基本功能)的前提下，進(jìn)一步提高計(jì)算效率.

表6　累計(jì)產(chǎn)生的解的數(shù)量的統(tǒng)計(jì)結(jié)果

4.5.3單目標(biāo)優(yōu)化

單目標(biāo)優(yōu)化是多目標(biāo)優(yōu)化中的一個(gè)重要指標(biāo)，表征了非支配解的分布范圍，這也是在精英選擇中直接保留單目標(biāo)最優(yōu)的兩個(gè)非支配解的原因.表7記錄了IBBA和BBA的10組單目標(biāo)最小值及其統(tǒng)計(jì)結(jié)果.在最大值、最小值、平均值和標(biāo)準(zhǔn)差等各項(xiàng)統(tǒng)計(jì)指標(biāo)上，IBBA的兩個(gè)單目標(biāo)最小值的表現(xiàn)都優(yōu)于BBA.這主要是由于在圍繞單目標(biāo)最優(yōu)解進(jìn)行局部搜索時(shí)，IBBA能夠自適應(yīng)調(diào)整搜索空間，從而增加單目標(biāo)最優(yōu)解獲得改進(jìn)的機(jī)會(huì).

有必要指出的是，上述計(jì)算結(jié)果質(zhì)量、計(jì)算效率和單目標(biāo)優(yōu)化的各項(xiàng)指標(biāo)具有一定的關(guān)聯(lián)性.例如，單目標(biāo)最優(yōu)解獲得改進(jìn)與非支配解均勻分布均有利于S指標(biāo)的改善.

表7　IBBA和BBA的10組單目標(biāo)最小值及其統(tǒng)計(jì)結(jié)果

5　結(jié)論

(1)將醫(yī)院中模塊化可重構(gòu)服務(wù)機(jī)器人群任務(wù)規(guī)劃這一工程問題提煉為一個(gè)多目標(biāo)、多約束的多維組合優(yōu)化問題求解，擴(kuò)展了模塊化可重構(gòu)機(jī)器人的研究范疇.

(2)提出改進(jìn)二進(jìn)制蜜蜂算法作為基本算法框架，融入組合方案的表示與進(jìn)化方法、多目標(biāo)處理方法、約束處理方法等要素，解決了此優(yōu)化問題.

(3)提出的改進(jìn)二進(jìn)制蜜蜂算法在計(jì)算結(jié)果質(zhì)量、計(jì)算效率和單目標(biāo)優(yōu)化等方面的表現(xiàn)優(yōu)于其算法原型，并且能夠從算法機(jī)制中得到合理解釋.

參考文獻(xiàn)

［1］王兵，蔣蓁.模塊化重構(gòu)機(jī)器人技術(shù)的現(xiàn)狀與發(fā)展綜述［J］.機(jī)電工程，2008，25(5): 1 - 4.Wang Bing，Jiang Zhen.Review on the status and development of modular reconfigurable robot technology［J］.Jourhal of Mechanical＆Electrical Engineering，2008，25(5): 1 -4.(in Chinese)

［2］孫美艷，朱龍英，趙忠偉.可重構(gòu)環(huán)保機(jī)器人模塊設(shè)計(jì)［J］.機(jī)械傳動(dòng)，2010，34(3):43 -45.Sun Mei-yan，Zhu Long-ying，Zhao Zhong-wei.Module design of reconfigurable environment robots［J］.Journal of Mechanical Transmission，2010，34(3):43 -45.(in Chinese)

［3］曹燕軍，葛為民，張華瑾.一種新型模塊化自重構(gòu)機(jī)器人結(jié)構(gòu)設(shè)計(jì)與仿真研究［J］.機(jī)器人，2013，35(5):568 -575.Cao Yan-jun，Ge Wei-min，Zhang Hua-jin.Structure design and simulation analysis of an innovative modular self-reconfigurable Robot-360bot［J］.Robot，2013，35(5): 568 -575.(in Chinese)

［4］D Oetomo，D Daney，K Harada，et al.Topology design of surgical reconfigurable robots by interval analysis［A］.Proceedings of ICRA［C］.Kobe，Japan: IEEE Press，2009.3085 -3090.

［5］吳文強(qiáng)，管貽生，等.面向任務(wù)的可重構(gòu)模塊化機(jī)器人構(gòu)型設(shè)計(jì)［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2014，46(3): 93 -98.Wu Wen-qiang，Guan Yi-sheng，et al.Task-oriented configuration design of reconfigurable modular robots［J］.Journal of Harbin Institute of Technology，2014，46(3): 93 - 98.(in Chinese)

［6］姜勇，王洪光，潘新安，等.模塊化可重構(gòu)機(jī)器人的構(gòu)形在線自主辨識(shí)［J］.機(jī)械工程學(xué)報(bào)，2011，47(15):17 -24.Jiang Yong，Wang Hong-guang，Pan Xin-an，et al.Autonomous online identification of configurations for modular reconfigurable robot［J］.Journal of Mechanical Engineering，2011，47(15): 17 -24.(in Chinese)

［7］王洪波，徐桂玲，等.助老助殘四足/兩足可重構(gòu)并聯(lián)腿步行機(jī)器人運(yùn)動(dòng)學(xué)建模與仿真［J］.燕山大學(xué)學(xué)報(bào)，2010，34(6): 508 -515.Wang Hong-bo，Xu Gui-ling，et al.Kinematics modeling and simulation of quadruped/biped walking robot with parallel leg mechanism for the elderly and the disabled［J］.Journal of Yanshan University，2010，34(6): 508 -515.(in Chinese)

［8］高文斌，等.一種可重構(gòu)模塊化機(jī)器人系統(tǒng)的運(yùn)動(dòng)學(xué)研究［J］.機(jī)械設(shè)計(jì)與制造，2012(10): 122 -124.Gao Wen-bin，et al.Research on the kinematics of a modular reconfigurable robot system［J］.Machinery Design＆Manufacture，2012(10): 122 -124.(in Chinese)

［9］張力平，等.可重構(gòu)星球探測(cè)機(jī)器人的運(yùn)動(dòng)學(xué)建模及軌跡規(guī)劃［J］.西安交通大學(xué)學(xué)報(bào)，2005，39(1): 87 -91.Zhang Li-ping，et al.Kinematic modeling and trajectory planning for reconfigurable planetary robot system［J］.Journal of Xi’an Jiaotong University，2005，39(1): 87 -91.(in Chinese)

［10］W Wu，Y Guan，H Li，et al.Task-oriented inverse kinematics of modular reconfigurable robots［A］.Proceedings of AIM［C］.Wollongong，Australia: IEEE Press，2013.1187 -1192.

［11］G Liu，Y Liu，et al.Design，analysis，and control of a spring-assisted modular and reconfigurable robot［J］.IEEE/ASME Transactions on Mechatronics，2011，16(4): 695 -706.

［12］IWARD Project［OL］.http: / /www.iward.eu，2015 - 07 -21.

［13］SXu，Z Ji，D T Pham，et al.Bio-inspired binary bees algorithm for a two-level distribution optimisation problem［J］.Journal of Bionic Engineering，2010，7(2):161 -167.

［14］S Xu，Z Ji，D T Pham，et al.Binary bees algorithm: Bioinspiration from the foraging mechanism of honeybees to optimize a multi-objective multidimensional assignment problem［J］.Engineering Optimization，2011，43(11): 1141 -1159.

［15］KVon Frisch.The Dance Language and Orientation of Bees ［M］.Cambridge，MA: Harvard University Press，1967.

［16］D T Pham，A Ghanbarzadeh，E Koc，et al.The bees algorithm: A novel tool for complex optimisation problems ［A］.Proceedings of IPROMS［C］.Cardiff，UK: Elsevier Press，2006.454 -459.

［17］李中凱，李艾民，朱真才.擁擠距離排序的多目標(biāo)文化粒子群優(yōu)化算法［J］.控制與決策，2012，27(9): 1406 -1410.Li Zhong-kai，Li Ai-min，Zhu Zhen-cai.Cultural based multi-objective particle swarm optimization algorithm using crowding distance sorting method［J］.Control and Decision，2012，27(9): 1406 -1410.(in Chinese)

［18］S Xu，F(xiàn) Yu，Z Luo，et al.Adaptive bees algorithm: Bioinspiration from honeybee foraging to optimize fuel economy of a semi-track air-cushion vehicle［J］.The Computer Journal，2011，54(9): 1416 -1426.

［19］E Zitzler.Evolutionary Algorithm for Multiobjective Optimization: Methods and Applications［D］.Zurich: A Dissertation in Swiss Federal Institute of Technology，1999.

許爍男，1982年8月出生，河北望都人，副教授、碩士生導(dǎo)師.2005年和2011年分別在上海交通大學(xué)獲工學(xué)學(xué)士和工學(xué)博士學(xué)位.現(xiàn)為上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院教師，主要從事服務(wù)機(jī)器人機(jī)器智能與人機(jī)關(guān)系、計(jì)算智能等方面的研究工作.

E-mail: sxu@ shu.edu.cn

王陽男，1993年9月出生，安徽淮南人.2013年在安徽工業(yè)大學(xué)獲工學(xué)學(xué)士學(xué)位.現(xiàn)為上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院碩士研究生，主要從事計(jì)算智能方面的研究工作.

孫成愷男，1987年4月出生，河南新鄉(xiāng)人.2011年和2014年分別在河南理工大學(xué)和上海大學(xué)獲工學(xué)學(xué)士和工學(xué)碩士學(xué)位.現(xiàn)為上海德邁科電氣控制工程有限公司項(xiàng)目工程師.

Mission Planning for a Team of Modular and Reconfigurable Service Robots

XU Shuo1，2，WANG Yang1，SUN Cheng-kai1
(1.School of Mechatronic Engineering and Automation，Shanghai University，Shanghai 200072，China; 2.Shanghai Key Laboratory of Intelligent Manufacturing and Robotics，Shanghai 200072，China)

Abstract:The mission planning problem of a team of modular and reconfigurable robots(MRRs)in hospital service is studied.By analyzing and modeling，it is abstracted as a multidimensional combinatorial optimization problem with multiobjectives and multiconstraints.A population-based metaheuristic，the Improved Binary Bees Algorithm(IBBA)，is proposed to optimize this NP-hard problem.The IBBA is featured as，1)Functional partitioning and parallel implementation of global search and local search; 2)Integrating the methods of combinatorial schemes’expression and evolution，multiobjectives’handling and constraints’handing into the basic algorithm framework; and 3)Improving local search strategy from the prototype algorithm.Experiments are conducted with respect to a practical example.The IBBA exhibits feasibility，stability and advantages over its prototype algorithm in indices of solution quality，computational efficiency and single-objective optimization.Further，the advantages are interpretable from algorithm mechanisms.This study extends the field of research of MMR，and provides a general modeling method and optimization algorithm to solve general combinatorial optimization problems with multiobjectives and multiconstraints.

Key words:modular and reconfigurable robot(MRR); robot team; multidimensional assignment problem(MAP); combinatorial optimization problem(COP); improved binary bee algorithm

作者簡(jiǎn)介

基金項(xiàng)目:國(guó)家自然科學(xué)基金(No.61203351)

收稿日期:2014-04-09;修回日期: 2015-08-18;責(zé)任編輯:孫瑤

DOI:電子學(xué)報(bào)URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.015

中圖分類號(hào)：TP242

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0372-2112(2015)01-0101-09