Applications of matroid theory to the structural synthesis and analysis of kinematic chains and mechanisms

Abstract

A decomposição estrutural de cadeias cinemáticas em seus subgrafos biconexos é um procedimento de grande relevância para a síntese e a análise estrutural de mecanismos. No entanto, os métodos atualmente disponíveis ainda apresentam oportunidades de aprimoramento. Abordagens exaustivas, embora garantam a identificação de todas as subcadeias, sofrem com uma complexidade computacional duplamente exponencial, o que as torna inviáveis para cadeias com mais de cinco circuitos independentes. Por outro lado, métodos baseados em heurísticas tendem a ser mais eficientes, mas, por não examinarem todas as combinações possíveis de circuitos, não asseguram completude e podem falhar na detecção de determinadas subcadeias rígidas. Esta tese propõe e valida um novo método completo para a decomposição estrutural, fundamentado na teoria de matroides. A abordagem explora a relação formal entre as uniões de circuitos de um matroide gráfico e os flats de seu matroide dual. Ao enumerar sistematicamente os flats do dual, o algoritmo gera todas as uniões de circuitos do matroide original, garantindo a identificação exata de todas as subcadeias biconexas, sem a redundância de uma busca exaustiva. A eficácia do algoritmo é demonstrada por meio de sua aplicação em duas áreas complementares da teoria dos mecanismos. Na síntese estrutural, o método é empregado como um filtro de degeneracidade em um processo de geração de grafos, permitindo enumerações em larga escala que resultaram em novas listas de cadeias enumeradas. As contribuições incluem a enumeração de cadeias planares com até sete circuitos independentes, a identificação de conjuntos de cadeias mínimas e a primeira enumeração completa de cadeias planares com um grau de liberdade e oito circuitos, totalizando 1.518.499.932 estruturas. Adicionalmente, a síntese de cadeias de Baranov foi estendida para 17 elos, possibilitando a geração de 1.102.170.279 novos grupos de Assur de 16 elos. Na análise estrutural, o método de decomposição serve como base para um novo algoritmo de cálculo de conectividade e variedade. A análise comparativa de métodos existentes mostra que diferentes abordagens da literatura apresentam um problema em comum: seus resultados podem depender da escolha inicial da árvore geradora, isto é, do conjunto selecionado de circuitos independentes, o que pode levar a inconsistências dos resultados. O método proposto supera essa limitação ao produzir uma matriz de mobilidade mínima que é independentemente dessa escolha. Assim, esta pesquisa procura oferecer uma base teórica e computacional que apoia a síntese, ao possibilitar enumerações mais amplas e validadas, e a análise, ao fornecer uma ferramenta para o cálculo de propriedades estruturais.

Abstract: The structural decomposition of kinematic chains into their biconnected subgraphs is a procedure of great relevance for the structural synthesis and analysis of mechanisms. However, currently available methods still present opportunities for improvement. Exhaustive approaches, although they guarantee the identification of all subchains, suffer from double exponential computational complexity, which makes them impractical for chains with more than five independent circuits. On the other hand, heuristic-based methods tend to be more efficient but, by not examining all possible combinations of circuits, do not ensure completeness and may fail to detect certain rigid subchains. This thesis proposes and validates a new complete method for structural decomposition, grounded in matroid theory. The approach explores the formal relationship between the unions of circuits of a graphic matroid and the flats of its dual matroid. By systematically enumerating the dual's flats, the algorithm generates all unions of circuits of the original matroid, ensuring the exact identification of all biconnected subchains without the redundancy of an exhaustive search. The effectiveness of the algorithm is demonstrated through its application in two complementary areas of mechanism theory. In structural synthesis, the method is employed as a degeneracy filter within a graph-generation process, enabling large-scale enumerations that produced new lists of enumerated chains. The contributions include the enumeration of planar chains with up to seven independent circuits, the identification of sets of minimal chains, and the first complete enumeration of planar one-degree-of-freedom chains with eight circuits, totaling 1,518,499,932 structures. Additionally, the synthesis of Baranov chains was extended to 17 links, enabling the generation of 1,102,170,279 new 16-link Assur groups. In structural analysis, the decomposition method serves as the basis for a new algorithm for computing connectivity and variety. A comparative analysis of existing methods reveals that different approaches in the literature share a common issue: their results may depend on the initial choice of a spanning tree, that is, the selected set of independent circuits, which can lead to inconsistent results. The proposed method overcomes this limitation by producing a minimal mobility matrix that is independent of such choices. Thus, this research provides a theoretical and computational basis that supports synthesis, by enabling broader and validated enumerations, and analysis, by providing a tool for computing structural properties.