Thèse ou mémoire avec insertion d'articles. / Avec la nature critique des défis environnementaux tels que le changement climatique et les émissions de CO2, le rôle du reboisement comme moyen de surmonter ces difficultés a reçu plus d'attention. Afin d'atteindre les objectifs des efforts de reboisement, il est nécessaire de développer des outils d'aide à la décision. L'objectif principal de cette thèse est d'améliorer la performance de la chaîne de valeur du reboisement en proposant des outils et des méthodes de planification d'une chaîne multi-produit et multi-site. Trois objectifs spécifiques ont été définis en support à l'objectif principal. Le premier objectif était de fournir un cadre formel pour la chaîne de valeur du reboisement (CVR) afin d'améliorer la compréhension de l'ensemble de la CVR; ses processus et les modèles de planification d'optimisation potentiels qui pourraient améliorer la performance de la chaîne de valeur. À cet égard, une analyse herméneutique de la littérature a été effectuée et un cadre formel pour la CVR a été fourni, qui tient compte des niveaux de planification stratégique, tactique et opérationnel pour accroître la collaboration entre les intervenants. Des opportunités de modélisation ont également été proposées pour mettre en évidence les besoins et tendances futures pouvant interpeler les scientifiques et les décideurs. Le deuxième objectif était de fournir un modèle de planification de l'allocation des semences dans le contexte d'une production sur commande (make-to-order) pour une chaîne de valeur collaborative de reboisement. Ce modèle a été utilisé pour analyser la chaîne de valeur du reboisement au Québec comprenant un centre de semences, 18 pépinières et des centaines de sites de reboisement. Lors de la résolution du modèle, les résultats ont montré qu'il était possible d'augmenter le succès du reboisement en allouant des semences compatibles aux sites de mise en terre et d'équilibrer les stocks de semences pour satisfaire les demandes entrantes. Pour le troisième objectif, un outil d'aide à la décision visant à améliorer la planification intégrée de la production et du transport a été développé. L'idée était de déterminer quels lots de semences devaient être produits par quelles pépinières afin de satisfaire l'attribution des lots de semences prédéfinie (second objectif). Le modèle a testé 10 scénarios différents pour déterminer les capacités contractuelles des pépinières, offrir un aperçu de l'impact de la durabilité sur le système et pour guider la prise de décisions liées aux investissements en infrastructures de production. / With the critical nature of environmental issues such as climate change and CO2 emissions, the role of reforestation as a way to overcome these challenges has received more attention. In order to achieve the reforestation objective, developing decision-making tools are required. The main objective of this thesis is to enhance the performance of reforestation value chains by proposing tools and methods for planning a multi-product, multi-site chain. To achieve this, three specific objectives were defined. The first objective was to provide a formal framework for the RVC to improve mutual understanding throughout the reforestation value chain, its processes, and the potential optimization planning models which could improve the value chain performance. In this regard, a hermeneutic literature review was conducted and a formal framework for the RVC provided, which considers strategic, tactical, and operational planning levels to increase collaboration among stakeholders. Modeling opportunities were also proposed to highlight future trends for scientists and policy makers. The second objective was to provide a seed allocation planning model in the context of a make-to-order collaborative reforestation value chain. This model was used to analyze the Quebec reforestation value chain comprising one seed center, 18 nurseries, and hundreds reforestation sites. When solving the model, results showed that it was possible to increase reforestation success by allocating compatible seeds to sites and to balance seed inventories to satisfy incoming demands. In the third objective, a decision-making tool to improve integrated production and transportation planning was developed. The idea was to determine which seed lots should be produced by which nurseries so as to satisfy the seed los allocation defined during the second objective. The model tested 10 different scenarios to determine contractual capacities of nurseries, to provide an overview of the impact of sustainability on the system, and to help in making decisions related to investment in infrastructure.

L’apparition de robots de service de plus en plus complexes ouvre de nouvelles perspectives quant aux tâches de manipulation d’objets. Malgré les progrès récents des techniques de planification de mouvement, peu d'entre elles s'intéressent directement à des systèmes multi-bras comme les torses humanoïdes. Notre contribution à travers cette thèse porte sur trois aspects. Nous proposons une technique de planification de mouvement performante basée sur la coordination des mouvements du système multi-bras. Elle exploite au mieux la structure du système en la divisant en parties élémentaires dont les mouvements sont planifiés indépendamment du reste du système. La fusion des différents réseaux élémentaires générés est ensuite réalisée dans le but d’obtenir un graphe prenant en compte le robot tout entier. Une seconde contribution porte sur l'extension des méthodes de planification pour des robots présentant des chaînes cinématiques fermées. Ces boucles cinématiques apparaissent dans le système lorsque, par exemple, le torse humanoïde saisit un objet avec plusieurs bras. Cette méthode traite explicitement les configurations singulières des manipulateurs, offrant ainsi une meilleure maniabilité de l’objet. Finalement, nous proposons deux approches pour la planification de tâches de manipulation d'objets par un torse humanoïde. La première concerne la résolution d’une tâche de prise et pose d'objets par un torse humanoïde à deux bras dans le cas où les contraintes imposées par la tâche nécessitent le passage par une double prise afin de transférer l'objet d'une main à l'autre. La seconde porte sur la résolution du même type de tâche par un manipulateur mobile. La thèse, effectuée dans le cadre du projet européen Phriends, présente les résultats d'expérimentations réalisées sur le robot Justin, démonstrateur du projet. / The emergence of new more and more complex service robots opens new research fields on objet manipulation. Despite the recent progresses in motion planning techniques, few of them deal directly with multi-arm systems like humanoid torsos. Our contribution through this thesis focuses on three aspects. We present an efficient motion planning technique based on the multi-arm system motion coordination. It takes advantage of the system's structure by dividing it into elementary parts of which movements are planned independently of the rest of the system. Generated elementary networks are then fused to obtain a roadmap that takes into account the whole robot. The second contribution consists of the extension of motion planning methods for a robot under loop closure constraints. These kinematic loops appear in the system when, for example, the humanoid torso grasps an objet with two arms. This method treats explicitly the singular configurations of the manipulators, providing better handling of the object. Finally, we present two approaches for planning object manipulation tasks by humanoid torsos. The first concerns solving pick and place task by humanoid torso where the imposed task constraints require a passage through a double grasp to transfer the object from one hand to the other. The second approach concerns the resolution of the same type of task by a mobile manipulator. The presented methods have been integrated on a real platform, Justin, and validated with experiments in the frame of E.U. FP-6 PHRIENDS project.

Le résumé en français n'a pas été communiqué par l'auteur. / Le résumé en anglais n'a pas été communiqué par l'auteur.

Un robot humanoïde est un système polyarticulé complexe dont la cinématique et la dynamique sont gouvernées par des équations non linéaires. Trouver des postures viables qui minimisent une tâche objectif tout en satisfaisant un ensemble de contraintes (intrinsèques ou extrinsèques) est un problème central pour la planification de mouvement robotique et est une fonctionnalité importante de tout logiciel de robotique. Le générateur de posture (PG) a pour rôle de trouver une posture viable en formulant puis résolvant un problème d’optimisation non linéaire. Nous étendons l’état de l’art en proposant de nouvelles formulations et méthodes de résolution de problèmes de génération de postures. Nous enrichissons la formulation de contraintes de contact par ajout de variables au problème d’optimisation, ce qui permet au solveur de décider automatiquement de la zone d’intersection entre deux polygones en contact ou encore de décider du lieu de contact sur une surface non plane. Nous présentons une reformulation du PG qui gère nativement les variétés non Euclidiennes et nous permet de formuler des problèmes mathématiques plus élégants et efficaces. Pour résoudre de tels problèmes, nous avons développé un solveur non linéaire par SQP qui supporte nativement les variables sur variétés. Ainsi, nous avons une meilleure maîtrise de notre solveur et pouvons le spécialiser pour la résolution de problèmes de robotique. / Humanoid robots are complex poly-articulated structures whose kinematics and dynamics are governed by nonlinear equations. Finding viable postures to realize set-point task objectives under a set of constraints (intrinsic and extrinsic limitations) is a key issue in the planning of robot motion and an important feature of any robotics framework. It is handled by the so called posture generator (PG) that consists in formalizing the viable posture as the solution to a nonlinear optimization problem. We present several extensions to the state-of-the-art by exploring new formulations and resolution methods for the posture generation problems. We reformulate the notion of contact constraints by adding variables to enrich our optimization problem and allow the solver to decide on the shape of the intersection of contact polygons or of the location of a contact point on a non-flat surface. We present a reformulation of the PG problem that encompasses non-Euclidean manifolds natively for a more elegant and efficient mathematical formulation of the problems. To solve such problems, we decided to implement a new SQP solver that is most suited to non-Euclidean manifolds structural objects. By doing so, we have a better mastering in the way to tune and specialize our solver for robotics problems.

L’objectif de ce travail est de permettre à une équipe de robots autonomeshétérogènes d’effectuer une mission complexe dans un environnement réel et sous contraintede communication. Cette thèse a donc consisté à créer et à valider une architecturedistribuée à bord des robots et intégrant planification, supervision de l’exécution du planet réparation de ce plan suite à l’occurrence d’aléas. Ce manuscrit présente la conceptiond’un algorithme de planification hybride, dénommé HiPOP, utilisé pour calculer un planinitial, avant le début de la mission, et pour réparer le plan en cours de mission quandun événement perturbateur survient. Il présente aussi la conception d’un algorithme desupervision, dénommé METAL, utilisé pour suivre l’exécution du plan sur chaque robot et,le cas échéant, faisant appel à HiPOP pour réparer le plan. Ces deux algorithmes ont étéimplémentés et ont permis de réaliser des missions de surveillance allant jusqu’à impliquer12 robots, à la fois en simulation et avec de vrais robots. / The goal of this work is to enable a team of heterogeneous autonomous robotsto perform a complex mission in a real environment with communication constraints. Thisapproach was therefore to create and validate a distributed embedded architecture ableto plan, to monitor the execution of a plan and to repair a plan when an unexpectedevent occurs. This document shows the conception of an hybrid planning algorithm, namedHiPOP, used to compute initial plans before the beginning of the mission and to repair theplan during the mission when something unexpected happens. It also shows the conceptionof a monitoring algorithm, named METAL, used to monitor the execution of the planon each robot and, when needed, which calls HiPOP to repair the plan. Both algorithmswere implemented and used to carry out surveillance missions up to 12 robots, both insimulation and in a real life scenario.

Cette thèse s'inscrit dans le cadre de la planification de tâches en intelligence artificielle. Après avoir introduit le domaine et les principaux algorithmes de planification dans le cadre classique, nous présentons un état de l'art de la planification SAT. Nous analysons en détail cette approche qui permet de bénéficier directement des améliorations apportées régulièrement aux solveurs SAT. Nous proposons de nouveaux codages qui intègrent une stratégie de moindre engagement en retardant le plus possible l'ordonnancement des actions. Nous présentons ensuite le système TSP que nous avons implémenté pour comparer équitablement les différents codages puis nous détaillons les résultats de nombreux tests expérimentaux qui démontrent la supériorité de nos codages par rapport aux codages existants. Nous présentons ensuite un état de l'art de la planification temporelle en analysant les algorithmes et l'expressivité de leurs langages de représentation. La très grande majorité de ces planificateurs ne permet pas de résoudre des problèmes réels pour lesquels la concurrence des actions est nécessaire. Nous détaillons alors les deux approches originales de notre système TLP-GP permettant de résoudre ce type de problèmes. Ces approches sont comparables à la planification SAT, une grande partie du travail de recherche étant déléguée à un solveur SMT. Nous proposons ensuite des extensions du langage de planification PDDL qui permettent une certaine prise en compte de l'incertitude, du choix, ou des transitions continues. Nous montrons enfin, grâce à une étude expérimentale, que nos algorithmes permettent de résoudre des problèmes réels nécessitant de nombreuses actions concurrentes.

Un des challenges actuels de la planification est la résolution de problèmes pour lesquels on cherche à optimiser la qualité d'une solution telle que le coût d'un plan-solution. Dans cette thèse, nous développons une méthode originale pour la planification de coût optimal dans un cadre classique non temporel et avec des actions valuées.<br /><br />Pour cela, nous utilisons une structure de longueur fixée appelée graphe de planification. L'extraction d'une solution optimale, à partir de ce graphe, est codée comme un problème de satisfaction de contraintes pondérées (WCSP). La structure spécifique des WCSP obtenus permet aux solveurs actuels de trouver, pour une longueur donnée, une solution optimale dans un graphe de planification contenant plusieurs centaines de nœuds. <br /><br />Nous présentons ensuite plusieurs méthodes pour déterminer la longueur maximale des graphes de planification nécessaire pour garantir l'obtention d'une solution de coût optimal. Ces méthodes incluent plusieurs notions universelles comme par exemple la notion d'ensembles d'actions indispensables pour lesquels toutes les solutions contiennent au moins une action de l'ensemble. <br /><br />Les résultats expérimentaux effectués montrent que l'utilisation de ces méthodes permet une diminution de 60% en moyenne de la longueur requise pour garantir l'obtention d'une solution de coût optimal. La comparaison expérimentale avec d'autres planificateurs montre que l'utilisation du graphe de planification et des CSP pondérés pour la planification optimale est possible en pratique même si elle n'est pas compétitive, en terme de temps de calcul, avec les planificateurs optimaux récents.

Le probleme aborde dans ce mémoire est celui de la planification des mouvements d'un mobile a soumis a des contraintes cinématiques et dynamiques et se déplaçant dans un espace de travail dynamique w. Ce mémoire défend la thèse selon laquelle le probleme considère, connu pour être complexe, peut entre résolu de façon efficace lorsqu'il existe une structuration de w naturelle pour a, i.e. Lorsqu'il est possible de structurer w en un ensemble de zones libres a l'intérieur desquelles a peut se déplacer. Dans ce cas, le probleme peut être aborde suivant deux directions complémentaires: 1) la planification de chemin qui prend en compte les contraintes cinématiques de a et les obstacles fixes de w, et; 2) la planification de trajectoire qui prend en compte les contraintes dynamiques de a et les obstacles mobiles de w. Ce mémoire traite le cas d'une voiture dans le réseau routier. Les zones libres sont alors définies par les voies de circulation. A est soumis a une contrainte cinématique non-holonome qui l'oblige a se déplacer dans une direction perpendiculaire a l'axe de ses roues. De plus, le rayon de braquage, l'accélération et la vitesse de a sont limites. Nous commençons par présenter deux techniques de resolution propres a chacune des deux planifications mentionnées ci-dessus et bien adaptées au contexte dans lequel nous nous plaçons. Puis, nous montrons comment intégrer ces deux techniques au sein d'un système de planification de mouvement qui permet de résoudre efficacement le probleme considéré

Permettre à plusieurs agents de planifier et de coordonner leurs activités de manière distribuée tel est l'objectif des travaux présentés dans ce mémoire. L'approche proposée s'appuie sur des opérateurs de composition de plans. Afin de gérer au mieux les interactions entre différents agents, leurs plans sont produits par IxTeT, un système de planification permettant la prise en compte de contraintes temporelles numériques et gérant le parallélisme des tâches ainsi que le partage de ressources. Les deux premiers chapitres décrivent le formalisme logique utilisé par IxTeT ainsi que le fonctionnement du planificateur lui-même et les améliorations qu'il est possible d'y apporter. Le troisième chapitre détaille alors formellement les méthodes et algorithmes permettant de réaliser des opérateurs de composition de plans: union de plans, insertion de nouveaux buts dans un plan existant. On y démontre leurs limites théoriques. Le quatrième chapitre décrit la mise en œuvre de ces opérateurs en exhibant des algorithmes tant pour améliorer les performances de la planification incrémentale mono-agent que pour réaliser un système distribué de planification multi-agents. Dans ce système, un plan global est élaboré par composition successive de plans individuels. Ce plan global reste implicite et n'est donc jamais centralisé. On présente ensuite les problèmes spécifiques rencontrés lorsque planification et exécution sont réalisées simultanément. Ces problèmes ouverts sont cruciaux dans un contexte multi-agents. Le document se termine par une illustration et une évaluation sur des exemples appliqués au domaine multi-robots permettant d'apprécier les avantages mais aussi les limites de l'utilisation de ces opérateurs de composition de plans et par une comparaison avec un autre système de planification distribuée.

Thèse de doctorat : Sciences de gestion : Université Nancy 2 : 2007. / Titre provenant de l'écran-titre.