This paper presents an efficient topology information extraction algorithm that is capable of extracting primary topological relations, such as, interior, boundary, and exterior from a single spatial or spatio-temporal object stored in a linear constraint database. Any non-spatial constraints will be preserved so that the input spatio-temporal object’s temporal constraints will not be sacrificed by the algorithm. Based on the three primary topological relations, more topological relations between regions, lines, and points can be defined in a constraint database for future spatial analysis.

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a new local consistency property for binary Constraint Satisfaction Problems (CSPs). Two advantages of the algorithm for enforcing NIC is that it automatically adapts its filtering power to the local connectivity of the network and has insignificant space overhead. However, studies on binary CSPs have shown that enforcing NIC is not effective on sparse graphs and too costly on dense graphs. In (Woodward et al. 2011), we introduced an algorithm for enforcing Relational Neighborhood Inverse Consistency (RNIC), which is an extension of NIC to non-binary CSPs. In this paper, we discuss how we enhance the propagation effectiveness of our algorithm and reduce its computational cost by reformulating the dual graph of the CSP. For that purpose, we describe two reformulation techniques that modify the topology of the dual graph without affecting the solution set of the problem. We present the two reformulations and their combinations, and discuss their effects on the consistency property enforced by the algorithm. We also describe a selection policy that nicely ties together the various components of our approach in a consistent, adaptive framework. Finally, we show that our automated selection policy outperforms all approaches in a statistically significant manner.

An example is a Mars rover: The major problem with applying POMDP approaches to thanks to low-level control and obstacle avoidance, rovers realistic planning problems like the Mars rovers is the sheer can be expected to reach their destinations reliably, and can size of the problems. Using point-based approximations and collect and communicate data, but they do not know in advance structured representations similar to those used in classical which science targets are interesting and hence will planning (Poupart 2005), problems with tens of millions provide valuable data. Similarly, robots performing tasks of states can be solved approximately, but even that corresponds such as security or cognitive assistance are generally able to to a classical planning problem with only 25 binary navigate reliably, but use unreliable vision algorithms to detect variables, which is a quite small problem by the standards the people and objects with which they are supposed of classical deterministic planning. The alternative we propose to interact. Following Besse and Chaib-draa (2009), we in this paper is to construct a series of classical deterministic will refer to problems with deterministic actions but stochastic planning problems from the quasi-deterministic observations as quasi-deterministic problems, which differ problem. By solving each of these deterministic problems from Deterministic-POMDPs (DET-POMDPS) (Bonet we construct a contingent plan--one that contains branches 2009) by taking into account of uncertainty from observation to be chosen between at run-time.

We present a novel method for generating a wide range of equivalent Boolean encodings of cardinality, while in contrast all previous Boolean encodings of cardinality have only one form. Experiments for applying this method to automated error diagnosis in formal verification of buggy variants of a complex reconfigurable VLIW processor indicate speedup of up to two orders of magnitude, relative to previous encodings of cardinality. Besides automated debugging of hardware and software, the presented Boolean encodings of cardinality have applications to many other problems.

We propose a novel method for combined Routing and Wave-length Assignment (RWA) in optical networks by reformulation to an equivalent Pseudo-Boolean Satisfiability (PB-SAT) problem. We introduce edge observability variables to represent whether an edge is on the optimal route, combined with either a simple or a hierarchical SAT encoding to select a wavelength for that edge only when the edge is on the route. This translation exponentially reduces the size of the solution space, making it independent of the number of wavelengths per link. We present experimental results for routing instances with up to 3,000 nodes, 15,000 edges, and 2,048 wavelengths per edge, and achieve at least 8 orders of magnitude speedup relative to a previous PB-SAT encoding by Aloul et al., such that the speedup is increasing with the number of nodes and edges in the network, and the number of wavelengths per edge. A portfolio of 4 parallel strategies, each based on the new approach and a different hierarchical encoding, resulted in additional speedup of up to 6 times, and reduced the variability of the run times for large networks.

In this paper we describe a reformulation strategy for solving multi-dimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the unidimensional constraints in the problem. It exploits the approximate symmetries identified on the domain values in order to enforce the selected constraint on the simplified problem. This paper uses the game of SET, a combinatorial card game, to motivate and illustrate our strategy. We propose a multi-dimensional constraint model for SET, and describe a basic constraint solver for finding all solutions of an instance of the game. Then, we introduce an algorithm that implements our reformulation strategy, and show that it yields a dramatic reduction of the search effort. Our approach sheds a new light on the dynamic reformulation of CSPs, leading the way to new strategies for effective problem solving. We use the game of SET as a toy problem to illustrate our strategy and explain its operation. We believe that our approach is applicable to more complex domains of scientific and industrial importance, and deserves thorough investigations in the future.

We present here a view on abstraction originating from the relation between formulas in a partially ordered language L and their extension on a set of instances W . In Formal Concept Analysis, this relation is materialized as a lattice G . Particular self-maps on either L or the powerset P ( W) are known to ensure structure-preserving reductions of the lattice G and have been shown to be in one to one correspondence with abstractions , defined subsets of either L or P ( W) closed under union. We investigate specifically extensional abstractions (subsets of P ( W) . Such an abstraction comes down to a change in granularity: extensions are now considered as union of abstract instances , that is, union of predefined subsets of instances. The main contribution of the paper is the investigation of the class of (non normal) monotonic modal logics whose semantics relies on such abstractions, and that we call abstract modal logics .

This paper explores six different representations of the BlocksWorld Domain. It compares the results of seven planners run on these representations. It shows that the rankings for the International Planning Competition, using the non-satisficing scoring function, would change for every representation.

Suppose an agent builds a policy that satisfactorily solves a decision problem; suppose further that some aspects of this policy are abstracted and used as starting point in a new, different decision problem. How can the agent accrue the benefits of the abstract policy in the new concrete problem? In this paper we propose a framework for simultaneous reinforcement learning, where the abstract policy helps start up the policy for the concrete problem, and both policies are refined through exploration. We report experiments that demonstrate that our framework is effective in speeding up policy construction for practical problems.

This paper investigates spatiotemporal interpolation methods for the application of air pollution assessment. The air pollutant of interest in this paper is fine particulate matter PM2.5. The choice of the time scale is investigated when applying the shape function-based method. It is found that the measurement scale of the time dimension has an impact on the interpolation results. Based upon the comparison between the accuracies of interpolation results, the most effective time scale out of four experimental ones was selected for performing the PM2.5 interpolation. The paper also evaluates the population exposure to the ambient air pollution of PM2.5 at the county-level in the contiguous U.S. in 2009. The interpolated county-level PM2.5 has been linked to 2009 population data and the population with a risky PM2.5 exposure has been estimated. The risky PM2.5 exposure means the PM2.5 concentration exceeding the National Ambient Air Quality Standards. The geographic distribution of the counties with a risky PM2.5 exposure is visualized. This work is essential to understanding the associations between ambient air pollution exposure and population health outcomes.