Introduction
The verification of safety-critical systems in fields such as aerospace, robotics, and chemical engineering requires mathematical certainty that a system will never enter an unsafe state. This is achieved through reachability analysis, which calculates the set of all possible states a system can reach over time from a range of initial conditions. For nonlinear systems, where dynamics do not follow straight lines, computing these sets accurately is a significant challenge. Errors often accumulate, leading to the "wrapping effect," where the calculated enclosure becomes overly conservative and potentially useless for verification.
The ARCH-COMP21 report summarizes a "friendly competition" between five state-of-the-art tools designed to verify these complex nonlinear and hybrid systems. By testing these tools against a suite of rigorous benchmarks, the report provides a transparent snapshot of the current trade-offs between computational speed, numerical rigor, and the ability to handle systems that switch between different behaviors.
Verification Methodology and Tools
The competition evaluated five tools, each bringing a different mathematical philosophy to the problem:
- Ariadne (C++): Employs "Computable Analysis" to provide high-rigor numerical results with strict rounding control.
- CORA (MATLAB): Uses "conservative linearization" and zonotopes to achieve high scalability for large systems.
- DynIbex (C++): Combines interval constraint satisfaction with guaranteed Runge-Kutta integration to produce sound results accounting for floating-point errors.
- JuliaReach (Julia): A high-performance suite using Taylor models and interval arithmetic, known for its speed and flexibility.
- Kaa (Python): A newcomer using "parallelotope bundles" and PCA-based strategies to approximate reachable sets.
Benchmark Problems
The tools were evaluated using five challenging benchmark problems:
- ROBE21 (Robertson System): A benchmark focusing on "stiffness," where some variables change much faster than others, often causing standard simulators to fail.
- CVDP20 (Coupled Van der Pol): A 4-variable oscillatory system with a stable limit cycle.
- LALO20 (Laub-Loomis): A 7-variable model of enzymatic activities used to test performance in higher-dimensional state spaces.
- LOVO21 (Lotka-Volterra): A hybrid predator-prey model featuring "tangential crossings," where trajectories barely graze mode boundaries.
- SPRE21 (Space Rendezvous): A complex hybrid model of a spacecraft approaching a station, involving switched controllers and nondeterministic transitions.
Comparative Analysis of Tool Performance
The results confirm that there is no "one tool to rule them all"; tool selection depends heavily on the specific problem requirements. For instance, in the Coupled Van der Pol benchmark, JuliaReach was the fastest, completing the task in 1.5 seconds, followed by CORA at 7.7 seconds. However, for high-stakes applications requiring extreme numerical rigor, Ariadne often provides the necessary precision, as seen in its tight enclosure for the hybrid LOVO21 benchmark.
The "wrapping effect" remains a primary hurdle in nonlinear reachability. As illustrated in Figure 3, different tools produce enclosures of varying sizes and shapes for the same problem. In the Lotka-Volterra benchmark, the area of the final enclosure varied wildly between tools—from $1.2 \times 10^{-4}$ to $4.7 \times 10^{-1}$—demonstrating how quickly approximation errors can bloom.
Furthermore, the introduction of the Robertson benchmark (ROBE21) highlighted that stiffness is a major frontier. While tools like JuliaReach maintained high precision, they required significantly more computation time, while others saw their error bounds fluctuate unexpectedly.
Conclusion
ARCH-COMP21 demonstrates significant progress in the verification of nonlinear systems while identifying clear paths for future research. Key priorities include better support for "crossings" in hybrid systems and more consistent benchmarking constraints. The competition itself has served as a catalyst for tool improvement, leading to updates such as parallelization in Ariadne and more sophisticated template-generation techniques in Kaa. As autonomous systems become more prevalent, the continued evolution of these verification tools is critical for ensuring their safety and reliability.
Summary updated