Synthesizing robust systems

Systems should not only be correct but also robust in the sense that they behave reasonably in unexpected situations. This article addresses synthesis of robust reactive systems from temporal specifications. Existing methods allow arbitrary behavior if assumptions in the specification are violated. To overcome this, we define two robustness notions, combine them, and show how to enforce them in synthesis. The first notion applies to safety properties: If safety assumptions are violated temporarily, we require that the system recovers to normal operation with as few errors as possible. The second notion requires that, if liveness assumptions are violated, as many guarantees as possible should be fulfilled nevertheless. We present a synthesis procedure achieving this for the important class of GR(1) specifications, and establish complexity bounds. We also present an implementation of a special case of robustness, and show experimental results.     

A survey of stochastic ω-regular games

We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.     

A new social and momentum component adaptive PSO algorithm for image segmentation

In this paper, we present a new variant of Particle Swarm Optimization (PSO) for image segmentation using optimal multi-level thresholding. Some objective functions which are very efficient for bi-level thresholding purpose are not suitable for multi-level thresholding due to the exponential growth of computational complexity. The present paper also proposes an iterative scheme that is practically more suitable for obtaining initial values of candidate multilevel thresholds. This self iterative scheme is proposed to find the suitable number of thresholds that should be used to segment an image. This iterative scheme is based on the well known Otsu’s method, which shows a linear growth of computational complexity. The thresholds resulting from the iterative scheme are taken as initial thresholds and the particles are created randomly around these thresholds, for the proposed PSO variant. The proposed PSO algorithm makes a new contribution in adapting ‘social’ and ‘momentum’ components of the velocity equation for particle move updates. The proposed segmentation method is employed for four benchmark images and the performances obtained outperform results obtained with well known methods, like Gaussian-smoothing method (Lim, Y. K., & Lee, S. U. (1990). On the color image segmentation algorithm based on the thresholding and the fuzzy c-means techniques. Pattern Recognition, 23, 935–952; Tsai, D. M. (1995). A fast thresholding selection procedure for multimodal and unimodal histograms. Pattern Recognition Letters, 16, 653–666), Symmetry-duality method (Yin, P. Y., & Chen, L. H. (1993). New method for multilevel thresholding using the symmetry and duality of the histogram. Journal of Electronics and Imaging, 2, 337–344), GA-based algorithm (Yin, P. -Y. (1999). A fast scheme for optimal thresholding using genetic algorithms. Signal Processing, 72, 85–95) and the basic PSO variant employing linearly decreasing inertia weight factor.     

Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization

The particle swarm optimization (PSO) is a relatively new generation of combinatorial metaheuristic algorithms which is based on a metaphor of social interaction, namely bird flocking or fish schooling. Although the algorithm has shown some important advances by providing high speed of convergence in specific problems it has also been reported that the algorithm has a tendency to get stuck in a near optimal solution and may find it difficult to improve solution accuracy by fine tuning. The present paper proposes a new variation of PSO model where we propose a new method of introducing nonlinear variation of inertia weight along with a particle's old velocity to improve the speed of convergence as well as fine tune the search in the multidimensional space. The paper also presents a new method of determining and setting a complete set of free parameters for any given problem, saving the user from a tedious trial and error based approach to determine them for each specific problem. The performance of the proposed PSO model, along with the fixed set of free parameters, is amply demonstrated by applying it for several benchmark problems and comparing it with several competing popular PSO and non-PSO combinatorial metaheuristic algorithms.     

Strategy logic

We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL¹, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula).     

An application of PSO technique for harmonic elimination in a PWM inverter

Harmonic elimination problem in PWM inverter is treated as an optimization problem and solved using particle swarm optimization (PSO) technique. The derived equation for computation of total harmonic distortion (THD) of the output voltage of PWM inverter is used as the objective function in the PSO algorithm. The objective function is minimized to contribute the minimum THD in the voltage waveform and the corresponding switching angles are computed. The method is applied to investigate the switching patterns of both unipolar and bipolar case. While minimizing the objective function, the individual selected harmonics like 5th, 7th, 11th and 13th can be controlled within the allowable limits by incorporating the constraints in the PSO algorithm. The results of the unipolar case using five switching angles are compared with that of a recently reported work and it is observed that the proposed method is effective in reducing the voltage THD in a wide range of modulation index. The simulated results are also validated through suitable experiments.     

Reduced complexity two stage vector quantization

We address the issue of complexity for vector quantization (VQ) of wide-band speech LSF (line spectrum frequency) parameters. The recently proposed switched split VQ (SSVQ) method provides better rate–distortion (R/D) performance than the traditional split VQ (SVQ) method, even at the requirement of lower computational complexity, but at the expense of much higher memory. We develop the two stage SVQ (TsSVQ) method, by which we gain both the memory and computational advantages and still retain good R/D performance. The proposed TsSVQ method uses a full dimensional quantizer in its first stage for exploiting all the higher dimensional coding advantages and then, uses an SVQ method for quantizing the residual vector in the second stage so as to reduce the complexity. We also develop a transform domain residual coding method in this two stage architecture such that it further reduces the computational complexity. To design an effective residual codebook in the second stage, variance normalization of Voronoi regions is carried out which leads to the design of two new methods, referred to as normalized two stage SVQ (NTsSVQ) and normalized two stage transform domain SVQ (NTsTrSVQ). These two new methods have complimentary strengths and hence, they are combined in a switched VQ mode which leads to the further improvement in R/D performance, but retaining the low complexity requirement. We evaluate the performances of new methods for wide-band speech LSF parameter quantization and show their advantages over established SVQ and SSVQ methods.     

User-input driven QoS management in ad hoc networks

Though the network quality-of-service (QoS) metrics are defined in terms of technical parameters (e.g., delay, jitter, bandwidth), they are rather subjective when it comes to the end user. Oftentimes, the end user finds it difficult to express his desired QoS in such technical parameters, though he has a fair idea of what QoS he desires. In this paper, we show how translation functions can be devised and used to translate the user inputs to networking parameters that are used by various layers of the protocol stack. In particular, we consider an ad hoc network and show an interface design that uses translation functions to map user supplied inputs to parameters at the medium access control (MAC) and routing layers. These parameters, in turn, choose the right strategies that particular layer functionality can adopt, such that the QoS desired by the user is achieved. We also compute the associated costs due to the different strategies adopted. We implement the interface on ns-2 and conduct simulation experiments with randomly scattered IEEE 802.11 enabled nodes. Results show the functionality of the interface and demonstrate how delay, throughput, and network lifetime are affected when the end user seeks different levels of QoS.     

A new fuzzy rule based algorithm for estimating software faults in early phase of development

Estimation of reliability and the number of faults present in software in its early development phase, i.e., requirement analysis or design phase is very beneficial for developing reliable software with optimal cost. Software reliability prediction in early phase of development is highly desirable to the stake holders, software developers, managers and end users. Since, the failure data are unavailable in early phase of software development, different reliability relevant software metrics and similar project data are used to develop models for early software fault prediction. The proposed model uses the linguistic values of software metrics in fuzzy inference system to predict the total number of faults present in software in its requirement analysis phase. Considering specific target reliability, weightage of each input software metrics and size of software, an algorithm has been proposed here for developing general fuzzy rule base. For model validation of the proposed model, 20 real software project data have been used here. The linguistic values from four software metrics related to requirement analysis phase have been considered as model inputs. The performance of the proposed model has been compared with two existing early software fault prediction models.