Probabilistic constraint reasoning

Dissertação apresentada para obtenção do Grau de Doutor em Engenharia Informática, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Probabilistic constraint reasoning with Monte Carlo integration to robot localization

This work studies the combination of safe and probabilistic reasoning through the hybridization of Monte Carlo integration techniques with continuous constraint programming. In continuous constraint programming there are variables ranging over continuous domains (represented as intervals) together with constraints over them (relations between variables) and the goal is to find values for those variables that satisfy all the constraints (consistent scenarios). Constraint programming “branch-and-prune” algorithms produce safe enclosures of all consistent scenarios. Special proposed algorithms for probabilistic constraint reasoning compute the probability of sets of consistent scenarios which imply the calculation of an integral over these sets (quadrature). In this work we propose to extend the “branch-and-prune” algorithms with Monte Carlo integration techniques to compute such probabilities. This approach can be useful in robotics for localization problems. Traditional approaches are based on probabilistic techniques that search the most likely scenario, which may not satisfy the model constraints. We show how to apply our approach in order to cope with this problem and provide functionality in real time.

Double implementation in a market for indivisible goods with a price constraint

I consider the problem of assigning agents to objects where each agent must pay the price of the object he gets and prices must sum to a given number. The objective is to select an assignment-price pair that is envy-free with respect to the true preferences. I prove that the proposed mechanism will implement both in Nash and strong Nash the set of envy-free allocations. The distinguishing feature of the mechanism is that it treats the announced preferences as the true ones and selects an envy-free allocation with respect to the announced preferences.

Differential epipolar constraint in mobile robot egomotion estimation

The estimation of camera egomotion is a well established problem in computer vision. Many approaches have been proposed based on both the discrete and the differential epipolar constraint. The discrete case is mainly used in self-calibrated stereoscopic systems, whereas the differential case deals with a unique moving camera. The article surveys several methods for mobile robot egomotion estimation covering more than 0.5 million samples using synthetic data. Results from real data are also given

Comparison of Work Scheduling Using Constraint Programming or Auctions

Business processes designers take into account the resources that the processes would need, but, due to the variable cost of certain parameters (like energy) or other circumstances, this scheduling must be done when business process enactment. In this report we formalize the energy aware resource cost, including time and usage dependent rates. We also present a constraint programming approach and an auction-based approach to solve the mentioned problem including a comparison of them and a comparison of the proposed algorithms for solving them

Locating emergency services with different priorities: The priority queuing covering location problem

Previous covering models for emergency service consider all the calls to be of the sameimportance and impose the same waiting time constraints independently of the service's priority.This type of constraint is clearly inappropriate in many contexts. For example, in urban medicalemergency services, calls that involve danger to human life deserve higher priority over calls formore routine incidents. A realistic model in such a context should allow prioritizing the calls forservice.In this paper a covering model which considers different priority levels is formulated andsolved. The model heritages its formulation from previous research on Maximum CoverageModels and incorporates results from Queuing Theory, in particular Priority Queuing. Theadditional complexity incorporated in the model justifies the use of a heuristic procedure.

A new chance-constrained maximum capture location problem

The paper presents a new model based on the basic Maximum Capture model,MAXCAP. The New Chance Constrained Maximum Capture modelintroduces astochastic threshold constraint, which recognises the fact that a facilitycan be open only if a minimum level of demand is captured. A metaheuristicbased on MAX MIN ANT system and TABU search procedure is presented tosolve the model. This is the first time that the MAX MIN ANT system isadapted to solve a location problem. Computational experience and anapplication to 55 node network are also presented.

Estimating parameters for generalized mass action models using constraint propagation.

As modern molecular biology moves towards the analysis of biological systems as opposed to their individual components, the need for appropriate mathematical and computational techniques for understanding the dynamics and structure of such systems is becoming more pressing. For example, the modeling of biochemical systems using ordinary differential equations (ODEs) based on high-throughput, time-dense profiles is becoming more common-place, which is necessitating the development of improved techniques to estimate model parameters from such data. Due to the high dimensionality of this estimation problem, straight-forward optimization strategies rarely produce correct parameter values, and hence current methods tend to utilize genetic/evolutionary algorithms to perform non-linear parameter fitting. Here, we describe a completely deterministic approach, which is based on interval analysis. This allows us to examine entire sets of parameters, and thus to exhaust the global search within a finite number of steps. In particular, we show how our method may be applied to a generic class of ODEs used for modeling biochemical systems called Generalized Mass Action Models (GMAs). In addition, we show that for GMAs our method is amenable to the technique in interval arithmetic called constraint propagation, which allows great improvement of its efficiency. To illustrate the applicability of our method we apply it to some networks of biochemical reactions appearing in the literature, showing in particular that, in addition to estimating system parameters in the absence of noise, our method may also be used to recover the topology of these networks.

An Improved Hybrid Model for the Generic Hoist Scheduling Problem

Peer-reviewed

Women over thirty choosing education as a solution to a problem

This study explored motivations of mid-life women over 30 years old who had returned to school. It sought to fmd whether these women returned to solve a problem arising from life events, whether viewing a problem was related to internal or external motivation, whether this perception was related to having greater coping skills, and whether having greater coping was related to seeking support from internal or external sources. This study examined which emotions were most related to viewing a life event as a problem. Finally, it explored the results of previous research of mid-life women in their role as a student. Women (N==83) from three types of institutions volunteered for this study: a university (N==34), a college (N==28), and an adult education centre (N==21). Participants took home a questionnaire package - a I3-page questionnaire and consent form - that were completed and mailed back to the researcher in pre-paid envelopes. Results showed that women over 30 seek education as a solution to a life event problem. External motivation was related to a life event being a problem (p<.005). There was a significant difference in coping scores between institutions. Moods that were related to viewing a life event as problematic were: anger and depressive moods (p<. 001), fatigue and vigor (p<.O 1), and tension/anxiety (p<.05). Mid-life women students' satisfaction in this role was related to being externally motivated. These women sought support from both internal and external sources, rarely had social interactions with peers, and viewed this role as important, yet, temporary in that it will help them change their lives. Implications ofthe results suggest further exploration ofthe roles of anger and depression in motivating women over 30 to learn and finding ways of directing women to use their emotional intelligence to seek out learning.

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

Relation entre la satisfaction et la qualité de vie reliée à la santé bucco-dentaire chez les patients totalement édentés

Problématique : La satisfaction des patients et la qualité de vie reliée à la santé bucco-dentaire (OHRQoL) sont deux mesures de résultats fréquemment utilisées durant les études cliniques. Néanmoins, chez les patients totalement édentés, les évidences scientifiques relatives au niveau de relation entre ces deux mesures sont faibles. De plus, on ignore toujours quels éléments de la satisfaction des patients relativement à leurs prothèses partagent la meilleure relation avec la OHRQoL. Objectifs : Déterminer, chez les patients totalement édentés, s’il existe un lien entre leur satisfaction de leurs prothèses et leur OHRQoL et identifier les déterminants de satisfaction qui démontrent le meilleur niveau de relation avec la OHRQoL. Méthodologie : Les données provenant de 255 patients totalement édentés qui ont participé à une étude randomisée et contrôlée ont été utilisées. La OHRQoL a été évaluée à l’aide du questionnaire Oral Health Impact Profile (OHIP-20). Le McGill Denture Satisfaction Instrument a été utilisé pour estimer la satisfaction des patients. Ces mesures ont été prises au temps initial, à 6 mois et à 12 mois suivants la mise en bouche des prothèses. Des analyses statistiques de régression linéaire simples et multiples ont été utilisées afin d’évaluer la relation entre les deux mesures. Résultats : Une relation positive et considérable existe entre la satisfaction des patients totalement édentés et leur OHRQoL. La difficulté masticatoire (P = .005) et la condition buccale (P = .002) sont les éléments de la satisfaction qui possèdent le meilleur lien avec la OHRQoL. Ces deux facteurs expliquent 46.4% (P = .0001) de la variance dans l’amélioration d’OHIP suivant un traitement prosthodontique. La relation décrite est dépendante du temps, mais pas du type de traitement ni des variables sociodémographiques. Conclusions : Dans les limites de l’étude, il est conclu qu’une relation positive existe entre la satisfaction des patients et leur OHRQoL. La difficulté masticatoire et la condition buccale sont les deux éléments de la satisfaction les plus importants.

Academic and social adjustment of teenagers in social rehabilitation : the role of intrinsic need satisfaction and autonomy support

Les études antérieures ont démontré les bénéfices de la satisfaction des besoins intrinsèques et du soutien à l’autonomie dans le domaine de l’éducation. Or, l’applicabilité des tenants principaux de la Théorie de l’Auto-Détermination (TAD; Deci & Ryan, 2000) n’a pas été investiguée auprès d’une population clinique d’adolescents. L’objectif de cette thèse doctorale est de faire la lumière sur la façon dont l'adaptation scolaire et sociale peut être favorisée par les agents de socialisation dans le contexte de la réadaptation sociale. Cette thèse est composée de deux études s’intéressant à l’application des tenants clés de la TAD auprès de deux échantillons d’adolescents vivant des problèmes d’adaptation et recevant des services d’éducation spécialisée et de réadaptation sociale. Les relations entre les concepts motivationnels de base sont étudiés afin de déterminer si, comme la TAD le propose, la satisfaction des besoins intrinsèques des jeunes peut être soutenue par le style interpersonnel des agents de socialisation (c.-à-d., le soutien à l’autonomie, l’implication et la structure). Il est aussi vérifié si ces concepts motivationnels améliorent la motivation ainsi que d’autres conséquences qui résultent de leur expérience, proposées par la TAD. La première étude a évalué si le style interpersonnel des enseignants peut favoriser la satisfaction des besoins des élèves, leur style de motivationl, tout comme leur ajustement scolaire. Les élèves en difficulté d’adaptation (N = 115) inscrits aux écoles internes des Centres de Réadaptation en raison de leurs problématiques émotionnelles et comportementales ont rempli les questionnaires à deux reprises, au début et à la fin de l’année scolaire. Les analyses de modèles d’équations structurelles révèlent que l’augmentation du soutien à l’autonomie et de l’implication (mais pas de la structure) des enseignants pendant l’année est associée à une augmentation de la satisfaction des besoins des élèves qui, conséquemment, conduit à une motivation scolaire plus auto-déterminée et à une diminution d’intentions de décrochage à la fin de l’année scolaire. De plus, l’amélioration de la satisfaction des besoins mène directement à une meilleure expérience affective à l’école. La deuxième étude consiste en une recherche expérimentale conduite auprès d’adolescentes en difficulté d’adaptation (N = 29). Le devis expérimental a permis de comparer l’impact de la présence (c. absence) du soutien à l’autonomie sur l’internalisation d’une tâche et sur les conséquences motivationnelles et expérientielles des jeunes. La tâche, fastidieuse mais importante, consistait à de la résolution de problèmes interpersonnels (activité clinique). Les résultats suggèrent qu’un style interpersonnel soutenant l’autonomie a augmenté la motivation auto-déterminée, la perception de la valeur de la tâche et son appréciation, ainsi que diminué les affects négatifs comparativement à la condition sans soutien à l’autonomie. Les résultats sont discutés en lien avec les implications théoriques et pratiques d’étendre la portée de la TAD à une population clinique d’adolescents aux prises avec des difficultés d’adaptation.

Les attentes, la satisfaction et la qualité de vie des édentés suite à une réhabilitation par mise en charge immédiate d'une prothèse totale reliée à deux implants non jumelés : une étude pilote expérimentale

Problématique : La majorité des études publiées sur la réhabilitation par mise en charge immédiate de deux implants non jumelés avec une prothèse totale mandibulaire de recouvrement n’ont rapporté que des mesures cliniques objectives et très peu ont évalué les mesures centrées sur le patient, et ce, avec des erreurs de mesure. Aucune étude n’a évalué les attentes des patients vis-à-vis d'un tel protocole. Objectifs : Évaluer les attentes, le niveau de satisfaction ainsi que la qualité de vie reliée à la santé bucco-dentaire des édentés complets suite à un protocole de mise en charge immédiate. Méthodologie : Cet essai clinique de phase 1 utilise un design pré-post afin d’évaluer les mesures centrées sur le patient. Dix-huit individus, complètement édentés et âgés en moyenne de 62,39 ± 7,65 ans, ont reçu une prothèse totale mandibulaire de recouvrement sur deux implants non jumelés suite à un protocole de mise en charge immédiate, conjointement à une prothèse totale conventionnelle maxillaire. Un instrument adapté pour mesurer leurs attentes à l’aide d’échelles visuelles analogues, le questionnaire « McGill Denture Satisfaction Instrument » ainsi que le questionnaire OHIP-20 ont été remis aux patients avant de procéder aux traitements (T0), ainsi qu’aux rendez-vous de suivi à 2 semaines (T1), 1 mois (T2) et 4 mois (T3). De plus, l’inventaire de personnalité révisé (NÉO PI-R) ainsi qu’un questionnaire sociodémographique ont été remplis par les participants. Les « change scores » ont été calculés puis des tests non paramétriques et des analyses de variances en mesures répétées suivies de comparaisons par paires ont été utilisés afin d’analyser les données recueillies. La taille d’effet a été estimée. Résultats : Les participants avaient différentes attentes par rapport à la mise en charge immédiate. Certains s’attendaient à un effet positif à court terme par rapport à leur apparence esthétique (83,3 %) et à leur vie sociale (55,7 %), alors que d’autres avaient des craintes envers leur confort (5,6 %), leur habileté à mastiquer (11,1 %) et à nettoyer leur prothèse inférieure (11,1 %). À 4 mois, le protocole de mise en charge immédiate avait rencontré la majorité des attentes des patients par rapport à l’esthétique (94.4 %), la mastication (83.3 %), la phonétique (61.1 %), le confort (94.4 %), l’hygiène (88.9 %) et leur vie sociale (88.9 %). Une amélioration statistiquement significative de la satisfaction en générale, du confort, de l’esthétique, de la stabilité de la prothèse inférieure et de l’habileté à mastiquer a été notée à 2 semaines (p<0,001). Également, les comparaisons par paires ont révélé une diminution statistiquement significative du score total de l’OHIP-20 (p < 0,001) de même que la majorité des domaines de l’OHIP (p < 0.01), sauf pour l’handicap social qui n’a diminué significativement qu’après 1 mois (p = 0.01). Ces changements (pour la satisfaction et la qualité de vie) sont restés stables au cours des suivis subséquents. Indépendamment des traits de personnalité et des variables sociodémographiques, le protocole immédiat a satisfait 94,4 % des participants et a amélioré leur qualité de vie avec une large magnitude d’effet (d = 1.9; p < 0.001). Bien que deux patients aient perdu des implants au cours du traitement, 100 % des participants étaient d’accord pour recommander cette procédure à leurs pairs. Conclusions: Le protocole de mise en charge immédiate semble satisfaire les patients quelles que soient leurs attentes. Le protocole MCI peut améliorer, à court terme, la qualité de vie des patients totalement édentés. Les résultats prometteurs de la phase 1 devraient être corroborés lors de la 2e phase de cette étude.