💻 computer science

Compositionally Safe Construction of Autonomous Driving Systems

This paper proposes a mathematically rigorous, compositionally safe framework for autonomous driving that ensures safety by construction through the coordinated execution of distinct control policies for specific driving configurations, thereby overcoming the limitations of both end-to-end AI and traditional systems engineering.

Original authors: Marius Bozga, Joseph Sifakis

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marius Bozga, Joseph Sifakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to drive a car. You have two main ways to do it:

The "Black Box" Method (AI): You throw a million miles of driving videos at a neural network and hope it learns to drive like a human. The problem? You don't know why it makes decisions. If it suddenly swerves, you can't explain why, and you can't mathematically prove it won't kill anyone.
The "Old School" Method (Traditional Engineering): You try to write a rule for every single possible situation in the world. The problem? The world is too complex. There are too many variables (weather, other drivers, road shapes), and the math gets so heavy the computer can't handle it in real-time.

This paper proposes a "Third Way."

Think of it like teaching a child to cross the street. Instead of memorizing every single street in the city, you teach them a few fundamental skills (like "look left, look right, cross") and explain that if they master these skills, they can cross any street safely.

Here is the core idea of the paper, broken down with simple analogies:

1. The "Lego Block" Philosophy

The authors argue that driving isn't one giant, impossible puzzle. It's actually just a sequence of small, manageable Lego blocks (which they call "Driving Configurations").

No matter how complex a city is, a car only ever finds itself in one of three simple situations:

The Highway (Road): You are driving straight. There are no intersections ahead. You just need to follow the car in front of you.
The Merge (Joining): You are trying to get onto a busy highway or change lanes. You have to wait for a gap in the faster traffic.
The Intersection (Crossing): You are at a stop sign or a traffic light where your path crosses with others. You have to wait your turn.

The Magic: If you can prove that your car is safe in each of these three simple blocks, then the whole journey is safe. You don't need to predict the future; you just need to handle the current block correctly.

2. The "Invisible Bubble" (Free Space)

How does the car know it's safe? The paper introduces a concept called "Free Space."

Imagine every car has an invisible, protective bubble around it.

This bubble is calculated based on how fast the car is going and how quickly it can stop (braking distance).
The rule is simple: As long as your bubble doesn't touch anyone else's bubble, you are safe.

The car's computer constantly checks: "Is my bubble clear?"

If there is a car ahead, the bubble shrinks to stop just behind them.
If there is a stop sign, the bubble stops before the sign.
If the bubble is clear, the car accelerates. If it's getting crowded, the car slows down.

3. The "Two-Step Dance"

When the car faces a tricky situation (like merging onto a highway), it doesn't panic. It performs a specific two-step dance:

Step 1: The Caution Phase (The "Wait"): The car slows down and gets ready. It calculates: "If I merge now, will I hit that car coming from the left?" It waits until the math says "Yes, there is enough room."
Step 2: The Progress Phase (The "Go"): Once the math confirms it's safe, the car accelerates and moves forward.

The paper proves that if every car follows this "Wait then Go" dance based on its own "Free Space," they will never crash, even if they don't talk to each other.

4. The "Traffic Cop" vs. The "Driver"

In many systems, there is a central "Traffic Cop" (a super-computer) telling every car where to go. This paper says: No need for a Traffic Cop.

Instead, every car is a responsible citizen.

The Rule: "I am responsible for my own bubble. If I stay in my bubble and follow the rules (stop signs, lights), and everyone else does the same, we will all be safe."
This is called "Assume-Guarantee."
- Assume: "I assume everyone else follows the rules."
- Guarantee: "I guarantee I will stay in my bubble."

Why is this a big deal?

Safety by Design: Unlike AI, which is a "black box," this method is built on math. We can prove it works. It's like building a bridge where we know exactly how much weight it can hold, rather than just hoping it doesn't collapse.
Simplicity: It breaks a terrifyingly complex problem (driving in a city) into tiny, solvable math problems.
Robustness: It doesn't rely on the car "guessing" what a human driver will do. It relies on strict rules and physical limits (like braking distance).

The Bottom Line

This paper suggests that to build truly safe self-driving cars, we shouldn't try to make them "smart" like humans (which is unpredictable). Instead, we should make them disciplined like a well-trained athlete. If every car strictly follows a few simple, mathematically proven rules about speed, stopping distance, and right-of-way, the entire system becomes safe by construction.

It's the difference between hoping a chaotic crowd doesn't bump into each other, and organizing them into a line where everyone knows exactly where to stand.

1. Problem Statement

The development of trustworthy Autonomous Driving Systems (ADS) faces a dichotomy between two existing approaches, both of which have significant limitations regarding safety guarantees:

End-to-End AI Solutions: While simple and cost-effective, these black-box models lack interpretability, determinism, and formal safety guarantees. They suffer from non-explainability and anomalies.
Traditional Multi-Module Systems: These offer better interpretability but struggle with the intrinsic complexity of the problem. They often suffer from a lack of module composability, leading to compound errors and information loss.
Existing Control Theory: Methods like PID, MPC, and LPV are hampered by computational complexity and difficulty in realistically modeling safety constraints for diverse driving scenarios.

The core challenge is to construct an ADS that is safe by construction, capable of handling complex, dynamic environments without relying on unproven AI heuristics or intractable global optimization.

2. Methodology

The authors propose a compositional, rule-based approach grounded in formal methods and "assume-guarantee" contracts. The methodology decomposes the global safety problem into manageable local sub-problems based on three key principles:

A. Decomposition Principles

Locality of Context: Safety policies are decomposed based on specific road patterns (e.g., straight roads, merges, intersections). The system assumes the traffic infrastructure is a composition of finite patterns.
Locality of Knowledge: Vehicles rely only on local visibility (a "visibility zone"). Safety is ensured by considering only obstacles within this zone, including fictitious vehicles at the visibility limits to account for uncertainty.
Rights-Based Responsibility: Each vehicle is responsible for managing its own "free space" defined by traffic rules. If every vehicle drives safely within its allocated free space, the entire system (SADS) is safe.

B. Driving Configurations

The system models the environment as a Metric Graph (roads and junctions). The autopilot receives Driving Configurations as inputs, defined as a triple $\langle q_e, q_F, q_A \rangle$ :

$q_e$ : State of the ego vehicle.
$q_F$ : States of front obstacles (vehicles or signals) on the ego's route.
$q_A$ : States of arriving vehicles at junctions or merging points.

These configurations are classified into three types:

Road Configurations: No junctions in visibility; the vehicle follows the lead obstacle.
Merging Configurations: The ego vehicle joins a higher-priority road or changes lanes.
Crossing Configurations: The ego vehicle crosses a junction (protected by traffic lights, stop signs, or yield signs).

C. Control Policy Architecture

The autopilot operates in two consecutive phases for each configuration type:

Caution Phase: The vehicle approaches a potential conflict (e.g., a yield sign or intersection) by managing speed to ensure it can stop safely if conditions do not clear.
Progress Phase: Once a clearance condition is met (proving no collision risk), the vehicle accelerates to clear the obstacle.

The policies are implemented using two fundamental mathematical functions characterizing vehicle dynamics:

Braking Function $B(v)$ : The distance required to stop from speed $v$ .
Speed Control Function $C(v, V_L)$ : Calculates the maximum safe speed variation $\Delta v$ and distance $\Delta d$ given current speed and a sequence of speed limits $V_L$ , ensuring the vehicle remains controllable.

3. Key Contributions

Compositional Safety Proof: The paper provides a formal proof that if a vehicle is safe in every individual driving configuration type (Road, Merge, Cross), and the transitions between these configurations satisfy specific temporal conditions, the global system behavior is safe.
Formal Definition of "Free Space": The authors define a dynamic "free space" for each vehicle, bounded by the nearest obstacle, speed limits, and braking capabilities. They prove that if vehicles stay within their disjoint free spaces, collisions are impossible.
Assume-Guarantee Contracts: The system uses contracts where the "assumption" is that other agents (or the environment) behave according to traffic rules within their own free spaces, and the "guarantee" is that the ego vehicle will not violate its safety constraints.
Two-Phase Policy Design: A novel control structure that explicitly separates "caution" (risk mitigation) from "progress" (efficiency), governed by a boolean clearance flag. This prevents the system from being overly conservative (deadlocks) or reckless.
Handling of Visibility Constraints: The method incorporates "fictitious vehicles" at the limits of visibility zones to ensure safety even when the full environment is not known.

4. Results

Theoretical Verification: The authors prove Theorem 1: If a System of ADS (SADS) is initially safe, it remains safe throughout execution. This is achieved by showing that:
- Safe states imply compliance with speed limits and disjoint free spaces (Lemma 1).
- The transition between states preserves safety (Lemmas 2–4).
- The step between states is "non-intrusive" (no vehicle suddenly appears in another's free space in a way that violates safety) (Lemma 6).
Coverage of Operations: The framework successfully covers major driving operations: entering main roads, overtaking (modeled as two merges), crossing intersections (with lights, stop signs, or yield signs), and freeway driving.
Simplicity: The control policies rely on simple arithmetic calculations involving braking distances and travel time predictions, avoiding complex neural networks or heavy optimization solvers.

5. Significance

A "Third Way" for ADS: The paper offers a viable alternative to the current AI vs. Traditional Engineering debate. It combines the rigor of formal verification with the practicality of rule-based systems.
Scalability: By decomposing the problem into local configurations and proving compositionality, the method avoids the "state explosion" problem common in global verification of multi-agent systems.
Safety by Construction: Unlike post-hoc testing or simulation-based validation, safety is mathematically guaranteed by the design of the control policies and the invariants they maintain.
Practical Applicability: The reliance on simple functions ( $B$ and $C$ ) suggests that this approach can be implemented on standard automotive hardware with low computational overhead, provided the underlying vehicle dynamics are well-characterized.

In conclusion, Bozga and Sifakis demonstrate that autonomous driving safety can be achieved through a modular, compositional framework that rigorously links local vehicle behaviors to global system safety, offering a robust path toward trustworthy autonomous systems.