Solving subgraph isomorphism problems with constraint programming

The subgraph isomorphism problem consists in deciding if there exists a copy of a pattern graph in a target graph. We introduce in this paper a global constraint and an associated filtering algorithm to solve this problem within the context of constraint programming. The main idea of the filtering algorithm is to label every node with respect to its relationships with other nodes of the graph, and to define a partial order on these labels in order to express compatibility of labels for subgraph isomorphism. This partial order over labels is used to filter domains. Labelings can also be strengthened by adding information from the labels of neighbors. Such a strengthening can be applied iteratively until a fixpoint is reached. Practical experiments illustrate that our new filtering approach is more effective on difficult instances of scale free graphs than state-of-the-art algorithms and other constraint programming approaches.     

Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model

We study the problem of sparse-matrix dense-vector multiplication (SpMV) in external memory. The task of SpMV is to compute y:=Ax, where A is a sparse N×N matrix and x is a vector. We express sparsity by a parameter k, and for each choice of k consider the class of matrices where the number of nonzero entries is kN, i.e., where the average number of nonzero entries per column is k.     

Principles of adjustable autonomy: a framework for resilient human–machine cooperation

Unmanned ground vehicles tend to be more and more autonomous, but both complete teleoperation and full autonomy are not efficient enough to deal with all possible situations. To be efficient, the human–robot system must be able to anticipate, react and recover from errors of different kinds, i.e., to be resilient. From this observation, this paper proposes a survey on the resilience of a human–machine system and the means to control the resilience. The resilience of a system can be defined as the ability to maintain or recover a stable state when subject to disturbance. Adjustable autonomy and human–machine cooperation are considered as means of resilience for the system. This paper then proposes three indicators to assess different meanings of resilience of the system: foresight and avoidance of events, reaction to events and recovery from occurrence of events. The third of these metrics takes into consideration the concept of affordances that allows a common representation for the opportunities of action between the automated system and its environment.     

Engineering an efficient two‐phase local search algorithm for the co‐rotating twin‐screw extruder configuration problem

The twin‐screw configuration problem arises during polymer extrusion and compounding. It consists in defining the location of a set of pre‐defined screw elements along the screw axis in order to optimize different, typically conflicting objectives. In this paper, we present a simple yet effective stochastic local search (SLS) algorithm for this problem. Our algorithm is based on efficient single‐objective iterative improvement algorithms, which have been developed by studying different neighborhood structures, neighborhood search strategies, and neighborhood restrictions. These algorithms are embedded into a variation of the two‐phase local search framework to tackle various bi‐objective versions of this problem. An experimental comparison with a previously proposed multi‐objective evolutionary algorithm shows that a main advantage of our SLS algorithm is that it converges faster to a high‐quality approximation to the Pareto front.     

Safety,Security, and Rescue Missions with an Unmanned Aerial Vehicle (UAV)

Several missions with an Unmanned Aerial Vehicle (UAV) in different realistic safety, security, and rescue field tests are presented. First, results from two safety and security missions at the 2009 European Land Robot Trials (ELROB) are presented. A UAV in form of an Airrobot AR100-B is used in a reconnaissance and in a camp security scenario. The UAV is capable of autonomous waypoint navigation using onboard GPS processing. A digital video stream from the vehicle is used to create photo maps—also known as mosaicking—in real time at the operator station. This mapping is done using an enhanced version of Fourier Mellin based registration, which turns out to be very fast and robust. Furthermore, results from a rescue oriented scenario at the 2010 Response Robot Evaluation Exercises (RREE) at Disaster City, Texas are presented. The registration for the aerial mosaicking is supplemented by an uncertainty metric and embedded into Simultaneous Localization and Mapping (SLAM), which further enhances the photo maps as main mission deliveries.     

Spectral registration of noisy sonar data for underwater 3D mapping

3D mapping is very challenging in the underwater domain, especially due to the lack of high resolution, low noise sensors. A new spectral registration method is presented that can determine the spatial 6 DOF transformation between pairs of very noisy 3D scans with only partial overlap. The approach is hence suited to cope with sonar as the predominant underwater sensor. The spectral registration method is based on Phase Only Matched Filtering (POMF) on non-trivially resampled spectra of the 3D data.     

Nano-structured solid oxide fuel cell design with superior power output at high and intermediate operation temperatures

A solid oxide fuel cell (SOFC) with a thin-film yttria-stabilized zirconia (YSZ) electrolyte was developed and tested. This novel SOFC shows a similar multilayer set-up as other current anode-supported SOFCs and is composed of a Ni/8YSZ anode, a gas-tight 8YSZ electrolyte layer, a dense Sr-diffusion barrier layer and a LSCF cathode. To increase the power density and lower the SOFC operating temperature, the thickness of the electrolyte layer was reduced from around 10 μm in current cells to 1 μm, using a nanoparticle deposition method. By using the novel 1 μm electrolyte layer, the current density of our SOFC progressed to 2.7, 2.1 and 1.6 A/cm² at operation temperatures of 800, 700 and 650°C, respectively, and out-performs all similar cells reported to date in the literature. An important consideration is also that cost-effective dip-coating and spin-coating methods are applied for the fabrication of the thin-film electrolyte. Processing of 1 μm layers on the very porous anode substrate material was initially experienced as very difficult and therefore 8YSZ nanoparticle coatings were developed and optimized on porous 8YSZ model substrates and transferred afterwards to regular anode substrates. In this paper, the preparation of the novel SOFC is shown and its morphology is illustrated with high resolution SEM pictures. Further, the performance in a standard SOFC test is demonstrated.     

Mixed-Signal Approximate Computation: A Neural Predictor Case Study

As transistors shrink and processors trend toward low power, maintaining precise digital behavior grows more expensive. Replacing digital units with analog equivalents sometimes allows similar computation to be performed at higher speed using less power. As a case study in mixed-signal approximate computation, the authors describe an enhanced neural prediction algorithm and its efficient analog implementation.