Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-16T09:24:56.132Z Has data issue: false hasContentIssue false
  • English
  • Français

Partially defined constraints in constraint-based design

Published online by Cambridge University Press:  09 November 2006

ARNAUD LALLOUET  and
ANDREÏ LEGTCHENKO
ARNAUD LALLOUET
Affiliation:
Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, Orléans, France
ANDREÏ LEGTCHENKO
Affiliation:
Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, Orléans, France
Get access Rights & Permissions [Opens in a new window]

Abstract

In constraint-based design, components are modeled by variables describing their properties and subject to physical or mechanical constraints. However, some other constraints are difficult to represent, like comfort or user satisfaction. Partially defined constraints can be used to model the incomplete knowledge of a concept or a relation. Instead of only computing with the known part of the constraint, we propose to complete its definition by using machine-learning techniques. Because constraints are actively used during solving for pruning domains, building a classifier for instances is not enough: we need a solver able to reduce variable domains. Our technique is composed of two steps: first we learn a classifier for the constraint's projections and then we transform the classifier into a propagator. We show that our technique not only has good learning performances but also yields a very efficient solver for the learned constraint.

Keywords

Computer-Aided DesignConstraint ProgrammingMachine Learning
Type
Research Article
Information
AI EDAM , Volume 20 , Issue 4 , November 2006 , pp. 297 - 311
Copyright
© 2006 Cambridge University Press

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

Abdennadher, S. & Rigotti, C. (2004). Automatic generation of rule-based constraint solvers over finite domains. Transactions on Computational Logic 5(2).
Alberti, M., Gavanelli, M., Lamma, E., Mello, P., & Milano, M. (in press). A chr-based implementation of known arc-consistency. Theory and Practice of Logic Programming.
Apt, K.R. (1999). The essence of constraint propagation. Theoretical Computer Science 221(1–2), 179–210.Google Scholar
Apt, K.R. & Monfroy, E. (1999). Automatic generation of constraint propagation algorithms for small finite domains. In Int. Conf. Principles and Practice of Constraint Programming, Lecture Notes in Computer Science (Joxan, J., Ed.), Vol. 1713, pp. 58–72, Alexandria, VA. New York: Springer.
Bessière, C., Coletta, R., Freuder, E.C., & O'Sullivan, B. (2004). Leveraging the learning power of examples in automated constraint acquisition. In Principles and Practice of Constraint Programming, Lecture Notes in Computer Science (Wallace, M., Ed.), Vol. 3258, pp. 123–137, Toronto. New York: Springer.
Bessière, C., Hebrard, E., Hnich, B., & Walsh, T. (2004). The complexity of global constraints. In National Conf. Artificial Intelligence (McGuiness, D.L. & Ferguson, G., Eds.), pp. 112–117. San Jose, CA, July 25–29, 2004. Menlo Park, CA: AAAI Press/MIT Press.
Bessière, C. & Régin, J.-C. (1997). Arc-consistency for general constraint networks: preliminary results. In IJCAI, pp. 398–404, Nagoya, San Francisco, CA: Morgan Kaufmann.
Chandrasekaran, B. (1999). Design problem solving: a task analysis. AI Magazine 11(4), 59–71.Google Scholar
Coletta, R., Bessière, C., O'Sullivan, B., Freuder, E.C., O'Connell, S., & Quinqueton, J. (2003). Semi-automatic modeling by constraint acquisition. In Int. Conf. Principles and Practice of Constraint Programming, Lecture Notes in Computer Science (Rossi, F., Ed.), Vol. 2833, pp. 812–816, Kinsale, Ireland. New York: Springer.
Davenport, A., Tsang, E., Wang, C., & Zhu, K. (1994). GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement. In National Conf. Artificial Intelligence, pp. 325–330, Seattle, WA. Menlo Park, CA: AAAI Press.
Faltings, B. & Macho-Gonzalez, S. (2002). Open constraint satisfaction. In Int. Conf. Principles and Practice of Constraint Programming, Lecture Notes in Computer Science (van Hentenryck, P., Ed.), Vol. 2470, pp. 356–370, Ithaca, NY, September 7–13, 2002. New York: Springer.
Freund, Y. & Shapire, R. (1999). A short introduction to boosting. Journal of the Japanese Society for Artificial Intelligence 14(5), 771–780.Google Scholar
Hornik, K., Stinchcombe, M., & White, H. (1989). Multilayer feedforward networks are universal approximators. Neural Networks 2(5), 359–366.Google Scholar
Lallouet, A., Dao, T.B.H., Legtchenko, A., & Ed-Dbali, A. (2003). Finite domain constraint solver learning. In Int. Joint Conf. Artificial Intelligence (Gottlob, G., Ed.), pp. 1379–1380, Acapulco, Mexico. Menlo Park, CA: AAAI Press.
Lallouet, A., Legtchenko, A., Monfroy, E., & Ed-Dbali, A. (2004). Solver learning for predicting changes in dynamic constraint satisfaction problems. In Changes'04, Int. Workshop on Constraint Solving Under Change and Uncertainty (Brown, K., Beck, C. & Verfaillie, G., Eds.), Toronto.
Mitchell, T.M. (1997). Machine Learning. New York: McGraw–Hill.
Moore, R.E. (1966). Interval Analysis. Englewood Cliffs, NJ: Prentice Hall.
O'Sullivan, B. (2002). Constraint-Aided Conceptual Design. London: Professional Engineering Publishing.
Rossi, F. & Sperduti, A. (2004). Acquiring both constraint and solution preferences in interactive constraint system. Constraints 9(4).CrossRef
RuleQuest Research. (2004). See5: An informal tutorial. Available on-line at http://www.rulequest.com/see5-win.html
Rumelhart, D.E., Hinton, G.E., & Williams, R.J. (1986). Learning internal representations by error propagation. Parallel Distributed Processing 1, 318–362.
van Hentenryck, P., Saraswat, V., & Deville, Y. (1991). Constraint processing in cc(fd). Unpublished manuscript.
Verfaillie, G. & Jussien, N. (2003). Dynamic constraint solving. CP'2003 Tutorial. Unpublished manuscript.
Yorke-Smith, N. & Gervet, C. (2003). Certainty closure: A framework for reliable constraint reasoning with uncertainty. In 9th Int. Conf. Principles and Practice of Constraint Programming, Lecture Notes in Computer Science (Rossi, F., Ed.), Vol. 2833, pp. 769–783, Cork, Ireland. New York: Springer.