姜 栋，徐 欣

(杭州电子科技大学 通信工程学院，杭州 310018)

基于帕累托改进的多机器人动态任务分配算法

姜 栋，徐 欣*

(杭州电子科技大学 通信工程学院，杭州 310018)

针对多机器人系统动态任务分配中存在的优化问题，在使用合同网初始任务分配的基础上提出了一种使用帕累托改进的任务二次分配算法。多机器人系统并行执行救火任务时，首先通过初始化任务分配将多机器人划分为若干子群；然后,每个子群承包某一救火任务，子群在执行任务的同时与就近子群进行帕累托改进确定需要迁移的机器人，实现两子群之间帕累托最优；最后,使用后序二叉树遍历对所有子群进行帕累托改进实现全局帕累托最优。理论分析和仿真结果表明，相较于强化学习算法和蚁群算法，所提算法的救火任务时间分别减少26.18%和37.04%；相较于传统合同网方法,所提算法在时间方面能够高效完成救火任务，在系统收益方面也具有明显优势。

多机器人；救火任务；任务分配；合同网；帕累托改进；帕累托最优

0 引言

多机器人系统越来越多地应用到军事、未知环境和灾区等领域，包括无人飞行器(Unmanned Aerial Vehicle, UAV)、自动地面车辆(Automatic Ground Vehicle, AGV)、无人水下航行器(Unmanned Underwater Vehicle, UUV)。多机器人通过协作来交流和分享信息改进了单个机器人的性能，如任务执行效率、健壮性、灵活性和容错性[1-5]。因此，多机器人系统的研究成为机器人研究热点，近年来，多机器人系统涵盖了分布式决策，编队控制、区域覆盖及其相关应用[6]。Gerkey等[7]对多机器人系统在不同领域的任务分配问题进行特定分类，包括运筹学、经济学、调度问题、网络流量问题和组合优化问题。……