Miss Manners and Benchmarking

Name: Miss Manners
Main class: org.drools.benchmark.manners.MannersBenchmark
Type: Java application
Rules file: manners.drl
Objective: Advanced walkthrough on the Manners benchmark, covers Depth conflict resolution in depth.

Introduction

Miss Manners is throwing a party and, being a good host, she wants to arrange good seating. Her initial design arranges everyone in male-female pairs, but then she worries about people have things to talk about. What is a good host to do? She decides to note the hobby of each guest so she can then arrange guests not only pairing them according to alternating sex but also ensuring that a guest has someone with a common hobby, at least on one side.

Figure 8.22. Miss Manners' Guests

Miss Manners' Guests

BenchMarking

Five benchmarks were established in the 1991 paper "Effects of Database Size on Rule System Performance: Five Case Studies" by David Brant, Timothy Grose, Bernie Lofaso and Daniel P. Miranker:

  • Manners uses a depth-first search approach to determine the seating arrangements alternating women and men and ensuring one common hobby for neighbors.

  • Waltz establishes a three-dimensional interpretation of a line drawing by line labeling by constraint propagation.

  • WaltzDB is a more general version of Waltz, supporting junctions of more than three lines and using a database.

  • ARP is a route planner for a robotic air vehicle using the A* search algorithm to achieve minimal cost.

  • Weaver VLSI router for channels and boxes using a black-board technique.

Manners has become the de facto rule engine benchmark. Its behavior, however, is now well known and many engines optimize for this, thus negating its usefulness as a benchmark which is why Waltz is becoming more favorable. These five benchmarks are also published at the University of Texas http://www.cs.utexas.edu/ftp/pub/ops5-benchmark-suite/.

Miss Manners Execution Flow

After the first seating arrangement has been assigned, a depth-first recursion occurs which repeatedly assigns correct seating arrangements until the last seat is assigned. Manners uses a Context instance to control execution flow. The activity diagram is partitioned to show the relation of the rule execution to the current Context state.

Figure 8.23. Manners Activity Diagram

Manners Activity Diagram

The Data and Results

Before going deeper into the rules, let's first take a look at the asserted data and the resulting seating arrangement. The data is a simple set of five guests who should be arranged so that sexes alternate and neighbors have a common hobby.

The Data

The data is given in OPS5 syntax, with a parenthesized list of name and value pairs for each attribute. Each person has only one hobby.

(guest (name n1) (sex m) (hobby  h1)  )
(guest (name n2) (sex f) (hobby  h1)  )
(guest (name n2) (sex f) (hobby  h3)  )
(guest (name n3) (sex m) (hobby  h3)  )
(guest (name n4) (sex m) (hobby  h1)  )
(guest (name n4) (sex f) (hobby  h2)  )
(guest (name n4) (sex f) (hobby  h3)  )
(guest (name n5) (sex f) (hobby  h2)  )
(guest (name n5) (sex f) (hobby  h1)  )
(last_seat (seat 5)  )

The Results

Each line of the results list is printed per execution of the "Assign Seat" rule. They key bit to notice is that each line has a "pid" value one greater than the last. (The significance of this will be explained in the discussion of the rule "Assign Seating".) The "ls", "rs", "ln" and "rn" refer to the left and right seat and neighbor's name, respectively. The actual implementation uses longer attribute names (e.g., leftGuestName, but here we'll stick to the notation from the original implementation.

[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5] 
[Seating id=2, pid=1, done=false, ls=1, ln=n5, rs=2, rn=n4] 
[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3] 
[Seating id=4, pid=3, done=false, ls=3, rn=n3, rs=4, rn=n2] 
[Seating id=5, pid=4, done=false, ls=4, ln=n2, rs=5, rn=n1]

Indepth Discussion

Cheating

Manners has been designed to exercise cross product joins and Agenda activities. Many people not understanding this tweak the example to achieve better performance, making their port of the Manners benchmark pointless. Known cheats or porting errors for Miss Manners are:

  • Using arrays for a guests hobbies, instead of asserting each one as a single fact massively reduces the cross products.

  • Altering the sequence of data can also reduce the amount of matching, increasing execution speed.

  • It's possible to change the <kw>not</kw> Conditional Element so that the test algorithm only uses the "first-best-match", which is, basically, transforming the test algorithm to backward chaining. The results are only comparable to other backward chaining rule engines or ports of Manners.

  • Removing the context so the rule engine matches the guests and seats prematurely. A proper port will prevent facts from matching using the context start.

  • It's possible to prevent the rule engine from performing combinatorial pattern matching.

  • If no facts are retracted in the reasoning cycle, as a result of the <kw>not</kw> CE, the port is incorrect.

Conflict Resolution

The Manners benchmark was written for OPS5 which has two conflict resolution strategies, LEX and MEA. LEX is a chain of several strategies including salience, recency and complexity. The recency part of the strategy drives the depth first (LIFO) firing order. The CLIPS manual documents the Recency strategy as follows:

 

Every fact and instance is marked internally with a "time tag" to indicate its relative recency with respect to every other fact and instance in the system. The pattern entities associated with each rule activation are sorted in descending order for determining placement. An activation with a more recent pattern entity is placed before activations with less recent pattern entities. To determine the placement order of two activations, compare the sorted time tags of the two activations one by one starting with the largest time tags. The comparison should continue until one activation’s time tag is greater than the other activation’s corresponding time tag. The activation with the greater time tag is placed before the other activation on the agenda. If one activation has more pattern entities than the other activation and the compared time tags are all identical, then the activation with more time tags is placed before the other activation on the agenda.

 
 --CLIPS Reference Manual

However Jess and CLIPS both use the Depth strategy, which is simpler and lighter, which Drools also adopted. The CLIPS manual documents the Depth strategy as:

 

Newly activated rules are placed above all rules of the same salience. For example, given that fact-a activates rule-1 and rule-2 and fact-b activates rule-3 and rule-4, then if fact-a is asserted before fact-b, rule-3 and rule-4 will be above rule-1 and rule-2 on the agenda. However, the position of rule-1 relative to rule-2 and rule-3 relative to rule-4 will be arbitrary.

 
 --CLIPS Reference Manual

The initial Drools implementation for the Depth strategy would not work for Manners without the use of salience on the "make_path" rule. The CLIPS support team had this to say:

 

The default conflict resolution strategy for CLIPS, Depth, is different than the default conflict resolution strategy used by OPS5. Therefore if you directly translate an OPS5 program to CLIPS, but use the default depth conflict resolution strategy, you're only likely to get the correct behavior by coincidence. The LEX and MEA conflict resolution strategies are provided in CLIPS to allow you to quickly convert and correctly run an OPS5 program in CLIPS.

 
 --Clips Support Forum

Investigation into the CLIPS code reveals there is undocumented functionality in the Depth strategy. There is an accumulated time tag used in this strategy; it's not an extensively fact by fact comparison as in the recency strategy, it simply adds the total of all the time tags for each activation and compares.

Rule "assignFirstSeat"

Once the context is changed to START_UP, activations are created for all asserted guest. Because all activations are created as the result of a single Working Memory action, they all have the same Activation time tag. The last asserted Guest object would have a higher fact time tag, and its Activation would fire because it has the highest accumulated fact time tag. The execution order in this rule has little importance, but has a big impact in the rule "Assign Seat". The activation fires and asserts the first Seating arrangement and a Path, and then sets the Context attribute state to create an activation for rule findSeating.

rule assignFirstSeat
    when
        context : Context( state == Context.START_UP )
        guest : Guest()
        count : Count()
    then
        String guestName = guest.getName();
        
        Seating seating =
          new Seating( count.getValue(), 1, true, 1, guestName, 1, guestName);
        insert( seating );
        
        Path path = new Path( count.getValue(), 1, guestName );
        insert( path );
        
        modify( count ) { setValue ( count.getValue() + 1 )  }

    System.out.println( "assign first seat :  " + seating + " : " + path );

        modify( context ) {
            setState( Context.ASSIGN_SEATS )
        } 
end

Rule "findSeating"

This rule determines each of the Seating arrangements. The rule creates cross product solutions for all asserted Seating arrangements against all the asserted guests except against itself or any already assigned chosen solutions.

rule findSeating
   when 
       context : Context( state == Context.ASSIGN_SEATS )
       $s      : Seating( pathDone == true )
       $g1     : Guest( name == $s.rightGuestName )
       $g2     : Guest( sex != $g1.sex, hobby == $g1.hobby )

       count   : Count()

       not ( Path( id == $s.id, guestName == $g2.name) )
       not ( Chosen( id == $s.id, guestName == $g2.name, hobby == $g1.hobby) )
   then
       int rightSeat = $s.getRightSeat();
       int seatId = $s.getId();
       int countValue = count.getValue();
       
       Seating seating =
         new Seating( countValue, seatId, false, rightSeat,
                      $s.getRightGuestName(), rightSeat + 1, $g2.getName() );
       insert( seating );
                            
       Path path = new Path( countValue, rightSeat + 1, $g2.getName()  );
       insert( path );
       
       Chosen chosen = new Chosen( seatId, $g2.getName(), $g1.getHobby() );
       insert( chosen  );

       System.err.println( "find seating : " + seating + " : " + path +
                           " : " + chosen);

       modify( count ) {setValue(  countValue + 1 )}
       modify( context ) {setState( Context.MAKE_PATH )}
end

However, as can be seen from the printed results shown earlier, it is essential that only the Seating with the highest pid cross product be chosen. How can this be possible if we have activations, of the same time tag, for nearly all existing Seating and Guest objects? For example, on the third iteration of findDeating the produced activations will be as shown below. Remember, this is from a very small data set, and with larger data sets there would be many more possible activated Seating solutions, with multiple solutions per pid:

=>[ActivationCreated(35): rule=findSeating 
[fid:19:33]:[Seating id=3, pid=2, done=true, ls=2, ln=n4, rs=3, rn=n3] 
[fid:4:4]:[Guest name=n3, sex=m, hobbies=h3] 
[fid:3:3]:[Guest name=n2, sex=f, hobbies=h3]

=>[ActivationCreated(35): rule=findSeating 
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4] 
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1] 
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1] 

=>[ActivationCreated(35): rule=findSeating 
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5] 
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1] 
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

The creation of all these redundant activations might seem pointless, but it must be remembered that Manners is not about good rule design; it's purposefully designed as a bad ruleset to fully stress-test the cross product matching process and the Agenda, which this clearly does. Notice that each activation has the same time tag of 35, as they were all activated by the change in the Context object to ASSIGN_SEATS. With OPS5 and LEX it would correctly fire the activation with the Seating asserted last. With Depth, the accumulated fact time tag ensures that the activation with the last asserted Seating fires.

Rules "makePath" and "pathDone"

Rule makePath must always fire before pathDone. A Path object is asserted for each Seating arrangement, up to the last asserted Seating. Notice that the conditions in pathDone are a subset of those in makePath - so how do we ensure that makePath fires first?

rule makePath
    when 
        Context( state == Context.MAKE_PATH )
        Seating( seatingId:id, seatingPid:pid, pathDone == false )
        Path( id == seatingPid, pathGuestName:guestName, pathSeat:seat )
        not Path( id == seatingId, guestName == pathGuestName )
    then
        insert( new Path( seatingId, pathSeat, pathGuestName ) );
end
rule pathDone
    when
        context : Context( state == Context.MAKE_PATH ) 
        seating : Seating( pathDone == false ) 
    then
        modify( seating ) {setPathDone( true )} 
        
    modify( context ) {setState( Context.CHECK_DONE)}
end

Figure 8.24. Rete Diagram

Rete Diagram

Both rules end up on the Agenda in conflict and with identical activation time tags. However, the accumulate fact time tag is greater for "Make Path" so it gets priority.

Rules "continue" and "areWeDone"

Rule areWeDone only activates when the last seat is assigned, at which point both rules will be activated. For the same reason that makePath always wins over path Done, areWeDone will take priority over rule continue.

rule areWeDone
    when
        context : Context( state == Context.CHECK_DONE ) 
        LastSeat( lastSeat: seat )
        Seating( rightSeat == lastSeat ) 
    then
        modify( context ) {setState(Context.PRINT_RESULTS )}
end
rule continue
    when
        context : Context( state == Context.CHECK_DONE ) 
    then
        modify( context ) {setState( Context.ASSIGN_SEATS )}
end

Output Summary

Assign First seat
=>[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
=>[fid:14:14]:[Path id=1, seat=1, guest=n5]

==>[ActivationCreated(16): rule=findSeating
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

==>[ActivationCreated(16): rule=findSeating
[fid:13:13]:[Seating id=1 , pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1]*

Assign Seating
=>[fid:15:17] :[Seating id=2 , pid=1 , done=false, ls=1, lg=n5, rs=2, rn=n4]
=>[fid:16:18]:[Path id=2, seat=2, guest=n4]
=>[fid:17:19]:[Chosen id=1, name=n4, hobbies=h1]

=>[ActivationCreated(21): rule=makePath 
[fid:15:17] : [Seating id=2, pid=1, done=false, ls=1, ln=n5, rs=2, rn=n4]
[fid:14:14] : [Path id=1, seat=1, guest=n5]*

==>[ActivationCreated(21): rule=pathDone
[Seating id=2, pid=1, done=false, ls=1, ln=n5, rs=2, rn=n4]*

Make Path
=>[fid:18:22:[Path id=2, seat=1, guest=n5]]

Path Done

Continue Process
=>[ActivationCreated(25): rule=findSeating
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4]
[fid:7:7]:[Guest name=n4, sex=f, hobbies=h3]
[fid:4:4] : [Guest name=n3, sex=m, hobbies=h3]*

=>[ActivationCreated(25): rule=findSeating
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4]
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1]
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1], [fid:12:20] : [Count value=3]

=>[ActivationCreated(25): rule=findSeating
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

Assign Seating
=>[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, lnn4, rs=3, rn=n3]]
=>[fid:20:27]:[Path id=3, seat=3, guest=n3]]
=>[fid:21:28]:[Chosen id=2, name=n3, hobbies=h3}]

=>[ActivationCreated(30): rule=makePath
[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3]
[fid:18:22]:[Path id=2, seat=1, guest=n5]*

=>[ActivationCreated(30): rule=makePath 
[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3]
[fid:16:18]:[Path id=2, seat=2, guest=n4]*

=>[ActivationCreated(30): rule=done 
[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3]*

Make Path
=>[fid:22:31]:[Path id=3, seat=1, guest=n5]

Make Path 
=>[fid:23:32] [Path id=3, seat=2, guest=n4]

Path Done

Continue Processing
=>[ActivationCreated(35): rule=findSeating
[fid:19:33]:[Seating id=3, pid=2, done=true, ls=2, ln=n4, rs=3, rn=n3]
[fid:4:4]:[Guest name=n3, sex=m, hobbies=h3]
[fid:3:3]:[Guest name=n2, sex=f, hobbies=h3], [fid:12:29]*

=>[ActivationCreated(35): rule=findSeating 
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4] 
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1]
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1]

=>[ActivationCreated(35): rule=findSeating 
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5] 
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1], [fid:1:1] : [Guest name=n1, sex=m, hobbies=h1]

Assign Seating
=>[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]]
=>[fid:25:37]:[Path id=4, seat=4, guest=n2]]
=>[fid:26:38]:[Chosen id=3, name=n2, hobbies=h3]

==>[ActivationCreated(40): rule=makePath 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]
[fid:23:32]:[Path id=3, seat=2, guest=n4]*

==>[ActivationCreated(40): rule=makePath 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2] 
[fid:20:27]:[Path id=3, seat=3, guest=n3]*

=>[ActivationCreated(40): rule=makePath 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]
[fid:22:31]:[Path id=3, seat=1, guest=n5]*

=>[ActivationCreated(40): rule=done 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]*

Make Path 
=>fid:27:41:[Path id=4, seat=2, guest=n4]

Make Path
=>fid:28:42]:[Path id=4, seat=1, guest=n5]]

Make Path
=>fid:29:43]:[Path id=4, seat=3, guest=n3]]

Path Done

Continue  Processing
=>[ActivationCreated(46): rule=findSeating 
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4] 
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1], [fid:2:2]
[Guest name=n2, sex=f, hobbies=h1]

=>[ActivationCreated(46): rule=findSeating 
[fid:24:44]:[Seating id=4, pid=3, done=true, ls=3, ln=n3, rs=4, rn=n2]
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]*

=>[ActivationCreated(46): rule=findSeating 
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

Assign Seating
=>[fid:30:47]:[Seating id=5, pid=4, done=false, ls=4, ln=n2, rs=5, rn=n1]
=>[fid:31:48]:[Path id=5, seat=5, guest=n1]
=>[fid:32:49]:[Chosen id=4, name=n1, hobbies=h1]