Yase - A Holistic Approach for Intelligent Vehicle Simulation Von der Fakultät für Energie-, Verfahrens- und Biotechnik der Universität Stuttgart zur Erlangung der Würde eines Doktors der Ingenieurwissenschaften (Dr.-Ing.) genehmigte Abhandlung Vorgelegt von Max Paul Bauer-Marquardt aus Bühl, Baden-Baden Hauptberichter: Prof. Dr.-Ing Dr. h.c. (DonNTU) Dr. h.c. (RAS/Sib) Hon. Prof. (RAS/Sib) Michael M. Resch Mitberichter: Prof. Dr.-Ing Hans-Christian Reuss Tag der mündlichen Prüfung: 21.01.2025 Institut für Höchstleistungsrechnen der Universität Stuttgart 2025 ii Abstract In the automobile industry there is an ongoing fundamental change towards more intelligent vehicles. This is mainly driven by high hopes regarding economical, safety and ecological benefits. However, the step towards intel- ligent vehicles lead to new challenges in the development and validation of such. This arising complexity cannot be handled any more without proper simulation. However, current simulation approaches still suffer from practi- cal limitations and requirements are not yet fully solved. On the one hand, simulation must be modular, maintainable, and adaptable for manyfold use cases and test levels. On the other hand, the inconsistent landscape of pro- prietary and standardized formats enforces massive redundant work. This thesis provides a framework concept with several contributions to solve these needs. First, a holistic approach is developed, which solves the need for modular- ity as well as the easy combination of multiple input formats and simulator solutions. The architecture is designed according to the established concept of programming language compilers and is developed with state-of-the-art software design standards. The Yase (Acronym for Yet Agnostic Scenario Engine / Yet Another Scenario Engine) framework is a three-stage architec- ture, which allows to connect different input formats to different simulators or sub scopes of them. Hereby all input formats are translated via front ends into an intermediate format, which resides in the middle end. Against this middle end interface, simulators, or sub scopes of them can be implemented independent of the actual input format. For the middle end as the central part of the framework, it is shown what kind of controller architectures are adaptable. Here, multiple controller ar- chitectures are analyzed and compared against each other with the help of ISO defined quality goals. The best fitting concept of behavior trees is then analyzed further regarding their different implementation strategies and a survey of existing open-source projects is presented. Since none of the exist- ing projects fit all the domain specific needs, a Yase specific implementation called Agnostic Behavior Tree (ABT) is presented. iii iv Based on the middle end work, an exemplary back end is built up to demonstrate all derived domain specific use cases. Here, it is shown the first time that the behavior tree concept is capable enough to express all rele- vant intelligent vehicle simulation use cases. First, the implementation of a concrete scenario is shown, as well as extensions such as combinations with evaluations and the usage within an exploitative search. Last, the implemen- tation of driver and traffic models with the same behavior nodes is presented. With a massive traffic simulation, the potential for exploratory searches is highlighted. At the end, it is demonstrated with the OpenSCENARIO DSL front end, how a state-of-the-art scenario language standard can be integrated into the framework. It is explained how the translation with a transpiler to an exe- cutable behavior tree instance works. Furthermore, OpenSCENARIO DSL language specific constructs are discussed, and implementation strategies are presented. Zusammenfassung Die Automobilindustrie ist in den vergangenen Jahren einem fundamentalen Wandel unterworfen hin zu immer intelligenteren Fahrzeugen. Dieser Trend ist getrieben sowohl von hohen ökonomischen und ökologischen, als auch von Erwartungen im Hinblick auf die Erhöhung der Verkehrssicherheit. Der Weg zu solch hochintelligenten Systemen ist jedoch gepflastert mit zahlreichen ungelösten Herausforderungen bei der Entwicklung und der Validation. Die damit einhergehende Komplexität kann nicht mehr ohne Simulation gemeis- tert werden. Jedoch erfüllen die aktuellen Simulationsansätze nicht alle Anforderungen optimal. Auf der einen Seite müssen Simulationslösungen modular, wartbar und anpassbar sein an unterschiedliche Anwendungen und Test-Level. Auf der anderen Seite gibt es aktuell einen massiv redundanten Arbeitsaufwand für die verschiedenen Simulationslösungen aufgrund einer Vielzahl proprietärer und standardisierter Formate. In dieser Arbeit wird das Yase Framework-Konzept vorgestellt, mit dem diese Probleme gelöst werden können. Zuerst wird dazu ein ganzheitlicher Ansatz entwickelt, der zum einen Modularität und zum anderen die Kom- bination von verschiedenen Input-Formaten sowie letztlich Simulatoren er- möglicht. Dabei orientiert sich die Architektur an Programmiersprachen- Compilern und an neusten Software-Design-Standards. Das Ergebnis ist ein Framework namens Yase (Akronym für Yet Agnostic Scenario En- gine, beziehungsweise Yet Another Scenario Engine). Das entwickelte Drei- Phasen-Konzept erlaubt es, unterschiedliche Input-Formate mit verschiede- nen Simulatoren, beziehungsweise Subsets von Simulatoren zu verbinden. Dazu werden alle Input-Formate von Frontends in ein Zwischenformat übersetzt, welches im Middleend verortet ist. Gegen dieses Middleend- Interface können die Simulatoren, oder Subsets von diesen, implementiert werden. Sie sind daher unabhängig vom tatsächlichen Input-Format. Für das Middleend als zentralem Teil der Architektur wird aufgezeigt, welche Controller-Architektur am besten geeignet ist. Dafür werden verschiedene Architekturen analysiert und mithilfe von ISO-definierten Qualitätszielen miteinander verglichen. Die am besten zum Problem v vi passende Lösung, das sogenannte Behavior-Tree-Konzept, wird daraufhin weiter analysiert hinsichtlich schon existierender Open-Source-Projekte und Implementierungsstrategien. Da keines dieser Projekte den Ansprüchen der vorliegenden Aufgabenstellung genügt, wird daraufhin eine angepasste Yase Behavior-Tree-Implementierung namens Agnostic Behavior Tree (ABT) vorgestellt. Basierend auf dem Behavior Tree des Middleends wird ein exemplarisches Backend implementiert, um Domain-spezifische Anwendungen demonstri- eren zu können. Hier wird erstmals aufgezeigt, dass damit alle relevanten Simulationsanwendungen für die Entwicklung intelligenter Fahrzeuge aus- geführt werden können. Zuerst wird die Implementierung eines konkreten Scenarios dargestellt sowie Kombinationen dieses Szenarios mit Evaluierun- gen. Basierend auf diesem Szenario wird die Anwendung in einer explo- rativen Suche dargelegt. Daraufhin wird mit den gleichen Bausteinen die Implementierung von Fahrer- und Verkehrsmodellen demonstriert. Das Po- tential solcher Modelle bei der explorativen Suche wird dann mittels einer umfangreichen Verkehrssimulation aufgezeigt. Schließlich wird mit Hilfe eines OpenSCENARIO-DSL-Frontends beschrieben, wie eine komplexe Szenario-Sprache mithilfe des Yase Frame- work implementiert werden kann. Dabei wird erklärt, wie mithilfe eines Tran- spilers aus Szenario-Dateien ausführbare Behavior-Tree-Instanzen erzeugt werden können. Des Weiteren werden OpenSCENARIO-DSL-spezifische Sprachkonstrukte diskutiert und Implementierungsstrategien vorgestellt. Acknowledgements “No significant research work can be completed done without the contribution of many people.” - Unknown. This statement is definitely valid for this thesis. I would like to thank all, who supported me in this journey. First and foremost, I want to express my gratitude from the depths of my heart to my fiancée Kira Marquardt for the ongoing support, trust, and patience. It has been years with long nights, which are challenging for re- lationships, especially the closest ones. Your ongoing support gave me the energy to pull of this thesis. This is also true for my family and friends, who I like to thank for their support as well. A special thanks is towards my Professor Michael Resch and my Bosch company supervisor Frank Lattemann, who facilitated and supported me during this thesis. The trust, support and given freedom were the foundation for the creativity within this thesis. Furthermore, I like to thank all the colleagues I was working with over the last years. May that be colleagues from within my team, from other companies due to the Yase open-source activities or with standardization projects such as SetLevel or Asam OpenSCENARIO DSL. I want to thank especially those closest ones, who supported me in the development of Yase or gave as active users constant feedback, ideas, and reviews. The list of names is hereby too long to mention, but they will know if they are meant. A dedicated acknowledgment is also towards Anthony Ngo, who also wrote a thesis in the same team and was a partner in crime during this time. The mutual support and exchange were essential for this thesis. Last, but not least, in the spirit of Calvin Cordozar Broadus Jr: “I want to thank me. I want to thank me for believing in me, for doing this hard work. And I want to thank me for never quitting” - and especially for writing this thesis without any usage of AI such as ChatGPT, purely with my own skills and creativity. vii viii Contents 1 Introduction 1 1.1 Intention Behind Intelligent Vehicles . . . . . . . . . . . . . . 1 1.2 Development and Validation Challenges . . . . . . . . . . . . . 2 1.2.1 Increasing Problem Domain Space . . . . . . . . . . . . 3 1.2.2 Agile Development and Testing Level Depth . . . . . . 5 1.3 Simulation as Crucial Element . . . . . . . . . . . . . . . . . . 6 1.3.1 Simulation Approaches . . . . . . . . . . . . . . . . . . 7 1.3.2 State of the Art . . . . . . . . . . . . . . . . . . . . . . 8 1.3.3 Simulation Specific Challenges . . . . . . . . . . . . . . 10 1.4 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4.1 Goal and Requirements . . . . . . . . . . . . . . . . . . 12 1.4.2 Quality Goals . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.3 Technical and Organizational Constraints . . . . . . . . 13 1.5 The Yase Contribution . . . . . . . . . . . . . . . . . . . . . . 14 1.5.1 Document Outline . . . . . . . . . . . . . . . . . . . . 16 2 Yase Architecture Design 17 2.1 Main Design Driver . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Three-stage Compiler Pattern . . . . . . . . . . . . . . . . . . 18 2.3 The Yase Three Stage Concept . . . . . . . . . . . . . . . . . 21 3 Middle End: Scenario Representation 25 3.1 Survey of Control Architectures . . . . . . . . . . . . . . . . . 25 3.1.1 Finite State Machines . . . . . . . . . . . . . . . . . . 26 3.1.2 Hierarchical Finite State Machines . . . . . . . . . . . 26 3.1.3 Decision-Tree Related Architectures . . . . . . . . . . . 27 3.1.4 OpenSCENARIO XML Architecture . . . . . . . . . . 29 3.1.5 Behavior Trees . . . . . . . . . . . . . . . . . . . . . . 31 3.1.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Behavior Tree - State of the Art . . . . . . . . . . . . . . . . . 38 3.3 Behavior Tree Implementation Variants . . . . . . . . . . . . . 40 ix x CONTENTS 3.3.1 First and Second Generation of Behavior Trees . . . . 40 3.3.2 Event Driven Behavior Trees . . . . . . . . . . . . . . . 41 3.3.3 Blackboards . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4 Agnostic Behavior Tree of Yase . . . . . . . . . . . . . . . . . 42 3.4.1 Reason for Yase Development . . . . . . . . . . . . . . 43 3.4.2 Behavior Node Implementation . . . . . . . . . . . . . 43 3.4.3 Behavior Execution and Execution States . . . . . . . 46 3.4.4 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.4.5 Provided Set of ABT Nodes . . . . . . . . . . . . . . . 50 3.4.6 Provided Set of Utility Methods . . . . . . . . . . . . . 52 3.4.7 Implementation Guidelines . . . . . . . . . . . . . . . . 52 3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4 Back End: Holistic Scenario Modeling 57 4.1 MockupSimulator Backend . . . . . . . . . . . . . . . . . . . . 57 4.1.1 MockupSimulator Architecture . . . . . . . . . . . . . 57 4.1.2 Backend: Supported Vehicle Actions . . . . . . . . . . 59 4.2 Implementation of Concrete Scenarios . . . . . . . . . . . . . . 59 4.2.1 EuroNCAP Cut-in Scenario . . . . . . . . . . . . . . . 60 4.2.2 Simulation of the Euro NCAP Cut-in Scenario . . . . . 61 4.2.3 Scenario Checks and Test Criteria . . . . . . . . . . . . 61 4.3 Implementation of Models . . . . . . . . . . . . . . . . . . . . 64 4.3.1 Highway Driver Model Behavior . . . . . . . . . . . . . 65 4.3.2 Traffic Model Behavior . . . . . . . . . . . . . . . . . . 66 4.3.3 Combination of Models and Concrete Scenarios . . . . 66 4.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.4.1 Exploitative Search with the Euro NCAP Cut-in Scenario 67 4.4.2 Exploratory Search with the Traffic Model . . . . . . . 68 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5 Front End - OpenSCENARIO DSL Compiler 75 5.1 The OpenSCENARIO DSL Language . . . . . . . . . . . . . . 75 5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6 Conclusion and Outlook 85 6.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.2 Evaluation of Contributions . . . . . . . . . . . . . . . . . . . 88 6.3 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 CONTENTS xi 7 Appendix 93 7.1 ISO/IEC 25010 Quality Goals . . . . . . . . . . . . . . . . . . 93 7.2 Further Material . . . . . . . . . . . . . . . . . . . . . . . . . 95 xii CONTENTS List of Figures 1.1 Ideogram of the domain space. . . . . . . . . . . . . . . . . . . 4 1.2 Testing pyramid of modern software development. . . . . . . . 6 2.1 The modular three-stage LLVM compiler concept. . . . . . . . 20 2.2 UML diagram of the modular three stage Yase concept. . . . . 22 2.3 UML diagram of the Yase concept in usage in a final product. 24 3.1 Example of a Finite State Machine. . . . . . . . . . . . . . . . 27 3.2 Simplified driver model modeled as decision tree. . . . . . . . 28 3.3 Example of two independent, partly nested Cloe Triggers. . . . 28 3.4 Simplified scenario structure of OpenSCENARIO XML. . . . . 30 3.5 Temporal execution of a ChangeLane behavior with execution states kRunning (blue) and kSuccess (green). . . . . . . . . . . 33 3.6 UML diagram of a simplistic behavior node implementation and its primitives. . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.7 Graphical convention of behavior node primitives and their composition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.8 Graphical convention of first generation node primitives. . . . 41 3.9 Condition check implemented as a decorator. . . . . . . . . . . 41 3.10 Simplified C++ extract of the behavior node base class. . . . . 44 3.11 Simplified C++ extract of the three node primitives. . . . . . 45 3.12 Execution of a behavior tree in Yase. . . . . . . . . . . . . . . 46 3.13 Exemplary execution of a parallel behavior with a Success- Running child behavior. . . . . . . . . . . . . . . . . . . . . . 48 3.14 Simplified C++ extract of generic tasks. . . . . . . . . . . . . 49 3.15 Different terminal convenience prints of a behavior tree. . . . . 53 3.16 Simplified extract of the C++ blackboard interface. . . . . . . 54 4.1 The MockupSimulator decorator node above a generic subtree. 59 4.2 The scenario behavior Euro NCAP Cut-in. . . . . . . . . . . . 60 xiii xiv LIST OF FIGURES 4.3 Phases of the Euro NCAP Cut-in scenario with its behavior execution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.4 Simulation setup of the Euro NCAP Cut-in scenario with a separate test case. . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.5 Simulation of the Euro NCAP Cut-in scenario with integrated test criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.6 Highway driver model behavior composed out of basic behaviors. 65 4.7 The TrafficModel behavior using the HighWayModel. . . . . . 66 4.8 The combined CutInTrafficModel behavior. . . . . . . . . . . . 67 4.9 The test setup behavior for the exploratory search. . . . . . . 68 4.10 Critical distance map of eploitative search with the Euro NCAP scenario. . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.11 Exploratory test setup with random traffic. . . . . . . . . . . . 69 4.12 Average traffic distance with confidence intervals. . . . . . . . 72 4.13 Average simulation duration with confidence intervals. . . . . 72 4.14 Actual traffic participant density during simulation run. . . . . 73 5.1 Simplified extract of the OpenSCENARIO DSL grammar with aspects of behavior description. . . . . . . . . . . . . . . . . . 77 5.2 Simple OpenSCENARIO DSL scenario example with two ve- hicle actors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.3 Generated Abstract Syntax Tree (AST) of the dynamic be- havior part of scenario 5.2. . . . . . . . . . . . . . . . . . . . . 80 5.4 Generated behavior tree of scenario 5.2. . . . . . . . . . . . . . 80 5.5 Example in which the imported scenario 5.2 is instantiated with different actor assignment. . . . . . . . . . . . . . . . . . 81 5.6 Generated behavior tree of scenario 5.5. . . . . . . . . . . . . . 82 5.7 Simple scenario with one behavior and a modifier. . . . . . . . 82 5.8 Generated behavior tree of scenario 5.7 with a modifier. . . . . 83 7.1 Simplified C++ example of a lane change node. . . . . . . . . 96 7.2 Pseudo code of a visitor implementation. . . . . . . . . . . . . 97 7.3 Code line count of the Agnostic Behavior Tree package (with the cloc tool). . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.4 Code line count of the Agnostic Type System package (with the cloc tool). . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.5 Code line count of the OpenSCENARIO DSL front end pack- age (with the cloc tool). . . . . . . . . . . . . . . . . . . . . . 98 List of Tables 3.1 Comparison of the functional suitability. . . . . . . . . . . . . 36 3.2 Comparison of usability. . . . . . . . . . . . . . . . . . . . . . 36 3.3 Comparison of maintainability. . . . . . . . . . . . . . . . . . . 37 3.4 Comparison of the different architectures. . . . . . . . . . . . . 37 xv xvi LIST OF TABLES List of Acronyms ABS Antilock Braking System ABT Agnostic Behavior Tree ACC Adaptive Cruise Control AD Autonomous Driving ADAS Advanced Driver Assistance System AEB Automatic Emergency Braking ANTLR ANother Tool for Language Recognition ASAM Association Standardization of Automation and Measuring Systems AST Abstract Syntax Tree ATS Agnostic Type System BNF Backus–Naur form BT Behavior Tree CD Continuous Development CI Continuous Integration DSL Domain Specific language DT Decision Tree EBNF Extended Backus–Naur form EDA Event-driven architecture ESC Electronic Stability Control xvii xviii LIST OF TABLES FSA Finite State Automaton FSM Finite State Machine GCC GNU Compiler Collection HIL Hardware in the Loop H-FSM Hierarchical Finite State Machine LLVM Low Level Virtual Machine NPC Non Player Characte SIL Software in the Loop SUMO Simulation of Urban MObility VTD Virtual Test Drive V2V Vehicle-to-Vehicle V2X Vehicle-to-X YASE Yet Agnostic Scenario Engine / Yet Another Scenario Engine Chapter 1 Introduction The development towards more intelligent vehicles is together with the change from combustion engines to electric engines the most significant trend in the automobile industry. Intelligent vehicles take over more responsibil- ities from human drivers and economic and ecological benefits due to less accidents, optimized traffic flow, car sharing, etc. are expected. However, the rising complexity of intelligent vehicles requires a more complex devel- opment and validation. In the following, general development challenges of such systems are elaborated. Subsequent, it is shown that simulation is a crucial element to tackle the rising complexity. Here, the state of the art is presented, and the current limitations are discussed. Based on this, a prob- lem statement for holistic simulation frameworks is defined. This includes a requirement and quality goal analysis with the help of international stan- dards and software architecture templates. Last, the contribution of this thesis with the Yase concept to solve these holistic needs are discussed and the outline of this thesis is presented. 1.1 Intention Behind Intelligent Vehicles In the last decades a development towards an increased vehicle automati- zation can be observed [1], [2]. At the beginning, small systems such as the Anti-lock Braking System (ABS) were introduced to reduce skid while braking. Further Advanced Driver Assistance Systems (ADAS) such as Elec- tronic Stability Control (ESC) were added later to improve overall safety of the drivers. With time, the focus opened from safety to comfort as well. Next to safety systems such as Automatic Emergency Braking (AEB), other sys- tems focused on increasing comfort as the Adaptive Cruise Control (ACC). In parallel to the automatization of the vehicle systems itself, vehicles are also 1 2 CHAPTER 1. INTRODUCTION getting more connected to benefit from synergy effects. Vehicle-to-Vehicle (V2V) communication between vehicles allows to predict and forecast situa- tions better. Vehicle-to-X (V2X) communication with infrastructure enables the interaction with the static environment such as traffic lights. The overall goal of these developments are Autonomous Driving (AD) vehicles, which can take over all responsibilities from the driver and integrate themselves in the surrounding environment in the most comfortable, safest, economic, and ecological way. The conglomerate of these developments is summarized in the following thesis as intelligent vehicle development. The reasons for this trend within the automotive industry towards full vehicle automatization is hereby man- ifold. On the economic side car manufacturers try to segregate themselves from other competitors by offering more advanced assistance systems. These assistance systems can increase the driving comfort and the safety of passen- gers. Additionally, full automatization towards autonomous driving levels allow to exploit new market fields. AD vehicles can be deployed as robo cabs, which allows manufacturers to become mobility providers. With re- source efficient utilization with less idle states of such AD vehicles, even high development costs can be amortized fast. Despite these economic interests, there is also a general interest of the society in intelligent vehicles. The sys- tem automatization promises to reduce the number of fatal accidents, injuries and collision related financial damages. Also, less traffic is promised, as bet- ter utilization and organization of the traffic could lead to improved traffic flow. And last, there is an expectation of a more ecological and resource efficient transportation approach, as the traffic flows could be improved, and shared resources lead to overall less consumption. 1.2 Development and Validation Challenges While intelligent vehicles are desirable in general from a safety, economic and ecological perspective, there are still challenges which must be solved first. The development of such intelligent vehicles is an ongoing process, and it is getting more and more complex. This is caused by two main challenges: On the one hand the increasing variety of intelligent vehicle features to develop and the resulting large domain space to test. And on the other side the agile software development environment with continuous development and testing and an increased testing level depth. 1.2. DEVELOPMENT AND VALIDATION CHALLENGES 3 1.2.1 Increasing Problem Domain Space With more and more intelligent vehicles, the problem domain space gets also more complex. Simple safety systems such as Automatic Emergency Brak- ing (AEB) may be restricted to simple domain spaces with highway similar environments and no lane interpretation at all. Full AD systems on the other hand must be able to handle significant more situations. As an example, this includes consideration of all surrounding lanes with an appropriate scene un- derstanding, interpretation of regulatory elements such as traffic lights and speed limits, prediction of vehicles, pedestrians, bicyclists, emergency vehi- cles, and any combination of those. This sheer size of this new technology domain space introduces a never seen complexity in the automobile industry. With a continuous test space, each smallest parameter variation or com- bination can create a new unique situation. Therefore, it is impossible to completely cover the scenario space fully, but only to a certain extent. Under the assumption, one could span up an adequate domain scenario set D, the set would be extremely large. In [3], the authors claim that it would be necessary to test ”11 billion miles to demonstrate with 95% confidence that autonomous vehicles (AVs) are 20% better than humans”. Other sources come to similar numbers in the same magnitude of order, stating that such test coverage cannot be provided with realistic capabilities before market launch [4]. However, from this full domain space only a subset R is relevant for testing, as in the majority of scenarios the system under test has no impact on the situation. An example of an irrelevant scenario may be a vehicle behind with enough safety distance performing a lane change, which has no effect on the system under test at all. This set of relevant scenarios can be divided further into a smaller subset O of objective scenarios. In these scenarios the system under test must react over the normal extent to prevent accidents or other incidents. The most important subset within these objective scenarios is the critical subset C. These scenarios are challenging scenarios, which have a high probability to cause a critical or undefined system behavior and must be fixed and developed further. Each of these subsets are distinct smaller than the set in which they reside. D ⊂ R ⊂ O ⊂ C (1.1) Many already faced fatal accidents of intelligent vehicle systems occurred in unexpected situations, as it can be observed in the deadly Tesla crash 2016 [5]. Such situations come only into awareness after they happened as it is not known prior where the potential critical situations are located within the scenario space. Finding such critical scenarios in the full domain set D is a non-trivial problem and is literally like finding a needle in a Haystack. Fur- 4 CHAPTER 1. INTRODUCTION Do ma in sce na rio set D Re lev an t s cen ari o s ub set R Ob jec tiv e s cen ari o s ub set O Cr itic al sce na rio sub set C Figure 1.1: Ideogram of the domain space. 1.2. DEVELOPMENT AND VALIDATION CHALLENGES 5 thermore, development and testing resources are limited to economical and practical constraints. As stated in [4], the full scenario space is impossible to cover fully. Therefore, it is important to provide solutions, which allow to ex- plore the scenario space in a meaningful way to make statistical assumptions about the general coverage of the remaining scenario space. Furthermore, the areas with critical scenarios should be exploited as much as possible to identify all corner cases. 1.2.2 Agile Development and Testing Level Depth Besides the sheer size of the domain space to test, another challenge for the automobile industry is the change from a traditional end of line test towards agile software development. Modern software development requires agile de- velopment with constant retesting in Continuous Integration & Continuous Development (CI&CD) pipelines. This is due to the fact, that any new com- mit in a code base has the potential to alter the overall state to a defective state. All previously made tests are in theory therefore not informative any- more. As in large projects with hundreds of developers such code changes come in easily a hundred times a day, these tests must be executed for every change. This is often accompanied by further nightly, weekly and several release stages tests. With the already huge domain scenario space, this need for constant retesting accumulates the numbers of tests even further. Additionally, the growing complexity with an interplay of more and more components requires more in-depth tests. Final acceptance tests with real test drives with the full system are by far not sufficient enough. Like the development of mechanical engines, each component must be tested in sep- aration before the fully assembled system is tested. This is also an essential requirement of modern software development. Here, the testing levels are typically distinguished into four levels [6]: At first, the smallest units of the compiled code are tested regarding their functionality. The goal is to ensure the intended base unit functionality, such as functions, classes and methods work as expected. This is typically tested with example and corner case val- ues, to capture potential undefined behaviors. Once the base is tested, the first functional components serving a certain self-contained use case can be tested via component testing. As soon as the functionality of each separate component is assured, the overall system can be tested as whole. For this, the components are combined and tested. Hereby errors can be found, which emerge from the complex interplay of the components itself. The last test level are acceptance tests which validate if the customers need is actually fulfilled. Together, all of these levels form up a full testing pyramid as seen in Fig. 1.2. 6 CHAPTER 1. INTRODUCTION Unit tests Component tests System tests Acceptance tests Figure 1.2: Testing pyramid of modern software development. These testing levels can be mapped for intelligent vehicle development. Acceptance tests are hereby test drives in real traffic, to prove the overall functionality. System tests are specifically created scenarios, in which the system is tested against certain corner cases. In component tests, individual components can be tested in isolation with component specific scenarios. As an example, the planner component, responsible to drive within the environ- ment, can be tested with perfect perception data to ensure its functionality. Last, even the lowest functions such as Kalman filters or perception cluster algorithms can be tested as well in isolation. 1.3 Simulation as Crucial Element With this great complexity, simulation became one of the essential key ele- ments to tackle these challenges. This is since any system under test can be stimulated with artificial sensor data with varying quality to test it [7], [8], [9]. Here, no limitations are given. The system itself can be simulated in dif- ferent ways, such as in Hardware in the Loop (HIL) as well as in Software in the Loop (SIL) platforms. Also, the sensor input data can be generated with different quality levels and even with specific fault injection to test corner cases. Since the system under test can be separated into its individual com- ponents, simulation can be also used to simulate on all levels of the testing pyramid shown in 1.2. One great benefit is that simulation does not require actual vehicles or test drivers. Therefore, it is not safety critical and does not endanger lives of test drivers or other traffic participants. This allows to test situations with potential crashes, which could not be done in reality due to safety or financial impacts. Furthermore, the absence of target hardware and human drivers make simulations about magnitudes of orders faster and 1.3. SIMULATION AS CRUCIAL ELEMENT 7 cheaper. While in real world tests a vehicle must be brought in certain sit- uations in a controlled environment during work hours of the testing team, simulation can run the same tests with no preparation even faster than real time at any time. The simulation computation costs are in comparison to the target hardware and employee cost negligible. Also, with the only re- quirement of computing power, dynamic simulation scaling on servers is only restricted by financial limits. While simulation can never replace real world tests fully, the majority of tests is nowadays done with simulation due to its benefits. This importance can be seen in the 2021 Waymo safety report [10], in which they state that they have driven 15+ billion simulated miles versus 20+ million real world autonomously driven miles. 1.3.1 Simulation Approaches As shown, simulation is an essential element in the development and test- ing process. Simulation gives here several possibilities to cover the scenario domain space. For the following thesis, they are differentiated into three main categories: Simulation of concrete scenarios, exploitative searches, and exploratory searches. Simulation of concrete scenarios The simplest use case is the simulation of concrete scenarios. Hereby a con- crete scenario flow is simulated to test the reaction of the system under test. Concrete scenarios play an essential role in homologation, such as in the Euro NCAP [11] and UN ALKS protocols [12]. Here, regulatory authorities pro- vide test sets with certain concrete scenarios to pass as the bare minimum. With this, vehicle manufacturers and suppliers can show and guarantee a certain quality level. On the development side, concrete scenarios are also important. They allow to create new test situations, against which the sys- tem can be developed. Once those scenarios are mastered, they can be added to a CI&CD pipeline as regression test. This prevents that already achieved functionality is altered to a defective state within the later development. The sources for such concrete scenarios can be manifold. One main source are the created use case scenarios of the developers and test engineers themselves. They usually create the most important scenarios, as they know the most about the peculiarities of the system. Once the systems are tested in reality, recorded scenarios can be an important source for concrete scenarios as well. These scenarios can be either a replay of trajectories or with a more generic scenario description, which allow further variation. Additionally, the test set can be enriched by scenarios from accident databases or by representative 8 CHAPTER 1. INTRODUCTION scenario sets generated with traffic studies. Exploitation of scenario spaces Concrete scenarios with a fixed scenario flow are essential to test a certain situation. They often also serve as a base scenario for exploitation when it is required to cover more of such scenario instances. This can be done by discretization and variation of scenario parameters. As an example, the UN ALKS protocols [12] dictates the variation for each concrete scenario parameter. In the cut in scenario for example the speed of a challenging vehicle as well as the cut in distance is varied. It is also defined in which bounds the system under test must react in which way. With this approach it is possible to exploit greater areas in the scenario domain space. Exploration of scenario spaces While exploitation allows to search the scenario space around known and representative base scenarios, broader search approaches are needed to cover more of the scenario domain space. Exploratory searches need to explore areas outside of known scopes. In best case the search is here in promising areas for critical scenarios within the domain space. Approaches for such exploratory searches can be manifolded. One approach may be combinato- rial composition of smaller scenario behaviors to create greater and unique scenarios. Other approaches can be the generation of random traffic around a system under test, which constantly creates new and unique test situations. 1.3.2 State of the Art With simulation as such an essential element, a large eco system has de- veloped around it. Multiple organizations work on standards to create a common basis among the industry. Furthermore, multiple open source and commercial simulators aim to solve the industry needs. Also, several co- simulation frameworks claim to enhance the connection between simulators and different systems under tests. Standards With multiple companies and organizations working on the same problem, there is a desire for a more standardized development across companies. However as often, unique solutions, incompatible approaches, and company interest lead to a fragmented landscape of diverging standards. The Associ- ation Standardization of Automation and Measuring Systems (ASAM) [13] 1.3. SIMULATION AS CRUCIAL ELEMENT 9 alone lists six different, partly incompatible standards for simulation. Fur- thermore, they develop more than eleven also relevant standards in the field of Test Automation and Data Management & Analysis. Due to this magni- tude of standards, the main focus is in the following on scenario description languages. A broad analysis of such scenario description languages can be found in [14]. Subsequent, only the two OpenSCENARIO language versions are introduced since they are the only standardized scenario description lan- guages. OpenSCENARIO XML [15] is a xml-based standardized scenario file for- mat. It is designed to execute imperative scenarios across multiple simula- tors. The standard defines a static hierarchical scenario structure with state machines nodes. Also, it provides concrete catalogs with actors and actions. Parameter variation is a minor focus here. Due to its longer existence, the easy to parse xml-based format and its concrete, static scenario structure, the standard is currently widely distributed. OpenSCENARIO DSL [16] is the successor of OpenSCENARIO XML and aims to evolve the previous version. However, while the same naming indicates consistency between the versions, it is a completely new language with nearly no connections to the previous one. The changes address the fol- lowing critics and demanding needs: The first critic of the previous version is the xml-based description. While it is easy to parse xml from a devel- oper perspective, the syntactical overhead which comes with xml decreases human readability. For this reason, OpenSCENARIO DSL changed towards a self-defined Domain Specific language (DSL), which improves readability. A second critic point is the static scenario structure, which makes it hard to modify, extend or combine scenarios. Due to this, the static structure is abducted and replaced with a modular approach in which any tree like hierarchy can be build up. Besides the advanced readability and modularity, the new standard version tried to include a large list of new features. Besides concrete scenario execution, the goal is that the standard can also serve to define full test plans with evaluations and domain space coverage. This re- quired a fundamental paradigm change from an imperative towards a more declarative language. Simulators Several commercial tool providers provide solutions for intelligent vehicle simulation. In the following, the most important ones in the automotive industry are briefly introduced. Virtual Test Drive (VTD) [17] is a widely distributed and according to their website the world’s most widely used sim- ulator platform for intelligent vehicles. It provides a simulator with a visu- 10 CHAPTER 1. INTRODUCTION alization engine and is the main driver behind the OpenSCENARIO XML standard. The IPG CarMaker [18] is also a widely distributed simulator. It provides similar features such as VTD, however it is also highly known for its realistic vehicle dynamic and powertrain simulation. Besides these commer- cial tool providers, there exists also a magnitude of successful open-source projects. The Carla simulator [19] is with more than 2.2 thousand forks and 7.5 thousand stars one the most actively developed open-source simulator. It convinces with an Unreal based visualization and its open structure, as well as with its large community. The openPASS simulator [20] is mainly developed by the German automobile industry to serve as a standardization playground and exchange platform. It allows to generate and run several test suites and provides a simplistic visualization. Esmini [21] is another simulator which is mainly developed by Volvo. It is a lightweight simula- tor with a basic visualization. Mostly it is known for its OpenSCENARIO XML implementation, which makes it the standard implementation of the OpenSCENARIO XML standard. SUMO (Simulation of Urban MObility) [22] is a multi-modal traffic simulation package, which is intended to be used within other simulators. Its focus is on the generation on realistic traffic simulations. Co-Simulation Frameworks Besides simulators and standards, there exists a multitude of co-simulation frameworks, which aim to connect the different simulator solutions with sys- tem under tests. The Bosch developed Cloe framework [23] is an abstraction layer between vehicle simulators and system implementations. It allows to exchange simulators since everything is internally mapped to an internal data format. The Eclipse MOSAIC co-simulation framework is intended for con- nected and automated mobility [24]. Simulators can be connected here with different models and exchange via communication. In the paper [25] another approach is introduced to combine such multiple simulators. Like the Cloe approach, the framework allows to connect different simulators and systems via an internal data representation. 1.3.3 Simulation Specific Challenges The current simulation landscape suffers from several challenges. The first one is the scattered landscape of standards. Even within the standardized in- put file formats there are contradictions. For example, one might expect that the OpenSCENARIO XML and OpenSCENARIO DSL versions are consis- tent, but with the version increment, a contradictory approach was chosen. 1.4. PROBLEM STATEMENT 11 While the first version is built as an imperative language, the second one bases on a declarative approach. This magnitude of contradictory standards causes a lack of support by simulation tools. Since each standard requires integration and maintenance effort, simulation tools support either only a selected standard to a limited support or just an own defined input format language. Sharing this development effort collaboratively is difficult since each simulator introduces its own world data representation and architec- ture. This causes redundant development effort for each simulator solution. The co-simulation frameworks are here also of minor help. They circum- vent the mentioned problems by connecting different simulators. This leaves the redundant effort for the simulators itself untouched. Also, the integra- tion costs are shifted towards the integration of the simulators and systems against the framework specific world data format. Either this data format is solution specific, or they rely again on one of the many standards. As the last point, most of the solutions are still developed with a mental mind set of testing on a system and acceptance test level. Nearly all simulators provide many features but are too monolithic and slow to be used in deeper test levels such as in component or unit test levels. While this traditional testing approach is still important, the other levels are essential for modern software development. 1.4 Problem Statement As it was shown, the field of intelligent vehicle development and testing is complex. A nearly infinite domain space needs to be covered on a reoccurring basis with reasonable effort. Simulation solutions are essential to tackle these problems. However, there is on the one side a wide range of simulators with a growing number of open and proprietary input standards on the other side, which are also getting more complex. This puts simulation tool providers in the unfavorable position to provide more and more combinations with increasing effort. Therefore, a solution is needed, which helps to solve the rising complexity of intelligent vehicle simulation and the practical problems within the simulation landscape. In the following this solution space is nar- rowed down systematically with the help of the arc42 architecture template [26]. First, the overall goal is defined, and its requirements are derived. Sub- sequent, quality goals to guide the implementations are determined. Last, constraints, restricting the solution space, are gathered. 12 CHAPTER 1. INTRODUCTION 1.4.1 Goal and Requirements A framework is needed, which helps to solve the rising complexity of intel- ligent vehicle development and the practical challenges within the simula- tion landscape. Such a framework must enable minimizing redundant work by developing input file format compilers collaboratively for multiple tar- get simulators. Also, it should be possible to use one or more simulators with different sub scopes and combinations as co-simulation if needed. To be holistic, the framework must be capable enough to represent all necessary intelligent vehicle simulation use cases. Furthermore, it must be usable in an incremental way so it can be used on each test level. Based on this goal, the following requirements are derived: Req. 1: Agnostic development of input format compilers and sim- ulator bindings The redundant development of input format compilers for different simula- tors must be reduced. This concerns for example scenario formats, simulation and system configuration formats, and map formats. While all of them are important, the focus of this thesis will be on scenario formats. The solu- tion must provide a way in which the integration of a new input scenario format can be split into two independent sub tasks: The development of an input format compiler, which processes all format specific tasks which are independent of the underlying simulator. And the development of simula- tor specific bindings, which allow to connect this with a simulator specific implementation. Req. 2: Incremental simulation for all test levels Since all test levels of the testing pyramid are important, the framework must be built up in such a way that it can be used for all levels. It must be possible to test the full intelligent vehicle stack with simulation, but also down scaled simulations are needed to test for example the perception unit in isolation. Such a holistic framework must allow to build up highly customized simula- tion solutions to match exactly the complexity of each individual test. For this it is necessary to be able to produce different simulation output qual- ity, either by providing different simulation scopes or the usage of different simulators, even as co-simulation. In this thesis a simulator scope refers to a smaller but more lightweight subset of the full simulator set. Furthermore, the whole framework basis must be designed in such a way, that it is inherent to be used in unit tests. This concludes for example the avoidance of network or inter-process communication. 1.4. PROBLEM STATEMENT 13 Req. 3: Ability to perform concrete, exploitative and exploratory searches A holistic framework must be able to represent any kind of intelligent vehicle simulation use case. This includes the simulation of concrete scenarios for regression tests and basic development. Furthermore, it must enable more advanced domain space search approaches for homologation. This includes the exploitation of local scenarios spaces and exploration of large scenario areas in the domain space. 1.4.2 Quality Goals To evaluate a software product quality, the ISO/IEC 25010 [27] introduces eight characteristics. They are Functional Suitability, Performance efficiency, Compatibility, Usability, Reliability, Security, Maintainability and Portabil- ity. Not all of these characteristics are relevant for every project. The arc42 reference guide [26] advises to choose the top three relevant characteristics for a project. Since the goal is to provide an easy-to-use framework to minimize development and maintenance effort, the following three quality goals are chosen for this project: Functional Suitability, Usability, and Maintainabil- ity. The concrete definitions of these characteristics are given in the appendix 7.1; 1.4.3 Technical and Organizational Constraints While the requirements and the quality goals define the solution space, it is restricted further by technical and organizational constraints. In the field of intelligent vehicle simulation, the following constraints exist: Constraint 1: Industry Adequate C++ Code In the industry there are constraints for the code itself. On the one hand, it must be performant enough for real-time capable applications. On the other hand, it must support safety argumentation required by standards such as the ISO26262 [28]. The current language of choice in the industry for production code is hereby C++. The ISO driven standardization also guarantees long term API stability to a certain degree. This performant language allows to write real-time capable applications and the static type system also adds an extra layer of reliability. Furthermore, a rich eco system with libraries and commercial support such as for static code analysis allows to write better and safer code. While this could be achieved also with other languages, the interaction with other, mainly C++ based code is often an extra hurdle. 14 CHAPTER 1. INTRODUCTION Therefore, C++ shall be used as the underlying language for the current work. Furthermore, the code must be of an industry adequate level, ensured by extensive unit testing, static code analysis and usage of style guides. Constraint 2: Simplicity As already pointed out, one overall goal is to reduce integration and mainte- nance costs. Therefore, only well-known designs and solutions shall be used so developers have a low barrier to entry when interacting with the frame- work. Furthermore, the usage of simulation standards and own developed world data representations shall be avoided. This is due the already dis- cussed effect, that the simulation landscape is yet in a scattered state and no commonly accepted standard exist yet. Users should not be forced to use a specific standard, but they should always build in such standards on top. 1.5 The Yase Contribution The field of intelligent vehicle simulation is fairly complex and even with the fact that a multitude of simulation solutions exists, the author is not aware of a solution which solves the specified goal above in a sufficient way. For this reason, the so called Yase (Yet Agnostic Scenario Engine/ Yet Another Scenario Engine) framework is presented in this thesis. It is an input for- mat and simulator agnostic scenario engine. The three-stage approach allows to design and develop scenario format compilers (front ends) and simulator adapters (back ends) independent of each other. Internally it bases on Be- havior Trees (BT) to link everything together. With its modular approach it is also applicable for holistic and incremental simulation of all testing levels. This work contributes to the state-of-the-art research regarding intelligent vehicle simulation for testing and validation in multiple ways. The specific contributions can be summarized as follows: • Development of a holistic and incremental simulation frame- work: For the derived problem space, the concept a three-stage frame- work approach with a middle end, front ends, and back ends is devel- oped. It is capable to perform holistic simulation while being incre- mental and agnostic. • Analysis of control architectures: For the scenario representation independent of input file formats and simulators, the most important control architectures are elaborated. Furthermore, they are evaluated with the help of ISO quality goals. 1.5. THE YASE CONTRIBUTION 15 • Introduction to behavior trees: The general concept of behav- ior trees is presented. In this context the most canonical implemen- tation strategies, graphical representation, and terminology is intro- duced. Furthermore, the behavior tree characteristics are compared to the other control architectures. • Agnostic Behavior Tree (ABT) implementation: Next, the Yase behavior tree implementation is introduced. This implementation is specifically designed for the intelligent vehicle simulation domain. The implementation serves as the basis for the further work and is also released open-source. • Demonstration of simulator back end implementation: Within this context the implementation of a simulator back end based on the agnostic behavior tree is demonstrated. Hereby the implementation of behavior nodes is discussed, and a representative scenario is built up. The scenario is hereby used to exploit a two-dimensional scenario space. Furthermore, it is discussed how driver and traffic models can be build up with the same behaviors. With this as basis, a massive traffic simulation is simulated to demonstrate an exploratory search. Despite scenario simulation, the behavior tree can be used as a full simulation engine. It is shown that behavior trees are able to fulfill all needs of simulators such as scheduling, ensuring data consistency and more. • Demonstration of a compiler frontend implementation: To demonstrate a Yase front end implementation, the implementation of such is demonstrated exemplarily for the OpenSCENARIO DSL lan- guage. Here, the general process from translating an input file to an ex- ecutable behavior tree is pointed out. Furthermore, OpenSCENARIO DSL specific features are discussed, and implementation strategies are shown. • Open sourced implementation: Next to theoretical concepts, the most important contribution of this thesis is the open-sourced imple- mentation. This allows to collaborate among different companies. As a sub project under the openPASS repository, it is a well-established project with an active community [29]. Besides the noted contributions, the Yase concept already serves as the basis for more developments. Especially to mention is the Agnostic Type System (ATS), which is next to the Agnostic Behavior Tree (ABT) a central element in the Yase middle end. Furthermore, open sourced and company intern 16 CHAPTER 1. INTRODUCTION front ends and back ends are developed on this basis. However, these are not part of this thesis. 1.5.1 Document Outline The following thesis is structured into five chapters. First, the overall Yase architecture with its separation into three logical stages is presented. It is shown how the concept is derived from the successful design pattern of com- puter language compilers. This results into a separation of the problem into an intermediate scenario representation as a middle end, scenario language specific front ends and simulator specific back ends. Secondly, the inter- mediate representation of scenarios as the underlying interface of the other stages is elaborated. Hereby potential approaches are discussed and com- pared against each other. For the subsequent work the concept of behavior trees is used as the intermediate representation of scenarios. As behavior trees are not a strictly defined concept, several implementation strategies and open-source projects are summarized and evaluated. Based on this, the Yase specific implementation is derived. In the fourth chapter it is shown how the Yase middle end with its behavior tree can be used to implement a simulation specific back end. First, several exemplary behavior node im- plementations are introduced, which serve as a basis for the following more complex behaviors. Hereby it is also discussed how the approach can be used to model the whole simulation as behavior tree. With so called MockupSim- ulator, the implementation of concrete scenarios is demonstrated exemplary with an Euro NCAP scenario. Secondly, it is shown how reactive behaviors such as driver and traffic models can be designed out of the same behavior nodes. The presented models are then evaluated regarding their capabilities of exploratory traffic simulation. Last, the concrete scenario is used for an exploitative search to find critical scenarios. In the next chapter, the stage of scenario language specific front ends is elaborated. Hereby it is presented for the OpenSCENARIO DSL standard, how a front end can compile such a scenario with the help of an Extended Backus–Naur form (EBNF) grammar and transpilers into an executable behavior tree. The last chapter recapitu- lates the outcomes of this thesis. Here, is summarized how the concept meets the defined requirements and quality goals. Finally, the current state of the Yase project and its open-source community is presented. Chapter 2 Yase Architecture Design In this chapter the overall architecture design of the Yase (Acronym for Yet Agnostic Scenario Engine / Yet Another Scenario Engine) framework is presented. First, the main design driver is identified, and the problem is compared to the design of programming language compilers. It is shown how the typical architecture of programming language compilers is built to fulfill the same requirement. Based on this, a three-stage architecture for the Yase framework is presented. These three stages separation also serves as the layout for the following thesis. 2.1 Main Design Driver The goal of the Yase framework is to enable holistic simulation-based devel- opment and testing of intelligent vehicle systems in complex and changing software and tool environments. This requires all deduced requirements of section 1.4.1 to be fulfilled. However, some of these requirements are more influential on the overall architecture design then others. In the current case, the first requirement 1.4.1 stating agnosticism regarding input file formats and simulators and sub scopes is the most important one. Simulation in large industry and research cooperations is usually quite incompatible among the individual projects. This is caused by project specific needs, which often lead to the usage of different simulators, tools, and processes. Since the industry is lacking generally accepted scenario or simulation input file standards, many simulators and tools use their own propriety formats. This causes tremen- dous efforts when sharing and cooperating among projects. While in general combinations of multiple simulators (co-simulation) and sharing data with other simulation solutions is desired and encouraged, the benefits are often less than the effort to integrate the different simulation solutions. This is 17 18 CHAPTER 2. YASE ARCHITECTURE DESIGN since for each simulation solution an adapter is necessary to read in a dif- ferent format. The number of required adapters for complete compatibility among all input formats and tools rises in the worst case quadratic with the number of tool and input formats. adaptersmax = formats× tools (2.1) Furthermore, writing adapters is usually not trivial and expensive. The initial high effort cultivates ongoing work in parallel and self-contained simulation solutions with little reuse for other projects, sometimes even in one common project. As another side effect, it increases lock-in effects in various degrees on tool vendors, since already existing data bases can often just be interpreted by one specific tool. The Yase concept aims to avoid this by enabling the development of parsers for input files independent and reusable for different simulators. On the one hand it should be possible to develop input file parsers agnostic of the underling simulator. On the other hand, simulators should be usable agnostic of the used input file format. This is the basis for joint development of shared and reusable tools. A similar problem exists in the field of computer language compilers. Compiler programs consume files of a given high level programming language, mostly human readable languages. These are then translated into lower-level languages which usually is executed on a certain target hardware. Contrary to interpreters, which translate and execute programming languages line by line, compilers first parse the full file into an intermediate representation. This intermediate representation allows to realize performance optimizations and safety checks before translating the code further. Last, compilers trans- late this intermediate representation into executable instructions for the given target hardware. Compilers are also designed from the perspective that there exists a multitude of programming languages on the one side and multiple target hardware architectures on the other side. Most compilers alleviate the problem by using the intermediate representation as an abstraction layer be- tween the input formats and the output format. This allows to separate the problem into tools which read in input files into the abstract intermediate representation and tools which translates this into a set of instructions for the target hardware. 2.2 Three-stage Compiler Pattern Compilers are a well-studied research field in computer science and proven in praxis [30]. For these compilers a common design pattern evolved over the years with a clear separation of concerns. The compiler architecture is hereby 2.2. THREE-STAGE COMPILER PATTERN 19 separated into the three stages of front ends, a middle end and back ends. The most important stage is the middle end with the intermediate representation. It is a low-level representation of the given problem domain and serves as an abstraction layer. Front ends for specific programming languages parse and translate files into the intermediate representation of the middle end. This intermediate representation then serves as the interface for a back end. It takes the intermediate representation and translates it into the necessary instructions for a given target platform. In the Fig. 2.1 the LLVM (Low Level Virtual Machine) compiler [31] is illustrated as an example for the LLVM is together with the GCC (GNU Compiler Collection) [32] the most established compiler and has a special focus on modularity and extensibility. For the LLVM compiler there exist a magnitude of front ends and back ends. As an example, the C++ Clang frontend [33] parses and translates C++ files into the LLVM intermediate representation. From there on it can be directly executed on different target hardware such as ARM or X86 via back ends. The modular ith an intermediate representation as abstraction layer scales well with more combinations. The problem of parsing a specific input file is decoupled from the translation to a certain target hardware. adaptersmax = formats+ target (2.2) While the direct translation has a quadratic complexity rise as shown in equation 2.1, the intermediate representation reduces it to a linear complexity rise for each new format or target architecture as shown in equation 2.2. As an example, the developers of the relatively new computer language Rust avoided to write their own compiler, but developed a Rust front end for the existing LLVM compiler instead [34]. With this front end they were directly able to compile Rust code on all target hardware which are already supported by LLVM. Middle end: Abstraction layer for domain problem The basis of a compiler middle end is an abstraction layer, which is capable to represent the full domain space as an intermediate representation without loss of information. Often, the code is represented as an Abstract Syntax Tree (AST). It represents the essential syntax of the code in a tree structure. Irrelevant syntax such as comments, empty lines can be pruned before. Fur- thermore, programming specific syntax is translated in the abstract format. Based on this abstract representation, it is possible to reason about further performance optimization independent of any given input file format. Typ- ically, compilers eliminate instructions, which do not have any effect. This may be calculations of unused variables or removal of code, which can never 20 CHAPTER 2. YASE ARCHITECTURE DESIGN C++ Clang Front End Fortran Front End Rust Front End LLVM Middle End X86 Back End Arm Back End MSP430 Back End Figure 2.1: The modular three-stage LLVM compiler concept. be reached. Such optimization is done under the strict “as if” rule. It states that any optimization is allowed under the constraint that the result is the same as if it would have been without optimization. Furthermore, middle ends can perform safety checks such as type checks and finding memory leaks. Front end: Lexing and parsing Compiler front ends are responsible to translate files of a certain input format into the AST structure of the middle end. These front ends are often unique since the language formats can differ strongly. Hereby the given language format is defined with the help of a grammar such as Backus-Naur-Form (BNF) or the Extended-Backus-Naur-Form (EBNF) [35]. The process of file parsing can be divided into the lexical analysis and the syntactical analysis. The lexical analysis is done with Lexers, which are sometimes also called Tokenizers. They split up the input file into a sequence of tokens. The tokens are keywords defined in the grammar and it allows to check for ambiguities or undefined tokens. Once the input file is translated into a valid stream of tokens, it serves as the input for the parser. Parsers perform syntactical analysis on the given input token stream. Hereby the relative occurrence of the tokens is checked against the grammar and transformed into the abstract syntax tree. This AST can then be processed further in the middle end by traversing the tree with the help of visitors. Since front ends are needed for many use cases, there exist multiple transpilers (also sometimes called compiler-compiler) to support the development of such. 2.3. THE YASE THREE STAGE CONCEPT 21 Back end: Platform specific execution In the last compiler stage, the back end translates the processed and opti- mized intermediate representation into processor specific instructions. Since processor architectures differ, for each processor architecture an individual back end is required. Besides just translating, the back ends can also perform further optimizations, as it has knowledge of the specific hardware architec- ture. Compilers usually support a variety of target hardware. As an example, the LLVM compiler can support many processor architectures such as X86, ARM or PowerPC. 2.3 The Yase Three Stage Concept Programming language compilers solve a comparable problem as scenario en- gines. In both cases one or more input file formats must be parsed. For com- pilers it is computer language files and for scenario engines scenario descrip- tion files. This is then translated into a logical sequence of instructions for a given target. Here, compilers produce sequences of hardware instructions for a certain hardware setup. Scenario engines on the other hand produce a sequence of action instructions for one or more given simulators. The only difference is the fact that the high-level language input format is translated to a sequence of simulation instructions instead of hardware instructions. As the established language compiler design scales well for supporting multiple input formats and targets, it is a promising architecture for Yase. Therefore, Yase is consequently build up as a three-stage approach with a middle end, front ends and back ends. In Fig. 2.2 the concept is presented which demon- strates how a back end and front end can be developed agnostic of each other. In a final project, the relevant back ends and front ends are imported and combined to a project specific scenario engine as shown In Fig. 2.3 . The three stages serve also as the layout of thesis. Hereby each stage with the specific design decisions is elaborated in individual chapters. Middle end: Intermediate representation of scenarios The most important stage of the design is the middle end with its interme- diate representation. This serves as the abstraction layer between any input format specific front enddd and the simulator specific back ends. Therefore, the Yase middle end with its intermediate representation must be expressive enough to represent the full domain space of simulation. The most impor- tant content to express are simulation behaviors of multiple kinds: Scenario 22 CHAPTER 2. YASE ARCHITECTURE DESIGN Figure 2.2: UML diagram of the modular three stage Yase concept. behaviors, simulation runtime behaviors and sensor model behaviors. There- fore, the middle end must provide a behavior representation, which allows to model and combine such behaviors in a generic way. Some input formats instantiate these behaviors with additional static typed input arguments, therefore there must be possibilities to express behavior definitions in a type safe way. This can be done with the Agnostic Type System package which contains a static type system with type safe function expressions, arithmetic expressions, user defined type definitions, casts and conversions. This simu- lator and scenario file agnostic convenience tool is also included in the middle end. While the type system is also an integral part of Yase, the focus of this thesis will be solely on the representation of the dynamic behaviors. Back end: Platform Specific Execution A back end in the Yase context is any set of supported behavior primitives, which should be made available for front ends. These primitives must be modeled in the way as defined by the middle end. The scope of a back end is hereby unconstrained. It can be either the full set of all possible behavior instructions for a given simulator. Alternatively, this full set is split into multiple, self-consistent back ends for simulator sub scopes. This allows to slice the content of a simulator into different system cuts and provide only what is needed for a specific simulation. Furthermore, multiple simulators and simulator system cuts can be combined later on. 2.3. THE YASE THREE STAGE CONCEPT 23 Front end: Input File Translation Yase front ends provide the mechanisms to translate a specific input format into a consistent and executable simulation in the way defined by the mid- dle end. This is highly input format dependent as they differ in semantics and syntax. As an example, the OpenSCENARIO XML standard defines a static scenario structure in a XML format, while the OpenSCENARIO DSL standard uses an own Domain Specific Language (DSL). The front end com- piles everything which is independent of any simulator. At places in which an implementation specific behavior must be placed in, it uses a key value storage provided by the Agnostic Type System to look up and place actions. With this generic key value storage, the front end does not need prior knowl- edge of the supported content and can be developed independent of it. The key value storage is later filled by all used back ends, which introduce their scopes via dependency injection. While the focus of this thesis is on scenario execution, the same approach can be used to parse configuration files in the same way. This can include for example sensor setups with different sensor model behaviors. 24 CHAPTER 2. YASE ARCHITECTURE DESIGN Figure 2.3: UML diagram of the Yase concept in usage in a final product. Chapter 3 Middle End: Scenario Representation The central element of the Yase concept is the middle end stage as the in- terface between front ends and middle ends. For this purpose, a powerful intermediate representation is needed, which is capable enough to represent all types of scenarios. While there are several aspects of such a scenario representation, the most important one is the representation of the dynamic content of a scenario. In this section the design of the middle end is elabo- rated. First, the most important control architectures are examined, which could serve as such an intermediate scenario representation. Subsequently, it is shown why and how behavior trees fit best for the task. After the com- parison, the behavior tree concept is investigated further. Hereby the most common implementation strategies and open-source projects are presented and compared. Based on this, the agnostic behavior tree architecture to match the domain specific use case of Yase is presented. Hereby the termi- nology and design are compared with other implementations. 3.1 Survey of Control Architectures Control architectures are mental models to structure actions in a meaningful way that they can express a behavior over time dependent on given input. Such models are elementary in computer science and robotics. The most common ones are hereby Finite State Machines (FSMs) and Hierarchical Fi- nite State Machines (H-FSM). Also, Decision Tree (DT) similar approaches can help to model behaviors. Besides these well studied models, manifold lesser-known architectures exist. Examples in the AD/ADAS industry are scenario engines closely implemented after the OpenSCENARIO XML sce- 25 26 CHAPTER 3. MIDDLE END: SCENARIO REPRESENTATION nario structure. A further, relatively new concept from the gaming industry is Behavior Trees. 3.1.1 Finite State Machines A Finite State Machine (FSM) or Finite State Automaton (FSA) is an el- ementary conceptual model in computer science to describe transitions be- tween states [36], [37]. FSMs consist of a set of possible states with conditions for transitions between these states. A Finite State Machine can be seen as a graph, where the vertices represent the states and directed edges represent the transitions with their conditions. At any given time, FSMs can be only in exactly one state of the finite set of possible states. With a given initial state and all given inputs, the FSM and its trace is fully defined. As one of the first established models, automata theory became an essential part of the computer science. Due to its simplicity, this model is used in practical applications in many fields. However, while FSMs are easy to understand and implement for simple systems with low complexity, they often get overly complicated for larger systems. Adding, removing, relocating, or modifying states can potentially affect any other states within the graph. This is caused by the nature of the graph structure, where each state can potentially have a transition to any other state including itself. For a given FSM with N states, the number of potential transitions transitionsmax rise quadratic with the number of possible states: transitionsmax = N ×N (3.1) The potential quadratic rise of transitions worsens the ability to add or re- move a new state since potentially all existing nodes may have to be revisited due to transition dependencies. An additional problem is that FSMs often lead in implementations to a tight coupling of states and the transitions with their trigger conditions. The transition to the next state is often integrated within the state itself, which is comparable to the problematic “goTo” expres- sion. This mixture makes it hard to implement generic behaviors independent of the circumstances they are used in. 3.1.2 Hierarchical Finite State Machines Since the complexity becomes more difficult to handle with growing number of states, the classical FSM concept was improved over time towards hier- archical FSMs (H-FSM) [38], [39], [40]. With this extension, self-contained parts of a FSM are packed into greater states, often called “SuperStates”. 3.1. SURVEY OF CONTROL ARCHITECTURES 27 Figure 3.1: Example of a Finite State Machine. Each “SuperStates” provides unique entry and exit points for the underling FSM and therefore allows to model more abstract FSMs with defined in- terfaces. Since these “SuperStates” can be nested again in arbitrary depth, the H-FSM exhibit a hierarchy which gives the extension its name. The hi- erarchical grouping of independent parts reduces complexity and eases the understanding by grouping sub behaviors. But it still does not solve the problem fully. At each hierarchy level the complexity can still have N × N complexity, whereas N is the number of states at the specific level. 3.1.3 Decision-Tree Related Architectures FSMs and their extensions show good capabilities on processing procedural tasks, however often reactive systems are needed which can perform actions based on certain condition changes in the environment. To solve this prob- lem, several approaches have been developed. In this thesis, they are sum- marized under the term “Decision-Tree Related Architectures” [41], but they are also sometimes refereed as Event-driven architecture (EDA), Trigger En- gines or Event Engines. All these architectures perform actions as a reaction on certain events. The concrete implementation can hereby differ. Some implementations re-evaluate the events in every step, while others evaluate them only once. Some implementations check for all events equally in paral- 28 CHAPTER 3. MIDDLE END: SCENARIO REPRESENTATION LaneAheadFree ? FollowLane LaneLeftFree ? LaneChange[Left] LaneRightFree ? LaneChangeRight Decelerate Figure 3.2: Simplified driver model modeled as decision tree. Cloe Triggers Once[StartEvent1] Action1 Once[StartEvent2] Once[StartEvent3] Action3 Once[StartEvent4] Action4 Figure 3.3: Example of two independent, partly nested Cloe Triggers. lel, while others may have some sort of priority order. Some implementations even allow deeper nesting of events. In Fig. 3.2 an exemplary decision tree implementation of a simplified driver model is presented. This decision tree can be evaluated in every step to enable reactive behavior. The conditions, such as LaneAheadFree?, are evaluated to choose either the left or right branch. Based on the current en- vironment state, the decision tree can be traversed in every step to find the adequate driver model action. Similar solutions are implemented in many simulators and simulator frameworks to solve various use cases. As an ex- ample, the Cloe simulation framework provides a Trigger Engine [42], which allows to perform actions and evaluations within the simulations based on events. In the specific Cloe case, all triggers are evaluated in parallel until each trigger is evaluated once. Furthermore, the Cloe framework allows to combine multiple triggers into greater triggers. An exemplary setup can be seen in Figure 3.3. While such decision tree related approaches show good reactiveness, they have disadvantages. Procedural tasks such as sequences are not intended in the concept and require additional internal state vari- ables to model it. Also, the execution of parallel tasks can be modeled only 3.1. SURVEY OF CONTROL ARCHITECTURES 29 as separate and independent trees. This complicates the generation of large, partly reactive, partly parallel, and partly procedural scenarios. 3.1.4 OpenSCENARIO XML Architecture Within the intelligent vehicle simulation community, first standardization ef- forts regarding scenario description and execution were taken with the Open- SCENARIO XML standard [15], [43],. The result is a mixture of a static hierarchical scenario structure with finite state machines at certain levels. In Figure 3.4 a simplified version of the scenario structure is visualized. It consists of the following levels: • A Scenario contains one InitPhase and one Storyboard for the dynamic content. • An InitPhase contains zero or more parallel InitActions. • A Storyboard contains one StopTrigger, which runs zero or more Stories in parallel. • A Story contains one or more Acts, which are executed in parallel. • An Act contains one mandatory StartTrigger and an optional StopTrigger. It executes zero or more ManeuverGroups in parallel. • A ManeuverGroup contains zero or more Actors references. For these Actors zero or more Maneuvers can be defined, which run in parallel. • A Maneuver contains one or more Events, which run in parallel based on a FSM and EventPolicies. • An Event consists of a StartTrigger and one or more Actions, which run in parallel. While the structure is static and strictly hierarchical, some levels contain FSM logic. As an example, actors are represented as FSMs and also the se- lection of Events in the Maneuver level are chosen via a FSM logic and Event- Policies in a decision tree similar style. This standard has been influential for the execution model of many simulator implementations. As an example, in the simulator esmini [44] and the deprecated openPASS scenario engine im- plementation [45] this static scenario structure is implemented. Each level of the scenario tree is resembled with an equivalent C++ class, which contains the logic as defined in the standard. 30 CHAPTER 3. MIDDLE END: SCENARIO REPRESENTATION Scenario InitPhase InitAction1 . . . StopTrigger Storyboard Story StartTrigger StopTrigger[Optional] Act ManeuverGroup Maneuver StartTrigger Event Action . . . . . . . . . . . . . . . . . . Figure 3.4: Simplified scenario structure of OpenSCENARIO XML. 3.1. SURVEY OF CONTROL ARCHITECTURES 31 However, the description and implementation of scenarios with the static OpenSCENARIO XML scenario structure has drawbacks. First, the static scenario structure obtains a high complexity for even simple scenarios. Even if only one action should be executed in a scenario, the whole scenario tree shown in Figure 3.4 has to be build up. This adds up to twelve partly su- perfluous hierarchy levels, which is also difficult to comprehend for users. Secondly, the static scenario structure impedes modularization and abstrac- tion. The scenario structure can only grow in width, while the depth of the scenario is defined by the standard. Also, elementary operations such as the StopTrigger and StartTrigger are restricted to certain levels. These tight rules make separation of abstract sub scenarios difficult. Third, the execution model lacks elementary operators to combine and extend behav- iors. Since all levels are intended to run in parallel, elementary composition operations such as sequences of actions can only be modeled with Start/Stop- Trigger and synchronized state variables. These synchronized state variables build up dependencies between different scenario parts and make the overall scenario difficult to maintain and extend. 3.1.5 Behavior Trees In the recent past, modular, maintainable, and reusable development of Non- Player Character (NPC) in gaming became more important. Implementa- tions with complex FSMs and H-FSMs have shown to be difficult to develop and maintain with the rising complexity. To overcome these problems, the concept of behavior trees was first developed in 2005 for the game “Halo” [46]. Since then behavior trees became the standard in gaming engines and robotics [47], [48], [49], [50]. As the concept is relatively new, there is no canonical design pattern yet and manifold implementation varieties exist. However, all behavior trees consist of three basic concepts, which are canoni- cal among all major implementations. The representation of behaviors in an object orientated way as nodes, the stepwise execution and the general node primitive’s classification, which allow to compose trees of behaviors. Behavior Nodes and Execution States The general idea behind behavior trees is to encapsulate a task or any other arbitrary behavior as a self-contained behavior node class. The sole pur- pose of such a node is to express its specific behavior. As an example, a lane change of a vehicle in the simulation context can be modeled with a ChangeLane behavior node. To trigger the execution of one small step of the behavior (also refereed as to execute or tick a behavior), behavior nodes 32 CHAPTER 3. MIDDLE END: SCENARIO REPRESENTATION provide an API method, usually named executeTick(). Most intelligent vehi- cle simulators proceeded the simulation time with discrete time steps. While some behavior tasks can be executed immediately in full extent, others need to be stretched over a certain duration. For example the ChangeLane be- havior needs multiple ticks to perform the full behavior, while a ButtonPress behavior could potentially finish within one step. To be able to track the execution process from the outside independent of the underlying behavior, the executeTick() method returns an execution state. All behavior tree im- plementations consist of the basic execution states kRunning, kSuccess and kFailure. A behavior which is executed, but is not finished yet, possesses the state kRunning. This state indicates that the behavior needs to be re- executed at least one more time in order to finish the intended behavior. Once a behavior is executed fully in the desired way, the status changes to kSuccess. Contrary, if it was not possible to express the intended behavior, a kFailure status is returned. These execution states are inherent to the be- havior tree concept, as it allows to observe the current execution state from the outside and compose behavior nodes agnostic of their implementation in upstream logic. In Fig. 3.5 an example for the temporal execution is given for the Change- Lane behavior. The simulation step width is set in the example with a time delta ∆t = 1s. With the first tick, the behavior node starts expressing the intended behavior in the simulation environment by moving the vehicle to- wards the adjacent lane. As the lane change requires time, the node preforms only a small part of the behavior at each simulation step. During this pro- cess, the behavior node indicates the yet unfinished behavior progress with the execution status Running. This information is used by the simulator to re-execute the behavior in the subsequent steps. Once the lane change is successfully performed, the returned execution state changes to kSuccess. As the ChangeLane is the sole behavior to execute, the simulator can stop the simulation at this point and report the positive feedback of a successful scenario execution. In an alternative simulation situation with the circum- stances of no adjacent lane, the ChangeLane behavior would return a kFailure to indicate that the desired behavior cannot be expressed. In this case the simulator can decide how to handle the execution state kFailure, for example with a simulation abort. Behavior Node Primitves To be able to treat all behavior nodes the same, they are all derived from one generic behavior node interface as shown in the UML diagram in Fig. 3.6. Hereby, this abstract behavior node is in most implementations derived fur- 3.1. SURVEY OF CONTROL ARCHITECTURES 33 t = 0s,∆t = 1s ChangeLane[Left] t = 1s,∆t = 1s ChangeLane[Left] t = 2s,∆t = 1s ChangeLane[Left] Figure 3.5: Temporal execution of a ChangeLane behavior with execution states kRunning (blue) and kSuccess (green). Figure 3.6: UML diagram of a simplistic behavior node implementation and its primitives. ther into three primitives: Actions, Decorators and Composites. Behaviors, performing atomic tasks, are called Actions and are represented as rectan- gles (see Fig. 3.7a). Actions perform usually atomic tasks, for which it does not make sense to split the behavior further and therefore it can be fully ex- pressed with one node. An example is the previously described ChangeLane behavior. But often such behaviors need to be used in slightly different con- texts or it is necessary to extend the underlying behavior partly to a given situation. This can be done with Decorator nodes, which allow to extend the logic of other behaviors without modifying the underlying behavior it- self. The ChangeLane action for example may be used in a driver model and here it should perform the lane change only if the adjacent lane is free. Or it may be used to create a critical situation, in which the lane change must be performed when a reference vehicle is approaching on the lane to change to. A third example is when the lane change should be performed twice over two lanes. Instead of creating specialized actions for each use case, decorator 34 CHAPTER 3. MIDDLE END: SCENARIO REPRESENTATION behaviors allow to extend the underlying behavior. Decorators can perform logic before and after the execution of the decorated child behavior and al- low to modify the returned execution state of the child. Due to that reason, decorators can influence if, when, how long, under which circumstances and how many times an underlying behavior node is executed. As decorators can only decorate one child behavior, they are represented as a rectangle on top of the behavior to decorate as displayed in Fig. 3.7b. In the example the ChangeLane node is decorated with a Repeat decorator, which repeats the underlying behavior two times. With this approach the double lane change can be modeled together with a Repeat decorator instead with a partly redun- dant action DoubleChangeLane. Furthermore, the generic Repeat decorator can now also be reused to decorate any other behavior. Contrary to Decora- ChangeLane[Left] (a) Action. Repeat[2] ChangeLane[Right] (b) Decorator. ThreeChangeLanes → ChangeLane[Left] Repeat[2] ChangeLane[Right] (c) Composite. Figure 3.7: Graphical convention of behavior node primitives and their com- position. tor nodes, the Composite nodes (or lesser known as Flow-control nodes) allow to combine more than one behavior to a greater behavior. Here, any kind of composition of underling behaviors can be implemented. However, among most implementations three common composites are dominant as they cover the most elementary composition operations: The Sequence composite allows to execute multiple child behaviors in a row. Here, the first child is executed until it returns kSuccess, which causes the next child to be executed from the next tick on. The typical execution order is from the left child to the right until all children are executed successfully. If one of the children fails during the process, the sequence aborts also with a kFailure. In Figure 3.7c such a sequence is presented with the commonly used → symbol. With the Parallel composite it is possible to execute multiple behaviors in parallel. This is for example necessary to model the independent behaviors of two vehicles in parallel. Here, the executeTick() method call is passed to all child behaviors in each tick. Once a child behavior succeeds, it is not ticked anymore in the subsequent steps. The Parallel composite succeeds once all child behaviors succeed. Same as with the sequence, a kFailure of one child causes a kFail- ure of the whole composite. Parallel composites are represented with the ⇒ 3.1. SURVEY OF CONTROL ARCHITECTURES 35 symbol. To allow reactive behaviors, most implementations provide also a Selector composite (sometimes also refereed as Priority Selector or Fallback Selector), which is labeled with the ? symbol. This composite executes the child behaviors subsequently within a tick until one child behavior can han- dle the situation with a kRunning or kSuccess state. Hereby it is allowed that a child behavior returns a kFailure as long there is still a fallback child behavior which is not failing. Besides these standard composites, any other specialized composite is allowed to combine multiple behaviors. These ba- sic node primitives (composites, decorators, and actions) are the building blocks, which allow to build up any arbitrary behavior tree. Hereby there is no limitation regarding the tree structure in terms of depth or width. 3.1.6 Evaluation To determine the best fitting control architecture for the Yase middle end, the presented architectures are evaluated in the following against each other. Hereby the ISO quality goals presented in 1.4.2 with their sub characteristics are used. Each architecture is given a point in a category if they stand out in comparison to the other architectures. The decisions are hereby based on the discussions of the previous sections. Functional Suitability This quality goal is divided into three sub characteristics. The functional completeness defines the degree to which specific tasks and user objects are covered. FSMs, H-FSMs and BTs are used in practice for a long time in nearly all fields. Therefore, it can be assumed that they could cover all as- pects. OSC1 and DT are on the other hand restricted to certain domains such as decision making or lack of elementary operations such as sequences. Functional correctness defines the degree to which a product provides correct results. Here, all architectures are comparable except BTs, which show addi- tional benefits in this field due to their explicit kFailure state. This execution state allows inherently build in failure management. Functional appropriate- ness is the degree to which the architecture facilitates the accomplishment of specified tasks and objectives. Since this prerequisites completeness, these architectures are within in the shortlist for appropriateness. However due to the hard to maintain complexity of FSMs, only H-FSMs and BTs are considered here as appropriate. 36 CHAPTER 3. MIDDLE END: SCENARIO REPRESENTATION FSM H-FSM DT OSC1 BT Completeness + + 0 0 + Correctness 0 0 0 0 + Appropriateness 0 + 0 0 + Table 3.1: Comparison of the functional suitability. Usability The quality goal is divided into six sub characteristics, from which only three are considered here. To make conscientious evaluations for the categories ap- propriateness recognizability, user interface aesthetics and accessibility, more user studies would need to be done. Learnability on the other side is given for all broadly known architectures, as they are teached as basics in the field of computer theory. The exception is OSC1, which is a quite complex standard with a lot of peculiarities. In the field of operability, BTs and DTs are given a point since they provide easy entry points and a clear tree structure. For user error protection, the BTs get credit again for introducing failures as an inherent state. FSM H-FSM DT OSC1 BT Learnability + + + 0 + Operability 0 0 + 0 + User error protection 0 0 0 0 + Table 3.2: Comparison of usability. Maintainability The maintainability criteria define the ability to modify, improve, correct, and adapt a system to changes of its environment or requirements. In the subcategory modularity, all tree-based approaches have superior characteris- tics compared to graph structures, since they have minimal and clear inter dependencies as shown before. Since H-FSMs are a step towards this direc- tion, they are given a point as well for this category. In terms of reusability and modifiability the tree-based approach is also beneficial. Furthermore, a second design pattern of behavior trees makes them superior to FSMs and H-FSMs in terms of reusability. In FSMs the implementation of states con- tains the transitions towards other nodes together with the actual state task. 3.1. SURVEY OF CONTROL ARCHITECTURES 37 This is can be compared to goto statements within code, which are consid- ered harmful [51]. Furthermore, the tight coupling of transitions and tasks to perform is complicated to separate afterwards. In the concept of behavior trees, tasks and transitions are separated. Action nodes solely perform tasks, while the task of transitioning between nodes is handled specialized compos- ite nodes. This decoupling makes the concept more modular in the sense of separation of concerns. Regarding analyzability, there is again a clear advan- tage for the tree-based approaches. Failures and impacts of changes can be traced back easily along tree branches. In the last category testability, none of the concepts exhibits noteworthy benefits. FSM H-FSM DT OSC1 BT Modularity 0 + + 0 + Reusability 0 0 + 0 + Modifiability 0 0 + 0 + Analysability 0 0 0 0 + Testability 0 0 0 0 0 Table 3.3: Comparison of maintainability. Decision For Yase In table 3.4 the results of the quality goals are accumulated. It can be observed that the behavior tree approach shows superior characteristics in nearly all criteria. One reason for this good result is that behavior trees FSM H-FSM DT OSC1 BT Functional Suitability 1 2 0 0 3 Usability 1 1 2 0 3 Maintainability 0 1 3 0 4 Overall 2 4 5 0 10 Table 3.4: Comparison of the different architectures. incorporate the best concepts of the other architectures while using proven good software practices such as separation of concerns. As discussed in the section 3.1.5, behavior trees advance on the one hand the hierarchical ab- straction of H-FSMs by using a tree structure. On the other hand, they separate tasks and transitions between nodes into two independent prob- lems. Furthermore, they incorporate the idea of decision trees. As shown in 38 CHAPTER 3. MIDDLE END: SCENARIO REPRESENTATION [47] the FSMs, H-FSM and DT architectures can be expressed with behavior trees. Since the OpenSCENARIO XML approach is also a mixture of the previous mentioned architectures, it can be also modeled as behavior tree as well. This gives the best of all architectures. Another reason is the sim- plicity, which allows users to easily understand, visualize, and narrow down failures to sub trees. The effect can be observed since all gaming engines provide some sort of behavior tree packages for game designers to model their behaviors. With the superior characteristics and the widespread usage across many industries, behavior trees are the most promising candidate for the Yase middle end. Due to that reason, the following concepts will be built on behavior trees as basis. The appropriateness of behavior trees as an intermediate representation layer shall be underlined with the following quote: “The behavior tree becomes a domain specific language (DSL) with efficient interpreter.”[52] 3.2 Behavior Tree - State of the Art Since Behavior Trees are not a standardized concept, the most influential implementations and publications are presented first. The relevance criteria in this thesis are either influential publications in this research area, relevance for intelligent vehicle simulation or widely used implementations. BehaviorTree.CPP Implementation The BehaviorTree.CPP project [53] provides a C++ library with a behavior tree framework. With more than 350 forks and an active community it is the most popular behavior tree project for C++. It bases on the influential work “Behavior Trees in Robotics and AI” of Michele Colledanchise and Petter Ogren [47]. While its original focus is on robotics, it is also intended to be usable in other contexts. Since the implementation is provided as a lightweight C++ library, it can be used even in the smallest projects. This is essential for the usage in all levels of incremental simulation. Besides the core library with the behavior tree, it provides also a rich eco system with a GUI and convenience functionality such as logging. One downside is the XML based configuration of trees, which is tightly coupled in the implementation. Furthermore, it partly consists of outdated concepts (such as condition primitives) of the so called first generation of behavior trees. 3.2. BEHAVIOR TREE - STATE OF THE ART 39 Gam