Multi-robot task allocation for exploration

来源期刊：中南大学学报(英文版)2006年第5期

论文作者：高平安 蔡自兴

文章页码：548 - 551

Key words：multi-robot systems; task allocation; average path cost; multi-round single-item auction; target tree

Abstract: The problem of allocating a number of exploration tasks to a team of mobile robots in dynamic environments was studied. The team mission is to visit several distributed targets. The path cost of target is proportional to the distance that a robot has to move to visit the target. The team objective is to minimize the average path cost of target over all targets. Finding an optimal allocation is strongly NP-hard. The proposed algorithm can produce a near-optimal solution to it. The allocation can be cast in terms of a multi-round single-item auction by which robots bid on targets. In each auction round, one target is assigned to a robot that produces the lowest path cost of the target. The allocated targets form a forest where each tree corresponds a robot s exploring targets set. Each robot constructs an exploring path through depth-first search in its target tree. The time complexity of the proposed algorithm is polynomial. Simulation experiments show that the allocating method is valid.