Master's Thesis - Evolution of Least-Restrictive Solutions for incomplete Scenario Models
Creators: name: Bergemann, Niko
Publisher: name: Zenodo
Year: 2021
Subjects: SML
GR(1)
LTL
Evolution
Automata
Graphs
Restrictiveness
Production Cell

description: This digital object represents the entirety of the Master's Thesis "<strong>Evolution of Least-Restrictive Solutions for incomplete Scenario Models</strong>". Contained in this publication are The thesis paper itself the pdf all related sources to compile the PDF The application used for our evaluation The source code A guide on how to build the sources A guide on how to run the evolutionary search A guide on how to generate the evaluation results The specific databases and evaluation plots that were created during our evaluation runs <strong>Directory Structure</strong><br> - EvaluationResults:<br> - ```The databases for our algorithm runs, which we used for the evaluation.```<br> - ```The pdf files containing plots showing the behavior of the different restrictiveness metrics``` - Sources ```the different source repositories```<br> - MOEAFramework ```Framework for the multi-objective evolutionary algorithm```<br> - scenariotools ```clone of the scenariotools repositor```<br> - geneticscenarios ```The utility / plugin to run the evolutionary algorithm for SML. Here the restrictiveness metrics are evaluated and applied as optimization objectives. Utilize this to execute the evaluation on the databases again, or create your own exemplary databases with a tabu search run. Information about how to do that is given in the "Sources/geneticscenarios/Readme.md".```<br> - master_thesis ```repository for storing the latex sources for the master's thesis itself (PDF document)``` - Thesis.pdf ```Master's thesis: "Evolution of Least-Restrictive Solutions for incomplete Scenario Models"```<br> - Readme.md ```Information about the contents``` <strong>Info / Abstract</strong><br> In this thesis, we present an extension for the evolutionary algorithm that Schmelter et al. implemented for the scenario modeling language SML.<br> SML is a modeling language for requirements engineering, in which the system designer can implement and validate reactive black-box behavior for a system by modeling not only the system itself but also the environment (sensors and actors) the system operates in.<br> With their evolutionary algorithm that is able to create new assumptions to add to the SML specification, Schmelter et al. offer an automatic utility to repair incomplete / unrealizable SML specifications.<br> For this generation, they utilize the MOEAFramework, which enables them to search for solutions that are optimal in regards to multiple different objectives.<br> As a new objective, we showcase different metrics to create a notion of \emph{environment restrictiveness}.<br> As a base for that, we were able to utilize multiple graph measures, since we believe that the restrictiveness (or rather the complexity) of an arbitrary SML specification can be represented by its respective state graph.<br> We adjusted and optimized these graph measures to fit our goal of environment restrictiveness and implemented 12 additional different candidates to choose from.<br> After incorporating them into the evolutionary algorithm of Schmelter et al., we evaluated those 12 (and an additional proprietary, already existing) metric candidates with the help of a case study applied on two research examples ("Production Cell" and "EBEAS") to find out which of these metrics is best applicable for our purpose.<br> In the end, we compare the metric candidates in regards to runtime and performance, enabling us to now recommend 3 metrics as good metrics that can all be used for the evolutionary algorithm:<br> - $R4$ (the number of distinct decisions, the environment can make when interacting with the system)<br> - $R6_S$ (the finite hausdorff dimension of the state graph resembling the SML specification - after adjusting the state graph for super steps)<br> - $R7_S$ (measuring the state graph of the specification for a simplified version of the weakness measure proposed by Cavezza et al. - also after adjusting for super steps).<br> We additionally recommend using $R4$ over the other two metrics, simply because of its superior runtime.