Various approaches have been explored to detect and resolve software model inconsistencies in a generic and scalable way. In this position paper, we outline our research that aims to use the technique of automated planning for the purpose of resolving model inconsistencies. We discuss the scalability results of the approach obtained through several stress-tests and we propose several alternatives to the automated planning approach.
In this article we give an overview of di erent automated planning techniques (Section 3). Based on a simple case study (Section 4.1) we present an approach using a forwardchaining heuristic planner to resolve inconsistencies (Section 4.2). One of our requirements is that the time required for resolving inconsistencies has to be su ciently small so as not to disturb the designer in his/her work. Therefore, we investigate the scalability of the approach to larger software models (Section 4.3). Based on these results we discuss ways to improve the scalability of the proposed technique (Section 4.4). We also discuss alternatives to automated planning that may be more appropriate (Section 5).
State-of-the-art approaches on inconsistency resolution
exhibit several problems. In [
Our aim is to tackle the problem of inconsistency resolution by generating possible resolution plans without the need of manually writing resolution rules or writing any procedures that generate choices. The approach needs to generate valid models with respect to the modelling language and needs to enable the resolution of multiple inconsistencies at once and to perform the resolution in a reasonable time. In addition, the approach needs to be generic, i.e. it needs to be easy to apply it to di erent modelling languages. In this article we investigate the use of Automated Planning for this purpose.
Automated planning is a technique coming from arti cial intelligence research. It aims to create plans, which are sequences of primitive actions that lead from an initial state to a state meeting a speci c prede ned goal. To accomplish this, the planner decomposes the world into logical conditions and represents a state as a conjunction of literals. As input the planner needs a planning environment, composed of an initial state, a desired goal and a set of primitive actions that can be performed. The initial state represents the current state of the world. The goal is a partially speci ed state that describes the world that we would like to obtain. The actions express how each element of a state can be changed. The actions are composed of a precondition and an e ect. The e ect of an action is executed if and only if the precondition is satis ed.
Classical planning is an automated planning subset that aim
to nd a sequence of actions that reaches a desired state
in a nite, static, deterministic and fully observable world.
In general a planning approach consists of a representation
language used to describe the problem and an algorithm
representing the mechanism to solve the problem.
Fikes et al [
Two main approaches exist to solve classical planning
problems [
Regression planning is a backward state-space search that
starts in the goal state and searches a sequence of actions
that reach the initial state. This algorithm avoids the
problems of the previous one by working only with relevant
actions. The problem of this algorithm is that it is not always
obvious to nd a possible predecessor of an action.
Another distinction can be made between total-order and
partial-order planning. With the former approach, the set
of actions that composes the strategy found by the
algorithm is strictly linear and ordered from the initial state to
the goal. This category of algorithms cannot execute
different actions simultaneously and cannot take advantage of
the subdivision of a goal. Instead, partial-order planning
(POP) explores the plan-space without committing to a
totally ordered sequence of actions. POP works back from the
goal to the initial state and it can place two actions into a
strategy without specifying which comes rst. As a result,
these actions can be executed in parallel and their order is
unimportant because they achieve di erent sub-divisions of
the goal [
Many planners exist that implement some variant of a
planner algorithm. In this article we use the heuristic state-space
progression planner called FF (for \Fast-Forward Planning
System" [
Design models can be of di erent types (e.g. UML, Petri
nets, feature models, business process models). In this
article we restrict ourselves to UML class diagrams [
An inherited cyclic composition inconsistency arises when a composition relationship and an inheritance chain form a cycle that would produce an in nite containment of objects upon instantiation. Both occurrences, ICC1 and ICC2, of this inconsistency in Figure 1 arise with the same composition relationship, between Vehicle and Amphibious Vehicle, but with di erent inheritance chains. The rst occurrence ICC1 appears in the inheritance chain Vehicle Boat
Amphibious Vehicle. The second inconsistency ICC2 occurs in the inheritance chain Vehicle Car Amphibious Vehicle. A cyclic inheritance inconsistency arises when an inheritance chain forms a cycle. Figure 1 has two occur
Vehicle
rences CI1 and CI2 of this type of inconsistency. The rst
occurrence CI1 forms an inheritance cycle that involves the
classes Vehicle, Boat and Amphibious Vehicle. The
second occurrence CI2 forms an inheritance cycle that involves
the classes Vehicle, Car and Amphibious Vehicle.
All four aforementioned inconsistency occurrences share two
of the three classes that compose their respective
inheritance chains: Vehicle and Amphibious Vehicle. Because
of this overlap, it is possible to resolve more than one
inconsistency occurrence with the same resolution action. For
example, removing the composition relationship between
Vehicle and Amphibious Vehicle solves the two inconsistency
occurrences ICC1 and ICC2. Removing the inheritance
relationship between Boat and Amphibious Vehicle solves the
two inconsistency occurrences ICC1 and CI1. This clearly
illustrates that, in order to resolve model inconsistencies in
an optimal way, it is important to consider all
inconsistencies simultaneously. In [
Using the example of Figure 1, we illustrate how to
create a sequence of inconsistency resolution actions with
automated planning. We require as input an initial state (the
inconsistent model), a set of possible actions (that change
the model) and a desired goal (the consistent model).
Planning requires logic conditions as input, so the whole model
environment (e.g. model, meta-model, detection rules) is
translated into a conjunction of logic literals. The syntax of
PDDL is Lisp-like. Each logic literal is a tuple represented
between parentheses. The tuple starts with the name of
the literal, followed by pairs of variable names and their
type (separated by a \{"). There are no primitive types in
PDDL. More information about the PDDL syntax can be
found in [
The initial state is expressed as a conjunction of literals, and represents the current world. In our case the initial state will be the inconsistent model. We can choose between three di erent representations of this initial state: (1) using the complete model; (2) using a partial model that contains only those elements that are involved in one or more inconsistency occurrences; (3) using a partial model that contains only those elements that are involved in a single inconsistency occurrence. We exclude option (3) as it only allows us to solve one inconsistency at a time, and it does not take into account any dependency between inconsistency occurrences or their resolution actions.
The metamodel for our class diagram is given below using PDDL syntax. Each metamodel element is represented by a unique id through which it can be referred. (Class ?id - class_id ?name - String) (Generalisation ?id - g_id ?label - String
?child_class - class_id ?parent_class - class_id)
(Association_End ?id - ae_id ?class - class_id ?role - String
?upper_mult - Cardinal ?lower_mult - Cardinal
?composite - Boolean)
(Association ?id - a_id ?name - String ?ass_end_1 - ae_id
?ass_end_2 - ae_id)
A partial model conforming to this metamodel is given
below. It contains only the elements that are involved in the
inconsistency occurrences. This is illustrated by the shaded
part of Figure 1.
(Class c1 Vehicle)
(Class c5 Boat)
(Class c6 Car)
(Class c9 Amphibious_Vehicle)
(Generalisation g4 label4 c5 c1)
(Generalisation g5 label5 c6 c1)
(Generalisation g8 label8 c9 c5)
(Generalisation g9 label9 c9 c6)
(Generalisation g10 label10 c1 c9)
(Association_End ae1 c9 role1 star one non)
(Association_End ae2 c1 role2 one one yes)
(Association a1 ass1 ae1 ae2)
The set of actions that can be performed to change a model
are represented in terms of a precondition that must hold
before the execution and the action to execute. In our
approach, inspired by [
The inherited cyclic composition inconsistency detection rule using the PDDL syntax is given bellow. Observe that it only speci es an inheritance chain involving three classes. PDDL syntax does not allow to express transitive closure to make the rule more generic. (exists (?a - class_id ?b - class_id (and (exists (?g - g_id ?Label - g_label)
(Generalisation ?g ?Label ?c ?a)) (exists (?g - g_id ?Label - g_label) (Generalisation ?g ?Label ?b ?c)) ?c - class_id) (exists (?ae - ae_id ?role - ae_role
?upper - upper_cardinal ?lower - lower_cardinal) (Association_End ?ae ?a ?role ?upper ?lower yes)) (exists (?ae - ae_id ?role - ae_role ?upper - upper_cardinal ?composite - boolean) (Association_End ?ae ?b ?role ?upper one_l ?composite)) )) The advantage of using alternative (1) above is that it can be used to detect and resolve inconsistency occurrences at the same time. Alternative (2) will only be able to resolve inconsistency occurrences that have already been identi ed previously. On the other hand, as we will see later, alternative (1) su ers from severe scalability problems. In both alternatives we use logic negation to express the fact that we do not want inconsistencies in the model. Because negation of the conjunction of literals is used we need a planning approach that allows the use of disjunction and negative literals in the goal. This is one of the main reasons why we have selected FF as a planning tool for our experiments. The plan is a sequence of actions that reaches the desired goal. It is generated automatically by the domain independent planning algorithm. A complete resolution plan that solves the four inconsistency occurrences of the motivating example is shown in Figure 2. Remark that our approach prohibits the generation of a resolution plan that leads to ill-formed models (i.e., models that do not conform to their metamodel). delete_Generalisation :
(Generalisation g10 label10 c1 c9) modify_Association_End_Lower_Multiplicity : from: (Association_End ae1 c9 role1 star one non) to: (Association_End ae1 c9 role1 star zero non)
There are di erent ways in which to specify the input for the automated planning algorithm. To specify the initial state, we can either use the complete model or we can restrict the search space by using a partial model that contains only those elements that are involved in the inconsistency occurrences. To specify the desired goal, we can choose between using the negation of the inconsistency detection rules or using the negation of the inconsistency occurrences themselves.
In order to assess which of the above four choices produces the best results, we compared the timing results of each considered possibility. In order to remove noise, each experiment was executed 10 times and the average time and standard deviation was computed. All experiments were carried out on a 64-bit Apple MacBook with 2.4 GHz Intel Core 2 Duo processor and 4GB RAM, 2.9GB of which were available for the experiment.
The experiments using the complete model as initial state and the negation of the inconsistency detection rules as desired goal and using the partial model as initial state and the negation of the inconsistency detection rules as desired goal, ran out of memory. Using the complete model as initial state and the negation of the inconsistency occurrences as desired goal, the resolution plan of Figure 2 was generated in 14.84 seconds on average with a very low standard deviation of 0.09 seconds. Using a partial model as initial state, and the negation of the inconsistency occurrences as desired goal, the resolution plan of Figure 2 was generated in 0.268 seconds on average, with a standard deviation of 0.004 seconds.
To verify whether the proposed approach scales up to larger models, we have stress-tested both of the successful experiments (using the negation of the inconsistency occurrences as desired goal). Again each experiment was executed 10 times and the average time and standard deviation was computed.
First, we arti cially augmented the size of the motivating example of Figure 1 by adding an increasing number of isolated classes to the model (from 1 class to 20 classes). Since these classes are unrelated to the inconsistency occurrences that the algorithm needs to resolve, the algorithm is still able to nd the same resolution plan and the partial model is left untouched. However, the time it takes to generate a plan increases as the model size increases.
Figure 3a illustrates the timing results if we use the complete model as initial state. It takes only 15 seconds for our initial example, but it takes more than 5 hours for the model with 20 more added classes. A regression analysis reveals an exponential relation with coe cient of determination R2 = 0:982, indicating a very good t of the regression model. Two other candidate regression models we veri ed had a lower goodness of t: 0.977 for a quadratic polynomial model and 0.884 for a power curve. These results show that using a complete model as initial state does not scale up to larger models.
Secondly we studied the timing results when the size of the partial model increases. The motivating example of Figure 1 contains an inheritance chain of classes for the two types of considered inconsistencies. We arti cially augmented the size of the model by increasing the length of the inheritance chains involved in the inconsistency occurrences. We did this gradually, by adding between one and eight intermediate superclasses, and computing the timing results for each partial model.
Figure 3b shows the timing results of carrying out this experiment. The gure shows a strong increase in time to compute the resolution plan as the size of the partial model increases. The standard deviation was always below 2%, and less than 0.4% on average. A regression analysis reveals an exponential growth (with coe cient of determination R2 = 0:995) in the time needed to nd a resolution plan. Two other regression models we veri ed had a lower goodness of t: 0:927 for a quadratic polynomial model and 0:949 for a power curve. We also veri ed whether the number of inconsistency occurrences to be resolved a ected the timing results. To achieve this, we reduced the desired goal by generating plans that resolve only 2 or 3 inconsistency occurrences, respectively. In all of these cases we found an exponential growth in time. We obtained a goodness of t R2 = 0:991 for resolving 2 inconsistency occurrences, and R2 = 0:992 for resolving 3
Avg
Std R! = 0.9939 0.269 0.278 0.300 0.315 0.350 0.3288 0.442 0.518 0.611 0.711 0.852 1.001 1.180 1.398 1.628 1.945 2.273 2.643 3.057 3.528 0.267 0.279 0.295 0.313 0.348 03.390 0.444 0.532 0.605 0.711 0.851 0.997 1.180 1.398 1.639 1.950 2.272 2.631 3.057 3.540
Avg ) 4 s ( e250 m i T 125 3 2 0 0 4 3 2 1 0 inconsistency occurrences.
Finally, we veri ed whether the size of the metamodel a ects the timing results. To achieve this, we added a new element to the metamodel: (Attribute ?id - attribute_id ?class - class_id ?Name - String ?Type - Type) This requires to add three new actions, to create, modify and delete attributes, respectively. It did not a ect the timing results as long as attributes are not used in the initial state and the desired goal. power model with R regression analysis revealed a quadratic polynomial with a goodness of t R
= 0:994. Two other regression models we veri ed were an exponential model with R = 0:982 and a 2 4.4
The exponential timing results obtained through the experiments described in the previous section, indicate that the approach is not usable in practice. Using the approach to resolve inconsistencies one by one would be feasible because the partial model and desired goal will remain relatively small. This is not a good solution, because it does not take full advantage of automated planning. In addition, inconsistency occurrences and their resolution actions are often interdependent. Another important limitation we encountered is the expressiveness of the PDDL syntax. It does not o er important features such as transitive closure, primitive types, numbers. In addition, literals cannot be modi ed (they have to be deleted and added again). A third limitation of our approach is that, currently, we generate only a single resolution plan. The resolution of several inconsistencies can give rise to several di erent resolution plans, i.e., di erent sequences of resolution actions leading to possibly di erent consistent models.
Several improvements to the approach can be envisaged. A rst improvement is to adapt the planning algorithm so that it generates several resolution plans among which the model designer could choose.
The scalability problem could be
adressed by implementing a domain-speci c planner that
can be optimized by making it more speci c and more
performant for the speci c problem we want to tackle. In
addition, since we are not constrained by the PDDL syntax, this
would solve the problems of expressiveness we encountered.
The timing results could be improved by using regression
planning as opposed to progression planning [
Since the automated planning approach does not meet our expectations, we would also like to study other techniques coming from the domain of arti cial intelligence for the purpose of resolving modeling inconsistencies in an automated way.
Logic-based approaches have been used for di erent but
related purposes in inconsistency resolution. Marcelloni and
Akist [
In order to assess the adequacy of all these di erent approaches to inconsistency management, there is also an urgent need to de ne benchmarks allowing to compare them. Such a benchmark should contain at least a set of shared case studies on which to evaluate each approach; as well as a set of clearly identi ed criteria enabling the comparison of approaches and their quality.
In this article, we explored the use of automated planning, a logic-based approach originating from arti cial intelligence, for the purpose of resolving model inconsistencies. We are not aware of any other work having used this technique for this particular purpose. The results of our experiments reveal that the approach is feasible but su ers from various scalability problems. We have discussed ways in which the scalability can be improved. We have also discussed alternative search-based techniques that may deal with inconsistency resolution in a scalable way.
Acknowledgements. This work has been partially supported by (i) the F.R.S. { FNRS through FRFC project 2.4515.09 \Research Center on Software Adaptability"; (ii) research project AUWB-08/12UMH \Model-Driven Software Evolution", an Action de Recherche Concertee nanced by the Ministere de la Communaute francaise - Direction generale de l'Enseignement non obligatoire et de la Recherche scienti que, Belgium; (iii) Avec le soutien de Wallonie - Bruxelles International et du Fonds de la Recherche Scienti que, du Ministere Francais des A aires etrangeres et europeennes, du Ministere de l'Enseignement superieur et de la Recherche dans le cadre des Partenariats Hubert Curien.