🚀 go-pugleaf

--------------------------------------------------------------------------

                                                    
F O R S C H U N G S K O L L O Q U I U M             
Kuenstliche Intelligenz
                                                    
im Sommersemster 2000                               
                                                    
                                                    
Dienstag, den 18. Juli 2000
16.15 - 17.45 Uhr
Raum  FR 0513
Franklinstr. 28/29
D-10587 Berlin

--------------------------------------------------------------------------
 

      ERFÜLLUNG VON CONSTRAINTNETZEN BEIM RÄUMLICHEN SCHLIEßEN

                           Carsten Gips

                            TU Berlin 

Thema der Arbeit ist die Überprüfung der gleichzeitigen Erfüllbarkeit 
mehrerer räumlicher Relationen. Für die Definition der Relationen wurde 
der Ansatz aus dem DFG-Projekt 'Modellierung von Inferenzen in Mentalen 
Modellen' benutzt, bei dem Objekten Koordinatensysteme zugeordnet werden 
und die Relationen durch Constraints über den Transformationsmatrizen 
zwischen zwei Objekten beschrieben werden. Da aus Komplexitätsgründen 
eine analytische Überprüfung der Constraints nicht machbar ist, wurde 
ein konstruktives heuristisches Verfahren entwickelt.
Zunächst wurden anhand einer Beispielszene einige räumliche Relationen
ausgewählt und die zugehörigen Constraints mit CAL5 gelernt. Dann werden 
zu einer gegebenen textuellen Beschreibung von räumlichen Beziehungen 
zwischen Objekten Depiktionen generiert, die nicht nur die gegebenen 
Relationen erfüllen, sondern auch Hintergrundwissen über die Objektgrößen 
berücksichtigen und sicherstellen, daß sich Objekte nicht überlappen und 
alle in einem Zimmer plaziert werden. Da durch die Relationen 
Objektpositionen in verschiedenen Bezugssystemen beschrieben werden, sind 
Koordinatentransformationen notwendig.

In der Arbeit wurden dazu zwei Algorithmen entwickelt und implementiert. 
Der Basisalgorithmus ist ein Brute-Force-Ansatz. Alle zum Problem gehörigen 
Objekte werden beliebig im Zimmer plaziert. Danach wird mit Hilfe der 
gelernten Entscheidungsbäume getestet, ob alle geforderten Relationen 
gelten. Zusätzlich erfolgt noch die Kollisionsüberprüfung. Durch die 
zufällige Plazierung der Objekte ist eine hohe Zahl von Versuchen notwendig, 
um eine mit der Beschreibung kompatible Szene zu erhalten.

Der erweiterte Algorithmus baut auf der Basisvariante auf. Hier werden 
die zulässigen Gebiete für die Relationen aus den Entscheidungsbäumen 
extrahiert und für die Bestimmung von Ausdehnung und Position der Objekte 
verwendet. Dadurch ergeben sich wesentlich höhere Trefferraten. Da dieser 
Algorithmus die Relationen nacheinander abarbeitet, eignet er sich für die 
interaktive Erzeugung von Depiktionen. Die Effizienz des Verfahrens kann 
durch gezieltere Generierung von Trainingsdaten beim Lernen der Relationen 
noch verbessert werden. 


------------------------------------------------------------------------

TU Berlin
FG Methoden der Künstlichen Intelligenz
Franklinstr. 28/29, FR 5-8
10587 Berlin

--------------------------------------------------------------------------
--------------------------------------------------------------------------
  Das aktuelle Kolloquiumsprogramm finden Sie im WWW unter 

                http://ki.cs.tu-berlin.de/col.html 
--------------------------------------------------------------------------
--------------------------------------------------------------------------


-- 
### Peter Geibel 
### TU Berlin, KI, Sekr. FR 5-8, Franklinstr. 28/29, D-10587 Berlin
### Tel. +49-30-314-25491, Fax +49-30-314-24913
### http://www.cs.tu-berlin.de/~geibel, mailto:geibel@cs.tu-berlin.de