Reconfiguration is an important aspect of industrial product configuration. Once an industrial artefact has been built according to an initial configuration, constant reconfigurations are necessary during its lifetime due to changed requirements or a changed product specification. This reconfigurations should affect as few parts of the running system as possible. Due to the large number of involved components, approaches based on optimization are often not usable in practice. This paper introduces a novel approach for reconfiguration based on a replay heuristic (the product is rebuilt from scratch while trying to use as many decisions from the legacy configuration as possible) and describes its realisation using the standard solving technologies Constraint Satisfaction and Answer Set Programming.
Configuration is the task of deriving a valid, complete and purposeful
system structure assembled from a set of components [
M4 M3 M2 M1
M3 is a generic specification of the problem domain. In an objectoriented environment, this would be the class model. Constraints are usually used to describe the different dependencies and restrictions between the different objects. Such a model M3 defines the space of all the technically feasible configuration solutions. Model M2 is a concrete problem instance, containing specific requirement definitions which are usually formalized in terms of constraints, initial configuration objects and requirement and resource parameters. M2 is based on M3 and uses its language and concepts (M4). Finally, M1 - a configuration - consists of all the instances, their properties and (a) The problem domain M3 has been changed. Reasons could be changes in the product catalogue, changes in the structure of the product line, regulation changes, etc. A legacy configuration already installed in the field may be inconsistent now to the new problem domain description and must be reconfigured. (b) The requirements in M2 has been changed or extended. Again, a legacy configuration which is inconsistent now w.r.t. the changed requirements must be adapted. (c) A configuration (M1) has been changed by an external process (e.g. by a manual user input or by reading a configuration from an external repository) and is now inconsistent. Again, reconfiguration must find a consistent modification of the configuration.
In all these cases, a crucial demand is that the reconfigured solution is as close as possible to the original configuration. The definition of the quality of a reconfiguration (How close is the new configuration to the legacy configuration?) could get quite subtle. [Friedrich et al., 2011], e.g., use cost functions for the different change operators. Reconfiguration is then the problem of minimizing the overall modification costs. In this paper, we are using a more light-weight approach: We don’t define cost functions but use a rather heuristic and simple definition of minimality: the number of differences between the original and the reconfigured solution should be as small as possible. This corresponds to equal cost values for all types of modifications.
We present methods how such reconfiguration problems can be modelled and solved by variations of standard, complete solving techniques (like SAT solving or backtracking). A challenge here is that reconfiguration starts with an inconsistent configuration fragment and standard solving (e.g. backtracking) would immediately return a failure result. Our idea is to start solving from scratch, but trying to re-build the search tree following the decisions of a given (inconsistent) legacy configuration. That’s why we call it replaybased reconfiguration. The composition of a reconfiguration will deviate from the legacy configuration in cases where inconsistencies are to be avoided.
Our main contributions in this work are: (1) An Answer Set
Programming (ASP) encoding of the reconfiguration problem using the
special predicate heuristic of clingo (Potassco [
The rest of the paper is organized as follows: Section 2 sketches a small hardware configuration problem which will serve as example for the subsequent sections. Section 3 describes how the task of reconfiguration can be modelled and solved in 2 different frameworks: ASP and standard CSP. We compare and evaluated these techniques in Section 4 and conclude the work with a discussion of related works and a conclusion. 2
A small example from the domain of railway interlocking hardware should demonstrate the dynamics of the configuration problems we want to model and solve. Of course, real-world problems are much larger and the object network and dependencies between the objects are more complex and varied.
Figure 2 shows the UML diagram and represents the problem domain M3 (cf. Table 1). A part of configuring an interlocking system is to create appropriate control modules for each outdoor element (e.g., a signal or a switch point) and to place them into the right slots of a frame, which in turn must be inserted into a rack. At the beginning, only the outdoor elements are known. Racks, frames and modules must be created during solving. In our example tracks require modules of type ’ModuleA’ and signals require modules of type ’ModuleB’.
A concrete problem instance is defined by a set of outdoor elements of different kinds (model level M2). The goal is to find the right set and constellation of racks, frames, and modules, such that each element is connected to exactly one module. Of course, we aim for a minimal set of hardware. Additionally, various types of constraints restrict the allowed constellations. Typical examples of such constraints are: Some types of models should not be mixed within a frame. Certain types of modules must not be mounted on neighbouring places in the frame.
It shall be noted that for a concrete problem instance on model level M2, it is not known beforehand how many racks, frames, and modules are needed for a valid solution on model level M1. This is why such kinds of problems are called dynamic problems in contrast to static problems. 3
According to Fig. 1, inputs to the reconfiguration solver are the problem descriptions M3’ and M2’, and the legacy configuration M1’.
Output is M1” which should be consistent w.r.t. M3’ and M2’ and as close as possible to M1’.
The basic of idea of our reconfiguration approach is to influence a solver to search in the neighbourhood of the legacy configuration. This is achieved by defining a heuristic for the solver to choose for every decision the same value that has been used in the legacy configuration, whenever possible. In a way this reconstruct the search tree which was built creating the legacy configuration. Deviations from that search tree should only happen when previously consistent choices are inconsistent now.
Our approach will perform poorly, if there is no consistent configuration close to an inconsistent legacy configuration. But the approach will perform well if only a small percentage of the overall configuration is modified during reconfiguarion, which is the case in most reconfiguration scenarios in practice especially for large configurations. E.g., from our experience in the rail automation domain, most system modifications are only very local changes in the outdoor installation.
To show that our approach is applicable to different solving paradigms we implemented it in two standard AI technologies, answer set programming (ASP) and constraint satisfaction (CSP).
For the ASP implementation we used Potassco’s clingo which allows to define domain specific heuristics within ASP with a special predicate heuristic. With this predicate the solver can be influenced to prefer certain atoms during solving. By giving the legacy configuration as preferred heuristic facts we achieve a kind of replay of the original configuration. Details are described in Chap. 3.1.
CSP systems often are more open to adaptations of the search procedure than ASP solvers. For our experiments, we used Choco which allows to plug in your own variable and value ordering heuristics used during backtrack search. We wrote variable and value ordering heuristics which prefer the decisions of the legacy configuration. Details are described in Chap. 3.2.
We chose Potassco and Choco for our experimental implementations because they are well recognized implementations of ASP and CSP technology. Potassco is very fast and regularly wins competitions. Choco is a standard constraint solver in Java. Most likely there are CSP systems with better performance, but we belief that all solvers based on a backtracking scheme suffer from the same fundamental behaviour of sometimes running into heavy backtracking as shown in our evaluation (cf. Sec. 4).
ASP is a declarative problem solving approach, which originated in
the area of knowledge representation and reasoning [
"position","integer"). ooasp_attribute_minInclusive("hw","Module", "position",1). ooasp_attribute_maxInclusive("hw","Module", "position",5). ooasp_assoc("hw","Module_element", "Module",1,1, "Element",1,1). ooasp_assoc("hw","Rack_frames", "Rack",1,1, "Frame",0,4).
In a similar manner the predicates ooasp isa, ooasp attribute value and ooasp associated are used to define (partial) configurations i.e. instantiations of the object-model.
One standard reasoning task of OOASP is to complete a partial configuration i.e. to add components to the partial configuration until all constraints of the knowledge base are satisfied. For example given a partial configuration consisting only of one track (represented by the fact ooasp isa("c"; "T rack"; "A1")), completing a configuration will return all configurations containing one track, with at least one module of type A, one frame and one rack. 3.1.1 Heuristic reconfiguration Given an inconsistent legacy configuration the default reconfiguration reasoning task in OOASP finds a valid configuration that is cheapest in terms of some user defined cost function. The costs can be either domain-specific or cardinality based. The cardinality based cost function simply counts the difference (in number of facts) of the legacy configuration and the reconfigured configuration. This default reconfiguration task in OOASP is implemented using ASP optimization statements. Unfortunately it has a bad performance for large problem sizes due to the large number of possible configurations. This was one of the motivations for developing a novel approach to reconfiguration with OOASP based on heuristics.
Heuristic reconfiguration for OOASP
described in this paper uses the special predicates
heuristic(AT OM; T RUT HV ALUE; LEV EL) from
[
To implement our heuristic approach we add the facts describing the legacy configuration as heuristics facts heuristic(F ACT F ROMLEGACY; true; 1) to the ASP program and run the default OOASP configuration task with this heuristic information. This way the ASP solver is expected to find configurations that are close (cardinality based) to the legacy configuration first.
For example given the heuristic information below the ASP solver will try to assign track A1 first to the module M1 and set its position to 4. % user supplied fact ooasp_isa("c","Track","A1") % legacy configuration converted to heuristic _heuristic( ooasp_isa("c","ModuleA","M1"), true,1). _heuristic( ooasp_attribute_value( "c", "position", "M1",4), true,1). _heuristic( ooasp_associated( "c", "Module_element", "M1","A1"), true,1). ...
The encoding of a dynamic problem with a standard constraint
formalism (like MiniZinc2 or Choco3) makes it necessary to define a
maximum number of instances of each object type. If, e.g., we allow
at most 5 racks for our example problem in Section 2, the maximum
numbers of instances for the other types can be computed by
cardinality propagation: 20 frames, 320 modules and 320 elements. For
complex networks of classes, this cardinality propagation is not
trivial [
We briefly sketch here the CSP encoding of configuration problems we used in our implementation. We use a pseudo code notation,
which could directly be translated to a concrete CSP notation (e.g. Choco). To represent the instances of a class, we use an array of boolean variables representing which element is actually used in a solution and which not. E.g., let r be that variable array for the class Rack. nr be the maximum number of racks.
ri 2 f0; 1g;
8i 2 f1; :::; nrg
The following symmetry breaking constraints states that unused instances are always in the rear part of the array: ri = 0 ! rj = 0;
8i;j 2 f1; :::; nrg; i < j
Attribute encoding is straight-forward. For each possible instance of a class, a CSP attribute variable is used. E.g., attribute modulePos of modules is represented by the variable array mp (let nm be the maximum number of modules): mpi 2 f 1; 1; :::; 16g; 8i 2 f1; :::; nmg
We provide a special attribute value (-1 for mp) for attributes of unused components. The following constraint states that unused components must have this special value, and used components must have a value from the regular domain of the attribute.
mi = 0 $ mpi = 1; 8i 2 f1; :::; nmg
The interesting part of the model is the encoding of associations.
A very general approach is to represent each association by a
matrix of boolean variables on the instances of the two involved classes.
A matrix entry mij = 1 means that object with index i is
associated to object with index j. This representation needs a lot of CSP
variables and makes the formulation of consistency constraints on
associations quite intricate, causing low solving performance.
Another approach [
We use a simpler representation: For a 1:n-association, we use a variable array on the n side of the association. Each such variable points to the associated object, or has value -1, if not connected. Example: The association
j ff rj j j 2 f1; :::; nf g; f rj = i g j 4; 8i 2 f1; :::; nrg
Example for a constraint on attributes and associations: All modules in a frame must have different module positions: mfi = mfj ^mfi 1 ! mpi 6= mpj ; 8i;j 2 f1; :::; nmg; i < j
It should be noted that such object-constraint mapping on dynamic problems (where the number of instances in a solution is not known beforehand) has many disadvantages: (1) The representation of objects as a flat set of constraint variables is very unnatural and hard to read, debug, and maintain. This can be mitigated by an automatic translation from objects to constraints. (2) A maximal set of possible object instances must already be provided at problem formulation. Decisions on maximum values are in general not easy; too few objects could rule out possible solutions; too many objects blows up the problem size. (3) Current constraint solvers (mainly based on backtracking) are very sensitive to changes. Small changes in the variable structure or of the constraints could hugely influence solving performance, which makes a repeated tuning of the variable and value ordering heuristics necessary. (4) The representation of associations is crucial. A simple representation, as described above, does not directly support n:m associations and ordered associations. More elaborate encodings are difficult to handle in terms of constraint formulations, and often impair performance. (5) Modelling of inheritance additionally increases representation complexity. (6) Attributes of more complex types, like reals, multi-valued variables, or strings, are often not supported at all in constraint systems.
To formalize reconfiguration in terms of standard CSP, we first need to define a metric to have a notion of the distance between a legacy configuration and a reconfigured solution. Let (V; D; C) be a CSP with variables V , their domains D, and constraints C. An assignment is a tuple (v; d), v 2 V , d 2 Dv, representing the assignment of value d to variable v. Let A be a set of assignments. vars(A) is the set of variables in A: vars(A) = fv j (v; d) 2 Ag. vars(A1; A2) is the set of variables both in A1 and A2: vars(A1; A2) = fv j v 2 vars(A1); v 2 vars(A2)g. di (A1; A2) is the number of assignments with different values on the common variables in A1 and A2: is represented as an integer variable f r for each frame: di (A1; A2) = j fv j v 2 vars(A1; A2); f ri 2 f 1; 1; :::; nrg; 8i 2 f1; :::; nf g
The special value -1 is used if a frame is not associated to a rack at all. This special value is also used for unused frames. fi = 0 ! f ri = 1; 8i 2 f1; :::; nf g
Additional consistency constraints are needed to rule out invalid association constellations. Each used frame must be connected to a rack: fi = 1 ! f ri 2 f1; :::; nrg; 8i 2 f1; :::; nf g
f ri 1 ! rfri = 1; 8i 2 f1; :::; nf g
(v; d1) 2 A1; (v; d2) 2 A2; d1 6= d2g j di defines a simple metric on the space of all assignment sets of a CSP. The CSP reconfiguration problem can now be simply defined as follows: Let (V; D; C) be a CSP. Let A be an assignment on V or a subset on V . A is potentially inconsistent w.r.t. the constraints C. A reconfiguration A0 is a consistent assignment on the variables V (i.e., A0 is a solution of the corresponding CSP) which minimizes di (A; A0).
Reconfiguration can be simply implemented by slightly changing the backtracking search procedure. We can’t start with the legacy configuration (a variable assignment), because it is potentially inconsistent and standard backtracking would stop with output failure immediately. But we could solve the problem from scratch and use the legacy configuration to guide expanding the search tree. Each time when a value for the current variable is selected, the value of the legacy configuration - if an assignment tuple for that variable is 4.1
Figures 3 and 4 show the solving time results for our ASP and CSP implementations. The x-axis shows the different problem sizes in terms of number of Elements. Note that the number of objects in a configuration solution is far higher than these values, because all the HW elements (racks, frames, modules) and internal variables are created during solving. The y-axis shows the solving execution time in seconds. For ASP, this is the sum of grounding and SAT solving time.
We incremented the problem size, i.e. the number of Elements, in steps of 10. We generated 40 different configurations per problem size, modified them randomly and solved the reconfiguration problem. Black circles in the plots are the measured times for each run. Blue squares are the mean runtime values for that problem size. Red triangles indicate timeouts (time > 2 minutes).
(3%) (8%) (55%) data point mean value timeout data point mean value timeout part of the legacy configuration - is preferably chosen. Of course, if that value is inconsistent with the current constellation, an alternative value is taken. But basically, the legacy configuration is replayed, and changes are made only because of inconsistent states. The result is a consistent configuration which is very similar to the legacy configuration, which is exactly what we want - we want minimal reconstruction of the system in the field.
A brief note on our implementation: We used the constraint solver Choco V3.2.2 to represent and solve configuration problems (as described in the first part of this subsection) and replay-based reconfiguration. Choco allows to plug in your own value selector by implementing the interface IntValueSelector. With only a few lines of code, we extended the standard value selector of Choco by preferring the values stored in a given legacy configuration. If a legacy value for the current variable is not available or inconsistent, standard Choco value selection is used.
Advantages: (1) This method is light-weight, i.e., no additional modelling concepts (like cost functions) are needed. Changes in the existing backtracking search procedures are minimal. (2) Most of the existing backtracking algorithms (intelligent backtracking, etc.) and variable and value ordering heuristics can still be used with only minimal adaptations. (3) Replay-based reconfiguration can be applied to inconsistent configuration fragments, which is not the case for standard backtracking and consistency algorithms. (4) The method is complete (a solution is found, if one exists).
Disadvantages: (1) It is not guaranteed, that a solution with minimal changes is found. The quality of the solution depends on the variable/value ordering heuristics used. Nevertheless, results of our prototypical implementation have shown, that the reconfiguration solutions are often the optimum or very close to the optimum. (2) Replaying an inconsistent configuration may lead search into inconsistent branches which may heavily impair performance. (3) The approach is suited only for domains where a cardinality based cost function is applicable, e.g. homogeneous hardware configuration problems. 4
We did experimental evaluations on our ASP (cf. Section 3.1) and CSP (cf. Section 3.2) implementations using randomly generated problem instances for the example problem domain sketched in Fig. 2. We ran the tests on a standard Windows 7 machine with a Intel dual-core i5 CPU and 8 GB RAM. We used clingo V4.4.0 from the Potassco suite for the ASP implementation, and Choco V3.2.2 for the CSP implementation.
It should be mentioned that we intentionally didn’t use a highperformance hardware setting and we did not do any coding optimizations. Of course, ASP and CSP experts could find encodings which would perform better, but we wanted to test if AI techniques like ASP and CSP could be used by engineers with just standard skills in these techniques.
The input values for our HW configuration problem are the number and types of Elements. We generated randomly a set of input problem instances, solved them, made random changes to the solutions and applied the heuristic replay-based solvers (both ASP and CSP) to solve the reconfiguration problem. We measured solving time, memory consumption, and quality of the reconfiguration solution (i.e., how close is the result to the original configuration).
It should be mentioned that integration of reasoning functionality into our configuration infrastructure – an object-oriented data model and environment implemented in Java – was easier with Choco than with clingo, because Choco provides a Java API.
ASP is much more robust than CSP. For problems up to a size of ca. 90 Elements ASP finds a solution in a well predictable time. In contrast, CSP often needs a lot of time even for small problems and very often runs into timeout.
Consequently, the sizes of problems where ASP finds a solution in acceptable time is also well predictable. In our test environment, ca. 100 Elements are the upper limit for ASP.
CSP is much more sensitive to the input problem constellation. If the backtracking procedure makes invalid choices in the first part 150 ) c (se 100 e m it ilgvn 50 o S
0 ) 100 c e s ( e m tign 50 il v o S 0 10 20 30 40 50 60 70 80 90
Problem size (#input elements) of the search tree, backtracking gets out of hand. This is why CSP runs very often into timeout even for small problem sizes. In cases without or with little backtracking, CSP is very fast, even for large problems.
If one is willing to tune the variable and value ordering heuristics for her/his specific problem instance, CSP can solve much bigger problems than ASP very efficiently. The key is to avoid backtracking.
The variance of runtime continuously grows with problem size for ASP. This is not the case for CSP. If CSP manages to solve the problem, it can do it most of the time very quickly. For the solvable problem sizes, there is rarely a difference in the CSP runtimes depending on the size of the input variables. 4.2
For all the test cases, we also measured indicators for memory consumption (cf. Fig. 5). For ASP, we used grounding size in MBytes. For CSP, we counted the number of CSP variables used. Note that, aside from user-defined variables (cf. Section 3.2), Choco creates a lot of additional, internal variables. Of course, grounding memory size for ASP and numbers of variables in CSP cannot be compared directly, but they give good indicators about the memory growth rate depending on the input configuration size.
10 20 30 40 50 60 70 80 Problem size (#input elements) 10 20 30 40 50 60 70 80 Problem size (#input elements)
Not surprisingly, memory of both ASP and CSP grows with accelerated speed depending on the problem size. ASP grows with a slightly higher rate. Not only in the context of reconfiguration, ASP often shows its limits at grounding. Most of the execution time and a big amount of memory is used for grounding.
To give estimations of consumed memory for CSP is a bit more subtle. As shown in Fig. 5(b), we used the number of variables as memory indicator. A rough memory profile using Choco’s statistics functionality has shown, that for 100,000 variables ca. 20 MByte RAM is consumed (for the cases without heavy backtracking). This means that CSP’s footprint is roughly 20 times smaller than ASP’s footprint. 4.3
To evaluate the quality of a reconfiguration we measured the distance of the original, legacy configuration to the reconfigured solution. We used a graph-based difference metric counting the differences in the rack/frame/module constellation of the legacy configuration to the reconfiguration.
The first and simplest case is to provide a legacy configuration which is already consistent. This means that a reconfiguration should reproduce the legacy configuration without any changes. Both ASP and CSP did this in many test cases of various sizes.
The more interesting case is a legacy configuration which is inconsistent to the problem description. For each problem size (starting from 10 Elements up to 80 Elements in steps of 10), we randomly modified up to 20% of a valid configuration. For each problem size, we did 40 different tests.
ASP CSP 10 20
30 40 50 60 Problem size (#input elements) 70 80
The results are shown in Fig. 6. ASP most of the time finds solutions of high quality. In fact, for smaller problem sizes we could manually verify that ASP nearly all the times finds the optimal solution. With CSP, the mean distance to the legacy configuration is a bit higher than with ASP, but has an acceptable quality on most of the cases. 4.4
Table 2 gives a summarized comparison of our ASP and CSP reconfiguration encodings and the results of our experimental evaluations. For solving placement problems like our hardware example, there is no clear winner. If the problem is of moderate size, ASP provides a sound, predictable and easy-to-use reasoning functionality. For larger problem, CSP may be better, but probably additional coding is needed for tuning search. 5
Related to our work presented in this paper are all techniques for finding a valid reconfiguration for a given, possibly inconsistent configuration (fragment). The main research approaches are:
Repair-based approaches. Repair-based approaches aim for
finding diagnoses and repairs to conflicting requirements or
constraints [
Minimization of modification costs. The basis of these approaches
is the definition of cost functions for the different modification
operations [
Rule-based approaches. Especially in model-driven engineering,
a lot of research in model synchronization has been done and is still
on-going. Correspondences between two models are defined as
transformation rules, describing how values from one model are mapped
to another model. Examples of such systems are triple graph
grammars [
Common to all these approaches – at least to a certain degree – is that reconfiguration actions are modelled on a declarative level. The specification of potential modification operations and reconfiguration reasoning are separated. Another approach used in industry (e.g. in factory facilities, steel plants) is to offer upgrade or modernization packages. There the focus lies on finding and recommending modernization packages which are appropriate to add functionalities to a system in the field. 6
There is no standard way of doing reconfiguration for product configuration especially for large problem sizes. In this paper we showed the implementation of a heuristic approach to reconfiguration using standard solving techniques and the applicability up to moderate problem sizes. The main challenge for using these techniques in an industrial setting are grounding size and solving time. Grounding size typically can be influenced by finding a better encoding or by problem decomposition. Solving time is also influences by the encoding of the problem and by finding the right heuristic for the domain.
Because of the heterogeneous nature of the constraints in product configuration coming up with a good encoding and heuristics for a problem is currently as much an art as a science and requires an experienced knowledge engineer. Also it requires experiments with different solving paradigms as SAT, ASP, CSP, MIP etc. Therefore we welcome the further integration of AI and OR solving techniques that have taken place in the last years as we believe there will not be THE solving technique for product (re-)configuration in the foreseeable future.
For the future we plan to further study and improve heuristic
reconfiguration solving techniques and to apply them to fields beyond
product configuration. As we have seen in our experiments, CSP
solving – though it is very fast and produces good results if it doesn’t
fall into a heavy backtracking trap – currently isn’t robust enough to
be applied in an industrial environment. We believe that the
integration of additional heuristics which are automatically derived from the
problem domain or techniques like lazy clause generation [
Interesting fields beyond product configuration, where reconfiguration methods could be applied, are:
Production configuration: With the increasing demand for
individualized products, the need for flexible production processes,
modular factories and intelligent production infrastructures is also
increasing. Factories of the future are generic production
facilities, that can be easily adapted to the needs of the product to be
manufactured [
Case-based reasoning: In case-based reasoning, a database of
solutions from previous problems are used to find a solution to a new
problem [
This work has been funded by the Vienna Business Agency in the programme ZIT13-plus within the project COSIMO (Collaborative Configuration Systems Integration and Modeling) under grant number 967327, and by FFG FIT-IT within the project HINT (Heutistic Intelligence) under grant number 840242. 80