Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-23T03:27:17.687Z Has data issue: false hasContentIssue false
  • English
  • Français

Constraint-based reasoning via Grobner Bases

Published online by Cambridge University Press:  27 February 2009

Sivand Lakmazaheri
Sivand Lakmazaheri
Affiliation:
Department of Civil Engineering, The Catholic University of America, Washington, DC 20064, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Constraint-based reasoning is a problem-solving approach based on deductive reasoning. In this approach, a problem is modeled in terms of hypotheses and conclusion constraints, and it is solved via constraint satisfaction. The ability to handle linear and nonlinear algebraic constraints is essential for successful application of constraint-based reasoning in engineering. Due to the scarcity of algebraic techniques for satisfying nonlinear constraints, little attention has been paid to the use of constraint-based reasoning for solving nonlinear problems. This paper examines the use of the Grobner Bases method for satisfying nonlinear constraints in the context of constraint-based reasoning. After a brief introduction to the Grobner Bases method and its role in constraint-based reasoning, two examples are presented. The first example illustrates the use of Grobner bases, in the context of constraint-based reasoning, for reasoning about the behavior of beams. The second example illustrates the geometry configuration of truss structures via constraint-based reasoning.

Keywords

Constraint-based ReasoningGrobner BasesDeductive ReasoningConstraints
Type
Articles
Information
AI EDAM , Volume 11 , Issue 1 , January 1997 , pp. 5 - 15
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Adams, W. W., & Loustaunau, P. (1990). An Introduction to Grobner Bases. The American Mathematical Society, Providence, RI.Google Scholar
Borning, A. (1979). ThingLab—A constraint-oriented simulation laboratory. Xerox PARC Technical Report SSL–79–3, Palo Alto, CA.Google Scholar
Buchberger, B. (1965). Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalem Polynomideal. Ph.D. Thesis, Inst. University of Innsbruck, Innsbruck, Austria.Google Scholar
Chan, W.T. (1986). Logic programming for managing constraint-based engineering design. Ph.D. Thesis, CE Department, Stanford University, Stanford, CA.Google Scholar
Chou, S.C. (1985). Proving and discovering theorems in elementary geometry using Wu's method. Ph.D. Thesis, Department of Mathematics, University of Texas, Austin.Google Scholar
Collins, G.E. (1975). Quantifier Elimination for Real Fields by Partial Cylindrical Algebraic Decomposition (Lecture Notes in Computer Science 33). Springer-Verlag, New York.Google Scholar
Cox, D., Little, J., & O'Shea, D. (1991). Ideals, Varieties, and Algorithms. Springer-Verlag, New York.Google Scholar
Dahl, V., Sidebottom, G., & Ueberla, J. (1995). Automatic configuration through constraint based reasoning. Int. J. Expert Sys. 6(4), 561–579.Google Scholar
de la Cruz, J., Conejo-Munoz, R., Morales-Bueno, R., & Puy-Huarte, H. (1995). Highway design by constraint specification. Artif. Intell. Engrg. 9(3), 127–139.CrossRefGoogle Scholar
Ervin, S.M., & Gross, M.D. (1987). RoadLab: A constraint based laboratory for road design. Artif. Intell. Engrg. 2(4), 224–234.CrossRefGoogle Scholar
Gritzmann, P., & Sturmfels, B. (1993). Minkowski addition of polytopes: Computational complexity and applications to Grobner Bases. SIAM J. Discrete Math. 6(2), 246–269.CrossRefGoogle Scholar
Gross, M. (1986). Design as exploring constraints. Ph.D. Thesis, Department of Architecture, MIT, Cambridge.Google Scholar
Guesgen, H., & Hertzberg, J. (1993). A constraint-based approach to spatiotemporal reasoning. J. Appl. Intell. 3(1), 71–90.CrossRefGoogle Scholar
Hong, H. (1993). RISC-CLP(Real): Logic programming with nonlinear constraints over the reals. In Constraint Logic Programming (Benhamou, F. and Colmerauer, A., Eds.). MIT Press, Cambridge.Google Scholar
Ioakimidis, N.I., & Anastasselou, E.G. (1993). Computer-based manipulation of systems of equations in elasticity problems with Grobner Bases. Comput. Methods Appl. Mech. Engrg. 110(1/2), 103–111.CrossRefGoogle Scholar
Ioakimidis, N.I., & Anastasselou, E.G. (1994). Application of Grobner Bases to problems of movement of a particle. Comp. Math. Applic. 27(3), 51–57.CrossRefGoogle Scholar
Ioakimidis, N.I. (1995). Determination of critical buckling loads with Grobner Bases. Comput. Struct. 55(3), 433–440.CrossRefGoogle Scholar
Lakmazaheri, S., & Rasdorf, W.J. (1989). Constraint logic programming for the analysis and partial synthesis of truss structures. AI EDAM 3(3), 157–173..Google Scholar
Lakmazaheri, S., & Rasdorf, W.J. (1990). The analysis and partial synthesis of truss structures via theorem proving. Engrg. Comput. 6(1), 31–45.CrossRefGoogle Scholar
Navinchandra, D. (1986). Intelligent use of constraints for activity scheduling. CERL-N-86/15, Construction Engineering Research Laboratory, University of Illinois.Google Scholar
Sawada, H., Terasaki, S., & Aiba, A. (1994). Parallel computation of Grobner Bases on distributed memory machines. J. Symb. Computat. 18(3), 207–222.CrossRefGoogle Scholar
Schwab, S. (1992). Extended parallelism in the Grobner Basis algorithm. J. Parallel Processing 21(1), 39–66.CrossRefGoogle Scholar
Sussman, G.J., & Steele, G.L. (1980). Constraint—A language for expressing almost-hierarchical descriptions. Artif. Intell. 14(1), 1–39.CrossRefGoogle Scholar
Suzuki, H., Ando, H., & Kimura, F. (1990). Geometric constraints and reasoning for geometrical CAD systems. Comput. Graphics 14(2), 211–224.CrossRefGoogle Scholar
Sutherland, I. (1963). SketchPad: A man-machine graphical communication system. IFIP Proc. Spring Joint Computer Conference.CrossRefGoogle Scholar
Wu, W. (1978). On the decision problem and the mechanization of theorem proving in elementary geometry. Scientia Sinica 21(2), 152–172.Google Scholar