Bøger i Kunstliche Intelligenz serien

Das vorliegende Bueh ist eine iiberarbeitete Fassung meiner Habilitati­ onssehrift 'Funktionen in Hornklausellogik'. Die Arbeit ist an der Teehnisehen Universitat Miinehen im Rahmen des ESPRIT-Projektes P973 ALPES fertiggestellt worden. Herrn Prof. Bibel und Herrn Prof. Jessen moehte ieh danken, daB sie mir die Arbeit in der fruehtbaren und anregenden Atmosphare der Forsehungsgruppe Intellek­ tik ermoglieht haben. Herrn Prof. Brauer danke ieh fUr das Interesse, daB er dieser Arbeit entgegengebraeht hat. Ein wiehtiger Teil der Arbeit baut auf meiner wissensehaftliehen Tatigkeit an der Fakultat fiir Informatik der Univer­ sitat der Bundeswehr Miinehen auf. Fiir die Unterstiitzung wahrend die­ ser Zeit, sowie fUr zahlreiehe Verbesserungsvorsehlage moehte ieh Herrn Prof. Niegel herzlich danken. Die Zusammenarbeit mit meinem Kollegen Steffen Holldobler hat mir groBen SpaB gemaehtj seine Ideen, seine Diskussionsbereitsehaft und seine Kritikfreudigkeit haben mich stets angeregt. Diskussionen mit Thierry Conrad, Jean-Yves Cras und Bertram Fronhofer haben wesent­ lich mitgeholfen. Die Implementierung des FHCL-Systems wurde von Thomas Laufier­ meier, die der parallelen Version von Matthias Schuster angefertigt. Chri­ stian Suttner war FHCL-Anwender bei der Entwicklung von Smoothsort. Er hat auch zusammen mit Peter Baumgartner und Max Moser friihere Fassungen dieser Arbeit kritiseh gelesen.

In unüberschaubarer Fülle werden derzeit in der Künstlichen Intelligenz Formalismen vorgeschlagen, die den sogenannten gesunden Menschenverstand in Betracht ziehen und damit den unvollständigen Charakter verfügbarer Informationen verschleiern können. Der potentielle Benutzer ist etwas verwirrt durch die Vielfalt der ihm vorgeschlagenen Methoden, insofern als diese in einer vielfältigen weitverstreuten Literatur dargestellt sind, wo wenig Vergleichselemente zwischen den von verschiedenen Denkschulen vorgeschlagenen Ansätzen existieren. Dies kam einer Gruppe französischer Wissenschaftler zu Bewußtsein anläßtich einer ersten Arbeitstagung in Prelenfrey (Isere) am 34 März 1986, der Fachgruppe lnferenz und Kontrolle des Forschungsprogramms GRECO der Künstlichen Intelligenz, die kurz zuvor mit Unterstützung des Forschungsministeriums und des CNRS entstanden war. Es stellte sich in diesen zwei Tagen heraus, daß dieselben Beispiele zur Illustration und Begründung oftmals radikal verschiedener, teils symbolischer, teils auf numerischen Unsicherheitstheorien basierender Ansätze benutzt wurden. Wenig später wählte eine Arbeitsgruppe, die aus neun Personen bestand (Philippe Besnard, Marie-Odile Cordier, Didier Dubois, Luis Farift.as del Cerro, Christine Froidevaux, Yves Moinard, Henri Prade, Camilla Schwind et Pierre Siegel), den Namen Lea Sombe (aus im folgenden offensichtlichen Gründen) und beschloß, eine Vergleichsstudie an Hand eines anschaulichen Beispiels durchzuführen.

Since both the coments and the structure of the book appeared to be successful, only minor changes were made. As the world today has become so complex that humans apparently fail to manage it properly with their intellectual gifts, the realization of this dream might be regarded even as something like a necessity.

Die Programmiersprache Prolog gewinnt in weiten Kreisen von EDV-Fachleuten und Anwendern stark an Popularitat. 1m universitaren Kreis besitzt diese Spra­ che besonders im Bereich der wissensbasierten Systeme seit geraumer Zeit einen hohen Stellenwert. Das Ziel des Buches ist es, einen in Lektionen eingeteilten, methodisch geglie­ derten Einfuhrungskurs in die Programmierung mit Prolog zu geben. Das Buch basiert auf dem Praktikum "Programmieren in Prolog", das an der Technischen Universitat in Braunschweig seit dem Wintersemester 1984/85 regelmafiig an­ ge boten wird. Das Buch wendet sich an Schuler und Student en ebenso wie an Interessierte aller Fachrichtungen, die sich einen Einblick in die logis~he Programmierung und ihre Anwendungen verschaffen wollen. Fi.ir die erste Aufiage des Buches haben uns K. Drosten, D. Kruse, J. Risius und W. Struckmann wertvolle Anregungen gegeben. In der zweiten Aufiage haben wir zahlreiche Hinweise unserer Leser berucksichtigt. Wir danken insbesondere Herrn U. Schreiweis, der uns das Material fUr die neue praxisbezogene Lektion 19 zu Verfiigung gestellt hat und uns bei der Durchsicht des Manuskripts sehr behilfiich war. Ferner danken wir dem Vieweg-Verlag fUr die gute Zusammenarbeit.

Eine Programmiersprache wird eingesetzt, um Verfahren zur Lösung von Anwen­ dungsproblemen auf dem Computer zu formulieren. Daher sollte das Erlernen einer Programmiersprache immer in Bezug auf ein Anwendungsgebiet erfolgen. Kennt man die Grundbegriffe einer Programmiersprache, erlangt man einen höheren Grad ihrer Beherrschung am besten durch das Studium von Programmen, die typischen Einsatzgebieten der Sprache entstammen. Dabei sollte man wiederum an realen Aufgaben orientierte praktische Programmierübungen durchführen. Auf diese Weise erhält man ein lebendiges Bild von der Sprache, lernt sie aktiv beherrschen und erwirbt gleichzeitig ein Verständnis wichtiger Begriffe, Denkweisen und Algorithmen der Einsatzgebiete. LISP ist seit jeher die dominierende Sprache in der Künstlichen Intelligenz und in der Symbolischen Mathematik. Außerdem wird es bei der systemnahen Program­ mierung, z. B. bei der Erstellung von Programmierumgebungen, eingesetzt. Im vorliegenden Buch wollen wir den Gebrauch von LISP in diesen Anwendungs­ gebieten anband einiger Fallstudien vorführen. Unter einer Fallstudie verstehen wir die Darstellung der kompletten Lösung eines Anwendungsproblems. Diese schließt insbesondere die Erörterung der algorithmischen Hilfsmittel ein. Für unsere Zwecke kann die einzelne Studie nur so umfangreich sein, daß man sie als Ganzes gut überschauen und erfassen kann.

Erkenntnis bildet sich nur ikonisch, durch konkrete An­ schauung, und die Anschaulichkeit (Ikonizitiit) mufl ab­ solut sein. Umberto Eco Mit "Rechnersehen" wird heute ein umfangreiches Forschungs- und Anwen­ dungsgebiet bezeichnet. Bildhafte Information wird dabei von Rechnern mit ver­ schiedenen Methoden in abstraktere Beschreibungen transformiert, die zur Steue­ rung, Uberwachung, Interpretation oder anderer Weiterverarbeitung verwendet werden konnen. Diese Transformation wird in der Disziplin "Mustererkennung" behandelt. Zur Gewinnung von Bildinformation gibt es viele technische Verfahren, von de­ nen die meisten Daten liefern, deren Struktur sich gleichzeitig am menschlichen Sehapparat und an den Erfordernissen und Moglichkeiten der digitalen Datenver­ arbeitung orientiert. An den Aufbau der Augen angelehnt sind die Prinzipien der Kameras, die eine zweidimensionale Projektion der erfaBten dreidimensionalen Welt liefern. Stereoaufnahmen mit zwei oder mehr Kameras bilden im Prinzip ebenfalls die zwei Augen des Menschen nacho Die Darstellung der Sensordaten, die in den meisten Fallen digital in Form einer Matrix erfolgt, ist am Aufbau der Rechner orientiert, in dem dann die Abtastung in einem regelmaBigen Gitter vorliegt.

Das Fuhren von Terminierungsbeweisen flir rekursiv definierte Algorithmen erfordert eine gewisse Kreativitiit des (menschlichen oder automatischen) Bewei­ sers, die sich im Erfinden einer Hypothese manifestiert, deren Giiltigkeit hinrei­ chend flir die Terminierung eines Algorithmus ist. In dieser Arbeit wird ein Ver­ fahren vorgestellt, mit dem diese KreativiUit durch ein Computerprogramm nachgebildet werden soIl. Mit diesem Verfahren konnen Terminierungsbeweise in vielen Hillen vollautomatisch, d.h. ohne jegliche menschliche Unterstutzung, gefiihrt werden. Es wird gezeigt, - wie flir einen Algorithmus eine Terminierungshypothese automatisch synthetisiert werden kann, - welches Wissen uber Algorithmen dazu erforderlich ist, - wie dieses Wissen reprasentiert wird, und - wie dieses Wissen durch eine Maschine selbst berechnet werden kann. Das hier beschriebene Verfahren lOst die gestellte Aufgabe fUr eine relevante Klasse von Algorithmen, wie etwa klassische Sortieralgorithmen und Algorith­ men flir grundlegende arithmetische Operationen, die in einer rein funktionalen Programmiersprache gegeben sind. Die hier vorliegende Arbeit, die in den Jahren 1984 -1988 entstand, wurde zum Teil durch den Sonderforschungsbereich 314 "Kunstliche Intelligenz und Wissensbasierte Systeme" der Deutschen Forschungsgemeinschaft gefOrdert und von der Fakultat flir Informatik der Universitat Karlsruhe als Habilitations­ schrift angenommen. Ich danke Prof. Dr. P. Deussen flir die Arbeitsmoglichkei­ ten und Unterstiitzung wahrend der Jahre an seinem Institut.

Die Infonnatik ist ein fester, nicht mehr wegzudenkender Bestandteil un serer heuti­ gen Welt In alien Bereichen von Technik, Wirtschaft und Wissenschaft erledigen Rechenprogramme Routineaufgaben dauerhaft, meist zuverllissig und schnell. Der Fort­ schritt der Rechnertechnologie erlaubt dabei, daB dem Computer immer komplexere Aufgabenstellungen tibertragen werden konnen. Zudem werden immer mehr Bereiche von Programmen erfaBt, die nicht nur Rechenarbeit, sondern fast schon Denkarbeit erfordern. Wann Rechenarbeit aufhort und Denkarbeit anfllngt, Hillt sich natfirlich nicht definieren. 1m Idealfall kann man sich ein Programm vorstellen, das exakt die SchluB­ folgerungsmechanismen des menschlichen Geistes nachvollzieht und gestellte Probleme wie dieser, nur enonn schneller, lost Mit so einem Programm hlitte man dem Rechner, also einer Maschine, kUnstliche Intelligenz eingepf/anzt. Ob das grundslitzlich moglich ist, solI hier nicht diskutiert werden. Kfinstliche Intelligenz (KI) ist heute das Schlagwort, unter das alie Versuche subsu­ miert werden, menschliche Denkarbeit durch Rechner vornehmen zu lassen. An ein universelles Problemlosungsprogramm (general problem solver), wie es Newell und Simon (und anderen) noch Anfang der 60er Jahre vorschwebte, glaubt heute ernsthaft niemand mehr. Eher wird versucht, auf eng eingegrenzten Gebieten Spezialwissen menschlicher Experten irn Rechner zur Verftigung zu stellen, um es einem groBeren Anwenderkreis mitzbar zu machen. Dieses Wissen enthlilt dann nicht nur Daten, son­ dern auch Algorithmen zu deren Anwendung. Dem Benutzer wird also (z. B.

Das Gefiige unserer Welt wird immer engmaschiger mit technischen Systemen zu einem uniiberschaubar komplexen Gesamtsystem verflochten. Von ihrer Konzeption her sind solehe techDischen Systeme (und damit auch das Gesamtsystem) jedoch so angelegt, daB sie nur dann beherrseht werden kl>nnen, wenn men schlicher Geist sie durehschaut und begreift. Zwischen diesen beiden Sachverhalten tut sieh ein Zwiespalt auf, der an immer hltufigeren Pannen unterschiedliehen AusmaBes erkennbar ist. Ihnen allen ist gemein, daB sie die bete~gten Menschen rat- und hilflos erseheinen lassen. Technische Systeme herkl>mmlicher Bauart lassen sich als funktional ,,kodiertes" Detailwissen interpretieren. Sie zu verstehen heiBt dieses Wissen und seine Kodierung im einzelnen zu kennen. Nur unter dieser Voraussetzung ist es ml>glich, eine Anpassung des Systems bei verllnderten Einsatzbedingungen durehzufiihren oder bei einem auf­ tretenden Fehlverhalten des Systems die Ursaehe zu orten und wenn ml>glich Abhilfe zu schaffen. Die Ratlosigkeit entsteht dadurch, daB dieses Wissen in der Praxis in aller Regel nicht verfiigbar ist.

Dieses Buch basiert auf zwei zentralen Annahmen: Für den wissen­ schaftlichen und technischen Fortschritt einer wissenschaftlichen Disziplin ist erstens ein geeignetes mathematisches Handwerkszeug zur Formulierung und Zusammenfassung neuer Ideen nötig. Zweitens ist die symbolische Logik ein sehr wesentlicher Bestandteil der in der Forschung über Künstliche Intelligenz (KI) verwendeten Mathe­ matik. Beide Behauptungen müssen begründet werden. Man sollte allerdings meinen, unser erster Grundsatz fände ei­ gentlich allgemeine Zustimmung. Dennoch gibt es in neuen Wissen­ schaftsgebieten, in denen das Wissen hauptsächlich an die Praxis und empirische Fallstudien gebunden ist, vehemente Einwände gegen die Versuche einer Mathematisierung. (Einer der Autoren erinnert sich beispielsweise daran, wie sich in den 50-er Jahren einige Elektroingenieure darüber beklagten, daß zum Verständnis von elek­ trischen Schaltkreisen und Kontrollsystemen Differentialglei­ chungen doch völlig unnötig seinen!) Wir behaupten nicht, daß das Wissen um die mathematischen Grundlagen und Techniken einer Diszi­ plin allein ausreicht, um in der Forschung oder in der Praxis er­ folgreich zu sein. Wir sind allerdings der Meinung, daß zu einem VIII Vorwort erfolgreichem Studium der modernen, insbesonders technisch orien­ tierten Wissenschaftsdisziplinen immer auch ein solides mathema­ tisches Handwerkszeug der jeweiligen Disziplin gehört. Das Studium dieser Grundlagen bietet die Voraussetzungen, um die jeweilige Disziplin interpretieren, verstehen und ausbauen zu können. Da die KI eine noch relativ junge Disziplin ist, ist es nicht verwunderlich, daß es hitzige und geistreiche Debatten zwischen "Formalisten" und "Experimentalisten" gibt. Die Formalisten mei­ nen, dieExperimentalisten kämen schneller voran, wenn sie ein tieferes Verständnis der theoretischen Grundlagen der KI besäßen.

Zur EntwicklungWissensbasierter Systeme stehen inzwischen unterschiedliche Werkzeuge zur VerfUgung. Eines dieser Werkzeuge ist O}>S5, das speziell zur Erstellung regelbasierter Systeme dient. Es hat schon seit llingerem den Weg aus den Entwicklungslaboratorien gefunden und wurde fUr erfolgreich eingesetzte Experten­ systeme verwendet. Auch in der Bundesrepublik hat es Verbreitung in Universitliten und Unternehmen gefunden. Ein Lehrbuch in deutscher Sprache, wie es sie fUr Sprachen wie Pascal oder FORTRAN in breiter Auswahl gibt, existierte fUr OPS5 jedoch bislang nicht. Als die Autoren Anfang 1985 begannen, sich mit OPS5 zu beschliftigen, gab es als einzige Unterlage lediglich das knappe Handbuch von Charles L. Forgy als Bericht der Carnegie-Mellon Universitlit sowie einige kurze VerMfentlichungen anderer Universitliten. Zum Erlernen einer Sprache sind HandbUcher aber weder geeignet noch gedacht, da sie didaktische Gesichtspunkte vfillig auBer acht lassen. Auch wird in ihnen weder auf das zugrundeliegende Programmierparadigma eingegangen noch etwas fiber das Umfeld oder den Einsatz der Sprache ausgesagt. Viele Fragen lassen sich aufgrund des Handbuches auch nicht beantworten. Die Autoren konnten deshalb detaillierte Kenntnisse Uber OPS5 und dessen Mfiglichkeiten nur auf experimentellem Weg gewinnen. Um anderen den Einstieg in OPS5 zu erleichtem, begannen sie, ihre gewonnenen Erkenntnisse zu dokumentieren. Daraus entstand zunlichst ein Skript als Arbeitsmaterial fUr ein Seminar Uber OPS5. Aufgrund der mit den Teilnehmern gemachten Erfahrungen wurde das Skript korri­ giert und erglinzt. FUr das vorliegende Buch wurde das Material vfillig Uberarbeitet und wesentlich erweitert. Dabei enstand die nun vorliegende Dreiteilung.