基于交换树的多机器人任务协调与负荷平衡方法

doi:10.11772/j.issn.1001-9081.2016.11.3127

计算机应用 ›› 2016, Vol. 36 ›› Issue (11): 3127-3130.DOI: 10.11772/j.issn.1001-9081.2016.11.3127

基于交换树的多机器人任务协调与负荷平衡方法

沈莉, 李杰, 朱华勇

国防科技大学机电工程与自动化学院, 长沙 410073

收稿日期:2016-04-26 修回日期:2016-07-14 出版日期:2016-11-10 发布日期:2016-11-12
通讯作者: 沈莉
作者简介:沈莉(1992-),女,江苏吴江人,硕士研究生,主要研究方向:人工智能、大规模群体、任务规划;李杰(1984-),男,湖南长沙人,讲师,博士,主要研究方向:人工智能、大规模群体、无人机任务规划;朱华勇(1973-),男,浙江舟山人,教授,博士,主要研究方向:无人机系统工程、无人机任务规划。
基金资助:
国家自然科学基金资助项目（61403410）。

Task coordination and workload balance method for multi-robot based on trading-tree

SHEN Li, LI Jie, ZHU Huayong

College of Mechatronic Engineering and Automation, National University of Defense Technology, Changsha Hunan 410073, China

Received:2016-04-26 Revised:2016-07-14 Online:2016-11-10 Published:2016-11-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61403410).

摘要/Abstract

摘要： 针对多机器人任务分工与协调过程中，未能有效解决的带任务偏序关系的负荷平衡问题，提出一种基于交换树的多机器人任务协调与负荷平衡方法。首先，通过有向赋权图（约束图）对带偏序关系约束的多机器人任务分工问题进行描述；其次，根据有向赋权图提出了初始任务分工策略，通过改进Dijkstra算法解决多机器人之间任务协调问题；最后，提出负荷平衡策略，通过交换树竞拍的方法解决机器人之间任务负荷不平衡问题。仿真结果表明，与一般Dijkstra方法相比，执行完任务负荷平衡策略之后，工作效率明显提高了12%，机器人之间的任务负荷差也减少了30%，验证了该方法的有效性。

关键词: 偏序关系约束, 任务协调, 工作负荷平衡, 多机器人

Abstract: In task decomposition and coordination for multi-robot, the problem of workload imbalance in task with partial order constraint still exists. To overcome this problem, a task coordination and workload balance method for multi-robot based on trading-tree was proposed. Firstly, the task decomposition problem satisfying partial order constraint was described as a constraint graph. Secondly, an initial task assignment strategy was proposed according to the directed weighted graph, and the problem of task coordination among multiple robots was solved by using the improved Dijkstra algorithm. At last, the strategy of workload balance was proposed to balance each robot's workload without violating any constraints via a protocol based on trading-tree. The experimental results show that, compared with Dijkstra algorithm, after finishing the strategy of workload balance, the efficiency signifiantly increases by 12% and the difference of workload reduces by 30%.

Key words: partial order constraint, task coordination, workload balance, multi-robot

中图分类号:

TP242.6

沈莉, 李杰, 朱华勇. 基于交换树的多机器人任务协调与负荷平衡方法[J]. 计算机应用, 2016, 36(11): 3127-3130.

SHEN Li, LI Jie, ZHU Huayong. Task coordination and workload balance method for multi-robot based on trading-tree[J]. Journal of Computer Applications, 2016, 36(11): 3127-3130.

参考文献

[1] LAVENDELIS E. Responsibility area based task allocation method for homogeneous multi robot systems[C]//Proceedings of the 2014 International Workshops on Ad Hoc Networks and Wireless. Berlin:Springer, 2015:232-245.
[2] BRAMBILLA M, FERRANTE E, BIRATTARI M, et al. Swarm robotics:a review from the swarm engineering perspective[J]. Swarm Intelligence, 2013, 7(1):1-41.
[3] AYDIN M E. Coordinating metaheuristic Agents with swarm intelligence[J]. Journal of Intelligent Manufacturing, 2012, 23(4):991-999.
[4] KE W, PENG Z, YUAN Q, et al. A method of task allocation and automated negotiation for multi robots[J]. Journal of Electronics (China), 2012, 29(6):541-549.
[5] DIAS M B, ZLOT R, KALRA N, et al. Market-based multirobot coordination:a survey and analysis[J]. Proceedings of the IEEE, 2006, 94(7):1257-1270.
[6] ZHANG H, LIU H, LI L. Research on a kind of assembly sequence planning based on immune algorithm and particle swarm optimization algorithm[J]. International Journal of Advanced Manufacturing Technology, 2014, 71(5/6/7/8):795-808.
[7] YUN S K, SCHWAGER M, RUS D. Coordinating construction of truss structures using distributed equal-mass partitioning[J]. IEEE Transactions on Robotics, 2011, 30(1):188-202.
[8] YUN S K, RUS D. Adaptation to robot failures and shape change in decentralized construction[C]//Proceedings of the 2010 IEEE International Conference on Robotics and Automation. Piscataway, NJ:IEEE, 2010:2451-2458.
[9] SANDERSON A C, ZHANG H, HOMEM D M L S. Assembly sequence planning[J].AI Magazine, 1990, 11(1):62-81.
[10] GRUSHIN A, REGGIA J A. Automated design of distributed control rules for the self-assembly of prespecified artificial strutures, Robotics and Autonomous Systems, 2008, 56(4):334-359.
[11] CORMEN T, LEISERSON C, RIVEST R. Introduction to Algorithms[M]. Cambridge, MA:MIT Press,1990:658-659.

基于交换树的多机器人任务协调与负荷平衡方法

Task coordination and workload balance method for multi-robot based on trading-tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[2]	梁志刚, 顾军华, 董永峰. 基于头脑风暴优化算法的多机器人气味源定位[J]. 计算机应用, 2017, 37(12): 3614-3619.
[3]	姜栋, 徐欣. 基于帕累托改进的多机器人动态任务分配算法[J]. 计算机应用, 2017, 37(12): 3620-3624.
[4]	吴晋张国良汤文俊孙一杰. 基于改进人工协调场的多机器人避碰算法[J]. 计算机应用, 2013, 33(11): 3123-3128.
[5]	仰晓芳倪建军. 基于生物刺激神经网络的多机器人编队方法[J]. 计算机应用, 2013, 33(05): 1298-1304.
[6]	张捍东黄鹂岑豫皖. 改进的多移动机器人混合编队方法[J]. 计算机应用, 2012, 32(07): 1955-1957.
[7]	柯文德朴松昊彭志平蔡则苏苑全德. 基于π演算的足球机器人协作Q学习方法[J]. 计算机应用, 2011, 31(03): 654-656.
[8]	陆波波，黄鸿. 一种多机器人系统仿真平台的框架结构研究[J]. 计算机应用, 2005, 25(05): 1029-1030.