Feedback min–max model predictive control using robust one-step sets

A solution to the infinite-horizon min–max model predictive control (MPC) problem of constrained polytopic systems has recently been defined in terms of a sequence of free control moves over a fixed horizon and a state feedback law in the terminal region using a time-varying terminal cost. The advantage of this formulation is the enlargement of the admissible set of initial states without sacrificing local optimality, but this comes at the expense of higher computational complexity. This article, by means of a counterexample, shows that the robust feasibility and stability properties of such algorithms are not, in general, guaranteed when more than one control move is adopted. For this reason, this work presents a novel formulation of min–max MPC based on the concept of within-horizon feedback and robust contractive set theory that ensures robust stability for any choice of the control horizon. A parameter-dependent feedback extension is also proposed and analysed. The effectiveness of the algorithms is demonstrated with two numerical examples.     

Sampled suffix array with minimizers

Sampling (evenly) the suffixes from the suffix array is an old idea trading the pattern search time for reduced index space. A few years ago Claude et al. showed an alphabet sampling scheme allowing for more efficient pattern searches compared with the sparse suffix array, for long enough patterns. A drawback of their approach is the requirement that sought patterns need to contain at least one character from the chosen subalphabet. In this work, we propose an alternative suffix sampling approach with only a minimum pattern length as a requirement, which is more convenient in practice. Experiments show that our algorithm (in a few variants) achieves competitive time‐space tradeoffs on most standard benchmark data. Copyright © 2017 John Wiley & Sons, Ltd.     

Finding Induced Paths of Given Parity in Claw-Free Graphs

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time.     

Training neural networks on high-dimensional data using random projection

Pattern Analysis and Applications - Training deep neural networks (DNNs) on high-dimensional data with no spatial structure poses a major computational problem. It implies a network architecture...     

Improving object classification robustness in RGB-D using adaptive SVMs

Nowadays object recognition is a fundamental capability for an autonomous robot in interaction with the physical world. Taking advantage of new sensing technologies providing RGB-D data, the object recognition capabilities increase dramatically. Object recognition has been well studied, however, known object classifiers usually feature poor generality and, therefore, limited adaptivity to different application domains. Although some domain adaptation approaches have been presented for RGB data, little work has been done on understanding the effects of applying object classification algorithms using RGB-D for different domains. Addressing this problem, we propose and comprehensively investigate an approach for object recognition in RGB-D data that uses adaptive Support Vector Machines (aSVM) and, in this way, achieves an impressive robustness in cross-domain adaptivity. For evaluation, two datasets from different application domains were used. Moreover, a study of state-of-the-art RGB-D feature extraction techniques and object classification methods was performed to identify which combinations (object representation - classification algorithm) remain less affected in terms of performance while switching between different application domains.     

Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

The problem of computing the chromatic number of a P ₅-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P ₅-free graph admits a k-coloring, and finding one, if it does.