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

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.