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

Jeffrey Mahler, Florian T. Pokorny, A. Frank van der Stappen, Ken Goldberg
In IEEE RA-Letters, 2016


Caging grasps are valuable as they can be robust to bounded variations in object shape and pose and do not depend on friction. Full caging is useful but may not be necessary in cases where forces such as gravity are present (consider a stone in a cupped hand). This paper extends caging theory by defining energy-bounded cages under a constant potential energy field (such as gravity) based on the minimum energy required to escape. This paper also introduces Energy-Bounded-Cage-Analysis-2D (EBCA-2D), a sampling-based algorithm for planar analysis that takes as input a constant energy field specified as a function over poses, a polygonal object, and a configuration of rigid polygonal obstacles, and returns a lower bound on the minimum escape energy, which can be infinite when the object is fully caged. Building on recent results in collision detection and the computational geometric theory of weighted α-shapes, EBCA-2D is provably-correct and runs in time O(N 2 + N log(1/∆) + N V 3 ) time where N is the number of samples, ∆ is an energy resolution used for binary search, and V is the total number of object and obstacle vertices. We implemented EBCA-2D and evaluated it with nine parallel-jaw gripper 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 with an RRT* optimal motion planning algorithm that was unable to find escape paths with lower energy. EBCA-2D required an average of 3 minutes per problem on a single-core processor but has potential to be parallelized in a Cloud-based implementation. Additional proofs, data, and code are available at:


Download this publication


@inproceedings{mahler2016a, title={Energy-Bounded Caging: Formal Definition and 2D Lower Bound Algorithm Based on Weighted Alpha Shapes}, author={Mahler, Jeffrey and Pokorny, Florian T. and van der Stappen, A. Frank and Goldberg, Ken}, booktitle = {IEEE RA-Letters}, url={}, year = {2016}, }