Certified Zonotopic Reachability Analysis for Trajectory Tracking on Lie Groups

Yanliang Huang, Peng Xie, Zhen Zhang, Zhuoqi Zeng, Amr AlanwararXiv 2026 · arXiv

TL;DR

Researchers have developed a new method for certifying the safety of autonomous vehicles by using zonotopes to track errors on matrix Lie groups. By performing reachability analysis in Lie algebra coordinates, the algorithm produces significantly tighter "safety tubes" than traditional ellipsoid methods, remaining valid even under large disturbances where previous techniques fail.

What Problem Does This Paper Address?

When an autonomous drone or aircraft follows a planned path, unknown disturbances (like wind) cause it to deviate. To guarantee safety, engineers calculate a "tube" around the path—a volume that is guaranteed to contain the vehicle despite these disturbances. If this tube doesn't hit any obstacles, the flight is certified as safe.

The challenge lies in the math: aerial vehicle rotations and positions are best described using matrix Lie groups (like $SO(3)$ for rotation). In standard coordinates like Euler angles, the physics equations are highly nonlinear, which makes calculating tight safety tubes extremely difficult. Existing methods often use "invariant ellipsoids," which are easy to compute but very conservative (the tubes are much larger than they need to be), or interval methods that suffer from the "wrapping effect," where the error bounds grow uncontrollably over time.

Methods

The authors propose a zonotope-based reachability algorithm that operates in Lie algebra coordinates.

  1. Linearization in Lie Algebra: For a specific class of "group-affine" systems (which includes basic rigid-body kinematics), the error dynamics become linear when expressed in Lie algebra coordinates.
  2. Zonotopic Propagation: The algorithm uses zonotopes—a computationally efficient way to represent sets—to propagate the linear part of the error. Zonotopes are particularly good at handling linear maps and Minkowski sums without the excessive growth seen in box-based methods.
  3. Jacobian Splitting: The disturbance enters the system through a nonlinear matrix called the inverse right Jacobian. The authors split this into three parts: a constant input, a bilinear term (linear in error for each disturbance component), and a higher-order remainder. They derived new, closed-form bounds for this remainder to keep the tube as tight as possible.
  4. Hybrid Coordinates: For vehicles like standard quadrotors that can't control all directions at once (unmatched systems), the authors introduced "hybrid coordinates." These coordinates allow a feedback controller to cancel out nonlinearities that would otherwise cause the safety tube to explode in size.
Figure 1: The tracking error on the Lie group and in Lie algebra coordinates. In the left panel, the vehicle 𝑋(𝑡) follows the reference ¯𝑋(𝑡), and the tube contains every tracking error that the disturbances can cause. A tube that avoids the obstacle certifies the reference. The inset shows a zonotope mapped onto 𝑆𝑂(3) by the exponential map, whose edges become curved, so we propagate the zonotopes in Lie algebra coordinates. The right panel shows zonotopes in Lie algebra or hybrid coordinates, which contain the tracking error at the time steps, and the tube, whose time-interval sets contain it between the time steps. The dashed curves are a trajectory of the vehicle and its tracking error. The enlarged zonotope consists of its center 𝑐and its generators, and each step adds generators for the disturbance. The bounds on the attitude error and the position error are read from these sets.

Datasets

The method was evaluated on several benchmarks:

  • Planar Aircraft: A kinematic model on $SE(2)$ used to compare against ellipsoid methods.
  • Attitude Benchmark: A standard $SO(3)$ test case for comparing against interval-based methods.
  • Multirotor Simulation: A fully actuated multirotor on $SE_q(3)$ to test hybrid coordinates under strong disturbances.
  • Real-World Flight Data: Data collected from a Crazyflie 2.1 nano-quadrotor tracked by a motion capture system to verify the tube's validity in physical flight.

Key Insights and Ideas

  • Exploiting Geometry: By moving the analysis from the Lie group to its Lie algebra, the authors transformed a complex nonlinear reachability problem into a much simpler linear one (plus a small, bounded remainder).
  • Tighter Remainder Bounds: Instead of using generic bounds (like the Hessian of the dynamics), the authors derived specific bounds for the Lie group's exponential map remainder. This "tailor-made" math is what allows the tubes to stay so close to the actual reachable set.
  • Solving the "Unmatched" Problem: The introduction of hybrid coordinates is a clever "middle ground." It keeps the benefits of Lie algebra for rotations while using body-frame coordinates for translation, ensuring the controller can effectively cancel out the most problematic nonlinear terms.
Figure 2: One step of Algorithm 1, with illustrative sets. The lower row is the solution (18) of the closed-loop error equa- tion over the step. The linear part maps the zonotope to another zonotope without over-approximation, the input adds a zonotope with one generator per disturbance compo- nent, and a box encloses the remaining terms. The sum of the three sets contains the tracking error at the end of the step.

Key Results

  • Superior Tightness: In multirotor simulations, the zonotopic tubes were 84% smaller in attitude error and 55% smaller in position error compared to the best ellipsoid methods.
  • Robustness to Noise: Under "strong" disturbances, the ellipsoid method often failed to find any valid safety bound (infeasible), whereas the zonotopic tubes remained valid and tight.
  • Real-World Validation: In actual quadrotor flights, the calculated tube successfully contained 100% of the measured tracking errors across multiple flights. The zonotope bounds were 25% to 41% tighter than those produced by ellipsoids.
  • Efficiency: The "fixed step" version of the algorithm is 10 to 24 times faster than the "refined step" version while only losing a small amount of accuracy, making it promising for real-time applications.

Limitations and Future Work

  • Group-Affine Assumption: The core mathematical advantage relies on the system being "group-affine." While this covers rigid-body kinematics, more complex aerodynamic models might require further approximations.
  • Controller Dependency: The method assumes a dynamic inversion controller is used to cancel out matched nonlinearities. Safety guarantees for other types of controllers (like standard PID or MPC) would need additional work.
  • Future Directions: The authors suggest integrating this reachability analysis directly into online motion planners, allowing drones to safely navigate tight spaces by calculating these tubes on the fly.

Summary updated

Abstract

Autonomous vehicles track planned trajectories close to obstacles. Unknown disturbances make them deviate from these trajectories. With a bound on the tracking error that disturbances can cause, a planned trajectory can be certified as safe before execution. Existing set-based methods bound the tracking error by one invariant ellipsoid for the whole trajectory or by intervals, which are both conservative. For aerial and space vehicles, the tracking error evolves on a matrix Lie group with nonlinear dynamics. However, for group-affine systems, the error dynamics are linear in Lie algebra coordinates when the vehicle receives the inputs of the reference. The control input and the disturbance enter through the inverse right Jacobian, a matrix that depends on the error. We propagate the linear part of the error dynamics with zonotopes and enclose the effect of the inverse right Jacobian on the disturbance in closed form. The resulting tubes are tight and provably contain all reachable tracking errors in continuous time. When some error components have no input, the inverse right Jacobian leaves unmatched nonlinear terms in the closed loop. None of the tested methods certifies such a closed loop. Hybrid coordinates make these terms matched, so that our controller cancels every nonlinear term that does not contain the disturbance. Our tubes give tighter bounds than the ellipsoid method in simulations of a planar aircraft and a fully actuated multirotor and in real flights of a quadrotor, where the tube contains every measured attitude error. Under larger disturbances and the same feedback gain, the ellipsoid method yields no valid ellipsoid, whereas our tubes remain valid.
BibTeX
@misc{huang2026certified,
  author = {Yanliang Huang and Peng Xie and Zhen Zhang and Zhuoqi Zeng and Amr Alanwar},
  title = {{Certified Zonotopic Reachability Analysis for Trajectory Tracking on Lie Groups}},
  year = {2026},
  eprint = {2611.12767},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.12767},
}
Figure