5373454
A Logic of Limited Belief for Reasoning with Disjunctive Information
The goal of producing a general purpose, semantically motivated, and computationally tractable deductive reasoning service remains surprisingly elusive. By and large, approaches that come equipped with a perspicuous model theory either result in reasoners that are too limited from a practical point of view or fall off the computational cliff. 
 
In this paper, we propose a new logic of belief called SL which lies between the two extremes. We show that query evaluation based on SL for a certain form of knowledge bases with disjunctive information is tractable in the propositional case and decidable in the first-order case. Also, we present a sound and complete axiomatization for propositional SL.
7009361
Tractable Reasoning in First-Order Knowledge Bases with Disjunctive Information
This work proposes a new methodology for establishing the tractability of a reasoning service that deals with expressive first-order knowledge bases. It consists of defining a logic that is weaker than classical logic and that has two properties: first, the entailment problem can be reduced to the model checking problem for a small number of characteristic models; and second, the model checking problem itself is tractable for formulas with a bounded number of variables. We show this methodology in action for the reasoning service previously proposed by Liu, Lakemeyer and Levesque for dealing with disjunctive information. They show that their reasoning is tractable in the propositional case and decidable in the first-order case. Here we apply the methodology and prove that the reasoning is also tractable in the first-order case if the knowledge base and the query both use a bounded number of variables.
16346812
A hoare-style proof system for robot programs
Golog is a situation calculus-based logic programming language for high-level robotic control, This paper explores Hoare's axiomatic approach to program verification in the Golog context. We present a novel Hoare-style proof system for partial correctness of Golog programs. We prove total soundness of the proof system, and relative completeness of a subsystem of it for procedureless Golog programs. Examples are given to illustrate the use of the proof system.
117877852
A Tractability Result for Reasoning with Incomplete First-Order Knowledge Bases
In previous work, Levesque proposed an extension to classical databases that would allow for a certain form of incomplete first-order knowledge. Since this extension was sufficient to make full logical deduction undecidable, he also proposed an alternative reasoning scheme with desirable logical properties. He also claimed (without proof) that this reasoning could be implemented efficiently using database techniques such as projections and joins. In this paper, we substantiate this claim and show how to adapt a bottom-up database query evaluation algorithm for this purpose, thus obtaining a tractability result comparable to those that exist for databases.
6127426
A Complete Axiomatization for Blocks World
Blocks World (BW) has been one of the most popular model domains in AI history. However, there has not been serious work on axiomatizing the state constraints of BW and giving justification for its soundness and completeness. In this paper, we model a state of BW by a finite collection of finite chains, and call the theory of all these structures BW theory. We present seven simple axioms and prove that their consequences are precisely BW theory, using Ehrenfeucht-Fräıssé games. We give a simple decision procedure for the theory which can be implemented in exponential space, and prove that every decision procedure (even if nondeterministic) for the theory must take at least exponential time. We also give a characterization of all nonstandard models for the theory. Finally, we present an expansion of BW theory and show that it admits elimination of quantifiers. As a result, we are able to characterize all definable predicates in BW theory, and give simple examples of undefinable predicates.
8135119
Tractable Reasoning with Incomplete First-Order Knowledge in Dynamic Systems with Context-Dependent Actions
A basic reasoning problem in dynamic systems is the projection problem: determine if a formula holds after a sequence of actions has been performed. In this paper, we propose a tractable solution to the projection problem in the presence of incomplete first-order knowledge and contextdependent actions. Our solution is based on a type of progression, that is, we progress the initial knowledge base (KB) wrt the action sequence and answer the query against the resulting KB. The form of reasoning we propose is always logically sound and is also logically complete when the query is in a certain normal form and the agent has complete knowledge about the context of any context-dependent actions.
6564204
A robust method for shape-based 3D model retrieval
Proliferation of 3D models necessitates developing efficient methods for indexing or retrieving the models in a large database. Many previous methods for this purpose defined functions on concentric spheres as approximation of 3D geometry for spherical harmonic transform (SHT). In this paper, we point out that this is not robust as the surface of a model may shift between different shells under perturbation, and multi-layer of surfaces may exist in one shell, making the function definition ambiguous. To solve these problems, we propose a method to characterize 3D shape using delta functions. Then, spherical functions are defined by sampling in the frequency domain of the delta functions for SHT. By doing so, our method can support retrieval with controllable acuity, which benefits wider range of applications and facilitates customization to different users. Experiments have shown that our method is more robust than previous approaches.
18654744
Evaluating collinearity constraint for automatic range image registration
While most of the existing range image registration algorithms either have to extract and match structural (geometric or optical) features or have to estimate the motion parameters of interest from outliers corrupted point correspondence data for the elimination of false matches in the process of image registration, the registration error and the collinearity error derived directly from the traditional closest point criterion are also capable of doing the same job. However, the latter has an advantage of easy implementation. The purpose of this paper is to investigate which definition of collinearity is more accurate and stable in eliminating false matches inevitably introduced by the closest point criterion. The experiments based on real images show the advantages and disadvantages of different definitions of collinearity.
7923791
Discontinuity-Based Simplification of Free Form Surface From a Range Image
This paper improves an existing method for more accurate simplification of free form surface represented as dense points. The main improvement lies in two aspects: one is the introduction of a novel transformation of curvatures, the other is to propose sampling points using both curvature information and curvature variation information. The experimental results based on real images show that the original object surface has been better approximated and the majority of the surface discontinuities have been better preserved with considerably few sampled (5%) data points
29553031
S-Club: an overlay based efficient service discovery mechanism in CROWN grid
Information service plays a key role in grid system, handles resource discovery and management process. Employing existing information service architectures suffers from poor scalability, long search response time, and large traffic overhead. In this paper, we propose a service club mechanism, called S-Club, for efficient service discovery. In S-Club, an overlay based on existing GIS mesh network of CROWN is built, so that GISs are organized as service clubs. Each club serves for a certain type of service while each GIS may join one or more clubs. S-Club is adopted in RLDS as the information service in CROWN grid and the performance of S-Club is evaluated by comprehensive simulations. The results show that S-Club scheme significantly improves search performance and outperforms existing approaches
17779261
A Framework for Incorporating Class Priors into Discriminative Classification
Discriminative and generative methods provide two distinct approaches to machine learning classification. One advantage of generative approaches is that they naturally model the prior class distributions. In contrast, discriminative approaches directly model the conditional distribution of class given inputs, so the class priors are only implicitly obtained if the input density is known. In this paper, we propose a framework for incorporating class prior proportions into discriminative methods in order to improve their classification accuracy. The basic idea is to enforce that the distribution of class labels predicted on the test data by the discriminative model is consistent with the class priors. Therefore, the discriminative model has to not only fit the training data well but also predict class labels for the test data that are consistent with the class priors. Experiments on five different UCI datasets and one image database show that this framework is effective in improving the classification accuracy when the training data and the test data come from the same class proportions, even if the test data does not have exactly the same feature distribution as the training data.