Modeling assembly program with constraints. A contribution to WCET problem

Dissertação para obtenção do Grau de Mestre em Lógica Computacional

Constraint reasoning with local search for continuous optimization

Optimization is a very important field for getting the best possible value for the optimization function. Continuous optimization is optimization over real intervals. There are many global and local search techniques. Global search techniques try to get the global optima of the optimization problem. However, local search techniques are used more since they try to find a local minimal solution within an area of the search space. In Continuous Constraint Satisfaction Problems (CCSP)s, constraints are viewed as relations between variables, and the computations are supported by interval analysis. The continuous constraint programming framework provides branch-and-prune algorithms for covering sets of solutions for the constraints with sets of interval boxes which are the Cartesian product of intervals. These algorithms begin with an initial crude cover of the feasible space (the Cartesian product of the initial variable domains) which is recursively refined by interleaving pruning and branching steps until a stopping criterion is satisfied. In this work, we try to find a convenient way to use the advantages in CCSP branchand- prune with local search of global optimization applied locally over each pruned branch of the CCSP. We apply local search techniques of continuous optimization over the pruned boxes outputted by the CCSP techniques. We mainly use steepest descent technique with different characteristics such as penalty calculation and step length. We implement two main different local search algorithms. We use “Procure”, which is a constraint reasoning and global optimization framework, to implement our techniques, then we produce and introduce our results over a set of benchmarks.

Constraint reasoning for differential models

The basic motivation of this work was the integration of biophysical models within the interval constraints framework for decision support. Comparing the major features of biophysical models with the expressive power of the existing interval constraints framework, it was clear that the most important inadequacy was related with the representation of differential equations. System dynamics is often modelled through differential equations but there was no way of expressing a differential equation as a constraint and integrate it within the constraints framework. Consequently, the goal of this work is focussed on the integration of ordinary differential equations within the interval constraints framework, which for this purpose is extended with the new formalism of Constraint Satisfaction Differential Problems. Such framework allows the specification of ordinary differential equations, together with related information, by means of constraints, and provides efficient propagation techniques for pruning the domains of their variables. This enabled the integration of all such information in a single constraint whose variables may subsequently be used in other constraints of the model. The specific method used for pruning its variable domains can then be combined with the pruning methods associated with the other constraints in an overall propagation algorithm for reducing the bounds of all model variables. The application of the constraint propagation algorithm for pruning the variable domains, that is, the enforcement of local-consistency, turned out to be insufficient to support decision in practical problems that include differential equations. The domain pruning achieved is not, in general, sufficient to allow safe decisions and the main reason derives from the non-linearity of the differential equations. Consequently, a complementary goal of this work proposes a new strong consistency criterion, Global Hull-consistency, particularly suited to decision support with differential models, by presenting an adequate trade-of between domain pruning and computational effort. Several alternative algorithms are proposed for enforcing Global Hull-consistency and, due to their complexity, an effort was made to provide implementations able to supply any-time pruning results. Since the consistency criterion is dependent on the existence of canonical solutions, it is proposed a local search approach that can be integrated with constraint propagation in continuous domains and, in particular, with the enforcing algorithms for anticipating the finding of canonical solutions. The last goal of this work is the validation of the approach as an important contribution for the integration of biophysical models within decision support. Consequently, a prototype application that integrated all the proposed extensions to the interval constraints framework is developed and used for solving problems in different biophysical domains.

Repairs of databases with null values

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

Modern techniques for constraint solving the CASPER experience

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

Constraint-based modeling of minimum set covering: application to species differentation

Work presented in the context of the European Master in Computational Logics, as partial requisit for the graduation as Master in Computational Logics

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.

Viewpoints and goals: towards an integrated approach

Dissertação de Mestrado em Engenharia Informática

Integrando problem frames com aspectos

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

A new approach to the initial value problem

5th Portuguese Conference on Automatic Control, September, 5-7, 2002, Aveiro, Portugal

Software languages engineering: experimental evaluation

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

A terapia ocupacional como recurso para idosos institucionalizados: um estudo de avaliação das necessidades ocupacionais

RESUMO: O envelhecimento populacional está associado a necessidades de saúde, incluindo aspectos ligados à realização das actividades quotidianas e à vertente ocupacional em geral.O presente estudo procurou identificar as necessidades ocupacionais de uma amostra de idosos institucionalizados e avaliar alterações no desempenho ocupacional e na satisfação após participação num programa de actividades terapêuticas. A amostra foi constituída por 20 indivíduos, com uma média de idades de 86,2 anos (DP=6,0), maioritariamente do sexo feminino e viúvos, com níveis de escolaridade diversos, sem défice cognitivo grave, provenientes de duas instituições para idosos em Lisboa. Os instrumentos utilizados foram entrevista de caracterização sócio-demográfica. Mini- Mental State Examination. Índice de Katz e Medida Canadiana de Desempenho Ocupacional. Após a participação no programa de actividades, oito indivíduos mantiveram as notas de desempenho e de satisfação na Medida Canadiana; cinco apresentaram aumento em ambas as notas; para dois, o desempenho permaneceu inalterado e o grau de satisfação diminuiu; finalmente, três deixaram de ter pelo menos um problema no desempenho, destacando-se um indivíduo que deixou de ter problemas para se alimentar, tornando-se independente nesta área. Comparando as avaliações iniciais e as reavaliações pósintervenção, não se registaram diferenças significativas nas pontuações de desempenho nem de satisfação da Medida Canadiana. Em conclusão, muitos dos participantes do estudo referiram um desempenho deficiente em muitas actividades ocupacionais que valorizavam, assim como um grau elevado de insatisfação em relação a esse desempenho. Apesar de ter tido algum impacto nas necessidades ocupacionais dos participantes, o programa de actividades não pareceu trazer benefícios generalizados nesta pequena amostra.------------ABSTRACT:The aging process in institutionalized populations has implications that encompass various issues related to health, including occupational development and the performance of daily activities. It was this study’s objective to identify the occupational needs of a sample of institutionalized elderly and to identify the existence of changes in occupational performance and satisfaction after participation in a program of therapeutic activities. The sample consisted of 20 individuals (mostly female and widowed) from two nursing homes in Lisbon, having various levels of education and an average age of 86,2 years (SD=6,0) as well as the ability of verbal expression without severe cognitive deficit. The instruments used were a structured interview for socio-demographic characterization, the Mini Mental State Examination, the Katz Index and the Canadian Occupational Performance Measure. We found that older respondents claimed that the performance of daily activities constituted a problem. They stated that the activities of self-care and leisure were the most problematic, that they had negative self-perceptions regarding their own performance, and that they were dissatisfied with this performance of their daily activities. After participating in program activities, eight respondents experienced no change in their respective grades of performance and satisfaction, five showed increases in both grades and, for two respondents, the performance remained unchanged while the satisfaction level showed a decline. Three stopped having at least one problem in performance, and one participant even stopped referring feeding problems, having become independent in this area. Regarding the evolution of the Canadian Measure performance and satisfaction scores (before versus after the intervention), we found no significant differences. In conclusion, most participants stated that they were performing badly in what concerned the occupational activities they valued the most. The same applies to low levels of satisfaction regarding that performance. In this small sample, and despite some benefits, the program of therapeutic activities did not prove to be significantly effective.

Constraint-based verification of imperative programs

work presented in the context of the European Master’s program in Computational Logic, as the partial requirement for obtaining Master of Science degree in Computational Logic