Resolving Model Inconsistencies with Automated Planning Jorge Pinna Puissant, Tom Mens Ragnhild Van Der Straeten Université de Mons Vrije Universiteit Brussel 20 Place du Parc 1050 Brussel, Belgium 7000 Mons, Belgique Université Libre de Bruxelles {jorge.pinnapuissant, 1050 Bruxelles, Belgique tom.mens}@umons.ac.be rvdstrae@vub.ac.be ABSTRACT 2. PROBLEM STATEMENT Various approaches have been explored to detect and resolve State-of-the-art approaches on inconsistency resolution ex- software model inconsistencies in a generic and scalable way. hibit several problems. In [18], resolution rules are specified In this position paper, we outline our research that aims to manually, which is an error-prone process. Automatic gen- use the technique of automated planning for the purpose of eration of inconsistency resolution actions would resolve this resolving model inconsistencies. We discuss the scalability problem. This is what is done by Nentwich et al. [19], by gen- results of the approach obtained through several stress-tests erating resolution actions automatically from the inconsis- and we propose several alternatives to the automated plan- tency detection rules. The execution of these rules, however, ning approach. only resolves one inconsistency at a time. As recognised by the authors, this may cause problems when inconsistencies Keywords and their resolution are interdependent [17]. An additional inconsistency resolution, UML models, automated planning, problem is the interaction of the resolutions with the syntac- scalability tical constraints imposed by the modelling language. Xiong et al. [28] define a language in which it is possible to spec- ify the inconsistency rule and the possibilities to resolve the 1. INTRODUCTION inconsistencies. This requires inconsistency rules to be an- In model-driven software engineering (MDE) [24, 26], model notated with resolution information. Almeida da Silva et inconsistencies inevitably arise, because a (software) system al. [1] propose an approach to generate resolution plans for description is composed of a wide variety of diverse mod- inconsistent models. The approach is based on the exten- els, some of which are developed and maintained in parallel, sion of inconsistency detection rules with information about and most of which are subject to continuous evolution. Our the causes of the inconsistency, and on the use of genera- research focuses on the resolution of inconsistencies. The tor functions, which are manually written and are used to inconsistency resolution activity is divided into the follow- generate resolution actions. Instead of explicitly defining or ing steps: (1) Select the inconsistencies that need to be re- generating resolution rules, a set of models satisfying a set solved; (2) Identify possible resolution plans to resolve the of consistency rules can be generated and presented to the selected inconsistencies; (3) Perform a cost-benefit analysis user. Egyed et al. [6] define such an approach for resolv- of the implementation of each of these resolution plans; (4) ing inconsistencies in UML models. Given an inconsistency Select and apply resolution actions, based on the previous and using choice generation functions, possible resolution choices [25]. We focus on how to automate step (2) of the choices, i.e., possible consistent models, are generated. The inconsistency resolution activity: identification of possible choice generation functions are dependent on the modelling resolution plans. To do this, we propose to use the Au- language, i.e., they take into account the syntactical con- tomated Planning technique from the Artificial Intelligence straints of the modelling language and they only consider domain. the impact of one consistency rule at a time. Furthermore these choice generation functions need to be implemented In this article we give an overview of different automated manually. planning techniques (Section 3). Based on a simple case study (Section 4.1) we present an approach using a forward- Our aim is to tackle the problem of inconsistency resolution chaining heuristic planner to resolve inconsistencies (Sec- by generating possible resolution plans without the need of tion 4.2). One of our requirements is that the time required manually writing resolution rules or writing any procedures for resolving inconsistencies has to be sufficiently small so that generate choices. The approach needs to generate valid as not to disturb the designer in his/her work. Therefore, models with respect to the modelling language and needs to we investigate the scalability of the approach to larger soft- enable the resolution of multiple inconsistencies at once and ware models (Section 4.3). Based on these results we discuss to perform the resolution in a reasonable time. In addition, ways to improve the scalability of the proposed technique the approach needs to be generic, i.e. it needs to be easy to (Section 4.4). We also discuss alternatives to automated apply it to different modelling languages. In this article we planning that may be more appropriate (Section 5). investigate the use of Automated Planning for this purpose. 8 3. PLANNING TECHNIQUES the goal. Automated planning is a technique coming from artificial intelligence research. It aims to create plans, which are se- Regression planning is a backward state-space search that quences of primitive actions that lead from an initial state starts in the goal state and searches a sequence of actions to a state meeting a specific predefined goal. To accomplish that reach the initial state. This algorithm avoids the prob- this, the planner decomposes the world into logical condi- lems of the previous one by working only with relevant ac- tions and represents a state as a conjunction of literals. As tions. The problem of this algorithm is that it is not always input the planner needs a planning environment, composed obvious to find a possible predecessor of an action. of an initial state, a desired goal and a set of primitive ac- tions that can be performed. The initial state represents Another distinction can be made between total-order and the current state of the world. The goal is a partially spec- partial-order planning. With the former approach, the set ified state that describes the world that we would like to of actions that composes the strategy found by the algo- obtain. The actions express how each element of a state can rithm is strictly linear and ordered from the initial state to be changed. The actions are composed of a precondition and the goal. This category of algorithms cannot execute dif- an effect. The effect of an action is executed if and only if ferent actions simultaneously and cannot take advantage of the precondition is satisfied. the subdivision of a goal. Instead, partial-order planning (POP) explores the plan-space without committing to a to- Classical planning is an automated planning subset that aim tally ordered sequence of actions. POP works back from the to find a sequence of actions that reaches a desired state goal to the initial state and it can place two actions into a in a finite, static, deterministic and fully observable world. strategy without specifying which comes first. As a result, In general a planning approach consists of a representation these actions can be executed in parallel and their order is language used to describe the problem and an algorithm unimportant because they achieve different sub-divisions of representing the mechanism to solve the problem. the goal [22, 23]. Neither total-order nor partial-order is ef- ficient without a good heuristic function that estimates the Fikes et al [7] developed, in 1971, a formal planning repre- distance from a state to the goal. sentation language called STRIPS (STanford Research In- stitute Problem Solver ). In 1989, Pednault [21] developed Many planners exist that implement some variant of a plan- a more advanced and expressive language called ADL (Ac- ner algorithm. In this article we use the heuristic state-space tion Description Language, not to be confused with Archi- progression planner called FF (for “Fast-Forward Planning tecture Description Language). ADL has an improved ex- System” [12, 13]). It is considered by [23] as the “The most pressiveness compared to STRIPS. In particular, ADL ap- successful state-space searcher”, and was awarded for Out- plies the open world principle: unspecified literals are con- standing Performance at the AIPS 2000 planning competi- sidered as unknown instead of being assumed false. ADL tion and Top Performer at the AIPS 2002 planning compe- also allows to use negative literals and disjunction, whereas tition. FF has been chosen not only because of its perfor- STRIPS only allows positive literals and conjunctions. In mance, but also because it uses PDDL language with full recent years a standard PDDL (Planning Domain Defini- ADL subset support, including positive and negative liter- tion Language) [10] has been developed for the International als, conjunction and disjunction, negation, typing, and logic Planning Competition (IPC) of the International Conference quantification in the desired goal. This is crucial to our on Artificial Intelligence Planning and Scheduling (ICAPS). approach, as will be explained in the next section. PDDL is a generic language allowing to represent the syntax of STRIPS, ADL and other languages. Even if PDDL cov- 4. AUTOMATED PLANNING IN ACTION ers all the functionalities of these languages, the majority of 4.1 Case Study planners only implement the STRIPS subset [14]. The most Design models can be of different types (e.g. UML, Petri recent version of PDDL is version 3.0 [9]. This language nets, feature models, business process models). In this arti- is used in the competition to compare the benchmarks of cle we restrict ourselves to UML class diagrams [20]. They different planning approaches [23]. can suffer from many kinds of inconsistencies, such as struc- tural and behavioural inconsistencies. Figure 1 illustrates a Two main approaches exist to solve classical planning prob- simple class diagram containing two structural inconsistency lems [14]: (1) translating the planning problem into a prob- occurrences of type “inherited cyclic composition” and two lem that can be solved by a different approach (e.g. a occurrences of type “cyclic inheritance” [27]. boolean satisfiability problem, a constraint satisfaction prob- lem, or a model checking problem); (2) generating a search An inherited cyclic composition inconsistency arises when space (which can be either a state space, a plan space, or a a composition relationship and an inheritance chain form a planning graph) and looking for a solution plan in this space. cycle that would produce an infinite containment of objects We will focus on this second approach only. Depending on upon instantiation. Both occurrences, ICC1 and ICC2, of the direction in which the state space is traversed to look this inconsistency in Figure 1 arise with the same composi- for a solution, we can distinguish between: tion relationship, between Vehicle and Amphibious Vehi- cle, but with different inheritance chains. The first occur- Progression planning is a forward search that starts in the rence ICC1 appears in the inheritance chain Vehicle ← Boat initial state and tries to find a sequence of actions that ← Amphibious Vehicle. The second inconsistency ICC2 oc- reaches a goal state. The problem of this algorithm is that it curs in the inheritance chain Vehicle ← Car ← Amphibious does not exclude irrelevant actions. An action is considered Vehicle. A cyclic inheritance inconsistency arises when an relevant if it can achieve the goal or one of the conjuncts of inheritance chain forms a cycle. Figure 1 has two occur- 9 account any dependency between inconsistency occurrences Vehicle or their resolution actions. The metamodel for our class diagram is given below using Aircraft Bicycle Motorcycle Boat Car PDDL syntax. Each metamodel element is represented by a unique id through which it can be referred. Amphibious (Class ?id - class_id ?name - String) Helicopter Airplane (Generalisation ?id - g_id ?label - String Vehicle 1..* ?child_class - class_id ?parent_class - class_id) (Association_End ?id - ae_id ?class - class_id ?role - String ?upper_mult - Cardinal ?lower_mult - Cardinal Figure 1: Class diagram with 4 inconsistency occurrences, ?composite - Boolean) inspired by [27]. (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 be- rences CI1 and CI2 of this type of inconsistency. The first low. It contains only the elements that are involved in the occurrence CI1 forms an inheritance cycle that involves the inconsistency occurrences. This is illustrated by the shaded classes Vehicle, Boat and Amphibious Vehicle. The sec- part of Figure 1. ond occurrence CI2 forms an inheritance cycle that involves (Class c1 Vehicle) the classes Vehicle, Car and Amphibious Vehicle. (Class c5 Boat) (Class c6 Car) (Class c9 Amphibious_Vehicle) All four aforementioned inconsistency occurrences share two (Generalisation g4 label4 c5 c1) of the three classes that compose their respective inheri- (Generalisation g5 label5 c6 c1) (Generalisation g8 label8 c9 c5) tance chains: Vehicle and Amphibious Vehicle. Because (Generalisation g9 label9 c9 c6) of this overlap, it is possible to resolve more than one incon- (Generalisation g10 label10 c1 c9) sistency occurrence with the same resolution action. For ex- (Association_End ae1 c9 role1 star one non) (Association_End ae2 c1 role2 one one yes) ample, removing the composition relationship between Ve- (Association a1 ass1 ae1 ae2) hicle and Amphibious Vehicle solves the two inconsistency occurrences ICC1 and ICC2. Removing the inheritance rela- The set of actions that can be performed to change a model tionship between Boat and Amphibious Vehicle solves the are represented in terms of a precondition that must hold two inconsistency occurrences ICC1 and CI1. This clearly before the execution and the action to execute. In our ap- illustrates that, in order to resolve model inconsistencies in proach, inspired by [2], the set of actions corresponds to the an optimal way, it is important to consider all inconsisten- elementary operations (basically, create, modify and delete) cies simultaneously. In [17, 18], the impact of dependen- of the different types of model elements that can be derived cies between model inconsistencies and their resolution ac- from the metamodel. These elementary operations, com- tions were studied using the notion of critical pair analysis bined with the logic literals of the metamodel, allow us to of graph transformation rules. compute the list of all possible actions. As an example, the specification of modify_Association_Name is given below. (:action modify_Association_Name 4.2 Planning for Inconsistency Resolution :parameters (?id - id ?name - String ?ass_end_1 - ae_id Using the example of Figure 1, we illustrate how to cre- ?ass_end_2 - ae_id ?new_name - String) :precondition (Association ?id ?name ?ass_end_1 ?ass_end_2) ate a sequence of inconsistency resolution actions with au- :effect (when (not (= ?name ?new_name)) tomated planning. We require as input an initial state (the (and (not (Association ?id ?name ?ass_end_1 ?ass_end_2)) inconsistent model), a set of possible actions (that change (Association ?id ?new_name ?ass_end_1 ?ass_end_2))) the model) and a desired goal (the consistent model). Plan- ) ning requires logic conditions as input, so the whole model The desired goal is a partially specified state, represented environment (e.g. model, meta-model, detection rules) is as a conjunction of literals using logic quantification. It spec- translated into a conjunction of logic literals. The syntax of ifies the objective that we want to reach, namely a consistent PDDL is Lisp-like. Each logic literal is a tuple represented model. To represent this consistent model we can use two between parentheses. The tuple starts with the name of alternatives: (1) the negation of the inconsistency detection the literal, followed by pairs of variable names and their rules; (2) or the negation of the inconsistency occurrences. type (separated by a “–”). There are no primitive types in An inconsistency detection rule is a conjunction of literals PDDL. More information about the PDDL syntax can be representing a pattern that, if matched in the model, detects found in [8]. inconsistency occurrences. The initial state is expressed as a conjunction of literals, The inherited cyclic composition inconsistency detection rule and represents the current world. In our case the initial state using the PDDL syntax is given bellow. Observe that it only will be the inconsistent model. We can choose between three specifies an inheritance chain involving three classes. PDDL different representations of this initial state: (1) using the syntax does not allow to express transitive closure to make complete model; (2) using a partial model that contains only the rule more generic. those elements that are involved in one or more inconsistency (exists (?a - class_id ?b - class_id ?c - class_id) occurrences; (3) using a partial model that contains only (and those elements that are involved in a single inconsistency (exists (?g - g_id ?Label - g_label) (Generalisation ?g ?Label ?c ?a)) occurrence. We exclude option (3) as it only allows us to (exists (?g - g_id ?Label - g_label) solve one inconsistency at a time, and it does not take into (Generalisation ?g ?Label ?b ?c)) 10 (exists (?ae - ae_id ?role - ae_role as desired goal, the resolution plan of Figure 2 was gener- ?upper - upper_cardinal ?lower - lower_cardinal) ated in 14.84 seconds on average with a very low standard (Association_End ?ae ?a ?role ?upper ?lower yes)) (exists (?ae - ae_id ?role - ae_role deviation of 0.09 seconds. Using a partial model as initial ?upper - upper_cardinal ?composite - boolean) state, and the negation of the inconsistency occurrences as (Association_End ?ae ?b ?role ?upper one_l ?composite)) desired goal, the resolution plan of Figure 2 was generated )) in 0.268 seconds on average, with a standard deviation of The advantage of using alternative (1) above is that it can 0.004 seconds. be used to detect and resolve inconsistency occurrences at the same time. Alternative (2) will only be able to resolve To verify whether the proposed approach scales up to larger inconsistency occurrences that have already been identified models, we have stress-tested both of the successful experi- previously. On the other hand, as we will see later, alter- ments (using the negation of the inconsistency occurrences native (1) suffers from severe scalability problems. In both as desired goal). Again each experiment was executed 10 alternatives we use logic negation to express the fact that times and the average time and standard deviation was com- we do not want inconsistencies in the model. Because nega- puted. tion of the conjunction of literals is used we need a planning approach that allows the use of disjunction and negative lit- First, we artificially augmented the size of the motivating erals in the goal. This is one of the main reasons why we example of Figure 1 by adding an increasing number of iso- have selected FF as a planning tool for our experiments. lated classes to the model (from 1 class to 20 classes). Since these classes are unrelated to the inconsistency occurrences The plan is a sequence of actions that reaches the desired that the algorithm needs to resolve, the algorithm is still goal. It is generated automatically by the domain indepen- able to find the same resolution plan and the partial model dent planning algorithm. A complete resolution plan that is left untouched. However, the time it takes to generate a solves the four inconsistency occurrences of the motivating plan increases as the model size increases. example is shown in Figure 2. Remark that our approach prohibits the generation of a resolution plan that leads to Figure 3a illustrates the timing results if we use the com- ill-formed models (i.e., models that do not conform to their plete model as initial state. It takes only 15 seconds for metamodel). our initial example, but it takes more than 5 hours for the model with 20 more added classes. A regression analysis re- delete_Generalisation : veals an exponential relation with coefficient of determina- (Generalisation g10 label10 c1 c9) tion R2 = 0.982, indicating a very good fit of the regression modify_Association_End_Lower_Multiplicity : model. Two other candidate regression models we verified from: (Association_End ae1 c9 role1 star one non) had a lower goodness of fit: 0.977 for a quadratic polynomial to: (Association_End ae1 c9 role1 star zero non) model and 0.884 for a power curve. These results show that using a complete model as initial state does not scale up to Figure 2: Complete resolution plan that resolves all four larger models. inconsistency occurrences. Secondly we studied the timing results when the size of the 4.3 Scalability Study partial model increases. The motivating example of Figure 1 contains an inheritance chain of classes for the two types of There are different ways in which to specify the input for the considered inconsistencies. We artificially augmented the automated planning algorithm. To specify the initial state, size of the model by increasing the length of the inheritance we can either use the complete model or we can restrict the chains involved in the inconsistency occurrences. We did search space by using a partial model that contains only this gradually, by adding between one and eight intermedi- those elements that are involved in the inconsistency occur- ate superclasses, and computing the timing results for each rences. To specify the desired goal, we can choose between partial model. using the negation of the inconsistency detection rules or using the negation of the inconsistency occurrences them- Figure 3b shows the timing results of carrying out this exper- selves. iment. The figure shows a strong increase in time to compute the resolution plan as the size of the partial model increases. In order to assess which of the above four choices produces The standard deviation was always below 2%, and less than the best results, we compared the timing results of each 0.4% on average. A regression analysis reveals an exponen- considered possibility. In order to remove noise, each ex- tial growth (with coefficient of determination R2 = 0.995) in periment was executed 10 times and the average time and the time needed to find a resolution plan. Two other regres- standard deviation was computed. All experiments were sion models we verified had a lower goodness of fit: 0.927 for carried out on a 64-bit Apple MacBook with 2.4 GHz Intel a quadratic polynomial model and 0.949 for a power curve. Core 2 Duo processor and 4GB RAM, 2.9GB of which were available for the experiment. We also verified whether the number of inconsistency occur- rences to be resolved affected the timing results. To achieve The experiments using the complete model as initial state this, we reduced the desired goal by generating plans that and the negation of the inconsistency detection rules as de- resolve only 2 or 3 inconsistency occurrences, respectively. sired goal and using the partial model as initial state and In all of these cases we found an exponential growth in time. the negation of the inconsistency detection rules as desired We obtained a goodness of fit R2 = 0.991 for resolving 2 goal, ran out of memory. Using the complete model as ini- inconsistency occurrences, and R2 = 0.992 for resolving 3 tial state and the negation of the inconsistency occurrences 11 R! = 0.9816 Real Time 30000 20000 10000 inconsistency occurrences. Finally, we verified whether the size of the metamodel affects 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 the timing results. To achieve this, we added a new element to the metamodel: 20000 (Attribute ?id - attribute_id ?class - class_id ?Name - String ?Type - Type) 15000 This requires to add three new actions, to create, modify and delete attributes, respectively. It did not affect the timing # Added 0 1 2 3 4 5 6 7 8 9 Avg Std results as long as attributes are not used in the initial state Time (s) Classes 0 0,390 0,269 0,27 0,269 0,268 0,268 0,267 0,276 0,271 0,127 0,2673 0,05048833 18,89% 10000 2 1 3 2,089 0,880 7,102 0,741 2,077 7,085 0,75 2,06 7,08 0,744 2,071 7,111 0,745 2,059 7,082 0,745 2,066 7,085 0,745 2,063 7,083 0,745 2,075 7,086 0,747 2,056 7,097 0,744 2,080 7,066 0,7583 2,0691 7,0872 0,00116496 0,15% 0,00910161 0,44% 0,01358505 0,19% and the desired goal. 4 17,469 17,385 17,41 17,392 17,387 17,382 17,412 17,406 17,399 17,398 17,4035 0,01015505 0,06% 5 40,073 40,014 40,02 39,985 40,039 39,970 40,021 40,067 39,939 39,995 40,012 0,04048787 0,10% 6 86,647 86,323 86,53 86,373 86,308 86,202 86,315 86,268 86,335 86,415 86,3711 0,09767722 0,11% 7 190,834 189,670 191,63 191,153 191,396 189,989 191,130 189,767 190,803 190,553 190,6927 0,6618924 0,35% 8 476,024 470,955 476,83 473,100 477,228 472,734 483,688 473,010 476,349 473,134 475,3051 3,72613423 0,78% 0,27% As a next step, we increased the size of the initial state by 5000 600 adding 1 to 20 attributes to the existing classes of the model. R! = 0,9946 The desired goal was not modified. The standard deviation 450 was 0,7% on average. The results are shown in Figure 3c. 0 For an initial state with 1 attribute added the time was 0.27 300 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 # Added Atributes 0 Number of isolated classes added to the model 1 2 3 4 5 6 7 8 9 Avg Std seconds. After adding 20 attributes it was 3.5 seconds. A (a) Using the 150 0 1 complete model as initial state. 0.280 0.269 0.262 0.267 0.26 0.26 0.260 0.265 0.264 0.264 0.264 0.266 0.262 0.267 0.265 0.269 0.267 0.267 0.265 0.269 0.2652 0.2667 0.00212132 0.00199553 regression analysis revealed a quadratic polynomial with a 2 0.278 0.279 0.28 0.277 0.276 0.278 0.279 0.278 0.279 0.278 0.2777 0.00141421 3 4 5 0.300 0.315 0.295 0.313 0.30 0.31 0.298 0.314 0.298 0.313 0.294 0.311 0.299 0.312 0.298 0.314 0.300 0.315 0.295 0.315 0.2975 0.3135 0.002 0.00140789 goodness of fit R2 = 0.994. Two other regression models we 0.350 0.348 0.35 0.343 0.348 0.349 0.345 0.346 0.348 0.347 0.3469 0.00199553 verified were an exponential model with R2 = 0.982 and a 0 16 2 0.388 3 0.390 40.39 5 0.391 6 0.390 7 0.459 8 0.392 0.389 0.393 0.392 0.3971 0.02426895 7 0.442 0.444 0.44 0.444 0.444 0.446 0.444 0.444 0.445 0.449 0.4441 0.00277424 power model with R2 = 0.763. 8 0.518 0.532 0.51 0.521 0.528 0.523 0.521 0.518 0.517 0.516 0.5207 0.00465794 9 500 10 0.611 0.711 0.605 0.711 0.61 0.71 0.606 0.709 0.603 0.707 0.608 0.708 0.606 0.705 0.606 0.707 0.607 0.710 0.614 0.713 0.6075 0.7091 0.00320435 0.00244584 11 0.852 0.851 0.84 0.843 0.840 0.839 0.843 0.839 0.842 0.838 0.8431 0.00226779 12 1.001 0.997 1.00 1.001 1.003 1.017 0.998 1.001 0.997 1.002 1.0013 0.00659951 13 1.180 1.180 1.18 1.186 1.181 1.197 1.197 1.188 1.185 1.178 1.1856 0.00688684 14 15 16 17 1.398 1.628 1.945 2.273 1.398 1.639 1.950 2.272 1.40 1.65 1.95 2.27 1.396 1.640 1.958 2.268 1.403 1.643 1.946 2.272 1.394 1.637 1.940 2.266 1.400 1.642 1.954 2.273 1.389 1.652 1.953 2.269 1.389 1.645 1.944 2.270 1.401 1.644 1.961 2.270 1.3964 1.6415 1.95 2.2704 0.00523723 0.00437526 0.00717013 0.00223207 4.4 Discussion 375 18 2.643 2.631 2.63 2.630 2.650 2.622 2.640 2.643 2.637 2.645 2.6369 0.00950845 The exponential timing results obtained through the exper- 19 3.057 3.057 3.05 3.057 3.067 3.046 3.057 3.069 3.057 3.056 3.0575 0.00744384 20 3.528 3.540 3.53 3.533 3.530 3.533 3.532 3.541 3.541 3.537 3.5345 0.00450198 iments described in the previous section, indicate that the Chart 4 4 approach is not usable in practice. Using the approach to Time (s) R! = 0.9939 250 resolve inconsistencies one by one would be feasible because the partial model and desired goal will remain relatively 3 small. This is not a good solution, because it does not take 125 full advantage of automated planning. In addition, incon- Avg sistency occurrences and their resolution actions are often 2 interdependent. Another important limitation we encoun- 0 tered is the expressiveness of the PDDL syntax. It does not 0 1 2 3 4 5 6 7 8 Number of related classes added to the model. offer important features such as transitive closure, primitive (b) Adding intermediate 1 superclasses to the partial types, numbers. In addition, literals cannot be modified model. (they have to be deleted and added again). A third limita- 0 tion of our approach is that, currently, we generate only a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 single resolution plan. The resolution of several inconsisten- 4 cies can give rise to several different resolution plans, i.e., different sequences of resolution actions leading to possibly different consistent models. 3 Several improvements to the approach can be envisaged. A first improvement is to adapt the planning algorithm so that 2 it generates several resolution plans among which the model designer could choose. The scalability problem could be adressed by implementing a domain-specific planner that 1 can be optimized by making it more specific and more per- formant for the specific problem we want to tackle. In addi- 0 tion, since we are not constrained by the PDDL syntax, this 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 would solve the problems of expressiveness we encountered. (c) Adding class attributes to the partial model. The timing results could be improved by using regression planning as opposed to progression planning [23], as used Figure 3: Scalability timing results (the y-axis represents by FF. Progression planning depends mainly on the size of the time in seconds). the initial state and it does not exclude irrelevant actions. Regression planning works only with relevant actions. Be- cause of this, the search space will be significantly smaller. Further experiments are needed to verify whether regression planning will be more appropriate for our needs. 12 5. BEYOND PLANNING - Bruxelles International et du Fonds de la Recherche Scientifique, du Since the automated planning approach does not meet our Ministère Français des Affaires étrangères et européennes, du Min- expectations, we would also like to study other techniques istère de l’Enseignement supérieur et de la Recherche dans le cadre coming from the domain of artificial intelligence for the pur- des Partenariats Hubert Curien. pose of resolving modeling inconsistencies in an automated way. 7. REFERENCES [1] M. A. Almeida da Silva, A. Mougenot, X. Blanc, and Logic-based approaches have been used for different but re- R. Bendraou. Towards automated inconsistency lated purposes in inconsistency resolution. Marcelloni and handling in design models. In CAiSE 2010, Lecture Akist [15, 16] used fuzzy logic to cope with methodologi- Notes in Computer Science. Springer, 2010. cal inconsistencies in design models. It remains to be seen [2] X. Blanc, A. Mougenot, I. Mounier, and T. Mens. whether this approach can be generalised to resolve any kind Detecting model inconsistency through of model inconsistency. Castro et. al. [5] used logic abduction operation-based model construction. In Proc. Int’l to detect and resolve inconsistencies in source code. Some Conf. Software Engineering (ICSE), volume 1, pages preliminary results we carried out to apply this approach to 511–520, 2008. resolve inconsistencies in design models appeared promising, [3] J. Brownlee. Variable neighbourhood search. Technical but further work is necessary to assess whether the approach Report CA-TR-20100206-1, The Clever Algorithms scales up and works in practice. Almeida da Silva et al. [1] Project http://www.CleverAlgorithms.com, February implemented a Prolog program to generate resolution plans 2010. for inconsistent models. The approach is promising but still [4] G. Caporossi and P. Hansen. Variable Neighborhood requires a lot of manual encoded input to specify the gener- Search for Extremal Graphs 1. The AutoGraphiX ator functions and the causes of the inconsistencies. System. Discrete Math., 212:29 – 44, 2000. Harman [11] advocates the use of search-based approaches [5] S. Castro, J. Brichau, and K. Mens. Diagnosis and in software engineering. This includes a wide variety of semi-automatic correction of detected design different techniques and approaches such as metaheuristics inconsistencies in source code. In IWST ’09: (e.g. variable neighborhood search [3, 4]), local search al- Proceedings of the International Workshop on gorithms, automated learning, genetic algorithms [23]. We Smalltalk Technologies, pages 8–17, New York, NY, believe that these techniques could be applied to the problem USA, 2009. ACM. of model inconsistency management, because it satisfies at [6] A. Egyed, E. Letier, and A. Finkelstein. Generating least three important properties that motivate the need for and evaluating choices for fixing inconsistencies in search-based software engineering: the presence of a large UML design models. In Proc. Int’l Conf. Automated search space, the need for algorithms with a low computa- Software Engineering, pages 99–108. IEEE, 2008. tional complexity, and the absence of known optimal solu- [7] R. Fikes and N. J. Nilsson. STRIPS: A new approach tions. to the application of theorem proving to problem solving. In 2nd International Joint Conference on In order to assess the adequacy of all these different ap- Artificial Intelligence., pages 608–620, 1971. proaches to inconsistency management, there is also an ur- [8] A. Gerevini and D. Long. BNF description of PDDL gent need to define benchmarks allowing to compare them. 3.0. http://zeus.ing.unibs.it/ipc-5/, October 2005. Such a benchmark should contain at least a set of shared [9] A. Gerevini and D. Long. Plan constraints and case studies on which to evaluate each approach; as well as preferences in PDDL3 : The language of the fifth a set of clearly identified criteria enabling the comparison of international planning competition. Technical report, approaches and their quality. Department of Electronics for Automation, University of Brescia, Italy, August 2005. 6. CONCLUSION [10] M. Ghallab, A. Howe, C. Knoblock, and In this article, we explored the use of automated planning, a D. McDermott. PDDL — the planning domain logic-based approach originating from artificial intelligence, definition language. Technical Report DCS TR-1165, for the purpose of resolving model inconsistencies. We are Yale Center for Computational Vision and Control, not aware of any other work having used this technique for New Haven, Connecticut, 1998. this particular purpose. The results of our experiments re- [11] M. Harman. Search based software engineering. In veal that the approach is feasible but suffers from various Computational Science - ICCS 2006, volume scalability problems. We have discussed ways in which the 3994/2006 of Lecture Notes in Computer Science, scalability can be improved. We have also discussed alter- pages 740–747. Springer Berlin / Heidelberg, 2006. native search-based techniques that may deal with inconsis- Workshop on Computational Science in Software tency resolution in a scalable way. Engineering (CSSE’06). [12] J. Hoffmann. FF: The Fast-Forward Planning System. Acknowledgements. This work has been partially supported by (i) The AI Magazine, 2001. the F.R.S. – FNRS through FRFC project 2.4515.09 “Research Cen- [13] J. Hoffmann and B. Nebel. The FF Planning System: ter on Software Adaptability”; (ii) research project AUWB-08/12- Fast plan generation through heuristic search. Journal UMH “Model-Driven Software Evolution”, an Action de Recherche of Artificial Intelligence Research, 14:253–302, 2001. Concertée financed by the Ministère de la Communauté française [14] S. Jiménez Celorrio. Planning and Learning under - Direction générale de l’Enseignement non obligatoire et de la Uncertainty. PhD thesis, Universidad Carlos III de Recherche scientifique, Belgium; (iii) Avec le soutien de Wallonie Madrid, 2010. 13 [15] F. Marcelloni and M. Aksit. Leaving inconsistency using fuzzy logic. Information and Software Technology, 43(12):725 – 741, 2001. [16] F. Marcelloni and M. Aksit. Fuzzy logic-based object-oriented methods to reduce quantization error and contextual bias problems in software development. Fuzzy Sets and Systems, 145(1):57 – 80, 2004. Computational Intelligence in Software Engineering. [17] T. Mens and R. Van Der Straeten. Incremental resolution of model inconsistencies. In J. L. Fiadeiro and P.-Y. Schobbens, editors, Algebraic Description Techniques, volume 4409 of Lecture Notes in Computer Science, pages 111–127. Springer-Verlag, 2007. [18] T. Mens, R. Van Der Straeten, and M. D’Hondt. Detecting and Resolving Model Inconsistencies Using Transformation Dependency Analysis. In Proc. Int’l Conf. Model Driven Engineering Languages and Systems (MoDELS), volume 4199 of Lecture Notes in Computer Science, pages 200–214. Springer-Verlag, October 2006. [19] C. Nentwich, W. Emmerich, and A. Finkelstein. Consistency management with repair actions. In Proc. 25th Int’l Conf. Software Engineering, pages 455–464. IEEE Computer Society, May 2003. [20] Object Management Group. Unified modeling language: Super structure version 2.1, january 2006. [21] E. P. D. Pednault. ADL: Exploring the middle ground between STRIPS and the situation calculus. In 1st International Conference on Principles of Knowledge Representation and Reasoning (KR’89), pages 324–332, 1989. [22] J. S. Penberthy and D. S. Weld. Ucpop: A sound, complete, partial order planner for adl. In 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92), pages 103–114, 1992. [23] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2nd edition, 2002. [24] D. C. Schmidt. Guest editor’s introduction: Model-driven engineering. IEEE Computer, pages 25 – 31, February 2006. [25] G. Spanoudakis and A. Zisman. Inconsistency management in software engineering: Survey and open research issues. In Handbook of Software Engineering and Knowledge Engineering, pages 329–380. World scientific, 2001. [26] T. Stahl and M. Völter. Model Driven Software Development: Technology, Engineering, Management. Wiley, 2006. [27] R. Van Der Straeten. Inconsistency management in model-driven engineering: an approach using description logics. PhD thesis, Vrije Universiteit Brussel, 2005. [28] Y. Xiong, Z. Hu, H. Zhao, H. Song, M. Takeichi, and H. Mei. Supporting automatic model inconsistency fixing. In H. van Vliet and V. Issarny, editors, Proc. ESEC/FSE 2009, pages 315–324. ACM, 2009. 14