Automatic emergency-braking case study¶
This notebook uses the safety-supervisor, vehicle-response, predicted-clearance, and target contracts from Pacti's maintained AEB examples. The numerical envelopes are parameters of the contract example, not measured properties of a vehicle implementation.
Figure 1: AEB architecture from the GR(1) paper. The three-component composition eliminates u, MOV, DCL, STP, and v, leaving the predicted clearance z externally visible.
| Variable | Sort | Meaning |
|---|---|---|
d |
real | measured obstacle distance (m) |
URG, WRN |
Boolean | urgent and warning conditions |
MOV, DCL, STP |
Boolean | moving, decelerating, and stopped modes |
u |
real | longitudinal velocity command (m/s) |
v |
real | realized forward speed (m/s) |
z |
real | one-step predicted clearance (m) |
The supervisor produces the modes and u. The vehicle contract consumes this interface and produces v. The clearance contract uses d and v to produce z.
from html import escape
from IPython.display import HTML, display
from pacti.iocontract import GR1IoContract, Var
sorts = {name: "bool" for name in ("URG", "WRN", "MOV", "DCL", "STP")}
sorts.update({name: "real" for name in ("d", "u", "v", "z")})
def show_full_contract(label, contract):
text = escape(contract.to_pretty_string())
display(HTML(
f"<details><summary>{label}</summary>"
f"<pre style='white-space: pre-wrap; overflow-wrap: anywhere'>{text}</pre></details>"
))
Component contracts¶
The supervisor assumes an initial distance between 20 and 30 and assigns the hazard indicators from d: urgent at or below 10, warning between 10 and 15, and clear above 15. The clear condition recurs. Its guarantees enforce one active mode, the mode transitions, and distance-dependent command bounds.
supervisor = GR1IoContract.from_dict({
"input_vars": ["d", "URG", "WRN"],
"output_vars": ["MOV", "DCL", "STP", "u"],
"variable_sorts": sorts,
"assumptions": {
"init": ["20 <= d", "d <= 30", "!URG", "!WRN"],
"inv": [
"0 <= d",
"d <= 30",
"d <= 10 -> (URG & !WRN)",
"(10 < d & d <= 15) -> (WRN & !URG)",
"d > 15 -> (!URG & !WRN)",
],
"liv": ["!URG & !WRN"],
},
"guarantees": {
"init": ["MOV", "!DCL", "!STP", "u = d/10"],
"inv": [
"(MOV | DCL | STP) & !(MOV & DCL) & !(MOV & STP) & !(DCL & STP)",
"(URG & !WRN) -> X(STP)",
"(WRN & !URG & (MOV | DCL)) -> X(DCL)",
"(WRN & !URG & STP) -> X(STP)",
"!(URG | WRN) -> X(MOV)",
"0 <= u",
"u <= 6",
"u <= d/5",
"X(STP) -> u = 0",
"X(DCL) -> u <= 3",
"X(MOV) -> u >= d/10",
],
"liv": ["MOV"],
},
}, simplify=False)
The vehicle accepts mode-indexed commands between 0 and 6 and assumes that moving mode recurs. It guarantees nonnegative speed and one-step tracking error at most 1/2.
vehicle = GR1IoContract.from_dict({
"input_vars": ["u", "MOV", "DCL", "STP"],
"output_vars": ["v"],
"variable_sorts": sorts,
"assumptions": {
"init": ["2 <= u", "u <= 3"],
"inv": [
"0 <= u",
"u <= 6",
"X(STP) -> u = 0",
"X(DCL) -> u <= 3",
"X(MOV) -> u >= 2",
],
"liv": ["MOV"],
},
"guarantees": {
"init": ["v = u"],
"inv": ["v >= 0", "u - 1/2 <= X(v)", "X(v) <= u + 1/2"],
},
}, simplify=False)
The predicted-clearance contract has no assumptions. With the one-second prediction horizon used here, its invariant is X(z) = d - X(v). Thus z is a one-step calculation, not an additional physical state.
prediction = GR1IoContract.from_dict({
"input_vars": ["d", "v"],
"output_vars": ["z"],
"variable_sorts": sorts,
"assumptions": {},
"guarantees": {"inv": ["X(z) = d - X(v)"]},
}, simplify=False)
Safety target¶
The target \(\mathcal{C}_T\) has interface (d, URG, WRN) -> v. It retains the supervisor's environment model, assumes d >= 3/2, and requires d >= 20 whenever the road is clear. Its safety guarantee X(v) <= d - 1 leaves a one-metre clearance over the one-second horizon. Its liveness guarantee requires a clear condition with next speed at least 3/2 to recur.
target = GR1IoContract.from_dict({
"input_vars": ["d", "URG", "WRN"],
"output_vars": ["v"],
"variable_sorts": sorts,
"assumptions": {
"init": ["20 <= d", "d <= 30", "!URG", "!WRN"],
"inv": [
"0 <= d",
"d <= 30",
"d <= 10 -> (URG & !WRN)",
"(10 < d & d <= 15) -> (WRN & !URG)",
"d > 15 -> (!URG & !WRN)",
"d >= 3/2",
"!(URG | WRN) -> d >= 20",
],
"liv": ["!URG & !WRN"],
},
"guarantees": {
"inv": ["X(v) <= d - 1"],
"liv": ["!URG & !WRN & X(v) >= 3/2"],
},
}, simplify=False)
print(target.to_pretty_string())
Inputs: d, URG, WRN
Outputs: v
Assumptions
INIT:
(20 <= d) ∧ (30 >= d) ∧ ¬(URG) ∧ ¬(WRN)
INV:
□(((20 <= d) ∨ URG ∨ WRN) ∧ (d >= 3/2) ∧ (30 >= d) ∧ (URG → ¬(WRN)) ∧ (URG → (d <= 10)) ∧ (¬(URG) → ¬((d <= 10))) ∧ (WRN → (d <= 15)))
LIV:
□◇(¬(URG) ∧ ¬(WRN))
Guarantees
INV:
□(X(v) <= (-1 + d))
LIV:
□◇(¬(URG) ∧ ¬(WRN) ∧ (X(v) >= 3/2))
Composition¶
The interconnection is compatible in the clear region only when d >= 20. This follows from the vehicle requirement X(MOV) -> u >= 2 and the supervisor's lower envelope u >= d/10 in moving mode. The first composition eliminates u, MOV, DCL, and STP, leaving (d, URG, WRN) -> v. Composing with \(\mathcal{C}_D\) also eliminates v and leaves (d, URG, WRN) -> z.
system = supervisor.compose(vehicle)
full_system = system.compose(prediction)
internal = ["u", "MOV", "DCL", "STP"]
assert [variable.name for variable in system.inputvars] == ["d", "URG", "WRN"]
assert [variable.name for variable in system.outputvars] == ["v"]
assert all(Var(name) not in system.a.vars + system.g.vars for name in internal)
assert [variable.name for variable in full_system.inputvars] == ["d", "URG", "WRN"]
assert [variable.name for variable in full_system.outputvars] == ["z"]
assert Var("v") not in full_system.a.vars + full_system.g.vars
print("C_S || C_V interface: (d, URG, WRN) -> v")
print("C_S || C_V || C_D interface: (d, URG, WRN) -> z")
print("Eliminated variables: u, MOV, DCL, STP, v")
show_full_contract("Full computed C_S || C_V contract", system)
show_full_contract("Full computed C_S || C_V || C_D contract", full_system)
C_S || C_V interface: (d, URG, WRN) -> v
C_S || C_V || C_D interface: (d, URG, WRN) -> z
Eliminated variables: u, MOV, DCL, STP, v
Full computed C_S || C_V contract
Inputs: d, URG, WRN
Outputs: v
Assumptions
INIT:
20 <= d
INV:
□((WRN ∨ (d <= 10) ∨ (d <= 15) ∨ X(WRN) ∨ ¬((X(d) <= 10)) ∨ ¬(X(URG)) ∨ ¬((d >= 0)) ∨ ¬((d <= 30)) ∨ ¬((X(d) <= 30)) ∨ (d >= 20) ∨ ¬((d <= 60)) ∨ ¬((X(d) >= 0)) ∨ ¬((X(d) <= 15))) ∧ (URG ∨ WRN ∨ (d <= 10) ∨ (d <= 15) ∨ X(WRN) ∨ (X(d) <= 10) ∨ (X(d) <= 15) ∨ X(URG) ∨ ¬((d >= 0)) ∨ ¬((d <= 30)) ∨ ¬((X(d) <= 30)) ∨ ¬((X(d) <= 60)) ∨ (d >= 20) ∨ ¬((d <= 60)) ∨ ¬((X(d) >= 0))) ∧ (URG ∨ WRN ∨ (d <= 10) ∨ (d <= 15) ∨ (X(d) <= 10) ∨ ¬(X(WRN)) ∨ X(URG) ∨ ¬((d >= 0)) ∨ ¬((d <= 30)) ∨ ¬((X(d) <= 30)) ∨ ¬((X(d) <= 60)) ∨ (d >= 20) ∨ ¬((d <= 60)) ∨ ¬((X(d) >= 0)) ∨ ¬((X(d) <= 15))) ∧ (0 <= d) ∧ (30 >= d) ∧ (¬((10 >= d)) ∨ (URG ∧ ¬(WRN))) ∧ (¬((¬((d <= 10)) ∧ (15 >= d))) ∨ (WRN ∧ ¬(URG))) ∧ ((d <= 15) ∨ (¬(URG) ∧ ¬(WRN))))
LIV:
□◇(¬(URG) ∧ ¬(WRN))
Guarantees
INIT:
(X(v) <= (1/2 + v)) ∧ (v = (1/10 * d)) ∧ (v <= (1/2 + X(v)))
INV:
□((0 <= X(v)) ∧ (0 <= v) ∧ ((X(v) + (-1/5 * d)) <= 1/2) ∧ (¬(URG) ∨ WRN ∨ (X(v) <= 1/2)) ∧ (URG ∨ WRN ∨ (((-1 * X(v)) + (1/10 * d)) <= 1/2)))Full computed C_S || C_V || C_D contract
Inputs: d, URG, WRN
Outputs: z
Assumptions
INIT:
20 <= d
INV:
□((WRN ∨ (d <= 10) ∨ (d <= 15) ∨ X(WRN) ∨ ¬((X(d) <= 10)) ∨ ¬(X(URG)) ∨ ¬((d >= 0)) ∨ ¬((d <= 30)) ∨ ¬((X(d) <= 30)) ∨ (d >= 20) ∨ ¬((d <= 60)) ∨ ¬((X(d) >= 0)) ∨ ¬((X(d) <= 15))) ∧ (URG ∨ WRN ∨ (d <= 10) ∨ (d <= 15) ∨ X(WRN) ∨ (X(d) <= 10) ∨ (X(d) <= 15) ∨ X(URG) ∨ ¬((d >= 0)) ∨ ¬((d <= 30)) ∨ ¬((X(d) <= 30)) ∨ ¬((X(d) <= 60)) ∨ (d >= 20) ∨ ¬((d <= 60)) ∨ ¬((X(d) >= 0))) ∧ (URG ∨ WRN ∨ (d <= 10) ∨ (d <= 15) ∨ (X(d) <= 10) ∨ ¬(X(WRN)) ∨ X(URG) ∨ ¬((d >= 0)) ∨ ¬((d <= 30)) ∨ ¬((X(d) <= 30)) ∨ ¬((X(d) <= 60)) ∨ (d >= 20) ∨ ¬((d <= 60)) ∨ ¬((X(d) >= 0)) ∨ ¬((X(d) <= 15))) ∧ (0 <= d) ∧ (30 >= d) ∧ (¬((10 >= d)) ∨ (URG ∧ ¬(WRN))) ∧ (¬((¬((d <= 10)) ∧ (15 >= d))) ∨ (WRN ∧ ¬(URG))) ∧ ((d <= 15) ∨ (¬(URG) ∧ ¬(WRN))))
LIV:
□◇(¬(URG) ∧ ¬(WRN))
Guarantees
INIT:
(((9/10 * d) + (-1 * X(z))) <= 1/2) ∧ ((-9/10 * d) <= (1/2 + (-1 * X(z))))
INV:
□((((4/5 * d) + (-1 * X(z))) <= 1/2) ∧ (¬(URG) ∨ WRN ∨ ((d + (-1 * X(z))) <= 1/2)) ∧ (X(z) <= d) ∧ (URG ∨ WRN ∨ (((-9/10 * d) + X(z)) <= 1/2)))The generated formulas are available above without replacing them by a hand-written result. Their longest clauses are difficult to read inline, so the following compact three-component contract is constructed separately and checked against the computed contract in both refinement directions.
compact_full_system = GR1IoContract.from_dict({
"input_vars": ["d", "URG", "WRN"],
"output_vars": ["z"],
"variable_sorts": sorts,
"assumptions": {
"init": ["20 <= d", "d <= 30", "!URG", "!WRN"],
"inv": [
"0 <= d",
"d <= 30",
"d <= 10 -> (URG & !WRN)",
"(10 < d & d <= 15) -> (WRN & !URG)",
"d > 15 -> (!URG & !WRN)",
"!(URG | WRN) -> d >= 20",
],
"liv": ["!URG & !WRN"],
},
"guarantees": {
"init": ["9*d/10 - 1/2 <= X(z)", "X(z) <= 9*d/10 + 1/2"],
"inv": [
"4*d/5 - 1/2 <= X(z)",
"X(z) <= d",
"(URG & !WRN) -> X(z) >= d - 1/2",
"!(URG | WRN) -> X(z) <= 9*d/10 + 1/2",
],
},
}, simplify=False)
assert full_system.refines(compact_full_system)
assert compact_full_system.refines(full_system)
print(compact_full_system.to_pretty_string())
print("The computed and compact composition contracts refine one another.")
Inputs: d, URG, WRN
Outputs: z
Assumptions
INIT:
(20 <= d) ∧ (30 >= d) ∧ ¬(URG) ∧ ¬(WRN)
INV:
□(((20 <= d) ∨ URG ∨ WRN) ∧ (30 >= d) ∧ (0 <= d) ∧ (URG → ¬(WRN)) ∧ (URG → (d <= 10)) ∧ (¬(URG) → ¬((d <= 10))) ∧ (WRN → (d <= 15)))
LIV:
□◇(¬(URG) ∧ ¬(WRN))
Guarantees
INIT:
((9/10 * d) <= (1/2 + X(z))) ∧ (X(z) <= (1/2 + (9/10 * d)))
INV:
□(((4/5 * d) <= (1/2 + X(z))) ∧ (X(z) <= d) ∧ (¬((URG ∧ ¬(WRN))) ∨ (X(z) >= (-1/2 + d))) ∧ (URG ∨ WRN ∨ (X(z) <= (1/2 + (9/10 * d)))))
The computed and compact composition contracts refine one another.
The two certificates establish equivalence between the displayed compact form and Pacti's returned three-component contract. They do not assert that CAVE is an exact temporal projection: the returned contract is a sound relaxation of the exact composition.
Safety refinement¶
The safety target is expressed over v, so the relevant check is \(\mathcal{C}_S \parallel \mathcal{C}_V \leq \mathcal{C}_T\). A successful check means that, under the target assumptions, the composed supervisor and vehicle satisfy the one-step clearance bound and recurring-progress requirement.
composition_refines_target = system.refines(target)
target_refines_composition = target.refines(system)
assert composition_refines_target
print("C_S || C_V <= C_T:", composition_refines_target)
print("C_T <= C_S || C_V:", target_refines_composition)
C_S || C_V <= C_T: True
C_T <= C_S || C_V: False
The forward refinement is established. The reverse direction is not established. The target states the required safety and progress properties without reproducing every guarantee of the composed implementation.
Quotient¶
The quotient \(\mathcal{Q}=\mathcal{C}_T/\mathcal{C}_V\) holds the vehicle fixed and computes requirements for a missing supervisor-side component. Its inputs are d, URG, and WRN. Its outputs are u and the three modes.
quotient = target.quotient(vehicle)
assert [variable.name for variable in quotient.inputvars] == ["d", "URG", "WRN"]
assert set(variable.name for variable in quotient.outputvars) == {"u", "MOV", "DCL", "STP"}
print("Quotient interface: (d, URG, WRN) -> (u, MOV, DCL, STP)")
show_full_contract("Full computed C_T / C_V contract", quotient)
Quotient interface: (d, URG, WRN) -> (u, MOV, DCL, STP)
Full computed C_T / C_V contract
Inputs: d, URG, WRN
Outputs: u, MOV, DCL, STP
Assumptions
INIT:
20 <= d
INV:
□(((20 <= d) ∨ URG ∨ WRN) ∧ (d >= 3/2) ∧ (30 >= d) ∧ (URG → ¬(WRN)) ∧ (URG → (d <= 10)) ∧ (¬(URG) → ¬((d <= 10))) ∧ (WRN → (d <= 15)))
LIV:
□◇(¬(URG) ∧ ¬(WRN))
Guarantees
INIT:
(2 <= u) ∧ (3 >= u)
INV:
□((X(MOV) → (2 <= u)) ∧ (X(DCL) → (3 >= u)) ∧ (X(STP) → (0 = u)) ∧ (6 >= u) ∧ (0 <= u) ∧ (3/2 <= ((-1 * u) + d)))
LIV:
□◇(¬(((0 <= d) ∧ (30 >= d) ∧ (¬((10 >= d)) ∨ (URG ∧ ¬(WRN))) ∧ (¬((¬((d <= 10)) ∧ (15 >= d))) ∨ (WRN ∧ ¬(URG))) ∧ ((d <= 15) ∨ (¬(URG) ∧ ¬(WRN))) ∧ (d >= 3/2) ∧ ((20 <= d) ∨ URG ∨ WRN))) ∨ ((¬((u >= -1/2)) ∨ (2 <= u)) ∧ (URG → ¬((u >= -1/2))) ∧ (WRN → ¬((u >= -1/2)))))
□◇(¬(MOV) → ¬(((0 <= d) ∧ (30 >= d) ∧ (¬((10 >= d)) ∨ (URG ∧ ¬(WRN))) ∧ (¬((¬((d <= 10)) ∧ (15 >= d))) ∨ (WRN ∧ ¬(URG))) ∧ ((d <= 15) ∨ (¬(URG) ∧ ¬(WRN))) ∧ (d >= 3/2) ∧ ((20 <= d) ∨ URG ∨ WRN))))The generated quotient contains long liveness clauses. The compact form below keeps its two recurrence obligations separate: clear operation with u >= 2 must recur, and MOV must recur. It also exposes the safety margin u <= d - 3/2, which accounts for the vehicle's tracking error.
compact_quotient = GR1IoContract.from_dict({
"input_vars": ["d", "URG", "WRN"],
"output_vars": ["u", "MOV", "DCL", "STP"],
"variable_sorts": sorts,
"assumptions": {
"init": ["20 <= d", "d <= 30", "!URG", "!WRN"],
"inv": [
"0 <= d",
"d <= 30",
"d <= 10 -> (URG & !WRN)",
"(10 < d & d <= 15) -> (WRN & !URG)",
"d > 15 -> (!URG & !WRN)",
"d >= 3/2",
"!(URG | WRN) -> d >= 20",
],
"liv": ["!URG & !WRN"],
},
"guarantees": {
"init": ["2 <= u", "u <= 3"],
"inv": [
"0 <= u",
"u <= 6",
"u <= d - 3/2",
"X(STP) -> u = 0",
"X(DCL) -> u <= 3",
"X(MOV) -> u >= 2",
],
"liv": ["!URG & !WRN & u >= 2", "MOV"],
},
}, simplify=False)
assert quotient.refines(compact_quotient)
assert compact_quotient.refines(quotient)
print(compact_quotient.to_pretty_string())
print("The computed and compact quotient contracts refine one another.")
Inputs: d, URG, WRN
Outputs: u, MOV, DCL, STP
Assumptions
INIT:
(20 <= d) ∧ (30 >= d) ∧ ¬(URG) ∧ ¬(WRN)
INV:
□(((20 <= d) ∨ URG ∨ WRN) ∧ (d >= 3/2) ∧ (30 >= d) ∧ (URG → ¬(WRN)) ∧ (URG → (d <= 10)) ∧ (¬(URG) → ¬((d <= 10))) ∧ (WRN → (d <= 15)))
LIV:
□◇(¬(URG) ∧ ¬(WRN))
Guarantees
INIT:
(2 <= u) ∧ (3 >= u)
INV:
□((0 <= u) ∧ (6 >= u) ∧ (u <= (-3/2 + d)) ∧ (X(STP) → (0 = u)) ∧ (X(DCL) → (3 >= u)) ∧ (X(MOV) → (2 <= u)))
LIV:
□◇(¬(URG) ∧ ¬(WRN) ∧ (2 <= u))
□◇(MOV)
The computed and compact quotient contracts refine one another.
The original supervisor should refine the quotient. Recomposition with the fixed vehicle should then refine the target. Neither reverse relation is assumed.
recomposed = vehicle.compose(quotient)
supervisor_refines_quotient = supervisor.refines(quotient)
quotient_refines_supervisor = quotient.refines(supervisor)
recomposition_refines_target = recomposed.refines(target)
target_refines_recomposition = target.refines(recomposed)
assert supervisor_refines_quotient
assert recomposition_refines_target
print("C_S <= C_T / C_V:", supervisor_refines_quotient)
print("C_T / C_V <= C_S:", quotient_refines_supervisor)
print("C_V || (C_T / C_V) <= C_T:", recomposition_refines_target)
print("C_T <= C_V || (C_T / C_V):", target_refines_recomposition)
C_S <= C_T / C_V: True
C_T / C_V <= C_S: False
C_V || (C_T / C_V) <= C_T: True
C_T <= C_V || (C_T / C_V): False
The composition exposes predicted-clearance bounds over the external environment variables. The target refinement establishes the requested one-step safety margin and recurring progress. The quotient constrains the command and mode behavior required of a supervisor paired with the fixed vehicle. CAVE returns sound finite-window bounds and is not complete for every temporal projection. A False refinement result is therefore inconclusive in general. These computations do not solve controller realizability or synthesize a braking controller.