Source-linked AI summary
GJK-CBF: Control Barrier Functions for Convex Rigid Body Collision Avoidance on SE(3)
Yi-Hsuan Chen, Shuo Liu, Wei Xiao, Michael Otte, Calin Belta
TL;DR
Collision avoidance for convex bodies requires accounting for both bodies’ geometry, while existing CBF formulations often obtain exact separation gradients through differentiable optimization. GJK-CBF constructs the exact distance gradient from the witness pair without diffOpt, subject to a strict-convexity condition. The paper reports collision-free motion across its validation scenarios and less-conservative motion than supporting-hyperplane CBF in comparative studies.
Problem
For general convex bodies, exact separation measures are typically optimized and their CBF gradients often use differentiable optimization, adding computational overhead.
Source: §I · pp. 1–2Method
GJK-CBF uses the witness pair to construct an explicit exact-distance gradient on SE(3) without diffOpt, for convex-body pairs with at least one strictly convex body.
Source: §I · p. 2Results
The method is reported to maintain collision-free motion in the evaluated scenarios and to be less conservative than supporting-hyperplane CBF in comparative studies.
Source: A. Comparative study · pp. 6–7, C. 6-DOF UR5 manipulator · p. 7, §VI · p. 7Takeaways & Limitations
The formulation applies in 2D and 3D and was validated in multi-robot swaps, vertical-slit navigation, and a UR5 manipulator application.
Source: §I · p. 2, §VI · p. 7Each collision pair must contain at least one strictly convex body; relaxing this assumption is left for future work.
Source: §I · p. 2, §VI · p. 7
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Robotic collision avoidance must account for both bodies’ geometry while satisfying motion and safety constraints, but exact separation gradients are commonly obtained through differentiable optimization. GJK-CBF instead uses the witness pair to construct an exact distance gradient without diffOpt, for convex-body pairs meeting a strict-convexity condition.
I. INTRODUCTION
- Geometry-aware collision avoidance must handle separation that depends on both bodies’ relative position and orientation, while satisfying kinematic or dynamic constraints, safety, and actuation limits.Prior CBF approaches either differentiate optimization-based separation measures or use optimization-free surrogate measures.Source: §I · pp. 1–2
- GJK-CBF derives the exact distance gradient directly from the witness pair, avoiding diffOpt for convex rigid bodies when at least one body in each pair is strictly convex.The formulation is geometry-agnostic within this class and applies in both 2D and 3D.Source: §I · p. 2
- The framework can be implemented decentrally when each collision pair’s information is accessible to its corresponding robots.The introduction also reports validation across 2D and 3D scenarios and comparison with the supporting-hyperplane CBF.Source: §I · p. 2
A. Control Barrier Functions (CBFs)
- The CBF safe set is the zero-superlevel set of a continuously differentiable function, and satisfying the CBF condition makes that set forward invariant.A minimally invasive safety filter can impose the CBF constraint in a discretized quadratic program.Source: A. Control Barrier Functions (CBFs) · p. 2
B. Rigid Body Kinematics on Lie Groups
Rigid-body configurations are described using Lie groups for rotation and pose, with body velocity represented as a twist. The kinematics express position and orientation changes in terms of that body velocity.
B. Rigid Body Kinematics on Lie Groups
- Rigid-body motion combines translation and rotation and is described using SO(d), SE(d), and their Lie algebras for d ∈ {2, 3}.The body configuration is specified relative to an inertial world frame and a body-fixed frame.Source: B. Rigid Body Kinematics on Lie Groups · pp. 2–3
- The body velocity, or twist, comprises translational and angular velocity, and the rigid-body kinematics relate it to changes in position and orientation.The body origin may be chosen arbitrarily; orientation is represented by R_i and position by p_i.Source: B. Rigid Body Kinematics on Lie Groups · p. 3
- In 2D, angular velocity is represented by a scalar ω ∈ R; in 3D, it is represented by a vector ω = [ω1, ω2, ω3]⊤ ∈ R3, with corresponding hat maps introduced.Equivalently, the kinematics can be written in homogeneous form.Source: B. Rigid Body Kinematics on Lie Groups · p. 3
III. PROBLEM FORMULATION
The problem considers collision avoidance among robots and static obstacles modeled as convex rigid bodies in 2D or 3D. Given collision-free initial and goal configurations, each robot needs a safe controller that minimally modifies its nominal controller while avoiding collisions.
III. PROBLEM FORMULATION
- Robots and obstacles are modeled as convex rigid bodies in a 2D or 3D workspace, with robot pose as state and body velocity as input.The formulation also allows alternative Euler-angle and quaternion state representations in 3D.Source: §III · p. 3
- The assumptions require compact convex occupied sets with nonempty interiors, static obstacles, and at least one strictly convex body in every collision pair.Robots must have access to relevant robot and obstacle information, with perfect inter-robot communication assumed.Source: §III · p. 3
- Given collision-free initial and goal configurations, the task is to design admissible safe controllers that minimally modify nominal controllers while avoiding robots and obstacles.The robots’ admissible control sets are convex polyhedral sets.Source: §III · p. 3
IV. MAIN RESULTS
The section formulates minimum distance as a collision-avoidance CBF and derives its time derivative from the current witness pair and rigid-body motion. It establishes the conditions for differentiability and safe-set invariance, while noting limits for nonunique penetration witnesses and force- or torque-controlled systems.
A. Minimum Distance as a CBF
- Under Assumption (ii), the witness pair is unique and continuous, making the CBF continuously differentiable with respect to the pair configuration.The formulation requires Assumption (ii) for differentiability, not for computing the witness pair.Source: A. Minimum Distance as a CBF · p. 3
- The CBF derivative is computed from the witness pair, current configurations, and body-velocity controls, without differentiating the optimization that finds the pair.The witness pair can be obtained with GJK or other proximity-query algorithms.Source: A. Minimum Distance as a CBF · pp. 3–4
- Under the CBF condition, the safe set is forward invariant, maintaining separation for all time.For the driftless kinematics considered, zero input satisfies the CBF condition.Source: A. Minimum Distance as a CBF · p. 4
- For intersecting bodies, the same derivative applies when the penetration witness pair is unique; nonunique pairs introduce nonsmoothness.The paper focuses on the C1 setting established in Lemma 1.Source: A. Minimum Distance as a CBF · pp. 3–4
- For force- or torque-controlled systems, the distance-based CBF has relative degree two, and a direct extension requires a higher-order CBF involving distance-Hessian sensitivity.The control first appears in the CBF's second time derivative.Source: A. Minimum Distance as a CBF · p. 4
B. Alternative Attitude Representations in 3D
The GJK-CBF derivative can be expressed using Euler angles or unit quaternions in 3D, as well as the default SE(d) representation. These attitude representations differ in their parameterization and singularity properties.
B. Alternative Attitude Representations in 3D
- Euler angles are intuitive and minimal but have singularities, while quaternions avoid them at the cost of an additional parameter.The paper gives equivalent expressions for the CBF derivative in both representations.Source: B. Alternative Attitude… · pp. 4–5
- The Euler-angle derivative expression is valid away from the singularity, where cos θ_k ≠ 0.The result reduces to an earlier rod-shaped-robot result when roll is zero.Source: B. Alternative Attitude… · p. 5
- For unit quaternions, the derivative expression uses a valid quaternion-coordinate Jacobian obtained via a left inverse.The state is constrained to unit quaternions.Source: B. Alternative Attitude… · p. 5
C. Decentralized Implementation
The decentralized implementation splits each pairwise CBF constraint between the two robots so that each independently solves for its own control input. Under perfect communication and feasible local QPs, the split constraints recover the original pairwise safety condition.
C. Decentralized Implementation
- Each robot independently computes the pairwise CBF value and its own body-velocity Jacobian, then solves a local CBF-QP for its control input.The pairwise responsibility is divided using a user-defined parameter that may reflect control capabilities.Source: C. Decentralized Implementation · p. 5
- The two local constraints sum to the original pairwise CBF condition, yielding forward invariance when the local QPs are feasible and communication is perfect.These conditions are stated under Assumption (iii).Source: C. Decentralized Implementation · p. 5
- Each robot enforces at most N − 1 inter-robot constraints in one local QP, with M additional robot-obstacle constraints.Source: C. Decentralized Implementation · p. 5
V. SIMULATION RESULTS
The simulations assess GJK-CBF in 2D and 3D robot position-swapping scenarios, 3D slit passage, and a velocity-controlled manipulator. Figure 2 compares six ellipsoidal robots swapping positions using GJK-CBF and supporting-hyperplane-CBF.
V. SIMULATION RESULTS
- The validation includes 2D and 3D multirobot position swapping, passage through a 3D slit, and a velocity-controlled manipulator example.Source: §V · p. 5
- The simulations use superellipsoids to model strictly convex bodies; their shape parameter ρ determines whether they are ellipsoid-like or increasingly box-like.ρ = 2 gives an ellipsoid, and larger ρ produces increasingly box-like shapes.Source: §V · p. 5
- Figure 2 compares trajectories for six ellipsoidal robots swapping positions and plots minimum pairwise CBF values and control-loop computation-time distributions.The computation-time distributions include pairwise CBF evaluations and local QP solves for the six robots.Source: Figure 2 · p. 6
A. Comparative study
The comparison shows GJK-CBF maintaining separation in the robot swap and allowing direct passage through a slit where enclosing-ellipsoid approximations force a detour. The tested supporting-hyperplane-CBF also has lower computation time, but uses a higher-dimensional local QP.
A. Comparative study
- The robot-swap comparison uses six heterogeneous ellipsoidal robots whose goals are the initial positions of their diametrically opposite robots.The robots are simulated for 8 s with a 5 ms time step.Source: A. Comparative study · p. 6
- In the tested comparison, GJK-CBF maintains positive pairwise separation while supporting-hyperplane-CBF results in inter-robot collisions.The authors note the collisions might arise from inter-sample effects.Source: A. Comparative study · p. 6
- The supporting-hyperplane-CBF has lower computation time but a higher-dimensional local QP; the custom GJK implementation is not optimized for computational efficiency.The authors anticipate accelerated variants such as GJK++ can further reduce GJK-CBF runtime.Source: A. Comparative study · p. 6
- In slit passage, GJK-CBF with original geometries allows direct passage, while enclosing-ellipsoid approximations force a detour above the obstacles.The comparison uses a 4 × 8 × 1 m box-shaped robot and two superellipsoidal obstacles.Source: A. Comparative study · pp. 6–7
B. Multi-robot swap in 3D
Four heterogeneous superellipsoidal robots exchange diagonally opposite poses using decentralized GJK-CBF, with all robots maintaining positive pairwise CBF values.
B. Multi-robot swap in 3D
- All four robots safely exchange poses while maintaining positive pairwise CBF values.The result is shown for the decentralized GJK-CBF.Source: B. Multi-robot swap in 3D · p. 7, Figure 3 · p. 7
- The robots exchange diagonally opposite poses and differ in their semi-axes and shape parameters.The simulation runs for 6 s with a 10 ms time step.Source: B. Multi-robot swap in 3D · p. 7
- The accompanying figure shows pose-exchange snapshots above and the corresponding pairwise CBF values below.Source: Figure 3 · p. 7
C. 6-DOF UR5 manipulator
The paper applies GJK-CBF to a velocity-controlled UR5 manipulator whose nominal end-effector path intersects two obstacles. The safety filter modifies joint velocities to guide the manipulator around them.
C. 6-DOF UR5 manipulator
- The UR5 is modeled with four superellipsoids enclosing its upper arm, forearm, and two wrist sections, and the input is joint velocity.The task moves the end effector from a start point to a goal point.Source: C. 6-DOF UR5 manipulator · p. 7
- Without the safety filter, the nominal trajectory intersects both obstacles; GJK-CBF modifies joint velocities and guides the manipulator around them.The joint-velocity bounds are −1.5 to 1.5 rad/s for each joint.Source: C. 6-DOF UR5 manipulator · p. 7
- For each link-obstacle pair, the CBF derivative is computed by chaining the body-velocity Jacobian with the parent-link geometric Jacobian.The parent-link frame origin is used as the reference point for the body-velocity Jacobian.Source: C. 6-DOF UR5 manipulator · p. 7
VI. CONCLUSIONS AND FUTURE WORK
GJK-CBF is a distance-based collision-avoidance CBF for convex-body pairs, with at least one strictly convex body per pair. The paper reports collision-free validation and reduced conservativeness, while identifying higher-relative-degree systems as future work.
VI. CONCLUSIONS AND FUTURE WORK
- GJK-CBF provides a general distance-based collision-avoidance CBF for convex bodies when at least one body in each pair is strictly convex.Source: §VI · p. 7
- The method is reported continuously differentiable, with its gradient computed from the witness pair without diffOpt.Source: §VI · p. 7
- Validation covers 2D and 3D position swapping, 3D slit passage, and a UR5 manipulator; comparison with supporting-hyperplane-CBF shows less conservativeness while maintaining collision-free motion.Source: §VI · p. 7
- Future work would relax strict convexity using generalized gradients and nonsmooth CBFs, and extend the framework to higher-relative-degree systems.Source: §VI · p. 7