Deutsch <> English
SFB 637  >>  Teilprojekte  >>  Projektbereich A  >  A4

A4 - Modellierung selbststeuernder Logistikprozesse mit Hilfe regelbasierter Graphtransformation

Prof. Dr. Hans-Jörg Kreowski

Universität Bremen
Fachbereich Mathematik/Informatik
Technologie-Zentrum Informatik (TZI)
Arbeitsgruppe Theoretische Informatik
Linzer Str. 9a, 28359 Bremen, Germany
Tel: +49 421 218 64451, Fax: +49 421 218 4322
E-Mail , Homepage
Motivation

Wie in der Softwaretechnik und anderen Gebieten der Informatik werden auch in der Logistik beim Modellieren von Prozessen und Systemen in vielfältiger Weise Diagramme und Graphen verwendet, um komplexe Strukturen zu beschreiben und visuell darzustellen. In der Informatik ist Graphtransformation ein gut untersuchter, integrativer und semantisch fundierter Modellierungs- und Transformationsansatz, der vielfältig eingesetzt wird und sich auch für die Modellierung von Prozess- und Systemabläufen in der Logistik anbietet. Die in der ersten Projektphase eingeführten autonomen Einheiten haben sich für die graphtransformatorische Modellierung selbststeuernder logistischer Prozesse als geeignet erwiesen und bilden daher den Ausgangspunkt weiterer Untersuchungen.

Ergebnisse 1. Phase (2004-2007)

Den Kern der Arbeit in dieser Projektphase bildet das Konzept der autonomen Graphtransformationseinheiten, die in einer gemeinsamen Umgebung unabhängig voneinander interagieren und dabei eigene oder gemeinsame Aufgaben erledigen. Die operationelle Semantik ist in drei Stufen mit wachsender Komplexität definiert: Die einfachste Semantik ist rein sequentiell und erlaubt nur eine Aktion pro Schritt, in der zweiten Stufe können beliebig viele Einheiten beliebig viele ihrer Regeln parallel anwenden, die letzte Stufe ist eine nebenläufige Semantik, in der zeitliche Rechenfolgen nur noch bei kausalen Abhängigkeiten feststellbar sind. Um die Nutzbarkeit dieses Konzepts zu erproben, ist eine Reihe von Fallstudien durchgeführt worden, die von der Spezifikation von Brettspielen, über die Modellierung von "Ameisenkolonien" bis zu Beispielen aus der Transport- und Produktionslogistik reichen.

Ziele 2. Phase (2008-2011)

Ausgehend von den Ergebnissen der ersten Projektphase ist das Ziel des Teilprojekts A4 nun die Erweiterung der autonomen Einheiten zu einer semantisch fundierten, graphtransformatorischen Modellierungssprache für interagierende selbststeuernde Logistikprozesse mit besonderem Fokus auf nebenläufige Prozesssemantik. Die Modellierungssprache soll die Integration vieler verschiedener Formen der Selbststeuerung erlauben von der Fitnessfunktion bei genetischen Algorithmen und Schwarmintelligenz über maschinelles Lernen zu Selbstevaluation sowie diversen Planungs- und Entscheidungsverfahren. Weiterhin sollen verwandte Modellierungsansätze wie logistische Geschäftsprozessmodelle, Spieltheorie und Multiagentensysteme, objektorientierte Modellierung mit UML, Ameisensysteme, evolutionäre Algorithmen und DNA-Computing in autonome Einheiten übertragen werden.

Ergebnisse 2. Phase (2008-2011)

Die sequentielle, parallele und nebenläufige operationelle Semantik der autonomen Einheiten wurde untersucht. Zur weiteren Erprobung des Konzepts autonomer Einheiten wurden sie in einer ganzen Reihe experimenteller Anwendungen eingesetzt, die vom Rundreiseproblem, Tourenplanung und dynamischem Scheduling, über die Modellierung von Ameisensystemen und Multiagentensystemen sowie evolutionären Algorithmen reichen. Weitere Studien wurden zu DNA-Computing und Produktionsnetzen durchgeführt. Erste Untersuchungen zur Ergänzung der logistischen Modellierungssprache ALEM um eine formale Ausführungschicht sind in Arbeit.
Die Eigenschaften und Fähigkeiten autonomer Einheiten außerhalb ihres Einsatzes als Modellierungswerkzeug sind im Rahmen konzeptioneller Studien zu Modelltransformation, massivem Parallelismus, Komplexität und Termination, Visualisierung und Verifikation untersucht worden.
Zusätzlich existieren Vorarbeiten zur Implementierung autonomer Einheiten mit dem Graph-transformationssystem GrGen.NET sowie zur semantischen Analyse von Graphtransformationsabläufen mit dem SAT-Solver MiniSat.

Projektmitarbeiter

Dipl.-Inf. Marcus Ermler

Universität Bremen
Fachbereich Mathematik/Informatik
Technologie-Zentrum Informatik und Informationstechnik (TZI)
Arbeitsgruppe Theoretische Informatik
Linzer Str. 9a, 28359 Bremen, Germany
Tel: +49 421 218 64453, Fax: +49 421 218 4322
E-Mail , Homepage


Dr. Sabine Kuske

Universität Bremen
Fachbereich Mathematik/Informatik
Technologie-Zentrum Informatik und Informationstechnik (TZI)
Arbeitsgruppe Theoretische Informatik
Linzer Str. 9a, 28359 Bremen, Germany
Tel: +49 421 218 64456, Fax: +49 421 218 4322
E-Mail , Homepage


Dipl.-Inf. Caroline Diana von Totth

Universität Bremen
Fachbereich Mathematik/Informatik
Technologie-Zentrum Informatik und Informationstechnik (TZI)
Arbeitsgruppe Theoretische Informatik
Linzer Str. 9a, 28359 Bremen, Germany
Tel: +49 421 218 64457, Fax: +49 421 218 4322
E-Mail , Homepage