Admission control for a responsive distributed middleware using decision trees to model run-time parameters

The software in modern systems has become too complex to make accurate predictions about their performance under different configurations. Real-time or even responsiveness requirements cannot be met because it is not possible to perform admission control for new or changing tasks if we cannot tell how their execution affects the other tasks already running. Previously, we proposed a resource-allocation middleware that manages the execution of tasks in a complex distributed system with real-time requirements. The middleware behavior can be modeled depending on the configuration of the tasks running, so that the performance of any given configuration can be calculated. This makes it possible to have admission control in such a system, but the model requires knowledge of run-time parameters. We propose the utilization of machine-learning algorithms to obtain the model parameters, and be able to predict the system performance under any configuration, so that we can provide a full admission control mechanism for complex software systems. In this paper, we present such an admission control mechanism, we measure its accuracy in estimating the parameters of the model, and we evaluate its performance to determine its suitability for a real-time or responsive system.     

Face tracking with automatic model construction

This paper describes an active model with a robust texture model built on-line. The model uses one camera and it is able to operate without active illumination. The texture model is defined by a series of clusters, which are built in a video sequence using previously encountered samples. This model is used to search for the corresponding element in the following frames. An on-line clustering method, named leaderP is described and evaluated on an application of face tracking. A 20-point shape model is used. This model is built offline, and a robust fitting function is used to restrict the position of the points. Our proposal is to serve as one of the stages in a driver monitoring system. To test it, a new set of sequences of drivers recorded outdoors and in a realistic simulator has been compiled. Experimental results for typical outdoor driving scenarios, with frequent head movement, turns and occlusions are presented. Our approach is tested and compared with the Simultaneous Modeling and Tracking (SMAT) [1], and the recently presented Stacked Trimmed Active Shape Model (STASM) [2], and shows better results than SMAT and similar fitting error levels to STASM, with much faster execution times and improved robustness.     

An Analysis of Edge Detection by Using the Jensen-Shannon Divergence

This work constitutes a theoretical study of the edge-detection method by means of the Jensen-Shannon divergence, as proposed by the authors. The overall aim is to establish formally the suitability of the procedure of edge detection in digital images, as a step prior to segmentation. In specific, an analysis is made not only of the properties of the divergence used, but also of the method's sensitivity to the spatial variation, as well as the detection-error risk associated with the operating conditions due to the randomness of the spatial configuration of the pixels. Although the paper deals with the procedure based on the Jensen-Shannon divergence, some problems are also related to other methods based on local detection with a sliding window, and part of the study is focused to noisy and textured images.     

Virtual rights? Property in online game objects and characters

The new industry of Massively Multi-Player Online Role-Playing Games (MMORPGs) brings together two sets of fictions: the interactive stories of shared computer games and the legal devices of intellectual property. In these virtual worlds, scarcity need not exist, but players tend to prefer the competition it creates. This leads to the development of property rights within the game world and players trading real money for virtual objects, ‘land’ and characters. This new phenomenon brings with it familiar legal problems such as theft, fraud and ownership disputes. Game creators also challenge the right of the players to claim ownership outside the game world. The volume and value of the items traded make real money trading an important area of current interest for intellectual property lawyers. Something is being traded, but does it fit neatly into existing conceptions of property rights and who owns it? Analysing the novel problems that result from various theoretical perspectives (utilitarianism, labour-desert theory and personality theory) leads to the conclusion that with time, we will see the development of property rights for players in online games. This connects with a growing understanding that the traditional conception of copyright law dealing with creative work generated by the solitary author is becoming less appropriate in the new creative spaces that information and communications technology brings, where individuals are both consumer and producer. In virtual worlds, new forms of intellectual property, and perhaps even new rights, are taking shape.     

Some Statistical-Estimation Methods for Stochastic Finite-State Transducers

Formal translations constitute a suitable framework for dealing with many problems in pattern recognition and computational linguistics. The application of formal transducers to these areas requires a stochastic extension for dealing with noisy, distorted patterns with high variability. In this paper, some estimation criteria are proposed and developed for the parameter estimation of regular syntax-directed translation schemata. These criteria are: maximum likelihood estimation, minimum conditional entropy estimation and conditional maximum likelihood estimation. The last two criteria were proposed in order to deal with situations when training data is sparse. These criteria take into account the possibility of ambiguity in the translations: i.e., there can be different output strings for a single input string. In this case, the final goal of the stochastic framework is to find the highest probability translation of a given input string. These criteria were tested on a translation task which has a high degree of ambiguity.     

Architectural Methodology Based on Intentional Configuration of Behaviors

Intelligence has been an object of study for a long time. Different architectures try to capture and reproduce these aspects into artificial systems (or agents), but there is still no agreement on how to integrate them into a general framework. With this objective in mind, we propose an architectural methodology based on the idea of intentional configuration of behaviors. Behavior‐producing modules are used as basic control components that are selected and modified dynamically according to the intentions of the agent. These intentions are influenced by the situation perceived, knowledge about the world, and internal variables that monitor the state of the agent. The architectural methodology preserves the emergence of functionality associated with the behavior‐based paradigm in the more abstract levels involved in configuring the behaviors. Validation of this architecture is done using a simulated world for mobile robots, in which the agent must deal with various goals such as managing its energy and its well‐being, finding targets, and acquiring knowledge about its environment. Fuzzy logic, a topologic map learning algorithm, and activation variables with a propagation mechanism are used to implement the architecture for this agent.     

Stochastic automata-based estimators for adaptively compressing files with nonstationary distributions.

This correspondence shows that learning automata techniques, which have been useful in developing weak estimators, can be applied to data compression applications in which the data distributions are nonstationary. The adaptive coding scheme utilizes stochastic learning-based weak estimation techniques to adaptively update the probabilities of the source symbols, and this is done without resorting to either maximum likelihood, Bayesian, or sliding-window methods. The authors have incorporated the estimator in the adaptive Fano coding scheme and in an adaptive entropy-based scheme that "resembles" the well-known arithmetic coding. The empirical results obtained for both of these adaptive methods are obtained on real-life files that possess a fair degree of nonstationarity. From these results, it can be seen that the proposed schemes compress nearly 10% more than their respective adaptive methods that use maximum-likelihood estimator-based estimates.     

Performance lower bounds in stochastic robust and adaptive control

The fundamental issues of capability of robust and adaptive control in dealing with uncertainty are investigated in stochastic systems. It is revealed that to capture the intrinsic limitations of adaptive control, it is necessary to use sup_t types of transient and persistent performance, rather than lim sup_t types which reflect only asymptotic behavior of a system. For clarity and technical tractability, a simple first-order linear time-varying system is employed as a vehicle to explore performance lower bounds of robust and adaptive control. Optimal performances of nominal, robust and adaptive control are explicitly derived and their implications are discussed in an information framework. An adaptive strategy is scrutinized for its achievable performance bounds. The results indicate that intimate interaction and inherent conflict between identification and control result in a certain performance lower bound which does not approach the nominal performance even when the system varies very slowly. Explicit lower bounds are obtained when disturbances are either normally or uniformly distributed     

A comparison of directed formulations for the capacitated minimal spanning tree problem

In this paper, we compare linear integer programming directed formulations for the capacitated minimal spanning tree (CMST) problem. This problem is directly related to network design and consists of finding the cheapest way to link a set of terminals at different locations with a central node (a computer site, for instance). The present work focuses on a single commodity flow formulation presented in [3,4]. This formulation includes two sets of variables and, hence, it also must include coupling constraints between the two sets of variables. These coupling constraints can be defined in several ways. The main result of this work establishes that when the strongest form of the coupling constraints is used in the flow formulation (as in [4]), the equivalent formulation using only theX _ij variables satisfies the so-called multistar constraints. These constraints are shown to be stronger than the weakest form of the generalized subtour breaking constraints and, hence, our result improves on the characterization given in [5] for the flow formulation presented in [4]. For certain parameters, the multistar constraints induce facets of the non-directed CMST polytope (see [2]). We also show that it is not possible to compare the linear relaxations of a formulation that involves the multistar constraints with one that involves the generalized subtour breaking constraints.     

Computational haemodynamics: geometry and non-newtonian modelling using spectral/hp element methods

The increased availability of large scale computational facilities is enabling the use of computational modelling for the treatment of complex problems of industrial interest. Computational haemodynamics is an area where improved computational power and algorithmic development have permitted the application in biomechanics of techniques originally devised for direct numerical simulations in others areas of scientific interest. In this paper we present a highly accurate algorithm for the numerical solution of the incompressible Navier–Stokes equations which employs a spectral/hp element spatial discretisation and a high-order time splitting. Two important developments discussed in this paper are the coupling of these techniques with unstructured mesh generation, used in many everyday engineering applications, and the introduction of a non-Newtonian viscosity model to account for the shear thinning properties of blood. The proposed method will be applied to the analysis of shear stress distributions in flows of interest in haemodynamics. Received: 5 May 1999 / Accepted: 21 september 1999