Organizations: Department of Aerospace Engineering, University of Maryland, College Park, MD, USA · Department of Mechanical Engineering, Boston University, Boston, MA 02215, USA · School of Electrical and Electronic Engineering, Nanyang Technological University, and with M3S, SMART, Singapore · Department of Electrical and Computer Engineering and Department of Computer Science, University of Maryland, College Park, MD, USA
Collision avoidance among convex bodies is a fundamental problem in robotics. Control Barrier Functions (CBFs) provide a practical framework for real-time safety filtering due to their computational efficiency. For general convex bodies, exact separation measures, such as distance or scaling factor, are typically computed through optimization. Existing CBF formulations often obtain the required gradient via differentiable optimization (diffOpt), adding computational overhead. In contrast, we leverage the Gilbert-Johnson-Keerthi (GJK) algorithm to obtain the current witness pair---the pair of points realizing the minimum distance or penetration depth---and formulate a CBF, termed GJK-CBF, whose gradient is constructed directly from the relative rigid-body motion of the witness pair, without resorting to diffOpt. This formulation applies to both 2D and 3D environments across a broad class of convex body pairs, provided that at least one in each one-to-one interaction is strictly convex. The proposed GJK-CBF is validated in various scenarios, including multi-robot position swapping in both 2D and 3D, navigation through a vertical slit in 3D, and its applicability to manipulators. The results demonstrate collision-free motion across all scenarios while reducing the conservativeness introduced by geometric approximations, particularly in narrow environments.
Figures & tables
Figure 1: Side (left) and top (right) views of a polytopic robot (blue) traversing a vertical slit in 3D. (Top) Conservative enclosing-ellipsoid approximations render the direct passage through the slit infeasible, forcing the robot to slightly detour above the obstacles [ 7 ] . (Bottom) In contrast, the proposed GJK-CBF operates directly on the original convex geometries and successfully guides the robot through. Its construction and gradient computation require only the pair of closest points—witness pair—between two convex bodies without using differentiable optimization . Only the initial and goal poses are given, with no intermediate poses or waypoints.
Figure 2: Left: Comparison between (top) the supporting-hyperplane-CBF [ 7 ] and (bottom) the proposed GJK-CBF for six ellipsoidal robots swapping positions. Dotted outlines denote the desired poses, and solid curves show the robot trajectories. Dash-dotted lines in the top row represent the supporting hyperplanes. Right: (top) minimum pairwise CBF values and (bottom) control-loop computation-time distributions, which are measured for the serial implementation and include all pairwise CBF evaluations and local QP solves for the six robots.
Figure 3: Top: Snapshots of four heterogeneous superellipsoidal robots exchanging diagonally opposite poses using the decentralized GJK-CBF ( 18 ). Bottom: The corresponding pairwise CBF values.
Figure 4: Collision avoidance for a velocity-controlled UR5 manipulator. Top: Side (left) and top (right) views of the motion from the start (green) to the goal (magenta). The blue and cyan curves denote the reference and filtered end-effector trajectories, respectively. Bottom: CBF values for the four links relative to superellipsoidal obstacles O1 and O2 .
GRASP Laboratory, University of Pennsylvania, Philadelphia, PA, USA · Department of Computer Science, University of Illinois Chicago, Chicago, IL, USA · Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC, USA
Department of Electrical and Computer Engineering at Northeastern University, Boston, MA · Departments of Mechanical and Industrial Engineering and Electrical and Computer Engineering at Northeastern University, Boston, MA