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.
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.
The Energy Bounded Caging website, by the Berkeley AUTOLAB, is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.