ZAPP! Zonotope Agreement of Prediction and Planning for Continuous-Time Collision Avoidance with Discrete-Time Dynamics

Luca Paparusso, Shreyas Kousik, Edward Schmerling, Francesco Braghin, Marco Pavone

Predicting the movement of dynamic agents and planning safe trajectories around them are two of the most challenging tasks in autonomous robotics. Traditionally, these systems operate independently, often leading to a "representation mismatch" that compromises safety. ZAPP (Zonotope Agreement of Prediction and Planning) is a novel framework designed to bridge this gap, ensuring robots remain safe throughout continuous time rather than just at discrete intervals.

The Representation Mismatch Problem

In modern robotics, a fundamental friction exists between prediction and planning:

  1. Predictors typically operate on coarse time steps (e.g., 0.5s intervals) and use unbounded distributions (like Gaussians) to manage uncertainty.
  2. Planners require fine-grained time steps to maintain dynamic accuracy and bounded uncertainty to provide formal safety guarantees.

This discrepancy often leads to "tunneling," where a robot plans a path that is safe at discrete time steps but results in a collision in the intervals between them. Furthermore, integrating high-performance neural network predictors into gradient-based optimization loops is mathematically difficult.

The ZAPP Framework

ZAPP resolves these issues through three core pillars:

  • Zonotope Reachable Sets: Instead of points or Gaussians, ZAPP represents agent occupancy as a zonotope—a computationally efficient, symmetric polytope.
  • Continuous-Time Extension: The framework geometrically "stretches" these zonotopes into tubes that cover the entire interval between predicted time steps, eliminating the risk of tunneling.
  • Differentiable Collision Constraints: ZAPP converts zonotope collision checks into differentiable linear inequalities (H-representations). This allows planners to use standard gradient-based solvers (like IPOPT) to optimize trajectories in real-time.
Conceptual diagram of the ZAPP framework showing the geometric agreement between predicted zonotopes and the planned trajectory.

Experimental Evaluation

To test ZAPP in highly interactive environments, the authors developed a new simulation framework featuring an Interactive Hallway Task. A robot must navigate through a hallway filled with 10 non-ego agents governed by nonlinear social forces. This creates complex, reactive scenarios that are significantly more difficult to navigate than standard traffic datasets.

Key Results

The researchers compared ZAPP against MATS, a state-of-the-art baseline using discrete-time collision avoidance. The results demonstrate that ZAPP provides a massive safety boost without sacrificing performance.

Performance comparison table showing ZAPP's superior success rate (G/C) and robustness compared to baselines.
  • Safety: ZAPP achieved a 96.7% success rate, reducing the crash rate by a factor of 10 compared to the MATS baseline (70%).
  • Robustness: When subjected to model error (different physics in training vs. simulation), ZAPP maintained an 86.7% success rate, while the baseline plummeted to 53.3%.
  • Efficiency: Despite the increased safety constraints, ZAPP maintained an average speed (3.80 m/s) nearly identical to the riskier baselines.

Conclusion and Future Work

ZAPP demonstrates that bridging the gap between prediction and planning using zonotopes significantly enhances robot safety in interactive environments. While current solver times are approximately one order of magnitude slower than real-time in Python, future implementations in C++ or CUDA are expected to reach real-time performance. Future research will also focus on formal reachability analysis and real-world hardware trials to account for sensor noise and latency.

Summary updated

Abstract

The past few years have seen immense progress on two fronts that are critical to safe, widespread mobile robot deployment: predicting uncertain motion of multiple agents, and planning robot motion under uncertainty. However, the numerical methods required on each front have resulted in a mismatch of representation for prediction and planning. In prediction, numerical tractability is usually achieved by coarsely discretizing time, and by representing multimodal multi-agent interactions as distributions with infinite support. On the other hand, safe planning typically requires very fine time discretization, paired with distributions with compact support, to reduce conservativeness and ensure numerical tractability. The result is, when existing predictors are coupled with planning and control, one may often find unsafe motion plans. This paper proposes ZAPP (Zonotope Agreement of Prediction and Planning) to resolve the representation mismatch. ZAPP unites a prediction-friendly coarse time discretization and a planning-friendly zonotope uncertainty representation; the method also enables differentiating through a zonotope collision check, allowing one to integrate prediction and planning within a gradient-based optimization framework. Numerical examples show how ZAPP can produce safer trajectories compared to baselines in interactive scenes.
BibTeX
@inproceedings{paparusso2024zapp,
  author = {Luca Paparusso and Shreyas Kousik and Edward Schmerling and Francesco Braghin and Marco Pavone},
  title = {{ZAPP! Zonotope Agreement of Prediction and Planning for Continuous-Time Collision Avoidance with Discrete-Time Dynamics}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2024},
  url = {https://openreview.net/forum?id=nQgbRn7Tq5},
}
Figure