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.
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.
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/.
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.
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]
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.
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.
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
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.
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
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.
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
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]