5  Forschungsschwerpunkte

Räumliche Datenstrukturen und Sichtbarkeitsplanung in großen Szenen
(Spatial Indices and Visibility)

Ein Ziel ist die Entwicklung effizienter und praktikabler Datenstrukturen zur Unterstützung von Anfragen auf räumliche Daten. Bisher wurden folgende Punkte untersucht: dynamische Update-Eigenschaften bei Veränderung der Objekte; Verwaltung großer Datenmengen im langsamen Sekundärspeicher; Behandlung realistischer (beispielsweise wenig dichter) Szenen; Vergleich verschiedener Clusteralgorithmen; Hierarchische Approximation von Objekten und Szenen.

Durch die Verwendung räumlicher Datenstrukturen lassen sich Bewegungsplanungs- und Sichtbarkeitsanfragen insbesondere in großen Szenen wesentlich beschleunigen, da sich deren Vorteile (beispielsweise Vergröbern und Verfeinern, dynamische Eigenschaften und Speicherhandhabung) direkt ausnutzen lassen. Außerdem werden die Auswirkungen realistischer Annahmen über die Szene (z. B. beschränkte Dichtheit und Überlappungsgrad) sowie der Nutzen von zeitlich-räumlichen Schließen bei der Bewegungsplanung untersucht. Dies sind wichtige methodische Grundlagen für Animation, Visualisierung, Virtual Reality-Anwendungen.

Lokalisation und Navigation für autonome Roboter in Produktions- und Serviceumgebungen mittels Laser-Radar
(Localization and Navigation for Autonomous Robots in Industrial and Service Environments Using Laser Radar)

Die Entwicklung einer ortsmarkenfreien Navigation ist wichtige Voraussetzung für die Realisierung autonomer Roboter. Ziel des Projekts ist es, die methodischen Grundlagen zu untersuchen, adäquate Modellierungen zu finden und diese im konkreten Anwendungsfeld zu erproben. Hierbei wird vor allen Dingen die Laser-Technologie, die robust, billig, schnell und relativ präzise ist, für die Navigation verwendet.

Flexible Fertigung
(Flexible Manufacturing)

Fertigungsprozesse im industriellen Umfeld bieten häufig vielerlei Möglichkeiten der Optimierung. Ziel dieses Projekts ist es, einige Ansatzpunkte an ausgewählten Szenarien zu untersuchen. Beispiele hierfür sind die automatische Fahrweggenerierung für Schweißroboter, der Einsatz von Mustererkennungsverfahren in der Qualitätskontrolle, die Planung einer Assemblierfolge einschließlich der Teilefixierung bei komplexen Werkstücken, die Optimierung von Bestückungssequenzen bei der Platinenbestückung.

Netzwerk-Entwurf und Netzwerk-Ausbau
(Network Design and Network Improvement)

Ein Ziel des Projekts ist die Entwicklung von effizienten Approximationsalgorithmen für NP-harte diskrete Optimierungsaufgaben aus dem Bereich des Netzwerkdesigns. Da es unwahrscheinlich scheint, daß man einen polynomialen Algorithmus für ein NP-hartes Problem finden kann, ist es sinnvoll, anstelle von optimalen Lösungen solche zu suchen, welche die Optimalität garantiert nur geringfügig verletzen, dafür aber effizient algorithmisch bestimmt werden können.

Es werden für NP-harte Mehrkriterienprobleme vier Problembereiche betrachtet: Netzwerkausbau bei Standortproblemen, Netzwerkmodifikationen bei Schnittproblemen, Netzwerk-Entwurf in gerichteten Graphen und die Formulierung von generischen Approximationsalgorithmen für ganze Klassen von Mehrkriterienproblemen mit Hilfe eines syntaktischen Rahmens. Die Implementierung grundlegender Techniken der Approximationsverfahren soll darüber hinaus als Basis für eine breit nutzbare Bibliothek dienen, die auch für großdimensionierte Problemausprägungen effiziente Verfahren bereitstellt.

Lokationsprobleme
(Facility Layout)

Lokationsprobleme beschäftigen sich damit, eine optimale Standortentscheidung zu treffen. Beispiele hierfür sind das Plazieren von Fabriken, Notfallversorgungseinheiten oder von Computern. Die Optimalität der Entscheidung hängt vom jeweiligen Problem ab. Es existieren eine größere Anzahl von Kriterien, mit denen die Qualität einer Standortentscheidung bewertet werden. Lokationsprobleme haben vielfältige Anwendungen im Bereich der Standortplanung und bei Bestückungsproblemen. Da viele Lokationsprobleme NP-hart sind, sind auch hier Approximationsverfahren von Interesse, die in polynomialer Zeit Lösungen mit einer Qualitätsgarantie liefern.

Optimierungsmethoden für Disjunktive Deduktive Datenbanken
(Optimization Techniques for Disjunctive Deductive Databases)

Deduktive Datenbanken benutzen Konzepte der Logikprogrammierung für mächtige, deklarative Anfragesprachen und zur Verwaltung von großen Mengen von Daten. Neue Möglichkeiten für Wissensbanken erwachsen aus der Verwendung von unsicherem und unvollständigem Wissen, repräsentiert durch Logikprogramme mit disjunktiven Fakten und Regeln. Allerdings ist die Inferenz in disjunktiven deduktiven Datenbanken sehr aufwendig, besonders im Zusammenhang mit Negation.

Es wurden einige wichtige Auswertungsansätze theoretisch untersucht. Diese beruhen alle auf einer Reihe von grundlegenden Inferenztechniken: Hyperresolution, nicht-monotones Schließen mit Closed-World-Annahmen und Negation-as-Failure-Konzepte.

Diese Inferenztechniken wurden in einem System namens DISLOG mit Hilfe von neuen Datenstrukturen und effizienten Algorithmen implementiert.

zurück zum Inhaltsverzeichnis

Drittmittel / Kooperationen