Inscrit dans le contexte de la robotique autonome, cette thèse se focalise sur l'étude de la <br />navigation intentionnelle, c'est à dire le pilotage d'un robot mobile de façon à atteindre un but <br />en tenant compte d'informations perceptives. <br />Pour atteindre cet objectif, nous allons nous poser trois questions fondamentales que nous <br />préciserons par la suite : <br />– Comment définir une tâche de navigation intentionnelle (TNI) ? <br />– Comment réaliser une TNI ? <br />– Comment implanter une TNI ? <br />Nos réponses à ces questions s'articulent en une arborescence de problématiques que nous <br />illustrons dans la figure 1.1. Nous allons maintenant détailler cette arborescence.

Le problème abordé dans ce document est celui de la "navigation autonome en environnement incertain et dynamique". L'objectif est de développer des modèles et<br />des techniques informatiques permettant à un robot terrestre de se déplacer de manière autonome, c'est-à-dire sans intervention humaine, dans un environnement mal maitrisé et en présence d'obstacles mobiles.

Baker [9] defines scheduling as the problem of allocating scarce resources to activities over time1. In<br />this manuscript, we consider several scheduling problems with a variety of different environments.<br />The two parts of this manuscript provide an overview of two of our major research interests. The first<br />part (Chapters 2 to 5) is dedicated to polynomial time solutions of equal{processing{time scheduling<br />problems. The second one (Chapters 7 to 15) deals with the application of Constraint Programming<br />to scheduling. These two parts re<br />ect the balance we have tried to keep between theoretical and<br />more applied research.<br />Although all the topics covered in this manuscript are related to scheduling, Parts 1 and 2 are<br />dedicated to very different aspects of scheduling. Some few results discussed in Part 1 are occasionally<br />used in Part 2 but they are independent one from another. In the following, we brie<br />y review the<br />content Parts 1 and 2. More detailed introductions are provided in Sections 1 and 7 respectively.

.

.

In this thesis we summarize our recent work on the control of timed systems.

Dans le domaine du test de circuits complexes, a la fin des annees 70 apparait le concept de test fonctionnel : batir un test a partir seulement des fonctions realisees par le circuit en s'affranchissent completement de sa structure. La formidable evolution des microprocesseurs a mis ceux-ci au centre du debat suivant : comment realiser un test fonctionnel de tels circuits ? Bien que de nombreuses methodes de test fonctionnel de microprocesseurs aient ete proposees, un aspect important semble avoir ete neglige : la mesure de l'efficacite de ces methodes. Les rares tentatives effectuees dans ce domaine se sont basees sur un principe d'injection de fautes de collage dans des modeles de simulation du circuit a tester. Dans cette these l'efficacite du test fonctionnel est etudiee par une methode basee sur l'injection de defauts a lÕaide dÕequipements laser dans des circuits reputes bons. Le but est de constituer un echantillon realiste de circuits defectueux, possedant chacun un defaut plausible a un emplacement aleatoire. Diverses experiences realisees sur des microprocesseurs 8-bits et 16-bits du commerce (Motorola 6800 et 68000) sont presentees et permettent de tirer des conclusions sur la methode d'injection de defauts et sur l'efficacite du test fonctionnel par rapport a celle du test structurel du fabricant. Ceci aboutit a l'identification de ce qui est le role veritable du test fonctionnel pour les circuits complexes : l'aide a la validation de conception et au diagnostic.

De nombreux travaux portent sur les réseaux de neurones artificiels appliqués à des systèmes fortement contraints (systèmes ambulatoires, systèmes autonomes, systèmes adaptatifs, etc), pour lesquels le caractère élémentaire et massivement distribué des calculs neuronaux s'avère un atout. De façon plus large, ce caractère définit la nature même des calculs connexionnistes : une puissance de calcul et une robustesse fondées sur un parallélisme massif à grain très fin où les unités de calcul s'insèrent dans un flux d'informations très dense. Il est donc indispensable de pouvoir pleinement exploiter ce parallélisme connexionniste, à la fois en termes de potentiel de calcul et en termes de perspectives d'implantations embarquées efficaces. Une partie de ces travaux s'attache à définir différentes approches d'implantation massivement parallèle de réseaux neuronaux. Une approche globale de la pratique de calcul connexionniste ne peut pas faire l'économie d'une réflexion sur les fondements de la conception des architectures connexionnistes susceptibles de résoudre un problème donné. L'essentiel des travaux sur les réseaux de neurones s'est concentré sur la définition de familles de modèles neuronaux dont l'apprentissage permet de traiter des tâches telles que classification, régression, discrimination, auto-régression, etc. Ces modèles restent d'actualité, ne serait-ce que par la variété des applications dans lesquelles ils jouent encore un rôle central, et les travaux rapportés dans ce manuscrit portent en partie sur ces modèles. Néanmoins, ils n'apparaissent le plus souvent que comme des outils de traitement statistique de données, au même titre que de nombreux autres modèles. Ils se heurtent ainsi à une barrière de complexité dans les problèmes qu'ils sont susceptibles de résoudre. Franchir "à l'aveuglette" cette barrière, c'est à dire proposer ex nihilo des architectures connexionnistes capables de réaliser des tâches cognitives complexes, ne semble pas raisonnable. De nombreux chercheurs suggèrent alors de prendre appui sur des exemples naturels de systèmes distribués capables de réaliser ces tâches. Les neurosciences sont une orientation possible. C'est cette inspiration sur la base des mécanismes observés dans le cerveau qui est proposée dans une partie des travaux rapportés dans ce manuscrit. L'objet de ces travaux n'est pas de faire le tour de l'apport possible des neurosciences pour la conception des modèles connexionnistes, mais de montrer que même dans le cas de modèles d'inspiration corticale, la défense du parallélisme connexionniste passe par une étude focalisée sur les mécanismes locaux de gestion du flux d'informations sous-jacent à ces modèles.

.

A cause de la complexité croissante des systèmes sur puce (SoC), la vérification devient un aspect très important : 70 - 80% du coût de conception est alloué à cette tâche. Plus de 60% des projets de développement d'ASIC doivent être repris à cause des erreurs fonctionnelles, environ 50% des erreurs de conception étant situées au niveau du module. Dans le monde industriel, la vérification est souvent synonyme de simulation - une méthode de vérification naturelle pour les concepteurs, mais qui ne garantit pas l'absence d'erreurs. Une alternative est fournie par la vérification formelle qui prouve mathématiquement qu'un circuit satisfait une spécification. Dans cette thèse, on s'intéresse aux méthodes déductives basées sur la démonstration de théorèmes. La démonstration de théorèmes permet de vérifier formellement des descriptions matérielles de haut niveau et des systèmes réguliers ou très complexes, car la taille de données n'a plus d'importance. Par contre la modélisation de la description matérielle se fait directement en logique, ce qui rend l'accès difficile pour les concepteurs. Notre travail a pour but de faciliter l'introduction des outils de démonstration de théorèmes dans le flot de conception. Nous proposons une méthode automatique de traduction d'un circuit VHDL vers un modèle sémantique basé sur des équations récurrentes par rapport au temps qui peut être l'entrée de tout outil de démonstration de théorèmes et nous définissons une approche de vérification adaptée au modèle. Afin de valider notre proposition, nous avons choisi le démonstrateur ACL2 pour vérifier une bibliothèque de circuits de cryptographie.