We develop a new approach for a pre-disaster planning problem which consists in computing an optimal investment plan to strengthen a transportation network, given that a future disaster probabilistically destroys links in the network. We show how the problem can be formulated as a non-linear integer program and devise an AI algorithm to solve it. In particular, we introduce a new type of extreme resource constraint and develop a practically efficient propagation algorithm for it. Experiments show several orders of magnitude improvements over existing approaches, allowing us to close an existing real-world benchmark and to solve to optimality other, more challenging benchmarks.

Identifying important components or factors in large amounts of noisy data is a key problem in machine learning and data mining. Motivated by a pattern decomposition problem in materials discovery, aimed at discovering new materials for renewable energy, e.g. for fuel and solar cells, we introduce CombiFD, a framework for factor based pattern decomposition that allows the incorporation of a-priori knowledge as constraints, including complex combinatorial constraints. In addition, we propose a new pattern decomposition algorithm, called AMIQO, based on solving a sequence of (mixed-integer) quadratic programs. Our approach considerably outperforms the state of the art on the materials discovery problem, scaling to larger datasets and recovering more precise and physically meaningful decompositions. We also show the effectiveness of our approach for enforcing background knowledge on other application domains.

This paper outlines a new approach to creating value from the Smart Grid by incorporating individual households into the response system that must be deployed to accommodate increasingly large sources of intermittent renewable power. We propose a framework that couples agent-based AI techniques with envelope methods. Envelope methods provide a unified mathematical framework to model intermittent renewable resources, conventional dispatchable resources, demand side response, and storage. The overall goal of our system is to develop a distributed autonomous agent architecture that is able to facilitate market transactions among load serving entities, residential consumers, conventional merchant power producers, and intermittent power producers.

Among the languages used for representing goals, actions and their consequences on the world for decision making and planning, GDL (Game Description Language) has the ability to represent complex actions in potentially uncertain and competitive environments. The aim of this paper is to exploit stochastic constraint networks in order to provide compact representations of strategic games, and to identify optimal policies in those games with generic forward checking method. From this perspective, we develop a compiler allowing to translate games, described in GDL, into instances of the Stochastic Constraint Optimization Problem (SCSP). Our compiler is proved correct for the class GDL of games with complete information and oblivious environment. The interest of our approach is illustrated by solving several GDL games with a SCSP solver.

In this challenge paper, we consider the importance of preferences in smart homes and assistive environments and discuss the potential application of models and algorithms developed within the computational preferences community. We suggest the value of future research collaborations.

To achieve high performance, autonomous systems, such as science explorers, should adapt to the environment to improve utility gained, as well as robustness. Flexibility during temporal plan execution has been explored extensively to improve robustness, where flexibility exists both in activity choices and schedules. These problems are framed as conditional constraint networks over temporal constraints. However, flexibility has been exploited in a limited form to improve utility. Prior work considers utility in choice or schedule, but not their coupling. To exploit fully flexibility, we introduce conditional simple temporal networks with preference (CSTNP), where preference is a function over both choice and schedule. Enumerating best solutions to a CSTNP is challenging due to the cost of scheduling a candidate STPP and the exponential number of candidates. Our contribution is an algorithm for enumerating solutions to CSTNPs efficiently, called A star with bounding conflicts (A*BC), and a novel variant of conflicts, called bounding conflicts, for learning heuristic functions. A*BC interleaves Generate, Test, and Bound. When A*BC bounds a candidate, by solving a STPP, it generates a bounding conflict, denoting neighboring candidates with similar bounds. A*BC's generator then uses these conflicts to steer away from sub-optimal candidates.

Finding satisfying assignments for the variables involved in a set of constraints can be cast as a (bounded) model generation problem: search for (bounded) models of a theory in some logic. The state-of-the-art approach for bounded model generation for rich knowledge representation languages like ASP and FO(.) and a CSP modeling language such as Zinc, is ground-and-solve: reduce the theory to a ground or propositional one and apply a search algorithm to the resulting theory. An important bottleneck is the blow-up of the size of the theory caused by the grounding phase. Lazily grounding the theory during search is a way to overcome this bottleneck. We present a theoretical framework and an implementation in the context of the FO(.) knowledge representation language. Instead of grounding all parts of a theory, justifications are derived for some parts of it. Given a partial assignment for the grounded part of the theory and valid justifications for the formulas of the non-grounded part, the justifications provide a recipe to construct a complete assignment that satisfies the non-grounded part. When a justification for a particular formula becomes invalid during search, a new one is derived; if that fails, the formula is split in a part to be grounded and a part that can be justified. Experimental results illustrate the power and generality of this approach.

The goal of constraint-based sequence mining is to find sequences of symbols that are included in a large number of input sequences and that satisfy some constraints specified by the user. Many constraints have been proposed in the literature, but a general framework is still missing. We investigate the use of constraint programming as general framework for this task. We first identify four categories of constraints that are applicable to sequence mining. We then propose two constraint programming formulations. The first formulation introduces a new global constraint called exists-embedding. This formulation is the most efficient but does not support one type of constraint. To support such constraints, we develop a second formulation that is more general but incurs more overhead. Both formulations can use the projected database technique used in specialised algorithms. Experiments demonstrate the flexibility towards constraint-based settings and compare the approach to existing methods.

As one of the most important types of (weaker) supervised information in machine learning and pattern recognition, pairwise constraint, which specifies whether a pair of data points occur together, has recently received significant attention, especially the problem of pairwise constraint propagation. At least two reasons account for this trend: the first is that compared to the data label, pairwise constraints are more general and easily to collect, and the second is that since the available pairwise constraints are usually limited, the constraint propagation problem is thus important. This paper provides an up-to-date critical survey of pairwise constraint propagation research. There are two underlying motivations for us to write this survey paper: the first is to provide an up-to-date review of the existing literature, and the second is to offer some insights into the studies of pairwise constraint propagation. To provide a comprehensive survey, we not only categorize existing propagation techniques but also present detailed descriptions of representative methods within each category.

The Region Connection Calculus (RCC) is a well-known calculus for representing part-whole and topological relations. It plays an important role in qualitative spatial reasoning, geographical information science, and ontology. The computational complexity of reasoning with RCC5 and RCC8 (two fragments of RCC) as well as other qualitative spatial/temporal calculi has been investigated in depth in the literature. Most of these works focus on the consistency of qualitative constraint networks. In this paper, we consider the important problem of redundant qualitative constraints. For a set $\Gamma$ of qualitative constraints, we say a constraint $(x R y)$ in $\Gamma$ is redundant if it is entailed by the rest of $\Gamma$. A prime subnetwork of $\Gamma$ is a subset of $\Gamma$ which contains no redundant constraints and has the same solution set as $\Gamma$. It is natural to ask how to compute such a prime subnetwork, and when it is unique. In this paper, we show that this problem is in general intractable, but becomes tractable if $\Gamma$ is over a tractable subalgebra $\mathcal{S}$ of a qualitative calculus. Furthermore, if $\mathcal{S}$ is a subalgebra of RCC5 or RCC8 in which weak composition distributes over nonempty intersections, then $\Gamma$ has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from $\Gamma$. As a byproduct, we show that any path-consistent network over such a distributive subalgebra is weakly globally consistent and minimal. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.