Computing explanations for interactive constraint-based systems

Constraint programming has emerged as a successful paradigm for modelling combinatorial problems arising from practical situations. In many of those situations, we are not provided with an immutable set of constraints. Instead, a user will modify his requirements, in an interactive fashion, until he is satisfied with a solution. Examples of such applications include, amongst others, model-based diagnosis, expert systems, product configurators. The system he interacts with must be able to assist him by showing the consequences of his requirements. Explanations are the ideal tool for providing this assistance. However, existing notions of explanations fail to provide sufficient information. We define new forms of explanations that aim to be more informative. Even if explanation generation is a very hard task, in the applications we consider, we must manage to provide a satisfactory level of interactivity and, therefore, we cannot afford long computational times. We introduce the concept of representative sets of relaxations, a compact set of relaxations that shows the user at least one way to satisfy each of his requirements and at least one way to relax them, and present an algorithm that efficiently computes such sets. We introduce the concept of most soluble relaxations, maximising the number of products they allow. We present algorithms to compute such relaxations in times compatible with interactivity, achieving this by indifferently making use of different types of compiled representations. We propose to generalise the concept of prime implicates to constraint problems with the concept of domain consequences, and suggest to generate them as a compilation strategy. This sets a new approach in compilation, and allows to address explanation-related queries in an efficient way. We define ordered automata to compactly represent large sets of domain consequences, in an orthogonal way from existing compilation techniques that represent large sets of solutions.

Identifying sources of global contention in constraint satisfaction search

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine-grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this work we present two methods for learning from search using restarts, in order to identify these critical variables prior to solving. Both methods are based on the conflict-directed heuristic (weighted-degree heuristic) introduced by Boussemart et al. and are aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimizing the overhead of these restarts. We further examine the impact of different sampling strategies and different measurements of contention, and assess different restarting strategies for the heuristic. Finally, two applications for constraint weighting are considered in detail: dynamic constraint satisfaction problems and unary resource scheduling problems.

Synecology in soft sediment bivalves: the influence of parasites, physiological processes, and environmental stressors on health and disease

Ecosystem goods and services provided by estuarine and near coastal regions are being increasingly recognised for their immense value, as is the biodiversity in these areas and these near coastal communities have been identified as sentinels of climate change also. Population structure and reproductive biology of two bivalve molluscs, Cerastoderma edule and, Mytilus edulis were assessed at two study sites over a 16-month study period. Following an anomalously harsh winter, advancement of spawning time was observed in both species. Throughout Ireland and Europe the cockle has experienced mass surfacings in geographically distinct regions, and a concurrent study of cockles was undertaken to explore this phenomenon. Surfaced and buried cockles were collected on a monthly basis and their health compared. Age was highlighted as a source of variation between dying and healthy animals with a parasite threshold being reached possibly around age three. Local factors dominated when looking at the cause of surfacing at each site. The health of mussels was explored too on a temporal and seasonal basis in an attempt to assess what constitutes a healthy organism. In essence external drivers can tip the balance between “acceptable” levels of infection where the mussel can still function physiologically and “unacceptable” where prevalence and intensity of infection can result in physiological impairment at the individual and population level. Synecological studies of intertidal ecosystems are lacking, so all bivalves encountered during the sampling were assessed in terms of population structure, reproduction, and health. It became clear, that some parasites might specialize on one host species while others are not so specific in host choice. Furthermore the population genetics of the cockle, its parasite Meiogymnophallus minutus, and its hyperparasite Unikaryon legeri were examined too. A small nucleotide polymorphism was detected upon comparison of Ireland and Morocco.