87.10. House of Doom example decisions (backward chaining and recursion)

The House of Doom example decision set demonstrates how the decision engine uses backward chaining and recursion to reach defined goals or subgoals in a hierarchical system.

The following is an overview of the House of Doom example:

  • Name: backwardchaining
  • Main class: org.drools.examples.backwardchaining.HouseOfDoomMain (in src/main/java)
  • Module: drools-examples
  • Type: Java application
  • Rule file: org.drools.examples.backwardchaining.BC-Example.drl (in src/main/resources)
  • Objective: Demonstrates backward chaining and recursion

A backward-chaining rule system is a goal-driven system that starts with a conclusion that the decision engine attempts to satisfy, often using recursion. If the system cannot reach the conclusion or goal, it searches for subgoals, which are conclusions that complete part of the current goal. The system continues this process until either the initial conclusion is satisfied or all subgoals are satisfied.

In contrast, a forward-chaining rule system is a data-driven system that starts with a fact in the working memory of the decision engine and reacts to changes to that fact. When objects are inserted into working memory, any rule conditions that become true as a result of the change are scheduled for execution by the agenda.

The decision engine in Red Hat Decision Manager uses both forward and backward chaining to evaluate rules.

The following diagram illustrates how the decision engine evaluates rules using forward chaining overall with a backward-chaining segment in the logic flow:

図87.27 Rule evaluation logic using forward and backward chaining

RuleEvaluation Enterprise

The House of Doom example uses rules with various types of queries to find the location of rooms and items within the house. The sample class Location.java contains the item and location elements used in the example. The sample class HouseOfDoomMain.java inserts the items or rooms in their respective locations in the house and executes the rules.

Items and locations in HouseOfDoomMain.java class

ksession.insert( new Location("Office", "House") );
ksession.insert( new Location("Kitchen", "House") );
ksession.insert( new Location("Knife", "Kitchen") );
ksession.insert( new Location("Cheese", "Kitchen") );
ksession.insert( new Location("Desk", "Office") );
ksession.insert( new Location("Chair", "Office") );
ksession.insert( new Location("Computer", "Desk") );
ksession.insert( new Location("Drawer", "Desk") );

The example rules rely on backward chaining and recursion to determine the location of all items and rooms in the house structure.

The following diagram illustrates the structure of the House of Doom and the items and rooms within it:

図87.28 House of Doom structure

TransitiveReasoning Enterprise

To execute the example, run the org.drools.examples.backwardchaining.HouseOfDoomMain class as a Java application in your IDE.

After the execution, the following output appears in the IDE console window:

Execution output in the IDE console

go1
Office is in the House
---
go2
Drawer is in the House
---
go3
---
Key is in the Office
---
go4
Chair is in the Office
Desk is in the Office
Key is in the Office
Computer is in the Office
Drawer is in the Office
---
go5
Chair is in Office
Desk is in Office
Drawer is in Desk
Key is in Drawer
Kitchen is in House
Cheese is in Kitchen
Knife is in Kitchen
Computer is in Desk
Office is in House
Key is in Office
Drawer is in House
Computer is in House
Key is in House
Desk is in House
Chair is in House
Knife is in House
Cheese is in House
Computer is in Office
Drawer is in Office
Key is in Desk

All rules in the example have fired to detect the location of all items in the house and to print the location of each in the output.

A recursive query repeatedly searches through the hierarchy of a data structure for relationships between elements.

In the House of Doom example, the BC-Example.drl file contains an isContainedIn query that most of the rules in the example use to recursively evaluate the house data structure for data inserted into the decision engine:

Recursive query in BC-Example.drl

query isContainedIn( String x, String y )
  Location( x, y; )
  or
  ( Location( z, y; ) and isContainedIn( x, z; ) )
end

The rule "go" prints every string inserted into the system to determine how items are implemented, and the rule "go1" calls the query isContainedIn:

Rules "go" and "go1"

rule "go" salience 10
  when
    $s : String()
  then
    System.out.println( $s );
end

rule "go1"
  when
    String( this == "go1" )
    isContainedIn("Office", "House"; )
  then
    System.out.println( "Office is in the House" );
end

The example inserts the "go1" string into the decision engine and activates the "go1" rule to detect that item Office is in the location House:

Insert string and fire rules

ksession.insert( "go1" );
ksession.fireAllRules();

Rule "go1" output in the IDE console

go1
Office is in the House

Transitive closure rule

Transitive closure is a relationship between an element contained in a parent element that is multiple levels higher in a hierarchical structure.

The rule "go2" identifies the transitive closure relationship of the Drawer and the House: The Drawer is in the Desk in the Office in the House.

rule "go2"
  when
    String( this == "go2" )
    isContainedIn("Drawer", "House"; )
  then
    System.out.println( "Drawer is in the House" );
end

The example inserts the "go2" string into the decision engine and activates the "go2" rule to detect that item Drawer is ultimately within the location House:

Insert string and fire rules

ksession.insert( "go2" );
ksession.fireAllRules();

Rule "go2" output in the IDE console

go2
Drawer is in the House

The decision engine determines this outcome based on the following logic:

  1. The query recursively searches through several levels in the house to detect the transitive closure between Drawer and House.
  2. Instead of using Location( x, y; ), the query uses the value of (z, y; ) because Drawer is not directly in House.
  3. The z argument is currently unbound, which means it has no value and returns everything that is in the argument.
  4. The y argument is currently bound to House, so z returns Office and Kitchen.
  5. The query gathers information from the Office and checks recursively if the Drawer is in the Office. The query line isContainedIn( x, z; ) is called for these parameters.
  6. No instance of Drawer exists directly in Office, so no match is found.
  7. With z unbound, the query returns data within the Office and determines that z == Desk.

    isContainedIn(x==drawer, z==desk)
  8. The isContainedIn query recursively searches three times, and on the third time, the query detects an instance of Drawer in Desk.

    Location(x==drawer, y==desk)
  9. After this match on the first location, the query recursively searches back up the structure to determine that the Drawer is in the Desk, the Desk is in the Office, and the Office is in the House. Therefore, the Drawer is in the House and the rule is satisfied.

Reactive query rule

A reactive query searches through the hierarchy of a data structure for relationships between elements and is dynamically updated when elements in the structure are modified.

The rule "go3" functions as a reactive query that detects if a new item Key ever becomes present in the Office by transitive closure: A Key in the Drawer in the Office.

Rule "go3"

rule "go3"
  when
    String( this == "go3" )
    isContainedIn("Key", "Office"; )
  then
    System.out.println( "Key is in the Office" );
end

The example inserts the "go3" string into the decision engine and activates the "go3" rule. Initially, this rule is not satisfied because no item Key exists in the house structure, so the rule produces no output.

Insert string and fire rules

ksession.insert( "go3" );
ksession.fireAllRules();

Rule "go3" output in the IDE console (unsatisfied)

go3

The example then inserts a new item Key in the location Drawer, which is in Office. This change satisfies the transitive closure in the "go3" rule and the output is populated accordingly.

Insert new item location and fire rules

ksession.insert( new Location("Key", "Drawer") );
ksession.fireAllRules();

Rule "go3" output in the IDE console (satisfied)

Key is in the Office

This change also adds another level in the structure that the query includes in subsequent recursive searches.

Queries with unbound arguments in rules

A query with one or more unbound arguments returns all undefined (unbound) items within a defined (bound) argument of the query. If all arguments in a query are unbound, then the query returns all items within the scope of the query.

The rule "go4" uses an unbound argument thing to search for all items within the bound argument Office, instead of using a bound argument to search for a specific item in the Office:

Rule "go4"

rule "go4"
  when
    String( this == "go4" )
    isContainedIn(thing, "Office"; )
  then
    System.out.println( thing + "is in the Office" );
end

The example inserts the "go4" string into the decision engine and activates the "go4" rule to return all items in the Office:

Insert string and fire rules

ksession.insert( "go4" );
ksession.fireAllRules();

Rule "go4" output in the IDE console

go4
Chair is in the Office
Desk is in the Office
Key is in the Office
Computer is in the Office
Drawer is in the Office

The rule "go5" uses both unbound arguments thing and location to search for all items and their locations in the entire House data structure:

Rule "go5"

rule "go5"
  when
    String( this == "go5" )
    isContainedIn(thing, location; )
  then
    System.out.println(thing + " is in " + location );
end

The example inserts the "go5" string into the decision engine and activates the "go5" rule to return all items and their locations in the House data structure:

Insert string and fire rules

ksession.insert( "go5" );
ksession.fireAllRules();

Rule "go5" output in the IDE console

go5
Chair is in Office
Desk is in Office
Drawer is in Desk
Key is in Drawer
Kitchen is in House
Cheese is in Kitchen
Knife is in Kitchen
Computer is in Desk
Office is in House
Key is in Office
Drawer is in House
Computer is in House
Key is in House
Desk is in House
Chair is in House
Knife is in House
Cheese is in House
Computer is in Office
Drawer is in Office
Key is in Desk