Partial convex hull algorithms for efficient grasp quality evaluation

We present two algorithms to efficiently determine the value of two grasp quality metrics formerly proposed in literature. The first one is heavily used in practice but has some drawbacks, e.g., it is not scale invariant and it does not focus on the disturbance forces that will occur in practice when the robot grasps an object. The second one overcomes these limitations, but is rarely used because it is computationally too demanding. The two algorithms we propose are based on the common intuition that both metrics can be efficiently computed through a modified version of the QuickHull algorithm that is commonly used to compute convex hulls. In both cases it is possible to establish when enough information has been generated to determine the desired value, and then stop the construction of a suitably defined convex hull. Extensive numerical evaluations demonstrate that our algorithms provide substantial computational gains when compared with the state of the art. The speedup provides an immediate benefit to planners using grasp quality metrics to guide the search through the space of possible grasps.