RSS 2015 Papers

This paper proposes an efficient and effective scheme to applying the sliding window approach popular in computer vision to 3D data. Specifically, the sparse nature of the problem is exploited via a voting scheme to enable a search through all putative object locations at any orientation. We prove that this voting scheme is mathematically equivalent to a convolution on a sparse feature grid and thus enables the processing, in full 3D, of any point cloud irrespective of the number of vantage points required to construct it. As such it is versatile enough to operate on data from popular 3D laser scanners such as a Velodyne as well as on 3D data obtained from increasingly popular push-broom configurations. Our approach is "embarrassingly parallelisable" and capable of processing a point cloud containing over 100K points at eight orientations in less than 0.5s. For the object classes car, pedestrian and bicyclist the resulting detector achieves best-in-class detection and timing performance relative to prior art on the KITTI dataset as well as compared to another existing 3D object detection approach.

Long-term operations of resource-constrained robots typically require hard decisions be made about which data to process and/or retain. The question then arises of how to choose which data is most useful to keep to achieve the task at hand. As spacial scale grows, the size of the map will grow without bound, and as temporal scale grows, the number of measurements will grow without bound. In this work, we present the first known approach to tackle both of these issues. The approach has two stages. First, a subset of the variables (focused variables) is selected that are most useful for a particular task. Second, a task-agnostic and principled method (focused inference) is proposed to select a subset of the measurements that maximizes the information over the focused variables. The approach is then applied to the specific task of robot navigation in an obstacle-laden environment. A landmark selection method is proposed to minimize the probability of collision and then select the set of measurements that best localizes those landmarks. It is shown that the two-stage approach outperforms both only selecting measurement and only selecting landmarks in terms of minimizing the probability of collision. The performance improvement is validated through detailed simulation and real experiments on a Pioneer robot.

This paper presents a collaborative control strategy designed to enable a team of robots to track attracting Lagrangian coherent structures (LCS) and unstable manifolds in two-dimensional flows. Tracking LCS in dynamical systems is important for many applications such as planning energy optimal paths in the ocean and predicting various physical and biological processes in the ocean. Similar to existing approaches, the proposed strategy does not require global information about the dynamics of the surrounding flow, and is based on local sensing, prediction, and correction. Different from existing approaches, the proposed strategy has the ability to track attracting LCS and unstable manifolds in real time through direct computation of the local finite time Lyapunov exponent field. The collaborative control strategy is implemented on a team of robots and the theoretical guarantees of the tracking strategy is briefly discussed. We demonstrate the tracking strategy in simulation using static and time dependent flows and experimentally validate the strategy using a team of micro autonomous surface vehicles (mASVs) in an actual fluid environment.

In everyday applications of robotics, people will likely interact with groups of robots. Most human-robot interaction (HRI) research to date, however, has studied humans interacting with individual robots. Initial research suggests that humans respond differently to individual robots and robots in groups, making responses to groups of robots critical to study. This paper presents a study performed in a public setting familiar to participants (university cafeterias) to examine how participants respond when robots, individually and in groups, enter their space. We examined participant survey and behavioral responses to different numbers of robots (Single or Group) with different behaviors (Social or Functional). Because robots will be used across cultures, we performed the study in Japan and the USA. Across cultures, we found that people interact more with robots in groups than single robots, yet report similar levels of liking for both; participants also rated social robots as more friendly and helpful than functional robots in general. They rated single social robots more positively than a group of social robots, but a group of functional robots more positively than single functional robots. Japanese participants reported liking the robots more than USA participants. This suggests that researchers and designers should be aware of how robot characteristics influence group effects.

The performance of a state lattice motion planning algorithm depends critically on the resolution of the lattice to ensure a balance between solution quality and computation time. There is currently no theoretical basis for selecting the resolution because of its dependence on the robot dynamics and the distribution of obstacles. In this paper, we examine the problem of motion planning on a resolution constrained lattice for a robot with non-linear dynamics operating in an environment with randomly generated disc shaped obstacles sampled from a homogeneous Poisson process. We present a unified framework for computing explicit solutions to two problems - i) the critical planning resolution which guarantees the existence of an infinite collision free trajectory in the search graph ii) the critical speed limit which guarantees infinite collision free motion. In contrast to techniques used by \citet{karaman2012high}, we use a novel approach that maps the problem to parameters of directed asymmetric hexagonal lattice bond percolation. Since standard percolation theory offers no results for this lattice, we map the lattice to an infinite absorbing Markov chain and use results pertaining to its survival to obtain bounds on the parameters. As a result, we are able to derive theoretical expressions that relate the non-linear dynamics of a robot, the resolution of the search graph and the density of the Poisson process. We validate the theoretical bounds using Monte-Carlo simulations for single integrator and curvature constrained systems and are able to validate the previous results presented by Karaman and Frazolli independently using the novel connections introduced in this paper.

Natural substrates are often composed of particulates of varying size, from fine sand to pebbles and boulders. Robot locomotion on such heterogeneous substrates is complicated in part due to large force and kinematic fluctuations introduced by heterogeneities. To systematically explore how heterogeneity affects locomotion, we study the movement of a hexapedal robot (15 cm, 150 g) in a trackway filled with ~1 mm sand, with a larger convex boulder of various shape and roughness embedded within. We investigate how the presence of the boulder affects the robot's trajectory. To do so we develop a fully-automated terrain creation system, the SCATTER (Systematic Creation of Arbitrary Terrain and Testing of Exploratory Robots), to control the initial conditions of the substrate, including sand compaction, boulder distribution, and substrate inclination. Analysis of the robot's trajectory indicates that the interaction with a boulder can be modeled as a scatterer with attractive and repulsive features. Depending on the contact position on the boulder, the robot will be scattered to different directions after the interaction. The trajectory of an individual interaction depends sensitively on the initial conditions, but remarkably this dependence of scattering angle upon initial contact location is universal over a wide range of boulder properties. For a larger heterogeneous field with multiple scatterers, the trajectory of the robot can be estimated using a superposition of the scattering angles from each scatterer. This scattering superposition can be applied to a variety of complex terrains, including heterogeneities of different geometry, orientation, and texture. Our results can aid in development of both deterministic and statistical descriptions of robot locomotion, control and path planning in complex terrain.

In shared autonomy, user input and robot autonomy are combined to control a robot to achieve a goal. Often, the robot does not know a priori which goal the user wants to achieve, and must both predict the user's intended goal, and assist in achieving that goal. We formulate the problem of shared autonomy as a Partially Observable Markov Decision Process with uncertainty over the user's goal. We utilize maximum entropy inverse optimal control to estimate a distribution over the user's goal based on the history of inputs. Ideally, the robot assists the user by solving for an action which minimizes the expected cost-to-go for the (unknown) goal. As solving the POMDP to select the optimal action is intractable, we use hindsight optimization to approximate the solution. In a user study, we compare our method to a standard predict-then-blend approach. We find that our method enables users to accomplish tasks more quickly while utilizing less input. However, when asked to rate each system, users were mixed in their assessment, citing a tradeoff between maintaining control authority and accomplishing tasks quickly.

We present a novel trajectory optimization framework to address the issue of robustness, scalability and efficiency in optimal control and reinforcement learning. Based on prior work in Cooperative Stochastic Differential Game (CSDG) theory, our method performs local trajectory optimization using cooperative controllers. The resulting framework is called Cooperative Game-Differential Dynamic Programming (CG-DDP). Compared to related methods, CG-DDP exhibits improved performance in terms of robustness and efficiency. The proposed framework is also applied in a data-driven fashion for belief space trajectory optimization under learned dynamics. We present experiments showing that CG-DDP can be used for optimal control and reinforcement learning under external disturbances and internal model errors.

Optimization is often difficult to apply to robots due to the presence of significant errors in the optimization model, which may cause constraints to be violated during execution on a real robot. This work presents a method to optimize trajectories with large modeling errors using a combination of robust optimization and parameter learning. In particular it considers the problem of computing a dynamically-feasible trajectory along a fixed path under frictional contact, where friction is uncertain and actuator effort is noisy. It introduces a robust time-scaling method that is able to accept confidence intervals on uncertain parameters, and uses a convex parameterization that allows dynamically-feasible motions under contact to be computed in seconds. This is combined with an iterative learning method that uses feedback from execution to learn confidence bounds on modeling parameters. Experiments on a manipulator performing a ``waiter'' task, on which an object is moved on a carried tray as quickly as possible, demonstrate this method can compensate for modeling uncertainties within a handful of iterations.

This paper shows how to define quantitative measures of a robot's ability to balance itself actively on a single point of support. These measures are expressed as ratios of velocities, and are called velocity gains. This paper builds on earlier work in this area by showing how these gains can be defined and calculated for the case of a general planar robot balancing on a general rolling-contact point in the plane, and the case of a general spatial robot balancing on a general rolling-contact point in 3D space. The case of balancing on a contact area with compliance is also considered. The paper concludes with two examples showing how to use velocity gains in the design of a triple pendulum and the analysis of a hydraulic quadruped.

In the last years several direct (i.e. featureless) monocular SLAM approaches have appeared showing impressive semi-dense or dense scene reconstructions. These works have questioned the need of features, in which consolidated SLAM techniques of the last decade were based. In this paper we present a novel feature-based monocular SLAM system that is more robust, gives more accurate camera poses, and obtains comparable or better semi-dense reconstructions than the current state of the art. Our semi-dense mapping operates over keyframes, optimized by local bundle adjustment, allowing to obtain accurate triangulations from wide baselines. Our novel method to search correspondences, the measurement fusion and the inter-keyframe depth consistency tests allow to obtain clean reconstructions with very few outliers. Against the current trend in direct SLAM, our experiments show that by decoupling the semi-dense reconstruction from the trajectory computation, the results obtained are better. This opens the discussion on the benefits of features even if a semi-dense reconstruction is desired.

We introduce a principled method for multi-robot coordination based on a generic model (termed a MacDec-POMDP) of multi-robot cooperative planning in the presence of stochasticity, uncertain sensing and communication limitations. We present a new MacDec-POMDP planning algorithm that searches over policies represented as finite-state controllers, rather than the existing policy tree representation. Finite-state controllers can be much more concise than trees, are much easier to interpret, and can operate over an infinite horizon. The resulting policy search algorithm requires a substantially simpler simulator that models only the outcomes of executing a given set of motor controllers, not the details of the executions themselves and can to solve significantly larger problems than existing MacDec-POMDP planners. We demonstrate significantly improved performance over previous methods and application to a cooperative multi-robot bartending task, showing that our method can be used for actual multi-robot systems.

Place recognition has long been an incompletely solved problem in that all approaches involve significant com- promises. Current methods address many but never all of the critical challenges of place recognition _ viewpoint-invariance, condition-invariance and minimizing training requirements. Here we present an approach that adapts state-of-the-art object proposal techniques to identify potential landmarks within an image for place recognition. We use the astonishing power of convolutional neural network features to identify matching landmark proposals between images to perform place recognition over extreme appearance and viewpoint variations. Our system does not require any form of training, all components are generic enough to be used off-the-shelf. We present a range of challenging experiments in varied viewpoint and environmental conditions. We demonstrate superior performance to current state-of-the- art techniques. Furthermore, by building on existing and widely used recognition frameworks, this approach provides a highly compatible place recognition system with the potential for easy integration of other techniques such as object detection and semantic scene interpretation.

This paper builds off of recent work on rapidly exponentially stabilizing control Lyapunov functions (RES-CLF) and control Lyapunov function based quadratic programs (CLF-QP) for underactuated hybrid systems. The primary contribution of this paper is developing a robust control technique for underactuated hybrid systems with application to bipedal walking, that is able to track desired trajectories with significant model perturbation (mass and inertia increased by up to 200%.) We evaluate our proposed control design on a model of RABBIT, a five-link planar bipedal robot.

This paper presents a new framework for the generation of high-speed running jumps to clear terrain obstacles in quadrupedal robots. Our methods enable the quadruped to autonomously jump over obstacles up to 40 cm in height within a single control framework. Specifically, we propose new control system components, layered on top of a low-level running controller, which actively modify the approach and select stance force profiles as required to clear a sensed obstacle. The approach controller enables the quadruped to end in a preferable state relative to the obstacle just before the jump. This multi-step gait planning is formulated as a multiple-horizon model predictive control problem and solved at each step through quadratic programming. Ground reaction force profiles to execute the running jump are selected through constrained nonlinear optimization on a simplified model of the robot that possesses polynomial dynamics. Exploiting the simplified structure of these dynamics, the presented method greatly accelerates the computation of otherwise costly function and constraint evaluations that are required during optimization. With these considerations, the new algorithms allow for online planning that is critical for reliable response to unexpected situations. Experimental results, for a stand-alone quadruped with on-board power and computation, show the viability of this approach, and represent important steps towards broader dynamic maneuverability in experimental machines.

The application of autonomous robots to efficiently locate small wildlife species has the potential to provide significant ecological insights not previously possible using traditional land-based survey techniques, and a basis for improved conservation policy and management. We present an approach for autonomously localizing radio-tagged wildlife using a small aerial robot. We present a novel two-point phased array antenna system that yields unambiguous bearing measurements and an associated uncertainty measure. Our estimation and information-based planning algorithms incorporate this bearing uncertainty to choose observation points that improve confidence in the location estimate. These algorithms run online in real time and we report experimental results that show successful autonomous localization of stationary radio tags and live radio-tagged birds.

In unlabeled multi-robot motion planning several interchangeable robots operate in a common workspace. The goal is to move the robots to a set of target positions such that each position will be occupied by some robot. In this paper, we study this problem for the specific case of unit-square robots moving amidst polygonal obstacles and show that it is PSPACE-hard. We also consider three additional variants of this problem and show that they are all PSPACE-hard as well. To the best of our knowledge, this is the first hardness proof for the unlabeled case. Furthermore, our proofs can be used to show that the labeled variant (where each robot is assigned with a specific target position), again, for unit-square robots, is PSPACE-hard as well, which sets another precedence, as previous hardness results require the robots to be of different shapes.

To operate reliably in real-world traffic, an autonomous car must evaluate the consequences of its potential actions by anticipating the uncertain intentions of other traffic participants. This paper presents an integrated behavioral inference and decision-making approach that models vehicle behavior for both our vehicle and nearby vehicles as a discrete set of closed-loop policies that react to the actions of other agents. Each policy captures a distinct high-level behavior and intention, such as driving along a lane or turning at an intersection. We first employ Bayesian changepoint detection on the observed history of states of nearby cars to estimate the distribution over potential policies that each nearby car might be executing. We then sample policies from these distributions to obtain high-likelihood actions for each participating vehicle. Through closed-loop forward simulation of these samples, we can evaluate the outcomes of the interaction of our vehicle with other participants (e.g., a merging vehicle accelerates and we slow down to make room for it, or the vehicle in front of ours suddenly slows down and we decide to pass it). Based on those samples, our vehicle then executes the policy with the maximum expected reward value. Thus, our system is able to make decisions based on coupled interactions between cars in a tractable manner. This work extends our previous multipolicy system by incorporating behavioral anticipation into decision-making to evaluate sampled potential vehicle interactions. We evaluate our approach using real-world traffic-tracking data from our autonomous vehicle platform, and present decision-making results in simulation involving highway traffic scenarios.

We study the problem of path planning for unlabeled (indistinguishable) unit-disc robots in a planar environment cluttered with polygonal obstacles. We introduce an algorithm which minimizes the total path length, i.e., the sum of lengths of the individual paths. Our algorithm is guaranteed to find a solution if one exists, or report that none exists otherwise. It runs in time $\tilde{O}(m^4+m^2n^2)$, where $m$ is the number of robots and $n$ is the total complexity of the workspace. Moreover, the total length of the returned solution is at most $O(\text{OPT}+O(m))$, where OPT is the optimal-solution cost. To the best of our knowledge this is the first algorithm for the problem that has such guarantees. The algorithm has been implemented in an exact manner and we present experimental results that attest to its efficiency.