.

La recherche d'ARN non-codants (ARNnc) a reçu un regain d'intérêt suite à la découverte de nouveaux types d'ARNnc aux fonctions multiples. De nombreuses techniques ont été développées pour localiser ces ARN dans des séquences génomiques. Nous utilisons ici une approche supposant la connaissance d'un ensemble d'éléments de structure discriminant une famille d'ARNnc appelé signature.<br /><br />Dans cette approche, nous combinons plusieurs techniques de \textit{pattern-matching} avec le formalisme des réseaux de contraintes pondérées afin de modéliser simplement le problème, de décrire finement les signatures et d'attribuer un coût à chaque solution. Nos travaux nous ont conduit à élaborer plusieurs techniques de filtrage ainsi que des algorithmes de pattern-matching originaux que nous présentons ici.<br /><br />Nous avons de plus conçu un logiciel, appelé DARN!, qui implante notre approche, ainsi qu'un module de génération de signatures. Ceux-ci permettent de rechercher efficacement de nouveaux ARNnc.

L’intelligence artificielle est un domaine de l’informatique étudiant la conception d’agents intelligents. Un agent est une entité acquérant de l’information sur son environnement par ses capteurs et agissant sur son environnement à travers ses actionneurs. Certains agents existent seulement dans le domaine logiciel, comme par exemple un agent intelligent pour un jeu vidéo, alors que d’autres existent dans le monde physique, tels les robots mobiles. Les domaines des jeux vidéo et de la robotique partagent certaines caractéristiques, dont la nécessité de prendre des décisions en temps réel dans un environnement dynamique ainsi qu’une vue incomplète sur cet environnement. Ce mémoire est divisé en deux chapitres. Le premier chapitre traite d’une approche de planification de trajectoires exploitant la géométrie d’une classe particulière de robots omnidirectionnels non-holonomes afin de calculer des chemins adéquats leur permettant d’atteindre une destination désirée. Les résultats obtenus avec cette approche tendent à démontrer qu’elle est plus efficace que les algorithmes traditionnels de planification de trajectoires grâce à l’information additionnelle prise en compte lors du calcul. Le second chapitre décrit l’architecture décisionnelle de l’agent intelligent SPAR qui est en mesure de jouer de façon autonome des parties de StarCraft : Brood War, un jeu de stratégie en temps réel. L’architecture de SPAR inclut entre autres des algorithmes de planification de trajectoires similaires à ceux du premier chapitre. Elle permet de faire face plus facilement et de façon plus rigoureuse, en comparaison avec les architectures existantes, aux nombreuses difficultés propres à ce type de jeu. Ces difficultés incluent un degré élevé de concurrence dans les actions et une multitude d’unités à contrôler dans un contexte temps réel. L’agent SPAR a participé aux volets 2011 et 2012 de la compétition AIIDE de StarCraft et à l’édition 2012 de la compétition SSCAI où il a obtenu à chaque fois des résultats honorables.

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.

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

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

Nous nous intéressons dans cette thèse à la planification pour les problèmes de prise de décision décentralisée séquentielle dans l'incertain. Dans le cadre centralisé, l'utilisation des formalismes MDP et POMDP a permis d'élaborer des techniques de planification efficaces. Le cadre Dec-POMDP permet de formaliser les problèmes décentralisés. Ce type de problèmes appartient à une autre classe de complexité que les problèmes centralisés. Pour cette raison, jusqu'à récemment, seuls de très petits problèmes pouvaient être résolus et uniquement pour des horizons très faibles. Des algorithmes heuristiques ont récemment été proposés pour traiter des problèmes de taille plus conséquente mais n'ont pas de preuve théorique de qualité de solution. Nous montrons comment une information heuristique sur le problème à résoudre représentée par une distribution de probabilité sur les croyances centralisées permet de guider la recherche approchée de politique. Cette information heuristique permet de formuler chaque étape de la planification comme un problème d'optimisation combinatoire. Cette formulation conduit à des politiques de meilleure qualité que les approches existantes. / In this thesis, we focus on planning in decentralised sequentialdecision taking in uncertainty. In the centralised case, the MDP andPOMDP frameworks leads to efficient planning algorithms. The Dec-POMDPframework is used to model decentralised problems. This kind ofproblems is in a higher class of complexity than the centralisedproblem. For this reason, until recently, only very small problem could be solved and only for very small horizons. Recently, some heuristic algorithms have been proposed to handle problem of higher size but there is no theoretic proof of the solution quality. In this thesis, we show how to use a heuristic information in the problem, modelled as a probability distribution on the centralised beliefs, to guide the search for a good approximate policy. Using this heuristic information, we formulate each time step of the planning procedure as a combinatorial optimisation problem. This formulation leads to policies of better quality than previously existing approaches.

La problématique d'interrogation d'une base de données en présence d'une ontologie (OBQA pour "Ontology-based Query Answering") consiste à prendre en compte des connaissances générales, typiquement une ontologie de domaine, lors de l'évaluation d'une requête. Dans le cadre de cette thèse, ces connaissances sont représentées par des formules de la logique du premier ordre appelées "règles existentielles". Les règles existentielles sont aussi connues sous le nom de règles Datalog+/- ou "tuple-generating dependencies". Nous considérons une approche couramment utilisée, qui consiste à réécrire la requête en exploitant les règles de façon à se ramener à un problème classique l'interrogation d'une base de données. Nous définissons un cadre théorique d'étude des algorithmes de réécriture d'une requête conjonctive en une union de requêtes conjonctives, accompagné d'un algorithme de réécriture générique, prenant en paramètre un opérateur de réécriture. Nous proposons ensuite plusieurs opérateurs de réécriture et développons différentes optimisations, que nous évaluons sur des benchmarks du domaine. / The issue of querying a knowledge base, also called Ontology-based Query Answering (OBQA), consists of taking into account general knowledge, typically a domain ontology, when evaluating queries. In this thesis, ontological knowledge is represented by first-order logical formulas, called existential rules. Existential rules are also known as Datalog+/- and tuple-generating dependencies. We adopt a well-known approach, which consists of rewriting the query with the rules to reduce the problem to a classical database query answering problem. We define a theoretical framework to study algorithms that rewrite a conjunctive query into a union of conjunctive queries, as well as a generic rewriting algorithm that takes into account a rewriting operator. Then, we propose several rewriting operators and develop several optimisations, which we evaluate on benchmarks of the domain.

Des catastrophes comme celles de Ghislenghien (Belgique), Ludwigshafen (Allemagne), ou Lyon (France), ont été attribuées à des travaux à proximité de réseaux de gaz. Bien que les canalisations soient une des méthodes les plus sures de transport pour les substances dangereuses, chaque année plusieurs cas d'accidents sont enregistrés en France. La plupart d'entre eux sont attribués à des travaux à proximité des réseaux et certains illustrent le manque de fiabilité des informations fournies. Pour prévenir de tels accidents qui impliquent les ouvriers et le public, les autorités françaises ont mis en place deux réglementations : DT-DICT : pour la sécurisation des réseaux à proximité d'excavation ; Multifluide : pour celle des réseaux dangereux lors d'événements aléatoires. Eviter de tels accidents nécessite d'acquérir et de contrôler des informations 3D concernant les différents réseaux urbains, et particulièrement ceux enterrés. Des stratégies de prévention doivent alors être adoptées. Voilà pourquoi travailler sur les réseaux et leur visualisation et la cartographie des risques, en prenant en compte le flou, est une recherche récente et importante. Les applications logicielles que je développe devraient aider les services publics et les entrepreneurs à se concentrer sur la prévention des événements dangereux grâce à des ensembles de données précises pour les utilisateurs, la définition d'un réseau de géomatique, mais aussi des méthodes telles que la triangulation, la modélisation par éléments, les calculs géométriques, l'intelligence artificielle, la réalité virtuelle. / Disasters like the ones that happened in Ghislenghien (Belgium), Ludwigshafen (Germany), or Lyon (France), have been attributed to excavations in the vicinity of gas pipelines. Though pipes are one of the safest methods of transportation for conveying hazardous substances, each year many cases of damage to gas pipes are recorded in France. Most of them are due to works in the vicinity of the networks and some illustrate the lack of reliability of the provided information. Concessionaries have to take stock of the situation and to suggest areas of improvement, so that everyone could benefit from networks becoming safer.To prevent such accidents which involve workers and the public, French authorities enforce two regulations: DT / DICT: reform of the network no-damage by securing the excavations, Multifluide: reform which is interested in securing networks of hazardous events.So, to avoid such accidents or other problems, it is necessary to acquire and control the 3D information concerning the different city networks, especially buried ones.Preventive strategies have to be adopted. That’s why working on the networks and their visualization and risk cartography, taking the blur into account, is a recent and appropriate research. The software applications I develop should help the utility and construction contractors and focus on the prevention of hazardous events thanks to accurate data sets for users and consumers, the definition of a geomatics network but also some methods such as triangulation methods, element modeling, geometrical calculations, Artificial Intelligence, Virtual Reality.

La régulation du trafic dans un carrefour à feux concerne en général deux objectifs distincts: la fluidification ou la résorption de congestion. Dans le premier cas, on évite de se retrouver dans une situation de trafic très dense en essayant d'ajuster les durées de commutations des feux en fonction de la demande d'affluence au carrefour: c'est une action a priori. Dans le second cas, on est confronté à un trafic saturé (état de congestion). Dans ce cas, il faudra agir a posteriori.Dans ce travail, nous nous intéressons essentiellement à un travail en amont (action a priori) permettant d'éviter la congestion en forçant les files d'attente à ne pas dépasser le niveau du trafic correspondant à l'optimum opérationnel des lignes. Plus précisément, après avoir modélisé le système, nous proposons une commande par retour d'état basée sur le concept d'invariance positive des ensembles et permettant d'atteindre l’objectif. Deux approches sont utilisées: La première fait appel aux inégalités matricielles Linéaires (LMI). La deuxième approche utilise le concept de la (A-B)-invariance issu de la généralisation du théorème de Farkas. Ensuite, nous enrichissons ces deux approches par la technique des réseaux de neurones pour estimer les flux d'entrée au carrefour afin de garantir la faisabilité en temps réel de la commande proposée. Enfin, les résultats de ces travaux sont appliqués sur un carrefour réel du boulevard Anatole France afin de montrer leur intérêt. / Traffic control in a signalized intersection relates generally two distinct objectives: the thinning or reduction of congestion. In the first case, we avoid ending up in a situation of heavy traffic trying to adjust the durations of switching lights depending on the demand for attendance at the crossroads: it is an action a priori. In the second case, one is faced with a saturated traffic (congestion state). In this case, it will act retrospectively. In this work, we focus mainly on upstream work (action a priori) to avoid congestion by forcing queues to not exceed the level of traffic corresponding to the optimum operational lines. Specifically, modeled after the system, we propose a state feedback control based on the concept of positive invariance of sets and to achieve the objective. Two approaches are used: The first uses the Linear matrix inequalities (LMI). The second approach uses the concept of (AB)-invariance from the generalization of the theorem of Farkas. Then, we enrich both approaches by the technique of neural networks to estimate the inflow at the crossroads to ensure real-time feasibility of the proposed control. Finally, the results of this work are applied to a real intersection of the boulevard Anatole France to show their interest.