YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

German subtitles

← Unit 2, Topic 2, Route Finding Question

Unit 2, Topic 2, Route Finding Question

Get Embed Code
20 Languages

Showing Revision 1 created 10/13/2011 by Amara Bot.

  1. Die Antwort ist nein -

  2. der Agent kann keine Lösung entwickeln,
  3. da Bucharest nicht auf der Karte enthalten ist.
  4. Daher weiß der Agent nicht, welche Aktion ihn dorthin bringen könnte.
  5. Deswegen geben wir dem Agenten nun eine bessere Chance.
  6. Nun haben wir dem Agenten die komplette Karte von Rumänien gegeben.
  7. Anfangs befindet er sich in Arad und das Ziel ist Bucharest.
  8. Und dem Agenten wird dieses Problem präsentiert und er muss mit einer Reihe von Aktionen
  9. am Ziel ankommen.
  10. Ist es nun für den Agenten möglich das Problem zu lösen?
  11. Und die Antwort lautet: Ja.
  12. Es gibt mehrere Wege oder Schritte oder Sequenzen von Aktionen, die zum Ziel führen.
  13. Hier ist eine:
  14. Angefangen in Arad machen wir zunächst diesen Schritt, dann diesen und dann diesen,
  15. dann diesen und abschließend diesen um am Ziel anzukommen.
  16. Das wäre eine gültige Lösung des Problems.
  17. Also garantiert uns eine Reihe von Aktionen, die nacheinander ausgeführt werden, das Ziel zu erreichen.
  18. [DEFINITION EINES PROBLEMS]
  19. Nun definieren wir formal, wie ein Problem aussieht.
  20. Ein Problem kann in mehrere Bestandteile unterteilt werden.
  21. Zunächst gibt es den initialen Zustand, mit dem der Agent startet. [INITIAL STATE]
  22. Der initiale Zustand des Agenten unseres Wegfindungsproblems war die Stadt Arad.
  23. Als Nächstes eine Aktionsfunktion [ACTIONS (s) {a1,a2,a3...}], die einen Zustand als Input erhält und
  24. eine Menge möglicher Aktionen, die der Agent ausführen kann, zurückliefert, wenn der Agent sich in diesem Zustand befindet.
  25. [ACTIONS (s) {a1,a2,a3...}]
  26. Bei einigen Problemen kann der Agent in allen Zuständen die selben Aktionen ausführen
  27. und bei anderen Problemen kann der Agent in Abhängigkeit vom Zustand unterschiedliche Aktionen ausführen.
  28. Beim Wegfindungsproblem sind die Aktionen abhängig vom Zustand.
  29. Wenn wir uns in einer Stadt befinden, können wir in benachbarte Städte gelangen,
  30. aber in keine anderen Städte.
  31. Als Nächstes haben wir eine Ergebnisfunktion [RESULT (s,a) s1], die als Input einen Zustand und eine Aktion erhält
  32. und als Resultat einen neuen Zustand liefert.
  33. Beispielsweise, wenn der Agent in der Stadt Arad ist und wir dies als seinen Zustand betrachten
  34. und als Aktion das Fahren entlang der Straße E-671 Richtung Timisoara sehen,
  35. dann wäre das Ergebnis, wenn man die Aktion auf den Zustand Arad anwendet, ein neuer Zustand,
  36. bei dem sich der Agent in der Stadt Timisoara befinden würde.
  37. Nun brauchen wir eine Zieltestfunktion [GOAL TEST (s) T/F],
  38. die einen Zustand als Input erhält und einen Boolschen Wert,
  39. also wahr oder falsch, zurückliefert. Dieser Wert sagt uns, ob dieser Zustand das Ziel ist oder nicht.
  40. Bei einem Wegfindungsproblem wäre das einzige Ziel das Erreichen des Zielorts -
  41. die Stadt Bucharest - und alle anderen Zustände würden beim Zieltest falsch zurückliefern.
  42. Und abschließend brauchen wir noch eine Pfadkostenfunktion,
  43. die als Eingabe einen Pfad, also eine Sequenz von Zustand/Aktion-Übergängen enthält
  44. und liefert eine Zahl zurück, die den Kosten für diesen diesen Pfad entsprechen. [PFADKOSTEN]
  45. Für die meisten Probleme, mit denen wir uns beschäftigen, machen wir die Pfadkostenfunktion additiv,
  46. so dass die Pfadkosten die Summe der Kosten der einzelnen Schritte sind.
  47. Und daher setzen wir die Pfadkostenfunktion als Schrittkostenfunktion um.
  48. Die Schrittkostenfunktion erhält als Eingabeparameter einen Zustand, eine Aktion und den daraus resultierenden Zustand
  49. und liefert eine Nummer n zurück, welche die Kosten dieser Aktion darstellt. [STEP COST (s,a,s1)=n]
  50. Im Wegfindungsbeispiel könnten die Kosten die Anzahl der zurückgelegten Kilometer darstellen
  51. oder aber die benötigte Zeit in Minuten, die man braucht um dorthin zu gelangen.