Autonomous robot navigation in unstructured outdoor environments is a challenging and largely unsolved area of active research. The navigation task requires identifying safe, traversable paths that allow the robot to progress towards a goal while avoiding obstacles. Machine learning techniques are well adapted to this task, accomplishing near-to-far learning by training appearance-based models using near-field stereo readings in order to predict safe terrain and obstacles in the far field. However, these methods are subject to degraded performance when training data sets exhibit class imbalance, or skew, where data instances of one class outnumber those in another. In such scenarios, classifiers can be overwhelmed by the majority class, and will tend to ignore the minority class. In this paper, we show that typical outdoor terrain scenarios are associated with training data imbalance, and examine the impact of using undersampling, oversampling, SMOTE, and biased penalties techniques to correct for imbalance in stereo-derived training data. We conduct a statistically significant, repeated measures empirical evaluation and demonstrate improved far-field terrain prediction performance when using such methods for handling class imbalance versus taking no corrective action at all.

802.11 localization algorithms provide the ability to accurately position and track wireless clients thereby enabling location-based services and applications. However, we show that these localization techniques are vulnerable to non-cryptographic attacks where an adversary uses a low-cost directional antenna to appear from the localization algorithm's perspective to be in another arbitrary location of their choosing. The attacker's ability to actively influence where they are positioned is a key distinguishing feature of the directional attack relative to prior localization attacks that use transmit power control to introduce localization errors. We implement a representative set of received signal strength-based localization algorithms and evaluate the attack in a real office building environment. To mitigate the attack's effectiveness, we develop and evaluate an attack detection scheme that offers a high detection rate with few false positives.

Many terrains in outdoor robot navigation problems have paths that are distinct and continuous compared to the non-traversable regions. In image space these paths correspond to continuous segments that can be thought of as clusters embedded in image feature space. These segments very often translate directly to traversable ground plane. In this paper we build the intuition for semi-supervised methods in path identification and present a Markov random walk based approach that requires very few labeled points. The method creates a nearest neighbor graph representation of the current image frame using features deemed suitable for the task and propagates labels based on the concept of absorbing Markov chains. We extend this formalism to the task of dynamically identifying traversable and non-traversable regions in the incoming image frames. We present results on actual terrains corresponding to test courses used by the LAGR test team. The results demonstrate that with minimal initial supervision the robot can navigate to the goal. We also conduct comparisons of our path labeling technique against other machine learning techniques including nonlinear support vector machines on hand labeled data. The results demonstrate that our semi-supervised approach is proficient in the domain of path traversal in unstructured domains.

Algorithms such as Field-D* use linear interpolation to infer continuous fields of costdistance-to-goal, where costdistance is cost integrated over distance. Traditionally, field values have been used as direct input to trajectory planners. In contrast, we focus on extracting a minimum costdistance path between two points, given the continuous field. We identify a suboptimal phenomenon that occurs when standard path extraction techniques are used on linearly interpolated quantity-to-goal fields. The phenomenon causes paths to drift sideways toward their horizontal or vertical bounds, resulting in increased path length and unnecessary turns. We find that the sub-optimality is a mathematical consequence of the linear interpolation used to create the costdistance-to-goal field. We present a possible improvement that calculates path segment directions using an interpolation between the costdistance-to-goal gradient vectors, and perform a series of experiments comparing this method with the current state-of-the-art. We find that the proposed method can achieve a significant reduction in path length error, and we provide discussion and examples of when it should and should not be used.

Autonomous robot navigation in unstructured outdoor environments is a challenging area of active research. The navigation task requires identifying safe, traversable paths which allow the robot to progress toward a goal while avoiding obstacles. Machine learning techniques - in particular, classifier ensembles - are well adapted to this task, accomplishing near-to-far learning by augmenting near-field stereo readings in order to identify safe terrain and obstacles in the far field. Composition of the ensemble and subsequent combination of model outputs in this dynamic problem domain remain open questions. Recently, Ensemble selection has been proposed as a mechanism for selecting and combining models from an existing model library and shown to perform well in static domains. We propose the adaptation of this technique to the time-evolving data associated with the outdoor robot navigation domain. Important research questions as to the composition of the model library, as well as how to combine selected modelspsila outputs, are addressed in a two-factor experimental evaluation. We evaluate the performance of our technique on six fully labeled datasets, and show that our technique outperforms memoryless baseline techniques that do not leverage past experience.

The role of a distance metric in many supervised and semi-supervised learning applications is central in the success of clustering algorithms. Since existing metrics like Euclidean do not necessarily reflect the true structure (clusters or manifolds) in the data, it becomes imperative that an appropriate metric be somehow learned from training or labeled data. Metric learning has been a relatively new topic in data mining and machine learning, though most work that deals with this topic learns a suitable linear transformation of the original data. This transformation is usually learned using training data and has been shown to improve test data classification accuracy. In this paper we present a Markov random walk based semi-supervised method for metric learning. Our method differs from the aforementioned techniques in that we use minimal labeled data and we do not assume any Mahalanobis type metric structure on the data. We create a computationally efficient nearest neighbor graph representation of the data and pose a semidefinite program that learns the random walk on the associated graph. This is used to generate a distance measure between all unlabeled points and the performance is compared against other important metrics using the k-NN classification rule.

An approach to stereo based local path planning in unstructured environments is presented. The approach differs from previous stereo based and image based planning systems (e.g. top-down occupancy grid planners, autonomous highway driving algorithms, and view-sequenced route representation), in that it uses specialized cost functions to find paths through an occupancy grid representation of the world directly in the image plane and forgoes a projection of cost information from the image plane down onto a top-down 2D Cartesian cost map. We discuss three cost metrics for path selection in image space. We present a basic image based planning system, discuss its susceptibility to rotational and translational oscillation, and present and implement two extensions to the basic system that overcome these limitations - a cylindrical based image system and a hierarchical planning system. All three systems are implemented in an autonomous robot and are tested against a standard top-down 2D Cartesian planning system on three outdoor courses of varying difficulty. We find that the basic image based planning system fails under certain conditions; however, the cylindrical based system is well suited to the task of local path planning and for use as a high resolution local planning component of a hierarchical planning system.

Autonomous robot navigation in unstructured outdoor environments is a challenging area of active research. The navigation task requires identifying safe, traversable paths which allow the robot to progress toward a goal while avoiding obstacles. One approach is to apply Machine Learning techniques that accomplish near to far learning by augmenting near-field Stereo to identify safe terrain and obstacles in the far field. Some mechanism for applying past learned experience to the active navigation task is crucial for effective far-field classification. We introduce a new method for long-term learning in the robot navigation task by selecting a subset of previously learned linear binary classifiers. We then combine their output to produce a final classification for a new image. Techniques for efficient selection of models, as well as the combination of their output, are addressed. We evaluate the performance of our technique on three fully labeled datasets, and show that our technique outperforms several baseline techniques that do not leverage past experience.

Clustering aims to find useful hidden structures in data. In this paper we present a new clustering algorithm that builds upon the consistency method (Zhou, et.al., 2003), a semi-supervised learning technique with the property of learning very smooth functions with respect to the intrinsic structure revealed by the data. Other methods, e.g. Spectral Clustering, obtain good results on data that reveals such a structure. However, unlike Spectral Clustering, our algorithm effectively detects both global and within-class outliers, and the most representative examples in each class. Furthermore, we specify an optimization framework that estimates all learning parameters, including the number of clusters, directly from data. Finally, we show that the learned cluster-models can be used to add previously unseen points to clusters without re-learning the original cluster model. Encouraging experimental results are obtained on a number of real world problems.

Robot programmers can often quickly program a robot to approximately execute a task under specific environment conditions. However, achieving robust performance under more general conditions is significantly more difficult. We propose a framework that starts with an existing control system and uses reinforcement feedback from the environment to autonomously improve the controller's performance. We use the policy gradient reinforcement learning (PGRL) framework, which estimates a gradient (in controller space) of improved reward, allowing the controller parameters to be incrementally updated to autonomously achieve locally optimal performance. Our approach is experimentally verified on a Cye robot executing a room entry and observation task, showing significant reduction in task execution time and robustness with respect to un-modelled changes in the environment.

The Minimax Probability Machine Classification (MPMC) framework [Lanckriet et al., 2002] builds classifiers by minimizing the maximum probability of misclassification, and gives direct estimates of the proba- bilistic accuracy bound Ω. The only assumptions that MPMC makes is that good estimates of means and covariance matrices of the classes exist. However, as with Support Vector Machines, MPMC is computationally expensive and requires extensive cross validation experiments to choose kernels and kernel parameters that give good performance. In this paper we address the computational cost of MPMC by proposing an algorithm that constructs nonlinear sparse MPMC (SMPMC) models by incremen- tally adding basis functions (i.e. kernels) one at a time – greedily select- ing the next one that maximizes the accuracy bound Ω. SMPMC auto- matically chooses both kernel parameters and feature weights without us- ing computationally expensive cross validation. Therefore the SMPMC algorithm simultaneously addresses the problem of kernel selection and feature selection (i.e. feature weighting), based solely on maximizing the accuracy bound Ω. Experimental results indicate that we can obtain reli- able bounds Ω, as well as test set accuracies that are comparable to state of the art classification algorithms.

We formulate the regression problem as one of maximizing the mini- mum probability, symbolized by (cid:10), that future predicted outputs of the regression model will be within some (cid:6)" bound of the true regression function. Our formulation is unique in that we obtain a direct estimate of this lower probability bound (cid:10). The proposed framework, minimax probability machine regression (MPMR), is based on the recently de- scribed minimax probability machine classification algorithm [Lanckriet et al.] and uses Mercer Kernels to obtain nonlinear regression models. MPMR is tested on both toy and real world data, verifying the accuracy of the (cid:10) bound, and the efficacy of the regression models.

  We address two open theoretical questions in Policy Gradient Reinforce- ment Learning. The first concerns the efficacy of using function approx- imation to represent the state action value function, . Theory is pre- sented showing that linear function approximation representations of can degrade the rate of convergence of performance gradient estimates by a factor of relative to when no function approximation of is used, where is the number of basis functions in the function approximation representation. The sec- ond concerns the use of a bias term in estimating the state action value function. Theory is presented showing that a non-zero bias term can improve the rate of convergence of performance gradient estimates by is the number of possible actions. Experimen-
   tal evidence is presented showing that these theoretical results lead to significant improvement in the convergence properties of Policy Gradi- ent Reinforcement Learning algorithms. is the number of possible actions and

A nonparametric learning algorithm is used to build a robust mapping between an image obtained from a mobile robot's on-board camera, and the robot's current position. The mapping uses 19,200 unprocessed pixel values (160 by 120 pixel image). Because the learning algorithm is nonparametric, it uses the learning data obtained from these raw pixel values to automatically choose a structure for the mapping without human intervention, or any a priori assumptions about what type of image features should be used. The learning data consisting of a series example image inputs and corresponding position values, is collected in a calibration phase where the robot randomly traverses its intended workspace. This process of building visual localization maps for mobile robots is completely general and can be applied to any implementation which uses on-board cameras. We demonstrate the feasibility of this approach on a mobile platform performing in a robotics laboratory workspace. This workspace is visually cluttered, with humans and other objects continually moving within the robot's environment. The mapping learned in this environment is robust to these dynamic visual features and consistently reports timely localization information (at greater than 7 Hz) to within acceptable limits.

We propose a framework for programming robotic tasks using human-to-robot skill transfer. We assume that there exists a human expert who can accomplish a task in an unstructured environment by using various sensor displays and controls. The human expert performs the desired task a number of times while his/her input/output pairs are being recorded by the robot. The robot then uses this recorded data to construct a mapping between these sensor inputs and actuator outputs. This mapping must be general enough to allow the robot to accomplish the same task, in similar but not identical, dynamic, unstructured environments. This paper presents a testbed for human-to-robot skill transfer which is based on the teleoperated control of a small mobile robot working in an unstructured environment. The skill which is transferred from human-to-robot is loosely based on the tree tending task, a task which was chosen for its inherently unstructured nature. The SPORE approximation is proposed as a means for creating the robot's mapping from sensor inputs to actuator outputs.

A new method, termed the offset modification method (OM method), for solving the manipulator inverse kinematics problem is presented. The OM method works by modifying the link offset values of a manipulator until it is possible to derive closed-form inverse kinematics equations for the resulting manipulator (termed the model manipulator). This procedure allows one to derive a set of three nonlinear equations in three unknowns that, when numerically solved, give an inverse kinematics solution for the original manipulator. The OM method can be applied to manipulators with any number of degrees of freedom, as long as the manipulator satisfies a given set of conditions (Theorem 1). The OM method is tested on a 6-degree-of-freedom manipulator that has no known closed-form inverse kinematics equations. It is shown that the OM method is applicable to real-time manipulator control, can be used to guarantee convergence to a desired endpoint position and orientation (if it exists), and allows one to directly choose which inverse kinematics solution the algorithm will converge to (as specified in the model manipulator closed-form inverse kinematics equations). Applications of the method to other 6-DOF manipulator geometries and to redundant manipulators (i.e. greater than 6 DOF geometries) are discussed.>