Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-97CLXD
Type: | Dissertação de Mestrado |
Title: | Técnicas de leilão aplicadas à coordenação de múltiplos robôs em missões de exploração de ambientes |
Authors: | Rodolfo Carneiro Cavalcante |
First Advisor: | Luiz Chaimowicz |
First Co-advisor: | Thiago Ferreira de Noronha |
First Referee: | Sebastián Alberto Urrutia |
Second Referee: | Mario Fernando Montenegro Campos |
Abstract: | A exploração de ambientes utilizando múltiplos robôs autônomos é considerada um dos problemas fundamentais da robótica móvel. Um problema de exploração típico é aquele onde os robôs possuem um modelo do ambiente e precisam visitar um conjunto de pontos ou alvos virtuais neste ambiente de forma a executar alguma operação ou apenas coletar informações nestes pontos. A utilização de um time de robôs cooperativos para executar esta tarefa de exploração apresenta várias vantagens como rapidez na missão e robustez do sistema de exploração em comparação a sistemas com único robô. No entanto, atribuir robôs para a visita dos alvos de forma a minimizar os custosda missão é um problema NP-Difícil. Leilões de único item e leilões sequenciais de único item são mecanismos aproximados que têm sido muito utilizados para resolver o problema de coordenação em missões de exploração. No entanto, dadas as limitações destes leilões, estes métodos acabam produzindo alocações com baixa qualidade. Nestetrabalho, foi investigado a aplicação dos leilões combinatórios ao problema de coordena ção de múltiplos robôs na exploração de ambientes. Leilões combinatórios são mais complexos, porém são capazes de prover soluções de melhor qualidade. Foi propostoo uso de alguns algoritmos de forma a tornar o leilão combinatório um processo de alocação polinomial. Tais algoritmos foram implementados e diversos experimentos foram realizados de forma a comparar a qualidade das soluções providas pelos leilões combinatórios com aquelas providas pelos leilões de único item e leilões sequenciais. Osresultados mostraram que alguns destes algoritmos utilizados nos leilões combinatórios apresentaram resultados melhores que os leilões de único item e sequenciais. |
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. |
Subject: | Robótica Computação |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-97CLXD |
Issue Date: | 27-Feb-2013 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
rodolfocarneiro.pdf | 8.01 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.