CTL model checking of complex systems often suffers from the state-explosion problem. We propose using Symbolic Guided Search to avoid difficult-to-represent sections of the state space and prevent state explosion from occurring.

Image computation is the key step in fixpoint computations that are extensively used in model checking. Two techniques have been used for this step: one based on conjunction of the terms of the transition relation, and the other based on recursive case splitting. We discuss when one technique outperforms the other, and consequently formulate a hybrid approach to image computation. Experimental results show that the hybrid algorithm is much more robust than the “pure” algorithms and outperforms both of them in most cases. Our findings also shed light on the remark of several researchers that splitting is especially effective in approximate reachability analysis.

Techniques for the computation of fixpoints are key to the success of many formal verification algorithms. To be efficient, these techniques must take into account how sets of states are represented. When BDDs are used, this means controlling, directly or indirectly, the size of the BDDs. Traditional fixpoint computations do little to keep BDD sizes small, apart from reordering variables. In this paper, we present a new strategy that attempts to keep the size of the BDDs under control at every stage of the computation. Our contribution includes also new techniques to compute partial images, and to speed up and test convergence. We present experimental results that prove the effectiveness of our strategy by demonstrating up to 40 orders of magnitude improvement in the number of states computed.

Efficient techniques for the manipulation of Binary Decision Diagrams (BDDs) are key to the success of formal verification tools. Recent advances in reachability analysis and model checking algorithms have emphasized the need for efficient algorithms for the approximation and decomposition of BDDs. In this paper we present a new algorithm for approximation and analyze its performance in comparison with existing techniques. We also introduce a new decomposition algorithm that produces balanced partitions. The effectiveness of our contributions is demonstrated by improved results in reachability analysis for some hard problem instances.

Three dimensional vision applications, such as robot vision, require modeling of the relationship between the two-dimensional images and the three-dimensional world. Camera calibration is a process which accurately models this relationship. The calibration procedure determines the geometric parameters of the camera, such as focal length and center of the image. Most of the existing calibration techniques use predefined patterns and a static camera. Recently, a novel calibration technique for computing the focal length and image center, which uses an active camera, has been developed. This technique does not require any predefined patterns or point-to-point correspondence between images-only a set of scenes with some stable edges. It was observed that the algorithms developed for the image center are sensitive to noise and hence unreliable in real situations. This report extends the techniques provided to develop a simpler, yet more robust method for computing the image center.

We address the problem of reachability analysis for large finite state systems. Symbolic techniques have revolutionized reachability analysis but still have limitations in traversing large systems. We present techniques to improve the symbolic breadth-first traversal and compute a lower bound on the reachable states. We identify the problem as one of density during traversal and our techniques seek to improve the same. Our results show a marked improvement on the existing breadth-first traversal methods.

Three dimensional vision applications, such as robot vision, require modelling of the relationship between the 2D images and the 3D world. Camera calibration is a process which accurately models this relationship. The calibration procedure determines the geometric parameters of the camera, such as focal length and center of the image. Most of the existing calibration techniques use predefined patterns and a static camera. Recently, A. Basu (1993) developed a novel calibration technique for computing the focal length and image center which uses an active camera. This technique does not require any predefined patterns or point to point correspondence between images-only a set of scenes with some stable edges. It was observed that the algorithms developed for image center are sensitive to noise and hence unreliable in real situations. The article extends the techniques provided by Basu to develop a simpler, yet more robust method for computing the image center.

Robot calibration is essential to improve the positioning accuracy of robot manipulators. A mathematical (kinematic) model is used to describe the geometric structure of a robot manipulator. Robot calibration procedure involves calculating and improving the values of this model's parameters. The robot calibration technique presented in this paper uses a vision system, to calibrate the kinematic model. For an n-linked robot manipulator, the procedure calibrates one link at a time, starting with the n/sup th/ link by making small movements. The resulting equations are linear, consequently, the algorithms are simple.