On a Formal Model of Safe and Scalable Self-driving Cars

Shai Shalev-Shwartz; Shaked Shammah; Amnon Shashua

Source-linked AI summary

On a Formal Model of Safe and Scalable Self-driving Cars

Shai Shalev-Shwartz, Shaked Shammah, Amnon Shashua

arXiv:1708.06374v6Aug 21, 2017cs.ROcs.AIstat.ML

TL;DR

Self-driving research needs standardized nominal-safety assurance and scalable designs, because existing safety claims and validation approaches face serious limitations. The paper introduces Responsibility-Sensitive Safety and a semantic driving framework, showing bounded planning complexity and a system design intended to support scalable safety assurance.

Problem
Self-driving cars lack a nominal-safety standard for safe logical decision making, while validating extremely rare safety-critical mistakes through driving data is unrealistic.
Method
The paper formalizes Responsibility-Sensitive Safety as a mathematical interpretation of Duty of Care and introduces a semantic language for planning, sensing, actuation, and scalable system design.
Results
10^4 trajectories bound the number inspected at any planning time regardless of the planning horizon, while semantic representations support Q-function learning and PAC sensing tied to RSS.
Takeaways & Limitations
RSS provides an interpretable, implementation-agnostic safety model aimed at preventing agents from causing accidents and compensating for reasonable mistakes by others.
Takeaways & Limitations
Q-function approximation and noisy state measurements can make nearly equivalent driving actions difficult to distinguish, potentially affecting policy decisions.

Abstract

from arXiv · show

In recent years, car makers and tech companies have been racing towards self driving cars. It seems that the main parameter in this race is who will have the first car on the road. The goal of this paper is to add to the equation two additional crucial parameters. The first is standardization of safety assurance --- what are the minimal requirements that every self-driving car must satisfy, and how can we verify these requirements. The second parameter is scalability --- engineering solutions that lead to unleashed costs will not scale to millions of cars, which will push interest in this field into a niche academic corner, and drive the entire field into a "winter of autonomous driving". In the first part of the paper we propose a white-box, interpretable, mathematical model for safety assurance, which we call Responsibility-Sensitive Safety (RSS). In the second part we describe a design of a system that adheres to our safety assurance requirements and is scalable to millions of cars.

1 Introduction

The paper addresses safety and scalability risks that could stall autonomous-vehicle progress by proposing a formal safety model and semantic framework spanning sensing, planning, and actuation.

Motivation: Safety guarantees are difficult because accidents can involve multiple agents, while statistical validation at a 10^-9 fatality rate would require more than 10^9 driving hours.The paper argues that this scale is unrealistic without additional assumptions.
Motivation: Scalability matters because autonomous vehicles must support mass production and lower-cost mobility rather than remain unsustainable science projects.The paper links insufficient scalability with the risk of an autonomous-vehicle winter.
Safety model: Responsibility-Sensitive Safety (RSS) formalizes an interpretation of Duty of Care intended to support sound, useful, and efficiently verifiable driving policies.RSS focuses on nominal safety: whether an error-free vehicle makes safe logical decisions.
Safety model: RSS is implementation-agnostic and targets behavior in which vehicles avoid causing accidents while compensating for reasonable mistakes by other drivers.The model does not require guaranteeing that an agent will never be involved in any accident.
Scalable system design: A semantic language organizes units, measurements, and action spaces across Planning, Sensing, and Actuation, addressing computational complexity, sensing-error handling, and safety–comfort interaction.The paper also uses semantics to support HD maps from low-bandwidth sensing data and crowd-sourced construction.
Scalable system design: In reinforcement learning, semantic actions bound the number of trajectories inspected at any time by 10^4 regardless of the planning time horizon.The paper also reports that semantic-space signal-to-noise is high enough to support effective Q-function modeling.
Scalable system design: The proposed methodology combines sense, plan, and act with redundant sensing, offline validation, and PAC sensing to connect nominal safety assurance with scalable deployment.The paper presents this combination as a complete methodology for safe and scalable autonomous vehicles.

2 Existing Approaches to Claims on Safe AV Decision Making

The paper argues that existing statistical, simulation, and scenario-based approaches do not provide reliable assurance of safe autonomous-vehicle decision making. Their limitations include enormous data requirements, insufficiently representative testing, simulator-validation difficulty, and weak generalization.

Five industry approaches evaluate AV safety: miles driven, disengagements, simulation, scenario-based testing, and proprietary methods.
1/p1 samples can fail with constant probability to distinguish an AV making accidents with probability p1 from one that never makes accidents.
30 million miles are needed to statistically establish human-level fatal-accident probability, while a 10^-9 target requires 30 billion miles.The estimate assumes 30 miles per hour and one hour of driving as the unit of probability.
Disengagement counts are confounded by easy-versus-challenging test-case distributions and may not predict rare difficult accidents.
Simulator validation is as difficult as validating the driving policy because a simulator accurate for π may omit rare failures of a modified policy π′.
Scenario-based verification depends on generalization and risks overfitting the AV to tested situations.

3 The Responsibility-Sensitive Safety (RSS) model for Multi-agent Safety

RSS replaces impossible absolute-safety guarantees with a formal responsibility model for multi-agent driving. It defines careful behavior that avoids causing accidents and compensates for reasonable mistakes, while aiming to remain useful and verifiable.

Absolute safety is impossible because surrounding vehicles can create situations from which the central car cannot escape.
RSS formalizes an interpretation of Duty of Care into mathematical rules for self-driving cars.
RSS seeks a sound, useful, and efficiently verifiable interpretation rather than an over-cautious policy that blocks traffic.
Five common-sense rules underlie RSS: avoid rear-end collisions, avoid reckless cut-ins, yield right-of-way, exercise caution with limited visibility, and avoid preventable accidents.
In a single-lane setting, proper response behavior is proved to prevent the rear car from hitting the front car under stated braking assumptions.The proof uses an inductive sequence of non-collision intervals and non-dangerous states.

3.2 Preliminaries — A Lane-Based Coordinate System

The paper converts general lane geometry into lane-based longitudinal and lateral coordinates. This transformation preserves the logical ordering of vehicles and distinguishes actual lateral maneuvers from motion caused by changing lane width.

A generic transformation maps global planar positions into a lane-based coordinate system for analyzing non-straight roads.
The lane is represented by a directed center curve r and a continuous width function w over longitudinal positions.
The transformation preserves ordering: a car behind another has smaller longitudinal coordinate, and a car to the left has smaller lateral coordinate.
The mapping φ assigns each lane point its longitudinal position and normalized lateral offset within the lane.
A car on a widening lane boundary can move away from the center without performing a lateral maneuver because lane-relative boundary position remains fixed.

3.3 Longitudinal Safe Distance and Proper Response

RSS defines longitudinal safety through distance thresholds and proper responses tailored to vehicle direction. Dangerous situations trigger acceleration constraints intended to prevent collisions or assign responsibility when assumptions are violated.

For same-direction traffic, the rear car is responsible for maintaining safe distance and preparing for unexpected but reasonable braking by the front car.
Opposite-direction traffic requires both vehicles to reduce speed, with the vehicle traveling against the lane direction expected to brake harder.
Safe longitudinal distance is defined by response time, braking limits, acceleration limits, and whether vehicles travel in the same or opposite directions.
A longitudinally dangerous time occurs when the inter-vehicle distance is non-safe, and the Danger Threshold is the earliest time after which danger persists.
Proper response constrains acceleration during the response interval until vehicles regain a safe state or reach a full stop.
For opposite-direction cases, the proper-response constraints require the relevant vehicles to brake toward full stops according to their directional roles.

3.4 Lateral Safe Distance and Proper Response

The section defines lateral safety using a robust lateral-velocity notion, a safe lateral distance, and braking-based proper responses. These definitions are extended to arbitrary vehicle shapes and accommodate physical implementation constraints.

Lateral velocity: µ-lateral-velocity is zero if a point returns to its current lateral position before reaching a ±µ/2 boundary; otherwise it is its signed average lateral velocity to that boundary.
Safe lateral distance: A lateral distance is safe when mutual lateral acceleration during the response time followed by lateral braking leaves at least µ separation.The construction uses lateral acceleration toward one another for [0, ρ], then braking until both cars reach zero lateral velocity.
Lateral proper response: The lateral proper response constrains cars after the lateral Danger Threshold time to brake away from one another until reaching µ-lateral-velocity of 0.Before the threshold-plus-response interval, lateral acceleration is bounded; afterward, the cars apply opposite braking constraints until their lateral velocities are neutralized.
Lateral proper response: After reaching µ-lateral-velocity of 0, each car may continue with lateral velocity directed away from the other car.The permitted signs are non-positive for the left car and non-negative for the right car.
Scope and implementation: Physical vehicles need not switch instantaneously to zero lateral velocity, provided their lateral travel does not exceed the corresponding full-stop braking distance.The paper states that stronger initial braking followed by gradual deceleration can realize this requirement without changing RSS’s essence.
Scope and implementation: The definitions cover arbitrary vehicle shapes by taking the worst case over all points, including semi-trailers and vehicles with open doors.

3.5 Combining Longitudinal and Lateral Proper Responses

The paper combines longitudinal and lateral proper responses into one response for shared-geometry multi-lane roads. It proves that universal compliance with this response prevents collisions.

Combining responses: On multi-lane roads sharing one geometry, all lanes can be treated as one wide lane with defined longitudinal and lateral positions.Merges, junctions, roundabouts, and unstructured roads require a subsequent treatment using priority.
Combining responses: A situation is dangerous only when it is both longitudinally and laterally dangerous, and its Danger Threshold time is the maximum of the corresponding thresholds.
Combining responses: For side-by-side cars, the relevant proper response is lateral, whereas for cars traveling one behind another, it is longitudinal.Each configuration is already non-safe on the irrelevant axis, so danger develops on the other axis.
Combining responses: The basic proper response applies the longitudinal or lateral speed constraints associated with whichever Danger Threshold time is reached.
Safety result: No collisions occur on a shared-geometry multi-lane road when all cars comply with the basic proper response at all times.The proof uses an induction over successive times at which each pairwise situation becomes non-dangerous again.

3.6 Compensating for improper behavior of others

The paper adds evasive effort for cases where another agent fails to respond properly. Legal manoeuvres must avoid the immediate accident without violating the constraints that preserve the collision-prevention proof.

Motivation: When another agent does not comply, a car should make its best effort to avoid a dangerous situation without causing another accident.
Prediction and manoeuvres: Naive prediction extrapolates an agent’s current acceleration until its velocity reaches zero, then sets acceleration to zero.The future velocity and position are obtained by integrating this acceleration profile.
Prediction and manoeuvres: An evasive manoeuvre specifies longitudinal and lateral position functions over a plan interval, with velocities and accelerations given by their derivatives.
Prediction and manoeuvres: The manoeuvre is valid when, under the other car’s naive prediction, it prevents collision throughout the interval and makes the situation non-dangerous at its end.
Legal evasive effort: A legal evasive manoeuvre must also satisfy the basic proper-response constraints and acceleration bounds.The lateral acceleration magnitude is bounded by alat_max,accel, while longitudinal acceleration lies in [−amax,brake, amax,accel].
Legal evasive effort: If a legal evasive manoeuvre exists after another car violates the basic response, the proper response requires applying it in addition to the basic constraints.Because the manoeuvre never contradicts the basic response, the no-collision proof still applies.

3.7 Multiple Geometry and Right-of-Way Rules

The paper extends RSS to scenes with intersecting routes and different geometries by defining route-aware ordering, safe distances, and proper responses. Traffic-light priority is treated as a route-priority rule, while pairwise constraints preserve conflict-free calculations.

Multiple Geometries: Different route geometries can create contradictory proper-response constraints, motivating route-aware safety definitions for intersections, roundabouts, and merges.The paper identifies conflicts when one vehicle must follow incompatible responses relative to cars on routes with different geometries.
Multiple Geometries: Safe lateral distance for intersecting routes is defined from each vehicle’s reachable lateral interval under bounded acceleration and braking, requiring route restrictions to remain at least μ apart.The intervals are computed over a response period followed by lateral braking, then compared using the distance between restricted route sets.
Multiple Geometries: Longitudinal ordering for intersecting routes compares same-route ordering or each vehicle’s distance to the route intersection when the vehicles occupy separate routes.The definition is used where route geometry prevents a common longitudinal axis; its robustness is considered adequate when the cars already maintain safe distance.
Multiple Geometries: Pairwise proper responses are translated into constraints relative to the ego vehicle’s route, and taking their minimum avoids conflicts among multiple other vehicles.This star-shape calculation preserves the pairwise structure used by the safety reasoning.
Right-of-Way Rules: Traffic-light behavior reduces to route priority: a green-light route has priority over red-light routes, but a vehicle with priority must still yield when necessary to avoid an accident.The paper formalizes this as “right of way is given, not taken.”
Unstructured Roads: The unstructured-road kinematic model bounds changes in inverse turning radius and yaw rate, producing extreme future arcs that support collision avoidance.The resulting proper responses preserve bounded future-position calculations and can be applied against multiple other vehicles.

3.8 Pedestrians

For pedestrians, the paper reuses RSS safe-distance and proper-response ideas while adapting routes, motion assumptions, and priority rules. Examples show how these adaptations determine vehicle caution around stationary, crossing, and running pedestrians.

Pedestrian Rules: Pedestrian collision avoidance adjusts safe-distance and proper-response parameters, specifies pedestrian routes, and assigns their priority relative to vehicle routes.Pedestrian routes may be structured, such as sidewalks and crossings, or unstructured, such as residential streets.
Stationary Pedestrians: A standing pedestrian on a residential road is assigned all rays from the current position, yielding a 50cm safety radius under a 500ms delay and 2m/s^2 acceleration and braking.Vehicles must remain kinematically able to stay outside this radius under proper response.
Traffic Lights: When a pedestrian has a red light and a vehicle has a green light, the vehicle route has priority, but the vehicle must brake if the pedestrian enters while the vehicle is at a safe distance.The vehicle may otherwise drive at normal speed while assuming the pedestrian remains on the sidewalk.
Moving Pedestrians: For a pedestrian running at 10 km per hour, possible future trajectories form an isosceles triangle about 15m high, defining the distance within which cars should not enter the route.If a car enters beyond 15m and the pedestrian continues into a collision, responsibility is assigned to the pedestrian.

3.9 Cautiousness with respect to Occlusion

The paper formalizes cautious driving under occlusion by defining when an object becomes observable and by allowing bounded, reasonable assumptions about hidden road users. These assumptions avoid both delayed responses and excessively defensive behavior.

Reasonable assumptions: Assuming the worst possible behavior in every occluded position would produce over-defensive, unnatural driving.The paper motivates additional reasonable assumptions about occluded objects instead of universally assuming maximal danger.
Exposure Time: Exposure Time is the first moment an occluded object becomes visible, after which the vehicle must follow the regular proper-response rules.The definition requires an unobstructed line of sight between the object and the ego vehicle.
Velocity constraints: RSS bounds the speeds of occluded vehicles using parameters tied to map position, priority rules, scene structure, and other conditions.The unreasonable-speed definition compares lateral and longitudinal velocities with low and high limits.
Velocity constraints: Priority rules allow vehicles on the prioritized route a higher maximum-speed bound when approaching an occluded intersection.This lets the yellow car merge while assuming the other car approaches slowly enough.
Occluded agents: Occluded road users are assumed not to perform certain unreasonable cut-ins, including excessive lateral motion by vehicles or sudden entry by pedestrians.The same reasoning applies to static and slowly moving occluders.
Improper behavior: If a following car cannot avoid a stopped obstacle after the car ahead swerves away at the last moment, the resulting accident can appear to be the follower’s responsibility despite another agent’s improper behavior.The paper treats this as a distinct unreasonable situation arising from another agent’s behavior.

3.10 Responsibility

The paper defines responsibility through compliance with proper response constraints, while recognizing that occlusions can make responsibility unclear. This motivates rules that account for what agents could reasonably observe and assume.

Responsibility: An agent is responsible for an accident when it fails to comply with the proper response constraints.Without occlusions, a collision implies that at least one agent violated those rules.
Responsibility: Occlusions can produce accidents with no clear responsibility because an agent may reasonably assume that another vehicle is responding properly outside its view.The paper uses the Figure 14 scenario to illustrate this ambiguity.

3.11 Utopia is Possible

The paper argues that its occlusion-aware proper-response rules recover the basic safety guarantees. Consequently, if all road agents follow the specified rules, no collisions can occur.

Safety under occlusion: With occlusions, the extended proper-response rules are designed to preserve collision avoidance despite reasonable assumptions about hidden agents.The result addresses accidents in which neither agent is directly responsible under the occlusion assumptions.
Safety under occlusion: Lemma 6 shows that compliance with the extended rules implies compliance with the basic proper-response rules.Each agent therefore behaves as if it observes all other agents.
Proof strategy: The proof proceeds by induction on the distance between agents.The inductive claim establishes basic proper-response compliance for increasingly distant pairs.

4 Driving Policy

The paper formulates driving-policy design as reinforcement learning, where actions must be evaluated by their long-term effects. It proposes semantic actions to combine long-horizon evaluation with resource-efficient planning, while repeatedly adapting decisions to unmodeled environmental changes.

Policy formulation: A driving policy maps sensed world states to driving commands, whose consequences determine subsequent states and rewards.The commands include lateral and longitudinal accelerations, while other agents also affect the next state.
Policy formulation: Long-horizon action evaluation improves quality but increases computation exponentially, creating a trade-off between planning accuracy and resources.Short horizons can miss delayed outcomes such as reaching a highway exit, whereas brute-force evaluation requires substantial computation or memory.
Policy formulation: Existing resource-efficient approximations reduce computational demands but may produce inaccurate Q values and poor decisions, while learning complicated multi-agent Q functions remains difficult.The difficulty is linked to problematic Markovian assumptions and low signal-to-noise ratios caused by fine-grained decision making.
Semantics to the rescue: The proposed approach replaces geometrical actions with a semantic action space so Q evaluation can use long time horizons without inspecting many future actions.Semantic instructions encode goals such as lane position, relative vehicle position and speed, speed targets, and speed constraints.
Semantics to the rescue: Semantic actions are structured around lateral and longitudinal goals plus an aggressiveness level, with bounded numbers of relevant alternatives.The passage gives 16 lateral goals and up to 48 longitudinal goals of the first type as examples of this bounded design.
Constructing an evaluation function for semantic actions: The policy handles modeling errors by reapplying decisions at high frequency, continually adapting to environmental aspects beyond the model.This approach balances modeling error against planning frequency rather than relying entirely on a fixed long-horizon model.

5 Sensing

The sensing framework evaluates approximations by their effect on semantic driving actions and safety or comfort, rather than by geometric accuracy alone. It defines PAC sensing and shows how semantic guarantees and redundant validation support scalable safety assurance.

The sensing state summarizes static and dynamic scene information and serves as input to the driving-policy module.It includes lanes, road delimiters, speed and right-of-way constraints, occluders, and dynamic vehicles.
A sensing system maps raw sensor and mapping data x ∈ X to an approximate sensing state ˆs(x) ∈ S.The paper formalizes this mapping as ˆs : X → S.
Sensing quality is judged by whether approximation errors change the selected semantic action or materially reduce its quality under the true state.The policy selects π(s) = argmax_a Q(s, a), so the same action or nearly equivalent quality can justify accepting ˆs(x).
The PAC definition is sufficient but not necessary for comfort, because short-lived mistakes may have negligible ride impact; a multi-frame version is omitted as more technical.For example, detecting a missed slower vehicle after 100 milliseconds may leave the ride effectively unchanged.
Ego-accuracy below 3.5% can still confuse braking situations, producing substantially different Q values and failing to guarantee PAC sensing.The example shows that small relative positional error may cause a semantic lane-assignment mistake.
For an L-semantically-Lipschitz Q, semantic positioning error at most ϵ/L with probability at least 1 − δ yields PAC sensing with parameters ϵ, δ.The PAC definition evaluates sensing against a distribution over raw data and true states, a quality function Q, and the induced policy.
Offline validation can reduce the required dataset from order 10^9 to order 10^5 examples for a 10^-9 safety-critic mistake probability when each system is tested separately.The broader design uses large ground-truth datasets and redundant sensing modalities with at least two independent subsystems detecting each object.
Semantic high-definition mapping through Road Experience Management is presented as a system component alongside sensing and validation design.The paper contrasts this with geometrical point-cloud mapping, whose disadvantages include large memory requirements per kilometer.

A.1 Technical Lemma 1

This technical lemma establishes an exponential lower bound useful for the paper’s probability analysis on the interval [0, 0.1].

For every x ∈ [0, 0.1], 1 − x ≥ e^−2x.The proof defines f(x) = 1 − x − e^−2x and verifies that its derivative remains positive on the interval.