|
Abstraction for model checking multi-agent systems
Conghua ZHOU, Bo SUN, Zhifeng LIU
Front Comput Sci Chin. 2011, 5 (1): 14-25.
https://doi.org/10.1007/s11704-010-0358-y
Model checking multi-agent systems (MAS) always suffers from the state explosion problem. In this paper we focus on an abstraction technique which is one of the major methods for overcoming this problem. For a multi-agent system, we present a novel abstraction procedure which reduces the state space by collapsing the global states in the system. The abstraction is automatically computed according to the property to be verified. The resulting abstract system simulates the concrete system, while the universal temporal epistemic properties are preserved. Our abstraction is an over-approximation. If some universal temporal epistemic property is not satisfied, then we need to identify spurious counterexamples. We further show how to reduce complex counterexamples to simple structures, i.e., paths and loops, such that the counterexamples can be checked and the abstraction can be refined efficiently. Finally, we illustrate the abstraction technique with a card game.
Figures and Tables |
References |
Related Articles |
Metrics
|
|
Indeterminacy-aware service selection for reliable service composition
Xiaoqin FAN, Xianwen FANG, Zhijun DING
Front Comput Sci Chin. 2011, 5 (1): 26-36.
https://doi.org/10.1007/s11704-010-0077-4
With the development of Internet and Web service technology, Web service composition has been an effective way to construct software applications; service selection is the crucial element in the composition process. However, the existing selection methods mostly generate static plans since they neglect the inherent stochastic and dynamic nature of Web services. As a result, Web service composition often inevitably terminates with failure. An indeterminacy-aware service selection algorithm based on an improved Markov decision process (IMDP) has been designed for reliable service composition, but it suffers from higher computation complexity. Therefore, an efficient method is proposed, which can reduce the computation cost by converting the service selection problem based on IMDP into solving a nonhomogeneous linear equation set. Experimental results demonstrate the success rate of service composition has been improved greatly, whilst also reducing computation cost.
Figures and Tables |
References |
Related Articles |
Metrics
|
|
Behavior pattern extraction by trajectory analysis
Jia WEN, Chao LI, Zhang XIONG
Front Comput Sci Chin. 2011, 5 (1): 37-44.
https://doi.org/10.1007/s11704-010-0074-7
Trajectory clustering and behavior pattern extraction are the foundations of research into activity perception of objects in motion. In this paper, a new framework is proposed to extract behavior patterns through trajectory analysis. Firstly, we introduce directional trimmed mean distance (DTMD), a novel method used to measure similarity between trajectories. DTMD has the attributes of anti-noise, self-adaptation and the capability to determine the direction for each trajectory. Secondly, we use a hierarchical clustering algorithm to cluster trajectories. We design a length-weighted linkage rule to enhance the accuracy of trajectory clustering and reduce problems associated with incomplete trajectories. Thirdly, the motion model parameters are estimated for each trajectory’s classification, and behavior patterns for trajectories are extracted. Finally, the difference between normal and abnormal behaviors can be distinguished.
Figures and Tables |
References |
Related Articles |
Metrics
|
|
Fuzzy c-means clustering with non local spatial information for noisy image segmentation
Feng ZHAO, Licheng JIAO, Hanqiang LIU
Front Comput Sci Chin. 2011, 5 (1): 45-56.
https://doi.org/10.1007/s11704-010-0393-8
As an effective image segmentation method, the standard fuzzy c-means (FCM) clustering algorithm is very sensitive to noise in images. Several modified FCM algorithms, using local spatial information, can overcome this problem to some degree. However, when the noise level in the image is high, these algorithms still cannot obtain satisfactory segmentation performance. In this paper, we introduce a non local spatial constraint term into the objective function of FCM and propose a fuzzy c-means clustering algorithm with non local spatial information (FCM_NLS). FCM_NLS can deal more effectively with the image noise and preserve geometrical edges in the image. Performance evaluation experiments on synthetic and real images, especially magnetic resonance (MR) images, show that FCM_NLS is more robust than both the standard FCM and the modified FCM algorithms using local spatial information for noisy image segmentation.
Figures and Tables |
References |
Related Articles |
Metrics
|
|
A fast algorithm for computing moments of gray images based on NAM and extended shading approach
Yunping ZHENG, Mudar SAREM
Front Comput Sci Chin. 2011, 5 (1): 57-65.
https://doi.org/10.1007/s11704-010-0337-3
Computing moments on images is very important in the fields of image processing and pattern recognition. The non-symmetry and anti-packing model (NAM) is a general pattern representation model that has been developed to help design some efficient image representation methods. In this paper, inspired by the idea of computing moments based on the S-Tree coding (STC) representation and by using the NAM and extended shading (NAMES) approach, we propose a fast algorithm for computing lower order moments based on the NAMES representation, which takes O(N) time where N is the number of NAM blocks. By taking three idiomatic standard gray images ‘Lena’, ‘F16’, and ‘Peppers’ in the field of image processing as typical test objects, and by comparing our proposed algorithm with the conventional algorithm and the popular STC representation algorithm for computing the lower order moments, the theoretical and experimental results presented in this paper show that the average execution time improvement ratios of the proposed NAMES approach over the STC approach, and also the conventional approach are 26.63%, and 82.57% respectively while maintaining the image quality.
Figures and Tables |
References |
Related Articles |
Metrics
|
|
Soft spectral clustering ensemble applied to image segmentation
Jianhua JIA, Bingxiang LIU, Licheng JIAO
Front Comput Sci Chin. 2011, 5 (1): 66-78.
https://doi.org/10.1007/s11704-010-0161-9
An unsupervised learning algorithm, named soft spectral clustering ensemble (SSCE), is proposed in this paper. Until now many proposed ensemble algorithms cannot be used on image data, even images of a mere 256 × 256 pixels are too expensive in computational cost and storage. The proposed method is suitable for performing image segmentation and can, to some degree, solve some open problems of spectral clustering (SC). In this paper, a random scaling parameter and Nystr?m approximation are applied to generate the individual spectral clusters for ensemble learning. We slightly modify the standard SC algorithm to aquire a soft partition and then map it via a centralized logcontrast transform to relax the constraint of probability data, the sum of which is one. All mapped data are concatenated to form the new features for each instance. Principal component analysis (PCA) is used to reduce the dimension of the new features. The final aggregated result can be achieved by clustering dimension-reduced data. Experimental results, on UCI data and different image types, show that the proposed algorithm is more efficient compared with some existing consensus functions.
Figures and Tables |
References |
Related Articles |
Metrics
|
|
Boosting performance in attack intention recognition by integrating multiple techniques
Hao BAI, Kunsheng WANG, Changzhen HU, Gang ZHANG, Xiaochuan JING
Front Comput Sci Chin. 2011, 5 (1): 109-118.
https://doi.org/10.1007/s11704-010-0321-y
Recognizing attack intention is crucial for security analysis. In recent years, a number of methods for attack intention recognition have been proposed. However, most of these techniques mainly focus on the alerts of an intrusion detection system and use algorithms of low efficiency that mine frequent attack patterns without reconstructing attack paths. In this paper, a novel and effective method is proposed, which integrates several techniques to identify attack intentions. Using this method, a Bayesian-based attack scenario is constructed, where frequent attack patterns are identified using an efficient data-mining algorithm based on frequent patterns. Subsequently, attack paths are rebuilt by re-correlating frequent attack patterns mined in the scenario. The experimental results demonstrate the capability of our method in rebuilding attack paths, recognizing attack intentions as well as in saving system resources. Specifically, to the best of our knowledge, the proposed method is the first to correlate complementary intrusion evidence with frequent pattern mining techniques based on the FP-Growth algorithm to rebuild attack paths and to recognize attack intentions.
Figures and Tables |
References |
Related Articles |
Metrics
|
13 articles
|