结合遗传算法和滚动调度的多机器人任务分配算法

doi:10.11772/j.issn.1001-9081.2022121916

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (12): 3833-3839.DOI: 10.11772/j.issn.1001-9081.2022121916

结合遗传算法和滚动调度的多机器人任务分配算法

邓辅秦¹^,², 黄焕钊¹, 谭朝恩¹, 付兰慧¹, 张建民¹, 林天麟²()

^1.五邑大学智能制造学部，广东江门 529020
^2.香港中文大学（深圳）深圳市人工智能与机器人研究院，广东深圳 518116

收稿日期:2023-01-04 修回日期:2023-02-21 接受日期:2023-02-22 发布日期:2023-03-07 出版日期:2023-12-10
通讯作者: 林天麟
作者简介:邓辅秦（1982—），男，湖南郴州人，高级工程师，博士，主要研究方向：机器学习、移动机器人系统与多机器人系统
黄焕钊（1998—），男，广东汕头人，硕士研究生，主要研究方向：多机器人任务分配
谭朝恩（1999—），男，广东顺德人，硕士研究生，主要研究方向：多机器人路径规划
付兰慧（1987—），女，河南新乡人，讲师，博士，主要研究方向：机器学习、图像信息处理
张建民（1981—），男，河北沧州人，讲师，硕士，主要研究方向：机器学习、移动机器人系统与多机器人系统；
基金资助:
国家重点研发计划“智能机器人”重点专项(2020YFB1313300);深圳市科技计划项目(KQTD2016113010470345);深圳市人工智能与机器人研究院探索性研究项目(AC01202101103);五邑大学横向课题项目(33520098)

Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling

Fuqin DENG¹^,², Huanzhao HUANG¹, Chaoen TAN¹, Lanhui FU¹, Jianmin ZHANG¹, Tinlun LAM²()

^1.Faculty of Intelligent Manufacturing，Wuyi University，Jiangmen Guangdong 529020，China
^2.Shenzhen Institute of Artificial Intelligence and Robotics for Society，The Chinese University of Hong Kong，Shenzhen，Shenzhen Guangdong 518116，China

Received:2023-01-04 Revised:2023-02-21 Accepted:2023-02-22 Online:2023-03-07 Published:2023-12-10
Contact: Tinlun LAM
About author:DENG Fuqin， born in 1982， Ph. D.， senior engineer. His research interests include machine learning， mobile robotic systems and multi-robot systems.
HUANG Huanzhao， born in 1998， M. S. candidate. His research interests include multi-robot task allocation.
TAN Chaoen， born in 1999， M. S. candidate. His research interests include multi-robot path planning.
FU Lanhui， born in 1987， Ph. D.， lecturer. His research interests include machine learning， image information processing.
ZHANG Jianmin， born in 1981， M. S.， lecturer. His research interests include machine learning， mobile robotic systems and multi-robot systems.
Supported by:
National Key Research and Development Program “Intelligent Robot” Key Project(2020YFB1313300);Shenzhen Science and Technology Program(KQTD2016113010470345);Exploratory Research Project of Shenzhen Institute of Artificial Intelligence and Robotics for Society(AC01202101103);Wuyi University Horizontal Research Project(33520098)

摘要/Abstract

摘要：

研究多机器人任务分配（MRTA）的目的是提高智能工厂中机器人完成任务的效率。针对现有算法在处理大规模、多约束的MRTA时存在不足的问题，提出一种结合遗传算法和滚动调度的MRTA算法（ACGARS）。首先，在遗传算法中采用基于有向无环图（DAG）的编码方式高效地处理任务之间的优先级约束；其次，在遗传算法的初始种群中加入先验知识以提高算法的搜索效率；最后，设计基于任务组的滚动调度策略用于减小求解问题的规模，从而实现对大规模问题的高效求解。在大规模问题实例上的实验结果表明，相较于构造性启发式算法（CHA）、最小化干扰算法（MIA）和基于惩罚策略的遗传算法（GAPS）生成的方案，当任务组数为20时，所提算法生成的方案的平均订单完成时间分别缩短了30.02%、16.86%和75.65%，验证了所提算法能有效地缩短订单的平均等待时间，提升多机器人任务分配效率。

关键词: 多机器人任务分配, 遗传算法, 智能工厂, 有向无环图, 滚动调度策略

Abstract:

The purpose of research on Multi-Robot Task Allocation （MRTA） is to improve the task completion efficiency of robots in smart factories. Aiming at the deficiency of the existing algorithms in dealing with large-scale multi-constrained MRTA， an MRTA Algorithm Combining Genetic Algorithm and Rolling Scheduling （ACGARS） was proposed. Firstly， the coding method based on Directed Acyclic Graph （DAG） was adopted in genetic algorithm to efficiently deal with the priority constraints among tasks. Then， the prior knowledge was added to the initial population of genetic algorithm to improve the search efficiency of the algorithm. Finally， a rolling scheduling strategy based on task groups was designed to reduce the scale of the problem to be solved， thereby solving large-scale problems efficiently. Experimental results on large-scale problem instances show that compared with the schemes generated by Constructive Heuristic Algorithm （CHA）， MinInterfere Algorithm （MIA）， and Genetic Algorithm with Penalty Strategy （GAPS）， the scheme generated by the proposed algorithm has the average order completion time shortened by 30.02%， 16.86% and 75.65% respectively when the number of task groups is 20， which verifies that the proposed algorithm can effectively shorten the average waiting time of orders and improve the efficiency of multi-robot task allocation.

Key words: multi-robot task allocation, genetic algorithm, smart factory, Directed Acyclic Graph (DAG), rolling scheduling strategy

中图分类号:

TP242

邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟. 结合遗传算法和滚动调度的多机器人任务分配算法[J]. 计算机应用, 2023, 43(12): 3833-3839.

Fuqin DENG, Huanzhao HUANG, Chaoen TAN, Lanhui FU, Jianmin ZHANG, Tinlun LAM. Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling[J]. Journal of Computer Applications, 2023, 43(12): 3833-3839.

图/表 13

图1 代表一个任务组的DAG

Fig.1 DAG representing one task group

图2 本文算法的整体框架

Fig.2 Overall framework of proposed algorithm

图3 改进遗传算法的流程

Fig.3 Flowchart of improved genetic algorithm

图4 分配矩阵确定执行任务的机器人团队示例

Fig. 4 Example of assignment matrix to determine robot team to perform task

图5 根据DAG与调度矩阵确定任务的执行顺序示例

Fig.5 Example of determination of task execution order according to DAG and scheduling matrix

图6 交叉算子示意图

Fig. 6 Schematic diagram of crossover operator

图7 突变算子示意图

Fig. 7 Schematic diagram of mutation operator

图8 基于任务组窗口的滚动调度策略的流程

Fig.8 Flowchart of rolling scheduling strategy based on task group window

图9 两个算法生成方案对应的甘特图

Fig. 9 Gantt charts corresponding to schemes generated by two algorithms

图10 两个算法迭代过程中目标函数最优值的变化

Fig.10 Changes of optimal values of objective functions of two algorithms in iteration process

表1 小规模问题上不同算法的目标函数值对比

Tab.1 Comparison of objective function values of different algorithms on small-scale problems

算法	任务组数
算法	1	2	3
CHA	38 678.50	58 228.92	82 433.61
MIA	37 953.50	56 144.08	77 166.72
GAPS	37 496.83	67 530.50	108 314.50
IGA	36 203.50	50 167.75	67 087.33
IGAPK	36 203.50	49 152.75	65 987.72

表2 大规模问题上不同算法的目标函数值对比

Tab.2 Comparison of objective function values of different algorithms on large-scale problems

算法	任务组数
算法	10	15	20
CHA	65 954.75	92 442.40	117 752.35
MIA	58 504.18	80 602.80	99 117.29
GAPS	137 600.00	217 680.00	338 400.00
IGAPK	56 811.92	80 428.98	98 505.98
ACGARS	48 312.18	66 724.49	82 405.81

表3 大规模问题上不同算法的CPU耗时对比 (s)

Tab.3 Comparison of CPU time consumption of different algorithms on large-scale problems

算法	任务组数
算法	10	15	20
CHA	0.12	0.30	0.59
MIA	0.13	0.33	0.64
GAPS	230.62	549.68	1 364.92
IGAPK	266.77	708.49	1 447.31
ACGARS	63.89	99.63	118.47

参考文献 31

1	LI X， LI D， WAN J， et al. A review of industrial wireless networks in the context of Industry 4.0 ［J］. Wireless Networks， 2017， 23（1）： 23-41. 10.1007/s11276-015-1133-7
2	LIANG G， LUO H， LI M， et al. FreeBOT： a freeform modular self-reconfigurable robot with arbitrary connection point-design and implementation［C］// Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE， 2020： 6506-6513. 10.1109/iros45743.2020.9341129
3	CHEN K-C， LIN S-C， J-H HSIAO， et al. Wireless networked multirobot systems in smart factories ［J］. Proceedings of the IEEE， 2020， 109（4）： 468-494. 10.1109/jproc.2020.3033753
4	WANG S， WAN J， ZHANG D， et al. Towards smart factory for industry 4.0： a self-organized multi-agent system with big data based feedback and coordination ［J］. Computer Networks， 2016， 101： 158-168. 10.1016/j.comnet.2015.12.017
5	FECZKO J， MANKA M， KROL P， et al. Review of the modular self reconfigurable robotic systems［C］// Proceedings of the 2015 10th International Workshop on Robot Motion and Control. Piscataway： IEEE， 2015： 182-187. 10.1109/romoco.2015.7219733
6	赵辉，郝梦雅，王红君，等. 基于资源拍卖的农业多机器人任务分配［J］.计算机应用与软件，2021，38（12）：286-290，313. 10.3969/j.issn.1000-386x.2021.12.046
	ZHAO H， HAO M Y， WANG H J， et al. Cooperative task allocation of agricultural multi-robot based on resource auction［J］. Computer Applications and Software， 2021，38（12）：286-290，313. 10.3969/j.issn.1000-386x.2021.12.046
7	KIM J， SON H I. A Voronoi diagram-based workspace partition for weak cooperation of multi-robot system in orchard ［J］. IEEE Access， 2020， 8： 20676-20686. 10.1109/access.2020.2969449
8	NIKITENKO A， LAVENDELIS E， EKMANIS M， et al. Task allocation methods for homogeneous multi-robot systems： feed pushing case study ［J］. Automatic Control and Computer Sciences， 2018， 52： 371-381. 10.3103/s0146411618050097
9	林思梦. 基于粒子群算法的灾后救援多机器人任务分配［D］.徐州：中国矿业大学，2020： 2.
	LIN S M. Multi-robot task allocation for rescue after disaster based on particle swarm optimization algorithm［D］. Xuzhou： China University of Mining and Technology， 2020： 2.
10	MOURADIAN C， SAHOO J， GLITHO R H， et al. A coalition formation algorithm for multi-robot task allocation in large-scale natural disasters ［C］// Proceedings of the 2017 13th International Wireless Communications and Mobile Computing Conference. Piscataway： IEEE， 2017： 1909-1914. 10.1109/iwcmc.2017.7986575
11	GUNN T， ANDERSON J. Dynamic heterogeneous team formation for robotic urban search and rescue ［J］. Journal of Computer and System Sciences， 2015， 81（3）： 553-567. 10.1016/j.jcss.2014.11.009
12	李鑫滨，章寿涛，闫磊，等. 基于鲁棒Restless Bandits模型的多水下自主航行器任务分配策略［J］.计算机应用，2019，39（10）：2795-2801. 10.11772/j.issn.1001-9081.2019020341
	LI X B， ZHANG S T， YAN L， et al. Multiple autonomous underwater vehicle task allocation policy based on robust Restless Bandit model［J］. Journal of Computer Applications， 2019，39（10）：2795-2801. 10.11772/j.issn.1001-9081.2019020341
13	CARRENO Y， PAIRET È， PETILLOT Y， et al. A decentralized strategy for heterogeneous AUV missions via goal distribution and temporal planning ［C］// Proceedings of the 2020 International Conference on Automated Planning and Scheduling. Palo Alto： AAAI Press， 2020： 431-439. 10.1609/icaps.v30i1.6738
14	GUO X， HU J， CHEN J， et al. Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment ［J］. IEEE Robotics and Automation Letters， 2021， 6（4）： 8349-8356. 10.1109/lra.2021.3058935
15	KORASH G A， STENTZ A， DIAS M B. A comprehensive taxonomy for multi-robot task allocation ［J］. The International Journal of Robotics Research， 2013， 32（12）：1495-1512. 10.1177/0278364913496484
16	GERKEY B P， MATARIĆ M J. A formal analysis and taxonomy of task allocation in multi-robot systems ［J］. The International Journal of Robotics Research， 2004， 23（9）： 939-954. 10.1177/0278364904045564
17	KORSAH G A， KANNAN B， BROWNING B， et al. xBots： an approach to generating and executing optimal multi-robot plans with cross-schedule dependencies［C］// Proceedings of the 2012 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2012： 115-122. 10.1109/icra.2012.6225234
18	WANG Z， GOMBOLAY M. Learning scheduling policies for multi-robot coordination with graph attention networks ［J］. IEEE Robotics and Automation Letters， 2020， 5（3）： 4509-4516. 10.1109/lra.2020.3002198
19	BISCHOFF E， MEYER F， INGA J， et al. Multi-robot task allocation and scheduling considering cooperative tasks and precedence constraints［C］// Proceedings of the 2020 IEEE International Conference on Systems， Man， and Cybernetics. Piscataway： IEEE， 2020： 3949-3956. 10.1109/smc42975.2020.9283215
20	BISCHOFF E， TEUFEL J， INGA J， et al. Towards interactive coordination of heterogeneous robotic teams — introduction of a reoptimization framework ［C］// Proceedings of the 2021 IEEE International Conference on Systems， Man， and Cybernetics. Piscataway： IEEE， 2021： 1380-1386. 10.1109/smc52423.2021.9659002
21	MILORADOVIĆ B， ÇÜRÜKLÜ B， EKSTRÖM M， et al. A genetic algorithm approach to multi-agent mission planning problems［C］// Proceedings of the 2020 9th International Conference on Operations Operations Research and Enterprise Systems. Cham： Springer， 2020： 109-134. 10.1007/978-3-030-37584-3_6
22	MILORADOVIĆ B， ÇÜRÜKLÜ B， EKSTRÖM M， et al. Extended colored traveling salesperson for modeling multi-agent mission planning problems ［C］// Proceedings of the 2019 8th International Conference on Operations Research and Enterprise Systems. Cham： Springer， 2019： 237-244. 10.5220/0007309002370244
23	QI B， PU L， XU C， et al. Multi-robot task assignment method in the construction waste sorting system ［C］// Proceedings of the 2022 IEEE International Conference on Mechatronics and Automation. Piscataway： IEEE， 2022： 1364-1369. 10.1109/icma54519.2022.9856058
24	CECHINEL A K， DE PIERI E R， FERNANDES PEREZ A L， et al. Multi-robot task allocation using island model genetic algorithm ［J］. IFAC-PapersonLine， 2021， 54（1）： 558-563. 10.1016/j.ifacol.2021.08.063
25	范学满，薛昌友，张会.基于多种群遗传算法的多UUV任务分配方法［J］.水下无人系统学报，2022，30（5）：621-630. 10.11993/j.issn.2096-3920.202107001
	FAN X M， XUE C Y， ZHANG H. Task assignment method for multiple UUVs based on multi-population genetic algorithm ［J］. Journal of Unmanned Undersea Systems，2022，30（5）：621-630. 10.11993/j.issn.2096-3920.202107001
26	RAMCHURN S D， POLUKAROV M， FARINELLI A， et al. Coalition formation with spatial and temporal constraints［C］// Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. New York： ACM， 2010，3： 1181-1188.
27	KOES M， NOURBAKHSH I， SYCARA K， et al. Heterogeneous multi-robot coordination with spatial and temporal constraints［C］// Proceedings of the 20th National Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2005： 1292-1297.
28	ZHANG Y， PARKER L E. Multi-robot task scheduling［C］// Proceedings of the 2013 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2013： 2992-2998. 10.1109/icra.2013.6630992
29	方剑，席裕庚.周期性和事件驱动的Job Shop滚动调度策略［J］.控制与决策，1997， 12（2）：159-162，166. 10.3321/j.issn:1001-0920.1997.02.015
	FANG J， XI Y G. A periodic and event-driven rolling horizon job shop scheduling strategy［J］. Control and Decision， 1997， 12（2）：159-162，166. 10.3321/j.issn:1001-0920.1997.02.015
30	SUSLOVA E， FAZLI P. Multi-robot task allocation with time window and ordering constraints［C］// Proceedings of the 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE， 2020： 6909-6916. 10.1109/iros45743.2020.9341247
31	ENTEZARI Z， MAHOOTCHI M. Developing a mathematical model for staff routing and scheduling in home health care industries： genetic algorithm-based solution scheme ［J］. Scientia Iranica， 2021， 28（6）： 3692-3718.

[1]	梁军, 洪泽泓, 余松森. 基于改进粒子群优化算法和遗传变异的图像分割模型[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1743-1749.
[2]	王彬, 向甜, 吕艺东, 王晓帆. 基于NSGA‑Ⅱ的自适应多尺度特征通道分组优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1401-1408.
[3]	张敏, 韩晓龙. 多目标模糊机会约束规划的低碳多式联运路径优化[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 636-644.
[4]	薛海蓉, 韩晓龙. 基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3848-3855.
[5]	刘乾, 张洋铭, 万定生. 网格化分布式新安江模型并行计算算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3327-3333.
[6]	姜松岩, 廖晓鹃, 陈光柱. 基于可满足性模理论的多处理机通信延迟优化任务调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 185-191.
[7]	王旭, 申玉民, 熊晓芸, 李鹏, 王金龙. 基于哈希图的建筑物联网数据管理方法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2471-2480.
[8]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[9]	刘延飞, 彭征, 王艺辉, 王忠. 基于改进的遗传算法的有刷直流电机PID参数整定[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1634-1641.
[10]	李晓寒, 贾华丁, 程雪, 李太勇. 基于改进遗传算法和图神经网络的股市波动预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1624-1633.
[11]	吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.
[12]	陈权, 李莉, 陈永乐, 段跃兴. 面向深度学习可解释性的对抗攻击算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 510-518.
[13]	刘忠慧, 王梓宥, 闵帆. 近似概念的遗传生成算法及其推荐应用[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 412-418.
[14]	张俊杰, 仇润鹤. 认知超密集网络用户关联与资源分配联合优化遗传算法[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3856-3862.
[15]	高银萍, 苌道方, 陈俊贤. 混堆模式下基于动态规则NSGA Ⅱ的自动堆垛起重机作业优化[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3259-3267.

结合遗传算法和滚动调度的多机器人任务分配算法

Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 31

相关文章 15

编辑推荐

Metrics