许　烁，王　阳，孙成恺

(1.上海大学机电工程与自动化学院，上海200072; 2.上海市智能制造及机器人重点实验室，上海200072)



模块化可重构服务机器人群的任务规划

许烁1，2，王阳1，孙成恺1

(1.上海大学机电工程与自动化学院，上海200072; 2.上海市智能制造及机器人重点实验室，上海200072)

摘要：对模块化可重构服务机器人群在医院中应用所产生的任务规划问题进行了分析和建模，提炼出一个多目标、多约束的多维组合优化问题.设计了改进二进制蜜蜂算法(IBBA)进行组合方案寻优.作为一种启发式群智能优化算法，其特点在于:(1)全局搜索和局部搜索的功能划分明确且并行实施;(2)在基本算法框架中融入了组合方案的表示与进化方法、多目标处理方法、约束处理方法等要素;(3)在算法原型的基础上改进了局部搜索策略.针对一个实际算例进行了优化计算，算法在可行性、稳定性、计算结果质量、计算效率、单目标优化等方面取得了较好表现，并从算法机制中得到了合理解释.扩展了模块化可重构机器人的研究范畴，为多目标、多约束的多维组合优化问题提出了通用的建模方法和优化算法.

关键词：模块化可重构机器人;机器人群;多维分配问题;组合优化问题;改进二进制蜜蜂算法

1　引言

与传统机器人相比，模块化可重构机器人(Modular and Reconfigurable Robot，MRR)在提高工作柔性、降低设备成本等方面具有明显优势，因此在生产、生活中获得了日益广泛的应用，其研究领域也不断扩展［1］.

模块化可重构机器人的研究目前主要集中在以下几个方面:

(1)模块设计.例如，文献［2］为行走、连杆、关节、执行等子系统配置了不同结构、不同尺寸的模块，使操作者能够根据工作要求选择合适的模块组合成所需要的机器人构形.文献［3］提出设计一种可独立运动、具有丰富连接面、结构简单的单元模块.

(2)构形设计与辨识.“构形设计”指根据具体任务确定机器人的最佳构形，包括构形的表达、设计、评价、优化等内容［4，5］.当模块重新组合后对新的构形进行识别即“构形辨识”.例如，文献［6］提出一种基于上层数据库与底层接口电路相结合的构形在线自主辨识方法，分三步完成关节模块类型与数量辨识、关节模块排序辨识和连杆模块类型辨识.

(3)运动学建模与求解，包括正运动学［7～9］和逆运动学［8～10］.例如，文献［9］利用D-H方法建立了子机器人的运动学模型，并给出了运动学正解;同时，综合运用代数法、几何法原理和空间投影关系，结合子机器人的结构特殊性，推导出运动学逆解，从而得到工作空间内全部的解.

(4)运动规划与控制.例如，上述文献［9］在运动学建模的基础上，通过考虑可重构机器人结构间的约束关系，提出了一种适合该结构的轨迹规划方法.文献［11］在每个模块关节处设置了一个制动器和嵌入式弹簧，通过对这些制动器和弹簧进行协调控制提高了机器人的承载性能.

显然，上述研究均将机器人承担的工作任务已知作为前提条件.但是，对于模块化可重构机器人群一类的多agent系统(一例为欧盟第六框架项目IWARD［12］)，这个前提条件并不成立，反之需要在线对各个agent进行任务分配.因此，模块化可重构机器人群的“构形设计”问题实际上扩展为任务分配与构形设计相结合的综合性问题.

在IWARD项目中，一组模块化可重构服务机器人在医院执行引导、监控、配送、清扫等四类辅助任务，要求系统自主地将这些任务合理分配给各个机器人，同时要求机器人有相应的构形(即在机器人平台上预先搭载相应类型的任务模块)与之匹配.此外，医院里还设置了一定数量的停靠站供机器人停放和充电，因此还需要为机器人群分配停靠站.文献［13，14］对这个二维组合优化问题进行了研究.但是，由于没有明确各项任务的执行时间，从而导致计算得到的任务分配方案无法实际执行.

鉴于此，本文将该问题进一步扩展为模块化可重构服务机器人群的任务规划问题，在向各个机器人分配任务(模块)和停靠站的同时确定各项任务的执行时间，即增加一维将任务向时间域的分配.问题的改变将会对优化目标、约束条件和算法机制产生显著影响.

2　问题分析与建模

2.1问题分析

设定该问题中有M个常规任务、R个机器人平台和H个停靠站，其中，引导、监控、配送、清扫四类常规任务数分别为M1、M2、M3、M4.此处，“常规任务”指可以预知数量并提前规划的任务，如常规清扫、定期监控、定时送药等.除此之外，医院中还可能会有一些不可预测的任务发生，如新入院病人引导、紧急事件处理等.因此，机器人群任务规划的目标是，一方面合理安排常规任务，另一方面最大限度地保留应对不可预测任务的能力.

在问题解决过程中必须满足以下约束条件:

(1)每项常规任务必须分配且只能分配给一个机器人;

(2)每个机器人必须分配且只能分配到一个停靠站;

(3)每个机器人能够搭载的任务模块数量有限;

(4)每个机器人不得重复搭载同类任务模块;

(5)每项常规任务的开始执行时间限制在给定区间内;

(6)每个机器人承担的各项常规任务不能存在时间冲突;

(7)每个机器人能够承担的工作量有限;

(8)每类任务模块的数量有限;

(9)每个停靠站的容量有限.

综上所述，这个模块化可重构服务机器人群的任务规划问题可以提炼为一个两目标、多约束的三维组合优化问题.

2.2解的定义

定义一个M×R的矩阵MR，用于记录常规任务向机器人分配的情况.其中，M行代表M项常规任务，R列代表R个机器人;每行中有且只有一个元素值为1，其余元素值为0，从而满足“每项常规任务必须分配且只能分配给一个机器人”的约束条件.类似地，定义一个R×H的矩阵RH，用于记录机器人向停靠站分配的情况，每行中有且只有一个元素值为1，其余元素值为0，从而满足“每个机器人必须分配且只能分配到一个停靠站”的约束条件.定义一个M元素的数组st，用于记录各项常规任务开始执行的时间，并分别用M元素数组stup和stdown定义其上下阈值.

将MR、RH和st的集合定义为问题的一个解.

2.3优化目标建模

将第一个优化目标设定为，在保证M项常规任务均能够完成的前提下，使机器人群的总工作量最小.机器人群的总常规工作量由完成这M项常规任务所消耗的工作量以及搭载相应任务模块所消耗的工作量等两部分构成.

由于机器人停靠站与任务发生地点之间的距离影响机器人执行该任务所消耗的工作量，因此定义一个M×H的矩阵TH，用于记录机器人从不同停靠站出发执行各项常规任务的工作量.根据矩阵MR、RH和TH计算第i个机器人执行常规任务所消耗的工作量为

定义一个M×4的矩阵MT，用于记录各项常规任务的类型，即机器人执行该任务所需任务模块的类型.定义一个4元素的数组tm，用于记录机器人搭载各类任务模块所消耗的工作量.根据MR、MT和tm计算机器人i搭载任务模块所消耗的工作量为

式中，符号函数sign(·)用于将非零正数赋值为1，表示机器人i无论承担几项同类型任务，都只需配置1个该类型的任务模块，从而满足约束4.在式(7)和式(15)中，sign(·)函数也起到同样的作用.

根据式(1)和式(2)求得机器人i的总常规工作量w(i)以及机器人群的总常规工作量tw分别为

第一个优化目标可定量表示为tw的最小化:

将第二个优化目标设定为，在保证M项常规任务均能够完成的前提下，使机器人群处理不可预测任务的能力最强.

针对每个机器人定义一个4×1440的后备能力矩阵MRC，元素值为1或0，用于表示该机器人在各个时间点(以分钟为单位)处理四类不可预测任务的能力.鉴于处理某类不可预测任务必须同时满足有空闲的机器人、该机器人搭载了相应类型的任务模块以及该机器人有足够的剩余能量等3个必要条件，机器人i的MRC矩阵计算过程如下:

(1)将MRC矩阵中全部元素赋值为1.

(2)由MR矩阵得到机器人i分配到的常规任务，由MT矩阵得到这些任务的类型，从而得到机器人i上搭载的任务模块类型.如果机器人i没有搭载某类任务模块，则将MRC矩阵相应行中的全部元素赋值为0，表示机器人i在任何时刻均无法执行该类不可预测任务.

(3)根据式(3)中机器人i的总常规工作量w(i)，求出其执行常规任务之后的剩余能量rt(i)= wl(i)-w(i).式中，wl(i)表示机器人i的最大能量.根据MT 和TH矩阵计算四类常规任务的平均工作量，用它代表同类不可预测任务的平均工作量，记录在一个4元素的平均工作量数组aw中.如果剩余能量rt(i)小于aw中的某个元素值，则表明机器人i由于能量不足在任何时刻均无法执行该类不可预测任务，从而将MRC矩阵相应行中的全部元素赋值为0.

(4)根据MR、RH、st和TH计算机器人i执行各项常规任务所占用的时间区间，将MRC矩阵中的相应元素赋值为0，表示不可预测任务不能与常规任务发生时间冲突.

(5)将MRC矩阵中执行各项常规任务所占用时间区间之前的相应aw(j)(j = 1，2，3，4)范围内的元素赋值为0，同样表示不可预测任务不能与常规任务发生时间冲突.

将R个机器人的后备能力矩阵MRC相加得到机器人群的后备能力矩阵MTRC.对MTRC按行求平均值，得到一个4元素的数组an，各元素分别表示机器人群在各个时刻可执行该类不可预测任务的平均数.分别用机器人总数R减去an中的各个元素值，得到4元素数组lc，表示机器人群由于执行常规任务而损失的对各类不可预测任务的处理能力.将第二个优化目标定量表示为lc中最大元素值的最小化:

式中，函数max(·)用于求数组中的最大元素值.

有必要指出的是，规划方案对上述两个优化目标的影响有些方面相同，有些方面相反.例如，减小各机器人的常规工作量能够同时改善这两个优化目标;但是，增加机器人群使用的任务模块数量，虽然有利于改善第二个目标，却会导致第一个目标的恶化.这说明无法找到任何一种规划方案使这两个目标同时达到最优，反之要寻找一组对这两个目标而言的非支配解.

2.4约束建模

约束1和约束2已分别在MR和RH矩阵的建模过程中予以体现，见2.2节.约束4已在优化目标函数的建模过程中予以体现，见2.3节.

约束3要求各个机器人搭载的任务模块的数量均不超过其最大容量，结合约束4，即要求搭载的任务模块的种类不超过最大容量.以机器人i为例，根据MT 和MR矩阵计算其搭载的任务模块的种类为

相应的约束为

式中，tl(i)表示机器人i能够搭载的任务模块的最大容量.

约束5要求将每项常规任务的开始执行时间限制在给定区间内.以任务k为例，定量表示为

式中，st(k)、stup(k)和stdown(k)分别表示任务k的开始执行时间及其上下阈值，均已在2.2节中定义.

约束6要求每个机器人承担的各项常规任务的执行区间不能重叠.以机器人i为例，它执行任务k所用的工作量和开始执行时间分别为

将ST矩阵各行中的元素进行升序排列，相应调整Wmi矩阵各行中的元素顺序.构造R×M的矩阵OLC，将第一列元素赋值为0，其余元素赋值如下

进一步可求重叠约束数组ocl，用于统计OLC矩阵第i行元素中负数的个数，即机器人i各项常规任务的执行区间发生重叠的数量.

约束7要求每个机器人的常规工作量均不超过其最大能量.以机器人i为例，定量表示为

式中，w(i)和wl(i)分别表示机器人i的常规工作量和最大能量，均已在2.3节中定义.

约束8要求机器人群执行常规任务所需要的各类任务模块的数量均不超过其最大备份数量.如式(15)所示，根据MT和MR矩阵计算机器人群执行第j类常规任务所需要的任务模块的数量m(j)，则约束8可由式(16)定量表示

式中，ml(j)表示第j类任务模块的最大备份数量.

约束9要求各个停靠站分配的机器人的数量均不超过其最大容量.以停靠站l为例，定量表示为

式中，v(l)和vl(l)分别表示向停靠站l分配机器人的数量及其最大容量.

将约束违反总数sv定义为约束3、约束5、约束6、约束7、约束8和约束9的违反数量之和，用于比较不可行解的优劣，见3.2节.数学建模如下

R

式中，stv、sstv、solv、swv、smv和svv分别表示机器人搭载任务模块数量、任务开始执行时间、任务执行区间重叠、机器人能量、任务模块数量和停靠站容量等约束的违反数量.

3　改进二进制蜜蜂算法

3.1算法思想

本文提出一种新型的蜜蜂算法——改进二进制蜜蜂算法(Improved Binary Bees Algorithm，IBBA)作为基本算法框架，协调全局搜索和局部搜索，进行启发式群智能寻优.同时，将组合方案的表示与进化方法、多目标处理方法、约束处理方法等要素融入改进二进制蜜蜂算法基本框架，用以求解第2节中提出的多目标、多约束的多维组合优化问题.

作为一种仿生算法，蜜蜂算法(及其各种变式)的寻优过程模仿了蜂群中侦察蜂和工蜂分工合作的觅食机理［15，16］，由并行实施的全局搜索和局部搜索构成，两者具有明确的功能划分——全局搜索算子负责随机探索(exploration)，局部搜索算子负责对精英个体邻域进行深度发掘(exploitation).

文献［13，14］设计了二进制蜜蜂算法(BBA)解决机器人群的任务分配问题，从而将蜜蜂算法的应用领域扩展到多维组合优化问题.通过与主流的NSGA-II算法和SPEA2算法的对比试验，一方面证明了“功能划分、并行搜索”机制的可行性和优势，但另一方面也表现出，其采用的“Hamming邻域”范围内的局部搜索策略(即仅允许在MR或RH矩阵中改变1个“1”位位置)约束过于苛刻，对局部搜索效果和计算量产生了不利影响.因此，有必要对该策略进行调整.同时，随着问题复杂度的增大、非支配解数量的增多、局部搜索范围适度扩大，为避免局部搜索力量过于分散，应对精英解(局部搜索中心)的选择提出更加合理有效的策略.本文提出的改进二进制蜜蜂算法将着眼于解决这两个问题.

3.2算法流程

改进二进制蜜蜂算法的算法流程如图1所示，每次循环均由全局搜索、精英选择和局部搜索三部分组成.“全局搜索”指在解空间中随机搜索新的组合方案.它采取有指导的随机搜索策略，为了避免在相同区域进行重复随机搜索，根据搜索历史计算本次全局搜索在解空间中的分布概率，进而通过赌轮盘的方法随机确定组合方案.

精英选择在目标函数空间中进行，参与对象包括上一次的非支配解、上一次的局部搜索解和本次的全局搜索解，依次进行约束处理、非支配排序和基于均匀度的多样性保留等三步筛选.其中，约束处理算子采取的策略是，优先保留可行解，当可行解数量不足时，保留约束违反总数sv较小的不可行解.非支配排序算子采取的策略是，仅保留Pareto Front上的非支配解.多样性保留算子采取的策略是，一方面直接保留单目标最优的两个解，即Pareto Front的两个端点;另一方面通过拥挤距离循环排序选择，保留在目标函数空间中密度较低、多样性较显著的部分非支配解.所谓“拥挤距离循环排序选择”指反复执行计算拥挤距离和排除拥挤距离最小解的步骤，直至剩余解的数量或其在目标函数空间中的分布均匀度符合要求.与拥挤距离一次性排序选择的传统方法［14，17］相比，本方法能够避免相邻较近的非支配解子集被同时排除的问题，从而能够更好地保留解的多样性.

“局部搜索”指在解空间中对挑选出的精英方案进行微调.参照文献［18］中针对函数优化问题提出的自适应策略，根据最优解的来源和进化效率动态调整局部搜索范围(即MR、RH和st中“1”位改变的数量).在此范围内，以挑选出的精英解为中心进行随机调整.

4　试验

4.1试验条件

硬件配置主要包括，Intel+CoreTMi3处理器、2.00G内存.

软件配置主要包括，32位Windows7操作系统、MATLAB R2008a版本.

程序代码未进行优化.

程序终止条件为，Pareto Front稳定10次.

4.2试验参数

根据对某医院实际情况的调查，将本算例中的参数设置如下:

4.3求解示例

本试验的目的在于，利用3.2节中提出的改进二进制蜜蜂算法对本算例进行优化计算，检验算法可行性，并分析目标函数空间和解空间中解的含义.

在目标函数空间中最终计算得到的Pareto Front如图2所示，包括5个非支配解.方案1表示机器人群的总常规工作量最小，但处理不可预测任务的能力最弱;相反，方案5表示机器人群处理不可预测任务的能力最强，但总常规工作量最大;中间三个解在不同程度上对两个优化目标进行平衡.

上述每个非支配解都对应解空间中的一种或多种分配方案.以方案4为例，其分配方案如表1所示，从中可得MR、RH和st的值.

4.4拥挤距离循环选择法示例

本试验的目的在于，演示拥挤距离循环选择法的工作过程，并与一次性排序选择法进行对比评价.

图3所示为优化计算过程中出现的一组(8个)非支配解，它们的归一化拥挤距离如表2所示(其中，单目标最优的两个解直接保留，无需计算拥挤距离).在第一次循环中排除拥挤距离最小的解2，剩余7个解的分布如图4所示.重新计算它们之间的拥挤距离，结果如表3所示.排除拥挤距离最小的解6后，剩余6个解的分布如图5所示，它们归一化拥挤距离的标准差/均值为0.05/0.59.

若采用拥挤距离一次性排序选择法处理图3中的这组非支配解，则根据表2中的数据，将排除拥挤距离最小的解2和解3.剩余6个解的分布如图6所示，它们归一化拥挤距离的标准差/均值为0.22/0.53，分布均匀度明显不及图5中的结果.

4.5算法性能比较

本组试验的目的在于，对改进二进制蜜蜂算法(IBBA)在计算结果质量、计算效率和单目标优化等方面的表现进行评估.各项试验均采用文献［14］中提出的二进制蜜蜂算法原型(BBA)作为对比算法，均进行10次重复计算以增加结果的可靠性.

表1　分配方案4在解空间中的情况

表2　第一次循环选择时的非支配解的拥挤距离

表3　第二次循环选择时的非支配解的拥挤距离

4.5.1计算结果质量

采用S指标和C指标［19］定量评估IBBA和BBA的计算结果质量.S(A)表示算法A的支配区域，C(A，B)表示算法B的非支配解被算法A的非支配解弱支配的比例.如果S(A)- S(B)大于0，C(A，B)近似等于1，C(B，A)近似等于0，则可判断算法A计算结果的质量优于算法B，反之亦然.由于IBBA和BBA各进行10次计算，因此两者在S指标和C指标上均有100组数据，以其统计结果作为质量评价依据.

表4记录了IBBA和BBA的100组S指标差的统计结果，包括正数百分比、最大值、最小值和平均值.IBBA在以下三个方面表现出对BBA的优势:(1)S指标差在大多数情况下为正数(83%);(2)最大值大于最小值的绝对值;(3)平均值为正数.

表4　S指标差的统计结果

表5记录了IBBA和BBA的100组C指标的统计结果，包括发生整组非支配解被完全弱支配的百分比以及C指标的最大值、最小值和平均值.IBBA再次表现出优势:(1)在100组计算结果中，BBA的一组非支配解被IBBA的一组非支配解完全弱支配的情况发生了7次，反之则没有发生;(2)C(IBBA，BBA)的平均值远大于C(BAA，IBBA)的平均值.

表5　C指标的统计结果

4.5.2计算效率

采用迭代计算过程中累计产生的解的数量作为计算效率的评估指标.10次试验的统计结果如表6所示，IBBA解的数量比BBA平均少12.7%，计算效率优势明显.原因如下:根据4.4节中的试验结果，IBBA采用拥挤距离循环选择法避免了相邻较近的非支配解子集被同时排除的问题，使保留下来的精英解在目标函数空间中分布得比较均匀.可以合理地预见，其在解空间中也分布得比较均匀.因此，以这些精英解为中心进行局部搜索，既能够避免由于它们距离太近而导致的对所在邻域过度搜索的问题，又能够避免由于同一邻域内的非支配解全部被排除而导致无法对该邻域进行搜索的问题，从而能够在解空间中合理分配局部搜索的计算资源.这有利于提高计算效率.此外，IBBA根据最优解的来源和进化效率自适应调节局部搜索的邻域范围，从而能够在保证计算精度(局部搜索的基本功能)的前提下，进一步提高计算效率.

表6　累计产生的解的数量的统计结果

4.5.3单目标优化

单目标优化是多目标优化中的一个重要指标，表征了非支配解的分布范围，这也是在精英选择中直接保留单目标最优的两个非支配解的原因.表7记录了IBBA和BBA的10组单目标最小值及其统计结果.在最大值、最小值、平均值和标准差等各项统计指标上，IBBA的两个单目标最小值的表现都优于BBA.这主要是由于在围绕单目标最优解进行局部搜索时，IBBA能够自适应调整搜索空间，从而增加单目标最优解获得改进的机会.

有必要指出的是，上述计算结果质量、计算效率和单目标优化的各项指标具有一定的关联性.例如，单目标最优解获得改进与非支配解均匀分布均有利于S指标的改善.

表7　IBBA和BBA的10组单目标最小值及其统计结果

5　结论

(1)将医院中模块化可重构服务机器人群任务规划这一工程问题提炼为一个多目标、多约束的多维组合优化问题求解，扩展了模块化可重构机器人的研究范畴.

(2)提出改进二进制蜜蜂算法作为基本算法框架，融入组合方案的表示与进化方法、多目标处理方法、约束处理方法等要素，解决了此优化问题.

(3)提出的改进二进制蜜蜂算法在计算结果质量、计算效率和单目标优化等方面的表现优于其算法原型，并且能够从算法机制中得到合理解释.

参考文献

［1］王兵，蒋蓁.模块化重构机器人技术的现状与发展综述［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］孙美艳，朱龙英，赵忠伟.可重构环保机器人模块设计［J］.机械传动，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］曹燕军，葛为民，张华瑾.一种新型模块化自重构机器人结构设计与仿真研究［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］吴文强，管贻生，等.面向任务的可重构模块化机器人构型设计［J］.哈尔滨工业大学学报，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］姜勇，王洪光，潘新安，等.模块化可重构机器人的构形在线自主辨识［J］.机械工程学报，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］王洪波，徐桂玲，等.助老助残四足/两足可重构并联腿步行机器人运动学建模与仿真［J］.燕山大学学报，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］高文斌，等.一种可重构模块化机器人系统的运动学研究［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］张力平，等.可重构星球探测机器人的运动学建模及轨迹规划［J］.西安交通大学学报，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］李中凯，李艾民，朱真才.拥挤距离排序的多目标文化粒子群优化算法［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 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月出生，河北望都人，副教授、硕士生导师.2005年和2011年分别在上海交通大学获工学学士和工学博士学位.现为上海大学机电工程与自动化学院教师，主要从事服务机器人机器智能与人机关系、计算智能等方面的研究工作.

E-mail: sxu@ shu.edu.cn

王阳男，1993年9月出生，安徽淮南人.2013年在安徽工业大学获工学学士学位.现为上海大学机电工程与自动化学院硕士研究生，主要从事计算智能方面的研究工作.

孙成恺男，1987年4月出生，河南新乡人.2011年和2014年分别在河南理工大学和上海大学获工学学士和工学硕士学位.现为上海德迈科电气控制工程有限公司项目工程师.

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

作者简介

基金项目:国家自然科学基金(No.61203351)

收稿日期:2014-04-09;修回日期: 2015-08-18;责任编辑:孙瑶

DOI:电子学报URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.015

中图分类号：TP242

文献标识码：A

文章编号：0372-2112(2015)01-0101-09