La planification forestière est un exercice ardu qui demande des efforts humains et matériels très importants. Plusieurs modèles de planification forestière sont proposés dans la littérature. Cependant, ils sont généralement difficiles à implémenter. En outre, leur performance est limitée aux forêts de petite taille ou de taille moyenne. L’objectif général de cette thèse est de proposer des outils simples et efficients qui permettent de réduire la complexité de cet exercice en utilisant la modélisation mathématique. Les modèles proposés dans cette thèse traitent le problème de planification forestière sur un horizon tactique et considèrent principalement deux restrictions spatiales qui sont des restrictions d’adjacence ou de période de régénération et des restrictions de rendement soutenu de récolte. Dans la première partie, nous avons proposé une nouvelle formulation mathématique basée sur la programmation en nombres entiers qui permet de modéliser le problème de planification tactique sous des contraintes spatiales. Nous avons eu recours à une méthode de résolution exacte à l’aide d’un solveur commercial pour résoudre le problème. Nous avons utilisé plusieurs forêts réelles de tailles différentes dont trois sont de très grandes forêts dans la région de la Mauricie au Québec. Pour évaluer la performance de notre modèle proposé, nous avons utilisé deux autres formulations mathématiques qui sont déjà proposées dans la littérature pour résoudre le même problème sous les mêmes contraintes. Les résultats ont montré que notre formulation est plus simple d’un point de vue de la modélisation et de l’implémentation. En ce qui concerne la résolution, les résultats ont montré qu’il n’y pas une formulation qui avait une performance supérieure lorsque la taille des forêts est petite ou moyenne. Cependant, lorsque la taille des forêts devient large, notre formulation avait une performance supérieure. Dans la deuxième partie de la thèse, nous avons proposé deux méthodes pour résoudre le même problème en utilisant les grandes forêts. La première méthode est une heuristique basée sur la relaxation linéaire. Pour évaluer sa performance, nous avons comparé les résultats qu’elle a fournis avec ceux obtenus en utilisant un solveur commercial pendant une durée de résolution prédéfinie. Les résultats ont montré que le solveur est plus performant lorsque le problème est mono-période. Cependant, lorsque le problème est multi-période, contrairement à notre heuristique, le solveur n’était pas capable d’obtenir un résultat pendant le temps de résolution fixé. La deuxième méthode consiste à contrôler la taille des problèmes à résoudre à travers un indicateur qui contrôle la forme des regroupements de peuplements à couper. En plus de sa simplicité, cette méthode permet de réduire significativement la taille des problèmes et d’avoir une planification opérationnelle plus efficiente par l’élimination des regroupements de peuplement ayants des formes non désirables. Dans la troisième partie, nous avons proposé un modèle intégré stochastique bi-niveau qui permet la planification de la coupe tout en considérant les feux de forêts. La formulation mathématique proposée dans la première partie de la thèse représente le premier niveau. Le deuxième niveau est un modèle de propagation de feux. Il considère des points d’ignition du feu, des points critiques tels que des municipalités et des croisements de routes forestières et deux scénarios de différentes directions et vitesses de vent. L’intégration est possible à travers la reformulation primal-dual des conditions d’optimalités du problème du plus court chemin entre les points d’ignition et les points critiques. Nous avons utilisé des forêts hypothétiques pour les expérimentations. Les résultats ont montré que les regroupements de peuplements planifiés sont localisés dans des zones qui permettent de retarder la propagation du feu des points d’ignition vers les points critiques. / Forest planning is a difficult task that needs important human and material efforts. Many forest planning modelsare proposed in the literature. However, their implementation is usually complex. More over, their performanceis limited to small and medium forests. The whole objective of this thesis is to propose simple and efficient tools to reduce the complexity of the forest planning using mathematical modeling. In this thesis, proposed models are applied for tactical forest planning and consider mainly two spatial restrictions that are adjacency or green-up restrictions and sustainable timber yields restrictions.In the first part, we proposed a new mathematical formulation based on integer programming to model the tactical forest planning under spatial restrictions. We solved the model with an exact method using a commercial solver. We used many real forests with different sizes. Three of them are very large forests and are located in the Mauricie region of Quebec. We evaluated the performance of the proposed model using two other formulation sexisting in the literature to model the same problem under the same restrictions. Results showed that there isno formulation that out performed others when small and medium forests are used. However, the proposed formulation out performed others when large forests are used.In the second part, we proposed two heuristic approaches to solve the same problem using large forests. The first one is a linear relaxation heuristic. We compared results obtained with the heuristic with those obtained with a commercial solver when a computational time is predefined. Results showed that the solver is more performant when mono-periods problems were solved. However, when multi-periods problems were solved, unlike ourheuristic, the solver does not find any feasible solution within the fixed computational time. The second heuristicis a size reduction heuristic which uses a shape index to control the shape of the clusters of stands. Besides its simplicity, this method is very beneficial as it reduces significantly problems size and anticipate the operational planning by eliminating non-profitable clusters. In the third part, we proposed a stochastic programming model formulated as an integrated mixed integerprogramming model for scheduling harvesting operations, which directly takes into account a fire spread model. It is a bi-level model. In the first level, we used the tactical forest planning model proposed in the first part. The second level represents the fire spread model that considers fire spread between ignition points and critical points, which could be, for example, municipalities and important road crossings. It considers multiple scenarios, which takes into account wind direction, and wind spread. The integration is possible due to a reformulation of a bi-level optimization problem where the lower level shortest path representation is written explicitly with aprimal-dual reformulation of its optimality conditions. Results based on a set of illustrative instances are presented. Results vary depending on spatial restrictions considered in the model. However, harvesting scheduled are usually allocated to delay fires reaching critical points and tends to allocate harvesting operations around critical points.

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.