We consider the problem of finding optimal grasp contacts for arbitrary objects, based on a given grasp quality function. Our approach formulates a framework for contact-level grasping as a path-finding problem in the space of super-contact grasps. The initial super-contact grasp contains all grasps, and in each step along a path, grasps are removed. To achieve this, we introduce and formally characterize search space structure and cost functions, under which minimal cost paths correspond to optimal grasps. Our formulation avoids expensive exhaustive search and reduces computational cost by several orders of magnitude.
We present admissible heuristic functions and exploit approximate heuristic search to further reduce computational cost while maintaining bounded sub-optimality for resulting grasps. We exemplify our formulation with point-contact grasping, for which we define domain-specific heuristics and demonstrate optimality and bounded sub-optimality by comparing against exhaustive and uniform cost search on example objects. Furthermore, we explain how to restrict the search graph to satisfy grasp constraints for modeling hand kinematics. We also analyze our algorithm empirically in terms of created and visited search states and resultant effective branching factor.
Supplementary notes can be added here, including code and math.