Energy-bounded caging: Formal definition and 2-D energy lower bound algorithm based on weighted alpha shapes

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 letter extends caging theory by defining energy-bounded cages with respect to an energy field such as gravity. This letter also introduces energy-bounded-cage-analysis-2-D (EBCA-2-D), 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-2-D builds on recent results in collision detection and the computational geometric theory of weighted α-shapes and runs in O(s^2 + sn^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-2-D 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-2-D are consistent with intuition, and we verified the algorithm experimentally with Box2-D simulations and RRT* motion planning experiments that were unable to find escape paths with lower energy. EBCA2-D required an average of 3 min 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: http://berkeleyautomation.github.io/caging/.