Using Ontologies for the Formalization and Recognition of Criticality for Automated Driving

Lukas Westhofen,
Christian Neurohr,
Martin Butz,
Maike Scholtes,
and Michael Schuldes
The research leading to these results is funded by the German Federal Ministry for Economic Affairs and Climate Action within the project 'Verification & Validation Methods for Automated Vehicles in Urban Environments'. The authors would like to thank the consortium for the successful cooperation.
Lukas Westhofen and Christian Neurohr are with the German Aerospace Center (DLR) e.V., Institute of Systems Engineering for Future Mobility, Oldenburg, Germany (e-mail: firstname.lastname@dlr.de).
Martin Butz is with the Robert Bosch GmbH, Renningen, Germany (e-mail: martin.butz@de.bosch.com).
Maike Scholtes is with the RWTH Aachen, Germany (e-mail: maike.scholtes@rwth-aachen.de).
Michael Schuldes is with the ika, Aachen, Germany (e-mail: michael.schuldes@ika.rwth-aachen.de).

Knowledge representation and reasoning has a long history of examining how knowledge can be formalized, interpreted, and semantically analyzed by machines.
In the area of automated vehicles, recent advances suggest the ability to formalize and leverage relevant knowledge as a key enabler in handling the inherently open and complex context of the traffic world.
This paper demonstrates ontologies to be a powerful tool for a) modeling and formalization of and b) reasoning about factors associated with criticality in the environment of automated vehicles.
For this, we leverage the well-known 6-Layer Model to create a formal representation of the environmental context.
Within this representation, an ontology models domain knowledge as logical axioms, enabling deduction on the presence of critical factors within traffic scenarios.
For executing automated analyses, a joint description logic and rule reasoner is used in combination with an a-priori predicate augmentation.
We elaborate on the modular approach, present a publicly available implementation, and exemplarily evaluate the method by means of a large-scale drone data set of urban traffic scenarios.

Intelligent vehicles, Safety, Knowledge representation, Inference mechanisms

§ INTRODUCTION

Pursuing the feat of automated driving – i.e. taking human operators out of the control loop – has sparked scientific interest for several decades.
Pushed by pioneers like Ernst Dickmanns as early as the 1980s, it peaked in prestigious research projects such as PROMETHEUS <cit.>.
Despite focused industry efforts and assertive claims, the dream of full driving automation on urban roads has not been realized ever since.

Currently, systems at SAE Level 3 <cit.> – e.g. traffic jam assists – are developed only for highly restricted operational design domains (ODDs).
This indicates that a key barrier lies within both the complexity and openness of less restricted driving contexts as well as their robust perception and subsequent semantic understanding.
Consequentially, the development of an automated driving system (ADS) mature enough to overcome these challenges can only be mastered by including stakeholders of a diverse set of disciplines.

It is hence imperative to identify a common conceptualization of the ODD across all parties involved in the system's development and operation.
Furthermore, this conceptualization must also be comprehensible for machines, as it forms the basis of the interaction for all subsystems of the ADS with the real world.
While for restricted and highly regulated domains such as highways, a model may be feasibly constructed in a comparatively short time, an urban context has two properties impeding this approach.
Firstly, it is highly complex, meaning that individuals in such scenarios can be of a vast amount of possible types, each of them possessing a multitude of potentially relevant properties possibly with uncountably large value ranges.
Secondly, the urban context is open, meaning that new classes, properties, and behaviors of individuals can emerge rapidly without prior notice or time to respond.
Therefore, a central question arises: How to construct a machine-comprehensible model of open and complex driving contexts?

Earlier work suggests that such operational domains (ODs) can be structured through the identification and subsequent explanation of safety-relevant factors, called criticality phenomena <cit.>.
This knowledge can then be constituted to a context model, in turn enabling semantic reasoning.

For example, such reasoning allows for an automated assessment of the situational risk.
In the area of automated driving, risk evaluations are often performed using criticality metrics <cit.>, e.g. to guide decisions of the driving automation towards states of minimal risk or to derive relevant test cases within a safety case.
Essentially, such metrics measure 'late' factors that closely precede traffic conflicts, e.g. (predicted) small temporal and spatial distances.
Naturally, the question arises: Can the previously derived criticality phenomena be simultaneously used to approximate the actual risk earlier?

Exemplary interaction of criticality phenomena and metrics in traffic conflicts, based on an ontology.
Criticality phenomena are hatched, metrics are white. TTB is the time to brake, $a_\mathit{req}$ is the maximum required deceleration.

<ref> sketches an example of how criticality phenomena and metrics interact.
Here, the presence of kindergartens goes along with the presence of children alongside the driving area at pick-up times.
The resulting possibility of traffic participants with unpredictable behaviors can be, statistically speaking, antecedent to an increased maximum required deceleration ($a_\mathit{req}$) or decreased time to brake (TTB).
In total, the recognition and analysis of combinations of factors like the presence of kindergartens, children, and certain daytimes, can lead to a more timely and robust comprehension of the situational risk.

The work at hand addresses the two challenges directly visible in <ref>:
Firstly, building an underlying ontology and secondly, leveraging it to reason on criticality phenomena.
The core of our work is based on the family of well-understood description logics (DLs) as a formalism to construct an ontology.
Contemporary approaches suggest the use of ontologies for situation comprehension within ADSs, but lack a justification behind the selection and formalization of relevant concepts.
As to bridge this gap, we propose to integrate the construction of the ontology into the verification and validation process of an ADS.
More specifically, this ontology is iteratively refined by expressing the criticality phenomena using DL axioms and rules.
Finally, the approach enables us to analyze these factors using a statistical evaluation of their association with traffic conflicts as measured by criticality metrics.

To summarize, the main contributions of this work are

* to provide a method that enables the

* construction of an ontology based on a set of criticality phenomena,

* formalization of such factors based on the ontology,

* inference of their presence in traffic scenarios, and

* an open-source implementation of the method, including

* the Automotive Urban Traffic Ontology, and

* an ontology-based tooling that recognizes criticality phenomena in traffic scenario data.

After presenting related work in <ref>, <ref> introduces the foundations of our approach, namely the methodical criticality analysis and the formalisms of description logics and rules.
The method to both construct an ontology as well as to infer the presence of criticality phenomena (first contribution) is the topic of <ref>.
The implemented ontology (second contribution) is portrayed in <ref>, followed by an example on its iterative construction based on the formalization process in <ref>.
To conclude contribution two, <ref> presents our publicly available tooling.
An initial evaluation is provided in <ref>, for which we have exemplarily chosen a drone data set, depicting the usage of this method for an in-depth semantic analysis of data.

§ RELATED WORK

For road traffic, conceptualizations of knowledge have been collected, aggregated, consolidated, and described since the regulation of the traffic domain.
For example, in Germany, there exist harmonized taxonomies and guidelines on the type of objects as well as how they shall be constructed <cit.>.

For automated systems sufficiently intelligent to navigate complex traffic scenarios, the subsequent step is making this aggregated knowledge accessible.

A unified terminology of the basic models – scene, situation, scenario – was defined by Ulbrich et al. <cit.>.
Within those scenarios, it was found that classes of entities could be structured along the so-called 6-Layer Model, a deliberately informal but comprehensive framework <cit.>.
We base the work at hand on these natural-language definitions as well as their classes of entities and provide a formal implementation thereof.
Going into more detail, Czarnecki et al. collected large amounts of structured albeit informal domain knowledge regarding the environment of automated vehicles <cit.>.
Furthermore, several standards present a structured domain model alongside, e.g. ASAM OpenSCENARIO <cit.>.
These sources were considered during the development of our implementation.

Hence, an ontology with formal semantics can be constructed from structured knowledge.

For automated driving, several groups have formalized their domain conceptualizations by means of ontologies to represent both knowledge and data.
This includes the Ronny ontology for intersection situations <cit.>, the Automotive Global Ontology (AGO) <cit.>, an Object-Oriented Framework (OOF) <cit.>, and an approach of Core Ontologies (CO) <cit.>.
Recently, the community initiated standardization efforts for the simulation domain <cit.>.
Three of those ontologies are developed for specific use cases – intersection recognition for Ronny, closed world scenario descriptions for OOF, and automated decision making for CO – while the ontology presented for the work at hand aims to support various competencies.
The AGO provides a knowledge organization framework focused on data labeling, but also includes a methodical approach to derive ontological concepts.
This derivation is based on pre-existing data schemes to foster compatibility for the subsequent labeling use case.
Hence, none of the ontologies considers its systematic integration into a safety case by means of a traceable identification and formalization of concepts w.r.t. the safety-relevant aspects of the OD.
Rather, they represent the particular views and knowledge of the authors and knowledge sources.

Besides formalizing (shared) conceptualizations, research has leveraged the capabilities using logic reasoning on formalized ontologies to facilitate artificial intelligence functionality in ADSs.
For a general semantic interpretation of perceived scenes, approaches have been presented as early as 2006 <cit.>, based on the foundations of prior research in logics for artificial intelligence, including expert systems <cit.> as well as spatial and temporal logics for robotics <cit.> in the 1970s to 1990s.
Applications for automated driving can be traced back to using Ronny on the 2007 DARPA Urban Challenge vehicle AnnieWAY <cit.>, which relies on a plain DL approach for scene inference on road geometries.
We adopt a similar dogma, but also consider scenarios, i.e. the dynamical actions of traffic participants, in the inference process.
Furthermore, our work specifically addresses the problem of lifting concrete domains to abstract ones such that input data becomes suitable for DL reasoning.
Subsequent to Ronny, various ontology-based approaches for situation comprehension and planning components of automated vehicles were proposed.
This includes a turning assistant for urban intersections <cit.> and context-aware speed adaption systems <cit.>.
Furthermore, ontological formalisms were profoundly leveraged by Hülsen et al. in order to interpret the driving context at urban intersections using a combined DL-rule approach. <cit.>.
Their application of ontology-based inference on A-Boxes is related to the evaluation presented in <ref>: They specifically leverage the open world assumption and rely on rules and description logics for situation analysis.
Note, however, that the authors were developing their approach specifically for run time inference.
Reasoning is hence only performed on abstract concepts within a reduced ontology.
Furthermore, this inference approach is purely scene-based, whereas the work at hand aims to show how inference on large ontologies can be performed on complex scenario data at design time.

While these use cases relate to the situation comprehension of an ADS, our approach views ontologies as an inherent cornerstone of a safety case, which is in turn required for homologation.
In the end, a shared ontological model between the stakeholders of the safety case will be necessary.
For this purpose, it is hence insufficient to omit a justification for the selection of concepts, e.g. why to differentiate between a personal mobility device and a bicycle.
This justification can then be used for verifying and validating the situation comprehension of the ADS.
First steps have been made by Jatzkowski et al.  who demonstrated how the relevancy of scene concepts can be derived from abstract system skills <cit.>.
In order to methodically support a safety case, Bagschik and Menzel examined how a knowledge base can be leveraged for automated scene creation <cit.> which in turn can be used to derive test scenarios from keywords <cit.>.
In such a scenario-based verification and validation process, it is essential to assign observed concrete scenarios to scenario classes, an approach coined as tagging in prior work <cit.>.
Albeit all four approaches are methodically integrated into their respective verification and validation processes, they do not highlight the applicability of the underlying logical formalisms for automated reasoning, or leave this issue for future work.
However, it is only due to a logical foundation that a) concepts become rigorously traceable and b) inference can be leveraged for e.g. formal scenario analysis or consistency checks of the domain model (i.e. whether certain axioms are contradictory).

Finally, when moving from risk assessment at design time to dynamic risk assessment, early work shows that ontological reasoning can be employed to quantify risk at run time <cit.>.
Here, a rudimentary and small ontology was used for demonstration purposes, leaving open the methodical construction of larger ontologies necessary to represent complex urban contexts and the handling of issues accompanied by the growth in size in terminological and assertional components.

§ PRELIMINARIES

§.§ Criticality and its Phenomena within the Open Context

The Open Context Problem
An open and complex urban context poses great challenges when aiming to safely deploy an ADS <cit.>.
Therefore, the ISO/DIS 21448 instructs to reduce the set of unknown hazardous scenarios, which can lead to unsafe situations if they are not considered in the design process <cit.>.
This requirement becomes harder to fulfill as the context grows in openness and complexity.

Criticality Analysis
It is therefore imperative to analyze the operational environment prior to system design, which was coined under the term criticality analysis <cit.>.

Its goal is to identify and understand the OD elements that are – independent of the system's realization – safety-relevant for the driving task.
Hence, it uncovers both potential unknown unknowns as well as increases the understanding of known unknowns.
The analysis delivers evidences for OD coverage and decomposition by a) the creation of a finite catalog of abstract scenarios that can be used to identify both requirements on the system behavior and relevant test cases, b) an argumentation about the coverage of such a catalog w.r.t. the OD, and c) a downstream effort reduction by providing generic statements about the safety-relevant elements of the OD.

To this end, one is specifically concerned with identifying situations of high accident risk.
Hence, criticality can roughly be understood as a function of the probability and severity of the occurrence of any accident given a traffic situation.
We build upon the following definitions from prior work.

Criticality is the combined risk of the involved actors when the situation is continued.

Aspects of criticality are measured using criticality metrics:
A criticality metric is a function $\kappa: \mathcal{S} \times \mathbb{R}^+ \rightarrow O$ that measures for a given traffic scene $S \in \mathcal{S}$ at a time $t \in \mathbb{R}^+$ aspects of criticality on a predetermined scale of measurement $O \subseteq \mathbb{R} \cup {-\infty, +\infty}$. Scenario level criticality metrics extend this definition from scenes to scenarios.

Criticality metrics measure late factors present in the chain of events leading to traffic conflicts.
Consequentially, a measurement of factors preceding in turn increases in criticality metrics can be fruitful for purposefully generating evidences in a safety case, e.g. to identify factors of high relevance.
We refer to these factors as criticality phenomena.
A criticality phenomenon is a single influencing factor, or a combination thereof, that is associated with increased criticality in a scene or scenario.

This work examines how a formalization of such phenomena can be leveraged for the construction of an ontology as well as for an analysis of criticality in traffic scenarios.
The construction of such an ontology is inherently tied to a safety case, as elaborated in <ref>.
A subsequent ontology-based analysis contributes, in turn, to the single steps of a verification and validation process, as illustrated in <ref>.

§.§ Knowledge Representation and Reasoning

Knowledge representation and reasoning concerns formalisms that model expert knowledge as well as methods thereon that enable machines to reason about conceptualizations of the real world.
We base our approach on those foundations, which are concisely introduced in the following.

Ontologies and Description Logics

The term ontology originates from philosophy, denoting the discipline of studying things, their existence, and human conceptualizations thereof.
Based on this, the fields of formal logic and computer science specify an ontology as a formalization of a conceptualization of a shared mental model of a certain aspect of the real world (often called the domain of discourse).

Such a shared formal model of the domain of discourse enables multiple stakeholder to agree on a common and consistent terminological basis.
This is specifically important considering the multiple points of failure in information exchange:
Different symbols can stand for the same real-world things, and different real-world things can be referred to by the same symbols.
Furthermore, a layer of indirection is introduced by the interpreter through first resolving symbols to certain concepts, which is eventually resolved to a (potentially unintendedly different) real-world object.
Ontologies make those relations explicit: they clearly assign semantics to concepts which are unambiguously denoted by a set of symbols.
They can also aid in making the ambiguities of natural language explicit.
Having a consistent and commonly understood ontology therefore mitigates mismatches in the semantics of used symbols and concepts among all parties.

DLs is a family of formal logics to represent such ontologies as a decidable fragment of first order logic.

At the core of DLs are so-called concepts (or classes), which are semantically defined as sets of individuals, and roles (or relations), which are, analogously, sets of tuples of individuals.
Individuals are concrete, existing instances within the domain of interest <cit.>.
All three can be referred to by their names, i.e. symbols.

A vocabulary is a triple $\mathsf{N} = (\mathsf{N}_R, \mathsf{N}_C, \mathsf{N}_I)$ of sets of role names $\mathsf{N}_R$, concept names $\mathsf{N}_C$, and individual names $\mathsf{N}_I$.

An ontology over a vocabulary $\mathsf{N}$ is a tuple $\mathcal{O} = (\mathcal{T}, \mathcal{A})$, where

* $\mathcal{T}$ is a finite set of terminological assertions (called T-Box), namely general concepts inclusions (GCIs) such as $\mathtt{C} \sqsubseteq \mathtt{C'}$ for two concept names $\mathtt{C}, \mathtt{C'} \in \mathsf{N}_C$ as well as role inclusion axioms (RIAs) such as $\mathtt{r} \sqsubseteq \mathtt{r'}$ for two role names $\mathtt{r}, \mathtt{r'} \in \mathsf{N}_R$, and

* $\mathcal{A}$ is a finite set of concept and role assertions (CAs and RAs) (called A-Box), such as $\mathtt{C}(\mathtt{x})$ and $\mathtt{r}(\mathtt{x}, \mathtt{x'})$ for $\mathtt{x}, \mathtt{x'} \in \mathsf{N}_I$, $\mathtt{C} \in \mathsf{N}_C$, and $\mathtt{r} \in \mathsf{N}_R$.

Note that the possible logical operators that can be used to define the right- and left-hand sides of the GCIs and RIAs in $\mathcal{T}$ are determined by the given DL fragment, consisting e.g. of negation ($\neg$), intersection ($\sqcap$), union ($\sqcup$), and universal ($\forall \mathtt{r}.\mathtt{C}$) and existential ($\exists \mathtt{r}.\mathtt{C}$) role quantification.
Semantically, the operators are defined in terms of an interpretation $\mathcal{I} = (\Delta^\mathcal{I}, \cdot^\mathcal{I})$, where $\Delta^\mathcal{I}$ is the interpretation domain and $\cdot^\mathcal{I}$ an interpretation function assigning each operator a subset of $\Delta^\mathcal{I}$ or $\Delta^\mathcal{I} \times \Delta^\mathcal{I}$.
For example, we say that $\mathtt{C} \sqsubseteq \mathtt{C'}$ iff for all interpretations $\mathcal{I}$ it holds that $\mathtt{C}^\mathcal{I} \subseteq \mathtt{C'}^\mathcal{I}$.
$\top, \bot \in \mathsf{N}_C$ are unique names for the top (universally true) and bottom (universally false) concept with $\top^\mathcal{I} = \Delta^\mathcal{I} \wedge \bot^\mathcal{I} = \emptyset\ \forall\ \mathcal{I}$.
The work omits further details and assumes some familiarity with DLs <cit.>.

For our purposes, we additionally define the special functions $\mathit{con}: \mathcal{T} \rightarrow 2^{\mathsf{N}_C}$, $\mathit{rol}: \mathcal{T} \rightarrow 2^{\mathsf{N}_R}$, and $\mathit{ind}: \mathcal{A} \rightarrow 2^{\mathsf{N}_I}$ which retrieve the set of employed roles, concepts, and individual names from the given GCI, RIA, CA, and RA respectively.
In conjunction, we say $\mathit{nms} \coloneqq \mathit{rol} \cup \mathit{con} \cup \mathit{ind}$.
Furthermore, the set of T-Box axioms that involve a concept or a role $\mathtt{X}$ is defined as $\mathit{axs}(\mathtt{X}) \coloneqq \{ \alpha \in \mathcal{T} \,|\, \mathtt{X} \in \mathit{nms}(\alpha) \}$.

The modeled axioms of a DL ontology are often enhanced by rules in form of a set of Horn clauses <cit.>.

For a given ontology $\mathcal{O}$ over a vocabulary $\mathsf{N}$, a rule atom over a set of variables names $V$ is an expression of the form

* $\mathtt{C}(v)$,

* $\mathtt{r}(v, v')$,

* $v = v' \circ v''$ or $v \sim v''$ for $\circ \in \{+, -, \cdot, \div\}$ and
$\sim \in \{<, \leq, =, \neq, \geq, >\}$,

where $\mathtt{C} \in \mathsf{N}_C$, $\mathtt{r} \in \mathsf{N}_R$, and $v, v' \in V$, $v'' \in V \cup \mathbb{Q}$.

For a given ontology $\mathcal{O}$ over a vocabulary $\mathsf{N}$, a rule over variables $V$ is a Horn clause of a set of antecedent rule atoms $R_A$ over $V$ and precedent rule atoms $R_P$ over $V' \subseteq V$, i.e. of the form $\bigwedge_{r_a \in R_A} r_a \implies \bigwedge_{r_p \in R_P} r_p$.
Semantically, they are defined by universal quantification over the variables of $V$.

A reasoner can then deduct new assertions from the given ontology, and is therefore able to check propositions and answer queries.
For example, it can deduce the axiom $\mathtt{C'}(\mathtt{x})$ from the previously sketched axioms in <ref>.
Generally, we denote the entailment of an axiom $\alpha$ from an ontology $\mathcal{O}$ by $\mathcal{O} \models \alpha$.

Based on this, a subset of relevant decision problems is:

* a concept is inconsistent, i.e. $\mathtt{C} \sqsubseteq \bot$,

* a concept subsumes another, i.e. $\mathtt{C} \sqsubseteq \mathtt{C'}$,

* two concepts are equivalent, i.e. $\mathtt{C} \sqsubseteq \mathtt{C'} \wedge \mathtt{C'} \sqsubseteq \mathtt{C}$ (concisely, $\mathtt{C} \equiv \mathtt{C'}$), and

* membership of a given individual to a concept, i.e. $\mathtt{C}(\mathtt{x})$.

Furthermore, knowledge bases can be queried, i.e. retrieving all individuals $\mathtt{x}: \mathtt{C}(\mathtt{x})$.
These reasoning inquiries are substantiated to our domain of discourse in <ref>.

§ REASONING ABOUT CRITICALITY FOR OPEN CONTEXT SYSTEMS

§.§ Ontologies for Structuring an Open and Complex Context

The necessity of tackling the open context problem has been introduced in <ref>, for which we propose to use ontologies as introduced in <ref>.
In its core, ontologies are based on the so-called open-world assumption, stating that if $\mathcal{O} \not\models \alpha$ then $\mathcal{O} \models \neg \alpha$ does not necessarily hold.
Therefore, ontologies distinguish between the actual truth value of a statement and the information about it that can be inferred from the current knowledge, mitigating the problem of incomplete knowledge about the open context.
Here, the openness refers to the inherent existence of things possibly unknown at design time, e.g. a traffic participant may not be detected by a machine learning perception system due to its anomalistic shape (such as  costumes during carnivals).
Although a reasoner may find that, based on the knowledge retrieved from the perception system, $\mathcal{O} \not\models (\exists \mathtt{has\_traffic\_entity} . \mathtt{Traffic\_Participant})(\mathtt{s_{i}})$ holds, it will not conclude that no traffic participant is present in the current scene $\mathtt{s_i}$.
This can be then, for example, be propagated when querying the ontology whether it knows about the absence of vulnerable road users close to the road.

On a more general note, <ref> schematically depicts how an ontology functions as a central interface between the real world and the various entities that relate to the world.

Schematic representation of the role of an ontology in developing and safeguarding complex systems in open contexts.

In the life cycle of a complex system, those entities are manifold in appearance, ranging from persons, such as developers, engineers, and testers, up to artifacts, such as the safety case, data schemes, and even the system itself, all with diverse models of the world.

A mismatch in the understanding of the context between one of those entities can be fatal.
This issue specifically concerns data-focused applications as a well-founded safety case relies not solely on a single data source but rather on various recording modalities to support its claims, e.g. from test vehicles, naturalistic driving studies, or drone data from intersections.
Their data schemes need to be aligned in order to avoid discrepancies between these evidences.

For example, a safety case may demonstrate that a machine learning-based pedestrian perception has an acceptable False Negative Rate w.r.t. the overall positive risk balance.
Everything else should then relate to precisely the same understanding of a pedestrian that was used for labeling the test data and hence for calculating the False Negative Rate.

Naturally, the questions arise how to reach an agreement on a common conceptualization as well as how to construct a formalization thereof.
We propose to guide the creation of such a model along the identification of criticality phenomena.

A methodical criticality analysis iteratively assembles a list of safety-relevant factors within traffic scenarios, although its completeness argumentation is based on two assumptions:

* there exist finitely many criticality phenomena, and

* their traces are recognizable within data.

The justification of these assumptions rests upon a comparison to human driving skills <cit.>.
The completeness assumption can then be justified as follows:
By definition, each criticality phenomenon is associated with criticality.
If we choose a suitable measurement principle (e.g. a suitable criticality metric) that can uncover their implications by finding related traffic conflicts, we are able to identify their traces in data.
By analyzing whether this event can not be explained by a previously discovered phenomenon – i.e. we have found a new phenomenon –, it is possible to achieve a completeness based on the overall finiteness assumption <cit.>.
This completeness can then be recognized by a reduced frequency of unexplained traffic conflicts.
Further discussion on discovering and explaining phenomena are given by Neurohr et al. <cit.>.

Concurrently to the criticality analysis, a shared ontology can be created from these factors, closing the gap in handling the open context at design time.
Note that the completeness of the shared ontology is based on the validity of the justification of the two previously mentioned assumptions.
Obviously, the ontology needs to be maintained during deployment.
Furthermore, concepts irrelevant for safety, e.g. those regarding mobility or performance goals of the system, may be added.

§.§ Competency Questions

We now derive competency questions that aid in developing an ontology for structuring the open context.

Preliminaries for Competencies
First, we introduce some high-level DL notations on the representation of criticality phenomena and scenarios.
Those high-level classes and their relations are depicted in <ref>.

Model of the relevant concepts and relations of the competency questions. A solid edge with solid tip is a custom relation, a solid edge with open tip is the subsumption relation, and a dashed edge is a definition.

We start with the concept of all scenarios, $\mathtt{Scenario}$.
Scenarios can have various member individuals $\mathtt{i}$, denoted by the relation $\mathtt{has\_traffic\_entity}$.
Criticality phenomena are modeled as sets of such scenario entities.
For each criticality phenomenon $X$, we denote its corresponding concept $\mathtt{CP_X} \sqsubseteq \exists \mathtt{has\_traffic\_entity}^{-1}.\top$.
For example, the class of all fast vehicles can be defined as $\mathtt{CP_{fast}} \equiv \mathtt{Vehicle} \sqcap \mathtt{Fast\_Object}$.
Whereas this example solely refers to one subject w.r.t. criticality, such phenomena can generally address one or more objects in addition to the subject.
Occlusion, for example, has the occluded entity as its subject but also relates to the occluding entity as well as the entity for which the occlusion happens.
Therefore, objects are referred to by the relation $\mathtt{object_{CP_X}}$, mapping from $\mathtt{CP_X}$ to a number of objects.

Eventually, we are interested in decomposing the scenario space into a set of abstract scenarios covering the identified criticality phenomena.
For a given $\mathtt{CP_X}$, we therefore denote its scenario class by $\mathtt{S_{CP_X}} \equiv \exists \mathtt{has\_traffic\_entity}. \mathtt{CP_X}$.

Derivation of Competency Questions
Starting early in the design phase of ADSs, contemporary approaches suggest to cluster the scenario space into abstract scenario classes.
This clustering can be formally analyzed to support the experts decomposing the OD.
Relevant questions are:

* Whether a set of scenario classes can occur at the same time – if they are disjoint, e.g. risk estimations can be performed without explicitly considering their conjunction – i.e. $\mathtt{S_{CP_1}} \sqcap \dots \sqcap \mathtt{S_{CP_n}} \sqsubseteq \bot$ (T1).

* Whether a scenario class is subsumed by another, as to facilitate a hierarchical decomposition within the safety argumentation, i.e. $\mathtt{S_{CP_1}} \sqsubseteq \mathtt{S_{CP_2}}$ (T2).

* Whether the chosen decomposition is complete, i.e. $\mathtt{Scenario} \sqsubseteq \mathtt{S_{CP_1}} \sqcup \dots \sqcup \mathtt{S_{CP_n}}$ (T3).

This decomposition can be supported by a counterexample-guided abstraction refinement as proposed by Neurohr et al. <cit.>.
For this, is is necessary to assess whether a given scenario is member of a certain scenario class or an individual is or is involved in a criticality phenomenon – i.e., $\neg \mathtt{S_{CP_X}}(\mathtt{s})$ (A1), $\neg \mathtt{CP_X}(\mathtt{i})$ (A2), or $\exists\mathtt{object_{CP_X}}^{-1}.\top(\mathtt{i})$ (A3).
Reasoning services on the ontology can support answering such questions formally by delivering counterexamples as to why these memberships do not hold.
Furthermore, data recording and subsequent scenario mining is often used to identify relevant test scenarios.
Given a real world traffic recording, we can find representative instances for our previously defined abstract scenario classes by asking a reasoner to query for A1 to A3.
Finally, during system testing, answering A1 to A3 allows to check whether a concrete simulation or test run is an instance of a given test case.
As one central element of a safety case, system testing can contribute valuable evidences for a necessary homologation prior to deployment.

However, even after successful homologation, constant monitoring of the ODD is required post-deployment, e.g. to detect changes in the assumptions on the ODD that were made in the pre-deployment safety case.
The ontology can be used to formalize such assumptions on the ODD definition.
An ontology-based monitor can then decide whether a) the observed scenario is consistent with the modeled knowledge about the world (i.e. the assumptions) and b) the observed or predicted future scenario still lies within the ODD.
Otherwise, appropriate mechanisms have to be executed by the ADS.
The first query reduces to the formal expression $\mathcal{O} \models \mathtt{Scenario}(\mathtt{s})$ (A4), whereas the second one can be based on A1 to A3.
Especially after incidents but also in joint operation with humans, e.g. for Level 3 functions, the system's behavior needs to be explainable at runtime.
If a vehicle chooses a behavior based on specific circumstances in its environment (i.e. assesses A1 to A3), it is advisable to investigate why this behavior was chosen.
We can query a reasoner to derive a logical explanation as to why $\mathtt{S_{CP_X}}$ was deemed to be present.

Competency questions of the proposed ontology. Questions with bold-faced identifiers are focused on in this work.

Reasoning     DL notation     Explanation     Example     ID

$\mathtt{S_{CP_X}}(\mathtt{s})$     Membership of a scenario $\mathtt{s}$ within a scenario class $\mathtt{S_{CP_X}}$     Does the scenario have an occluded pedestrian?     A1

4*A-Box     $\mathtt{CP_X}(\mathtt{i})$     Membership of an individual $\mathtt{i}$ within a criticality phenomenon $\mathtt{CP_X}$     Is the pedestrian occluded?     A2

$\exists\mathtt{object_{CP_X}}^{-1}.\top(\mathtt{i})$     Membership of an individual $\mathtt{i}$ as an object of a criticality phenomenon $\mathtt{CP_X}$     In the given scenario, is the ego vehicle causing an occlusion?     A3

$\mathcal{O} \models \mathtt{Scenario}(\mathtt{s})$     Consistency of an observed scenario $\mathtt{s}$ with the modeled knowledge     Is the perceived pedestrian with 40km/h consistent with the modeled knowledge?     A4

$\mathtt{S_{CP_1}} \sqcap \dots \sqcap \mathtt{S_{CP_n}} \sqsubseteq \bot$     Compatibility of a set of criticality phenomena     Can the criticality phenomena Foggy Night & Sun Glare exist simultaneously?     T1

T-Box     $\mathtt{S_{CP_1}} \sqsubseteq \mathtt{S_{CP_2}}$     Abstraction relation of criticality phenomena     Is the concretization of Occluded Road User into Occluded Vehicle and Occluded Pedestrian correct?     T2

$\mathtt{Scenario} \sqsubseteq \mathtt{S_{CP_1}} \sqcup \dots \sqcup \mathtt{S_{CP_n}}$     Completeness of a set of scenario classes     Is the scenario space decomposition into right and left turn maneuvers complete?     T3

<ref> presents the derived seven competency questions – A1 to A4 and T1 to T3 – the proposed ontology was implemented against.
Note that there also exist other possible competency questions, such as model finding – algorithmically generating a witness for the satisfiability of $\top \sqsubseteq \neg \texttt{C}$, e.g. a concrete scenario $\mathtt{s}$ for a given abstract scenario class $\mathtt{S_{CP_X}}$.
Such competency questions require different architectures and approaches in ontology design and were thus excluded.

Whereas the ontology has been implemented w.r.t. all competency questions, the evaluation of the ontology-based tooling as presented in <ref> and <ref> is focused on the first three competency questions, A1 to A3.
This allows, on one hand, to keep the ontology implementation generic and applicable to a variety of use cases, and, on the other hand, the practical evaluation focused and comprehensible.

§.§ Methodical Formalization and Recognition Criticality

We have introduced the working hypothesis that by creating an ontology via a set of identified criticality phenomena we are able to achieve an iterative completeness of the model w.r.t. the safety relevant factors.
Furthermore, we established the practical relevance of the guiding competency questions regarding the safety assurance of ADSs within a thereby created model.
In particular, we demonstrated the importance of answering competency question A1 – scenario membership.
Based on these foundations, we propose a general method that

* formalizes criticality phenomena within an iteratively refined ontology,

* transforms data from various sources into the language of the ontology, and

* utilizes DL & rule reasoners to infer the presence of criticality phenomena in such traffic scenarios

The process is depicted in <ref> where these steps are respectively marked by 1, 2, and 3.

The general method of formalizing a natural language phenomenon and reasoning about its presence in data.

In step 1, the T-Box $\mathcal{T}$ is iteratively constructed by formalizing a list of criticality phenomena.
This list is constantly growing by continuous conduction of a criticality analysis <cit.>.
We therefore pick a criticality phenomenon $\mathtt{CP_X}$ and create a formalization of its semantics using appropriate rules or DL axioms.
This semantics can be based on both existing concepts – $\mathtt{C_1}, \dots, \mathtt{C_n}$ – as well as newly introduced concepts – $\mathtt{C_k}, \dots, \mathtt{C_l}$.
This necessitates the addition of $\mathtt{C_k}, \dots, \mathtt{C_l}$ to $\mathcal{T}$, in turn recursively formalizing them until the valid assumption can be made that so-called basic concepts can not be further specified.
A validation of the assumption is required, i.e. it has to be argued why neither a rule nor a description logic axiom is suitable to represent the given concept.

If one aims to infer the presence of a formalized criticality phenomenon, these basic concepts are then required to be either directly quantifiable or computationally derivable from the data.
In that case, they shall have a definition in natural language as to facilitate a correct observation.
If basic concepts are not observable in data (for example, if the recording modality does not allow to recognize certain features such as whether turning indicators are enabled), an analysis of the phenomena relying on those concepts can not be performed.

Hinging on the assumption of convergence of the criticality analysis, this process leads to an iterative completion of the ontology towards an exhaustive representation of all concepts that are deemed essential for identifying safety-relevant factors.
This step is elaborated on in detail in the upcoming <ref> – concerning the basic ontological framework – and <ref> – concerning the formalization of criticality phenomena within this ontological framework.

Step 2 unifies the various scenario data sources by conversion into a $\mathcal{T}$-compliant A-Box $\mathcal{A}$.
This creates scenarios $\mathtt{s_1}$ to $\mathtt{s_n}$ with traffic entities $\mathtt{i}$ to $\mathtt{i'}$ that are represented using the concepts $\mathtt{C}$, $\mathtt{C'}, \dots$ and roles $r$, $r'$, $\dots$ of $\mathcal{T}$.

A realization of this step is given in <ref> and <ref>.

Once the manifold data sources are convertible from their native data schemes, new facts can be inferred by performing reasoning on the ontology $\mathcal{O} = (\mathcal{T}, \mathcal{A})$, as indicated by 3.
Such a reasoning pipeline has been prototypically implemented for the work at hand whilst taking  into account various practical concerns, e.g. temporal reasoning performance and concrete domain abstraction.
This finally answers competency question A1, i.e. for which $i \in \{1, \dots, n\}$ $\mathtt{S_{CP_X}}(\mathtt{s_i})$ holds, and, per definition, also A2 to A3, cf. <ref>.

§ THE AUTOMOTIVE URBAN TRAFFIC ONTOLOGY

Starting with step 1 of the sketched method of <ref>, this section presents the employed T-Box.
It describes the conceptual foundations, general structure, idea, modeling, and implementation of an integrated set of suitable ontologies.

§.§ The 6-Layer Model as a Conceptual Foundation

As a tool for structured environment description, the well-known Layer Model can be utilized to create a formal model of the context.
It was originally defined by Schuldt <cit.> and has been continuously refined for specific use cases, e.g. by Bagschick et al. for the instantiation of highway scenes <cit.>.
In a recent work by Scholtes et al., their ideas are examined in-depth and adapted for urban environments while keeping compatibility to the fundamental ideas behind the Layer Model <cit.>.
Since Scholtes et al. give detailed definitions of the layers as well as justifications, guidance, and examples, it serves as a suitable basis for our use case – namely, the construction of a formal ontology implementing the Layer Model.

The work categorizes the environment, its entities, and their properties in six individual layers: Road Network and Traffic Guidance Objects (L1), Roadside Structures (L2), Temporary Modifications of the former (L3), Dynamic Objects (L4), Environmental Conditions (L5), and Digital Information (L6), encompassing the so-called 6-Layer Model (6LM).
It thereby provides a generally usable, unbiased, and objective environment description, i.e. it functions as a clearly structured basis for scenario descriptions and their ontologies.
While the 6LM provides a unique top-level structuring for the environment, an ontology details and formalizes the different entities, properties, and relations in a more comprehensive way.

§.§ Architecture

In order to address the issue of integrating the 6LM into a formal ontology as necessitated by the process of <ref>, we present the AUTO (AUTO).
In its core, it is a set of integrated ontologies with the goal to enable reasoning about criticality in urban traffic scenarios.
Due to this scope, the 6LM as defined by Scholtes et al. for urban environments, is used as an architectural guiding pattern.

Architecturally, we separate each layer into a core and an implementation.
Cores represent an ontological interface which other layers and applications of the ontology can access without being concerned with detailed domain knowledge, which in turn is given in a set of implementations.
For example, the concept $\mathtt{Lane}$ is part of the Layer 1 core, but concrete specializations of lanes can be given in an implementation.

Moreover, this work extends the 6LM by detaching conceptually separated parts which semantically span over multiple layers or are completely independent of the traffic domain.
This modularity enables separation of concerns and re-use of concepts, e.g. for spatial properties (heights, distances, etc.).

Note that often, so-called Upper Level Ontologies are employed for the purpose of unification.
We deliberately omit the use of such ontologies as we were not able to identify an ontology that satisfied the needs imposed by the competency questions.
Namely, this concerns issues of suitable formalization to enable inferences by DL reasoners, documentation, implementation, comprehensibility, and modularity.
This problem is currently addressed in the standardization project ASAM OpenXOntology <cit.>, where an Upper Level Ontology is laboriously integrated into a traffic domain ontology.

We hence opt for a lean approach, where single, re-usable domain ontologies are imported, as displayed in <ref>.

Detached, related ontologies of the 6LM used within AUTO

Ontology     Competency     Example Concepts     Example Roles

Time     Temporal concepts     Intervals, Time Points     After, Before

Geometry     Geometries & shapes     Geometry, Rectangle     Contain, Disjoint

Physics     Physical properties     Dynamical object     Speed, Acceleration

Act     Activities over time     Actor, Event, Activity     Conduct, Participate

Communication     Message exchange     Sender, Receiver     Transmit, Receive

Perception     Perceiving Entities     Observer, Occlusion     Is Occluded For

On top of the related ontologies, we introduce a framework in which traffic entities of the 6LM are integrated into traffic models such as scenes and scenarios.
Collectively, this conglomerate of ontologies yields the AUTO shown in <ref>.

The modular architecture of the AUTO.

The diagram indicates the direction of the dependencies of the modules through arrows.
Therefore, both the traffic models as well as the 6LM rely on the set of related ontologies.
The former uses e.g. temporal concepts to specify scenarios, the latter uses e.g. physical properties for traffic participants.

§.§ Implementation

We provide an open-source implementation[<http://github.com/lu-w/auto>] of the previously introduced ontology in OWL2 (i.e. the DL  $\mathcal{SROIQ}^{(D)}$).

The provided AUTO consists of 26 OWL2 files implementing the modular architecture of <ref>.
Each file represents one ontology module in which its respective domain concepts are defined.
For example, the Physics ontology defines concepts such as $\mathtt{Spatial\_Object}$, $\mathtt{Dynamical\_Object}$, and $\mathtt{Non\_Moving\_Dynamical\_Object}$ alongside their natural language definition.
Here, a $\mathtt{Spatial\_Object}$ is defined as 'any physical object with a geometrical representation, e.g. a vehicle'.
If expressible in DLs, the OWL2 files also specifies logical axioms implementing these natural language definitions.
For example, the Physics ontology states $\mathtt{Dynamical\_Object} \sqsubseteq \mathtt{Spatial\_Object}$ and $\mathtt{Non\_Moving\_Dynamical\_Object} \equiv \mathtt{Dynamical\_Object} \sqcap \exists \mathtt{has\_velocity}.\{0.0\}$.
Those logical T-Box axioms then allow the reasoner, in turn, to infer entailed statements on the A-Boxes for the subsequent evaluation – such as, whether a given vehicle is a $\mathtt{Non\_Moving\_Dynamical\_Object}$.
For a visual excerpt of the T-Box of AUTO, including the subsumption relation and other logical axioms, we reference to <ref>.

We also rely on well-established ontologies, enabling compatibility to a wide range of tooling such as GraphDB:

* geometrical concepts are represented using OGC's GeoSPARQL ontology[<https://www.ogc.org/standards/geosparql>], which gives access to DE-9IM and RCC8 vocabularies <cit.>, and

* temporal concepts are represented using W3C's OWL Time ontology[<https://www.w3.org/TR/owl-time>], which itself relies on an adapted version of Allen's 13 temporal relations <cit.>.

*A Note on Temporal Identity
Some ontological approaches assume a perdurantistic dogma, i.e. things are inherently four dimensional entities in space-time.
AUTO takes an endurantistic view:
it specifies individuals in three dimensions and tracks temporal identity by the role $\mathtt{identical\_to}$.

§ ONTOLOGY-BASED FORMALIZATION OF CRITICALITY PHENOMENA

In general, criticality phenomena are not fixed to the combined DL-rule approach proposed in this work.

Various approaches exhibit differences in ease and specificity of the modeling process, computational efficiency of decidability problems, and availability of expertise.
However, a common feature is their formalization being based on an implicit or explicit ontology.
This section depicts the formalization process for our DL-rule approach as well as how the formalization can be leveraged for the construction of such an ontology.

§.§ The Formalization Process

Recall that the general method of <ref> started the formalization process (step 1) where a criticality phenomenon is formalized.
We now explain this process in more detail, which is based on the previously introduced framework of AUTO and a catalog[<https://github.com/lu-w/auto/blob/main/criticality_phenomena.owl>] of criticality phenomena defined in natural language that was assembled during prior work <cit.>.
We illustrate the formalization of the exemplary criticality phenomenon 'Bicyclist Illegitimately Riding Over Pedestrian Crossing' (CP 69) as a special case of Misconduct (CP 143).

The first step involves the collection and assembly of knowledge regarding the semantics of the criticality phenomenon, which relies on standards, laws, and domain experts.
For our example, we deem as necessary the semantics of the relevant regulatory aspects, bicyclists, pedestrian crossings, and riding over.
During the process, the stakeholders agree on

* the relevant regulatory aspects being given by the German traffic regulations (StVO) stating that a bicyclist can not exercise the right of way indicated by a pedestrian crossing if the bicyclist is mounted,

* a bicyclist as a traffic participant on a bicycle, and

* a pedestrian crossing as a an area that is officially marked with corresponding white stripes.

* riding over as the movement of an actor across an area

A suggestion of an (aspectual) semantics is then given by:

“A bicyclist that in one scene is not on a drivable lane, and in a directly succeeding scene on a pedestrian crossing where the bicyclist is exercising a right of way is using this pedestrian crossing illegitimately.”

As temporal identities of traffic entities need to be tracked through different scenes, we express this using a rule-based approach such that individuals can be bound to variables:

\begin{equation*}
\begin{aligned}
&\mathtt{Scene}(s_1) \wedge \mathtt{Scene}(s_2) \wedge \mathtt{has\_traffic\_entity}(s_1, b_1) \\&
\wedge \mathtt{has\_traffic\_entity}(s_2, b_2) \wedge \mathtt{identical\_to}(b_2, b_1) \\&
\wedge \sunderline{\mathtt{Bicyclist}}(b_1) \wedge \sunderline{\mathtt{Bicyclist}}(b_2) \wedge \mathtt{directly\_after}(s_2, s_1)
\\&
\wedge \sunderline{\mathtt{Non\_Driveable\_Lane}}(w) \wedge \mathtt{has\_traffic\_entity}(s_1, w) \\&
\wedge \mathtt{intersects}(b_1, w) \wedge \sunderline{\mathtt{Pedestrian\_Crossing}}(c) \\&
\wedge  \mathtt{has\_traffic\_entity}(s_2, c) \wedge \mathtt{intersects}(b_2, c) \\& \wedge \mathtt{Driveable\_Lane}(l) \wedge \mathtt{in\_scene}(l, s_2) \wedge \mathtt{intersects}(c, l) \\&
\wedge \mathtt{Driver}(d) \wedge \mathtt{drives}(d, v) \wedge \mathtt{in\_scene}(d, s_2) \\&
\wedge \mathtt{intersects}(d, l) \wedge \mathtt{has\_intersecting\_path}(v, b_2)\\&
\rightarrow \mathtt{CP_{69}}(b_2)
\end{aligned}
\end{equation*}

Intuitively, this rule states that if a bicyclist is driving on a non-drivable lane (e.g., sidewalk) in one scene and on a pedestrian crossing in a subsequent scene in which also a traffic participant on an intersecting lane with an intersecting path, then $\mathtt{CP_{69}}$ holds for that bicyclist.
More specifically, the identity of the bicyclist in the first scene ($s_1$) is referred to as $b_1$, respectively as $b_2$ for the second scene ($s_2$).
The scenes have $b_1$ and $b_2$ as their respective traffic entity (hence, $\mathtt{has\_traffic\_entity}$) and are directly after each other (hence, $\mathtt{directly\_after}$).
Furthermore, $s_1$ has a non-drivable lane $w$ as its traffic entity which the bicyclist $b_1$ intersects.
Similarly, the second scene $s_2$ has a pedestrian crossing $c$ and driveable lane $l$ that intersects $c$. Furthermore, $s_2$ has a driver $d$ within $s_2$ on lane $l$ that drives a vehicle $v$ which in turn has an intersecting path with the bicyclist $b_2$.

The formalization relies on a set of concepts from AUTO that are assumed to be already existent as well as suitably defined and axiomatized in the ontology, e.g. for temporal and spatial concepts.
On the other hand, $\mathtt{Bicyclist}$, $\mathtt{Pedestrian\_Crossing}$, and $\mathtt{Non\_Driveable\_Lane}$ (underlined) are, for the scope of the example, not present at the time of formalization and therefore need to be added to $\mathcal{T}$.
The following integration of concepts and their subsumption is also visualized in <ref>.

Derived concepts for the criticality phenomenon 'Bicyclist Illegitimately Riding Over Pedestrian Crossing' including their subsumption into relevant parts of the existing T-Box, as implemented in AUTO

* $\mathtt{Bicyclist} \equiv \mathtt{Human} \sqcap \exists \mathtt{rides} . \mathtt{Bicycle}$

* $\mathtt{Human}$, $\mathtt{Bicycle}$ are basic concepts

* $\mathtt{rides} \equiv \mathtt{mounted}$

* $\mathtt{mounted}$ is a basic concept (something physically and stably touches another spatial object)

* $\begin{aligned}[t]&\mathtt{Pedestrian\_Crossing} \equiv \exists \mathtt{has\_geometry}. \\&(\mathtt{Rectangle} \sqcap \exists \mathtt{is\_signed\_by}. \mathtt{StVO\_350})\end{aligned}$

* $\mathtt{has\_geometry}$ (geometries of spatial objects), $\mathtt{Rectangle}$ (a two-dimensional shape), $\mathtt{is\_signed\_by}$ (which traffic signs apply to an individual), and $\mathtt{StVO\_350}$ (marker for pedestrian crossing) are basic concepts

* $\mathtt{Non\_Driveable\_Lane}$, a basic concept (a lane that is not intended to be driven on by any vehicle, e.g. a walkway)

Requiring that the necessary basic concepts can either be directly observed in the analyzed data or at least be derived therefrom, e.g. by means of machine learning algorithms such as image segmentation for $\mathtt{Non\_Driveable\_Lane}$, we now have the ability to (aspectually) infer the presence of $\mathtt{CP_{69}}$.

§.§ Approaching Formalizability

Concepts and phenomena may be inherently unformalizable due to their vagueness (e.g. subjectivity and case-by-case decisions).
To mitigate this problem, $\mathtt{CP_X}$ can be specified by:

* An exact representation: if possible, we give an exact representation using an equivalence, i.e. $\mathtt{CP_X} \equiv f(\mathtt{C_k}, \dots, \mathtt{C_l})$ where $f$ is a logical concept expression.

* An under approximation: if an exact representation is not possible, we use an approximation. In DL, an under approximation can be specified as a GCI of the form $\mathtt{CP_X} \sqsupseteq f(\mathtt{C_k}, \dots, \mathtt{C_l})$.
On top of DL, sufficient conditions for $\mathtt{CP_X}$ can be stated as a rule, i.e. $\bigwedge_{r_a \in R_A} r_a \rightarrow \mathtt{CP_X}(\mathtt{v})$.

* An over approximation: an over approximation is specified by a GCI $\mathtt{CP_X} \sqsubseteq f(\mathtt{C_k}, \dots, \mathtt{C_l})$.
Combined with an under approximation, it allows for a two-sided bound.

For example, 'Occluded Pedestrian' (CP 157) can be exactly formalized assuming that $\mathtt{Pedestrian}$, $\mathtt{Is\_Occlusion}$, and $\mathtt{is\_occluded}$ are exactly formalized or basic concepts: $\mathtt{CP_{157}} \equiv \mathtt{Is\_Occlusion} \sqcap \exists \mathtt{is\_occluded} . \mathtt{Pedestrian}$
The phenomenon 'Misconduct' (CP 143) on the other hand has a broad scope.

We hence model certain aspects of it, such as driving without vehicle lights turned on in night scenarios: $\mathtt{CP_{143}} \sqsupseteq (\mathtt{Off\_Light\_Vehicle} \sqcap \exists \mathtt{in\_traffic\_model}.\mathtt{Night\_Scenario}) \sqcup \mathtt{CP_{69}}$
Similarly, 'Vulnerable Road User with Road Access' (CP 114), contains the vague concept Road Access, which was over approximated in terms of $\mathtt{is\_near}$.
It is formalized as $\mathtt{CP_{114}} \sqsubseteq \mathtt{Vulnerable\_Road\_User} \sqcap \exists \mathtt{is\_near} . \mathtt{Driveable\_Lane}$.
Such approximations can be iteratively refined.

Exactly ($\equiv$) or over ($\sqsubseteq$) resp. under ($\sqsupseteq$) approximately formalized criticality phenomena for the prototypical evaluation.

(L1) Road Network     (L2) Roadside Structures     (L4) Dynamic Objects     (L5) Environmental Conditions     Physics     Perception     Policy

Pedestrian Crossing / Ford$^\equiv$     Building for Unpredictable Road Users near Road$^\sqsubseteq$     Pedestrian on Roadway$^\equiv$Vulnerable Road User with Road Access$^\sqsubseteq$Passing of Parking Vehicle$^\equiv$Intersecting Planned Paths$^\sqsupseteq$     Heavy Rain$^\equiv$Freezing Temperatures$^\equiv$     Small Distance$^\sqsupseteq$Strong Braking Maneuver$^\equiv$High Relative Speed$^\equiv$     Occlusion$^\equiv$Occluded Pedestrian$^\equiv$Occluded Traffic Infrastructure$^\equiv$     Illegitimate Use of Pedestrian Crossing$^\sqsupseteq$Misconduct$^\sqsupseteq$

Besides those three formalizations, our prototype contains the definitions of in total 16 criticality phenomena, depicted along their primary classification within AUTO in <ref>.
They were selected from a catalog of roughly 300 criticality phenomena described in natural language which originated during an initial iteration of the criticality analysis.
Their formalization is detailedly presented in the Appendix.

§ IMPLEMENTING THE CRITICALITY RECOGNITION

We present a Python implementation[<https://github.com/lu-w/criticality-recognition>] of the process of <ref> that is based on the ontology introduced in <ref>.

While the realization of step 1 has already been unveiled, we now focus on the data and reasoning steps, i.e. 2 and 3.

§.§ The OMEGA-Format

As motivated in <ref>, the use of various data sources is of high value when analyzing the criticality within traffic scenarios.
Methodically, our approach rests upon a unified data format that allows to represent traffic scenarios from different sources, including drones, measurement vehicles, and stationary cameras.
This format therefore provides input for AUTO A-Boxes.
For this, the OMEGA-format was chosen <cit.>.
The data format is HDF5-based and designed to store reference data of urban automotive settings in an object-list structure together with map and weather information.

§.§ Ontology Mapping

In order for AUTO to harness the information provided by OMEGA-compliant data sets, we need to map the OMEGA-format onto the concepts provided by AUTO, i.e. a realization of step 2.
As the development of the OMEGA-format was performed in conjunction with the development of AUTO, the format is naturally mappable to the concepts of the ontology.

For example, we translate each object of the OMEGA-type  into a corresponding axiom within the ABox.
The following specification of the OMEGA-format defines reflector guiding lamps as

“6.1 Type: : Any reflectors or lamps along the lane (reflectors and guiding lamps are assumed to be regularly placed, their exact position is not known.)”.

We create a new individual $\mathtt{i}$ as well as a corresponding boundary geometry $\mathtt{i_\mathtt{geom}}$ and map the definition to $\mathtt{i}$ by:

\begin{gather*}
(\mathtt{System} \sqcap \forall \mathtt{consists\_of}. (\mathtt{Reflector\_Guiding\_Lamp}\\ \sqcap \exists \mathtt{within}. \{\mathtt{i_{geom}}\}))(\mathtt{i})
\end{gather*}

§.§ Automated Recognition of Criticality Phenomena

After creating an A-Box $\mathcal{A}$ based on $\mathcal{T}$ containing a set of $n$ scenarios, the naïve option would be to run the reasoner directly on $\mathcal{O} = (\mathcal{T}, \mathcal{A})$.
With this, two problems arise:

* deriving abstract facts from concrete domains, such as performing complex trigonometrical calculations to check whether one geometry occludes another, and

* exploding state spaces for large A-Boxes, especially when analyzing real world scenarios.

We resolve both issues within our implementation.

Deriving Abstract Facts from Concrete Domains
Here, we propose an iterative augmentation approach to lift A-Boxes from concrete to abstract domains.
We provide a library where the user can easily specify definitions for arbitrary concepts $\mathtt{C}$ and (reified) roles $\mathtt{r}$ using Python code[<https://github.com/lu-w/owlready2-augmentator>].
This enables us to derive whether those concepts or roles are present by means of classical imperative programming.

The library provides a high level interface that performs such an augmentation for each individual within $\mathcal{A}$ of an ontology $\mathcal{O}$, denoted by do_augmentation$\mathcal{O}$, changing $\mathcal{O}$ in-place and returning the number of performed augmentations.

Finally, the lifting of domains needs to be integrated with the reasoner, whose interface is denoted by do_reasoning$\mathcal{O}$.
This integration is sketched by <ref>.

Inference by lifting concrete to abstract domains

Input: an ontology $\mathcal{O}$

Output: $\mathcal{O}$ including all inferred facts
[1]
$a = 1$
$a > 0$
$a =$ Do_Augmentation$\mathcal{O}$

This simple yet correct procedure yields an iterative detection of all possible inferences on $\mathcal{O}$.
Note that efficiency can be improved by directly integrating the augmentation into the reasoning engine, which was left for future work.

Exploding State Spaces
The second issue concerns the sheer size of real world scenarios.
As an example, a complex urban traffic scene may contain 80 individuals on Layer 4 and 200 individuals on Layers 1 and 2.
Even at a sampling rate of 3 Hertz, this amounts to over $2.5\cdot10^5$ individuals in 30 seconds and a combinatorial size of $6.25\cdot10^{10}$ and $1.5625\cdot10^{16}$ for potential binary and ternary relations.

Upon closer inspection, many of those relations may not be logically possible.
For example, spatial relations between a lane in scene one and a vehicle in scene two are irrelevant.
Therefore, we safely use successive examination of the single scenes to correctly infer all non-temporal facts.

This still leaves open the question of handling temporality.
For example, the previously introduced rule for criticality phenomenon $\mathtt{CP_{69}}$ argues over two directly succeeding scenes, which can not be recognized on a scene level.
However, running the reasoner directly on the scenario-level A-Box leads to the discussed scalability issues.
Analogously to program slicing <cit.>, we suggest a temporal slicing approach.

Temporal inference

Input: an ontology $\mathcal{O} = (\mathcal{T}, \mathcal{A})$ with exactly one scenario $\mathtt{s}$ and scenes $\mathtt{s_1} \dots \mathtt{s_n}$ in $\mathcal{A}$

Output: $\mathcal{O}$ including inferred facts for $\mathtt{s}$
[1]
$i \in \{1, \dots, n\}$
$\mathcal{A}_\mathtt{s_i}$$ = $ Scene$\mathcal{A}, i$
Do_Inference$(\mathcal{T}, \mathcal{A}_\mathtt{s_i})$
$\eqmakebox[lhs1][l]{$\mathcal{A}_\mathit{merged}$} = $ Merge$\mathcal{A}_\mathtt{s_1}, \dots, \mathcal{A}_\mathtt{s_n}$
$\eqmakebox[lhs1][l]{$C$} = $ Temporal_Concepts$\mathcal{T}$
$\eqmakebox[lhs1][l]{$\mathcal{A}_\mathit{sliced}$} = $ Slice$\mathcal{A}_\mathit{merged}, C$
Do_Inference$(\mathcal{T}, \mathcal{A}_\mathit{sliced})$
$\eqmakebox[lhs1][l]{$\mathcal{A}_\mathit{res}$} = $ Merge$\mathcal{A}_\mathtt{merged}, \mathcal{A}_\mathtt{sliced}$
$(\mathcal{T}, \mathcal{A}_\mathit{res})$

Here, entities not relevant for temporal inference are sliced from the A-Box and re-added after finishing the temporal reasoning on the whole scenario, as shown in <ref>.
The algorithm relies on the following operators:

* Scene$\mathcal{A}, i$, which reduces $\mathcal{A}$ to an A-Box $\mathcal{A}_\mathtt{s_i}$ with only individuals of scene $\mathtt{s_i}$, i.e. $\mathcal{A}_\mathtt{s_i} \coloneqq \{\alpha \in \mathcal{A}\,|\, \exists \mathtt{n} \in \mathit{ind}(\alpha): (\exists \mathtt{has\_traffic\_entity}^{-1}.\{\mathtt{s_i}\})(\mathtt{n})\}$.

* merge$\mathcal{A}_1, \dots, \mathcal{A}_n$, whose result is roughly equal to $\bigcup_{i\in \{1,\dots,n\}} \mathcal{A}_i$, but special temporally constant individuals (e.g. lanes) are not merged as to avoid duplicates.
Temporal identity is added by the merge$\cdot$ algorithm using the previously introduced role $\mathtt{identical\_to}$.

* Temporal_Concepts$\mathcal{T}$, which identifies a set $\mathsf{N}_T$ of concepts and roles that are (possibly indirectly) used in an axiom involving a concept from a set of temporal concepts $T$, e.g. $T = \{\mathtt{Interval}, \mathtt{Point}\}$.
Formally, $\mathsf{N}_T = \{\mathtt{C} \in \mathsf{N}_C \cup \mathsf{N}_R \,\mid\, \mathtt{D} \in T, k \geq 0, \exists \alpha_0 \in \mathit{axs}(\mathtt{C}), \exists \alpha_2, \dots, \alpha_{k-1} \in \mathcal{T}, \alpha_k \in \mathit{axs}(\mathtt{D}): \bigwedge_{i=0}^{k-1} (\mathit{nms}(\alpha_i) \cap \mathit{nms}(\alpha_{i+1}) \neq \emptyset) \}$.
In the case that $\mathcal{O}$ contains rules, $\mathsf{N}_T$ can be defined analogously.

* Slice$\mathcal{A}, \mathsf{T}$, which creates an A-Box $\mathcal{A}_\mathit{sliced}$ with only individuals that relate to concepts in $\mathsf{T}$, i.e. $\mathcal{A}_\mathit{sliced} \coloneqq \{ \alpha \in \mathcal{A} \,|\, \exists \mathtt{i} \in \mathit{ind}(\alpha):\, \exists \mathtt{C} \in \mathsf{T}:\, \mathtt{C}(\mathtt{i}) \}$.

Intuitively, the algorithm takes as input an A-Box $\mathcal{A}$ with one scenario consisting of $n$ scenes.
It creates an A-Box $\mathcal{A}_\mathit{res}$ where all temporal facts – i.e. those on a scenario-level – are inferred.
This concerns, for example, the rule for $\mathtt{CP_{69}}$, which can only be applied when multiple scenes are present in the analyzed A-Box.
Firstly, it infers all entailed facts on each scene using <ref>.
Afterwards, it merges all scenes into a single A-Box $\mathcal{A}_\mathit{merged}$.
Based on the formalized criticality phenomena in $\mathcal{T}$, it also derives a set of temporal concepts $C$ which are necessary to infer facts about the presence of temporal criticality phenomena.
Those are then used to create a sliced A-Box $\mathcal{A}_\mathit{sliced}$ in which only individuals of concepts in $C$ remain.
This sliced A-Box is then considerably smaller than the original A-Box and therefore suitable for the inference sketched in <ref>.
Finally, all individuals that were previously sliced away are re-added to the A-Box $\mathcal{A}_\mathit{res}$.

Since criticality phenomena have been modeled as axioms within $\mathcal{T}$, <ref> eventually yields an inferred A-Box $\mathcal{A}$ in which the presence of criticality phenomena is documented.

§ EVALUATION AND RESULTS

We evaluate the implementation on the inD data set <cit.>, showing how the reasoner can answer the competency questions A1 to A3 based on the exemplary set of formalized phenomena and our implementation of <ref> and <ref>.
Albeit the main contribution of this work being the development of the method and tooling, we present a first evaluation for a semantic data analysis use case.
Recall that we have previously argued that a verification and validation process relies on various recording modalities, including fleet monitoring, test vehicles, and drone data.
As to exemplarily examine one of these relevant data sources, we have selected a large-scale drone data set which can act as a precursor to a rigorous investigation of a variety of data sources.

§.§ The inD data set

The inD data set consists of naturalistic trajectories of more than 11 500 road users, including vehicles, bicyclists, and pedestrians, at four urban intersections in Aachen, Germany.

The utilization of drones in the creation of the data set retains naturalistic driving behavior by being inconspicuous and aids the accuracy of positioning and object dimensions.
Its distinctive perspective allows to draw conclusions about the behavior of traffic participants in certain situations – e.g. bicyclists at pedestrian crossings – which in turn can be constructively used as assumptions for designing, implementing, and safeguarding an ADS.
Moreover, and in contrast to an in-vehicle perspective, we are able to assume a holistic view on the traffic scenario, i.e. tracking of 'behavior chains' where the decisions of traffic participants influences each other through transitive propagation.
As an example of such a chain, consider an occluded pedestrian which leads to a strong braking maneuver of an intersecting vehicle that in turn leads to a potential rear-end collision of a following vehicle.

§.§ Reasoning Results

In order to demonstrate the practicality and utility of our approach, we evaluate of the method on inD in three steps:

* Firstly, we present an intuitive example depicting the inference results for a single, representative traffic conflict.

* Secondly, analyze four scenarios on each intersection.

* Lastly, we compare the inferences of our tooling against two criticality metrics as determined by prior work <cit.>.

§.§.§ An Exemplary Traffic Conflict

We identified a simple yet representative traffic conflict within the inD data set[Namely, scenario number 94 in recording number 18].
Here, a passenger car approaches the intersection at the Frankenberger Park in Aachen, Germany, from the east while a pedestrian is occluded behind parking vehicles.
The passenger car is forced to a substantial braking maneuver by the appearance of the pedestrian.
The criticality phenomena within this conflict were inferred automatically by our tooling and are represented visually in <ref>.

The inferred criticality phenomena over time of a 6.6 second scenario with one moving vehicle, one pedestrian, and eight parking vehicles. The subject (and objects) are annotated by gray boxes on each criticality phenomenon. Occ. by = Occluded by and Passing Park. Veh. = Passing of Parking Vehicles.

The inferences show that the pedestrian and vehicle are indeed bilaterally occluded by parking vehicles while having a high relative speed during the first seconds of the scenario.
Furthermore, the driver passes these parking vehicles while the pedestrian has access to the road.
This leads to the occurrence of the more concrete criticality phenomenon Small Distance.
Note that, albeit a harsh braking, the criticality phenomenon Strong Braking Maneuver was not detected, as the vehicle has been decelerated just below the threshold of $4.61$ m/s².
This showcases an inherent limitation of the binary identification approach, where values just below thresholds are deemed irrelevant albeit possibly still influencing the overall criticality.

As an illustration of the aforementioned holistic view on traffic scenarios, <ref> shows a bar chart of the amount of criticality phenomena per scene for the exemplary scenario.

Identified criticality phenomena within the exemplary scenario.

It is evident that occluded traffic infrastructures – such as lane markings – make up a large amount of the overall criticality phenomena.
Furthermore, we find a considerable number of small distances and intersecting planned paths, as is to be expected in urban intersection scenarios.
Overall, the amount of inferred criticality phenomena per scene is quite high, raising the issue of the specificity of the formalizations.

§.§.§ Evaluation of Multiple Scenarios

We present an evaluation of in total 16 scenarios – four scenarios for each of the four inD intersections – with a mean duration of 11.27 $\pm$ 3.68 seconds covering a total span of 180.28 seconds with 361 unique traffic participants.
The scenarios were converted into AUTO A-Boxes at a rate of 1 Hertz, leading to 183 scenes.
Due to the large scale of the data set, we reduced the evaluation to scene-level criticality phenomena, i.e. performing only <ref>.
The overall number of inferred criticality phenomena amounts to 114 922, resp. 628 per scene.
If this number is again taken relative to the involved traffic participants, we find that there exist roughly 1.74 criticality phenomena per scene per traffic participant.

A detailed break-down of the inferred criticality phenomena per scene per traffic participant into the single phenomena classes for each of the intersections is presented in <ref>.

Inferred criticality phenomena (CP) relative to the number of traffic participants (TP) and scenes over the selected 16 scenarios, arranged by intersection (Int.).

CP per TP per Scene     Int. 1     Int. 2     Int. 3     Int. 4

High Relative Speed     0.380     0.438     0.584     1.99

Intersecting Planned Paths     0.058     0.066     0.050     0.047

Occluded Pedestrian     0.811     1.332     0.377     0.291

Occluded Traffic Infrastructure     21.781     13.127     47.658     32.076

Occlusion     1.629     1.628     1.076     0.978

Presence of VRUs With Road Access     0.257     0.180     0.094     0.191

Small Distance     0.278     0.513     0.338     0.271

Strong Braking Maneuver     0.003     0     0     0

For example, on intersection two, there exist 1.332 occluded pedestrians per traffic participant in each scene.
The value is considerably lower for the other intersections, indicating a higher pedestrian occurrence or occlusion potential.

To further show the capabilities of a semantic analysis, we demonstrate how a naïve analysis of the temporal relation of two criticality phenomena can be performed – namely Intersecting Planned Paths and Occlusion – on passenger car-pedestrian constellations.
We first formulate two hypotheses:

$H_1$ occlusions and intersecting paths are, independent of their temporal constellation, associated between passenger cars and pedestrians, and

$H_2$ in the cases where both occur, it is more likely to observe intersecting paths after occlusions than before.

We test $H_1$ by means of a simple contingency table as depicted in <ref>.
This table displays the amount of cases of all four combinations of the occurrence of the two criticality phenomena between passenger cars and pedestrians.

Amount of the criticality phenomena for all pairwise combinations of passenger cars and pedestrians.

Occlusion     No Occlusion

Intersecting Paths     7     1

No Intersecting Paths     846     532

From this table, we compute the phi coefficient as
$$\Phi = \frac{n_{11}n_{00}-n_{10}n_{01}}{\sqrt{(n_{10} + n_{11}) \cdot (n_{00} + n_{01}) \cdot (n_{00} + n_{01}) \cdot (n_{01} + n_{11})}}\text{,}$$

where $n_{ij}$ indicates the number $n$ in the $i$-th row and $j$-th column of the contingency table.
For the analyzed criticality phenomena, this yields $\Phi = 0.04$.
With the phi coefficient taking values from $[-1,1]$ in the dichotomous case, we find a minor yet positive correlation between the variables.

As to test $H_2$, we first perform a simple analysis of the differences of the starting times of the intervals in which the criticality phenomena occur, taking into account all combinations of traffic participants.
Since the association has been examined by $\Phi$, we can now focus on only the cases in which both small distances and occlusions occur.
Our results indicate that, on average, small distances start 0.87 seconds after occlusions, with a standard deviation of 5.83 seconds.

§.§.§ Comparison against Criticality Metrics

Besides comparing the relations between criticality phenomena themselves, one can also identify their relation to measured criticality as computed by criticality metrics.

Here, our hypothesis states that an increase of a criticality metric is often preceded by a set of relevant criticality phenomena.
This methodical approach obviously rests upon the assumption of a specific and sound formalization of criticality phenomena as well as upon employing valid criticality metrics.

Prior work has already examined various criticality metrics for 22 traffic scenarios of inD for left-turn and passing maneuvers of vehicle pairs <cit.>.

We restrict our exemplary comparison to the analysis of one scenario and two metrics, namely scenario number 449 in recording number 28 and the Time To Collision (TTC) and Required Acceleration ($a_\mathit{req}$).
Similar to <ref>, the plot of this scenario is presented in <ref> but now includes the metrics' values over time.

The computed criticality metrics and inferred criticality phenomena for the exemplary scenario between both traffic participants over time.

In the example, a minimum TTC of 0.6 s and $a_\mathit{req}$ of -11.8 m/s² is given, with the metrics starting a linear approach of their minimum values at second 1044.7.
After second 1046.7, the passing maneuver is finished.
Our tooling observes that before this critical encounter, an occlusion took place between both traffic participants.
Furthermore, we also identified high relative speeds during the passing phase of both vehicles.

*A note on risk quantification

Within a rigorous safety case, this relation needs to be examined statistically on populations of representative scenarios, i.e. how strong is the association between certain phenomena and measured criticality across the OD.
Depending on this strength, certain phenomena may be treated differently during the argumentation and evidence generation.
For example, an argument as to why the ADS sufficiently mitigates the risk induced by occluded pedestrians may be elaborated on more extensively than those in which a lane marking is occluded – depending on the associational findings and subsequent causal analyses.
After this initial examination of the OD, safety standards require the development of a system design as well as a subsequent hazard analysis and assessment of risks.
This assessment can be based upon prior knowledge that originated from the analysis of criticality metrics and phenomena.
Since criticality phenomena represent factors that impact the safety in traffic in general, it is likely that such phenomena will also be relevant for the hazard analysis of the given system.
The quantification provided by the aforementioned associational analysis of criticality can be used as an initial estimate for the risk assessment, although the specific system design may influence the actual risk.
For example, an ADS could be designed in a way that effectively mitigates risks induced by occluded pedestrians.

Nevertheless, an argument as to why this specific criticality phenomenon is handled sufficiently well by the system is mandatory.

§ CONCLUSION AND FUTURE WORK

We presented a first step towards a structured method to obtain a formalized definition of an OD, incorporated into the framework provided by the criticality analysis.
This ontological OD definition has shown to be well-suited for reasoning over formalized criticality phenomena, thereby being a central element in a verification and validation strategy.

Obviously, future work can address the extension of the knowledge base – formalizing a wider variety of criticality phenomena –, the data sources – analyzing data generated by test vehicles or simulation runs –, a rigorous data analysis – studying the presence of (conjunctions of) criticality phenomena and their relation to traffic conflicts – as well as a practical evaluation of the competency questions A4 and T1 to T3.
An in-depth semantic analysis of large-scale intersection scenarios over a variety of criticality phenomena enables insights into the complex operating contexts of urban ADSs prior to system design.
Furthermore, a first evaluation demonstrated the method's feasibility on a drone data set. However, its transferability to live settings under real-time constraints, e.g. for monitoring of ODD boundaries defined via criticality phenomena, is yet to be examined.
Incorporating a vehicle perspective (instead of the actor-agnostic view of drones) implicates the necessity of theoretically and practically addressing incomplete and uncertain knowledge about the environment originating from vehicle sensor data.
Eventually, the results of this method can be used for safeguarding specific system designs.
Future work has to address a rigorous analysis of the relation between criticality phenomena and criticality metrics as well as how these results can be used for the system's hazard analysis and risk quantification.

Theoretically, we based the presented approach on DLs as well as rules and identified them as a suitable formalism to represent and reason on abstract knowledge about road traffic.

For this theoretical aspect of the work, it remains an open question how to formalize knowledge about concrete domains directly in DLs.

For the examined application of A-Box reasoning, we have tackled this challenge by means of augmentations that annotate existing spatio-temporal relations, but methodically, an integration into the logical framework is preferable.
In the case of more abstract T-Box reasoning, it is not only preferable, but also mandatory to incorporate spatio-temporal semantics.
For example, Allen's calculus states that $\mathtt{meets} \circ \mathtt{during} \sqsubseteq \mathtt{overlaps} \sqcup\mathtt{during} \sqcup \mathtt{starts}$, which is not a valid RIA in $\mathcal{SROIQ^{(D)}}$.
In general, $\mathcal{SROIQ^{(D)}}$ has been shown not to be able to represent the semantics of such calculi <cit.>, i.e. relational composition tables, due to the lack of e.g. role negations.
At least for RCC8, an alternative formalization using GCIs was proposed <cit.> and prototypically implemented <cit.>, although the work seems to be abandoned.
Therefore, theoretical advances need to address the incorporation of spatio-temporal semantics into the reasoning process, e.g. by integrating qualitative reasoning frameworks.

We furthermore presented an implementation of the proposed method and evaluated a prototype on the large and multi-faceted A-Boxes of the inD drone data set.

Practically, we found that reasoners, albeit mature, currently diminish in viability, leaving many of the available tools unmaintained.

Another practical aspect concerns the extensive space and time consumption of the Pellet reasoner when running on the large A-Boxes of inD, and hence potential performance improvements by e.g. extending the idea of A-Box slicing.
Alternatively, one refrain from using DL reasoners for inferring temporal properties.
Scenarios can still be sliced, but analyzed with a solver for a scenario language.

Lastly, the work has two assumptions: First, we assumed crisp terminological concepts within the T-Box. Second, the A-Box was considered perfectly representing ground truth.

The first issue ignores that the OD model represents inherently fuzzy knowledge of humans – e.g. 'heavy rain' may not have a crisp boundary.
Representations of knowledge need to acknowledge vagueness within the T-Box and incorporate it into the reasoning process.
The second issue concerns the applicability when presented with uncertain inputs.
Here, one has to propagate those perception uncertainties along the inferences made by the reasoner.
For a meaningful contribution to verification and validation, it is therefore imperative to both regard vagueness at design time and uncertainties at run time.

[Evaluated Criticality Phenomena]

We now display the formalization of the examined criticality phenomena as introduced in <ref>.

Employed concepts are only traced one layer down their recursive formalization.
Basic concepts are marked by ${}^b$.
Concepts that are augmented by an algebraic or first order logic formalization are indicated by $\coloneqq$ instead of the DL operators $\equiv$, $\sqsubseteq$, or $\sqsupseteq$.
For this, we mix first-order predicate logic with DL and algebraic operations.
Semantically, this is to be understood as a first order logic formula over the corresponding algebraic or geometric theory where the DL fragments, e.g. $\exists \mathtt{has\_traffic\_entity} . \{A_i\}$, represent sets of individuals on which we use set operators.

These formulae are implemented using the augmentation library.
We rely on some geometrical notation, listed in <ref>.
We restrict the geometries to two dimension in Euclidean space and assume a single coordinate system.

Employed geometrical notation and functions.

Notation     Semantics

$p$     A point in two-dimensional Euclidean space

$p_i$     The centroid's position of the geometry $g_i$

$d_i$     The diameter of the geometry $g_i$ (m)

[l]$p_i^{fl}$, $p_i^{fr}$,
$p_i^{br}$, $p_i^{bl}$     [l]The front left, right and back left, right points of
the geometry $g_i$ (assuming a given yaw $\theta_i$)

$\text{dist}(p_1, p_2)$     The euclidean distance between two points (m)

$\text{area}(g_i)$     The area of the geometry $g_i$ (m²)

$\text{points}(g_i)$     The set of points of the geometry $g_i$

$\text{ray}(p, \theta)$     A ray (half-line) starting from $p$ with angle $\theta$

$\text{circle}(p, r)$     A circle around $p$ with radius $r$

$\text{centroid}(g_i)$     The centroid point of the geometry $g_i$

$\text{polygon}(P)$     The polygon spanned by a tuple of points $P$

Overall, the algebraic and geometric formalizations are based on the notation depicted in <ref>.

Employed mathematical identifiers including their corresponding DL representation (in AUTO).

Notation     Semantics     AUTO representation

$A_i$     A traffic participant with identifier no. $i$     $\mathtt{Traffic\_Participant}(\mathtt{A})$, $(\exists \mathtt{identifier}^{-1} . \{A\})(i)$

$O$     A spatial object     $\mathtt{Spatial\_Object}(O)$

$g_i$     The geometry of $A_i$ described as a polygon (tuple of points)     $\mathtt{hasGeometry}$

$\theta_i$     The yaw angle (°) of $A_i$     $\mathtt{has\_yaw}$

$\theta_i^\mathit{max}$     The assumed maximum yaw angle (°) of $A_i$     $\mathtt{has\_maximum\_yaw}$

$\omega_i^\mathit{max}$     The assumed maximum yaw rate (°/s) of $A_i$     $\mathtt{has\_maximum\_yaw\_rate}$

$s_i$     The speed (scalar, m/s) of $A_i$     $\mathtt{has\_speed}$

$a_i$     The acceleration (scalar, m/s²) of $A_i$     $\mathtt{has\_acceleration}$

For an additional overview, <ref> presents a listing of all employed target values for criticality phenomena where thresholds have been applied or used within their concepts.

Target values for each criticality phenomenon (CP).

CP ID     Concept     Target Value(s)     Unit

113     $\mathtt{is\_near}$     4     m

295     $\mathtt{Heavy\_Rain}$     10     mm/h

295     $\mathtt{Extremely\_Heavy\_Rain}$     50     mm/h

294     $\mathtt{Freezing\_Air}$     0     °C

91     $\mathtt{has\_intersecting\_path}$     8 ($\tau_1$)     s

91     $\mathtt{has\_intersecting\_path}$     3 ($\tau_2$)     s

150     $\text{relevant\_area}$     1     s

103     $\mathtt{has\_acceleration}$     -4.61, -3.3     m/s²

163     $\mathtt{high\_relative\_speed}$     0.25     -

Pedestrian Crossing / Ford (CP 117)

CP 117 is defined as the disjunction of pedestrian crossings and fords.

\begin{gather*}
\mathtt{CP_{117}} \equiv \mathtt{Pedestrian\_Crossing}^b \sqcup \mathtt{Pedestrian\_Ford}^b
\end{gather*}

Building for Unpredictable Road Users near Road (CP 181)

CP 181 is under-approximated by the (not exhaustive) union of retirement homes, schools, and kindergartens.

\begin{gather*}
\mathtt{Kindergarten}^b \sqcup \mathtt{Retirement\_Home}^b \sqcup \mathtt{School}^b \sqsubseteq \mathtt{CP_{181}}
\end{gather*}

Pedestrian on Roadway (CP 82)

CP 82 is a pedestrian that geometrically intersects with a driveable lane.

\begin{gather*}
\mathtt{CP_{82}} \equiv \mathtt{Pedestrian} \sqcap \exists \mathtt{intersects} . \mathtt{Driveable\_Lane}^b
\end{gather*}

$\mathtt{Pedestrian} \equiv \mathtt{Human} \sqcap \nexists \mathtt{drives} . \mathtt{Vehicle}$, and

$\mathtt{intersects}(a,b) \coloneqq \exists g_1 \in (\exists \mathtt{hasGeometry}^{-1} . \{a\}) \wedge \exists g_2 \in (\exists \mathtt{hasGeometry}^{-1} . \{b\}) . \text{points}(g_1) \cap \text{points}(g_2) \neq \emptyset$.

Vulnerable Road User with Road Access (CP 113)

CP 113 is a vulnerable road user near some driveable lane.

\begin{gather*}
\mathtt{CP_{113}} \equiv \mathtt{VRU} \sqcap \exists \mathtt{is\_near} . \mathtt{Driveable\_Lane}^b
\end{gather*}

with $\mathtt{VRU} \equiv \mathtt{Bicyclist} \sqcup \mathtt{Pedestrian}$, and
$\mathtt{is\_near}(a,b) \coloneqq \text{dist}(a,b) < 4 \text{m}$.

Passing of Parking Vehicle (CP 91)

CP 91 is a temporal CP and therefore defined as a passing activity that is conducted by a driver overtaking parking vehicles.

\begin{gather*}
\mathtt{CP_{91}} \equiv \mathtt{Pass} \sqcap \exists \mathtt{conducted\_by}^b . \mathtt{Driver} \sqcap \\
\exists \mathtt{has\_participant}^b . \mathtt{Parking\_Vehicle}
\end{gather*}

with $\mathtt{Driver} \equiv \exists \mathtt{drives} . \mathtt{Vehicle}$ and
$\mathtt{Parking\_Vehicle} \sqsupseteq \mathtt{Vehicle} \sqcap \mathtt{Non\_Moving\_Dynamical\_Object} \sqcap \exists \mathtt{intersects} (\mathtt{Parking\_Lane \sqcup \mathtt{Parking\_Space}})$.
The passing activity is augmented using finite look back from the current scene $s_i$, searching for a scene $s_j$ and scenes $s_k$ between $s_i$ and $s_j$ satisfying the passing constraint.

\begin{gather*}
\mathtt{Pass}(A_i, O) \coloneqq  \\
O \in (\mathtt{is\_in\_proximity}.\{A_i\}) \wedge O \in (\mathtt{behind}.\{A_i\}) \wedge \\
\exists s_i \in (\exists \mathtt{has\_traffic\_entity} . \{A_i\}) . \\
O \in (\exists \mathtt{in\_traffic\_model}.\{s_i\}) \wedge \exists s_j \in (\exists \mathtt{before} . \{s_i\}) . \\
\exists A_j \in (\exists \mathtt{in\_traffic\_model}.\{s_j\} \sqcap \exists \mathtt{identical\_to}.\{A_i\}) . \\
\exists O_j \in (\exists \mathtt{in\_traffic\_model}.\{s_j\} \sqcap \exists \mathtt{identical\_to}.\{O\}) . \\
O_j \in (\exists \mathtt{is\_in\_proximity}.\{A_j\}) \wedge
O_j \in (\exists \mathtt{in\_front\_of}.\\\{A_j\})
\forall s_k \in (\exists \mathtt{after} . \{s_j\} \sqcap \exists \mathtt{before} . \{s_i\}). \\
\exists A_k \in (\exists \mathtt{in\_traffic\_model}.\{s_k\} \sqcap \exists \mathtt{identical\_to}.\{A_i\}) . \\
\exists O_k \in (\exists \mathtt{in\_traffic\_model}.\{s_k\} \sqcap \exists \mathtt{identical\_to}.\{O\}) . \\
O_k \in (\exists \mathtt{is\_in\_proximity}.\{A_k\}) \wedge \\
O_k \in (\nexists \mathtt{in\_front\_of}.\{A_k\}) \wedge O_k \in (\nexists \mathtt{behind}.\{A_k\})
\end{gather*}

Due to mixing of universal, existential, and negated existential quantification, this formalization can not be depicted as a rule.

Intersecting Planned Paths (CP 293)

Paths are represented as rays, for which we check whether they intersect in a given threshold ($\tau_1$) and how close it is ($\tau_2$).

\begin{gather*}
\mathtt{CP_{91}} \equiv \mathtt{Dynamical\_Object}^b \sqcap \\
\exists \mathtt{has\_intersecting\_path} . \mathtt{Dynamical\_Object}^b
\end{gather*}

\begin{gather*}
\mathtt{has\_intersecting\_path}(A_1, A_2) \coloneqq \exists p \in \mathbb{R}^2. \\
p \in \text{ray}(p_1, \theta_1) \cap \text{ray}(p_2, \theta_2) \wedge
\frac{\text{dist}(p_1, p)}{s_1} + \frac{\text{dist}(p_2, p)}{s_2} < \tau_1 \wedge \\
\left|\frac{\text{dist}(p_1, p)}{s_1} - \frac{\text{dist}(p_2, p)}{s_2}\right| < \tau_2
\end{gather*}

where $\tau_1 \coloneqq 8 \text{ s}$ and $\tau_2 \coloneqq 3 \text{ s}$.

Heavy Rain (CP 295)

CP 295 is defined as a rain with a precipitation intensity of at least 10 mm/h.

\begin{gather*}
\mathtt{CP_{295}} \equiv \mathtt{Extremely\_Heavy\_Rain} \sqcup \mathtt{Heavy\_Rain}
\end{gather*}
with rules
$\mathtt{Rain}(r) \wedge \mathtt{has\_precipitation\_intensity}(r, x)$
$\wedge x > 50 \rightarrow \mathtt{Extremely\_Heavy\_Rain}(r)$ and
$\mathtt{Rain}(r) \wedge \mathtt{has\_precipitation\_intensity}(r, x) \wedge x \geq 10 \wedge x < 50 \rightarrow \mathtt{Heavy\_Rain}(r)$.

Freezing Temperatures (CP 294)

We define CP 294 as an air individual that has a temperature of below 0 °C.

\begin{gather*}
\mathtt{CP_{294}} \equiv \mathtt{Freezing\_Air}
\end{gather*}
$\mathtt{Air}(a) \wedge \mathtt{has\_temperature}(a, t) \wedge t < 0 \rightarrow \mathtt{Freezing\_Air}(a)$.

Small Distance (CP 83)

We identify any individual that has a small distance to some spatial object as CP 83.

\begin{gather*}
\mathtt{CP_{150}} \equiv \exists \mathtt{{object}_{CP_{150}}} . \mathtt{Spatial\_Object}
\end{gather*}
with $\mathtt{{object}_{CP_{150}}}(A_1, A_2) \coloneqq \text{relevant\_area}(A_1) \cap \text{relevant\_area}(A_2) \neq \emptyset$.
The relevant area is defined as the set of points that can be realistically reached:

\begin{gather*}
\text{relevant\_area}(A_i) \coloneqq \{x \in \mathbb{R}^2 \mid \exists \omega \in [-\omega_i^\mathit{max}, \dots, \omega_i^\mathit{max}]. \\
\exists t < t_H. \exists p \in \{p_i^{fl}, p_i^{fr}\}. \mathit{pos}_\omega(p, s_i, \theta_i, t) = x \}
\end{gather*}
$\mathit{pos}_\omega(p_i, s_i, \theta_i, t) \coloneqq p_i + s_i \cdot t \cdot (\cos (\theta_i^t), \sin (\theta_i^t))$ and

$\theta_i^t \coloneqq \begin{cases} (\theta_i + \text{sgn}(\omega) \cdot \theta_i^\mathit{max} \cdot t - \frac{{\theta_i^\mathit{max}}^2}{2 \cdot \omega}) & \text{if}\, |\omega \cdot t| > \theta_i^\mathit{max} \\ (\theta_i + \frac{\omega \cdot t^2}{2}) & \text{else} \end{cases}$ and $t_H$ is a time horizon (set to 1 s).
<ref> shows two relevant areas and their intersection (in red).

The relevant areas of two vehicles in a following scenario.

Strong Braking Maneuver (CP 103)

Strong braking maneuvers are inferred based on the driven vehicle type.

\begin{gather*}
\mathtt{Motorized\_Road\_Vehicle}^b(v) \wedge \mathtt{has\_acceleration}^b(v, a) \\
\wedge a < -4.61 \rightarrow \mathtt{CP_{103}}(v)\\
\mathtt{Bicycle}^b(v) \wedge \mathtt{has\_acceleration}^b(v, a) \wedge a < -3.3 \\
\rightarrow \mathtt{CP_{103}}(v)
\end{gather*}

High Relative Speed (CP 163)

CP 163 is a vehicle with high relative speed, i.e. $\mathtt{CP_{163}} \equiv \exists \mathtt{{object}_{CP_{163}}} . \top$ with

\mathtt{object}_{\mathtt{CP_{163}}}(A_1, A_2) \coloneqq
\frac{||v_1-v_2||_2}{\min(s_\mathit{max}^\mathit{rule}, s_\mathit{max}^{A_1})} \geq 0.25

where $s_\mathit{max}^\mathit{rule}$ is the maximum allowed speed and $s_\mathit{max}^{A_1}$ is the estimated maximum speed capability of $A_1$.

Occlusion (CP 25)

Occlusions are modeled as $n$-ary relations, allowing multiple occluding objects.
CP 25 is the reified occlusion relation, i.e. $\mathtt{CP_{25}} \equiv \mathtt{Is\_Occlusion}$.

Visualization of occlusions on an inD scene. Occluded areas are orange, occluding objects are blue, and the observer is a purple dot.

Our two-dimensional approach is visualized in <ref>.

We over approximate occlusions by assuming a circular field of view with some visibility range $r$ for an analyzed subject, i.e. $\text{fov}(A_i) \coloneqq \{x \in \mathbb{R}^2 \mid ||c_i-x|| \leq r \}$.
$c_i$ is the point where the sensing of $A_i$ is assumed to be located.
For simplicity,
$$c_i \coloneqq \text{centroid}(g_i)  + (\cos(\theta_i), \sin(\theta_i)) \cdot \frac{||p_i^{bl} - p_i^{fl}||_2}{4}.$$

For a given opaque entity of non-zero height with its polygon exterior $g$ and a subject $A_i$, the left- and rightmost points and relative angles from the viewpoint of $c_i$ are:

* $p_{g,i}^{l} \coloneqq \text{argmin}_{p \in g} \theta_\mathit{rel}(c_i, p)$

* $p_{g,i}^{r} \coloneqq \text{argmax}_{p \in g} \theta_\mathit{rel}(c_i, p)$

* $\theta_{g,i}^{l} \coloneqq \text{min}_{p \in g} \theta_\mathit{rel}(c_i, p)$

* $\theta_{g,i}^{r} \coloneqq \text{max}_{p \in g} \theta_\mathit{rel}(c_i, p)$

where $\theta_\mathit{rel}(c_i, p) \coloneqq \text{arctan2} (p_{i,1} - c_{i,1}, p_{i,0} - c_{i,0})$.
For the edge case that $c_{i,1} \in [\text{min}_{p_i \in g} p_{i,1}, \text{max}_{p_i \in g} p_{i,1}]$ and $\exists p \in g. \theta_\mathit{rel}(c_i, p) \in [270, 360)$ and $\exists p \in g. \theta_\mathit{rel}(c_i, p) \in [0, 90)$, we note that min and max need to be switched in the definitions.

The circular segment spanned by $g$ onto the boundary of the field of view is $\text{circular\_segment}(c_i, r, \theta_{g,i}^{l}, \theta_{g,i}^{r}) \coloneqq \{ r \cdot (\cos(\theta), \sin(\theta)) + c_i \mid \theta \in [\theta_{g,i}^{l}, \theta_{g,i}^{r}] \}.$
The exterior of $g$'s occluded area for $A_i$'s viewpoint is then $\text{occluded}(A_i, g) \coloneqq \text{polygon}(\text{circular\_segment}(c_i, r, \theta_{g,i}^{l}, \theta_{g,i}^{r}) \frown (p_{g,i}^{r}, p_{g,i}^{l})) \cup \text{polygon}(g)$,
with $\frown$ denoting tuple concatenation.
For a geometry $g_O$ of a spatial object $O$ and the subject actor $A_i$, we denote the rate of occlusion of $O$ through $g_1, \dots, g_n$ by[This is not perfectly accurate, but it suffices for our case.]

\begin{gather*}
\delta(A_i, g_O, g_1, \dots, g_n) \coloneqq \\ \frac{\text{area}(g_O) \cap \bigcup_{j=1}^n \text{area}(\text{occluded}(A_i, g_j))}{\text{area}(g_O \cap \text{fov}(A_i))}\text{.}
\end{gather*}

If for an  $\mathtt{Observer}(A)$ and $\mathtt{Spatial\_Object}(O)$ it holds that there are $\{O_1, \dots, O_n\} \sqsubseteq (\mathtt{Spatial\_Object} \sqcap \neg \{A, O\})$ with $\delta(A, O, O_1, \dots, O_n) = d > 0 \wedge \bigwedge_{k=1}^n \exists h \in (\exists \mathtt{has\_height}^{-1}. \{O_k\}). h > 0$
then it there exists an individual $\mathtt{Is\_Occlusion}(N)$ with

* $\mathtt{is\_occluded\_for}(N, A)$,

* $\mathtt{is\_occluded\_by}(N, O_1), \dots, \mathtt{is\_occluded\_by}(N, O_n)$,

* $\mathtt{is\_occluded}(N, O)$,

* $\mathtt{has\_occlusion\_rate}(N, d)$.

Occluded Pedestrian (CP 160)

This phenomenon is:

\begin{gather*}
\mathtt{CP_{160}} \equiv \mathtt{Is\_Occlusion} \sqcap \exists \mathtt{is\_occluded} . \mathtt{Pedestrian}
\end{gather*}

Occluded Traffic Infrastructure (CP 265)

\begin{gather*}
\mathtt{CP_{265}} \equiv \mathtt{Is\_Occlusion} \sqcap \\ \exists \mathtt{is\_occluded} . \mathtt{Traffic\_Infrastrcture}
\end{gather*}

Illegitimate Use of Pedestrian Crossing (CP 69)

The formalizing rule is detailedly presented in <ref>.

Misconduct (CP 143)

We base CP 143 on CP 69 as well as not turning on the vehicle lights in night scenarios.

\begin{gather*}
\mathtt{CP_{143}} \sqsupseteq (\mathtt{Off\_Light\_Vehicle} \sqcap \\
\exists \mathtt{in\_traffic\_model}^b. \mathtt{Night\_Scenario}) \sqcup \mathtt{CP_{69}}
\end{gather*}
$\mathtt{Off\_Light\_Vehicle} \equiv \mathtt{Vehicle} \sqcap 	\nexists \mathtt{consists\_of} (\mathtt{Headlight \sqcap \mathtt{Active\_Lamp}})$ and $\mathtt{Night\_Scenario} \equiv \mathtt{Scenario} \sqcap \exists \mathtt{has\_traffic\_entity} . \mathtt{Night\_Environment}\text{.}$

Lukas Westhofen received the degrees of B.Sc. and M.Sc. (with honors) in computer science by the RWTH Aachen University in 2015 and 2019, specializing on the topics of probabilistic programs and software verification. He currently works at the German Aerospace Center (DLR e.V.) Institute of Systems Engineering for Future Mobility, where his research focuses on developing methods to establish confidence in the safety of automated vehicles. More specifically, his interests include the formalization of knowledge as well as its exploitation for safeguarding automated driving functions.

Christian Neurohr received the B.Sc. and M.Sc. degrees in mathematics in 2011 and 2013 respectively, both from Technische Universität Kaiserslautern, Germany and the Ph.D. degree (Dr. rer. nat.) from Carl von Ossietzky Universität Oldenburg, Germany in 2018. After a short period as a visiting researcher with the MAGMA group at the University of Sydney, he started his occupation as a postdoctoral researcher at the German Aerospace Center (DLR e.V.) Institute of Systems Engineering for Future Mobility where he is working in the area of scenario-based verification and validation of automated vehicles. Specifically, he is the scientific coordinator of the sub-project 'Criticality Analysis' within the project VVMethods.

Martin Butz received the Ph.D. degree (Dr. rer. nat) in mathematics from the University of Regensburg in 2012. Since then he is working as a research engineer in the field of formal methods and software architecture at corporate research of Robert Bosch GmbH in Renningen, Germany. The main focus of his current research is verification and validation of autonomous driving functions, in particular, the application of formal modeling techniques for open context problems.

Maike Scholtes received the B.Sc. and M.Sc. degrees in computational engineering science from RWTH Aachen University, Germany, in 2015 and 2017, respectively, and the Ph.D. degree from the Institute for Automotive Engineering (ika), RWTH Aachen University. During semesters abroad she, inter alia, studied at the University of California, San Diego. After working one year in the area of driving simulation at fka SV Inc. in the Silicon Valley, she started her Ph.D. degree. She works on the assessment of automated driving and ADAS with a focus on machine perception. She received the Dean’s List Award for her M.Sc. degree.

Michael Schuldes received the B.Sc. and M.Sc. degrees in electrical engineering from RWTH Aachen University, Germany, in 2016 and 2019, respectively. He is currently a Research Assistant with the Institute for Automotive Engineering, RWTH Aachen University. His research interests include assessment of autonomous driving functions with a focus on data-driven scenario-based approaches.