Goal models described with the Goal-oriented Requirement Language (GRL) are amenable to various kinds of analyses, including quantitative and qualitative propagations of satisfaction values. However, most approaches use bottom-up evaluations involving operational semantics that can only answer “what if” questions. This paper introduces a new declarative semantics for GRL based on a constraint-oriented interpretation of goal models. This semantics enables constraint solvers to evaluate and optimize goal models in a way that is more generic than bottom-up and top-down propagation techniques, hence enabling other questions to be answered. A prototype that combines the jUCMNav modeling tool and the JaCoP constraint solver to support quantitative evaluations is used to demonstrate the feasibility and potential of this new approach.
The User Requirements Notation (URN) is a language that combines scenario
modeling (with Use Case Maps – UCM) and goal modeling (with the Goal-oriented
Requirement Language – GRL) to support requirements engineering activities,
especially for reactive systems and business processes. This standard language is defined with
a metamodel, a concrete graphical syntax, and an XML-based interchange format [
In GRL, a model is composed of intentional elements (i.e., goals, softgoals, tasks,
resources, and beliefs) connected by links (decomposition, contribution, and
dependencies) and potentially allocated to actors. The URN standard includes a set of
guidelines and requirements describing how to analyze GRL models based on a set of
initial satisfaction values given to some of the intentional elements (i.e., an evaluation
strategy), which are then propagated to the other intentional elements through the
links connecting them. Satisfactions in GRL can be qualitative (satisfied, denied, etc.)
or quantitative (integer in [!100..100]). Similarly, contributions can have a qualitative
weight (make, break, etc.) or a quantitative one ([!100..100]). One particularity of
GRL (which does not exist in i*) is that intentional elements in an actor can have an
importance factor that, when combined to satisfaction levels, helps measure the
overall satisfaction of an actor (again, these measures can be qualitative or quantitative).
Although the standard does not impose specific propagation algorithms to evaluate
a goal model against a given evaluation strategy, several algorithms (fully
quantitative, fully qualitative, and hybrid) are suggested and are further explored in [
Bottom-up analysis in limitative in practice; it is akin to testing in terms of analytical power, i.e., one often uses many strategies to find a good global trade-off or find an optimal satisfaction value for a given goal or actor (usually without any guarantee). There is a need to support top-down and inside-out analysis techniques for GRL in order to find solutions to more interesting questions such as “is there a way to reach this satisfaction level for this top-level goal?”, or more generically “what is the maximum satisfaction of this goal given these constraints on other goals?”.
This paper presents a new semantics and an algorithm for GRL model analysis that will enable modelers to answer all these types of questions. Tool support is also provided to demonstrate the feasibility of the approach. 2
This research aims to support a generic and automatic propagation algorithm for GRL models that can support bottom-up, top-down, and inside-out analysis, as well as optimizations in the presence of constraints (i.e., intentional elements initialized anywhere in the model). To enable such an algorithm, we need to move away from the operational semantics often associated with GRL to a declarative semantics amenable to solving in the presence of constraints. Our approach is as follows: i) provide a declarative semantics for GRL (in this paper, we limit ourselves to quantitative evaluations only), ii) define a transformation of this semantics in terms of a constraintoriented language for which automated solvers exist, and iii) prototype the approach.
The prototype algorithm is integrated to the jUCMNav tool as one of its GRL
evaluation algorithms. jUCMNav is a free Eclipse-based URN modeling and analysis tool
that already supports qualitative, quantitative, and hybrid evaluation mechanisms for
GRL, but that only use bottom-up propagation [
This section briefly presents the three main contributions of our work. 3.1
The proposed declarative semantics for GRL is expressed in mathematical terms.
Intuitively, the syntactic domain is composed of intentional elements (with their types
and importance factors), decomposition links (and their types: OR or AND),
contribution links (and their weights), dependency links, actors, and a strategy, with the
semantics and well-formedness rules expressed in the URN standard (e.g., an
intentional element has only one type of decomposition). The semantic domain is one where
each syntactically correct GRL diagram is interpreted as an evaluated set of
intentional elements and actors, where evaluations are integers between !100 (denied) and 100
(satisfied), inclusively, as required by the URN standard [
a) AND-decomposition
b) OR-decomposition ܣ ͳ ܵ AND ܣ ʹ ܵ ܥ 2 ǥ ܥܹ ܰ … ܣ ܰ ܥ ܰ ܵ OR ܱ ʹ ܵ ܦ 2 ǥ … ܱ ܰ ܦ ܰ c) Contributions
d) Dependencies (assuming different actors) Ù ݒ ሺ ܵ ሻ ൌ ٿ ௫ேୀଵ ݒሺܵሻ ݒܦሺ
௫ ሻ ሺ ͳെͲǡ ሺ ͳͲǡ ଵ௫ஸே ݒሺܣ ௫ ሻ σ ௫ேୀଵ ݒܥሺ ௫ ሻ ൈ ܥܹ ௫ Τ ͳͲ ሻ The relationship for the OR-decomposition is similar, but with max instead of min. 3.2
The JaCoP library comes with a set of functions and search mechanisms that can support an implementation of the semantics introduced in the previous section. Each intentional element in the GRL model becomes a unique variable in JaCoP, with [!100..100] as a domain. The equations and inequalities describing each of the intentional elements in terms of its links are converted to JaCoP constraints. For example, B£A becomes XlteqY(A,B), C=min(A,B) becomes Min({A,B},C), and so on (some complex relationships need to be split into intermediate constraints along the way). Finally, the strategy definition provides constant values to the variables corresponding to the intentional elements initialized by that strategy.
We also experimented with the notion that GRL tasks that are leaf nodes in a model should only have 100 or 0 as possible satisfaction values, denoting the fact that these tasks are either performed/selected completely or not at all. It is trivial to detect such situations and to add corresponding JaCoP constraints.
JaCoP allows for different types of searches through the solution space to come up with a solution, when one exists. For example, one can maximize, minimize, or find median values for the variables. Heuristics are also available to accelerate the search. Multiple solutions can also be reported when more than one exists. However, refining the model while navigating through multiple solutions is left for future work. 3.3
Our proof-of-concept implementation integrates the JaCoP library to jUCMNav [
Fig. 2a illustrates the traditional situation where we have the equivalent of a
bottom-up propagation (leaves are initialized). Our algorithm can actually do everything
that the quantitative algorithm in [
a) Bottom-up b) Top-down c) Generic, with constraints d) Unsolvable e) Top-down, with task f) Generic, with task This paper proposes a simple and yet powerful interpretation of GRL models through a declarative semantics amenable to transformations to constraint-oriented languages. The prototype implementation, which combines the jUCMNav modeling tool and the JaCoP constraint solver to support quantitative evaluations, demonstrates the feasibility and potential of the semantics and overall analysis approach.
Not only are the proposed semantics and quantitative propagation algorithm more
generic than the existing ones for GRL [
Extensions to this work include the support of remaining GRL concepts (e.g., XORdecomposition, tolerance, and satisfaction at the actor level), but also GRL extensions like key performance indicators. We could also consider a global satisfaction for the entire model computed from actor satisfaction levels. Better formalization of the semantics, including an assessment of its soundness and completeness, are also required. There should also be a way to specify in a GRL strategy whether some goals should be maximized or minimized, and this could be taken into consideration by constraint solvers for an enhanced analysis experience. We also need to explore the usefulness of adapting this work to qualitative and hybrid evaluations. Although early performance results of our prototype are encouraging (most average-sized models we have played with can be solved within several milliseconds, hence enabling modelers to explore different values for a strategy on the fly), we often faced situations where a certain combination of model/strategy requires hours to solve. These situations need to be investigated, with a way to stop long evaluations. Finally, we believe that such declarative semantics will enable researchers to explore the usability of various semantics of goal modeling languages (in terms of complexity and customization) for different categories of users, application domains, and development phases.
Acknowledgements. We thank NSERC for financial support, and P. Heymans and F. Roucoux for useful discussions on the topics of GRL formalization and analysis.