Expressive query languages are gaining relevance in knowledge representation (KR), and new reasoning problems come to the fore. Especially query containment is interesting in this context. The problem is known to be decidable for many expressive query languages, but exact complexities are often missing. We introduce a new query language, guarded queries (GQ), which generalizes most known languages where query containment is decidable. GQs can be nested (more expressive), or restricted to linear recursion (less expressive). Our comprehensive analysis of the computational properties and expressiveness of (linear/nested) GQs also yields insights on many previous languages.

In optimal planning as heuristic search, admissible pruning techniques are paramount. One idea is dominance pruning, identifying states "better than" other states. Prior approaches are limited to simple dominance notions, like "more STRIPS facts true" or "higher resource supply". We apply simulation, well-known in model checking, to compute much more general dominance relations based on comparing transition behavior across states. We do so effectively by expressing state-space simulations through the composition of simulations on orthogonal projections. We show how simulation can be made more powerful by intertwining it with a notion of label dominance. Our experiments show substantial improvements across several IPC benchmark domains.

In this article we present DUAL-PECCS, an integrated Knowledge Representation system aimed at extending artificial capabilities in tasks such as conceptual categorization. It relies on two different sorts of cognitively inspired common-sense reasoning: prototypical reasoning and exemplars-based reasoning. Furthermore, it is grounded on the theoretical tenets coming from the dual process theory of the mind, and on the hypothesis of heterogeneous proxytypes, developed in the area of the biologically inspired cognitive architectures (BICA). The system has been integrated into the ACT-R cognitive architecture, and experimentally assessed in a conceptual categorization task, where a target concept illustrated by a simple common-sense linguistic description had to be identified by resorting to a mix of categorization strategies. Compared to human-level categorization, the obtained results suggest that our proposal can be helpful in extending the representational and reasoning conceptual capabilities of standard cognitive artificial systems.

At each node of the search tree, Branch and Bound solvers for Max-SAT compute the lower bound (LB) by estimating the number of disjoint inconsistent subsets (IS) of the formula. IS are detected thanks to unit propagation (UP) then transformed by max-resolution to ensure that they are counted only once. However, it has been observed experimentally that the max-resolution transformations impact the capability of UP to detect further IS. Consequently, few transformations are learned and the LB computation is redundant. In this paper, we study the effect of the transformations on the UP mechanism. We introduce the notion of UP-resiliency of a transformation, which quantifies its impact on UP. It provides, from a theoretical point of view, an explanation to the empirical efficiency of the learning scheme developed in the last ten years. The experimental results we present give evidences of UP-resiliency relevance and insights on the behavior of the learning mechanism.

Exploiting parallelism is a key strategy for speeding up computation. However, on hard combinatorial problems, such a strategy has been surprisingly challenging due to the intricate variable interactions.We introduce a novel way in which parallelism can be used to exploit hidden structure of hard combinatorial problems. Our approach complements divide-and-conquer and portfolio approaches. We evaluate our approach on the minimum set basis problem: a core combinatorial problem with a range of applications in optimization, machine learning, and system security. We also highlight a novel sustainability related application, concerning the discovery of new materials for renewable energy sources such as improved fuel cell catalysts. In our approach, a large number of smaller sub-problems are identified and solved concurrently. We then aggregate the information from those solutions, and use this information to initialize the search of a global, complete solver. We show that this strategy leads to a substantial speed-up over a sequential approach, since the aggregated sub-problem solution information often provides key structural insights to the complete solver. Our approach also greatly outperforms state-of-the-art incomplete solvers in terms of solution quality. Our work opens up a novel angle for using parallelism to solve hard combinatorial problems.

We propose a novel class of Sequential Monte Carlo (SMC) algorithms, appropriate for inference in probabilistic graphical models. This class of algorithms adopts a divide-and-conquer approach based upon an auxiliary tree-structured decomposition of the model of interest, turning the overall inferential task into a collection of recursively solved sub-problems. The proposed method is applicable to a broad class of probabilistic graphical models, including models with loops. Unlike a standard SMC sampler, the proposed Divide-and-Conquer SMC employs multiple independent populations of weighted particles, which are resampled, merged, and propagated as the method progresses. We illustrate empirically that this approach can outperform standard methods in terms of the accuracy of the posterior expectation and marginal likelihood approximations. Divide-and-Conquer SMC also opens up novel parallel implementation options and the possibility of concentrating the computational effort on the most challenging sub-problems. We demonstrate its performance on a Markov random field and on a hierarchical logistic regression problem.

The Heuristic Search community has been concentrating much effort during the last decades in solving more and more efficiently the SHORTEST PATH problem (SPP). As a result, a valuable body of scientific results has been produced, mostly in the form of heuristics and search algorithms. However, not much attention has been given to other problems even if they result from slight variations of the typical problems addressed by the community. Furthermore, other communities attempt at solving hard combinatorial problems which might be well solved with heuristic search. In this paper, an attempt is presented to introduce a preliminary selection of relevant problems that goes well beyond the classical SPP.

The traditional focus of combinatorial search research is to speed up the search algorithm. An alternative, however, is to create a sparser representation of the search space. This relates to the idea of spanners from graph theory. These are subgraphs which retain paths between any two vertices of the original graph while guaranteeing a maximum stretch in path length. In practice, the path degradation of graph spanners is significantly smaller than the theoretical bound. Even so, expected path degradation of graph spanners is typically not studied. This work focuses on grid path-finding to propose an algorithm that constructs a grid spanner, where analysis for the obstacle-free case shows that significant performance gains can be achieved with a small decrease in expected path quality. This is an important first step towards studying the expected performance of spanners. Experiments on game maps show that expected path quality with obstacles is only sometimes marginally lower than that in the obstacle-free case and that a significant reduction in the size of the search space can be achieved.

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n -dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.

In the last decade the emphasis on improving the operational performance of domain independent automated planners has been in developing complex techniques which merge a range of different strategies. This quest for operational advantage, driven by the regular international planning competitions, has not made it easy to study, understand and predict what combinations of techniques will have what effect on a planner’s behaviour in a particular application domain. In this paper, we consider two machine learning techniques for planner performance improvement, and exploit a modular approach to their combination in order to facilitate the analysis of the impact of each individual component. We believe this can contribute to the development of more transparent planning engines, which are designed using modular, interchangeable, and well-founded components. Specifically, we combined two previously unrelated learning techniques, entanglements and relational decision trees, to guide a “vanilla” search algorithm. We report on a large experimental analysis which demonstrates the effectiveness of the approach in terms of performance improvements, resulting in a very competitive planning configuration despite the use of a more modular and transparent architecture. This gives insights on the strengths and weaknesses of the considered approaches, that will help their future exploitation.