Extending the CSP Model to Cope With Partial Information

R. Cucchiara, M. Gavanelli, E. Lamma, P. Mello, M. Milano, M. Piccardi

Abstract:

We present the Interactive Constraint Satisfaction Problem (ICSP), an extension of the widely used Constraint Satisfaction Problem (CSP) model, suitable when we have incomplete knowledge at the beginning of the computation. The knowledge about the problem is acquired during the resolution process by means of Interactive Constraints, which retrieve consistent information only when needed.   To deal with interactive constraints and information extracted during computation, the basic concept of variable domain  is extended to partially defined domain. We also present an application in visual search and the basic library to extend the popular Constraint Logic Programming (CLP) language  ECLiPSe  to cope with partially defined domains.
 

Contents

 

Introduction: the CSP model

The Constraint Satisfaction Problem (CSP) model is a widely used framework within Artificial Intelligence and Operation Research  [vHent89]. A CSP is a problem defined on a set of variables each ranging on a finite domain of objects of arbitrary type and a set of constraints limiting the possible combinations of assignments the variables can assume. A solution to a CSP is an assignment of values to variables which satisfies all the constraints. Without loss of generality, we can consider only unary and binary constraints (i.e. constraints involving one or two variables). In this case, the CSP can be represented with a graph, where each node represents a variable and each arc represents a constraint imposed between two variables.
 

Example: the map coloring problem

 
For example, let's consider the map coloring problem: we have a number N of countries in a map and we want to assign a color to each country from a given palette, such that each country has a different color with respect to all the neighboring countries.
In this problem, we can consider a variable for each country in the map. Each variable can be assigned a color, so the domains will be the range of colors.
Not every assignment is feasible, because of the constraint that imposes different color for neighboring countries. The constraint graph can be represented as a set of nodes, which represent the countries, and arcs connecting the nodes which represent the constraints between two neighboring countries.

 

The vision system

As a second example, we can consider a vision system: here we want to recognize a given shape in an image. We can model the shape to be found by means of constraints.

Suppose that we want to recognize a rectangle: we say that an object is a rectangle if it's composed of four edges (say X1, X2, X3, X4), which satisfy some geometric and topologic properties. We want X1 to touch X2, X1 to be parallel to X3, X1 not to touch X3, X2 to be perpendicular to X3, and so on. In this case, the variables of the CSP are the four edges composing the rectangle, each ranging on the set of segments in the given figure.
 

The constraints are topologic and geometric relations, such as touch, parallel, perpendicular, no_touch. So, the model of the rectangle that we want to recognize is composed of the following constraints:

touch(X1,X2), touch(X2,X3), touch(X3,X4), touch(X4,X1), no_touch(X1,X3), no_touch(X2,X4), perpendicular(X1,X2), perpendicular(X2,X3), perpendicular(X3,X4), perpendicular(X4,X1), parallel(X1,X3), parallel(X2,X4).
Some of the constraints are redundant; this helps if we use an incomplete propagation process (such as arc-consistency  [vHent89]).
 

Of course, the system needs to know where the segments are in the figure, so a segmentation step must be made in order to extract the segments from the figure. This operation can be  performed by a different system, which takes as input the image given in some binary form, finds the edges of the shapes, extracts the segments, and returns information about each segment.
The image we present is taken from  [DARPA] , a widely used benchmark for vision systems. The second picture shows the image after the edge detection phase.

For example, a system we proposed returned Prolog terms like:

segment(X1,Y1,X2,Y2,Length,Inclination)

where (X1,Y1) and (X2,Y2) are the ending points of the segment, Length is its length and Inclination is the angle formed by the segment with a line parallel to the x axis.

The architecture of a CSP based recognizing system is composed of two systems:


 Next