cs.ROMar 31, 2026

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

Authors: Yi-Hsuan Chen, Salman Ghori, Ania Adil, Eric Feron, Calin Belta

Organizations: 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.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: Top: The proposed multi-rate framework with a MILP-MPC planner and a geometry-aware Minkowski-CBF safety filter. Bottom: A triangular robot with double-integrator dynamics navigating in a polytopic maze-like environment. It collides with an obstacle when using MILP-MPC alone with a point-mass model (pink), and becomes trapped in a local minimum using a CLF-CBF-QP approach (orange) due to its inherent reactive nature. In contrast, the proposed framework (blue) successfully guides the robot to the goal without a reference path or waypoints from an external planner .
Figure 2: Long-horizon nominal predictions (dashed cyan) generated by the high-level MILP-MPC planner under (a) single- ( Top ) and (b) double-integrator ( Bottom ) dynamics, navigating the robot to the goal. Left: The actual closed-loop trajectory (solid blue) tracks the MPC predicted states (brown squares) as the robot (blue) avoids obstacles (gray). Right: Control inputs u\bm{u} and CBF values, verifying that strict safety h(x)≥0h(\bm{x})\geq 0 is guaranteed with respect to the real robot’s geometry over time.
Figure 3: Top-row: Comparison of the proposed MILP-MPC-CBF framework in a U-shaped environment under single- ( Left column) and double-integrator ( Right column) dynamics. In each case, the left compares the proposed framework with MILP-MPC only, where the green segment indicates the interval during which the geometry-aware Minkowski-(HO)CBF safety filter is active, while the right compares it with the reactive CLF-(HO)CBF-QP. Bottom-row: Time histories of control inputs u\bm{u} and CBFs hh for MILP-MPC-CBF, showing that the full-geometry robot remains in the safe set throughout the navigation.

Explore similar work

CardsList

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

    Mar 6, 2026Shuo Liu, Zhe Huang, Calin A. BeltaRobot Collision AvoidanceSafe Motion Planning

    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

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

    Jun 8, 2026Alejandro Gonzalez-Garcia, Dries Dirckx, Jan Swevers +1Constrained Motion PlanningControl Barrier Functions

  3. Control Barrier Functions via Minkowski Operations for Safe Navigation among Polytopes

    Aug 3, 2026Yi-Hsuan Chen, Shuo Liu, Wei Xiao +2Signed Distance FunctionsControl 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