Suche Home Einstellungen Anmelden Hilfe  

Antwortmengenprogrammierung

Torsten Schaub, Universität Potsdam

Die Idee der Formalisierung logischer Schlußweisen läßt sich bis in die Antike zu den Arbeiten von Aristoteles (gest. 322 v.Chr.) zurückverfolgen. Die damals entscheidende Entdeckung war, daß logische Schlüsse allein von der Form der beteiligten Aussagen abhängen und damit vom Inhalt der Aussagen unabhängig sind - eine für die Automatisierung durch Rechenmaschinen unabdingbare Voraussetzung! Es war dann Leibniz (1646-1716), der als erster den Traum einer voll automatisierten Denkmaschine formulierte. Der effektive Durchbruch bei der Abbildung logischer Schlußweisen auf ausführbare Rechenoperationen gelang allerdings erst Robinson im Jahre 1965 mit dem sogenannten Resolutionskalkül. Im Gegensatz zu den bis dato dem menschlichen Vorgehen nachempfundenen Schlußregeln, ist die Resolutionsregel bestens für die mechanische Abarbeitung durch Computer geeignet. Genauso wie eine Vielzahl heutiger Hochleistungsbeweiser basiert auch die Programmiersprache Prolog auf dem Resolutionskalkül.

Mit der Erfindung von Prolog Anfang der 70er Jahre haben Colmerauer und Kowalski gezeigt, wie Logik zum Programmieren verwendet werden kann. Damit gelang eine erfolgreiche Synthese deklarativer und prozeduraler Programmierung. Grob gesprochen kann man damit eine Prolog-Regel, wie

über(X,Y) :- auf(X,Z),über(Z,Y),
(gelesen: Wenn X auf Z liegt und sich Z über Y befindet, dann befindet sich auch X über Y) in deklarativer Weise als die logische Formel
\begin{displaymath}\forall xy (\exists z (\mathit{auf}(x,z)\wedge\mathit{\ddot{u}ber}(z,y))\to\mathit{\ddot{u}ber}(x,y))\end{displaymath}

verstehen. Prozedural kann die Regel auch als (Teil einer) Prozedur "über" mit zwei Parametern X und Y, einer lokalen Variable Z und zwei Prozeduraufrufen auf(X,Z) und über(Z,Y), ähnlich wie in der Programmiersprache Pascal, interpretiert werden.

Prolog ist allerdings nicht rein deklarativ, was man daran erkennen kann, daß die beiden Programme

über(X,Y) :- auf(X,Y). 
über(X,Y) :- auf(X,Z),über(Z,Y). 
und
über(X,Y) :- über(Z,Y),auf(X,Z). 
über(X,Y) :- auf(X,Y). 
zwar bezüglich ihrer logischen Interpretation äquivalent sind, sich aber bezüglich ihres prozeduralen Verhaltens unterscheiden. Fügt man zum Beispiel die Aussage
auf(buch,tisch)
zu beiden Programmen hinzu und stellt dann die Anfrage
über(buch,tisch),
so wird dies durch das erste Programm bejaht, während sich das zweite in einer Endlosschleife verirrt und nicht terminiert. Dies liegt daran, daß in Prolog die Abarbeitung der Regeln durch ihre Reihenfolge bestimmt wird. Doch auch wenn dies aus Sicht eines Programmierers durchaus legitim erscheint, so genügt es nicht den Ansprüchen einer rein deklarativen Sicht der Programmierung.

Bis zum Ende der 90er Jahre wurde deshalb eine Vielzahl von Alternativen untersucht, um diese Abweichung der deklarativen Bedeutung eines logischen Programms von seiner prozeduralen Ausführung zu beseitigen. Die Antwortmengenprogrammierung kann als ein erfolgreiches Resultat dieses Forschungsvorhabens gesehen werden; sie vereint Techniken aus der logischen Programmierung mit denen aus den Gebieten der Wissensrepräsentation, der deduktiven Datenbanken und des nichtmonotonen Schließens. Regeln der Form

L0 <-- L1, ..., Lm, not Lm+1,..., not Ln
(mit atomaren Aussagen Lk für 0<=k<=m über endlichem Gegenstandbereich) werden hier jeweils als Randbedingungen (engl.: constraints) an zu formende Antwortmengen A aufgefasst: Wenn LiA  für 1<=i<=m und LjA für m<j<=n, dann ist L0A. Logische Programme bestehen dann aus einer Menge solcher Regeln und haben keine, eine oder gar mehrere Antwortmengen. Zum Beispiel hat das Programm
 
(1) p <-- p
(2) q <-- not p
eine einzige Antwortmenge, nämlich {q}. Denn nur mittels der zirkulären Regel (1) kann p nicht zur Antwortmenge gehören, und nach Regel (2) gehört q zur Antwortmenge, falls p nicht dazugehört. Das Programm
p <-- not q
q <-- not p
besitzt zwei Antwortmengen {p} und {q}. Auch können Integritätsbedingungen durch "kopflose" Regeln (d.h. unter Weglassen von L0) formuliert werden. Das Programm
p <-- not q
q <-- not p
<-- not p
hat dann nur eine Antwortmenge: {p}. Die Integritätsbedingung wird immer dann verletzt, wenn p nicht zur Antwortmenge gehört; dies führt zur Elimination der Antwortmenge {q}.

Formal wird die Semantik von Antwortmengen durch Fixpunkte nichtmonotoner Operatoren beschrieben. Man kann zeigen, daß alle Entscheidungs- und Suchprobleme in der Problemklasse NP (auch salopp als die Klasse der in einfach exponentieller Zeit lösbaren Probleme bezeichnet) durch die Berechnung von Antwortmengen entsprechender (aussagen)logischer Programme gelöst werden können. Interessanterweise erhöht weder die Verwendung von Integritätsbedingungen noch die Erweiterung der Sprache um die explizite Negation $\neg$ die Komplexität und damit die eigentliche Ausdrucksstärke des Formalismus. Mit letzterem kann man etwa leicht Weltabgeschlossenheitsaxiome, wie

$\neg$p(x) <-- not p(x)
formulieren, frei nach dem Motto: "Ist p(x) nicht beweisbar, dann ist p(x) falsch". Die Komplexität und damit einhergehend die Ausdruckskraft wird erst durch die Hinzunahme von Regeln mit Disjunktion auf der linken Seite der Regel erhöht. Man befindet sich dann in der Problemklasse NPNP. Daran ändert auch die Hinzunahme des Operators not auf der linken Seite und sogar die beliebige Schachtelung von Formeln mit not, $\neg$, sowie Disjunktion und Konjunktion nichts mehr. Zum Beispiel kann die Frage nach einer Belegung von a und b mit wahr/falsch, die die Formel
\((a\vee\neg b)\wedge (\neg a\vee b)\)
wahr macht, wie folgt repräsentiert werden:
\begin{displaymath}\begin{array}[t]{rc}{ a\vee not~a}&{\leftarrow}\\{ b\vee ......\leftarrow}&{ not~a, b}\\{\leftarrow}&{ a, not~b}\end{array}\end{displaymath}

Während die beiden Regeln auf der linken Seite den (zweiwertigen) Wertebereich von a und b, also die Menge aller möglichen Belegungen beschreiben, eliminieren die beiden Integritätsbedingungen rechts alle unzulässigen Kandidaten. Hieraus resultieren zwei Antwortmengen A1={a,b} und A2=, die den beiden Lösungen unseres Problems entsprechen.

Ein in der Praxis enorm hilfreiches und erfreulicherweise komplexitätsneutrales Sprachkonstrukt ist die Kardinalitätsbeschränkung. Grob gesprochen steht ein Kardinalitätsliteral, wie m{p(x)}n, für jede Menge mit mindestens m und höchstens n Instanzen von p(x). Zur Illustration wollen wir das oft in der Informatik behandelte n-Damenproblem verwenden. Es geht darum, n Damen so auf einem n*n-Schachbrett zu plazieren, daß keine Dame eine andere bedroht. Folgendes Programm realisiert das Gewünschte:

d(1..n) <--
1{q(x,y)}1 <-- d(x)
1{q(x,y)}1 <-- d(y)
<-- q(x,y),q(x',y'), xx', yy', |x-x'|=|y-y'|
Während das Prädikat d den Wertebereich fixiert -- es gibt also n Damen, die von 1 bis n durchnumeriert sind --, beschreibt q die Positionen der Damen. Die zweite und dritte Regel generieren sozusagen alle Schachbretter, in deren Spalten und Zeilen genau eine Dame steht. Steht die Dame mit der Nummer x in der Spalte (bzw. Zeile) x, so ist die Zahl der Felder q(x,y), auf der eine Dame steht, mindestens und höchstens 1. Die Integritätsbedingung eliminiert dann noch solche, bei denen sich zwei Damen auf derselben Diagonale befinden. Jede Antwortmenge repräsentiert dann eine Lösung des n-Damenproblems.

Oft wird die Modellierung spezieller Problemklassen durch abstrakte Sprachkonstrukte unterstützt. Bei der Handlungsplanung setzt man beispielsweise zur Modellierung kausaler Abläufe Konstrukte wie

bewege(b,l)  causes auf(b,l)
inertial auf(b,l)
ein, die dann direkt in logische Regeln der Form
auf(b,l,t+1)  <-- bewege(b,l,t). 
auf(b,l,t+1)  <-- auf(b,l,t), not $\neg$auf(b,l,t+1). 
übersetzt werden können. Die erste Regel sagt, daß die Bewegung eines Blockes b zum Ort l zum Zeitpunkt t zur Folge hat, daß b zum Zeitpunkt t+1 auf l steht; während die zweite Regel sagt, daß wenn sich ein Block b zum Zeitpunkt t auf l befindet, er sich auch zum Zeitpunkt t+1 dort befindet, es sei denn man kann das Gegenteil beweisen.

Neben der Handlungsplanung ist die Antwortmengenprogrammierung für viele weitere Anwendungen geeignet, etwa Diagnose, Scheduling, Konfigurierung, Stundenplanprobleme, Model Checking, Kryptographie u.v.m. Zu den interessantesten Anwendungen der Antwortmengenprogrammierung zählen momentan die Konfigurierung von (Debian) Linux und Schedulingaufgaben beim Space Shuttle der NASA. Die Vorteile des Ansatzes liegen sicherlich in seiner Einfachheit und der daraus resultierenden Transparenz. Mit der Verfügbarkeit effizienter Systeme dringt die Methodik auch immer mehr in Anwendungsgebiete vor, wo es gilt, komplexe Systeme qualitativ zu modellieren.

Literatur

Adresse

Prof. Dr. Torsten Schaub
Institut für Informatik
Universität Potsdam
August-Bebel-Str. 89
14482 Potsdam
Email: torsten@cs.uni-potsdam.de
WWW: http://www.cs.uni-potsdam.de/~torsten

Lebenslauf

Torsten Schaub (36 Jahre) hat an der TU Darmstadt Informatik studiert, wo er von 1990 bis 1993 als wissenschaftlicher Mitarbeiter gearbeitet hat. 1992 wurde er dort promoviert. 1995 hat er sich an der Universität Rennes, Frankreich, habilitiert. Zwischen 1993 und 1995 war er Forschungsassistent am französichen Forschungsinstitut IRISA/INRIA in Rennes und danach bis 1997 Professor an der Universität Angers, Frankreich. Dort gründete er die Forschungsgruppe FLUX, die sich mit der Automatisierung von logischen Schlußverfahren für unvollständiges, widersprüchliches und evolutives Wissen befaßte. 1997 wurde er zum Professor für Wissensverarbeitung und Informationsverarbeitung an die Universität Potsdam berufen. Seit 1999 ist er zugleich Adjunct Professor an der School of Computing Science der Simon Fraser University, Kanada. Seine Forschungsinteressen reichen von den theoretischen Grundlagen bis zur praktischen Implementierung von Methoden für Wissensverarbeitung unvollständiger und/oder inkonsistenter Information.

Glossar

Resolutionskalkül: Maschinell nachvollziehbares Verfahren, mit dem Behauptungen aus vorgegebenen Tatsachen bewiesen werden können (sofern sie daraus beweisbar sind). Der Resolutionskalkül ist Berechnungsgrundlage aller logischen Programmiersprachen, wie Prolog.

deklarative Programmierung: Form der Programmierung, bei der zunächst alle Randbedingungen des Problems beschrieben werden. Die Aufgabe der Maschine besteht dann darin, innerhalb dieses Rahmens selbständig eine Lösung zu ermitteln. Zur Klasse der deklarativen Programmiersprachen rechnen mit Einschränkungen die logischen Programmiersprachen (z.B. Prolog) und die funktionalen Programmiersprachen.

prozedurale Programmierung: Form der Programmierung, bei der der Weg, auf dem zu einem gegebenen Problem eine Lösung zu ermitteln ist, beschrieben wird. Traditionelle imperative Programmiersprachen, wie Pascal, C, Modula, gehören zur Kategorie der prozeduralen Programmiersprachen.

Integritätsbedingung: Integrität von Datenbeständen ist gegeben, wenn eine korrekte und widerspruchsfreie Speicherung der Daten gewährleistet ist. Integritätsbedingungen beschreiben Eigenschaften möglicher Zustände der abgespeicherten Daten sowie von Beziehungen zwischen Daten.

NP: Klasse aller Probleme, die durch nichtdeterministische Programme in polynomieller Zeit gelöst werden können. Man geht davon aus (kann es aber bisher nicht beweisen), daß alle Probleme dieser Klasse mit deterministischen Programmen nicht schneller als in exponentieller Zeit gelöst werden können.
 

Benutzer: gast • Besitzer: schwill • Zuletzt geändert am: