Freiburg i. Br., Univ., Diss., 2007.

Diese Arbeit untersucht auf Basis der aktuellen Forschung Möglichkeiten, die Interaktion mit humanoiden Robotern variabler und somit attraktiver zu gestalten. Hierzu werden Möglichkeiten betrachtet, Emotionen und Absichten dynamisch mittels parametrisierter Gesten auszudrücken. Zunächst werden Gesten und mögliche Parameter analysiert, die zur Generierung eines Whole-Body-Gestensets notwendig sind, um anschließend diese auf Grund ihrer Auswirkungen auf die Gestenphasen in Intra- und Interphasenparameter zu unterteilen. Dadurch werden die innere und äußere Expressivität einer Geste definiert, die zur Bildung der Single Gesture Expression und der Multi Gesture Expression führen. Diese stellen das Steigerungspotential von Gesten beziehungsweise Absichten dar. Gesten werden anschließend nach Feedback-Arten untergliedert und in Abhängigkeit der Expressivität miteinander in Beziehung gesetzt. Somit entsteht ein Gestenset, das durch die Parameter „Feedback-Art“ und „Expressivität“ bestimmt wird. Besagtes Gestenset wurde daraufhin zur Verwendung durch den humanoiden Roboter Nao innerhalb der Entwicklungsumgebung Choregraphe umgesetzt. Zudem wurde eine Verhaltensbibliothek entwickelt, die sämtliche, implementierte Gesten zur Wiederverwendung enthält. Als Ergebnis entstand ein parametrisiertes Gestenset in Theorie und Praxis, das für die ausdrucksstarke Verwendung durch einen humanoiden Roboter geeignet ist und die Kommunikation und Interaktion zwischen Mensch und Roboter erweitert, verfeinert und verbessert.:1 Einleitung 9 2 Theoretische Hintergründe 11 2.1 Überblick über Gesten 11 2.2 Verwendung von Gesten in der Mensch-Roboter-Interaktion 13 2.2.1 Erkennung von Gesten einer Person durch einen Roboter 13 2.2.2 Verwendung von Gesten durch einen Roboter 15 2.3 Generierung und Parametrisierung von Gesten 17 2.4 Anwendungen von Gesten unter Verwendung des Nao 19 3 Entwurf eines parametrisierten Gestensets 23 3.1 Gestenanalyse 23 3.1.1 Entstehung und Entwicklung von Gesten 23 3.1.2 Analyse alltäglicher Gesten 26 3.1.3 Analyse von Gesten zur Feedback-Gestaltung 29 3.2 Parametrisierung von Gesten 33 3.2.1 Analyse und Bewertung möglicher Parameter 33 3.2.2 Auswahl und Kategorisierung der Parameter 35 3.2.3 Zuordnung der Parametern zu den Gesten 40 3.3 Kategorisierung und Auswahl relevanter Feedback-Gesten 41 3.3.1 Arten des expressiven Ausdrucks 41 3.3.2 Kategorisierung der Gesten anhand von Expressivitätsspannen 43 4 Implementierung des Gestensets für einen humanoiden Roboter 51 4.1 Technische Grundlagen 51 4.2 Grundüberlegungen zur Umsetzung 53 4.2.1 Umsetzung der Gestenerzeugung 53 4.2.2 Umsetzung der Multi Gesture Expression 54 4.3 Implementierung in Choregraphe 56 5 Abschließende Bem 61 5.1 Zusammenfassung 61 5.2 Fazit 62 5.3 Ausblick 63 Literaturverzeichnis 65 Abbildungsverzeichnis 69 Tabellenverzeichnis 71 Anhang 73 A Auswirkungen der Steigerung der Parameter auf die Gesten 73 B Anpassung der Expressivitätsspannen an den Nao und Unterteilung der Gesten in Stufen 79 C Aufbau der implementierten Gestenerzeugung in der Entwicklungsumgebung Choregraphe 83 / This work investigates the possibilities of developing a more variable, and thus attractive, interaction with humanoid robots based on current research. For this purpose possibilities of dynamically expressing emotions and intentions associated with parametrised gestures are contemplated. First, gestures and possible parameters, which are necessary for the generation of a whole-body gesture set, are analysed. Afterwards, these are classified into intraphaseparameters and interphase-parameters depending on their impact on gesture phases. A gesture’s inner and outer expressivity are thereby defined which leads to the establishment of the single gesture expression and the multi gesture expression. These constitute the gesture’s and the intention’s potential for increase. Gestures are subsequently classified by feedback types and are related depending on their expressivity. Hence, a gesture set which is defined by the parameters “feedback type” and “expressivity” is developed. As a result, the aforementioned gesture set has been implemented with the development environment Choregraphe to be used by humanoid robots. Additionally a behaviour library is generated for reusability which contains every implemented gesture. The result reveals a parametrised gesture set in theory and practice which is suitable to be expressively used by a humanoid robot and enhances, refines and improves the human-robot-interaction.:1 Einleitung 9 2 Theoretische Hintergründe 11 2.1 Überblick über Gesten 11 2.2 Verwendung von Gesten in der Mensch-Roboter-Interaktion 13 2.2.1 Erkennung von Gesten einer Person durch einen Roboter 13 2.2.2 Verwendung von Gesten durch einen Roboter 15 2.3 Generierung und Parametrisierung von Gesten 17 2.4 Anwendungen von Gesten unter Verwendung des Nao 19 3 Entwurf eines parametrisierten Gestensets 23 3.1 Gestenanalyse 23 3.1.1 Entstehung und Entwicklung von Gesten 23 3.1.2 Analyse alltäglicher Gesten 26 3.1.3 Analyse von Gesten zur Feedback-Gestaltung 29 3.2 Parametrisierung von Gesten 33 3.2.1 Analyse und Bewertung möglicher Parameter 33 3.2.2 Auswahl und Kategorisierung der Parameter 35 3.2.3 Zuordnung der Parametern zu den Gesten 40 3.3 Kategorisierung und Auswahl relevanter Feedback-Gesten 41 3.3.1 Arten des expressiven Ausdrucks 41 3.3.2 Kategorisierung der Gesten anhand von Expressivitätsspannen 43 4 Implementierung des Gestensets für einen humanoiden Roboter 51 4.1 Technische Grundlagen 51 4.2 Grundüberlegungen zur Umsetzung 53 4.2.1 Umsetzung der Gestenerzeugung 53 4.2.2 Umsetzung der Multi Gesture Expression 54 4.3 Implementierung in Choregraphe 56 5 Abschließende Bem 61 5.1 Zusammenfassung 61 5.2 Fazit 62 5.3 Ausblick 63 Literaturverzeichnis 65 Abbildungsverzeichnis 69 Tabellenverzeichnis 71 Anhang 73 A Auswirkungen der Steigerung der Parameter auf die Gesten 73 B Anpassung der Expressivitätsspannen an den Nao und Unterteilung der Gesten in Stufen 79 C Aufbau der implementierten Gestenerzeugung in der Entwicklungsumgebung Choregraphe 83

In der klassischen Komplexitätstheorie unterscheiden wir zwischen der Klasse P von in Polynomialzeit lösbaren Problemen, und der Klasse NP-schwer von Problemen bei denen die allgemeine Annahme ist, dass diese nicht in Polynomialzeit lösbar sind. Allerdings sind viele Probleme, die wir lösen möchten, NP-schwer. Gleichzeitig besteht eine große Diskrepanz zwischen den empirisch beobachteten und den festgestellten worst-case Laufzeiten. Es ist bekannt, dass Vorverarbeitung oder Datenreduktion auf realen Instanzen zu Laufzeitverbesserungen führt. Hier stoßen wir an die Grenze der klassischen Komplexitätstheorie. Der Fokus dieser Arbeit liegt auf Vorverarbeitungsalgorithmen für NP-schwere Probleme. Unser Ziel ist es, bestimmte Instanzen eines NP-schweren Problems vorverarbeiten zu können, indem wir die Struktur betrachten. Genauer gesagt, für eine gegebene Instanz und einen zusätzlichen Parameter l, möchten wir in Polynomialzeit eine äquivalente Instanz berechnen, deren Größe und Parameterwert nur durch eine Funktion im Parameterwert l beschränkt ist. In der parametrisierten Komplexitätstheorie heißen diese Algorithmen Kernelisierung. Wir werden drei NP-schwere Graphenprobleme betrachten, nämlich Vertex Cover, Edge Dominating Set und Subset Feedback Vertex Set. Für Vertex Cover werden wir bekannte Ergebnisse für Kernelisierungen vereinheitlichen, wenn der Parameter die Größe einer Entfernungsmenge zu einer gegebenen Graphklasse ist. Anschließend untersuchen wir die Kernelisierbarkeit von Edge Dominating Set. Es stellt sich heraus, dass die Kernelisierbarkeit deutlich komplexer ist. Dennoch klassifizieren wir die Existenz einer polynomiellen Kernelisierung, wenn jeder Graph in der Graphklasse eine disjunkte Vereinigung von konstant großen Komponenten ist. Schließlich betrachten wir das Subset Feedback Vertex Set Problem und zeigen, dass es eine randomisierte polynomielle Kernelisierung hat, wenn der Parameter die Lösungsgröße ist. / In classical complexity theory, we distinguish between the class P, of polynomial-time solvable problems, and the class NP-hard, of problems where the widely-held belief is that we cannot solve these problems in polynomial time. Unfortunately, many of the problems we want to solve are NP-hard. At the same time, there is a large discrepancy between the empirically observed running times and the established worst-case bounds. Using preprocessing or data reductions on real-world instances is known to lead to huge improvements in the running time. Here we come to the limits of classical complexity theory. In this thesis, we focus on preprocessing algorithms for NP-hard problems. Our goal is to find ways to preprocess certain instances of an NP-hard problem by considering the structure of the input instance. More precisely, given an instance and an additional parameter l, we want to compute in polynomial time an equivalent instance whose size and parameter value is bounded by a function in the parameter l only. In the field of parameterized complexity, these algorithms are called kernelizations. We will consider three NP-hard graph problems, namely Vertex Cover, Edge Dominating Set, and Subset Feedback Vertex Set. For Vertex Cover, we will unify known results for kernelizations when parameterized by the size of a deletion set to a specified graph class. Afterwards, we study the existence of polynomial kernelizations for Edge Dominating Set when parameterized by the size of a deletion set to a graph class. We point out that the existence of polynomial kernelizations is much more complicated than for Vertex Cover. Nevertheless, we fully classify the existence of polynomial kernelizations when every graph in the graph class is a disjoint union of constant size components. Finally, we consider graph cut problems, especially the Subset Feedback Vertex Set problem. We show that this problem has a randomized polynomial kernelization when the parameter is the solution size.

In der klassischen Komplexitätstheorie werden worst-case Laufzeiten von Algorithmen typischerweise einzig abhängig von der Eingabegröße angegeben. In dem Kontext der parametrisierten Komplexitätstheorie versucht man die Analyse der Laufzeit dahingehend zu verfeinern, dass man zusätzlich zu der Eingabengröße noch einen Parameter berücksichtigt, welcher angibt, wie strukturiert die Eingabe bezüglich einer gewissen Eigenschaft ist. Ein parametrisierter Algorithmus nutzt dann diese beschriebene Struktur aus und erreicht so eine Laufzeit, welche schneller ist als die eines besten unparametrisierten Algorithmus, falls der Parameter klein ist. Der erste Hauptteil dieser Arbeit führt die Forschung in diese Richtung weiter aus und untersucht den Einfluss von verschieden Parametern auf die Laufzeit von bekannten effizient lösbaren Problemen. Einige vorgestellte Algorithmen sind dabei adaptive Algorithmen, was bedeutet, dass die Laufzeit von diesen Algorithmen mit der Laufzeit des besten unparametrisierten Algorithm für den größtmöglichen Parameterwert übereinstimmt und damit theoretisch niemals schlechter als die besten unparametrisierten Algorithmen und übertreffen diese bereits für leicht nichttriviale Parameterwerte. Motiviert durch den allgemeinen Erfolg und der Vielzahl solcher parametrisierten Algorithmen, welche eine vielzahl verschiedener Strukturen ausnutzen, untersuchen wir im zweiten Hauptteil dieser Arbeit, wie man solche unterschiedliche homogene Strukturen zu mehr heterogenen Strukturen vereinen kann. Ausgehend von algebraischen Ausdrücken, welche benutzt werden können, um von Parametern beschriebene Strukturen zu definieren, charakterisieren wir klar und robust heterogene Strukturen und zeigen exemplarisch, wie sich die Parameter tree-depth und modular-width heterogen verbinden lassen. Wir beschreiben dazu effiziente Algorithmen auf heterogenen Strukturen mit Laufzeiten, welche im Spezialfall mit den homogenen Algorithmen übereinstimmen. / In classical complexity theory, the worst-case running times of algorithms depend solely on the size of the input. In parameterized complexity the goal is to refine the analysis of the running time of an algorithm by additionally considering a parameter that measures some kind of structure in the input. A parameterized algorithm then utilizes the structure described by the parameter and achieves a running time that is faster than the best general (unparameterized) algorithm for instances of low parameter value. In the first part of this thesis, we carry forward in this direction and investigate the influence of several parameters on the running times of well-known tractable problems. Several presented algorithms are adaptive algorithms, meaning that they match the running time of a best unparameterized algorithm for worst-case parameter values. Thus, an adaptive parameterized algorithm is asymptotically never worse than the best unparameterized algorithm, while it outperforms the best general algorithm already for slightly non-trivial parameter values. As illustrated in the first part of this thesis, for many problems there exist efficient parameterized algorithms regarding multiple parameters, each describing a different kind of structure. In the second part of this thesis, we explore how to combine such homogeneous structures to more general and heterogeneous structures. Using algebraic expressions, we define new combined graph classes of heterogeneous structure in a clean and robust way, and we showcase this for the heterogeneous merge of the parameters tree-depth and modular-width, by presenting parameterized algorithms on such heterogeneous graph classes and getting running times that match the homogeneous cases throughout.