Energy-Bounded Caging

Synthesis Paper Analysis Paper

This project is maintained by BerkeleyAutomation

Energy Bounded Caging

Energy-Bounded Caging

Fig. 1. Two energy-bounded cages of industrial parts (blue) by robotic grippers (black) under a gravitational field indicated by the center arrow. Neither object is completely caged, but both are energy-bounded caged.

Synthesis of Energy-Bounded Planar Caging Grasps using Persistent Homology

Fig. 2. Persistence diagram for ranking energy-bounded cages. Left: polygonal part and gripper polygons serve as input. We sample object poses X in collision and generate an alpha-shape representation (shown in gray in the three middle figures). Given an energy potential, we insert simplices in D(X)-A(X) in decreasing order of energy potential, creating a filtration of simplicial complexes. Voids (yellow and orange) are born with the addition of edges (red) at threshold energy levels, and die with the additions of the last triangle in the void (red). The associated second persistence diagram (right figure) reveals cages with large persistence corresponding to energy-bounded cages with high escape energy. In particular, configuration q_1 is identified as more persistent (and therefore with higher escape energy) than configuration q_2.

Summary

Caging grasps restrict object motion without requiring complete immobilization, providing a practical alternative to force- and form-closure grasps. Previously, we introduced ``energy-bounded caging'', an extension that relaxes the requirement of complete caging in the presence of gravity and presented EBCA-2D, an algorithm for analyzing a proposed grasp using alpha shapes to lower-bound the escape energy. In this paper, we address the problem of synthesizing energy-bounded cages by identifying optimal gripper and force-direction configurations that require the largest increases in potential energy for the object to escape. We present Energy-Bounded-Cage-Synthesis-2D (EBCS-2D), a sampling-based algorithm that uses persistent homology, a recently-developed multiscale approach for topological analysis, to efficiently compute candidate rigid configurations of obstacles that form energy bounded cages of an object from an alpha-shape approximation to the configuration space. EBCS-2D runs in a worst-case O(s^3 + s*n^2) time where s is the number of samples, and n is the total number of object and obstacle vertices, where typically n << s, and in practice we observe run-times closer to O(s) for fixed n. We show that constant velocity pushing in the horizontal plane generates an energy field analogous to gravity in the vertical plane that can be analyzed with our approach. We implement EBCS-2D using the PHAT (Persistent Homology Algorithms Toolbox) library and study performance on a set of eight planar objects and four gripper types. Experiments suggest that EBCS-2D takes 2-3 minutes on a 6 core processor with 200,000 pose samples. We also find that an RRT* motion planner is unable to find escape paths with lower energy. Physical experiments suggest that EBCS-2D push grasps are robust to perturbations.

Publications

Energy-Bounded Caging: Formal Definition and 2D Energy Lower Bound Algorithm Based on Weighted Alpha Shapes

Energy-Bounded-Cage-Analysis 2D

Fig. 3. Illustration of the steps of the EBCA-2D algorithm. Given a polygonal object (blue), set of polygonal obstacles / fingers (black) and an energy function U, EBCA-2D finds a lower bound on the minimum escape energy or reports that the object is completely caged. (1) The first step is to conservatively approximate the collision space by uniformly sampling object poses and keeping only poses where the object is in collision with the obstacles. For each colliding pose q_i, we compute the penetration depth r_i which defines a ball strictly inside the collision space (red). (2) The union of these balls conservatively approximates the collision space. We then discretize the configuration space into cells by computing the weighted Delaunay triangulation from the points and use the weighted alpha-shape with alpha=0 to classify the cells belonging to the collision space (the white trianglular mesh). (3) Finally, we use binary search to find the maximum energy "u" for which no escape path exists by classifying the set of cells that are either in collision or have energy higher than u, determining the connected components of the remaining "free" cells, and checking if the component containing the initial object pose q_0 is bounded. Blue and yellow indicate connected components, while green indicates poses such that U(q) > u.

Summary

Caging grasps are valuable as they can be robust to bounded variations in object shape and pose, do not depend on friction, and enable transport of an object without full immobilization. Complete caging of an object is useful but may not be necessary in cases where forces such as gravity are present. This paper extends caging theory by defining energy-bounded cages with respect to an energy field such as gravity. This paper also introduces Energy-Bounded-Cage-Analysis-2D (EBCA-2D), a sampling-based algorithm for planar analysis that takes as input an energy function over poses, a polygonal object, and a configuration of rigid fixed polygonal obstacles, e.g. a gripper, and returns a lower bound on the minimum escape energy. In the special case when the object is completely caged, our approach is independent of the energy and can provably verify the cage. EBCA-2D builds on recent results in collision detection and the computational geometric theory of weighted alpha-shapes and runs in O(s^2 + s n^2) time where s is the number of samples, n is the total number of object and obstacle vertices, and typically n << s. We implemented EBCA-2D and evaluated it with nine parallel-jaw gripper configurations and four nonconvex obstacle configurations across six nonconvex polygonal objects. We found that the lower bounds returned by EBCA-2D are consistent with intuition, and we verified the algorithm experimentally with Box2D simulations and RRT* motion planning experiments that were unable to find escape paths with lower energy.

Publications

Contributors

These are ongoing projects at UC Berkeley with contributions from:
Jeffrey Mahler, Florian Pokorny, Zoe McCarthy, Sherdil Niyaz, A Frank van der Stappen, Ken Goldberg

Support or Contact

Please contact Jeffrey Mahler at jmahler@berkeley.edu or Prof. Ken Goldberg, Director of the Berkeley AUTOLAB at goldberg@berkeley.edu

Creative Commons License
The Energy Bounded Caging website, by the Berkeley AUTOLAB, is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.