Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems.  We investigate parallel algorithms for optimal sequential planning, with an emphasis on exploiting distributed memory computing clusters.  In particular, we focus on an approach which distributes and schedules work among processors based on a hash function of the search state.  We use this approach to parallelize the A* algorithm in the optimal sequential version of the Fast Downward planner.  The scaling behavior of the algorithm is evaluated experimentally on clusters using up to 128 processors, a significant increase compared to previous work in parallelizing planners.  We show that this approach scales well, allowing us to effectively utilize the large amount of distributed memory to optimally solve problems which require hundreds of gigabytes of RAM to solve. We also show that this approach scales  well for a single, shared-memory multicore machine.

Explicit abstraction heuristics, notably pattern-database and merge-and-shrink heuristics, are employed by some state-of-the-art optimal heuristic-search planners. The major limitation of these abstraction heuristics is that the size of the abstract space has to be bounded by a (large) constant. Targeting this issue, Katz and Domshlak (2008b) introduced structural, and in particular fork-decomposition, abstractions, in which the planning task is abstracted by an instance of a tractable fragment of optimal planning. At first view, however, the lunch was not free. Some of the power of the explicit abstraction heuristics comes from pre-computing the heuristic function offline, and then determine h(s) for each evaluated state s by a very fast lookup in a "database." In contrast, fork-decomposition offer a poly-time, yet far from being fast, computation.   In this contribution, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. Specifically, we show that an equivalent of the explicit abstractions' notion of "database" exists for the fork-decomposition abstractions as well, and this despite of their exponential-size abstract spaces. Experimentally, we show that heuristic search with such "databased" fork-decomposition heuristics favorably competes with the state-of-the-art of optimal planning.

Real-world automated reasoning systems must contend with inconsistencies and the vast amount of information stored in relational databases.  In this paper, we introduce compilation techniques for inconsistency-tolerant reasoning over the combination of classical logic and a relational database.  Our resolution-based algorithms address a quantifier-free, function-free fragment of first-order logic while leveraging off-the-shelf database technology for all data-intensive computation.

Pattern Databases (PDBs) are the most common form of memory-based heuristics, and they have been widely used in a variety of permutation puzzles and other domains. We explore the true-distance heuristics (TDHs) (also appeared in  (Sturtevant et al. 2009)) which are a different form of memory-based heuristics, designed to work in problem states where there isn't a fixed goal state. Unlike PDBs, which build a heuristic based on distances in an abstract state space, TDHs store distances which are computed in the actual state space. We look in detail at how TDHs work, providing both theoretical and experimental motivation for their use.

Given a system design (SD), a key task is to optimize this design to reduce the probability of catastrophic failures. We consider the task of redesigning an SD to minimize the probability of particular faults by introducing components selected from a component library. We have implemented a General Redesign Engine (GRE), which uses model-based reasoning techniques and Boolean functional synthesis from component libraries, to automate redesign for combinational circuits. For a significant subset of observations leading to catastrophic (forbidden) modes we demonstrate that GRE trades off redesign cost for increased fault tolerance, and shows a significant advantage compared to the Triple-Modular Redundancy (TMR) method. Our algorithm has a wide application in AI, including automated software and hardware design, error detection, reconfiguration and recovery, and modular robotics.

In this paper, we investigate knowledge reasoning within a simple framework called knowledge structure. We use variable forgetting as a basic operation for one agent to reason about its own or other agents\' knowledge. In our framework, two notions namely agents\' observable variables and the weakest sufficient condition play important roles in knowledge reasoning. Given a background knowledge base and a set of observable variables for each agent, we show that the notion of an agent knowing a formula can be defined as a weakest sufficient condition of the formula under background knowledge base. Moreover, we show how to capture the notion of common knowledge by using a generalized notion of weakest sufficient condition. Also, we show that public announcement operator can be conveniently dealt with via our notion of knowledge structure. Further, we explore the computational complexity of the problem whether an epistemic formula is realized in a knowledge structure. In the general case, this problem is PSPACE-hard; however, for some interesting subcases, it can be reduced to co-NP. Finally, we discuss possible applications of our framework in some interesting domains such as the automated analysis of the well-known muddy children puzzle and the verification of the revised Needham-Schroeder protocol. We believe that there are many scenarios where the natural presentation of the available information about knowledge is under the form of a knowledge structure. What makes it valuable compared with the corresponding multi-agent S5 Kripke structure is that it can be much more succinct.

In this paper we describe the application of a novel learning and problem solving architecture to the domain of airspace management, where multiple requests for the use of airspace need to be reconciled and managed automatically. The key feature of our "Generalized Integrated Learning Architecture" (GILA) is a set of integrated learning and reasoning (ILR) systems coordinated by a central meta-reasoning executive (MRE). Each ILR learns independently from the same training example and contributes to problem-solving in concert with other ILRs as directed by the MRE. Formal evaluations show that our system performs as well as or better than humans after learning from the same training data. Further, GILA outperforms any individual ILR run in isolation, thus demonstrating the power of the ensemble architecture for learning and problem solving.

This paper introduces the challenge of digital preservation in the   area of engineering design and manufacturing and presents a   methodology to apply knowledge representation and semantic   techniques to develop Digital Engineering Archives.  This work   is part of an ongoing, multi-university, effort to create   Cyber-Infrastructure-Based Engineering Repositories for   Undergraduates (CIBER-U) to support engineering design education.   The technical approach is to use knowledge representation techniques   to create formal models of engineering data elements, workflows and   processes.  With these formal engineering knowledge and processes   can be captured and preserved with some guarantee of long-term   interpretability.  The paper presents examples of how the techniques   can be used to encode specific engineering information     packages and workflows.  These techniques are being integrated   into a semantic Wiki that supports the CIBER-U engineering education   activities across nine universities and involving over 3,500   students since 2006.

Self-organizing maps can be used to implement an associative memory for an intelligent system that dynamically learns about new high-level domains over time. SOMs are an attractive option for implementing associative memory: they are fast, easily parallelized, and digest a stream of incoming data into a topographically organized collection of models where more frequent classes of data are represented by higher-resolution collections of models. Typically, the distribution of models in an SOM, once developed, remains fairly stable, but developing expertise in a new high-level domain requires altering the allocation of models. We use a mixture of analysis and empirical studies to characterize the behavior of SOMs for high-level associative memory, finding that new high-resolution collections of models develop quickly. High-resolution areas of the SOM decay rapidly unless actively refreshed, but in a large SOM, the ratio between growth rate and decay rate may be high enough to support both fast learning and long-term memory.

In many real-world planning scenarios, the users are interested in optimizing multiple objectives (such as makespan and execution cost), but are unable to express their exact tradeoff between those objectives. When a planner encounters such partial preference models, rather than look for a single optimal plan, it needs to present the pareto set of plans and let the user choose from them. This idea of presenting the full pareto set is fraught with both computational and user-interface challenges. To make it practical, we propose the approach of finding a representative subset of the pareto set. We measure the quality of this representative set using the Integrated Convex Preference (ICP) model, originally developed in the OR community. We implement several heuristic approaches based on the Metric-LPG planner to find a good solution set according to this measure. We present empirical results demonstrating the promise of our approach.