A Novel Framework for Verification and Validation of Simulations of Autonomous Robots

Dr. Phillip J. Durst, Mr. David McInnis, Mr. Jeremy Davis, Dr. Christopher T. Goodin

Abstract

Modelling and simulation (M&S) plays a critical role in both engineering and basic research processes. However, M&S is only truly useful if the model and simulation outputs are accurate. As such, signi cant research has been undertaken to establish what \accurate" means for simulations and what subsequent level of “trust" should be given to M&S outputs. Trust in M&S outputs is established by verifying and validating the models and simulations. While a wealth of research can be found to de ne veri cation and validation (V&V) for traditional M&S, little research has been done to define a methodology for the V&V of simulations of complex, intelligent, and autonomous systems. Speci cally, no methodology for V&V of simulations of autonomous robots has been developed to date. This paper presents a brief overview of the current V&V methods in use for traditional simulations. In light of this review, a novel framework for the V&V of simulations for predicting the behaviors of autonomous robots is developed, and this framework is presented in detail. This V&V framework is then applied to the use-case of an autonomous unmanned ground vehicle's (UGV's) navigation task. The framework is applied for model validation of Global Positioning System (GPS), inertial measurement unit (IMU), and RGB camera sensor models. The framework is further applied to validate these sensor models for an example camera-based autonomous navigation algorithm, stop sign detection.

Keywords: autonomous systems, veri cation and validation, simulation accuracy, senor simulations, environment modelling

1. Introduction

Computer simulations of physical systems and processes became a critical part of science and engineering research in the mid to late 1960s as computer systems became smaller, faster, and more readily available. In these early modelling and simulation applications, models were formulated as mathematical representations of a physical system, and simulations were the execution of a model over time. This M&S method was realized as the completion of this two-step process. For example, forecasting weather involves rst establishing mathematical equations representing environmental phenomena and second solving these equations over a suitable time domain. Therefore, the initial theories of M&S can be thought of as the accepted methods for breaking down physical systems into these two steps such that the M&S results could be considered accurate.

These initial approaches to M&S and the early applications of M&S to realworld applications can be found in [1], [2], and [3]. Formal M&S concepts where then further re ned in [4]. Similarly, the concept of V&V of models and simulations can be found in [5] (much more on this topic later). These early simulations were readily adopted into a wide range of research areas, including geology [6], human anatomy and biology [7], and electronics [8]. These early studies and simulation applications gave rise to the proli c use of simulations seen today.

Starting from the 1970s, the concept of veri cation and validation (V&V) of simulation models started to become formalized as theoretical frameworks and methods for V&V. The concept of V&V became necessary once M&S was applied to practical engineering problems. Simulations of slow-changing physical processes, such as geological changes over the course of several years, can be useful without necessarily being precisely accurate. On the other hand, simulations of engineering systems, like a car engine, must be extremely accurate to be used in the design and development process.

V&V is a critical step in the model development process; for a model/simulation tool to be adopted for use, assurances must be made that the simulation provides accurate results. Veri cation of a model ensures that the model works as expected. Veri cation is a software-level process that does not necessarily require information about the model's outputs; it is more of a check that the model's equations are implemented in software correctly. Validation is the testing of a model's outputs against experimental data to see if the model provides accurate outputs. Together, V&V of a model and/or simulation insures that they work correctly and provides accurate and meaningful outputs.

An agreed-upon theory and methodology for V&V of the di erent types of models used today exists, and will be shown in Section 2. However, there is one major area where the techniques presented in this section fall short: simulations of intelligent and autonomous systems, such as autonomous robots. Simulations of autonomous robots and their perception and intelligence algorithms do not involve a single model or even a coupled system of two models but rather are simulation environments: software tools involving multiple models working in concert to simulate the outputs or behaviors of complex systems. While each individual model can be veri ed and validated (V&Ved) using the standard, accepted methods, this type of V&V does not necessarily guarantee that the overall simulation outputs will be accurate.

To that end, this paper proposes a new framework for the V&V of simulation environments for autonomous robots. As a test case, this paper focuses on how this framework could be applied to simulating autonomous unmanned ground vehicles (UGVs). The new V&V framework is built on the theories and frameworks already established and in use by the simulation community. An overview of these theories is presented in the following section, and the Proposed V&V Approach section presents the new framework for V&V of simulation environments for simulating autonomous robots. The Example Application of the Proposed Framework section applies the new V&V framework to an example UGV navigation algorithm: stop sign detection. Finally, the Conclusion section provides some closing thoughts.

Several important terms are used throughout this paper, and it is pertinent to defi ne them here. For the purposes of this paper, the following de nitions for V&V “methodology" and “V&V framework" will be used:

V&V Methodology: The speci c tests used to V&V a model, simulation, or simulation environment and the sub-systems thereof.

V&V Framework: The sequential steps in which V&V methods should be applied, the interactions between these steps, and the metrics for measuring final model, simulation, or simulation environment's degree of V&V.

As for model and simulation, the de nitions originally provided by [9] are used:

Model: A physical, mathematical, or otherwise logical representation of a system, entity, phenomenon, or process.

Simulation: A method for implementing a model over time.

2. Background

For the purpose of this work, V&V methods and frameworks can be broken down into two general categories. First, there are the formal theories and de nitions already established in the community for traditional models and simulations. Second, there are the emergent e orts to V&V simulations of autonomous systems. This section will give a brief background of how V&V has evolved over time, including early work creating formal de nitions and theory. It will show the movement from general model validation to full simulations of autonomous robots done to date.

The below sections are presented as a brief introduction to the formal ideas of V&V and their application to robotics. A more in-depth literature review on the history and evolution of V&V methods and theories can be found in the 2017 publication [10]. This article details the progression of V&V theories and methods over time and a comparative analysis between V&V frameworks.

2.1. Formal V&V Theories and De nitions

A substantial amount of research has been performed to define methods for verifying and validating computer models. The bulk of this research focuses on analytic/discrete event models and simulation models. These types of models are most often models of processes (i.e., economic forecasts or manufacturing outputs) versus physical phenomena (e.g., fluid flow). In fact, most of the theoretical work done to de ne V&V was done for these types of models. One early definition of V&V was proposed by Fishman and Kiviat in [11]:

“Veri fication, which determines whether a model actually behaves as an experimenter assumes it does; [and] validation, which tests whether the model reasonably approximates a real system."

The earliest work to establish a well-de fined methodology for V&V of simulation models was that performed by Schlesinger et. al [12], in which they de fine validation as “substantiation that a computerized model within its domain of applicability possesses a satisfactory range of accuracy consistent with the intended application of the model." For a time, this was the most commonly accepted definition for model validation; however, the concept of a “range of accuracy" left room for qualitative interpretation of simulation results.

In later works, Sargent provides what is considered one of the canonical methods for V&V of simulation models. First proposed in [13] and further refi ned in [14], Sargent follows Fishman and Kiviat's definitions of veri cation and validation, and goes on to propose formal methods for the V&V of simulations as follows:

  1. The model development team decides if and when the model is valid for its application domain.

  2. The model development team works in close collaboration with the model's end users so that these users define the validation of the model.

  3. Independent verifi cation and validation (IV&V), where a separate third party assesses the validity of the model.

  4. The use of scoring models.