OnaFormalModelofSafeandScalableSelf-drivingCars（Mobileye安全定义）资源-CSDN文库

需积分: 9 19 浏览量 2018-02-09 10:47:55 上传评论收藏 1.06MB PDF 举报

资源推荐

资源详情

资源评论

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

Shai Shalev-Shwartz, Shaked Shammah, Amnon Shashua

Mobileye, 2017

Abstract

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 ﬁrst car on the road. The goal of this paper is to add to the equation two

additional crucial parameters. The ﬁrst 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 ﬁeld into a niche academic corner, and drive the entire ﬁeld into a “winter of autonomous driving”. In the ﬁrst

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 “Winter of AI” is commonly known as the decades long period of inactivity following the collapse of Artiﬁcial

Intelligence research that over-reached its goals and hyped its promise until the inevitable fall during the early 80s.

We believe that the development of Autonomous Vehicles (AV) is dangerously moving along a similar path that might

end in great disappointment after which further progress will come to a halt for many years to come.

The challenges posed by most current approaches are centered around lack of safety guarantees, and lack of scala-

bility. Consider the issue of guaranteeing a multi-agent safe driving (“Safety”). Given that society will unlikely tolerate

road accident fatalities caused by machines, guarantee of Safety is paramount to the acceptance of AV. Ultimately, our

desire is to guarantee zero accidents, but this is impossible since multiple agents are typically involved in an accident

and one can easily envision situations where an accident occurs solely due to the blame of other agents (see Fig. 1 for

illustration). In light of this, the typical response of practitioners of AV is to resort to a statistical data-driven approach

where Safety validation becomes tighter as more mileage is collected.

To appreciate the problematic nature of a data-driven approach to Safety, consider ﬁrst that the probability of a

fatality caused by an accident per one hour of (human) driving is known to be 10

−6

. It is reasonable to assume that for

society to accept machines to replace humans in the task of driving, the fatality rate should be reduced by three orders

of magnitude, namely a probability of 10

−9

per hour

. In this regard, attempts to guarantee Safety using a data-driven

statistical approach, claiming increasing superiority as more mileage is driven, are naive at best. The amount of data

required to guarantee a probability of 10

−9

fatality per hour of driving is proportional to its inverse, 10

hours of data

(see details in the sequel), which is roughly in the order of thirty billion miles. Moreover, a multi-agent system interacts

with its environment and thus cannot be validated ofﬂine

, thus any change to the software of planning and control will

require a new data collection of the same magnitude — clearly unwieldy. Finally, developing a system through data

invariably suffers from lack of interpretability and explainability of the actions being taken — if an AV kills someone,

we need to know the reason. Consequently, a model-based approach to Safety is required but the existing ”functional

safety” and ASIL requirements in the automotive industry are not designed to cope with multi-agent environments.

Hence the need for a formal model of Safety which is one of the goals of this paper.

This estimate is inspired from the fatality rate of air bags and from aviation standards. In particular, 10

−9

is the probability that a wing will

spontaneously detach from the aircraft in mid air.

unless a realistic simulator emulating real human driving with all its richness and complexities such as reckless driving is available, but the

problem of validating the simulator is even harder than creating a Safe AV agent — see Section 2.2.

arXiv:1708.06374v4 [cs.RO] 18 Dec 2017

The second area of risk lies with lack of scalability. The difference between AV and other great science and

technology achievements of the past is that as a “science project” the effort is not sustainable and will eventually lose

steam. The premise underlying AV goes beyond “building a better world” and instead is based on the premise that

mobility without a driver can be sustained at a lower cost than with a driver. This premise is invariably coupled with

the notion of scalability — in the sense of supporting mass production of AVs (in the millions) and more importantly of

supporting a negligible incremental cost to enable driving in a new city. Therefore the cost of computing and sensing

does matter, if AV is to be mass manufactured, the cost of validation and the ability to drive “everywhere” rather than

in a select few cities is also a necessary requirement to sustain a business.

The issue with most current approaches is centered around a “brute force” state of mind along three axes: (i)

the required “computing density”, (ii) the way high-deﬁnition maps are deﬁned and created, and (iii) the required

speciﬁcation from sensors. A brute-force approach goes against scalability and shifts the weight towards a future in

which unlimited on-board computing is ubiquitous, somehow the cost of building and maintaining HD-maps becomes

negligible and scalable, and that exotic super advanced sensors would be developed, productized to automotive grade,

and at a negligible cost. A future for which any of the above holds is indeed plausible but having all of the above

hold becomes a low-probability event. The combined issues of Safety and Scalability contain the risk of “Winter of

AV”. The goal of this paper is to provide a formal model of how Safety and Scalability are pieced together into an

AV program that society can accept and is scalable in the sense of supporting millions of cars driving anywhere in the

developed countries.

The contribution of this paper is twofold. On the Safety front we introduce a model called “Responsibility Sen-

sitive Safety” (RSS) which formalizes the common sense of human judgement with regard to the notion of “who is

responsible for causing an accident”. RSS is interpretable, explainable, and incorporates a sense of “responsibility”

into the actions of a robotic agent. The deﬁnition of RSS is agnostic to the manner in which it is implemented — which

is a key feature to facilitate our goal of creating a convincing global safety model. RSS is motivated by the observation

(as highlighted in Fig. 1) that agents play a non-symmetrical role in an accident where typically only one of the agents

is responsible for the accident and therefore is to be blamed for it. The RSS model also includes a formal treatment of

“cautious driving” under limited sensing conditions where not all agents are always visible (due to occlusions of kids

behind a parking vehicle, for example). Our ultimate goal is to guarantee that an agent will never cause an accident,

rather than to guarantee that an agent will never be involved in an accident (which, as mentioned previously, is impos-

sible). It is important to note that RSS is not a formalism of blame according to the law but instead it is a formalism of

the common sense of human judgement. For example, if some other car violated the law by entering an intersection

while having the red light signal, while the robotic car had the green light, but had time to stop before crashing into

the other car, then the common sense of human judgement is that the robotic car should brake in order to avoid the

accident. In this case, the RSS model indeed requires the robotic car to brake in order not to cause an accident, and if

the robotic car fails to do so, it shares responsibility for the accident.

Clearly, a model is useful only if it comes with an efﬁcient Policy

that complies with RSS — in particular an

action that looks innocent at the current moment might lead to a catastrophic event in the far future (“butterﬂy effect”).

We prove that our deﬁnition of RSS is useful by constructing a set of local constraints on the short-term future that

guarantees Safety for the entire future.

Our second contribution evolves around the introduction of a “semantic” language that consists of units, measure-

ments, and action space, and speciﬁcation as to how they are incorporated into Planning, Sensing and Actuation of the

AV. To get a sense of what we mean by Semantics, consider how a human taking driving lessons is instructed to think

about “driving policy”. These instructions are not geometric — they do not take the form “drive 13.7 meters at the

current speed and then accelerate at a rate of 0.8 m/s

”. Instead, the instructions are of a semantic nature — “follow

the car in front of you” or “overtake that car on your left”. The language of human driving policy is about longitudinal

and lateral goals rather than through geometric units of acceleration vectors. We develop a formal Semantic language

and show that the Semantic model is crucial on multiple fronts connected to the computational complexity of Planning

that do not scale up exponentially with time and number of agents, to the manner in which Safety and Comfort interact,

to the way the computation of sensing is deﬁned and the speciﬁcation of sensor modalities and how they interact in

a fusion methodology. We show how the resulting fusion methodology (based on the semantic language) guarantees

the RSS model to the required 10

−9

probability of fatality, per one hour of driving, while performing only ofﬂine

a function that maps the “sensing state” to an action.

validation over a dataset of the order of 10

hours of driving data.

Speciﬁcally, we show that in a reinforcement learning setting we can deﬁne the Q function

over actions deﬁned

over a semantic space in which the number of trajectories to be inspected at any given time is bounded by 10

regardless

of the time horizon used for Planning. Moreover, the signal to noise ratio in this space is high, allowing for effective

machine learning approaches to succeed in modeling the Q function. In the case of computation of sensing, Semantics

allow to distinguish between mistakes that affect Safety versus those mistakes that affect the Comfort of driving. We

deﬁne a PAC model

for sensing which is tied to the Q-function and show how measurement mistakes are incorporated

into Planning in a manner that complies with RSS yet allows to optimize the comfort of driving. The language of

semantics is shown to be crucial for the success of this model as other standard measures of error, such as error with

respect to a global coordinate system, do not comply with the PAC sensing model. In addition, the semantic language

is also a critical enabler for deﬁning HD-maps that can be constructed using low-bandwidth sensing data and thus be

constructed through crowd-sourcing and support scalability.

To summarize, we propose a formal model that covers all the important ingredients of an AV: sense, plan and act.

The model guarantees that from a Planning perspective there will be no accident of the AV’s blame, and also through

a PAC-sensing model guarantees that, with sensing errors, a fusion methodology we present will require only ofﬂine

data collection of a very reasonable magnitude to comply with our Safety model. Furthermore, the model ties together

Safety and Scalability through the language of semantics, thereby providing a complete methodology for a safe and

scalable AV. Finally, it is worth noting that developing an accepted safety model that would be adopted by the industry

and regulatory bodies is a necessary condition for the success of AV — and it is better to do it earlier rather than later.

An early adoption of a safety model will enable the industry to focus resources along a path that will lead to acceptance

of AV. Our RSS model contains parameters whose values need to be determined through discussion with regulatory

bodies and it would serve everyone if this discussion happens early in the process of developing AV solutions.

1.1 Outline

We follow the classic sense-plan-act robotic control methodology. The sensing system is responsible for understanding

the present state of the environment. The planning part, which we call “driving policy”, is responsible for ﬁguring out

what is the best next move (a “what will happen if” type of reasoning). The acting part is responsible for implementing

the plan. The focus of the paper is on the sensing and planning parts (since the acting part is by and large well

understood by control theory).

Mistakes that might lead to accidents can stem from sensing errors or planning errors. Planning is a multi-agent

game, as there are other road users (humans and machines) that react to our actions. Section 2 underscores the problem

with existing approaches to safety guarantees for the planning part, which we call multi-agent safety. We formally

show that statistical estimation of the probability of planning errors must be done “online”, namely, after every update

of the software we must drive billions of miles with the new version. This is clearly infeasible. As an alternative,

in Section 3 we propose a formal mathematical model for multi-agent safety which we call Responsibility Sensitive

Safety (RSS). This model gives a 100% guarantee that the planning module will not make mistakes of the AV’s

responsibility (the notion of “responsibility” is formally deﬁned). Such a model is useless without an efﬁcient way to

validate that a certain driving policy adheres to it. In Section 4 we accompany the RSS deﬁnitions with computationally

efﬁcient methods to validate them.

Mistakes of the sensing system are easier to validate, since sensing can be independent

of the vehicle actions, and

therefore we can validate the probability of a severe sensing error using “ofﬂine” data. But, even collecting ofﬂine

data of more than 10

hours of driving is challenging. In Section 6.2, as part of a description of our sensing system,

we present a fusion approach that can be validated using a signiﬁcantly smaller amount of data.

The rest of the sections deal with Scalability. We outline a complete system that is safe and can scale to millions

of cars. In Section 5 we describe our driving policy, starting from an explanation of why existing methods are so

computationally demanding, and then showing how our semantic-based approach leads to a computationally efﬁcient

A function evaluating the long term quality of performing an action a ∈ A when the agent is at state s ∈ S. Given such a Q-function, the

natural choice of an action is to pick the one with highest quality, π(s) = argmax

Q(s, a).

Probably Approximate Correct (PAC), borrowing Valiant’s PAC-learning terminology.

Strictly speaking, the vehicle actions might change the distribution over the way we view the environment. However, this dependency can be

circumvented by data augmentation techniques.

Figure 1: The central car can do nothing to ensure absolute safety.

driving policy. In Section 6 we connect our semantic driving policy to semantic requirements from the sensing system,

showing how it leads to sensing and mapping requirements that can scale to millions of cars in today’s technology.

2 Multi-agent Safety

This section formalizes our arguments with regard to the necessity of a thorough safety deﬁnition, a minimal standard

to which AV systems must abide.

2.1 Absolute Safety is Impossible

We begin with a naive attempt at deﬁning a safe action-taking by a car, and immediately rule it out as infeasible. We

say an action a taken by a car c is absolutely safe if no accident can follow it at some future time. It is easy to see that

it is impossible to achieve absolute safety, by observing simple driving scenarios, for example, as depicted in Figure 1:

from the central car’s perspective, no action can ensure that none of the surrounding cars will crash into it, and no

action can help it escape this potentially dangerous situation. We emphasize that solving this problem by forbidding

the autonomous car from being in such situations is completely impossible — every highway with more than 2 lanes

will lead to it and forbidding this scenario amounts to staying in the parking lot.

2.2 Deﬁciencies of the Statistical Approach

Since it is impossible to guarantee absolute safety, a popular approach is to propose a statistical guarantee, attempting

to show that self-driving cars are statistically better than human drivers. There are several problems with this approach.

First, as we formally prove below, validating this claim is infeasible. Second, statistical guarantees are not transparent.

What will happen when a self-driving car will kill a little kid? Even if statistically self-driving cars will be involved

in 50% less accidents than the average human driver, will the society be satisﬁed with this statistical argument? We

believe that the statistical approach can be useful only if it leads to several orders of magnitude less accidents, and as

shown in the next paragraph, this is infeasible to achieve.

Validating the statistical claim is infeasible: In the following technical lemma, we formally show why a statistical

approach to validation of an AV system is infeasible, even for validating a simple claim such as “the system makes N

accidents per hour”.

Lemma 1 Let X be a probability space, and A be an event for which Pr(A) = p

< 0.1. Assume we sample m =

i.i.d. samples from X, and let Z =

i=1

[x∈A]

. Then

Pr(Z = 0) ≥ e

−2

Proof We use the inequality 1 − x ≥ e

−2x

(proven for completeness in Appendix A.1), to get

Pr(Z = 0) = (1 − p

)

≥ e

−2p

= e

−2

Corollary 1 Assume an AV system AV

makes an accident with small yet insufﬁcient probability p

. Any deterministic

validation procedure which is given 1/p

samples, will, with constant probability, not distinguish between AV

and a

different AV system AV

which never makes accidents.

In order to gain perspective over the typical values for such probabilities, assume we desire an accident probability of

−9

per hour, and a certain AV system provides only 10

−8

probability. Even if we obtain 10

hours of driving, there

is a constant probability that our validation process will not be able to tell us that the system is dangerous.

Finally, note that this difﬁculty is for invalidating a single, speciﬁc, dangerous AV system. A full solution cannot

be viewed as a single system, as new versions, bug ﬁxes, and updates will be necessary. Each change, even of a single

line of code, generates a new system from a validator’s perspective. Thus, a solution which is validated statistically,

must do so online, over new samples after every small ﬁx or change, to account for the shift in the distribution of states

observed and arrived-at by the new system. Repeatedly and systematically obtaining such a huge number of samples

(and even then, with constant probability, failing to validate the system), is infeasible.

On the problem of validating a simulator: As explained previously, multi-agent safety is hard to validate sta-

tistically as it should be done in an “online” manner. One may argue that by building a simulator of the driving

environment, we can validate the driving policy in the “lab”. The problem with this argument is that validating that

the simulator faithfully represents reality is as hard as validating the policy itself. To see why this is true, suppose that

the simulator has been validated in the sense that applying a driving policy π in the simulator leads to a probability of

an accident of ˆp, and the probability of an accident of π in the real world is p, with |p − ˆp| < . (Say that we need that

 will be smaller than 10

−9

.) Now we replace the driving policy to be π

. Suppose that with probability of 10

−8

, π

performs a weird action that confuses human drivers and leads to an accident. It is possible (and even rather likely)

that this weird action is not modeled in the simulator, without contradicting its superb capabilities in estimating the

performance of the original policy π. This proves that even if a simulator has been shown to reﬂect reality for a driving

policy π, it is not guaranteed to reﬂect reality for another driving policy.

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

In the previous section we have shown that absolute safety is impossible. The implications might seem, at ﬁrst glance,

disappointing. Nothing is absolutely safe. However, we claim that this requirement is too harsh, as evident by the fact

that humans do not get even close to following absolute safety. Instead, humans follow a safety notion that depends

on responsibility. To be more precise, the crucial aspect missing from the absolute safety concept is the non-symmetry

of most accidents - it is usually one of the drivers who is responsible for a crash, and is to be blamed. Clearly, in the

example we consider in Figure 1, the central car is not to be blamed if the left car, for example, suddenly drives into

it. We’d like to formalize the fact that considering its lack of responsibility, a behaviour of staying in its own lane can

be considered safe. In order to do that, we develop a formal concept of “accident responsibility”, which, we argue,

captures the common sense behind human judgement of “who was driving safely and who was responsbile for the

accident”. The premise of RSS is that while self-driving cars might be involved in accidents, they will never cause an

accident.

By and large, RSS is constructed by formalizing the following 4 “common sense” rules:

1. Keep a safe distance from the car in front of you, so that if it will brake abruptly you will be able to stop in time

2. Keep a safe distance from cars on your side, and when performing lateral manoeuvres and cutting-in to another

car’s trajectory, you must leave the other car enough space to respond

剩余32页未读，继续阅读

评论收藏

内容反馈

heshimin

粉丝: 0
资源: 7

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

最新资源

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

Mobileye EyeQ技术对比

Self-Driving Cars A Survey(自动驾驶综述)

Mobileye 5 - 御眼安装说明书

Map.Framework.A.Formal.Model.of.Maps

An Introduction to Formal Languages and Automata - 5th Edition - 2011

On a problem of formal logic___ramsey___1928

[rtps]formal-19-04-03-rtps1.pdf

study of implicator-conjunctor-based and noise-tolerant fuzzy rough sets

Formal Specification and Documentation using Z - A Case Study Approach.rar

Formal Correctness of Security Protocols

Formal Syntax And Semantics of Programming Languages

Theory of Computation Formal Languages, Automata, and Complexity (高清扫描版)

Hardware-Software Co-Design of Embedded Systems: The POLIS Approach

雷蛇PUBG鼠标宏-雷蛇鼠标驱动

Synaptics病毒专杀工具

WishRecy数据恢复软件

软件测试实战项目(Web项目)

VMware Workstation Pro 安装包

EXE一机一码打包加密大师1.5.0 (解压密码1234)

双闭环直流调速系统仿真

最新资源

On a problem of formal logic_ramsey_1928