org.opencyc.constraintsolver
Class ForwardCheckingSearcher

java.lang.Object
  |
  +--org.opencyc.constraintsolver.ForwardCheckingSearcher

public class ForwardCheckingSearcher
extends java.lang.Object

The ForwardCheckingSearcher object to perform forward checking search for one or more solutions to the ConstraintProblem.

Author:
Stephen L. Reed

Copyright 2001 Cycorp, Inc., license is open source GNU LGPL.

the license

www.opencyc.org

OpenCyc at SourceForge

THIS SOFTWARE AND KNOWLEDGE BASE CONTENT ARE PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENCYC ORGANIZATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE AND KNOWLEDGE BASE CONTENT, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

See Also:
UnitTest#testConstraintProblem

Field Summary
protected static int ASK_ALL_OR_INDIV_THRESHOLD
          When instantiating a rule having one variable left to instantiate for subsequent asking the KB, this parameter sets the threshold beyond which a variable is used in the ask -- returning what bindings are known (or proven) in the KB.
protected  ConstraintProblem constraintProblem
          Reference to the parent ConstraintProblem object.
protected  java.util.ArrayList constraintRules
          Reference to the collection of the constraint rules used in the search for solution(s).
protected  int nbrSteps
          Number of search steps performed during the search for solution(s).
protected  Solution solution
          Reference to the Solution for the parent ConstraintProblem object.
protected  ValueDomains valueDomains
          Reference to the ValueDomains object for the parent ConstraintProblem object.
protected  int verbosity
          Sets verbosity of the constraint solver output.
 
Constructor Summary
ForwardCheckingSearcher(ConstraintProblem constraintProblem)
          Constructs a new FowardCheckingSearcher object.
 
Method Summary
protected  java.util.ArrayList askWithVariable(CycList instantiatedRule, CycVariable variable)
          Returns a list of bindings for single unbound variable left in the rule.
protected  boolean checkForwardDifferentRule(ConstraintRule rule, java.util.ArrayList remainingRuleVariables, int level, Binding currentBinding)
          Applies the all-different constraint rule to the remaining domains and returns true iff no domains are wiped out.
protected  boolean checkForwardInstantiatedRule(CycList instantiatedRule, java.util.ArrayList remainingRuleVariables, java.util.ArrayList bindings, int level, Binding currentBinding)
          Recurses to instantiate the rule in the constraint problem microtheory with all remaining variables as bindings.
protected  boolean checkForwardNonEvaluatableRule(ConstraintRule rule, int level, Binding currentBinding)
          Performs forward checking of the given non-evaluatable rule to restrict the domains of remaining variables.
protected  boolean checkForwardRule(ConstraintRule rule, java.util.ArrayList remainingRuleVariables, int level, Binding currentBinding)
          Performs forward checking of the given rule to restrict the domains of remaining variables.
protected  boolean checkForwardRules(java.util.ArrayList remainingVariables, int level, Binding currentBinding)
          Performs forward checking of applicable rules to restrict the domains of remaining variables.
protected  int constraintDegree(CycVariable variable, java.util.ArrayList variables)
          Returns the number of constraint rules applicable to variable and one or more of the other variables.
protected  void markPermittedRemainingBindings(CycList instantiatedRule, java.util.ArrayList remainingVariables, java.util.ArrayList bindings, Binding currentBinding, ConstraintRule currentRule)
          Recurses to instantiate the constraint rule in the constraint problem KB microtheory with all remaining variables as bindings, marking the domain values as permitted with Boolean true.
protected  void restore(java.util.ArrayList remainingVariables, int level)
          Restores the eliminated value choices for constraint variables due to a backtrack in the search.
 boolean search(java.util.ArrayList variables, int level)
          Performs a depth-first search of the solution space, using forward checking to prune alternatives.
protected  CycVariable selectVariable(java.util.ArrayList variables)
          From the list of variables, heuristically chooses the one most likely to narrow the remaining search space.
 void setVerbosity(int verbosity)
          Sets verbosity of the constraint solver output.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

verbosity

protected int verbosity
Sets verbosity of the constraint solver output. 0 --> quiet ... 9 -> maximum diagnostic input.

constraintProblem

protected ConstraintProblem constraintProblem
Reference to the parent ConstraintProblem object.

constraintRules

protected java.util.ArrayList constraintRules
Reference to the collection of the constraint rules used in the search for solution(s).

solution

protected Solution solution
Reference to the Solution for the parent ConstraintProblem object.

valueDomains

protected ValueDomains valueDomains
Reference to the ValueDomains object for the parent ConstraintProblem object.

ASK_ALL_OR_INDIV_THRESHOLD

protected static final int ASK_ALL_OR_INDIV_THRESHOLD
When instantiating a rule having one variable left to instantiate for subsequent asking the KB, this parameter sets the threshold beyond which a variable is used in the ask -- returning what bindings are known (or proven) in the KB. Under this threshold, the rule is fully instantiated for the of each variable binding in the unmarked value domain and the KB ask is performed on each of these.

nbrSteps

protected int nbrSteps
Number of search steps performed during the search for solution(s).
Constructor Detail

ForwardCheckingSearcher

public ForwardCheckingSearcher(ConstraintProblem constraintProblem)
Constructs a new FowardCheckingSearcher object.
Parameters:
constraintProblem - the parent constraint problem
Method Detail

setVerbosity

public void setVerbosity(int verbosity)
Sets verbosity of the constraint solver output. 0 --> quiet ... 9 -> maximum diagnostic input.
Parameters:
verbosity - 0 --> quiet ... 9 -> maximum diagnostic input

search

public boolean search(java.util.ArrayList variables,
                      int level)
               throws java.io.IOException,
                      CycApiException
Performs a depth-first search of the solution space, using forward checking to prune alternatives. Employs recursion to search subtrees.
Parameters:
variables - is the ArrayList of remaining variables to solve
level - is the current depth of the search
Returns:
true when done with the search

selectVariable

protected CycVariable selectVariable(java.util.ArrayList variables)
From the list of variables, heuristically chooses the one most likely to narrow the remaining search space.
Parameters:
variables - the ArrayList of variables from which the choice is made
Returns:
the variable most likely to narrow the remaining search space

checkForwardRules

protected boolean checkForwardRules(java.util.ArrayList remainingVariables,
                                    int level,
                                    Binding currentBinding)
                             throws java.io.IOException,
                                    CycApiException
Performs forward checking of applicable rules to restrict the domains of remaining variables. Returns true iff no remaining variable domains are wiped out.
Parameters:
remainingVariables - the ArrayList of variables for which no domain values have yet been bound
currentBinding - the current variable and bound value
Returns:
true iff no remaining variable domains are wiped out

checkForwardRule

protected boolean checkForwardRule(ConstraintRule rule,
                                   java.util.ArrayList remainingRuleVariables,
                                   int level,
                                   Binding currentBinding)
                            throws java.io.IOException,
                                   CycApiException
Performs forward checking of the given rule to restrict the domains of remaining variables. Returns true iff no remaining variable domains are wiped out. Delegates forward checking to specific methods for all-different constraint, evaluatable constraint, non-evaluatable constraint. Non-evaluatable constraints are asked in the knowledge base rather than evaluated in the constraint solver object.
Parameters:
rule - the constraint rule
remainingRuleVariables - the ArrayList of rule variables for which no domain values have yet been bound
level - the current level of solution search depth
currentBinding - the current variable and bound value
Returns:
true iff no remaining variable domains are wiped out

checkForwardNonEvaluatableRule

protected boolean checkForwardNonEvaluatableRule(ConstraintRule rule,
                                                 int level,
                                                 Binding currentBinding)
                                          throws java.io.IOException,
                                                 CycApiException
Performs forward checking of the given non-evaluatable rule to restrict the domains of remaining variables. Returns true iff no remaining variable domains are wiped out. Non-evaluatable constraints are asked in the knowledge base rather than evaluated in the constraint solver object.
Parameters:
rule - the constraint rule
level - the current level of solution search depth
currentBinding - the current variable and bound value
Returns:
true iff no remaining variable domains are wiped out

markPermittedRemainingBindings

protected void markPermittedRemainingBindings(CycList instantiatedRule,
                                              java.util.ArrayList remainingVariables,
                                              java.util.ArrayList bindings,
                                              Binding currentBinding,
                                              ConstraintRule currentRule)
                                       throws java.io.IOException,
                                              CycApiException
Recurses to instantiate the constraint rule in the constraint problem KB microtheory with all remaining variables as bindings, marking the domain values as permitted with Boolean true.
Parameters:
instantiatedRule - the constraint rule
remainingVariables - the variables left to instantiate in the constraint rule
bindings - the instantiated values for variables already instantiated in the constraint rule

askWithVariable

protected java.util.ArrayList askWithVariable(CycList instantiatedRule,
                                              CycVariable variable)
                                       throws java.io.IOException,
                                              CycApiException
Returns a list of bindings for single unbound variable left in the rule.
Parameters:
instantiatedRule - the rule in CycList form which has a single unbound variable
variable - the variable for which bindings are sought
Returns:
a ArrayList of bindings for single unbound variable left in the rule

checkForwardDifferentRule

protected boolean checkForwardDifferentRule(ConstraintRule rule,
                                            java.util.ArrayList remainingRuleVariables,
                                            int level,
                                            Binding currentBinding)
Applies the all-different constraint rule to the remaining domains and returns true iff no domains are wiped out.
Parameters:
rule - the all-different constraint rule
remainingRuleVariables - the variables left to instantiate in the constraint rule
level - the current level of solution search depth
currentBinding - the current variable and bound value
Returns:
true iff no remaining variable domains are wiped out

checkForwardInstantiatedRule

protected boolean checkForwardInstantiatedRule(CycList instantiatedRule,
                                               java.util.ArrayList remainingRuleVariables,
                                               java.util.ArrayList bindings,
                                               int level,
                                               Binding currentBinding)
                                        throws java.io.IOException
Recurses to instantiate the rule in the constraint problem microtheory with all remaining variables as bindings. Returns true iff no domains are wiped out.
Parameters:
rule - the instantiated constraint rule
remainingRuleVariables - the variables left to instantiate in the constraint rule
bindings - the list of bindings instantiated so far
level - the current level of solution search depth
currentBinding - the current variable and bound value
Returns:
true iff no remaining variable domains are wiped out

restore

protected void restore(java.util.ArrayList remainingVariables,
                       int level)
Restores the eliminated value choices for constraint variables due to a backtrack in the search.

constraintDegree

protected int constraintDegree(CycVariable variable,
                               java.util.ArrayList variables)
Returns the number of constraint rules applicable to variable and one or more of the other variables.
Parameters:
variable - the variable which must be used in the counted constraint rules
variables - the counted constraint rules must use only these variables and no others.
Returns:
the number of constraint rules applicable to variable and one or more of the other variables