Gérard Verfaillie

ICAPS Conference 2014 Conference Paper

Satellite Data Download Management with Uncertainty about the Generated Volumes

• Cédric Pralet
• Gérard Verfaillie
• Adrien Maillard
• Emmanuel Hebrard
• Nicolas Jozefowiez
• Marie-José Huguet
• Thierry Desmousceaux
• Pierre Blanc-Paques

Earth observation satellites are space sensors which acquire data, compress and record it on board, and then download it to the ground. Because of the use of more and more sophisticated compression algorithms, the amount of data resulting from an acquisition is more and more unpredictable. In such conditions, planning satellite data download activities offline on the ground is more and more problematic. In this paper, we report the results of a work aiming at evaluating the positive impact of planning downloads onboard when the amount of data produced by each acquisition is known. The data download problem to be solved on board is an assignment and scheduling problem with unsharable resources, precedence constraints, time-dependent minimum durations, and a complex optimization criterion. The generic InCELL library is used to model constraints and criterion, to check non temporal constraints, to propagate temporal constraints, and to evaluate the criterion. On top of this library, greedy and local search algorithms have been designed to produce download plans with limited time and computing resources available on board.

ICAPS Conference 2014 Conference Paper

Time-Dependent Simple Temporal Networks: Properties and Algorithms

• Cédric Pralet
• Gérard Verfaillie

Simple Temporal Networks (STNs) allow minimum and maximum distance constraints between time-points to be represented. They are often used when tackling planning and scheduling problems that involve temporal aspects. This paper is a summary of the journal article "Time-dependent Simple Temporal Networks: Properties and Algorithms" published in RAIRO - Operations Research. This journal article introduces an extension of STN called Time-dependent STN (TSTN), which covers temporal constraints for which the temporal distance required between two time-points is not necessarily constant. Such constraints are useful to model time-dependent scheduling problems, in which the duration of an activity may depend on its starting time. The paper introduces the TSTN framework, its properties, resolution techniques, as well as examples of applications.

ICAPS Conference 2013 Conference Paper

Dynamic Online Planning and Scheduling Using a Static Invariant-Based Evaluation Model

• Cédric Pralet
• Gérard Verfaillie

Sequential decision-making under uncertainty often uses an approach in which a plan is built over a given horizon ahead using a deterministic model, the first decisions in this plan are applied, new information is acquired, the plan is adapted or rebuilt from scratch over a sliding horizon, and so on. This paper introduces a generic local search library that can be used in this context to quickly build and rebuild good quality plans. This library is built upon the notion of invariant used in constraint-based local search. Invariants allow temporal constraints, resource constraints, and criteria to be very quickly evaluated from a variable assignment and re-evaluated from a small change in this assignment. The paper also shows how the library can be used to reason on dynamic problem instances using a unique static problem model, without dynamic memory allocation. The approach is illustrated on a problem of data download under uncertainty about the volume of data, coming from the space domain.

ECAI Conference 2010 Conference Paper

Constraint-Based Controller Synthesis in Non-Deterministic and Partially Observable Domains

• Cédric Pralet
• Gérard Verfaillie
• Michel Lemaître
• Guillaume Infantes

Controller synthesis consists in automatically building controllers taking as inputs observation data and returning outputs guaranteeing that the controlled system satisfies some desired properties. In system specification, these properties may be safety properties specifying that some conditions must always hold. In planning, they express that the evolution of the controlled system must terminate in a goal state. In this paper, we propose a generic approach able to synthesize memoryless or finite-memory controllers for both safety-oriented and goal-oriented control problems. This approach relaxes some restrictive assumptions made by existing work on controller synthesis with non-determinism and partial observability and is shown to induce potentially significant gains. The proposed "Simulate and Branch" algorithm consists in exploring the possible evolutions of the controlled system and in adding new control elements when uncovered states are discovered. The approach developed is constraint-based in the sense that control problems are formulated using the flexibility of constraint programming languages and that our implementation uses the Gecode constraint programming library.

KER Journal 2010 Journal Article

How to model planning and scheduling problems using constraint networks on timelines

• Gérard Verfaillie
• Cédric Pralet
• Michel Lemaître

Abstract The CNT framework ( Constraint Network on Timelines ) has been designed to model discrete event dynamic systems and the properties one knows, one wants to verify, or one wants to enforce on them. In this article, after a reminder about the CNT framework, we show its modeling power and its ability to support various modeling styles, coming from the planning, scheduling, and constraint programming communities. We do that by producing and comparing various models of two mission management problems in the aerospace domain: management of a team of unmanned air vehicles and of an Earth observing satellite.

ECAI Conference 2010 Conference Paper

Knowledge Compilation Using Interval Automata and Applications to Planning

• Alexandre Niveau
• Hélène Fargier
• Cédric Pralet
• Gérard Verfaillie

Knowledge compilation [6, 5, 14, 8] consists in transforming a problem offline into a form which is tractable online. In this paper, we introduce new structures, based on the notion of interval automaton (IA), adapted to the compilation of problems involving both discrete and continuous variables, and especially of decision policies and transition tables, in the purpose of controlling autonomous systems.

ICAPS Conference 2009 Conference Paper

Forward Constraint-Based Algorithms for Anytime Planning

• Cédric Pralet
• Gérard Verfaillie

This paper presents a generic anytime forward-search constraint-based algorithm for solving planning problems expressed in the CNT framework (Constraint Network on Timelines). It is generic because it allows many kinds of search to be covered, from complete tree search to greedy search. It is anytime because some parameter settings, together with domain-specific knowledge, allow high quality plans to be produced very quickly and to be further improved. It is forward because it systematically considers the decisions to be made in a chronological order. It is finally constraint-based because it is built on top of the CNT framework which is an extension of the CSP framework able to model discrete event dynamic systems and because it is implemented on top of the Choco constraint programming tool from which it inherits all the constraint handling machinery. Experimental comparisons are made in terms of quality profile with other domain-dependent and domain-independent planners.

ICAPS Conference 2008 Conference Paper

Using Constraint Networks on Timelines to Model and Solve Planning and Scheduling Problems

• Cédric Pralet
• Gérard Verfaillie

In the last decades, there has been an increasing interest in the connection between planning and constraint programming. Several approaches were used, leading to different forms of combination between the two domains. In this paper, we present a new framework, called Constraint Network on Timelines (CNT), to model and solve planning and scheduling problems. Basically, CNTs are a kind of dynamic CSPs, enhanced with special variables called dimension variables representing the initially unknown number of steps in a valid or optimal plan. We also present an algorithm and experimental results showing that the expressiveness of CNTs allows efficient models to be developed, and can lead to significant gains on problems taken from planning competitions.

ECAI Conference 2006 Conference Paper

Decision with Uncertainties, Feasibilities, and Utilities: Towards a Unified Algebraic Framework

• Cédric Pralet
• Gérard Verfaillie
• Thomas Schiex

Several formalisms exist to express and solve decision problems. Each is designed to capture different kinds of knowledge: utilities expressing preferences, uncertainties on the environment, or feasibility constraints on the decisions, with a possible sequential aspect. Despite the fact that every framework relies on specific properties exploited by dedicated algorithms, these formalisms present interesting similarities. In this paper, we show that it is possible to capture these similarities in a generic algebraic framework for sequential decision making with uncertainties, feasibilities, and utilities. This framework subsumes several existing approaches, from constraint satisfaction problems to quantified boolean formulas, Bayesian networks or possibilistic Markov decision processes. We introduce this framework using a toy example, increasingly sophisticated by uncertainties, feasibilities and possible observations. This leads to a formal definition of the framework together with dedicated queries representing usual decision problems. Generic algorithms for solving the considered queries should allow to both factorize existing algorithmic works and allow for cross-fertilization between the subsumed formalisms.

UAI Conference 2006 Conference Paper

From Influence Diagrams to Multi-operator Cluster DAGs

• Cédric Pralet
• Thomas Schiex
• Gérard Verfaillie

There exist several architectures to solve influence diagrams using local computations, such as the Shenoy-Shafer, the HUGIN, or the Lazy Propagation architectures. They all extend usual variable elimination algorithms thanks to the use of so-called 'potentials'. In this paper, we introduce a new architecture, called the Multi-operator Cluster DAG architecture, which can produce decompositions with an improved constrained induced-width, and therefore induce potentially exponential gains. Its principle is to benefit from the composite nature of influence diagrams, instead of using uniform potentials, in order to better analyze the problem structure.

AAAI Conference 1999 Conference Paper

A Generic Customizable Framework for Inverse Local Consistency

• Gérard Verfaillie
• David Martinez
• ONERA-CERT; Christian Bessière
• LIRMM-CNRS

Local consistency enforcing is at the core of CSP (Constraint Satisfaction Problem) solving. Although arc consistency is still the most widely used level of local consistency, researchers are going on investigating more powerful levels, such as path consistency, k-consistency, (i,j)-consistency. Recently, more attention has been turned to inverse local consistency levels, such as path inverse consistency, k-inverse consistency, neighborhood inverse consistency, that do not suffer from the drawbacks of the other local consistency levels (changes in the constraint definitions and in the constraint graph, prohibitive memory requirements). In this paper, we propose a generic framework for inverse local consistency that includes most of the previously defined levels and allows a rich set of new levels to be defined. The first benefit of such a generic framework is to allow a user to define and test many different inverse local consistency levels, in accordance with the problem or even the instance he has to solve. The second benefit is to allow a generic algorithm to be defined. This algorithm, that is parameterized by the chosen inverse local consistency level, generalizes the AC7 algorithm used for arc consistency, and produces from any instance its locally consistent closure at the chosen level.

AAAI Conference 1996 Conference Paper

Russian Doll Search for Solving Constraint Optimization Problems

• Gérard Verfaillie

If the Constraint Satisfaction framework has been extended to deal with Constraint Optimization problems, it appears that optimization is far more complex than satisfaction. One of the causes of the inefficiency of complete tree search methods, like Depth First Branch and Bound, lies in the poor quality of the lower bound on the global valuation of a partial assignment, even when using Forward Checking techniques. In this paper, we introduce the Russian Doll Search algorithm which replaces one search by n successive searches on nested subproblems (n being the number of problem variables), records the results of each search and uses them later, when solving larger subproblems, in order to improve the lower bound on the global valuation of any partial assignment. On small random problems and on large real scheduling problems, this algorithm yields surprisingly good results, which greatly improve as the problems get more constrained and the bandwidth of the used variable ordering diminishes.

ECAI Conference 1996 Conference Paper

Using Mean Field Methods for Boosting Backtrack Search in Constraint Satisfaction Problems

• Bertrand Cabon
• Gérard Verfaillie
• David Martinez
• P. Bourret

ECAI Conference 1994 Conference Paper

Stubborness: A Possible Enhancement for Backjumping and Nogood Recording

• Thomas Schiex
• Gérard Verfaillie

ICAPS Conference 1990 Conference Paper

Operations research and artificial intelligence cooperation to solve scheduling problems: the OPAL and OSCAR systems

• C. Badie
• G. Bel
• E. Bensana
• Gérard Verfaillie