Evolutionary Computation Approach to Decentralized Multi-robot Task Allocation

摘要

The problem of allocating exploration tasks to a team of mobile robots was addressed in this paper. Each task consists of a site location that needs to be explored by a robot. The objective of the allocation is to minimize the maximum path cost of the robots. Auction-based methods are efficient for decentralized mobile robots to allocate tasks. However, the quality of allocation cannot be guaranteed. This paper presents a decentralized allocation algorithm which combines a sequential single-task auction and task transfer among the robots. After all of the tasks are auctioned off, the robots of the same sub-team transfer tasks to improve the quality of allocation. In order to increase the efficiency of task transferring, the tasks allocated to the sub-team are clustered using an orthogonal genetic algorithm. Each robot determines which tasks should be transferred, and to which robots the tasks should be transferred according to the clusters. The validity of the proposed algorithm was verified with some benchmarks of vehicle routing problem and traveling salesperson problem. The results showed that the proposed algorithm decreased the robot path costs 40% more than that of a well-known auction-based algorithm in most cases.