Hybrid System Planning using a Mixed-Integer ADMM Heuristic and Hybrid Zonotopes

Joshua A. Robbins; Andrew F. Thompson; Jonah J. Glunt; Herschel C. Pangborn

cs.ROFeb 19, 2026

Hybrid System Planning using a Mixed-Integer ADMM Heuristic and Hybrid Zonotopes

Authors: Joshua A. Robbins, Andrew F. Thompson, Jonah J. Glunt, Herschel C. Pangborn

Organizations: Department of Mechanical Engineering, The Pennsylvania State University, University Park, PA 16802 USA

Abstract

Embedded optimization-based planning for hybrid systems is challenging due to the use of mixed-integer programming, which is computationally intensive and often sensitive to the specific numerical formulation. To address that challenge, this article proposes a framework for motion planning of hybrid systems that pairs hybrid zonotopes - an advanced set representation - with a new alternating direction method of multipliers (ADMM) mixed-integer programming heuristic. A general treatment of piecewise affine (PWA) system reachability analysis using hybrid zonotopes is presented and extended to formulate optimal planning problems. Sets produced using the proposed identities have lower memory complexity and tighter convex relaxations than equivalent sets produced from preexisting techniques. The proposed ADMM heuristic makes efficient use of the hybrid zonotope structure. For planning problems formulated as hybrid zonotopes, the proposed heuristic achieves improved convergence rates as compared to state-of-the-art mixed-integer programming heuristics. The proposed methods for hybrid system planning on embedded hardware are experimentally applied in a combined behavior and motion planning scenario for autonomous driving.

Figures & tables

Panel of Figure 1 — Fig. 1: Hybrid zonotope reachability analysis is used to construct planning problems for PWA systems. Then an ADMM-based mixed integer programming heuristic efficiently finds feasible, and often nearly optimal, solutions.

method	$n_{Gc}$	$n_{Gb}$	$n_{C}$	$\nnz{G}$	$\nnz{A}$
PWA	$Nn_{Gc,\psi}+n_{G,0}$	$Nn_{Gb,\psi}$	$N(n_{C,\psi}+n_{x})$	$\mathrm{nnz}(G_{\psi,+})$	$N(2\mathrm{nnz}(G_{\psi,+})+\mathrm{nnz}(A_{\psi}))+n_{x}n_{G,0}$
MLD	$N(n_{G,u}+n_{Gc,w}+n_{e})$	$Nn_{Gb,W}$	$N(n_{C,w}+n_{e})$	$Nn_{x}n_{G,\mathrm{uw}}$	$N^{2}\left(\frac{n_{e}n_{G,\mathrm{uw}}}{2}\right)+N(n_{C,w}(n_{Gc,w}+n_{Gb,w})$
	$+n_{G,0}$			$+n_{x}n_{G,0}$	$+2n_{e}+n_{G,\mathrm{uw}}/2+n_{G,0})$

TABLE I: Memory complexity upper bounds for

N

-step reachable sets

\mathcal{X}_{N}

using MLD system reachability calculations and the proposed PWA system reachability calculations.

Panel of Figure 3 — Fig. 3: Convex relaxations for the 5-step reachable set $\mathcal{X}_{5}$ of the two-equilibrium system. Note that $\mathit{CR}(\mathcal{X}_{5})\neq\mathit{CH}(\mathcal{X}_{5})$ for the PWA – Sharp Union case because the generalized intersection in ( 26 ) does not preserve sharpness.

set	method	$n$	$n_{Gc}$	$n_{Gb}$	$n_{C}$	$\mathrm{nnz}(G)$	$\mathrm{nnz}(A)$
$\mathcal{X}_{15}$	MLD	2	182	15	150	2	692
$\mathcal{X}_{15}$	PWA cond.	2	92	30	75	12	442
$\mathcal{X}_{15}$	PWA sharp	2	122	30	105	12	502
$\mathcal{Z}_{15}$	PWA cond.	32	152	30	135	34	722
$\mathcal{Z}_{15}$	PWA sharp	32	182	30	165	34	782

TABLE II: Memory complexity of unconstrained reachable sets

\mathcal{X}_{15}

(Def. 2 ) and lifted, constrained reachable sets

\mathcal{Z}_{15}

(Def. 3 ).

parameter	$\rho$	$\epsilon_{p}$	$k_{\mathrm{restart}}$	$k_{ph1}$	$k_{ph2}$	$l_{\mathrm{buf}}$	$\epsilon_{\mathrm{buf}}$
value	10	0.001	5000	10000	90000	20	0.001

TABLE III: Default parameter values for ADMM-FP.

parameter	$\alpha_{0}$	$\phi$	$t$	$\delta_{\alpha}$	$l_{\mathrm{buf}}$
value	1	0.9	20	0.005	10

TABLE IV: Default parameter values for OFP [ 33 ] .

Panel of Figure 7 — Fig. 4: Comparison of solution methods for an MILP feasibility problem for which the feasible space is a random, non-empty hybrid zonotope. In these box and whisker plots, the box encloses the middle 50% of data points, and the whiskers enclose all other data points. The median is depicted as a black line.

Panel of Figure 8 — Fig. 6: Trajectories produced by ADMM-FP prior to convergence at the specified numerical tolerance $\epsilon_{p}=0.001$ . Colors indicate the primal residual norm $r_{p}$ of a given trajectory, with convergence corresponding to $r_{p}<\epsilon_{p}$ .

Panel of Figure 9 — Fig. 7: Times to find a feasible solution, peak memory usage, and percentage of cases where a feasible solution was found for 100 randomly generated motion planning problem. Whiskers in (a) and bands in (b) enclose all data points.

statistic	solve time (sec)	sub-optimality (%)
median	0.23	19.1
minimum	0.06	3.51
maximum	1.29	31.6

TABLE V: ADMM-FP solution statistics over 25 trials for a representative reach-avoid problem.

statistic	run time (sec)	iteration count
median	0.99	14,915
minimum	0.03	377
maximum	7.8	121,561

TABLE VI: ADMM-FP solution statistics over 50 trials with

\epsilon_{p}=0.01

for the ball and paddle system.

Panel of Figure 12 — Fig. 8: Example ball and paddle system solution with $\epsilon_{p}=0.01$ . The black bar is the ceiling and the red bar is the paddle. The opaque ball corresponds to the planned trajectory while the translucent ball corresponds to the open-loop simulation using the planned control inputs.

Panel of Figure 13 — Fig. 9: Velocity constraints for combined behavior and motion planning system.

Panel of Figure 14 — Fig. 11: Comparison of convex relaxation (C.R.) initialization and warm-start (W.S.) initialization for randomly generated combined behavior and motion planning scenarios. Warm-start times include the time to solve ( 46 ), and convex relaxation times include the time to solve the relaxation of ( 19 ). Whiskers enclose all data points.

Panel of Figure 15 — Fig. 12: Overhead images from the experimental demonstration of combined behavior and motion planning. Imperfect correction of the fisheye effect in the overhead camera results in some minor misalignment of the behavior and motion plan with the camera images.

	unit	median	min	max
ADMM-FP time	ms	5.2	3.4	103.0
ADMM-FP iterations	count	114	21	3888
Warm start time	ms	15.4	4.1	34.5
Eq. ( 25 ) and Eq. ( 24b ) time	ms	1.9	1.3	1.9
Alg. 2 time	ms	4.4	2.9	6.4

TABLE VII: Problem formulation and solution time statistics for combined behavior and motion planning experiment.

Motion Planning

Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.

See all 405 papers

May 5, 2026

Feasibility-aware Hybrid Control for Motion Planning under Signal Temporal Logics

In this work, a novel method for planar task and motion planning based on hybrid modeling is proposed. By virtue of a discrete variable which models local constraint satisfaction and enables local feasibility analysis, the proposed control architecture unifies planning with control design. Concurrently, control barrier functions are designed on a transformed disk version of the original nonconvex and geometrically complex robotic workspace, thus amending the issue of deadlocks. Simulations of the proposed method indicate effective handling of multiple overlapping spatio-temporal tasks even in the face of input saturation.

Panagiotis Rousseas, Dimos V. Dimarogonas

∗KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Division of Decision and Control Systems

Constrained Motion Planning Signal Temporal Logic STL Planning Feedback Control Robot Motion Planning Safe Motion Planning+2

Ask PDF

Mar 20, 2026

Multi-Agent Motion Planning on Industrial Magnetic Levitation Platforms: A Hybrid ADMM-HOCBF approach

This paper presents a novel hybrid motion planning method for holonomic multi-agent systems. The proposed decentralised model predictive control (MPC) framework tackles the intractability of classical centralised MPC for a growing number of agents while providing safety guarantees. This is achieved by combining a decentralised version of the alternating direction method of multipliers (ADMM) with a centralised high-order control barrier function (HOCBF) architecture. Simulation results show significant improvement in scalability over classical centralised MPC. We validate the efficacy and real-time capability of the proposed method by developing a highly efficient C++ implementation and deploying the resulting trajectories on a real industrial magnetic levitation platform.

Bavo Tistaert, Stan Servaes, Alejandro Gonzalez-Garcia +4

Decentralized Multi-Agent Motion Planning Motion Planning Safe Motion Planning Model Predictive Control

Ask PDF

Feb 24, 2026

Explainable Planning for Hybrid Systems

The recent advancement in artificial intelligence (AI) technologies facilitates a paradigm shift toward automation. Autonomous systems are fully or partially replacing manually crafted ones. At the core of these systems is automated planning. With the advent of powerful planners, automated planning is now applied to many complex and safety-critical domains, including smart energy grids, self-driving cars, warehouse automation, urban and air traffic control, search and rescue operations, surveillance, robotics, and healthcare. There is a growing need to generate explanations of AI-based systems, which is one of the major challenges the planning community faces today. The thesis presents a comprehensive study on explainable artificial intelligence planning (XAIP) for hybrid systems that capture a representation of real-world problems closely.

Mir Md Sajid Sarwar

School of Mathematical & Computational Sciences Indian Association for the Cultivation of Science Kolkata, India

Explainable Artificial Intelligence

Ask PDF

Abstract

Motion Planning

Explore similar work

Feasibility-aware Hybrid Control for Motion Planning under Signal Temporal Logics

Multi-Agent Motion Planning on Industrial Magnetic Levitation Platforms: A Hybrid ADMM-HOCBF approach

Explainable Planning for Hybrid Systems