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.

Malaria prevention in north-eastern Tanzania: patterns of expenditure and determinants of demand at the household level.

Objective. This study aims to provide a better understanding of the amounts spent on different malaria prevention products and the determinants of these expenditures. Methods. 1,601 households were interviewed about their expenditure on malaria mosquito nets in the past five years, net re-treatments in the past six months and other expenditures prevention in the past two weeks. Simple random sampling was used to select villages and streets while convenience sampling was used to select households. Expenditure was compared across bed nets, aerosols, coils, indoor spraying, using smoke, drinking herbs and cleaning outside environment. Findings. 68% of households owned at least one bed net and 27% had treated their nets in the past six months. 29% were unable to afford a net. Every fortnight, households spent an average of US $0.18 on nets and their treatment, constituting about 47% of total prevention expenditure. Sprays, repellents and coils made up 50% of total fortnightly expenditure (US$0.21). Factors positively related to expenditure were household wealth, years of education of household head, household head being married and rainy season. Poor quality roads and living in a rural area had a negative impact on expenditure. Conclusion. Expenditure on bed nets and on alternative malaria prevention products was comparable. Poor households living in rural areas spend significantly less on all forms of malaria prevention compared to their richer counterparts. Breaking the cycle between malaria and poverty is one of the biggest challenges facing malaria control programmes in Africa.

Operational expenditure costs for wave energy projects and impacts on financial returns

This paper examines 'availability' and the input metrics of operational expenditure (OPEX) for wave energy projects and reports on a case study which assesses the impact of these inputs on project profit returns. Case study simulations modelled a 75 MW wave energy project at two locations; the west coast of Ireland and the north coast of Portugal. Access and availability with respect to weather windows at both locations are discussed and their impact on energy output and wave farm operations is quantified. The input metrics used to calculate OPEX of wave energy projects are defined as well as the impact of OPEX on project net present value (NPV) and internal rate of return (IRR). Results indicate that access and resultant availability factors have a significant impact on case study results by reducing energy output and correspondingly financial returns. Furthermore, the technology maturity level designated for a project also impacts on availability factors and consequently energy output and NPV. Case study profits proved to be very sensitive to annual OPEX, especially if overhaul and replacement costs were accounted for. As a result of the impact of 'availability' on project profit returns. Feed-in tariffs will need to be tailored to the location in question as well as the device technology maturity level, with case study simulations indicating that high FIT will be required to support early stage WEC projects. (C) 2012 Elsevier Ltd. All rights reserved.

A constraint and position identification (CPI) approach for the synthesis of decoupled spatial translational compliant parallel manipulators

This paper introduces a screw theory based method termed constraint and position identification (CPI) approach to synthesize decoupled spatial translational compliant parallel manipulators (XYZ CPMs) with consideration of actuation isolation. The proposed approach is based on a systematic arrangement of rigid stages and compliant modules in a three-legged XYZ CPM system using the constraint spaces and the position spaces of the compliant modules. The constraint spaces and the position spaces are firstly derived based on the screw theory instead of using the rigid-body mechanism design experience. Additionally, the constraint spaces are classified into different constraint combinations, with typical position spaces depicted via geometric entities. Furthermore, the systematic synthesis process based on the constraint combinations and the geometric entities is demonstrated via several examples. Finally, several novel decoupled XYZ CPMs with monolithic configurations are created and verified by finite elements analysis. The present CPI approach enables experts and beginners to synthesize a variety of decoupled XYZ CPMs with consideration of actuation isolation by selecting an appropriate constraint and an optimal position for each of the compliant modules according to a specific application.

Constraint-force-based approach of modelling compliant mechanisms: principle and application

Numerous works have been conducted on modelling basic compliant elements such as wire beams, and closed-form analytical models of most basic compliant elements have been well developed. However, the modelling of complex compliant mechanisms is still a challenging work. This paper proposes a constraint-force-based (CFB) modelling approach to model compliant mechanisms with a particular emphasis on modelling complex compliant mechanisms. The proposed CFB modelling approach can be regarded as an improved free-body- diagram (FBD) based modelling approach, and can be extended to a development of the screw-theory-based design approach. A compliant mechanism can be decomposed into rigid stages and compliant modules. A compliant module can offer elastic forces due to its deformation. Such elastic forces are regarded as variable constraint forces in the CFB modelling approach. Additionally, the CFB modelling approach defines external forces applied on a compliant mechanism as constant constraint forces. If a compliant mechanism is at static equilibrium, all the rigid stages are also at static equilibrium under the influence of the variable and constant constraint forces. Therefore, the constraint force equilibrium equations for all the rigid stages can be obtained, and the analytical model of the compliant mechanism can be derived based on the constraint force equilibrium equations. The CFB modelling approach can model a compliant mechanism linearly and nonlinearly, can obtain displacements of any points of the rigid stages, and allows external forces to be exerted on any positions of the rigid stages. Compared with the FBD based modelling approach, the CFB modelling approach does not need to identify the possible deformed configuration of a complex compliant mechanism to obtain the geometric compatibility conditions and the force equilibrium equations. Additionally, the mathematical expressions in the CFB approach have an easily understood physical meaning. Using the CFB modelling approach, the variable constraint forces of three compliant modules, a wire beam, a four-beam compliant module and an eight-beam compliant module, have been derived in this paper. Based on these variable constraint forces, the linear and non-linear models of a decoupled XYZ compliant parallel mechanism are derived, and verified by FEA simulations and experimental tests.