Wednesday, March 19, 2008

Drools and Multi Colored Balls

I thought I would share with our readers a thread from our priority support system. It's an interesting thread as it covers some complex constraint problems in good detail, which I think most rules users might find interesting, and it also demonstrates the level of support we provide to our priority customers. This conversation is printed "as is" with only the user and customer names removed. Services have just asked me to mention that when you purchase JBoss Drools priority support subscriptions, you aren't just getting high quality support as shown below, but also a legal commitment from us to respond with guaranteed response times (whose values depend on the type of agreement they purchased of course).

User
I have a query to help me retrieve different combination of 5 balls out of 20 balls.

Here is my simple query,
query "get balls set"
ball1 : Ball();
ball2 : Ball(this != ball1);
ball3 : Ball(this != ball1 && != ball2);
ball4 : Ball(this != ball1 && != ball2 && != ball3);
ball5 : Ball(this != ball1 && != ball2 && != ball3 && != ball4);
end
And now, I want to add one more rule to this query.
The rule is, only 0-2 balls can be (color == 'yellow').

That means, after the rule was added, I may have a set of balls that having,
no balls in yellow color; or
1 ball in yellow color; or
2 balls in yellow color.

So, how should I modify the query?


Edson
In other words, balls 3, 4 and 5 must be different from yellow, right?

query "get balls set"
ball1 : Ball();
ball2 : Ball(this != ball1);
ball3 : Ball(this != ball1 && != ball2, color != "yellow" );
ball4 : Ball(this != ball1 && != ball2 && != ball3, color != "yellow" );
ball5 : Ball(this != ball1 && != ball2 && != ball3 && != ball4, color != "yellow" );
end

Does that help you?


User
Yes, you are right. Thank you.
What if I want to apply some rules on the ball set to ensure some mutually exclusion?

Say,
1. color == 'red' and color == 'blue' cannot be co-exists in the same ball set.
2. when having 2 size == 'medium', no ball with size == 'big' can be selected.

And I am going to have dozen of these mutually exclusion rules.


Edson
Well, all constraints must be expressed in some way. Some are more complex than others, but the language is Turing complete and any constraint can be expressed.

So, for your first question, we can use a simple approach writing down the possible combinations and using a class to represent the mutually exclusive colors. You can obviously hard code the colors, but I'm just trying to show you different approaches to the problem:
query "avoid mutually exclusive colors"
ball1 : Ball( $c1 : color );
ball2 : Ball(this not in ( ball1 ), $c2 : color );
ball3 : Ball(this not in ( ball1, ball2 ), $c3 : color );
ball4 : Ball(this not in ( ball1, ball2, ball3 ), $c4 : color );
ball5 : Ball(this not in ( ball1, ball2, ball3, ball4 ), $c5 : color );
not MutuallyExclusiveColors((color1==$c1 && color2 in ($c2,$c3,$c4,$c5))||
(color1==$c2 && color2 in ($c1,$c3,$c4,$c5))||
(color1==$c3 && color2 in ($c1,$c2,$c4,$c5))||
(color1==$c4 && color2 in ($c1,$c2,$c3,$c5))||
(color1==$c5 && color2 in ($c1,$c2,$c3,$c4)))
end
Now, we can also use a simple trick to add some flexibility, and a whole new set of possibilities are open for us. Since we can create lists using the MVEL dialect, we can define a dummy function to help us.
function java.util.List returnList( java.util.List list ) {
return list;
}
So, we can express your original question with a rule like that:
rule "Select maximum 2 yellow balls"
when
$b1 : Ball( )
$b2 : Ball( this not in ($b1) )
$b3 : Ball( this not in ($b1, $b2) )
$b4 : Ball( this not in ($b1, $b2, $b3) )
$b5 : Ball( this not in ($b1, $b2, $b3, $b4) )
Number( intValue <= 2 )
from accumulate( $b : Ball( color == "yellow" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
then
System.out.println( "Balls: "+$b1+" "+$b2+" "+$b3+" "+$b4+" "+$b5 );
end
The same way, we can express your red/blue constraint by writing something like:
rule "red and blue can not co-exist"
when
$b1 : Ball( )
$b2 : Ball( this not in ($b1) )
$b3 : Ball( this not in ($b1, $b2) )
$b4 : Ball( this not in ($b1, $b2, $b3) )
$b5 : Ball( this not in ($b1, $b2, $b3, $b4) )
Number( $red : intValue )
from accumulate( $b : Ball( color == "red" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
Number( intValue == 0 || eval( $red == 0 ) )
from accumulate( $b : Ball( color == "blue" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
then
System.out.println( "Balls: "+$b1+" "+$b2+" "+$b3+" "+$b4+" "+$b5 );
end
Your second constraint can be expressed as:
rule "if there are 2 or more mediums, no big allowed"
when
$b1 : Ball( )
$b2 : Ball( this not in ($b1) )
$b3 : Ball( this not in ($b1, $b2) )
$b4 : Ball( this not in ($b1, $b2, $b3) )
$b5 : Ball( this not in ($b1, $b2, $b3, $b4) )
Number( $big : intValue )
from accumulate( $b : Ball( size == "big" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
Number( intValue < 2 || eval( $big == 0 ) )
from accumulate( $b : Ball( size == "medium" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
then
System.out.println( "Balls: "+$b1+" "+$b2+" "+$b3+" "+$b4+" "+$b5 );
end
Now I would like to call your attention to the fact that such kind of rules have the potential for combinatory explosion and, as such, a great performance degradation.

What I mean is that if you have for instance 10 balls in the working memory and you want to select 5, you are effectivelly doing permutation without repetitions, whose total possible permutations are given by the formula:
P(10, 5) = 10! / (10-5)! = 30240 possible results.
If you add just one more ball to the working memory, you will get:
P(11, 5) = 11! / (11-5)! = 55440 possible results.
As you can see, it is an exponential growth. Just something to be aware of.


User
OK, I digested your message now.
It helps alot.

I am trying to merge all your 3 rules into a single query.
Like this,
Query "Merging all rules into single query"
$b1 : Ball( )
$b2 : Ball( this not in ($b1) )
$b3 : Ball( this not in ($b1, $b2) )
$b4 : Ball( this not in ($b1, $b2, $b3) )
$b5 : Ball( this not in ($b1, $b2, $b3, $b4) )
Number( intValue <= 2 )
from accumulate( $b : Ball( color == "yellow" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
not ( Number( $red : intValue )
from accumulate( $b : Ball( color == "red" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
&&
Number( intValue == 0 || eval( $red == 0 ) )
from accumulate( $b : Ball( color == "blue" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) ) )
not ( Number( $big : intValue )
from accumulate( $b : Ball( size == "big" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
&&
Number( intValue < 2 || eval( $big == 0 ) )
from accumulate( $b : Ball( size == "medium" ) from returnList( [$b1, $b2, $b3, $b4, $b5] ),
count( $b ) )
Do you think I can merge these 3 rules like this?
And after merging it, would it introduce any new performance issues?


Edson
Technically speaking, you can merge them. The major impact is still the combinatorial explosion the first 5 patterns will cause, as detailed in my previous message, but of course, each additional pattern will make the query a bit heavier.

Also, it is not easy to read it, but if that is what you need, then I don't think there is any other way.

Finally, with a small modification to your dummy function, you can avoid calling it every time to create the list over and over again.

The "from" CE will always iterate over the elements of the collection that is returned by the function call, so, instead of returning a collection of balls, change it to return a collection of collection of balls:
function java.util.List returnWrappedList( java.util.List list ) {
return new ArrayList( list );
}
Then you can write a pattern in your query like:
$balls : List() from returnWrappedList( [$b1,$b2,$b3,$b4,$b5] )
And then you can use $balls instead of recreating the list over and over again. Example:
Number( intValue <= 2 )
from accumulate( $b : Ball( color == "yellow" ) from $balls,
count( $b ) )


------------------------
NB:
With latest MVEL (1.2.24), we don't need a dummy function anymore... we can simply use MVEL's return statement:

from return( [$b1, $b2, $b3, $b4, $b5] )

Or if we need a wrapped list:

from return( [[ $b1, $b2, $b3, $b4, $b5 ]] )

6 comments:

  1. Guys, I hate to sound like a broken record, but constraint satisfaction problems(CSP) should be solved with software that have been specifically designed for that kind problems. In particular, it allows incremental addition of constraints, has embedded allDiff() operator to avoid pairwise '!=', etc. I don't even want to start about performance - most of the constraint problems are combinatorial, as you know ...

    The best solution should be hybrid, integrating rules and constraints, i.e. where rules conditions may become constraints in CSP sense and vice-versa

    ReplyDelete
  2. "The best solution should be hybrid, integrating rules and constraints"

    Yes and no. I know what you mean and in a complex scenario, you may be right. This case, though, is obviously a scenario abstraction that allows us to see just a glimpse of the full kind of problem the user is modeling. With more information/requirements available, we would be able to recommend or not a hybrid approach. With the available information, we do conservative recommendations.

    "has embedded allDiff() operator to avoid pairwise '!='"

    Drools also has a series of options that help some specific scenarios. The question here is again, with available information, should we recommend them? Setting RulebaseConfiguration.setRemoveIdentities(true) will have the same effect of avoiding a single fact from matching multiple patterns at once, eliminating the need to explicitly declare the "!=" constraints, but is that what the user really wants?

    So, CSP is something to have in mind when dealing with such kind of problems, but at this point, only the customer has all the requirements and can either make this decision or call for external recommendation/consultancy.

    Edson

    ReplyDelete
  3. Edson,

    I mostly based my post on this statement from the user
    ========================
    Yes, you are right. Thank you.
    What if I want to apply some rules on the ball set to ensure some mutually exclusion?

    Say,
    1. color == 'red' and color == 'blue' cannot be co-exists in the same ball set.
    2. when having 2 size == 'medium', no ball with size == 'big' can be selected.

    And I am going to have dozen of these mutually exclusion rules.
    ===============================

    Once you combine this with the possibility that there could be 4 or 6 or 15 balls - you get my point, right? It is not only the performance, but the ability to describe the logic in comprehensible way too.

    ReplyDelete
  4. I agree with stanislov. Let's forget rule engines a minute and think about "how easy is it for a new developer to use?"
    although it can be done with existing syntax, writing it that way is a bit ugly. the biggest draw back I see, is the syntax gets very ugly as the number of balls increase, as stanislov points out. Even without using CSP, there's better ways to solve the problem, which can work with any number of balls.

    I feel the industry in general needs to provide better guidance on different techniques for writing rules. Telling users to write a rule that way can lead to a maintenance nightmare. Instead, rule chaining should be used to break the problem down.

    I like the example though, but not for the same reason. It shows users why they shouldn't write a rule like that.

    ReplyDelete
  5. Hit publish to quickly. I've seen this same type of question on JESS mailing list dozens of times over the years. The advice that ernest gives is to rewrite the rule to use chaining. More people should search JESS mailing list, since it has a wealth of information and examples.

    There are a few seasoned people on JESS mailing list, who consistently provide great advice. I'm not talking about simple stuff either, but elegant solutions that work well. For me, the biggest advantage of JESS and CLIPS is the wealth of expertise in the user base. Even blaze and JRules user base doesn't have that kind of breadth and depth.

    ReplyDelete
  6. Hello,

    I need some help to understand how to enforce dependency rules with Drools.
    Suppose you have two objects - A and B - and two business rules that say: "if A is selected, unselect B" and "if B is selected, unselect A".

    How can I be sure that Drools unselects B when user selects A and viceversa?
    How can avoid a loop or Drools resolving dependency unselecting what the user just selected?

    Should I use Solver or Fusion?

    Thanks a lot!

    ReplyDelete