next up previous contents
Next: 4 Veröffentlichungen Up: Tätigkeitsbericht 2000 Previous: 2 Drittmittel

Subsections

3 Darstellung der Forschungsvorhaben

3.1 Projekte

``Komplexität, Information, Redundanz und Neuronale Netze''

(Antragsteller: Brauer , Schmidhuber (LMU) ; Mitarbeiter: Hochreiter )

Aufgrund der äußerst erfolgreichen und mit sehr großer Resonanz aufgenommenen Resultate aus den Punkten (1a) und (1c) des Erstantrags, stehen diese Punkte im Mittelpunkt des Folgeantrags. Die Untersuchungen zu diesen Punkten konnten wegen zeitlichen und personellen Beschränkungen nicht abgeschlossen werden und ein Test an praxisnahen Datensätzen steht noch aus. Diese Untersuchungen und Tests sind jedoch notwendig, um kommerzielle Anwendungen zu ermöglichen. Algorithmen, entwickelt in diesen beiden Punkten, lösten erstmals künstliche Aufgabenstellungen, die bislang nicht gelöst werden konnten. Die Erprobung der entwickelten Algorithmen an Echtweltdaten und die Umsetzung der Ideen aus dem ersten Teil des Vorhabens wurde von anderen Forschern und Anwendern aus der Praxis gefordert. Dies soll im Folgeantrag geleistet werden. Zwei Punkte des Erstantrags sollen weiter untersucht werden: Sequenzkompression und Merkmalextraktion. Bei beiden Punkten sollen ausgehend von den theoretischen Untersuchungen und entwickelten Algorithmen aus dem ersten Teil des Vorhabens Algorithmen verbessert und getestet und neue abgeleitet werden.


``Qualitative Repräsentation von Bewegungsverläufen: Kognitive und Psychophysische Grundlagen'' , Projekt BR 609/9-2 im DFG-Schwerpunktprogramm ``Raumkognition''.

(Antragsteller: Brauer , Schill (LMU) ; Mitarbeiter: Musto , Röhrbein (LMU)
in Zusamenarbeit mit Stein , Graduiertenkolleg Kooperation und Ressourcenmanagement in verteilten Systemen)

In dem insgesamt auf 6 Jahre ausgelegten Projekt sollen in interdisziplinärer Zusammenarbeit Aussagen über die Repräsentation und Verarbeitung von Bewegungsverläufen sowie ihrer Prädiktion gewonnen werden. Hierzu werden zum einen psychophysische Untersuchungen auf Basis eines spatio-temporales Gedächtnismodells durchgeführt, um ein Verständnis für die Verarbeitung von sich örtlich-zeitlich ändernden Situationen zu gewinnen. Auf der anderen Seite werden Algorithmen und Verfahren entwickelt, um Bewegungsspuren auf numerischer wie symbolischer Ebene weiterzuverarbeiten, zu vergleichen, zu generalisieren, zu matchen und vorherzusagen. Die entwickelte Repräsentation soll nicht nur kognitive Prozesse erklären, sondern auch für Anwendungen geeignet sein, z.B. in der Robotik (Bewegungsplanung), Verkehrsüberwachung oder Indizierung von Bildfolgen in Multimediadatenbanken. Bei einer Kooperation mit dem Bremer Robotikprojekt ``Bildfolgenbasierte semilokale 3D Landmarken zur Navigation in dynamischen Umgebungen'' wurden die entwickelten Repräsentationen und Algorithmen zur Navigation mittels aufgezeichneter Eigenbewegung sowie zur Navigation mittels grober qualitativer Routenbeschreibungen eingesetzt.


``Konfliktbewältigung und Strukturwandel: Gesellschaftstheorie als Bauanleitung für lernfähige Mehragentensysteme''

(Antragsteller: Brauer , Malsch (TU Hamburg/Harburg), Weiß ; Teilnehmer: Brauer , Weiß , Brandt , Nickles , Rovatsos )

Die primären Ziele des im Rahmen des SPP ``Sozionik'' von der DFG geförderten Projekts ``Konfliktbewältigung und Strukturwandel: Gesellschaftstheorie als Bauanleitung für lernfähige Mehragentensysteme'' (ConStruct) sind die Verbesserung des Design-Prozesses und der Effizienz von Multiagenten-Systemen mit Hilfe soziologisch fundierter Modelle, und die Konstruktion neuartiger Architekturen für sehr große, lernfähige ``künstliche Gesellschaften'' nach dem Vorbild der menschlichen Gesellschaft. Um dies zu erreichen, verbinden wir VKI-Konzepte für Lernen und Konfliktbewältigung in MAS mit soziologischen Konzepten für die Beschreibung von Strukturwandel und Konflikten. Mit diesem Ansatz wollen wir insbesondere auch neue Design- und Programmier-Methoden auf dem zunehmend an Bedeutung gewinnenden Gebiet des Agenten-orientierten Software- Engineering (AOSE) beitragen. In enger interdisziplinärer Zusammenarbeit entwickeln wir gegenwärtig zwei unterschiedliche Architekturen, die sich aus zwei konkurrierenden soziologischen Paradigmen ergeben: (1) Pragmatismus und symbolischer Interaktionismus, und (2) Niklas Luhmanns Theorie sozialer Systeme. Aus diesen gegensätzlichen Ansätzen bei der Betrachtung der Wechselbeziehung von Konflikten und Sozialstrukturen leiten wir zwei konkurrierende Modelle für künstliche Sozialität ab: (1) ein Modell selbstbestimmten Wandels durch die kreative Bewältigung von Handlungskonflikten und (2) ein Modell ``evolutionärer Differenzierung sozialer Systeme als Differenzierung von Konflikten'' (Luhmann). Beide Modelle bzw. die darauf basierenden Architekturen werden anhand von realitätsnahen Anwendungsszenarien konkretisiert und bewertet. Systeme für das semantische Rating von Websites durch konkurrierende Agenten und die Agenten-gestützte Verlinkung von Webseiten wurden bereits spezifiziert und werden gegenwärtig praktisch umgesetzt.
Finanzierung: DFG-Projekt BR 609/11-1: ``Konfliktbewältigung und Strukturwandel: Gesellschaftstheorie als Bauanleitung für lernfähige Mehragentensysteme'', DFG-Schwerpunktprogramm ``Sozionik'' .
Zusammenarbeit mit: TU Hamburg/Harburg (Prof. Thomas Malsch , Kai Lorentzen, Kai Paetow)


``Mobile Systeme und Systeme höherer Ordnung''
(Teilnehmer: Esparza , König , Röckl )

Mobile Systeme sind verteilte Systeme mit Zustandsvariabilität, die in der Lage sind, ihre Kommunikationsstruktur während der Laufzeit dynamisch zu verändern. Dies wird dadurch erreicht, daß sie Port-Adressen oder ganze Prozesse verschicken und empfangen können. Mobilität bietet neue Möglichkeiten für die Spezifikation von verteilten Systemen, bringt aber auch neue Herausforderungen mit sich, insbesondere, was die Verifikation von mobilen Prozessen und Prozessen höherer Ordnung angeht. Ein prominenter Vertreter mobiler Prozeßkalküle ist der pi-Kalkül.

In diesem Bereich sind wir einerseits an vollständigen, semi-automatischen Techniken interessiert, die es ermöglichen Bisimularität mit Hilfe des Theorembeweisers Isabelle/HOL zu zeigen.

Andererseits beschäftigen wir uns mit Verfahren zur statischen Analyse, die auf (generischen) Typsystemen basieren. Diese Methoden werden sowohl für die Analyse von Prozeßkalkülen, als auch von Graphersetzungssystemen eingesetzt.
Finanzierung: Sonderforschungsbereichs 342 ``Werkzeuge und Methoden für die Nutzung paralleler Rechnerarchitekturen'', DAAD-Projekt ``Verifikationstechniken für imperative parallele Sprachen höherer Ordnung'' mit INRIA Sophia Antipolis, ESPRIT TMR Research Network: GETGRATS ``General Theory of Graph Transformation Systems''.
Zusammenarbeit mit: INRIA Sophia Antipolis (Dr. Davide Sangiorgi, Dr. Gérard Boudol), Universität Pisa (Ugo Montanari, Andrea Corradini).

3.2 Weitere Forschungsvorhaben

Bartmann
Identifikation eines Tastaturbenutzers durch Analyse des Tippverhaltens
Dieses Projekt beschäftigt sich mit einem neuartigen Authentifikationssystem, das auf dem psychometrischen Merkmal ``Tippverhalten'' basiert. Durch Analyse von Schreibrhythmus, Anschlagfolge und anderen Aspekten des Tippverhaltens soll es damit möglich sein, auf Grund eines ca. 100 Zeichen langen, beliebigen Eingabestrings, eine Person mit Hilfe gewöhlicher Hardware zu identifizieren. Dazu werden klassische statistische Verfahren mit Methoden aus dem Bereich der KI kombiniert. Das Einsatzgebiet reicht von der einmaligen Identifikation bei der Zutrittskontrolle über elektronische Unterschrift und Textautorisierung bis hin zur ständigen Identitätsüberwachung im laufenden System.


Brauer , Brandt , Weiß
Automatisierte Auktionsverfahren
Weiterentwicklung der bereits durchgeführten Arbeiten zu auktionsbasierten Verteilungsstrategien (English, Dutch und Vickrey) mit variabler Vertragsbindung (Vertragsauflösung durch Strafe). Detaillierte Analyse der Vickrey Auktion, insbesondere der Möglichkeit den Profit fremder Agenten zu minimieren.


Brauer , Weiß
Lernen und Planen in Multiagentensystemen
Entwicklung und Untersuchung von hybriden Lern- und Planungsverfahren für Multiagentensysteme, wobei der Schwerpunkt auf der Zusammenführung von reaktiven und deliberativen Problemlösungsstrategien lag.


Brauer , Weiß , Nickles , Rovatsos
Agentenorientiertes Software Engineering
Ausgehend von einer Evaluierung des Forschungs- und Anwendungsstandes beim Engineering von agentenorientierter Software soll untersucht werden, inwieweit soziologische Konzepte der Systemtheorie und des Pragmatismus für die Analyse und das Design solcher Software nützlich ist.


Gilsdorf
Optimierung von Routingalgorithmen in Telekommunikationsnetzen mit Hilfe von Fuzzy Logik und Neuronalen Netzen
Die Bedeutung von Telekommunikations Netzen hat in den letzten Jahren stark zugenommen. Öffentliche und privatwirtschaftliche Abhängigkeit von diesen Netzen verlangt von ihnen eine hohe Verfügbarkeit und große Zuverlässigkeit. Andererseits zwingt der Wettbewerb die Betreiber zur maximalen Ausnutzung ihrer Netze. Die Zeitspanne für die Schaltaktionen in den Festnetzen wird immer kürzer. Wird die Routenauswahl nicht auf die richtige Weise getroffen, so wird die Qualität der Netze sehr schnell vermindert. Die Kombination von Fuzzy Logik und Neuronalen Netzen bietet eine ausgezeichnete Möglichkeit die unterschiedlichen Aspekte zu berücksichtigen, die bei der Bewertung eine Rolle spielen. Es werden verschiedene Architekturen untersucht um die automatische Routenauswahl in Festnetzen so zu gestalten, dass die Qualität des Festnetzes erhalten bleibt. Es wurde nachgewiesen, dass eine reine Fuzzy Logik Lösung, eine erfolgreiche Methode ist die Kanten in einem Festnetz zu bewerten. Durch die Transformation der Fuzzy Regelbasis in ein neuronales Netz, wurde das System erfolgreich um die Lernfähigkeit erweitert.

Diese Arbeit wird von der Firma SBS unterstützt.


Holzer
Die auf der Konferenz ,,Computational Complexity 2000`` vorgestellten Ergebnisse zur Komplexität des Tensorkalküls basierend auf Formeln konnten auf Schaltkreise erweitert werden. Hierzu mußten neue Methoden, die speziell für Schaltkreise geeignet sind, erarbeitet werden. Die erzielten Komplexitätsresultate erlauben es, viele Klassen zwischen NP und EXPTIME durch geeignete Tensorprobleme zu charakterisieren. Die Ergebnisse wurden zur Veröffentlichung angenommen.
Zusammenarbeit mit: Beaudry (Uni Sherbrooke), Damm (Uni Göttingen), McKenzie (Uni Montréal)

Holzer
Basierend auf Wortersetzungssystemen wurde eine Sprachhierarchie im Sinne von McNaughton untersucht. Neben Inklusionsstruktur und Abschlußeigenschaften wurden auch Komplexitätstheoretische Untersuchungen zum Wortproblem durchgeführt. Es zeigt sich, daß diese bisher unbeachtete Hierarchie in gewissen Bereichen eine Alternative zur bekannten Chomsky Hierarchie darstellt. Die Ergebnisse wurden zur Veröffentlichung eingereicht.
Zusammenarbeit mit: Beaudry (Uni Sherbrooke), Niemann (Uni Kassel), Otto (Uni Kassel)


Holzer
Es wurden Untersuchungen über den Einfluß der Anzahl der Startzustände auf die Zustandskomplexität bei deterministischen endlichen Automaten durchgeführt. So zeigte sich z.B., daß sich durch  k viele Anfangszustände bis zu O(n k) Zustände sparen lassen; die erzielten Schranken wurden als scharf nachgewiesen. Neben dem Vorteil der Zustandseinsparung gesellt sich der Nachteil der PSPACE-Vollständigkeit der Minimierung deterministischer endlicher Automaten mit mehreren Anfangszuständen. Die Ergebnisse wurden zur Veröffentlichung angenommen.
Zusammenarbeit mit: Salomaa (Queens Uni), Yu (Uni Western Ontario)


Kiehn
Intelligente Agenten und Multiagentensysteme

Die Untersuchungen zur formalen Semantik von Multiagentensystemen wurden fortgesetzt. Besonders studiert wurden auch Querbezüge zu anderen Disziplinen wie der Psychologie (erweiterte Intelligenzbegriffe), der Neurobiologie (neue Erkenntnisse aus bildgebenden Verfahren), der Philosophie (Leib-Seele-Problem) und der Sozionik.


König
Methoden zur Modellierung und Analyse von mobilen Prozessen

Mobile Prozesse können während ihrer Laufzeit ihre Kommunikationsstruktur verändern, indem sie beispielsweise Adressen oder sogar ganze Prozesse verschicken.

Neben der Möglichkeit, Prozesse durch eine lineare Syntax (wie z.B. im pi-Kalkül) zu modellieren, kann man Prozesse auch durch Graphen beschreiben, wobei die operationelle Semantik durch Graphtransformationen gegeben wird. Es wurde ein solcher Kalkül entwickelt und untersucht, wie man ihn zur Analyse von Prozessen einsetzen kann.

Für Prozeßgraphen kann man besonders elegant Typsysteme angeben, mit denen man bestimmte Eigenschaften von Prozessen - insbesondere solche, die mit der Struktur des Prozesses zu tun haben - analysieren kann. Dabei ist es auch möglich generische Typsysteme zu entwickeln, die - geeignet instanziiert - verschiedene Eigenschaften analysieren können und nicht auf bestimmte Eigenschaften festgelegt sind. Solche generische Typsysteme kann man - unabhängig von Graphen - auch für klassische Kalküle, wie z.B. den pi-Kalkül angeben.


Pompl
MELDOQ

(http://www.imse.med.tu-muenchen.de/mi/derma/index.html)
In den letzten Jahrzehnten wurde eine stark steigende Neuerkrankungsrate des malignen Melanoms der Haut (``schwarzer Hautkrebs'') beobachtet. Bei frühzeitiger Erkennung bestehen für den Patienten gute Heilungschancen. Allerdings ist die korrekte Diagnose in frühen Phasen selbst für erfahrene Dermatologen nicht immer einfach. Daher wurde, gefördert durch das DLR, im interdisziplinären Projekt MELDOQ (http://www.imse.med.tu-muenchen.de/mi/derma/index.html) ein System entwickelt, das den Dermatologen bei der Diagnosefindung unterstützen soll. Dabei wird eine verdächtige Hautveränderung mit der Technik der Dermatoskopie digital aufgenommen und patientenbezogen archiviert. Kern des Systems ist die quantitative Charakterisierung von Objektmerkmalen und die Zusammenfassung der Einzelergebnisse  zu einem Diagnosevorschlag. Dabei konnte eine Klassifikationsrate von über 90% erreicht werden. Die Merkmalscharakterisierungen können am Objekt visualisiert werden, so daß der Dermatologe den Diagnosevorschlag nachvollziehen kann. Im Rahmen des Technologietransfers wird das System mittlerweile von der Firma Rodenstock Präzisionsoptik kommerziell angeboten.


Röckl
Beweiserunterstützte Verifikation von Prozeßäquivalenzen
Es wurde eine Beweis- und Analyseumgebung für den Pi-Kalkül in Isabelle/HOL entwickelt und formalisiert, auf der Basis der im letzten Tätigkeitsbericht beschriebenen Vorarbeiten. Die Umgebung erlaubt sowohl die syntaktische und semantische Analyse des Pi-Kalkül als auch die Implementierung von Semantiken und aufbauend die Arbeit mit Prozeßäquivalenzen.

Ein wesentlicher Bestandteil der Arbeit war die mechanisierte Validierung der ``Theory of Contexts'' für den Pi-Kalkül, eine größere Fallstudie zur Syntaxanalyse in Syntax höherer Ordnung. Die nötigen Prinzipien zur strukturellen Induktion wurden dabei durch Regelinduktion über geeigneten Wohlgeformtheitsprädikaten modelliert.


Römer
Entwicklung und Implementierung von Verifikationstechniken auf der Basis von Netzentfaltungen

Themengebiete dieses Forschungsbereichs sind die Entwicklung und Umsetzung effizienter Datenstrukturen und Algorithmen zur Darstellung und Manipulation von Petrinetzen. Schwerpunkt der Arbeiten bilden Model-Checking-Verfahren zur Verifikation nebenläufiger Systeme mit Hilfe von Netzentfaltungen. Es werden Implementierungen und Optimierungen rechenzeitkritischer Programmprototypen vorgenommen, sowie deren Einbindung in das Analysewerkzeug PEP (Programming Environment based on Petri nets).



Runkler
Information Mining

Information Mining umfaßt den Prozess der Extraktion von ,,Wissen`` aus großen Datenmengen. Zu den wichtigsten Datenquellen gehören industrielle Prozess- und Netzwerksysteme sowie betriebswirtschaftliche Datenbanken, die meist rein numerische Daten enthalten. Zur Extraktion relevanter Informationen aus solchen numerischen Datensätzen werden (neben konventionellen statistischen Verfahren wie Korrelation und Regression) Methoden der Clusteranalyse, Fuzzy-Logik, Neuroinformatik und Machine Learning angewandt. Insbesondere die alternierende Clusterschätzung hat sich als universelles Werkzeug zur Datenanalyse etabliert. Durch die wachsende Verbreitung automatischer Bilderfassungssysteme stehen über rein numerische Datensätze hinaus umfangreiche Bild-, Video- und Multimediadaten zur Verfügung. Durch die zunehmende Nutzung von E-Mail und Internet spielen nicht zuletzt auch Textdaten eine immer größere Rolle. Für die Analyse solcher nichtnumerischer Daten wurden relationale und merkmalsorientierte Algorithmen entwickelt. Die genannten Methoden haben sich in realen Anwendungsprojekte aus Prozeßtechnik, Netzwerktechnik, Bildverarbeitung und Marketing bewährt.


Schröter
Reduktionstechniken für entfaltungsbasierte LTL Model-Checking-Verfahren
Entfaltungsbasierte Verifikationsverfahren unterliegen der Problematik, daß die Größe der Entfaltung exponentiell in der Größe des Ausgangssystems wächst. Um die Entfaltungen möglichst klein zu halten, wurde für ein von Esparza und Heljanko entwickeltes LTL Model-Checking-Verfahren untersucht, inwieweit das Ausgangssystem vereinfacht werden kann, ohne daß für das Model-Checking-Verfahren notwendige Informationen verloren gehen. Dazu wurden verschiedene Reduktionsregeln entworfen und implementiert.


Stein (Graduiertenkolleg ``Kooperation und Ressourcenmanagement in verteilten Systemen'')
Qualitative Raumrepräsentation
Bewegungen von Fahrzeugen, beweglichen Robotern aber auch Menschen und Tieren können in Form von Trajektorien (also Spuren oder Routen) beschrieben werden. Autonome Fahrzeuge können anhand vorgegebener Routen navigieren und die selbstgefahrenen Wege zum Aufbau einer ,,Landkarte`` benutzen. Hierzu müssen die Routeninformationen mehrfach bearbeitet werden: Die gemessenen Routen werden geglättet (generalisiert), verglichen (,,matching``) und segmentiert. Landmarken dienen als Fixpunkte der Navigation und müssen folglich in die Routenbeschreibungen integriert werden. Für eine einfache Interaktion mit dem Benutzer ist eine Umwandlung in eine qualitative Darstellung hilfreich, ebenso wie umgekehrt die Möglichkeit, qualitative Eingaben (Z.B. Wegbeschreibungen) des Benutzers verarbeiten zu können.

Zu diesen Punkten wurden in Zusammenarbeit mit Alexandra Musto und den anderen Mitarbeitern des Projektes Qualitative Repräsentation von Bewegungsverläufen: Kognitive und psychophysische Grundlagen (DFG-Schwerpunktprogramm Raumkognition) bereits Algorithmen (vor allem zur Generalisierung) entwickelt. Der nächste Schitt ist nun die Entwicklung von Matching-Algorithmen und die Nutzung von Landmarkeninformation für Matching und Segmentierung, sowie die Untersuchung der Eigenschaften der unterschiedlichen Algorithmen bei verschiedenen Parametersätzen und in verschiedenen Kontexten.

Da sich die Verarbeitung von Bewegungsdaten für unterschiedliche Referenzrahmen (egozentrisch vs. allozentrisch) vor allem in Hinblick auf Fehlerakkumulation stark unterscheidet, mßsen die Algorithmen gerade in dieser Hinsicht gut untersucht werden, ebenso wie die Frage, inwiefern sich hier Landmarken zur Fehlerkorrektur und -vermeidung einsetzen lassen.


Ungerer
Neuronale Identifikation von Totzeiten
Bei diesem Projekt handelt es sich um ein interdisziplinäres Forschungsvorhaben: es beschäftigt sich mit der Anwendung neuronaler Netze in der Regelungstechnik. Ein schwieriges Problem in der Regelungstechnik stellt der Umgang mit sog. Totzeiten bzw. mit Totzeitsystemen dar. In realen Systemen kommen derartige Totzeiten zahlreich vor, erschweren aber die Systemregelung, da sich Einflüsse auf das System erst zeitverzögert bemerkbar machen. Die Totzeitproblematik wird bisher ungenügend bis gar nicht berücksichtigt. Oft werden im System vorhandene Totzeiten einfach ignoriert, da sie unbekannt sind und nicht identifiziert werden können, und somit wird eine optimale Regelung verhindert. Der in diesem Projekt verfolgte Ansatz ist die Verwendung von speziellen neuronalen Netzen und Lernverfahren zur Identifikation von Totzeiten in nichtlinearen dynamischen Systemen.


next up previous contents
Next: 4 Veröffentlichungen Up: Tätigkeitsbericht 2000 Previous: 2 Drittmittel
Felix Brandt, Mon Jun 25 15:32:09 MET DST 2001