一种基于近场子集划分的多机器人任务分配算法  

A Multi-robot Task Allocation Algorithm Based on Near-field Subset Partition

作　　者：宋薇[1] 高原 沈林勇[1] 章亚男[1] SONG Wei;GAO Yuan;SHEN Linyong;ZHANG Ya’nan(School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学机电工程与自动化学院,上海200444

出　　处：《机器人》2021年第5期629-640,共12页Robot

摘　　要：针对医护人员重复、机械地配送医疗物资工作效率低的问题,使用了多机器人进行替代,并提出了一种基于"任务地点"近场子集划分的多机器人群体智能任务分配算法。首先采用蚁群算法对任务集进行有序排列,形成一条近场相关的任务链。然后根据任务完成的时间和机器人的路径成本设计目标优化函数,利用遗传算法对该任务链进行子集划分,再将任务子集分配给机器人个体。最后模拟了医院病房的应用场景,设计并搭建了一套多机器人医疗物资运输分配系统。用户在该系统的操作平台上,通过可视化界面能够实时发布新任务,查看已发布任务的分配情况,以及查看机器人的路径。基于该模拟实验平台,对3种不同的任务分配算法进行对比分析,结果是本文算法的分配结果最为合理,所有任务都在规定的时间内完成,机器人的行驶距离大幅缩短。所提出的多机器人任务分配算法可有效解决医疗环境中医疗物资的配送问题,提高了系统的工作效率。Facing the problem of low working efficiency of the medical staff in tasks of the repeated and mechanical delivery of medical supplies, the multiple robots are used as a replacement, and an intelligent task allocation algorithm based on near-field(location of the task) subset partitioning method is proposed for the multi-robot group system. Firstly, ant colony algorithm is used to arrange the tasks in an orderly manner to form a near-field related task chain. Then, an objective optimization function is designed according to the time taken to complete tasks and the cost of robot path. After the task chain is divided into subsets by genetic algorithm, the task subsets are assigned to individual robots. Finally, the application scenes of the hospital wards are simulated, and a transportation and allocation system of medical supplies is designed for multiple robots. On the operating platform of the system, users can release new tasks in real time, view the allocation results of the released tasks and view the robot paths by a visual interface. Based on the simulated experimental platform, 3 different task allocation algorithms are compared and analyzed. And the allocation result of the proposed algorithm is the most reasonable one, as all tasks are completed within a specified time, and the traveling distance of robots is greatly reduced. Therefore, the proposed multi-robot task allocation algorithm can effectively solve the problem of medical supplies allocation in medical environments, and can improve the working efficiency of the system.

关 键 词：多机器人系统 任务分配 任务链优化 蚁群算法 遗传算法 

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