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

doi:10.11772/j.issn.1001-9081.2022121916

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (12): 3833-3839.DOI: 10.11772/j.issn.1001-9081.2022121916

• Advanced computing • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP242

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.

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

Figures/Tables 13

Fig.1 DAG representing one task group

Fig.2 Overall framework of proposed algorithm

Fig.3 Flowchart of improved genetic algorithm

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

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

Fig. 6 Schematic diagram of crossover operator

Fig. 7 Schematic diagram of mutation operator

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

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

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

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

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

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

References 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]	Jun LIANG, Zehong HONG, Songsen YU. Image segmentation model based on improved particle swarm optimization algorithm and genetic mutation [J]. Journal of Computer Applications, 2023, 43(6): 1743-1749.
[2]	Bin WANG, Tian XIANG, Yidong LYU, Xiaofan WANG. Adaptive multi-scale feature channel grouping optimization algorithm based on NSGA‑Ⅱ [J]. Journal of Computer Applications, 2023, 43(5): 1401-1408.
[3]	Hairong XUE, Xiaolong HAN. Integrated scheduling considering automated guided vehicle charging strategy based on improved NSGA-Ⅱ [J]. Journal of Computer Applications, 2023, 43(12): 3848-3855.
[4]	Qian LIU, Yangming ZHANG, Dingsheng WAN. Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model [J]. Journal of Computer Applications, 2023, 43(11): 3327-3333.
[5]	JIANG Songyan, LIAO Xiaojuan, CHEN Guangzhu. Optimal task scheduling method based on satisfiability modulo theory for multiple processors with communication delay [J]. Journal of Computer Applications, 2023, 43(1): 185-191.
[6]	Xu WANG, Yumin SHEN, Xiaoyun XIONG, Peng LI, Jinlong WANG. Data management method for building internet of things based on Hashgraph [J]. Journal of Computer Applications, 2022, 42(8): 2471-2480.
[7]	Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291.
[8]	Yanfei LIU, Zheng PENG, Yihui WANG, Zhong WANG. PID parameter tuning of brushed direct-current motor based on improved genetic algorithm [J]. Journal of Computer Applications, 2022, 42(5): 1634-1641.
[9]	Xiaohan LI, Huading JIA, Xue CHENG, Taiyong LI. Stock market volatility prediction method based on improved genetic algorithm and graph neural network [J]. Journal of Computer Applications, 2022, 42(5): 1624-1633.
[10]	Qingqing WU, Lihua ZHOU, Xuanyi CUN, Guowang DU, Yiting JIANG. Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks [J]. Journal of Computer Applications, 2022, 42(3): 895-903.
[11]	Quan CHEN, Li LI, Yongle CHEN, Yuexing DUAN. Adversarial attack algorithm for deep learning interpretability [J]. Journal of Computer Applications, 2022, 42(2): 510-518.
[12]	Zhonghui LIU, Ziyou WANG, Fan MIN. Genetic algorithm for approximate concept generation and its recommendation application [J]. Journal of Computer Applications, 2022, 42(2): 412-418.
[13]	Junjie ZHANG, Runhe QIU. Joint optimization of user association and resource allocation in cognitive radio ultra-dense networks to improve genetic algorithm [J]. Journal of Computer Applications, 2022, 42(12): 3856-3862.
[14]	Yinping GAO, Daofang CHANG, Chun‑Hsien CHEN. Optimization of automated stacking crane operation based on NSGA Ⅱ with dynamic rules in mixed stacking mode [J]. Journal of Computer Applications, 2022, 42(10): 3259-3267.
[15]	ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 31

Related Articles 15

Recommended Articles

Metrics