Dr. Uwe Franke
Daimler AG, Böblingen
The performance of future driver assistance systems - as well as the potential of autonomous robots - depends on precision, robustness and completeness of their environment perception. The urban scenario in particular poses high demands on the computer vision, since dangerous situations have to be recognized fast and with high confidence. The talk will present a dense stereo analysis scheme with real-time capability. Recently developed methods to reach maximum precision in sub-pixel accuracy will be described. Most known stereo systems concentrate on single image pairs. It will be shown that a smart fusion of stereo vision and motion analysis (optical flow) gives much better results than classical frame-by-frame reconstructions. The basic idea is to track points with depth known from stereo vision over two and more consecutive frames and to fuse the spatial and temporal information using Kalman filters. The result is an improved accuracy of the 3D-position and an estimation of the 3D-motion of the considered point at the same time. This approach, called 6D Vision, enables the detection of moving objects even if they are partially hidden. From static points very accurate occupancy grids are built. A global optimization technique delivers a robust estimation of the free space which is important for the situation analysis. The moving pixels are clustered to objects which are then tracked over time in order to estimate their motion state and to predict their paths. This allows for powerful collision avoidance systems: pedestrians crossing the street are detected before they enter the lane; the same holds for vehicles from the side, which are not detected by common radar systems. The presentation will be held in German. (03.11.2009, dfi)
Dipl-Inf. Stefan Richter
Public libraries have served an invaluable function for a long time. Yet in an age of digital media, traditional methods of publishing and distributing information become increasingly marginalized. In this talk, we pose the question if and how information technology can be employed to find functional alternatives, conforming to the needs of society that have been changed by information technology itself. To this end we introduce the concept of world libraries: Massively distributed systems that allow for the efficient sharing of large data volumes in open, untrusted environments while preserving privacy. After defending the utility of our definition with philosophical, economical, and legal arguments, we examine anonymous file sharing systems with regard to their applicability for world libraries. We identify reasons why these systems have failed to achieve popularity so far, as well as promising principles and structures for successful world library implementations. Of these, distributed hash tables (DHTs) turn out to be particularly important. That is why we study their security and privacy properties in detail. Using both analytical models and simulation, weaknesses in earlier approaches are shown, leading us to the discovery of the first practical DHT that scalably defends against active adversaries. Finally, we summarize our findings and their impact on world library design. (02.11.2009, dfi)
Dr. rer. nat. Stefan Kriebel
BMW Group, München
Die Entwicklung sicherheitsrelevanter Systeme im Automobil gewinnt rasch zunehmend an Bedeutung. Zum einen liegt dies an der stetig zunehmenden Komplexität von Funktionen, zum anderen an deren ebenfalls stark zunehmenden Vernetzung. Die Beherrschung dieser Vernetzung ist die Grundlage für Innovationen und somit eine notwendige Basis für OEMs. Dies gilt insbesondere auch für sicherheitsrelevante Funktionen, zum Beispiel im Bereich (teil-) autonomes Fahren.
Um die Wirtschaftlichkeit in Entwicklung, Produktion und Service von vernetzten sicherheitsrelevanten Funktionen für einen OEM sicherzustellen, sind Veränderungen in der heute eingeführten Wertschöpfungskette der Automobilindustrie erforderlich. Diese werden u.a. durch eine ganzheitliche Betrachtung der Dimensionen der Funktionssicherheit motiviert. (02.11.2009, dfi)
Dipl.-Ing. Jan Kritzner
Multimedia traffic like Video Streaming is becoming more and more important in the Internet. Existing transport protocols like TCP and UDP/RTP are not able to deliver the required service as needed. A new transport protocol is required to cope with these problems.
Future transport protocols need four key features: tunability, adaptability, compatibil-ity and flexibility. With these requirements in mind, a new transport protocol TPTR (Transport Protocol with Tunable Reliability) has been defined. It consists of three sublayers: 1) Application Framing, 2) Windowing, Reliability, Timing and Flow-Control, and 3) Congestion Control.
The presentation will highlight several improvements to existing techniques: At the Application Framing level the concept of decodability will be presented which trans-forms structural information into priority values. At the next sublayer the generalised priority based scheduler is introduced, and an analysis of the congestion control problem and some solutions are given. (16.10.2009, dfi)
Prof. Dr. Marta Kwiatkowska
University of Oxford, UK
The vast majority of software verification research to date has concentrated on qualitative analysis methods, for example the absence of safety violations in program executions. Many programs, however, contain randomisation, timing and resource information. Quantitative verification is a technique for establishing quantitative properties of a system model, such as the probability of battery power dropping below minimum, the expected time for message delivery and the expected number of messages lost before protocol termination. Tools such as the probabilistic model checker PRISM (www.prismmodelchecker.org) are widely used in several application domains, including security and network protocols, but their application to real software is limited.
This lecture presents recent results concerning quantitative software verification for ANSI-C programs extended with random assignment. The goal is to focus on system software that exhibits probabilistic behaviour and properties such as "the maximum probability of file-transfer failure", or "the maximum expected number of failed transmissions". We use a quantitative abstraction-refinement framework based on predicate abstraction, in which probabilistic programs are represented as Markov decision processes and their abstractions as stochastic two-player games. These techniques have been implemented using components from GOTO-CC, SATABS and PRISM and successfully used to verify actual networking software. (23.09.2009, dfi)
Dipl.-Inform. Tingting Han
In this talk, we consider two important aspects of model checking Markov models: diagnosis - generating counterexamples and synthesis - providing valid parameter values. The two aspects are relatively independent while both contribute to developing new theory and algorithms in the research field of probabilistic model checking.
In the first part, we consider counterexample generation in the setting of probabilistic model checking. To achieve this, we transform the problem of finding informative counterexamples to shortest path(s) (SP) problems in graph theory, where new SP algorithms are proposed to tackle new scenarios. We then present a more compact representation of counterexamples by regular expressions. Heuristic-based algorithms are applied to generate short regular expression counterexamples. Finally we extend the definition and counterexample generation algorithms to various combinations of probabilistic models and logics.
The second part of the presentation is concerned with synthesizing values for parametric continuous-time Markov chains (pCTMCs) wrt. time-bounded reachability specifications. The rates in the pCTMCs are expressed by polynomials over reals with parameters and the main question is to find all the parameter values (forming a synthesis region) with which the specification is satisfied. To this end, a symbolic approach based on a closed-from expression and a nonsymbolic approach based on interval arithmetic will be presented with the respective error bound, time complexity as well as a detailed comparison. (22.09.2009, dfi)
Frau Prof. Dr. Myra Spiliopoulou
Otto-von-Guericke-Universität Magdeburg
The multi-relational data mining paradigm deals with the challenge of model learning over a set of correlated database tables. This paradigm is intended for static datasets though, while many modern applications require the analysis of streams. It is obvious that customer transactions in an e-shop constitute a stream; there are mature methods for mining such a stream in isolation. However, the customers themselves constitute another stream that brings new objects whenever an individual becomes a customer. The products build a further, slower stream from which objects are forgotten when they are no longer offered for sale. Learning a model over such a “multi-table stream” implies solving problems that do not occur in the static scenario. In this talk, we will see solutions to these problems.
The methods we discuss deal with (a) the management of the correlated streams and their transformation into a single stream for mining and (b) the impact of growing objects upon the model. The first issue involves synchronizing streams that reference each other and arrive at different speeds, judiciously forgetting objects that reference each other, and dealing with changes in the valuerange of the attributes. The second issue involves monitoring how an object “grows” as other objects reference it, and then deciding which objects to involve in model learning – depending, among others on object size. We report on experiments for unsupervised model learning over a labeled and an unlabeled multi-table stream (08.09.2009, dfi)
Dipl.-Inform. Stefan Rieger
We present an abstraction and verification framework for pointer programs operating on unbounded heaps. To this end, we introduce an abstraction method for pointermanipulating programs employing context-free hyperedge replacement graph grammars to model the data structures and compute the abstraction mappings.
By means of partial concretization steps we avoid the necessity for explicitly defining the effect of pointer-manipulating operations on abstracted parts of the heap: it is obtained “for free” by combining partial concretization, the concrete pointer operation, and re-abstraction of the transformed state.
Besides the possibility to check for pointer safety, assuring the absence of null dereferences, and shape safety, the preservation of the data structure, we establish an expressive pointer logic that is based on LTL. It allows to specify safety as well as liveness properties for the executions of the system. We show that the corresponding model checking problem can be reduced to an LTL model checking problem enabling the application of existing, highly optimized model checkers. (08.09.2009, dfi)
Since 2002, FoLLI (the Association for Logic, Language, and Information) awards the E. W. Beth Dissertation Prize to outstanding dissertations in the fields of Logic, Language, and Information. The dissertations are judged on the impact they made in their respective fields, breadth and originality of the work, and also on its interdisciplinarity. Ideally the winning dissertation will be of interest to researchers in all three fields. The E.W. Beth Dissertation Prize 2009 has been jointly awarded to Emmanuel Chemla from the Ecole Normale Superieure de Paris for the thesis 'Presuppositions and Scalar Implicatures: Formal and Experimental Studies', and Lukasz Kaiser from Aachen University, Research Group Mathematical Foundations of Computer Science, for the thesis 'Logic and Games on Automatic Structures'. (14.08.2009, dfi)
Dipl.-Inform. Carsten Kern,
Learning algorithms are increasingly used in multiple disciplines of today's computer science reaching from robotics and formal verification to bioinformatics or natural language recognition.
In this talk, we consider learning algorithms in the context of software development and verification. Two novel variants of learning algorithms will be presented. In the first part, we introduce NL* an algorithm for learning nondeterministic automata from queries and counterexamples. NL* will be shown to yield exponentially better results concerning number of states of the resulting automata than its deterministic version L*. Though theoretical worst case results concerning membership- and equivalence queries are worse than for L*, we will show that in practice NL* usually outperforms L* by far.
The second part of the presentation is concerned with learning and synthesizing distributed automata. To this end, we extend the well-known L* learning algorithm for deterministic automata. Many existing approaches learn a global communicating system and project it to its communicating processes. This, however, usually implies additional and most often undesired behavior. In contrast, we present an approach which yields exact systems, i.e., behavior that was specified as positive will always be contained in the final system and undesired behavior excluded. (30.07.2009, dfi)
Prof. Dr. Ingo Schmitt
Technische Universität Cottbus
Im Vortrag werden die Grundkonzepte der Anfragesprache CQQL vorgestellt, welche eine logikbasierte Kombination von Ähnlichkeitsbedingungen ermöglicht. Dabei werden Ähnlichkeitsbedingungen unterstützt, welche sich durch eine semi-positiv definite Korrelationsmatrix ausdrücken lassen. Die Sprache CQQL stellt eine Verallgemeinerung des relationalen Bereichskalküls dar. Ein spezieller Gewichtungsansatz ermöglicht eine Gewichtung unterschiedlicher Bedingungen. Die Gewichte können direkt spezifiziert, aber auch aus Präferenzen über Beispielobjekten gelernt werden. Konkrete Gewichtswerte lassen sich im Rahmen eines Relevance-Feedback-Verfahrens komplett vor dem Nutzer verbergen. Das Lernverfahren kann zum Lernen von logischen Verknüpfungen von Ähnlichkeitsbedingungen erweitert werden. Dies ist zum Beispiel zum Entdecken von logischen Zusammenhängen zwischen low-Level- Feature und high-level-Feature im Kontext einer Multimediasuche hilfreich. (16.07.2009, dfi)
Dipl.-Inform. Joachim Kneis
Exakte Algorithmen haben sich in den letzten Jahren als Ansatz zur Lösung NP-schwerer Probleme etabliert. Dies beruht zum einen auf den Einschränkungen möglicher Alternativen. Beispielsweise existieren keine Approximationsalgorithmen für Independent Set oder Dominating Set mit konstanter Güte. Zum anderen besteht in einigen Gebieten die Notwendigkeit, optimale Lösungen zu finden, zum Beispiel in der Bioinformatik.
In vielen Fällen basieren exakte Algorithmen mittlerweile auf sehr aufwendigen Operationen oder großen Fallunterscheidungen, um die exponentiellen Laufzeitkomponenten möglichst zu reduzieren. Allerdings sind die resultierenden Algorithmen nicht nur sehr kompliziert und wenig ästhetisch, sondern weisen auch einen hohen polynomiellen Overhead auf.
Im Gegensatz dazu liegt in diesem Vortrag das Augenmerk auf intuitiven und einfachen Algorithmen. Die besondere Schwierigkeit liegt dabei darin, die Algorithmen so einfach wie möglich zu halten und gleichzeitig konkurrenzfähige Laufzeiten zu erreichen. Vorteile solcher intuitiver Algorithmen sind dann unter anderem eine leichtere Implementierbarkeit und oft auch überlegene Laufzeiten auf kleinen Instanzen, bedingt durch geringeren Overhead. Anhand mehrerer Beispiele wird das Potential dieses Ansatzes erläutert werden. (14.07.2009, dfi)
The team "OldEurOpe" of RWTH Aachen University clearly won this years "Capture-the-flag" contest Cipher 5. The second best Team "HackerDom" of Ural State University, Russia followed with 77% of OldEuroOpe's points. The RWTH team toped the 34 opponent teams in all three categories: offensive, defensive, and ethical. http://www.cipher-ctf.org/cipher5/ (13.07.2009, sts)
Vivekanand Gopalkrishnan, Ph.D.
Nanyang Technological University Singapore
Frequent pattern mining is one of the most well-studied topics in data mining. The set of frequent patterns of a transactional database can be treated as a summary that contains all useful information within the database. Previously, frequent patterns have been successfully applied for classification, clustering, association rule mining, and indexing. This talk covers two basic applications of frequent patterns: in database characterization and in finding interesting patterns. We show the limitations of these applications and discuss possible approaches to enhance them.
Because of the redundancy among the set of frequent patterns, it is usually too large for characterizing and understanding the database. To resolve this issue, we propose to summarize the frequent patterns in ways that allow easier analysis.
While most interesting patterns are frequent, some are (barely) not, especially in the presence of noise. Naive approaches attempt to recover such interesting patterns by reducing support. Instead, we propose to mine generalized (fault-tolerant) patterns, so that more interesting patterns can be discovered, without mining many un-interesting patterns. (29.06.2009, dfi)
Dr. Michael Ley
Universität Trier
Die Trierer Bibliographie "DBLP" enthält z.Zt. (Juni 2009) mehr als 1.2 Millionen Nachweise von Informatik-Fachpublikationen. Die Anfänge der Sammlung entstanden Ende 1993. Zunächst war DBLP eine spezialisierte Bibliographie für die Bereiche "DatenBanken" und "LogikProgrammierung". Später wurde die thematische Abdeckung erheblich erweitert. Die noch lange nicht erreichte Wunschvorstellung ist eine Nachweisdatenbank für die gesamte Informatik.
Trotz aller Unzulänglichkeiten wird DBLP von vielen Informatikern als Werkzeug zur Literaturrecherche und bei der Zusammenstellung von Literaturlisten für eigene Veröffentlichungen benutzt.
Bei der Zusammenstellung von Programmkomitees wird DBLP oft zu Rate gezogen, um die fachliche Ausrichtung und Veröffentlichungsaktivitäten von Kollegen auf einen Blick einzuschätzen. Von hier aus ist es nur noch ein kleiner Schritt bis zur umstrittenen bibliometrischen Evaluation von Personen, Arbeitsgruppen, Fachbereichen, Zeitschriften oder Tagungsreihen. Spätestens hier muss die Datengrundlage "DBLP" kritisch hinterfragt werden. Die bibliographischen Informationen in DBLP können in keinster Weise "vollständig" sein.
Der Vortrag soll eine realistische Einschätzung der Stärken, Schwächen und Entwicklungsmöglichkeiten von DBLP ermöglichen und Impulse zur Diskussion über die Rolle von Publikationen im Fach Informatik geben. (22.06.2009, dfi)
Dipl.-Inform. Anne-Therese Körtgen
In Entwicklungsprozessen wird das zu entwickelnde System aus unterschiedlichen Blickwinkeln und auf verschiedenen Abstraktionsstufen durch Dokumente beschrieben, welche in der Regel mittels heterogener, voneinander unabhängiger Software-Werkzeuge bearbeitet werden. Dokumente überlappen sich inhaltlich, wodurch es bei paralleler Bearbeitung der Dokumente zu inkonsistenten Beschreibungen kommen kann. Zur Behebung dieser Inkonsistenzen bedarf es Werkzeugunterstützung, so dass Änderungen an einem Dokument konform in andere betroffene Dokumente übertragen werden.
Thema dieses Vortrags sind spezielle Aspekte allgemeiner Konzepte und Werkzeuge zur Konsistenzwiederherstellung, auch Integration genannt. Beispielhaft werden Konsistenzprobleme in verfahrenstechnischen Entwicklungsprozessen untersucht, die zugrunde liegenden Probleme und deren Lösungen gelten aber auch für andere Anwendungsfelder. Basis sind graphbasierte Spezifikationen möglicher Beziehungen zwischen Dokumenten, die in sog. Integrationsregeln vorliegen.
Auf Änderungen an den Dokumenten kann mit verschiedenartigen konsistenzwiederherstellenden Transformationen reagiert werden, welche dynamisch konstruiert werden müssen. Die verschiedenen Alternativen und ihre Konstruktion werden im Vortrag vorgestellt. Des Weiteren wird die Modellierungssprache für Integrationsregeln präsentiert, sowie zwei Ansätze zur automatischen Regelerstellung, da ihre bisherige händische Erstellung ein aufwändiger Prozess ist. Aus bestehenden Beziehungen (i) zwischen Elementen der Dokumentenebene bzw. (ii) zwischen Typen und Attributen der Dokumentenmodellebene werden Integrationsregeln induziert. Die Beziehungen werden zuvor mit einer interaktiven Korrespondenzanalyse ermittelt, die auch von dem Konsistenzsicherungswerkzeug durchgeführt wird anhand generischer Integrationsregeln. (22.06.2009, dfi)
Frau Dr. Ira Assent
Aalborg University, Dänemark
For large multimedia databases, outsourcing of data is an interesting option for reducing cost and maintenance overhead. To protect valuable data, privacy needs to be guaranteed while still providing the means for meaningful access to the data. This work considers private similarity search on arbitrary metric features in an outsourcing scenario. We propose techniques that transform the data prior to supplying it to the outsourcing service provider in order to protect privacy. The techniques represent different, useful trade-offs among data privacy, query cost and accuracy. We characterize the privacy offered by the different techniques, and discuss how they can be further extended for the k-anonymization model. Our experiments with real world data demonstrate that the techniques are capable of offering privacy while enabling efficient and accurate processing of similarity queries. (17.06.2009, dfi)
Researchers from the Mobile Multimedia Processing group at RWTH Aachen, in a collaboration with ETH Zurich, won the "Best Vision Paper Award" at the recent International Conference on Robotics and Automation (ICRA'09) held in Kobe, Japan, in May 2009. The rewarded work finds and tracks pedestrians in dynamic inner-city environments from a mobile platform. More information can be found on the MMP webpage. (02.06.2009, sts)
John Field
IBM T.J. Watson Research Center
Scripting languages are justifiably popular because of their support for rapid and exploratory development. However, scripts are notoriously hard to compose and to evolve. Additionallly, though more and more applications require concurrency for example, to manage interaction with remote distributed services support for concurrency in existing scripting languages is weak at best. In this talk, I will describe Thorn, a new concurrent scripting language being developed by IBM and Purdue University. I will show how Thorn's module and type annotation features support the evolution of scripts into industrial-grade programs. I will also show how Thorn's concurrency features can be used to rapidaly develop scalable applications, while avoiding many of the pitfalls of Java-style concurrency.
This work is joint with B. Bloom, N. Nystrom, J. Östlund, G. Richards, R. Strnis(a, J. Vitek, and T. Wrigstad. (29.05.2009, dfi)
Jim Carlo
J. Carlo Consulting LLC
This talk will describe the IEEE 802 organization, focusing on the key principles that have led to the success of IEEE 802 standards. Jim will also describe the process requirements in developing IEEE standards and how Patents are handled in the process. Patents can both benefit and harm the overall Standard Process. (29.05.2009, dfi)
Dipl.Ing. Maja Popovic
In this thesis, three possible aspects of using linguistic (i.e. morpho-syntactic) knowledge for statistical machine translation are described: the treatment of syntactic differences between source and target language using source POS tags, statistical machine translation with a small amount of bilingual training data, and automatic error analysis of translation output.
Reorderings in the source language based on the POS tags are systematically investigated: local reorderings of nouns and adjectives or the Spanish-English language pair and long range reorderings of verbs for the German-English language pair. Both types of reorderings result in better performance of the translation system, local reordering being more important for the scarce training corpora. For such corpora, strategies for achieving an acceptable translation quality by applying appropriate morpho-syntactic transformations are exploited for three language pairs: Spanish-English, German-English and Serbian-English. Very scarce task-specific corpora as well as conventional dictionaries are used as bilingual training material. In addition to conventional dictionaries, the use of phrasal lexica is proposed and investigated.
A framework for automatic analysis and classification of actual errors in translation output based on combining existing automatic evaluation measures with linguistic information is presented. Experiments on different types of corpora and various language pairs show that the results of automatic error analysis correlate very well with the results of human evaluation. The new metrics based on analysed error categories are used for comparison of different translation systems trained on various sizes of texts with and without morpho-syntactic transformations.
For improving the quality of a statistical machine translation system by the use of morpho-syntactic information, the choice of the method and the significance of improvements strongly depend on the language pair, the translation direction and the nature of the corpus. Error analysis of the translation output is important in order to define weak points of the system and apply methods for improvement in the optimal way. (24.04.2009, dfi)
Prof. Dr. Daniel Cremers
University of Bonn
Numerous computer vision problems can be cast as labelling problems where each point is assigned one of several labels. The case of two labels includes problems like binary segmentation and multiview reconstruction. The case of multiple labels includes problems such as stereo depth reconstruction and image denoising. In my presentation, I will introduce methods of convex relaxation and functional lifting which allow to optimally solve such labelling problems in a spatially continuous setting. Experimental results demonstrate that these spatially continuous approaches provide numerous advantages over spatially discrete (graph cut) formulations, in particular they are easily parallelized (lower runtime), they require less memory (higher resolution) and they do not suffer from metrication errors (better accuracy). This is joint work with Kalin Kolev, Maria Klodt, Thomas Brox, Selim Esedoglu and Thomas Pock. (24.04.2009, dfi)
Dr. Pieter Collins,
CWI Amsterdam
While digital computers are inherently discrete automata, they are often used to solve problems arising in continuous mathematics. This gives rise to fundamental questions regarding how to represent objects (such as real numbers and subsets of Euclidean space), what constitutes a valid computation, and which operators can be computed. In this talk, I will outline a theory of computation in which the main types used in continuous mathematics can be handled in a natural yet rigorous way, and use the results to solve some problems arising in dynamical systems and control theory. (14.04.2009, dfi)
Dr. Clemens Grelck
University of Amsterdam, University of Hertfordshire
The first generation of multicore processors has reached the mass computer market while the development roadmaps of all major processor manufacturers promise a steep rise in the number of cores for the near future. This paradigm shift in processor architecture brings parallel computing from the niche market of supercomputing applications into the mainstream of computing. These new hardware requirements will cause a similar paradigm shift in software engineering: To make efficient use of available hardware resources, any software must become parallel. Established parallel programming models and languages, however, are very much geared towards the needs of supercomputing applications: They allow expert programmers to achieve high runtime efficiency on a given class of machines, but incur development costs that are hardly justifiable outside supercomputing labs.
We present two complementary approaches to efficient programming of multicore systems: SaC and S-Net. SaC is a fully-fledged functional array programming language that adopts the syntactic conventions of C/C++/C#/Java to allow for a smooth transition from these languages. The array programming model of SaC encourages a data parallel programming style that is suitable for fully compiler-based identification and utilisation of concurrency. In essence, programmers may write a parallel program with a sequential mindset. Our aggressively optimising SaC compiler yields sequential programs that are competitive in performance with C and Fortran codes; automatic parallelisation achieves true speedups over these machine-oriented languages.
Not all problems lend themselves to a data parallel solution in a natural way. Automatic detection of other forms of concurrency in regular sequential code, however, has proven to be be overly ambitious. Therefore, we have proposed S-Net as a declarative coordination language for explicit concurrency engineering. S-Net achieves a near complete separation of concerns between the development of sequential (or implicitly parallel) application building blocks and their parallel orchestration in a streaming network of asynchronous components. Concurrency is dealt with explicitly, but instead of augmenting a sequential language with all sorts of annotations and, hence, intertwining computing and concurrency issues, we introduce an explicit concurrency layer into the software engineering process. (24.03.2009, dfi)
Prof. Dr. Anthony T. Chronopoulos
University of Texas at San Antonio
Grid computing can be used for high performance computations. However, a serious difficulty in concurrent programming of such heterogeneous systems is how to deal with scheduling and load balancing of such systems which may consist of heterogeneous computers on different sites. Distributed scheduling schemes suitable for parallel loops with independent iterations on heterogeneous computer clusters have been proposed and analyzed in the past. We implemented previously derived schemes in MPICH-G2 and MPIg on the TeraGrid. We present performance results for three loop scheduling schemes on single and multi-site TeraGrid clusters. (24.03.2009, dfi)
Jan Peters, Ph. D.
MPI for Biological Cybernetics
Autonomous robots that can assist humans in situations of daily life have been a long standing vision of robotics, artificial intelligence, and cognitive sciences. A first step towards this goal is to create robots that can learn tasks triggered by environmental context or higher level instruction. However, learning techniques have yet to live up to this promise as only few methods manage to scale to high-dimensional manipulator or humanoid robots. In this talk, we investigate a general framework suitable for learning motor skills in robotics which is based on the principles behind many analytical robotics approaches. It involves generating a representation of motor skills by parameterized motor primitive policies acting as building blocks of movement generation, and a learned task execution module that transforms these movements into motor commands.
Learning parameterized motor primitives usually requires reward-related self- improvement, i.e., reinforcement learning. We propose a new, task-appropriate architectures, such as the Natural Actor-Critic and the PoWER algorithm. For the proper execution of motion, we need to learn how to realize the behavior prescribed by the motor primitives in their respective task space through the generation of motor commands. This transformation corresponds to solving the classical problem of operational space control through machine learning techniques.
Such robot control problems can be reformulated as immediate reward reinforcement learning problems. We derive an EM-based reinforcement learning algorithm which reduces the problem of learning with immediate rewards to a reward-weighted regression problem. The resulting algorithm learns smoothly without dangerous jumps in solution space, and works well in application to complex high degree-of-freedom robots. (11.03.2009, dfi)
Dipl.-Inform. Ingo Assenmacher
Virtual Reality (VR) environments define computer simulated worlds. The users' interaction with these worlds should be as intuitive as possible, using the visual, aural and haptic senses and natural body movements. In order to achieve this goal, VR software systems have to process inherently parallel but heterogeneous tasks under real-time conditions. The time for signal processing and reproduction is constrained by human perception thresholds. The reproduction systems often suffer from unavoidable latency, which leads to a violation of the real-time constraints and thus to perception perturbations. If the reproduction system suffers from unavoidable latency, compensation algorithms have to be used. In order to be effective, the compensation must be combined with efforts to minimize the VR system overhead.
This talk presents a comprehensive approach to lower the overall VR system latency by a concurrent device and data processing architecture and its embedding in a generalized interaction concept. Low latency history recording and data exchange for multi-modal data types are among the key concepts of the approach. The architecture is presented in the context of the "Virtueller Kopfhörer" system, which is a representative of a demanding multi-modal environment that was developed as a joint research project between the Institute of Technical Acoustics and the VR Group at RWTH Aachen University. The reproduction environment is discussed with respect to its interface and latency as a distributed architecture. An adaptive tracking approach is presented for latency compensation. Finally, event-interleaved master/slave rendering is outlined as a low latency data- and swap-locking approach for CAVE-rendering based on commodity PC clusters. (23.01.2009, dfi)
Dipl.-Inform. Alexander Nyßen
Aufgrund eines erhöhten Abstraktionsniveaus und eines gesteigerten Automatisierungspotentials erscheint gerade die modellbasierte Software-Entwicklung (MBSE) als ein adäquates Mittel, um die Komplexität von Software zu beherrschen. Insbesondere bei der Entwicklung eingebetteter Echtzeitsysteme bietet eine modellbasierte Herangehensweise deutliche Vorteile gegenüber traditionellen Ansätzen, was sich an der zunehmenden Verbreitung modellbasierter Ansätze im Automobilbau, in der Luft- und Raumfahrt oder in der Telekommunikation ablesen lässt. Insbesondere bei der Entwicklung kleiner eingebetteter Echtzeitsysteme, wie sie abseits dieser Kernsparten zu finden sind, ist eine Anwendung modellbasierter Ansätze aber bislang nicht zu beobachten. Dies kann darauf zurückgeführt werden, dass bisher veröffentlichte modellbasierte Ansätze den dort anzutreffenden spezifischen technischen und organisatorischen Rahmenbedingungen nicht ausreichend Beachtung schenken.
In diesem Vortrag wird ein modellbasierter Ansatz speziell für die Software-Entwicklung kleiner eingebetteter Echtzeitsysteme vorstellt. MeDUSA, eine modellbasierte Software-Konstruktionsmethode, und ViPER, eine UML-basierte Entwicklungsumgebung mit spezifischer methodischer Unterstützung für MeDUSA, bilden die beiden Kernbestandteile dieses Ansatzes, ihre Vorstellung somit den Kern des Vortrags. Dabei werden die auf die technischen und organisatorischen Rahmenbedingungen zugeschnittenen Besonderheiten des Ansatzes, insbesondere die zu seiner Charakterisierung als Methodologie führende enge Kopplung von Methode und Werkzeug, motiviert und anhand ausgewählter Details demonstriert. Der Vortrag wird abgeschlossen mit der Präsentation ausgewählter Evaluierungsergebnisse sowie mit einer Bewertung des entwickelten Ansatzes. (14.01.2009, tga)
Prof. Dr.-Ing. M. J. Hampe, Verfahrenstechnik, TU Darmstadt
Auswahl von Studienbewerbern im Fachbereich Maschinenbau an der Technischen Universität Darmstadt
Der Fachbereich Maschinenbau führt seit drei Jahren Auswahlgespräche mit seinen Studienbewerbern durch. Ziel der Gespräche ist es, nur geeignete Bewerber zum Studium zuzulassen und sie früh und eng an den Fachbereich zu binden. Das Gespräch ist als halbstrukturiertes Interview konzipiert und wird von zwei Professoren und einem das Protokoll führenden Beisitzer mit jeweils einem Bewerber eine halbe Stunde lang geführt. In dem Gespräch sollen die Motivation des Bewerbers für Studium und Fach, aber auch Persönlichkeitsmerkmale offengelegt werden. Die Leistungen aus dem Abiturzeugnis gehen zu 60 % und die Auswertung des Gesprächs zu 40 % in eine Endnote ein, die über die Zulassung zum Studium entscheidet. Die Bewerber erfahren unmittelbar nach dem Gespräch, ob sie einen Studienplatz erhalten. Im Vortrag werden die Fragenkomplexe des halbstrukturierten Interviews und das Bewertungsschema vorgestellt.
Prof. Dr. K. Weihe, Fachbereich Informatik, TU Darmstadt
Jedem Studieninteressierten eine faire Chance
Der Fachbereich Informatik der TU Darmstadt hat sich aus verschiedenen Gründen gegen ein Auswahlverfahren für den Bachelorstudiengang entschieden, die formalen Voraussetzungen (z.B. Abitur) reichen aus für die Zulassung. Statt dessen haben wir unsere Bemühungen um Beratung von Studieninteressierten im Vorfeld intensiviert und insbesondere 2006 ein studentisches Intensiv- Mentorensystem im ersten Fachsemester eingerichtet, in dem jeder Erstsemester im wöchentlichen Turnus unter vier Augen von einem erfahrenen älteren Studierenden betreut wird. Der Vortrag erläutert die Gründe für diese Entscheidung, das Konzept dieses Betreuungssystems und unsere Erfahrungen. (12.01.2009, tga)
Prof. Dr. Alfons Kemper, Ph.D., TU München
Information und Informationsverarbeitung gehören mittlerweile zu den wichtigsten Faktoren wirtschaftlichen und wissenschaftlichen Erfolges. Gleichzeitig wollen Unternehmen und Forschungsorganisationen diesen Bedarf möglichst kosteneffizient befriedigen – in Zeiten des Cloud-Computings am besten als einen extern verwalteten Service. Im ersten Teil dieses Vortrags werden Datenbanksystem-Erweiterungen für die Mandanten- oder Multi-Tenancy-Fähigkeit untersucht. Insbesondere geht es darum, erweiterbare Datenmodelle vieler Mandanten (Tenants) auf ein Datenbanksystem zu konsolidieren, um dadurch die Betriebskosten zu reduzieren. Es werden mehrere Schemaabbildungstechniken für relationale Datenbanksysteme vorgestellt und deren Leistungsfähigkeit wird verglichen. Im zweiten Teil des Vortrags geht es um Quality-of-Service für Datenbankdienste. In Multi-Tenancy-Anwendungen ist die Selbstadministration der Software/Hardware-Infrastruktur eine wichtige Voraussetzung, um hochwertige Datenbankdienste in einem Cloud-Computing-Ansatz garantieren zu können. Den Benutzern werden in Service Level Agreements (SLAs) bestimmte Quality of Service-Garantien zugesichert, deren Erfüllung kontinuierlich überwacht wird. Gerade das Datenbanksystem stellt aber vielfach die Achillesverse in einer derartigen Architektur dar, da letztendlich fast alle Services darauf zugreifen, um ihre Zustände dauerhaft zu verwalten. (12.01.2009, tga)
Prof. Nikos Mamoulis, Ph.D., University of Hong Kong
In this talk, I will discuss our research on evaluation of large-scale matching problems. Given two sets of objects (e.g., a set of cars and a set of parking slots) the goal is to find a one-to-one matching which satisfies a condition (e.g., stable-marriage property) or maximizes an objective function (e.g., number of cars in matching, sum of distances between cars and parking slots in the matching). Matching problems are found in many applications including assigning cars to parking slots, students to schools, customers of a booking service to hotel rooms, police cars to emergency incidents, mobile devices to WiFi routers, applicants to jobs, university applicants to degree programmes, etc. Although polynomial algorithms have been developed for matching problems considering a wide range of objectives, they all suffer from large space and time requirements. Specifially, all these methods have at least quadratic time and space complexity, a fact that makes them inapplicable for inputs in the order of millions. On the other hand, it is not uncommon to find real-life problems of that magnitude. Our goal is to develop scalable algorithms for matching problems, which are applicable to large-scale inputs. Our methodology is based on the use of indexing methods to guide search and the development of geometric search techniques that can derive bounds for the objective function helping towards finding a solution without exploring the whole space. Recently, we have done some work in this direction for one-to-one and many-to-one matching problems where the objective function is parametric to the spatial distance between the matched pairs. Our solutions apply for instance to the problem of finding a matching between cars and parking slots that minimizes the total distance between pairs in the assignment. Other extensions currently being studied is updating the matching for dynamic data, the incorporation of additional constraints in the problems (e.g., a car may not be assigned to a very remote slot), and the study of alternative objective functions based on personalized ranking (e.g., users assigned to services like hotel rooms based on their personal preferences). (09.01.2009, tga)
Dipl.-Inform. Heiner Ackermann
Congestion-Spiele sind ein spieltheoretischer Ansatz zur Modellierung von Szenarien, in denen Agenten kosten- bzw. latenzminimale Teilmengen von Ressourcen belegen. Solche Mengen können z.B. Pfaden in einem Netzwerk entsprechen. Ein anerkanntes Lösungskonzept für solche Spiele sind Nash-Gleichgewichte, in denen kein Agent seine individuellen Kosten durch einen alleinigen Strategiewechsel verringern kann.
In diesem Vortrag betrachten wir zwei verschiedenen Arten von Verbesserungsdynamiken hinsichtlich der Anzahl an Schritten, bis diese in einem Nash-Gleichgewicht terminieren. Im Falle von sequentiellen Best-Response-Dynamiken untersuchen wir den Einfluss der kombinatorischen Strukturen der Strategieräume auf die Konvergenzzeit. Anschließend motivieren und diskutieren wir parallele Verbesserungsdynamiken, in denen Spieler die Strategien erfolgreicher Konkurrenten imitieren. Wir zeigen, unter welchen einschränkenden Annahmen solche Dynamiken schnell zu einem approximativen Gleichgewicht gelangen.
Abschließend diskutieren wir Erweiterungen des ursprünglichen Congestion-Spiel-Modells und präsentieren einige Ergebnisse bezüglich der Existenz von und der Konvergenz zu Nash-Gleichgewichten in diesen Erweiterungen. (16.12.2008, tga)
Dipl.-Inform. Alexander Hornung
Image- and video-based methods for photo-realistic image synthesis or surface reconstruction have received a considerable amount of attention in recent computer vision and graphics research. In our work we have investigated three representative problems of this spectrum of techniques: character reconstruction and animation as an example of image and video editing, a method for accurate 3D model reconstruction, and a technique for interactive free viewpoint rendering. This presentation will focus on the first two techniques.
In the first part of the presentation a new approach for creating animated characters from images and captured human motion data will be presented. The challenge addressed here is the development of a single representation that is able to cover a variety of character types and inputs. Based on a generic character shape template we propose new techniques for the problems of camera estimation, shape deformation and tracking, and character reconstruction. The results are complex animations from diverse input sources such as single images or uncalibrated video of moving subjects.
The second part will concentrate on accurate 3D object reconstruction. A new solution to the problems of multi-view stereo and point cloud reconstruction is presented which is able to compute 3D surface models at a high accuracy while at the same time being robust to degeneracies in the input data. This is achieved by a new volumetric approach for extracting the object surface from a surface confidence map using globally optimal graph cuts. Due to the use of efficient hierarchical and GPU-based techniques our approach achieves a high computational performance and allows for 3D model reconstructions of considerable quality. (16.12.2008, tga)
Dipl.-Inf. Jan Peter Schneider-Kamp
The most fundamental decision problem in computer science is the halting problem, i.e., given a description of a program and an input, decide whether the program terminates after finitely many steps or runs forever on that input. While Turing showed this problem to be undecidable in general, developing static analysis techniques that can automatically prove termination for many pairs of programs and inputs is of great practical interest.
This is true in particular for logic programming, as the inherent lack of direction in the computation virtually guarantees that any non-trivial program terminates only for certain classes of inputs.
In this talk, we show that techniques developed for proving termination of term rewriting can successfully be applied to analyze logic programs. The new techniques developed significantly extend the applicability and the power of automated termination analysis for logic programs.
In particular, we present a new pre-processing approach to transform logic programs with cuts into cut-free logic programs. Then, a new transformations from logic programs to a specialized version of term rewriting makes it possible to reuse techniques developed for termination analysis of term rewriting. We also show how to search for certain popular classes of well-founded orders on terms more efficiently by encoding the search into satisfiability problems of propositional logic. The contributions presented in this talk are implemented in our fully automated termination prover AProVE. The significance of our results is demonstrated by the fact that AProve has reached the highest score both for term rewriting and logic programming at the annual international Termination Competitions in 2004, 2005, 2006, 2007, and 2008. In this competition, the leading automated tools try to analyze termination of programs from different areas of computer science. (01.12.2008, dfi)
Dr. Kai Jakobs
RWTH Aachen
By now, the importance of standards has been widely recognised. This holds particularly for the ICT sector, where primarily compatibility standards are a sine-qua-non. Yet, as a document published by the European Commission's rightly oberves, "Standards are not only technical questions. They determine the technology that will implement the Information Society, and consequently the way in which industry, users, consumers and administrations will benefit from it". They also have a strong economic dimension - interested parties can use them to shape, or even create, markets. And standards can be, and in fact are, used by policy makers as regulatory tools.
However, for all their importance and impact dimensions, comparably little is known about the many questions that surround both the process of standardisation and its outcome. This presentation will address some of these questions.
Looking at the level of actual standards making, a very popular view has it that all stakeholders are represented and have an equal say in the process. This view, as well as widely held perceptions about the role of user companies, will be critically analysed. Also, an aspect that is frequently overlooked will be addressed - the role of the individual in the standards setting process.
To be technically relevant, standards should at least represent the technical state-of-the-art, and ideally move beyond it. To this end, active contributions from the research community would be crucial. However, researchers and academics tend to be conspicuously absent from the process. Some options how this situation could be improved will be identified and discussed.
Specifically in the ICT sector, standards are developed by an almost impenetrable maze of Standards Setting Bodies. Their activities may overlap; they may complement, or compete with, each other. As a consequence, companies that either wish to actively contribute to standards setting, or that have to implement standards for a certain functionality, need to identify the SSB(s) whose activities best suit their needs, and which (of potentially competing) standards to pick, respectively. At least in Europe, policy makers still consider standards consortia's (e.g., the W3C; also the IETF) products inferior to those of the 'formal', 'accredited' bodies (like, e.g., ISO or ETSI). Whether or not this is a sustainable view, and which other factors might play a more important role than 'accreditation' does, will also be discussed. (25.11.2008, dfi)
Prof. Dr. Michael Codish
Ben-Gurion University, Beer-Sheva, Israel
Size change graphs provide an abstract mathematical representation which describes how the size of "the data" changes in the transitions made by a given program. Size change graphs provide also a basis to reason about the termination of the programs they describe.
I will present two techniques to prove termination based on size change graphs: the more standard "global approach" and the more interesting "local approach". I will show the correctness result for the local approach which applies Ramsey's Theorem. I will also show a completeness result which states that for a given set of size change graphs, if there exists any proof of termination then there exists one of a very simple form. Here hides one main advantage of the local approach: Size change termination is decidable and easy to automate.
Deeper hiding is also the main pitfall: proofs of termination in the local approach may introduce an exponential number of graphs which must be considered. To counter this problem I will come back to the global approach and illustrate a new approach to proving termination with size change graphs. This is the first decision procedure for size change termination (SCT) which makes direct use of global ranking functions. It handles a well-defined and significant subset of SCT instances, designed to be amenable to a SAT-based solution. We have implemented the approach using a state-of-the-art Boolean satisfaction solver. Experimentation indicates that the approach is a viable alternative to the complete SCT decision procedure based on local ranking functions. (25.11.2008, dfi)
Dr. Christof Löding
RWTH Aachen
In der Verifikation treten häufig Systeme auf, die durch die Verwendung von unbeschränkten Datenstrukturen oder Rekursion prinzipiell unendlich sind. Für rekursive Programme mit Variablen über endlichen Datentypen ist es möglich, Techniken zur Verifikation von endlichen Systemen zu übertragen. Die Grundlage hierfür bilden Algorithmen für Pushdown-Systeme, die zur Modellierung von Rekursion verwendet werden können. Für solche Systeme sind auch nicht-reguläre Spezifikationen interessant, wie zum Beispiel Vor- und Nachbedingungen für Prozeduren. In den letzten Jahren sind, aufbauend auf Arbeiten von Alur, Etessami und Madhusudan, Methoden entwickelt worden, die es erlauben, kontextfreie Spezifikationen dieser Art algorithmisch zu überprüfen. In dem Vortrag geben wir einen Überblick über diese Methoden und stellen einige neue Entscheidbarkeitsresultate zu unendlichen Spielen und zu einer nicht-regulären Erweiterung der Logik PDL vor. (25.11.2008, dfi)
Dipl.-Inform. Thomas Deselaers
In this thesis, we present approaches to image retrieval, object recognition, and discriminative models. For image retrieval, we evaluate a large variety of different descriptors and answer the questions how descriptors can be combined and which descriptor should be chosen according to which criterion. We suggest a set of local descriptors that have been used successfully for object recognition and combine these with textual information and several other descriptors. Additionally, we present methods to optimally fuse visual and textual data for retrieval. For object recognition, we propose different models and investigate and analyse their relationships and their individual advantages and disadvantages. In particular, we try to avoid heuristics in the creation of the models and incorporate all available knowledge cues. We extend the bag-of-visual words approach into several directions in order to overcome its limitations. In total, we present eight different models for object recognition including a nearest neighbour-based model, two variants of bag-of-visual-words models, and a model based on geometric matching incorporating spatial relationships. We also present a model based on Gaussian mixtures which abandons vector quantisation, can be trained discriminatively, and can incorporate spatial relationships. This model is then rewritten and extended toward log-linear mixtures and support vector machines. We also present a random-forest-based approach that fuses appearance, shape, and depth cues for human computer interaction. Regarding discriminative models, we delve deeper into some aspects of image retrieval and object recognition. We propose a novel model for optical character recognition. We extend log-linear models to incorporate hidden variables, thus allowing for modelling image deformations and multi-modal data. Furthermore, we investigate the relationship between certain support vector machines and Gaussian mixtures in order to achieve a joint model that fuses their advantages. All approaches proposed in this work were evaluated on standard benchmarks. For image retrieval, we experimentally evaluated the performance of a large variety of descriptors, how they perform on different tasks, and how they can be combined to achieve different results. We participated in several Image-CLEF evaluations and obtained excellent results using content-based image retrieval techniques. In particular, we achieved the best result using visual retrieval in the Image-CLEF 2007 medical retrieval task using our discriminatively trained feature combination. The object recognition approaches were evaluated on the Caltech and PASCAL tasks and it could be shown that Gaussian mixtures and related approaches incorporating spatial information and avoiding vector quantisation outperform all other approaches. The methods proposed in the chapter on discriminative models were evaluated on the standard USPS and MNIST tasks and our deformation-aware log-linear model achieves very competitive results while using an order of magnitude fewer parameters than competing approaches. The talk will mainly focus on the parts about object recognition and discriminative models. (25.11.2008, dfi)