Globally Optimal Grasp Planning using a Two-Stage Branch-And-Bound Algorithm

We present the first algorithm to compute the globally optimal gripper pose that maximizes a grasp metric. We solve this problem using a two-level branch-and-bound (BB) algorithm. Unlike previous work that only searches for grasp points, our method can take the gripper's kinematic feasibility into consideration. And compared with sampling-based grasp planning algorithms, our method can compute the globally optimal gripper pose or predict infeasibility with finite-time termination. Our main technical contribution is a novel mixed-integer conic programming (MICP) formulation for the inverse kinematics of the gripper which uses a small number of binary variables and tightened constraints. Our experiments show that globally optimal gripper poses for various target objects can be computed within 3hr of computation on a desktop machine and the computed grasp quality is better than those generated using sampling-based planners.