The Foretellix Blog

Summary: Here is a list of papers I read lately about verifying Autonomous Vehicles. For each, I say why I think it is interesting.

These papers all start with something like “AVs are upon us, so they’d better be safe and well-verified”, and then go on to explain their (very diverse) ideas about how to do that. I was mainly interested in questions like which scenarios they are trying to verify and why, how they try to reach corner cases, which simulators they use, and any special insights.

Note: When I say I read these papers, this is a bit like that old “library” comic skit:

Hostess (showing guests her huge library): Yes, I read all these books
Guest (opening a book at random): So you read all of “War and Peace”?
Hostess: Oh, there are also words inside?

I am that hostess: For some of these papers, I just scanned through them (and skipped most of the math). Anyway, here we go:

Zofka et al.: Testing and Validating High Level Components for Automated Driving: Simulation Framework for Traffic Scenarios

Talks about the various AV simulators, and makes the point that they all have their issues. Thus, one needs to use several of these, each with a different verification focus. His figure 3 illustrates this.

They eventually end up using SUMO (for the general traffic environment) connected to ROS/Gazebo (for the DUT and sensor inputs).

BTW, ROS seems be in quite a few of those AV simulation environments. Consider figure 1 below (taken from this post):

Here are some choices people seem to have made regarding “what’s in the DUT and how does it connect to the verification environment”:

• The Zofka paper, Autoware, Righthook: Input via data shortcut, output is new state, interface via sockets (ROS topics)
• Udacity’s simulator: Input via data shortcut, output is actions, interface via sockets
• Test tracks: The DUT is the whole car, interface via actual sensing

Zhao’s PhD thesis: Accelerated Evaluation of Automated Vehicles

In general, he talks not about “finding unknown bugs”, but rather about “finding bad tuning of parameters” (e.g. being too aggressive when doing an unprotected left turn).

He talks about using Importance Sampling – a technique for rare-event-simulation. Here is his suggestion:

1) Collect a large quantity of naturalistic driving data. 2) Extract events that have potential multi-vehicle conflicts. 3) Model the conflict driving scenarios using stochastic models. 4) Reduce the non-safety-critical events by skewing the probability density functions. 5) Conduct Monte Carlo simulations with the skewed (accelerated) probability density function, resulting in more intense interactions between the AV and HVs. 6) “Skew back” the simulation results to calculate the performance of AVs under naturalistic driving xxii conditions. The proposed approach can be used in computer simulations, human-in-the loop tests with driving simulators, hardware-in-the-loop tests, or vehicle tests

Figure 7 of the other Zhao paper mentioned below illustrates it well. The kinds of challenges this technique could be good for are:

i) Challenge in sensing/detection (e.g., fog, snow, low light)
ii) Challenge in perception (e.g., hand gesture, eye contact, blinking lights)
iii) Aggression of surrounding vehicles/pedestrians/pedal-cyclists
(e.g., running red light, cut-in, jaywalk)
iv) Challenge in making decisions (e.g., low confidence, multiple threats)
v) Challenge due to lower (than normal) control authorities
(e.g., slippery roads, heavy vehicle load)

He freely admits at the end that this technique is not good for finding e.g. SW bugs, and says:

Four possible approaches can be used in the future to find test scenarios for AVs: i) Brainstorming, ii) Crowdsourcing, iii) Analysis of existing crash databases, iv) Analysis of naturalistic driving databases.

He does not mention CDV-style testing as an alternative. I discussed this whole area of “assessing safety as related to known issues” vs. “finding bugs you don’t know about” in this post, and I think this area is currently under-researched.

He talks about a “Worst-case scenario evaluation technique” (as an alternative to what he is doing). I did not know this specific technique – perhaps superseded by hybrid reachability analysis I described here? He talks about getting faster to dangerous situations via the “Cross Entropy method” which I did not fully understand but seems significant.

Zhao et al.: Towards Secure and Safe Appified Automated Vehicles

Much of the material is similar to Zhao’s PhD thesis above. The (somewhat scary) premise of this paper is that there will be (multi-vendor) AV apps, and this talks about verifying them (both safety and security verification). It has a lot of good references. They claim (I think wrongly) that most vehicle OSes are based on ROS. Finally, they explain how much of the verification can use the standard CAN bus – an important point.

Huang et al.: Autonomous Vehicles Testing Methods Review (behind IEEE paywall)

A review of the various test techniques. Their figure 1 is a good illustration of x-in-the-loop testing. They describe various test tracks (M-city in the US, iVPC in China) and their various facilities.

They talk about the need to calibrate sensor models to reality, but do not elaborate much. They talk a lot about Vehicle in the Loop – I assume this is stationary actual vehicle in a virtual environment – one of the execution platforms I described here.

They mention “thousands” of scenarios – seems like a small number (but perhaps they mean “scenario templates”). The description of sequencing of various small scenarios (e.g. figure 5) is nice.

Huang et al.: Intelligence Testing for Autonomous Vehicles: A New Approach (behind IEEE paywall)

This is by the same authors as the paper above. They talk (e.g. in figure 3) about how to combine scenarios (e.g.  “urban travelling”), tasks (e.g. “lane changing”) function atoms (e.g. “traffic light detection”). This is an important point: verification scenario creation (and coverage definition) should span / mix all of these in an intelligent way.

Also: they mention the fact that one needs to match the verified functionality with the current state of an AV prototype (which may lack some functionality). They also talk about verifying non-safety parameters like comfort and efficiency

Wachenfeld and Winner: Virtual Assessment of Automation in Field Operation A New Runtime Validation Method

Note: This is part of workshop proceedings, which is mostly in German.

Suggests a technique (which I assume some, like Tesla, may be already using): Have autonomous cars roaming city streets in non-autonomous mode (i.e. with a real driver). And have the AV logic produce in parallel what it would have done, and check that.

This obviously works only in small, a-few-seconds slices (because the actual trajectory of the vehicle will then diverge from what the AV requested, assuming the human driver drives somewhat differently). But it is still useful.

The Claytex data sheet: Virtual Testing of Autonomous Vehicles

Claytex, a UK company, seem to be building a virtual testing env based on Dymola (part of, and also ancestor of, Modelica). They seem to use “functional and predictive models” – interesting. They use rFpro, which I mentioned here.

Greenyer et al.: Scenario-based Specification of Car-to-X systems

This is one of a set of papers on ScenarioTools, a tool based on David Harel’s LSC notation for combining multiple scenario “snippets” into a single execution. This is an important topic when creating scenarios.

Nilsson’s PhD thesis: Computational Verification Methods for Automotive Safety Systems

As I said in a previous post, this is a good introduction to AV / ADAS verification by Jonas Nilsson of Volvo (long, best viewed in Acrobat Reader). Lots of good stuff, and a good introduction to the concepts.

The formal-related papers mentioned in this post

As I said in the post, there seems to be hope for some limited FV in that domain, but it seems mostly non-conventional FV (e.g. hybrid reachability analysis).

Notes

I’d like to thank Gil Amid, Thomas (Blake) French and Amiram Yehudai for commenting on previous versions of this post.