Iterative Convex Optimization with Control Barrier Functions for Obstacle Avoidance among Polytopes

Shuo Liu; Zhe Huang; Calin A. Belta

cs.ROMar 6, 2026

Iterative Convex Optimization with Control Barrier Functions for Obstacle Avoidance among Polytopes

Authors: Shuo Liu, Zhe Huang, Calin A. Belta

Organizations: Boston University, Brookline, MA, USA · Department of Electrical and Computer Engineering and with the Department of Computer Science, University of Maryland, College Park, MD, USA

Abstract

Obstacle avoidance of polytopic obstacles by polytopic robots is a challenging problem in optimization-based control and trajectory planning. Many existing methods rely on smooth geometric approximations, such as hyperspheres or ellipsoids, which allow differentiable distance expressions but distort the true geometry and restrict the feasible set. Other approaches integrate exact polytope distances into nonlinear model predictive control (MPC), resulting in nonconvex programs that limit real-time performance. In this paper, we construct linear discrete-time control barrier function (DCBF) constraints by deriving supporting hyperplanes from exact closest-point computations between convex polytopes. We then propose a novel iterative convex MPC-DCBF framework, where local linearization of system dynamics and robot geometry ensures convexity of the finite-horizon optimization at each iteration. The resulting formulation reduces computational complexity and enables fast online implementation for safety-critical control and trajectory planning of general nonlinear dynamics. The framework extends to multi-robot and three-dimensional environments. Numerical experiments demonstrate collision-free navigation in cluttered maze scenarios with millisecond-level solve times.

Figures & tables

Fig. 1 : Motivating example: an L-shaped robot performing narrow-passage traversal. Simulation results are shown in Sec. V-C .

Approaches	Explicitness	Smoothness	Metric	Optimization	Horizon	3-D Demonstrated	Multi-robot Demonstrated
SDF-linearized CBF [ 13 ]	Implicit	Smooth	Distance	Convex	$1$	Yes	No
Opti-free CBF [ 14 ]	Explicit	Smooth	Distance	Convex	$1$	No	Yes
Diff-opti CBF [ 15 ]	Implicit	Smooth	Scaling factor	Convex	$1$	Yes	No
Polynomial CBF [ 16 ]	Explicit	Smooth	Distance	Convex	$1$	No	No
Duality-based CBF [ 17 ]	Implicit	Nonsmooth	Distance	Convex	$1$	No	No
Duality-based DCBF + MPC [ 18 ]	Implicit	Nonsmooth	Distance	Nonconvex	$N$	No	No

TABLE I : Conceptual comparison of existing CBF-based collision avoidance methods for polytopic sets. Implicit indicates that CBFs are defined via optimization. Smoothness refers to the differentiability of the CBF function. Metric describes the geometric quantity used to quantify separation in the CBF.

Fig. 2 : Schematic of the iterative process of solving the convex MPC at time $t$ .

Panel of Figure 4 — Fig. 3 : Autonomous navigation results for different robot geometries in 2-D environments. The green circle and the red pentagon denote the starting position and the goal positions, respectively. The orange curve represents the local reference path, while the curves in other colors correspond to the predicted local trajectories generated by the controller.

Panel of Figure 5 — Fig. 4 : Navigation results from three viewpoints. The robot moves from the green circle (start) to the red pentagram (goal), generating collision-free trajectories in the cluttered environment.

Obstacle shapes			$\gamma_{1}=0.1$	$\gamma_{1}=0.2$
2-D Rectangle	N=6	mean / std (ms)	$5.016\pm 0.760$	$4.819\pm 0.675$
	N=12	mean / std (ms)	$11.406\pm 2.481$	$10.917\pm 2.064$
	N=24	mean / std (ms)	$30.592\pm 8.881$	$31.278\pm 9.042$
2-D Triangle	N=6	mean / std (ms)	$4.326\pm 0.432$	$4.457\pm 0.659$
	N=12	mean / std (ms)	$10.254\pm 1.184$	$10.318\pm 2.099$
	N=24	mean / std (ms)	$25.212\pm 5.186$	$25.065\pm 7.107$

TABLE II : Computation time statistics for 2-D and 3-D robot shapes under different horizon

N

and DHOCBF hyperparameter

\gamma_{1}

. Each entry reports mean and standard deviation over 50 trials.

Explore similar work

Long-Horizon Geometry-Aware Navigation among Polytopes via MILP-MPC and Minkowski-Based CBFs
Mar 31, 2026Yi-Hsuan Chen, Salman Ghori, Ania Adil +2Safe Robot Navigation Motion Planning
Dept. of Aerospace Engineering, University of Maryland, College Park, MD, USA. · Computer, Electrical and Mathematical Science & Engineering Division (CEMSE), KAUST, Saudi Arabia. · Dept. Electrical and Computer Engineering and Dept. Computer Science, University of Maryland, College Park, MD, USA.
Safe Polytope-in-Polytope Motion Planning and Control with Control Barrier Functions
Jun 8, 2026Alejandro Gonzalez-Garcia, Dries Dirckx, Jan Swevers +1Constrained Motion Planning Control Barrier Functions
Control Barrier Functions via Minkowski Operations for Safe Navigation among Polytopes
Aug 3, 2026Yi-Hsuan Chen, Shuo Liu, Wei Xiao +2Signed Distance Functions Control Barrier Functions
Department of Aerospace Engineering, University of Maryland, College Park, MD 20742, 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 +1

Mar 31, 2026J/K move · Enter open · S save

Long-Horizon Geometry-Aware Navigation among Polytopes via MILP-MPC and Minkowski-Based CBFs

Yi-Hsuan Chen, Salman Ghori, Ania Adil, Eric Feron+1

Dept. of Aerospace Engineering, University of Maryland, College Park, MD, USA. · Computer, Electrical and Mathematical Science & Engineering Division (CEMSE), KAUST, Saudi Arabia. · Dept. Electrical and Computer Engineering and Dept. Computer Science, University of Maryland, College Park, MD, USA.

Safe Robot Navigation Motion Planning Constrained Motion Planning Control Barrier Functions Model Predictive Control

Open paper AskPDF arXiv

Autonomous navigation in complex, non-convex environments remains challenging when robot dynamics, control limits, and exact robot geometry must all be taken into account. In this paper, we propose a hierarchical planning and control framework that bridges long-horizon guidance and geometry-aware safety guarantees for a polytopic robot navigating among polytopic obstacles. At the high level, Mixed-Integer Linear Programming (MILP) is embedded within a Model Predictive Control (MPC) framework to generate a nominal trajectory around polytopic obstacles while modeling the robot as a point mass for computational tractability. At the low level, we employ a control barrier function (CBF) based on the exact signed distance in the Minkowski-difference space as a safety filter to explicitly enforce the geometric constraints of the robot shape, and further extend its formulation to a high-order CBF (HOCBF). We demonstrate the proposed framework in U-shaped and maze-like environments under single- and double-integrator dynamics. The results show that the proposed architecture mitigates the topology-induced local-minimum behavior of purely reactive CBF-based navigation while enabling safe, real-time, geometry-aware navigation.

Abstract

Explore similar work

Long-Horizon Geometry-Aware Navigation among Polytopes via MILP-MPC and Minkowski-Based CBFs

Safe Polytope-in-Polytope Motion Planning and Control with Control Barrier Functions

Control Barrier Functions via Minkowski Operations for Safe Navigation among Polytopes