Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-24T19:09:04.202Z Has data issue: false hasContentIssue false
  • English
  • Français

Search heuristics for constraint-aided embodiment design

Published online by Cambridge University Press:  11 February 2009

R. Chenouard ,
L. Granvilliers  and
P. Sebastian
R. Chenouard
Affiliation:
ENSAM Bordeaux, Transferts Ecoulements Fluides Energétique, CNRS, Talence, France
L. Granvilliers
Affiliation:
University of Nantes, Laboratoire d'Informatique de Nantes Atlantique, CNRS, Nantes, France
P. Sebastian
Affiliation:
ENSAM Bordeaux, Transferts Ecoulements Fluides Energétique, CNRS, Talence, France
Get access Rights & Permissions [Opens in a new window]

Abstract

Embodiment design (ED) is an early phase of product development. ED problems consist of finding solution principles that satisfy product requirements such as physics behaviors and interactions between components. Constraint satisfaction techniques are useful to solve constraint-based models that are often partial, heterogeneous, and uncertain in ED. This paper proposes new constraint satisfaction techniques to tackle piecewise-defined physics phenomena or skill-based rules and multiple categories of variables arising in design applications. New search heuristics and a global piecewise constraint are introduced in the branch and prune framework. The capabilities of these techniques are illustrated with both academic and real-world problems. Complete models of the latter are presented.

Keywords

Constraint SatisfactionEmbodiment DesignHeuristicSearch
Type
Research Article
Information
AI EDAM , Volume 23 , Issue 2 , May 2009 , pp. 175 - 195
Copyright
Copyright © Cambridge University Press 2009

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

Beame, P., Cook, S., Edmonds, J., Impagliazzo, R., & Pitassi, T. (1995). The relative complexity of NP search problems. Proc. 27th Annual ACM Symp. Theory of Computing, STOC ’95, pp. 303–314. New York: ACM Press.Google Scholar
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys 35 ( 3), 268–308.CrossRefGoogle Scholar
Benhamou, F., Goualard, F., Granvilliers, L., & Puget, J.-F. (1999). Revising hull and box consistency. Int. Conf. Logic Programming, pp. 230–244. Cambridge, MA: MIT Press.Google Scholar
Bliek, C., Neveu, B., & Trombettoni, G. (1998). Using graph decomposition for solving continuous CSPs. CP’98, Pisa, Italy.Google Scholar
Collavizza, H., Delobel, F., & Rueher, M. (1999). Extending consistent domains of numeric CSPs. IJCAI'99, Stockholm, Sweden.Google Scholar
Cook, S.A., & Mitchell, D.G. (1997). Finding hard instances of the satisfiability problem: a survey. DIMACS Series in Discrete Math and Theoretical Computer Science 35, 1–17.CrossRefGoogle Scholar
Fischer, X., Sébastian, P., Nadeau, J.-P., & Zimmer, L. (2004). Constraint based approach combined with metamodeling techniques to support embodiment design. SCI'04, Orlando, FL.Google Scholar
Gelle, E., & Faltings, B. (2003). Solving mixed and conditional constraint satisfaction problems. Constraints 8, 107–141.CrossRefGoogle Scholar
Goldsztejn, A., & Jaulin, L. (2006). Inner and outer approximations of existentially quantified equality constraints. CP'06, Nantes, France.Google Scholar
Granvilliers, L., & Benhamou, F. (2006). Algorithm 852: realpaver: an interval solver using constraint satisfaction techniques. ACM TOMS 32 ( 1), 138–156.CrossRefGoogle Scholar
Hyvönen, E. (1989). Constraint reasoning based on interval arithmetic. IJCAI'89, Detroit.Google Scholar
Jégou, P., & Terrioux, C. (2003). Hybrid backtracking bounded by tree decomposition of constraint networks. Artificial Intelligence 146, 43–75.CrossRefGoogle Scholar
Kearfott, R.B. (1996). Rigorous Global Search: Continuous Problems. Nonconvex Optimization and Its Applications. New York: Kluwer Academic.CrossRefGoogle Scholar
Lhomme, O. (1993). Consistency techniques for numeric CSPs. IJCAI'93, Chambéry, France.Google Scholar
Mailharro, D. (1998). A classification and constraint-based framework for configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12 ( 4), 383–397.CrossRefGoogle Scholar
Mittal, S., & Falkenhainer, B. (1990). Dynamic constraint satisfaction problems. AAAI'90, Boston.Google Scholar
Moore, R. (1966). Interval Analysis. Englewood Cliffs, NJ: Prentice–Hall.Google Scholar
Neveu, B., Chabert, G., & Trombettoni, G. (2006). When interval analysis helps interblock backtracking. CP'06, Nantes, France.Google Scholar
O'Sullivan, B. (2001). Constraint-Aided Conceptual Design. London: Professional Engineering Publishing.Google Scholar
Pahl, G., & Beitz, W. (1996). Engineering Design: A Systematic Approach. Berlin: Springer.CrossRefGoogle Scholar
Richardson, D. (1968). Some unsolvable problems involving elementary functions of a real variable. Journal of Symbolic Logic 33, 514–520.CrossRefGoogle Scholar
Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. New York: Elsevier.Google Scholar
Rothwell, R., & Gardiner, P. (1990). Robustness and Product Design Families, Design Management: A Handbook of Issues and Methods (Oakley, M., Ed.), pp. 279–292. Cambridge, MA: Blackwell.Google Scholar
Sabin, M., Freuder, E.C., & Wallace, R.J. (2003). Greater efficiency of conditional constraint satisfaction. CP'03, Kinsale, Ireland.Google Scholar
Sam-Haroud, D., & Faltings, B. (1996). Consistency techniques for continuous constraints. Constraints 1, 85–118.CrossRefGoogle Scholar
Sébastian, P., Chenouard, R., Nadeau, J.-P., & Fischer, X. (2006). The embodiment design constraint satisfaction problem of the BOOTSTRAP facing interval analysis and genetic algorithm based decision support tools. Proc. Virtual Concept 2006, Mexico.Google Scholar
Stumptner, M., Friedrich, G., & Haselböck, A. (1998). Generative constraint-based configuration of large technical systems. Artificial Intelligence for Engineering Design, Analysis and Manfacturing 12 ( 4), 307–320.Google Scholar
Van-Hentenryck, P., Mc Allester, D., & Kapur, D. (1997). Solving polynomial systems using branch and prune approach. SIAM Journal on Numerical Analysis 34 ( 2), 797–827.CrossRefGoogle Scholar
Vareilles, E., Aldanondo, M., Gaborit, P., & Hadj-Hamou, K. (2005). Using interval analysis to generate quadtrees of piecewise constraints. IntCP ’05, Barcelona, Spain.Google Scholar
Vu, X., Sam-Haroud, D., & Silaghi, M. (2002). Approximation techniques for non-linear problems with continuum of solutions. SARA’02, Kananaskis, Canada.Google Scholar
Wang, P.S. (1974). The undecidability of the existence of zeros of real elementary functions. Journal of ACM 21 ( 4), 586–589.CrossRefGoogle Scholar
Yannou, B., Simpson, T.W., & Barton, R.R. (2003). Towards a conceptual design explorer using metamodeling approaches and constraint programming. ASME DETC ’03, Chicago.Google Scholar
Zimmer, L., & Zablit, P. (2001). Global aircraft predesign based on constraint propagation and interval analysis. CEAS-MADO ’01, Koln, Germany.Google Scholar