Edinburgh Napier University

  Abstract: This thesis proposes solutions to four new problems stemming from a general framework of horizontal behavior composition, in which transition systems are used to model behaviors. The framework allows the realization of a new behavior from a set of available behaviors, through the synthesis of a controller, which delegates each action of the new behavior to an available behavior for execution. In this thesis, the behaviors are associated with software components—such as web services—, hardware components—such as connected objects—, or even agents. Besides, a composition consists of a controller and the behaviors interacting with the controller for realizing a target behavior, for example the one of a new agent. The first problem considers that the behaviors are subject to real-time constraints. The controller synthesis is done using the same algorithms as those of the general framework. Two additional steps are, however, required: one for modeling the interactions between the controller and behaviors in a closed-loop control system and another one for checking whether the closed-loop control system is deadlock free in all of its execution according to the set of real-time constraints. The second problem concerns the assembly of compositions. In contrast to the general framework that uses transition systems as modeling formalism in a purely monolithic control context, the proposed approach, on one hand, uses a process calculus as a formalism to represent all the elements of the closed-loop control system, and, on the other hand, performs a modular control to combine controllers using process calculus operators in order to obtain a global control. The third problem is an extension of the controller synthesis problem when the operations of the behaviors have qualitative or quantitative attributes and the operations of the target behavior are expressed in the form of preferences. The horizontal preference-based behavior composition makes it possible to realize a new behavior that could not be realized without considering preferences. Finally, the last problem is the formation of a most robust team of agents at a lower cost. It is formulated as a multi-objective linear integer programming problem. First, it focuses on finding a set of compositions such that each of them carries out the same target behavior while satisfying its preferences at best. Second, all the agents involved in the compositions form a team that remains effective even if one or more agents fail. This thesis provides an original solution for each of these problems while illustrating it with some examples. The use of SMV/TLV, Uppaal and PuLP tools makes it possible to check, synthesize or calculate the elements of the proposed examples.

Résumé : Cette thèse propose des solutions à quatre nouveaux problèmes issus d’un cadre général de composition horizontale de comportements modélisés à l’aide de systèmes à transition. Ce dernier permet la réalisation d’un nouveau comportement à partir d’un ensemble de comportements prédéfinis, à travers la synthèse d’un contrôleur qui délègue chacune de ses actions à un comportement prédéfini pour son exécution. Dans cette thèse, les comportements sont associés à des composants logiciels, comme des services Web, à des composants matériels, comme des objets connectés, ou à des agents. De plus, une composition est constituée d’un contrôleur et des comportements avec lesquels il interagit pour réaliser un comportement désiré, par exemple celui d’un nouvel agent. Le premier problème considère que les comportements sont soumis à des contraintes temps réel. La synthèse de contrôleur s’effectue en utilisant les mêmes algorithmes que ceux du cadre général. Toutefois, deux étapes additionnelles sont nécessaires : l’une pour modéliser les interactions entre les comportements et le contrôleur dans une boucle de rétroaction ; l’autre pour vérifier si la boucle de rétroaction est sans interblocage dans toutes ses exécutions considérant l’ensemble des contraintes temps réel. Le deuxième problème concerne l’assemblage de compositions. Contrairement au cadre général qui utilise des systèmes à transition comme formalisme de modélisation dans un contexte de contrôle purement monolithique, l’approche retenue suggère, d’une part, d’utiliser un calcul de processus comme formalisme pour représenter tous les éléments de la boucle de rétroaction et, d’autre part, d’effectuer un contrôle modulaire c’est-à-dire de combiner des contrôleurs à l’aide d’opérateurs du calcul de processus pour obtenir un contrôle global. Le troisième problème est une extension du problème de la synthèse de contrôleur lorsque les actions des comportements possèdent des attributs qualitatifs ou quantitatifs et que les actions du comportement désiré sont exprimées sous la forme de préférences. La composition horizontale de comportements basée sur des préférences permet de réaliser un nouveau comportement qui ne pourrait l’être autrement. Enfin, le dernier problème est celui de la formation d’une équipe d’agents la plus robuste possible et à moindre coût. Il est formulé comme une problème de programmation linéaire multi-objective en nombre entier. Premièrement, il s’agit de trouver un ensemble de compositions, chacune réalisant le même comportement désiré tout en satisfaisant au mieux ses préférences. Deuxièmement, l’ensemble des agents impliqués dans les compositions forment une équipe qui survit aux pannes d’un ou plusieurs agents. Cette thèse apporte une solution originale à chacun de ces problèmes tout en l’illustrant à l’aide d’exemples. L’utilisation des outils SMV/TLV, Uppaal et PuLP permet de vérifier, de synthétiser ou de calculer des éléments des exemples proposés.