DragonBreath An Optimization Engine based on Constraint Programming and Local Search |
[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Internal Structure]
[General Approach] [Docking Graph] [Test Graph] [Graph Repair]
In this section the general approach used to solve SCSPs is presented. It introduces requirements for an implementation of structural constraint satisfaction.
The whole DragonBreath engine was developed under the paradigm of Using Global Constraints for Local Search. Accordingly the structural constraint satisfaction should also follow this path, as it is described in Applying Local Search to Structural Constraint Satisfaction. If you do not know the concepts of structural constraints and what a docking graph or a test graph is please read the second referenced text.
Each structural constraint consists of one docking graph and several test graph. As a working concept structural constraint instances are introduced, they speed up the search process. Each instance represents one found isomorphism (a match) of the docking graph into the CSP graph. With every change of the CSP graph the structural constraints have to be updated.
Requirements:
For each found docking graph at least one of the test graphs also have to be found for the constraint to be fulfilled. We do not only want to check whether the constraint is fulfilled or not, but also search for a solution for the SCSP. Therefore we have to repair the graph, so that the test graph can be found.
For conventional constraint satisfaction the level where the search takes place is the one of the constraints. For each constraint exists a heuristic that changes locally the values of the variables the constraint restraints. A combination of the local changes leads to a globally correct CSP.
In the case of structural constraints the parts of the problem that are restraint by a constraint are not variables but all those places in the CSP graph where the docking graph, i.e. an instance of the structural constraint was found. To repair said place one of the test graph has to be created there. It may happen that different instances of the same constraint require contradictory changes of the CSP graph. But we do not want to repair the CSP graph globally, not even in regard of one single structural constraint. We want to perform only local changes. Therefore the repair is not conducted at the level of structural constraints but at the one of the structural constraint instances.
As a CSP graph is not planar it is not imediately clear what local means. The locallity is required to disturb as few other constraints as possible during repair. So we can define a pseudo locallity by trying to interfere with as few other constraints as possible. That can be done by testing each planned change of the graph for interference with the other constraint instances, and perform it only if it doesn't interfere or is inevitable.
A graph that fulfills one instance is reached if either the docking and the test graph can be found, or if the docking graph can not be found, in which case the instance is destroyed. When for all constraint instances the graph is locally correct the whole structural constraint is fulfilled. If more then one structural constraints exist the sum of changes of the single constraints lead to a graph that is correct in total.
The repair measures of the different constraint instances may be contradictory. So there must be a stochastic element in the search to circumvent local maxima and plateaus introduced by the local search.
Part of the concept of global constraints for local search is that for each constraint a special repair heuristic can be defined. That way special knowledge about the problem can be incorparated in the search process. The same should also be possible for structural constraints, so the repair process has to be customizable.
We need a method of fulfilling the CSP graph for a single structural constraint instance. The easiest way of doing that is by using a simple gradient descent. Therefore we need a greedy criteria which evaluates the graph in the adjacency of the constraint instance. All the changes by the repair should be kept local local.
Requirements:
As the DragonBreath engine should be used to solve realtime problems the search for a solution should be as fast as possible.
It should be possible to load the definition of a strucutral constraint from an XML-file.
First all instances of all structural constraints have to be found. Then they have to be checked via their test graphs. Once all structural errors are determined they have to be repaired.
For the structural repair each instance is repaired locally. That is achieved via a gradient descent. To perform the gradient descent a greedy critaria is needed. Locallity is achieved by testing the repair steps for interference with other constraint instances.
Requirement 3 makes it necessary that all the changes of the CSP graph are communicated to all existing structural constraints
and their instances to update the matchings.
The CSP graph is managed in the GlobalSearchControl.
So there has to be an interface between the GlobalSearchControl and the structural constraints. To decouple the
structural constraint handling and the normal CSP graph handling this is done via
a special StructuralConstraintManagement class, that provides a interface to the structural constraint functions.
StrukturalConstraintManagement
All communication between GlobalSearchControl and the structural constraints takes place via this class. That includes graph changes and graph repair and loading and storage of structural constraints. With each graph change the GlobalSearchControl calls registerDeletedNode(), registerExpandedNode(), registerNewNode() or registerReducedNode() to register the changes.
As normally several changes appear at once, the overhead of testing each single change immediately when it was performed, is too big. Instead there is an explicit function checkStructuralConstraints() in the StrukturalConstraintManagement which initiates the check of all changes since it's last call.
Each structural constraint can be devided into the type and the instances. The type holds the data necessary for finding the instances. Normally an the type of a structural constraint does not need any knowledge about the test graphs. But as the constraint instances only appear when the docking graph was found the general structure of the test graphs has to be stored somewhere. The obvious place is the constraint type, which is known to all it's constraint instances. Thereby the strucure of the test graphs only has to be stored once and can be used by all instances.
Once an instance is found the test graphs have to be checked. Each test graph check has to be done in regard of the instance's position. Each StructuralConstraintInstance contains the concrete match of the docking graph and the test graph. That makes the instance the best place to initiate the update of these graphs. That is done via the checkChangedNodes() function.
To decouple the concrete test and docking graph implementation from the constraint instance and type a factory procuces the two graph types. It is also a intermediary between the graph saved in XML and the concrete graph as an object structure. (Requirement 13)
Encapsulate strategies to repair the test respectively the docking graph. That makes the repair mechanism exchangable (Requirement 9).
A sequence diagramm of a typical node change check is displayed in the following pictures.
[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Internal Structure]
[General Approach] [docking graph] [Test Graph] [Graph Repair]
For questions, comments or suggestions, please visit our feedback forum.
Last update:
May 09, 2003 by Tim Baermann