Im folgenden werden mehrere Themen stichwortartig skizziert. Eine genauere Festlegung der Inhalte erfolgt nach Absprache mit dem Ansprechpartner/Betreuer.
Der Lehrstuhl besitzt in diesem Bereich sowohl eine bereits in Echtzeit laufende Simulation von große Roboterschwärmen (mehr als 60 Agenten möglich) als auch reale Roboter für den Outdoor-Bereich. In dem Forschungsbereich von Herrn Puzicha geht es darum, diese Aspekte miteinander zu verschmelzen. Das bedeutet, dass weitere reale Komponenten mit Hilfe von übertragenen Echtzeitdaten simuliert werden müssen und simulierte Daten das Verhalten der Roboter steuern müssen.
1) Modellprädiktive Regelung für reale Roboter in Echtzeit unter ROS für Windows (ggf. Linux)
2) Entwicklung weiterer mathematische Funktionen zum Abbilden von Schwarmverhalten und Missionen. Es existieren
beispielsweise Funktionen für drei Missionen: Geländeexploration, Eskortierung von Objekten und Aufbau von MANETs.
3) Entwurf und Implementierung effizienter Abbildungen (Datenstrukturen& Parallelisierung) realer Roboter in einer Simulation
4) Entwurf und Implementierung effizienter Strukturen zur Umfeldbewertung und Wegplanung
5) Entwurf und Implementierung effizienter Strukturen zur Aufbau einer Potentialkarte aus Sensordaten in Echtzeit
6) Analyse und Optimierung von Streaming Daten (Sollen lieber Rohdaten oder vorverarbeitete Daten übertragen werden?
Wer hat welche Ressourcen?)
7) Extraktion von Kartendaten (GoogleMaps/OpenstreetMap/OpenseaMap) und Aufbereitung für die Simulation von Hindernissen
8) Parallelisierung von Regelungsalgorithmen auf GPUs
Die Arbeiten werden teilweise in Kooperation mit dem LS7 angeboten und können je nach Umfang als BA-/MA-Arbeiten bearbeitet werden.
1 Sammlung von Traces (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• Sammlung von Traces aus Internetquellen mit Schwerpunkt auf Performance-relevanten Daten.
• Festlegung eines Standardformats inkl. Konvertierungstools zur Nutzung in anderen Tools.
• Fitten der Verteilung/Prozess mit ein bis zwei Verfahren aus ProFiDo.
• Klassifizierung/Einschätzung der Traces aus Sammlung in leicht/mittel/schwer zu ”fittende” Traces.
2 Vergleich verschiedener Algorithmen aus ProFiDo (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• Ggf. aufbauend auf obiger Trace-Sammlung experimentelles Herausfinden ”guter” Programm-Parameter.
• Heuristische Regeln für die Wahl des Verfahrens anhand trace-spezifischer Kenngrößen.
• Toolunterstützung zur Bestimmung geeigneter Programm-Parameter.
3 Analyse der Anpassungsgüte in ProFiDo (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Graphische Darstellung der Anpassungsgüte theoretischer Verteilungen an empirische Daten durch QQ-, PP- oder Box-Plots.
• Integration von Anpassungstest wie χ2 -, KS- oder AD-Test.
• Falls möglich Nutzung von Standardsoftware wie R oder Python-Bibliotheken zur Realsierung der Komponenten.
• Unterstützung bei der vergleichenden Bewertung mehrerer angepasster Verteilungen.
4 Untersuchung von Korrelationen in Fehlertraces und ihrer Modellierung durch MAPs (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Analyse von Fehlertraces auf inhomogene und korrelierte Ausfallzeiten.
• Visualisierung der Abhängigkeiten.
• Anpassung von MAPs an die Daten mit Hilfe von ProFiDo.
• Test der Anpassungsgüte.
5a Methoden zur Parameterschätzung von Standardverteilungen und ihre Integration in ProFiDo (Bachelorarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Implementierung der ML-Schätzer für Standardverteilungen aus Law.
• Bestimmung der Verteilungsparameter anhand ausgewählter Traces.
• Vergleich verschiedener Verteilungen untereinander und mit angepassten Phasenverteilungen auf Basis ausgewählter Kennzahlen (Momente, Quantile, Histogramme).
5b Erweiterung eines Brute Force-Ansatzes zum Fitten von Verteilungen (Masterarbeit; Dr. Bause)
• Fitting-Methode aus [19] erweitern auf Mischungen von Normalverteilungen, deterministische Verteilungen und optional weiterer Verteilungen
• Integration der Implementation in die Softwareumgebung ProFiDo
• experimentelle Bewertung der Erweiterung
6 M/M/1 oder G/G/1 Resultate (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• umfassende Darstellung der Resultate aus der Literatur. Die Resultate sollten neben stationären auch transiente Ergebnisse beinhalten.
• Tool zur M/M/1 od. G/G/1-Analyse erstellen, welches alle theoretischen Resultate anzeigt bzw. visualisiert.
7 Markov Decision Processes (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• Tool/GUI zur Definition MDPs.
• Visualisierung elementarer Algorithmen (value/policy iteration).
• Anwendung auf konkrete Beispiele,
z.B. analog Agent walk Beispiel, siehe
http://www.microveggies.com/csci/index.php/9-csci-3202-lecture-notes/31-lecture12-markov-decision-processe
https://mpatacchiola.github.io/blog/2016/12/09/dissecting-reinforcement-learning.html
8 Schrankenberechnung für Concurrent MDPs (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Vorstellung der Modelle aus [6] und [14].
• Beschreibung deterministischer und zyklischer Politiken für CMDPs.
• Berechnung von Schranken für deterministische stationäre Politiken mit Hilfe von ILPs und Schnittebenen (als Erweiterung des Ansatzes aus [6]).
9 Toolvergleich (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• Vergleich OMNeT++ und AnyLogic hinsichtlich Laufzeit, Speicherplatz und ”Ergebnisqualität”.
• einfache Vergleichsmodelle z.B. aus dem Bereich der Warteschlangennetze: tandem, tandem with blocking,
central server-Modelle (mit und ohne memory constraints), producer/consumer-Modelle
• Der Vergleich sollte auch die eventuelle Nutzung von GPUs berücksichtigen.
10 Ansätze zum Screening von Parametern in Simulationsstudien (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Vorstellung von Ansätzen zum Faktorscreening aus der Literatur [8, 17,18].
• Implementierung der Verfahren in C++ oder Java zur Nutzung in Kombination mit einem Simulationswerkzeug (z.B. OMNeT++, AnyLogic).
• Empirische Bewertung der Verfahren anhand einiger Beispielmodelle.
11 Statische Verfahren (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• Vorgegebene endliche Datenmenge.
• Effiziente Verfahren zur Ermittlung von typischen Kenngrößen (mean, median, moments, confidence interval for mean, curtosis, . . .) implementieren.
• Evtl. Erweiterung auf Prozess-Kenngrößen (auto-correlation, joint moments).
• Toolentwicklung; Unix-ASCII-basiert, ggf. unter Ausnutzung vorhandener GPUs.
12 Dynamische Verfahren (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• On the fly statistische Analyse eines Datenstromes ("streaming statistical analysis")
• typische Kenngrößen wie unter Nr. 11 (Statische Verfahren).
• Evtl. Erweiterung auf Prozess-Kenngrößen (auto-correlation, joint moments).
• Toolentwicklung; Unix-ASCII-basiert, ggf. unter Ausnutzung vorhandener GPUs.
13 Bootstrapping Ansätze zur Bestimmung von Konfidenzbändern für Verteilungsfunktionen (Bachelorarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Vorstellung des Bootstrapping-Ansatzes zzur Bestimmung von Konfidenzbändern von Verteilungsfunktionen (z.B. der Verweilzeit in einem System) [9, 10].
• Implementierung der Verfahren im Kontext von OMNeT++.
• Empirische Bewertung der Konfidenzbänder auf Basis einfacher Beispiele.
14 SLA-Tool : Experimentserien (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• Unterstützung zur Durchführung von Experimentserien in das SLA-Tool integrieren.
• Verwaltung von Ergebnissen integrieren.
15 SLA-Tool : Validierung/Vergleich mit Simulation (Bachelorarbeit; Ansprechpartner: Dr. Bause)
• Validierung: Werden die Grenzen eingehalten?
• Vergleich: Wie ”brauchbar” sind die Grenzen in der Praxis?
• ”typische” kleinere Modelle verwenden, hierzu Literatursichtung.
• Einschätzung der Abbildbarkeit bzw. approximativen Darstellung der Modelle in SLA.
16 Erstellung eines Editors für PH-Graphen (Bachelorarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Beschreibung der Klasse der PH-Graphen aus [2].
• Entwurf und prototypische Implementierung eines Editors zur Spezifikation von PH-Graphen.
• Anbindung der numerischen Verfahren zur Bestimmung kürzester Wege im Graphen.
• Definition eines adäquaten Ausgabeformats für PH-Graphen.
17 Parallelisierung iterativer Lösungsalgorithmen für Markov Ketten mit OpenMP (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Untersuchung von Parallelisierungsstrategien für Vektor-Matrix-Multiplikationen und weitere Basisoperationen iterativer Lösungsmethoden.
• Prototypische Implementierung der Verfahren im Kontext von USENUM auf Mehrkernprozessoren.
• Vergleich sequentieller und paralleler Implementierung anhand ausgesuchter Beispielmodelle.
18 GPU-Implementierung von Operationen auf HTDs (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
• Beschreibung der hierarchsichen Tucker Dekomposition und der zugehörigen Operationen [11].
• Parallelisierung der C-Implementierung aus [5] mit Hilfe von CUDA.
• Vergleich sequentieller und GPU-Implementierung.
[1] J. Banks (eds.). Handbook of simulation. Principles, Methodology, Advances, Applications, and Practice. John Wiley & Sons, 1998.
[2] Peter Buchholz, Iryna Felko. PH-graphs for analyzing shortest path problems with correlated traveling times. Computers & OR 59: 51-65 (2015).
[3] F. Bause, J. Kriege. Correlated Random Number Generation for Simulation Experiments. 16. ASIM Fachtagung (ASIM 2015), Simulation in Produktion und Logistik, TU Dortmund,
23. bis 25. September 2015, Markus Rabe & Uwe Clausen (eds.), Fraunhofer IRB Verlag, Stuttgart 2015, pp. 641–650, ISBN 978-3-8396-0936-1.
[4] F. Bause, P. Buchholz. SLA Tool. In Proc. of the 19th International GI/ITG Conference on Measurement, Modelling and Evaluation of Computing Systems,
German R., Hielscher KS., Krieger U. (eds) Measurement, Modelling and Evaluation of Computing Systems. MMB 2018, LNCS 10740, Springer, Cham, 2018, pp. 302--306.
[5] Peter Buchholz, Tugrul Dayar, Jan Kriege, M. Can Orhan. On compact solution vectors in Kronecker-based Markovian analysis. Perform. Eval. 115: 132-149 (2017).
[6] P. Buchholz, D. Scheftelowitsch Computation of weighted sums of rewards for concurrent MDPs. Math. Meth. of OR 89(1): 1-42 (2019).
[7] G. Bolch, S. Greiner, H. de Meer, K. Trivedi. Queueing Networks and Markov Chains. 2nd eds., 2006.
[8] Russell C. H. Cheng. Searching for Important Factors: Sequential Bifurcation under Uncertainty. Winter Simulation Conference 1997: 275-280.
[9] Russell C. H. Cheng. Bootstrapping simultaneous confidence bands. Winter Simulation Conference 2005: 240-247.
[10] Russell Cheng. Bootstrap confidence bands and goodness-of-fit tests in simulation input/output modelling. Winter Simulation Conference 2015: 16-30.
[11] Daniel Kressner, Christine Tobler. Algorithm 941: htucker - A Matlab Toolbox for Tensors in Hierarchical Tucker Format. ACM Trans. Math. Softw. 40(3): 22:1-22:22 (2014).
[12] A. Law, W. Kelton. Simulation modeling and analysis. 5th ed., McGraw Hill, 2014.
[13] P. Buchholz, S. Vastag. An Introduction to SLA Calculus for the Analytical Validation of SLAs. http://ls4-www.cs.tu-dortmund.de/download/buchholz/sla.pdf
[14] Lauren N. Steimle, David L. Kaufman, Brian T. Denton. Multi-model Markov Decision Processes Under revision, available at http://www.optimization-online.org/DB HTML/2018/01/6434.html
[15] OMNeT++ Community Site. http//www.omnetpp.org/.
[16] S. Vastag. SLA Calculus. Dissertation, Technische Universität Dortmund, Fakultät für Informatik, Dortmund, 2014.
[17] Hong Wan, Bruce E. Ankenman, Barry L. Nelson. Controlled Sequential Bifurcation: A New Factor-Screening Method for Discrete-Event Simulation. Operations Research 54(4): 743-755 (2006).
[18] Reza Yaesoubi, Stephen D. Roberts, Robert W. Klein. A modification of Cheng’S method: An alternative Factor Screening method for stochastic simulation models. Winter Simulation Conference 2010: 1034-1047.
[19] F. Bause. An Efficient Brute Force Approach to Fit Finite Mixture Distributions. In: Hermanns H. (eds) Measurement, Modelling and Evaluation of Computing Systems. MMB 2020. Lecture Notes in Computer Science, vol 12040. Springer, Cham, 2020, pp. 208--224.