Course Description
Course DescriptionThe integration of CSP and objects raises two main issues. First, it should provide an efficient implementation of existing algorithms to solve complex problems. We illustrate this point with the design of a constraint solver, called BackTalk, a canonical integration of CSP with Smalltalk based on the systematic reification of the main concepts of constraint satisfaction: domains, variables, constraints, problems and algorithms. This design allows to integrate specialized algorithms for each constraint.
The second point concerns the representation of knowledge to speed up
the search. In the context of embedded object-oriented CSPs, this aspect
has two sides. First, we show how the design of a CSP involving objects
can drastically influence the performance of the resulting system. This
point is illustrated with a system that performs musical harmonization
of melodies. Second, we show how domain specific knowledge can be
expressed and exploited by the standard CSP mechanism to avoid exploring
useless branches of the search space. This point will be illustrated by
a system that generates crossword grids.
Attendees should be familiar with object-oriented programming, but not
necessarily with constraint programming.
Prerequisite Knowledge
Pierre Roy
is pursuing a Ph.D. thesis at the Laforia Laboratory, under the
supervision of Francois Pachet. He is the main author of the BackTalk
system that will be used throughout the tutorial for demonstrations. He
has realized an automatic harmonization system built with BackTalk and
has published several papers dealing with the integration of constraint
satisfaction techniques with objects. He has presented a tutorial on
these matters at the conference Expert Systems'1995 in Cambridge (UK),
and at the European Smalltalk Users Group (ESUG) in Lausanne
(Switzerland) in 1996.
About the Lecturers
Francois Pachet (Ph.D., Eng.) is associate Professor at University of Paris 6, Laforia-IBP. He is specialized in knowledge representation using object-oriented techniques. He is the author of several papers describing the integration of artificial intelligence techniques in object-oriented languages. He presented various tutorials and organized several workshops at the OOPSLA conference on this theme (embedded object-oriented production systems, metamodeling in 95).