Transcript
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])
¨ Ubungsblatt 6 Wissensrepr¨ asentation,Planung und Robotik Abgabe der Onlineaufgaben vor Montag, 18. Juli 2016, 14:00 Uhr Abgabe der schriftlichen Ausarbeitung vor der Saal¨ ubung am 18. Juli 2016, 14:00 Uhr Bonuspunkte fur die Klausur werden nur vergeben, wenn eine schriftliche L¨ osung aller Aufgaben (incl. Onlinefragen) abgegeben wurde Die Antworten auf die Onlinefragen k¨ onnen unter http://wwwiaim.ira.uka.de/websubmit/ eingetragen werden.
Allgemeines ¨ Nach der Ubung werden die Musterl¨ osungen im Internet zug¨ anglich gemacht. Die Aufgaben wer¨ den in der Ubung besprochen. Die Reihenfolge der angegebenen L¨ osungsm¨ oglichkeiten der OnlineAufgaben entspricht nicht zwangsl¨ aufig der Reihenfolge der L¨ osungen 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¨ atze an. Erstellen Sie hierf¨ ur 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¨ oglich) durch Widerspruchsbeweis ab. (i) A,
(ii) B,
(iii) ¬C.
Onlinefrage Nr. 1: Welche Aussage k¨ onnen Sie nicht ableiten? (a) A (b) B (c) ¬C
1
1.c Zeigen Sie mit Hilfe des DPLL-Verfahrens, dass folgende Klauselmenge S erf¨ ullbar ist: ¬C D D E ¬C D
∨ ∨ ∨ ∨ ∨ ∨
¬A ¬E A D ¬A E A
∨ ∨ ∨ ∨ ∨ ∨
B ¬A C B ¬B C
Onlinefrage Nr. 2: F¨ ur welches der folgenden Symbole existiert jeweils f¨ ur alle Belegungen ein Modell, das S erf¨ ullt, 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¨ ur k¨ onnen die Aktionen Load, U nload und T ransport definiert werden. Außerdem werden die zwei Pr¨ adikate In(c, p) und At(x, a) ben¨ otigt. 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¨ ost.
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¨ ucke 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¨ ost.
Aufgabe 3 - Planungsgraph Ein Haushaltsroboter soll in der K¨ uche die Sp¨ ulmaschine bedienen. Hierf¨ ur ist es n¨ otig, dass der Roboter die Sp¨ ulmaschine ¨ offnet, das Geschirr einr¨ aumt und Sp¨ ulmittel
2
einf¨ ullt. F¨ ur den dazu ben¨ otigten Plan wurden folgende Aktionen sowie ein Start- und ein Zielzustand in ADL formuliert: Aktionen: Action(
) Action(
) Action(
Startzustand: Zielzustand:
¨ Sp¨ ulmaschineOffnen(), Vorbed.: ausgeschaltet ∧ ¬ge¨ offnet Effekt: ge¨ offnet GeschirrEinr¨ aumen(), Vorbed.: ge¨ offnet ∧ ¬einger¨ aumt Effekt: einger¨ aumt Sp¨ ulmittelEinf¨ ullen(), Vorbed.: ge¨ offnet ∧ ¬eingef¨ ullt Effekt: eingef¨ ullt
) ausgeschaltet ∧ ¬ge¨ offnet ∧ ¬einger¨ aumt ∧ ¬eingef¨ ullt einger¨ aumt ∧ eingef¨ ullt
Konstruieren Sie zu dieser Planungsaufgabe den Planungsgraphen inklusive aller MutexLinks.
Aufgabe 4 - Bahnplanung Gegeben sei die unten abgebildete Hinderniskonstellation mit einem punktf¨ ormigen 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¨ onnen 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¨ achst graphisch den Konfigurationsraum, den Hindernisraum und den Freiraum. Wie k¨ onnen Sie Hindernis- und Freiraum anpassen, wenn der Roboter zwar einen Durchmesser von d besitzt, Sie aber trotzdem von einem punktf¨ ormigen 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¨ urden. 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¨ uck zum vorgelagerten Knoten f¨ uhren. 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¨ aherung, 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
