Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
Main Article Content
Keywords
Graph cycle, Groebner basis, constraint graph, mechanisms, assemblies.
Resumen
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
Descargas
Referencias
[2] O. Ruiz and P. Ferreira. Algebraic geometry and group theory in geometric constraint satisfaction, Proceedings, International Symposium on Symbolic and Algebraic Computation, University of Oxford, 224-233 (1994).
[3] A. Ambler and R. Popplestone. Inferring the positions of bodies from specified spatial relationships, Artificial Intelligence, 6, 1975.
[4] E. Celaya and C. Torras. Finding object configurations that satisfy spatial relationships, Proceedings, European Conference on Artificial Intelligence, Stockholm, 141-146 (1990).
[5] D. Rocheleau and K. Lee. System for interactive assembly modelling, Computer Aided Design, 19(2), 1987.
[6] Z. Fu and A. DePennington. Geometric reasoning based on grammar parsing, Journal of Mechanical Design, 116(3), 763-769 (1994).
[7] G. Kramer. Solving geometric constraint systems, MIT Press, 1992.
[8] J. Turner et al. Constraint representation and reduction in assembly modeling and analysis, IEEE Journal of Robotics and Automation, 8, 741-750 (1992).
[9] J. Angeles. Rational kinematics, Springer-Verlag, 1988.
[10] J. Herve. Analyse structurelle des mechanisms par groupe des deplacements, Mechanism and Machine Theory, 13, 437-450 (1978).
[11] C. Hoffmann. Geometric and solid modeling, Morgan-Kaufmann Publishers Co., 1989.
[12] J. Angeles. Spatial kinematic chains, Springer-Verlag, 1982.
[13] R. Popplestone et al. An interpreter for a language for describing assemblies, Artificial Intelligence, 14, 79-106 (1980).
[14] R. Popplestone. Group theory and robotics, Robotics Research, The First Intl. Symposium, MIT Press, M. Brady and R. Paul, editors, 1984.
[15] R. Popplestone et al. A group theoretic approach to assembly planning, Artificial Intelligence Magazine, 1990.
[16] F. Thomas and C. Torras. Inferring feasible assemblies from spatial constraints, Technical Report IC-DT-1989.03, Institute of Cybernetics, Univ. Polytecnic of Catalonia, 1989.
[17] F. Thomas. Graphs of kinematic constraints, Computer Aided Mechanical Assembly Planning, L. Homem de Mello and S. Lee, editors, Kluwer Academic Publishers, 81–109 (1991).
[18] E. Celaya and C. Torras. Solving multiloop linkages with limited-range joints, Mechanism and Machine Theory, 29(3), 1994.
[19] O. Ruiz. Geometric reasoning in computer aided design, manufacturing and process planning, Ph.D. Thesis, University of Illinois at Urbana-Champaign, 1995.
[20] Oscar E. Ruiz S. and Placid M. Ferreira. Algebraic Geometry and Group Theory in Geometric Constraint Satisfaction for Computer Aided Design and Assembly Planning, IIE Transactions. Focused Issue in Design and Manufacturing. 28(4), ISSN 0740-817X, London: Chapman and Hall, 281–294 (1996).
[21] D. Kapur and Y. Lakshman. Elimination methods: an introduction, Symbolic and Numerical Computation for Artificial Intelligence, Academic Press, B. Donald, D. Kapur and J. Mundy, editors, 45-88 (1992).
[22] B. Buchberger. Applications of Groebner basis in non-linear computational geometry, Geometric Reasoning, MIT Press, D. Kapur and J. Mundy editors, 413–446 (1989).
[23] Oscar E. Ruiz S. and Placid M. Ferreira. Geometric Reasoning in the Analysis of Assemblies and Mechanisms, ASME Design Engineering Technical Conferences. Boston, Massachusetts, ISBN 0-7918-1716-4, New York: A.S.M.E. Press, 1–12 (1995).
[24] J. J. McPhee. On the use of linear graph theory in multibody system dynamics. Non-linear Dynamics, 9(1-2), ISSN: 0924-090X, Springer: Netherlands, 73–90 (1996).
[25] C. Hoffmann and R. J. Arinyo. Symbolic Constraints in Constructive Geometric Constraint Solving. J. Symbolic Computation, 23(2/3), 287–299 (1997).
[26] W. Ledermann. Introduction to the theory of finite groups, Oliver and Boyd, 1953.
[27] W. Ledermann. Introduction to group theory, Barnes and Noble, 1973.
[28] J. R. Johnson and D. Johnson. Graph theory with engineering applications, New York: Ronald Press Company, 1972.
[29] N. Deo. Graph theory with applications to engineering and computer science, Englewood Cliffs, N.J.: Prentice-Hall Inc., 1974.
[30] M. Swamy and K. Thulasiraman. Graphs, networks and algorithms, John Wiley & Sons, 1974.
[31] T. Becker. Groebner bases: a computational approach to commutative algebra, New York: Springer-Verlag, 1993.