Basic Introductory Tutorial on Soft Constraints

INTRODUCTION

Constraint logic programming has evolved as a major programming paradigm for solving real-life problems. All instances of problems can be represented as relationships between the objects involved and the problem can be solved by making sure that those relationships can be satisfied.

Lot of problems in real-life cannot be expected to have a perfect solution. Most of the problems that are required to be solved are over-constrained and so most of the times don’t lead to any solution. In such situations we need to relax the restrictions so that we can at least find a solution which is as close as possible to the expected solution. This is definitely much better than not finding a solution at all. Some of the constraints can be differentiated as required while others as preferential constraints.

Constraint hierarchy forms the set of both hard and soft constraints. So in such cases what we need to do is soften the restrictions or constraints on those problems and then try to obtain a solution that is as optimal as possible. Soft constraints give more scope for relaxing the restrictions and attaching concepts such as cost and priorities to the constraints depending on the preference of the constraint being satisfied in the CSP. They are comparatively very expressive as they provide us with an idea of which constraint is preferred over the other and this is helpful in cases where we don’t find a solution. However soft constraints at the same time can be more difficult to handle.

So the concept of soft constraints is that constraints are ranked according to their importance and the form that satisfies the maximum high ranking constraints is considered the optimal.

CONSTRAINT HANDLING RULES

CHR provide simplification and propagation of user defined constraints.

Simplification in the sense that they replace constraints by constraints which are much simpler and propagation adds new constraints which are logically redundant but may cause further simplification

Soft Constraints can be described by the type of ordering or scoring that can be done. It can be classified in to two types basically

a) Assigning values to each possible tuple in a constraint

b) Assigning a value to the actual constraint itself.

MODELING OF SOFT CONSTRAINTS

Soft Constraints can be modeled in a number of ways using these two methods.
– Fuzzy CSP’s for example allow constraint tuples to have an associated preference, like for example 1 = best and 0 = worst.

– While fuzzy CSPs associate a level of preference with each tuple in each constraint, in weighted CSPs (WCSPs) tuples come with an associated cost. This allows one to model optimization problems where the goal is to minimize the total cost (time, space, number of resources, …) of the proposed solution

– According to Roman Bartak Fuzzy CSP aims at maximizing the overall level of consistency while balancing the level of all constraints. On the other hand Weighted CSP’s aim at getting the minimum cost globally, even though some constraints may be neglected and thus present a big cost.

BASIC FRAMEWORK OF SOFT CONSTRAINTS

A more general way of explaining over-constrained problems has been proposed by Stefano Bistarelli. He calls this framework as the Semiring-based Constraint Satisfaction problem.

Bistarelli’s main idea is that:

A semi-ring (that is, a domain plus two operations satisfying certain properties) is all that is needed to satisfy to describe many constraint satisfaction schemes. In fact the domain of the semiring provides the levels of consistency which can be interpreted as cost or degrees of preferences or probabilities or others and the two operations define a way to combine constraints together. More precisely we define the notion of constraint solving over any semiring. Specific choices of semiring will then give rise to different instances of the framework which may correspond to new constraint solving schemes.

A c-semiring is a quintuple (A,+, x, 0, 1) such that

• A is a set and 0, 1 ∈ A;
• + is defined over sets of elements as follows
• For all a ∈ A , Σ ({a}) = a;
• Σ (φ) = 0 and Σ(A) = 1;
• Σ ( U Ai, i ∈ I) = Σ ({Σ (Ai), i ∈ I}) for all I
• x is a binary associative and commutative operation such that 1 is its unit element and 0 is its absorbing element.

OTHER SOFT CSP FRAMEWORKS

Bistarelli showed that some of the previous constraint satisfaction approaches can be seen as instances of this theory differing only in the choice of the semiring.

Classical: Constraints in a classical CSP can be modeled with a semi-ring containing only 1 and 0 in A. Also constraint combination can be modeled with logical and the projection over some of the variables with logical or. Thus a CSP can be seen as a SCSP with the following semiring

S (CSP) = ({0, 1}, ⋁, ⋀, 0, 1)

Fuzzy CSP: Fuzzy CSP’s allow for associating a preference level with each tuple of values. This level of preference lies between 0 and 1. The solution of a fuzzy CSP is defined as a set of tuples of values for all the variables which have a maximal value. Fuzzy CSP’s can be modeled in the SCSP framework by choosing the following semiring.

S (FCSP) = ({x/x ∈ [0, 1]}, max, min, 0, 1)

Probablistic CSP: In Probabilistic CSP’s each constraint c has an associated probability p(c). c has probability p means that the situation corresponding to c has probability p of occurring in the real-life problem. The semi-ring corresponding to the probabilistic CSP is as follows.

S (prob) = ({x/x ∈ [0, 1]}, max, X, 0,1)

Weighted CSP: While Fuzzy CSPs’ come with preferences, Constraints are associated with costs in weighted CSP’s. The solution to a problem in such models is the one with minimum cost. The associated semiring for a weighted CSP is

S (WSCP) = (R*, min, +, ∞, 0)

APPLICATIONS OF SOFT CONSTRAINTS

• TITLE: DYNAMAN: A recursive model of Human Motion
• A hard constraint also known as kinematic constraint is a skeletal joint. These hard constraints are satisfied by choosing a state vector that describes only the degrees of freedom to the left of the system.
• However apart from the hard constraints we also need to collect data about image observation and integrate it into the evolution of the dynamic model.
• So this observation data can be easily modeled as soft constraints because of their probabilistic nature. Soft constraints also have the added advantage of being used to model the external influences on the dynamic system such as gravity.
• The model predictions also stabilize tracking by providing constraints that help the tracking algorithm reject distractions in the environment
AUTHORS:
Christopher R.Wren (cwren@media.mit.edu)
Alex P.Pentland (sandy@media.mit.edu)
PLACE:
MIT Media Laboratory;
20 Ames Street; Cambridge
MA 02139 USA
PUBLICATION:
Appeared in the journal of Image and Vision Computing special issue on Face and Gesture Recognition.
• TITLE: MADSUM: is a system for providing tailored responses and which acts as a decision support
• His is a system that supports a user in making a buy / don’t- buy decision in a financial investment domain.
• Hard constraints have been built in such a way that they are the values that an attribute must not exceed in a response and are used to parse the search space before utility is calculated. Soft constraints are something that the user would prefer not be exceeded in constructing a response.
• Examples of soft constraints that were set were the length of the response returned by the system, cost and processing time.
• Three different responses that were derived from setting three different soft constraints were documented. These examples illustrate the decision-support systems ability to utilize soft constraints and model the responses accordingly.
AUTHORS:
Terrence Harvey (harvey@cis.udel.edu)
Keith Decker (decker@cis.udel.edu)
Sandra Carberry (carberry@cis.udel.edu)
PLACE:
University of Delaware
Computer and Information Sciences
Newark, Delaware – 19716.
PUBLICATION:
DRAFT: Multi-Agent Decision Support via User-Modeling, AAMAS’ 05, July 25-29, 2005, Utrecht, Netherlands
• TITLE: Constraint-based vehicle assembly Line sequencing
• The problem is to determine the order in which a given list of vehicles should be produced subject to a set of constraints so that it in turn guarantees cost of production and quality of the vehicles produced.
• The soft constraints that were designed in this system could be violated at a cost and each soft constraint was associated with a penalty value that is incurred every time it is violated.
• The soft constraints are Run-length and Change-over.
• The quality of the solution is measured by the total penalty values that are incurred by violations of soft constraints. The lower the total penalty values, the higher the quality of the solution.
AUTHORS:
Michael E.Bergen (bergen@cs.ualberta.ca)
Peter Van Beek (vanbeek@cs.ualberta.ca)
Tom Carchrae (carchrae@tigrsoft.com)
PLACE:
Department of Computing Science
University of Alberta
Edmonton, Alberta, Canada – T6G 2H1
PUBLICATION:
Lecture Notes in Computer Science; Vol. 2056 Proceedings of the 14th Biennial Conference of the Canadian Society on Computational Studies of Intelligence: Advances in Artificial Intelligence, 2001
• TITLE: NETWORK PROBLEM
• A network problem can be modeled as a Soft Constraint Satisfaction Problem (SCSP) very conveniently and the problem is that there are a set of processes running on distinct locations and sharing some variables over which they need to be synchronized.
• So the variables, domains and constraints can be modeled as follows:
• Variables : each variable models a shared variable
• Domains: domain of each variable is the set of all possible actions including the idle ones.
• Constraints: each constraint models a process and connects the variables according to the shared variables of that process
• Several soft constraint solvers for each node have been proposed to be used so that each will be in charge of receiving the necessary information from other agents and using it to achieve the synchronization of the processes in its location.
AUTHORS:
Stefano Bistarelli (stefano.bistarelli@iit.car.it)
Simon N.Foley ( s.foley@cs.ucc.ie)
Barry O.Sullivan (b.osullivan@cs.ucc.ie)
• CONSONA: Constraint Networks for the Synthesis of Networked applications
• · The main goal of this project is to see how application-independent Coordination Services, Time-bounded synthesis and Service Composition and Adaptation come together in a non-trivial example application.
• In this project both services and applications are modeled as sets of soft constraints that can be maintained at run-time.
• The reason that has been given for using soft constraints is that constraint optimization is far more feasible and quality improves with time available.
• Also it is more adaptive as soft constraints can model resource aggregation and dynamic selection of task-execution strategies and also is robust because they are particularly suited for obtaining graceful degradation in case of physical malfunction or task overload.
• Also modeling requirements as soft-constraints is better suited to real-time distributed systems whereas hard constraints lead to intractability.
• The status of the project report is that the modeling using soft constraints has already been achieved.
AUTHORS:
Lambert Meertens
Cordell Green
Asuman Sunbul
Stephen Fitzpatrick
PLACE:
Kestrel Institute
Palo Alto, California
PUBLICATION:
Work on the project is still in progress.