Volume 20, 2001, No. 5

On Different Models for Generating Random SAT Problems

P. JANICIC, N. DEDIC, G. TERZIC   Abstract In the last decade a lot of effort has been invested into both theoretical and experimental analysis of sat phase transition. However, a deep theoretical understanding of this phenomenon is still lacking. Besides, many of experimental results are based on some assumptions that are not supported theoretically. In this paper we introduce the notion of sat--equivalence and we prove that some restrictions often used in sat experiments don't make an impact on location of a crossover point. We consider several fixed and random clause length sat models and relation between them. We also discuss one new sat model and report on a detected phase transition for it.

 

Improved Reasoning About Infinity Using Qualitative Simulation

A. C. C. SAY   Abstract The AI technique of qualitative simulation, enabling the representation and use of incomplete knowledge, is a useful mathematical tool, especially for the analysis, design, and diagnosis of dynamic systems. One desirable property of qualitative simulators is their ability to handle infinite ``values'' explicitly, leading to formal predictions about asymptotic behavior. We present two modifications to the qualitative simulation algorithm QSIM, which improve the technique's performance in reasoning tasks involving infinite values and infinite time. The first modification corrects an error which causes the algorithm to miss certain real solutions of the simulated equation. The second modification augments the temporal attribute computation routine, and results in better identification of infinite time intervals by the algorithm. This, in turn, helps our modified algorithm to successfully eliminate some additional inconsistent predictions from its output set. We show that several famous qualitative physics problems are handled with increased predictive accuracy by the new algorithm.

 

Optimizing the Number of Learning Cycles in the Design of Radial Basis Neural Networks Using a Multi-Agent System

J. M. MOLINA, I. M. GALVAN, J. M. VALLS, A. LEAL   Abstract Radial Basis Neural (RBN) network has the power of the universal approximation function and the convergence of those networks is very fast compared to multilayer feedforward neural networks. However, how to determine the architecture of the RBN networks to solve a given problem is not straightforward. In addition, the number of hidden units allocated in an RBN network seems to be a critical factor in the performance of these networks. In this work, the design of RBN network is based on the cooperation of n+m agents: n RBN agents and m manager agents. The n+m agents are organized in a Multi-agent System. The training process is distributed among the n RBN agents, each one with a different number of neurons. Each agent executes a number of training cycles, a stage, when the manager decides about that is the best RBN agent and sends it the corresponding message. The m manager agents have in charge to control the evolution of each problem. Each manager agent controls one problem. Manager agents govern the whole process; each one decides about the best RBN agent in each stage for each problem. The results show that the proposed method is able to find the most adequate RBN network architecture. In addition, a reduction in the number of training cycles is obtained with the proposed Multi-agent strategy instead of sequential strategy.

 

A New Robust Fundamental Matrix Estimation Based on Genetic Algorithm

M. Hu, B. Yuan, X. Tang M. HU, B. YUAN, X. TANG   Abstract Fundamental matrix, the key to many problems of computer vision, encapsulates all the information on camera motion and internal parameters available from image feature correspondences between two views. In this paper, we present a new approach based on genetic algorithm to estimate fundamental matrix, which uses a minimum number of corresponding point (seven points) as a subset for fundamental matrix estimation and can eventually find the near-optimal solution without the need of initial guesses. Results from our extensive study using both synthetic data and real images demonstrate the excellent performance of the proposed technique in terms of robust, accuracy and convergence.

 

Volume 20, 2001, No. 5