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

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

作　　者：邓辅秦 黄焕钊 谭朝恩 付兰慧 张建民 林天麟 DENG Fuqin;HUANG Huanzhao;TAN Chaoen;FU Lanhui;ZHANG Jianmin;LAM Tinlun(Faculty of Intelligent Manufacturing,Wuyi University,Jiangmen Guangdong 529020,China;Shenzhen Institute of Artificial Intelligence and Robotics for Society,The Chinese University of Hong Kong,Shenzhen,Shenzhen Guangdong 518116,China)

机构地区：[1]五邑大学智能制造学部,广东江门529020 [2]香港中文大学(深圳)深圳市人工智能与机器人研究院,广东深圳518116

出　　处：《计算机应用》2023年第12期3833-3839,共7页journal of Computer Applications

基　　金：国家重点研发计划“智能机器人”重点专项(2020YFB1313300);深圳市科技计划项目(KQTD2016113010470345);深圳市人工智能与机器人研究院探索性研究项目(AC01202101103);五邑大学横向课题项目(33520098)。

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

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

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]