An Efficient Ant Colony System for Multi-Robot Task Allocation with Large-scale Cooperative Tasks and Precedence Constraints

Abstract

Multiple heterogeneous robots can work together to execute complex tasks. Given multiple heterogeneous tasks and heterogeneous robots, the allocation of tasks to robots is a challenging optimization problem. Lots of methods have been proposed for the multi-robot task allocation (MRTA) problem. However, most existing methods only consider small-scale tasks without precedence constraints. Hence, this paper tracks the time-extended MRTA problem with large-scale cooperative tasks and precedence constraints, and proposes an efficient ant colony system (ACS) to solve the problem. In the proposed algorithm, we adopt a permutation with task-robot alliance pairs as the encode scheme to represent a feasible solution. A pheromone matrix is initialized by a hierarchical greedy strategy and iteratively updated to record historical experience. Heuristic information related to the optimization objective is also designed to help algorithm find better solutions according to the current state. Through combining pheromone and heuristic information, the ACS is able to search high-quality solutions from a global perspective. Experimental results on multiple problem instances are reported to show the advantage of the proposed method. The proposed ACS method can well solve the MRTA problem with large-scale cooperative tasks and precedence constraints.