Fakultät für Informatik Übungen zu Kognitive Systeme Sommersemster 2016 M. Sperber ([email protected]) T. Nguyen ([email protected]) S. Speidel ([email protected]) D. Katic ([email protected]) Übungsblatt 6 Wissensrepräsentation,Planung und Robotik Abgabe der Onlineaufgaben vor Montag, 18. Juli 2016, 14:00 Uhr Abgabe der schriftlichen Ausarbeitung vor der Saalübung am 18. Juli 2016, 14:00 Uhr Bonuspunkte fur die Klausur werden nur vergeben, wenn eine schriftliche Lösung aller Aufgaben (incl. Onlinefragen) abgegeben wurde Die Antworten auf die Onlinefragen können unter http://wwwiaim.ira.uka.de/websubmit/ eingetragen werden. Allgemeines Nach der Übung werden die Musterlösungen im Internet zugänglich gemacht. Die Aufgaben werden in der Übung besprochen. Die Reihenfolge der angegebenen Lösungsmöglichkeiten der OnlineAufgaben entspricht nicht zwangsläufig der Reihenfolge der Lösungen im Internet. Weitere Informationen und Kontaktadressen finden Sie auf der Vorlesungsseite. Aufgabe 1 - Resolution und DPLL 1.a Geben Sie die Konjunktive Normalform folgender Sätze an. Erstellen Sie hierfür zuerst eine Wahrheitstabelle. (i) α = A ∨ (¬B ∧ C), (ii) β = (A ∧ C) ∨ (¬B ∧ ¬A), (iii) γ = (¬A ∧ ¬B) ∨ C. 1.b Gegeben sei die Klauselmenge (A ∨ ¬B), (A ∨ ¬B ∨ ¬C), (A ∨ ¬C), (B). Leiten Sie folgende Aussagen (falls möglich) durch Widerspruchsbeweis ab. (i) A, (ii) B, (iii) ¬C. Onlinefrage Nr. 1: Welche Aussage können Sie nicht ableiten? (a) A (b) B (c) ¬C 1 1.c Zeigen Sie mit Hilfe des DPLL-Verfahrens, dass folgende Klauselmenge S erfüllbar ist: ¬C D D E ¬C D ∨ ∨ ∨ ∨ ∨ ∨ ¬A ¬E A D ¬A E A ∨ ∨ ∨ ∨ ∨ ∨ B ¬A C B ¬B C Onlinefrage Nr. 2: Für welches der folgenden Symbole existiert jeweils für alle Belegungen ein Modell, das S erfüllt, und das vom DPLL-Algorithmus gefunden wird? (a) A (b) B (c) C Aufgabe 2 - STRIPS & ADL Das Problem des Schiffstransportes besteht aus dem Be- und Entladen von Schiffen, und dem Transport von einem Hafen zum anderen. Hierfür können die Aktionen Load, U nload und T ransport definiert werden. Außerdem werden die zwei Prädikate In(c, p) und At(x, a) benötigt. In(c, p) bedeutet, dass die Fracht c sich in dem Schiff p befindet. At(x, a) bedeutet, dass sich ein Objekt (Schiff oder Fracht) am Hafen a befindet (, wobei sich die Fracht nicht am Hafen befindet, solange sie noch in einem Schiff ist). 2.a Definieren Sie die Aktionen Load, U nload und T ransport durch die Liste der Parameter, Vorbedingung und Effekt in STRIPS. 2.b Die Fracht C1 und das Schiff P1 befinden sich in Hamburg (HH) und soll nach New York (NY) transportiert und abgeladen werden. Dort soll die Fracht C2 aufgeladen, nach Hamburg transportiert und dort abgeladen werden. Geben Sie Initialzustand und Zielzustand des Planungsproblems in STRIPS an. Geben Sie eine Folge von Aktionen mit Parametern in STRIPS an, welche das genannte Problem löst. 2.c In diesem Aufgabenteil sollen sich die Fracht C1 und das Schiff P1 in Hamburg (HH) befinden. Am Hafen New York (NY) befindet sich die Fracht C2 . Ziel soll sein, dass sich beide Frachtstücke am gleichen Hafen befinden. Geben Sie Initialzustand und Zielzustand des Planungsproblems in der Planungssprache ADL an. Geben Sie eine Folge von Aktionen mit Parametern in ADL an, welche das oben beschriebene Problem löst. Aufgabe 3 - Planungsgraph Ein Haushaltsroboter soll in der Küche die Spülmaschine bedienen. Hierfür ist es nötig, dass der Roboter die Spülmaschine öffnet, das Geschirr einräumt und Spülmittel 2 einfüllt. Für den dazu benötigten Plan wurden folgende Aktionen sowie ein Start- und ein Zielzustand in ADL formuliert: Aktionen: Action( ) Action( ) Action( Startzustand: Zielzustand: SpülmaschineÖffnen(), Vorbed.: ausgeschaltet ∧ ¬geöffnet Effekt: geöffnet GeschirrEinräumen(), Vorbed.: geöffnet ∧ ¬eingeräumt Effekt: eingeräumt SpülmittelEinfüllen(), Vorbed.: geöffnet ∧ ¬eingefüllt Effekt: eingefüllt ) ausgeschaltet ∧ ¬geöffnet ∧ ¬eingeräumt ∧ ¬eingefüllt eingeräumt ∧ eingefüllt Konstruieren Sie zu dieser Planungsaufgabe den Planungsgraphen inklusive aller MutexLinks. Aufgabe 4 - Bahnplanung Gegeben sei die unten abgebildete Hinderniskonstellation mit einem punktförmigen mobilen Roboter am Startpunkt und einem gegebenen Zielpunkt. Der Bildrahmen sei hierbei kein Hindernis. Die Eckpunkte sind durch Großbuchstaben gekennzeichnet und mit der Entfernung zum Zielpunkt angegeben. In der Tabelle sind die Distanzen zwischen den Punkten angegeben. Hinweis: Sie können sich die Abbildung zur Bearbeitung auch von der Vorlesungshomepage herunterladen und nochmals ausdrucken. Start (106) A (90) B (60) D (49) C (70) E (46) Ziel (0) 4.a Start Start 0 A 17 B 54 C 41 D 63 E 67 F 108 G 106 Ziel 106 A 17 0 43 24 50 53 91 90 90 B 54 43 0 41 12 15 87 87 60 C 41 24 41 0 41 45 67 65 70 D 63 50 12 41 0 4 80 80 49 E F G Ziel 67 108 106 106 53 91 90 90 15 87 87 60 45 67 65 70 4 80 80 49 0 80 80 46 80 0 4 55 80 4 0 57 46 55 57 0 G (57) F (55) Bestimmen Sie zunächst graphisch den Konfigurationsraum, den Hindernisraum und den Freiraum. Wie können Sie Hindernis- und Freiraum anpassen, wenn der Roboter zwar einen Durchmesser von d besitzt, Sie aber trotzdem von einem punktförmigen Roboter ausgehen wollen? 4.b Bilden Sie nun kollisionsfreie Teilstrecken zwischen den Hindernissen, indem Sie einen Sichtgraphen erstellen. Skizzieren Sie den Graph. 3 Onlinefrage Nr. 3: Wieviele Kanten besitzt der Graph ? (a) 19 (b) 12 (c) 9 4.c Geben Sie den Suchbaum und die Punktfolge an, welche die unten genannten Planer ermitteln würden. Hierbei gilt g(n) : Kosten vom Startknoten zum Knoten n. h(n) : Kosten des direkten Weges vom Knoten n zum Zielknoten. Verfolgen Sie keine Pfade weiter, wenn bekannt ist, dass der Knoten auch durch gleiche oder geringere Kosten erreicht werden kann. Verfolgen Sie auch keine Pfade, die zurück zum vorgelagerten Knoten führen. 1. Der Planer expandiert jeweils den Knoten n, bei dem die Evalutionsfunktion h(n) minimal ist. 2. Der Planer expandiert jeweils den Knoten n, bei dem die Evalutionsfunktion f (n) = g(n) + h(n) minimal ist. Wie heißen die Algorithmen, die die beiden Planer verwenden? Onlinefrage Nr. 4: Wie lange ist die vom zweiten Planer ermittelte Wegstrecke? (a) 187 (b) 121 (c) 115 4.d Zeichnen Sie das Voronoi-Diagramm (in grober Annäherung, nicht exakt) zu dieser Hinderniskonstellation ein. Betrachten Sie hierbei jede Seite des Begrenzungsrahmens als ein Hindernis. 5 - Quaternionen 5.a Gegeben sei das Quaternion q1 = (s, (x, y, z)) = (1, (2, 7, −1)). Berechnen Sie das multiplikativ inverse Quaternion q1−1 . 5.b √ Rotieren Sie den Punkt ~ x = (1, 1, 1) mit dem Quaternion q2 = ( √ 2 , ( 22 , 0, 0)). 2 5.c Onlinefrage Nr. 5: Welche Arten von Koordinatentransformationen lassen sich durch Quaternionen darstellen? (a) nur Translationen (b) nur Rotationen (c) Translationen und Rotationen 4
© Copyright 2024 ExpyDoc
