Geometric constraint subsets and subgraphs in the analysis of assemblies and mechanisms
Main Article Content
Keywords
graph cycle, Groebner basis, constraint graph, mechanisms, assemblies.
Abstract
Geometric Reasoning ability is central to many applications in CAD/CAM/CAPP environments. An increasing demand exists for Geometric Reasoning systems which evaluate the feasibility of virtual scenes specified by geometric relations. Thus, the Geometric Constraint Satisfaction or Scene Feasibility (GCS/SF) problem consists of a basic scenario containing geometric entities, whose context is used to propose constraining relations among still undefined entities. If the constraint specification is consistent, the answer of the problem is one of finitely or infinitely many solution scenarios satisfying the prescribed constraints. Otherwise, a diagnostic of inconsistency is expected. The three main approaches used for this problem are numerical, procedural or operational and mathematical. Numerical and procedural approaches answer only part of the problem, and are not complete in the sense that a failure to provide an answer does not preclude the existence of one. The mathematical approach previously presented by the authors describes the problem using a set of polynomial equations. The common roots to this set of polynomials characterizes the solution space for such a problem. That work presents the use of Groebner basis techniques for verifying the consistency of the constraints. It also integrates subgroups of the Special Euclidean Group of Displacements SE(3) in the problem formulation to exploit the structure implied by geometric relations. Although theoretically sound, these techniques require large amounts of computing resources. This work proposes Divide-and-Conquer techniques applied to local GCS/SF subproblems to identify strongly constrained clusters of geometric entities. The identification and preprocessing of these clusters generally reduces the effort required in solving the overall problem. Cluster identification can be related to identifying short cycles in the Spatial Constraint graph for the GCS/SF problem. Their preprocessing uses the aforementioned Algebraic Geometry and Group theoretical techniques on the local GCS/SF problems that correspond to these cycles. Besides improving the efficiency of the solution approach, the Divide-and-Conquer techniques capture the physical essence of the problem. This is illustrated by applying the discussed techniques to the analysis of the degrees of freedom of mechanisms.
MSC: 68U07
Downloads
References
[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.