Ingeniería y Ciencia (Jun 2006)
Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
Abstract
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. MSC: 68U07
