DEPS: a model- and property-based language for system synthesis problems

Abstract

DEPS (design problem specification) is a new modeling language designed to pose and solve system design problems. DEPS addresses problems of sizing, configuration, resource allocation and of architecture generation for systems. Unlike system modeling languages, which are dedicated to the representation of a defined system for evaluation or analysis, we propose a problem modeling language for representing the design problem with a view to its automatic resolution. Compared with other declarative problem modeling languages, DEPS is a declarative structured and property-based language that combines structural modeling features specific to object-oriented languages with problem specification features from constraint programming. The mathematical nature of the problems is described by formal properties encapsulated in models organized according to the architecture of the studied system. The main features of the language are presented in details and are illustrated with examples in different domains. An integrated modeling and solving environment called DEPS Studio allows the designer to express its models in DEPS, to compile the models and to compute automatically the solutions. The validation of the approach is done through two case studies. Finally, we will conclude with the studies and developments in progress which will be integrated into the next version of DEPS Studio.

1 Introduction

1.1 System modeling languages and problem modeling languages

A lot of work in the field of model-based system engineering (MBSE) has focused on the representation of fully defined systems in order to verify them, evaluate their performance or simulate their operation. It is therefore above all a question of applying an analytical approach to a known system rather than formalizing the engineering problem to be solved [1].

The development and diffusion of modeling languages for software engineering (UML) [2] and then for system engineering (SysML) [3] have produced languages well adapted to the description of systems. Nevertheless they remain solution-oriented. AADL [4] for software systems and Modelica for physical and multi-physical systems [5] are other examples of system description formalisms intended for analysis and simulation.

Moreover, still in the field of solution-oriented approaches, the development of the software tools that support them have motivated research [6, 7] to add the computational capabilities that are naturally missing in basic environments. Indeed, as stated in the OMG SysML tutorial [3]: "Computational engine is provided by applicable analysis tool and not by SysML". Let us also note some recent initiatives to introduce variability in SysML, i.e., degrees of freedom in a system description language coupled with a constraint programming library [1]. These works assume that the problem description is done in UML or in SysML and that its resolution is delegated to a suitable solver after a model transformation. Unfortunately these languages are made to describe systems and not to model problems. Finally, the development of such a model requires fast development phases which do not seem to us compatible with the heaviness of a model transformation approach [8].

These solution-oriented approaches are necessary for the detailed design phases of systems but insufficient for the preliminary design phases in which detailed models of system components are useless since the aim is to obtain one or more admissible system architectures as soon as possible. This limitation had been pointed out by [6] but does not seem to have been resolved since. Shah suggests that in order to make real progress it would be necessary to have a real object-oriented modeling language for engineering design problems, which would be the counterpart in the field of mathematical programming of what Modelica [5] is in simulation.

The OCL (object constraint language), a complement to UML despite its acronym, is not an exception to this rule. OCL is a specification language that typically allows us to specify invariant conditions that a UML model must check to be correct. But even in its most recent version [9] OCL constraints remain specifications, whose evaluation for verification purposes is not supported by the language itself and whose resolution for sizing purposes is not considered. This language is designed to verify that an instance of a model conforms to its model when it is entered; it is not designed to solve design problems.

The IEEE1220 [10] standard is representative of the solution-oriented approach. Its chapter "system definition stage" recommends a development process based on checking and system analysis.

Conversely, the recent ISO/IEEE 42020 standard [11] recommends, in the preliminary stages of system development, to conceptualize the system architecture by means of a representation of the problem space and then to determine its admissible technical solutions. It is obviously representative of a synthesis approach and our work fully fits into it.

More precisely, we are interested in the description of a language for modeling the design problems of technical systems in order to solve them. The systems considered are highly structured and can be either predominantly technological (mechanical, electrical, electronic, energetic systems, …) or either software intensive (embedded systems) or mixed (cyber physical systems).

The name modeling language is generally insufficient: We model something in order to do something with what has been modeled. In practice, we distinguish between system modeling languages and problem modeling languages. For the field of system design there are:

- languages used to model a system in order to manage it during the design project, or to evaluate its performance.

- languages for modeling a design problem with a view to its automatic resolution, i.e., to generate correct systems by construction.

1.2 Research goal

Our work falls within the scope of the second category of languages. Languages coming from mathematical programming and operational research allow a flat representation of a problem to be solved using variables, matrices, vectors, equations and inequalities to be satisfied. They also enable the mathematical formalization of an objective function to be optimized. Conversely, they have no structuring and abstraction capacity which does not allow an explicit representation of the structures inherent to the architecture design problem modeling activity. Our research goal is to propose a language built for modeling design problem for automatic computer resolution. The aim of this language is to fill the gap between current flat modeling languages and the need for sophisticated representation of structured problems.

We present in this paper the DEPS language. The purpose of DEPS is to allow the user first to formally pose a given design problem and then, after compilation, either to solve it, i.e., to find one or more solutions if they exist, or to optimize it, i.e., to find the best solution(s) in relation to given criteria. DEPS is a declarative language, based on models and properties that facilitate the modeling of system design problems. On the one hand, the structure and abstraction features allow to represent the architecture (the structure) of the system to be designed while the use of properties using mathematical concepts (parameters, unknowns, equations, inequalities) allows to pose the design problems associated with it: sizing, configuration, resource allocation etc.

1.3 Structure of the paper

The paper is organized as follows: Sect. 2 explains our motivation. The needs are exposed in Sect. 2.1, an analysis of the state of the art is done in Sect. 2.2, and the genesis of the DEPS project is presented in Sect. 2.3. In Sect. 3, we describe the language, focusing in particular on its capacities to express value domains, physical quantities, structural aspects and properties. Section 4 focuses on language constants and variables. In Sect. 5, the way of dealing with model instances is described in detail. Section 6 describes how to structure a problem and create relationships between model. The various properties that can be used in the language are described in Sect. 7. Section 8 presents the modeling and resolution environment called DEPS Studio which, through an implementation of the language, includes model edition, compilation and generation of solutions. Section 9 is dedicated to the validation of the approach through two case studies. Finally, Sect. 10 describes the ongoing work as well as some perspectives of future evolution.

2 Motivations

2.1 Representation and resolution needs for model-based system synthesis

The targeted systems of the MBSE that we consider, are physical, software-intensive or mixed (embedded, mechatronics, cyber-physics) systems.

We have seen that the classical MBSE approach is an analysis approach that does not model the problem but describes a solution. The classical calculation process associated with the definition model often integrates a loop for evaluating the performance of the described system to check whether the requirements of the specifications are met. In case of failure, certain parameters of the described system are modified to produce another system and so on inside a loop (cf Fig. 1).

Fig. 1

Analysis approach [17]

Architecture description languages (ADL) all have in common that they represent a system architecture produced by the designer without any guarantee as to its eligibility. Once modeled, the system must be evaluated according to a point of view adopted by the language in order to verify the requirements considered. Some languages are generalist, others are more specific to the architecture of the system and/or the requirements to be verified. As described in the INCOSE SE vision 2035 [12], ADLs allow to formalize the result of the architecture activity. On the one hand, for several years, work on systems engineering has led to the emergence of the SysML [3] system modeling language based on UML [2] and OCL [9]. Initially, a model realized in UML was supposed to represent a computer application, i.e., a solution to a given problem which one wishes to solve by the realization of a software. In the same way, SysML makes it possible to describe a system architecture that can be solved from several points of view using different diagrams. Recent works on SysML V2 [13] propose a dedicated formal language independent of OCL, but still position itself as the vector of a description of architecture and requirements, with the aim of evaluating this described architecture. On the other hand, several domain-specific modeling languages (DSMLs) have emerged in recent years. They depend on the type of system to represent and the type of point of view to be addressed. Let us mention, widely and without being exhaustive, Modelica [5] for the representation of physical systems with a view to simulating their dynamic behavior, AADL [4] for describing architectures of embedded systems, DEVS for discrete event systems [14], B and Event-b for real-time systems [15] or S2ML [16] for modeling systems with a view to their safety. Because of their common founding myth “to describe a system or an architecture without having formal assurance on the satisfaction of the requirements of the specifications”, sometimes bidirectional bridges have been established between these languages. In this context, the design process is conducted in an iterative manner, possibly using parametric optimization tools. The evaluation and/or proof software dedicated to each formalism acts as an evaluation function in the implementation of the optimization loop. These languages are thus adapted to express an architectural solution to be evaluated.

If we wish to work in the problem space and solve the problems encountered in system design, we will need to address the following types of problems [17]:

- System sizing (PT1): problem for which the architecture of the system is known but its dimensions are not (e.g., the length of an object). Unknowns are variables that are often continuous, sometimes discrete. Functional requirements can be quite complex and can be expressed as linear or nonlinear algebraic relationships between constants and variables.

- System configuration (PT2): configuration problems involve the choice of components based on a set of compatibility relationships, options, and cardinality. They are most often discrete-dominant problems.

- Resource allocation (PT3): allocation problems involve allocating physical resources to system functions (or deploying system functions on a set of resources) based on a set of functional and non-functional requirements.

- Architecture generation (PT4): System architecture problems combine the three previous problems. They are based on a specification combining requirements and constraints to produce architectures that will meet the specification. We can also talk about architecture synthesis.

To represent and solve such design problems, we will need additional capabilities to:

• 1. Formalize a sub-defined or partially defined system, i.e., one with degrees of freedom both from the point of view of the possible value ranges (discrete or continuous) for unknowns but also from the point of view of optional parts of the system structure (choices about components …). Partially defined system modeling includes structural and behavioral modeling.

• 2. Formalize the functional and non-functional requirements on the system in terms of declarative properties.

• 3. Solve the problem posed by finding values for the unknowns that are compatible with the declared properties.

As summarized in Fig. 2, this synthesis activity is complementary to the usual MBSE analysis and performance evaluation activity that [17] called MBSS for model-based system synthesis. The MBSS approach supports the idea of modeling the problem rather than the candidate solution and then solving the problem by producing correct-by-construction solutions instead of evaluating the performance of a candidate solution.

Fig. 2

Model-based system synthesis approach (MBSS) [17]

Of course, the analysis approach (cf Fig. 1) and the MBSS point of view (cf Fig. 2) are complementary. MBSS is suitable for preliminary system design phases, while system modeling and analysis tools are more suited to detailed design phases. They enable detailed analyses and simulations that are not possible with the algebraic tools of MBSS.

Several authors such as [6, 18,19,20,21] have shown the limits of the “analysis approach” in the context of the activity of representation and resolution of the problem of architecture synthesis, showing the need for a language of description of the problem for its resolution. Thus another approach is possible (as illustrated in Fig. 2), in which one starts from a sub-definite system architecture and a representation of the requirements to be satisfied and in which, with the help of a solution generation tool, one tries to obtain one or several architecture descriptions correct-by-construction.

A subdefinite architecture is an architecture for which the values of the design variables are not fixed. This approach requires a description language of the problem to solve. In theory, these kinds of languages are rather adapted to the design stage of the system architecture by allowing the automatic production of pre-sized and configured architectures that necessarily meet the expressed requirements. On the one hand, languages coming from mathematical programming and operational research allow a flat representation of a problem to be solved using variables, matrices, vectors, equations and inequalities to be satisfied. They also enable the mathematical formalization of an objective function to be optimized. Let us mention the OPL [22], AMPL [23], MiniZinc [24] and GAMS [25] languages as the main representatives of this type of formalism.

From our point of view, they suffer from a lack of structuring and abstraction capacity which does not allow an explicit representation of the structures inherent to the architecture design activity. On the other hand, work on the representation of software product lines has led to the emergence of interesting problem description languages for design. Thus, Clafer [19] proposes a unified model based on objects and features and allows the user to easily express logical relationships between these elements. Unfortunately for solving the full range of design problems, these languages only address configuration issues.

The DEPS language that is the subject of this paper is a proposed solution to tool the MBSS approach from the point of view of the representation of the design problem.

In addition, due to the typology of problems to be covered we will need to work both on real and integer variables. This point will be illustrated in Sect. 9.

2.2 Related work

The idea of combining object-oriented approaches and computational methods to propose high level declarative problem solving formalisms in engineering sciences is not new. In the following, we describe several related works, distinguishing, on the one hand, from the precursory works that can be linked to the general problem of knowledge representation in artificial intelligence and, on the other hand, from the more recent works undertaken in systems engineering and which is are related to the development and diffusion of MBSE.

In ThingLab [26], constraints stored in the class of an object authorize the expression of relations. One can express, for example, that any resistance obeys Ohm's law. However, since ThingLab was designed to produce animated simulations, the solving methods used, which are sufficient in this field, are ineffective for solving the systems of equations and inequalities of engineering design problems. Moreover, in ThingLab, a constraint is declared in an object and its behavior is programmed in methods of this object. This procedural character of the representation of constraints makes it impossible to consider ThingLab as a declarative modeling language.

The NEMO-TEC language [27] is described as an object-oriented extension of the Unicalc mathematical problem solver based on the technology of sub-defined models. This technology is comparable to interval constraint programming methods. NEMO-TEC was essentially designed to generate a stand-alone computing system, consisting of a compiled model of the dependency network between the unknowns of the problem and a user interface. This system must guide a user in his successive design choices and validate them by propagation. The interactive nature of the design is prioritized to the detriment of the resolution capacity in this work.

ONERA, in the framework of a research work in preliminary aircraft design, has proposed to combine logic programming with constraints (CLP) and object concepts to represent and solve design problems [28, 29]. Logic programming brings the capabilities of tree searching and logic rules writing; its generalization to the CLP framework brings the capabilities of formulating and solving mathematical constraints on discrete or continuous variables. The object-oriented concepts (classes, attributes, instances) enable to capture the structure of the product (i.e., its decomposition in classes) and to use it to propose configurations (i.e., different instantiations of the product). The proposal mixes in the object representation the procedural features of predicates with the declarative features of clauses. Additionally all the equations must be decomposed into binary and ternary predicates. Finally although the proposed implementation makes it possible to simulate object features in a Prolog program, the framework still remains fundamentally that of logic programming with constraints. Moreover, the scope remains limited to the expression of configuration problems and the representation of mathematical concepts remains procedural. This is neither a full-fledged object language nor a true declarative mathematical modeling language.

The COB language [30] developed at about the same time at the New York University in Buffalo also proposes to combine constraints and objects by relying on the resolution capabilities of a logic programming language with constraints, in this case CLP(R). But it differs significantly from the previous development by a number of points which constitute notable advances. COB is a true language. Its syntax is formally specified by a grammar and its operational semantics is validated by the development of a compiler [31]. This compiler translates a COB program into a CLP(R) program. Unfortunately COB is still too much influenced by CLP(R). In addition to attributes and constraints, a class is also composed of predicates and constructors. Finally COB is more like an attempt at a general multi-paradigm programming language (classes and objects, methods, constraints and rules) than a specific modeling language dedicated to the engineer.

In the lineage of predicate-based languages, the Alloy software system specification language [32] is worth mentioning. Alloy consists of a declarative language inspired by the Z language and its analyzer. It associates first order logic with relational capabilities. The Alloy Analyzer is a fully automatic tool that finds instances of Alloy specifications (or Alloy model), i.e., it is able to assign values to the sets and relationships of the specification so that for each assignment all formulas of the specification are valid. It transforms the set of models created in Alloy into a SAT problem. Alloy is a true language with a compiler. Unfortunately, it only handles Boolean variables without possible resolution on real ones.

The s-COMMA [33, 34] platform is an attempt to use UML to produce an environment combining modeling and resolution. The idea is to use the capabilities of the meta-modeling and model transformation tools associated with the UML standard to build a visual and object-oriented language for modeling constraint satisfaction problems. The platform is composed of two main parts, a modeling tool and a projection:

• The visual modeling language combines the declarative aspects of constraint programming with the structuring aspects of object-oriented programming:

• The projection tool is a translator that transforms the modeling of a problem described in the previous language into a constraint programming program dedicated to a targeted solver.

The advantages of the approach are:

• A certain independence of the problem modeling language from the solver languages;

• A development of projection tools on new solvers facilitated by the use of model-driven development tools such as KM3 (Metamodel Specification Language) or ATL (Model Transformation Rule Description Language).

However, the model-driven development approach used in s-COMMA presents some drawbacks. The description of the compilation architecture presented in the user manual shows us that it is organized in three layers (modeling, projection, resolution) and that two transformations are needed to go through them: the s-comma object model is first compiled into a flat-s-comma model with a syntax closer to that of the target resolution languages, then this flat-s-comma model will itself be compiled into the target language of a given solver.

This complex compilation chain decouples the problem description model from the solution finding and poses the fundamental question of the debugging of the model.

The Deklare [35] and KoMod [36] projects focused on the representation of the functional and organic structures of the products to be designed in order to enable the associated design problems to be posed and solved using a commercially available constraint programming library.

The objective of the CO2 (constraint-based design) project (a Grant from the French National Research Agency) was to develop methods and tools to solve design problems. The project produced Constraint Explorer (CE), a problem solving software environment comprising a modeling language and a numerical solver based on interval methods [18]. The solving characteristics and performances of CE are relevant, but the language lacks the object-oriented structuring features required for system design.

Clafer [19], a recent proposal seems particularly interesting. It proposes an object-based and feature-based model and allows the user to easily express logical relationships between these elements. A Clafer model can be transformed into an intermediate format [20] so that it can be taken into account by the constraint programming library Choco or by Alloy [19]. Clafer remains for the time being oriented towards the representation of configuration problems or software product lines and deals essentially with discrete problems. In addition, the environment requires the use of an external solver to solve the models.

Finally, let us mention the work around the taking into account of uncertainty in software engineering. [21] talks about partial models represented in the form of graphs with alternatives and a resolution process using an external SAT solver. However, they do not propose any formal language. Moreover, only Boolean degrees of freedom can be represented.

2.3 Our proposal

The current needs expressed in preliminary design, particularly in the field of the generation of architecture of eligible systems, are not covered [1, 37]. This observation led us to start this work of specification and development of a declarative language adapted to system design.

Our proposal to meet these needs is:

• A native language, declarative, structured and property based, offering the possibility to describe an ontology of physical quantities and enabling the representation of variables and properties in discrete and continuous domains.

• An Integrated Modeling and Solving Environment enabling model edition, compilation and resolution within the same integrated environment.

As partial system descriptions are naturally more frequent in the upstream phases of system definition, DEPS is a natural candidate for preliminary design even if its use is not limited to this stage. In preliminary design, DEPS Studio can be seen as a synthesis tool that proposes eligible systems as opposed to analysis tools used at later stages to verify or validate a system.

We describe the main features of the language in the remainder of this paper.

3 DEPS fundamental features

In this section, after giving an overview of DEPS, we describe the fundamental elements of the language, which will serve as a basis for the rest of the paper.

3.1 Overview

In DEPS, a design problem is represented by a set of DEPS models so the fundamental feature of the DEPS language is the “Model”. Any model encapsulates in order: a set of arguments, a set of constants, a set of variables, a set of elements and a set of properties. Arguments can be either constants or elements identifiers. Elements are instances of other models.

Figure 3 gives a representation of the DEPS meta-model and synthesizes all the concepts that will be presented in the rest of this paper.

Fig. 3

A part of the meta-model of the current version of the DEPS language

3.2 Models

The fundamental feature of the DEPS language is the model. Any model is defined using the keyword Model followed by its name and its (possibly empty) list of arguments. It contains in order: an area for declaration or definition of model constants (keyword Constants), an area for definition of model variables (keyword Variables), an area for declaration or definition of model elements (keyword Elements) and an area for definition of model properties (keyword Properties).

In the following, we will agree that:

• The notion of declaration refers to the description of the type of the constant or element passed as an argument of a model but constructed outside of it,

• The notion of definition refers to the construction of the constant or the element inside a model.

A Model is defined according to the following syntax:

With

A model can be qualified as abstract (optional keyword abstract). In this case, it cannot be instantiated. An instance of a model is called an Element. Therefore, no instance of an abstract model can be displayed in the Elements area of a model.

It is possible to extend models (extends keyword). This functionality will be detailed in Sect. 6.1.

The arguments of a model can be either values, constants or instances of other models (Elements) and nothing else. Any constant argument of a model will have its declaration in the Constants area of the model. Any element argument of a model will have its declaration in the Elements area of the model. These points will be detailed in Sect. 6.2.

3.3 Problem

The problem to be solved is expressed using the keyword Problem. Syntactically, a problem is a Model without arguments. For each system design project to be represented in DEPS, there is one and only one Problem defined. The problem is broken down into Elements. Each Element is an instance of a Model. Since each Model can also be made up of Elements, the Problem is the root of a hierarchy of Elements.

Then, a Problem is defined according to the following syntax:

3.4 Quantity kind and quantity

Data manipulated in DEPS can be:

• Integer or real values.

• Integer intervals, real intervals, integer enumerated domains, or real enumerated domains.

If we stick to these simple types, we cannot represent the quantities manipulated by the designers of technical systems. Therefore, we have proposed two concepts to represent these quantities: QuantityKind and Quantity.

Several research works have focused on the integration of quantities in models [38]. These works are based on the definition of UML stereotypes intended to represent quantities as well as the associated operators in the form of member functions. Several other implementation of the concept of quantities exist: QUDV for SysML [39], the QUDT ontology [40] from NASA and the representation of quantities in the Modelica language too [41]. Our proposal is different on several points:

• We make a clear distinction between the Quantity that will carry the unit and the QuantityKind that will carry the dimension of the quantity.

• Our approach is purely declarative and we do not use member functions. The operations between quantities are directly managed by the DEPS Studio environment that we have developed and that is able to do algebraic operations guaranteed on the domains of possible values of quantities.

• We want to be able to represent both ordinal and cardinal quantities.

• Our aim is not to describe quantities in all their generality, but to provide just enough information to be able to correctly type the constants and variables of the problems we wish to represent in DEPS.

Note that a set of universal quantities and quantity kinds of physics have been predefined in DEPS: Pressure, temperature, electric current, mass, length, power, …

The basics quantities Real and Integer are also predefined.

They are all included in a dedicated package available with the language.

3.4.1 Quantity kind

In DEPS, both constants and variables are associated with types of physical or technological quantities called quantities (Quantity). They are mandatory in Systems Engineering.

A QuantityKind carries a basic type (integer or real), a min limit, a max limit as well as the dimension in the sense of the dimensional analysis of the quantity [42, 43]. For example L is the dimension of a length, LT⁻² is the dimension of an acceleration where M represents a mass, L a length and T a time. We can also define dimensionless Quantitykind as processor indexes or other. In this case, the dimensionless symbol u will be used.

The negative and positive infinite values for the domain terminals are noted -maxreal and + maxreal for real and -maxint, + maxint for integers.

A QuantityKind is defined according to the following syntax:

Figure 4 shows a QuantityKind representing a potential difference (PotentialDifference). A potential is therefore a zero (Min) or positive unbound real quantity (Max). According to the dimensional analysis, the dimension of an electric potential is ML²T⁻³I⁻¹ where M represents a mass, L a length, T the time, and I the electric intensity [42, 44].

Fig. 4

QuantityKind example

3.4.2 Quantity

A Quantity is defined from a QuantityKind. The QuantityKind carries the dimension, and the Quantity carries the unit.

More precisely, a Quantity has:

• A base quantity type (Kind). For example, Real, Integer, Length;

• A Min (resp. Max) bound that represents the minimum (resp. maximum) value that can be taken by any constant or variable having the defined quantity as its type;

• A Unit of the quantity.

Let us assume that:

• $D_{{\left\langle {{\text{Quantity}}\;{\text{Name}}} \right\rangle }}$ represents the domain of values of the Quantity

• $D_{{\left\langle {{\text{Quantity}}\;{\text{Kind}}\;{\text{Name}}} \right\rangle }}$ represents the domain of values of the QuantityKind

The definitions of the quantity has to satisfy:

$$ D_{{\left\langle {{\text{Quantity}}\;{\text{Name}}} \right\rangle }} \subseteq D_{{\left\langle {{\text{Quantity}}\;{\text{Kind}}\;{\text{Name}}} \right\rangle }} $$

A Quantity is defined according to the following syntax:

For example, the meter m can be the unit for a length and the volt V can be the unit of an electrical potential or voltage. The symbol u is used to designate quantities without a unit (cf Fig. 5).

Fig. 5

Quantity example

Separating Quantity and QuantityKind allows several quantities to refer to the same quantitykind. The quantitykind carrying the dimension and the quantity carrying the unit, it will be possible to express the same quantity (same dimension) in several units.

Tables are tables of correspondence between values. A table has a name, a set of typed attributes and a dataset organized in tuples. A table ends with the keyword End.

Tables are defined according to the following syntax:

The table in Fig. 6 represents a set of tuples for the characteristics of batteries. It describes for each battery referenced by an Index the available combinations for the voltage and the maximum intensity.

Fig. 6

An example of table in DEPS

For example, the battery whose reference (ref) value is 2 will have a voltage of 12 V and a maximum delivered current of 400A.

4 Constants and variables

As mentioned in Sects. 3.2 and 3.3, models are made up of constants and variables. This section focuses on the description of these elements and their interpretation mechanisms.

4.1 Constants

A constant is a numerical quantity whose value does not vary during the lifetime of any copy of the model in which it is declared or defined. A defined constant is a constant local to the model which is defined in its Constants area and whose value is that of a local expression to the model. A declared constant is a constant local to the model which is defined in its Constants area and whose value is that of an expression passed as an argument of the model. In addition, some universal constants are predefined in DEPS. Thus, Pi represents the constant whose value is that of the transcendental number π.

When they are local to a Model, constants are defined according to the following syntax:

Constants values and quantities can be set by default and can be redefined too. This point will be detailed in Sect. 6.5

When they are passed as arguments of the Model, constants are declared according to the following syntax:

Figure 7 shows some examples of definition of constants. Note that some constants may depend on other previously defined constants both for the definition domain and for the value.

Fig. 7

examples of definition of constants

4.2 Variables

A variable is an unknown in the model. It is characterized by its Quantity possibly restricted to a sub-area of possible values. A variable must be defined in the Variables field of the model. As an unknown, its value is not defined. It is important to point out that the variables carry the sub-defined character of DEPS models.

Variables are defined according to the following syntax:

Variables quantities can be set and can be redefined. They can be prefixed too. These points will be detailed in Sect. 6.5.

Figure 8 shows some examples of definition of Variables. Note that some variables may depend on previously defined constants for the definition domain.

Fig. 8

examples of definition of variables

Let us define for example an electric dipole model (see Fig. 9). A dipole is characterized by the current flowing through it (I) and by the voltage at its terminals (U). The possible values of the voltage U have been reduced to the continuous range [0, 1000]. This model is qualified here as abstract. It cannot be instantiated. In DEPS, model instances are called Elements.

Fig. 9

A dipole abstract model

5 Elements

As mentioned in Sects. 3.2 and 3.3, elements are parts of models. This section focuses on the different ways of handling elements. An Element is an instance of a model. It can be passed as an argument to a model for implementing aggregation relationship. It can also be defined in a model for implementing composition relationship (see Sect. 6.2). An Element can be defined or declared as follows:

5.1 Defining an element

When they are local to a Model, Elements are defined according to the following syntax:

 < ListOfArgValues > is the list of argument values needed to define the element. This list must be compatible with the signature of the model < ModelName > of which the element is an instance (cf Sect. 6.3). Moreover, models can be redefined in a certain limit. This point will be detailed in Sect. 6.5.

5.2 Declaring an element

When they are passed as arguments of the Model, elements are declared according to the following syntax:

5.3 Model signature

Each Model has a signature. Signatures allow the designer to define several models with the same name, different contents as soon as their signatures are different. A signature is declared according to the following syntax:

In Fig. 10, they are defined:

• A model A with two arguments: a real constant (c1) and an integer constant (c2),

• a model B with one argument named DeclElt which is an instance element of the model A. We will therefore specify its signature A[Real, Integer] in its Elements part. Inside the model B is also defined in the elements area an instance of A named DefElt, created with the arguments cb1 and cb2: A(cb1, cb2).

Fig. 10

examples of declared and defined elements

Then, as B has one argument which is an instance of A which signature is A[Real, Integer], the signature of B model is:

B[A[Real, Integer]].

6 Organization of the models

DEPS models can be combined with each other using different relationships that we will now detail.

6.1 Inheritance

DEPS models can simply inherit from each other (keyword extends). This is public inheritance: constants, variables, elements and properties are thus directly inherited.

So be MExtends an extended model of a given model M, any instance of MExtends will contain:

• The arguments of M as well as the locally declared arguments of MExtends.

• The constants defined or declared in the Constants area of M as well as the constants defined or declared in the Constants area of MExtends.

• The variables defined in the Variables area of M and the variables defined in the Variables area of MExtends.

• The elements defined or declared in the Elements area of M as well as the elements defined or declared in the Elements area of MExtends.

• The properties expressed in the Properties area of M as well as the properties expressed in the Properties area of MExtends.

We thus define in Fig. 11 a first resistor model. A resistor is a dipole with an unknown ohmic resistance (R) and subject to Ohm's law.

Fig. 11

A resistor model

We can also define a second resistor in which the resistance R is a declared constant whose ohmic value is passed as an argument to the model (cf Fig. 12). In this case, the model is parameterized.

Fig. 12

A parameterized resistor model

6.2 Composition and aggregation

An element can be passed as an argument to a model to represent an aggregation and must then be declared in the Model Elements field area. It can also be created in a model to represent a composition and must then be defined in the Model Elements area.

When an element is passed as an argument to a model, it is simply declared in the Elements area of the model. It is declared by typing it by the signature of the model to which it refers.

To define an element, it is constructed by calling the name of the model to which it refers followed by the list of its effective arguments.

Thus, if in our example we wish to associate two dipoles in series, we will define a serial link model between two aggregated dipoles (cf Fig. 13).

Fig. 13

Serial model of two dipoles

6.3 Polymorphism and genericity

As previously mentioned in Sect. 5.3, each Model has a signature. Thus the signature of the Serial Model will be denoted Serial [Dipole[], Dipole[]]. This mechanism removes ambiguity in case of aggregation of Models with the same name but different signatures.

The signature of a model consists of its name followed by the list of signatures of its arguments. If the argument is a constant its signature is its quantity.

This notion of signature allows the overloading of models: several models can have the same name as long as their signatures are different.

Thus if we now wish to have a resistance model in series specifying explicitly that the first dipole of the aggregation is a resistor of unknown Ohmic value and that the second dipole of the aggregation is a resistor of known value we will have to remove the ambiguity by means of the signature of each of the resistance models (cf Fig. 14).

Fig. 14

Serial model of two different types of resistors

Thus, in Fig. 12, the model Resistor has an ohmic resistance value as argument. Its signature is therefore Resistor[Resistance]. Figure 14 shows a serial connection model between a resistor of unknown ohmic value and a resistor of given ohmic value. The signature of the Serial model is therefore Serial[Resistor[], Resistor[Resistance]]. Let us assume that we would like to model a new resistor which depends on temperature (cf Fig. 15) and that we want to connect with a serial connection this resistance to the two previous one. We will create a new model that will extend the two-resistor series model into a three-resistor model, the third of which will be a temperature-dependent resistor (see Fig. 16). The signature of this new Serial model is therefore Serial[Resistor[], Resistor[Resistance], Resistor[Resistance, Temperature]].

Fig. 15

A temperature-dependent resistor model

Fig. 16

Serial model of three different resistors

Thus if we wish to construct an element mSerial, instance of the new Serial model, we will have to pass it in order:

• An argument of type instance of a two arguments serial model inherited from Serial[Resistor[], Resistor[Resistance]].

• An argument of type instance of a temperature-dependent resistor whose signature is Resistor[Resistance, Temperature].

Now let assume we want to create an electrical system containing two resistors in series, one known and one unknown, connected to a given voltage source. We will create a SysElec model with a voltage source (G) as argument. This model (see Fig. 17) will be composed of a resistor with a known Ohmic value (10 Ohm), a resistor with an unknown Ohmic value and a serial link between these two dipoles. R1 and R2 being instances of the Resistance Models, themselves derived from Dipole, we can pass these resistors as an argument of the Serial model.

Fig. 17

Model of the electric system

6.4 Access to model elements

All the elements of a problem are organized using aggregation and compositional relationships forming a tree structure. Access to the elements of this structure is authorized by the use of a doted notation.

A constant, variable, or element at different levels of this tree structure can be designated and manipulated using a path.

If the current I flowing through resistor R1 is to be accessed in the model shown in Fig. 14, this is done via the path R1.I.

6.5 Constants, variables and elements redefinition

Let us assume that:

${\text{Dredef}}_{{ < {\text{Const}} \left| {\text{ Var}} \right\rangle }}$ represents the domain of values redefined for a constant or a variable in the extended Model.

$D_{{ < {\text{Const}} \left| { {\text{Var}}} \right\rangle }}$ represents the domain of values defined by default for a constant or a variable in the basic Model.

The definitions of the redefined domains have to satisfy:

$$ {\text{Dredef}}_{{ < {\text{Const}} \left| {\text{ Var}} \right\rangle }} \subseteq D_{{ < {\text{Const}} \left| {\text{ Var}} \right\rangle }} $$

Then, in Fig. 18, domain and value of the c constant have been redefined, and the domain of the b constant has been redefined. In the same way, the domain of the V variable has been modified. It is also possible to redefine an element (model instance) under certain conditions. Let us take the example of a Model SysElecWithResistor extension of a SysElec (cf. Figure 19). Initially, the first SysElec Model consisting of two elements R1 and R2 instances of Dipole. It is possible to extend the first SySElec model into a SySElecWithResistor model in which the elements R1 and R2 are redefined (redefine) as an instance of Resistor[] and an instance of Resistor[Resistance]. This is possible if and only if Resistor[] and Resistor[Resistance] are extended models of Dipole.

Fig. 18

Illustration of redefinition of constants and variables

Fig. 19

Illustration of an Element redefinition

6.6 Composition, aggregation, inheritance and overloading

It is possible to combine the aggregation, composition, inheritance and overloading capabilities of DEPS models. Consider models Dipole, Resistor[] and Resistor[Resistance] in Fig. 20. Dipole is the root model of an inheritance tree. Indeed, Resistor[] derives from Dipole and Resistor[Resistance] derives from Dipole too.

Fig. 20

A very simple hierarchy for demonstration

The Agreg model of Fig. 21 is an aggregation of two instances d1, d2 declared as instances of Dipole. Because of the inheritance between models, it is possible to instantiate Agreg with as arguments an instance of Resistor[] and an instance of Resistor[Resistance] as it is the case in the UseAgreg model of Fig. 21. The RootComp model is composed of two instances d1 and d2 of Dipole. Because of the inheritance relation, it is possible to extend RootComp into an ExtComp model by redefining d1 and d2 as instances of Resistor[] and Resistor[Resistance], respectively.

Fig. 21

A very simple hierarchy for demonstration

Moreover, this type of mechanism makes it quite easy to have templates. Self-referencing of models is limited. Thus, if one wishes to define a model of chained lists of reals in DEPS, one would be tempted to proceed as in Fig. 22.

Fig. 22

Wrong definition of self-referencing model

And we would be unable to express the signature of the List Model. On the other hand, by using the inheritance mechanism combined with overloading, it becomes possible to define quasi-recursive models (cf Fig. 23).

Fig. 23

model self-referencing

7 Properties

DEPS is a declarative and property based language. In this way, it is possible to express within a model a set of properties that must necessarily be satisfied by any of the instances of this model. A property is a relationship necessarily respected by any instance of the model that contains it. In the current version of DEPS, properties are either algebraic relationships between expressions (cf. Section 7.3) or relationships defined in extension that use tables of values of variables compatible with each other (cf. Section 7.4).

7.1 Algebraic expressions

Algebraic expressions can be for integer or real values, integer or real constants and variables of any type (continuous domain, discrete domain or enumerated domain). Usual unary algebraic operators are available such as logarithmic, power, exponential, trigonometric, hyperbolic, … (cf Fig. 24). In DEPS, all algebraic operators are strongly typed. Depending on their operands, they can return either an integer value or a real value or a continuous domain or a discrete domain or an enumeration of integer values or an enumeration of decimal values.

Fig. 24

Unary expressions in DEPS

In the same way, the usual arithmetic binary operators are recognized in DEPS as well as the min and max binary operators (cf Fig. 25).

Fig. 25

Binary expressions in DEPS

7.2 Piecewise operators

It may be necessary in some design problems to express piecewise functions from ${\mathbb{R}}$ to ${\mathbb{R}}$. This is the case when a function is defined continuously by pieces.

As an example, the following function is a nonlinear piecewise function:

$y = f\left( x \right)$ defined on [0, 100] such that:

$$ f\left( x \right) = x\;{\text{if}} x\; \in [0,1] $$

$$ f\left( x \right) = x^{2} \;{\text{if}}\;x\; \in \;[1,10] $$

$$ f\left( x \right) = 1e^{3} /x\;{\text{if}}\;x\; \in \;[10,100] $$

In the case where the function to represent is piecewise nonlinear, we have the following operator:

$$ {\varvec{pw}}\left( { < varg > ,\; < I_{1} > ,\; < expr_{1} > ,\; \ldots ,\; < I_{n} > ,\; < expr_{n} > } \right); $$

with < varg > being the name of the argument variable of the function. For each i from 1 to n, < I_i > represents the ith value domain for < varg > and < expr_i > represents the expression of the function on < I_i > . Here again, the operator returns a continuous interval.

Then, for representing the previous piecewise function, we will write the following property with the pw operator:

$$ y = pw(x,[0,1],x,[1,10]x^{2} ,[10,100],1e3/x); $$

Figure 26 illustrates the use of a piecewise operator inside a DEPS model.

Fig. 26

an example of nonlinear piecewise function in DEPS

When the piecewise function is piecewise linear (see Fig. 27), the following operators are available in DEPS:

$$ {\varvec{pwl}}\left( { < varg > ,\; < TableName > } \right); $$

with < varg > being the name of the argument variable of the piecewise linear function. This operator returns a continuous interval. < TableName > is the name of the data table in which the pairs of values characterizing the pieces of line segments of the function will be stored.

Fig. 27

An example of a linear piecewise function

It is also possible to enumerate these pairs directly in the operator as follows:

$$ {\varvec{pwl}}\left( { < varg > ,\;\left( {varg_{1} , \, vim_{1} } \right),\;\left( {varg_{2} , \, vim_{2} } \right), \ldots ,\left( {varg_{n} , \, vim_{n} } \right)} \right); $$

with varg_i the ith value of varg and vim_i the ith value of the corresponding image of varg_i.

Thus, for the piecewise function of Fig. 27 we will write the following property with the pwl operator:

$$ y \, = \, pwl\left( {x, \, \left( {0, \, 0} \right), \, \left( {10, \, 35} \right), \, \left( {25, \, 25} \right), \, \left( {50, \, 40} \right), \, \left( {65, \, 10} \right)} \right); $$

A pwl operator can be posted by using a data table (cf Fig. 28) that encapsulate the coordinates of the break points as follow:

$$ y = \, pwl\left( {x, \, PwlValues} \right); $$

Fig. 28

An example of data table

7.3 Defining properties

Several properties can be expressed in DEPS. A property is a relationship between variables. More precisely, we have in DEPS the usual binary algebraic relations making it possible to establish relations of equality ( =), difference (< >) and inequality (< , <  = , > , > =) between two algebraic expressions. We have also the affectation relation (: =) for allocating a name to an expression.

In order to illustrate the ability to express complex algebraic properties, we give in Fig. 29 an example of an equality constraint between two nonlinear algebraic expressions on mixed domains.

Fig. 29

Example of an equality constraint between two nonlinear algebraic expressions on mixed domains

A declared or named expression (keyword expr) points to an algebraic expression and makes it possible to reference it.

Thus, the same algebraic expression can be used at several places in a model through its name without being rewritten.

An expression is declared in the Variables zone of a model in the same way as a variable by prefixing it with the keyword expr.

An expr can be initialized (using the assignment operator: =) in the Properties area of the model where it is declared or inside the Properties area of another model via a path. Initializing an expr means defining the explicit algebraic expression to which it will point and whose value it will take. Each expr is defined once and only once. For a given problem the expr graph must necessarily be a direct acyclic graph (DAG).

In addition to reuse, declaring expressions avoids to artificially increase the number of unknowns of problem. This is the case when these expressions are useful to the system designer only for observation or for renaming purposes (cf examples in Sect. 9).

Thus, in the Serial model in Fig. 13, we have created an expr U initialized at the value of the sum of the voltages at the terminals of each dipole of the serial link.

It is also possible to specify in DEPS that the value of a variable is an objective to be minimized by using the obj keyword. An objective is an expression whose value defined with the affectation relation (: =) must be minimized. This allows to express optimization problems in DEPS. A problem expressed in DEPS must have at most one obj expression.

7.4 Properties defined in extension

It is possible to force a set of variables to take their values in a Table and only in this Table.

To do this we have a catalog constraint with the following syntax:

Catalog ([< v1 > , < v2 > , …, < vn >], < TableName >);

The first argument of this constraint is the list of variables to constrain. The second argument is the name of the constraining table.

Sometimes a data table is reused to put a catalog constraint on a subset of the table's columns. To do this, we have another catalog constraint with the following syntax:

Catalog([< v1 > , …, < vn >], [< i1 > , …, < in >], < TableName >);

The first argument of this constraint is the list of variables to constrain. The second argument is the list of the column numbers to be considered in the table. The third argument is the name of the constraining table. This catalog property can work on every kind of domains of variables: continuous, discrete and enumerations.

Figure 30 illustrates the use of such a constraint in the case where we want to create a VSource voltage generator model consisting of generators which maximum voltage and current characteristic values are constrained by the Battery table.

Fig. 30

DEPS model of generator with catalog

Figure 31 and Fig. 32 represent a problem in which one wishes to know the unknown resistance of an electrical system S represented by two resistors in series connected to a voltage generator G. The Power P dissipated by the system is constrained to not exceed a value Pmax. The goal is to find one value for R1 and one value for G that requires the Power P value dissipated between 10 W and Pmax.

Fig. 31

A very simple electrical system to design

Fig. 32

DEPS Problem ElecPb

7.5 Meta properties

The posing of a set of properties can be conditioned in DEPS by the satisfaction of a logical formula. A logical formula is a logical expression tree whose nodes are logical operators (not, and, or, xor) and which leaves carry algebraic properties.

As an example, ((x = y) or (z = cos(y)) and (w + y = z + x) is logical formula.

The result of the evaluation of a logical formula is done in a trivalued logic. The formula can be certainly true, certainly false or unknown.

As an example:

$$ {\text{when}}\; x \in \left[ {2, 10} \right],\; y \in \left[ { - 1, 4} \right], $$

$$ \left( {x > 2} \right){\text{and }}\left( {y > 2} \right) {\text{is}} {\text{unknown}} $$

but

$$ {\text{when }}\;x \in \left[ { - 1, 1} \right], \;y \in \left[ { - 1, 1} \right], $$

$$ \left( {x > 2} \right){\text{and}} \left( {y > 2} \right) {\text{is}}\;{\text{certainly}}\;{\text{false}} $$

and

$$ {\text{when}}\; x \in \left[ {3, 10} \right],\;y \in \left[ {3, 10} \right], $$

$$ \left( {x > 2} \right)and \left( {y > 2} \right) is certainly true $$

These formulas are used in two dedicated meta properties: IfThen and IfThenElse.

Concerning the IfThen property it takes as argument a logical formula and a list of algebraic properties. It is defined using the following syntax:

$$ {\varvec{IfThen}}\;( < {{Logical}}\;{{Formula}} > ,\; < {{List}}\;{{Of}}\;{{Properties}} > \, ); $$

If the logical formula is certainly true then the properties of < List of Properties > are active. In the example below, if x is greater than 3 and z is less than 20, then the properties x^2 = 16 and x + z = 15 are set.

$$ {\text{IfThen}}((x > 3)\;{\text{and}}\;(z < 20),[x^{2} = 16,x + z = 15]); $$

Concerning the IfThenElse property it takes as arguments a logical formula, a list of algebraic properties to be set if and only if the logical formula is certainly true and a second list of properties to be set if and only if the logical formula is certainly false.

It is defined using the following syntax:

$$ {\varvec{IfThenElse}}( < {{Logical}}\;{{Formula}} > \, , \, < {{List}}\;{{Of}}\;{{Properties}} > \, , \, < {{Other}}\;{{List}}\;{{Of}}\;{{Properties}} > \, ); $$

If the logical formula < Logical Formula > is certainly true, then the properties of < List of Properties > are active, and if the logical formula is certainly false, then the properties of < Other List of Properties > will be active. In the following example, if x is greater than 3 and z is less than 20, then the properties x^2 = 16 and x + z = 15 are set. Otherwise, the properties x^2 = 1 and x + z = 10 are set.

$$ {\text{IfThenElse}}((x > 3)\;{\text{and}}\;(z < 20),[x^{2} = 16,x + z = 15],[x^{2} = 1,x + z = 10]); $$

Let us suppose we want to enrich our electrical system model with a diode model. A diode conducts current as a function of the voltage across its terminals. If the voltage at its terminals is lower than a given threshold voltage Vs, then the current becomes zero. Otherwise, it follows an exponential law. Figure 33 shows this law using the If Then Else metaproperty.

Fig. 33

Using meta properties to model a diode

8 The DEPS Studio IDE

8.1 Overview

The modeling and resolution process with DEPS is based on a software environment called DEPS Studio [45]..It integrates modeling and solving environment associated with the DEPS language includes a model editor, a project manager, a compiler and a solver (cf Fig. 34). Experience shows that the specification of a system design problem is never right at the first time and that many modeling errors are only detectable by calculation. We therefore decided to develop and integrate our own solver into the development environment so that the solution finding contributes effectively to the problem modeling process. This is a rapid model development approach (analogous to a RAD approach) which, contrary to a model transformation approach, reduces the execution time of the model development loop. It also enables errors to be traced back to the correct level of abstraction. DEPS Studio is currently available as a freeware on request via the contact page of the deps link nonprofit organization website [46]. It can be possible to contact the authors of this paper directly.

Fig. 34

DEPS Studio IDE

8.2 Editor and project management

A problem to be solved is organized into a project. A project consists of several packages. Each package is saved in a file. The packages contain models, kind of quantities, quantities, and tables. One of the packages has to contain a particular model without arguments and declared as the problem. This model represents the global problem to be solved expressed with constants, variables, elements and properties.

The environment has:

• A multi-window editor to load, modify and save packages,

• A project manager to load, modify and save the modeling project of a problem made up of all its packages.

A project is defined as a set of packages. Each package follows the following structure:

8.3 The compiler

The compiler we have developed directly transforms the DEPS "source" model of a design problem into a structured network of elements which properties are associated with the < V, D, C > model of a Constraint Satisfaction Problem (CSP) [47]. It is thus a "native" compiler which is not an overlayer of a constraint programming language. Compilation is anticipated; the whole network is thus generated before resolution.

The static typing of the DEPS language is exploited by the compiler to detect type errors on constant, variables and elements before resolution.

The compilation is done in two passes:

The first compilation pass checks the packages used by the project, analyzes lexically and syntactically their contents and creates the hierarchy of the project models;

The second pass creates the set of elements that define the problem starting from the creation of the single instance element of the model declared as problem.

Errors are processed and reported to the user at all stages of compilation: package checking, lexical analysis, syntactic analysis, creation of the model hierarchy and creation of the sub-defined elements.

The compiler produces a structured computational model. This computational model is executed on an execution machine, which is the mixed CP solver developed for this purpose (cf Sect. 8.4).

If the compilation step succeeds, then the resolution step will have the task of assigning values to the variables satisfying all the properties/constraints of the problem.

In the case of the ElecPb problem (cf Fig. 32), the compilation generates the instance structure shown in Fig. 35. Each instance contains its own sets of constants, variables and properties. The structure of the problem is thus preserved until its resolution.

Fig. 35

Example of an instance tree generated by the compiler

8.4 The solver

Solving a design problem requires the ability to take into account:

• Under-constrained problems

• Nonlinear algebraic equations and inequalities on mixed domains

• Other types of relationships such as value tables.

To do so, we have developed a constraint-based solver dedicated to computation on structured DEPS models. The calculation methods we use come from CSP resolution technics [47]. The structure of the DEPS models is preserved throughout the compilation chain up to the calculation models.

The solver implements a revised HC4 propagation method [48] on equations and inequalities. Initially intended for continuous domains, we have extended the method to four types of domains: open real intervals, integer intervals, enumerated sets of floating values and enumerated sets of signed integer values. For performance reasons, reductions are performed directly on the typed domains without going back to the real intervals. The root-finding algorithm uses a branch and prune method. For the moment, only the classical round-robin and first-fail strategies are implemented. In the case of an over-constrained problem, a failure may occur at the first propagation or after exploring the remaining parts of the search tree. Following the CSP paradigm, the failure is interpreted as proof that there is no solution to the problem and not as a failure of the solving algorithm. The object-oriented architecture of the solver has been designed in such a way that it can be extended to other existing propagation and/or resolution methods (box-consistency, local methods, …).

The tree in Fig. 34 is solved instantly by the solver and gives the results in Table 1.

Table 1 Results of DEPS Studio for the ElecPB problem

9 Validation

DEPS and DEPS Studio have recently been used successfully on several academic and industrial case studies. In particular, they have been used to express and solve the following problems:

• Deployment of avionics functions on embedded hardware architectures with capacity, safety and reliability requirements in aeronautics [49].

• Software architecture synthesis of embedded electrical generation and distribution system under safety constraints. [50].

• Sizing and architecture generation of battery-type electrical storage system with mission profile requirements [51, 52].

• Configuration and positioning of an on board camera in a UAV [17].

• Sizing of a power transmission system with environmental requirements [53].

• In terms of the typology of problems described in Sect. 2.1, the first two problems are a mix of PT1 and PT3 problems. The last two problems are a mix of PT1, PT2 and PT4 problems.

All these case studies have been solved on a “basic” machine, with the following specification: Gen Intel(R) Core(TM) i7 @ 2.80 GHz, 4 cores. After compiling the models in DEPS Studio, we obtained the following resolution times: 0.297 s for the first case, 0.15 s for the second one, 0.1 s for the third one, 0.19 s for the next one and 0.01 s for the last one.

In order to illustrate the expressiveness and reusability of DEPS language, we present in this paper two other case studies that will be fully described:

• The problem of sizing a planar RR manipulator.

• The problem of deploying software tasks on a hardware architecture embedded in a UAV.

9.1 Sizing of a planar RR manipulator

9.1.1 Problem description

Planar robots are a class of robots whose role is to access points located on a plane. The robot itself is planar, i.e., its effector (the end of the robot) necessarily has a planar trajectory, generally in a plane parallel or coincident with the plane in which the points to be reached are located. These robots can be used to move objects on a plane or to implant electronic components on a board.

Several architectures of planar robots exist [54]. We will limit ourselves here to a simple chain planar robot with two degrees of freedom.

In this paragraph, we present the example of the sizing of a planar RR manipulator (Rotoïde, Rotoïde) (cf Fig. 36). In terms of the typology of problems described in Sect. 2.1, this is a PT1 problem.

Fig. 36

Geometry of the planar robot

A planar RR manipulator consists of a rotoid link parameterized by its rotation angle q₁ followed by an arm of length l₁ and then a rotoid link parameterized by its rotation angle q₂ followed by an arm of length l₂.

The problem is to size the RR manipulator to reach one or more points in the plane.

To design this manipulator implemented in (0, 0) in the plane, it is necessary to determine the values of the design variables l₁ and l₂ such that there is a value of the couple of operating variables (q₁, q₂) allowing to reach a reference frame P given in the plane by the coordinates of its origin (x, y) and an angle q of orientation of its x-axis. The notation used is that of Denavit–Hartenberg limited to the dimension of the plane [55].

If we want to reach n points P₁, P₂, …, P_n in the plane with our RR planar robot, we will have to determine a couple of values l₁, l₂ such that whatever the point to be reached among the n, this point is reachable.

$$ \exists \left( {l1, l2} \right) \in {\mathbb{R}}^{ + *} , \forall i \in \left\{ {1, .., n} \right\}, \exists \left( {q_{1i} ,q_{2i} } \right) \in \left[ { - \pi , \pi } \right], \;{\text{IsReached}}\left( {P_{i} , q_{1i} , q_{2i} } \right) $$

The referential to be reached by the end of our planar robot (x and y are the coordinates of the origin of the referential and q is the orientation) will therefore be represented by the given 3 × 3 homogeneous matrix P such that:and when P is reached by the robot we have the equality:

$$ P = \left( {\begin{array}{*{20}c} {\cos q} & { - \sin q} & x \\ {\sin q} & {\cos q} & y \\ 0 & 0 & 1 \\ \end{array} } \right) $$

$$ P = {\text{Rot}}\left( {q_{1} } \right) \times {\text{Trans}}\left( {l_{1} } \right) \times {\text{Rot}}\left( {q_{2} } \right) \times {\text{Trans}}\left( {l_{2} } \right) $$

(1)

With the rotation matrix ${\text{Rot}}\left( {q_{i} } \right)$ such that:

$$ {\text{Rot}}\left( {q_{i} } \right) = \left( {\begin{array}{*{20}c} {\cos q_{i} } & { - \sin q_{i} } & 0 \\ {\sin q_{i} } & {\cos q_{i} } & 0 \\ 0 & 0 & 1 \\ \end{array} } \right) $$

And with the translation matrix ${\text{Trans}}\left( {l_{i} } \right)$ such that:

$$ {\text{Trans}}\left( {l_{i} } \right) = \left( {\begin{array}{*{20}c} 1 & 0 & {l_{i} } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} } \right) $$

The second member of Eq. (1) is called the direct geometric model of the RR manipulator.

This case study is academic. The problem presents formalization difficulties that will allow us to illustrate the interest of the DEPS language. From the point of view of resolution, it is an inverse problem.

9.1.2 DEPS modeling

We start by creating a Referential Model (cf Fig. 37). A referential is characterized by an origin (x, y) in the plane, and an orientation angle (theta) relative to an absolute referential located at (0,0) with the unit vectors (1,0) and (0,1).

Fig. 37

DEPS model of a 2D referential

Thus, the model of a link (cf. Figure 38) will include an input referential (refIn), an output referential (refOut) and a passage matrix (mat), itself a referential, such that (cf Fig. 39):

Fig. 38

DEPS model of a 2D link

Fig. 39

Mathematical modeling of a link

This last relationship is developed in the properties part of the Link model. Link is an abstract model.

To create the model of a truss of our 2D robot (cf. Figure 40), we will define an extended model of the linkage model which will contain by construction all that a linkage contains with in addition the specific characteristics of a truss, i.e., in our case its length L, design variable of our robot. Moreover, our truss being totally defined once the value of the variable L is fixed, the corresponding referential will be blocked in rotation (mat.theta = 0) and along the y axis (mat.y = 0). The translation along the x axis is L (mat.x = L).

Fig. 40

DEPS models of 2D Truss and Axis

In the same way, we can create an axis model (cf Fig. 40) corresponding to a zero translation and a rotation of an angle q.

We then describe a connection model between two links which specifies that the output referential of the first link will be identical to the input referential frame of the second link (cf Fig. 41).

Fig. 41

DEPS model of connection between two links

We can now use these different models to build a model of the robot's structure RobotStruct (cf Fig. 42) and a model of its behavior RobotBehav (cf Fig. 43). Note that the structure model is an argument of the behavior model. Thus, the structure of the robot can be shared between all these behaviors.

Fig. 42

DEPS model of the RR robot structure

Fig. 43

DEPS model of the RR robot behavior

Thus, a 2D robot structure (cf. Figure 42) has a fixed known base represented by the base argument and a 2D robot behavior has an end carrying referential represented by the effector argument.

The models have been written in such a way to facilitate their reusability and extensibility. Thus, if we now wish to represent an RRR robot with a third rotoid joint associated with a third bar, we will simply add a bar in the RobotStruct model and a rotoid and a connection in the RobotBehav model as shown in Fig. 44 and Fig. 45 where the adds are indicated in red color.

Fig. 44

DEPS model of the RRR robot structure

Fig. 45

DEPS model of the RRR robot behavior

Now the problem (cf Fig. 46) is to look for the robots positioned in (0,0) whose design variables RStruct.b1.L and RStruct.b2.L are such that there exists a configuration of the axes RBeehav1.j1 and RBehav.j2 (i.e., that the angles RBehav1.j1.q and RBehav1.j2.q exist) in order to reach the frame of reference pt1 located in (10, 20, π/2). If we want to find a robot that reaches two points pt₁ and pt2, we just need to add an instance of the RobotBehav model RBehav2 in the elements of the problem (cf Fig. 45).

Fig. 46

DEPS model of the RR robot sizing problem

9.1.3 Solving results

After having compiled this problem in the DEPS Studio environment, we launch the solver. It immediately tells us by constraint propagation that there is no solution with a single robot to reach the two points pt1 and pt2. We relax the constraint to reach point pt2 in the model and restart the solver and obtain a first solution for the bar lengths b1 and b2 shown in Table 2 in 0.63 s on a Gen Intel(R) Core(TM) i7 @ 2.80 GHz, 4cores. This illustrates the interest of having an integrated modeling and solving environment for the system design activity.

Table 2 First robot structure solution generated by DEPS Studio

9.2 Software task deployment on heterogeneous embedded drone architecture

9.2.1 Problem description

The second problem is described in [1, 56] and it deals with Unmanned Aerial Vehicle (UAV) also called drone. The degree of autonomy of these systems evolves progressively from the tracking of a trajectory defined by an operator to a complete autonomy. In the case of trajectory tracking, a key functionality of the UAV is its ability to detect obstacles and plan a new trajectory that will allow it to avoid the UAV while continuing its path to the desired destination. This function composed of obstacle detection, decision making and calculation of a new trajectory must be ensured by the drone alone, without intervention from the ground station, in order to gain in efficiency. It must also be optimized to adapt to the drone's energy resources. The obstacle detection and avoidance functionality is provided by a platform (HW) using a heterogeneous multi-core architecture (SHMC processor), which allows the UAV to have a high computing power while reducing its energy consumption (compared to a single-core or homogeneous multi-core processor). The SHMC processor is composed of cores with different computing power but using the same instruction set. A core can thus be allocated to any software task, without the need for recompilation. The cores can also be shut down when they are not allocated to any task, without the need to be kept in a sleep mode. On this type of processor we generally find a set of more powerful cores (Big Core) and a set of less powerful cores (Little Core). The platform used for the case study is an Exynos 5422 processor, composed of four Cortex A15 cores called "BigCore" and four Cortex A7 cores called "LittleCore". The maximum power dissipation is 4 Watt for a Big Core and 1 Watt for a Little Core.

The problem consists of deploying ten tasks (image acquisition, filtering, obstacle detection, …) on a maximum of 8 processors (cores) by satisfying a set of constraints. In terms of the typology of problems described in Sect. 2.1, this is a PT3 problem.

A task is characterized by:

• A memory size required for its execution (MemorySize).

• A period (Period).

• Two WCET (Worst Case Execution Time) depending on whether the task is performed by a Big Core (WCETBC) or a Little Core (WCETLC).

As an example the first Task T0 called "GetFrame" will capture camera images and place them in memory in a FIFO queue. The second T1 called "ShowPicture" distributes these images so that they can be filtered by the two filtering tasks. Task T2 and T3 called “Filtering 1” and “Filtering 2” will filter the queued images, in order to extract the edges of the objects These two tasks have a high WCET, but can be allocated to two different cores for parallel execution, with a semaphore to prevent concurrent access to the same image.

A core is characterized by:

• An index (Index) By convention the indexes from 1 to 4 refer to the BigCore and the indexes from 5 to 8 refer to the LittleCore,

• A maximum amount of available RAM (Memory).

One core must be allocated to each of these ten tasks, meeting the following requirements (constraints):

• Req 1: A task T_i is deployed on one and only one core.

• Req 2: Some tasks can only be performed by certain cores according to Table 3.

• Req 3 : Some tasks must be performed by the same core or by two different cores. This type of constraint is noted OnSameCore or OnDifferentCore. These constraints group together tasks sharing a large amount of data (images stored after acquisition) and separate other tasks for parallelism or reliability (in case of failure of a core). Thus, Tasks T1 and T3 as well as Task T2 and T4 must necessarily be deployed on the same core. Similarly, Task T0 and T1 must necessarily be deployed on different cores.

• Req 4: The amount of RAM memory available in each core to execute the tasks assigned to it must not be exceeded. Thus, the sum of the memory sizes required to perform the tasks assigned to a core must be less than or equal to the memory size of the considered core.

• Req 5:The utilization rate of each core, which must not exceed 100%. Thus the sum of the quotients of WCET by the period for each task assigned to a core must be less than or equal to 1.

Table 3 Requirement 2

9.2.2 DEPS modeling

First we will model the Cores and the tasks in DEPS. For the Cores (cf Fig. 47), we create a very general Core model. A core is defined by its index (Index) from 1 to 8 and by a memory capacity (Memory) of a maximum of 2000. We then extend the Core model into two derived models BigCore and LittleCore. We consider that the Cores from 1 to 4 are BigCore and that those from 5 to 8 are LittleCore. Moreover, the LittleCore instances have a memory capacity reduced to 500. The Index and Memory constants will therefore be redefined.

Fig. 47

DEPS models of the different cores

Regarding the representation of the tasks (cf Fig. 48), they are characterized by their memory requirements (Memory), their WCETBC, WCETLC and their Period. Finally, each task carries as unknown the Core to which it will be assigned during the resolution of the problem (CoreNumber) in accordance with the Req1 requirement.

Fig. 48

DEPS model of task

Some tasks can only be assigned to certain Cores. We have therefore extended the Task model into three models (cf Fig. 49) TaskType1, TaskType2, TaskType3 by redefining for each one the set of possible core indexes in accordance with the Req2. The TaskType1 model specifies that this type of task can only be executed on core 1 or core 5. In the same way, the TaskType2 model specifies that this type of task can only be executed on cores2 or core 6. In order to be able to express the Req3 requirement, we have defined models (cf Fig. 50) allowing the designer to set properties on a pair of tasks: both tasks on the same processor (OnSameCore) or on two different processors (OnDifferentCore).

Fig. 49

DEPS model of the three types of specialized tasks

Fig. 50

DEPS models of constraints between two tasks

A Model has also been created to express Req4 and Req5 requirements (cf Fig. 51).

Fig. 51

DEPS model of the usage rate and memory capacity

Finally, the problem is expressed in Fig. 52:

• The different processors are created: BCore1 to BCore4 instances of the BigCore model and LCore5 to LCore8 instances of the LittleCore model.

• The different tasks are created: T1 instance of the TaskType1 model, T2 instance of the TaskType2 model and T0, T2, T3, T4, T5, T6, T7, T8, T9 instances of the Task model.

• The constraints between tasks are set: Ct1 to Ct3 instances of the Onsamecore model and Ct4 instance of the OnDifferentCore model.

• Finally, the capacity and usage rate constraints on the processors are set: Ct5 to Ct12 as instances of the MemoryAndUsageCoreCapacity model.

Fig. 52

DEPS model of the deployment problem

9.2.3 Solving results

The experiments were carried out on a “basic” machine, with the following specification.: Gen Intel(R) Core(TM) i7 @ 2.80 GHz, 4 cores. After compiling the models in DEPS Studio, a first solution (cf Table 4) is generated in around 2 s (2, 735 s). It is correct by construction with regard to all the requirements expressed.

Table 4 First deployment solution generated in DEPS Studio

9.3 Discussion

In this section, we propose to examine the advantages and limitations of our approach in the light of the previous case studies. Again, the point of view we adopt in DEPS is that of representing the design problem with a view to its automatic resolution. Another important point is that we want to offer a modeling language that can be used by an embedded system designer as well as a mechanical or electrical system designer, and not a programming language that can only be used by a computer scientist. The language was built through an inductive research. Starting with real life cases of design problems, we tried to factorize language elements, gradually leading to the current version of the language. This version was then put to the test on other different problems. Either we were able to represent these problems, or we had to evolve the language. This was and still is our way of enriching the language.

From the point of view of the system design cycle as described in [10, 11], DEPS and DEPS Studio are clearly positioned on the so-called architecture or preliminary design stages of the system. DEPS enables a design problem to be represented using coarse-grained models for doing model-based system synthesis.

From the point of view of the systems to be designed, the language can be used to represent structured systems that can be structurally or functionally decomposed. Technological systems (mechanical, electrical, electronic, …), software-intensive systems (embedded systems) or mixed systems such as cyber-physical systems can thus be taken into account in their preliminary design phases. DEPS Studio can generate several solutions for systems that are correct by construction. However, in its current version, DEPS Studio will not synthesize computer code.

From the point of view of the typology of design problems proposed in Sect. 2.1, we have seen that all the case studies discussed or detailed in this paper illustrate the coverage of the typology's 4 problem types. For the moment, however, the language does not offer the ability to manipulate lists of elements and post properties on these lists. This could be an interesting convenience that is being studied for a future version of the language.

DEPS enables the simultaneous consideration of heterogeneous requirements within a single problem, which can be represented in the form of algebraic, conditional or extensional properties on variables that can take their values in mixed domains (continuous intervals, integer intervals and enumerations). If the requirements to be represented require the use of fine-grained models in the form of differential equations or finite-state automata, their verification will be delegated to the step of detailed system design, using other formalisms (AADL or Modelica, for example).

With regard to the DEPSStudio IDE, the integrated approach of modeling + compilation + resolution in a single software package makes it easier to refine the models. Indeed, the computational model generated by the compiler has the same structure as the problem model expressed in DEPS. The solver's results are therefore given directly in the modeling language and not in the language of an external solver.

Compared with existing general purpose problem-modeling languages such as AMPL [23], MiniZinc [24], OPL [22] or GAMS [25], DEPS offers structuring capabilities, as well as the ability to deal with mix variables and to combine models. These features naturally favor model reusability and extensibility. It allows the designer, to express algebraic, conditional and extensional properties on mixed variables. Compared with state-of-the-art attempts such as ThingLab [26], S-Comma [33, 34], COB [30], DEPS integrates notions that are non-existent in these works, such as parameterized models, model signatures, aggregation, composition, and model overloading. Compared with product line representation languages such as Clafer [19], DEPS natively allows the representation of mixed problems that must satisfy nonlinear algebraic properties.

From the point of view of scalability, DEPS allows the representation of large-scale problems. Models are extensible and reusable, especially due to the notions of signature and inheritance, as well as the passing of elements and constants as model arguments, which is not the case with other state-of-the-art approaches. As far as solving is concerned, the DEPS Studio solver is subject to the same constraints as all Constraint Programming (CP) solvers: a NP hard problem remains a difficult problem to solve. But most of time the first step is to correctly represent the design problem to solve in a way that is intelligible, extensible and reusable for the designer.

10 Conclusion

In this paper, we have presented the first implemented version of DEPS, a language designed to represent and solve system design problems. The targeted systems are physical, software-intensive or mixed systems (embedded, mechatronic, cyber-physics).

With regard to the research gap, DEPS makes it possible to fill the lack of structuring in current flat problem modeling languages by proposing a declarative, textual and structured language based on properties encapsulated in models.

In its current version, DEPS makes it possible to express sizing problems naturally. It also has functionalities enabling the representation of some problems of configuration, allocation and architecture. We are currently working on enriching the language so that it will express other types of design problems in later versions. We focus on the building of collections of elements and the expression of properties on them. We are also working on the implementation of specialized constraints. The long-term goal is to address complex architecture synthesis problems combining many functional (performance,…) and non-functional requirement (safety, security..)

The results will be integrated in the next version of DEPS Studio.

Moreover, DEPS and DEPS Studio have recently been used to describe and solve various academic and industrial application cases [17, 49,50,51,52,53].