Moving Horizon Estimation of Hybrid Systems Using Hybrid Zonotopes and Mixed-Integer Quadratic Programs

A. Motivation

• Hybrid-system MHE is a mixed-integer optimization problem that is computationally challenging because it must estimate continuous states and discrete modes from noisy measurements.The introduction notes that such programs are NP-hard.Source: A. Motivation · p. 1

B. Literature Review

• Earlier hybrid-system MHE formulations use MLD descriptions,, while hybrid zonotopes had been used for nonlinear-system estimation but not exact hybrid-dynamics representation,.The paper motivates zonotopes by their closure under reachability and estimation operations and by solvers that exploit their structure,.Source: B. Literature Review · p. 1

C. Contributions

• The paper formulates PWA-system MHE as an MIQP over a hybrid-zonotope feasible set, without requiring conversion to an MLD description.It also describes state-space lifting to recover mode sequences and periodic over-approximation to reduce feasible-set complexity.Source: C. Contributions · pp. 1–2
• The paper reports that its method solves orders of magnitude faster than the standard MLD approach on an example problem.The comparison is for the two-room thermal-system example.Source: C. Contributions · p. 2

D. Outline

• The paper proceeds from notation and preliminaries to the proposed MIQP formulation, two numerical examples, and a conclusion.The general notation uses lowercase scalars, bold lowercase vectors, uppercase matrices, and calligraphic sets; a function graph is introduced as a set of input-output pairs.Source: D. Outline · p. 2, A. Notation and General Definitions · p. 2

B. Piecewise Affine Hybrid System Model

• The PWA model has a mode-dependent state update selected by constraints on the state and input, while its output model does not vary by mode.Process and measurement noises are bounded, additive, and mode-independent; the state and input lie in bounded sets.Source: B. Piecewise Affine Hybrid System Model · p. 2

C. Moving Horizon Estimation

• MHE optimizes a state trajectory over a sliding window of recent measurements, minimizing the disturbances and measurement noises needed for consistency with the model.At each call, the oldest state is constrained by an initial set that can come from the previous estimate or a startup bound.Source: C. Moving Horizon Estimation · p. 2
• The arrival-cost and noise-weighting matrices balance uncertainty in the prior estimate against disturbances and measurement noise over the current horizon.The prior reference is typically taken from the previous MHE estimate, and the arrival-cost matrix can be selected for guaranteed convergence or stability.Source: C. Moving Horizon Estimation · p. 2
• Substituting the PWA dynamics and output equation eliminates outputs and measurement noise as decision variables, leaving an optimization in states and process noise.The cost function designed for the noise is retained.Source: C. Moving Horizon Estimation · p. 2

Zonotopes

• Zonotopes can represent any centrally symmetric convex polytope.The supplied definition introduces a generator matrix and center.Source: D. Zonotopic Set Representations · p. 3

Constrained Zonotopes

• Constrained zonotopes add equality constraints to the generator representation and can represent any convex polytope.Their elements have the form Gξ + c with Aξ = b and ξ bounded in [−1, 1].Source: D. Zonotopic Set Representations · p. 3

Hybrid Zonotopes

• Hybrid zonotopes add continuous and binary factors and can represent any finite union of bounded convex polytopes.Their complexity is counted by continuous generators, binary generators, and equality constraints.Source: D. Zonotopic Set Representations · p. 3
• Hybrid zonotopes are closed under affine maps, Cartesian products, Minkowski sums, and generalized intersections.These closed-form operations motivate their use for set-based reachability and estimation.Source: D. Zonotopic Set Representations · p. 3

III. HYBRID ZONOTOPE FORMULATION OF MHE FOR PWA SYSTEMS

• The section constructs the PWA MHE formulation from dynamics graphs, then uses horizon dynamics, measurements, and inputs to build the feasible space.It also presents lifting to estimate each time step's discrete mode and discusses propagation and periodic complexity reduction.Source: §III · p. 3
• The section's construction starts from the PWA system graph and proceeds to feasible-space construction using time-varying dynamics, received measurements, and applied inputs.This is the stated scope of the formulation before its mode-lifting and propagation topics.Source: §III · p. 3

A. Graph of Dynamics Function

• For each affine piece, the method constructs a graph over that piece's domain before forming the system-wide graph.The passage introduces the per-piece graph construction, while the next step combines those graphs by union.Source: A. Graph of Dynamics Function · p. 3
• State disturbances are omitted from the dynamics graph because they are assumed mode-independent and handled separately.Source: A. Graph of Dynamics Function · p. 3
• Hybrid zonotopes exactly represent a PWA dynamics graph by representing each affine piece and taking the union over pieces.The graph of the full system is assembled from the graph of each piece over its domain.Source: A. Graph of Dynamics Function · p. 3
• The union across affine pieces can use an identity from to preserve convex-relaxation sharpness or an identity from to reduce complexity.Source: A. Graph of Dynamics Function · p. 3

B. Constructing Hybrid Zonotope Feasible Space

• Each point in the horizon feasible-space set represents the state and disturbance sequence together with the terminal state.The tuple is (x0, w0, . . . , xN−1, wN−1, xN).Source: B. Constructing Hybrid Zonotope… · p. 3
• Construction starts from the earliest-step state set, taken from the previous MHE iteration, and the dynamics graphs for each horizon step.For time-invariant dynamics, the graph can be the same at every step.Source: B. Constructing Hybrid Zonotope… · p. 3
• At each step, the recursion combines the prior iterate with disturbances and measurement-consistent states, then intersects them with the dynamics graph enforcing the applied input.The measurement-consistent state set is denoted X̄k+1.Source: B. Constructing Hybrid Zonotope… · p. 4

C. Lifting State Dimension for Mode Tracking

• The lifted state augments the continuous state with a binary indicator for each mode, constrained so exactly one mode is selected.This permits examination of the mode trajectory for an optimal estimate or feasible modes for feasible state sets.Source: C. Lifting State Dimension for Mode… · p. 4
• For each mode, the lifted dynamics graph pairs that mode’s dynamics with its identity-vector indicator, and the overall graph is their union.The lifted feasible-space construction is correspondingly modified.Source: C. Lifting State Dimension for Mode… · p. 4
• When the initial mode is uncertain, continuous [0, 1] intervals can replace discrete mode indicators because the lifted dynamics graph exactly represents switching logic.Source: C. Lifting State Dimension for Mode… · p. 4
• Without the lifted form, the mode-related terms are dropped from the complexity expression.Source: C. Lifting State Dimension for Mode… · p. 4

D. Moving Horizon Propagation and Periodic Complexity Reduction

• Projecting the next initial-state set from the previous feasible set preserves its full complexity, so feasible-space complexity grows with each MHE call.The paper therefore requires periodic complexity reduction to keep online solution complexity tolerable.Source: D. Moving Horizon Propagation and… · p. 4
• The interval hull gives the lowest-complexity reduction, but in the lifted case it removes all coupling between state and mode estimates.It can be computed with 2nx support-function mixed-integer linear programs, or 2(nx + nm) in the lifted form.Source: D. Moving Horizon Propagation and… · p. 4
• Taking a union of mode-specific interval hulls preserves some state–mode coupling, at the cost of greater complexity than a single bounding box.Another option is convex relaxation to a constrained zonotope followed by simplification.Source: D. Moving Horizon Propagation and… · pp. 4–5

IV. NUMERICAL EXAMPLES

• The numerical examples implement the proposed methods in Python, with resulting MIQPs solved using the ADMM-based heuristic in.Source: §IV · p. 5
• Timing data came from an Ubuntu 24.04 desktop with an Intel Core Ultra 7 265 × 20 processor and 32 GB of RAM.Source: §IV · p. 5
• The reported examples evaluate the methods developed in the preceding section.Source: §IV · p. 5

• The example applies a double-integrator vehicle model in road-aligned Frenet coordinates with affine dynamics for right- and left-lane tracking.Source: A. Lane-changing Vehicle · p. 5
• Lateral control uses feedback terms kd=0.213 1/s2 and k ˙d=0.652 1/s, plus a feedforward term and a small perturbation.Source: A. Lane-changing Vehicle · p. 5
• Lane centerline positions distinguish the tracking modes; additional mode-dependent constraints and system interpretation are given in.Source: A. Lane-changing Vehicle · p. 5
• With N=15, the estimator measures the first two position states and uses bounded state-disturbance and measurement-noise sets.Source: A. Lane-changing Vehicle · p. 5
• 100 trials yielded a median solution time of 26.2 ms, with a 10.3 ms minimum and 29.1 ms maximum.Source: A. Lane-changing Vehicle · p. 5
• Toward the horizon's end, earlier-step mode uncertainty makes the feasible set split into disjoint polytopes represented by one hybrid zonotope.Source: A. Lane-changing Vehicle · p. 5

B. Two-room Thermal System

• The system has two room-temperature states and two binary heating vents, yielding four possible modes at each time step.The heater supply temperature, specific heat, and flow rate are assumed constant; the model is discretized with zero-order hold and a five-minute time step.Source: B. Two-room Thermal System · pp. 5–6
• The full simulation used C = I2, horizon N = 30, disturbance bounds W = [−0.15, 0.15]2, and noise bounds V = [−0.1, 0.1]2, with feasible-set complexity reduced by bounding boxes every 10 steps.Figures 2 and 3 show temperature estimates and feasible modes, respectively.Source: B. Two-room Thermal System · p. 6, Figure 2 · p. 6, Figure 3 · p. 6
• With both rooms measured, feasible-state intervals stayed tight around the true states; with periodic second-room measurements, they widened between samples and shrank when measured.The three cases compare measuring only room one, both rooms, or periodically measuring room two as well.Source: B. Two-room Thermal System · p. 6, Figure 4 · p. 7
• The PWA graph had hybrid zonotope complexity (16, 4, 9), versus (42, 4, 33) for MLD, due to MLD auxiliary variables and halfspace constraints.The section reports that PWA solved significantly faster across 100 trials at varying horizon lengths, with no warm-starting or arrival costs.Source: B. Two-room Thermal System · p. 7
• 298.0ms for PWA versus 12619ms for MLD were the maximum solve times during a 30-step simulation with horizon N = 10.The maxima occurred at k = 27 for PWA and k = 29 for MLD; after 30 steps, the problem complexities were (6630, 1020, 4845) and (13260, 1020, 10965), respectively.Source: B. Two-room Thermal System · p. 7

V. CONCLUSION

• For the two-room thermal system, the proposed approach solved much faster than the standard MLD approach.The reported advantage is attributed to lower complexity and tighter convex relaxations.Source: §V · pp. 7–8
• Hybrid zonotopes represent the feasible space of states consistent with the dynamics and measurements in the proposed hybrid-system MHE.Source: §V · p. 7
• The approach is demonstrated on a lane-changing vehicle and a two-room thermal system with uncertain discrete modes.Source: §V · p. 7
• Fig. 5 compares PWA and MLD solution times in one N = 10 simulation with propagated estimates and no complexity reduction.Source: Figure 5 · p. 8
• Future work will explore periodically reducing set-representation complexity between estimation iterations.Source: §V · p. 8