Michel Rueher

AAAI Conference 2017 Conference Paper

What’s Hot in Constraint Programming

• Laurent Michel
• Michel Rueher

The CP conference is the annual international conference on constraint programming. It is concerned with all aspects of computing with constraints, including theory, algorithms, environments, languages, models, systems, and applications such as decision-making, resource allocation, scheduling, configuration, and planning. The CP community is very keen to ensure it remains open to interdisciplinary research at the intersection between constraint programming and related fields. Hence, in addition to the usual technical and application tracks, the CP 2016 conference featured thematic tracks: Computational Sustainability, CP and Biology, Preferences, Social Choice and Optimization, and Testing and Verification. In this overview, we highlight several remarkable papers that have been selected by the senior program committee and papers with the most innovative methods and techniques, and a very high potential for applications (in our opinion).

ICRA Conference 2009 Conference Paper

Time-minimal path planning in dynamic current fields

• Michaël Soulignac
• Patrick Taillibert
• Michel Rueher

Numerous approaches have been proposed for path planning in dynamic current fields, for a fixed departure time. However, in many applications, the departure time is not necessarily known in advance, but can vary in a time window. In this context, the choice of a good departure time is a critical issue. That is why we introduce in this paper a new approach, called symbolic wavefront expansion, determining both the path and the departure time minimizing the travel time of the vehicle. The key idea of this approach is to propagate and compose functions instead of numerical values, with appropriate operators.

ICRA Conference 2008 Conference Paper

Adapting the wavefront expansion in presence of strong currents

• Michaël Soulignac
• Patrick Taillibert
• Michel Rueher

The wavefront expansion is commonly used for path planning tasks and appreciated for its efficiency. However, the existing extensions able to handle currents are subject to incorrectness and incompleteness issues when these currents become strong. That is, they may return physically infeasible paths or no path at all, even if a feasible path exists. This behavior endangers the robot, especially in a dynamic replanning context. That is why we propose a new extension called sliding wavefront expansion. This algorithm, combining an appropriate cost function and continuous optimization techniques, guarantees the existence of a path with an arbitrary precision.

IJCAI Conference 1999 Conference Paper

Extending consistent domains of numeric CSP

• Helene Collavizza
• Francois Delobel
• Michel Rueher

LOPSTR Conference 1994 Conference Paper

Propagation of Inter-argument Dependencies in "Tuple-distributive" Type Inference Systems

• Christine Solnon
• Michel Rueher

Abstract Many type inference systems for Prolog programs are based on the tuple-distributive closure abstraction which ignores inter-argument dependencies. Thus, dependencies specified by head-only shared variables cannot be handled, and the inferred types are often very inaccurate. In this paper, we define an unfolding process which propagates such inter-argument dependencies: each call to a predicate that contains head-only shared variables is replaced by its definition. Hence, dependencies are actually propagated and the accuracy of the inferred types is improved. This unfolding process is repeated until a fix-point is reached in the computation of the type system. Termination is ensured by an abstraction function which limits the depth of recursive structures.

LPAR Conference 1993 Conference Paper

Extracting Inheritance Hierarchies from Prolog Programs: A System Based on the Inference of Type Relations

• Christine Solnon
• Michel Rueher

Abstract We propose in this paper a type inference system for extracting inheritance hierarchies from Prolog programs. The inferred types define a superset of the denotation of the program, and a subset of the least fixed point of the tuple-distributive closure of the immediate consequence operator T P (i. e. , 1fp( α (T P )). The types are described by means of their relationships with other types of the program rather than by their instances. Thus, we infer a collection of not resolved formulas that describe set relationships between the terms appearing in the program. We have nevertheless defined an interpretation function from the type relations into the Herbrand universe that allows us to actually compute the set of ground terms associated with each type. The inferred type relations are used for defining two inheritance hierarchies. The first one is obtained through a formal comparison of the type relations, and is independent of the program's data, whereas the second one is obtained through the comparison of the interpretations of the types and is directly dependent of the program's data. These two hierarchies provide a scheme of the program that enables a better understanding of the underlying structure. Their comparison may outline some errors or incompleteness of the program.

LOPSTR Conference 1992 Conference Paper

Using a Prolog Prototype for Designing an Object Oriented Scheme

• Christine Solnon
• Michel Rueher

Abstract The purpose of this paper is to define a reverse engineering technique for recovering structural design information through the analysis of a Prolog prototype. Prolog is widely used for making prototypes due to its high level of abstraction, and object oriented programming has emerged as a successful paradigm for software development. However, object oriented modelling is difficult to achieve. Thus, we propose to extract an object oriented scheme from the Prolog prototype. We show that the identification of the inclusion polymorphism expressed by Prolog clauses allows us to define an inheritance hierarchy. In the first section, we define a polymorphic denotational type system for Prolog, and we show that a Prolog program expresses relationships between types which allow us to capture inclusion polymorphism. In the second section, we present an algorithm that infers relationships between types expressed in a Prolog program. These relationships are used to define an object oriented scheme, where the inheritance hierarchy only depends on the semantic relations specified by the clauses of the program. Finally, we compare our approach with some related works, and we show the advantage of our system for well capturing inheritance relations.