Polyèdres et systèmes d'inéquations linéaires. Rappels sur la théorie du couplage u-graphes. Rang des couplages maximum dans un graphe biparti. Rang des couplages maximum dans un graphe quelconque.

La technologie facilite l'intégration de nombreux composants sur une puce pour atteindre les performances et les besoins exigés par les applications. La tendance est à l'augmentation de la complexité de tels systèmes, appelés systèmes monopuces. <br />Les systèmes monopuces sont sur un marché très concurrentiel, et l'arrivée rapide du produit sur le marché est très importante. De plus, le coût lié à la conception des parties matérielles et logicielles est très élevé. Détecter une erreur après fabrication entraîne un surcoût financier et de temps non acceptable. Ceci nous entraîne vers les deux problèmes traités dans ce travail de thèse : s'assurer que la système est correct avant sa fabrication et accélérer le processus de conception.<br />Après avoir évalué plusieurs techniques de vérification, nous pensons que le prototypage sur plateforme reconfigurable est une solution adaptée pour les problèmes mentionnés. Ce prototypage permet de vérifier rigoureusement les systèmes grâce à une vitesse élevée, et de tester le système dans son environnement d'utilisation. Il accélère aussi la conception en permettent le développement de certaines couches logicielles avant que le système soit fini.<br />Pour obtenir rapidement un prototype à partir d'une description RTL d'une application, nous proposons un flot de prototypage basé sur une plateforme reconfigurable. Ce flot est composé de quatre étapes : allocation, configuration de la plateforme, adaptation de l'application, et génération du code.<br />Dans l'allocation, les concepteurs associent chaque partie de l'architecture à un nœud de prototypage de la plateforme. Ces associations indiquent sur quelles parties de la plateforme reconfigurable sont réalisées les parties de l'architecture de l'application. La configuration est la réorganisation de la plateforme reconfigurable. L'adaptation consiste à modifier l'application pour satisfaire aux caractéristiques de la plateforme reconfigurable. Cette étape est effectuée si la plateforme ne peut pas être configurée pour s'adapter aux besoins de l'application. Enfin, la génération du code est un processus standard tel que la compilation et l'édition de lien des logiciels, la synthèse logique, le placement sur FPGA, et le routage.<br />Ce flot a été validé en réalisant le prototypage des applications VDSL et DivX. La plateforme utilisée est une plateforme ARM Integrator avec une carte mère, quatre modules processeurs ARM, et d'un module FPGA communiquant à travers un bus AMBA AHB. Une expérience de co-émulation a également été réalisée pour explorer les difficultés et les avantages de cette technique. L'avantage principal est qu'on peut profiter de l'observabilité de la simulation et de la vitesse de l'émulation. <br />Ce travail de thèse montre que l'on peut obtenir rapidement un prototype en utilisant le flot propose sur une plateforme reconfigurable et aussi faciliter le développement des parties logicielles pour accélérer la conception. La configurabilité de plateforme de prototypage et l'intégration du flot de prototypage sur un flot de conception des systèmes restent des problématiques à approfondir.

Les systèmes embarqués multiprocesseur monopuces (Multi-Processor System-on-Chip, MPSoC) visent l'intégration des sous-systèmes variés, matériels et logiciels, sur une seule puce. Ainsi, l'hétérogénéité et les contraintes imposées pour la mise sur le marché rendent l'analyse en vue de l'évaluation des performances et de l'optimisation de ces systèmes très complexes. L'évaluation des performances est une étape clef dans n'importe quel flot de conception. En se basant sur les résultats de l'évaluation des performances, il est possible de prendre des décisions et de réaliser des compromis pour l'optimisation du système global. La littérature prouve qu'une grande partie du temps de conception est passée dans l'évaluation des performances. De plus, les itérations dans le flot de conception deviennent prohibitives pour des systèmes complexes. Par conséquent, la réalisation des MPSoCs à rendement élevé est un défi. La solution est fortement liée à la disponibilité des méthodes rapides et précises pour l'évaluation des performances. Dans cette thèse, le terme « performances » est limité aux performances des temps d'exécution pour la réalisation finale du système. L'aspect temporel est intensivement analysé pour la validation des systèmes temps-réel et l'optimisation des sous-ensembles d'interconnexion. Nous avons également considéré la vitesse de la méthode proposée d'évaluation des performances, car les temps d'évaluation peuvent devenir prohibitifs pour des systèmes MPSoC complexes. Notre principale contribution est de définir une méthodologie globale d'évaluation des performances pour les systèmes MPSoC. Nous avons également orienté notre recherche vers les performances de l'exécution du logiciel. On a considéré l'évaluation des performances pour un modèle de haut niveau d'abstraction, afin d'avoir une vitesse élevée d'évaluation. De plus, on a inclus des annotations des temps d'exécution, afin d'avoir une bonne précision d'évaluation.

La prise de décision dans l'incertain et la coordination sont au coeur des systèmes multiagents. Dans ce type de systèmes, les agents doivent être en mesure de percevoir leur environnement et de prendre des décisions en considérant les autres agents. Lorsque l'environnement est partiellement observable, les agents doivent être en mesure de gérer cette incertitude pour prendre des décisions les plus éclairées possible en considérant les informations incomplètes qu'ils ont pu acquérir. Par ailleurs, dans le contexte d'environnements multiagents coopératifs, les agents doivent être en mesure de coordonner leurs actions de manière à pouvoir accomplir des tâches demandant la collaboration de plus d'un agent. Dans cette thèse, nous considérons des environnements multiagents coopératifs complexes (dynamiques, incertains et temps-réel). Pour ce type d'environnements, nous proposons une approche de prise de décision dans l'incertain permettant une coordination flexible entre les agents. Plus précisément, nous présentons un algorithme de résolution en ligne de processus de décision de Markov partiellement observables (POMDPs). Par ailleurs, dans de tels environnements, les tâches que doivent accomplir les agents peuvent devenir très complexes. Dans ce cadre, il peut devenir difficile pour les agents de déterminer le nombre de ressources nécessaires à l'accomplissement de chacune des tâches. Pour résoudre ce problème, nous proposons donc un algorithme d'apprentissage permettant d'apprendre le nombre de ressources nécessaires à l'accomplissement des tâches selon les caractéristiques de celles-ci. Dans un même ordre d'idée, nous proposons aussi une méthode d'ordonnancement permettant d'ordonner les différentes tâches des agents de manière à maximiser le nombre de tâches pouvant être accomplies dans un temps limité. Toutes ces approches ont pour but de permettre la coordination d'agents pour l'accomplissement efficace de tâches complexes dans un environnement multiagent partiellement observable, dynamique et incertain. Toutes ces approches ont démontré leur efficacité lors de tests effectués dans l'environnement de simulation de la RoboCup- Rescue.

Cette thèse introduit une méthodologie composée d'une démarche de modélisation et d'un support informatique pour la simulation distribuée et l'analyse de systèmes complexes à larges flux de données désagrégées. Le choix méthodologique proposé est influencé à la fois par le système à simuler et par l'architecture informatique servant de support de simulation dans le but de proposer une solution où l'aspect technique soit en accord avec l'aspect conceptuel. La démarche de modélisation intègre une description hiérarchique représentant l'organisation interne d'un système complexe, la construction d'un graphe logique traduisant une décomposition structurelle du système. Le graphe logique est ensuite utilisé pour réaliser une projection qui produit un graphe physique établissant une abstraction qui lie le niveau de représentation conceptuel et le système distribué sous-jacent. La plate-forme Atlas est un support de simulation distribuée à événements discrets dirigée par le temps et dont les propriétés dynamiques reproduisent le comportement de larges flux de données désagrégées. Une des particularités de cette plate-forme réside dans le concept de migration physique par groupe qui donne une solution adaptée pour réaliser et coordonner la migration de larges flux d'objets. Cette migration par groupe possède de nombreux avantages pour la simulation de systèmes sociétaux et urbains, notamment pour les systèmes en transport. L'utilisation de notre méthodologie et de sa plate-forme est illustrée par une application en transport qui modélise et simule les flux de personnes entre les différents halls d'un terminal d'aéroport.

L'analyse des flots de conception classiques montre que les causes d'un tel coût de développement peuvent être ramenées, en grande partie, à l'intégration tardive des parties logicielles et matérielles d'un système multiprocesseurs mono puces (MPSoC). Les travaux de cette thèse s'intéressent à ce problème d'intégration tardive en proposant un modèle unifié permettant la représentation conjointe à différent nivaux d'abstraction des architectures logicielles/matérielles. Ce modèle doit faciliter la conception graduelle de ces architectures tout en permettant la validation et l'évaluation, à chaque niveau d'abstraction, des performances qui en découlent. Les contributions apportées par cette thèse sont (1) la définition d'un modèle de représentation unifié et à différents niveaux d'abstraction des architectures logicielles/matérielles des systèmes MPSoC basé sur le concept d'interface abstraite logiciel/matériel, (2) la spécification d'une sémantique d'exécution de ce modèle dans le cadre d'un environnement de cosimulation globale basé sur SystemC et (3) la proposition d'une méthodologie de raffinement automatique de ces interfaces abstraites exploitant une technologie de composition à base de graphe de dépendance de services.

Ce travail élabore un modèle théorique de la communication qui peut s'établir en poésie électronique entre un auteur et un lecteur à travers un dispositif technique constitué de deux ordinateurs. Sur l'un l'œuvre a été conçue, sur l'autre elle est consultée. La transmission entre les deux s'effectue via un cédérom.<br />Une étude de l'évolution diachronique du champ est menée tout d'abord. Celle-ci montre que les conceptions évoluent peu à peu. L'analyse des formes visuelles amène l'idée que la représentation mentale que se font les acteurs du dispositif est un élément important de la communication.<br />Un modèle, dit du texte lié, est proposé pour décrire ce point. Il propose de relativiser la notion de texte à la représentation globale de la situation chez chaque acteur. Ce modèle est développé dans son approche cognitive et sémiotique. Les notions de texte-à-voir, texte-écrit et texte-lu sont introduites.<br />L'étude se poursuit par une analyse des variations de l'exécution d'un programme dans divers contextes. Elle oblige à aborder la communication comme la transformation d'un processus d'exécution en un autre. Cette conception, dite procédurale, se développe en une analyse systémique en trois modèles : un modèle psychologique intrapersonnel, un modèle fonctionnel de la situation de communication et un modèle global décrivant les contextes relationnels et temporels. Le modèle fonctionnel de la situation fait apparaître une fonction particulière entre la lecture et l'écriture, la génération, qui explique les spécificités du dispositif. Ces modèles permettent d'intégrer les caractéristiques observées dans un discours unifié qui autorise une articulation des diverses conceptions. Cette articulation est traitée à l'aide de transformations graphiques.

Cette Thèse combine des résultats récents et des algorithmes originaux pour créer deux applications temps-réel robustes d'aide à la conduite (projet aussi appelé "le véhicule intelligent"). Les applications - commande de croisière adaptative ("ACC") et prédiction d'impact piétons - sont conçues pour être installées sur un véhicule et détectent d'autres utilisateurs de la route, en utilisant une seule caméra frontale. La thèse commence par un état de l'art sur la vision artificielle. Elle s'ouvre en passant en revue certaines avancées récentes dans le domaine. En particulier, nous traitons l'utilisation récente d'un nouvel algorithme nommé AdaBoost pour la détection des objets visuels dans une image, rapidement et sûrement. Nous développons la théorie, ajoutons des algorithmes et des méthodes (y compris une variante à base d'algorithmes aux besoins de vraies applications d'aide à la conduite. En particulier, nous prouvons plusieurs nouveaux résultats sur le fonctionnement de l'algorithme AdaBoost. Toujours sur le plan théorique, nous traitons des algoritmes d'évaluation de mouvement et des filtres particulaires et leur utilisation dans la vision. De ces développements algoritmiques, nous arrivons à la description de deux applications d'aide à la conduite, toutes les deux entièrement mises en application, validées et démontrées sur le véhicule d'essai du Centre de Robotique de l'Ecole des Mines de Paris. La première application, la commande de croisière adaptative ("ACC"), exploite les formes caractéristiques des véhicules pour les détecter. Ainsi, l'application détecte des véhicules en utilisant un ensemble d'algorithmes classiques de traitement d'image (détection d'ombres, des feux arrières, de symétrie et de bords), ainsi que l'algorithme AdaBoost mentionné ci-dessus. Cet ensemble d'algorithmes est fusionné en se plaçant dans le cadre du filtrage particulaire, afin de détecter les véhicules devant notre voiture. Puis, le système de contrôle prend pour cible la voiture située devant et garde une distance constante par rapport à celle-ci, tout en commandant l'accélération et le freinage de notre voiture. La deuxième application, le prédiction d'impact piétons, estime au temps t la probabilité d'un impact de notre voiture avec un piéton au temps t+s. Dans l'application, la trajectoire de chaque piéton est calculée, et la probabilité d'impact est calculée selon la direction du piéton, du bruit et d'autres facteurs. Cette application utilise un accélérateur matériel spécifique crée dans le cadre du projet européen CAMELLIA (Core for Ambient and Intelligent Imaging Applications).

L'objectif de cette thèse est l'étude de la synthèse de plans dans un contexte multi-agent. La problèmatique principale est de comprendre les mécanismes qui permettent à une société d'agents autonomes de construire collectivement un plan global. Contrairement aux approches classiques dans lesquelles la planification n'est qu'un outil parmi d'autres pour définir les activités des agents et la coordination une «surcouche» nécessaire à leur synchronisation, la contribution de nos travaux repose sur la conception d'un modèle de planification entièrement distribué dans lequel les agents raisonnent conjointement sur leurs activités respectives pour atteindre un but commun prédéfini en intégrant leurs compétences hétérogènes ainsi que leurs croyances partielles sur le monde. Dans cette perspective, nous proposons de considérer la synthèse de plans comme un raisonnement collectif et révisable fondé sur l'échange entre les agents de conjectures, i.e., des plans qui peuvent être exécutés si certaines conditions sont vérifiées et de réfutations, i.e., des objections quant à la réalisation du plan. Les intéractions entre agents peuvent se définir comme un processus dialectique d'investigation dans lequel les agents proposent leurs compétences pour démonter la validité de certaines hypothèses, réfuter les conjectures non réalisables, réparer lorsque cela est possible les conjectures précédemment réfutées et ainsi élaborer pas à pas un plan solution.

Ce travail de thèse s'intègre dans le cadre du développement de nouvelles approches de conception afin de réduire significativement la consommation électrique des Systèmes sur Puce (SoC)ou des Objets Communicants utilisés pour traiter numériquement des signaux. Le but est alors d'obtenir des systèmes entièrement contrôlés par les événements contenus dans les signaux. Dans ce contexte, une nouvelle catégorie de chaîne de traitement est définie, associant une implémentation matérielle asynchrone (sans horloge globale) et un échantillonnage non uniforme dans le temps dit « par traversée de niveaux ». Un convertisseur Analogique/Numérique dédié à<br />cette tâche ayant déjà été réalisé, ce travail se focalise sur le traitement des données composées de couples amplitude-temps dont cette thèse montre que toute opération doit obligatoirement prendre en compte l'information temporelle. Des filtres numériques à réponse impulsionnelle finie (RIF) et infinie (RII) sont alors définis dans le cadre de signaux échantillonnés non uniformément. Des architectures sont proposées puis comparées à celles utilisées classiquement montrant que la complexité combinatoire était accrue. Un critère sur le choix de la technologie à privilégier, spécifiant la charge de calcul totale sur une durée finie, montre alors qu'en diminuant le nombre de points traités, l'approche asynchrone peut compenser le surcoût de complexité. Ainsi le traitement de signaux faiblement actifs par une chaîne asynchrone, combinant échantillonnage non uniforme et conception asynchrone, permet de réduire son activité moyenne et donc la consommation du circuit intégré, rendant cette technologie très attractive pour le domaine des SoC.