An important problem in geometric reasoning is to find the configuration of a collection of geometric bodies so as to satisfy a set of given constraints. Recently, it has been suggested that this problem can be solved efficiently by symbolically reasoning about geometry. This approach, called degrees of freedom analysis, employs a set of specialized routines called plan fragments that specify how to change the configuration of a set of bodies to satisfy a new constraint while preserving existing constraints. A potential drawback, which limits the scalability of this approach, is concerned with the difficulty of writing plan fragments. In this paper we address this limitation by showing how these plan fragments can be automatically synthesized using first principles about geometric bodies, actions, and topology.

Although most scheduling problems are NP-hard, domain specific techniques perform well in practice but are quite expensive to construct. In adaptive problem-solving solving, domain specific knowledge is acquired automatically for a general problem solver with a flexible control architecture. In this approach, a learning system explores a space of possible heuristic methods for one well-suited to the eccentricities of the given domain and problem distribution. In this article, we discuss an application of the approach to scheduling satellite communications. Using problem distributions based on actual mission requirements, our approach identifies strategies that not only decrease the amount of CPU time required to produce schedules, but also increase the percentage of problems that are solvable within computational resource limitations.

Symmetric networks designed for energy minimization such as Boltzman machines and Hopfield nets are frequently investigated for use in optimization, constraint satisfaction and approximation of NP-hard problems. Nevertheless, finding a global solution (i.e., a global minimum for the energy function) is not guaranteed and even a local solution may take an exponential number of steps. We propose an improvement to the standard local activation function used for such networks. The improved algorithm guarantees that a global minimum is found in linear time for tree-like subnetworks. The algorithm, called activate, is uniform and does not assume that the network is tree-like. It can identify tree-like subnetworks even in cyclic topologies (arbitrary networks) and avoid local minima along these trees. For acyclic networks, the algorithm is guaranteed to converge to a global minimum from any initial state of the system (self-stabilization) and remains correct under various types of schedulers. On the negative side, we show that in the presence of cycles, no uniform algorithm exists that guarantees optimality even under a sequential asynchronous scheduler. An asynchronous scheduler can activate only one unit at a time while a synchronous scheduler can activate any number of units in a single time step. In addition, no uniform algorithm exists to optimize even acyclic networks when the scheduler is synchronous. Finally, we show how the algorithm can be improved using the cycle-cutset scheme. The general algorithm, called activate-with-cutset, improves over activate and has some performance guarantees that are related to the size of the network's cycle-cutset.

Many studies have been carried out in order to increase thesearch efficiency of constraint satisfaction problems; among them,some make use of structural properties of the constraintnetwork; others take into account semantic properties of theconstraints, generally assuming that all the constraints possessthe given property. In this paper, we propose a new decompositionmethod benefiting from both semantic properties of functional constraints (not bijective constraints) and structuralproperties of the network; furthermore, not all the constraints needto be functional. We show that under some conditions, the existenceof solutions can be guaranteed. We first characterize a particularsubset of the variables, which we name a root set. We thenintroduce pivot consistency, a new local consistency which is aweak form of path consistency and can be achieved in O(n^2d^2)complexity (instead of O(n^3d^3) for path consistency), and wepresent associated properties; in particular, we show that anyconsistent instantiation of the root set can be linearly extended to a solution, which leads to the presentation of the aforementioned new method for solving by decomposing functional CSPs.

We built a high-speed, digital mean-field Boltzmann chip and SBus board for general problems in constraint satjsfaction and learning. Each chip has 32 neural processors and 4 weight update processors, supporting an arbitrary topology of up to 160 functional neurons. On-chip learning is at a theoretical maximum rate of 3.5 x 108 connection updates/sec;recall is 12000 patterns/sec for typical conditions. The chip's high speed is due to parallel computation of inner products, limited (but adequate) precision for weights and activations (5bits), fast clock (125 MHz), and several design insights.

We built a high-speed, digital mean-field Boltzmann chip and SBus board for general problems in constraint satjsfaction and learning. Each chip has 32 neural processors and 4 weight update processors, supporting an arbitrary topology of up to 160 functional neurons. On-chip learning is at a theoretical maximum rate of 3.5 x 10

In his model, requirements needs, it must be able to represent is done unintentionally; a problem for filling system knowledge solver attempting to solve a gaps also direct explanation generation what these needs are. Ram proposed problem simply stores a trace of its by guiding retrieval and revision representations that include processing without attention to its of explanations during case-based the desired knowledge (possibly partially future relevance. However, Ng's previously explanation construction (Leake specified) and the reason that mentioned studies show that 1992). In the context of analogical the knowledge is sought. Leake for a different class of task, learning mapping, Thagard pointed out that focused on the representation of the goals have a strong effect on the goals, semantic constraints, and syntactic knowledge required to resolve anomalies learning performance of human constraints all affect analogical (which depends on a vocabulary learners. A future question is to identify mapping (Holyoak and Thagard 1989) of anomaly characterization structures the limits of goal-driven processing and the retrieval of potential analogs to describe the information in human learners.

My dissertation concerns the application of constraint-based reasoning to parametric engineering design (Murtagh 1991).1 It deals with the practical application of constraint networks, using automated reasoning to overcome some of the blind spots in conventional iterative design.

These original contributions provide a current sampling of AI approaches to problems of with an analysis program for structural biological significance; they are the first to treat the computational needs of concrete design, and design sessions the biology community hand-in-hand with appropriate advances in artificial were performed to demonstrate intelligence. Focusing on novel technologies and approaches, rather than on how redundant analysis could be proven applications, they cover genetic sequence analysis, protein structure representation and prediction, automated data analysis aids, and simulation avoided and examine different of biological systems. A brief introductory primer on molecular biology and aspects of the reasoning and propagation AI gives computer scientists sufficient background to understand much of the strategies provided. Interval biology discussed in the book.

Computational Intelligence, 9, 268–299.