一种基于动态聚类的异构联盟构建与瞬时匹配方法

摘要: 本发明涉及任务分配,尤其涉及一种基于动态聚类的异构联盟构建与瞬时匹配方法。背景技术:1、相比于单机器人执行任务,多机器人通过团队协作,展现了更好的任务适应能力、...
一种基于动态聚类的异构联盟构建与瞬时匹配方法

本发明涉及任务分配,尤其涉及一种基于动态聚类的异构联盟构建与瞬时匹配方法。

背景技术:

1、相比于单机器人执行任务,多机器人通过团队协作,展现了更好的任务适应能力、更低的成本与更高的任务完成效率,因此在灾害救援、城市物流、智慧农业等场景中广泛应用。不同场景下均对多机器人系统的自主的决策能力提出了要求。作为形成这一能力的关键技术,多机器人任务分配问题(mrta)一直以来是研究的热点问题,在诸多不同场景中落地应用。

2、多机器人任务分配问题类型多样,但都面对着动态化、去中心化和规模化的挑战。这三个挑战相互耦合影响构成了更严峻的挑战。这些挑战最终指向了一个问题,即在大规模多机器人系统中如何进行实时的进行动态弹性任务分配。

3、考虑多机器人系统三个挑战,分布式框架比集中式是更好的选择。集中式任务分配具有一个中央节点,负责进行任务分配计算并将下发至机器人。这种框架面临着单点风险、沉重的算力负担和巨大的通信开销。在面对动态突发情况时,集中式算法从开始进行重分配优化,或单独设计快速恢复策略,而这些策略以牺牲一定的优化性能以换取实时性。而分布式框架是指机器人仅掌握局部信息,通过信息交互实现全局的任务分配,因而天然能够避免单节点风险,将大规模机器人时的算力开销和通信开销下放至局部,同时具备良好的动态适应性,但是受限于局部信息,分布式往往无法求得全局任务分配问题的最优解。

4、从任务分配方法来看,多机器人任务分配主要可以分为基于市场的方法、基于智能优化的方法、基于学习的方法和基于聚类的方法。基于市场的方法主要包括cnp、cbba等算法,其借鉴市场机制的竞价方式,通过成员竞拍-成员间协商形成分配方案。市场内成员仅根据自身情况参与竞拍,因此这类方法天然具有分布式特性和良好的动态适应性,得益于此,当前多数动态任务分配问题是基于市场的方法开展研究。

5、基于智能优化的方法,例如遗传算法、粒子群算法、模拟退火算法等,多被使用在集中式的静态任务分配算法中,该类方法可以在一定时间内收敛到次优解甚至最优解。这类方法应对动态情况主要思路是全局重新优化或使用局部优化策略进行局部调整。全局重新优化会导致优化时间长、动态适应性不足,而局部调整则往往面临着全局最优性的考验。此外,面临大规模问题时求解困难、计算负担沉重等问题,严重限制了智能优化算法应用于动态任务分配问题的求解。

6、最近兴起的基于学习的方法,尤其是深度强化学习,给解决大规模多机器人系统弹性任务分配带来了新的思路。但是其面临着训练耗时长、场景迁移性弱、算法收敛困难等问题,仍极大限制了其推广使用。

7、基于聚类的方法主要思路是遵循多机器人的特性对其进行聚类,实现机器人数量的降维,以解决大规模多机器人系统任务分配时,面临解空间指数级增加、最优性求解困难、计算负担沉重的问题。现有的基于聚类的方法仅被当作一个规模降维的策略,而任务分配求解则是使用其他算法如基于市场的方法,任务分配的方法不能与聚类算法进行很好的融合。

8、针对这一问题,研究人员采用迭代聚类的方法解决机器人组建任务联盟的问题。其通过设计簇和簇之间个体交换、合并机制形成多机器人和任务组成的簇,在簇内通过整数规划实现机器人-任务的精确分配,以实现任务分配总收益的单调增加。然而,其研究是静态环境下的集中式多机器人任务分配问题,无法解决动态环境下分布式任务分配问题。

技术实现思路

1、本发明公开了一种基于动态聚类的异构联盟瞬时指派方法,以克服上述技术问题。

2、为了实现上述目的,本发明的技术方案是:

3、一种基于动态聚类的异构联盟构建与瞬时匹配方法,包括以下步骤:

4、s1:初始化为完成任务所组建的机器人联盟;

5、s2:随机选择分布式异构机器人集群中的一个机器人,作为簇合并者机器人,构建基于机器人通信距的分布式异构机器人集群的可变合并簇;其中,可变合并簇中包括没有属于任何机器人联盟的机器人和机器人联盟;

6、s3:根据任务联盟的机器人与任务之间的距离,建立针对所要执行任务组建机器人联盟的成本函数,以建立任务联盟的分配效用函数;并获取可变合并簇内的总效用;

7、s4:根据所述任务联盟的分配效用函数,建立以最大化簇内任务联盟的分配效用为目标的目标函数,并进行求解,获取可变合并簇内的候选局部分配方案,并获取候选局部分配方案的总效用;

8、s5:根据可变合并簇内的总效用和候选局部分配方案的总效用,确定最优局部分配方案;可变合并簇内的机器人执行所述最优局部分配方案,按照机器人的正常速度向对应的任务进行移动;

9、s6:当可变合并簇中存在突发损伤的机器人时,构建机器人联盟发生损毁后的收益函数,以建立机器人联盟发生损毁后的效用函数,获取机器人联盟发生损坏后的效用函数的值;

10、s7:若机器人联盟发生损坏后的效用函数的值不小于0,则可变合并簇内的机器人继续执行所述最优局部分配方案,按照机器人的发生损伤后的运动速度向对应的任务进行移动,直至机器人到达任务所在位置;

11、若机器人联盟发生损坏后的效用函数的值小于0,则解散所述机器人联盟,使得机器人联盟中的机器人均没有被分配任务;重复执行s2-s6;直至机器人到达任务所在位置。

12、进一步的,构建基于分布式异构机器人集群的可变合并簇的方法如下:

13、s21:随机选择分布式异构机器人集群中的一个机器人,作为簇合并者机器人,以确定簇合并者机器人通信距范围内的机器人集合与任务集合;

14、s22:若簇合并者机器人通信距范围内的机器人集合中的第个机器人没有被分配任务,则将簇合并者机器人通信距范围内的机器人集合中的第个机器人添加至簇合并者机器人的可变合并簇;为簇合并者机器人通信距范围内的机器人集合中的机器人索引;

15、若簇合并者机器人通信距范围内的机器人集合中的第个机器人已经被分配任务,即存在包含第个机器人的任务联盟,则若任务联盟内的机器人和对应的任务全部处于簇合并者机器人的通信距范围内,则将任务联盟和对应的任务添加至簇合并者机器人的可变合并簇;否则,不将簇合并者机器人通信距范围内的机器人集合中的第个机器人添加至簇合并者机器人的可变合并簇;

16、s23:重新执行s21-s22,直至可变合并簇内的机器人达到簇内机器人最大数量或者可变合并簇内的任务达到最大数量。

17、进一步的,获取可变合并簇的总效用所采用公式如下:

18、

19、式中:为任务联盟完成第个任务的分配效用函数;为机器人联盟的收益函数;为机器人针对第个任务组建联盟的成本;

20、

21、

22、式中:为机器人联盟的能力向量;为具有第个能力的机器人;为第个机器人;为表示机器人是否具有第个能力的0-1变量;为机器人的能力类型索引;为机器人的能力类型总数;

23、其中,针对所要执行任务组建机器人联盟的成本函数建立如下:

24、

25、式中:为机器人针对第个任务组建联盟的成本;为任务的索引;为第个机器人在时刻的位置向量,,均为第个机器人在时刻的位置坐标;为第个任务的位置向量,,均为第个任务的位置坐标;为向量范数;表示时刻为完成任务组建的联盟;

26、获取可变合并簇内的总效用如下:

27、

28、式中:为全局总效用;为所有可能的机器人任务全局分配方案。

29、进一步的,以最大化簇内任务联盟的分配效用为目标的目标函数建立如下:

30、

31、式中:为所有可能的机器人任务全局分配方案;为机器人联盟完成第个任务的分配效用函数;表示时刻为完成任务组建的机器人联盟;,分别为第个和第个机器人联盟;,均为机器人联盟的索引;为任务的索引;为任务的总数;为机器人联盟数量中的机器人数量;为机器人联盟中的最大机器人数量;为机器人的集合。

32、进一步的,获取机器人联盟发生损毁后的效用函数所采用方法如下:

33、s61:获取机器人联盟的损伤因子数值;

34、

35、式中:为机器人联盟的损伤因子数值;为时刻为完成任务组建的机器人联盟,;为机器人在时刻发生第种毁伤情况的概率因子数值;为第个机器人;

36、s62:根据机器人联盟的损伤因子数值,建立机器人联盟发生损毁后的收益函数;

37、

38、式中:为t时刻机器人联盟发生损毁后的收益函数;为机器人联盟的收益函数;

39、s63:根据机器人联盟发生损毁后的收益函数和机器人联盟的成本函数,建立机器人联盟发生损毁后的效用函数,表示如下;

40、

41、式中:为

t时刻机器人联盟发生损毁后的效用函数;为

t时刻机器人联盟发生损毁后的收益函数;为机器人针对第个任务组建联盟的成本。

42、进一步的,获取机器人的发生损伤后的运动速度所采用公式如下:

43、

44、式中:为发生损伤后机器人的运动速度;为时刻;为机器人在时刻发生第种毁伤情况的概率因子数值;为机器人的正常速度。

45、有益效果:本发明的一种基于动态聚类的异构联盟构建与瞬时匹配方法,通过在分布式异构机器人集群中,随机选择一个机器人作为簇合并者,构建可变合并簇,得到基于可变合并簇的分配方案;并通过求解以最大化簇内任务联盟的分配效用为目标的目标函数,得到可变合并簇内的候选局部分配方案。通过基于可变合并簇的分配方案的总效用与候选局部分配方案的总效用,确定最优局部分配方案;当可变合并簇中存在突发损伤的机器人时,构建机器人联盟发生损毁后的收益函数,以建立机器人联盟发生损毁后的效用函数,获取机器人联盟发生损坏后的效用函数的值,当机器人联盟发生损坏后的效用函数的值不小于0时,可变合并簇内的机器人继续执行所述最优局部分配方案,否则,则解散所述机器人联盟,重新进行任务的分配。

46、本发明仅依据机器人通信距内的局部信息同其他机器人组建联盟,建立可变合并簇,大大降低了算法的复杂度,并能够应对机器人突发损毁的动态情况。本发明面对机器人系统面临的突发损毁情况时,能够通过软降级机制与弹性级联释放机制;对于损毁导致分配效用暴跌的任务联盟,设计了任务联盟自动解散机制:健康机器人进入随机游走状态,并能够被其他任务联盟迅速捕获,实现整个机器人团队的快速韧性自愈。