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

作者：邓辅秦; 黄焕钊; 谭朝恩; 付兰慧; 张建民; 林天麟^*

来源：计算机应用, 2023, 43(12): 3833-3839.

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

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

• 单位
  香港中文大学（深圳）; 五邑大学; 深圳市人工智能与机器人研究院