=Paper= {{Paper |id=Vol-1453/12_HaselboeckSchenner_AHeuristic,Replay-BasedApproach_Confws-15_p73 |storemode=property |title=A heuristic, replay-based approach for reconfiguration |pdfUrl=https://ceur-ws.org/Vol-1453/12_HaselboeckSchenner_AHeuristic,Replay-BasedApproach_Confws-15_p73.pdf |volume=Vol-1453 }} ==A heuristic, replay-based approach for reconfiguration== https://ceur-ws.org/Vol-1453/12_HaselboeckSchenner_AHeuristic,Replay-BasedApproach_Confws-15_p73.pdf

A Heuristic, Replay-based Approach for Reconfiguration
Alois Haselböck and Gottfried Schenner 1

Abstract. Reconfiguration is an important aspect of industrial prod-
uct 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 prod-
uct 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 reconfigura-
tion 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.

1 INTRODUCTION
Figure 1. Reconfiguration scenarios.
Configuration is the task of deriving a valid, complete and purposeful
system structure assembled from a set of components [14]. For non-
trivial configuration problems, like product configuration, we distin-
guish the following levels of models (cf. Table 1): the language used relationships realizing a final system. If this configuration is com-
to represent and solve the configuration problem (M4), the problem plete and consistent w.r.t. M3 and M2, M1 is said to be a solution of
domain model (M3), the problem instance model (M2), and the con- the given configuration problem.
figuration model (M1). Reconfiguration is the task of changing a given configuration. Var-
ious scenarios are possible why a (partial) configuration becomes in-
Table 1. Different levels of models in a configuration application. consistent and reconfiguration is necessary (cf. Figure 1):

(a) The problem domain M3 has been changed. Reasons could be
M4 Modelling Lan- e.g. UML class diagrams and OCL,
changes in the product catalogue, changes in the structure of the
guage CSP, ASP, ...
product line, regulation changes, etc. A legacy configuration al-
M3 Problem Domain Generic specification of the compo- ready installed in the field may be inconsistent now to the new
Model nent catalogue problem domain description and must be reconfigured.
(b) The requirements in M2 has been changed or extended. Again, a
M2 Problem Instance Requirements specification of a
Model concrete configuration problem
legacy configuration which is inconsistent now w.r.t. the changed
requirements must be adapted.
M1 Configuration Solution to M2: a configuration ob- (c) A configuration (M1) has been changed by an external process
Model ject network (e.g. by a manual user input or by reading a configuration from an
external repository) and is now inconsistent. Again, reconfigura-
tion must find a consistent modification of the configuration.
M3 is a generic specification of the problem domain. In an object-
oriented environment, this would be the class model. Constraints are In all these cases, a crucial demand is that the reconfigured solu-
usually used to describe the different dependencies and restrictions tion is as close as possible to the original configuration. The defini-
between the different objects. Such a model M3 defines the space tion of the quality of a reconfiguration (How close is the new configu-
of all the technically feasible configuration solutions. Model M2 is ration to the legacy configuration?) could get quite subtle. [Friedrich
a concrete problem instance, containing specific requirement defi- et al., 2011], e.g., use cost functions for the different change opera-
nitions which are usually formalized in terms of constraints, initial tors. Reconfiguration is then the problem of minimizing the overall
configuration objects and requirement and resource parameters. M2 modification costs. In this paper, we are using a more light-weight
is based on M3 and uses its language and concepts (M4). Finally, M1 approach: We don’t define cost functions but use a rather heuristic
- a configuration - consists of all the instances, their properties and and simple definition of minimality: the number of differences be-
tween the original and the reconfigured solution should be as small
1 Siemens AG Österreich, Corporated Technology, Vienna, Austria, as possible. This corresponds to equal cost values for all types of
{alois.haselboeck, gottfried.schenner}@siemens.com modifications.

73 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
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 frag-
ment and standard solving (e.g. backtracking) would immediately re-
turn 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 replay-
based reconfiguration. The composition of a reconfiguration will de-
viate from the legacy configuration in cases where inconsistencies
are to be avoided.
Our main contributions in this work are: (1) An Answer Set Pro-
gramming (ASP) encoding of the reconfiguration problem using the
special predicate heuristic of clingo (Potassco [12]). (2) A
CSP encoding of the reconfiguration problem using a novel value
ordering heuristic which prefers value assignments from a legacy
configuration. (3) Experimental evaluation and indications of up to
which problem sizes these methods are applicable.
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 re-
configuration can be modelled and solved in 2 different frameworks:
ASP and standard CSP. We compare and evaluated these techniques Figure 2. Problem domain model (M3) of a hardware configuration
in Section 4 and conclude the work with a discussion of related works problem example.
and a conclusion.

2 EXAMPLE Output is M1” which should be consistent w.r.t. M3’ and M2’ and as
close as possible to M1’.
A small example from the domain of railway interlocking hardware The basic of idea of our reconfiguration approach is to influence
should demonstrate the dynamics of the configuration problems we a solver to search in the neighbourhood of the legacy configuration.
want to model and solve. Of course, real-world problems are much This is achieved by defining a heuristic for the solver to choose for
larger and the object network and dependencies between the objects every decision the same value that has been used in the legacy con-
are more complex and varied. figuration, whenever possible. In a way this reconstruct the search
Figure 2 shows the UML diagram and represents the problem do- tree which was built creating the legacy configuration. Deviations
main M3 (cf. Table 1). A part of configuring an interlocking system is from that search tree should only happen when previously consistent
to create appropriate control modules for each outdoor element (e.g., choices are inconsistent now.
a signal or a switch point) and to place them into the right slots of a Our approach will perform poorly, if there is no consistent con-
frame, which in turn must be inserted into a rack. At the beginning, figuration close to an inconsistent legacy configuration. But the ap-
only the outdoor elements are known. Racks, frames and modules proach will perform well if only a small percentage of the overall
must be created during solving. In our example tracks require mod- configuration is modified during reconfiguarion, which is the case in
ules of type ’ModuleA’ and signals require modules of type ’Mod- most reconfiguration scenarios in practice especially for large con-
uleB’. figurations. E.g., from our experience in the rail automation domain,
A concrete problem instance is defined by a set of outdoor ele- most system modifications are only very local changes in the outdoor
ments of different kinds (model level M2). The goal is to find the installation.
right set and constellation of racks, frames, and modules, such that To show that our approach is applicable to different solving
each element is connected to exactly one module. Of course, we aim paradigms we implemented it in two standard AI technologies, an-
for a minimal set of hardware. Additionally, various types of con- swer set programming (ASP) and constraint satisfaction (CSP).
straints restrict the allowed constellations. Typical examples of such For the ASP implementation we used Potassco’s clingo which
constraints are: Some types of models should not be mixed within a allows to define domain specific heuristics within ASP with a special
frame. Certain types of modules must not be mounted on neighbour- predicate heuristic. With this predicate the solver can be influ-
ing places in the frame. enced to prefer certain atoms during solving. By giving the legacy
It shall be noted that for a concrete problem instance on model configuration as preferred heuristic facts we achieve a kind of replay
level M2, it is not known beforehand how many racks, frames, and of the original configuration. Details are described in Chap. 3.1.
modules are needed for a valid solution on model level M1. This is CSP systems often are more open to adaptations of the search pro-
why such kinds of problems are called dynamic problems in contrast cedure than ASP solvers. For our experiments, we used Choco which
to static problems. 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. De-
3 Approach
tails are described in Chap. 3.2.
According to Fig. 1, inputs to the reconfiguration solver are the prob- We chose Potassco and Choco for our experimental implemen-
lem descriptions M3’ and M2’, and the legacy configuration M1’. tations because they are well recognized implementations of ASP

Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors 74
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
and CSP technology. Potassco is very fast and regularly wins com- be either domain-specific or cardinality based. The cardinality based
petitions. Choco is a standard constraint solver in Java. Most likely cost function simply counts the difference (in number of facts) of the
there are CSP systems with better performance, but we belief that all legacy configuration and the reconfigured configuration. This default
solvers based on a backtracking scheme suffer from the same funda- reconfiguration task in OOASP is implemented using ASP optimiza-
mental behaviour of sometimes running into heavy backtracking as tion statements. Unfortunately it has a bad performance for large
shown in our evaluation (cf. Sec. 4). 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.
3.1 Answer set programming
Heuristic reconfiguration for OOASP de-
ASP is a declarative problem solving approach, which originated in scribed in this paper uses the special predicates
the area of knowledge representation and reasoning [10]. To imple- heuristic(AT OM, T RU T HV ALU E, LEV EL) from
ment our approach we used the Potassco ASP implementation [12] [11] to express heuristics in ASP . If during search
and our OOASP framework [16]. OOASP provides special predicates heuristic(AT OM, T RU T HV ALU E, LEV EL) can be
for describing object-oriented knowledge bases in ASP. Our running derived and LEVEL > 0 then the ASP solver will prefer setting
example can be declared in OOASP as follows: atom ATOM to TRUTHVALUE, if given a choice. With the heuristic
predicates the order in which solutions (answer sets) are found can
be influenced. It does not affect the set of found solutions.
ooasp_class("hw","Rack").
To implement our heuristic approach we add the facts
ooasp_class("hw","Frame").
ooasp_class("hw","Module"). describing the legacy configuration as heuristics facts
ooasp_class("hw","ModuleA"). heuristic(F ACT F ROM LEGACY, true, 1) to the ASP
ooasp_class("hw","ModuleB"). program and run the default OOASP configuration task with this
ooasp_class("hw","Element"). heuristic information. This way the ASP solver is expected to
ooasp_class("hw","Track"). find configurations that are close (cardinality based) to the legacy
ooasp_class("hw","Signal"). configuration first.
For example given the heuristic information below the ASP solver
ooasp_subclass("hw","ModuleA","Module"). will try to assign track A1 first to the module M1 and set its position
ooasp_subclass("hw","ModuleB","Module").
to 4.
ooasp_subclass("hw","Track","Element").
ooasp_subclass("hw","Signal","Element").
% user supplied fact
ooasp_assoc("hw","Frame_modules", ooasp_isa("c","Track","A1")
"Frame",1,1, % legacy configuration converted to heuristic
"Module",0,5). _heuristic(
ooasp_isa("c","ModuleA","M1"),
ooasp_attribute("hw","Module", true,1).
"position","integer"). _heuristic(
ooasp_attribute_minInclusive("hw","Module", ooasp_attribute_value(
"position",1). "c",
ooasp_attribute_maxInclusive("hw","Module", "position",
"position",5). "M1",4),
true,1).
ooasp_assoc("hw","Module_element", _heuristic(
"Module",1,1, ooasp_associated(
"Element",1,1). "c",
ooasp_assoc("hw","Rack_frames", "Module_element",
"Rack",1,1, "M1","A1"),
"Frame",0,4). true,1).
...
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. 3.2 Constraint satisfaction
One standard reasoning task of OOASP is to complete a partial
The encoding of a dynamic problem with a standard constraint for-
configuration i.e. to add components to the partial configuration until
malism (like MiniZinc2 or Choco3 ) makes it necessary to define a
all constraints of the knowledge base are satisfied. For example given
maximum number of instances of each object type. If, e.g., we allow
a partial configuration consisting only of one track (represented by
at most 5 racks for our example problem in Section 2, the maximum
the fact ooasp isa(”c”, ”T rack”, ”A1”)), completing a configura-
numbers of instances for the other types can be computed by cardi-
tion will return all configurations containing one track, with at least
nality propagation: 20 frames, 320 modules and 320 elements. For
one module of type A, one frame and one rack.
complex networks of classes, this cardinality propagation is not triv-
ial [4].
3.1.1 Heuristic reconfiguration We briefly sketch here the CSP encoding of configuration prob-
lems we used in our implementation. We use a pseudo code notation,
Given an inconsistent legacy configuration the default reconfigura-
tion reasoning task in OOASP finds a valid configuration that is 2 http://www.minizinc.org/
3 http://choco-solver.org/
cheapest in terms of some user defined cost function. The costs can

75 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
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 | {f rj | j ∈ {1, ..., nf }, f rj = i } | ≤ 4, ∀i ∈ {1, ..., nr}
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 Example for a constraint on attributes and associations: All mod-
Rack. nr be the maximum number of racks. ules in a frame must have different module positions:

ri ∈ {0, 1}, ∀i ∈ {1, ..., nr}
mfi = mfj ∧mfi ≥ 1 → mpi 6= mpj , ∀i,j ∈ {1, ..., nm}, i < j
The following symmetry breaking constraints states that unused
instances are always in the rear part of the array: It should be noted that such object-constraint mapping on dy-
namic problems (where the number of instances in a solution is not
ri = 0 → rj = 0, ∀i,j ∈ {1, ..., nr}, i < j known beforehand) has many disadvantages: (1) The representation
Attribute encoding is straight-forward. For each possible in- of objects as a flat set of constraint variables is very unnatural and
stance of a class, a CSP attribute variable is used. E.g., attribute hard to read, debug, and maintain. This can be mitigated by an
modulePos of modules is represented by the variable array mp automatic translation from objects to constraints. (2) A maximal set
(let nm be the maximum number of modules): of possible object instances must already be provided at problem
formulation. Decisions on maximum values are in general not easy;
mpi ∈ {−1, 1, ..., 16}, ∀i ∈ {1, ..., nm} too few objects could rule out possible solutions; too many objects
blows up the problem size. (3) Current constraint solvers (mainly
We provide a special attribute value (-1 for mp) for attributes based on backtracking) are very sensitive to changes. Small changes
of unused components. The following constraint states that unused in the variable structure or of the constraints could hugely influence
components must have this special value, and used components must solving performance, which makes a repeated tuning of the variable
have a value from the regular domain of the attribute. and value ordering heuristics necessary. (4) The representation of
associations is crucial. A simple representation, as described above,
mi = 0 ↔ mpi = −1, ∀i ∈ {1, ..., nm} does not directly support n:m associations and ordered associations.
The interesting part of the model is the encoding of associations. More elaborate encodings are difficult to handle in terms of con-
A very general approach is to represent each association by a ma- straint formulations, and often impair performance. (5) Modelling
trix of boolean variables on the instances of the two involved classes. of inheritance additionally increases representation complexity. (6)
A matrix entry mij = 1 means that object with index i is associ- Attributes of more complex types, like reals, multi-valued variables,
ated to object with index j. This representation needs a lot of CSP or strings, are often not supported at all in constraint systems.
variables and makes the formulation of consistency constraints on
associations quite intricate, causing low solving performance. An- To formalize reconfiguration in terms of standard CSP, we first
other approach [7] models association links as ports; an object has need to define a metric to have a notion of the distance between
n association variables, where n is the maximum cardinality of the a legacy configuration and a reconfigured solution. Let (V, D, C)
association. be a CSP with variables V , their domains D, and constraints C.
We use a simpler representation: For a 1:n-association, we use a An assignment is a tuple (v, d), v ∈ V , d ∈ Dv , represent-
variable array on the n side of the association. Each such variable ing the assignment of value d to variable v. Let A be a set of
points to the associated object, or has value -1, if not connected. Ex- assignments. vars(A) is the set of variables in A: vars(A) =
ample: The association {v | (v, d) ∈ A}. vars(A1, A2) is the set of variables both in A1
and A2: vars(A1, A2) = {v | v ∈ vars(A1), v ∈ vars(A2)}.
1 diff(A1, A2) is the number of assignments with different values on
Rack Frame the common variables in A1 and A2:
0..4

is represented as an integer variable f r for each frame: diff(A1, A2) = | {v | v ∈ vars(A1, A2),
(v, d1) ∈ A1, (v, d2) ∈ A2, d1 6= d2} |
f ri ∈ {−1, 1, ..., nr}, ∀i ∈ {1, ..., nf }
diff defines a simple metric on the space of all assignment sets of
The special value -1 is used if a frame is not associated to a rack a CSP. The CSP reconfiguration problem can now be simply defined
at all. This special value is also used for unused frames. 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
fi = 0 → f ri = −1, ∀i ∈ {1, ..., nf } C. A reconfiguration A0 is a consistent assignment on the variables
Additional consistency constraints are needed to rule out invalid V (i.e., A0 is a solution of the corresponding CSP) which minimizes
association constellations. Each used frame must be connected to a diff(A, A0 ).
rack: Reconfiguration can be simply implemented by slightly changing
the backtracking search procedure. We can’t start with the legacy
fi = 1 → f ri ∈ {1, ..., nr}, ∀i ∈ {1, ..., nf } configuration (a variable assignment), because it is potentially incon-
sistent and standard backtracking would stop with output failure
Frames can only be connected to used racks:
immediately. But we could solve the problem from scratch and use
the legacy configuration to guide expanding the search tree. Each
f ri ≥ 1 → rf ri = 1, ∀i ∈ {1, ..., nf }
time when a value for the current variable is selected, the value of
Only up to 4 frames are allowed in a rack: the legacy configuration - if an assignment tuple for that variable is

Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors 76
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
part of the legacy configuration - is preferably chosen. Of course, if 4.1 Performance: Time
that value is inconsistent with the current constellation, an alternative
value is taken. But basically, the legacy configuration is replayed, and Figures 3 and 4 show the solving time results for our ASP and CSP
changes are made only because of inconsistent states. The result is a implementations. The x-axis shows the different problem sizes in
consistent configuration which is very similar to the legacy configu- terms of number of Elements. Note that the number of objects
ration, which is exactly what we want - we want minimal reconstruc- in a configuration solution is far higher than these values, because all
tion of the system in the field. the HW elements (racks, frames, modules) and internal variables are
A brief note on our implementation: We used the constraint solver created during solving. The y-axis shows the solving execution time
Choco V3.2.2 to represent and solve configuration problems (as de- in seconds. For ASP, this is the sum of grounding and SAT solving
scribed in the first part of this subsection) and replay-based reconfig- time.
uration. Choco allows to plug in your own value selector by imple- We incremented the problem size, i.e. the number of Elements,
menting the interface IntValueSelector. With only a few lines in steps of 10. We generated 40 different configurations per problem
of code, we extended the standard value selector of Choco by pre- size, modified them randomly and solved the reconfiguration prob-
ferring the values stored in a given legacy configuration. If a legacy lem. Black circles in the plots are the measured times for each run.
value for the current variable is not available or inconsistent, standard Blue squares are the mean runtime values for that problem size. Red
Choco value selection is used. triangles indicate timeouts (time > 2 minutes).
Advantages: (1) This method is light-weight, i.e., no additional
150 data point
modelling concepts (like cost functions) are needed. Changes in the (3%) (8%) (55%) mean value
existing backtracking search procedures are minimal. (2) Most of the timeout

Solving time (sec)
existing backtracking algorithms (intelligent backtracking, etc.) and 100
variable and value ordering heuristics can still be used with only min-
imal adaptations. (3) Replay-based reconfiguration can be applied
50
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). 0
Disadvantages: (1) It is not guaranteed, that a solution with mini- 10 20 30 40 50 60 70 80 90
mal changes is found. The quality of the solution depends on the vari- Problem size (#input elements)
able/value ordering heuristics used. Nevertheless, results of our pro-
totypical implementation have shown, that the reconfiguration solu-
tions are often the optimum or very close to the optimum. (2) Replay- Figure 3. ASP solving times.
ing 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.
data point
(30%)(29%)(56%)(49%)(54%)(48%)(53%)(34%) mean value
100
4 EVALUATION timeout
Solving time (sec)

We did experimental evaluations on our ASP (cf. Section 3.1) and
CSP (cf. Section 3.2) implementations using randomly generated 50
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 0
the Potassco suite for the ASP implementation, and Choco V3.2.2 10 20 30 40 50 60 70 80 90
for the CSP implementation. Problem size (#input elements)
It should be mentioned that we intentionally didn’t use a high-
performance hardware setting and we did not do any coding opti-
mizations. Of course, ASP and CSP experts could find encodings
Figure 4. CSP solving times.
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 num- We made the following interesting observations:
ber and types of Elements. We generated randomly a set of in-
put problem instances, solved them, made random changes to the • ASP is much more robust than CSP. For problems up to a size of
solutions and applied the heuristic replay-based solvers (both ASP ca. 90 Elements ASP finds a solution in a well predictable time.
and CSP) to solve the reconfiguration problem. We measured solv- In contrast, CSP often needs a lot of time even for small problems
ing time, memory consumption, and quality of the reconfiguration and very often runs into timeout.
solution (i.e., how close is the result to the original configuration). • Consequently, the sizes of problems where ASP finds a solution in
It should be mentioned that integration of reasoning functionality acceptable time is also well predictable. In our test environment,
into our configuration infrastructure – an object-oriented data model ca. 100 Elements are the upper limit for ASP.
and environment implemented in Java – was easier with Choco than • CSP is much more sensitive to the input problem constellation. If
with clingo, because Choco provides a Java API. the backtracking procedure makes invalid choices in the first part

77 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
of the search tree, backtracking gets out of hand. This is why CSP reproduce the legacy configuration without any changes. Both ASP
runs very often into timeout even for small problem sizes. In cases and CSP did this in many test cases of various sizes.
without or with little backtracking, CSP is very fast, even for large The more interesting case is a legacy configuration which is in-
problems. consistent to the problem description. For each problem size (start-
If one is willing to tune the variable and value ordering heuristics ing from 10 Elements up to 80 Elements in steps of 10), we ran-
for her/his specific problem instance, CSP can solve much bigger domly modified up to 20% of a valid configuration. For each problem
problems than ASP very efficiently. The key is to avoid backtrack- size, we did 40 different tests.
ing.
• The variance of runtime continuously grows with problem size 15 ASP

# changed variables (mean)
for ASP. This is not the case for CSP. If CSP manages to solve the CSP

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 10

depending on the size of the input variables.
5

4.2 Performance: Memory
0
For all the test cases, we also measured indicators for memory con- 10 20 30 40 50 60 70 80
sumption (cf. Fig. 5). For ASP, we used grounding size in MBytes. Problem size (#input elements)
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
Figure 6. ASP and CSP reconfiguration quality.
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.

·105 The results are shown in Fig. 6. ASP most of the time finds so-
lutions of high quality. In fact, for smaller problem sizes we could
Memory size (MByte)

600
#CSP variables

1 manually verify that ASP nearly all the times finds the optimal solu-
400
tion. With CSP, the mean distance to the legacy configuration is a bit
200 0.5 higher than with ASP, but has an acceptable quality on most of the
cases.
0 0
10 20 30 40 50 60 70 80 10 20 30 40 50 60 70 80
Problem size (#input elements) Problem size (#input elements)
4.4 Evaluation Summary
Table 2 gives a summarized comparison of our ASP and CSP re-
Figure 5. (a) ASP grounding memory size. (b) CSP number of variables. configuration encodings and the results of our experimental evalua-
tions. 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 functional-
Not surprisingly, memory of both ASP and CSP grows with ac-
ity. For larger problem, CSP may be better, but probably additional
celerated speed depending on the problem size. ASP grows with a
coding is needed for tuning search.
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. 5 RELATED WORKS
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 Related to our work presented in this paper are all techniques for
memory indicator. A rough memory profile using Choco’s statistics finding a valid reconfiguration for a given, possibly inconsistent con-
functionality has shown, that for 100,000 variables ca. 20 MByte figuration (fragment). The main research approaches are:
RAM is consumed (for the cases without heavy backtracking). This Repair-based approaches. Repair-based approaches aim for find-
means that CSP’s footprint is roughly 20 times smaller than ASP’s ing diagnoses and repairs to conflicting requirements or con-
footprint. straints [5]. Usually, methods from model-based diagnosis are used
(e.g., minimal hitting sets). Repair-based approaches are mainly stud-
4.3 Performance: Quality ied in the context of recommender systems [6]. These approaches are
complete, they are based on a clean, formal theory, and they typically
To evaluate the quality of a reconfiguration we measured the distance take user needs into account. Those repairs are in favour which may
of the original, legacy configuration to the reconfigured solution. We be of most usefulness for the user. When applied in a configuration
used a graph-based difference metric counting the differences in the context based on consistency and search algorithms, repair-based
rack/frame/module constellation of the legacy configuration to the methods introduce additional reasoning techniques which must be in-
reconfiguration. tegrated into the configurator framework. Our heuristic, replay-based
The first and simplest case is to provide a legacy configuration approach uses conventional solving techniques with slight modifica-
which is already consistent. This means that a reconfiguration should tions for reconfiguration.

Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors 78
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
Minimization of modification costs. The basis of these approaches to find solutions in a hill-climbing manner (e.g. greedy search algo-
is the definition of cost functions for the different modification op- rithms, genetic algorithms). In the context of product configuration,
erations [9]. Reconfiguration is then finding a valid modification Generative CSP (GCSP) is an extension of standard CSP and has
of the configuration which minimizes the sum of all modification been introduced in [8] for large, dynamic configuration problems. In
costs. Such techniques have been, e.g., intensively studied in the re- GCSP, mainly local search techniques - repair-based local search -
search project RECONCILE4 . The possibility of defining elaborate are used because no fast complete search methods are available yet
cost functions for configuration modifications along with a complete for dynamic systems. Repair-based local search tries to find local
optimization search procedure (in [9], based on ASP) is a great ad- modifications of an inconsistent or incomplete configuration. Thus,
vantage for applications where modifications in the field are expen- this technique intrinsically can deal with inconsistent configuration
sive. But this comes at the price of considerable additional modelling (fragments). Complex, dynamic problems can be modelled in a very
concepts for cost functions and often declined solving performance. natural way using object-oriented concepts. The main disadvantage
Compared to that, our approach is light-weight in the sense that no of local search methods is that they are incomplete – they may get
additional modelling is necessary, and most of the advanced back- stuck in a local optimum during search and may not find a solution,
tracking algorithms with only minimal adaptations are applicable. even if one exists. Compared to that, our approach is complete, be-
cause it is based on an exhaustive tree search (backtracking).
Table 2. Comparison of ASP and CSP reconfiguration modelling and Rule-based approaches. Especially in model-driven engineering,
behaviour. a lot of research in model synchronization has been done and is still
on-going. Correspondences between two models are defined as trans-
ASP CSP formation rules, describing how values from one model are mapped
to another model. Examples of such systems are triple graph gram-
Robustness High Low mars [13] or JTL [2]. Model synchronization (corresponding to re-
Predictable Very sensitive to input con- configuration in our definition) is done by triggering the transforma-
stellation and problem for-
mulation tion rules. Applying such methods to a reconfiguration problem in
product configuration means that all necessary types of modification
Performance Good for small problem Very good, if no or little operations for transforming an invalid configuration to a valid one
sizes backtracking, else timeout must be specified explicitly. Our heuristic, replay-based approach
Does not scale for larger Probability of timeout
problems grows with problem size
does not need any additional knowledge like transformation rules.
Reconfiguration is guided by a legacy configuration and a declara-
Memory High (grounding!) Low tive problem specification (models M3 and M2 in Tab. 1).
footprint Common to all these approaches – at least to a certain degree –
is that reconfiguration actions are modelled on a declarative level.
Solution Very good Never better than ASP, but
quality Most of the time the opti- most of the time acceptable
The specification of potential modification operations and reconfig-
mum or close to the opti- uration reasoning are separated. Another approach used in industry
mum (e.g. in factory facilities, steel plants) is to offer upgrade or modern-
ization packages. There the focus lies on finding and recommending
Integrability Typically, ASP systems are Many CSP solvers sup- modernization packages which are appropriate to add functionalities
not as easy to integrate into port APIs to programming
a Java environment as CSP languages like Java (e.g. to a system in the field.
systems. Choco9 , JaCoP10 ) or C++
The ASP solvers Potassco5 (e.g. Gecode11 , Minion12 ).
and Smodels6 provide C++ 6 CONCLUSION AND FUTURE WORK
libraries, DLV7 recently
provided a Java interface There is no standard way of doing reconfiguration for product con-
(JDLV8 ). figuration especially for large problem sizes. In this paper we showed
the implementation of a heuristic approach to reconfiguration us-
Problem Favoured is an automatic Direct encoding of an
ing standard solving techniques and the applicability up to moder-
encoding transformation from the object-oriented data model
object-oriented problem with a CSP system is quite ate problem sizes. The main challenge for using these techniques in
description to ASP. Direct intricate and error-prone. an industrial setting are grounding size and solving time. Ground-
ASP encoding is also Automatic transformation ing size typically can be influenced by finding a better encoding or
possible, because ASP has is highly recommended. by problem decomposition. Solving time is also influences by the
a compact syntax and is
readable. encoding of the problem and by finding the right heuristic for the
domain.
Because of the heterogeneous nature of the constraints in prod-
Local search methods. The main alternatives to backtracking-like uct configuration coming up with a good encoding and heuristics for
search are so-called heuristic (or local) search strategies which try a problem is currently as much an art as a science and requires an
4 http://isbi.aau.at/reconcile/ experienced knowledge engineer. Also it requires experiments with
5 http://potassco.sourceforge.net/ different solving paradigms as SAT, ASP, CSP, MIP etc. Therefore
6 http://www.tcs.hut.fi/Software/smodels/
we welcome the further integration of AI and OR solving techniques
7 http://www.dlvsystem.com/
8 http://www.dlvsystem.com/jdlv/
that have taken place in the last years as we believe there will not be
9 http://choco-solver.org/ THE solving technique for product (re-)configuration in the foresee-
10 http://www.jacop.eu/ able future.
11 http://www.gecode.org/ For the future we plan to further study and improve heuristic re-
12 http://minion.sourceforge.net/
configuration solving techniques and to apply them to fields beyond

79 Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
product configuration. As we have seen in our experiments, CSP [4] Ingo Feinerer and Gernot Salzer, ‘Numeric semantics of class dia-
solving – though it is very fast and produces good results if it doesn’t grams with multiplicity and uniqueness constraints’, Software and Sys-
tem Modeling, 13(3), 1167–1187, (2014).
fall into a heavy backtracking trap – currently isn’t robust enough to [5] Alexander Felfernig, Gerhard Friedrich, Monika Schubert, Monika
be applied in an industrial environment. We believe that the integra- Mandl, Markus Mairitsch, and Erich Teppan, ‘Plausible repairs for in-
tion of additional heuristics which are automatically derived from the consistent requirements’, in IJCAI 2009, Proceedings of the 21st Inter-
problem domain or techniques like lazy clause generation [17] will national Joint Conference on Artificial Intelligence, Pasadena, Califor-
fix this problem of poor robustness. Also the integration of CSP and nia, USA, July 11-17, 2009, pp. 791–796, (2009).
[6] Alexander Felfernig, Erich Teppan, Gerhard Friedrich, and Klaus Isak,
ASP (CASP [1]) looks promising. ‘Intelligent debugging and repair of utility constraint sets in knowledge-
Interesting fields beyond product configuration, where reconfigu- based recommender applications’, in Proceedings of the 2008 Interna-
ration methods could be applied, are: tional Conference on Intelligent User Interfaces, January 13-16, 2008,
Gran Canaria, Canary Islands, Spain, pp. 217–226, (2008).
• Production configuration: With the increasing demand for indi- [7] Adel Ferdjoukh, Anne-Elisabeth Baert, Annie Chateau, Remi Coletta,
and Clémentine Nebut, ‘A CSP approach for metamodel instantiation’,
vidualized products, the need for flexible production processes,
in 2013 IEEE 25th International Conference on Tools with Artificial
modular factories and intelligent production infrastructures is also Intelligence, Herndon, VA, USA, November 4-6, 2013, pp. 1044–1051,
increasing. Factories of the future are generic production facili- (2013).
ties, that can be easily adapted to the needs of the product to be [8] Gerhard Fleischanderl, Gerhard Friedrich, Alois Haselböck, Herwig
manufactured [3]. This means, before the factory can manufacture Schreiner, and Markus Stumptner, ‘Configuring large systems using
generative constraint satisfaction’, IEEE Intelligent Systems, 13(4), 59–
products of a product line, it has to be physically reconfigured for 68, (1998).
the specific production setting. This includes reconfiguration of [9] Gerhard Friedrich, Anna Ryabokon, Andreas A. Falkner,
the cyber-physical components of the factory [15], and therefore Alois Haselböck, Gottfried Schenner, and Herwig Schreiner,
the need for fast, flexible and robust reconfiguration technologies. ‘(re)configuration based on model generation’, in LoCoCo, pp.
26–35, (2011).
• Model synchronization: In model-driven engineering, model syn-
[10] M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub, Answer Set
chronization is the task of finding a mapping between overlap- Solving in Practice, Synthesis Lectures on Artificial Intelligence and
ping concepts of two different models. Typically, the overlaps of Machine Learning, Morgan and Claypool Publishers, 2012.
the two models are described as a correspondence model, includ- [11] M. Gebser, B. Kaufmann, J. Romero, R. Otero, T. Schaub, and
ing constraints which define the dependencies and interactions be- P. Wanko, ‘Domain-Specific Heuristics in Answer Set Programming’,
in Proceedings of the AAAI, (2013).
tween the models. This situation can be seen as a reconfiguration [12] Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Os-
problem: Given are two models (e.g., configuration instances of trowski, Torsten Schaub, and Marius Thomas Schneider, ‘Potassco: The
two different configuators) which have been changed in the course potsdam answer set solving collection’, AI Commun., 24(2), 107–124,
of a new system version, and a correspondence model. The recon- (2011).
[13] Frank Hermann, Hartmut Ehrig, Claudia Ermel, and Fernando Orejas,
figuration problem is now to find changes in the two evolved mod-
‘Concurrent model synchronization with conflict resolution based on
els which are (a) consistent to their domain model, (b) consistent triple graph grammars’, in Fundamental Approaches to Software Engi-
to the correspondence model, and (c) as close as possible to the neering, eds., Juan de Lara and Andrea Zisman, volume 7212 of Lec-
original models. ture Notes in Computer Science, 178–193, Springer Berlin Heidelberg,
• Case-based reasoning: In case-based reasoning, a database of so- (2012).
[14] U. Junker, ‘Configuration’, in Handbook of Constraint Programming,
lutions from previous problems are used to find a solution to a new eds., F. Rossi, P. vanBeek, and T. Walsh, pp. 837–873. Elsevier, (2006).
problem [18]. Usually, no perfectly fitting solution could be found, [15] Kunming Nie, Tao Yue, Shaukat Ali, Li Zhang, and Zhiqiang Fan,
but one which solved a similar problem. We think that our heuris- ‘Constraints: The core of supporting automated product configuration
tic, replay-based reconfiguration procedures could be applied to of cyber-physical systems’, in Model-Driven Engineering Languages
and Systems, eds., Ana Moreira, Bernhard Schätz, Jeff Gray, Antonio
the reuse/revise phase of case-based reasoning: To solve a new
Vallecillo, and Peter Clarke, volume 8107 of Lecture Notes in Computer
problem try to rebuild the configuration of a solved problem. Science, 370–387, Springer Berlin Heidelberg, (2013).
[16] Gottfried Schenner, Andreas Falkner, Anna Ryabokon, and Gerhard
Friedrich, ‘Solving object-oriented configuration scenarios with asp.’,
ACKNOWLEDGEMENTS Proceedings of the 15th International Configuration Workshop, 55–62,
(2013).
This work has been funded by the Vienna Business Agency in the [17] Peter J. Stuckey, ‘Lazy clause generation: Combining the power of SAT
programme ZIT13-plus within the project COSIMO (Collaborative and CP (and MIP?) solving’, in Integration of AI and OR Techniques
Configuration Systems Integration and Modeling) under grant num- in Constraint Programming for Combinatorial Optimization Problems,
7th International Conference, CPAIOR 2010, Bologna, Italy, June 14-
ber 967327, and by FFG FIT-IT within the project HINT (Heutistic 18, 2010. Proceedings, pp. 5–9, (2010).
Intelligence) under grant number 840242. [18] Hwai-En Tseng, Chien-Chen Chang, and Shu-Hsuan Chang, ‘Applying
case-based reasoning for product configuration in mass customization
environments’, Expert Syst. Appl., 29(4), 913–925, (2005).
REFERENCES
[1] Marcello Balduccini and Yuliya Lierler, ‘Integration schemas for con-
straint answer set programming: a case study’, TPLP, 13(4-5-Online-
Supplement), (2013).
[2] Antonio Cicchetti, Davide Di Ruscio, Romina Eramo, and Alfonso
Pierantonio, ‘Jtl: A bidirectional and change propagating transforma-
tion language’, in Software Language Engineering, eds., Brian Malloy,
Steffen Staab, and Mark van den Brand, volume 6563 of Lecture Notes
in Computer Science, 183–202, Springer Berlin Heidelberg, (2011).
[3] D. Dhungana, A. Falkner, A. Haselböck, and H. Schreiner, ‘Smart fac-
tory product lines: A configuration perspective on smart production
ecosystems’, in Manuscript submitted for publication, (2015).

Juha Tiihonen, Andreas Falkner, and Tomas Axling, Editors 80
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria