# Efficient Backward Reachability Using the Minkowski Difference of Constrained Zonotopes

arXiv: https://arxiv.org/abs/2207.04272 · HTML: https://mlsanity.com/paper/2207.04272/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2022.

## Built on by (most cited first, 3 of 3)

- [Parameterized Hardness of Zonotope Containment and Neural Network Verification](https://mlsanity.com/paper/2509.22849/) (2025)
- [Statistical Reachability Analysis of Stochastic Cyber-Physical Systems under Distribution Shift](https://mlsanity.com/paper/2407.11609/) (2024)
- [Towards Safe Reinforcement Learning with Reduced Conservativeness: A Case Study on Drone Flight Control](https://mlsanity.com/paper/2608.26852/) (2026)

## Abstract (arXiv)

Backward reachability analysis is essential to synthesizing controllers that ensure the correctness of closed-loop systems. This paper is concerned with developing scalable algorithms that under-approximate the backward reachable sets, for discrete-time uncertain linear and nonlinear systems. Our algorithm sequentially linearizes the dynamics, and uses constrained zonotopes for set representation and computation. The main technical ingredient of our algorithm is an efficient way to under-approximate the Minkowski difference between a constrained zonotopic minuend and a zonotopic subtrahend, which consists of all possible values of the uncertainties and the linearization error. This Minkowski difference needs to be represented as a constrained zonotope to enable subsequent computation, but, as we show, it is impossible to find a polynomial-sized representation for it in polynomial time. Our algorithm finds a polynomial-sized under-approximation in polynomial time. We further analyze the conservatism of this under-approximation technique, and show that it is exact under some conditions. Based on the developed Minkowski difference technique, we detail two backward reachable set computation algorithms to control the linearization error and incorporate nonconvex state constraints. Several examples illustrate the effectiveness of our algorithms.