No description available.

No description available.

This thesis introduces locomotion synthesis methods for humanoid characters. Motion synthesis is an under-constrained problem that requires additional constraints beyond user inputs. Two main approaches to introducing additional constraints are physics-based and data-driven. Despite significant progress in the past 20 years, major difficulties still exist for both approaches. In general, building animation systems that are flexible to user requirements while keeping the synthesized motions plausible remain a challenging task. The methods introduced in this thesis, presented in two-parts, aim to allow animation systems to be more flexible to user demands without radically violating constraints that are important for maintaining plausibility. In the first part of the thesis, we address an important subproblem in physics-based animation --- controller synthesis for humanoid characters. We describe a method for optimizing the parameters of a physics-based controller for full-body, 3D walking. The objective function includes terms for power minimization, angular momentum minimization, and minimal head motion, among others. Together these terms produce a number of important features of natural walking, including active toe-off, near-passive knee swing, and leg extension during swing. We then extend the algorithm to optimize for robustness to uncertainty. Many unknown factors, such as external forces, control torques, and user control inputs, cannot be known in advance and must be treated as uncertain. Controller optimization entails optimizing the expected value of the objective function, which is computed by Monte Carlo methods. We demonstrate examples with a variety of sources of uncertainty and task constraints. The second part of this thesis deals with the data-driven approach and the problem of motion modeling. Defining suitable models for human motion data is non-trivial. Simple linear models are not expressive enough, while more complex models require setting many parameters and are difficult to learn with limited data. Using Bayesian methods, we demonstrate how the Gaussian process prior can be used to derive a kernelized version of multilinear models. The result is a locomotion model that takes advantage of training data addressed by multiple indices to improve generalization to unseen motions.

This thesis introduces locomotion synthesis methods for humanoid characters. Motion synthesis is an under-constrained problem that requires additional constraints beyond user inputs. Two main approaches to introducing additional constraints are physics-based and data-driven. Despite significant progress in the past 20 years, major difficulties still exist for both approaches. In general, building animation systems that are flexible to user requirements while keeping the synthesized motions plausible remain a challenging task. The methods introduced in this thesis, presented in two-parts, aim to allow animation systems to be more flexible to user demands without radically violating constraints that are important for maintaining plausibility. In the first part of the thesis, we address an important subproblem in physics-based animation --- controller synthesis for humanoid characters. We describe a method for optimizing the parameters of a physics-based controller for full-body, 3D walking. The objective function includes terms for power minimization, angular momentum minimization, and minimal head motion, among others. Together these terms produce a number of important features of natural walking, including active toe-off, near-passive knee swing, and leg extension during swing. We then extend the algorithm to optimize for robustness to uncertainty. Many unknown factors, such as external forces, control torques, and user control inputs, cannot be known in advance and must be treated as uncertain. Controller optimization entails optimizing the expected value of the objective function, which is computed by Monte Carlo methods. We demonstrate examples with a variety of sources of uncertainty and task constraints. The second part of this thesis deals with the data-driven approach and the problem of motion modeling. Defining suitable models for human motion data is non-trivial. Simple linear models are not expressive enough, while more complex models require setting many parameters and are difficult to learn with limited data. Using Bayesian methods, we demonstrate how the Gaussian process prior can be used to derive a kernelized version of multilinear models. The result is a locomotion model that takes advantage of training data addressed by multiple indices to improve generalization to unseen motions.

Notre travail de recherche concerne l’étude de la commande à base de modèles pour une sous-classe de systèmes dynamiques hybrides (SDH). L’outil de modélisation choisi est l’automate hybride rectangulaire (AHR) pour sa puissance d’analyse. Nous proposons ainsi une méthode pour la synthèse de la commande des SDH modélisés par des AHR. Cette méthode repose sur l’application d’une procédure amont/aval de commande hors-ligne qui détermine d’une façon maximale permissive les nouvelles gardes de transition de l’automate respectant des spécifications de commande imposées par l’utilisateur. Tous les calculs réalisés reposent sur la détermination de la durée de séjour, valeur contrainte par l’espace atteignable du sommet correspondant. La garde portant à la fois sur l’état continu et sur l’événement discret, la commande se fait par ce dernier car il s’agit du seul élément contrôlable. Nous nous intéressons alors à la construction du contrôleur temporisé autorisant l’occurrence des événements contrôlables du système dans un intervalle d’horloge défini au sens de la maximale permissivité. / In this thesis, we study the control of a class of hybrid dynamic systems (HDS). The chosen modeling tool is the rectangular hybrid automaton (RHA) for his analysis power. We propose a method for the control synthesis of HDS modeled with RHA. This method consists on the application of a downstream/upstream offline control procedure that determines in a maximal permissive way the new automaton transition guards respecting the desired control specifications. All computations are based on the determination of the duration of stay, a value constrained by the reachable space of the corresponding location. Since the guard refers to both continuous state and discrete event, the control is made by the latter because it is the controllable element. Then we are interested in the construction of the timed controller authorizing the system controllable event occurrence in a clock interval defined in a maximal permissive way.

Today, many embedded or cyber-physical systems, e.g., in the automotive domain, comprise several control applications, sharing the same platform. It is well known that such resource sharing leads to complex temporal behaviors that degrades the quality of control, and more importantly, may even jeopardize stability in the worst case, if not properly taken into account. In this thesis, we consider embedded control or cyber-physical systems, where several control applications share the same processing unit. The focus is on the control-scheduling co-design problem, where the controller and scheduling parameters are jointly optimized. The fundamental difference between control applications and traditional embedded applications motivates the need for novel methodologies for the design and optimization of embedded control systems. This thesis is one more step towards correct design and optimization of embedded control systems. Offline and online methodologies for embedded control systems are covered in this thesis. The importance of considering both the expected control performance and stability is discussed and a control-scheduling co-design methodology is proposed to optimize control performance while guaranteeing stability. Orthogonal to this, bandwidth-efficient stabilizing control servers are proposed, which support compositionality, isolation, and resource-efficiency in design and co-design. Finally, we extend the scope of the proposed approach to non-periodic control schemes and address the challenges in sharing the platform with self-triggered controllers. In addition to offline methodologies, a novel online scheduling policy to stabilize control applications is proposed.

La théorie des jeux est un outils standard quand il s'agit de l'étude des systèmes réactifs. Ceci est une conséquence de la variété des modèle de jeux tant au niveau de l'interaction des joueurs qu'au niveau de l'information que chaque joueur possède.Dans cette thèse, on étudie le problème de la valeur pour des jeux où les joueurs possèdent une information parfaite, information partiel et aucune information. Dans le cas où les joueurs possèdent une information parfaite sur l'état du jeu,on étudie le problème de la valeur pour des jeux dont les objectifs sont des combinaisons booléennes d'objectifs qualitatifs et quantitatifs.Pour les jeux stochastiques à un joueur, on montre que les valeurs sont calculables en temps polynomiale et on montre que les stratégies optimalespeuvent être implementées avec une mémoire finie.On montre aussi que notre construction pour la conjonction de parité et de la moyenne positivepeut être étendue au cadre des jeux stochastiques à deux joueurs. Dans le cas où les joueurs ont une information partielle,on étudie le problème de la valeur pour la condition d'accessibilité.On montre que le calcul de l'ensemble des états à valeur 1 est un problème indécidable,on introduit une sous classe pour laquelle ce problème est décidable.Le problème de la valeur 1 pour cette sous classe est PSPACE-complet dansle cas de joueur aveugle et dans EXPTIME dans le cas de joueur avec observations partielles. / Game theory proved to be very useful in the fieldof verification of open reactive systems. This is due to the widevariety of games' model that differ in the way players interactand the amount of information players have.In this thesis, we study the value problem forgames where players have full knowledge on their current configurationof the game, partial knowledge, and no knowledge.\\In the case where players have perfect information,we study the value problem for objectives that consist in combinationof qualitative and quantitative conditions.In the case of one player stochastic games, we show thatthe values are computable in polynomial time and show thatthe optimal strategies exist and can be implemented with finite memory.We also showed that our construction for parity and positive-average Markov decisionprocesses extends to the case of two-player stochastic games.\\In the case where the players have partial information,we study the value problem for reachability objectives.We show that computing the set of states with value 1 is an undecidableproblem and introduce a decidable subclass for the value 1 problem.This sub class is PSPACE-complete in the case of blind controllersand EXPTIME is the setting of games with partial observations.

The research described in this dissertation deals with an open problem concerning the synthesis of controllers of xed order and structure. This problem is encountered in a variety of applications. Simply put, the problem may be put as the determination of the set, S of controller parameter vectors, K = (k1; k2; : : : ; kl), that render Hurwitz a family (indexed by F) of complex polynomials of the form fP0(s; ) + Pl i=1 Pi(s; )ki; 2 Fg, where the polynomials Pj(s; ); j = 0; : : : ; l are given data. They are specied by the plant to be controlled, the structure of the controller desired and the performance that the controllers are expected to achieve. Simple examples indicate that the set S can be non-convex and even be disconnected. While the determination of the non-emptiness of S is decidable and amenable to methods such as the quantier elimination scheme, such methods have not been computationally tractable and more importantly, do not provide a reasonable approximation for the set of controllers. Practical applications require the construction of a set of controllers that will enable a control engineer to check the satisfaction of performance criteria that may not be mathematically well characterized. The transient performance criteria often fall into this category. From the practical viewpoint of the construction of approximations for S, this dissertation is dierent from earlier work in the literature on this problem. A novel feature of the proposed algorithm is the exploitation of the interlacing property of Hurwitz polynomials to provide arbitrarily tight outer and inner approximation to S. The approximation is given in terms of the union of polyhedral sets which are constructed systematically using the Hermite-Biehler theorem and the generalizations of the Descartes' rule of signs.

The research described in this dissertation deals with an open problem concerning the synthesis of controllers of xed order and structure. This problem is encountered in a variety of applications. Simply put, the problem may be put as the determination of the set, S of controller parameter vectors, K = (k1; k2,...,kl), that render Hurwitz a family (indexed by F) of complex polynomials of the form {P0(s.a) + [summation] i=1 Pi(s,a)ki, a [set membership] F}, where the polynomials Pj(s,a), j = 0,...,l are given data. They are specied by the plant to be controlled, the structure of the controller desired and the performance that the controllers are expected to achieve. Simple examples indicate that the set S can be non-convex and even be disconnected. While the determination of the non-emptiness of S is decidable and amenable to methods such as the quantier elimination scheme, such methods have not been computationally tractable and more importantly, do not provide a reasonable approximation for the set of controllers. Practical applications require the construction of a set of controllers that will enable a control engineer to check the satisfaction of performance criteria that may not be mathematically well characterized. The transient performance criteria often fall into this category. From the practical viewpoint of the construction of approximations for S, this dissertation is dierent from earlier work in the literature on this problem. A novel feature of the proposed algorithm is the exploitation of the interlacing property of Hurwitz polynomials to provide arbitrarily tight outer and inner approximation to S. The approximation is given in terms of the union of polyhedral sets which are constructed systematically using the Hermite-Biehler theorem and the generalizations of the Descartes' rule of signs.

Le contrôle de systèmes industriels à cause de l’automatisation et la réduction de nombre des opérateurs devient un enjeu crucial. Les systèmes de production automatisés (AMS) sont d’autant plus touchés car une défaillance du programme de contrôle peut réduire considérablement la productivité voire entraîner l’arrêt du système de production. Pour certains de ces systèmes où le partage des ressources est pondérant, la notion de blocage partiel ou global est fréquente et la validation avant implantation est préférable pour réduire les risques.En raison de la capacité des réseaux de Petri à décrire aisément l’exécution concurrente des processus et le partage des ressources, de nombreuses méthodes de vérification d’absence de blocage et de synthèse de contrôleurs basées sur la théorie structurelle ou le graphe d’accessibilité des réseaux de Petri ont été proposées au cours des deux dernières décennies.Traditionnellement, une méthode de prévention de blocage est évaluée selon trois critères de performance: la complexité structurelle, la permissivité comportementale, et la complexité de calcul. Les méthodes fondées sur l’espace d’état aboutissent généralement à un contrôle maximal permissif mais souffrent de l'explosion combinatoire de l'espace d'états. En revanche, les méthodes de synthèse de contrôleurs fondées sur l’analyse structurelle évitent le problème de l’explosion de l’espace d’état mais aboutissent à des superviseurs pouvant restreindre considérablement les comportements admissibles du système. De plus si la théorie structurelle de contrôle de siphons pour la synthèse des superviseurs est mature dans le cas des réseaux de Petri ordinaires, elle est en développement pour les réseaux de Petri généralises. Par ailleurs, la plupart des travaux existants partent du principe que les ressources sont constamment disponibles. Or l’indisponibilité de ressources est en réalité un phénomène ordinaire. Il serait donc judicieux de développer une politique de vérification de blocage qui soit efficace tout en considérant des ressources non fiables.Cette thèse vise principalement à faire face aux limitations mentionnées ci-dessus. Nos principales contributions à la fois théoriques et algorithmiques sont les suivantes.Premièrement, après avoir revisité les conditions de contrôlabilité des siphons (cs–propriété) et précisé les limitations de la max cs- propriété et max’ cs- propriété, nous définissons la max’’ cs-propriété et nous démontrons que cette nouvelle propriété est une condition non seulement suffisante mais aussi nécessaire pour la vivacité de la classe des GS3PR (Generalized Systems of SimpleSequential Processes with Resources).Par la suite nous montrons comment le problème de la vérification de cette propriété et donc la vivacité des GS3PR peut se ramener à la résolution d’un programme linéaire en nombre entiers.Dans une seconde partie, nous proposons une classe de réseaux de Petri appelée M-Nets dotée d’une forte capacité de modélisation des systèmes de production automatisés. En combinant la théorie du contrôle siphon avec la théorie des régions, nous développons une méthode de prévention de blocage ayant un bon compromis entre l'optimalité du comportement et la complexité de calcul. De plus, nous proposons une méthode de synthèse d'un contrôleur maximal permissif pour une sous-classe de réseaux notée b-nets.Enfin, nous proposons dans cette thèse une méthode de conception d’un superviseur de systèmes de production automatisés où les ressources ne sont pas toutes fiables et particulièrement efficace pour la classe des S3PR (Systems of Simple Sequential Processes with Resources). / Because of automation and reduction of the number of operators, the control of industrial systems is becoming a critical issue. For automated manufacturing systems (AMS) where resource sharing is preponderant, the notion of partial or total blocking is frequent and validation before implementation is preferable to reduce the risks.Due to the easy and concise description of the concurrent execution of processes and the resource sharing by Petri nets, many methods to verify deadlock-freeness and to synthesize controllers using structural theory or reachability graph have been proposed over the past two decades.Traditionally, a deadlock control policy can be evaluated by three performance criteria : structural complexity, behavioral permissiveness, and computational complexity. Generally, deadlock control policies based on the state space analysis can approach the maximal permissive behavior, but suffer from the state explosionproblem. On the contrary deadlock control policies based on the structural analysis of Petri nets avoid in general the state explosion problem successfully, but cannot lead to the maximally or near maximally permissive controller. Morover, the current Deadlock control theory based on siphons is fairly mature for ordinary Petri nets,while for generalized Petri nets, it is presently at an early stage.On the other hand, most deadlock control policies based on Petri nets for AMS proceed on the premise that the resources in a system under consideration are reliable. Actually, resource failures are inevitable and common in most AMS, which may also cause processes to halt. Therefore, it is judicious to develop an effective and robust deadlock control policy considering unreliable resources.This thesis aims to cope with the limitations mentioned above. Our main theoretical and algorithmic contributions are the following. Firstly, after revisiting the controllability conditions of siphons and limitations of max and max' controlled-siphon properties, we define the max'' cs property and we prove that this new cs-property is not only sufficient but also a necessary liveness condition forgeneralized systems of simple sequential processes with resources (GS3PR). Moreover, we show how the checking of this property and hence liveness of GS3PR nets can be translaled into resolution of an integer programming (IP) model.Secondly, we propose a class of manufacturing-oriented Petri nets, M-nets for short, with strong modeling capability. Combining siphon control and the theory of regions, we develop a deadlock prevention method that makes a good trade-off between behavioral optimality and computational tractability Moreover, this thesis proposes a maximally permissive control policy for a subclass of Petri nets (calledBéta-nets) based on the token distribution pattern of unmarked siphons.Finally, we propose a designs method for robust liveness-enforcingsupervisors for AMS with unreliable resources appropriate in particular for systems of simple sequential processes with resources(S3PR)