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.     

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.     

The VFO-Driven Motion Planning and Feedback Control in Polygonal Worlds for a Unicycle with Bounded Curvature of Motion

Integrated motion planning and control for the purposes of maneuvering mobile robots under state- and input constraints is a problem of vital practical importance in applications of mobile robots such as autonomous transportation. Those constraints arise naturally in practice due to specifics of robot mechanical construction and the presence of obstacles in motion environment. In contrast to approaches focusing on feedback control design under the assumption of given reference motion or motion planning with neglection of subsequent feedback motion execution, we adopt a controller-driven motion planning paradigm, which has recently gained attention of many researchers. It postulates design of motion planning algorithms dedicated to specific feedback control policies, which compute a sequence of feedback control subtasks instead of classically planned open-loop controls or parametric paths. In this spirit, we propose a motion planning algorithm driven by the VFO (Vector Field Orientation) control law for the waypoint-following task. Presented analysis of the VFO control law reveals its beneficial properties, which are subsequently utilized to solve a generally nonlinear and non-convex optimal motion planning problem by formulating it as a mixed-integer linear program (MILP). The solution proposed in this paper yields a waypoint sequence, which is designed for execution by application of the VFO control law to drive a robot to a prescribed final configuration under an input constraint imposed by bounded curvature of robot motion and state constraints resulting from a convex decomposition of task space. Satisfaction of these constraints is guaranteed analytically and exactly, i.e., without utilization of numerical approximations. Moreover, for a given discrete set of possible waypoint orientations, the proposed algorithm computes plans optimal w.r.t. given cost functional, which can be any convex linear combination of quantities such as robot path length, curvature of robot motion, distance to imposed state constraints, etc. Furthermore, the planning algorithm exploits the possibility of both forward or backward movement of the robot to allow maneuvering in demanding environments. Generated waypoint sequences are a compact representation of a motion plan, which can be immediately executed with the VFO controller without any additional post-processing. Validity of the proposed approach has been confirmed by simulation studies and experimental motion execution with a laboratory-scale mobile robot.     

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.     

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.     

Randomized mutual exclusion on a multiple access channel

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes execute a concurrent program that occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource (also called a critical section), in such a way that at any time, there is at most one process accessing it. In our considerations, the shared resource is the shared communication channel itself (multiple access channel), and the main challenge arises because the channel is also the only mean of communication between these processes. We consider both the classic and a slightly weaker version of mutual exclusion, called \(\varepsilon \)-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most \(\varepsilon \). We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while the \(\varepsilon \)-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker \(\varepsilon \)-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.