IJCAI-97 TUTORIALS

Constraint Satisfaction Problems and Objects

Peirre Roy and Francois Pachet

Course Description

 Combinatorial optimization is a powerful paradigm to solve complex problems. It has a wide range of applications such as planning, scheduling, resource sharing, in a wide range of domains (transportation, production, mass marketing, network optimization, human resources management). CSP techniques provide efficient algorithms to prune search spaces. On the other hand, object-orientation is an acknowledged paradigm to represent richly structured domains. The combination of the two paradigms yields powerful programming languages. This tutorial aims at introducing the area of CSP and their use in conjunction with an object-oriented programming language. The tutorial will describe the range of applications, and give a comprehensive overview of technical issues.

The 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.

Prerequisite Knowledge

Attendees should be familiar with object-oriented programming, but not necessarily with constraint programming.

About the Lecturers

 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.

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).

higuchi@etl.go.jp
Last modified: Thu Feb 20 13:46:54 JST 1997