constraintprogramming.html


	*Constraint programming on ECAI98* Hana Rudova ECAI-98, the 13th in this series of conferences on artificial intelligence took place in Brighton Research Center from August 23 to 28 in United Kingdom. The conference programme was opened with the workshops and tutorials. I attended the workshops Constraint techniques for artisticapplications and Non binary constraints. The main 3-day programme consisted from invited talks, standard technical reports and shorter young researcher presentations. Presentations were divided into 4 streams where every section started with standard technical reports followed by shorter young researcher presentations. Mostly I will concentrate on streams about Constraint Reasoning or on the papers close to the area of constraint programming because I am working in this area and the conference offered many interesting presentations about this subject which contributed to improvement of my knowledge about the resent research in the area. Workshop Constraint techniques for artistic applications The goal of the workshop Constraint techniques for artistic applications was to study the application of constraint technologies in the artistic domain. Although the contributions in both music and graphical/animation domains were considered, the musical applications prevail over multimedia applications. Many papers were focused on use of constraints for the problem of musical harmonization. For example, F. Pachet and P. Roy defined the problem of automatic harmonization and corresponding CSP in a nice and understandable way. This paper concentrates on the formulation of constraint problems in naturally structured domains, compares this approach with flattened representation of domains and shows advantages of the first approach for applications where the underlying ontologies are not easily reduced to mathematical entities. The next set of papers started with the paper of C. Rueda, et al. discussing the integration of constraint programming approach with functional and visual programming and demonstrating real music composition examples. F. Pachet and O. Delerue proposed a system, in which users may listen to music while controlling location and spatialization of sound source in real time. G. Alvarez presented a calculus integrating concurrent objects and constraints which is used as a base for music composition tools. Non-musical applications were represented by 3 papers only. E. Languenou, et al. were the authors of an article presenting a virtual cameraman which provides the user with camera movements satisfying user defined constraints specified in the image space and/or constraints on the objects of the scene. The underlying constraint system is based on interval arithmetic. M. Jourdan described system for authoring multimedia documents and discussed the problems connected with use of constraint techniques for spatial and temporal organization of such a document. Z. Ruttkay reported on the potentials of an constraint-based animation editor to produce keyframes. Illustrative examples from the first version of facial animation editor were described and some open issues towards the constraint technology were raised. At the end of the workshop, particular application areas and differences between them were discussed. The large number of papers focused on musical applications can be explained by an existence of formalism for the music representation. The use of declarative constraint programming approach is much easier and natural here. For the animation, the problem has to be solved and besides that the problem has to be formally defined. Yet another problem is the 2-dimensionality of animation compared with music linearity, which adds complexity to the graphical and animation applications. The discussions about the particular papers were rich and the workshop was a fruitful meeting of the researchers interested in musical applications especially. But the number of people working in other artistic domains such as graphics and visual arts was low, which was a pity from my point of view. Workshop Non binary constraints he presentations of this workshop paid attention to non binary constraints for finite CSPs or numerical CSPs. The workshop started with the paper of C. Le Pape and P. Baptiste, which reviewed resource constraint propagation techniques for scheduling problems and compared them from the theoretical point of view. S. Heipcke and Y.Colombani formulated labour resource constraints scheduling problem and described types of constraints used in implementation. L. Granvilliers presented a new local consistency technique for constraints over the reals named int-consistency, which is generalization of hull-consistency and box-consistency and which is computed using interval Newton methods or operations from relational interval arithmetic. P. Roy and F. Pachet introduced a method for detecting and exploiting a particular class of symmetry occurring in constraint satisfaction problems, which speeds up the resolution of non-trivial symmetrical problems. P. Jeavons, et al. concentrated on the frequency assignment problem and discussed the need of considering higher-order constraints instead of simpler binary constraints for this kind of problem. J. Larrosa and P. Meseguer studied extending backtracking-based algorithms from binary to non-binary constraints and proposed to enlarge the set of considered constraints by adding projections of the initial constraints. This step decreases inefficiency of direct extension of simple backtracking-based algorithms but the open questions about the amount and type of used projections still exist. P. Shaw, et al. described quasigroup completion problem and compared two possible implementations - the first with all-different constraint and the second with binary pairwise constraint. The inefficiency of the second approach was demonstrated. Ch. Bessi\`ere and J.-Ch. R\'egin proposed a filtering technique in order to deal globally with conjunctions of constraints. First experiments show that cost of this approach is outweighed by the reduction of the search space for difficult problems. A. Liret, et al. presented using of n-ary constraints in the context of medical scenario recognition. B. Smith and L. Proll described a designed problem arising in the color printing industry. The problem was easily formulated but it was shown that many implied constraints has to be added to reduce the symmetry and to solve larger problems sufficiently. It can be said that the workshop was a meeting of constraint programming community at ECAI. A well-timed informations on web gave a view about the contents of this workshop, the quality of the proceedings was high and the organization of the workshop was creditable. After presentations the participants and especially two opposite schools - French and English - discussed their ideas and opinions about the future of the research in the area. The workshop ended by a pleasant wine tasting. Invited talks The first invited talk by R. Lopez de Mantaras started at the evening welcome reception at The Grand Hotel in Brighton by introducing a system for generating expressive musical performances using case-based techniques. Nice and old-fashioned hotel created a dignified atmosphere for his excellent talk. J. F. Puget described in his invited talk the area of constraint programming by the tutorial and the discussion about strengths and weaknesses of this AI technique, which is very successful for solving real industrial problems. An interesting example of the constraint programming market success is its use by 8 from the 10 biggest steel making companies. D. Schmeidler reported on case-based decision theory. S. Muggleton talked about the area of inductive logic programming and its applications in molecular biology and natural language processing. J.-O. Eklundh gave some ideas about robot vision where he concentrated to figure-ground segmentation in a complex and variable environment. The main principles were illustrated by presenting experimental evaluations of an active seeing agent, too. G. Shafer introduced causal logic that uses event spaces, which are generalized event trees, as its models. All these presentations gave me a survey about different areas of artificial intelligence and helped me to consider and understand them in a broader sense. Sections about Constraint Reasoning 2 papers were presented in the section Reformulation . The relation between SAT and CSP frameworks was introduced by T. Castell and H. Fargier . The generalization of both formalisms is defined as an extension of propositional logic where variables has non-binary domains. This common framework allows comparison and translation of some algorithms like resolution principle and the Davis and Putnam procedure. R. Weigel and Ch. Bliek studied reformulation of discrete CSP into a form that involves only boolean variables. This reformulation allows to identify class of tractable CSP and to present sufficient conditions for detecting solvability or unsolvability of the problem in linear time. Second day started with the section Extensions \& Applications . Its first presentation of N. Jussien and O. Lhomme described a new search techniques over numeric CSP called dynamic domain splitting. The domain splitting, where dichotomic search and consistency filtering is combined, creates the ground of searching but standard chronological backtracking is here replaced by dynamic backtracking. Second speaker was missing and so the section has a bit breathing space. Young researcher paper given by H. Rudová (author of this report) described a new framework for solving over-constrained problems using preferences on variables, so called variables' annotations. After presentation the general framework, a correspondence between constraint hierarchies and constraint systems with variables' annotations was showed. S. Heipcke integrated finite domain constraint programming techniques into mathematical programming such that linear programming relaxation was completed with local consistency information. G. Wetzel and F. Zabatta solved the problem of portfolio selection. Resulting quadratic programming problem was converted into linear complementarity problem which can be understood as a disjunctive linear programming problem and solved using constraint programming approach. Optimization section was opened with the paper of M-S. Affane and H. Bennaceur which reported on an algorithm for solving MAX-CSP. Using mathematical programming, a parametric lower bound of unsatisfied constraints' count is established and integrated in a branch and bound searching. J. Larrosa and P. Meseguer proposed partial lazy forward checking algorithm for solving MAX-CSP. The idea of partial forward checking and lazy evaluation is combined in such a way that the number of redundant check computations is decreased. The last speaker of this section J. Slaney presented his and S. Thieacutebaux paper about relation phase transitions and peaks of hardness in the decision problems with the corresponding optimization problems. The last section about Constraint Reasoning named Search & Heuristics ended the conference program. B.M. Smith and S.A. Grant studied behavior of searching with smallest-remaining-domain heuristic. This heuristic has been explained as an implementation of the first-fail principle. They proposed set of heuristics using probability of failing after instantiation of the given variable but their testing on random binary CSP refuted the first-fail principle as a base of smallest-remaining-domain heuristic. T. Walsh , the author of depth-bounded discrepancy search, joined together with the author of interleaved depth-first search P. Meseguer and they compared both algorithm to reduce the cost of heuristic mistakes at the top of the tree. The next speaker had been missing and so the last presentation of the conference followed. Y. Hamadi, et al. adapted intelligent backtracking algorithm to distributed constraint networks. Proposed algorithm allows simultaneous search on independent parts of the network and tries to minimize message passing and to avoid useless restorations when a dead-end is reached. Other presentations H. Shu dealt with solving of view update problem in relational databases by translation into a disjunction of CSPs. This is a novel approach to solve this problem obtaining sound and complete transformation. Between all CSPs solutions, a solution has to be chosen such that a number of changes in database is minimal, which was found in discussion as a possible point of inefficiency because all CSPs solutions have to be examined. In the section Heuristic search were presented 3 papers. S. Edelkamp described the finding of shortest path algorithm for moving target which can be thought as a dynamic version of the Dijkstra algorithm. The solving of this problem is based on incremental calculation of the shortest path tree. J. Holubec reported on a new version of bidirectional heuristic search algorithm obtained by implementation of a new technique depending on the difference between estimated and optimal cost. Very similar bidirectional search algorithm had published H. Kaindel in 1997. He together with A. Scheucher presented the next paper about comparison minimaxing and product propagation for backing up heuristic values in a game trees. The second approach is not used very often but it is expected as a viable alternative. The paper explains this situation because product propagation is better only under very unrealistic (described) conditions. S. Staab was author one of the prized papers entitled On Non-Binary Temporal Relations . He is engaged in generalization of temporal relations in Allen's calculus and in temporal CSP. This generalization includes interval relations with distances, temporal rules and other non-binary relations into temporal reasoning scheme. A.I. Mouaddib and S. Zilberstein were the next prize winners for the paper from the area of Planning and Scheduling . This paper presented a new approach to scheduling progressive processing units, which is based on formulating the scheduling problem as a Markov decision problem and finding an optimal policy. Conclusion I had the young researcher report at this conference which was my first presentation to an international audience. I would like to thank in this place referees for valuable comments which help me in my current research. Also the conference gave me new ideas concerning this work but it was not easy for me to discuss my research with people working in the same fields because of large number of participants from very different areas. On the other hand, many presentations were focused on constraint reasoning research and so I have visited many interesting presentations close to my subject. In my opinion, it was a pity that the papers from Planning and Scheduling sections overlapped 2 times from 3 cases with Constraint Reasoning sections -- scheduling is a natural application domain for constraint technology. The Brighton Research Center at the sea embankment in the center of city is a nice place for every conference. I was accommodated in halls of residence and I was pleasantly surprised by the quality of this student accommodation. I think that ECAI-98 was a successful conference, where many people from different areas of artificial intelligence could meet and discuss their work. Hana Rudova Faculty of Informatics, Masaryk University Botanicka 68a, 602 00 Brno, Czech Republic e-mail: hanka@fi.muni.cz

Constraint programming on ECAI98

Hana Rudova

ECAI-98, the 13th in this series of conferences on artificial intelligence took place in Brighton Research Center from August 23 to 28 in United Kingdom. The conference programme was opened with the workshops and tutorials. I attended the workshops Constraint techniques for artisticapplications and Non binary constraints. The main 3-day programme consisted from invited talks, standard technical reports and shorter young researcher presentations. Presentations were divided into 4 streams where every section started with standard technical reports followed by shorter young researcher presentations. Mostly I will concentrate on streams about Constraint Reasoning or on the papers close to the area of constraint programming because I am working in this area and the conference offered many interesting presentations about this subject which contributed to improvement of my knowledge about the resent research in the area.

Workshop Constraint techniques for artistic applications

The goal of the workshop Constraint techniques for artistic applications was to study the application of constraint technologies in the artistic domain. Although the contributions in both music and graphical/animation domains were considered, the musical applications prevail over multimedia applications.

Many papers were focused on use of constraints for the problem of musical harmonization. For example, F. Pachet and P. Roy defined the problem of automatic harmonization and corresponding CSP in a nice and understandable way. This paper concentrates on the formulation of constraint problems in naturally structured domains, compares this approach with flattened representation of domains and shows advantages of the first approach for applications where the underlying ontologies are not easily reduced to mathematical entities.

The next set of papers started with the paper of C. Rueda, et al. discussing the integration of constraint programming approach with functional and visual programming and demonstrating real music composition examples. F. Pachet and O. Delerue proposed a system, in which users may listen to music while controlling location and spatialization of sound source in real time. G. Alvarez presented a calculus integrating concurrent objects and constraints which is used as a base for music composition tools.

Non-musical applications were represented by 3 papers only. E. Languenou, et al. were the authors of an article presenting a virtual cameraman which provides the user with camera movements satisfying user defined constraints specified in the

image space and/or constraints on the objects of the scene. The underlying constraint system is based on interval arithmetic. M. Jourdan described system for authoring multimedia documents and discussed the problems connected with use of constraint techniques for spatial and temporal organization of such a document. Z. Ruttkay reported on the potentials of an constraint-based animation editor to produce keyframes. Illustrative examples from the first version of facial animation editor were described and some open issues towards the constraint technology were raised.

At the end of the workshop, particular application areas and differences between them were discussed. The large number of papers focused on musical applications can be explained by an existence of formalism for the music representation. The use of declarative constraint programming approach is much easier and natural here. For the animation, the problem has to be solved and besides that the problem has to be formally defined. Yet another problem is the 2-dimensionality of animation compared with music linearity, which adds complexity to the graphical and animation applications.

The discussions about the particular papers were rich and the workshop was a fruitful meeting of the researchers interested in musical applications especially. But the number of people working in other artistic domains such as graphics and visual arts was low, which was a pity from my point of view.

Workshop Non binary constraints

he presentations of this workshop paid attention to non binary constraints for finite CSPs or numerical CSPs.

The workshop started with the paper of C. Le Pape and P. Baptiste, which reviewed resource constraint propagation techniques for scheduling problems and compared them from the theoretical point of view. S. Heipcke and Y.Colombani formulated labour resource constraints scheduling problem and described types of constraints used in implementation. L. Granvilliers presented a new local consistency technique for constraints over the reals named int-consistency, which is generalization of hull-consistency and box-consistency and which is computed using interval Newton methods or operations from relational interval arithmetic. P. Roy and F. Pachet introduced a method for detecting and exploiting a particular class of symmetry occurring in constraint satisfaction problems, which speeds up the resolution of non-trivial symmetrical problems. P. Jeavons, et al. concentrated on the frequency assignment problem and discussed the need of considering higher-order constraints instead of simpler binary constraints for this kind of problem. J. Larrosa and P. Meseguer studied extending backtracking-based algorithms from binary to non-binary constraints and proposed to enlarge the set of considered constraints by adding projections of the initial constraints. This step decreases inefficiency of direct extension of simple backtracking-based algorithms but the open questions about the amount and type of used projections still exist. P. Shaw, et al. described quasigroup completion problem and compared two possible implementations - the first with all-different constraint and the second with binary pairwise constraint. The inefficiency of the second approach was demonstrated. Ch. Bessi\`ere and J.-Ch. R\'egin proposed a filtering technique in order to deal globally with conjunctions of constraints. First experiments show that cost of this approach is outweighed by the reduction of the search space for difficult problems. A. Liret, et al. presented using of n-ary constraints in the context of medical scenario recognition. B. Smith and L. Proll described a designed problem arising in the color printing industry. The problem was easily formulated but it was shown that many implied constraints has to be added to reduce the symmetry and to solve larger problems sufficiently.

It can be said that the workshop was a meeting of constraint programming community at ECAI. A well-timed informations on web gave a view about the contents of this workshop, the quality of the proceedings was high and the organization of the workshop was creditable. After presentations the participants and especially two opposite schools - French and English - discussed their ideas and opinions about the future of the research in the area. The workshop ended by a pleasant wine tasting.

Invited talks

The first invited talk by R. Lopez de Mantaras started at the evening welcome reception at The Grand Hotel in Brighton by introducing a system for generating expressive musical performances using case-based techniques. Nice and old-fashioned hotel created a dignified atmosphere for his excellent talk. J. F. Puget described in his invited talk the area of constraint programming by the tutorial and the discussion about strengths and weaknesses of this AI technique, which is very successful for solving real industrial problems. An interesting example of the constraint programming market success is its use by 8 from the 10 biggest steel making companies. D. Schmeidler reported on case-based decision theory. S. Muggleton talked about the area of inductive logic programming and its applications in molecular biology and natural language processing. J.-O. Eklundh gave some ideas about robot vision where he concentrated to figure-ground segmentation in a complex and variable environment. The main principles were illustrated by presenting experimental evaluations of an active seeing agent, too. G. Shafer introduced causal logic that uses event spaces, which are generalized event trees, as its models.

All these presentations gave me a survey about different areas of artificial intelligence and helped me to consider and understand them in a broader sense.

Sections about Constraint Reasoning

2 papers were presented in the section Reformulation . The relation between SAT and CSP frameworks was introduced by T. Castell and H. Fargier . The generalization of both formalisms is defined as an extension of propositional logic where variables has non-binary domains. This common framework allows comparison and translation of some algorithms like resolution principle and the Davis and Putnam procedure. R. Weigel and Ch. Bliek studied reformulation of discrete CSP into a form that involves only boolean variables. This reformulation allows to identify class of tractable CSP and to present sufficient conditions for detecting solvability or unsolvability of the problem in linear time.

Second day started with the section Extensions \& Applications . Its first presentation of N. Jussien and O. Lhomme described a new search techniques over numeric CSP called dynamic domain splitting. The domain splitting, where dichotomic search and consistency filtering is combined, creates the ground of searching but standard chronological backtracking is here replaced by dynamic backtracking. Second speaker was missing and so the section has a bit breathing space. Young researcher paper given by H. Rudová (author of this report) described a new framework for solving over-constrained problems using preferences on variables, so called variables' annotations. After presentation the general framework, a correspondence between constraint hierarchies and constraint systems with variables' annotations was showed. S. Heipcke integrated finite domain constraint programming techniques into mathematical programming such that linear programming relaxation was completed with local consistency information. G. Wetzel and F. Zabatta solved the problem of portfolio selection. Resulting quadratic programming problem was converted into linear complementarity problem which can be understood as a disjunctive linear programming problem and solved using constraint programming approach.

Optimization section was opened with the paper of M-S. Affane and H. Bennaceur which reported on an algorithm for solving MAX-CSP. Using mathematical programming, a parametric lower bound of unsatisfied constraints' count is established and integrated in a branch and bound searching. J. Larrosa and P. Meseguer proposed partial lazy forward checking algorithm for solving MAX-CSP. The idea of partial forward checking and lazy evaluation is combined in such a way that the number of redundant check computations is decreased. The last speaker of this section J. Slaney presented his and S. Thieacutebaux paper about relation phase transitions and peaks of hardness in the decision problems with the corresponding optimization problems.

The last section about Constraint Reasoning named Search & Heuristics ended the conference program. B.M. Smith and S.A. Grant studied behavior of searching with smallest-remaining-domain heuristic. This heuristic has been explained as an implementation of the first-fail principle. They proposed set of heuristics using probability of failing after instantiation of the given variable but their testing on random binary CSP refuted the first-fail principle as a base of smallest-remaining-domain heuristic. T. Walsh , the author of depth-bounded discrepancy search, joined together with the author of interleaved depth-first search P. Meseguer and they compared both algorithm to reduce the cost of heuristic mistakes at the top of the tree. The next speaker had been missing and so the last presentation of the conference followed. Y. Hamadi, et al. adapted intelligent backtracking algorithm to distributed constraint networks. Proposed algorithm allows simultaneous search on independent parts of the network and tries to minimize message passing and to avoid useless restorations when a dead-end is reached.

Other presentations

H. Shu dealt with solving of view update problem in relational databases by translation into a disjunction of CSPs. This is a novel approach to solve this problem obtaining sound and complete transformation. Between all CSPs solutions, a solution has to be chosen such that a number of changes in database is minimal, which was found in discussion as a possible point of inefficiency because all CSPs solutions have to be examined.

In the section Heuristic search were presented 3 papers. S. Edelkamp described the finding of shortest path algorithm for moving target which can be thought as a dynamic version of the Dijkstra algorithm. The solving of this problem is based on incremental calculation of the shortest path tree. J. Holubec reported on a new version of bidirectional heuristic search algorithm obtained by implementation of a new technique depending on the difference between estimated and optimal cost. Very similar bidirectional search algorithm had published H. Kaindel in 1997. He together with A. Scheucher presented the next paper about comparison minimaxing and product propagation for backing up heuristic values in a game trees. The second approach is not used very often but it is expected as a viable alternative. The paper explains this situation because product propagation is better only under very unrealistic (described) conditions.

S. Staab was author one of the prized papers entitled On Non-Binary Temporal Relations . He is engaged in generalization of temporal relations in Allen's calculus and in temporal CSP. This generalization includes interval relations with distances, temporal rules and other non-binary relations into temporal reasoning scheme.

A.I. Mouaddib and S. Zilberstein were the next prize winners for the paper from the area of Planning and Scheduling . This paper presented a new approach to scheduling progressive processing units, which is based on formulating the scheduling problem as a Markov decision problem and finding an optimal policy.

Conclusion

I had the young researcher report at this conference which was my first presentation to an international audience. I would like to thank in this place referees for valuable comments which help me in my current research. Also the conference gave me new ideas concerning this work but it was not easy for me to discuss my research with people working in the same fields because of large number of participants from very different areas. On the other hand, many presentations were focused on constraint reasoning research and so I have visited many interesting presentations close to my subject. In my opinion, it was a pity that the papers from Planning and Scheduling sections overlapped 2 times from 3 cases with Constraint Reasoning sections -- scheduling is a natural application domain for constraint technology.

The Brighton Research Center at the sea embankment in the center of city is a nice place for every conference. I was accommodated in halls of residence and I was pleasantly surprised by the quality of this student accommodation. I think that ECAI-98 was a successful conference, where many people from different areas of artificial intelligence could meet and discuss their work.

Hana Rudova
Faculty of Informatics,
Masaryk University
Botanicka 68a, 602 00 Brno,
Czech Republic
e-mail: hanka@fi.muni.cz