Subconjuntos y subgrafos de restricciones geométricas en el análisis de ensamblajes y mecanismos

The Geometric Reasoning skill is central to many CAD / CAM / CAPP (Computer Aided Design, Manufacturing and Process Planning) applications. There is a growing demand for Geometric Reasoning systems that assess the feasibility of virtual scenes, specified by geometric relationships. Therefore, the problem of Satisfaction of Geometric Restrictions or of Feasibility of Scene (GCS / SF) consists of a basic scenario containing geometric entities, the context of which is used to propose constraint relationships between entities that are still undefined. If the specification of the restrictions is consistent, the answer to the problem is one of the finite or infinite number of solution scenarios that satisfy the proposed restrictions. Otherwise, a diagnosis of inconsistency is expected. The three main strategies used for this problem are: numerical, procedural and mathematical. The numerical and procedural solutions solve only part of the problem, and are not complete in the sense that an absence of response does not mean the absence of it. The mathematical approach previously presented by the authors describes the problem using a series of polynomial equations. The roots common to this set of polynomials characterize the solution space for the problem. This paper presents the use of techniques with Groebner Bases to verify the consistency of the restrictions. She also integrates the subgroups of the special Euclidean group of displacements SE (3) in the formulation of the problem to exploit the structure implied by geometric relationships. Although theoretically sound, these techniques require large amounts of computational resources. This paper proposes Divide and Conquer techniques applied to local GCS / SF subproblems to identify sets of geometric entities strongly restricted to each other. The identification and pre-processing of such local assemblies generally reduces the effort required to solve the entire problem. The identification of these local sub-problems is related to the identification of short cycles in the Geometric Restrictions graph of the GCS / SF problem. Its preprocessing uses the aforementioned techniques of Algebraic Geometry and Groups in the local problems that correspond to these cycles. In addition to improving the efficiency of the solution, the Divide and Conquer techniques capture the physical essence of the problem. This is illustrated by its application to the analysis of degrees of freedom of mechanisms.La habilidad del Razonamiento Geométrico es central a muchas aplicaciones de CAD/CAM/CAPP (Computer Aided Design, Manufacturing and Process Planning). Existe una demanda creciente de sistemas de Razonamiento Geométrico que evalúen la factibilidad de escenas virtuales, especificados por relaciones geométricas. Por lo tanto, el problema de Satisfacción de Restricciones Geométricas o de Factibilidad de Escena (GCS/SF) consta de un escenario básico conteniendo entidades geométricas, cuyo contexto es usado para proponer relaciones de restricción entre entidades aún indefinidas. Si la especificación de las restricciones es consistente, la respuesta al problema es uno del finito o infinito número de escenarios solución que satisfacen las restricciones propuestas. De otra forma, un diagnóstico de inconsistencia es esperado. Las tres principales estrategias usadas para este problema son: numérica, procedimental y matemática. Las soluciones numérica y procedimental resuelven solo parte del problema, y no son completas en el sentido de que una ausencia de respuesta no significa la ausencia de ella. La aproximación matemática previamente presentada por los autores describe el problema usando una serie de ecuaciones polinómicas. Las raíces comunes a este conjunto de polinomios caracterizan el espacio solución para el problema. Ese trabajo presenta el uso de técnicas con Bases de Groebner para verificar la consistencia de las restricciones. Ella también integra los subgrupos del grupo especial Euclídeo de desplazamientos SE(3) en la formulación del problema para explotar la estructura implicada por las relaciones geométricas. Aunque teóricamente sólidas, estas técnicas requieren grandes cantidades de recursos computacionales. Este trabajo propone técnicas de Dividir y Conquistar aplicadas a subproblemas GCS/SF locales para identificar conjuntos de entidades geométricas fuertemente restringidas entre sí. La identificación y pre-procesamiento de dichos conjuntos locales, generalmente reduce el esfuerzo requerido para resolver el problema completo. La identificación de dichos sub-problemas locales está relacionada con la identificación de ciclos cortos en el grafo de Restricciones Geométricas del problema GCS/SF. Su preprocesamiento usa las ya mencionadas técnicas de Geometría Algebraica y Grupos en los problemas locales que corresponden a dichos ciclos. Además de mejorar la eficiencia de la solución, las técnicas de Dividir y Conquistar capturan la esencia física del problema. Esto es ilustrado por medio de su aplicación al análisis de grados de libertad de mecanismos