Fast Estimation of Globally Optimal Independent Contact Regions for Robust Grasping and Manipulation Jonathan P. King 1 , Harnoor Ahluwalia 2 , Michael Zhang 1 , and Nancy S. Pollard 1 Abstract This work presents a fast anytime algorithm for computing globally optimal independent contact regions (ICRs). ICRs are regions such that one contact within each region enables a valid grasp. Locations of ICRs can provide guidance for grasp and manipulation planning, learning, and policy transfer. However, ICRs for modern applications have been little explored, in part due to the expense of computing them, as they have a search space exponential in the number of contacts. We present a divide and conquer algorithm based on incremental n-dimensional Delaunay triangulation that produces results with bounded suboptimality in times sufficient for real-time planning. This paper presents the base algorithm for grasps where contacts lie within a plane. Our experiments show substantial benefits over competing grasp quality metrics and speedups of 100X and more for competing approaches to computing ICRs. We explore robustness of a policy guided by ICRs and outline a path to general 3D implementation. Code will be released on publication to facilitate further development and applications. I INTRODUCTION Independent contact regions have been recognized as a foundational tool for grasp planning [ 21 ] . Large ICRs suggest grasps that can accommodate uncertainties and have geometries conducive to contact. They have been employed as stepping stones for in-hand manipulation [ 16 , 13 ] and it is interesting to consider how they may enhance modern approaches to manipulation and grasping. For example, ICRs could provide guidance for hand-object contact placement in language based interfaces [ 36 , 3 ] , they could improve our ability to interpret and retarget human demonstrations [ 20 , 33 ] , they could result in more physically informed grasp filters [ 6 , 11 ] , or enhance our ability to co-design hand shapes and product geometries [ 15 ] . However, ICR computation has been plagued by computational complexity. Its search space is exponential in the number of contacts, and previous algorithms are practical only in special cases (e.g., [ 22 , 29 ] ) or for locally optimal solutions (e.g., [ 26 , 30 , 18 ] ). Fig. 1: (Top) ICRs shown in orange and pink guide a simple control policy to lift an object. (Bottom) Guidance provided by ICRs enables the policy to work even with errors in object size, location, and geometry. (Right) Results from policy transfer to an anthropomorphic hand. This paper presents an algorithm for fast identification of globally optimal ICRs in high-contact scenarios. The problem can be viewed as one of finding large empty regions in a high-dimensional volume. This problem has been studied elsewhere (e.g. [ 37 ] ), and it has been observed that Delaunay Triangulation of occupied sites enables the largest empty circular region (hypersphere) to be identified easily. In our scenario, an occupied site corresponds to a grasp that is undesirable. In this paper we use the term “invalid” grasp, which could mean a grasp that would not achieve force closure, a grasp that contacts a forbidden region, or a grasp with measured quality below a user-specified threshold for some metric. In our case, invalid grasps are not all known ahead of time, and so we develop an incremental Delaunay Triangulation algorithm that iteratively tests the largest empty region until the optimal (or a sufficiently large) set of ICRs is located. Our algorithm guarantees convergence and produces results with bounded suboptimality. Our results show nearly 100X speedup on average over a fast brute force implementation, and our algorithm enables for the first time \epsilon -optimal ICRs to be computed for grasps having as many as 7 contacts. Furthermore, it can be used as an anytime algorithm, as it is able to return the current best solution with optimality bounds at any point. ICRs returned by the algorithm can be used for policy guidance (Figure 1 ). Simple policies built from ICRs show robustness to real-world uncertainties in object size, location, and geometry. Fig. 2: (Left) A shape defined by a curve parameterized on [0, L] with frictional contacts and contact regions. (Middle) The grasp configuration space as an order simplex with force closure grasps in blue. The L_{\infty} Distance Transform computes the furthest interior point in the Chebyshev norm, corresponding to the largest square contained in the force closure space. The optimal ICR is shown in red made up of orange and green contact regions. (Right) Dimensionality of the order simplex goes up with number of contacts. Our divide and conquer algorithm has produced the first result to our knowledge for epsilon-optimal grasps having greater than 4 contacts. II Related Work Many algorithms for grasping and manipulation rely on measures of optimality or quality metrics [ 32 , 4 , 1 ] . Historically, these methods have tended to produce optimal grasps as sets of precise target contact points. As a result, it is easy to produce grasps that are impractical for a robot in the sense that an optimal grasp may be at some extreme, such as a small surface element or location that leads to instability in the face of position errors. Over time, partly because of difficulties such as these and partly due to trends in machine learning, quality metrics have evolved to include consideration of dynamics, uncertainty, and sensing and to evaluate the performance of policies based on real-world data and simulation [ 2 , 35 ] . However, finding good policies remains challenging, and many impressive manipulation demonstrations benefit from physical understanding and control of contacts and forces [ 17 , 38 ] . Metrics such as ICRs, if they can be computed quickly enough, can help to bring planning and policy based approaches together to handle constraints and uncertainties well while making good use of information available about the physics of an intended interaction. Independent (Contact) Regions (ICRs) were introduced by Nguyen to provide robustness to grasps in the presence of fingertip position error and further developed by Ponce and Faverjon, with ICRs determined geometrically for special case 2, 3, and 4-contact grasps in the plane [ 22 , 27 , 28 ] . Pollard computed ICRs for arbitrary numbers of contacts by growing regions from example grasps [ 25 , 26 ] , although these ICRs were not globally optimal. Cornella and Suarez proposed an algorithm for computing ICRs for n-contacts by working in the 2D object space [ 9 ] . These results are also not globally optimal as only a subset of the force closure space is considered. There has additionally been work in finding ICRs on 3D objects [ 30 ] , use of various contact models [ 8 , 31 ] , integration of kinematic reachability [ 13 ] , and planning in-grasp manipulations such as finger gaiting [ 23 ] . Most related to our contribution is work by Phoka and colleagues [ 24 ] , who make the connection that for two-contact grasps, the axis-aligned rectangle in contact space that corresponds to any ICR (e.g., as shown in Figure 2 ) must be centered on the L_{\inf} Voronoi diagram constructed from the polygon bounding the force closure regions [ 24 ] . The algorithm in [ 24 ] is presented for grasps with two contacts. Challenges to extending to more than two contacts include developing a stable software library for L_{\infty} Voronoi diagrams (see [ 5 ] for state of the art), and constructing volumes of higher-dimensional force closure regions – a pre-processing step that is exponential in number of contacts, in contrast to the divide and conquer algorithm that we propose here. We compare to their approach in Section IV . There have been other algorithms focused on finding the largest empty axis aligned box in a point set (e.g., [ 10 , 19 ] ). However, these algorithms assume that all invalid points are known. The algorithm presented in this manuscript is adapted to the situation where invalid points are discovered incrementally. We are motivated by approaches to finding the largest empty circle contained in a bounded region (e.g., [ 37 ] ), and build on this work to develop an anytime algorithm with convergence guarantees when invalid points are not known in advance. III Technical Implementation The brute force process for computing ICRs is illustrated in Figure 2 with a two-contact example. For purposes of discussion, assume a 2D object with contact on the perimeter. We will discuss how to lift those restrictions later in the paper. The object perimeter is discretized into L intervals as shown in Figure 2 . Contact 1 can be placed anywhere along the perimeter. We assume that contacts are ordered and cannot overlap. Contact 2 therefore must be placed at a location with greater index than Contact 1, resulting in a simplex of possible grasps as shown in the middle of Figure 2 . Each grasp can be evaluated based on any desired quality metric to determine whether it is “valid” or “invalid.” In the middle image of the figure, valid grasps based on the force closure property are colored blue. Once all possible grasps are classified, optimal ICRs are found as the largest axis aligned box having all valid grasps and contained within the simplex. We can quickly identify the optimal result for this example using the L_{\infty} metric distance transform, which is shown with shaded blue boxes in the right image of Figure 2 . The resulting optimal ICRs are highlighted, along with corresponding contact regions on the bunny perimeter in orange and green. A more formal description follows. III-A Grasp Configuration Space: The Order Simplex Formally, a contact lies on the parameterized object boundary \partial B according to c\in[0,L] . A grasp \mathcal{G} consists of d non-coincidental contacts. We assume that contact regions cannot overlap, resulting in a grasp configuration space C_{d} written C_{d}\coloneqq\left([0,L]^{d}\setminus\Delta^{d}_{[0,L]}\right)/\text{Sym}(d) (1) where we begin with the d -fold Cartesian product of the contact manifold [0,L] with itself, remove the fat diagonal \Delta , and then take the quotient space by the symmetric group \text{Sym}(d) , removing permutations in contact ordering. This is the space of unordered and unlabeled configurations of d contacts. Geometrically, we can represent C_{d} with an Order Simplex [ 14 ] by symmetrically dissecting the hypercube, reducing the volume by a factor of d! . An Order Simplex for d -contacts is written as \Delta^{d}\coloneqq\{t\in[0,L]^{d}:0\leq t_{1}\leq t_{2}\leq\cdots\leq t_{d}\leq L\} (2) Data: A shape object O , number of contacts d Result: The optimal ICR I^{*} \Delta^{*}\leftarrow OrderSimplex( O,d ) DT\leftarrow DelaunayTriangulation( \Delta^{*} ) /* Initialize ICR I^{*} , best candidate C^{*} */ I^{*}\leftarrow\emptyset,C^{*}\leftarrow BestCandidate( DT ) , \epsilon\leftarrow\infty /* while a better hypercube is possible */ while C^{*}.\mathtt{radius}>\max(I^{*}.\mathtt{radius},r_{min}) do /* get new ICR I and invalid grasp G */ I,G\leftarrow GrowHypercube( C^{*} ) /* if new best radius, store result */ if I.\mathtt{radius}>I^{*}.\mathtt{radius} then I^{*}\leftarrow I end if /* update DT,C^{*},\epsilon */ DT.\mathtt{insert\_point}(G) C^{*}.isExplored=True C^{*}\leftarrow BestCandidate( DT ) if I^{*}.\mathtt{radius}>0 then /* get current fractional bound */ \epsilon\leftarrow\frac{C^{*}.radius-I^{*}.radius}{I^{*}.radius} end if end while return I^{*} Algorithm 1 Optimal ICR Algorithm III-B Algorithm Setup Independent Contact Regions are assumed to be disjoint continuous regions on the object boundary \partial B such that any grasp \mathcal{G} with contacts in the same ICR can be classified as a valid grasp. Within the grasp configuration space C_{d} an ICR is an axis aligned box that contains only valid grasps. Algorithm Concept : Consider a set of valid and invalid grasps that have been identified within C_{d} . For the invalid grasp set \overline{V} , consider it’s Delaunay Triangulation DT=\textsc{DelaunayTriangulation}(\overline{V}) . The Delaunay property guarantees an empty circumsphere for every simplex, \sigma\in DT , in the triangulation. The algorithm that then comes to mind is to search within the largest empty circumsphere until an invalid grasp is found then update the triangulation, repeating the process until there can be no ICRs remaining that are larger than the largest already found within some bound. This is the basic idea of our approach (Figure 4 ). Fig. 3: Each simplex in the Delaunay Triangulation has a candidate score. When the circumcenter is in the interior of the Order Simplex (orange and blue), the score is the circumradius. Circumcenters outside the order simplex will undergo further processing (Section III-D ). (Inset) For a given hypersphere C^{*} with center S , the smallest hypercube C^{-} centered at S is the inscribed hypercube with half-edge length r^{-} and the largest hypercube C^{+} centered at S is the circumscribed hypercube with half-edge length r^{+} . Fig. 4: Illustration of iterative algorithm for computing Independent Contact Regions. (Top) A single iteration consists of identifying the best next candidate, i.e., the largest current empty region and attempting to grow a hypercube within that region. Once an invalid grasp is found, the triangulation is updated and the next iteration begins. Color coding is as follows: (left) purple vertices are invalid grasps; (middle) blue shading in triangles is darker for higher candidate scores; the orange circle is the circumsphere of the highest scoring candidate; (right) light blue are valid grasps shown for visualization only; green are valid grasps already discovered by the algorithm; orange is the largest hypercube that could be grown at the current candidate center (orange circle); red is the first invalid grasp found during hypercube growing. (Bottom) Snapshots at different stages in the process. Bounds : Delaunay Triangulation partitions the Order Simplex into smaller simplices, each having an enclosing circumsphere which has either already been explored or is empty. Enclosing circumspheres can be used to bound the largest possible empty axis aligned boxes, and hence the largest possible ICRs. For any small and positive \epsilon_{r} , bounds for a hypercube placed at the center S of an empty circumsphere can be expressed as (Figure 3 Inset): (r^{-}-\epsilon_{r})0 to classify grasps as valid vs. invalid. The ICRs returned are the \epsilon -optimal independent contact regions, i.e., the largest axis aligned volumes for which the given metric produces a valid grasp. We can consider ICRs found using the Ferrari and Canny metric as a volumetric measure based on that metric. We observe that this volumetric measure identified contacts qualitatively more likely to lead to a successful outcome given real-world constraints, dynamics, and uncertainties. Fig. 6: (Top) Optimal grasps found using the point based metric in [ 12 ] . (Bottom) Optimal ICRs identified using the identical metric to classify valid vs. invalid grasps. Robustness to Uncertainties. To test robustness to uncertainties, a simple control policy was implemented to move towards ICRs and apply balanced forces using impedance control. Experiments are ongoing, but the policy has been found to be robust to \pm 20\% size changes, 1.8cm position variation, and substantial geometric differences (Figure 1 ). V Discussion As illustrated in Figure 5 (Left plot), the iterative algorithm presented in this paper outperforms brute-force for all but the very lowest resolution and 2-contact cases, with the improvement in performance becoming substantial ( \approx 100X) as number of contacts increases. This improvement makes computation of ICRs feasible for higher contact grasps for the first time. The proportion of run time spent on major subroutines is dominated by finding the best candidate and growing hypercubes, with the latter being most dominant for higher resolution or higher numbers of contacts. Dependence on resolution comes from the fact that the hypercube size grows with resolution to the dth power, with d the number of contacts. Considering only the time required to grow the largest hypercube that enables termination, runtime requirements for hypercube growing, expressing region size as a fraction \alpha of the number of samples p on a shape is O((\alpha p)^{d}) . Complexity of the iterative Delaunay Triangulation depends on the number of invalid grasps added n_{b} , and can be expressed as O(n_{b}^{\lfloor\frac{d}{2}\rfloor}) . Both are exponential in d . However, higher dimensional triangulations tend to require relatively few insertions of invalid points and few simplices, and time required to grow hypercubes becomes the practical limiting factor in the algorithm’s performance. The linear growth in runtime in the log plot in Figure 5 (Left plot) reflects exponential growth with sample size. However, the iterative algorithm is practically much faster, as only most promising hypercubes need to be checked. In this approach, runtime speedup is limited by the fractional volume of the Order Simplex filled by the largest hypercube, and one promising future area of research is to address this limitation either with an analytical approach or sampling based techniques that would avoid exhaustive sampling of the largest hypercube. We expected increased friction cone angles to result in longer runtimes, as they might be expected to produce larger contact regions, and thus larger hypercubes to grow. This effect is seen in the runtimes for Phoka and colleagues [ 24 ] (Table I ). However, we did not observe this effect in our results. No effect was observed for \mu on runtimes ( P>0.6 ). A slight effect was observed for \mu^{d} on runtimes ( R^{2}=0.02,P<0.05 ). However, the effect was in the opposite direction expected, with increasing friction cones producing faster runtimes. It is possible this effect was due to larger friction cones making it easier to find valid solutions which enabled the algorithm to converge faster. This possibility is supported by larger \mu producing fewer iterations ( P<0.05 ). A similar phenomenon may be responsible for the dip in runtimes when moving from a resolution of 32 to a resolution of 64. With 32 samples, the algorithm often ends up subdividing the entire space to prove that it has found the best region, making it a brute force algorithm with overhead. However, when moving to 64 samples, larger regions exist and are found early in the search, eliminating this problem. Limitations One limitation of the algorithm is that the result returned is guaranteed to be optimal only within an \epsilon bound. If a true global optimal solution is desired, additional search must be performed within previously explored simplices. Implementing such a search is a topic for future work. A second limitation is the use of an occlusion point to break up the surface. If that occlusion point is chosen poorly, the true optimal grasp may not be found. The initial simplex may be expanded to allow the curve to wrap past the occlusion point and avoid this problem (e.g., as in [ 7 ] ). Finally, the algorithm currently is restricted to 2D objects with contact on the perimeter. It can be applied to thin objects, extruded objects, and to arbitrary 3D object slices (with some care put towards the definition of valid grasp). A path to lift this restriction is outlined in the Appendix. VI Conclusion We have presented an iterative algorithm for computing maximal independent contact regions that is fast, complete, works for any number of contacts, and can be used as an anytime algorithm. The key insight behind this approach is that Delaunay triangulation, which extends well to higher dimensions, offers a powerful way to search the grasp configuration space for regions where large ICRs may be found. The resulting ICRs can be used as guidance for real-time grasp planning, learning, and shared control. We look forward to exploring these and many other applications. VII Appendix - A Path to General 3D Grasps A sketch of a general 3D solution follows. Any manifold mesh can be flattened in a manner that best preserves properties of interest, such as local surface areas (e.g., [ 34 ] ). ICRs on the surface of the mesh will appear as sets of circles on these flattened meshes, such that any grasp composed of one contact within each circle can be a valid grasp. The algorithm described in this manuscript can be used to identify such regions. For three contacts, for example, use the described algorithm to search for the largest empty circumsphere in a six-dimensional space, where the 6D space consists of three copies of the flattened mesh. Instead of growing hypercubes, grow circles outward for each flattened mesh, testing all combinations of grasps represented by points in the grown 6D volume. Adjust epsilon bounds to account for the change in region geometry. We are excited to explore this and other extensions such as soft area contacts, ICRs for rolling and sliding, and ICRs for policy learning in future research.