Enumerating and assembling configurations with modular robots

Abstract

Esta tese apresenta novas contribuições para dois problemas fortemente relacionados: a enumeração e o sequenciamento da montagem de configurações (Assembly Sequence Planning - ASP) constituídas por robôs modulares. Ferramentas matemáticas, mais especificamente, ferramentas de Teoria dos Grafos, são largamente empregadas no tratamento desses dois problemas. Em sua primeira parte, a tese aborda o problema de enumeração, fornecendo um novo método que permite enumerar as configurações não-isomórficas de robôs modulares com módulos cúbicos. Este método é baseado em trabalhos anteriores do autor para robôs modulares com módulos planares. O método foi implementado em C++, fornecendo a enumeração de configurações com até 10 módulos cúbicos. Este resultado constitui um avanço em relação ao número de módulos alcançados na literatura. Em sua segunda parte, a tese introduz três novos ASP para robôs modulares que tratam classes de configurações em aberto na literatura. Esta tese é o primeiro trabalho a resolver os seguintes problemas: Como montar configurações compostas por sistemas de robôs modulares; como montar configurações com corredores estreitos; como montar configurações com furos internos; como montar configurações sem furos internos nem corredores estreitos, mas escolhendo o ponto de partida do ASP e como montar estruturas planares verticais. Todos os ASP obedecem a condição de acessibilidade, ou seja, nenhum módulo pode passar por um corredor entre dois robôs que estejam na estrutura, se este corredor for tão estreito quanto o lado de um módulo. Como resultado complementar, esta tese apresenta novas contribuições ao ASP para estrutura marítimas de Seo, Yim e Kumar.

Abstract : This thesis presents novel contributions to two strongly related problems:the enumeration and the assembly sequence planning (ASP) formodular robots. Mathematical tools, more specifically graph theorytools, are extensively employed in the treatment of both problems.First, this thesis deals with the enumeration problem, providing a completeand original method which allows enumerating the nonisomorphicconfigurations of cubic modular robots. The proposed method is basedon author s previous works for planar modular robots. This methodwas implemented in C++ providing the enumeration of configurationsup to 10 cubic modules which constitutes an advance compared to thenumber of modules achieved in literature. Then, three novel ASP formodular robots are introduced in this thesis. These ASP cover classesof target structures not solved in literature. To the best of the author sknowledge, the thesis is the first work that solves the following problems:assembling target structures composed by shape heterogeneousmodular robots systems; assembling planar target structures with narrowcorridors, i.e. corridors which are too narrow for a robot to traverse;assembling configurations without narrow corridors, and choosing theASP starting point; assembling planar vertical structures. All the ASPherein proposed satisfies the accessibility condition, i.e. any modulecannot pass through a gap only as large as a side of a module betweentwo physical robots already assembled in the structure. As a complementaryresult, this thesis presents novel contributions to the ASP formaritime structures of Seo, Yim and Kumar.