专利名称 ---【 基于分层式结构和资源整合的多机器人任务分配方法 】

基本信息
申请号
CN201711168423.4
申请日
2017.11.21
公开(公告)号
CN108171394A
公开(公告)日
2018.06.15
申请(专利权)人
中国科学院自动化研究所
申请人地址
100190 北京市海淀区中关村东路95号
发明人
曹志强;任亮;于莹莹;庞磊;谭民;喻俊志;周超; 专利类型 发明专利
摘要
本发明涉及多机器人任务分配领域,具体涉及一种基于分层式结构和资源整合的多机器人任务分配方法。本发明的多机器人任务分配方法,基于金字塔形的分层式结构进行任务分配。在构建金字塔时,自下而上,将机器人作为最底层,其余各层为管理者,且管理者个数逐层减少,到顶层只有一个管理者;然后,基于满足任务约束条件的各机器人,自下而上逐层计算各管理者拥有的资源。在分配任务时,自上而下查找出能满足任务需求的各最低层管理者,将各最低层管理者所直接或间接管理的且满足任务约束条件的机器人进行组合,并选择出匹配度最佳的机器人联盟作为执行任务的机器人联盟。本发明的计算方法效率高,能有效提高任务分配的实时性。 1
主权项
1.一种基于分层式结构和资源整合的多机器人任务分配方法,其特征在于,包括以下
步骤:
步骤S10,基于金字塔形的分层式结构,根据任务约束条件,以及各机器人的资源向量,
从金字塔的最底层筛选出满足任务约束条件的机器人;
步骤S20,根据所述满足任务约束条件的机器人,以及各机器人的资源向量,自下而上
计算所述金字塔形的分层式结构的每一层中各管理者拥有的资源向量;
步骤S30,根据任务需求资源向量,以及所述各管理者拥有的资源向量,自上而下,查找
出所述金字塔形的分层式结构中满足任务需求的各最低层管理者;
步骤S40,查找所述满足任务需求的各最低层管理者所直接或间接管理的,且满足任务
约束条件的机器人,选择能够满足任务需求的机器人组合,作为候选机器人联盟,进而组成
候选机器人联盟集合;
步骤S50,从所述候选机器人联盟集合中选择匹配度最佳的机器人联盟,作为被选派执
行任务的机器人联盟;
其中,
所述金字塔形的分层式结构,构建方法为:
步骤A10,将所有机器人作为金字塔的最底层,并按预设的机器人分组成员数将机器人
进行分组,针对各组机器人分别设置一个管理者;
步骤A20,按预设的管理者分组成员数,将管理者进行分组,针对各组管理者分别设置
一个上级管理者;按所述预设的管理者分组成员数将所述上级管理者分组,并对各组分别
设置再上一级管理者;依此类推,直到金字塔的最顶层只有一个管理者;
所述管理者为计算机。
2.根据权利要求1所述的多机器人任务分配方法,其特征在于,步骤A10具体为:
步骤A11,将总数量为robotNum的机器人作为金字塔的最底层,记层数为j=1;对机器
人进行分组,若(robotNum%P)=0,则组数groupNum1=robotNum/P,每组P个机器人;否则,
组数groupNum1=robotNum/P+1,第1至第groupNum1?1组中每组P个机器人,第groupNum1
中有robotNum?(groupNum1?1)*P个机器人;
步骤A12,为底层的每组机器人设置一个管理者,作为第2层的成员,并将该管理者所管
理的组内的各机器人称为该管理者的下属成员;管理者个数记为managerNum2=groupNum1
其中,
P为所述预设的机器人分组成员数;groupNum1为所述金字塔形的分层式结构的第1层中
机器人分组后的组数;managerNum2为第2层中管理者的个数。
3.根据权利要求2所述的多机器人任务分配方法,其特征在于,步骤A20具体为:
步骤A21,层数j=2;
步骤A22,对第j层管理者进行分组,若(managerNumj%Q)=0,则组数groupNumj
managerNumj/Q,每组Q个管理者;否则,组数groupNumj=managerNumj/Q+1,第1至第
groupNumj?1组中每组Q个管理者,第groupNumj组中有managerNumj?(groupNumj?1)*Q个管
理者;
步骤A23,为第j层的每组管理者设置一个上级管理者,作为第j+1层的成员,并将该上
级管理者所管理的组内的各管理者称为该上级管理者的下属成员;上级管理者个数
managerNumj+1=groupNumj
步骤A24,j=j+1,若j层管理者个数大于1,则转至步骤A22;否则,转至步骤A25;
步骤A25,记金字塔的总层数为N=j;
其中,
Q为所述预设的管理者分组成员数;groupNumj为所述金字塔形的分层式结构中第j层的
管理者分组后的组数;managerNumj为第j层的管理者的个数。
4.根据权利要求3所述的多机器人任务分配方法,其特征在于,所述满足任务约束条件
的机器人,为处于空闲状态且所拥有的资源向量大于或等于任务约束资源向量的机器人。
5.根据权利要求4所述的多机器人任务分配方法,其特征在于,资源向量之间的比较,
通过对其中各项资源的比较来进行,若资源向量F(a)的各项资源的数值均大于或等于资源
向量F(b)中对应资源的数值,则F(a)≥F(b);
其中,F(a)和F(b)分别为资源空间中的两个不同的资源向量;用F描述资源空间,其维
数为dim(F),F中的资源向量表示为F=[f1?f2...fdim(F)],fk表示资源向量的第k项资源的数
值,k=1,2,...,dim(F);F(a)和F(b)的维数均为dim(F),F(a)和F(b)分别
为:
F(a)=[f1(a)?f2(a)…fdim(F)(a)]
F(b)=[f1(b)?f2(b)…fdim(F)(b)]。
6.根据权利要求5所述的多机器人任务分配方法,其特征在于,步骤S20具体为:
基于所述满足任务约束条件的机器人,按照从第2层、第3层一直到第N层的顺序自下而
上进行资源整合,逐层更新管理者的资源向量
其中,
对位于第2层的各管理者,根据该管理者直接管理的满足任务约束条件的机器人的资
源向量,按照下式进行整合,从而实现对该管理者资源向量的更新:
为第2层中管理者的资源向量,下标2、g2、i2分别为该层管理者的层
号、组号、序号;为第1层中机器人的资源向量,下标1、g1、i1分别为机器人的
层号、组号、序号;Ωrl为所有满足任务约束条件的机器人的集合;
对第3层至第N层的各管理者,根据该管理者直接管理的下属成员的资源向量,按照下
式进行整合,进而更新该管理者的资源向量:
为第n层管理者的资源向量,下标n、gn、in分别为该层管理者的层号、
组号、序号;n=3,4,...,N。
7.根据权利要求6所述的多机器人任务分配方法,其特征在于,资源向量的整合通过对
每一项资源进行整合来完成;
对每项资源,根据该项资源的类型采取对应的整合规则;资源类型包括:累加型、最大
值型、最小值型;累加型资源的整合规则为将相应资源进行求和处理;最大值型资源的整合
规则为将相应资源求取最大值;最小值型资源的整合规则为将相应资源求取最小值。
8.根据权利要求7所述的多机器人任务分配方法,其特征在于,步骤S30具体为:
从所述金字塔形的分层式结构的第N层开始,按照自上而下的顺序将所述任务需求资
源向量与所述各管理者拥有的资源向量进行比较;当一个管理者拥有的资源向量大于或等
于任务需求资源向量,表明该管理者满足任务需求,则继续将所述任务需求资源向量跟该
管理者所直接管理的下属各成员的资源向量进行比较,如果仍存在满足任务需求的下属成
员,重复该比较过程直到第2层,将满足任务需求的第2层的成员作为最低层管理者;如果一
个位于第3层或更高层的管理者满足任务需求但其直接管理的下属各成员均不满足任务需
求,且尚未出现满足任务需求的最低层管理者,则将该管理者作为最低层管理者。
9.根据权利要求8所述的多机器人任务分配方法,其特征在于,步骤S40具体为:
步骤S41,对每一个满足任务需求的最低层管理者所处的层数进行判断,若处于第2层,
则转至步骤S42;否则,转至步骤S43;
步骤S42,查找出该最低层管理者所直接管理的所有满足任务约束条件的机器人;并对
所有满足任务约束条件的机器人,穷举所有可能的组合,当一个机器人组合拥有的资源向
量大于或等于任务需求资源向量时,表明该机器人组合满足任务需求,将满足任务需求的
机器人组合作为候选机器人联盟AT,添加到候选机器人联盟集合Ωrc中;
步骤S43,查找出该最低层管理者所间接管理的所有满足任务约束条件的机器人,并将
所有满足任务约束条件的机器人组合起来作为候选机器人联盟AT,添加到候选机器人联盟
集合Ωrc中。
10.根据权利要求9所述的多机器人任务分配方法,其特征在于,步骤S50具体为:
基于候选机器人联盟集合Ωrc,选择满足匹配度约束条件
σ1≤|F(T),F(AT)|≤σ2
且匹配度最佳的机器人联盟:
其中,|F(T),F(AT)|为任务需求资源向量F(T)与候选机器人联盟AT的资源向量F(AT)之
间的匹配度,用两者之间的加权欧式距离来衡量;σ1和σ2分别为预设的最小匹配度阈值和最
大匹配度阈值;为被选派执行任务T的最佳的机器人联盟。
11.根据权利要求1?10中任一项所述的多机器人任务分配方法,其特征在于,资源向量
之间的匹配度计算方法为:
F(a)=[f1(a)?f2(a)…fdim(F)(a)]
F(b)=[f1(b)?f2(b)…fdim(F)(b)]
其中,用F描述资源空间,其维数为dim(F),F中的资源向量可表示为F=[f1?
f2...fdim(F)];fk表示资源向量的第k项资源的数值,k=1,2,...,dim(F);F
(a)和F(b)分别为资源空间F中的两个不同的资源向量。

 

IPC信息
IPC主分类号
G06Q10/06(2012.01)I
IPC分类号
G06Q10/06(2012.01)I

 

法律状态信息
法律状态公告日
2018.07.13
法律状态
实质审查的生效 法律状态信息
实质审查的生效 IPC(主分类):G06Q 10/06 申请日:20171121
法律状态公告日
2018.06.15
法律状态
公开 法律状态信息
公开

 

代理信息
代理机构名称
北京瀚仁知识产权代理事务所(普通合伙) 11482
代理人姓名
郭文浩;关芳
相似专利

[发明专利] 一种实现焦油自消化的生物质气化方法
发明人:吴创之;阴秀丽;刘华财;潘贤齐;黄艳琴;袁洪友 申请日:2017-01-06

[发明专利] 用于农业复杂自适应搜索引擎系统的控制方法
发明人:王儒敬;黄河;张晓明;孙丙宇;魏圆圆 申请日:2007-11-21

点击次数: 21      分享到:0


| 联系我们 | 网站地图 | 版权声明 |

版权:中国科学院 主办:中国科学院科技促进发展局 承办:中国科学院成都文献情报中心 蜀ICP备05003827号-12

建议使用1024×768 分辨率 IE6.0以上版本浏览器