Uploaded image for project: 'Drools'
  1. Drools
  2. DROOLS-5198

Infinite loop induced by backward chaining

XMLWordPrintable

    • Icon: Bug Bug
    • Resolution: Unresolved
    • Icon: Major Major
    • None
    • 7.34.0.Final
    • core engine
    • None
    • Hide

      This is the simplest possible example I could come up with to illustrate the issue. Assuming the HasA relation represents "possession". When the facts below are inserted into WM and all rules fired, the facts inferred via BC ("House has John" and "John has Bedroom") provoke an infinite loop.

      Bedroom has John
      House has Bedroom
      John has House

      Fact type (Java class)

      @Role(FACT)
public class HasA {

    @Position(0)
    private String possessor;

    @Position(1)
    private String possessee;

    ... Setters, getters...
}

      Drools query

      query hasPossession(String possessor, String possessee)
  HasA(possessor, possessee)
  or
  (HasA(z, possessee) and hasPossession(possessor, z;))
end

      Test code

      ...
KieServices kieServices = KieServices.Factory.get();
KieContainer kieContainer = kieServices.getKieClasspathContainer();
KieSession kieSession = kieContainer.newKieSession();

kieSession.insert(new HasA("Bedroom", "John"));
kieSession.insert(new HasA("House", "Bedroom"));
kieSession.insert(new HasA("John", "House"));

kieSession.fireAllRules();
...
      Show
      This is the simplest possible example I could come up with to illustrate the issue. Assuming the HasA relation represents "possession". When the facts below are inserted into WM and all rules fired, the facts inferred via BC ("House has John" and "John has Bedroom") provoke an infinite loop. Bedroom has John House has Bedroom John has House Fact type (Java class) @Role(FACT) public class HasA { @Position(0) private String possessor; @Position(1) private String possessee; ... Setters, getters... } Drools query query hasPossession(String possessor, String possessee) HasA(possessor, possessee) or (HasA(z, possessee) and hasPossession(possessor, z;)) end Test code ... KieServices kieServices = KieServices.Factory.get(); KieContainer kieContainer = kieServices.getKieClasspathContainer(); KieSession kieSession = kieContainer.newKieSession(); kieSession.insert( new HasA( "Bedroom" , "John" )); kieSession.insert( new HasA( "House" , "Bedroom" )); kieSession.insert( new HasA( "John" , "House" )); kieSession.fireAllRules(); ...
    • NEW
    • NEW

      I could not find an out-of-the-box mechanism in Drools for stopping loops induced by backward chaining. I've found some research e.g., Avoiding Infinite Loops in Rule-Based Systems with Backward Chaining, indicating this is a recurring problem.

      When undeterred, these loops cause an OutOfMemoryError.

      I've already tried to:

      • Find configuration options in Drools to limit the behavior, but apparently there are't any;
      • Step through the code, trying to find ways to break the recursive behavior;
      • Change my rules to check for possible loops but that resulted either in partial facts being added to working memory (WM) or computationally expensive logic.

              mfusco@redhat.com Mario Fusco
              izilotti Ivan Zilotti (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

                Created:
                Updated: