Constraint Propagation and Value Acquisition: Why we should do it Interactively

1 Introduction

The Constraint Satisfaction Problem (CSP) formaliza­ tion has been widely used within Artificial Intelligence and related areas. A CSP is defined on a finite set of variables each ranging on a finite domain of objects of arbitrary type and a set of constraints. A solution to a CSP is an assignment of values to variables which satis­ fies all the constraints. Propagation algorithms [4] (e.g., forward checking, look ahead) have been proposed in or­ der to reduce the search space.

A basic hypothesis for a CSP model is that variable domain values are completely specified at the beginning of the constraint propagation process. We can consider the problem solving activity as the result of the coopera­ tion of two software components (depicted in figure 1) : a generator of domain values GEN and a constraint solver C S. The classical CSP formalization leads to a sequen­ tial use of this architecture, where GEN produces all domain values and the CS module processes constrained data. The generation or the acquisition of variable do­ main values should be completed before the constraints on variables are imposed and propagated.

M.Gavanelli, M. Piccardi

Dip. Ingegneria University of Ferrara Via Saragat, 1 44100 Ferrara ITALY

However, in many applications the acquisition of do­ main values is a computational expensive process. Thus, it is not convenient to acquire all domain values, but a pipelined behaviour is preferable. Take, for example, a visual system as GEN module. The acquisition of vi­ sual features (such as segments and surfaces) as domain values for the C S is a computational expensive task. In other applications, not all values are available at the beginning of the computation. Thus, it is not possi­ ble to acquire all the domain values at the beginning of the computation. Suppose we are processing an image representing a box of possibly overlapped pieces that a robot should handle one by one. We have no informa­ tion on occluded pieces (and thus on the corresponding visual features) until the robot has picked up the emerg­ ing pieces occluding the underlying ones.

We argue that interleaving the generation/acquisition of domain values and their processing could greatly in­ crease the performances of the problem solving strategy in some cases, and can be the only way of processing in presence of unknown information. Domain values acqui­ sition can be performed on demand only when values are effectively needed or available, as previously suggested by Sergot in [11] in the Logic Programming setting.

Furthermore, in many applications the GEN module is able to focus its attention on significant domain val­ ues (i .e., domain values satisfying some properties) or even provide consistent values when guided by means of constraints which we call interactive constraints.

For this purpose, the classical CSP model should be extended in order to (i) cope with partially or fully un­ known variable domains; (ii) dynamically acquire do­ main values on demand while the constraint propaga­ tion process is in progress; (iii) drive the domain value acquisition by means of interactive constraints; (iv) in­ crementally process new information without restarting a constraint propagation process from scratch each time new information is available. The resulting framework has been called Interactive Constraint Satisfaction Prob­ lem (ICSP) model.

In this paper, we present the ICSP model and cor­ responding propagation algorithms based on the For­ ward Checking (FC) [4] and Minimal Forward Checking (MFC) [2] which we call respectively Interactive Forward Checking (IFC) and Interactive Minimal Forward Checking (IMFC). If the GEN module is able to focus on significant domain values or even to provide consis­ tent values when guided by constraints, on average the number of acquisition greatly decreases with respect to the standard case. Otherwise, we have the same number of data acquisition of the standard case.

2 The ICSP model

In this section, we first recall some CSP-related concepts. Then, we present the interactive constraint satisfaction framework. We focus on binary CSPs. A binary CSP is a tuple (V, D, C) where V is a finite set of variables X 1, ... , Xn ranging on domains of objects of arbitrary type D1, ... , Dn. We call D; = [v;,, ... , v;J the domain of X;. C is a finite set of constraints on pairs of vari­ ables in V. A constraint con variables X; and Xj, i.e., c(X;,Xj) , defines a subset of the cartesian product of variable domains D; x Dj representing sets of possible assignments of values to variables. A solution to a CSP is an assignment of values to variables which satisfies all the constraints. A constraint c on variables X;, Xj is satisfied by a pair of values v;, Vj if (v;,vj) E c.

We now extend the CSP definition in order to allow constrained variables to range on partially or completely unknown domains.

Definition 2.1 An interactive domain of a variable X; D; = [v;, , V; 2 , ··· , v;k JXIJ is a set of possible values which can be assigned to that variable. We refer to Known; as the list of values representing the known domain part [v; 1 , v; 2 , .·· , v;k], and to UnKnown; as a variable XI representing a list of not yet available values for vari­ able X;. Declaratively, the association of a domain to a variable X; :: [v;,, v; 2 , ··. , v;k JXIJ holds iff

X; = v; 1 V X; = v; 2 V ... V X; = v;k V X; :: XI Both Known; and UnKnown; can be possibly empty lists 1 . Also, for each i, the intersection of Known; and UnKnown; is empty: this follows from the fact that the interactive domain is a set.

The interactive domain of variable X; can be either completely known, e.g, D; = [3, 4, 5], or only partially known, e.g. , D; = [3, 4, 5JXIJ, where XI is a variable representing a list of values which will be eventually re­ trieved in the future if needed, or completely unknown D·-X' ' e.g., ·- ;·

1 When both are empty an inconsistency arises.

The notion of interactive domains has some similari­ ties with the concept of streams [12] widely used for com­ munication purposes in Concurrent Prolog. A stream is a communication channel which can be assigned to a term that contains a message and an additional vari­ able. From this perspective, interactive domains repre­ sent communication channels between the GEN module and the CS module. The unknown part of the domain contains a message (one retrieved value) and an addi­ tional variable for future acquisitions.

The strength of the interactive approach concerns the fact that the CS module can guide knowledge acquisition (i.e., the GEN module) by means of constraints, called interactive constraints, and incrementally process new information without restarting a constraint propagation process from scratch each time new values are available. With no loss of generality, we define binary interactive constraints .

Definition 2.2 An interactive binary constraint c on variables X; and Xj, i.e., c(X;, Xj), defines a possi­ bly partially known subset of the cartesian product of variable interactive domains D; x Dj representing sets of possible assignments of values to variables. Declar­ atively, given the domains of X; :: [v; 1 , ··· , v;n JXIJ and Xj :: [vii, .. . , Vjm JXj], the constraint c(X;, Xj) is satis­ fied iff

Definition 2.3 A binary Interactive CSP (ICSP) is a tuple (V, D, C) where V is a finite set of variables X1, ... , Xn, D is set of interactive domains D1 , ... , Dn and C is a set of interactive (binary) constraints. A so­ lution to the ICSP is an assignment of values to variables which is consistent with constraints.

3 Search strategies

In this section, we define the Interactive Forward Check­ ing and the Interactive Minimal Forward Checking pro­ cedures. With no loss of generality, both the algorithms start by considering an ICSP where all variables range on a completely unknown domain, i.e., no value is avail­ able for any variable. Thus, all variables initially range on a completely unknown domain, and are chosen in the following instantiation order: X 1, ... , X; , ... , Xn. The current variable X; is the variable to be instantiated and D; is its current interactive domain. We refer to future connected variables to X; as the ordered subset of

2 With an abuse of notation, we impose the constraint c on variables representing a list . For the sake of readability, we have omitted the definition of a new variable Xnew :: XI on which constraints should be imposed.

procedure IFC(Var, Domain); begin for all Xi E Var do begin 1-label(i); I -propagation-acquisition ( i, fu t ure..connected.vars); end;

end;

procedure 1-label(i); begin known(i] := known(Domain(i]); % known part of Var(i] unknown(i] := unknown(Domain(i]); % unknown part of Var(i] if unknown(i] # [] % Var(i] domain is fully unknown then begin collect all unary constraints C on Var(i]; impose C on unknown(i]; acquire__one.val(i,C); end; if known(i] = [] then fail; end; else begin % Now known(i] is surely defined select a value Vi from known( i]; assign Var(i] =Vi; end;

Xi+l, ... , X n containing those variables linked to Xi by means of a constraint.

3.1 Interactive Forward Checking

In standard CSPs, the forward checking strategy [4] in­ terleaves a labeling step which instantiates variable xi to a value v in its domain with a constraint propagation process. This second step removes from the domains of future connected variables values which are not consis­ tent with v.

The interactive version of the FC (figure 2) is divided in two steps as well. A labeling move is used to find an instantiation for the current variable, and a propa­ gation/acquisition step is used to remove (already ac­ quired) values inconsistent with the current labeling, or to acquire new consistent values.

The labeling step, called I -label (figure 3), takes as input the index of the variable xi to be instantiated and either selects a value v in its known domain part if it exists, or retrieves one value v for Xi consistent with the unary constraints on xi. !-label then assigns xi= v.

The propagation/acquisition step (figure 4) takes as input the index i of the current variable and the set of future connected variables. For each future connected variable Xj, a classical FC propagation step is performed in order to remove inconsistent values if the domain of Xj is known. Otherwise, an acquisition is performed in order to retrieve all the values consistent with v. After the acquisition, the domain of Xi is completely known.

The main difference with the classical FC algorithm is achieved if the GEN module is able to be guided by means of constraints in order to retrieve consistent values. For instance, in a visual recognition system [1], constraints exploiting some form of locality, such as touches{Xl,X2) where Xl and X2 are segments, could

procedure I -propagation-acquisition ( i, fu t ure..connected _vars); begin for each V ar; in future..connected_vars do begin known(j] := known(DomainU]); unknownUJ := unknown(DomainU]); if knownUJ = (v;,, ... , v;m] then begin for each v;k in knownUJ do if not consistent(vi, v;k) then begin remove v;~ from knownUJ; if knownUJ = (] then fail; end else begin end; end; impose..constraints on unknownUJ acquire.alLvalues(unknownUJJ end;

guide the knowledge acquisition in order to let the G EN module to focus only on semantically significant image parts. If this capability could be exploited, the num­ ber of data acquisition performed by IFC is significantly smaller than those performed by FC.

3.2 Interactive Minimal Forward Checking

In the previous section, we have described the IFC algo­ rithm which performs, when needed, the acquisition of all domain values consistent with a given assignment.

As argued in [2], a more efficient algorithm finds and maintains only one consistent value in the domain of each future variable, suspending forward checks until other values are required by the search. In the inter­ active version of the MFC we retrieve only one value for each future connected variable, consistent with a given assignment. In addition, we impose new constraints on the unknown part of the domain for eventual future ac­ quisitions. The algorithm is the same as the one de­ scribed in figure 2. The I -propagation-acquisition step reported in figure 5 is different from the IFC since we acquire only one value by the GEN module and pro­ duce constraints on the unknown domain parts which will be used in backtracking for acquiring further values. Posing new constraints on the variables representing the unknown domain parts is a crucial point in our frame­ work that allows newly acquired data to be processed without starting the constraint propagation process from scratch each time new values are available.

As an example, consider the constraint X 1 < X2 , where variable X 1 is instantiated to 3 and the domain of variable X2 completely unknown, i.e., X2 :: X~. When the constraint is checked, a knowledge acquisition is per­ formed for X2. Suppose that value 5 is retrieved. The domain of x2 becomes x2 :: [5IX"2] and on X"2 a set of constraints is imposed, stating that X" 2 i- 5 and X" 2 > 3. These constraints are taken into account if value 5 is removed from the domain of X2 during con­ straint propagation. In this case, another consistent value for x2 is retrieved satisfying the imposed con­ straints on X"2·

procedure I-propagation-acquisition ( i ,fu tu re..con nected_vars); begin for each V ar; in future..connected_vars do begin knownUJ := known(Domain[j]); % contains at most one value unknown[j] := unknown(Domain[j]); if known[j] = [v;] then begin if not consistent( v;, v;) then begin remove v; from known[j]; impose_constraints on unknown[j]; acq uire_one _value( u n known[j]); end; else impose_constraints on unknown[jJ else begin % the domain of 'v ar; is fully unknown impose_constraints on unknown[j] acquire_one_value( unknown[j]) end ; end; end;

4 Heuristics

One important issue is the ordering in which variables are labelled and the ordering in which values are assigned to each variable. Decisions in these orderings signifi­ cantly affect the efficiency of the search strategy.

As concerns variable selection, a widely used CSP heuristics, called first fail principle, selects first the vari­ able with the smallest domain. When coping with par­ tially or fully unknown domains, we cannot know in ad­ vance how many values will be contained in the domain. Thus, we partially disable variable selection heuristics which depend on domain size. A general criterion which can be followed in the interactive framework tends to minimize knowledge acquisitions. Thus, we first select variables with a completely known domain and among those, then partially known variables, and finally, com­ pletely unknown variables.

As concerns the domain value choice, the only heuris­ tic used concerns the selection of a value belonging to the known part of a domain before the selection of the unknown part that results in an unguided knowledge acquisition. ·

5 Experimental Results

In order to test ICSP algorithms, we performed a se­ ries of experiments based on randomly generated CSPs. Each CSP is defined by a 4-tuple < n, m, p, q >, where n is the number of variables, m is the size of every domain, p is the probability that a binary constraint is imposed on a pair of variables (constraint density), and q is the conditional probability that two values in a constraint are consistent.

We consider both the number of constraint checks per­ formed by the high-level system and the number of con­ straint checks performed by the low-level system during interaction. Each time a single value is requested for one variable domain (function acquire_one_value) , first we check if an already acquired value is consistent w.r.t. the interactive constraints (and we count the number of constraint checks needed); if the element is not found we perform acquisition.

Figure 6 shows the ratio of the number of constraint checks performed by FC and by IFC (the higher the bars, the better is the interactive approach). The test was performed generating a number of problems with n = 10, d = 10, and varying p and q. Each bar is calculated on the average of 20 problems.

We can see that the number of constraint checks per­ formed by IFC is always less than plain FC and is consid­ erably lower when the constraint tightness is high (i.e., low values of q). This depends on the fact that, when binding a variable, the IFC algorithm acquires only the values consistent with constraints, so, if the constraint is tight, only few acquisitions will be performed.

Analogous considerations can be done for Minimal Forward Checking algorithm: as the constraint tightness grows, the interactive approach outperforms the non in­ teractive one.

Since in most applications the value extraction is usu­ ally the most expensive task, the comparison based on the number of extracted values is more significant than a comparison based on constraint checks. In Figure 9 we show the percentage of extracted elements for the IMFC algorithm in problems generated with n = 10, d = 10, varying p and q from 10% to 90%. We can see that in more than half of the cases the number of extracted elements is less than 50% of the number of elements ex­ tracted by CSP methods. The number of acquired values is very low if the constraints are tight, as every interac­ tive constraint will acquire only few values and this will be enough to demonstrate that the whole problem is in­ consistent.

The number of acquisitions is higher in IFC, because it extracts all values consistent with an interactive con­ straint (Figure 8). The displayed graph is quite similar to that in Figure 9, but shows a higher number of acqui­ sitions when q grows. If almost every value in a domain is consistent w.r.t. the interactive constraints, then it is likely that every acquisition will lead to a full extraction, i.e. every acquisition will extract nearly all the d values which can be assigned to a given variable.

5.1 3D Visual Object Recognition

In this section, we show some results obtained in 3D ob­ ject recognition by using the ICSP framework, [1]. We model 3D objects by means of constraint graphs: nodes represent object parts (say surfaces) and constraints ge­ ometric and topological relations among them. A graph representation of object models has been used in many different contexts of 2D shapes [9], and extended to the 3D scene recognition [7],[6] . Solving the 3D object recog­ nition problem as a standard CSP involves the extrac­ tion from the image of all surfaces 50 ... , Sm which are put in variable domains Do . .. Dn. Then, we have to find an assignment of surfaces to variables satisfying all constraints.

The CSP-based approach for object recognition suf­ fers of a severe limitation in term of efficiency when ap­ plied to real vision applications: surface extraction is a time consuming step working on range images. Thus, useless acquisitions should be avoided and the adop­ tion of ICSP leads to a significant performance improve­ ment. The ICSP-based recognition executes the follow­ ing steps: (i) the constraint solver queries the low-level image processing system for retrieving an unconstrained surface (S 1); (ii) the interacting constraint propagation starts, and whenever a variable domain is not known, new variable values satisfying constraints are requested. In this case, the GEN module is able to acquire vi­ sual features being guided by spatial constraints such as get_surface_touching(Xi) so that only adjacent sur­ faces to Xi are directly computed. This improves the ICSP performances since variable domains turn to be smaller and, more important, the visual system focusses only on significant image parts. Thus, the guided in­ teraction prevents the low-level system from acquiring many useless surfaces .

Several tests are performed on a specific data-base of range images: we have created a modified version of the Washington State University database [5] by assembling several images in order to obtain new ones containing many different possibly overlapped objects.

Results in Table 1 refer to a database of 9 images and describe the time (in seconds) spent for extracting the first 3D object with an L-shape: the CSP and the ICSP approaches are compared. Some images (marked with *) do not contain the object. In those cases the whole image has been explored and all surfaces computed for both approaches. When all the surfaces are extracted in the image, the performance gain using an interactive approach is not particularly high (in one case the ICSP is even slower since it uses more check points): never­ theless, in images containing the modelled 3D object , a speedup ranging between 2 to 8 has been obtained.

6 Related Work

The general idea that in many applications it is both unreasonable and unrealistic to force the user to provide in advance all information required to solve the problem was argued by Sergot [11] who proposed an extension of Prolog allowing interaction with the user. From an al­ gorithmic perspective, our starting points are the FC [4]

and the MFC [2] algorithms. They have been extended with the notion of interaction between a constraint solver and a low level module producing constrained data to be processed.

Dynamic Constraint Satisfaction (DCS) [8] is a field of AI taking into account dynamic changes of the con­ straint store such as the addition, deletion of values and constraints. The difference between DCS and our ap­ proach concerns the way of handling these changes. DCS approaches propagate constraints as if they work in a closed world. DCS solvers record the dependencies be­ tween constraints and the corresponding propagation in proper data structures so as to tackle modifications of the constraint store. In this perspective, we also cope with changes in the sense that the acquisition of new variable values can be seen as a modification of the con­ straint store. However, we work in an open world where domains are left opened thanks to their unknown part. Unknown domain parts intensionally represent future ac­ quisition, i.e., future changes. Thus, the propagation we perform is less powerful than that performed by dynamic approaches, but we do not need to store additional in­ formation for restoring the constraint store consistency as done by DCS approaches.

Other related approaches concern constraint-based re­ active systems [3]. Reactive programs are programs that react with their environment, are usually stateful, and have to make decisions before their consequences are known. They interleave information accumulation and decision making activities. Also in our approach data acquisition and its processing are interleaved. However, in reactive programs the constraint solver computes a solution for a given set of (incrementally added) vari­ ables starting from an already committed system state. Thus, the computation of a single query is performed with no interaction with the ( G EN) system. In our ap­ proach, instead, interactions between the system (the GEN module) and the constraint solver take place dur­ ing the execution of a single query.

As a final remark, in the field of programming lan­ guages, concurrent constraint . programming [10] repre­ sents a framework which is based on the notions of con­ sistency and entailment for computing with partial in­ formation. Computation emerges from the interaction of concurrently executing agents communicating by means of constraints on shared variables. In a sense, the work on concurrent constraint programming concentrates on the algorithms without paying attention to the seman­ tics of the external world. With our approach we add this semantics. Concurrent constraint programming can be used as an effective language for implementing the interactive constraint solver .

7 Conclusion and Future work

We have presented a model for interactive CSP which can be used when data on the domain is not completely known at the beginning of the computation, but can be dynamically acquired on demand by a low level system.

More important, it is used in order to guide the search by generating new constraints at each step. We have implemented the framework by extending the ECLipse CLP(FD) library. We have shown results on randomly generated CSPs and in the field of 3D object recognition.

Future work concerns the extension of other constraint propagation algorithms, like arc-consistency, to the in­ teractive case. In addition, we are investigating other fields such as planning and user interfaces which could benefit from the proposed approach.

Acknowledgements

This work has been partially supported by MURST Project on "Intelligent Agents: Interaction and Knowl­ edge Acquisition".