Cette habilitation décrit mes travaux en tomographie discrète, calcul quantique et ordonnancement.

L'objet de ces travaux de thèse est d'étudier la spécification et la synthèse de systèmes de contrôle, qui peuvent être composés à la fois de logiciel et de matériel, sur des architectures multiprocesseurs (ASIC, FPGA, et logiciel). Ce sujet de recherche fait partie à la fois de la synthèse de systèmes VLSI et de la conception mixte logicielle/matérielle. Afin d'atteindre ces objectifs, une méthodologie qui permet de concevoir conjointement le logiciel et le matériel a été développée. L'originalité de ce travail vient du fait que les spécifications à traiter sont décrites à un très haut niveau d'abstraction, appelé “niveau système”, avec le langage SDL. Ceci permet de concevoir des applications de plus en plus complexes. Ces travaux traitent principalement le problème du découpage de systèmes de contrôle en sous-systèmes de granularité plus fine et donc plus facilement synthétisables. L'approche de découpage qui a été développée se base sur une boîte à outils qui offre au concepteur le moyen de transformer, raffiner, découper un système puis d'affecter chaque sous-système à une technologie particulière en logiciel (C) ou en matériel (VHDL). La méthode de découpage suivie est interactive et utilise une forme intermédiaire basée sur un modèle de machines à états finis étendues communicantes via des canaux abstraits. Une autre tâche tout aussi importante dans cette méthodologie de raffinement est de synthétiser la communication entre les différentes partitions résultat d'un découpage. Cela se traduit par une étape d'allocation de protocoles de communication et une étape de synthèse d'interfaces entre les sous-systèmes communicants. La première étape consiste à sélectionner dans une bibliothèque les modèles de communication nécessaires entre les sous-systèmes. La deuxième étape consiste à adapter ou générer les interfaces des différents sous-systèmes.

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 aborde le problème du calcul et de la représentation de la visibilité mutuelle de polygones. Elle montre tout le potentiel et l'intérêt de cette information pour la résolution de problèmes difficiles en synthèse d'images et en propagation électromagnétique. <br />Nous proposons un nouvel algorithme pour calculer la visibilité dans l'espace de Plücker, afin de minimiser les coûts en temps et mémoire vis-à-vis des précédentes approches.<br />En synthèse d'images, nous utilisons l'information ainsi calculée pourproposer une nouvelle solution au calcul analytique des ombres douces en illumination directe. Cette solution concilie la qualité et la rapidité du rendu.<br />En propagation électromagnétique, nous proposons l'optimisation sans perte d'un modèle basé rayons. Celle-ci permet d'effectuer des simulations dont la précision est optimale tout en s'appliquant à des environnements de tailles significatives.

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.

Le regroupement d'objets, dans un cadre non-supervisé, est une tâche importante et difficile en apprentissage. Ce processus intervient dans des contextes variés tels que la découverte de connaissances, la simplification dans le représentation ou la description d'un ensemble de données.<br /><br />Nous proposons, dans cette étude, l'algorithme de clustering PoBOC permettant de structurer un ensemble d'objets en classes non-disjointes. Nous utilisons cette méthode de clustering comme outil de traitement dans deux applications très différentes.<br /><br />- En apprentissage supervisé, l'organisation préalable des instances apporte une connaissance utile pour la tâche d'induction de règles propositionnelles et logiques.<br /><br />- En Recherche d'Information, les ambiguïtés et subtilités de la langue naturelle induisent naturellement des recouvrements entre thématiques.<br /><br />Dans ces deux domaines de recherche, l'intérêt d'organiser les objets en classes non-disjointes est confirmé par les études expérimentales adaptées.

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.

Les systèmes sur puces sont un ensemble de composants hétérogènes. La conception des ces systèmes peut être vue sous deux aspects : la conception des composants et leurs intégration dans le même système. La conception des composants nécessiterait des compétences de différentes équipes de développement selon les besoins, les compétences et, les fonctionnalités, etc. L'intégration de ces composants requerrait alors (1) des connaissances multidisciplinaires des différents concepts utilisés par les composants, (2) des modèles globaux du système pour la description des composants et de leurs interactions et (3) un modèle de validation tout au long du flot de conception par assemblage de composants. Toutefois, la diversité des descriptions et de modélisations des différents composants rendent l'intégration un processus très complexe et laborieux.<br /> L'objectif de cette thèse est de généraliser le concept de modélisation et de validation globale des systèmes embarqués sur puce afin de faciliter le processus d'intégration et d'assemblage de composant de système sur puce. Cette généralisation concerne (1) les concepts communs pour la modélisation des systèmes hétérogènes avant la synthèse de leurs circuits notamment pour la simulation, l'exécution, etc. et (2) la définition d'un modèle de d'exécution global pour la validation des systèmes hétérogènes par composition d'autres modèles. Les concepts proposés dans cette thèse sont validés à travers trois applications complexes : un centre d'informations automobile, un modem d'une chaîne audio 802.16 et un système de radio définie par logiciel.

Les automates cellulaires fournissent un cadre agréable et uniforme pour aborder une des problématiques majeures de l'étude des «systèmes complexes» : comprendre comment et pourquoi des systèmes qui possèdent un comportement microscopique -- local -- facile à décrire peuvent avoir un comportement macroscopique -- global -- beaucoup plus compliqué. Depuis leur introduction dans les années 40, de nombreux travaux ont été entrepris afin de comprendre les liens existant entres les propriétés locales et globales des automates cellulaires.<br /><br />Ces vingt dernières années est apparue une nouvelle approche à travers la recherche de classifications pertinentes des automates cellulaires. Ainsi, de nombreuses classifications formelles ont été proposées pour mieux cerner les comportements de type «chaotique», principalement à l'aide d'outils de nature topologique. Cependant, une autre forme d'automates cellulaires complexes -- les automates cellulaires pour lesquels semblent émerger des structures locales, des particules, qui interagissent selon des schémas complexes -- reste peu étudiée. A notre connaissance, seuls les travaux d'I. Rapaport proposent une classification -- le groupage -- de nature algébrique, inspirée par cette forme de complexité. Nos travaux consistent en la généralisation de cette classification, afin d'une part de prendre en compte certaines notions intéressante comme l'universalité intrinsèque et d'autre part de renforcer la structure algébrique qui fait la force de cet outil -- tout en conservant sa nature géométrique.<br /><br />Dans une première partie, la structure interne des automates cellulaires est étudiée et une nouvelle caractérisation des automates cellulaires de dimension donnée est proposée, mettant en avant la notion de sous-automate. Dans une deuxième partie, les transformations «géométriques» des automates cellulaires sont caractérisées et un modèle de groupage abstrait est défini. Fort de ces deux outils et de la notion de sous-automate, une première extension du groupage est définie. La pertinence de cette classification est illustrée par l'étude de familles classiques d'automates cellulaires dans ce cadre. L'absence de structure de treillis en sus de la structure de pré-ordre amène l'introduction d'une nouvelle généralisation qui induit une structure de demi-treillis par l'opération de produit cartésien. Des liens entre les idéaux de cette structure et des problèmes de décision sont mis en avant. L'objet de la troisième partie est la notion d'automate cellulaire intrinsèquement universel, qui joue un rôle privilégié dans le cadre du groupage généralisé. L'indécidabilité de l'appartenance à cette famille d'automates cellulaires est établie et deux exemples de petits automates cellulaires de dimension 1 intrinsèquement universels sont construits, dont un automate cellulaire à 6 états et voisinage de von Neumann, le plus petit connu à ce jour.

Dans le cadre de l'étude des ensembles de pavages, nous nous sommes concentrés sur le cas des pavages de zonotopes (figures d'un espace formées de toutes les combinaisons linéaires d'un ensemble de vecteurs donnés). Après avoir défini un graphe dual d'un pavage de zonotope planaire (par l'utilisation de la relation d'adjacence liant les tuiles), nous avons montré la relation biunivoque qui lie les deux classes d'objets. Nous avons alors étudié comment l'opération de flip (qui est un réarrangement local de tuiles) peut s'exprimer sur le dual, permettant par la suite de construire l'ensemble des pavages du zonotope associé. Cette méthode ne pouvant que très difficilement s'adapter aux cas de dimensions supérieures (zonotopes non planaires), nous avons alors mis au point une méthode de décomposition permettant d'étudier un pavage en nous focalisant sur les propriétés de pavages plus petits. Ce type de méthode nous a permis de démontrer des résultats forts de reconstruction et de structure dans le cas de pavages de dimension 2. De plus, ceci nous a permis de démontrer des résultats de connexité dans certains cas particuliers de dimensions supérieures. Le choix des pavages de zonotopes étend naturellement certains pavages étudiés classiquement (tels que les pavages de dominos sur une grille carrée ou de losanges sur une grille triangulaire). En effet, ils ne peuvent être définis sur une grille, et sont définis en toute dimension.