#4 Dynamic domain values

[Denise Maria Vecino Sato]

Hello all,

I am trying to use DCOP (and Frodo) to solve a problem on the train’s domain. For the specific problem I will need to assign do each variable a different domain, which must be calculated (dynamically assigned), based on some constraints. For example, I will have an agent representing car 1 (on the train) and another to represent car 2. If the value of car 2 must be greater than the car 1 (defined in the constraints by using predicates), the domain for the car 1 should be reduced only to include greater values. It means that if my domain is 0..15, I want this domain for car2 e the domain 1…15 for car 1. Is there any way to declare a domain based on a function?

Kind regards,
Denise

[Thomas B. Léauté]

Hello Denise,

From your question, it is not absolutely clear whether your are dealing with integer-valued variables (the solution to the problem involves assigning a given integer value to each variable) or with set variables (the solution involves assigning a set of values to each variable). Since FRODO does not support set variables, I am going to assume that you are dealing with integer-valued variables.

Then, the short answer is: it is not possible to declare a domain based on a function. The domain of a variable must be defined a priori as a finite list of values that is independent of anything, and in particular independent of the constraints and of other variables.

Now, the longer answer. Can you motivate your need for this feature? Why would you need to be able to make a variable's domain definition depend on constraints and on other variables?

One possible motivation for reducing the sizes of the variable domains before running a DCOP algorithm could be that the performance of the DCOP algorithm depends on the sizes of the variable domain sizes. For instance, this is the case of the DPOP algorithm, whose time and space complexity is the variable domain size to some power. In this case, it is indeed important to make the domains as small as possible before you run DPOP.

Why not manually perform this domain reduction yourself when you define the problem, just like you did in your example? I can only see two reasons why this would not be possible or desirable:

1. It would be too complicated to do it when you define the problem, and you expect the agents to do it themselves automatically.
2. In the real-world application, it is not possible for the agents to perform domain reduction on their own variables, because they do not have all the information available. For instance, they don't know the domains of their neighboring variables, or they don't know all constraints involving their own variables.

The majority of DCOP algorithms assume that each agent knows all constraints imposed on their own variables, and also knows the domains of all variables involved in these constraints (i.e. their neighboring variables). So I doubt Point 2 is a valid reason, but you might have a different opinion, based on your knowledge of the real-life problem you are addressing.

On the other hand, Point 1 can be considered a valid one. If it applies to your case, then there is one way to achieve what you want without actually make variable domain definitions depend on constraints or other variables. This would be to run a distributed pre-processing algorithm before you run the actual DCOP algorithm. One example of such a pre-processing algorithm is Distributed Arc Consistency, which would enforce that, for each variable x, for each value x1 in its domain, and for each neighboring variable y, there exists at least one value y1 in y's domain for which all (binary) constraints between x and y are satisfied. In your example, this distributed algorithm would make sure that the value 0 is removed from var2's domain, because it is not compatible with any value in var1's domain from the point of view of the var2 > var1 constraint.

There are however two limitations/problems with running Distributed Arc Consistency before running the actual DCOP algorithm:

1. It does not work with constraints that involve more than 2 variables. There exist more complex pre-processing algorithms than Distributed Arc Consistency that will work with n-ary constraints, but they have higher complexity, and it is not clear a priori whether you would gain anything by running them before the actual DCOP algorithm.
2. It has not (yet) been implemented in FRODO.

Let me know if I have answered your question. If you really have a need for a pre-processing algorithm to perform variable domain reduction, I might consider implementing one in FRODO.

Best,

Thomas

[Denise Maria Vecino Sato]

Hi Thomas,

Thank you for yourresponse, it helps me to clarify things. I'm trying to
reduce the scope of the domain to improve performance... But I realize that
I can do it just as you told... So now, I'm running a pre-processing and
then generating the xcsp for Frodo. This pre-processing is in fact
implemented by an algorithm specific for the problem in question.
But I will need some help for other thing. I'm using integer values for
the variables, but the value in fact represents a bitstring, for example,
if the car receives the value 8, it represents the bitstring 1000. The
bitstring is a representation which helps to solve the problem
(classification trains). But, for the global cost, I will need a bit
operation... The global cost should be the sum of all "1" bits for all
agents. I didn't find anything on frodo about bit operation, so I'm
interesting in implement it. Do you think it's a good idea? Can I do this?

Thank you in advance,
Denise

[Denise Maria Vecino Sato]

Hello Thomas,

First, I want to thank you for all your help until now… Frodo and your
support is helping me a lot on my research. I have done some changes on my
approach. Now, I am using the bitstring values in my domain and I am
obtaining the expected results. However, I am not sure how to handle one
other need. Assuming 4 cars (4 variables), with this assigned values:

1: 0000

2: 0010

3: 0010

4: 0011

I will need a global constraint which sum for all columns in the
bitstrings, the "1" bits. For example, column 1 (right to left) is equal 1,
column 2 = 3, columns 3 and 4 equal 0. I must define a maximum limit for
this, for example 2, or 3... Nevertheless, when I try to define a global
constraint, involving for example 11 variables, frodo is not able anymore
to find a solution. I think this is because the DFS tree has too many
relations... There is any other way to define a relation involving all
variables, without adding all this relations on the DFS tree?

Thanks in advance,

Denise

[Thomas B. Léauté]

Hello Denise,

I am glad I could help.

Regarding constraints with large arity such as the column-wise sum constraint you need, such constraints can indeed have important performance implications, especially if you are using an algorithm whose complexity depends on the treewidth of the problem, such as DPOP. Are you also experiencing the same bad performance with other algorithms, such as SynchBB?

There are however some good news: your constraint could easily be decomposed into smaller-arity constraints over auxiliary constraints, which I expect should increase the performance of DPOP. For instance, instead of expressing the column-wise sum constraint over all 4 variables x1, x2, x3 and x4, you could introduce two auxiliary variables y12 and y34 that represent the two partial sums:

y12 = x1 + x2

y34 = x3 + x4

and then express your original constraint over y12 and y34 instead of over the 4 original xi variables. There are other ways to decompose the sum; for instance you also could do ((x1 + x2) + x3) + x4 instead of (x1 + x2) + (x3 + x4). You could experiment with various decompositions; maybe your knowledge of the real-life problem could also help you guess which decomposition would make most sense.

Best,

Thomas

[Denise Maria Vecino Sato]

Hi Thomas,

I've tried to implement some changes to improve the performance and I
could have a good result using SynchBB. But I'm not sure how to handle your
sugestion to use auxiliary variables in the global sum... I'm already using
auxiliary variables for each bit on the bitstring, but the global
constraint involves all variables... I'm sending you one sample problem
file, maybe you could figure out any other idea looking at the file.

Thanks again,
Denise

[Thomas B. Léauté]

Hi Denise,

The attachment is missing; please upload it in the discussion on the FRODO SourceForge website:
https://sourceforge.net/p/frodo2/support-requests/4/

Best,

Thomas

[Thomas B. Léauté]

Hi Denise,

I would expect it to be a bit complicated for you to implement it yourself, especially since FRODO does not yet have full API support for all JaCoP constraints (I am still working on feature request 37).

However, I believe there is already a way to achieve what you want using the JaCoP intensional soft constraints already supported in FRODO.

Let N be the value of the variable, which is written wxyz in binary base, i.e.:

N = w * 2^3 + x * 2^2 + y * 2 + z

where w, x, y and z are Booleans. Then you can compute them as follows:

z = N mod 2
y = (N div 2) mod 2
x = (N div 2^2) mod 2
w = (N div 2^3) mod 2

and therefore the cost function for the variable can be written a follows:

C = N mod 2 + (N div 2) mod 2 + (N div 2^2) mod 2 + (N div 2^3) mod 2

Note that such a complex functional expression will result in the creation of lots of auxiliary variables inside JaCoP, but this should not hurt the performance of the DCOP algorithm too much, since these auxiliary variables will be hidden inside JaCoP and not visible to the DCOP algorithm.

By the way, if what you really want are not integer-valued variables but bit-string-valued variables, is there any reason why you don't want to work in base 2 instead of in base 10? In other words, why not define the domain of your variables as follows:

0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

rather than as follows (which I assume is the way you do it)?

0..15

Then of course you would have to replace 2 with 10 in all the formulae above.

Best,

Thomas