Déterminer si un problème de satisfaction de contraintes (CSP) a une solution ou non est NP-complet. Les CSP sont résolus par inférence (c’est-à-dire, en appliquant un algorithme de cohérence), par énumération (c’est-à-dire en effectuant une recherche avec retour sur trace ou backtracking), ou, plus souvent, en intercalant les deux mécanismes. La propriété de cohérence la plus courante appliquée en cours du backtracking est la GAC (Generalized Arc Consistency). Au cours des dernières années, de nouveaux algorithmes pour appliquer des cohérences plus fortes que le GAC ont été proposés et montrés comme étant nécessaires pour résoudre les problèmes difficiles.Nous nous attaquons à la question de balancer d’une part le coût et, d’autre part, le pouvoir d’élagage des algorithmes de cohérence et posons cette question comme étant celle de déterminer où, quand et combien une cohérence doit-elle être appliquée en cours de backtracking. Pour répondre à la question « où », nous exploitons la structure topologique d'une instance du problème et focalisons la cohérence forte là où des structures cycliques apparaissent. Pour répondre à la question « quand », nous proposons une stratégie simple, réactive et efficace qui surveille la performance du backtracking puis déclenche une cohérence forte lorsque l’effort du retour sur trace devient alarmant. Enfin, pour la question du « combien », nous surveillons les mises à jour provoquées par la propagation des contraintes et interrompons le processus dès qu’il devient inactif ou coûteux même avant qu’il n’atteigne un point fixe. Les évaluations empiriques sur des problèmes de référence établissent l’efficacité de nos stratégies. / Determining whether or not a Constraint Satisfaction Problem (CSP) has a solution is NP-complete. CSPs are solved by inference (i.e., enforcing consistency), conditioning (i.e., doing search), or, more commonly, by interleaving the two mechanisms. The most common consistency property enforced during search is Generalized Arc Consistency (GAC). In recent years, new algorithms that enforceconsistency properties stronger than GAC have been proposed and shown to be necessary to solve difficult problem instances.We frame the question of balancing the cost and the pruning effectiveness of consistency algorithms as the question of determining where, when, and how much of a higher-level consistency to enforce during search. To answer the ‘where’ question, we exploit the topological structure of a problem instance and target high-level consistency where cycle structures appear. To answer the ‘when’ question, we propose a simple, reactive, and effective strategy that monitors the performance of backtrack search and triggers a higher-level consistency as search thrashes. Lastly, for the question of ‘how much,’ we monitor the amount of updates caused by propagation and interrupt the process before it reaches a fixpoint. Empirical evaluations on benchmark problems demonstrate the effectiveness of our strategies.

Les problèmes d'ordonnancement à contraintes de ressource ont été largement étudiés dans la littérature. Cependant, dans la plupart des cas, il est supposé que les activités ont une durée fixe et nécessitent une quantité constante de la ressource durant toute leur exécution. Dans cette thèse, nous nous proposons de traiter un problème d'ordonnancement dans lequel les tâches ont une durée et un profil de consommation de ressource variables. Ce profil, qui peut varier en fonction du temps, est une variable de décision du problème dont dépend la durée de la tâche associée. Par ailleurs, la considération de fonctions de rendement linéaires et non linéaires pour la représentation de l'utilisa- tion des ressources complexifie le problème et permet de modéliser de manière réaliste les transferts de ressources énergétiques. Pour ce problème NP-complet, nous présentons plusieurs propriétés per- mettant de dériver des modèles et méthodes de résolution. Ces méthodes de résolution sont divisées en deux parties. La première partie visualise ce problème du point de vue de la Programmation Par Contraintes et plusieurs méthodes dérivées de ce paradigme sont détaillées dont le développement du raisonnement énergétique sur le problème étudié. La seconde partie de la thèse est dédiée à des approches de Programmation Linéaire Mixte et plusieurs modèles, notamment un modèle à temps continu basé sur les événements, ainsi que des analyses théoriques et des techniques d'amélioration de ces modèles sont présentés. Enfin, des expérimentations viennent appuyer les résultats présentés dans ce manuscrit. / Resource-constrained scheduling problems have been widely studied in the literature. However, in most cases, it is assumed that the activities have a fixed duration and require a constant amount of the resource throughout their execution. In this thesis, we propose to treat a scheduling problem in wich tasks have a variable duration and a variable resource consumption profile. This profile, which may vary over time, is a decision variable of the problem on wich depends the ruration of the associated task. Furthermore, we consider linear and nonlinear efficiency functions to represent resource usage, which makes more complex the problem and permits the modeling of energy transfers. For this NP-complete problem, we present several properties allowing us to derive models and solution methods. These solution methods are divided into two parts. The first part studies the problem from the perspective of Constraint Programmming and several methods derived from this paradigm are detailed, among which new developments on energetic reasoning for the considered problem. The second part of the thesis, dedicated to Mixed Integer Linear Programming approches, presents several models, including a novel continuous time model based on events as well theoretical analysis of the models and improvement of theses techniques. Finally, experiments show the relative effectiveness of the results presented in this thesis.

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

Le cerveau présente une structure complexe. La segmentation et la reconnaissance automatique de ses sous-structures dans des IRM cérébrales est délicate et nécessite donc l'utilisation d'un modèle de l'anatomie. L'utilisation d'atlas iconiques est efficace pour traiter les données de sujets sains mais son adaptation au traitement de cas pathologiques reste problématique. Dans cette thèse nous utilisons un modèle symbolique de l'anatomie proche des descriptions linguistiques qui comprend les principales structures cérébrales. L'agencement spatial de ces structures y est représenté sous forme de relations spatiales et leur apparence est caractérisée par des relations sur leur contraste. Réaliser la reconnaissance grâce à ce modèle structurel consiste à obtenir pour chaque structure une région de l'image vérifiant les relations et caractéristiques portées par le modèle. Nous formulons ce problème comme un réseau de contraintes dont les variables sont les régions recherchées représentées sous forme d'ensembles flous. Les contraintes sont déduites du modèle en tirant parti de modélisations floues. Une contribution nouvelle porte sur la contrainte de connexité et la proposition de définitions et algorithmes adaptés au cas flou présentant de bonnes propriétés. Nous mettons alors en œuvre un algorithme de propagation de contraintes qui itérativement réduit l'espace de solutions. Enfin nous obtenons un résultat pour certaines structures d'intérêt par l'extraction d'une surface minimale relativement aux résultats de l'algorithme de propagation. Nous appliquons cette approche aux structures internes du cerveau chez des sujets sains. Finalement nous étendons ce processus au traitement de données de patients présentant une tumeur. Le modèle générique ne correspondant plus aux données à reconnaître, nous proposons un algorithme de propagation recherchant à la fois le modèle spécifique au patient et les structures anatomiques.

L'hybridation des mécanismes de méthodes incomplètes et des techniques de programmation par contraintes est souvent basée sur des combinaisons de type maître-esclave, dédiées à la résolution de classes de problèmes spécifiques. Dans cette thèse, nous nous intéressons à la définition d'un modèle théorique uniforme, basé sur les itérations chaotiques de K.R. Apt qui définissent un cadre mathématique pour l'itération d'un ensemble fini de fonctions sur des domaines abstraits munis d'un ordre partiel. Ce cadre permet<br />de prendre en compte une hybridation entre les méthodes incomplètes et les méthodes complètes. Dans ce contexte, la résolution s'apparente à un calcul de point fixe d'un ensemble de fonctions de réductions spécifiques. Notre cadre générique permet alors d'envisager des stratégies de combinaisons et d'hybridation de manière plus fine et d'étudier leurs propriétés. Nous avons employé un cadre général approprié pour modéliser la résolution des problèmes d'optimisation et nous présentons des résultats<br />expérimentaux qui mettent en avant les atouts de telles<br />combinaisons en regard d'une utilisation indépendante des techniques de résolution.

Ce travail propose une méthode d'aide à la coopération inter-entreprises dans un contexte de production à la commande. L'objectif est de tendre les flux de production inter-entreprises grâce à une coopération entre les décideurs de chaque entreprise. L'approche retenue assimile le problème d'organisation globale à un processus de décision distribuée dans lequel l'organisation est progressivement construite par un ensemble de coopérations entre des couples d'acteurs du réseau d'entreprises. Nous étudions en particulier les couples d'entreprises client-fournisseur pour lesquels la coopération concerne les attributs des commandes passées entre eux. Nos objectifs sont de fournir aux décideurs un cadre plus formel qui contractualise la coopération et des outils d'aide à la décision pour la coopération permettant de les assister dans les diverses phases du processus.

Les travaux présentés dans ce document traitent de méthodes arborescentes pour la résolution de problèmes combinatoires d'optimisation ou de décision. Le premier chapitre présente les contributions que nous avons apportées pour les méthodes de résolution dites " à divergences ". Ces contributions concernent les modes de comptage des divergences pour les problèmes à variables discrètes, le développement d'une heuristique dynamique à pondération de variables, ainsi que, dans un contexte d'optimisation, l'utilisation de bornes ou d'heuristiques pour la sélection des points de divergences. Ces différentes contributions sont illustrées sur des problèmes d'ordonnancement ou sur des problèmes de satisfaction de contraintes. Le deuxième chapitre traite de propagation de contraintes pour la résolution de problèmes d'ordonnancement disjonctifs en présence de contraintes temporelles généralisées. Des extensions de méthodes de propagation de contraintes efficaces dans ce contexte sont proposées et des applications à la résolution de différents problèmes d'ordonnancement sont également présentées. Le troisième chapitre s'intéresse à un problème de calcul d'itinéraires point à point sur des réseaux de transport multi-modaux. La prise en compte de la multi-modalité fait surgir à la fois de nouvelles contraintes permettant d'exprimer si la séquence de modes d'un itinéraire conduit ou non à une solution admissible, mais aussi de nouveaux objectifs comme la minimisation du nombre de changement de modes. Le problème étudié (minimisation du temps de trajet et du nombre de transferts) est polynomial et différentes variantes basées sur le principe de l'algorithme de Dijkstra sont présentées et évaluées sur un cas réel.

Dans cette thèse nous montrons que le raisonnement symbolique associé à la vérification de la consistance d'arc avec propagation de contraintes est un outil efficace pour interpréter les images. Nous montrons dans un premier temps que ce cadre théorique permet de vérifier l'organisation spatiale de différentes composantes d'un objet complexe dans une image. Nous proposons ensuite d'étendre l'utilisation de celui-ci à la reconnaissance sélective des formes décrites par des équations mathématiques, grâce à la notion de consistance d'hyper-arc à deux niveaux de contraintes. La pertinence et la faisabilité de cette approche ont été validées par de multiples tests. En outre, les résultats obtenus sur des images sur-segmentées montrent que la méthode proposée est résistante au bruit, même dans des conditions où les humains (dans certains cas d'agnosie visuelle) peuvent échouer. Ces résultats soutiennent l'intérêt du raisonnement symbolique dans la compréhension de l'image. / In this thesis we show that symbolic reasoning associated with arc consistency checking is an efficient tool for images interpretation. We first show that this theoretical framework makes it possible to verify the spatial organization of different components of a complex object in an image. We then propose to extend the use of this framework to the selective recognition of shapes described by mathematical equations, thanks to the notion of hyper-arc consistency with bi-levels constraint. The relevance and feasibility of this approach have been validated by multiple tests. In addition, the results obtained on over-segmented images show that the proposed method is noise-resistant, even under conditions where humans (in some cases visual agnosia) may fail. These results support the interest of symbolic reasoning in image understanding.

Présentation de concepts issus de la cotation volumique qui répondent aux besoins d'un système CFAO integré allant de la conception à la fabrication. Validation de ces concepts et des méthodes par implantation d'un logiciel de conception automatique de gammes d'usinage appelé Gagmat

Avec le développement rapide et les applications étendues de la technologie de robot, la recherche sur le robot mobile intelligent a été programmée dans le plan de développement de haute technologie dans beaucoup de pays. La navigation autonome joue un rôle de plus en plus important dans le domaine de recherche du robot mobile intelligent. La localisation et la construction de cartes sont les principaux problèmes à résoudre par le robot pour réaliser une navigation autonome. Les techniques probabilistes (telles que le filtre étendu de Kalman et le filtre de particules) ont longtemps été utilisées pour résoudre le problème de localisation et de cartographie robotisées. Malgré leurs bonnes performances dans les applications pratiques, ils pourraient souffrir du problème d'incohérence dans les scénarios non linéaires, non gaussiens. Cette thèse se concentre sur l'étude des méthodes basées sur l'analyse par intervalles appliquées pour résoudre le problème de localisation et de cartographie robotisées. Au lieu de faire des hypothèses sur la distribution de probabilité, tous les bruits de capteurs sont supposés être bornés dans des limites connues. Sur la base d'une telle base, cette thèse formule le problème de localisation et de cartographie dans le cadre du problème de satisfaction de contraintes d'intervalle et applique des techniques d'intervalles cohérentes pour les résoudre de manière garantie. Pour traiter le problème du "lacet non corrigé" rencontré par les approches de localisation par ICP (Interval Constraint Propagation), cette thèse propose un nouvel algorithme ICP traitant de la localisation en temps réel du véhicule. L'algorithme proposé utilise un algorithme de cohérence de bas niveau et est capable de diriger la correction d'incertitude. Par la suite, la thèse présente un algorithme SLAM basé sur l'analyse d'intervalle (IA-SLAM) dédié à la caméra monoculaire. Une paramétrisation d'erreur liée et une initialisation non retardée pour un point de repère naturel sont proposées. Le problème SLAM est formé comme ICSP et résolu par des techniques de propagation par contrainte d'intervalle. Une méthode de rasage pour la contraction de l'incertitude historique et une méthode d'optimisation basée sur un graphique ICSP sont proposées pour améliorer le résultat obtenu. L'analyse théorique de la cohérence de la cartographie est également fournie pour illustrer la force de IA-SLAM. De plus, sur la base de l'algorithme IA-SLAM proposé, la thèse présente une approche cohérente et peu coûteuse pour la localisation de véhicules en extérieur. Il fonctionne dans un cadre en deux étapes (enseignement visuel et répétition) et est validé avec un véhicule de type voiture équipé de capteurs de navigation à l'estime et d'une caméra monoculaire. / With the rapid development and extensive applications of robot technology, the research on intelligent mobile robot has been scheduled in high technology development plan in many countries. Autonomous navigation plays a more and more important role in the research field of intelligent mobile robot. Localization and map building are the core problems to be solved by the robot to realize autonomous navigation. Probabilistic techniques (such as Extented Kalman Filter and Particle Filter) have long been used to solve the robotic localization and mapping problem. Despite their good performance in practical applications, they could suffer the inconsistency problem in the non linear, non Gaussian scenarios. This thesis focus on study the interval analysis based methods applied to solve the robotic localization and mapping problem. Instead of making hypothesis on the probability distribution, all the sensor noises are assumed to be bounded within known limits. Based on such foundation, this thesis formulates the localization and mapping problem in the framework of Interval Constraint Satisfaction Problem and applied consistent interval techniques to solve them in a guaranteed way. To deal with the “uncorrected yaw” problem encountered by Interval Constraint Propagation (ICP) based localization approaches, this thesis proposes a new ICP algorithm dealing with the real-time vehicle localization. The proposed algorithm employs a low-level consistency algorithm and is capable of heading uncertainty correction. Afterwards, the thesis presents an interval analysis based SLAM algorithm (IA-SLAM) dedicates for monocular camera. Bound-error parameterization and undelayed initialization for nature landmark are proposed. The SLAM problem is formed as ICSP and solved via interval constraint propagation techniques. A shaving method for landmark uncertainty contraction and an ICSP graph based optimization method are put forward to improve the obtaining result. Theoretical analysis of mapping consistency is also provided to illustrated the strength of IA-SLAM. Moreover, based on the proposed IA-SLAM algorithm, the thesis presents a low cost and consistent approach for outdoor vehicle localization. It works in a two-stage framework (visual teach and repeat) and is validated with a car-like vehicle equipped with dead reckoning sensors and monocular camera.