Exact Algorithms for <Emphasis Type="Italic">L</Emphasis>(2,1)-Labeling of Graphs

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,…,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O ^*((k+1) ⁿ ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006 ⁿ ). Furthermore we show that dynamic programming can be used to establish an O(3.8730 ⁿ ) algorithm to compute an optimal L(2,1)-labeling.     

Augmenting the Rigidity of a Graph in <Emphasis Type="Italic">R</Emphasis><Superscript>2</Superscript>

Given a Laman graph G, i.e. a minimally rigid graph in R ², we provide a Θ(n ²) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is NP-hard for an arbitrary rigid graph G in R ².     

Multi‐agent system for knowledge‐based event recognition and composition

This work presents a multi‐agent system for knowledge‐based high‐level event composition, which interprets activities, behaviour and situations semantically in a scenario with multi‐sensory monitoring. A perception agent (plurisensory agent and visual agent)‐based structure is presented. The agents process the sensor information and identify (agent decision system) significant changes in the monitored signals, which they send as simple events to the composition agent that searches for and identifies pre‐defined patterns as higher‐level semantic composed events. The structure has a methodology and a set of tools that facilitate its development and application to different fields without having to start from scratch. This creates an environment to develop knowledge‐based systems generally for event composition. The application task of our work is surveillance, and event composition/inference examples are shown which characterize an alarming situation in the scene and resolve identification and tracking problems of people in the scenario being monitored.     

Applying intelligent agents and semantic web services in eGovernment environments

The increasing volume of eGovernment‐related services is demanding new approaches for service integration and interoperability in this domain. Semantic web (SW) technologies and applications can leverage the potential of eGovernment service integration and discovery, thus tackling the problems of semantic heterogeneity characterizing eGovernment information sources and the different levels of interoperability. eGovernment services will therefore be semantically described in the foreseeable future. In an environment with semantically annotated services, software agents are essential as the entities responsible for exploiting the semantic content in order to automate some tasks, and so enhance the user's experience. In this paper, we present a framework that provides a seamless integration of semantic web services and intelligent agents technologies by making use of ontologies to facilitate their interoperation. The proposed framework can assist in the development of powerful and flexible distributed systems in complex, dynamic, heterogeneous, unpredictable and open environments. Our approach is backed up by a proof‐of‐concept implementation, where the breakthrough of integrating disparate eGovernment services has been tested.     

Frequency domain regularization of d-dimensional structure tensor-based directional fields

The present work is intended to address two of the major difficulties that can be found when tackling the estimation of the local orientation of the data in a scene, a task which is usually accomplished by means of the computation of the structure tensor-based directional field. On one hand, the orientation information only exists in the non-homogeneous regions of the dataset, while it is zero in the areas where the gradient (i.e. the first-order intensity variation) remains constant. Due to this lack of information, there are many cases in which the overall shape of the represented objects cannot be precisely inferred from the directional field. On the other hand, the orientation estimation is highly dependent on the particular choice of the averaging window used for its computation (since a collection of neighboring gradient vectors is needed to obtain a dominant orientation), typically resulting in vector fields which vary from very irregular (thus yielding a noisy estimation) to very uniform (but at the expense of a loss of angular resolution). The proposed solution to both drawbacks is the regularization of the directional field; this process extends smoothly the previously computed vectors to the whole dataset while preserving the angular information of relevant structures. With this purpose, the paper introduces a suitable mathematical framework and deals with the d-dimensional variational formulation which is derived from it. The proposed formulation is finally translated into the frequency domain in order to obtain an increase of insight on the regularization problem, which can be understood as a low-pass filtering of the directional field. The frequency domain point of view also allows for an efficient implementation of the resulting iterative algorithm. Simulation experiments involving datasets of different dimensionality prove the validity of the theoretical approach.     

Context-sensitive refinements for stochastic optimisation algorithms in inductive logic programming

We describe a new approach to the application of stochastic search in Inductive Logic Programming (ILP). Unlike traditional approaches we do not focus directly on evolving logical concepts but our refinement-based approach uses the stochastic optimization process to iteratively adapt the initial working concept. Utilization of context-sensitive concept refinements (adaptations) helps the search operations to produce mostly syntactically correct concepts. It also enables using available background knowledge both for efficiently restricting the search space and for directing the search. Thereby, the search is more flexible, less problem-specific and the framework can be easily used with any stochastic search algorithm within ILP domain. Experimental results on several data sets verify the usefulness of this approach.     

Fault detection and isolation in robotic manipulators via neural networks: A comparison among three architectures for residual analysis

In this article we discuss artificial neural networks‐based fault detection and isolation (FDI) applications for robotic manipulators. The artificial neural networks (ANNs) are used for both residual generation and residual analysis. A multilayer perceptron (MLP) is employed to reproduce the dynamics of the robotic manipulator. Its outputs are compared with actual position and velocity measurements, generating the so‐called residual vector. The residuals, when properly analyzed, provides an indication of the status of the robot (normal or faulty operation). Three ANNs architectures are employed in the residual analysis. The first is a radial basis function network (RBFN) which uses the residuals of position and velocity to perform fault identification. The second is again an RBFN, except that it uses only the velocity residuals. The third is an MLP which also performs fault identification utilizing only the velocity residuals. The MLP is trained with the classical back‐propagation algorithm and the RBFN is trained with a Kohonen self‐organizing map (KSOM). We validate the concepts discussed in a thorough simulation study of a Puma 560 and with experimental results with a 3‐joint planar manipulator. © 2001 John Wiley & Sons, Inc.     

Verifying Temporal Properties of Reactive Systems: A STeP Tutorial

We review a number of formal verification techniques supported by STeP, the Stanford Temporal Prover, describing how the tool can be used to verify properties of several versions of the Bakery Mutual exclusion algorithm for mutual exclusion. We verify the classic two-process algorithm and simple variants, as well as an atomic parameterized version. The methods used include deductive verification rules, verification diagrams, automatic invariant generation, and finite-state model checking and abstraction.     

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.