Improving Combinatorial Auctions for Multi-Robot Exploration

The use of multiple robots in exploration missions has attracted much attention in recent years. Here we deal with the specific problem in which a team of robots have to visit a set of target points to perform some action. Robots have a map of the environment and should compute and execute paths in a distributed way, trying to minimize the total mission cost that is dependent on the quality of the target-to-robot allocation. In this paper, we focus on this target allocation problem and use combinatorial auctions to solve it. We propose novel approaches for improving combinatorial auction mechanisms in the target allocation problem and compare them with approaches based on single-item auctions, sequential auctions, and other combinatorial auction algorithms. Experimental results showed that the auction approaches for multi-robot target allocation proposed in this work achieved better results than other auction based mechanisms found in the literature.