CONTROL & DECISION Research Group

	DCSD
	Control & Decision Group

	PLANET
	Planet node

Keywords : Decision-making, Combinatorial optimization, Constraint satisfaction, Constrained optimization, Constraint programming, Operations research, Artificial intelligence.

Global research objective

This research aims at representing and solving the decision-making or computer-aided decision-making problems, that appear in areas such as action planning, task scheduling, resource management, system design, failure diagnosis, and situation assessment.

Among the most recently studied problems, we can cite :

• the mission management for Earth observation satellites, like Spot, Helios or 3S [ABB+95,BVA+96,BLV99c];
• the sharing of satellite resources between competitive entities [LVB98,BLV99a,BLVN99,BLV99b,LVB99];
• the frequency assignment to radio links [Pro95,CdGL+99];
• the computer-aided preliminary aircraft design [Mul98,Mul99,Ben99];
• the high-level scene recognition by a robot [Mon96,Lem96].

For solving these problems, we use the most recent combinatorial optimization techniques, built on the basic notion of constraint: constraint satisfaction, constrained optimization, constraint programming.

We are interested in the definition of formalisms that allow us to represent problems as accurately as possible, as well as in the design, implementation, experiment, and comparison of associated efficient solving methods that allow us to deal with large instances.

Our work is organized along several directions :

• maintenance of our knowledge about academic research and commercial tools;
• reuse of these works and use of these tools for specific applications;
• development of new methods to deal with challenging applications;
• comparison on these applications of the methods and tools that have been developed, either within, or outside the research group;
• basic research, that allows us to anticipate future needs and thus to answer them quickly and efficiently.

Constraint-based representation and solving

The Constraint Satisfaction Problem (CSP) framework is a natural generic way of representing the above cited decision-making problems : variables allow us to represent the decisions to make; value domains allow us to represent the choices that are associated with each decision; constraints between variables allow us to represent the necessary or desirable relations between decisions.

However, the classical CSP framework allows us to represent only satisfaction problems, when experience shows us that most of the real life problems are both satisfaction and optimization problems with hard constraints, which express imperative requirements and thus have to be absolutely satisfied, and soft constraints, which express preferences and thus have to be satisfied as much as possible. This has been the motivation for the extension from the CSP to the VCSP (Valued Constraint Satisfaction Problem) framework, in which valuations are associated with constraints and assignments [Sch92,SFV95,BFM+96,SFV97,BMR+99]. This framework is currently the basis for most of our developments.

The complete exact methods, which are based on a search tree and used in the classical CSP framework, have been extended to the valued framework, by changing Backtrack algorithms into Branch and Bound algorithms [SFV95,SFV97]. But the resulting optimization problem is far more difficult to solve than the original satisfaction problem [VdG97] and sophisticated bound computing methods are necessary for applying these algorithms to real life problems of medium size [VLS96,Ben97,LMSV98].

Incomplete, inexact, or approximate methods, which are based on a local, heuristic, and/or stochastic search, have been widely used [GV92,Ghe93,CVMB96,Cab96]. The cooperation between complete and incomplete methods is currently a promising research direction [CVMB96,MV96,Lob96,LL97,LM99].

It is well known that CSP and VCSP problems are both NP-hard and thus that their worst-case complexity grows exponentially with the size of the instances to solve. To face this situation, we developed research along two directions: on the one hand, the estimation of the complete solving time of a given instance by a given algorithm, via a sampling of the search tree [LL98a,LL98b]; on the other hand, an anytime bounding of the optimum of a given instance, via an upper bound provided by an incomplete method and a lower bound provided by the complete solving of simplifications of this instance [dGV97b,dGV97a,dGVS97,dG98,CdGV98].

The estimation of the complete solving time of a given instance by a given algorithm can be also used for selecting among a set of candidate algorithms the one that is likely to be the most efficient. A method, based on this principle, has been developed and successfully experimented [LL98c].

The fact that many real life problems are dynamic (possible changes in the instance to solve due to the user, the environment, or other agents in a distributed system) led us to design methods that, when a change occurs, can find quickly a solution for the new instance (efficiency criterion) that is as close as possible to the solution found for the previous instance (stability criterion). A large number of methods, based on solution and/or reasoning reuse, have been developed and experimented [VS94b,SV93,SV94a,SV94b,VS94a,VS95]. They have been designed in the classical CSP framework and then extended to the valued framework [DV96,Dag97].

Most of the algorithms that are developed in the CSP framework aim at producing one solution. However, producing, either a set of solutions, or all the solutions of a CSP, is interesting in many applications, especially in dynamic, distributed, and computer-aided decision-making contexts. The representation and the computation of sets of solutions, using sub-domain cartesian products, have been studied [Les94,Les95].

Many real life problems are distributed : local problems, which are not entirely independent, are solved by interacting local solvers. Assuming a common global objective, a realistic distributed method has been proposed [LV97a]. The impact of competitive local objectives has been studied in the particular context of the sharing of satellite resources (CNES study [BLV99a,LVB99]).

The fact that the currently available algorithms and tools are black boxes, with the input being an instance and the output a solution of this instance, is often criticized by the users, who would prefer a more interactive solving process, including interleaved user and software decisions, production and visualization of the consequences of the current decisions, ability to change the instance to be solved and to cancel previous decisions, explanations either about value removals, or about inconsistency. All these needs have been studied in [MV98,Mar98,VL99].

A generic software library , including the most efficient algorithms, has been developed under CNES contract. It is dedicated to the VCSP, written in Common Lisp, available via the Web, and regularly improved thanks to the developments that are performed within the research group.

Research directions and results

Generic studies

Valued CSP

[Sch92,SFV95,BFM+96,SFV97,VdG97,BMR+99]

Complete methods

[SFV95,SFV97,VLS96,Ben97,LMSV98]

Incomplete methods

[GV92,Ghe93,CVMB96,Cab96]

Hybrid methods, Cooperation

[CVMB96,MV96,Lob96,LL97,LM99]

Complexity estimation

[LL98a,LL98b,LL98c]

Anytime optimum bounding

[dGV97b,dGV97a,dGVS97,dG98,CdGV98]

Dynamic CSP

[VS94b,SV93,SV94a,SV94b,VS94a,VS95]

Solution sets

[Les94,Les95]

Distributed solving

[GV92,Ghe93,LV97a]

Interactive solving

[MV98,Mar98]

Explanations

[VL99]

Learning

[SV93,SV94a,SV94b,VS94a,VS95,DV96,Dag97]

Local consistency enforcing

[SRGV96,MV98,Mar98,VMB99]

Surveys

[VB95,Ver96,Ver97]

Tool assessments

[Mas96,LV97b]

Software library

(see Library )

Applications

Earth observation satellite management

[ABB+95,BVA+96,BLV99c]
(see Spot5 problems )

Dealing with uncertainty when managing earth observation satellites

[VBMEB99b,VBMEB99a]

Sharing the use of satellite resources between competitive entities

[LVB98,BLV99a,BLVN99,BLV99b,LVB99]

Frequency assignment

[Pro95,CdGL+99]
(see CELAR problems )

Aircraft design

[Mul98,Mul99,Ben99]

Scene recognition

[Mon96,Lem96]

Assembly line balancing

[Ben96]

Factory localization

[BBRS96]

Timetabling

[Aba96]

Research group members

Research engineers

Eric Bensana
Michel Lemaître
Gérard Verfaillie .

PhD students

Lionel Lobjois
Taufiq Mulyanto

Students

Nelly Lecubin

Références

Aba96

J.C. Abart.
Habillage d'horaires dans un service commercial par satisfaction de contraintes.
Technical Report Rapport de DESS Intelligence Artificielle, Université Paris VI, 1996.

ABB+95

J.C. Agnèse, N. Bataille, E. Bensana, D. Blumstein, and G. Verfaillie.
Exact and Approximate Methods for the Daily Management of an Earth Observation Satellite .
In Proc. of the 5th ESA Workshop on Artificial Intelligence and Knowledge Based Systems for Space, Noordwijk, The Netherlands, 1995.

BBRS96

G. Bel, E. Bensana, K. Rota, and B. Sarrochi.
Strategic Decision Making in Production Planning with Genetic Algorithms .
In Proc. of CIMAT-96, Grenoble, France, 1996.

Ben96

E. Bensana.
Constraint Logic Programming and Car Assembly Line Balancing .
In Proc. of the ICIMS-NOE Advanced Summer Institute, Toulouse, France, 1996.

Ben97

E. Bensana.
Cadre satisfaction de contraintes valués et programmation linéaire.
Technical Report 1/7600.53/DERA, CERT, 1997.

Ben99

E. Bensana.
Etudes conceptuelles d'avions non pilotés: apports de la programmation par contraintes sur les intervalles .
In Actes du Deuxième Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF-99), page 181, Autrans, France, 1999.

BFM+96

S. Bistarelli, H. Fargier, U. Montanari, F. Rossi, T. Schiex, and G. Verfaillie.
Semiring-based CSPs and Valued CSPs: Basic Properties and Comparison .
In M. Jampel, E. Freuder, and M. Maher, editors, Over-Constrained Systems (LNCS 1106, Selected papers from the Workshop on Over-Constrained Systems at CP-95, reprints and background papers), pages 111-150. Springer, 1996.

BLV99a

N. Bataille, M. Lemaître, and G. Verfaillie.
Partage équitable et efficace de ressources satellitaires .
In Actes du Deuxième Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF-99), page 179, Autrans, France, 1999.

BLV99b

N. Bataille, M. Lemaître, and G. Verfaillie.
Efficiency and Fairness when Sharing the Use of a Satellite.
In Proc. of the 5th International Symposium on Artificial Intelligence, Robotics, and Automation for Space (i-SAIRAS-99), pages 465-470, Noordwijk, The Netherlands, 1999.

BLV99c

E. Bensana, M. Lemaître, and G. Verfaillie.
Earth Observation Satellite Management .
Constraints : An international Journal, 4(3):293-299, 1999.

BLVN99

E. Bensana, M. Lemaître, G. Verfaillie, and N.Bataille.
Sharing the Use of a Satellite under Quota Constraints: an Overview of Methods .
In Proc. of the 2nd International Symposium on Spacecraft Ground Control and Data Systems (SCDII), Foz do Iguaçu, Brazil, 1999.

BMR+99

S. Bistarelli, U. Montanari, F. Rossi, T. Schiex, G. Verfaillie, and H. Fargier.
Semiring-Based CSPs and Valued CSPs: Frameworks, Properties and Comparison .
Constraints : An international Journal, 4(3):199-240, 1999.

BVA+96

E. Bensana, G. Verfaillie, J.C. Agnèse, N. Bataille, and D. Blumstein.
Exact and Approximate Methods for the Daily Management of an Earth Observation Satellite .
In Proc. of the 4th International Symposium on Space Mission Operations and Ground Data Systems (SpaceOps-96), Münich, Germany, 1996.

Cab96

B. Cabon.
Problèmes d'optimisation combinatoire : Evaluation des méthodes de la physique statistique.
Thèse de doctorat, ENSAE, Toulouse, France, 1996.

CdGL+99

B. Cabon, S. de Givry, L. Lobjois, T. Schiex, and J.P. Warners.
Radio Link Frequency Assignment .
Constraints : An international Journal, 4(1):79-89, 1999.

CdGV98

B. Cabon, S. de Givry, and G. Verfaillie.
Anytime Lower Bounds for Constraint Violation Minimization Problems .
In Proc. of the 4th International Conference on Principles and Practice of Constraint Programming (CP-98), pages 117-131, Pisa, Italia, 1998.

CVMB96

B. Cabon, G. Verfaillie, D. Martinez, and P. Bourret.
Using Mean Field Methods for Boosting Backtrack Search in Constraint Satisfaction Problems .
In Proc. of the 12th European Conference on Artificial Intelligence (ECAI-96), pages 165-169, Budapest, Hungary, 1996.

Dag97

P. Dago.
Extension d'algorithmes dans le cadre satisfaction de contraintes valué : application a l'ordonnancement de systèmes satellitaires.
Thèse de doctorat, ENSAE, Toulouse, France, 1997.

dG98

S. de Givry.
Algorithmes d'optimisation sous contraintes étudiés dans un cadre temps réel.
Thèse de doctorat, ENSAE, Toulouse, France, 1998.

dGV97a

S. de Givry and G. Verfaillie.
Optimum Anytime Bounding for Constraint Optimization Problems .
In Proc. of the AAAI-97 Workshop on "Building Resource-Bounded Reasoning Systems", Providence, RI, USA, 1997.

dGV97b

S. de Givry and G. Verfaillie.
Problèmes d'optimisation sous contraintes: Encadrement ANYTIME de l'optimum .
In Actes des 3ièmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets (JNPC-97), pages 33-39, Rennes, France, 1997.

dGVS97

S. de Givry, G. Verfaillie, and T. Schiex.
Bounding the Optimum of Constraint Optimization Problems .
In Proc. of the 3rd International Conference on Principles and Practice of Constraint Programming (CP-97), Schloss Hagenberg, Austria, 1997.

DV96

P. Dago and G. Verfaillie.
Nogood Recording for Valued Constraint Satisfaction Problems .
In Proc. of the 8th IEEE International Conference on Tools with Artificial Intelligence (ICTAI-96), pages 132-139, Toulouse, France, 1996.

Ghe93

K. Ghedira.
MASC : une Approche Multi-Agent des Problèmes de Satisfaction de Contraintes.
Thèse de doctorat, ENSAE, Toulouse, France, 1993.

GV92

K. Ghedira and G. Verfaillie.
A Multi-Agent Model for the Resource Allocation Problem: a Reactive Approach.
In Proc. of the 10th European Conference on Artificial Intelligence (ECAI-92), pages 252-254, Vienna, Austria, 1992.

Lem96

J. Lemaire.
Utilisation de descriptions de haut niveau et gestion de l'incertitude dans un système de reconnaissance de scènes.
Thèse de doctorat, ENSAE, Toulouse, France, 1996.

Les94

D. Lesaint.
Maximal Sets of Solutions for Constraint Satisfaction Problems .
In Proc. of the 11th European Conference on Artificial Intelligence (ECAI-94), pages 110,114, Amsterdam, The Netherlands, 1994.

Les95

D. Lesaint.
Calcul d'ensembles de solutions pour problèmes de satisfaction de contraintes.
Thèse de doctorat, ENSAE, Toulouse, France, 1995.

LL97

L. Lobjois and M. Lemaître.
Coopération entre méthodes complètes et incomplètes pour la résolution de (V)CSP: une tentative d'inventaire .
In Actes des 3ièmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets (JNPC-97), pages 67-73, Rennes, France, 1997.

LL98a

L. Lobjois and M. Lemaître.
Adaptation de l'estimateur de Knuth aux problèmes d'optimisation combinatoire .
In Actes des 4ièmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets (JNPC-98), pages 101-108, Nantes, France, 1998.

LL98b

L. Lobjois and M. Lemaître.
Adaptation de l'estimateur de Knuth aux problèmes d'optimisation combinatoire .
In Actes des 4ièmes Rencontres des Jeunes Chercheurs en Intelligence Artificielle (RJCIA-98), Toulouse, France, 1998.

LL98c

L. Lobjois and M. Lemaître.
Branch and Bound Algorithm Selection by Performance Prediction .
In Proc. of the 15th National Conference on Artificial Intelligence (AAAI-98), pages 353-358, Madison, WI, USA, 1998.

LM99

L. Lobjois and M.Lemaître.
LNS/VSP: une méthode de recherche locale pour la résolution de VCSP en contexte interruptible .
In Actes des 5ièmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets (JNPC-99), pages 163-170, Lyon, France, 1999.

LMSV98

J. Larrosa, P. Meseguer, T. Schiex, and G. Verfaillie.
Reversible DAC and Other Improvements for Solving Max-CSP .
In Proc. of the 15th National Conference on Artificial Intelligence (AAAI-98), pages 347-352, Madison, WI, USA, 1998.

Lob96

L. Lobjois.
Coopération entre méthodes exactes et inexactes pour la résolution de problèmes de satisfaction de contraintes valuées.
Technical Report Mémoire de DEA, ENSAE, Toulouse, France, 1996.

LV97a

M. Lemaître and G. Verfaillie.
An Incomplete Method for Solving Distributed Valued Constraint Satisfaction Problems .
In Proc. of the AAAI-97 Workshop on "Constraints and Agents", Providence, RI, USA, 1997.

LV97b

M. Lemaître and G. Verfaillie.
Daily management of an earth observation satellite : comparison of ILOG Solver with dedicated algorithms for Valued Constraint Satisfaction Problems .
In Proc. of the Third ILOG International Users Meeting, Paris, France, 1997.

LVB98

M. Lemaître, G. Verfaillie, and N. Bataille.
Sharing the use of a satellite: an overview of methods .
In Proc. of the 5th International Symposium on Space Mission Operations and Ground Data Systems (SpaceOps-98), Tokyo, Japan, 1998.

LVB99

M. Lemaître, G. Verfaillie, and N. Bataille.
Exploiting a Common Property Resource under a Fairness Constraint: a Case Study .
In Proc. of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99), pages 206-211, Stockholm, Sweden, 1999.

Mar98

D. Martinez.
Résolution Interactive de Problèmes de Satisfaction de Contraintes.
Thèse de doctorat, ENSAE, Toulouse, France, 1998.

Mas96

M. El Masbahi.
Optimisation de la programmation journalière des prises de vue du satellite SPOT5 avec Ilog Solver.
Technical Report Projet de fin d'études, INSA, Toulouse, France, 1996.

Mon96

C. Monestié.
Mise en uvre de techniques CSP dans un système d'interprétation de scènes.
Technical Report Projet de fin d'études, IUP, Systèmes Intelligents, Toulouse, France, 1996.

Mul98

T. Mulyanto.
Utilisation d'Outil de Programmation par Contraintes pour l'Étape Conceptuelle de la Conception d'Avions.
Technical Report Rapport de Stage, Mastère Systèmes Informatiques, ENSAE, Toulouse, France, 1998.

Mul99

T. Mulyanto.
Utilisation de Techniques de Propagation de Contraintes pour la Conception Préliminaire d'Avions dans un Contexte Distribué.
Technical Report Rapport de DEA, ENSAE, Toulouse, France, 1999.

MV96

D. Martinez and G. Verfaillie.
Echange de Nogoods pour la Résolution Coopérative de Problèmes de Satisfaction de Contraintes .
In Actes de la 2ième Conférence Nationale sur la Résolution Pratique de Problèmes NP-Complets (CNPC-96), pages 261-274, Dijon, France, 1996.

MV98

D. Martinez and G. Verfaillie.
Une calculette à contraintes pour la résolution interactive de CSP .
In Actes des 4ièmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets (JNPC-98), pages 13-20, Nantes, France, 1998.

Pro95

Euclid CALMA Project.
Final report.
Technical report, CERT, 1995.

Sch92

T. Schiex.
Possibilistic Constraint Satisfaction Problems or ``How to handle soft constraints ?'' .
In Proc. of the 8th International Conference on Uncertainty in Artificial Intelligence (UAI-92), Stanford, CA, USA, 1992.

SFV95

T. Schiex, H. Fargier, and G. Verfaillie.
Valued Constraint Satisfaction Problems : Hard and Easy Problems .
In Proc. of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), pages 631-637, Montréal, Canada, 1995.

SFV97

T. Schiex, H. Fargier, and G. Verfaillie.
Problèmes de satisfaction de contraintes valués .
Revue d'Intelligence Artificielle, 11(3):339-373, 1997.

SRGV96

T. Schiex, JC. Régin, C. Gaspin, and G. Verfaillie.
Lazy Arc Consistency .
In Proc. of the 13th National Conference on Artificial Intelligence (AAAI-96), pages 216-221, Portland, OR, USA, 1996.

SV93

T. Schiex and G. Verfaillie.
Nogood Recording for Static and Dynamic CSP.
In Proc. of the 5th IEEE International Conference on Tools with Artificial Intelligence (ICTAI-93), pages 48-55, Boston, MA, USA, 1993.

SV94a

T. Schiex and G. Verfaillie.
Nogood Recording for Static and Dynamic Constraint Satisfaction Problems .
International Journal of Artificial Intelligence Tools, 3(2):187-207, 1994.

SV94b

T. Schiex and G. Verfaillie.
Stubbornness: a Possible Enhancement for Backjumping and Nogood Recording .
In Proc. of the 11th European Conference on Artificial Intelligence (ECAI-94), pages 165-169, Amsterdam, The Netherlands, 1994.

VB95

G. Verfaillie and E. Bensana.
Optimisation Combinatoire: quelques leçons de la théorie et de l'expérience .
In Actes des Ateliers CNES Techniques et Technologies des Segments Sols Informatiques, Toulouse, France, 1995.

VBMEB99a

G. Verfaillie, E. Bensana, C. Michelon-Edery, and N. Bataille.
Dealing with Uncertainty when Managing an Earth Observation Satellite.
In Proc. of the 5th International Symposium on Artificial Intelligence, Robotics, and Automation for Space (i-SAIRAS-99), pages 205-207, Noordwijk, The Netherlands, 1999.

VBMEB99b

G. Verfaillie, E. Bensana, C. Michelon-Edery, and N. Bataille.
Dealing with Uncertainty when Managing an Earth Observation Satellite .
In Proc. of the 2nd International Symposium on Spacecraft Ground Control and Data Systems (SCDII), Foz do Iguaçu, Brazil, 1999.

VdG97

G. Verfaillie and S. de Givry.
Algorithmic problems and solutions in the Valued Constraint Satisfaction Problem framework .
In Proc. of the EUFIT-97 session on ``Valued Constraint Satisfaction'', Aachen, Germany, 1997.

Ver96

G. Verfaillie.
Optimisation Combinatoire et Temps Contraint: quelques leçons de la théorie et de l'expérience .
In Actes du Colloque INFAUTOM96, Gestion Optimale en Temps Réel des Grands Moyens de Transport, ENSAE, Toulouse, France, 1996.

Ver97

G. Verfaillie.
Texte de synthèse des travaux .
Thèse d'Habilitation à Diriger les Recherches, Université Paul Sabatier, Toulouse, France, 1997.
Présentation associée .

VL99

G. Verfaillie and L. Lobjois.
Problèmes incohérents: expliquer l'incohérence, restaurer la cohérence .
In Actes des 5ièmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets (JNPC-99), pages 111-120, Lyon, France, 1999.

VLS96

G. Verfaillie, M. Lemaître, and T. Schiex.
Russian Doll Search for Solving Constraint Optimization Problems .
In Proc. of the 13th National Conference on Artificial Intelligence (AAAI-96), pages 181-187, Portland, OR, USA, 1996.

VMB99

G. Verfaillie, D. Martinez, and C. Bessière.
A Generic Customizable Framework for Inverse Local Consistency .
In Proc. of the 16th National Conference on Artificial Intelligence (AAAI-99), pages 169-174, Orlando, FL, USA, 1999.

VS94a

G. Verfaillie and T. Schiex.
Dynamic Backtracking for Dynamic Constraint Satisfaction Problems .
In Proc. of the ECAI-94 Workshop on "Constraint Satisfaction Issues Raised by Practical Applications", Amsterdam, The Netherlands, 1994.

VS94b

G. Verfaillie and T. Schiex.
Solution Reuse in Dynamic Constraint Satisfaction Problems .
In Proc. of the 12th National Conference on Artificial Intelligence (AAAI-94), pages 307-312, Seattle, WA, USA, 1994.

VS95

G. Verfaillie and T. Schiex.
Maintien de solution dans les problèmes dynamiques de satisfaction de contraintes: bilan de quelques approches .
Revue d'Intelligence Artificielle, 9(3):269-309, 1995.

ONERA-CERT / DCSD / Control & Decision
2 av. Edouard Belin, BP 4025, F-31055 TOULOUSE, cedex FRANCE
Tél.: +33 (0)5 62 25 25 61   -   Fax: +33 (0)5 62 25 25 64
/dcsd/cd/

[DCSD ] [DCSD ] [Control & Decision Group] [PLANET] [Planet TCUs] copyright © ONERA 1996-99