The International Journal of Robotics Research

This paper describes a framework that enables robots to efficiently learn human-centric models of their environment from natural language descriptions. Typical semantic mapping approaches are limited to augmenting metric maps with higher-level properties of the robot’s surroundings (e.g. place type, object locations) that can be inferred from the robot’s sensor data, but do not use this information to improve the metric map. The novelty of our algorithm lies in fusing high-level knowledge that people can uniquely provide through speech with metric information from the robot’s low-level sensor streams. Our method jointly estimates a hybrid metric, topological, and semantic representation of the environment. This semantic graph provides a common framework in which we integrate information that the user communicates (e.g. labels and spatial relations) with metric observations from low-level sensors. Our algorithm efficiently maintains a factored distribution over semantic graphs based upon the stream of natural language and low-level sensor information. We detail the means by which the framework incorporates knowledge conveyed by the user’s descriptions, including the ability to reason over expressions that reference yet unknown regions in the environment. We evaluate the algorithm’s ability to learn human-centric maps of several different environments and analyze the knowledge inferred from language and the utility of the learned maps. The results demonstrate that the incorporation of information from free-form descriptions increases the metric, topological, and semantic accuracy of the recovered environment model.

This paper reports on an exact, real-time solution for server–client cooperative localization over a faulty and extremely bandwidth-limited underwater communication channel. Our algorithm, termed the origin state method, enables a ‘server’ vehicle to broadcast its navigation information to multiple ‘client’ vehicles over a bandwidth-limited and faulty communication channel. The server’s broadcasted pose-graph can be used in conjunction with an estimator on the client to exactly reproduce the corresponding server–client centralized estimate. We present an evaluation over an extensive real-time field implementation of the proposed algorithm for a multi-agent autonomous underwater vehicle network using underwater acoustic modems to communicate in a synchronous-clock transmission framework.

The construction of feedback control laws for underactuated nonlinear robotic systems with input saturation limits is crucial for dynamic robotic tasks such as walking, running, or flying. Existing techniques for feedback control design are either restricted to linear systems, rely on discretizations of the state space, or require solving a nonconvex optimization problem that requires feasible initialization. This paper presents a method for designing feedback controllers for polynomial systems that maximize the size of the time-limited backwards reachable set (BRS). In contrast to traditional approaches based on Lyapunov’s criteria for stability, we rely on the notion of occupation measures to pose this problem as an infinite-dimensional linear program which can then be approximated in finite dimension via semidefinite programs (SDPs). The solution to each SDP yields a polynomial control policy and an outer approximation of the largest achievable BRS which is well suited for use in a trajectory library or feedback motion planning algorithm. We demonstrate the efficacy and scalability of our approach on six nonlinear systems. Comparisons to an infinite-horizon linear quadratic regulator approach and an approach relying on Lyapunov’s criteria for stability are also included in order to illustrate the improved performance of the presented technique.

This paper presents a method for generating dynamically feasible, keyframe-interpolating motions for robots undergoing contact, such as in legged locomotion and manipulation. The first stage generates a twice-differentiable interpolating path that obeys kinematic contact constraints up to a user-specified tolerance. The second stage optimizes speeds along the path to minimize time while satisfying dynamic constraints. The method supports velocity, acceleration, and torque constraints, and polyhedral contact friction constraints at an arbitrary number of contact points. The method is numerically stable, and empirical running time is weakly linear in the number of degrees of freedom and polynomial in the time-domain grid resolution. Experiments demonstrate that full-body motions for robots with 100 degrees of freedom and dozens of contact points are calculated in seconds.

We present a new optimization-based approach for robotic motion planning among obstacles. Like CHOMP (Covariant Hamiltonian Optimization for Motion Planning), our algorithm can be used to find collision-free trajectories from naïve, straight-line initializations that might be in collision. At the core of our approach are (a) a sequential convex optimization procedure, which penalizes collisions with a hinge loss and increases the penalty coefficients in an outer loop as necessary, and (b) an efficient formulation of the no-collisions constraint that directly considers continuous-time safety Our algorithm is implemented in a software package called TrajOpt.

We report results from a series of experiments comparing TrajOpt with CHOMP and randomized planners from OMPL, with regard to planning time and path quality. We consider motion planning for 7 DOF robot arms, 18 DOF full-body robots, statically stable walking motion for the 34 DOF Atlas humanoid robot, and physical experiments with the 18 DOF PR2. We also apply TrajOpt to plan curvature-constrained steerable needle trajectories in the SE(3) configuration space and multiple non-intersecting curved channels within 3D-printed implants for intracavitary brachytherapy. Details, videos, and source code are freely available at: http://rll.berkeley.edu/trajopt/ijrr.

We propose three sampling-based motion planning algorithms for generating informative mobile robot trajectories. The goal is to find a trajectory that maximizes an information quality metric (e.g. variance reduction, information gain, or mutual information) and also falls within a pre-specified budget constraint (e.g. fuel, energy, or time). Prior algorithms have employed combinatorial optimization techniques to solve these problems, but existing techniques are typically restricted to discrete domains and often scale poorly in the size of the problem. Our proposed rapidly exploring information gathering (RIG) algorithms combine ideas from sampling-based motion planning with branch and bound techniques to achieve efficient information gathering in continuous space with motion constraints. We provide analysis of the asymptotic optimality of our algorithms, and we present several conservative pruning strategies for modular, submodular, and time-varying information objectives. We demonstrate that our proposed techniques find optimal solutions more quickly than existing combinatorial solvers, and we provide a proof-of-concept field implementation on an autonomous surface vehicle performing a wireless signal strength monitoring task in a lake.

The partially observable Markov decision process (POMDP) provides a principled mathematical model for integrating perception and planning, a major challenge in robotics. While there are efficient algorithms for moderately large discrete POMDPs, continuous models are often more natural for robotic tasks, and currently there are no practical algorithms that handle continuous POMDPs at an interesting scale. This paper presents an algorithm for continuous-state, continuous-observation POMDPs. We provide experimental results demonstrating its potential in robot planning and learning under uncertainty and a theoretical analysis of its performance. A direct benefit of the algorithm is to simplify model construction.