Técnicas de leilão aplicadas à coordenação de múltiplos robôs em missões de exploração de ambientes - Rodolfo Carneiro Cavalcante (2019)
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.