Institut für Roboterforschung

Permanent URI for this collection

http://hdl.handle.net/2003/22851

Lehrstuhl für Datenverarbeitungssysteme

Browse

Now showing 1 - 20 of 21

User-aware performance evaluation and optimization of parallel job schedulers
(2017) Schlagkamp, Stephan; Schwiegelshohn, Uwe; Tchernykh, Andrei
Die Dissertation User-Aware Performance Evaluation and Optimization of Parallel Job Schedulers beschäftigt sich mit der realitätsnahen, dynamischen Simulation und Optimierung von Lastsituationen in parallelen Rechensystemen unter Berücksichtigung von Feedback-Effekten zwischen Performance und Nutzerverhalten. Die Besonderheit solcher Systeme liegt in der geteilten Nutzung durch mehrere Anwender, was zu einer Einschr änkung der Verfügbarkeit von Ressourcen führt. Sollten nicht alle Rechenanfragen, die sogenannten Jobs, gleichzeitig ausgeführt werden können, werden diese in Warteschlangen zwischengespeichert. Da das Verhalten der Nutzer nicht genau bekannt ist, entsteht eine große Unsicherheit bezüglich zukünftiger Lastsituationen. Ziel ist es, Methoden zu finden, die eine Ressourcenzuweisung erzeugt, die den Zielvorstellungen der Nutzer soweit wie möglich entspricht und diese Methoden realistisch zu evaluieren. Dabei ist auch zu berücksichtigen, dass das Nutzerverhalten und die Zielvorstellungen der Nutzer in Abhängigkeit von der Lastsituation und der Ressourcenzuweisung variieren. Es wird ein dreigliedriger Forschungsansatz gewählt: Analyse von Nutzerverhalten unter Ressourcenbeschränkung: In Traces von parallelen Rechensystem zeigt sich, dass die Wartezeit auf Rechenergebnisse mit dem zukünftigen Nutzerverhalten korreliert, d.h. dass es im Durchschnitt länger dauert bis ein Nutzer, der lange warten musste, erneut das System nutzt. Im Rahmen des Promotionsprojekts wurde diese Analyse fortgesetzt und zusätzliche Korrelationen zwischen weiteren Systemparametern (neben der Wartezeit) und Nutzerverhalten aufgedeckt. Des Weiteren wurden Funktionen zur Zufriedenheit und Reaktion von Nutzern auf variierende Antwortzeiten von Rechensystemen entwickelt. Diese Ergebnisse wurden durch eine Umfrage unter Nutzern von Parallelrechner an der TU Dortmund erzielt, für die ein spezieller Frageboden entwickelt wurde. Modellierung von Nutzerverhalten und Feedback Wegen des dynamischen Zusammenhangs zwischen Systemgeschwindigkeit und Nutzerverhalten ist es nötig, Zuweisungsstrategien in dynamischen, feedback-getriebenen Simulationen zu evaluieren. Hierzu wurde ein mehrstufiges Nutzermodell entwickelt, welches die aktuellen Annahmen an Nutzerverhalten beinhaltet und das zukünftige Hinzufügen von zusätzlichen Verhaltenskomponenten ermöglicht. Die Kernelemente umfassen bisher Modelle für den Tages- und Nachtrhythmus, den Arbeitsrhythmus und Eigenschaften der submittierten Jobs. Das dynamische Feedback ist derart gestaltet, dass erst die Fertigstellung von bestimmten Jobs die zukünftige Jobeinreichung auslöst. Optimierung der Allokationsstrategien zur Steigerung der Nutzerzufriedenheit Die mit Hilfe des Fragebogens entwickelte Wartezeitakzeptanz von Nutzern ist durch ein MILP optimiert worden. Das MILP sucht nach Lösungen, die möglichst viele Jobs innerhalb eines akzeptierten Wartezeitfensters startet bzw. die Summe der Verspätungen minimiert. Durch die Komplexität dieses Optimierungsalgorithmus besteht die Evaluation bisher nur auf fixierten, statischen Szenarien, die Abbilder bestimmter System- und Warteschlangenzustände abbilden. Deswegen ist weiterhin geplant, Schedulingverfahren zur Steigerung der Anzahl an eingereichten Jobs und der Wartezeitzufriedenheit mit Hilfe des dynamischen Modells zu evaluieren.
Random finite set filters for superpositional sensors
(2017) Hauschildt, Daniel; Schwiegelshohn, Uwe; Clark, Daniel
The multi–object filtering problem is a generalization of the well–known single– object filtering problem. In essence, multi–object filtering is concerned with the joint estimation of the unknown and time–varying number of objects and the state of each of these objects. The filtering problem becomes particular challenging when the number of objects cannot be inferred from the collected observations and when no association between an observation and an object is possible. A rather new and promising approach to multi–object filtering is based on the principles of finite set statistics (FISST). FISST is a methodology, originally proposed by R. Mahler, that allows the formulation of the multi–object filtering problem in a mathematical rigorous way. One of the main building blocks of this methodology are random finite sets (RFSs), which are essentially finite set (FS) – valued random variables (RVs). Hence, a RFS is a RV which is not only random in the values of each element but also random in the number of elements of the FS. Under the premise that the observations are generated by detection–type sensors, many practical and efficient multi–object filters have been proposed. In general, detection–type sensors are assumed to generate observations that either originate from a single object or are false alarms. While this is a reasonable assumption in many multi–object filtering scenarios, this is not always the case. Central to this thesis is another type of sensors, the superposition (SPS)–type sensors. Those types of sensors are assumed to generate only one single observation that encapsulates the information about all the objects in the monitored area. More specifically, a single SPS observation is comprised out of the additive contribution of all the observations which would be generated by each object individually. In this thesis multi–object filters for SPS–type sensors are derived in a formal mathematical manner using the methodology of FISST. The first key contribution is a formulation of a SPS sensor model that, alongside errors like sensor noise, accounts for the fact that an object might not be visible to a sensor due to being outside of the sensor’s restricted field of view (FOV) or because it is occluded by obstacles. The second key contribution is the derivation of multi–object Bayes filter for SPS sensors that incorporates the aforementioned SPS sensor model. The third key contribution is the formulation of a filter variant that incorporates a multi–object multi–Bernoulli distribution as underlying multi–object state distribution, thus providing a multi–object multi–Bernoulli (MeMBer) filter variant for SPS–type sensors. As the stated variant turns out not to be conjugate, two approximations to the exact solution are given. The fourth key contribution is the derivation of computationally tractable implementations of the SPS MeMBer filters.
Laufen humanoider Roboter auf regelungstechnischer Basis mit Echtzeitmodifikation der Fußpositionen
(2017) Urbann, Oliver; Schwiegelshohn, Uwe; Visser, Ubbo
Humanoide Roboter werden allgemein angenommen als die universelle Maschine, die in Zukunft dem Menschen gefährliche oder unzumutbare Arbeit abnehmen kann, wie beispielsweise Rettungsmissionen in Erdbebengebieten oder ähnliche Katastrophenszenarien. Zweibeiniges Laufen hat hier entscheidende Vorteile gegenüber anderen Fortbewegungsmethoden in vielen Situationen: unwegsames Gelände, enge Passagen oder ähnliches. Die Stabilität selbst auf ebenem Boden ist bei weitem noch nicht mit menschlichem Laufen vergleichbar, insbesondere nicht auf kostengünstigen Roboterplattformen, ein notwendiges Merkmal für den breiten Einsatz. In dieser Arbeit wird zunächst ein physikalisches Modell ausgewählt, welches den Roboter in einer einfachen Form widerspiegelt. Dem Nachteil der starken Abstraktion steht der Vorteil gegenüber, dass dieses Modell linear ist und damit effiziente Methoden ermöglicht eine Bewegung anhand einer Referenz zu bestimmen. Die Methode, die dazu eingesetzt wird, muss verschiedene Anforderungen erfüllen, die sich aus den Zielen der Arbeit ergeben. Dazu gehören die Möglichkeit Sensordaten zu verarbeiten um kleine Störungen zu balancieren und die Möglichkeit die vorgeplanten Schritte zu modifizieren, um auch größere Störungen behandeln zu können. Zwei Methoden zeigen sich als vielversprechend: Preview Control (PC) und Model Predictive Control (MPC). Letztere beinhaltet bereits die Modifikation von Schritten, sollte der Roboter ansonsten instabil werden. Jedoch muss die Lösung numerisch gefunden werden, was in bestimmten Fällen zu einer hohen Laufzeit führt. Dahingegen ist bei PC die Laufzeit im gewünschten Rahmen, jedoch muss die Möglichkeit zur Schrittmodifikation hinzugefügt werden. Zwar können Instabilitäten durch den Regler behandelt werden, jedoch führt diese Behandlung möglicherweise selbst zu einer Instabilität. Der Ansatz ist daher eine mathematische Forderung zu formulieren, die eine Vermeidung der Instabilitäten durch den Regler verbietet. Diese lässt sich zu einer Gleichung umformen, welche eine Modifikation der Referenz vorgibt, so dass die Forderung erfüllt wird. Für diese Behandlung müssen jedoch die Sensordaten zunächst verarbeitet werden, so dass die Regler mit einem aktualisierten physikalischen Zustand der Roboters arbeiten können. Das geschieht durch den Beobachter, auf den separat eingegangen wird. Für einen Lauf reichen die Regler noch nicht aus, da die Ein- und Ausgabe des Gesamtalgorithmus eine andere ist. Für eine sinnvolle Anwendung sollte die gewünschte Geschwindigkeit vorgegeben werden können, und als Ausgabe werden von kostengünstigen Robotern häufig die Gelenkwinkel erwartet. Auch diese Module werden hier vorgestellt, beispielsweise die Erzeugung einer geeigneten Referenz für die Regler aus der gewünschten Geschwindigkeit, die Umwandlung der Ausgabe der Regler in Fußpositionen und anschliessende Umrechnung in Gelenkwinkel mittels inverser Kinematik. Die Evaluation beginnt zunächst mit einem Laufzeitvergleich. Hier zeigt sich bereits, dass MPC im vorgegebenen Rahmen nicht echtzeitfähig ist, so dass MPC nicht weiter untersucht wird. In weiteren Experimenten wird sowohl in der Simulation, als auch auf dem physischen Roboter der Beobachter untersucht. Dazu werden unter anderem Hindernisse am Boden platziert, die eine unerwünschte Schwingung beim Roboter erzeugen, die ohne Sensordatenrückführung in den meisten Fällen zum Sturz führt. So kann gezeigt werden, dass der Beobachter in der Lage ist, diese leichten Störungen zu stabilisieren. Jedoch können die Hindernisse am Boden in einem anderen Aufbau auch zu stärkeren Störungen führen, die nur mittels Modifikation der Schritte erfolgreich behandelt werden können. Auch Stöße zählen unter Umständen zu den größeren Störungen, die nachweislich von der Modifikation stabilisiert werden können.
Sensor positioning in distributed sensor networks
(2016) Kirchhof, Nicolaj; Schwiegelshohn, Uwe; Blankenbach, Jörg
In the thesis, it is shown how sensor placement problems (SPPs) can be stated and solved. New techniques to model these problems and to find approximate solutions are presented. Their evaluation is conducted for real world environments using the properties of a self-build positioning system. Nine methods are presented to search for an optimal sensor placement in a discrete or continuous environment. Two global optimization models, two greedy heuristics, two nonlinear optimization models, two decomposition based optimization models and one approximate optimization model. All of these methods serve the same goal, to minimize the number of sensors while serving the positioning constraint that a minimum positioning quality based on the sensor geometry is provided in the environment. Two of the methods also introduce secondary goals that become active if the primary goal is fulfilled. One maximizes the qualities in the environment and one increases the area that is covered with a minimum quality. The global optimization models are used solve discretized SPP. To state them, a customized sampling scheme is presented that allows a linear increase in sampled workspace position and sensor pose for an environment. In contrast to the global optimization models, the approximate optimization model and the greedy heuristics solve a simplified discretized problem with decreased complexity. Finally, the decomposition based optimization models separate the input environment into multiple small models. Therefore, their solution to the SPP is a combination of all independently calculated solutions. To state the decomposition based models, a convex polygon decomposition algorithm is introduced. It has a polynomial complexity and separates an input polygon into convex pieces with additional Steiner points that are only created on the polygon boundary. For the approximate optimization model the estimation of its solution quality is derived. The derivation introduces properties of approximate SPP solutions that can be exploited to improve them using an iterative problem specific search heuristic. All algorithms are validated using the digitalization of four real world input environments of different sizes and the properties of a custom developed indoor positioning system. Each environment is solved with an extensive set of varying discretization exactness, leading to more than 15,000 solved or improved SPP for each environment. The most important findings of the evaluation are the good performance of the Greedy Single Sensor Selection algorithm over the other approximation algorithms and the negligible influence of the sensor pose discretization exactness for the smaller environments. In addition, it could be shown that the worst case approximation ratio tends to be too pessimistic for larger problems. At last, it was shown that the iterative improvement of approximate solutions by the search heuristic can significantly increase the solution goodness.
Motion plan and control of humanoid walking robots
(2015) Liu, Jing; Schwiegelshohn, Uwe; Seyfarth, André
Walking for most humans and animals is an easy task due to the inherent robustness and the natural dynamics of the walking mechanism. Walking, however, for humanoid robots is not that easy because of its nonlinearity, high dimensionality, and natural instability. Effective use of humanoid robots in unstructured environments for human beings requires that they have autonomous and reliable locomotion capability. Locomotion for humanoid robots can take many forms. This thesis covers motion plan and control of humanoid walking robots. Five consecutive stages are addressed from the perspective of stable dynamic walking. Firstly, a natural and efficient walking pattern is designed on the basis of the insight gained from human walking. The walking pattern involves the configuration with stretched knees. Secondly, in view of the modeling error, as well as the environment uncertainty such as the unevenness and inclination of the surface, a posture controller, which online controls the orientation of the upper body of the robot is developed from the viewpoint of stability. Walking stability of the robot is improved through the control scheme. In the third stage, a gait controller, which online controls the swing-leg is developed. Fast and precise trajectory tracking of the swing-leg is achieved which enables humanoid robots to quickly swing the swing-leg so that fast walking can be realized. In the fourth stage, a controller with the purpose of decreasing the landing force and improving the walking stability by means of force control is developed. In the final stage, strategies for restoring equilibrium in the presence of external disturbances to maintain upright standing posture are analyzed. Simple models are introduced to exploit boundaries that determine the strategies used for preventing a fall. Simulation and experiments were performed with the humanoid robot NAO developed at Aldebaran Robotics in France. Using the walking system, NAO achieved dynamic stable walking and reached a maximum walking speed of 0.24 m/s in experiments. Besides, with the presented walking pattern NAO could walk stably with almost stretched knees at a lower speed, e.g. 0.10 m/s, so that the corresponding energy consumption was lower since the robot did not bend the knees all the time, which means that the robot is able to walk for a longer time without battery charging and has less heating problem.
Stochastic filtering on mobile devices in complex dynamic environments
(2014-04-02) Tasse, Stefan; Schwiegelshohn, Uwe; Burkhard, Hans-Dieter
Gathering information, especially about the immediately surrounding world, is a central aspect of any smart device, whether it is a robot, a partially autonomous vehicle, or a mobile handheld device. The consequential use of electrical sensors always implies the need to filter the imperfect sensor data output in order to gain reliable information. While the challenge of perception and cognition in machines is not a new one, new technology constantly opens up new possibilities and challenges. This is stressed further by the advent of cheap sensor technology and the possibility to use a multitude of small sensors, with the simultaneous constraint of limited resources on mobile, battery-powered computing devices. In this work, stochastic methods are used to filter sensor data, which is gathered by mobile devices, to model the devices' location and eventually also relevant parts of their dynamic environment. This is done with a focus on online algorithms and computation on these mobile devices themselves, which implies limited available processing power and the necessity for computational efficiency. This dissertation's purpose is to impart a better understanding about the conception and design of stochastic filtering solutions, to propose localization algorithms beyond the current state of the art, and to show the use of simultaneous localization and mapping algorithms in the context of cooperatively estimating the surrounding world of a team of robots in a fast changing, dynamic environment. To achieve these goals, the concepts are depicted in multiple application scenarios, design choices and their implications systematically cover all aspects of sensing and estimation, and the proposed systems are evaluated in real-world experiments on humanoid robots and other mobile devices.
Einsatz propriozeptiver Sensorik in der Bewegungssteuerung humanoider Roboter
(2013-11-08) Kerner, Sören; Schwiegelshohn, Uwe; Christaller, Thomas
Der Einsatz humanoider Roboter für unterschiedliche Aufgabengebiete rückt mehr und mehr in den Fokus des industriellen Interesses. Gleichzeitig kann jedoch das Problem der Bewegungssteuerung eines solchen Roboters keineswegs als gelöst gelten. Diese Arbeit erforscht Algorithmen, zum Einsatz propriozeptiver Sensorik, um die Präzision und Robustheit der Bewegungssteuerung zweibeiniger Roboter weiter zu verbessern. Alle Untersuchungen werden auf Basis des kommerziell erhältlichen Roboters NAO durchgeführt, um anderen Forschern die Übertragung der Ergebnisse zu vereinfachen und so die Vergleichbarkeit und Aussagekraft der Forschungsarbeit zu erhöhen. Ein primärer Fokus der Arbeit liegt auf dem Einsatz von Sensorik zur Wahrnehmung des Zustandes des Systems Roboter. Für die Fortbewegung besonders hervorzuheben sind dabei das Gleichgewicht, die Position des Schwerpunkts und die Orientierung des Oberkörpers im Raum. Der NAO ist mit einer Vielzahl propriozeptiver Sensoren ausgestattet, die auf ihre Eignung zur Bestimmung dieser Faktoren untersucht werden. Ein abschließender Vergleich untersucht ihre Praxistauglichkeit für die Berechnung verschiedener Algorithmen. Besonders wird hierbei der Einfluss von Fehlerursachen unterschiedlicher Art auf die Bestimmung des Systemzustandes evaluiert. Auf Basis dieser eingehenden Untersuchung wird im Rahmen der Arbeit ein Regelalgorithmus für die Fortbewegung des NAO entworfen, der auf dem populären Invertierten-Pendel- Ansatz basiert. Zur Stabilisierung wird das Konzept um einen Preview-Regler mit Beobachter erweitert. Eine eingehende Erprobung der Praxistauglichkeit des Algorithmus erfolgt sowohl anhand eines Simulators, als auch am realen Roboter. Damit der Roboter auf Basis der Bewegung zielgerichtet zukünftige Aktionen planen kann, ist es unabdingbar die tatsächlich ausgeführte Bewegung zu verfolgen. Hierzu wird das Konzept der Odometriemessung von rollenden auf laufende Roboter übertragen und der Algorithmus praktisch evaluiert. Zur Reduktion des Odometriefehler wird ein neuartiges Verfahren in Form von optischen Sensoren in den Fußsohlen entwickelt und praktisch am NAO erprobt. Eine weitere Verbesserung der Bewegungsverfolgung der verspricht der abschließend vorgestellte Filteralgorithmus. Im Gegensatz zu den üblicherweise in der mobilen Robotik angewandten Filtertechniken wird das Problem nicht auf ein Einkörper-Problem reduziert, sondern durch explizite Betrachtung der Nebenbedingungen ein effizienter Mehr-Körper-Filter entworfen. Sensorinformationen einzelner Festkörper können dadurch unmittelbar in das Filter integriert werden. Der Divergenz des Systems über die Zeit wird durch Ausnutzung des Wissens über die kinematische Struktur begegnet. Eine Erprobung des Verfahrens erfolgt lediglich im Simulator, da es Evaluierung auf der aktuellen Hardware des NAO aus Gründen der CPU-Leistung nicht in Echtzeit möglich ist.
Federated capacity planning for distributed computing infrastructures
(2013-08-30) Papaspyrou, Alexander; Schwiegelshohn, Uwe; Yahyapour, Ramin
Workflow-gestützte Bereitstellung von Grid Middleware-Diensten
(2013-02-06) Freitag, Stefan; Schwiegelshohn, Uwe; Streit, Achim
Dank nationaler und internationaler Initiativen tritt das Grid Computing langsam aus seinem Schattendasein hervor. Ausgehend von den ursprünglichen Hauptanwendern und auch -entwicklern aus der Hochenergie- und Teilchenphysik, weitet sich die Anwendung dieser Technologie auf andere Disziplinen, wie etwa die Klimaforschung und die Bio-Medizin, aus. Als zum Grid Computing komplementäre Technologie etablierte sich in den letzten fünf Jahren das Cloud Computing, welches im Hintergrund oft auf die Virtualisierung von Ressourcen und Plattformen zurückgreift. Eine mögliche und von europäischen Grid-Initiativen forcierte Kombination beider Technologien liegt in dem bedarfsorientierten Betrieb von Grid Middleware-Diensten in einer Cloud. Dabei sind die Dienste mitsamt dem unterliegenden Betriebssystem in eine virtuelle Appliance zu kapseln. Bei der Nutzung solcher Appliances stellen Abläufe für die kontrollierte, nachvollziehbare und wiederholbare Erzeugung einen wichtigen Punkt dar. Mit der Beschreibung dieser Abläufe als Workflows ist in dieser Arbeit eine erfolgversprechende Möglichkeit untersucht, die langfristig eine hochgradig automatisierte Installation und Konfiguration nicht nur von Grid Middleware-Diensten erlaubt.
Das Räuber-Beute-Modell für die mehrkriterielle Optimierung - Analyse und Anwendung
(2012-10-12) Grimme, Christian; Schwiegelshohn, Uwe; Schwefel, Hans-Paul
Das Streben nach Verbesserung von Systemen ist schon immer eine allgegenwärtige Herausforderung in Wissenschaft und technischer Anwendung. In der Regel ist jeder Ingenieur nicht nur mit dem Problem konfrontiert, ein einziges Ziel möglichst gut zu erfüllen; für die Entwicklung realer Systeme sind oftmals mehrere sich widersprechende Ziele (oder Kriterien) zugleich zu erfüllen. So ergibt sich für die mehrkriterielle Optimierung die Aufgabe, eine Menge sogenannter optimaler Kompromisse aufzufinden, die alle Kriterien zugleich möglichst gut erfüllen. In den letzten 30 Jahren haben evolutionäre Algorithmen als gute Heuristiken für diesen Bereich an Bedeutung gewonnen. Dort sind Standardverfahren entwickelt worden, die gute Approximationen der Kompromissmenge liefern, jedoch oftmals monolithisch aufgebaut sind und eine für die Anwenderschaft hohe Komplexität aufweisen. In dieser Arbeit betrachten wir eine einfache und ebenfalls naturinspirierte Alternative zu den etablierten Verfahren: das Räuber-Beute-Modell für die mehrkriterielle Optimierung. Anders als die Standardansätze basiert es auf lokal agierenden einkriteriellen algorithmischen Komponenten und ist sehr modular. Dies erleichtert neben der Parallelisierung des Ansatzes auch die exible und anwendungsbezogene Konfiguration. Zugleich ist es jedoch ein Verfahren, dessen Dynamik noch weitgehend unverstanden ist, so dass eine Abschätzung über das Potential des Ansatzes (über die zuvor genannte Flexibilität und Einfachheit in der Anwendung hinaus) bisher aussteht. Die erste Aufgabe in dieser Arbeit ist es daher, die inneren Prozesse des Räuber-Beute-Modells zu beobachten und theoretisch zu beschreiben. Erst mit diesem Wissen stellen wir exemplarisch zwei Erweiterungsmöglichkeiten des Verfahrens vor und zeigen deren Nutzen. Schließlich übertragen wir das Modell in die Anwendung für den Bereich des mehrkriteriellen Schedulings und stellen dar, dass es nicht nur etablierten Verfahren überlegen ist, sondern durch seinen modularen Aufbau auch als Framework zur Integration von heuristischem Expertenwissen gewinnbringend angewendet werden kann.
Orchestration of resources in distributed, heterogeneous grid environments using dynamic service level agreements
(2011-12-19) Wäldrich, Oliver; Schwiegelshohn, Uwe; Brazier, Frances M.
Die Akzeptanz des Internets und der zunehmende Ausbau von Netzwerkkapazitäten ermöglichen bereits heute einen effizienten und zuverlässigen Austausch riesiger Datenmengen zwischen verschiedenen Rechensystemen weltweit. Hieraus resultieren neue Paradigmen bei der Bereit-stellung und Nutzung verteilter IT-Ressourcen wie zum Beispiel das Grid-Computing. Im Grid-Computing werden Rechenressourcen verschiedener Institutionen bzw. Organisationen koordiniert zur Lösung wissenschaftlicher und wirtschaftlicher Problemstellungen genutzt. Neben Rechenressourcen werden dabei auch Daten, Datenspeicher oder Software bereitgestellt. Die Qualität mit der diese Ressourcen bereitgestellt werden gewinnt dabei zunehmend an Bedeutung. Qualitätseigenschaften sind zum Beispiel die minimale Verfügbarkeit von Rechenressourcen, die maximale Zugriffszeit eines Datenspeichers oder die maximale Antwortzeit einer web-basierten Anwendung. Für Ressourcenanbieter bedeutet dies dass spezifische Prozesse implementiert werden müssen um qualitativ hochwertige IT-Dienste bereitzustellen. Zudem können Dienste mit unterschiedlichen Dienstqualitäten bereitgestellt werden, wobei Dienste mit geringerer Qualität preiswerter angeboten werden als solche mit hoher Qualität. Anwender hingegen können den für sie passenden Dienst hinsichtlich ihrer Anforderungen und ihres Budgets auswählen. Service Level Agreements (SLAs) sind ein akzeptierter Ansatz um Verträge über IT-Dienste und Dienstqualitäten zu realisieren. SLAs beschreiben sowohl die funktionalen als auch die nicht-funktionalen Anforderungen von IT-Diensten als auch Vergütung und Strafen für Erfüllung bzw. Nichterfüllung der definierten Anforderungen. Diese Arbeit behandelt Methoden zur Verhandlung und Verwaltung von dynamischen SLAs in verteilten Systemen auf Basis des WS-Agreement Standards. Im Fokus steht hierbei die Deklaration von SLAs, deren automatisierte Verhandlung und Erstellung, das Monitoring von SLA Garantien, sowie die Verwendung von SLAs zur koordinierten Nutzung von IT-Ressourcen. Zu diesem Zweck wurde aufbauend auf die WS-Agreement Spezifikation ein Protokoll zur dynamischen Verhandlung bzw. Neuverhandlung von SLAs entwickelt. Dies beinhaltet die Definition eines Verhandlungsmodells zum Austausch von Angeboten zwischen den Verhandlungspartnern. Die anschließende Erstellung der SLAs basiert auf dem WS-Agreement Standard stellt einen automatisierter Prozess dar. Da es sich bei SLAs um elektronische Verträge handelt wurden Mechanismen zur Validierung von SLA Angeboten entwickelt und im Detail vorgestellt. Darüber hinaus werden Methoden zur automatisierten Evaluation von SLA Garantien beschrieben. Abschließend wird die Architektur und Implementierung eines Orchestrierungsdienstes zur Co-Allokation beliebiger Ressource wie z.B. Rechen- und Netzwerkressourcen vorgestellt. Die Ressourcenorchestrierung wurde hierbei mittels SLAs realisiert.
Dezentrales grid scheduling mittels computational intelligence
(2011-04-12) Lepping, Joachim; Schwiegelshohn, Uwe; Hüllermeier, Eyke
Das ständig wachsende Bedürfnis nach universell verfügbarer Rechen- und Speicherkapazität wird durch die in den letzten Jahren vorangetriebene Entwicklung neuer Architekturen für die vernetzte Interaktion zwischen Nutzern und Anbietern von Rechenressourcen mehr und mehr erfüllt. Dabei ist die Umsetzung einer Infrastruktur zur koordinierten Nutzung global verteilter Rechenressourcen längst in Forschung und Wirtschaft realisiert worden. Diese als Grid-Computing bezeichnete Infrastruktur wird künftig integraler Bestandteil der globalen Ressourcenlandschaft sein, sodass die Ausführung von lokal eingereichten Berechnungsaufgaben nicht mehr ortsgebunden ist, sondern flexibel zwischen unterschiedlichen Ressourcenanbietern migriert werden kann. Bereits heute sind unterschiedliche Nutzergemeinschaften im Rahmen von Community-Grids in virtuellen Organisationen zusammengefasst, die neben einem gemeinsamen Forschungs- oder Anwendungsinteresse auch häufig eine Menge von IT-Ressourcen gemeinsam nutzen. Ziel ist es aber, auf lange Sicht eine Community-übergreifende Kooperation im Sinne einer globalen Grid-Infrastruktur unter Wahrung lokaler Autonomie weiter zu fördern. Dabei bringt die Interaktion mit anderen Communities im Grid sowohl Chancen als auch Herausforderungen mit sich, da durch die Nutzbarkeit global verteilter Ressourcen auch höhere Anforderungen in Bezug auf Berechnungsgeschwindigkeit und Wartezeiten von Seiten der Nutzer gestellt werden. Der Schlüssel für den effizienten Betrieb künftiger Computational Grids liegt daher in der Entwicklung tragfähiger Architekturen und Strategien für das Scheduling, also in der Zuteilung der Jobs zu den Ressourcen. Bisher sind die Methoden für die Verhandlung von Jobübernahmen zwischen Ressourcenanbietern jedoch nur sehr rudimentär entwickelt. In dieser Arbeit werden deshalb dezentrale Schedulingstrategien für Computational Grids entwickelt und unter Einsatz von Methoden der Computational Intelligence realisiert und optimiert. Dabei werden einzelne virtuelle Organisationen als autonome Einheiten betrachtet, die über eine Annahme oder Abgabe sowohl von eigenen als auch von extern eingereichten Jobs entscheiden. Durch die Beachtung einer restriktiven Informationspolitik werden die Autorität und Sicherheit virtueller Organisationen gewahrt und zugleich wird die Skalierbarkeit in größeren Umgebungen durch den dezentralen Aufbau sichergestellt. Zunächst werden verschiedene dezentrale Strategien entwickelt und simulatorisch untersucht. Die Ergebnisse geben dann Aufschlüsse über die Dynamik und Eigenschaften eines derartigen Verbunds. Auf Basis der so gewonnenen Erkenntnisse werden die Mechanismen zur Entscheidungsfindung verfeinert und in einer neu entworfenen modularen Schedulingarchitektur umgesetzt. Mittels evolutionär optimierter Fuzzy-Systeme wird anschließend die Entscheidungsfindung optimiert. Die Interaktion zwischen virtuellen Organisationen wird dann alternativ mittels co-evolutionärer Algorithmen angepasst. Die auf Basis realer Arbeitslastaufzeichnungen durchgeführten Evaluationen zeigen, dass die so erstellten Grid-Schedulingstrategien für alle am Grid teilnehmenden Communities deutlich verkürzte Antwortzeiten für die jeweiligen Nutzergemeinschaften erreichen. Gleichzeitig wird eine große Robustheit der Verfahren sowohl gegenüber veränderlichen Grid-Umgebungen als auch gegenüber verändertem Nutzerverhalten bewiesen. Die Ergebnisse sind als Motivation für die stärkere Community-übergreifende Kooperation im Sinne eines Computational Grid zu sehen, da dies bei Nutzung entsprechend optimierter Verfahren in einer Win-win Situation für alle Teilnehmer resultiert.
Passive Infrarot-Lokalisierung
(2010-10-13) Kemper, Jürgen; Schwiegelshohn, Uwe; Kays, Rüdiger
Aufgrund der fortschreitenden Entwicklung im Bereich der Mikroelektronik sind wir heutzutage von einer Vielzahl intelligenter Systeme umgeben, die uns in unserem Tun unterstützen und uns neue Möglichkeiten der Interaktion mit unserer Umwelt bieten. Im Rahmen dieser Entwicklung sind ortsbezogene Dienste, die die Ortung einer Person erfordern, ein relativ neuer Trend. Im öffentlichen Bereich ist eine solche Ortung durch Systeme wie GPS bereits sehr etabliert, im häuslichen Bereich ist ihr Einsatz hingegen noch nicht so verbreitet. Zukünftig wird die sogenannte Inhaus-Lokalisierung aber eine immer größere Rolle spielen. So ist beispielsweise im Rahmen der Gebäudeautomatisierung eine Steuerung von Lichtszenen oder der Raumklimatisierung in Abhängigkeit von der Position einer Person denkbar. Allerdings stellt die Lokalisierung in Gebäuden im Hinblick auf Kosten, Benutzerkomfort und den Schutz der Privatsphäre besondere Anforderungen an die eingesetzten Systeme, die die bisher entwickelten Lösungen oft nicht in vollem Umfang erfüllen. So erfordern viele Ansätze das Mitführen einer aktiven Hardwarekomponente – auch Tag genannt – oder aber der Schutz der Privatsphäre ist aufgrund des Einsatzes von Kameras nicht gewährleistet. In dieser Arbeit wird ein System vorgestellt, das die Lokalisierung von Menschen anhand ihrer Körperwärmestrahlung ermöglicht. Da Körperwärmestrahlung dauerhaft und ohne Zutun des Benutzers emittiert wird und auf das Tragen eines Tags verzichtet werden kann, wird der Komfortgedanke bestmöglich erfüllt. Zusätzlich ist diese Art der Lokalisierung vollkommen anonym und gewährleistet so den Schutz der Privatsphäre. Um dem Kostenaspekt Rechnung zu tragen, erfolgt die Strahlungserfassung mit Hilfe einfacher, günstiger Sensoren (Thermopiles), die eine Objektpeilung erlauben. Der Einsatz einer speziellen Variante des Bayesschen Filters, dem Proability-Hypothesis-Density-Filter, ermöglicht eine recheneffiziente Lokalisierung mehrerer Personen, deren Anzahl implizit durch das Filter geschätzt wird. Die Realsierung und Evaluierung dieses Filters erfolgt mit Hilfe eines speziell für diesen Zweck entwickelten, echtzeitfähigen OpenGL-Simulators, der die Nachbildung dynamischer Inhaus-Szenen und der daraus resultierenden Sensorsignale erlaubt. Dadurch ist es möglich, den Aufwand zum Aufbau von Testumgebungen stark zu reduzieren. Weiterhin wird ein auf dem Newton-Raphson-Algorithmus basierendes Verfahren aufgezeigt, mit dem sich die Einrichtung und Inbetriebnahme des Systems extrem vereinfachen lässt. So besteht die einzige Aufgabe des Benutzers während der Systemkalibrierung darin, durch den Raum zu laufen und an verschiedenen Stellen stehen zu bleiben. Basierend auf den dabei durchgeführten Messungen werden anschließend die Position und Orientierung der Sensoren berechnet. Dadurch lässt sich im Vergleich zum manuellen Ausmessen eine enorme Zeitersparnis erreichen.
Evolutionäre Algorithmen zur Optimierung von Modellen für laufende Roboter
(2009-12-07T12:58:52Z) Hebbel, Matthias; Schwiegelshohn, Uwe; Burkhard, Hans-Dieter
Die Dissertation befasst sich mit der Modellierung und Optimierung von Laufbewegungen für zwei- und vierbeinige Roboter. Es werden parametrierbare Modelle für die Generierung von Laufbewegungen für zwei- und vierbeinige Roboter aufgestellt. Anschließend wird vorgestellt, wie Roboter mithilfe der Laufmodelle und dem Einsatz von Evolutionären Algorithmen autonom das Laufen erlernen. Zur Reduktion der benötigten Trainingsläufe werden verschiedene modellgestützte Evolutionsstrategien untersucht und eingesetzt. Da zur Beurteilung der Verfahren zahlreiche Optimierungsläufe notwendig sind, wird darüber hinaus präsentiert, wie ein physikalischer Robotersimulator lernt, sich möglichst so zu bewegen wie der reale Roboter.
Scheduling of tests on vehicle prototypes
(2009-10-22T08:24:32Z) Limtanyakul, Kamol; Schwiegelshohn, Uwe; Skutella, Martin
In the automotive industry, a manufacturer must perform several hundreds of tests on prototypes of a vehicle before starting its mass production. These tests must be allocated to suitable prototypes and ordered to satisfy temporal constraints and various kinds of test dependencies. To reduce costs, the manufacturer is interested in using the minimum number of prototypes. We apply Constraint Programming (CP) and a hybrid approach to solve the scheduling problem. Our CP method can achieve good feasible solutions even for our largest instances within a reasonable time. In comparison with existing methods, we can improve the solutions for most of our instances and reduce the average number of required prototypes. The hybrid approach uses mixed integer linear programming (MILP) to solve the planning part and CP to find the complete schedule. Although the hybrid approach is not as robust as CP with respect to data characteristics and additional constraints, it can complement CP in finding a better lower bound.
Component performance modeling and scheduling strategies on grids
(2009-08-11T09:27:43Z) Tonellotto, Nicola; Simoncini, Luca; Laforenza, Domenico; Schwiegelshohn, Uwe; Yahyapour, Ramin
A security architecture for microprocessors
(2008-11-26T13:59:17Z) Platte, Jörg; Schwiegelshohn, Uwe; Grimm, Christian
SAM ist eine Sicherheitsarchitektur, die aus einer Prozessorerweiterung und einem entsprechend angepassten Betriebssystem besteht. Die Prozessorerweiterung besteht primär aus einer für den Programmierer transparenten Sicherheitsschicht, die automatisch die Integrität aller geladenen Daten prüft und sämtliche Daten, die den Prozessor verlassen, verschlüsseln kann. Damit ist es selbst bei einem direkten Zugri auf den Hauptspeicher nicht möglich, ungeschützte Daten zu lesen oder zu manipulieren. Entschlüsselte Daten sind dabei nur innerhalb des Prozessors verfügbar und werden dort durch die Architektur vor unerlaubtem Zugri geschützt. Dieser Schutz schlie t auch Schutz vor privilegierten Benutzern wie Administratoren mit erweiterten Rechten ein. Weiterhin stellt SAM sicher, dass ein Programm nur auf bestimmten Prozessoren entschlüsselt werden kann und somit nur auf diesen ausführbar ist. Die Integritätssicherung wird über kryptographische Hashes erreicht. Diese ermöglichen eine überprüfung der Daten und dienen damit der Erkennung von Manipulationen. Jede vom Prozessor erkannte Manipulation führt zu einem sofortigen Programmabbruch. Somit ist sichergestellt, dass nur unmodifizierte Programme ausgeführt werden können und Manipulationen die Datensicherheit beeinträchtigen können. Der Prozessor muss verschlüsselte, gesicherte und ungesicherte (und damit auch unverschlüsselte) Speicherbereiche unterscheiden können. Bei SAM wird der Speicher dazu in einen gesicherten, einen verschlüsselten und einen ungesicherten Bereich aufgeteilt. Instruktionen, die in einem gesicherten Bereich liegen, können auf auf den gesamten Speicher zugreifen und verschlüsselte Daten werden transparent entschlüsselt. Ungesicherte Instruktionen können ebenfalls auf den gesamten Speicher zugreifen, allerdings bleiben verschlüsselte Bereiche verschlüsselt und können somit nicht analysiert werden. Das Betriebssystem basiert auf einem für SAM geringfügig angepassten Linux-Kernel. Die änderungen sind bestehen hauptsächlich aus der Anpassung hardwarenaher Funktionen des Prozessmanagements und des Multitaskings an die Sicherheitsfunktionen des Prozessors. Die Prozessorerweiterung ist als optionale Erweiterung entwickelt worden, damit normale und ungesicherte Programme parallel zu verschlüsselten Programmen ausgeführt werden können. Damit können die mit SAM gesicherten Prozessoren ebenfalls für nicht sicherheitskritische Aufgaben verwendet werden um deren Auslastung zu erhöhen. Die Umwandlung bestehender Programme in für SAM gesicherte Programme ist einfach, und erfordert nur minimale änderungen am Programmcode.
Beitrag zur Optimierung des Spanvolumens beim industrierobotergestützten Bandschleifen frei geformter Werkstücke
(2008-03-11T08:20:31Z) Čabaravdić, Malik; Künne, B.; Kuhlenkötter, B.
Fehlertolerante Integration limitierter Geräte in SOA unter Verwendung von Geräte-Proxies
(2008-02-12T09:10:35Z) Schramm, Peter; Schwiegelshohn, Uwe; Rehof, Jakob
Typische Ubiquitous-Computing-Umgebungen erfordern den Einsatz von Middleware, die in der Regel einen hohen Ressourcenbedarf an die teilnehmenden Geräte stellt. Jedoch befinden sich gerade in Ubiquitous-Computing-Umgebungen viele kleine, limitierte Geräte, die nur über geringe Ressourcen wie Rechenleistung, Arbeitsspeicher und Energie verfügen. In der Arbeit wird gezeigt, wie derart limitierte Geräte trotz ihrer Beschränkungen in Middleware-basierte Systeme integriert werden können. Dabei wird das Konzept der Geräte-Proxies verfolgt. Es wird gezeigt, wie Proxies für limitierte Geräte auf dynamische und transparente Weise bereitgestellt und ausgeführt werden können. Da Proxies und limitierte Geräte jedoch Seriensysteme bilden, wird durch den Einsatz des Proxy-Konzeptes die Ausfallwahrscheinlichkeit des Gesamtsystems erhöht. Aus diesem Grund werden im Rahmen der Arbeit geeignete Fehlertoleranzverfahren, wie die Migration von Proxies sowie die Anwendung von Rollback-Recovery-Protokollen untersucht. Anhand von Simulationen wird abschließend gezeigt, welche der betrachteten Rollback-Recovery-Protokolle sich für Proxy-basierte Systeme eignen.
Strategic negotiation models for grid scheduling
(2007-12-03T15:41:43Z) Li, Jiadao; Schwiegelshohn, Uwe; Gorlatch, Sergei
One of the key requirements for Grid infrastructures is the ability to share resources with nontrivial qualities of service. However, resource management in a decentralized infrastructure is a complex task as it has to cope with di erent policies and objectives of the di erent resource providers and the resource users. This problem is further complicated due to the diversity of the resource types and the heterogeneity of their local resource management systems. Agreement-based resource management can be used to address these issues because in the negotiation process of creating such bilateral service level agreements (SLAs) between Grid parties, the di erent polices of the resource providers and the users will be abstracted and observed. Such negotiation processes should be automated with no or minimal human interaction, considering the potential scale of Grid systems and the amount of necessary transactions. Therefore, strategic negotiation models play important roles. In this thesis, we have made several novel research contributions which are as follows: - An agreement based resource management approach is analyzed. Requirements for the automatic negotiation problems in Grid computing are introduced. Furthermore, related work in the areas of economics and agent communities are investigated. - Several negotiation models and negotiation strategies are proposed and examined. Simulation results demonstrate that these proposed negotiation models are suitable and e ective for Grid environments. - Firstly, a strategic negotiation model using time-based negotiation strategies is proposed and evaluated using discrete event based simulation techniques. - Secondly, time-based negotiation strategies are quite limited in the dynamically changing Grid environment because they are quite simple and static; so learning based negotiation strategies are investigated and evaluated, which are quite exible and e ective in the dynamically changing Grid environment. Also we adopted negotiation strategies considering opportunistic functions for Grid scheduling. - Thirdly, it is usually necessary that resources from di erent resource providers are co-allocated to satisfy the complex requirements of the users, so a strategic negotiation model supporting co-allocation and the tradeo between "first" and "best" agreements in the Grid computing is also proposed and evaluated. - Finally, the contributions of the current research work to the WSNegotiation protocol are analyzed.

Browse

Recent Submissions