Analyzing the structure of sampled features from an input data distribution is challenging when constrained by limited measurements in both the number of inputs and features. Traditional approaches often rely on the eigenvalue spectrum of the sample covariance matrix derived from finite measurement matrices; however, these spectra are sensitive to the size of the measurement matrix, leading to biased insights. In this paper, we introduce a novel algorithm that provides unbiased estimates of the spectral moments of the kernel integral operator in the limit of infinite inputs and features from finitely sampled measurement matrices. Our method, based on dynamic programming, is efficient and capable of estimating the moments of the operator spectrum. We demonstrate the accuracy of our estimator on radial basis function (RBF) kernels, highlighting its consistency with the theoretical spectra. Furthermore, we showcase the practical utility and robustness of our method in understanding the geometry of learned representations in neural networks.

In this paper, we present AmbiSense, an acoustic field based sensing system that performs proximity detection and bearing estimation for safer physical human-robot interactions. A single low cost piezoelectric transducer is used to setup this novel acoustic sensing modality to create a blindspot-free sound field engulfing a robot arm. Two detection algorithms leveraging spectral information from reflected audio waves of objects entering the acoustic field are proposed to infer object presence and bearing. We also present a new receiver structure which improves signal to noise ratio (SNR). AmbiSense is paired with a collision avoidance inverse kinematic solver for real world deployment on a Kinova Gen3 robot. Validation is performed using ten test objects generating 2000 proximity and bearing estimation events in real world settings, we show that AmbiSense detects proximity with 93.8% sensitivity and 96.6 % specificity. It estimates bearing and maps it to three zones on a robot link with 100% sensitivity and specificity, while using fewer sensors than state of the art methods for similar coverage.

We study fairness through the lens of cooperative multi-agent learning. Our work is motivated by empirical evidence that naive maximization of team reward yields unfair outcomes for individual team members. To address fairness in multi-agent contexts, we introduce team fairness, a group-based fairness measure for multi-agent learning. We then prove that it is possible to enforce team fairness during policy optimization by transforming the team's joint policy into an equivariant map. We refer to our multi-agent learning strategy as Fairness through Equivariance (Fair-E) and demonstrate its effectiveness empirically. We then introduce Fairness through Equivariance Regularization (Fair-ER) as a soft-constraint version of Fair-E and show that it reaches higher levels of utility than Fair-E and fairer outcomes than non-equivariant policies. Finally, we present novel findings regarding the fairness-utility trade-off in multi-agent settings; showing that the magnitude of the trade-off is dependent on agent skill.

Being able to grasp objects is a fundamental component of most robotic manipulation systems. In this paper, we present a new approach to simultaneously reconstruct a mesh and a dense grasp quality map of an object from a depth image. At the core of our approach is a novel camera-centric object representation called the “object shell” which is composed of an observed “entry image” and a predicted “exit image”. We present an image-to-image residual ConvNet architecture in which the object shell and a grasp-quality map are predicted as separate output channels. The main advantage of the shell representation and the corresponding neural network architecture, ShellGrasp-Net, is that the input-output pixel correspondences in the shell representation are explicitly represented in the architecture. We show that this coupling yields superior generalization capabilities for object reconstruction and accurate grasp quality estimation implicitly considering the object geometry. Our approach yields an efficient dense grasp quality map and an object geometry estimate in a single forward pass. Both of these outputs can be used in a wide range of robotic manipulation applications. With rigorous experimental validation, both in simulation and on a real setup, we show that our shell-based method can be used to generate precise grasps and the associated grasp quality with over 90% accuracy. Diverse grasps computed on shell reconstructions allow the robot to select and execute grasps in cluttered scenes with more than 93% success rate.

Learning intricate manipulation skills from human demonstrations requires good sample efficiency. We introduce a novel learning algorithm, the Curvature-regularized Variational Auto-Encoder (CurvVAE), to achieve this goal. The CurvVAE is able to model the natural variations in human-demonstrated trajectory data without overfitting. It does so by regularizing the curvature of the learned manifold. To showcase our algorithm, our robot learns an interpretable model of the variation in how humans acquire soft, slippery banana slices with a fork. We evaluate our learned trajectories on a physical robot system, resulting in banana slice acquisition performance better than current state-of-the-art.

A new approach to$L_{2}$-consistent estimation of a general density functional using$k$-nearest neighbor distances is proposed, where the functional under consideration is in the form of the expectation of some function$f$of the densities at each point. The estimator is designed to be asymptotically unbiased, using the convergence of the normalized volume of a$k$-nearest neighbor ball to a Gamma distribution in the large-sample limit, and naturally involves the inverse Laplace transform of a scaled version of the function$f$. Some instantiations of the proposed estimator recover existing$k$-nearest neighbor based estimators of Shannon and Rényi entropies and Kullback–Leibler and Rényi divergences, and discover new consistent estimators for many other functionals such as logarithmic entropies and divergences. The$L_{2}$-consistency of the proposed estimator is established for a broad class of densities for general functionals, and the convergence rate in mean squared error is established as a function of the sample size for smooth, bounded densities.

This paper presents a Dynamic Vision Sensor (DVS) based system for reasoning about high-speed motion. As a representative scenario we consider a robot at rest, reacting to a small, fast approaching object at speeds higher than 15 m/s. Since conventional image sensors at typical frame rates observe such an object for only a few frames, estimating the underlying motion presents a considerable challenge for standard computer vision systems and algorithms. We present a method motivated by how animals such as insects solve this problem with their relatively simple vision systems.Our solution takes the event stream from a DVS and first encodes the temporal events with a set of causal exponential filters across multiple time scales. We couple these filters with a Convolutional Neural Network (CNN) to efficiently extract relevant spatiotemporal features. The combined network learns to output both the expected time to collision of the object, as well as the predicted collision point on a discretized polar grid. These critical estimates are computed with minimal delay by the network in order to react appropriately to the incoming object. We highlight our system’s results with a toy dart moving at 23.4 m/s with a 24.73° error in θ, 18.4 mm average discretized radius prediction error, and 25.03% median time to collision prediction error.

This paper presents c2g-HOF networks which learn to generate cost-to-go functions for manipulator motion planning. The c2g-HOF architecture consists of a cost-to-go function over the configuration space represented as a neural network (c2g-network) as well as a Higher Order Function (HOF) network which outputs the weights of the c2g-network for a given input workspace. Both networks are trained end-to-end in a supervised fashion using costs computed from traditional motion planners. Once trained, c2g-HOF can generate a smooth and continuous cost-to-go function directly from workspace sensor inputs (represented as a point cloud in 3D or an image in 2D). At inference time, the weights of the c2g-network are computed very efficiently and near-optimal trajectories are generated by simply following the gradient of the cost-to-go function.We compare c2g-HOF with traditional planning algorithms for various robots and planning scenarios. The experimental results indicate that planning with c2g-HOF is significantly faster than other motion planning algorithms, resulting in orders of magnitude improvement when including collision checking. Furthermore, despite being trained from sparsely sampled trajectories in configuration space, c2g-HOF generalizes to generate smoother, and often lower cost, trajectories. We demonstrate cost-to-go based planning on a 7 DoF manipulator arm where motion planning in a complex workspace requires only 0.13 seconds for the entire trajectory.

We solve active target tracking, one of the essential tasks in autonomous systems, using a deep reinforcement learning (RL) approach. In this problem, an autonomous agent is tasked with acquiring information about targets of interests using its on-board sensors. The classical challenges in this problem are system model dependence and the difficulty of computing information-theoretic cost functions for a long planning horizon. RL provides solutions for these challenges as the length of its effective planning horizon does not affect the computational complexity, and it drops the strong dependency of an algorithm on system models. In particular, we introduce Active Tracking Target Network (ATTN), a unified deep RL policy that is capable of solving major sub-tasks of active target tracking – in-sight tracking, navigation, and exploration. The policy shows robust behavior for tracking agile and anomalous targets with a partially known target model. Additionally, the same policy is able to navigate in obstacle environments to reach distant targets as well as explore the environment when targets are positioned in unexpected locations.

In this work, we focus on mobile robot navigation in indoor environments where occlusions and field-of-view limitations hinder onboard sensing capabilities. We show that the footprint of a camera mounted on a robot can be drastically improved using learning-based approaches. Specifically, we consider the task of building an occupancy map for autonomous navigation of a robot equipped with a depth camera. In our approach, a local occupancy map is first computed using measurements from the camera directly. Afterwards, an inpainting network adds further information, the occupancy probabilities of unseen grid cells, to the map. A novel aspect of our approach is that rather than direct supervision from ground truth, we combine the information from a second camera with a better field-of-view for supervision. The training focuses on predicting extensions of the sensed data. To test the effectiveness of our approach, we use a robot setup with a single camera placed at 0.5m above the ground. We compare the navigation performance using raw maps from only this camera’s input (baseline) versus using inpainted maps augmented with our network. Our method outperforms the baseline approach even in completely new environments not included in the training set and can yield 21% shorter paths than the baseline approach. A real-time implementation of our method on a mobile robot is also tested in home and office environments.

We present a novel approach to robotic grasp planning using both a learned grasp proposal network and a learned 3D shape reconstruction network. Our system generates 6-DOF grasps from a single RGB-D image of the target object, which is provided as input to both networks. By using the geometric reconstruction to refine the candidate grasp produced by the grasp proposal network, our system is able to accurately grasp both known and unknown objects, even when the grasp location on the object is not visible in the input image.This paper presents the network architectures, training procedures, and grasp refinement method that comprise our system. Experiments demonstrate the efficacy of our system at grasping both known and unknown objects (91% success rate in a physical robot environment, 84% success rate in a simulated environment). We additionally perform ablation studies that show the benefits of combining a learned grasp proposal with geometric reconstruction for grasping, and also show that our system outperforms several baselines in a grasping task.

Perceiving obstacles and avoiding collisions is fundamental to the safe operation of a robot system, particularly when the robot must operate in highly dynamic human environments. Proximity detection using on-robot sensors can be used to avoid or mitigate impending collisions. However, existing proximity sensing methods are orientation and placement dependent, resulting in blind spots even with large numbers of sensors. In this paper, we introduce the phenomenon of the Leaky Surface Wave (LSW), a novel sensing modality, and present AuraSense, a proximity detection system using the LSW. AuraSense is the first system to realize no-dead-spot proximity sensing for robot arms. It requires only a single pair of piezoelectric transducers, and can easily be applied to off-the-shelf robots with minimal modifications. We further introduce a set of signal processing techniques and a lightweight neural network to address the unique challenges in using the LSW for proximity sensing. Finally, we demonstrate a prototype system consisting of a single piezoelectric element pair on a robot manipulator, which validates our design. We conducted several micro benchmark experiments and performed more than 2000 on-robot proximity detection trials with various potential robot arm materials, colliding objects, approach patterns, and robot movement patterns. AuraSense achieves 100% and 95.3% true positive proximity detection rates when the arm approaches static and mobile obstacles respectively, with a true negative rate over 99%, showing the real-world viability of this system.

This paper presents a supervised learning method to generate continuous cost-to-go functions of non-holonomic systems directly from the workspace description. Supervision from informative examples reduces training time and improves network performance. The manifold representing the optimal trajectories of a non-holonomic system has high-curvature regions which can not be efficiently captured with uniform sampling. To address this challenge, we present an adaptive sampling method which makes use of sampling based planners along with local, closed-form solutions to generate training samples. The cost-to-go function over a specific workspace is represented as a neural network whose weights are generated by a second, higher order network. The networks are trained in an end-to-end fashion. In our previous work, this architecture was shown to successfully learn to generate the cost-to-go functions of holonomic systems using uniform sampling. In this work, we show that uniform sampling fails for non-holonomic systems. However, with the proposed adaptive sampling methodology, our network can generate near-optimal trajectories for non-holonomic systems while avoiding obstacles. Experiments show that our method is two orders of magnitude faster compared to traditional approaches in cluttered environments.

There have been many recent advances in representation learning; however, unsupervised representation learning can still struggle with model identification issues related to rotations of the latent space. Variational Auto-Encoders (VAEs) and their extensions such as $\beta$-VAEs have been shown to improve local alignment of latent variables with PCA directions, which can help to improve model disentanglement under some conditions. Borrowing inspiration from Independent Component Analysis (ICA) and sparse coding, we propose applying an $L_1$ loss to the VAE's generative Jacobian during training to encourage local latent variable alignment with independent factors of variation in images of multiple objects or images with multiple parts. We demonstrate our results on a variety of datasets, giving qualitative and quantitative results using information theoretic and modularity measures that show our added $L_1$ cost encourages local axis alignment of the latent representation with individual factors of variation.

In this work, we present a hardware-efficient architecture for pedestrian detection with neuromorphic Dynamic Vision Sensors (DVSs), asynchronous camera sensors that report discrete changes in light intensity. These imaging sensors have many advantages compared to traditional frame-based cameras, such as increased dynamic range, lower bandwidth requirements, and higher sampling frequency with lower power consumption. Our architecture is composed of two main components: an event filtering stage to denoise the input image stream followed by a low-complexity neural network. For the first stage, we use a novel point-process filter (PPF) with an adaptive temporal windowing scheme that enhances classification accuracy. The second stage implements a hardware-efficient Binary Neural Network (BNN) for classification. To demonstrate the reduction in complexity achieved by our architecture, we showcase a Field-Programmable Gate Array (FPGA) implementation of the entire system which obtains a 86& reduction in latency compared to current neural network floating-point architectures.

We address the problem of reconstructing a high-resolution surface representing an object from a single image. We present Surface HOF, which takes an image of an object as input and generates a mapping function for surface generation. The mapping function takes samples from a canonical domain and maps each sample to a local tangent plane on the 3D reconstruction of the object. By efficiently learning a continuous mapping function, the surface can be generated at arbitrary resolution in contrast to other methods which generate fixed resolution outputs. Experiments show that Surface HOF is more accurate and uses more efficient representations than other state of the art methods for surface reconstruction. Surface HOF is also easier to train: it requires minimal input pre-processing and output post-processing and generates surface representations that are more parameter efficient. Its accuracy and convenience make Surface HOF an appealing method for single image reconstruction.

We consider the problem of planning views for a robot to acquire images of an object for visual inspection and reconstruction. In contrast to offline methods which require a 3D model of the object as input or online methods which rely on only local measurements, our method uses a neural network which encodes shape information for a large number of objects. We build on recent deep learning methods capable of generating a complete 3D reconstruction of an object from a single image. Specifically, in this work, we extend a recent method which uses Higher Order Functions (HOF) to represent the shape of the object. We present a new generalization of this method to incorporate multiple images as input and establish a connection between visibility and reconstruction quality. This relationship forms the foundation of our view planning method where we compute viewpoints to visually cover the output of the multiview HOF network with as few images as possible. Experiments indicate that our method provides a good compromise between online and offline methods: Similar to online methods, our method does not require the true object model as input. In terms of number of views, it is much more efficient. In most cases, its performance is comparable to the optimal offline case even on object classes the network has not been trained on.

A major challenge in reinforcement learning is exploration, when local dithering methods such as epsilon-greedy sampling are insufficient to solve a given task. Many recent methods have proposed to intrinsically motivate an agent to seek novel states, driving the agent to discover improved reward. However, while state-novelty exploration methods are suitable for tasks where novel observations correlate well with improved reward, they may not explore more efficiently than epsilon-greedy approaches in environments where the two are not well-correlated. In this paper, we distinguish between exploration tasks in which seeking novel states aids in finding new reward, and those where it does not, such as goal-conditioned tasks and escaping local reward maxima. We propose a new exploration objective, maximizing the reward prediction error (RPE) of a value function trained to predict extrinsic reward. We then propose a deep reinforcement learning method, QXplore, which exploits the temporal difference error of a Q-function to solve hard exploration tasks in high-dimensional MDPs. We demonstrate the exploration behavior of QXplore on several OpenAI Gym MuJoCo tasks and Atari games and observe that QXplore is comparable to or better than a baseline state-novelty method in all cases, outperforming the baseline on tasks where state novelty is not well-correlated with improved reward.

Collision detection is critical for safe robot operation in the presence of humans. Acoustic information originating from collisions between robots and objects provides opportunities for fast collision detection and localization; however, audio information from microphones on robot manipulators needs to be robustly differentiated from motors and external noise sources. In this paper, we present Panotti, the first system to efficiently detect and localize on-robot collisions using low-cost microphones. We present a novel algorithm that can localize the source of a collision with centimeter level accuracy and is also able to reject false detections using a robust spectral filtering scheme. Our method is scalable, easy to deploy, and enables safe and efficient control for robot manipulator applications. We implement and demonstrate a prototype that consists of 8 miniature microphones on a 7 degree of freedom (DOF) manipulator to validate our design. Extensive experiments show that Panotti realizes near perfect on-robot true positive collision detection rate with almost zero false detections even in high noise environments. In terms of accuracy, it achieves an average localization error of less than 3.8 cm under various experimental settings.

We consider the problem of finding optimal resource allocations subject to system constraints in a generic class of problems in wireless communications. These problems are inherently challenging due to functional optimization and potential non-convexities. However, these problems can be observed to take the form of a regression problem, although one in which the statistical loss function appears as a constraint. This motivates the use of machine learning model parameterizations. To apply gradient-based solution algorithms that do not require model knowledge, we convert the constrained optimization problem to an unconstrained one using Lagrangian duality. Despite the non-convexity in the problem, we formally show that the sub-optimality of the dual domain problem is small when the learning parameterization is sufficiently dense. We then present a primal-dual learning algorithm that looks for solutions to the dual problem using model-free gradient estimates. In a numerical simulation, we demonstrate the near-optimality of the proposed model-free algorithm using a neural network parametrization for a capacity maximization problem.

The representation of the environment strongly affects how robots can move and interact with it. This paper presents an online approach for continuous mapping using Gaussian Process Implicit Surfaces (GPISs). Compared with grid-based methods, GPIS better utilizes sparse measurements to represent the world seamlessly. It provides direct access to the signed-distance function (SDF) and its derivatives which are invaluable for other robotic tasks and it incorporates uncertainty in the sensor measurements. Our approach incrementally and efficiently updates GPIS by employing a regressor on observations and a spatial tree structure. The effectiveness of the suggested approach is demonstrated using simulations and real world 2D/3D data.

While off-policy temporal difference (TD) methods have widely been used in reinforcement learning due to their efficiency and simple implementation, their Bayesian counterparts have not been utilized as frequently. One reason is that the non-linear max operation in the Bellman optimality equation makes it difficult to define conjugate distributions over the value functions. In this paper, we introduce a novel Bayesian approach to off-policy TD methods, called as ADFQ, which updates beliefs on state-action values, Q, through an online Bayesian inference method known as Assumed Density Filtering. We formulate an efficient closed-form solution for the value update by approximately estimating analytic parameters of the posterior of the Q-beliefs. Uncertainty measures in the beliefs not only are used in exploration but also provide a natural regularization for the value update considering all next available actions. ADFQ converges to Q-learning as the uncertainty measures of the Q-beliefs decrease and improves common drawbacks of other Bayesian RL algorithms such as computational complexity. We extend ADFQ with a neural network. Our empirical results demonstrate that ADFQ outperforms comparable algorithms on various Atari 2600 games, with drastic improvements in highly stochastic domains or domains with a large action space.

In this paper, we propose a novel Reinforcement Learning approach for solving the Active Information Acquisition problem, which requires an agent to choose a sequence of actions in order to acquire information about a process of interest using on-board sensors. The classic challenges in the information acquisition problem are the dependence of a planning algorithm on known models and the difficulty of computing information-theoretic cost functions over arbitrary distributions. In contrast, the proposed framework of reinforcement learning does not require any knowledge on models and alleviates the problems during an extended training stage. It results in policies that are efficient to execute online and applicable for real-time control of robotic systems. Furthermore, the state-of-the-art planning methods are typically restricted to short horizons, which may become problematic with local minima. Reinforcement learning naturally handles the issue of planning horizon in information problems as it maximizes a discounted sum of rewards over a long finite or infinite time horizon. We discuss the potential benefits of the proposed framework and compare the performance of the novel algorithm to an existing information acquisition method for multi-target tracking scenarios.

We present a novel method enabling robots to quickly learn to manipulate objects by leveraging a motion planner to generate “expert” training trajectories from a small amount of human-labeled data. In contrast to the traditional sense-plan-act cycle, we propose a deep learning architecture and training regimen called PtPNet that can estimate effective end-effector trajectories for manipulation directly from a single RGB-D image of an object. Additionally, we present a data collection and augmentation pipeline that enables the automatic generation of large numbers (millions) of training image and trajectory examples with almost no human labeling effort.We demonstrate our approach in a non-prehensile tool-based manipulation task, specifically picking up shoes with a hook. In hardware experiments, PtPNet generates motion plans (open-loop trajectories) that reliably (89% success over 189 trials) pick up four very different shoes from a range of positions and orientations, and reliably picks up a shoe it has never seen before. Compared with a traditional sense-plan-act paradigm, our system has the advantages of operating on sparse information (single RGB-D frame), producing high-quality trajectories much faster than the expert planner (300ms versus several seconds), and generalizing effectively to previously unseen shoes. Video available at https://youtu.be/voIkyiBtwn4.

A wide array of complex biological, social, and physical systems have recently been shown to be quantitatively described by Ising models, which lie at the intersection of statistical physics and machine learning. Here, we study the fundamental question of how to optimize the state of a networked Ising system given a budget of external influence. In the continuous setting where one can tune the influence applied to each node, we propose a series of approximate gradient ascent algorithms based on the Plefka expansion, which generalizes the naive mean field and TAP approximations. In the discrete setting where one chooses a small set of influential nodes, the problem is equivalent to the famous influence maximization problem in social networks with an additional stochastic noise term. In this case, we provide sufficient conditions for when the objective is submodular, allowing a greedy algorithm to achieve an approximation ratio of 1-1/e. Additionally, we compare the Ising-based algorithms with traditional influence maximization algorithms, demonstrating the practical importance of accurately modeling stochastic fluctuations in the system.

This paper presents a novel constrained, sampling-based motion planning method for grasp and transport tasks with a redundant robotic manipulator. We utilize a planning margin for grasping with constraints that allow the best grasp configuration and approach direction to be determined automatically. For manipulators with many degrees of freedom, our method efficiently chooses the optimal grasp pose when there are many redundant solutions. The method also introduces a parameterized intermediate pose that is optimized to determine the approach direction, increasing robustness under sensor uncertainty and execution errors. Our method also considers transporting the grasped object to the desired target position using a Rapidly-exploring Random Tree (RRT) algorithm that incorporates soft constraints via appropriate cost penalties. We demonstrate the effectiveness and efficiency of our algorithms on a number of simulated and experimental applications. Our experimental results show a marked improvement in computational efficiency in comparison to previously studied approaches.

Legged robots that make use of compliant actuators have demonstrated greater robustness of locomotion than their rigid counterparts. Stiffness and damping are key parameters that characterize the adaptation to perturbations. In this work, by drawing inspirations from controllable compliance and damping in existing soft and bio-inspired legged robots, we propose an approach to design a nonlinear controller for the balancing of humanoid robots with rigid bodies. Existing literature has proposed simplified dynamical models of biped robots in order to predict the timing and placement of swing foot for walking without falling. We further employ the properties of invariance to perturbations in damped harmonic oscillators and formulate continuous feedback control in combination with predictive foot stepping in order to achieve continuous adaptive recoveries of the nominal walking cycle from unexpected physical disturbances. Our method allows asymptotic convergence of the rigid body dynamics to a subspace with the desired energy level. We demonstrate the robustness of the proposed algorithm base on extensive push recovery experiments on a NAO robot on flat terrains.

With the advent of polygonal maps finding their way into the navigational software of mobile robots, the Visibility Graph can be used to search for the shortest collision-free path. The nature of the Visibility Graph-based shortest path algorithms is such that first the entire graph is computed in a relatively time-consuming manner. Then, the graph can be searched efficiently any number of times for varying start and target state combinations with the A* or the Dijkstra algorithm. However, real-world environments are typically too dynamic for a map to remain valid for a long time. With the goal of obtaining the shortest path quickly in an ever changing environment, we introduce a rapid path finding algorithm-Minimal Construct-that discovers only a necessary portion of the Visibility Graph around the obstacles that actually get in the way. Collision tests are computed only for lines that seem heuristically promising. This way, shortest paths can be found much faster than with a state-of-the-art Visibility Graph algorithm and as our experiments show, even grid-based A* searches are outperformed in most cases with the added benefit of smoother and shorter paths.

Sampling-based motion planners have experienced much success due to their ability to efficiently and evenly explore the state space. However, for many tasks, it may be more efficient to not uniformly explore the state space, especially when there is prior information about its structure. Previous methods have attempted to modify the sampling distribution using hand selected heuristics that can work well for specific environments but not universally. In this paper, a policy-search based method is presented as an adaptive way to learn implicit sampling distributions for different environments. It utilizes information from past searches in similar environments to generate better distributions in novel environments, thus reducing overall computational cost. Our method can be incorporated with a variety of sampling-based planners to improve performance. Our approach is validated on a number of tasks, including a 7DOF robot arm, showing marked improvement in number of collision checks as well as number of nodes expanded compared with baseline methods.

We consider the problem of classifying data manifolds where each manifold represents invariances that are parameterized by continuous degrees of freedom. Conventional data augmentation methods rely on sampling large numbers of training examples from these manifolds. Instead, we propose an iterative algorithm, [Formula: see text], based on a cutting plane approach that efficiently solves a quadratic semi-infinite programming problem to find the maximum margin solution. We provide a proof of convergence as well as a polynomial bound on the number of iterations required for a desired tolerance in the objective function. The efficiency and performance of [Formula: see text] are demonstrated in high-dimensional simulations and on image manifolds generated from the ImageNet data set. Our results indicate that [Formula: see text] is able to rapidly learn good classifiers and shows superior generalization performance compared with conventional maximum margin methods using data augmentation methods.

Nearest-neighbor estimators for the Kullback-Leiber (KL) divergence that are asymptotically unbiased have recently been proposed and demonstrated in a number of applications. However, with a small number of samples, nonparametric methods typically suffer from large estimation bias due to the nonlocality of information derived from nearest-neighbor statistics. In this letter, we show that this estimation bias can be mitigated by modifying the metric function, and we propose a novel method for learning a locally optimal Mahalanobis distance function from parametric generative models of the underlying density distributions. Using both simulations and experiments on a variety of data sets, we demonstrate that this interplay between approximate generative models and nonparametric techniques can significantly improve the accuracy of nearest-neighbor-based estimation of the KL divergence.

Classical discriminant analysis attempts to discover a low-dimensional subspace where class label information is maximally preserved under projection. Canonical methods for estimating the subspace optimize an information-theoretic criterion that measures the separation between the class-conditional distributions. Unfortunately, direct optimization of the information-theoretic criteria is generally non-convex and intractable in high-dimensional spaces. In this work, we propose a novel, tractable algorithm for discriminant analysis that considers the class-conditional densities as interacting fluids in the high-dimensional embedding space. We use the Bhattacharyya criterion as a potential function that generates forces between the interacting fluids, and derive a computationally tractable method for finding the low-dimensional subspace that optimally constrains the resulting fluid flow. We show that this model properly reduces to the optimal solution for homoscedastic data as well as for heteroscedastic Gaussian distributions with equal means. We also extend this model to discover optimal filters for discriminating Gaussian processes and provide experimental results and comparisons on a number of datasets.

We consider the problem of learning a local metric in order to enhance the performance of nearest neighbor classification. Conventional metric learning methods attempt to separate data distributions in a purely discriminative manner; here we show how to take advantage of information from parametric generative models. We focus on the bias in the information-theoretic error arising from finite sampling effects, and find an appropriate local metric that maximally reduces the bias based upon knowledge from generative models. As a byproduct, the asymptotic theoretical analysis in this work relates metric learning to dimensionality reduction from a novel perspective, which was not understood from previous discriminative approaches. Empirical experiments show that this learned local metric enhances the discriminative nearest neighbor performance on various datasets using simple class conditional generative models such as a Gaussian.

This paper presents a novel adaptive approach to fast sampling-based motion planning by learning models of collision and collision-free regions in configuration spaces in an online manner. The proposed approach incrementally learns Gaussian Mixture Models (GMMs) for collision detection in high dimensional configuration spaces. In practical applications for robotic manipulation, the representation of collision and collision-free regions in configuration space can change due to relative motion between the robot base and workspace. We show how to rapidly adapt to such changes by using inverse kinematics to transform the parameters of the Gaussian mixture model to new configurations. The transformed model is initially used as a prior and then continually updated and refined as the RRT planning algorithm proceeds in real-time. This approach is extremely computationally efficient, and our proposed method is compared with traditional sampling-based planning methods on a number of experimental robot arm planning scenarios.

Existing trajectory planning based locomotion algorithms lack the analytic tools to fully comprehend energy based movements that would allow for full stability and mobility. Such drawbacks make humanoid robots' locomotion sensitive to external disturbances and compromise robots' agility in unstructured environment. In this work, we specifically focus on the push recovery problem for humanoid robots. We propose an approach to design a nonlinear controller that is robust to external disturbances. It allows the state of the rigid body dynamics to asymptotically converge to the subspace that meet the criteria of balancing, based on the properties of artificial invariant subspace and potential functions. Our algorithm is completely adaptive in real time without requiring trajectory planning in advance. We demonstrate the robustness of the proposed algorithm base on extensive push recovery experiments on the DARWIN-OP robot platform on flat terrains.

This paper presents a self-supervised online learning approach for 3D object tracking that requires no pretraining of appearance. Our method focuses on selecting the most relevant parts of the RGBD input by continuously updating appearance classifiers in conjunction with the spatial occupancy of the target. Fine-grained regions selected via the learned bottom-up saliency, together with spatial cues of the 3D shape model, are used to identify and localize the target via shape registration. The subsequent 3-D pose estimate along with positive and negative labels from the registration are used for online learning appearance. The proposed method outperforms competing model-based tracking algorithms on public datasets as well as on a new motion scene dataset that we have collected.

We present a simple and efficient mathematical framework suitable for generating motion in the context of a variety of robotic motion tasks ranging from low-level motor control up to high-level locomotion planning. Our concept is based on a one-dimensional second-order model that allows analytic computation of its inverse dynamics while respecting physical constraints. This makes it a particularly useful tool for tasks that are expressed only as a start and goal state, such as animation key frames or way points in path planning. By means of time synchronization, the model extends easily to an arbitrary number of dimensions in a way that the target is reached in all dimensions at the same time. The framework excels in terms of execution time, which lies in the microsecond range even for high-dimensional trajectory generation tasks. We demonstrate our method in two different settings - full-body trajectory generation and path planning - and show its benefits in comparison with current state-of-the-art algorithms.

This paper shows how metric learning can be used with Nadaraya-Watson (NW) kernel regression. Compared with standard approaches, such as bandwidth selection, we show how metric learning can significantly reduce the mean square error (MSE) in kernel regression, particularly for high-dimensional data. We propose a method for efficiently learning a good metric function based upon analyzing the performance of the NW estimator for Gaussian-distributed data. A key feature of our approach is that the NW estimator with a learned metric uses information from both the global and local structure of the training data. Theoretical and empirical results confirm that the learned metric can considerably reduce the bias and MSE for kernel regression even when the data are not confined to Gaussian.

In order for humanoid robots to complete various assigned tasks without any human assistance, they must have the ability to stand up on their own. In this abstract, we introduce complex stand-up motion of humanoid robots learned by using Reinforcement Learning.

This paper presents a new approach for fast collision detection in high dimensional configuration spaces for Rapidly-exploring Random Trees (RRT) motion planning. The proposed method is based upon Gaussian Mixture Models (GMM) that are learned using an incremental Expectation Maximization clustering algorithm trained online using exemplars provided by a slow, conventional kinematic-based collision detection routine. The number of collision checks needed can be drastically reduced using a biased random sampling from the learned GMM distribution, and the learned models are continually refined and improved as the RRT planning algorithm proceeds. Our proposed method is demonstrated on several example applications and experimental results show marked improvement in computational efficiency over previous approaches.

This paper presents an online learning approach to 3D object registration that vastly improves the performance of Iterative Closest Point (ICP) methods. Our approach achieves better robustness and stable convergence by learning generalized distance functions directly from a stream of object depth data. The proposed algorithm, Learning Anisotropic ICP (LA-ICP), parameterizes the point uncertainty of the underlying object surface as an anisotropic Gaussian, and estimates the covariance parameters of the likelihood function for ICP from data. Our learning scheme does not require manual tuning and the parameters of the algorithm are continually updated from observed data. Experiments on various RGB-D object datasets demonstrate the effectiveness of our approach in terms of convergence and pose accuracy as well as robustness to initial conditions.

Motion planning for high degree of freedom (DOF) robots is not an easy task, and often requires optimization in a high dimensional space. Still, a generic motion planner using a single cost function for optimization may not be optimal over a number of different tasks with various task specific constraints. In this paper, we present a motion planning system that utilizes both easy to communicate human preferences and dimensionality reduction to handle these issues. Joint trajectories with human preference costs are projected into the null space of the task space, which helps make the resulting optimization simpler and more reliable. In addition, we apply the dimensionality reduction for the optimization, which significantly lowers the computational load. The suggested controller has been successfully used in the DARPA Robotics Challenge (DRC) Finals to handle a number of manipulation tasks.

Standing up after falling is an essential ability for humanoid robots in order to resume their tasks without help from humans. Although many humanoid robots, especially small-size humanoid robots, have their own stand-up motions, there has not been a generalized method to automatically learn flexible stand-up motions for humanoid robots which can be applied to various fallen positions. In this research, we propose a method for learning stand-up motions for humanoid robots using Q-learning making use of their bilateral symmetry. We implemented this method on DarwIn-OP humanoid robots and learned an optimal policy in simulation. We compared the resulting stand-up motion with manually designed stand-up motions and with stand-up motions learned without considering bilateral symmetry. Both in simulation and on the real robot, the new stand-up motion was successful in most trials while other motions took longer or were not as robust.

This paper presents an online self-supervised approach to improve the quality and relevance of input point cloud to a 3D registration algorithm. The suggested method considers the visibility of the model points and learns discriminative appearance of the object under gradual changes. It selectively reduces the amount of information to process by excluding non-visible points of the model and removing outliers from data stream, which results in better alignment between the input data and the model. Thus, by providing a good initial pose, it speeds up the iterative procedure of EM-like optimization for pose estimation (i.e., ICP) to achieve better efficiency and robustness. We compiled a new object dataset of RGBD images under camera motion with ground truth poses of the camera and the objects. We have performed experiments on this dataset and obtained promising results.

Common design principles for low cost humanoid robots include a low center of mass height and a large support area for increased static stability. However, such principles limit the bipedal mobility of the robot due to the kinematic constraints involved. In this paper, we present an efficient locomotion controller that utilizes automatically calculated heel and toe lift motions to overcome the kinematic constraints. This helps with uneven terrain traversal by providing additional support, and also enables a dynamic heel-strike toe-off gait with a large stride length. We demonstrate the controller in physically realistic simulations, and on the THOR-RD full-sized humanoid robot and DARwIn-OP miniature humanoid robot.

Influence maximization in social networks has typically been studied in the context of contagion models and irreversible processes. In this paper, we consider an alternate model that treats individual opinions as spins in an Ising system at dynamic equilibrium. We formalize the \textit{Ising influence maximization} problem, which has a natural physical interpretation as maximizing the magnetization given a budget of external magnetic field. Under the mean-field (MF) approximation, we present a gradient ascent algorithm that uses the susceptibility to efficiently calculate local maxima of the magnetization, and we develop a number of sufficient conditions for when the MF magnetization is concave and our algorithm converges to a global optimum. We apply our algorithm on random and real-world networks, demonstrating, remarkably, that the MF optimal external fields (i.e., the external fields which maximize the MF magnetization) exhibit a phase transition from focusing on high-degree individuals at high temperatures to focusing on low-degree individuals at low temperatures. We also establish a number of novel results about the structure of steady-states in the ferromagnetic MF Ising model on general graphs, which are of independent interest.

Neural codes are inevitably shaped by various kinds of biological constraints, \emph{e.g.} noise and metabolic cost. Here we formulate a coding framework which explicitly deals with noise and the metabolic costs associated with the neural representation of information, and analytically derive the optimal neural code for monotonic response functions and arbitrary stimulus distributions. For a single neuron, the theory predicts a family of optimal response functions depending on the metabolic budget and noise characteristics. Interestingly, the well-known histogram equalization solution can be viewed as a special case when metabolic resources are unlimited. For a pair of neurons, our theory suggests that under more severe metabolic constraints, ON-OFF coding is an increasingly more efficient coding scheme compared to ON-ON or OFF-OFF. The advantage could be as large as one-fold, substantially larger than the previous estimation. Some of these predictions could be generalized to the case of large neural populations. In particular, these analytical results may provide a theoretical basis for the predominant segregation into ON- and OFF-cells in early visual processing areas. Overall, we provide a unified framework for optimal neural codes with monotonic tuning curves in the brain, and makes predictions that can be directly tested with physiology experiments.

The efficient coding hypothesis assumes that biological sensory systems use neural codes that are optimized to best possibly represent the stimuli that occur in their environment. Most common models use information-theoretic measures, whereas alternative formulations propose incorporating downstream decoding performance. Here we provide a systematic evaluation of different optimality criteria using a parametric formulation of the efficient coding problem based on the [Formula: see text] reconstruction error of the maximum likelihood decoder. This parametric family includes both the information maximization criterion and squared decoding error as special cases. We analytically derived the optimal tuning curve of a single neuron encoding a one-dimensional stimulus with an arbitrary input distribution. We show how the result can be generalized to a class of neural populations by introducing the concept of a meta-tuning curve. The predictions of our framework are tested against previously measured characteristics of some early visual systems found in biology. We find solutions that correspond to low values of [Formula: see text], suggesting that across different animal models, neural representations in the early visual pathways optimize similar criteria about natural stimuli that are relatively close to the information maximization criterion.

We consider a general class of K-armed bandits that adapt to the actions of the player. A single continuous parameter characterizes the “attitude” of the bandit, ranging from stochastic to cooperative or to fully adversarial in nature. The player seeks to maximize the expected return from the adaptive bandit, and the associated optimization problem is related to the free energy of a statistical mechanical system under an external field. When the underlying stochastic distribution is Gaussian, we derive an analytic solution for the long run optimal player strategy for different regimes of the bandit. In the fully adversarial limit, this solution is equivalent to the Nash equilibrium of a two-player, zero-sum semi-infinite game. We show how optimal strategies can be learned from sequential draws and reward observations in these adaptive bandits using Bayesian filtering and Thompson sampling. Results show the qualitative difference in policy pseudo-regret between our proposed strategy and other well-known bandit algorithms.

This paper presents an online self-supervised approach to monocular visual odometry and ground classification applied to ground vehicles. We solve the motion and structure problem based on a constrained kinematic model. The true scale of the monocular scene is recovered by estimating the ground surface. We consider a general parametric ground surface model and use the Random Sample Consensus (RANSAC) algorithm for robust fitting of the parameters. The estimated ground surface provides training samples to learn a probabilistic appearance-based ground classifier in an online and self-supervised manner. The appearance-based classifier is then used to bias the RANSAC sampling to generate better hypotheses for parameter estimation of the ground surface model. Thus, without relying on any prior information, we combine geometric estimates with appearance-based classification to achieve an online self-learning scheme from monocular vision. Experimental results demonstrate that online learning improves the computational efficiency and accuracy compared to standard sampling in RANSAC. Evaluations on the KITTI benchmark dataset demonstrate the stability and accuracy of our overall methods in comparison to previous approaches.

In this paper we derive and implement an algorithm for an indoor mobile robotics platform to estimate the manipulability of initially unknown obstacles while navigating through its environment to a pre-specified goal. The environment is represented by an evidence grid, where each cell contains a gamma-distributed cost as well as visual feature data in the form of a color histogram. While navigating, the robot associates visual features of objects occupying a given cell with manipulability cost estimates of that cell, learning whether an object or obstacle can be moved or not in the robot's attempt to reach the goal. We derive and utilize a lower confidence bound (LCB) estimate for the cost of each cell in order to incorporate an exploration (versus pure exploitation) element to the robot's search for the lowest-cost path. Combining the LCB cost estimates with the dynamic replanning search algorithm D*-Lite, we can quickly compute optimal navigation paths regardless of the numerous changes occurring in the robot's environmental belief state. We explain the probabilistic representation of cost in the evidence grid and provide simulation and real-world results for our algorithm in a navigation scenario with static and movable objects.

Major rule changes for the RoboCup Humanoid League in 2015 pose significant vision and locomotion challenges for disambiguating similarly colored objects and navigating soft terrain. These significant changes highlight the need for applying general purpose humanoid robotics approaches that can handle abrupt environment modifications, and we utilize the general purpose THOR (Tactical Hazardous Operations Robot) series of robot from the recent DARPA Robotics Challenge (DRC). Specific techniques for vision, kicking and autonomy complement software developed for robust deployments in the DRC. In this paper, we present these soccer playing techniques, which were validated in the Humanoid AdultSize league in Hefei. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Recently, there has been a growing interest in modeling planning with information constraints. Accordingly, an agent maximizes a regularized expected utility known as the free energy, where the regularizer is given by the information divergence from a prior to a posterior policy. While this approach can be justified in various ways, including from statistical mechanics and information theory, it is still unclear how it relates to decision-making against adversarial environments. This connection has previously been suggested in work relating the free energy to risk-sensitive control and to extensive form games. Here, we show that a single-agent free energy optimization is equivalent to a game between the agent and an imaginary adversary. The adversary can, by paying an exponential penalty, generate costs that diminish the decision maker's payoffs. It turns out that the optimal strategy of the adversary consists in choosing costs so as to render the decision maker indifferent among its choices, which is a definining property of a Nash equilibrium, thus tightening the connection between free energy optimization and game theory.

Asymptotically unbiased nearest-neighbor estimators for K-L divergence have recently been proposed and demonstrated in a number of applications. With small sample sizes, however, these nonparametric methods typically suffer from high estimation bias due to the non-local statistics of empirical nearest-neighbor information. In this paper, we show that this non-local bias can be mitigated by changing the distance metric, and we propose a method for learning an optimal Mahalanobis-type metric based on global information provided by approximate parametric models of the underlying densities. In both simulations and experiments, we demonstrate that this interplay between parametric models and nonparametric estimation methods significantly improves the accuracy of the nearest-neighbor K-L divergence estimator.

The challenging task of navigating in cluttered environments has been studied extensively with indoor autonomous mobile robots. However, few approaches attempt to estimate real-valued costs for manipulating said obstacles with no prior knowledge of the environment. Our approach not only estimates these costs but also models the uncertainty inherent in making such estimates. We present an algorithm that, with no prior knowledge of the environment, allows a mobile robot to determine which obstacles are movable and which are not while navigating a cluttered environment. The algorithm also applies this knowledge of manipulability to obstacles encountered in the future that are similar in appearance to ones previously seen. Using our approach, a mobile robot can act intelligently about uncertain information as well as successfully navigate initially unknown indoor environments without relying on human-provided information.

Developing a reliable humanoid robot that operates in uncharted real-world environments is a huge challenge for both hardware and software. Commensurate with the technology hurdles, the amount of time and money required can also be prohibitive barriers. This paper describes Team THOR's approach to overcoming such barriers for the 2013 DARPA Robotics Challenge (DRC) Trials. We focused on forming modular components - in both hardware and software - to allow for efficient and cost effective parallel development. The robotic hardware consists of standardized and general purpose actuators and structural components. These allowed us to successfully build the robot from scratch in a very short development period, modify configurations easily and perform quick field repair. Our modular software framework consists of a hybrid locomotion controller, a hierarchical arm controller and a platform-independent operator interface. These modules helped us to keep up with hardware changes easily and to have multiple control options to suit various situations. We validated our approach at the DRC Trials where we fared very well against robots many times more expensive.

Bipedal humanoid robots will fall under unforeseen perturbations without active stabilization. Humans use dynamic full body behaviors in response to perturbations, and recent bipedal robot controllers for balancing are based upon human biomechanical responses. However these controllers rely on simplified physical models and accurate state information, making them less effective on physical robots in uncertain environments. In our previous work, we have proposed a hierarchical control architecture that learns from repeated trials to switch between low-level biomechanically-motivated strategies in response to perturbations. However in practice, it is hard to learn a complex strategy from limited number of trials available with physical robots. In this work, we focus on the very problem of efficiently learning the high-level push recovery strategy, using simulated models of the robot with different levels of abstraction, and finally the physical robot. From the state trajectory information generated using different models and a physical robot, we find a common low dimensional strategy for high level push recovery, which can be effectively learned in an online fashion from a small number of experimental trials on a physical robot. This learning approach is evaluated in physics-based simulations as well as on a small humanoid robot. Our results demonstrate how well this method stabilizes the robot during walking and whole body manipulation tasks.

How does neural population process sensory information? Optimal coding theories assume that neural tuning curves are adapted to the prior distribution of the stimulus variable. Most of the previous work has discussed optimal solutions for only one-dimensional stimulus variables. Here, we expand some of these ideas and present new solutions that define optimal tuning curves for high-dimensional stimulus variables. We consider solutions for a minimal case where the number of neurons in the population is equal to the number of stimulus dimensions (diffeomorphic). In the case of two-dimensional stimulus variables, we analytically derive optimal solutions for different optimal criteria such as minimal L2 reconstruction error or maximal mutual information. For higher dimensional case, the learning rule to improve the population code is provided.

We describe a new online discriminative learning algorithm that efficiently and effectively recognizes phonemes in a speech sequence. The method builds upon recent work in online learning of a collection of generalized linear models using second order statistics of the model weight vectors. Evaluation on the TIMIT database shows that the algorithm achieves state-of-the-art phoneme recognition error rates compared to many other generative and discriminative models with the same expressive power.

During heavy work, humans utilize whole body motions in order to generate large forces. In extreme cases, exaggerated weight shifts are used to impart large impact forces. There have been approaches to design stable whole body impact motions based on precise dynamic models of the robot and the target object, but they have practical limitations as the uncertainty in the ensuing reaction forces can lead to instability. In the current work, we describe a motion controller for a humanoid robot that generates impacts at an end effector while keeping the robot body balanced before and after the impact. Instead of relying on the accuracy of the impact dynamics model, we use a simplified model of the robot and biomechanically motivated push recovery controllers to reactively stabilize the robot against unknown perturbations from the impact. We demonstrate our approach in physically realistic simulations, as well as experimentally on a small humanoid robot platform.

This paper sheds light on some fundamental connections of the diffusion decision making model of neuroscience and cognitive psychology with k-nearest neighbor classification. We show that conventional k-nearest neighbor classification can be viewed as a special problem of the diffusion decision model in the asymptotic situation. Applying the optimal strategy associated with the diffusion decision model, an adaptive rule is developed for determining appropriate values of k in k-nearest neighbor classification. Making use of the sequential probability ratio test (SPRT) and Bayesian analysis, we propose five different criteria for adaptively acquiring nearest neighbors. Experiments with both synthetic and real datasets demonstrate the effectivness of our classification criteria.

In this work we study how the stimulus distribution influences the optimal coding of an individual neuron. Closed-form solutions to the optimal sigmoidal tuning curve are provided for a neuron obeying Poisson statistics under a given stimulus distribution. We consider a variety of optimality criteria, including maximizing discriminability, maximizing mutual information and minimizing estimation error under a general $L_p$ norm. We generalize the Cramer-Rao lower bound and show how the $L_p$ loss can be written as a functional of the Fisher Information in the asymptotic limit, by proving the moment convergence of certain functions of Poisson random variables. In this manner, we show how the optimal tuning curve depends upon the loss function, and the equivalence of maximizing mutual information with minimizing $L_p$ loss in the limit as $p$ goes to zero.

We present a novel learning-based method for generating optimal motion plans for high-dimensional motion planning problems. In order to cope with the curse of dimensional- ity, our method proceeds in a fashion similar to block co- ordinate descent in finite-dimensional optimization: at each iteration, the motion is optimized over a lower dimensional subspace while leaving the path fixed along the other dimen- sions. Naive implementations of such an idea can produce vastly suboptimal results. In this work, we show how a prof- itable set of directions in which to perform this dimensional descent procedure can be learned efficiently. We provide suf- ficient conditions for global optimality of dimensional de- scent in this learned basis, based upon the low-dimensional structure of the planning cost function. We also show how this dimensional descent procedure can easily be used for problems that do not exhibit such structure with monotonic convergence. We illustrate the application of our method to high dimensional shape planning and arm trajectory planning problems.

We demonstrate how to find high-quality motion plans for high-dimensional holonomic systems efficiently using dynamic programming in a learned subspace of vastly reduced dimension. Our approach (SLASHDP) learns the low dimensional cost structure of an optimal control problem via an efficient spectral method. This structure results in a symmetric value function that serves as a an efficiently-computable surrogate for the true value function. High-quality feedback motion plans can then be obtained from the symmetric value function. Experimental results show that SLASHDP yields higher-quality plans than can be obtained by post-processing plans generated by a sampling-based motion planner, and with less computational effort for very high-dimensional problems. We demonstrate high-quality dynamic programming plans for an arm planning problem of up to 144 dimensions without using any domain-specific knowledge aside from that learned automatically by SLASHDP. Positive results are also shown for a high-dimensional deformable robot planning problem.

Dynamic bipedal walking is susceptible to external disturbances and surface irregularities, requiring robust feedback control to remain stable. In this work, we present a practical hierarchical push recovery strategy that can be readily implemented on a wide range of humanoid robots. Our method consists of low level controllers that perform simple, biomechanically motivated push recovery actions and a high level controller that combines the low level controllers according to proprioceptive and inertial sensory signals and the current robot state. Reinforcement learning is used to optimize the parameters of the controllers in order to maximize the stability of the robot over a broad range of external disturbances. The controllers are learned on a physical simulation and implemented on the Darwin-HP humanoid robot platform, and the resulting experiments demonstrate effective full body push recovery behaviors during dynamic walking.

We present an method for generating high-quality plans for a robot arm with many degrees of freedom based on Learning Dimensional Descent (LDD), a recently-developed algorithm for planning in high-dimensional spaces based on machine learning and optimization techniques. Unlike other approaches used to solve this problem, our method optimizes a well-defined objective and can be shown to generate optimal plans, in theory and practice, for a well-defined class of problems—those that possess low-dimensional cost structure. For the common case where such structure is only approximately present, LDD constitutes a powerful iterative optimization technique that makes non-homotopic path adjustments in each iteration, while still providing a guarantee of convergence to a local minimum of the objective. Experiments with a 7-DOF robot arm show that the method is able to find solutions in cluttered environments that are of a much higher quality than can be obtained with sampling-based planners and smoothing.

Bipedal walking in human environments is made difficult by the unevenness of the terrain and by external disturbances. Most approaches to bipedal walking in such environments either rely upon a precise model of the surface or special hardware designed for uneven terrain. In this paper, we present an alternative approach to stabilize the walking of an inexpensive, commercially-available, position-controlled humanoid robot in difficult environments. We use electrically compliant swing foot dynamics and onboard sensors to estimate the inclination of the local surface, and use a online learning algorithm to learn an adaptive surface model. Perturbations due to external disturbances or model errors are rejected by a hierarchical push recovery controller, which modulates three biomechanically motivated push recovery controllers according to the current estimated state. We use a physically realistic simulation with an articulated robot model and reinforcement learning algorithm to train the push recovery controller, and implement the learned controller on a commercial DARwIn-OP small humanoid robot. Experimental results show that this combined approach enables the robot to walk over unknown, uneven surfaces without falling down.

We present a novel method to control a biped humanoid robot to walk on unknown inclined terrains, using an online learning algorithm to estimate in real-time the local terrain from proprioceptive and inertial sensors. Compliant controllers for the ankle joints are used to actively probe the surrounding surface, and the measured sensor data are combined to explicitly learn the global inclination and local disturbances of the terrain. These estimates are then used to adaptively modify the robot locomotion and control parameters. Results from both a physically-realistic computer simulation and experiments on a commercially available small humanoid robot show that our method can rapidly adapt to changing surface conditions to ensure stable walking on uneven surfaces.

We present a method for real-time simultaneous object recognition and segmentation based on cascaded discriminative Markov random fields. A Markov random field models coupling between the labels of adjacent image regions. The MRF affinities are learned as linear functions of image features in a structured max-margin framework that admits a solution via convex optimization. In contrast to other known MRF/CRF-based approaches, our method classifies in real-time and has computational complexity that scales only logarithmically in the number of object classes. We accomplish this by applying a cascade of binary MRF-classifiers in a way similar to error-correcting output coding for general multiclass learning problems. Inference in this model is exact and can be performed very efficiently using graph cuts. Experimental results are shown that demonstrate a marked improvement in classification accuracy over purely local methods.

We consider the problem of finding sufficiently simple models of high-dimensional physical systems that are consistent with observed trajectories, and using these models to synthesize new trajectories. Our approach models physical trajectories as least-time trajectories realized by free particles moving along the geodesics of a curved manifold, reminiscent of the way light rays obey Fermat's principle of least time. Finding these trajectories, unfortunately, requires finding a minimum-cost path in a high-dimensional space, which is generally a computationally intractable problem. In this work we show that this high-dimensional planning problem can often be solved nearly optimally in practice via deterministic search, as long as we can find a certain low-dimensional structure in the Lagrangian that describes our observed trajectories. This low-dimensional structure additionally makes it feasible to learn an estimate of a Lagrangian that is consistent with the observed trajectories, thus allowing us to present a complete approach for learning from and predicting high-dimensional physical motion sequences. We finally show experimental results applying our method to human motion and robotic walking gaits. In doing so, we furthermore demonstrate efficient path planning in a 990-dimensional space.

We introduce a new family of online learning algorithms based upon constraining the velocity flow over a distribution of weight vectors. In particular, we show how to effectively herd a Gaussian weight vector distribution by trading off velocity constraints with a loss function. By uniformly bounding this loss function, we demonstrate how to solve the resulting optimization analytically. We compare the resulting algorithms on a variety of real world datasets, and demonstrate how these algorithms achieve state-of-the-art robust performance, especially with high label noise in the training data.

We consider the problem of learning a local metric to enhance the performance of nearest neighbor classification. Conventional metric learning methods attempt to separate data distributions in a purely discriminative manner; here we show how to take advantage of information from parametric generative models. We focus on the bias in the information-theoretic error arising from finite sampling effects, and find an appropriate local metric that maximally reduces the bias based upon knowledge from generative models. As a byproduct, the asymptotic theoretical analysis in this work relates metric learning with dimensionality reduction, which was not understood from previous discriminative approaches. Empirical experiments show that this learned local metric enhances the discriminative nearest neighbor performance on various datasets using simple class conditional generative models.

We present a search-based planning approach for controlling a quadrupedal robot over rough terrain. Given a start and goal position, we consider the problem of generating a complete joint trajectory that will result in the legged robot successfully moving from the start to the goal. We decompose the problem into two main phases: an initial global planning phase, which results in a footstep trajectory; and an execution phase, which dynamically generates a joint trajectory to best execute the footstep trajectory. We show how R* search can be employed to generate high-quality global plans in the high-dimensional space of footstep trajectories. Results show that the global plans coupled with the joint controller result in a system robust enough to deal with a variety of terrains.

In this paper we propose a discriminant learning framework for problems in which data consist of linear subspaces instead of vectors. By treating subspaces as basic elements, we can make learning algorithms adapt naturally to the problems with linear invariant structures. We propose a unifying view on the subspace-based learning method by formulating the problems on the Grassmann manifold, which is the set of fixed-dimensional linear subspaces of a Euclidean space. Previous methods on the problem typically adopt an inconsistent strategy: feature extraction is performed in the Euclidean space while non-Euclidean distances are used. In our approach, we treat each sub-space as a point in the Grassmann space, and perform feature extraction and classification in the same space. We show feasibility of the approach by using the Grassmann kernel functions such as the Projection kernel and the Binet-Cauchy kernel. Experiments with real image databases show that the proposed method performs well compared with state-of-the-art algorithms.

We present a novel method for incorporating prior knowledge about invariances in object recognition for discriminant analysis. In contrast to conventional isotropic regularization approaches, our approach shows how to incorporate known transformation invariances in the geometry of the problem to better regularize discriminant analysis. In particular, we show how to incorporate group invariance and tangent vector structure with multiple parameters and derive special covariance terms that are used to regularize discriminant analysis. We apply this method to Fisher discriminant analysis, as well as its kernelized version, and show that this invariant regularization improves recognition performance over conventional regularization techniques.

The authors present a novel approach to the task of autonomous terrain classification based on structured prediction. We consider the problem of learning a classifier that will accurately segment an image into "obstacle" and "ground" patches based on supervised input. Previous approaches to this problem have focused mostly on local appearance; typically, a classifier is trained and evaluated on a pixel-by-pixel basis, making an implicit assumption of independence in local pixel neighborhoods. We relax this assumption by modeling correlations between pixels in the submodular MRF framework. We show how both the learning and inference tasks can be simply and efficiently implemented-exact inference via an efficient max flow computation; and learning, via an averaged-subgradient method. Unlike most comparable MRF-based approaches, our method is suitable for implementation on a robot in real-time. Experimental results are shown that demonstrate a marked increase in classification accuracy over standard methods in addition to real-time performance.

Subspace-based learning problems involve data whose elements are linear subspaces of a vector space. To handle such data structures, Grassmann kernels have been proposed and used previously. In this paper, we analyze the relationship between Grassmann kernels and probabilistic similarity measures. Firstly, we show that the KL distance in the limit yields the Projection kernel on the Grassmann manifold, whereas the Bhattacharyya kernel becomes trivial in the limit and is suboptimal for subspace-based problems. Secondly, based on our analysis of the KL distance, we propose extensions of the Projection kernel which can be extended to the set of affine as well as scaled subspaces. We demonstrate the advantages of these extended kernels for classification and recognition tasks with Support Vector Machines and Kernel Discriminant Analysis using synthetic and real image databases.

We present a novel method for the localization of a legged robot on known terrain using only proprioceptive sensors such as joint encoders and an inertial measurement unit. In contrast to other proprioceptive pose estimation techniques, this method allows for global localization (i.e., localization with large initial uncertainty) without the use of exteroceptive sensors. This is made possible by establishing a measurement model based on the feasibility of putative poses on known terrain given observed joint angles and attitude measurements. Results are shown that demonstrate that the method performs better than dead-reckoning, and is also able to perform global localization from large initial uncertainty

Speech dereverberation remains an open problem after more than three decades of research. The most challenging step in speech dereverberation is blind chan- nel identification (BCI). Although many BCI approaches have been developed, their performance is still far from satisfactory for practical applications. The main difficulty in BCI lies in finding an appropriate acoustic model, which not only can effectively resolve solution degeneracies due to the lack of knowledge of the source, but also robustly models real acoustic environments. This paper proposes a sparse acoustic room impulse response (RIR) model for BCI, that is, an acous- tic RIR can be modeled by a sparse FIR filter. Under this model, we show how to formulate the BCI of a single-input multiple-output (SIMO) system into a l1- norm regularized least squares (LS) problem, which is convex and can be solved efficiently with guaranteed global convergence. The sparseness of solutions is controlled by l1-norm regularization parameters. We propose a sparse learning scheme that infers the optimal l1-norm regularization parameters directly from microphone observations under a Bayesian framework. Our results show that the proposed approach is effective and robust, and it yields source estimates in real acoustic environments with high fidelity to anechoic chamber measurements.

Many problems in neural computation and statistical learning involve optimizations with nonnegativity constraints. In this article, we study convex problems in quadratic programming where the optimization is confined to an axis-aligned region in the nonnegative orthant. For these problems, we derive multiplicative updates that improve the value of the objective function at each iteration and converge monotonically to the global minimum. The updates have a simple closed form and do not involve any heuristics or free parameters that must be tuned to ensure convergence. Despite their simplicity, they differ strikingly in form from other multiplicative updates used in machine learning. We provide complete proofs of convergence for these updates and describe their application to problems in signal processing and pattern recognition.

This paper proposes a method for matching two sets of images given a small number of training examples by exploiting the underlying structure of the image manifolds. A nonlinear map from one manifold to another is constructed by combining linear maps locally defined on the tangent spaces of the manifolds. This construction imposes strong constraints on the choice of the maps, and makes possible good generalization of correspondences between all of the image sets. This map is flexible enough to approximate an arbitrary diffeomorphism between manifolds and can serve many purposes for applications. The underlying algorithm is a non-iterative efficient procedure whose complexity mainly depends on the number of matched training examples and the dimensionality of the manifold, and not on the number of samples nor on the dimensionality of the images. Several experiments were performed to demonstrate the potential of our method in image analysis and pose estimation. The first example demonstrates how images from a rotating camera can be mapped to the underlying pose manifold. Second, computer generated images from articulating toy figures are matched using the underlying 4 dimensional manifold to generate image-driven animations. Finally, two sets of actual lip images during speech are matched by their appearance manifold. In all these cases, our algorithm is able to obtain reasonable matches between thousands of large-dimensional images, with a minimum of computation.

The need to accurately and efficiently estimate room impulse responses arises in many acoustic signal processing applications. In this work, we present a general family of algorithms which contain the conventional normalized least mean squares (NLMS) algorithm as a special case. Specific members of this family yield estimates which are robust both to different noise models and choice of parameters. We demonstrate the merits of our approach to accurately estimate sparse room impulse responses in simulations with speech signals

We propose a Bayesian framework for learning the optimal regularization parameter in the L1-norm penalized least-mean-square (LMS) problem, also known as LASSO [1] or basis pursuit [2]. The setting of the regularization parameter is critical for deriving a correct solution. In most existing methods, the scalar regularization parameter is often determined in a heuristic manner; in contrast, our approach infers the optimal regularization setting under a Bayesian framework. Furthermore, Bayesian inference enables an independent regularization scheme where each coefficient (or weight) is associated with an independent regularization parameter. Simulations illustrate the improvement using our method in discovering sparse structure from noisy data.

The authors present an innovative method for the efficient joint estimation of attitude and position in six degrees of freedom via sensors such as GPS, inertial measurement units, and odometry. Traditional methods for attitude estimation via Kalman filtering are beset by many conceptual problems relating to the representation of orientations in linear spaces, leading to difficulties in implementation and the interpretation of uncertainty estimates, among other issues. These problems are compounded when it is necessary to jointly estimate position and attitude. We demonstrate how Rao-Blackwellized particle filtering provides a framework for approaching this estimation problem that is both conceptually appealing and practical. Results are shown that demonstrate the filter's robustness to sensor outages and its ability to perform well even in situations with noisy sensors and high initial uncertainty in all state dimensions; these situations are precisely those in which traditional Kalman filtering approaches are most likely to experience problems

We describe a robust deconvolution algorithm for simultaneously estimating an acoustic source signal and convolutive filters associated with the acoustic room impulse responses from a pair of microphone signals. In contrast to conventional blind deconvolution techniques which rely upon a knowledge of the statistics of the source signal, our algorithm exploits the nonnegativity and sparsity structure of room impulse responses. The algorithm is formulated as a quadratic optimization problem with respect to both the source signal and filter coefficients, and proceeds by iteratively solving the optimization in two alternating steps. In the H-step, the nonnegative filter coefficients are optimally estimated within a Bayesian framework using a relevant set of regularization parameters. In the S-step, the source signal is estimated without any prior assumption on its statistical distribution. The resulting estimates converge to a relevant solution exhibiting appropriate sparseness in the filters. Simulation results indicate that the algorithm is able to precisely recover both the source signal and filter coefficients, even in the presence of large ambient noise.

We propose a nonlinear method for learning the low-dimensional pose of a robot from high-dimensional panoramic images. The panoramic images are assumed to lie on a nonlinear low-dimensional appearance manifold that is embedded in a high-dimensional image space. We demonstrate that the local geometry of a point and its nearest neighbors on this manifold can be used to project the point onto a low-dimensional coordinate space. Using this embedding, the unknown camera position can be estimated from a novel panoramic image. We show how the image-based position measurements can be integrated with odometry information in a Bayesian framework to yield an online estimate of a robot's position. Results from simulated data show that the proposed method outperforms other appearance-based models based upon principal components analysis and kernel density estimation.

We describe a method for estimating the relative poses of a team of mobile robots using only acoustic sensing. The relative distances and bearing angles of the robots are estimated using the time of arrival of audible sound signals on stereo microphones. The robots emit specially designed sound waveforms that simultaneously enable robot identification and time of arrival estimation. These acoustic observations are then combined with odometry to update a belief state describing the positions and heading angles of all the robots. To efficiently resolve the ambiguity in the heading angle of the observing robot as well as the back-front ambiguity of the observed robot, we employ a Rao-Blackwellised particle filter (RBPF) where the distribution over heading angles is represented by a discrete set of particles, and the uncertainty in the translational positions conditioned on each of these particles is described by a Gaussian. This approach combines the representational accuracy of conventional particle filters with the efficiency of Kalman filter updates in modeling the pose distribution over a number of robots. We demonstrate how the RBPF can quickly resolve uncertainties in the binaural acoustic measurements and yield a globally consistent pose estimate. Simulations as well as an experimental implementation on robots with generic sound hardware illustrate the accuracy and the convergence of the resulting pose estimates.

The interaural time difference (ITD) of arrival is a primary cue for acoustic sound source localization. Traditional estimation techniques for ITD based upon cross-correlation are related to maximum-likelihood estimation of a simple generative model. We generalize the time difference estimation into a deconvolution problem with nonnegativity constraints. The resulting nonnegative least squares optimization can be efficiently solved using a novel iterative algorithm with guaranteed global convergence properties. We illustrate the utility of this algorithm using simulations and experimental results from a robot platform.

We interpret several well-known algorithms for dimensionality reduction of manifolds as kernel methods. Isomap, graph Laplacian eigenmap, and locally linear embedding (LLE) all utilize local neighborhood information to construct a global embedding of the manifold. We show how all three algorithms can be described as kernel PCA on specially constructed Gram matrices, and illustrate the similarities and differences between the algorithms with representative examples.

Bayesian Regularization and Nonnegative Deconvolution (BRAND) is proposed for estimating time delays of acoustic signals in reverberant environments. Sparsity of the nonnegative filter coefficients is enforced using an L1-norm regularization. A probabilistic generative model is used to simultaneously estimate the regularization parameters and filter coefficients from the signal data. Iterative update rules are derived under a Bayesian framework using the Expectation-Maximization procedure. The resulting time delay estimation algorithm is demonstrated on noisy acoustic data.

Nonnegativity constraints arise frequently in statistical learning and pattern recognition. Multiplicative updates provide natural solutions to optimizations involving these constraints. One well known set of multiplicative updates is given by the Expectation-Maximization algorithm for hidden Markov models, as used in automatic speech recognition. Recently, we have derived similar algorithms for nonnegative deconvolution and nonnegative quadratic programming. These algorithms have applications to low-level problems in voice processing, such as fundamental frequency estimation, as well as high-level problems, such as the training of large margin classifiers. In this paper, we describe these algorithms and the ideas that connect them.

We have implemented a real time front end for detecting voiced speech and estimating its fundamental frequency. The front end performs the signal processing for voice-driven agents that attend to the pitch contours of human speech and provide continuous audiovisual feedback. The al- gorithm we use for pitch tracking has several distinguishing features: it makes no use of FFTs or autocorrelation at the pitch period; it updates the pitch incrementally on a sample-by-sample basis; it avoids peak picking and does not require interpolation in time or frequency to obtain high res- olution estimates; and it works reliably over a four octave range, in real time, without the need for postprocessing to produce smooth contours. The algorithm is based on two simple ideas in neural computation: the introduction of a purposeful nonlinearity, and the error signal of a least squares fit. The pitch tracker is used in two real time multimedia applica- tions: a voice-to-MIDI player that synthesizes electronic music from vo- calized melodies, and an audiovisual Karaoke machine with multimodal feedback. Both applications run on a laptop and display the user’s pitch scrolling across the screen as he or she sings into the computer.

We derive multiplicative updates for solving the nonnegative quadratic programming problem in support vector machines (SVMs). The updates have a simple closed form, and we prove that they converge monotoni- cally to the solution of the maximum margin hyperplane. The updates optimize the traditionally proposed objective function for SVMs. They do not involve any heuristics such as choosing a learning rate or deciding which variables to update at each iteration. They can be used to adjust all the quadratic programming variables in parallel with a guarantee of im- provement at each iteration. We analyze the asymptotic convergence of the updates and show that the coefficients of non-support vectors decay geometrically to zero at a rate that depends on their margins. In practice, the updates converge very rapidly to good classifiers.

We investigate a learning algorithm for the classification of nonnegative data by mixture models. Multiplicative update rules are derived that directly optimize the performance of these models as classifiers. The update rules have a simple closed form and an intuitive appeal. Our algorithm retains the main virtues of the Expectation-Maximization (EM) algorithm—its guarantee of monotonic im- provement, and its absence of tuning parameters—with the added advantage of optimizing a discriminative objective function. The algorithm reduces as a spe- cial case to the method of generalized iterative scaling for log-linear models. The learning rate of the algorithm is controlled by the sparseness of the training data. We use the method of nonnegative matrix factorization (NMF) to discover sparse distributed representations of the data. This form of feature selection greatly accelerates learning and makes the algorithm practical on large problems. Ex- periments show that discriminatively trained mixture models lead to much better classification than comparably sized models trained by EM.

Non-negative matrix factorization (NMF) has previously been shown to be a useful decomposition for multivariate data. Two different multi- plicative algorithms for NMF are analyzed. They differ only slightly in the multiplicative factor used in the update rules. One algorithm can be shown to minimize the conventional least squares error while the other minimizes the generalized Kullback-Leibler divergence. The monotonic convergence of both algorithms can be proven using an auxiliary func- tion analogous to that used for proving convergence of the Expectation- Maximization algorithm. The algorithms can also be interpreted as diag- onally rescaled gradient descent, where the rescaling factor is optimally chosen to ensure convergence.

The principle of maximizing mutual information is applied to learning overcomplete and recurrent representations. The underlying model con(cid:173) sists of a network of input units driving a larger number of output units with recurrent interactions. In the limit of zero noise, the network is de(cid:173) terministic and the mutual information can be related to the entropy of the output units. Maximizing this entropy with respect to both the feed(cid:173) forward connections as well as the recurrent interactions results in simple learning rules for both sets of parameters. The conventional independent components (ICA) learning algorithm can be recovered as a special case where there is an equal number of output units and no recurrent con(cid:173) nections. The application of these new learning rules is illustrated on a simple two-dimensional input example.