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

arXiv:2610.10883 · eess.SY, cs.SY · Submitted 2026-10-07 · Read on arXiv

Listen

Transcript

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

Rosa: Today's paper: "Moving Horizon Estimation of Hybrid Systems Using Hybrid Zonotopes and Mixed-Integer Quadratic Programs".

Dev: The gist Moving horizon estimation (MHE) for hybrid systems can be formulated as a mixed-integer program, which is computationally challenging,

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

Title and authors: Rosa: We’re moving on to the title and who wrote this paper, "Moving Horizon Estimation of Hybrid Systems Using Hybrid Zonotopes and Mixed-Integer Quadratic Programs."

Dev: It’s important to know who is behind this work, because it shows it comes from a team that understands both the continuous dynamics and the discrete constraints inherent in these hybrid systems.

Taro: I’m interested in seeing if the authors have experience tackling estimation problems that involve both continuous states and discrete modes in a practical setting.

Rosa: They do, because they are focused on autonomy research, and this paper directly addresses state estimation, which is a fundamental challenge when you have hybrid systems where both continuous states and discrete modes must be determined from noisy measurements.

Dev: The authors are using moving horizon estimation as the framework here to find states that require the minimum disturbances and noise to make measurements feasible with the modeled dynamics and initial condition.

Taro: So, what’s the big takeaway for us listening right now? Does this paper suggest a new way of thinking about how we approach state estimation in hybrid systems?

Rosa: It suggests a new way of formulating the problem by using hybrid zonotope representations to handle those mixed-integer sets efficiently.

Dev: They show that this representation can be used to efficiently construct the feasible space for the program using reachability-based calculations for piecewise affine systems, without needing to convert it into a mixed logical dynamical system.

Taro: So, when you hear it from us, what does that mean in plain terms? It means they found a way to manage the complexity of those mixed-integer constraints without having to build an entirely new kind of system description.

The paper's summary: Rosa: Now let’s look at the actual summary section of "Moving Horizon Estimation of Hybrid Systems Using Hybrid Zonotopes and Mixed-Integer Quadratic Programs."

Dev: The authors summarize that state estimation is a fundamental challenge in hybrid systems, where both continuous states and discrete modes must be determined from noisy measurements.

Taro: That’s the starting point, right? It sets the stage for why this problem is so hard before they introduce their solution.

Rosa: They then explain that moving horizon estimation yields an optimization problem over a past horizon to find the states that require minimum disturbances and noise to be feasible with the modeled dynamics and initial condition.

Dev: This optimization approach results in a mixed-integer program for the MHE, which they acknowledge is difficult both to formulate and solve online under computational limitations.

Taro: So, what’s their proposed solution at its heart? What are they actually proposing to fix this formulation problem?

Rosa: Their core proposal is using hybrid zonotope representations for mixed-integer sets to efficiently construct the feasible space for the program.

Dev: They detail how they formulate the MHE problem as an MIQP over a hybrid zonotope feasible set, which is done without requiring conversion to a mixed logical dynamical system description.

Taro: So, so they’re proposing that we use this geometric representation to define the constraints of the optimization problem in a way that bypasses the need for those complex logical descriptions.

The paper's improvements: Rosa: Let’s talk about what specific improvements the authors suggest in "Moving Horizon Estimation of Hybrid Systems Using Hybrid Zonotopes and Mixed-Integer Quadratic Programs."

Dev: One key improvement is the state space lifting technique they present to explicitly estimate the dynamic mode.

Taro: Can you explain that concept again? What exactly is this lifted state vector, and how does it help in tracking the mode trajectory?

Rosa: The lifted state is written as x-tilde equals x times lambda, where lambda is one when the system is in a certain mode and zero otherwise.

Dev: This lifting allows them to examine the mode trajectory by taking the union over each piece of the lifted dynamics, which constructs that overall graph of dynamics.

Taro: So this explicit estimation helps track what happens when the world misbehaves, like when we need to know exactly what mode we are in?

Rosa: Precisely; it lets them examine the mode trajectory associated with the optimal estimate by lifting the state dimension to include that indicator variable.

Conclusion: Dev: We’ve covered how they use hybrid zonotopes for formulation and how they handle complexity reduction for online use.

Rosa: To wrap up, the paper "Moving Horizon Estimation of Hybrid Systems Using Hybrid Zonotopes and Mixed-Integer Quadratic Programs" proposes a method to formulate and solve moving horizon estimation problems for hybrid systems.

Taro: The implication is that this approach is demonstrated on two numerical examples: a lane-changing vehicle example and a two-room thermal system with uncertain discrete modes.

Dev: For the two-room thermal system, the comparison against the existing mixed logical dynamical systems approach showed that their proposed PWA approach solved much faster due to its lower complexity and tighter convex relaxations.

Rosa: So, what does this mean for us in terms of practical application? It means we have a method that is demonstrated on two very different problems, showing it can handle both continuous and discrete states.

Dev: The final point is that they will explore additional methods for periodically reducing the set representation complexity between estimation iterations in their future work.

Taro: I just think figuring out better ways to manage those sets over time is definitely where the next research effort should focus, because that’s where you'd really see a practical system become more robust.

Jonah J. Glunt, Herschel C. Pangborn

The Pennsylvania State University

eess.SY, cs.SY

Submitted: 2026-10-07

Updated: 2026-10-07

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: The gist Moving horizon estimation (MHE) for hybrid systems can be formulated as a mixed-integer program, which is computationally challenging, and this paper shows how to efficiently construct the

Key concepts

Moving Horizon Estimation (MHE): MHE is an optimization technique used in state estimation for hybrid systems. It finds the best state estimate by minimizing the combined errors from dynamic disturbances and measurement noises, ensuring measurements are consistent with the system's known dynamics and initial conditions.
Hybrid Zonotope Formulation: This method uses hybrid zonotopes to mathematically define the set of all possible states that are consistent with a system's dynamics. This representation allows the complex MHE problem to be formulated as a Mixed-Integer Quadratic Program (MIQP) without needing to convert it into a mixed logical dynamical system.
State Space Lifting: To track which discrete mode the system is in, the state space is 'lifted' by adding an indicator variable. This allows the continuous state variables to be augmented with binary variables that explicitly represent the current discrete mode of the hybrid system.

Terminology

Hybrid System — 43× in this paper · explained in 2 episodes
Generator — 10× in this paper · explained in 2 episodes
Reachability Analysis — 3× in this paper · explained in 2 episodes
Benchmark — 2× in this paper · explained in 2 episodes
Papers — 2× in this paper · explained in 3 episodes
Core — 1× in this paper · explained in 2 episodes
Robustness — 1× in this paper · explained in 5 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

The gist Moving horizon estimation (MHE) for hybrid systems can be formulated as a mixed-integer program, which is computationally challenging, and this paper shows how to efficiently construct the feasible space using hybrid zonotope representations without requiring conversion to a mixed logical dynamical system.

Motivation

State estimation is a fundamental challenge in control of hybrid systems, where both continuous states and discrete modes must be determined from noisy measurements <ref:2610.10883#pg2>. Moving horizon estimation (MHE) is an optimization-based framework that yields a state estimate by minimizing the dynamic disturbances and measurement noises required for measurements to be feasible with the modeled dynamics and initial condition <ref:2610.10883#pg3>. Performing MHE on hybrid systems is computationally challenging, as it results in mixed-integer optimization programs that are NP-hard <ref:2610.10883#pg3>. Recent work has presented efficient methods for reachability of PWA systems as well as a heuristic for mixed-integer quadratic programs over hybrid zonotopes, which this paper applies toward MHE <ref:2610.10883#pg3>.

Hybrid Zonotope Formulation

The paper details how to formulate the MHE problem for PWA systems using hybrid zonotopes <ref:2610.10883#pg2>. The formulation of the MHE problem for PWA systems as an MIQP over a hybrid zonotope feasible set is detailed, without requiring conversion to an MLD system description <ref:2610.10883#pg2>. A set ZN is constructed such that any point z in ZN satisfies specific conditions related to the state trajectory and dynamics <ref:2610.10883#pg3>. The overall graph of the dynamics is constructed by taking the union over each piece of the PWA system's affine dynamics <ref:2610.10883#pg3>.

State Space Lifting for Mode Tracking

To examine the mode trajectory associated with the optimal estimate, the state dimension can be lifted to include an indicator variable for each mode <ref:2610.10883#pg4>. The lifted state is written as x˜ = (x,λ) in S × I where Pλi = 1 and λi = 1 when the system is in mode i <ref:2610.10883#pg5>. The overall graph of the dynamics is constructed by taking the union over each piece of the lifted dynamics <ref:2610.10883#pg5>.

Feasible Space Propagation and Complexity Reduction

The feasible sets are propagated from one MHE call to another, but since projecting the new X0 out of the old ZN retains full complexity, periodic complexity reduction is required <ref:2610.10883#pg6>. Typical methods for periodic complexity reduction include taking the interval hull (bounding box) of the initial state set or taking the convex relaxation of the hybrid zonotope representing X0 <ref:2610.10883#pg6>. Another option is to take the union of interval hulls corresponding to each dynamic mode, rather than an interval hull over all states and modes <ref:2610.10883#pg6>.

Numerical Examples

The proposed approach was evaluated in two numerical examples <ref:2610.10883#pg2>. In the lane-changing vehicle example, solving the mixed-integer MHE problem took a median solution time of 26.2ms, with a minimum of 10.3ms and a maximum of 29.1ms <ref:2610.10883#pg4>. For the two-room thermal system, comparison against the existing approach in the literature showed that the proposed PWA approach solved much faster due to its lower complexity and tighter convex relaxations.

Conclusion

This paper proposes a method to formulate and solve moving horizon estimation problems for hybrid systems <ref:2610.10883#pg2>. Hybrid zonotopes are used to represent the feasible space and encode the set of states consistent with the dynamics and measurements <ref:2610.10883#pg2>. The approach is demonstrated on two numerical examples, a vehicle changing driving lanes and a two-room thermal system with uncertain discrete modes <ref:2610.10883#pg2>. For the two-room thermal system, solution times are compared for the proposed approach and the MLD approach standard in the literature, and the proposed approach was found to solve much faster due to its lower complexity and tighter convex relaxations. Future work will explore additional methods for periodically reducing the set representation complexity between estimation iterations.

--- Page 1 ---

Conclusion

--- Page 2 ---

Motivation

State estimation is a fundamental challenge in control of hybrid systems, where both continuous states and discrete modes must be determined from noisy measurements <ref:2610.10883#pg3>. Moving horizon estimation (MHE) is an optimization-based framework that yields a state estimate by minimizing the dynamic disturbances and measurement noises required for measurements to be feasible with the modeled dynamics and initial condition <ref:2610.10883#pg3>. Performing MHE on hybrid systems is computationally challenging, as it results in mixed-integer optimization programs that are NP-hard <ref:2610.10883#pg3>. Recent work has presented efficient methods for reachability of PWA systems as well as a heuristic for mixed-integer quadratic programs over hybrid zonotopes, which this paper applies toward MHE <ref:2610.10883#pg3>.

Hybrid Zonotope Formulation

Improvements for AI systems

Bold header: Hybrid System State Estimation via Hybrid Zonotopes

This method allows for the formulation of an MHE problem for PWA systems as an MIQP over a hybrid zonotope feasible set, which enables state estimation for systems with both continuous and discrete states by efficiently constructing the feasible space without requiring conversion to a mixed logical dynamical system.

Bold header: Explicit Dynamic Mode Estimation

The proposed approach includes state-space lifting with mode indicator variables to explicitly estimate the dynamic mode, yielding a lifted state x˜ = (x,λ) ∈ S × I, which allows the estimation of the discrete dynamic mode at each time step.

Bold header: Faster Online MHE Solving

The method is shown to be solved orders of magnitude faster for one of the example problems compared to the standard mixed logical dynamical systems approach, improving computational feasibility for real-time applications.

Bold header: Robust Set Propagation

The construction of the feasible space involves recurring equations like Zk+1 = Zk × W × X¯k+1 ∩R2,k Ψ′k, which ensures that the estimation process accurately reflects all consistent state trajectories and mode sequences over the horizon.

Bold header: Complexity Management for Online Use

Periodic complexity reduction is achievable by taking the interval hull, also called bounding box, of the initial state set (and modes, if in the lifted form), which helps keep complexities tolerable for solving online, a necessity for practical deployment.

Sources

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