Local consistency properties and algorithms for enforcing them are central to the success of Constraint Processing. Recently, we have demonstrated the importance of higher levels of consistency and the effectiveness of their algorithms for solving difficult problems (Karakashian et al. 2010; Woodward et al. 2011). In this paper, we introduce two reformulation techniques for improving the effectiveness of our algorithm for the relational consistency property R (*, m ) C (Karakashian et al. 2010). Both techniques exploit a tree decomposition of the constraint network of a Constraint Satisfaction Problem (CSP), which is a tree embedding of the network. Our first reformulation technique exploits the structure of the decomposition tree and the state of the backtrack search to omit unnecessary steps from our algorithm and improve its performance. Our second contribution is new relational consistency property called T-R (*, m, z ) C that is strictly stronger than R (*, m ) C. This property is achieved by modifying the structure of the constraint network and adding new redundant constraints to the CSP at the intersection of two vertices of the tree decomposition (Rollon and Dechter 2010). We demonstrate the advantages of the proposed two reformulations for finding all the solutions of a CSP using the technique known as Backtracking with Tree Decomposition (BTD) (Jegou and Terrioux 2003).

We explore a symmetry-based reformulation technique which can speed up optimal pathfinding on undirected uniform-cost grid maps by over 30 times. Our offline approach decomposes grid maps into a set of empty rectangles, removing from each all interior nodes and possibly some from along the perimeter. We then add macro-edges between selected pairs of remaining perimeter nodes to facilitate provably optimal traversal through each rectangle. To further speed up search, we also develop a novel online pruning technique. Our algorithm is fast, memory efficient and retains both optimality and completeness during search.

We propose a theory of abstraction of discrete-event systems (DES) formulated at the semantic level, i.e., as a function that maps event traces at the original (ground) level to traces at the abstract level. We study how diagnosis of DES can be performed using an abstract model, and under which conditions this process leads to a correct solution (i.e., a set of alternative diagnoses that include the real status of the system). Finally, we study how the use of an abstract model can affect the precision of diagnosis, i.e., the presence of spurious system states in the solution. To this end, we introduce the notion of diagnosability with abstract models, which ensures the precision of abstract diagnoses, and we discuss a practical way to test it.

Moreover, all of the of a system and, after detection, to determine the location faults that occurred within the (possibly extended) time interval and/or the type of system faults that caused the abnormal during which the system has been observed must be behaviour. A diagnosis hypothesis indicates which fault(s) accounted for in the diagnosis. Considering again the diagnosis occurred in the system, and the diagnosis is the set of alternative of a car, for each component we could be interested hypotheses that explain (i.e., are compatible) with in knowing whether a fault has occurred to it during the last the observed system behaviour. In this paper, we focus on week; in such a case, it is difficult to perform a drastic abstraction Model-Based Diagnosis (MBD) of Discrete-Event Systems of the model without losing any precision in the (DESs, see (Cassandras and Lafortune 1999)), where the diagnosis discrimination among different hypotheses. is computed by comparing a complete DES model In this article, we study a novel approach to reduce the of the system behaviour with a (partial) observation of the complexity of DES diagnosis, based on a reformulation of actual system behaviour (Sampath et al. 1995).

Constraint programming is a successful technology for solving combinatorial problems modeled as constraint satisfaction problems (CSPs). Many real life problems come from uncertain and dynamic environments, which means that the initial description of the problem may change during its execution. In these cases, the solution found for a problem may become invalid. The search of robust solutions for dynamic CSPs (DynCSPs) has become an important issue in the field of constraint programming. In this paper we reformulate DynCSPs withlinear constraints as weighted CSPs (WCSPs), and we present an approach that searches for robust solutions in problems without associated information about possible future changes. Thus, the best solution for a modeled WCSP will be a robust solution for the original DynCSP.

With the exponential increase in the number of documents available online, e.g., news articles, weblogs, scientific documents, effective and efficient classification methods are required in order to deliver the appropriate information to specific users or groups. The performance of document classifiers critically depends, among other things, on the choice of the feature representation. The commonly used "bag of words" representation can result in a large number of features. Feature abstraction helps reduce a classifier input size by learning an abstraction hierarchy over the set of words. A cut through the hierarchy specifies a compressed model, where the nodes on the cut represent abstract features. In this paper, we compare feature abstraction with two other methods for dimensionality reduction, i.e., feature selection and Latent Dirichlet Allocation (LDA). Experimental results on two data sets of scientific publications show that classifiers trained using abstract features significantly outperform those trained using features that have the highest average mutual information with the class, and those trained using the topic distribution and topic words output by LDA. Furthermore, we propose an approach to automatic identification of a cut in order to trade off the complexity of classifiers against their performance. Our results demonstrate the feasibility of the proposed approach.

We present a technique for automatically extracting temporal mutual exclusion invariants from PDDL2.2 planning instances. Our technique builds on other approaches to invariant synthesis presented in the literature, but departs from their limited focus on instantaneous discrete actions by addressing temporal and numeric domains. To deal with time, we formulate invariance conditions that account for both the entire structure of the operators (including the conditions, rather than just the effects) and the possible interactions between operators.

The Resource-Constrained Project Scheduling Problem (RCPSP) and some of its extensions have been widely studied. Many approaches have been considered to solve this problem: constraint programming (CP), Boolean satisfiability (SAT), mixed integer linear programming (MILP), branch and bound algorithms (BB) and others. In this paper, we present a new approach for solving this problem: satisfiability modulo theories (SMT). Solvers for SMT generalize SAT solving by adding the ability to handle arithmetic and other theories. We provide several encodings of the RCPSP into SMT, and introduce rcp2smt, a tool for solving RCPSP instances using SMT solvers, which exhibits good performance.

The International Symposium on Abstraction, Reformulation and Approximation (SARA) series was established in 1994. It continues to provide a way for researchers to share results on ARA. The Ninth International Symposium on Abstraction, Reformulation and Approximation was held on July 17-18, 2011 at a renovated medieval castle in the Parador de Cardona hotel in Catalonia, Spain, about 60 miles northwest of Barcelona. This year the paper submissions came from four different continents and thirteen different countries. This volume contains all twenty of the papers that were accepted by the program committee for presentation at the symposium and publication in the proceedings.

This paper presents a training game intended to train crisis management teams to negotiate collaboratively in order to reach the group goal in the best way possible. The importance of the group goal in comparison to their individual goals is touched upon as well, as are various conflicts that can occur during such a negotiation. The game, which is implemented in the Blocks World 4 Teams environment, gives a team a specific scenario and allows them to negotiate a plan of action. This plan of action is then performed by agents, after which the team members will be debriefed on their performance. An experiment, containing multiple rounds to test the effect the game has on participants, is planned in the near future.