Bottom-up pro v ers prot from strong redundan y on trol but suer from the la k of goal-orien tation, whereas top-do wn pro v ers are goal-orien ted but often ha v ew eak al uli when their pro of lengths are onsidered. In order to in tegrate b oth approa hes, w e try to a hiev e o op eration b et w een a top-do wn and a b ottom-up pro v er in t w o dieren tw a ys: The rst te hnique aims at supp orting a b ottom-up with a top-do wn pro v er. A top-do wn pro v er generates subgoal lauses, they are then pro essed b y a b ottom-up pro v er. The se ond te hnique deals with the use of b ottom-up generated lemmas in a top-do wn pro v er.W e apply our on ept to the areas of mo del elimination and sup erp osition. W e dis uss the abilit y of our te hniques to shorten pro ofs as w ell as to reorder the sear h spa e in anappropriate manner. In tro du tion Automated dedu tion is at its lo w est lev el a sear h problem that spans h uge sear h spa es. In the past man y dieren t al uli ha v e b een dev elop ed in order to op e with problems from the area of automated theorem pro ving. Essen tially, for rst-order theorem pro ving t w o main paradigms for al uli are in use: T op-down al uli lik e mo del elimination (ME, Lo v eland, 1968, 1978) attempt to re ursiv ely break do wn and transform a goal in to subgoals that an nally b e pro v en immediately with the axioms or with assumptions madeduring the pro of. When omparing results of v arious pro v ers (e.g., Sut lie & Suttner, 1997) it is ob vious that pro v ers based on dieren t paradigms often b eha v e quite dieren tly . There are problems where b ottom-up theorem pro v ers p erform onsiderably w ell, but top-do wn pro v ers p o orly,and vi e v ersa. The main reason for this is that b ottom-up pro v ers often suer from the la k of goal-orien tation of their sear h, but prot from their strong redundan y on trol me hanisms. Therefore, a topi that has ome in to the fo us of resear h is the in tegration of b oth approa hes. It is also p ossible to mo dify al uli or pro v ers whi h w ork a ording to one paradigm so as to in tro du e asp e ts of the other paradigm in to it. This, ho w ev er, requires a lot of implemen tational eort to mo dify the pro v ers, whereas our approa h do es not require hanges of the pro v ers but only hanges of their input. Information that is w ell-suited for impro ving the p erforman e of top-do wn pro v ers are lemmas dedu ed b y b ottom-up pro v ers. These lemmas are added to the input of a top-do wn pro v er and an help to shorten the pro of length b y immediately solving subgoals. Normally, the emplo y ed pro of pro edures an signi an tly prot from the pro of length redu tion obtained. This means that an un b ounded use of b ottom-up generated lemmas without using te hniques for ho osing only r elevant lemmas (i.e.

The implementation is based on two insights: that many of the graph construction operations can be implemented as bit-level logical operations on bit vectors, and that the graph should not be explicitly constructed beyond the x point. A more detailed discussion of the competition, from the competitors' point of view, is in preparation. First, we observe that action pre-and post-conditions can be represented using bit vectors. Checking for mutual exclusion between pairs of actions which directly interact can be implemented using logical operations on these bit vectors. Mutual exclusion (mutex relations) between facts can be implemented in a similar way. Second, we observe that there is no advantage in explicit construction of the graph beyond the stage at which the x point is reached. Since no new facts, actions or mutex relations are added beyond the x point these goal sets can be considered without explicit copying of the fact and action layers. For example, using a heuristic discussed in Section 5.1, Sta In this paper we describe the spike and wave front mechanisms and provide experimental results indicating the performance advantages obtained. The layers correspond to snapshots of possible states at instants on a time line from the initial to the goal state.

Intractable distributions present a common difficulty in inference within the probabilistic knowledge representation framework and variational methods have recently been popular in providing an approximate solution. In this article, we describe a perturbational approach in the form of a cumulant expansion which, to lowest order, recovers the standard Kullback-Leibler variational bound. Higher-order terms describe corrections on the variational approach without incurring much further computational cost. The relationship to other perturbational approaches such as TAP is also elucidated. We demonstrate the method on a particular class of undirected graphical models, Boltzmann machines, for which our simulation results confirm improved accuracy and enhanced stability during learning.

In default reasoning, usually not all possible ways of resolving conflicts between default rules are acceptable. Criteria expressing acceptable ways of resolving the conflicts may be hardwired in the inference mechanism, for example specificity in inheritance reasoning can be handled this way, or they may be given abstractly as an ordering on the default rules. In this article we investigate formalizations of the latter approach in Reiter's default logic. Our goal is to analyze and compare the computational properties of three such formalizations in terms of their computational complexity: the prioritized default logics of Baader and Hollunder, and Brewka, and a prioritized default logic that is based on lexicographic comparison. The analysis locates the propositional variants of these logics on the second and third levels of the polynomial hierarchy, and identifies the boundary between tractable and intractable inference for restricted classes of prioritized default theories.

The notion of class is ubiquitous in computer science and is central in many formalisms for the representation of structured knowledge used both in knowledge representation and in databases. In this paper we study the basic issues underlying such representation formalisms and single out both their common characteristics and their distinguishing features. Such investigation leads us to propose a unifying framework in which we are able to capture the fundamental aspects of several representation languages used in different contexts. The proposed formalism is expressed in the style of description logics, which have been introduced in knowledge representation as a means to provide a semantically well-founded basis for the structural aspects of knowledge representation systems. The description logic considered in this paper is a subset of first order logic with nice computational characteristics. It is quite expressive and features a novel combination of constructs that has not been studied before. The distinguishing constructs are number restrictions, which generalize existence and functional dependencies, inverse roles, which allow one to refer to the inverse of a relationship, and possibly cyclic assertions, which are necessary for capturing real world domains. We are able to show that it is precisely such combination of constructs that makes our logic powerful enough to model the essential set of features for defining class structures that are common to frame systems, object-oriented database languages, and semantic data models. As a consequence of the established correspondences, several significant extensions of each of the above formalisms become available. The high expressiveness of the logic we propose and the need for capturing the reasoning in different contexts forces us to distinguish between unrestricted and finite model reasoning. A notable feature of our proposal is that reasoning in both cases is decidable. We argue that, by virtue of the high expressive power and of the associated reasoning capabilities on both unrestricted and finite models, our logic provides a common core for class-based representation formalisms.

As planning is applied to larger and richer domains the effort involved in constructing domain descriptions increases and becomes a significant burden on the human application designer. If general planners are to be applied successfully to large and complex domains it is necessary to provide the domain designer with some assistance in building correctly encoded domains. One way of doing this is to provide domain-independent techniques for extracting, from a domain description, knowledge that is implicit in that description and that can assist domain designers in debugging domain descriptions. This knowledge can also be exploited to improve the performance of planners: several researchers have explored the potential of state invariants in speeding up the performance of domain-independent planners. In this paper we describe a process by which state invariants can be extracted from the automatically inferred type structure of a domain. These techniques are being developed for exploitation by STAN, a Graphplan based planner that employs state analysis techniques to enhance its performance.

Cox's well-known theorem justifying the use of probability is shown not to hold in finite domains. The counterexample also suggests that Cox's assumptions are insufficient to prove the result even in infinite domains. The same counterexample is used to disprove a result of Fine on comparative conditional probability.

This paper introduces AntNet, a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems. AntNet's agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms' performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority.

Order of magnitude reasoning - reasoning by rough comparisons of the sizes of quantities - is often called 'back of the envelope calculation', with the implication that the calculations are quick though approximate. This paper exhibits an interesting class of constraint sets in which order of magnitude reasoning is demonstrably fast. Specifically, we present a polynomial-time algorithm that can solve a set of constraints of the form 'Points a and b are much closer together than points c and d.' We prove that this algorithm can be applied if `much closer together' is interpreted either as referring to an infinite difference in scale or as referring to a finite difference in scale, as long as the difference in scale is greater than the number of variables in the constraint set. We also prove that the first-order theory over such constraints is decidable.

Many of the artificial intelligence techniques developed to date rely on heuristic search through large spaces. Unfortunately, the size of these spaces and the corresponding computational effort reduce the applicability of otherwise novel and effective algorithms. A number of parallel and distributed approaches to search have considerably improved the performance of the search process. Our goal is to develop an architecture that automatically selects parallel search strategies for optimal performance on a variety of search problems. In this paper we describe one such architecture realized in the Eureka system, which combines the benefits of many different approaches to parallel heuristic search. Through empirical and theoretical analyses we observe that features of the problem space directly affect the choice of optimal parallel search strategy. We then employ machine learning techniques to select the optimal parallel search strategy for a given problem space. When a new search task is input to the system, Eureka uses features describing the search space and the chosen architecture to automatically select the appropriate search strategy. Eureka has been tested on a MIMD parallel processor, a distributed network of workstations, and a single workstation using multithreading. Results generated from fifteen puzzle problems, robot arm motion problems, artificial search spaces, and planning problems indicate that Eureka outperforms any of the tested strategies used exclusively for all problem instances and is able to greatly reduce the search time for these applications.