Técnicas de leilão aplicadas à coordenação de múltiplos robôs em missões de exploração de ambientes

Abstract

Exploring an environment using multiple autonomous robots is one of the fundamental problems in mobile robotics. A typical exploration problem is that in which robots have a model of the environment and they need to visit a set of virtual targets in this environment in order to perform some operation or just collect informations in these points. Using a team of cooperative robots in exploration tasks presents several advantagessuch as more speed in the mission and more robustness when compared with single robot systems. However, assign robots to visit targets in order to minimize the mission costs is a NP-Hard problem. Single-item Auctions and Sequential Single-Item Auctions are approximated mechanisms widely used in solving the coordination problem in exploration missions. However, given the limitations of these kind of auctions, these mechanisms provide low quality solutions. In the present work, it was investigated the use of combinatorial auctions in exploration of environments. It was proposed the use of some algorithms in order to make the combinatorial auction a polynomial allocationprocess. These algorithms were implemented and several experiments were performed in order to compare the quality provided by combinatorial auction with those provided by single-item auctions and sequential auctions. The results showed that some algorithms used in combinatorial auctions achieved better results than single-item andsequential auctions.