Locomotion Group Paper and Multimedia News
https://groups.csail.mit.edu/locomotion/
MIT's Robot Locomotion Group publications and videos. Updated whenever a paper/video is posted, or updated on the group website.Robust Output Feedback Control with Guaranteed Constraint Satisfaction
http://groups.csail.mit.edu/robotics-center/public_papers/Sadraddini20.pdf
Thu, 2 Jan 2020 00:00:00 ESTby Sadra Sadraddini and Russ Tedrake
<p> We propose a method to control linear time-varying (LTV) discrete-time systems subject to bounded process disturbances and measurable outputs with bounded noise, and polyhedral constraints over system inputs and states. We search over control policies that map the history of measurable outputs to the current control input. We solve the problem in two stages. First, we abstract the system to a linear one that predicts future observations using the past observations. The representation power of zonotopes characterizes the bounded error between the abstract system and the actual observations. Next, we synthesize output feedback controllers that are affine maps of abstract system errors by solving convex linear/quadratic programs such that constraint satisfaction is guaranteed for all allowable sequences of observation noise and process disturbances. Our method does not require any assumptions about system controllability and observability, and the controller design does not directly take into account the state-space dynamics, and its implementation does not require a full state observer. Instead, the intuition lies on the fact that imperfect observability may be sufficient to design a correct controller. We provide the polytopic representation of observability errors and reachable sets in the form of zonotopes. Illustrative examples are included.
<p><i> To Appear at HSCC 2020. Comments welcome.</i>Warm Start of Mixed-Integer Programs for Model Predictive Control of Hybrid Systems
http://groups.csail.mit.edu/robotics-center/public_papers/Marcucci19.pdf
Sun, 20 Oct 2019 00:00:00 ESTby Tobia Marcucci and Russ Tedrake
<p> In hybrid Model Predictive Control (MPC), a Mixed-Integer Convex Program (MICP) is solved at each sampling time to compute the optimal control action. Although these optimizations are generally very demanding, in MPC we expect consecutive problem instances to be nearly identical. This paper addresses the question of how computations performed at one time step can be reused to accelerate ('warm start') the solution of subsequent MICPs.
Reoptimization is not a rare practice in integer programming: for small variations of certain problem data, the branch-and-bound algorithm allows an efficient reuse of its search tree and the dual bounds of its leaf nodes. In this paper we extend these ideas to the receding-horizon settings of MPC. The warm-start algorithm we propose copes naturally with arbitrary model errors, has negligible computational cost, and frequently enables an a-priori pruning of most of the search space. Theoretical considerations and experimental evidence show that the proposed method tends to reduce the combinatorial complexity of the hybrid MPC problem to that of a one-step look-ahead optimization, greatly easing the online computation burden.
<p> Supplemental materials:
<a href=http://arxiv.org/abs/1910.08251> http://arxiv.org/abs/1910.08251 </a>
<p><i> Under review (arXiv available). Comments welcome.</i>The Nearest Polytope Problem: Algorithms and Application to Controlling Hybrid Systems
http://groups.csail.mit.edu/robotics-center/public_papers/Wu20a.pdf
Fri, 27 Sep 2019 00:00:00 ESTby Albert Wu and Sadra Sadraddini and Russ Tedrake
<p> We present three algorithms for solving the nearest polytope problem: given a list of polytopes and a distance metric in Euclidean space, find the nearest polytope to a query point. We consider the AH-polytope representation, which generalizes the H-polytope representation and is particularly useful in the context of control. Through preprocessing the polytopes into efficient data structures, we avoid exhaustive search at query time. We discuss the properties of the algorithms and compare their performances using polytopic datasets motivated by control applications, including sampling-based motion planning and model predictive control.
<p><i> Under review. Comments welcome.</i>Self-Supervised Correspondence in Visuomotor Policy Learning
http://groups.csail.mit.edu/robotics-center/public_papers/Florence20.pdf
Sun, 15 Sep 2019 00:00:00 ESTby Peter Florence and Lucas Manuelli and Russ Tedrake
<p> In this paper we explore using self-supervised correspondence for improving the generalization performance and sample efficiency of visuomotor policy learning. Prior work has primarily used approaches such as autoencoding, pose-based losses, and end-to-end policy optimization in order to train the visual portion of visuomotor policies. We instead propose an approach using self-supervised dense visual correspondence training, and show this enables visuomotor policy learning with surprisingly high generalization performance with modest amounts of data: using imitation learning, we demonstrate extensive hardware validation on challenging manipulation tasks with as few as 50 demonstrations. Our learned policies can generalize across classes of objects, react to deformable object configurations, and manipulate textureless symmetrical objects in a variety of backgrounds, all with closed-loop, real-time vision-based policies. Simulated imitation learning experiments suggest that correspondence training offers sample complexity and generalization benefits compared to autoencoding and end-to-end training.
<p> Supplemental materials:
<a href=https://sites.google.com/view/visuomotor-correspondence> https://sites.google.com/view/visuomotor-correspondence </a>
, <a href=https://youtu.be/nDRBKb4AGmA> https://youtu.be/nDRBKb4AGmA </a>
<p><i> Under review. Comments welcome.</i>Generative Modeling of Environments with Scene Grammars and Variational Inference
http://groups.csail.mit.edu/robotics-center/public_papers/Izatt20.pdf
Sun, 15 Sep 2019 00:00:00 ESTby Gregory Izatt and Russ Tedrake
<p> How do we verify that a cleaning robot that we have tested only in a simulator and in case studies in the lab, will work in every house in the world? A critical step in answering that question is to establish a quantitative understanding of the distribution of environments that a robot will face when when it is deployed. However, even restricting attention only to the distribution of objects in a scene, these distributions over environments are nontrivial: they describe mixtures of discrete and continuous variables related to the number, type, poses, and attributes of objects in the scene. We describe a probabilistic generative model that uses scene trees to capture hierarchical relationships between collections of objects, as well as a variational inference algorithm for tuning that model to best match a set of observed environments without any need for tediously labeled parse trees. We demonstrate that this model can accurately capture the distribution of a pair of nontrivial manipulation-relevant datasets and be deployed as a density estimator and outlier detector for novel environments.
<p><i> Under review. Comments welcome.</i>R3T: Rapidly-exploring Random Reachable Set Tree for Optimal Kinodynamic Planning of Nonlinear Hybrid Systems
http://groups.csail.mit.edu/robotics-center/public_papers/Wu20.pdf
Sun, 15 Sep 2019 00:00:00 ESTby Albert Wu and Sadra Sadraddini and Russ Tedrake
<p> We introduce R3T, a reachability-based variant of the rapidly-exploring random tree (RRT) algorithm that is suitable for (optimal) kinodynamic planning in nonlinear and hybrid systems. We developed tools to approximate reachable sets using polytopes and perform sampling-based planning with them. This method provides a unique advantage in the case of hybrid systems: different dynamic modes in the reachable set can be explicitly represented using multiple polytopes. We show that R3T retains probabilistic completeness and asymptotic optimality of RRT/RRT*. Moreover, R3T provides a formal verification method for reachability analysis of nonlinear systems. The advantages of R3T are demonstrated with case studies on nonlinear, hybrid, and contact-rich robotic systems.
<p> Supplemental materials:
<a href=https://youtu.be/E8TICePNqE0> https://youtu.be/E8TICePNqE0 </a>
<p><i> Under review. Comments welcome.</i>k{PAM-SC}: Generalizable {M}anipulation Planning using {K}ey{P}oint {A}ffordance and {S}hape {C}ompletion
http://groups.csail.mit.edu/robotics-center/public_papers/Gao20.pdf
Sun, 15 Sep 2019 00:00:00 ESTby Wei Gao and Russ Tedrake
<p> Manipulation planning is the task of computing robot trajectories that move a set of objects to their target configuration while satisfying physically feasibility. In contrast to existing works that assume known object templates, we are interested in manipulation planning for a category of objects with potentially unknown instances and large intra-category shape variation. To achieve it, we need an object representation with which the manipulation planner can reason about both the physical feasibility and desired object configuration, while being generalizable to novel instances. The widely-used pose representation is not suitable, as representing an object with a parameterized transformation from a fixed template cannot capture large intra-category shape variation. Hence building on our previous work kPAM, we propose a new hybrid object representation consisting of semantic keypoint and dense geometry (a point cloud or mesh) as the interface between the perception module and motion planner. Leveraging advances in learning-based keypoint detection and shape completion, both dense geometry and keypoints can be perceived from raw sensor input. Using the proposed hybrid object representation, we formulate the manipulation task as a motion planning problem which encodes both the object target configuration and physical feasibility for a category of objects. In this way, many existing manipulation planners can be generalized to categories of objects, and the resulting perception-to-action manipulation pipeline is robust to large intra-category shape variation. Extensive hardware experiments demonstrate our pipeline can produce robot trajectories that accomplish tasks with never-before-seen objects.
<p> Supplemental materials:
<a href=https://sites.google.com/view/generalizable-manipulation/> https://sites.google.com/view/generalizable-manipulation/ </a>
<p><i> Under review. Comments welcome.</i>{kPAM: KeyPoint Affordances for Category-Level Robotic Manipulation}
https://sites.google.com/view/kpam
Mon, 18 Mar 2019 00:00:00 ESTby Lucas Manuelli* and Wei Gao* and Peter Florence and Russ Tedrake
<p> We would like robots to achieve purposeful manipulation by placing any instance from a category of objects into a desired set of goal states. Existing manipulation pipelines typically specify the desired configuration as a target 6-DOF pose and rely on explicitly estimating the pose of the manipulated objects. However, representing an object with a parameterized transformation defined on a fixed template cannot capture large intra-category shape variation, and specifying a target pose at a category level can be physically infeasible or fail to accomplish the task -- e.g. knowing the pose and size of a coffee mug relative to some canonical mug is not sufficient to successfully hang it on a rack by its handle. Hence we propose a novel formulation of category-level manipulation that uses semantic 3D keypoints as the object representation. This keypoint representation enables a simple and interpretable specification of the manipulation target as geometric costs and constraints on the keypoints, which flexibly generalizes existing pose-based manipulation methods. Using this formulation, we factor the manipulation policy into instance segmentation, 3D keypoint detection, optimization-based robot action planning and local dense-geometry-based action execution. This factorization allows us to leverage advances in these sub-problems and combine them into a general and effective perception-to-action manipulation pipeline. Our pipeline is robust to large intra-category shape variation and topology changes as the keypoint representation ignores task-irrelevant geometric details. Extensive hardware experiments demonstrate our method can reliably accomplish tasks with never-before seen objects in a category, such as placing shoes and mugs with significant shape variation into category level target configurations.
<p><i> Under review. Comments welcome.</i>Linear Encodings for Polytope Containment Problems
https://arxiv.org/abs/1903.05214
Wed, 14 Mar 2019 00:00:00 ESTby Sadra Sadraddini and Russ Tedrake
<p> The polytope containment problem is deciding whether a polytope is a contained within another polytope. This problem is rooted in computational convexity, and arises in applications such as verification and control of dynamical systems. The complexity heavily depends on how the polytopes are represented. Describing polytopes by their hyperplanes (H-polytopes) is a popular representation. In many applications we use affine transformations of H-polytopes, which we refer to as AH-polytopes. Zonotopes, orthogonal projections of H-polytopes, and convex hulls/Minkowski sums of multiple H-polytopes can be efficiently represented as AH-polytopes. While there exists efficient necessary and sufficient conditions for AH-polytope in H-polytope containment, the case of AH-polytope in AH-polytope is known to be NP-complete. In this paper, we provide a sufficient condition for this problem that is cast as a linear program with size that grows linearly with the number of hyperplanes of each polytope. Special cases on zonotopes, Minkowski sums, convex hulls, and disjunctions of H-polytopes are studied. These efficient encodings enable us to designate certain components of polytopes as decision variables, and incorporate them into a convex optimization problem. We present examples on the zonotope containment problem, polytopic Hausdorff distances, zonotope order reduction, inner approximations of orthogonal projections, and demonstrate the usefulness of our results on formal controller verification and synthesis for hybrid systems.
<p><i> Under review. Comments welcome.</i>Mixed-Integer Formulations for Optimal Control of Piecewise-Affine Systems
http://groups.csail.mit.edu/robotics-center/public_papers/Marcucci18.pdf
Tue, 23 Oct 2018 00:00:00 ESTby Tobia Marcucci and Russ Tedrake
<p> In this paper we study how to formulate the optimal control problem for a piecewise-affine dynamical system as a mixed-integer program. Problems of this form arise typically in hybrid Model Predictive Control (MPC), where at every time step an open-loop optimal control sequence is computed via numerical optimization and applied to the system in a moving horizon fashion. Not surprisingly, the efficiency in the formulation of the underlying mathematical program has a crucial influence on computation times, and hence on the applicability of hybrid MPC to high-dimensional systems.
We leverage on modern concepts and results from the fields of mixed-integer and disjunctive programming to conduct a comprehensive analysis of this formulation problem: among the outcomes enabled by this novel perspective is the derivation of multiple highly-efficient formulations of the control problem, each of which represents a different tradeoff between the two most important features of a mixed-integer program, the size and the strength. First in theory, then through a numerical example, we show how all the proposed methods outperform the traditional approach employed in MPC, enabling the solution of larger-scale problems.
<p><i> Under review. Comments welcome.</i>Learning Particle Dynamics for Manipulating Rigid Bodies, Deformable Objects, and Fluids
http://groups.csail.mit.edu/robotics-center/public_papers/Li18a.pdf
Tue, 02 Oct 2018 00:00:00 ESTby Yunzhu Li and Jiajun Wu and Russ Tedrake and Joshua B. Tenenbaum and Antonio Torralba
<p> Real-life control tasks involve matters of various substances---rigid or soft bodies, liquid, gas---each with distinct physical behaviors. This poses challenges to traditional rigid-body physics engines. Particle-based simulators have been developed to model the dynamics of these complex scenes; however, relying on approximation techniques, their simulation often deviates from real-world physics, especially in the long term. In this paper, we propose to learn a particle-based simulator for complex control tasks. Combining learning with particle-based systems brings in two major benefits: first, the learned simulator, just like other particle-based systems, acts widely on objects of different materials; second, the particle-based representation poses strong inductive bias for learning: particles of the same type have the same dynamics within. This enables the model to quickly adapt to new environments of unknown dynamics within a few observations. We demonstrate robots achieving complex manipulation tasks using the learned simulator, such as manipulating fluids and deformable foam, with experiments both in simulation and in the real world. Our study helps lay the foundation for robot learning of dynamic scenes with particle-based representations.
<p> Supplemental materials:
<a href=http://dpi.csail.mit.edu/> http://dpi.csail.mit.edu/ </a>
, <a href=https://www.youtube.com/watch?v=FrPpP7aW3Lg> https://www.youtube.com/watch?v=FrPpP7aW3Lg </a>
, <a href=https://arxiv.org/abs/1810.01566> https://arxiv.org/abs/1810.01566 </a>
<p><i> Under review. Comments welcome.</i>{LVIS}: Learning from Value Function Intervals for Contact-Aware Robot Controllers
http://groups.csail.mit.edu/robotics-center/public_papers/Deits18.pdf
Wed, 19 Sept 2018 00:00:00 ESTby Robin Deits and Twan Koolen and Russ Tedrake
<p> Guided policy search is a popular approach for
training controllers for high-dimensional systems, but it has a
number of pitfalls. Non-convex trajectory optimization has local
minima, and non-uniqueness in the optimal policy itself can
mean that independently-optimized samples do not describe a
coherent policy from which to train. We introduce LVIS, which
circumvents the issue of local minima through global mixed-integer
optimization and the issue of non-uniqueness through
learning the optimal value function (or cost-to-go) rather than
the optimal policy. To avoid the expense of solving the mixed-integer
programs to full global optimality, we instead solve them
only partially, extracting intervals containing the true cost-togo
from early termination of the branch-and-bound algorithm.
These interval samples are used to weakly supervise the training
of a neural net which approximates the true cost-to-go. Online,
we use that learned cost-to-go as the terminal cost of a one-step
model-predictive controller, which we solve via a small mixed-integer
optimization. We demonstrate the LVIS approach on
a cart-pole system with walls and a planar humanoid robot
model and show that it can be applied to a fundamentally
hard problem in feedback control -- control through contact.
<p> Supplemental materials:
<a href=https://arxiv.org/abs/1809.05802> https://arxiv.org/abs/1809.05802 </a>
<p><i> Under review. Comments welcome.</i>Sampling-based Polytopic Trees for Approximate Optimal Control of Piecewise Affine Systems
http://groups.csail.mit.edu/robotics-center/public_papers/Sadraddini18.pdf
Wed, 19 Sept 2018 00:00:00 ESTby Sadra Sadraddini and Russ Tedrake
<p> Piecewise affine (PWA) systems are widely used to model highly nonlinear behaviors such as contact dynamics in robot locomotion and manipulation. Existing control techniques for PWA systems have computational drawbacks, both in offline design and online implementation. In this paper, we introduce a method to obtain feedback control policies and a corresponding set of admissible initial conditions for discrete-time PWA systems such that all the closed-loop trajectories reach a goal polytope, while a cost function is optimized. The idea is conceptually similar to LQR-trees Tedrake et al., 2010, which consists of 3 steps: (1) open-loop trajectory optimization, (2) feedback control for computation of funnels of states around trajectories, and (3)
repeating (1) and (2) in a way that the funnels are grown
backward from the goal in a tree fashion and fill the state-space
as much as possible. We show PWA dynamics can be exploited
to combine step (1) and (2) into a single step that is tackled using
mixed-integer convex programming, which makes the method
suitable for dealing with hard constraints. Illustrative examples
on contact-based dynamics are presented.
<p> Supplemental materials:
<a href=https://youtu.be/gGH0EuIzkgY> https://youtu.be/gGH0EuIzkgY </a>
, <a href=https://arxiv.org/abs/1809.09716> https://arxiv.org/abs/1809.09716 </a>
<p><i> Under review. Comments welcome.</i>Propagation Networks for Model-Based Control Under Partial Observation
http://groups.csail.mit.edu/robotics-center/public_papers/Li18.pdf
Wed, 19 Sept 2018 00:00:00 ESTby Yunzhu Li and Jiajun Wu and Jun-Yan Zhu and Joshua B. Tenenbaum and Antonio Torralba and Russ Tedrake
<p> There has been an increasing interest in learning dynamics simulators for model-based control. Compared with off-the-shelf physics engines, a learnable simulator can quickly adapt to unseen objects, scenes, and tasks. However, existing models like interaction networks only work for fully observable systems; they also only consider pairwise interactions within a single time step, both restricting their use in practical systems. We introduce Propagation Networks (PropNet), a differentiable, learnable dynamics model that handles partially observable scenarios and enables instantaneous propagation of signals beyond pairwise interactions. Experiments show that our propagation networks not only outperform current learnable physics engines in forward simulation, but also achieve superior performance on various control tasks. Compared with existing model-free deep reinforcement learning algorithms, model-based control with propagation networks is more accurate, efficient, and generalizable to new, partially observable scenes and tasks.
<p> Supplemental materials:
<a href=http://propnet.csail.mit.edu/> http://propnet.csail.mit.edu/ </a>
, <a href=https://arxiv.org/abs/1809.11169> https://arxiv.org/abs/1809.11169 </a>
, <a href=https://www.youtube.com/watch?v=ZAxHXegkz48> https://www.youtube.com/watch?v=ZAxHXegkz48 </a>
<p><i> Under review. Comments welcome.</i>A Supervised Approach to Predicting Noise in Depth Images
http://groups.csail.mit.edu/robotics-center/public_papers/Sweeney18a.pdf
Wed, 19 Sept 2018 00:00:00 ESTby Chris Sweeney and Greg Izatt and Russ Tedrake
<p> Modern robotic systems are very complex and need to be tested in simulations with detailed sensor noise models to effectively verify robotic behavior. Depth imagery in particular comes with significant noise in the form of scene-dependent pixel-wise dropouts and distortions. Unfortunately, many depth camera simulations contain limited noise models, or can only support generating realistic depth images of simple scenes, which limits their usefulness in effectively testing perception algorithms. We propose a data driven approach to generate more realistic noise for complex simulated environments by using a convolutional neural network (CNN) to predict which pixels of a simulated noise-free depth image will not have returns (no-depth-return pixels, or NDP). We choose to focus on NDP here, as these dropouts are the most common and dramatic form of depth image noise. To train this network, we use reconstructed real-world scenes from the Label Fusion dataset to provide ground truth depth for each noisy depth image used to scan the scene. We use the resulting noise-free and noisy depth image pairs as labeled examples and train the network to predict which pixels of the noise-free image will be NDP. When used to post-process a simulation of a depth sensor, this system produces realistic depth images, even in cluttered scenes. To demonstrate that our approach successfully closes the reality gap for depth imagery, we show that the popular ICP algorithm for object pose estimation fails more realistically on our CNN-corrupted simulated depth images than on uncorrupted depth images and unsupervised domain adaptation baselines.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=_IURYCbGR88> https://www.youtube.com/watch?v=_IURYCbGR88 </a>
<p><i> Under review. Comments welcome.</i>Controller Synthesis for Discrete-time Hybrid Polynomial Systems via Occupation Measures
http://groups.csail.mit.edu/robotics-center/public_papers/Han18a.pdf
Wed, 19 Sept 2018 00:00:00 ESTby Weiqiao Han and Russ Tedrake
<p> We consider the feedback design for stabilizing a rigid body system by making and breaking multiple contacts with the environment without prespecifying the timing or the number of occurrence of the contacts.
We model such a system as a discrete-time hybrid polynomial system, where the state-input space is partitioned into several polytopic regions with each region associated with a different polynomial dynamics equation.
Based on the notion of occupation measures, we present a novel controller synthesis approach that solves finite-dimensional semidefinite programs as approximations to an infinite-dimensional linear program to stabilize the system.
The optimization formulation is simple and convex, and for any fixed degree of approximations the computational complexity is polynomial in the state and control input dimensions.
We illustrate our approach on some robotics examples.
<p> Supplemental materials:
<a href=https://arxiv.org/abs/1809.06715> https://arxiv.org/abs/1809.06715 </a>
<p><i> Under review. Comments welcome.</i>Dense Object Nets: Learning Dense Visual Object Descriptors By and For Robotic Manipulation
http://groups.csail.mit.edu/robotics-center/public_papers/Florence18a.pdf
Wed, 19 Sept 2018 00:00:00 ESTby Peter R. Florence* and Lucas Manuelli* and Russ Tedrake
<p> What is the right object representation for manipulation? We would like robots to visually perceive scenes and learn an understanding of the objects in them that (i) is task-agnostic and can be used as a building block for a variety of manipulation tasks, (ii) is generally applicable to both rigid and non-rigid objects, (iii) takes advantage of the strong priors provided by 3D vision, and (iv) is entirely learned from self-supervision. This is hard to achieve with previous methods: much recent work in grasping does not extend to grasping specific objects or other tasks, whereas task-specific learning may require many trials to generalize well across object configurations or other tasks. In this paper we present Dense Object Nets, which build on recent developments in self-supervised dense descriptor learning, as a consistent object representation for visual understanding and manipulation. We demonstrate they can be trained quickly (approximately 20 minutes) for a wide variety of previously unseen and potentially non-rigid objects. We additionally present novel contributions to enable multi-object descriptor learning, and show that by modifying our training procedure, we can either acquire descriptors which generalize across classes of objects, or descriptors that are distinct for each object instance. Finally, we demonstrate the novel application of learned dense descriptors to robotic manipulation. We demonstrate grasping of specific points on an object across potentially deformed object configurations, and demonstrate using class general descriptors to transfer specific grasps across objects in a class.
<p> Supplemental materials:
<a href=https://arxiv.org/abs/1806.08756> https://arxiv.org/abs/1806.08756 </a>
, <a href=https://www.youtube.com/watch?v=L5UW1VapKNE> https://www.youtube.com/watch?v=L5UW1VapKNE </a>
, <a href=https://github.com/RobotLocomotion/pytorch-dense-correspondence> https://github.com/RobotLocomotion/pytorch-dense-correspondence </a>
<p><i> Accepted for publication. Comments welcome.</i>Evaluating Robustness of Neural Networks with Mixed Integer Programming
http://groups.csail.mit.edu/robotics-center/public_papers/Tjeng17.pdf
Mon, 20 Nov 2017 00:00:00 ESTby Vincent Tjeng and Kai Xiao and Russ Tedrake
<p> Neural networks trained only to optimize for training accuracy can often be fooled by adversarial examples --- slightly perturbed inputs misclassified with high confidence. Verification of networks enables us to gauge their vulnerability to such adversarial examples. We formulate verification of piecewise-linear neural networks as a mixed integer program. On a representative task of finding minimum adversarial distortions, our verifier is two to three orders of magnitude quicker than the state-of-the-art. We achieve this computational speedup via tight formulations for non-linearities, as well as a novel presolve algorithm that makes full use of all information available. The computational speedup allows us to verify properties on convolutional and residual networks with over 100,000 ReLUs --- several orders of magnitude more than networks previously verified by any complete verifier. In particular, we determine for the first time the exact adversarial accuracy of an MNIST classifier to perturbations with bounded l-infinity norm epsilon=0.1: for this classifier, we find an adversarial example for 4.38 percent of samples, and a certificate of robustness to norm-bounded perturbations for the remainder. Across all robust training procedures and network architectures considered, and for both the MNIST and CIFAR-10 datasets, we are able to certify more samples than the state-of-the-art and find more adversarial examples than a strong first-order attack.
<p> Supplemental materials:
<a href=https://openreview.net/forum?id=HyGIdiRqtm> https://openreview.net/forum?id=HyGIdiRqtm </a>
<p><i> Posted on arxiv while under review. Comments welcome.</i>Compositional Verification of Large-Scale Nonlinear Systems via Sums-of-Squares Optimization
http://groups.csail.mit.edu/robotics-center/public_papers/Shen17.pdf
Thu, 29 Sept 2017 00:00:00 ESTby Shen Shen and Russ Tedrake
<p> We consider the computationally prohibitive problem of stability and invariance verification of large-scale dynamical systems. We exploit the natural interconnected structure often arising from such systems in practice (i.e., they are interconnections of low-dimensional subsystems), and propose a compositional method. We construct independently for each subsystem a Lyapunov-like function, and guarantee that their sum automatically certifies the original high-dimensional system is stable or invariant. For linear time invariant systems, our method produces block-diagonal Lyapunov matrices without structural assumptions commonly found in the literature. For polynomial system tasks, our formulation results in significantly smaller sum-of-squares programs. Demonstrated on numerical and practical examples, our algorithms can handle problems beyond the reach of direct optimizations, and are orders of magnitude faster than existing compositional methods.
<p><i> Under review. Comments welcome.</i>NanoMap: Fast, Uncertainty-Aware Proximity Queries with Lazy Search over Local 3D Data
http://groups.csail.mit.edu/robotics-center/public_papers/Florence17.pdf
Fri, 15 Sep 2017 00:00:00 ESTby Peter R. Florence and John Carter and Jake Ware and Russ Tedrake
<p> We would like robots to be able to safely navigate at high speed, efficiently use local 3D information, and robustly plan motions that consider pose uncertainty of measurements in a local map structure. This is hard to do with previously existing mapping approaches, like occupancy grids, that are focused on incrementally fusing 3D data into a common world frame. In particular, both their fragile sensitivity to state estimation errors and computational cost can be limiting. We develop an alternative framework, NanoMap, which alleviates the need for global map fusion and enables a motion planner to efficiently query pose-uncertainty-aware local 3D geometric information. The key idea of NanoMap is to store a history of noisy relative pose transforms and search over a corresponding set of depth sensor measurements for the minimum-uncertainty view of a queried point in space. This approach affords a variety of capabilities not offered by traditional mapping techniques: (a) the pose uncertainty associated with 3D data can be incorporated in motion planning, (b) poses can be updated (i.e., from loop closures) with minimal computational effort, and (c) 3D data can be fused lazily for the purpose of planning. We provide an open-source implementation of NanoMap, and analyze its capabilities and computational efficiency in simulation experiments. Finally, we demonstrate in hardware its effectiveness for fast 3D obstacle avoidance onboard a quadrotor flying up to 10 m/s.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=9a0eEscz1Cs> https://www.youtube.com/watch?v=9a0eEscz1Cs </a>
<p><i> Under review. Comments welcome.</i>A Pipeline for Generating Ground Truth Labels for
Real {RGBD} Data of Cluttered Scenes
https://arxiv.org/abs/1707.04796
Fri, 15 Sep 2017 00:00:00 ESTby Pat Marion and Peter R. Florence and Lucas Manuelli and Russ Tedrake
<p> Deep neural network (DNN) architectures have been shown to outperform tradi-
tional pipelines for object segmentation and pose estimation using RGBD data,
but the performance of these DNN pipelines is directly tied to how representative
the training data is of the true data. Hence a key requirement for employing these
methods in practice is to have a large set of labeled data for your specific robotic
manipulation task, a requirement that is not generally satisfied by existing datasets.
In this paper we develop a pipeline to rapidly generate high quality RGBD data
with pixelwise labels and object poses. We use an RGBD camera to collect video of
a scene from multiple viewpoints and leverage existing reconstruction techniques
to produce a 3D dense reconstruction. We label the 3D reconstruction using a
human assisted ICP-fitting of object meshes. By reprojecting the results of labeling
the 3D scene we can produce labels for each RGBD image of the scene. This
pipeline enabled us to collect over 1,000,000 labeled object instances in just a few
days. We use this dataset to answer questions related to how much training data is
required, and of what quality the data must be, to achieve high performance from a
DNN architecture.
<p> Supplemental materials:
<a href=http://groups.csail.mit.edu/robotics-center/public_papers/Marion17sup.pdf> Marion17sup.pdf </a>
, <a href=https://www.youtube.com/watch?v=zoSNUAxiqzE> https://www.youtube.com/watch?v=zoSNUAxiqzE </a>
, <a href=http://labelfusion.csail.mit.edu> http://labelfusion.csail.mit.edu </a>
<p><i> Under review. Comments welcome.</i>Approximate Hybrid Model Predictive Control
for Multi-Contact Push Recovery in Complex Environments
http://groups.csail.mit.edu/robotics-center/public_papers/Marcucci17.pdf
Tue, 25 Jul 2017 00:00:00 ESTby Tobia Marcucci and Robin Deits and Marco Gabiccini and Antonio Bicchi and Russ Tedrake
<p> Feedback control of robotic systems interacting with the environment through contacts is a central topic in legged robotics.
One of the main challenges posed by this problem is the choice of a model sufficiently complex to capture the discontinuous nature of the dynamics but simple enough to allow online computations.
Linear models have proved to be the most effective and reliable choice for smooth systems; we believe that piecewise affine (PWA) models represent their natural extension when contact phenomena occur.
Discrete-time PWA systems have been deeply analyzed in the field of hybrid Model Predictive Control (MPC), but the straightforward application of MPC techniques to complex systems, such as a humanoid robot, leads to mixed-integer optimization problems which are not solvable at real-time rates. Explicit MPC methods can construct the entire control policy offline, but the resulting policy becomes too complex to compute for systems at the scale of a humanoid robot. In this paper we propose a novel algorithm which splits the computational burden between an offline sampling phase and a limited number of online convex optimizations, enabling the application of hybrid predictive controllers to higher-dimensional systems. In doing so we are willing to partially sacrifice feedback optimality, but we set stability of the system as an inviolable requirement.
Simulation results of a simple planar humanoid that balances by making contact with its environment are presented to validate the proposed controller.
<p><i> Under review. Comments welcome.</i>Feedback Design for Multi-contact Push Recovery via {LMI}
Approximation of the Piecewise-Affine Quadratic Regulator
http://groups.csail.mit.edu/robotics-center/public_papers/Han17.pdf
Tue, 25 Jul 2017 00:00:00 ESTby Weiqiao Han and Russ Tedrake
<p> To recover from large perturbations, a legged robot must make and break contact with its environment at various locations.
These contact switches make it natural to model the robot as a hybrid system.
If we apply Model Predictive Control to the feedback design of this hybrid system, the on/off behavior of contacts can be directly encoded using binary variables in a Mixed Integer Programming problem, which scales badly with the number of time steps and is too slow for online computation.
We propose novel techniques for the design of stabilizing controllers for such hybrid systems.
We approximate the dynamics of the system as a discrete-time Piecewise Affine (PWA) system, and compute the state feedback controllers across the hybrid modes offline via Lyapunov theory.
The Lyapunov stability conditions are translated into Linear Matrix Inequalities.
A Piecewise Quadratic Lyapunov function together with a Piecewise Linear (PL) feedback controller
can be obtained by Semidefinite Programming (SDP).
We show that we can embed a quadratic objective in the SDP, designing a controller approximating the Piecewise-Affine Quadratic Regulator.
Moreover, we observe that our formulation restricted to the linear system case appears to always produce exactly the unique stabilizing solution to the Discrete Algebraic Riccati Equation.
In addition, we extend the search from the PL controller to the PWA controller via Bilinear Matrix Inequalities.
Finally, we demonstrate and evaluate our methods on a few PWA systems, including a simplified humanoid robot model.
<p><i> Under review. Comments welcome.</i>Globally Optimal Object Pose Estimation in Point Clouds with Mixed-Integer Programming
http://groups.csail.mit.edu/robotics-center/public_papers/Izatt17b.pdf
Fri, 30 Jun 2017 22:00:00 ESTby Gregory Izatt and Hongkai Dai and Russ Tedrake
<p> Motivated by the limitations of local object trackers, we present a formulation of the underlying point-cloud object pose estimation problem as a mixed-integer convex program, which we efficiently solve to optimality with an off-the-shelf branch and bound solver. We show that reasoning about object pose estimation in this way allows natural extension to point-to-mesh correspondence, multiple simultaneous object pose estimation, and outlier rejection without losing the ability to obtain a globally optimal solution. We probe the extent to which rich problem-specific formulations typically tackled with unreliable nonlinear optimization can be rigorously treated in a global optimization framework to overcome the limitations of other global pose estimation methods.
<p><i> Under review. Comments welcome.</i>Global inverse kinematics via mixed-integer convex optimization
http://groups.csail.mit.edu/robotics-center/public_papers/Dai17.pdf
Fri, 30 Jun 2017 22:00:00 ESTby Hongkai Dai and Gregory Izatt and Russ Tedrake
<p> In this paper we present a novel formulation of the inverse kinematics (IK)
problem with generic constraints as a mixed-integer convex optimization program.
The proposed approach can solve the IK problem globally with generic task space
constraints, a major improvement over existing approaches, which either solve the
problem in only a local neighborhood of the user initial guess through nonlinear
non-convex optimization, or address only a limited set of kinematics constraints.
Specifically, we propose a mixed-integer convex relaxation on non-convex SO(3)
rotation constraints, and apply this relaxation on the inverse kinematics problem.
Our formulation can detect if an instance of the IK problem is globally infeasible,
or produce an approximate solution when it is feasible. We show results on a 7-
joint arm grasping objects in a cluttered environment, and a quadruped standing on
stepping stones. We also compare our approach against the analytical approach for
a 6-joint manipulator. The code is open-sourced at drake.mit.edu [29].
<p><i> Under review. Comments welcome.</i>Tracking Objects with Point Clouds from Vision and Touch
http://groups.csail.mit.edu/robotics-center/public_papers/Izatt16.pdf
Thu, 15 Sep 2016 22:00:00 ESTby Gregory Izatt and Geronimo Mirano and Edward Adelson and Russ Tedrake
<p> We present an object-tracking framework that fuses
point cloud information from an RGB-D camera with tactile
information from a GelSight contact sensor. GelSight can be
treated as a source of dense local geometric information, which
we incorporate directly into a conventional point-cloud-based
articulated object tracker based on signed-distance functions.
Our implementation runs at 12 Hz using an online depth
reconstruction algorithm for GelSight and a modified second-
order update for the tracking algorithm. We present data
from hardware experiments demonstrating that the addition
of contact-based geometric information significantly improves
the pose accuracy during contact, and provides robustness to
occlusions of small objects by the robot’s end effector.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=BIW_jq3dOEE> https://www.youtube.com/watch?v=BIW_jq3dOEE </a>
<p><i> Under review. Comments welcome.</i>Planning robust walking motion on uneven terrain via convex optimization
http://groups.csail.mit.edu/robotics-center/public_papers/Dai16a.pdf
Tue, 02 Aug 2016 17:00:00 ESTby Hongkai Dai and Russ Tedrake
<p> In this paper, we present a convex optimization problem to generate Center of Mass (CoM) and momentum trajectories of a walking robot, such that the motion robustly satisfies the friction cone constraints on uneven terrain. We adopt the Contact Wrench Cone (CWC) criterion to measure a robot's dynamical stability, which generalizes the venerable Zero Moment Point (ZMP) criterion. Unlike the ZMP criterion, which is ideal for walking on flat ground with unbounded tangential friction forces, the CWC criterion incorporates non-coplanar contacts with friction cone constraints. We measure the robustness of the motion using the margin in the Contact Wrench Cone at each time instance, which quantifies the capability of the robot to instantaneously resist external force/torque disturbance, without causing the foot to tip over or slide. For pre-specified footstep location and time, we formulate a convex optimization problem to search for robot linear and angular momenta that satisfy the CWC criterion. We aim to maximize the CWC margin to improve the robustness of the motion, and minimize the centroidal angular momentum (angular momentum about CoM) to make the motion natural. Instead of directly minimizing the non-convex centroidal angular momentum, we resort to minimizing a convex upper bound. We show that our CWC planner can generate motion similar to the result of the ZMP planner on flat ground with sufficient friction. Moreover, on an uneven terrain course with friction cone constraints, our CWC planner can still find feasible motion, while the outcome of the ZMP planner violates the friction limit.
<p><i> Under review. Comments welcome.</i>Balance control using center of mass height variation: limitations imposed by unilateral contact
http://groups.csail.mit.edu/robotics-center/public_papers/Koolen16.pdf
Tue, 02 Aug 2016 17:00:00 ESTby Twan Koolen and Michael Posa and Russ Tedrake
<p> Maintaining balance is fundamental to legged robots. The most commonly used mechanisms for balance control are taking a step, regulating the center of pressure (ankle strategies), and to a lesser extent, changing centroidal angular momentum (e.g., hip strategies). In this paper, we disregard these three mechanisms, instead focusing on a fourth: varying center of mass height. We study a 2D variable-height center of mass model, and analyze how center of mass height variation can be used to achieve balance, in the sense of convergence to a fixed point of the dynamics. In this analysis, we pay special attention to the constraint of unilateral contact forces. We first derive a necessary condition that must be satisfied to be able to achieve balance. We then present two control laws, and derive their regions of attraction in closed form. We show that one of the control laws achieves balance from any state satisfying the necessary condition for balance. Finally, we briefly discuss the relative importance of CoM height variation and other balance mechanisms.
<p><i> Under review. Comments welcome.</i>Integrated Perception and Control at High Speed: Evaluating Collision Avoidance Maneuvers Without Maps
http://groups.csail.mit.edu/robotics-center/public_papers/Florence16.pdf
Tue, 02 Aug 2016 17:00:00 ESTby Peter R. Florence and John Carter and Russ Tedrake
<p> We present a method for robust high-speed quadrotor flight through unknown cluttered environments using a fast approximation of
collision probabilities. Motivated by experiments in which the difficulty of accurate state estimation was a primary limitati...
<p><i> Under review. Comments welcome.</i>Localizing External Contact Using Proprioceptive Sensors: The Contact Particle Filter
http://groups.csail.mit.edu/robotics-center/public_papers/Manuelli16.pdf
Wed, 16 Mar 2016 17:00:00 ESTby Lucas Manuelli and Russ Tedrake
<p> In order for robots to interact safely and intelligently
with their environment they must be able to reliably
estimate and localize external contacts. This paper introduces
CPF, the Contact Particle Filter, which is a general algorithm
for detecting and localizing external contacts on rigid body
robots without the need for external sensing. CPF finds external
contact points that best explain the observed external joint
torque, and returns sensible estimates even when the external
torque measurement is corrupted with noise. We demonstrate
the capability of the CPF to track multiple external contacts
on a simulated Atlas robot, and compare our work to existing
approaches.
<p> Supplemental materials:
<a href=http://youtu.be/ckvsMK0QhB0> http://youtu.be/ckvsMK0QhB0 </a>
<p><i> Under review. Comments welcome.</i>Funnel Libraries for Real-time Robust Feedback Motion Planning
http://groups.csail.mit.edu/robotics-center/public_papers/Majumdar16.pdf
Mon, 21 Mar 2016 17:00:00 ESTby Anirudha Majumdar and Russ Tedrake
<p> We consider the problem of generating motion plans for a robot that are guaranteed to succeed despite uncertainty in the environment, parametric model uncertainty, and disturbances. Furthermore, we consider scenarios where these plans must be generated in real-time, because constraints such as obstacles in the environment may not be known until they are perceived (with a noisy sensor) at runtime. Our approach is to pre-compute a library of funnels along different maneuvers of the system that the state is guaranteed to remain within (despite bounded disturbances) when the feedback controller corresponding to the maneuver is executed. We leverage powerful computational machinery from convex optimization (sums-of-squares programming in particular) to compute these funnels. The resulting funnel library is then used to sequentially compose motion plans at runtime while ensuring the safety of the robot. A major advantage of the work presented here is that by explicitly taking into account the effect of uncertainty, the robot can evaluate motion plans based on how vulnerable they are to disturbances.
We demonstrate and validate our method using extensive hardware experiments on a small fixed-wing airplane avoiding obstacles at high speed (~12 mph), along with thorough simulation experiments of ground vehicle and quadrotor models navigating through cluttered environments. To our knowledge, the resulting demonstrations constitute one of the first examples of provably safe and robust control for robotic systems with complex nonlinear dynamics that need to plan in real-time in environments with complex geometric constraints.
<p> Supplemental materials:
<a href=http://journals.sagepub.com/doi/abs/10.1177/0278364917712421> http://journals.sagepub.com/doi/abs/10.1177/0278364917712421 </a>
<p><i> Preliminary version on arxiv. Comments welcome.</i>Director: A User Interface Designed for Robot Operation With Shared Autonomy
http://groups.csail.mit.edu/robotics-center/public_papers/Marion16.pdf
Sat, 19 Mar 2016 17:00:00 ESTby Pat Marion and Maurice Fallon and Robin Deits and Andr\'{e}s Valenzuela and Claudia P\'{e}rez D'Arpino and Greg Izatt and Lucas Manuelli and Matt Antone and Hongkai Dai and Twan Koolen and John Carter and Scott Kuindersma and Russ Tedrake
<p> Operating a high degree of freedom mobile manipulator, such as a humanoid, in a field
scenario requires constant situational awareness, capable perception modules, and effective
mechanisms for interactive motion planning and control. A well-designed operator interface
presents the operator with enough context to quickly carry out a mission and the flexibility
to handle unforeseen operating scenarios robustly. By contrast, an unintuitive user interface
can increase the risk of catastrophic operator error by overwhelming the user with unnecessary
information. With these principles in mind, we present the philosophy and design
decisions behind Director -- the open-source user interface developed by Team MIT to pilot
the Atlas robot in the DARPA Robotics Challenge (DRC). At the heart of Director is an
integrated task execution system that specifies sequences of actions needed to achieve a
substantive task, such as drilling a wall or climbing a staircase. These task sequences, developed
a priori, make queries to automated perception and planning algorithms online with
outputs that can be reviewed by the operator and executed by our whole-body controller.
Our use of Director at the DRC resulted in efficient high-level task operation while being
fully competitive with approaches focusing on teleoperation by highly-trained operators. We
discuss the primary interface elements that comprise the Director and provide analysis of
its successful use at the DRC.
<p> Supplemental materials:
<a href=http://onlinelibrary.wiley.com/doi/10.1002/rob.21681/full> http://onlinelibrary.wiley.com/doi/10.1002/rob.21681/full </a>
<p><i> Under review. Comments welcome.</i>Feedback-Motion-Planning with
Simulation-Based LQR-Trees
http://groups.csail.mit.edu/robotics-center/public_papers/Reist15.pdf
Mon, 21 Mar 2016 17:00:00 ESTby Philipp Reist and Pascal V. Preiswerk and Russ Tedrake
<p> The paper presents the simulation-based variant of the LQR-Tree feedback-motion-planning approach. The algorithm
generates a control policy that stabilizes a nonlinear dynamic system from a bounded set of initial conditions to a goal. The
policy is represented by a tree of feedback-stabilized trajectories. The algorithm explores the bounded set with random
state samples and, where needed, adds new trajectories to the tree using motion planning. Simultaneously, the algorithm
approximates the funnel of a trajectory, which is the set of states that can be stabilized to the goal by the trajectory’s
feedback policy. Generating a control policy that stabilizes the bounded set to the goal is equivalent to adding trajectories
to the tree until their funnels cover the set. In previous work, funnels are approximated with sums-of-squares verification.
Here, funnels are approximated by sampling and falsification by simulation, which allows the application to a broader
range of systems and a straightforward enforcement of input and state constraints. A theoretical analysis shows that in the
long run, the algorithm tends to improve the coverage of the bounded set as well as the funnel approximations. Focusing
on the practical application of the method, a detailed example implementation is given that is used to generate policies for
two example systems. Simulation results support the theoretical findings, while experiments demonstrate the algorithm’s
state-constraints capability, and applicability to highly-dynamic systems.
<p> Supplemental materials:
<a href=http://youtu.be/0-iHS6QdDuM> http://youtu.be/0-iHS6QdDuM </a>
, <a href=http://groups.csail.mit.edu/robotics-center/public_papers/Reist15_code.zip> Reist15_code.zip </a>
<p><i> To appear in the IJRR.</i>High-Speed Autonomous Obstacle Avoidance with Pushbroom Stereo
http://groups.csail.mit.edu/robotics-center/public_papers/Barry16a.pdf
Thu, 10 Mar 2016 17:00:00 ESTby Andrew J. Barry and Peter R. Florence and Russ Tedrake
<p> We present the design and implementation of a small autonomous unmanned aerial vehicle capable of high-speed flight through complex natural environments. Using only onboard GPS-denied sensing and computation, we perform obstacle detection,planning, and feedback control in realtime. We present a novel integrated approach to perception and control using pushbroom stereo, which exploits forward motion to enable efficient obstacle detection and avoidance using lightweight processors on a UAV. Our use of model-based planning and control techniques allows us to track precise trajectories that avoid obstacles identified by the vision system. We demonstrate a complete working system detecting obstacles at 120 Hz and avoiding trees at up to 14 m/s (31 MPH). To the best of our knowledge this is the fastest lightweight aerial vehicle to perform collision avoidance using 3D geometric information.
<p> Supplemental materials:
<a href=https://doi.org/10.1002/rob.21741> https://doi.org/10.1002/rob.21741 </a>
<p><i> Under review. Comments welcome.</i>Optimization and stabilization of trajectories for constrained dynamical systems
http://groups.csail.mit.edu/robotics-center/public_papers/Posa15.pdf
Tue, 15 Sept 2015 20:00:00 ESTby Michael Posa and Scott Kuindersma and Russ Tedrake
<p> Contact constraints, such as those between a foot
and the ground or a hand and an object, are inherent in
many robotic tasks. These constraints define a manifold of
feasible states; while well understood mathematically, they
pose numerical challenges to many algorithms for planning
and controlling whole-body dynamic motions. In this paper,
we present an approach to the synthesis and stabilization of
complex trajectories for both fully-actuated and underactuated
robots subject to contact constraints. We introduce an extension
to the direct collocation trajectory optimization algorithm that
naturally incorporates the manifold constraints to produce a
nominal trajectory with third-order integration accuracy—
a critical feature for achieving reliable tracking control. We
adapt the classical time-varying linear quadratic regulator to
produce a local cost-to-go in the tangent plane of the manifold.
Finally, we descend the cost-to-go using a quadratic program
that incorporates unilateral friction and torque constraints.
This approach is demonstrated on three complex walking and
climbing locomotion examples in simulation.
<p> Supplemental materials:
<a href=https://youtu.be/62GIUJC60P4> https://youtu.be/62GIUJC60P4 </a>
<p><i> Under review. Comments welcome.</i>Aggressive Quadrotor Flight through Cluttered Environments Using Mixed Integer Programming
http://groups.csail.mit.edu/robotics-center/public_papers/Landry15b.pdf
Tue, 15 Sept 2015 20:00:00 ESTby Benoit Landry and Robin Deits and Peter R. Florence and Russ Tedrake
<p> Quadrotor flight has typically been limited to sparse environments due to numerical complications that arise when dealing with large numbers of obstacles. We hypothesized that it would be possible to plan and robustly execute trajecto- ries in obstacle-dense environments using the novel Iterative Regional Inflation by Semidefinite programming algorithm (IRIS), mixed-integer semidefinite programs (MISDP), and a model-based controller. Unlike sampling-based approaches, the algorithm guarantees non-penetration of the trajectories even with small obstacles such as strings. We present experimental validation of this hypothesis by aggressively flying a small quadrotor (34g, 92mm rotor to rotor) in a series of indoor environments including a cubic meter volume containing 20 interwoven strings.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=v-s564NoAu0> https://www.youtube.com/watch?v=v-s564NoAu0 </a>
<p><i> Under review. Comments welcome.</i>A closed-form solution for real-time {ZMP} gait generation and feedback stabilization
http://groups.csail.mit.edu/robotics-center/public_papers/Tedrake15.pdf
Tue, 7 July 2015 20:00:00 ESTby Tedrake, Russ and Kuindersma, Scott and Deits, Robin and Miura, Kanako
<p> Here we present a closed-form solution to the continuous time-varying linear-quadratic regulator problem for zero-moment point (ZMP) tracking. This generalizes previous analytical solutions for gait generation by allowing ``soft
<p><i> Under review. Comments welcome.</i>Planning and Control for Quadrotor Flight through
Cluttered Environments
http://groups.csail.mit.edu/robotics-center/public_papers/Landry15.pdf
Tue, 26 May 2015 10:00:00 ESTby Benoit Landry
<p> Previous demonstrations of autonomous quadrotor flight have typically been limited
to sparse environments due to the computational burden associated with planning
for a large number of obstacles. We hypothesized that it would be possible to do
efficient planning and robust execution in obstacle-dense environments using the novel
Iterative Regional Inflation by Semidefinite programming algorithm (IRIS), mixedinteger
semidefinite programs (MISDP), and model-based control approaches. Here,
we present experimental validation of this hypothesis using a small quadrotor in a
series of indoor environments including a cubic meter volume containing 20 interwoven
strings. We chose one of the smallest hardware platforms available on the market
(34g, 92mm rotor to rotor), allowing for these dense environments and explain how to
overcome the many system identification, state estimation, and control problems that
result from the small size of the platform and the complexity of the environments.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=v-s564NoAu0> https://www.youtube.com/watch?v=v-s564NoAu0 </a>
<p><i> </i>Synthesis and optimization of force closure grasps via sequential semidefinite programming
http://groups.csail.mit.edu/robotics-center/public_papers/Dai15.pdf
Sun, 26 April 2014 20:00:00 ESTby Hongkai Dai and Anirudha Majumdar and Russ Tedrake
<p> In this paper we present a novel approach for synthesizing and optimizing both positions and forces in force closure grasps. This problem is a non-convex optimization problem in general since it involves constraints that are bilinear; in particular, computing wrenches involves a bilinear product between grasp contact points and contact forces. Thus, conventional approaches to this problem typically employ general purpose gradient-based nonlinear optimization. The key observation of this paper is that the force closure grasp synthesis problem can be posed as a Bilinear Matrix Inequality (BMI), for which there exist efficient solution techniques based on semidefinite programming. We show that we can synthesize force closure grasps on different geometric objects, and by maximizing a lower bound of a grasp metric, we can improve the quality of the grasp. While this approach is not guaranteed to find a solution, it has a few distinct advantages. First, we can handle non-smooth but convex positive semidefinite constraints, which can often be important. Second, in contrast to gradient-based approaches we can prove infeasibility of problems. We demonstrate our method on a 15 joint robot model grasping objects with various geometries. The code is included in https://github.com/RobotLocomotion/drake
<p><i> Under review. Comments welcome.</i>Optimization-based Locomotion Planning, Estimation, and Control Design for the {A}tlas Humanoid Robot
http://groups.csail.mit.edu/robotics-center/public_papers/Kuindersma14.pdf
Sun, 2 Nov 2014 16:00:00 ESTby Scott Kuindersma and Robin Deits and Maurice Fallon and Andr\'{e}s Valenzuela and Hongkai Dai and Frank Permenter and Twan Koolen and Pat Marion and Russ Tedrake
<p> This paper describes a collection of optimization algorithms for achieving dynamic planning, control, and state estimation for a bipedal robot designed to operate reliably in complex environments. To make challenging locomotion tasks tractable, we describe several novel applications of convex, mixed-integer, and sparse nonlinear optimization to problems ranging from footstep placement to whole-body planning and control. We also present a state estimator formulation that, when combined with our walking controller, permits highly precise execution of extended walking plans over non-flat terrain. We describe our complete system integration and experiments carried out on Atlas, a full-size hydraulic humanoid robot designed by Boston Dynamics, Inc.
<p><i> Under review. Comments welcome.</i>Whole-body Motion Planning with Centroidal Dynamics and Full Kinematics
http://groups.csail.mit.edu/robotics-center/public_papers/Dai14.pdf
Mon, 19 Oct 2014 20:00:00 ESTby Hongkai Dai and Andr\'es Valenzuela and Russ Tedrake
<p> To plan dynamic, whole-body motions for robots, one conventionally faces the choice between a complex, full-body dynamic model containing every link and actuator of the robot, or a highly simplified model of the robot as a point mass.
In this paper we explore a powerful middle ground between these extremes.
We exploit the fact that while the full dynamics of humanoid robots are complicated, their centroidal dynamics (the evolution of the angular momentum and the center of mass (COM) position) are much simpler.
By treating the dynamics of the robot in centroidal form and directly optimizing the joint trajectories for the actuated degrees of freedom, we arrive at a method that enjoys simpler dynamics, while still having the expressiveness required to handle kinematic constraints such as collision avoidance or reaching to a target.
We further require that the robot's COM and angular momentum as computed from the joint trajectories match those given by the centroidal dynamics.
This ensures that the dynamics considered by our optimization are equivalent to the full dynamics of the robot, provided that the robot's actuators can supply sufficient torque.
We demonstrate that this algorithm is capable of generating highly-dynamic motion plans with examples of a humanoid robot negotiating obstacle course elements and gait optimization for a quadrupedal robot.
Additionally, we show that we can plan without pre-specifying the contact sequence by exploiting the complementarity conditions between contact forces and contact distance.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=l3TEnNAyjmg> https://www.youtube.com/watch?v=l3TEnNAyjmg </a>
<p><i> To appear in Humanoids 2014.</i>Efficient Mixed-Integer Planning for {UAVs} in Cluttered Environments
http://groups.csail.mit.edu/robotics-center/public_papers/Deits15.pdf
Sun, 12 Oct 2014 22:00:00 ESTby Robin Deits and Russ Tedrake
<p> We present a new approach to the design of smooth trajectories for quadrotor unmanned aerial vehicles ({UAVs}), which are free of collisions with obstacles along their entire length. To avoid the non-convex constraints normally required for obstacle-avoidance, we perform a mixed-integer optimization in which polynomial trajectories are assigned to convex regions which are known to be obstacle-free. Prior approaches have used the faces of the obstacles themselves to define these convex regions. We instead use {IRIS}, a recently developed technique for greedy convex segmentation, to pre-compute convex regions of safe space. This results in a substantially reduced number of integer variables, which improves the speed with which the optimization can be solved to its global optimum, even for tens or hundreds of obstacle faces. In addition, prior approaches have typically enforced obstacle avoidance at a finite set of sample or knot points. We introduce a technique based on sums-of-squares ({SOS}) programming that allows us to ensure that the entire piecewise polynomial trajectory is free of collisions using convex constraints. We demonstrate this technique in 2D and in 3D using a dynamical model in the Drake toolbox for {MATLAB}.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=gJBitAHDPsA> https://www.youtube.com/watch?v=gJBitAHDPsA </a>
<p><i> Under review. Comments welcome.</i>Pushbroom Stereo for High-Speed Navigation in Cluttered Environments
http://groups.csail.mit.edu/robotics-center/public_papers/Barry15.pdf
Sun, 12 Oct 2014 22:00:00 ESTby Andrew J. Barry and Russ Tedrake
<p> We present a novel stereo vision algorithm that is capable of obstacle detection on a mobile ARM processor at
120 frames per second. Our system performs a subset of standard block-matching stereo processing, searching
only for obstacles at a single depth. By using an onboard IMU and state-estimator, we can recover the
position of obstacles at all other depths, building and updating a local depth-map at framerate.
Here, we describe both the algorithm and our implementation on a high-speed, small UAV, flying at over 20
MPH (9 m/s) close to obstacles. The system requires no external sensing or computation and is, to the best
of our knowledge, the first high-framerate stereo detection system running onboard a small UAV.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=cZE01bJIgvQ> https://www.youtube.com/watch?v=cZE01bJIgvQ </a>
<p><i> Under review. Comments welcome.</i>Stability analysis and control of rigid-body
systems with impacts and friction
http://groups.csail.mit.edu/robotics-center/public_papers/Posa14.pdf
Sat, 11 Oct 2014 22:00:00 ESTby Michael Posa and Mark Tobenkin and Russ Tedrake
<p> Many critical tasks in robotics, such as locomotion or manipulation, involve collisions between a rigid body and the environment or between multiple bodies. Methods based on sums-of-squares (SOS) for numerical computation of Lyapunov certificates are a powerful tool for analyzing the stability of continuous nonlinear systems, and can additionally be used to automatically synthesize stabilizing feedback controllers. Here, we present a method for applying sums-of-squares verification to rigid bodies with Coulomb friction undergoing discontinuous, inelastic impact events. The proposed algorithm explicitly generates Lyapunov certificates for stability, positive invariance, and safety over admissible (non-penetrating) states and contact forces. We leverage the complementarity formulation of contact, which naturally generates the semialgebraic constraints that define this admissible region. The approach is demonstrated on multiple robotics examples, including simple models of a walking robot, a perching aircraft, and control design of a balancing robot.
<p><i> Under review. Comments welcome.</i>Control and Verification of High-Dimensional Systems with {DSOS} and {SDSOS} Programming
http://groups.csail.mit.edu/robotics-center/public_papers/Majumdar14a.pdf
Sat, 20 Sep 2014 22:00:00 ESTby Anirudha Majumdar and Amir Ali Ahmadi and Russ Tedrake
<p> In this paper, we consider linear programming
(LP) and second order cone programming (SOCP) based
alternatives to sum of squares (SOS) programming and apply
this framework to high-dimensional problems arising in control
applications. Despite the wide acceptance of SOS programming
in the control and optimization communities, scalability has
been a key challenge due to its reliance on semidefinite
programming (SDP) as its main computational engine. While
SDPs have many appealing features, current SDP solvers do
not approach the scalability or numerical maturity of LP and
SOCP solvers. Our approach is based on the recent work
of Ahmadi and Majumdar [1], which replaces the positive
semidefiniteness constraint inherent in the SOS approach with
stronger conditions based on
diagonal dominance
and
scaled
diagonal dominance
. This leads to the
DSOS
and
SDSOS
cones
of polynomials, which can be optimized over using LP and
SOCP respectively. We demonstrate this approach on four high
dimensional control problems that are currently well beyond the
reach of SOS programming: computing a region of attraction
for a
22
dimensional system, analysis of a
50
node network
of oscillators, searching for degree
3
controllers and degree
8
Lyapunov functions for an Acrobot system (with the resulting
controller validated on a hardware platform), and a balancing
controller for a
30
state and
14
control input model of the
ATLAS humanoid robot. While there is additional conservatism
introduced by our approach, extensive numerical experiments
on smaller instances of our problems demonstrate that this
conservatism can be small compared to SOS programming.
<p><i> Final submission. To appear at CDC 2014.</i>An Architecture for Online Affordance-based Perception and Whole-body Planning
http://groups.csail.mit.edu/robotics-center/public_papers/Fallon14.pdf
Sun, 27 Jul 2014 17:00:00 ESTby Maurice Fallon and Scott Kuindersma and Sisir Karumanchi and Matthew Antone and Toby Schneider and Hongkai Dai and Claudia P\'{e}rez D'Arpino and Robin Deits and Matt DiCicco and Dehann Fourie and Twan Koolen and Pat Marion and Michael Posa and Andr\'{e}s Valenzuela and Kuan-Ting Yu and Julie Shah and Karl Iagnemma and Russ Tedrake and Seth Teller
<p> The DARPA Robotics Challenge Trials held in December 2013 provided a landmark demonstration of dexterous mobile robots executing a variety of tasks aided by a remote human operator using only data from the robot's sensor suite transmitted over a constrained, field-realistic communications link. We describe the design considerations, architecture, implementation and performance of the software that Team MIT developed to command and control an Atlas humanoid robot. Our design emphasized human interaction with an efficient motion planner, where operators expressed desired robot actions in terms of affordances fit using perception and manipulated in a custom user interface. We highlight several important lessons we learned while developing our system on a highly compressed schedule.
<p><i> Final submission. To appear in the Journal of Field Robotics.</i>Footstep Planning on Uneven Terrain with Mixed-Integer Convex Optimization
http://groups.csail.mit.edu/robotics-center/public_papers/Deits14a.pdf
Mon, 21 Jul 2014 20:00:00 ESTby Robin Deits and Russ Tedrake
<p> We present a new method for planning footstep placements for a robot walking on uneven terrain with obstacles, using a mixed-integer quadratically-constrained quadratic program ({MIQCQP}). Our approach is unique in that it handles obstacle avoidance, kinematic reachability, and rotation of footstep placements, which typically have required non-convex constraints, in a single mixed-integer optimization that can be efficiently solved to its global optimum. Reachability is enforced through a convex inner approximation of the reachable space for the robot’s feet. Rotation of the footsteps is handled by a piecewise linear approximation of sine and cosine, designed to ensure that the approximation never overestimates the robot’s reachability. Obstacle avoidance is ensured by decomposing the environment into convex regions of obstacle-free configuration space and assigning each footstep to one such safe region. We demonstrate this technique in simple 2D and 3D environments and with real environments sensed by a humanoid robot. We also discuss computational performance of the algorithm, which is currently capable of planning short sequences of a few steps in under one second or longer sequences of 10-30 footsteps in tens of seconds to minutes on common laptop computer hardware. Our implementation is available within the Drake {MATLAB} toolbox.
<p> Supplemental materials:
<a href=http://youtu.be/hGhCTPQuMy4> http://youtu.be/hGhCTPQuMy4 </a>
<p><i> Under review. Comments welcome.</i>Drift-Free Humanoid State Estimation
fusing Kinematic, Inertial and LIDAR sensing
http://groups.csail.mit.edu/robotics-center/public_papers/Fallon14a.pdf
Mon 21 Jul 2014 20:00:00 ESTby Maurice F. Fallon and Matthew Antone and Nicholas Roy and Seth Teller
<p> This paper describes an algorithm for the probabilistic fusion of sensor
data from a variety of modalities (inertial, kinematic and LIDAR)
to produce a single consistent position estimate for a walking
humanoid. Of specific interest is our approach for continuous LIDAR-based
localization which maintains reliable drift-free alignment to a prior map using
a Gaussian Particle Filter. This module can be bootstrapped by constructing the
map on-the-fly and performs robustly in a variety of challenging field
situations. We also discuss a two-tier estimation hierarchy which preserves
registration to this map and other objects in the robot's vicinity while also
contributing to direct low-level control of a Boston Dynamics Atlas robot.
Extensive experimental demonstrations illustrate how the approach can
enable the humanoid to walk over uneven terrain without stopping (for tens of
minutes), which would otherwise not be possible. We characterize the performance
of the estimator for each sensor modality and discuss the computational
requirements.
<p> Supplemental materials:
<a href=https://www.youtube.com/watch?v=V_DxB76MkE4> https://www.youtube.com/watch?v=V_DxB76MkE4 </a>
<p><i> Under review. Comments welcome.</i>Computing Large Convex Regions of Obstacle-Free Space through Semidefinite Programming
http://groups.csail.mit.edu/robotics-center/public_papers/Deits14.pdf
Tues, 16 Jul 2014 14:00:00 ESTby Robin L H Deits and Russ Tedrake
<p> This paper presents {IRIS} (Iterative Regional Inflation by Semi-definite programming), a new method for quickly computing large polytopic and ellipsoidal regions of obstacle-free space through a series of convex optimizations. These regions can be used, for example, to efficiently optimize an objective over collision-free positions in space for a robot manipulator. The algorithm alternates between two convex optimizations: (1) a quadratic program that generates a set of hyperplanes to separate a convex region of space from the set of obstacles and (2) a semidefinite program that finds a maximum-volume ellipsoid inside the polytope intersection of the obstacle-free half-spaces defined by those hyperplanes. Both the hyperplanes and the ellipsoid are refined over several iterations to monotonically increase the volume of the inscribed ellipsoid, resulting in a large polytope and ellipsoid of obstacle-free space. Practical applications of the algorithm are presented in 2D and 3D, and extensions to N-dimensional configuration spaces are discussed. Experiments demonstrate that the algorithm has a computation time which is linear in the number of obstacles, and our {MATLAB} implementation converges in seconds for environments with millions of obstacles.
<p><i> Final WAFR Submission.</i>Convex Optimization of Nonlinear Feedback Controllers via Occupation Measures
http://groups.csail.mit.edu/robotics-center/public_papers/Majumdar14.pdf
Sat, 28 Sep 2013 22:00:00 ESTby Anirudha Majumdar and Ram Vasudevan and Mark M. Tobenkin and Russ Tedrake
<p> 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 non-convex 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 (SDP)s. 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.
<p><i> Under review. Comments welcome.</i>An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion
http://groups.csail.mit.edu/robotics-center/public_papers/Kuindersma13.pdf
Sun, 15 Sep 2013 22:00:00 ESTby Scott Kuindersma and Frank Permenter and Russ Tedrake
<p> We describe a whole-body dynamic walking controller implemented as a convex quadratic program. The controller solves an optimal control problem using an approximate value function derived from a simple walking model while respecting the dynamic, input, and contact constraints of the full robot dynamics. By exploiting sparsity and temporal structure in the optimization with a custom active-set algorithm, we surpass the performance of the best available off-the-shelf solvers and achieve 1kHz control rates for a 34-DOF humanoid. We describe applications to balancing and walking tasks using the simulated Atlas robot in the DARPA Virtual Robotics Challenge.
<p> Supplemental materials:
<a href=http://arxiv.org/abs/1311.1839v1> http://arxiv.org/abs/1311.1839v1 </a>
<p><i> Under review. Comments welcome.</i>A Summary of Team {MIT}'s Approach to the Virtual Robotics Challenge
http://groups.csail.mit.edu/robotics-center/public_papers/Tedrake14.pdf
Sun, 15 Sep 2013 22:00:00 ESTby R. Tedrake and M. Fallon and S. Karumanchi and S. Kuindersma and M. Antone and T. Schneider and T. Howard and M. Walter and H. Dai and R. Deits and M. Fleder and D. Fourie and R. Hammoud and S. Hemachandra and P. Ilardi and C. Perez-D'Arpino and S. Pillai and A. Valenzuela and C. Cantu and C. Dolan and I. Evans and S. Jorgensen and J. Kristeller and J. A. Shah and K. Iagnemma and S. Teller
<p>
<p> Supplemental materials:
<a href=http://www.youtube.com/watch?v=CXHLntka5q4> http://www.youtube.com/watch?v=CXHLntka5q4 </a>
<p><i> Under review. Comments welcome.</i>Flying Between Obstacles with an Autonomous Knife-Edge Maneuver
http://groups.csail.mit.edu/robotics-center/public_papers/Barry14.pdf
Sun, 15 Sep 2013 22:00:00 ESTby Andrew J. Barry and Tim Jenks and Anirudha Majumdar and Huai-Ti Lin and Ivo G. Ros and Andrew Biewener and Russ Tedrake
<p>
<p> Supplemental materials:
<a href=http://www.youtube.com/watch?v=LGel-SdAIRg> http://www.youtube.com/watch?v=LGel-SdAIRg </a>
<p><i> Under review. Comments welcome.</i>