L'objet des recherches en planification de tâches est d'élaborer des algorithmes et des représentations qui participent à l'autonomie des robots en les dotant de capacités décisionnelles. Classiquement, un plan symbolique synthétisé par un planificateur permet au robot de décider des prochaines actions qu'il doit accomplir pour satisfaire sa mission. Dans cette thèse, nous développons l'idée que les planificateurs actuels, basés sur une représentation logique du monde, ne sont pas suffisants pour traiter des missions où les contraintes de mouvements des robots et celles liées à la manipulation d'objet ne peuvent pas être ignorées à cette étape. Souvent, en robotique, la faisabilité des mouvements et des manipulations est un pré-requis à la bonne exécution d'un plan. Dans cette thèse, nous introduisons un formalisme permettant de prendre en considération ces contraintes dans le modèle utilisé par un planificateur. En nous appuyant sur des résultats issus de la planification de mouvements et de manipulations autant que sur ceux de la planification de tâches, nous proposons un nouveau planificateur capable de raisonner sur ce formalisme. Nous produisons alors des plans définissant non seulement un ordre d'actions mais également les mouvements sans collision nécessaires à son exécution. L'implémentation de ce planificateur est présentée et évaluée.

Un système robotique agit par le mouvement dans un monde physique. La capacité de planification de mouvement est une composante essentielle de son autonomie. C'est le thème des travaux présentés dans ce mémoire. Ils s'articulent selon quatre axes.Le premier concerne l'algorithmique géométrique du mouvement. La ligne forte qui se retrouve dans nos travaux est de privilégier des méthodes effectives de planification. En effet, la plupart des problèmes réels résistent aux approches algorithmiques exactes; nous présentons des approches de nature différente, qui en satisfaisant une forme plus faible de complétude (e.g. complétude probabiliste) sont capables de mieux répondre aux besoins des applications en termes d'efficacité et de robustesse algorithmique. Nous considérons ensuite des problèmes plus riches que la seule planification de mouvement, et plus directement liés à la notion de tâches en robotique. La seconde partie porte sur la planification de tâches de manipulation d'objets. La formulation géométrique que nous présentons permet d'étendre le concept d'espace des configurations à la planification automatique de ces tâches. D'autre part, les mouvements d'un robot s'effectuant dans un monde réel, la robustesse algorithmique doit être étendue à la robustesse de la boucle planification/contrôle des mouvements vis à vis des incertitudes dans les modèles manipulés par le raisonnement ou des imprécisions liées à l'exécution. C'est le thème de la troisième partie qui présente une approche combinant planification avec incertitude et modes réactifs: les algorithmes de planification utilisent la connaissance a priori sur la tâche pour produire des primitives référencées capteurs adaptées à la robotique mobile. Enfin, la dernière partie porte sur la planification de mouvements pour des robots mobiles évoluant dans des environnements naturels non structurés. Les techniques prése ntées permettent de traiter des systèmes de locomotion complexes et des terrains fortement accidentés.

Ce mémoire présente une solution au problème de contrôle de caméra hors-ligne dans un environnement en trois dimensions où se déroule une bataille navale. D'abord, une introduction du domaine est présentée, le but étant d'établir les fondations sur lesquelles se basera l'ensemble des sections de ce document. Ensuite, une revue de la littérature est effectuée. Le contrôle de la caméra dans le domaine du cinéma est exploré. Diverses techniques de contrôle sont également présentées tout en discutant leur pertinence au problème. Une approche de planification par réseau de tâches hiérarchique est ultimement choisie comme solution. Pour décrire cette solution, la modélisation du planificateur et de ses composantes est d'abord exposée. Par la suite, l'algorithme de planification est présenté. Une architecture de planification et d'exécution, intégrant l'algorithme de planification avec le contrôle bas-niveau de la caméra est aussi proposée. L'implémentation de cette architecture est ensuite discutée et illustrée à l'aide des résultats expérimentaux. La conclusion est suivie par une annexe décrivant les détails de l'implémentation.

Cette thèse présente des contributions dans le domaine de la planification en intelligence artificielle, et ce, plus particulièrement pour une classe de problèmes qui combinent des actions concurrentes (simultanées) et de l'incertitude. Deux formes d'incertitude sont prises en charge, soit sur la durée des actions et sur leurs effets.Cette classe de problèmes est motivée par plusieurs applications réelles dont la robotique mobile, les jeux et les systèmes d'aide à la décision.Cette classe a notamment été identifiée par la NASA pour la planification des activités des rovers déployés sur Mars. Les algorithmes de planification présentés dans cette thèse exploitent une nouvelle représentation compacte d'états afin de réduire significativement l'espace de recherche. Des variables aléatoires continues sont utilisées pour modéliser l'incertitude sur le temps. Un réseau bayésien, qui est généré dynamiquement, modélise les dépendances entre les variables aléatoires et estime la qualité et la probabilité de succès des plans. Un premier planificateur, ACTUP LAN nc basé sur un algorithme de recherche à chaînage avant, prend en charge des actions ayant des durées probabilistes. Ce dernier génère des plans non conditionnels qui satisfont à une contrainte sur la probabilité de succès souhaitée. Un deuxième planificateur, ACTUP LAN, fusionne des plans non conditionnels afin de construire des plans conditionnels plus efficaces. Un troisième planificateur, nommé QUANPLAN, prend également en charge l'incertitude sur les effets des actions. Afin de modéliser l'exécution simultanée d'actions aux effets indéterminés, QUANP LAN s'inspire de la mécanique quantique où des états quantiques sont des superpositions d'états classiques. Un processus décisionnel de Markov (MDP) est utilisé pour générer des plans dans un espace d'états quantiques. L'optimalité, la complétude, ainsi que les limites de ces planificateurs sont discutées. Des comparaisons avec d'autres planificateurs ciblant des classes de problèmes similaires démontrent l'efficacité des méthodes présentées. Enfin, des contributions complémentaires aux domaines des jeux et de la planification de trajectoires sont également présentées.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse concerne la planification des tâches de manipulation effectuées par une main robotisée. Il s'agit de mettre au point un système de calcul automatique des trajectoires que doivent suivre les doigts et l'objet manipulé, pour passer d'une configuration initiale à une configuration finale données. La méthode proposée dans cette thèse s'appuie sur une formulation originale du problème de planification, basée sur l'étude de la connexité des espaces des configurations de prise. Ces espaces sont explorés par l'intermédiaire de graphes probabilistes. En particulier, un graphe est construit pour explorer GSn, l'espace des configurations de prise à n doigts, n étant le nombre de doigts de la main. Les arêtes de ce graphe sont des chemins linéaires dans GSn. Utiliser de tels chemins permet d'éviter le calcul des mouvements de reconfiguration de prise et donc de réduire les temps de calcul et l'espace mémoire requis par la construction du graphe. Ces chemins ne sont pas cinématiquement réalisables puisque la pose de l'objet et la position des contacts ne peuvent changer indépendamment mais leur utilisation est rendue possible par la généralisation de la propriété de réduction introduite par Alami et al. Les mouvements de changement de prise qui requièrent d'être explicitement calculés au cours de la construction du graphe, sont pris en compte lors d'une étape de fusion des composantes connexes du graphe. Ces fusions sont réalisées à l'aide de chemins élémentaires respectant la cinématique de la manipulation coordonnée. Ces chemins sont appelés "chemins de ressaisie" et "chemins de transfert". Une fois que les configurations initiale et finale appartiennent à une même composante connexe du graphe, les chemins dans GSn sont décomposés en une suite de mouvements de déplacement de l'objet et de reconfiguration de la prise (chemins de transfert et de ressaisie), cinématiquement réalisables. Pour assurer la stabilité des chemins construits, un critère de stabilité de la prise (fermeture de force) est vérifié le long des chemins, lors de leur construction. Pour valider cette approche, une plate-forme de simulation a été développée et a permis de planifier différentes tâches de manipulation dextre avec une main à quatre doigts. Le planificateur offre des performances très intéressantes en terme de temps de calcul et a permis de résoudre des problèmes complexes tels qu'aucun résultat pour des problèmes de difficulté équivalente n'avait jamais été présenté jusqu'à présent. La méthode proposée s'applique à n'importe quel type de main, quel que soit son nombre de doigts mais, comme elle explore uniquement GSn et GS{n-1}, elle peut manquer des solutions si la main robotisée et le modèle des contacts doigt-objet permet la prise avec un nombre différent de doigts. Pour remédier à cela, nous avons proposé une méthode légèrement différente qui s'applique à une main à cinq doigts et consiste à construire un graphe pour explorer chacune des cinq composantes connexes de GS4 à l'aide de chemins linéaires dans cet espace et à tenter de fusionner les différents graphes à l'aide de chemins linéaires dans GS5 ou de chemins de transfert-ressaisie (dans GS3). Enfin, une variante de la méthode proposée a été développée pour prendre en compte le roulement relatif des surfaces de contact au cours de la manipulation de l'objet. Les différentes modifications nécessaires, concernant la représentation des prises et le calcul de chemins de transfert, sont présentées en détail.

Le frittage est un phénomène physico-chimique excessivement complexe et gouverné par de nombreuses variables expérimentales. Nous souhaitions comprendre ce phénomène et identifier les variables expérimentales influençant les propriétés dun matériau ayant subi un cycle de frittage. Les variables expérimentales étant nombreuses et interagissant parfois entre elles, une approche multivariée du problème était indispensable afin de fournir un travail riche dinformations. Nous avons donc utilisé massivement des techniques dites de data-mining (planification expérimentale) afin de mettre en évidence les corrélations existantes entre les paramètres expérimentaux et les propriétés du matériau fritté.

Dans le domaine de l'apprentissage par renforcement, la planifi ation dans les processus de décisions markoviens est une approche en ligne utilisée pour contrôler un système dont on possède un modèle génératif. Nous nous proposons d'adresser ce problème dans le cas déterministe avec espace d'action discret ou continu. Cette thèse s'attache au chapitre 2 à présenter succinctement les processus de décision markoviens puis l'apprentissage par renforcement. Nous présentons en particulier trois algorithmes centraux que sont l'itération de la valeur, l'itération de la politique et le Q-Learning. Au chapitre 3, nous expliquons l'approche de la planifi cation dans les processus de décision markoviens pour contrôler des systèmes en ligne. Ainsi, nous supposons posséder un modèle génératif d'un système à contrôler et nous l'utilisons pour décider, à chaque pas de temps du système à contrôler, de l'action à lui appliquer en vue de le faire transiter dans un état maximisant la somme future des récompenses dépréciées. Nous considérons un modèle génératif comme une boite noire, laquelle étant donnée un état et une action, nous retourne un état successeur ainsi qu'une récompense associée. L'approche optimiste est détaillée dans sa philosophie et dans son application à la résolution du dilemme exploration-exploitation au travers de di fférentes techniques présentes dans la littérature. Nous présentons di fférents algorithmes issus de la littérature et s'appliquant dans le cadre de la plani fication dans les processus de décision markoviens. Nous nous concentrons en particulier sur les algorithmes effectuant une recherche avant par construction d'un arbre des possibilités look-ahead tree en anglais. Les algorithmes sont présentés et mis en relation les uns avec les autres. L'algorithme de recherche du plus court chemin dans un graphe A est présenté en vue d'être relié à notre première contribution, l'algorithme de plani fication optimiste. Nous détaillons cette première contribution au chapitre 4. Dans un premier temps, nous présentons en détail le contexte de la planification sous contrainte de ressources computationnelles ainsi que la notion de regret. Dans un second temps, l'algorithme de plani cation uniforme est présenté et son regret est analysé pour obtenir une base comparative avec l'algorithme de plani cation optimiste. Enfi n, celui-ci est présenté et son regret est analysé. L'analyse est étendue à une classe de problèmes dé finie par la proportion de chemins -optimaux, permettant ainsi d'établir une borne supérieure sur le regret de l'algorithme de plani cation optimiste meilleure que celle de l'algorithme de plani cation uniforme dans le pire des cas. Des expérimentations sont menées pour valider la théorie et chi rer les performances de l'algorithme de plani cation optimiste par le biais de problèmes issus de la littérature comme le cart-pole, l'acrobot ou le mountain car et en comparaison à l'algorithme de plani cation uniforme, à l'algorithme UCT ainsi qu'à l'algorithme de recherche aléatoire. Nous verrons que, comme suggéré par la dé nition de la borne supérieure sur son regret, l'algorithme de plani cation optimiste est sensible au facteur de branchement ce qui nous mène à envisager le cas où l'espace d'action est continu. Ceci fait l'objet de nos deux autres contributions au chapitre 5. Notre deuxième contribution est l'algorithme de plani cation lipschitzienne reposant sur une hypothèse de régularité sur les récompenses menant à supposer que la fonction de transition et la fonction récompense du processus de décision markovien modélisant le système à contrôler sont lipschitziennes. De cette hypothèse, nous formulons une borne sur un sous-ensemble de sousespaces de l'espace d'action continu nous permettant de l'explorer par discr étisations successives. L'algorithme demande cependant la connaissance de la constante de Lipschitz associée au système à contrôler. Des expérimentations sont menées pour évaluer l'approche utilisée pour diff érentes constantes de Lipschitz sur des problèmes de la littérature comme le cart-pole, l'acrobot ou la lévitation magnétique d'une boule en acier. Les résultats montrent que l'estimation de la constante de Lipschitz est diffi cile et ne permet pas de prendre en compte le paysage local des récompenses. Notre troisième contribution est l'algorithme de plani cation séquentielle découlant d'une approche intuitive où une séquence d'instances d'un algorithme d'optimisation globale est utilisée pour construire des séquences d'actions issues de l'espace d'action continu. Des expérimentations sont menées pour évaluer cet approche intuitive pour diff érents algorithmes d'optimisation globale sur des problèmes de la littérature comme le cart-pole, le bateau ou le nageur. Les résultats obtenus sont encourageants et valident l'approche intuitive. Finalement, nous concluons en résumant les di érentes contributions et en ouvrant sur de nouvelles perspectives et extensions.

Cette recherche pose un regard sur la transversalité et l'interdisciplinarité du projet de ville viable, à travers la pratique du design urbain, pratique à saveur culturelle et dont les objectifs sont très rapprochés de ceux du développement durable en milieu urbain. D'une part, la culture, malgré les bonnes intentions, reste un domaine auquel on n'accorde pas l'importance qui lui revient. D'autre part, le discours concernant l'apport du design urbain à la ville viable fait souvent la preuve de la dominante environnementale sur le discours du développement durable: réduction du transport, densité, réduction de la consommation d'énergie, choix des matériaux de construction, etc. À l'ère de la « bonne gouvernance » et de la participation citoyenne, le rôle de négociation des professionnels du design urbain est de plus en plus important. IIs doivent être porteurs du projet de développement durable pour favoriser la construction collective de ce qui sera considéré comme un design urbain viable. Ainsi, leur propre perception du projet devient un facteur clé. Sur cette base, la recherche avait pour objectif de comprendre la dynamique existante entre la planifïcation de la ville viable et sa mise en oeuvre dans la pratique du design urbain, au moyen d'entretiens semi-dirigés auprès d'employés et élus municipaux. Sous forme d'études de cas, quatre villes ont été ciblées: Copenhague, Oslo, Montréal et Québec. Les résultats et l'analyse sont présentés en deux temps: d'abord selon les quatre cas à l'étude, puis selon les fonctions occupées par les personnes rencontrées lors des entretiens. Premier constat: quatre villes à l'étude et autant de stratégies différentes pour atteindre la viabilité urbaine. Mais la perception du développement durable, et surtout celle de l'environnement, est fortement tributaire du discours environnementaliste, parfois au détriment de la flexibilité souhaitée. De plus, il existe des langages professionnels qu'il importerait de faire se rencontrer, et les urbanistes semblent avoir un rôle important à jouer à ce niveau. Enfin, l'esprit de la gouvernance a déjà fait sa marque; les gens de tous horizons semblent prêts à accepter l'expertise des autres. Il ne reste plus qu'à trouver de bonnes façons de favoriser le partage. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Ville viable, Développement durable, Design urbain, Interdisciplinarité, Transversalité, Culture, Processus, Perceptions, Information.

Cette thèse est consacrée au problème de la planification et de l'ordonnancement des tâches sous contraintes temporelles et incertitude. Les contraintes temporelles que nous traitons sont de deux types : qualitatives et quantitatives. L'incertitude sur la durée des tâches se traduit par une distribution de probabilités sur un ensemble fini.<br />Les tâches et les contraintes sont représentées à l'aide d'un graphe ET/OU et les durées des tâches sont pondérées par des probabilités d'exécution. Celles-ci expriment une incertitude sur la connaissance exacte des durées d'exécution des tâches qui ne seront réellement connues que lors de l'exécution effective. Ainsi, une tâche s'exécute durant l'une de ses durées d'exécution possibles avec la probabilité associée à celle-ci. Étant donné ce graphe, notre objectif est de déterminer un plan de tâches qui satisfait toutes les contraintes et qui répond aux critères de choix exigés par l'utilisateur en terme de temps, de coût et de probabilité. L'application de ce plan doit garantir le monde de façon que le but soit atteint tout en satisfaisant les contraintes du domaine.<br />Nous avons appliqué notre méthode de planification à un cas pratique relativement complexe qui concerne la planification d'un ensemble d'agents travaillant ensemble dans un lieu afin d'atteindre un but donné tout en respectant les délais et les contraintes du domaine (temps, coût, probabilité, disponibilité, spécialité,...).