Albert-Ludwigs-Universität Freiburg Kursvorlesung Grundlagen der KI Sommersemester 1999	Institut für Informatik Intelligente Autonome Systeme Dr. Wolfram Burgard Dipl.-Inf. Wolfgang Hatzack

Aufgabe 2.1 (2 Punkte)

Betrachten Sie die 2-Zimmer-Staubsaugerwelt aus der Vorlesung, in der Murphy's Law gilt (falls ein Raum bereits gereinigt ist, kann die Suck-Aktion in manchen Fällen den Raum wieder verschmutzen). Zeigen Sie, daß es unter der Voraussetzung der Zugänglichkeit (vollständiges Weltwissen) für jeden Anfangszustand eine Aktionssequenz gibt, die einen Zielzustand erreicht.

Aufgabe 2.2: (3 Punkte)

Geben Sie für die folgenden Problemstellungen jeweils eine möglichst präzise Formulierung an, die aus Anfangszustand, Zieltest sowie plausiblen Operatoren und einer Pfadkostenfunktion besteht.

1.

Sie haben sich im Dschungel des Amazonas verlaufen und suchen das offene Meer. In Ihrer Nähe ist ein Fluß.

2.

Ein Affe befindet sich in einem Raum mit einer Kiste, und an der Decke hängen außerhalb seiner Reichweite Bananen. Er würde gerne die Bananen essen.

3.

Sie haben sich in einer Kleinstadt verlaufen und müssen eine Apotheke finden. Es gibt keinen Stadtplan und alle Einwohner haben sich zu Hause eingeschlossen.

Aufgabe 2.3: (2 Punkte)

Welche Suchstrategien werden bei der Verwendung der Heuristik-Funktionen

(a)

h(n) = -g(n)

(b)

h(n) = g(n)

Aufgabe 2.4 (3 Punkte)

Spezifizieren Sie einen allgemeinen Suchraum, in dem iteratives Vertiefen viel schlechter ist als Tiefensuche.