Using prologue and clpr for the constraint system
I am looking to use a prologue in a desktop application to generate a random vector that satisfies a constraint system.
As an example, our user can provide our software with the following information at runtime:
Given a vector <x1, x2, x3, ... x30>
, we can have two constraints:
x1 > x2 + x3 + x4
x5 <= sin(x6 + x7)
what I would like to do is create a prologue program that follows the form loosely:
:- random(0.0, 1.0, X1)
:- random(0.0, 1.0, X2)
#...
# its also concievable that the bounds are different than 0 to 1
:- random(0.0, 1.0, X30)
clp(r) :- constraints {
X1 > X2 + X3 + X4,
X5 <= sin(X6 + X7)
}
?- [ X1, X2, X3, X4, ... X30 ]
which outputs a uniformly random vector in 30-dimensional space.
Is this possible with a prologue?
There's also the problem of consuming this output. What I would like to do is call a call next()
to re-create a new vector. In particular, I need to avoid recompiling as I would like to be able to generate approximately 10,000 of these vectors per second. Can I achieve this level of performance?
I hope to use the in-process instance of swi-prolog on the JVM that runs on the rest of our software. is that enough?
source to share
This is normal!
Basically the approach is fine, and personally I think Prolog is a good choice for such tasks.
However, there are a few subtleties you need to tackle.
First, let's get the syntax back CLP (R):
vector ([X1, X2, X3, X4, X5, X6, X7]): -
{X1> X2 + X3 + X4,
X5 = <sin (X6 + X7)}.
Note in particular the usage =<
as well as the correct usage {}/1
to denote CLP (R) constraints. The token is <=
ignored in Prolog arithmetic because it looks like an arrow that usually denotes an implication in conductors.
That's enough to get the first answers, even if they haven't been created for specific solutions yet:
? - vector (Ls).
Ls = [_1028, _1034, _1040, _1046, _1052, _1058, _1064],
{_1046 = _1028-_1034-_1040-_1088, _1088> 0.0},
{_1052-sin (_1058 + _1064) = <0.0},
{_1052-sin (_1058 + _1064) = <0.0},
{_1052-sin (_1058 + _1064) = <0.0}.
Using random/1
, we can assign random floating point numbers from (0,1) to any of the variables. For example:
? - vector ([A, B, C, D, E, F, G]),
random (A),
random (B).
A = 0.33797712696696053,
B = 0.7039688010209147,
{D = -0.3659916740539542-C-_894, _894> 0.0},
{E-sin (F + G) = <0.0},
{E-sin (F + G) = <0.0},
{E-sin (F + G) = <0.0}.
This solves one part of the problem. However, this method is not suitable for us in cases such as:
? - vector ([A, B, C, D, E, F, G]), random (A), random (B), random (C), random (D). false.
Here's the (deterministic!) Random number generation constraint conflicts . There are several ways to get around this. Before I show them, let's constrain the variables to the desired spacing using, for example, the following definition:
zero_to_one (X): - {0 = <X, X = <1}.
We can simply formulate this constraint as one additional requirement:
? - vector ([A, B, C, D, E, F, G]),
maplist (zero_to_one, [A, B, C, D, E, F, G]),
random (A),
random (B),
random (C).
It gives again false
.
Method 1: More of the same
One way to solve the above problem is to simply repeat the randomized job until a solution is found on return traffic:
? - vector ([A, B, C, D, E, F, G]),
maplist (zero_to_one, [A, B, C, D, E, F, G]),
random (A),
random (B),
repeat ,
random (C).
A = 0.9433451780634803,
B = 0.15859272177823736,
C = 0.706502025956454,
{D> = 0.0, _2064 = 0.07825043032878898-D, D <0.07825043032878898},
{E> = 0.0, E = <1.0, F> = 0.0, F == 0.0, G = <1.0, E-sin (...) = <0.0},
{E-sin (F + G) = <0.0},
{E-sin (F + G) = <0.0},
{E-sin (F + G) = <0.0}.
Thus, we are one step closer to a concrete solution, by which we mean full vector instantiation. The disadvantages are obvious: in extreme cases, we will never find a valid destination in this way. With a little better luck, it can take many tries to find a specific value for even one additional variable.
Method 2: maximize or minimize
Another way to solve this is to use maximize/1
and / or minimize/1
from CLP (R) to use the constraint solver itself to get specific solutions. This only works for linear constraints, and not even for all. For example, consider the following queries:
? - {X = sin (Y)},
maplist (zero_to_one, [X, Y]),
maximize (X).
false.
And even:
? - {X <1}, maximize (X).
false .
Although in contrast:
? - {X = <1}, maximize (X).
X = 1.0.
Now let's use the following trick to get rid of all non-linear constraints: we just assign random floats X6
and X7
using for example:
? - vector (Ls), Ls = [A, B, C, D, E, F, G], maplist (zero_to_one, Ls), random (F), random (G) .
Based on this, we can write:
? - vector (Ls), Ls = [A, B, C, D, E, F, G], maplist (zero_to_one, Ls), random (F), random (G), maximize (A), minimize (B + C + D + E). Ls = [1.0, 0.0, 0.0, 0.0, 0.0, 0.9702069686491169, 0.13220925936558517], A = 1.0, B = C, C = D, D = E, E = 0.0, F = 0.9702069686491169, G = 0.13220925936558517.
Thus, we have obtained a concrete solution that satisfies all the constraints and has some random components.
Concluding remarks
First, to reiterate, I think Prolog is a good choice for such tasks. Pruning with the constraint solver can help eliminate large chunks of the search space, and the constraint solver itself can help you get specific minimization and maximization solutions. Second, there are a few more questions that you need to keep in mind:
- First, the solutions created in this way (using any method) are not random in the sense that each solution is equally likely. Rather, there may be clusters of solutions that appear more often than others.
- As shown above, the equations may require additional reasoning and experimentation, both to reduce them to linear equations and to apply the applicable direction of optimization. Prolog is good for this kind of reasoning, and you can use it to try different strategies easily.
- You may need to find a trade-off between randomization and deterministic optimization to instantiate the remaining vector components. The tradeoff can also depend on the capture of vector components.
Finally, a very important note: Implicit random states work against the properties we expect from logical relationships, as they can cause your predicates to behave differently on subsequent calls, making debugging and systematic testing a nightmare. Therefore, I highly recommend that you provide a random seed, or transfer through the explicit state of the random number generator through your code. This will help you better understand the behavior of your program and make it fully deterministic. You can modify the seeds later to generate different collections of solutions.
source to share