近年来，多移动机器人系统被广泛应用于军事和民用领域，典型的应用包括区域探测、灾难救援和物料运输等。任务分配是提升多移动机器人系统自主协同控制能力的一项关键技术，其目的是为系统中的每个机器人指派其要执行的任务。本文研究了多移动机器人系统在集中式和分布式架构下的单机器人任务分配问题，并进一步研究了需要多个机器人同时执行的多机器人任务的分布式分配问题。第一，针对离线情况下处于基地位置的多移动机器人系统和已知任务的集中式任务分配需求，将上述任务分配问题建模成多目标多旅行商问题，优化目标包括机器人的最大代价和总代价，从而在最优化系统效能的同时平衡不同机器人的代价差异。现有路径增强型多目标优化算法仅在建立路径后使用代价矩阵衡量已经建立路径的性能，因此存在寻优能力差和运行时间长的问题。基于在建立路径过程中参考代价矩阵的蚁群系统算法，本文提出了相应的构建问题解和信息素更新规则，以适应多个优化目标和旅行商，从而提出了一种多目标蚁群系统（MOACS）算法。仿真和硬件在环实验结果表明，提出的MOACS算法在较短的运行时间内得到的帕累托最优解优于现有的两种路径增强型多目标优化算法。第二，针对多移动机器人系统在线实时感知任务的最大化系统成功执行任务数量的分布式分配需求，现有最大化分配数量的性能影响（PI-maxAss）算法需要在性能影响（PI）算法的基础上进行重规划，因此存在迭代次数多、运行时间长以及对通信网络依赖程度高的问题。本文提出了一种高效性能影响（EEPI）算法，其主要特点在于提出了一种最大化任务分配数量的代价函数和一种任务释放步骤。仿真和硬件在环实验结果表明，提出的EEPI算法能够在不到一半的迭代次数和运行时间内得到与PI-maxAss算法接近的任务分配数量。第三，针对在线情况下可能发现的需要多个机器人同时执行的复杂任务的分布式分配需求，现有一致性群算法（CBGA）未考虑执行同一个任务的多个机器人需要同时开始执行该任务的情况，从而在多数场景中无法给出可行的分配方案，以及任务的平均开始时间较晚的不足。本文提出了一种一致性时间表算法（CBTA），每个机器人使用时间表记录所有机器人预估开始执行所有任务的时间，并在时间表的基础上提出了相应的局部规划和全局一致规则。仿真结果表明，提出的CBTA在所有仿真场景中均能给出可行解，且可行解具有较早的任务平均开始时间。
In recent years, multi-mobile robot systems have been widely applied in military and civilian fields, with typical applications including area exploration, disaster relief, and material transportation. Task allocation is a key challenge in improving the efficient collaboration and autonomous control ability of multi-mobile robot systems, aiming to allocate tasks for each robot in the system. This paper addresses the allocation problem of signle-robot tasks and multi-mobile robot systems organized in centralized or decentralized manners, and the decentralized allocation of tasks requiring multiple robots simultaneously is further addressed.First, for the off-line centralized task allocation of a multi-mobile robot system parked in a base station and given tasks, the problem is formulated as a multi-objective multi-traveling salesmen problem. The objectives are to minimize the total and maximum costs of the robots to optimize the utility of the entire system and balance the workload of various robots. In existing tour-improvement-based multi-objective optimization algorithms, cost matrices are only used to measure the costs of constructed paths, resulting in suboptimal solutions and longer execution time. Based on the ant colony system algorithm, in which cost matrices are utilized during the path construction phase, this paper proposes a novel solution construction method and pheromone update rules to cope with multiple objectives and traveling salesmen, resulting in a multi-objective ant colony system (MOACS) algorithm. Extensive simulations and hardware-in-the-loop experiments in various scenarios suggest that the Pareto optimal solutions found by the proposed MOACS within a shorter time can dominate those of the existing two multi-objective optimization algorithms.Second, for the decentralized task allocation of online real-time tasks found by the robots to maximize the number of successfully executed tasks, rescheduling based on the result of the performance impact (PI) algorithm is required for the existing PI for maximizing assignments (PI-maxAss), resulting in more iterations and execution time to converge, making PI-maxAss more reliant on the communication networks of the robots. In this paper, an effective and efficient performance impact (EEPI) algorithm is proposed, which includes a novel cost function aiming to maximize the total task assignments and a task release procedure. Extensive simulations and hardware-in-the-loop experiments suggest that the proposed EEPI algorithm can achieve approximately the same task assignments as the state-of-the-art PI-maxAss algorithm, but it takes fewer iterations and less execution time to converge.Third, for the online decentralized allocation of more valuable multi-robot tasks requiring multiple robots, the robots for a task are not required to start the task simultaneously in the existing consensus-based grouping algorithm (CBGA), resulting in CBGA being unable to generate feasible task allocation plans in most scenarios, and the average start time of tasks being too late. In this paper, a novel consensus-based timetable algorithm (CBTA) is proposed, in which the estimated start time of each task by each robot is recorded in the timetable of each robot. The local allocation and global consensus phases are conducted based on the timetable of each robot. Extensive simulations suggest that the proposed CBTA can generate feasible solutions for all simulated multi-robot task scenarios, and the average start time of tasks is significantly earlier.
