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

Alessandro Pinto, Anthony Corso, Edward Schmerling

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.

Introduction

Ensuring the safety of autonomous systems, such as self-driving cars or pilotless aircraft, is one of the most significant challenges in modern engineering. Traditional empirical testing is insufficient for these systems; it is estimated that a self-driving vehicle would need to be tested for billions of miles to statistically prove it is as safe as a human driver.

Formal methods—mathematical techniques used to prove that a system meets its requirements—offer a rigorous alternative. However, these methods often struggle with the "tantamount complexity" of modern autonomous stacks, which integrate diverse technologies like sensors, AI-based perception, and complex control loops. This paper explores a compositional approach to modeling and verification, demonstrating how complex systems can be broken down into smaller, verifiable components using a contract-based framework.

Methodology: Contract-Based Design

The authors apply a Contract-Based Design (CBD) framework to a case study involving an autonomous aircraft taxiing from a gate to a runway. The core of this approach is the decomposition of the system into a manageable hierarchy: Route Generation → Trajectory Generation → Trajectory Following.

Compositional Modeling

Each component in the hierarchy is governed by a formal "contract." These contracts consist of two primary elements:

  1. Assumptions: The conditions the component expects from its environment or preceding components.
  2. Guarantees: The specific behaviors or outputs the component promises to provide, provided the assumptions are met.

Heterogeneous Viewpoints

To manage the diverse requirements of an autonomous system, the model is split into two distinct viewpoints:

  • Protocol View: This view utilizes Linear Temporal Logic (LTL) to model the timing and sequence of events, such as ensuring a new command is not issued until the previous one has been acknowledged.
  • Functional View: This view uses Many-Sorted First Order Logic (MS-FOL) to model data-specific properties, such as ensuring the aircraft remains within a specific distance (δ) of the taxiway centerline.

Verification and Inductive Reasoning

The authors use automated reasoning tools to prove that if the sub-components meet their individual contracts, the overall system requirements are satisfied. They utilize OCRA for temporal logic refinement and SMT solvers like Z3 and CVC5 for functional logic. For repetitive tasks, such as stopping at multiple "hold-short" lines during taxiing, the authors employ inductive proofs to show that if a contract holds for n segments, it remains valid for n+1.

Key Insights and Research Roadmap

While the authors successfully demonstrated the decomposition of a multi-layer autonomous taxi architecture, the process revealed several critical gaps in the current state of formal methods. The paper identifies six primary research needs to facilitate the adoption of these methods in industry:

  1. The Viewpoint Challenge: There is currently no standardized way to formally merge heterogeneous models (e.g., combining timing logic with data accuracy logic). Semantics for the composition of different viewpoints are required.
  2. Productivity and Libraries: Writing formal specifications is currently a slow, expert-heavy process. The authors advocate for libraries of formal models for common autonomous concepts (paths, graphs, motion primitives) to accelerate development.
  3. Explainability of Verification: When automated solvers find a violation (an "unsat" result), the output is often a cryptic mathematical trace. Methods are needed to "lift" these results back into human-readable specifications so engineers can effectively debug requirements.
  4. Probabilistic Contracts: Traditional formal methods are binary (True/False). However, AI components like object detectors are inherently probabilistic. A framework for "probabilistic contracts" is necessary to reason about imperfect implementations.
  5. Standard Functional Architectures: The industry lacks standard high-level architectures for autonomy, making it difficult to reuse formal models across different platforms.
  6. Higher-Order Contracts: There is a need for a theory of contracts that can be parameterized by other contracts to handle the dynamic mission horizons typical of autonomous operations.

Conclusion

This research demonstrates that compositional modeling provides a viable path toward the rigorous assurance of autonomous systems. By breaking the taxiing task into discrete, contract-bound components, the authors were able to prove top-level safety requirements using existing automated solvers. However, the transition from "nominal" models to robust, real-world applications requires addressing the identified research gaps, particularly regarding probabilistic reasoning and the integration of heterogeneous specification languages. Addressing these needs will be vital for increasing public and regulatory confidence in autonomous operations.

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},
}
Figure