Leveraging Compositional Methods for Modeling and Verification of an Autonomous Taxi System

Alessandro Pinto, Anthony Corso, Edward Schmerling

TL;DR

This paper explores how to use "contract-based" formal modeling to verify the safety of an autonomous aircraft taxi system. By breaking a complex system into smaller, verifiable components, the authors demonstrate a path toward rigorous assurance for autonomy while identifying six critical research gaps—ranging from probabilistic reasoning to model libraries—that currently hinder the widespread adoption of formal methods.

What Problem Does This Paper Address?

Ensuring the safety of autonomous systems (like self-driving cars or pilotless aircraft) is notoriously difficult. Traditional testing is insufficient; it’s estimated that a self-driving car would need to be tested for billions of miles to prove it is as safe as a human driver.

Formal methods—mathematical techniques to prove a system meets its requirements—offer a solution, but they struggle with the "tantamount complexity" of modern autonomous stacks. These systems involve diverse technologies (sensors, AI, control loops) and complex supply chains. The authors address the challenge of how to model and verify these systems in a "compositional" way—meaning you can verify individual parts and trust that the whole system works when they are plugged together.

Methods

The authors apply a Contract-Based Design framework to a case study of an aircraft taxiing from a gate to a runway.

  1. Compositional Modeling: The system is decomposed into a hierarchy: Route Generation $\rightarrow$ Trajectory Generation $\rightarrow$ Trajectory Following. Each component is governed by a "contract" consisting of Assumptions (what the component expects from its environment) and Guarantees (what the component promises to do).
  2. Heterogeneous Views: To manage complexity, they split the model into two views:
  3. Protocol View: Uses Linear Temporal Logic (LTL) to model the timing and sequence of events (e.g., "don't send a new command until the last one is done").
  4. Functional View: Uses Many-Sorted First Order Logic (MS-FOL) to model data properties (e.g., "the aircraft must stay within $\delta$ distance of the centerline").
  5. Refinement Verification: They use automated tools like OCRA (for temporal logic) and SMT solvers like Z3/CVC5 (for functional logic) to mathematically prove that if the sub-components meet their contracts, the overall system requirements are satisfied.
  6. Inductive Reasoning: For tasks that repeat (like stopping at multiple "hold-short" lines), they use inductive proofs to show that if a contract holds for $n$ segments, it holds for $n+1$.

Datasets

As this is a theoretical and modeling paper focused on formal verification, it does not use a traditional training dataset. Instead, it defines a formal airport taxi scenario as a benchmark, including roadmap graphs, motion primitives, and sensor error bounds. The authors provide a link to their formal models on GitHub for the community to use.

Key Insights and Ideas

  • The "Viewpoint" Challenge: One of the biggest hurdles isn't verifying one part of the system, but combining different "views" (like timing vs. data accuracy). There is currently no standard way to formally merge these heterogeneous models.
  • The Productivity Gap: Writing formal requirements is slow and requires experts. The authors argue for the creation of libraries of formal models for common autonomous concepts (like "paths," "graphs," and "trajectories") to speed up the process.
  • Explainability of Verification: When a formal tool finds a bug (an "unsat" result), the output is often a cryptic mathematical trace. We need better ways to translate these results back into "plain English" so engineers can fix the requirements.
  • Probabilistic Contracts: Most formal methods are binary (True/False). However, AI components (like object detectors) are probabilistic. The paper highlights the need for a framework that can handle "contracts that are satisfied only probabilistically."

Key Results

  • Successful Decomposition: The authors successfully modeled a multi-layer autonomous taxi architecture and proved that the top-level safety requirements (staying on the centerline, stopping at signs) could be refined down to individual component specs.
  • Tool Integration: They demonstrated that existing solvers (Z3, CVC5, OCRA) are powerful enough to handle these models if the abstractions are chosen correctly.
  • Research Roadmap: The paper's primary "result" is a clear taxonomy of six research needs:
  • Semantics for combining different viewpoints.
  • Formal model libraries.
  • Methods to lift solver results to the specification level.
  • Probabilistic contract frameworks.
  • Standard functional architectures for autonomy.
  • A theory of higher-order contracts.

Limitations and Future Work

The current model is "nominal," meaning it assumes the environment behaves predictably (e.g., no unexpected obstacles on the taxiway). The authors acknowledge that "relaxing requirements" to handle unforeseen scenarios would require radical changes to the system architecture.

Future work involves developing "Higher-Order Contracts"—contracts that are parameterized by other contracts—to handle the dynamic mission horizons common in autonomous operations. They also emphasize the need for "standard robust architectures" that don't require a total redesign every time a small requirement changes.

Summary updated

Abstract

We apply a compositional formal modeling and verification method to an autonomous aircraft taxi system. We provide insights into the modeling approach and we identify several research areas where further development is needed. Specifically, we identify the following needs: (1) semantics of composition of viewpoints expressed in different specification languages, and tools to reason about heterogeneous declarative models; (2) libraries of formal models for autonomous systems to speed up modeling and enable efficient reasoning; (3) methods to lift verification results generated by automated reasoning tools to the specification level; (4) probabilistic contract frameworks to reason about imperfect implementations; (5) standard high-level functional architectures for autonomous systems; and (6) a theory of higher-order contracts. We believe that addressing these research needs, among others, could improve the adoption of formal methods in the design of autonomous systems including learning-enabled systems, and increase confidence in their safe operations.
BibTeX
@inproceedings{pinto2023leveraging,
  author = {Alessandro Pinto and Anthony Corso and Edward Schmerling},
  title = {{Leveraging Compositional Methods for Modeling and Verification of an Autonomous Taxi System}},
  booktitle = {ICAA},
  year = {2023},
  url = {https://openreview.net/forum?id=jW720W3jyS},
}

Loading related content...

Figure