Safe Navigation under Uncertain Obstacle Dynamics using Control Barrier Functions and Constrained Convex Generators

arXiv:2601.07715 · eess.SY, cs.SY · Submitted 2026-01-12 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa, and with me are Dev and Taro, guest researcher.

Dev: Today's paper: "Safe Navigation under Uncertain Obstacle Dynamics using Control Barrier Functions and Constrained Convex Generators".

Rosa: Safe navigation under uncertain obstacle dynamics using Control Barrier Functions and Constrained Convex Generators presents a framework for collision-free motion of controlled agents in cluttered environments governed by uncertain linear…

Dev: First, who's behind it and why it matters.

Title and authors: Rosa: So we’re talking about the paper 'Safe Navigation under Uncertain Obstacle Dynamics using Control Barrier Functions and Constrained Convex Generators.' I want to start by getting a handle on what this title actually suggests is going on in terms of the core technical challenge they're tackling.

Dev: The title points directly at navigating around obstacles when those obstacles have uncertain dynamics, which means we're not dealing with perfectly predictable movement or fixed positions; it’s about handling that uncertainty within a safety framework.

Taro: From my perspective as an autonomy researcher, the uncertainty in dynamics is crucial because if the environment changes unexpectedly, you need a system that can react predictably without completely losing its guaranteed safe trajectory.

Rosa: Exactly; and the authors are proposing using Control Barrier Functions combined with Constrained Convex Generators to achieve collision-free motion in this uncertain setting. It sounds like they are aiming for a solution where safety is mathematically guaranteed through these two specific mathematical tools working together.

Dev: Mathematically, it suggests that the CBF provides the hard safety constraint, and the CCGs handle the uncertainty in how those obstacles move over time by providing a set-valued estimate of their possible positions.

Taro: That combination seems powerful because it allows you to use a method—set-valued estimation—that might be more robust in noncooperative or adversarial settings than traditional stochastic methods.

Rosa: Right; and the abstract mentions that they present a sampled-data framework for this, which is an important detail because it grounds the estimation process in discrete time steps rather than continuous tracking.

Dev: That sampled-data aspect ties directly into my concerns about loop rate; we have to ensure that the calculation of those CCG estimates at each sampling instant is computationally efficient enough for real-time operation.

Taro: If the estimation scheme itself becomes too slow or complex, it defeats the purpose of having a guaranteed controller, so I'm wondering how they managed to keep that estimation scheme tractable.

Rosa: The paper highlights that the core difficulty isn't just using CBFs or CCGs in isolation, but managing the conversion process between them when dealing with these set-valued representations.

Dev: That conversion is where I anticipate some tricky implementation issues, especially since they state that CCGs aren't directly translatable to CBFs without their proposed procedure.

Taro: So the paper’s main focus seems to be solving that non-trivial translation problem—how to map those estimated obstacle flows into a usable safety constraint for the controller.

Rosa: Precisely; and they claim one of their main contributions is developing a specific procedure for this conversion that yields a CBF via a convex optimization problem whose validity is established by the Implicit Function Theorem.

Dev: Establishing validity through the Implicit Function Theorem is strong mathematical backing, but it means we have to trust that the optimization problem always has a solution and that its structure remains valid across all relevant parameters.

Taro: It sounds like they've done a lot of foundational work on the mathematical machinery before showing how it applies to more complex dynamics or geometries.

Rosa: That’s right; and this paper sets up the foundation for using these tools in more demanding scenarios, which is what makes me excited about its potential impact.

Dev: I'm ready to see how they handle the computational load when we start integrating this into a high-speed loop, because MPC with CCGs is already computationally heavy.

The paper's summary: Rosa: Now that we’ve talked about the setup, let’s look at what they actually achieved in terms of their methodology for 'Safe Navigation under Uncertain Obstacle Dynamics using Control Barrier Functions and Constrained Convex Generators.' Essentially, what is the high-level summary of their main technical contribution?

Dev: The summary says collision-free motion is achieved by combining two main components: Control Barrier Function based safety filtering with set-valued state estimation using Constrained Convex Generators. That’s the architecture we need to understand.

Taro: So, at each sampling time, they run a finite-horizon guaranteed estimation scheme to get a CCG estimate of each obstacle, which is then propagated over the interval to create an estimated obstacle evolution flow.

Rosa: And that flow gives us a CCG-valued description of how the obstacles are expected to move in the next time step, which is then used to define what we consider "safe" for our agent's motion.

Dev: This estimated evolution flow is then translated into a set of obstacle-specific CBFs, and these specific CBFs are merged into a single overall safety filter using a smooth approximation of the minimum function.

Taro: So, instead of just checking if the agent’s position is safe relative to one obstacle at one time, they are creating a unified safety filter that accounts for all obstacles simultaneously in this estimated way.

Rosa: That unification is key; it moves us from managing individual constraints to managing a single overall safety condition derived from all the estimated CCG information.

Dev: And finally, this overall safety filter is then used to design the final controller through the standard Quadratic Program based approach, which essentially boils down to finding a safe control input that respects all those derived constraints.

Taro: So, for me, the system seems designed to be very systematic; it takes raw uncertainty and systematically processes it through estimation and conversion steps into a formal safety guarantee.

Rosa: Right; and this systematic processing is what makes me feel confident that the results are robust across different scenarios, even if the initial estimates aren't perfect yet.

Dev: I’m still focused on how that final QP formulation performs under high-frequency updates, because we need to make sure it doesn't introduce unacceptable delays into our control loop.

The paper's improvements: Rosa: Moving on to the improvements they suggest for 'Safe Navigation under Uncertain Obstacle Dynamics using Control Barrier Functions and Constrained Convex Generators,' what are the specific enhancements they propose to this framework?

Dev: The primary improvement is that they developed reduction techniques for specific set representations, including zonotopes, ellipsotopes, CZs, and CCGs. This suggests that while CCGs are useful, there might be other ways to simplify or refine the representation before feeding it into the CBF conversion step.

Taro: That makes sense because handling zonotopes or ellipsoids is often computationally easier than dealing with general affine transformations of generator sets, which might simplify the subsequent optimization problem.

Rosa: And they also introduced a newer CCG finite-horizon scheme that refines an estimate computed by an ellipsoidal observer using a limited history of measurements, which removes the need for order reduction methods.

Dev: That refinement technique sounds promising because if it can improve the accuracy of those initial estimates without adding massive computational overhead, it could help mitigate some of the issues we discussed earlier about needing order reduction techniques.

Taro: So, essentially they are trying to create a more efficient estimation pipeline that is both accurate and computationally manageable for real-time use.

Rosa: I think this addresses the computational burden head-on; it shows a pathway to get better accuracy without sacrificing the speed of computation needed for deployment.

Dev: That’s important because if we can reduce the complexity of the estimation step, it directly impacts our latency budget for control decisions.

Conclusion: Rosa: We’ve covered a lot about how this paper tackles collision-free motion under uncertain dynamics using Control Barrier Functions and Constrained Convex Generators. To wrap up, what are the final implications of this work for us?

Dev: The biggest implication is that we can now achieve guaranteed collision-free motion even when the obstacle dynamics are uncertain, which opens up applications in scenarios where we previously had to rely on less conservative approaches.

Taro: It’s about moving towards systems that are more reliable, and I see this as a step toward creating autonomous agents that can operate in unpredictable environments without constant manual intervention.

Rosa: I think the work demonstrates a general method for handling rigid-body agents of arbitrary geometry, which is something we really need to see implemented widely outside of simulation.

Dev: From an engineering standpoint, the paper lays out a path for creating certified safety filters using QP formulations, which means we can actually build systems where safety certification isn't just a theoretical concept but something we can implement in hardware.

Taro: I think the ability to treat general shapes systematically is a big win for real-world deployment because it removes the guesswork about how to model complex physical interactions correctly.

Rosa: So, in short, this paper introduces this framework, and listeners should keep an eye on how they move these concepts from theory into practical applications. We’ll wrap up our discussion on this paper here.

NOVA School of Science and Technology · Institute for Systems and Robotics

eess.SY, cs.SY

Submitted: 2026-01-12

Updated: 2026-10-04

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 82/100

The gist: Safe navigation under uncertain obstacle dynamics using Control Barrier Functions and Constrained Convex Generators presents a framework for collision-free motion of controlled agents in cluttered

Key concepts

Control Barrier Function (CBF): A mathematical function used in control systems to guarantee safety by ensuring that the system state never enters a forbidden region. If the CBF value remains non-negative, it signifies that the agent is safely away from obstacles, allowing for safe control adjustments.
Constrained Convex Generator (CCG): A method used for guaranteed state estimation in uncertain environments. It provides an estimate of where an obstacle will be by using a finite-horizon scheme and propagating these estimates over time to predict the obstacle's evolution.
Conversion Procedure: The core innovation that translates the CCG estimates into CBFs. Since CCGs are not directly CBFs, this procedure uses convex optimization problems to generate an obstacle-specific CBF, ensuring safety is maintained despite the uncertainty in the estimated obstacle trajectory.

Terminology

Control Barrier Function — 26× in this paper
European Control Conference — 5× in this paper
Instituto Superior Tecnico — 5× in this paper
Quadratic Program — 5× in this paper
Closed-Loop System — 3× in this paper · explained in 4 episodes
Conference on Decision and Control — 3× in this paper
Core — 3× in this paper · explained in 2 episodes
Accuracy — 2× in this paper · explained in 1 episode
American Control Conference — 2× in this paper
Control Barrier Function (CBF) — 2× in this paper · explained in 5 episodes
Control Barrier Functions (CBFs) — 2× in this paper · explained in 4 episodes
Hybrid System — 2× in this paper · explained in 2 episodes
Theoretical Guarantees — 2× in this paper · explained in 2 episodes
Combining Model Predictive Control — 1× in this paper
Computational overhead — 1× in this paper · explained in 2 episodes
Model Predictive Control (MPC) — 1× in this paper · explained in 5 episodes
Multi-Agent System — 1× in this paper · explained in 6 episodes
Singular Value Decomposition (SVD) — 1× in this paper · explained in 2 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

Safe navigation under uncertain obstacle dynamics using Control Barrier Functions and Constrained Convex Generators presents a framework for collision-free motion of controlled agents in cluttered environments governed by uncertain linear dynamics. This work addresses the challenge of ensuring safety when obstacles are modeled with uncertainty by combining set-valued state estimation with control barrier functions to design safe controllers.

The gist

Collision-free motion is achieved by combining Control Barrier Function (CBF)-based safety filtering with set-valued state estimation using Constrained Convex Generators (CCGs).

Guaranteed State Estimation using CCGs

The paper utilizes a sampled-data framework for guaranteed state estimation, which is crucial in noncooperative or adversarial settings where set-valued estimation offers an alternative to stochastic filtering. The core of this component involves obtaining a CCG estimate of each obstacle using a finite-horizon guaranteed estimation scheme at each sampling time. These estimates are then propagated over the sampling interval to obtain a CCG-valued flow that describes the estimated obstacle evolution. This process is formalized by recursive formulas that allow for the explicit computation of these CCG parameters, which are derived from an initial conservative estimate and fixed auxiliary variables precomputed offline.

Conversion of CCGs to Control Barrier Functions (CBFs)

A central and nontrivial contribution of this paper is a procedure to perform this conversion, which translates the estimated obstacle flows into CBFs. Since CCGs are defined as an affine transformation of a generator set subject to equality constraints, rather than as a sublevel set of a scalar function, they cannot be directly translated into CBFs. The authors develop a procedure that produces a CBF via a convex optimization problem whose validity is established by the Implicit Function Theorem. Subsequently, these obstacle-specific CBFs are then merged into a single CBF using a smooth approximation of the minimum function, and this overall safety filter is used to design the final controller through the standard Quadratic Program (QP)-based approach.

Handling Agent and Obstacle Geometries

The proposed framework naturally generalizes existing designs because CCGs support Minkowski sums, the proposed framework also naturally handles rigid-body agents and generalizes existing CBF-based rigid-body navigation designs to arbitrary agent and obstacle geometries. Specifically, the authors treat the agent as a point-mass agent by introducing an enlarged obstacle set that incorporates the agent body geometry. This allows for a systematic treatment of general agent and obstacle shapes once a mechanism for translating CCGs into CBFs is developed. The method is demonstrated for agents with both first-order control-affine dynamics and second-order strict-feedback dynamics, extending the approach via backstepping techniques.

Safety Controller Design

The final step involves designing a safe controller based on the overall CBF. For first-order systems, if the agent's position at time instant tk satisfies pk ∈ int(∩i∈ICi,k(tk)), then we can select the parameter βk so that hk(pk, tk) ≥ 0, thereby ensuring safety over the interval [tk, tk+1). For second-order systems (e.g., satellite dynamics), a backstepping-based design is required to construct a CBF for the extended state space. This involves defining an intermediate function, such as h1(p, z, t) = h(p, t) − 1/2σ∥z − k(p, t)∥2, which serves as a CBF for the second-order system. The resulting controller is then synthesized via a QP that minimizes the deviation from the nominal controller while satisfying h˙ k(p, t, z) ≥ −α1(hk1(p, z, t)).

Simulation and Practical Application

The effectiveness of the proposed method is demonstrated through three simulation examples. These examples cover various geometries (ellipsoidal and polytopic agents/obstacles) and dynamics (first-order control-affine and second-order strict-feedback models). The simulations confirm that collision-free motion is achieved for all the initial agent positions, confirmed by the nonnegativity of the overall CBF values over time. The results show that while the initial estimates from a finite horizon estimator might be looser estimates, they become steadier and tighter estimates after an initial transient phase, with tightness determined by parameters like the horizon length N and set bounds W and V. The framework is shown to be robust across different agent dynamics and obstacle geometries.

Conclusion

The paper introduces a control strategy that integrates CCG-based guaranteed state estimation with CBF safety filtering to ensure safe navigation around obstacles under uncertain linear dynamics. The key innovation lies in the procedure for converting the estimated CCG-valued flows into time-varying CBFs via convex optimization, providing a general method applicable to rigid-body agents of arbitrary geometry.

Improvements for AI systems

Here are specific improvements to AI systems based on the proposed framework:

Safety-Critical Navigation in Cluttered/Dynamic Environments:
Guaranteed Collision-Free Motion for Rigid-Body Agents with Arbitrary Geometries:
Robust State Estimation Under Uncertain Linear Dynamics (Sampling Framework):
Implementation of Smooth, Certified Safety Filters via Convex Optimization (QP):

AI systems utilizing this framework can achieve the following specific capabilities:

Safety-Critical Navigation in Cluttered/Dynamic Environments: The system can navigate a rigid agent through environments populated with dynamic obstacles where the agents' motion is governed by uncertain linear dynamics (e.g., unknown velocities or bounded disturbances). The core capability is guaranteeing that the agent's trajectory will never intersect any obstacle, even when relying on set-valued state estimations that account for input uncertainties.
Guaranteed Collision-Free Motion for Rigid-Body Agents with Arbitrary Geometries: The framework generalizes existing control barrier functions (CBFs) to handle arbitrary agent and obstacle geometries (e.g., non-convex shapes, mixtures of polytopes and ellipsoids). This allows the AI system to safely navigate complex obstacles that are modeled as general convex sets defined by Constrained Convex Generators (CCGs), rather than being restricted to simple shapes like spheres or boxes.
Robust State Estimation Under Uncertain Linear Dynamics (Sampling Framework): The system employs a sampled-data framework where state estimates of dynamic obstacles are obtained at discrete sampling instants using a finite-horizon guaranteed estimation scheme based on CCGs. This ensures that the obstacle state estimates are mathematically guaranteed to contain the true states, providing a robust foundation for control decisions even when measurements are noisy or inputs are uncertain.
Implementation of Smooth, Certified Safety Filters via Convex Optimization (QP): The system utilizes a procedure to convert the CCG-valued flow describing an estimated obstacle's evolution into time-varying Control Barrier Functions (CBFs). This conversion is achieved via a convex optimization problem, and the resulting safety filter is designed by minimizing the deviation from a nominal controller using a Quadratic Program (QP). This results in smooth and certified controllers that guarantee forward invariance of the safe set, ensuring collision avoidance while minimally perturbing the nominal control law.

Abstract

This paper presents a sampled-data framework for the safe navigation of controlled agents in environments cluttered with obstacles governed by uncertain linear dynamics. Collision-free motion is achieved by combining Control Barrier Function (CBF)-based safety filtering with set-valued state estimation using Constrained Convex Generators (CCGs). At each sampling time, a CCG estimate of each obstacle is obtained using a finite-horizon guaranteed estimation scheme and propagated over the sampling interval to obtain a CCG-valued flow that describes the estimated obstacle evolution. However, since CCGs are defined indirectly---as an affine transformation of a generator set subject to equality constraints, rather than as a sublevel set of a scalar function---converting the estimated obstacle flows into CBFs is a nontrivial task. One of the main contributions of this paper is a procedure to perform this conversion, ultimately yielding a CBF via a convex optimization problem whose validity is established by the Implicit Function Theorem. The resulting obstacle-specific CBFs are then merged into a single CBF that is used to design a safe controller through the standard Quadratic Program (QP)-based approach. Since CCGs support Minkowski sums, the proposed framework also naturally handles rigid-body agents and generalizes existing CBF-based rigid-body navigation designs to arbitrary agent and obstacle geometries. While the main contribution is general, the paper primarily focuses on agents with first-order control-affine dynamics and second-order strict-feedback dynamics. Simulation examples demonstrate the effectiveness of the proposed method.