org.metacsp.framework.meta

Class MetaConstraintSolver

java.lang.Object

org.metacsp.framework.ConstraintSolver

org.metacsp.framework.multi.MultiConstraintSolver

org.metacsp.framework.meta.MetaConstraintSolver

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

FuzzyActivityInferenceSolver, FuzzyActivityMetaSolver, Scheduler, SimpleHybridPlanner, SimplePlanner, StateVariableScheduler, TCSPSolver, TrajectoryEnvelopeScheduler

public abstract class MetaConstraintSolver
extends MultiConstraintSolver

A meta-CSP is a high-level CSP whose variables and/or constraints are defined implicitly. These variables and constraints are called meta-variables and meta-constraints. They typically represent the elements of a higher-level problem defined over a so.called ground-CSP. Many known problems can be cast as meta-CSPs. For instance, a resource scheduling problem is a meta-CSP whose meta-variables are sets of possibly concurrent activities that over-consume a resource. These activities are themselves variables in a ground-CSP which decides their placement in time according to temporal constraints. The activities and temporal constraints are, respectively, the variables and constraints of the ground-CSP, while the sets of possibly overlapping and over-consuming activities are meta-variables in the meta-CSP. The constraints of the meta-CSP (meta-constraints) are the resources themselves. Solving a meta-CSP consists in finding values for the meta-variables such that no meta-constraint is violated. The values of meta-variables are ConstraintNetworks - i.e., variables and constraints which should be posted to the ground-CSP(s) in order to satisfy the meta-constraints. In resource scheduling for instance, a value of a meta-variable is a temporal constraint that eliminates the temporal overlap of the concurrent over-consuming activities. This class provides the fundamental mechanisms to define and solve a meta-CSP. It implements a backtracking search over the search space defined by meta-variables, meta-values and meta-constraints. Examples of concrete MetaConstraintSolvers that implement this class are given in this framework (e.g., the TCSPSolver, which implements a Temporal Constraint Satisfaction Problem solver as a meta-CSP, and the Scheduler, which implements the ESTA algorithm for solving resource scheduling problems). This class also provides limited support for constraint optimization through branch-and-bound.

Author:

Federico Pecora

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	MetaConstraintSolver.TerminalNode

Nested classes/interfaces inherited from class org.metacsp.framework.multi.MultiConstraintSolver

MultiConstraintSolver.OPTIONS

Field Summary

Fields

Modifier and Type	Field and Description
protected long	animationTime
protected boolean	breakSearch
protected int	counterMoves
protected FocusConstraint	currentFocus
protected MetaVariable	currentVertex
protected edu.uci.ics.jung.graph.DelegateForest<MetaVariable,ConstraintNetwork>	g
protected java.util.Vector<MetaConstraint>	metaConstraints
protected java.util.HashMap<ConstraintNetwork,MetaConstraint>	metaVarsToMetaCons
protected java.util.HashMap<ConstraintNetwork,ConstraintNetwork>	resolvers
protected java.util.HashMap<ConstraintNetwork,ConstraintNetwork>	resolversInverseMapping

Fields inherited from class org.metacsp.framework.multi.MultiConstraintSolver

constraintSolvers, ingredients

Fields inherited from class org.metacsp.framework.ConstraintSolver

autoprop, components, constraintTypes, IDs, logger, name, nesting, noPropOnVarCreation, numcalls, skipPropagation, spacing, theNetwork, variableType

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	MetaConstraintSolver(java.lang.Class<?>[] constraintTypes, long animationTime, ConstraintSolver... internalSolvers)

Method Summary

Modifier and Type	Method and Description
void	addMetaConstraint(MetaConstraint metaConstraint) Method to add a MetaConstraint to this meta-CSP solver.
protected boolean	addResolver(ConstraintNetwork metaVarConstraintNetwork, ConstraintNetwork resolverNetwork)
protected abstract boolean	addResolverSub(ConstraintNetwork metaVariable, ConstraintNetwork metaValue) Implement this method to define any additional operations that should happen before adding a meta-value in the meta-CSP search (e.g., when branching).
boolean	backtrack() Initiates CSP-style backtracking search on the meta-CSP.
boolean	branchAndBound() Perform branch-and-bound search for an optimal solution to this meta-CSP.
void	breakSearch() Interrupt the current meta-CSP search.
void	clearResolvers() Clear memory of all resolvers added to the ground-CSP(s) in order to obtain the current solution to the meta-CSP.
void	draw() Draws the search space of the meta-CSP.
void	failurePruning(int failure_time)
void	focus(Variable... vars)
ConstraintNetwork[]	getAddedResolvers() Get the final list of resolvers (meta-values) added to the ground-CSP(s) for obtaining a solution to the meta-CSP.
protected MetaVariable	getConflict()
ConstraintSolver[]	getConstraintSolvers() Get all the ground constraint solvers of this meta-CSP.
int	getCounterMoves()
FocusConstraint	getCurrentFocusConstraint()
java.lang.String	getDescription() Gets a description of this ConstraintSolver stating which variable and constraint types it supports.
Variable[]	getFocused()
java.util.HashMap<ConstraintSolver,Variable[]>	getGroundVariables() Get all the Variables of all ground solvers used by this MetaConstraintSolver.
protected abstract double	getLowerBound()
MetaConstraint	getMetaConstraint(ConstraintNetwork metaVariable)
MetaConstraint[]	getMetaConstraints()
java.util.HashMap<ConstraintNetwork,ConstraintNetwork>	getResolvers()
java.util.HashMap<ConstraintNetwork,ConstraintNetwork>	getResolversInverseMapping()
boolean	getTimeOut()
protected abstract double	getUpperBound()
protected abstract boolean	hasConflictClause(ConstraintNetwork metaValue)
boolean	isFocused(Variable var)
abstract void	postBacktrack(MetaVariable metaVariable) Implement this method to define any extra operations that should be performed after branching over a MetaVariable.
abstract void	preBacktrack() Implement this method to define any extra operations that should be performed before backtracking over a MetaVariable (and before it is even chosen).
boolean	propagate() Propagate the constraint network.
void	registerValueChoiceFunctions()
void	removeFromCurrentFocus(Variable... vars)
protected abstract void	resetFalseClause()
protected void	retractResolver(ConstraintNetwork metaVar, ConstraintNetwork res)
void	retractResolvers() Retract all resolvers added to the ground-CSP(s) in order to obtain the current solution to the meta-CSP.
protected abstract void	retractResolverSub(ConstraintNetwork metaVariable, ConstraintNetwork metaValue) Implement this method to define any extra operations that should happen after retracting a meta-value in the meta-CSP search (e.g., when backtracking).
void	setCounterMoves(int counterMoves)
void	setCurrentFocusConstraint(FocusConstraint focus)
void	setFocus(Variable... vars)
protected abstract void	setLowerBound()
void	setResolvers(java.util.HashMap<ConstraintNetwork,ConstraintNetwork> resolvers)
protected abstract void	setUpperBound()

Methods inherited from class org.metacsp.framework.multi.MultiConstraintSolver

addConstraintsSub, createVariablesSub, createVariablesSub, createVariablesSub, drawConstraintNetworkHierarchy, drawConstraintSolverHierarchy, getConstraintNetworkHierarchy, getConstraintNetworksFromSolverHierarchy, getConstraintSolver, getConstraintSolverHierarchy, getConstraintSolversFromConstraintSolverHierarchy, getOption, removeConstraintsSub, removeVariablesSub, setConstraintSolver, setIngredients, setOptions

Methods inherited from class org.metacsp.framework.ConstraintSolver

addConstraint, addConstraintNoPropagation, addConstraints, addConstraintsDebug, addConstraintsNoPropagation, containsVariable, createVariable, createVariable, createVariables, createVariables, deplenish, getComponent, getComponents, getConstraintNetwork, getConstraints, getConstraints, getID, getOption, getVariable, getVariables, getVariables, getVariables, isCompatible, maskConstraints, removeConstraint, removeConstraints, removeVariable, removeVariables, setComponent, setComponents, setConstraintNetwork, setName, setOptions, toString, unmaskConstraints

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

metaConstraints

protected java.util.Vector<MetaConstraint> metaConstraints

g

protected edu.uci.ics.jung.graph.DelegateForest<MetaVariable,ConstraintNetwork> g

currentVertex

protected MetaVariable currentVertex

breakSearch

protected boolean breakSearch

metaVarsToMetaCons

protected java.util.HashMap<ConstraintNetwork,MetaConstraint> metaVarsToMetaCons

resolvers

protected java.util.HashMap<ConstraintNetwork,ConstraintNetwork> resolvers

resolversInverseMapping

protected java.util.HashMap<ConstraintNetwork,ConstraintNetwork> resolversInverseMapping

animationTime

protected long animationTime

counterMoves

protected int counterMoves

currentFocus

protected FocusConstraint currentFocus

Constructor Detail

MetaConstraintSolver

protected MetaConstraintSolver(java.lang.Class<?>[] constraintTypes,
                               long animationTime,
                               ConstraintSolver... internalSolvers)

Method Detail

getMetaConstraints

public MetaConstraint[] getMetaConstraints()

getAddedResolvers

public ConstraintNetwork[] getAddedResolvers()

Get the final list of resolvers (meta-values) added to the ground-CSP(s) for obtaining a solution to the meta-CSP.

Returns:

List of resolvers that were added to obtain the solution of the meta-CSP.

retractResolvers

public void retractResolvers()

Retract all resolvers added to the ground-CSP(s) in order to obtain the current solution to the meta-CSP. This is useful if one wants to "reset" the meta-CSP to its original unsolved state.

clearResolvers

public void clearResolvers()

Clear memory of all resolvers added to the ground-CSP(s) in order to obtain the current solution to the meta-CSP. This is useful if one wants to restart solving from the current solved state. Note that resolvers are not retracted - to "reset" the meta-CSP to its original unsolved state, use method retractResolvers().

addMetaConstraint

public void addMetaConstraint(MetaConstraint metaConstraint)

Method to add a MetaConstraint to this meta-CSP solver.

Parameters:

metaConstraint - The MetaConstraint to add.

getConflict

protected MetaVariable getConflict()

preBacktrack

public abstract void preBacktrack()

Implement this method to define any extra operations that should be performed before backtracking over a MetaVariable (and before it is even chosen).

postBacktrack

public abstract void postBacktrack(MetaVariable metaVariable)

Implement this method to define any extra operations that should be performed after branching over a MetaVariable.

Parameters:

metaVariable - The MetaVariable that has been branched upon.

backtrack

public boolean backtrack()

Initiates CSP-style backtracking search on the meta-CSP.

Returns:

true iff a set of assignments to all MetaVariables which satisfies the MetaConstraints was found.

getTimeOut

public boolean getTimeOut()

addResolver

protected final boolean addResolver(ConstraintNetwork metaVarConstraintNetwork,
                                    ConstraintNetwork resolverNetwork)

retractResolver

protected final void retractResolver(ConstraintNetwork metaVar,
                                     ConstraintNetwork res)

propagate

public boolean propagate()

Description copied from class: ConstraintSolver

Propagate the constraint network.

Specified by:

propagate in class MultiConstraintSolver

Returns:

A boolean value indicating whether propagation was successful.

retractResolverSub

protected abstract void retractResolverSub(ConstraintNetwork metaVariable,
                                           ConstraintNetwork metaValue)

Implement this method to define any extra operations that should happen after retracting a meta-value in the meta-CSP search (e.g., when backtracking).

Parameters:

metaVariable - The MetaVariable over which backtracking occurs.

metaValue - The meta-value that has been retracted.

addResolverSub

protected abstract boolean addResolverSub(ConstraintNetwork metaVariable,
                                          ConstraintNetwork metaValue)

Implement this method to define any additional operations that should happen before adding a meta-value in the meta-CSP search (e.g., when branching).

Parameters:

metaVariable - The MetaVariable over which the search is branching.

metaValue - The meta-value that has been selected (the branch).

Returns:

true iff the metavalue is consistent with the ground-CSP (Note: if false is returned, the ground-CSP has not been changed, i.e., it is left in a consistent state.)

getGroundVariables

public java.util.HashMap<ConstraintSolver,Variable[]> getGroundVariables()

Get all the Variables of all ground solvers used by this MetaConstraintSolver.

Returns:

The list of variables for each ground solver.

draw

public void draw()

Draws the search space of the meta-CSP.

getConstraintSolvers

public ConstraintSolver[] getConstraintSolvers()

Get all the ground constraint solvers of this meta-CSP.

Overrides:

getConstraintSolvers in class MultiConstraintSolver

Returns:

All ground constraint solvers of this meta-CSP.

breakSearch

public void breakSearch()

Interrupt the current meta-CSP search.

branchAndBound

public boolean branchAndBound()

Perform branch-and-bound search for an optimal solution to this meta-CSP. The cost of assignments is defined in the implementing class through the upper/lower-bound getter and setter methods.

Returns:

true iff IRAN: complete this please!

getUpperBound

protected abstract double getUpperBound()

setUpperBound

protected abstract void setUpperBound()

getLowerBound

protected abstract double getLowerBound()

setLowerBound

protected abstract void setLowerBound()

hasConflictClause

protected abstract boolean hasConflictClause(ConstraintNetwork metaValue)

resetFalseClause

protected abstract void resetFalseClause()

getDescription

public java.lang.String getDescription()

Description copied from class: ConstraintSolver

Gets a description of this ConstraintSolver stating which variable and constraint types it supports.

Overrides:

getDescription in class MultiConstraintSolver

Returns:

A description of this ConstraintSolver stating which variable and constraint types it supports.

failurePruning

public void failurePruning(int failure_time)

Overrides:

failurePruning in class MultiConstraintSolver

getCounterMoves

public int getCounterMoves()

getCurrentFocusConstraint

public FocusConstraint getCurrentFocusConstraint()

setCurrentFocusConstraint

public void setCurrentFocusConstraint(FocusConstraint focus)

getFocused

public Variable[] getFocused()

setFocus

public void setFocus(Variable... vars)

isFocused

public boolean isFocused(Variable var)

focus

public void focus(Variable... vars)

removeFromCurrentFocus

public void removeFromCurrentFocus(Variable... vars)

setCounterMoves

public void setCounterMoves(int counterMoves)

getResolvers

public java.util.HashMap<ConstraintNetwork,ConstraintNetwork> getResolvers()

getResolversInverseMapping

public java.util.HashMap<ConstraintNetwork,ConstraintNetwork> getResolversInverseMapping()

setResolvers

public void setResolvers(java.util.HashMap<ConstraintNetwork,ConstraintNetwork> resolvers)

getMetaConstraint

public MetaConstraint getMetaConstraint(ConstraintNetwork metaVariable)

registerValueChoiceFunctions

public void registerValueChoiceFunctions()

Overrides:

registerValueChoiceFunctions in class MultiConstraintSolver