A formal critique of OpenScenario 2.0

OpenScenario 2.0 is out! The Good, the Bad, and the Ugly. Yet the single biggest problem is the lack of coherence.

OpenScenario is an ongoing standard development project to leverage the scenario based testing of automated driving systems across the industry using a common and well-defined scenario description format. The first version of OpenScenario (dubbed 1.x series) has standardized a lower-level imperative language format to describe desired behaviors of traffic actors. Then driving simulators can execute these scenarios and challenge the system under test connected to the simulator. While this format is useful to describe individual concrete scenarios, large-scale testing workflows requires huge amount of test scenarios and it is impossible to feed the machine by writing them one by one manually. This is the point where we need the power of abstraction.

The development of OpenScenario 2.x series started more than two years ago with a goal of bringing abstract scenarios and workflows to enable large-scale simulation based testing for the automotive industry. After some months of delays, the first release candidate of OpenScenario 2.x series is recently made available to the public. You can find the first public release candidate here.

My review is intended to focus on the formal aspects of the OpenScenario 2.0 (OSC2.0) specifications, mainly described in this section. Since the foundations have important consequences on the implementation, Some background on formal languages would be definitely helpful, especially on regular expressions.

The Good

The OSC2.0 brings a set of powerful concepts to extensively test and validate highly automated driving systems in virtual environments. It aims to integrate industry-best practices in software testing, digital circuit verification, and system engineering as well as the research on timed systems and robotics. Surely none of these concepts is trivial and achieving a simple, coherent, and implementable scenario format is equivalent to the work required for multiple PhD theses… This goes beyond a mere standardization project.

Abstraction, abstraction, abstraction

We can safely say that the ability to write abstract scenarios is the single most beneficial part of the OpenScenario 2.0. This must be emphasized as much as possible because the current scene of V&V for automated driving functions suffer a great productivity problem indicating the lack of effective tools and techniques to help engineers.

However, raising the abstraction levels is not so easy and often require a mental jump into unknown territories. We should not be scared of abstraction as sometimes I feel from the discussions that it is the case. Yes, there is a risk of abstracting too much, as we seen mathematical sciences (Hello, String Theory). But we always have to keep our abstractions grounded in reality. This is the key for any useful abstraction. Said these general remarks and warnings, let’s go back to abstracting driving scenarios.

Fortunately we do not have to invent everything. The history of computer science is the history of abstraction. That must be our guide, always.

Traces on the real time axis, their sets and acceptance

Formal languages and automata theory is one of the cornerstones of computer science (CS) and have taught in virtually all CS programs. Although we focus too much on text processing in these courses, this is indeed a theory for all sorts of sequences. Therefore, it is applicable for sequences of textual characters as well as sequences of messages coming from simulators and automated driving systems.

One thing the OSC2.0 does well is in starting the discussion on the connection between driving scenarios and the computer science theory. A trace in the OSC2.0 terminology corresponds to the a word in the classical theory of formal languages. The OSC2.0 describes the scenario as sets of traces accepted by the specification. This exactly corresponds to how we define (formal) language. If we continue in this direction, then an OSC2.0 scenario specification must be essentially a regular expression-like object that represents sets of traces in a symbolic manner. Once we do such mental mapping between the OSC2.0 and classical theory, then it is obvious that we can use also scenarios to check, search, mine patterns on sequences of system states as much as we use regular expression over textual sequences. These are powerful ideas.

Porting ideas from the classical text processing to temporal behaviors have their own difficulties for sure. Concurrent nature of temporal sequences as well as the existence of timing constraints have no equivalent in the textual case but these are challenges to be solved. You can read more about that in my PhD thesis introducing timed pattern matching dealing with these issues.

The Bad

I have mentioned the importance of computer science theories in the previous section but also many mistakes are made in the 30+ years of timed systems research and in the 60+ years of programming language and compiler design. We all want that the OpenScenario 2.0 project would not repeat them as much as possible in its quest. This section lists the most important red flags in the OpenScenario 2.0 document from my point of view as someone who have designed timed specification languages and developed several algorithms to monitor them at runtime.

Continuous time model is bad

Currently the OSC2.0 formally defines a (behavior) trace as a function from a continuous time axis to the set of states. This seems the most natural and innocent choice after all, right? Believe it or not, the choice of continuous time model has serious drawbacks on the project including unimplementatability, fragmentation, and endless fruitless discussions.

Starting from the obvious, no simulator, logger, or any other physical device will give you a truly continuous trace to work on. Hereby truly continuous traces exist only in the realm of high mathematics. Therefore, in practice, we have to work with mapped sequences of time intervals where might be be open, closed, or half-closed depending on the inclusion of the endpoint. Problem solved? No — because now we have to define all temporal (composition) operations over all types of intervals and their permutations. But this is useless, no benefit for a great deal of complications as there is no observable (measurable) difference between an interval of [a,b] and an interval of [a,b). If this is done, it is done only for the name of mathematical rigor. And I have no appreciation of doing math for the sake of doing math.

Alternatively and more practically, we can pick a single type of interval (such as right-closed-left-open) and define every operation based on that. Although this is not mathematically rigorous, this is the sanest option in practice when squaring circles. But the question: why do you start with circles if you want squares? Simply define squares. Squares are no less formal than circles.

So this means that we must use the theory of sequences if we use sequences all the time. Then a non-continuous definition for traces would be:

A trace is a sequence of tuples (dt, S) that represents uniform temporal periods where dt denotes the duration of the period and S is a system state.

This is after all what we have in reality. Open Simulation Interface (OSI) traces, ROSbags, or other message logging formats are already there as examples. Also timestamps can be used instead of duration values in traces, assuming field values persist until next segment. Simply these are items for the standardization, not the quirks of Measure Zero.

Mixing declarative and imperative semantics is bad

The OSC2.0 document states that the semantics definition is of declarative nature and the composition operations are defined using the logical operation as expected (while keeping my reservations on the time model and unfamiliar parallel composition). However, that’s not all.

The current version of OpenScenario 2.0 mixes the declarative and imperative semantics in a weird way. The problematic part here is the very concept of scenario invocation/termination, which is normally belongs to imperative languages but seems to be placed at the heart of the OSC2.0. I have added more on invocations later but a declarative language has nothing with such imperative verbs like drive, do, and wait. Surely we can interpret these imperatives passively as predicates of is_driving, is_doing, is_waiting but the values of these predicates must be deduced from the trace and the trace only. Providing a back door (via other mechanisms) that affects the acceptance is against the whole idea.

I can see the need for some imperatives though but we must be careful. Below I will give two good examples that achieve a clean separation of declarative and imperative mechanisms inside the same system. The first one is the AWK programming language where you can read more here. And the other is a classical academic paper that gives an excellent overview of the problem and some solutions.

The AWK program is a command-line utility for line-oriented text processing. The interesting part for us is the way AWK specify the program with a (declarative) pattern and an action block (separated by curly braces) in the form of /pattern/ {action}. The execution could not be simpler: perform the action if the line matches the pattern. Declarative and imperative paradigms are separate yet working coherently.

The article Declarative Past and Imperative Future by Dov Gabbay is even more relevant as it does explicitly talk about temporal sequences rather than lines of text files. The key take here is that we can declare and check what is happened in the past, and imperative statements will tell us what to do in the future to generate the desired behavior. Again declarative and imperative paradigms are separate yet working coherently. There is more that Gabbay also proved that any temporal logic formula can be rewritten in the form of past_specs => future_specs , which is known as his Separation Theorem. That gives mathematical guarantees on that we do not lose anything by separating the past and future, declarative and imperative.

The Ugly

Unlike the hard takes of the previous section, I list in this section points that fall under could-be-designed better category. Since these points concern a large portion of the OpenScenario specification, I have to sadly say that the OpenScenario 2.0 is an not a well designed elegant language in its current form. Syntactic constructs, or other cosmetics, are easy to fix (but still must be addressed early) but I am interested more in the language design itself in this section.

Actions

An action is the OSC2.0 is defined to be a fundamental, non-decomposable behavior of an actor (in key terminology). But also remember that we also defined a trace over actor system states (in formal semantics). Normally we expect a consistency between these definitions. Could you see the problem: What is the fundamental unit of behaviors then? Actions or system states? Are they the same? Is there a relation between them? Do actions represent sets of traces like scenarios? Then what is the conceptual difference between actions and scenarios then? Are actions just basic predefined scenarios? In short, the term atomic behavior used in the document to describe actions is too vague and must be defined in terms of system states. Then we can finally answer what traces are accepted by the action drive.

The document states that actions are platform-specific and this is outside the scope of the OpenScenario. But this statement is problematic because we need the meaning of every action in order to compose them. We cannot simply leave it as a magical construct. This meaning must be given as a set of traces. This is the contract. Only after that, the implementation of actions could be platform-specific and even black-box. So actions must be seen as a predefined (maybe-black box) scenarios that have the similar acceptance definitions. This is too important to be missed in the document. Otherwise, no two simulator that uses the same scenario would behave the same.

Finally, I want to add that the predefined action model would be less and less useful as the level of autonomy increases. The reason is that the autonomy is tested better when the other actors are also autonomous, follow their own goals, and show emergent behaviors. A traffic actor performing predefined actions cannot react to or challenge our system adequately beyond a certain point. Therefore, predefined actions can be used but defining scenarios only based on them will not work for more ambitious goals. Eventually there would be only predicates…

Process-based Execution Model

If the OSC2.0 were a truly declarative language, there would be nothing to say here about execution models since a declarative language does not specify anything about the execution. Yes, some execution models may be better for the task but this is not the concern of the declarative specification. For example: Does a classical regular expression tell you how to implement a pattern matcher? Nope— It only describes what string is acceptable or not. We can implement pattern matchers using backtracking, automata, term rewriting, or sequential circuits, which are all different execution models.

I cannot say the OSC2.0 favor a certain implementation, but it does definitely favors a certain (invocation or process-based) execution model as it models scenarios as processes. This is an important choice first of all. We know such models are common in concurrent and distributed systems and they can be formally described using a process calculus. This is all fine. Yet the problem here is that a (computer) process is meant to do some computation in somewhat isolated fashion. Sure it can communicate with other processes via messages (events, in the OSC2.0) yet this is still a loose way of communication. I would argue here that a scenario execution requires much denser interaction with the environment. It should not be: fire a scenario, wait a scenario, terminate a scenario. This is ultimately limited for highly reactive systems. If the case, you need to try to limit the specification in order to match it. And that’s what is happening for the OSC2.0. It is the reason for several ugly requirements like event-trace consistency or events affecting the acceptance. The root cause is the invocation based execution model and it is embedded into the language.

The Minor

• Non-commutative parallel composition operation looks bad. Technically, I would only call the equal relation as the parallel composition. The other cases of overlapping periods must go to interval-based temporal logic operations. Yet this is much better as an extension.
• In my opinion, the OSC2.0 pushes too hard to become a full-fledged programming language. Many known but time-consuming problems would be immediately solved if the OSC2.0 were a Python library or an API specification instead of an external DSL.
• Negative duration values are always a bad idea…

Conclusion

I have to admit that the initial concept paper of the OpenScenario 2.0 was far more coherent than the release candidate. Perhaps I had overlooked the incoherent portions of the concept and thought it would be polished until we finally had a beautiful scenario format at the end. But apparently this is not the case. I think the promise of backward compatibility with the 1.x series is one reason for that. Most of my criticisms stem from the fact that the document takes some concept from one paradigm, try to stitch it to the another, and fails. Imperative actions inside declarative statements, events traces next to state traces, actions vs scenarios. Simply they do not fit well together. I can conclude that the lack of coherence is the single biggest issue regarding the current document.

Finally, some parallel composed temporal behaviors