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

• 先进计算 • 上一篇    下一篇

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

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

  1. 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 DENG1,2, Huanzhao HUANG1, Chaoen TAN1, Lanhui FU1, Jianmin ZHANG1, Tinlun LAM2()   

  1. 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)

摘要:

研究多机器人任务分配(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

中图分类号: