Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

Autor/Titel Begriff Zusammenfassung Metadaten
Norvig I 156
Planung/Künstliche Intelligenz/Norvig/Russell: Die Unvorhersehbarkeit und Teilbeobachtbarkeit realer Umgebungen wurde frühzeitig in Robotikprojekten, die Planungstechniken benutzten, wie Shakey (Fikes et al., 1972)(1) und FREDDY (Michie, 1974)(2), erkannt. Die Probleme erhielten mehr Aufmerksamkeit nach der Veröffentlichung von McDermotts (1978a) einflussreichem Artikel, Planning and Acting(3). >Belief States/Norvig.
Norvig I 366
Probleme: Ein einfacher problemlösender Agent (...) kann Handlungsabläufe finden, die zu einem Zielzustand führen. Aber er setzt sich mit atomaren Repräsentationen von Zuständen auseinander und benötigt daher eine gute domänenspezifische Heuristik, um gut funktionieren zu können. [Ein] hybrid propositional-logischer Agent (...) kann Pläne ohne domänenspezifische Heuristiken finden, da er domänenunabhängige Heuristiken verwendet, die auf der logischen Struktur des Problems basieren. Aber er basiert auf der variablenfreien (...) Inferenz von Propositionen, was bedeutet, dass er überfordert werden kann, wenn es viele Handlungen und Zustände gibt.
Norvig I 367
Planungsforscher haben sich auf eine gewichtete Darstellung festgelegt - eine, in der ein Zustand der Welt durch eine Sammlung von Variablen repräsentiert wird. Wir verwenden eine Sprache namens PDDL, die Planning Domain Definition Language, die es uns ermöglicht, alle 4Tn2-Handlungen mit einem Handlungsschema auszudrücken. Jeder Zustand wird als eine Verbindung von Fluenten dargestellt, die variablenfreie, funktionslose Atome sind. Es wird die Datenbanksemantik verwendet: Die closed-world assumption (Annahme zur Weltabgeschlossenheit) bedeutet, dass alle nicht erwähnten Fluenten falsch sind, und die unique names assumption bedeutet, dass [x]1 und [x]2 unterschiedlich sind. Handlungen werden durch eine Reihe von Handlungsschemata beschrieben, die implizit die Funktionen ACTIONS(s) und RESULT(s,a) definieren, die für eine Problemlösungssuche erforderlich sind. >Rahmenproblem.
Die klassische Planung konzentriert sich auf Probleme, bei denen die meisten Maßnahmen die meisten Dinge unverändert lassen.
Handlungen: Ein Set von (...) variablenfreien Handlungen kann durch ein einziges Handlungsschema dargestellt werden.
Das Schema ist eine angehobene Repräsentation - sie hebt die Ebene der Schlussfolgerung von der Aussagenlogik auf eine begrenzte Teilmenge der Logik erster Stufe an.
Handlungsschema: Das Schema besteht aus dem Handlungsnamen, einer Liste aller im Schema verwendeten Variablen, einer Vorbedingung und einem Effekt.
Norvig I 367
Vorwärts-/Rückwärtssuche (Progression/Regression) im Zustandsraum: Vgl. >Vorwärtsverkettung, >Rückwärtsverkettung.
Norvig I 376
Heuristiken für die Planung: Eine heuristische Funktion h(s) schätzt die Entfernung von einem Zustand s zum Ziel und dass, wenn wir für diese Entfernung eine zulässige Heuristik ableiten können - eine, die nicht überschätzt - dann können wir die A*-Suche zum Finden optimaler Lösungen nutzen.
Repräsentation: Die Planung verwendet eine gewichtete Repräsentation für Zustände und Handlungsschemata. Dies ermöglicht es, gute domänenunabhängige Heuristiken zu definieren und Programmen, automatisch eine gute domänenunabhängige Heuristik für ein bestimmtes Problem anzuwenden. Stellen Sie sich ein Suchproblem als einen Graphen vor, bei dem die Knoten Zustände und die Kanten Handlungen sind. Das Problem besteht darin, einen Pfad zu finden, der den Ausgangszustand mit einem Zielzustand verbindet. Es gibt zwei Möglichkeiten, dieses Problem zu lockern, um es einfacher zu machen: durch Hinzufügen von mehr Kanten zum Graphen, um es einfacher zu machen, einen Pfad zu finden, oder durch Gruppieren mehrerer Knoten, die eine Abstraktion des Zustandsraums bilden, der weniger Zustände hat und somit einfacher zu suchen ist.
Norvig I 377
Zustandsabstraktion: Viele Planungsprobleme haben 10100 oder mehr Zustände, und die Lockerung der Handlungen trägt nicht dazu bei, die Anzahl der Zustände zu reduzieren. Daher betrachten wir nun Lockerungen, die die Anzahl der Zustände verringern, indem sie eine Zustandsabstraktion bilden - ein many-to-one mapping von Zuständen in der variablenfreien Repräsentation des Problems auf die abstrakte Darstellung. Die einfachste Form der Zustandsabstraktion ist es, einige Fluente zu ignorieren.
Norvig I 378
Heuristiken: Eine Schlüsselidee bei der Definition von Heuristiken ist die Zerlegung: ein Problem in Teile zerlegen, jedes Teil unabhängig lösen und dann die Teile kombinieren. Die subgoal independence assumption ist, dass die Kosten für die Lösung einer Verbindung von Teilzielen durch die Summe der Kosten für die jeweils unabhängige Lösung jedes Teilziels approximiert werden.
Norvig I 390
Planung als constraint satisfaction: Siehe >Constraint-Satisfaction-Probleme.

Norvig I 393
Geschichte der KI-Planung: Die KI-Planung entstand aus Untersuchungen zur Suche von Zustandsraum, zum Nachweis von Theoremen und zur Kontrolltheorie sowie aus den praktischen Anforderungen der Robotik, Terminplanung und anderer Bereiche.
STRIPS (Fikes and Nilsson, 1971)(4), das erste große Planungssystem, veranschaulicht das Zusammenspiel dieser Einflüsse.
General Problem Solver/GPS: der General Problem Solver (Newell and Simon, 1961)(5),[war] ein System zur Suche von Zustandsraum, das die Means–End-Analyse verwendete. Die Kontrollstruktur von STRIPS wurde der von GPS nachempfunden.
Norvig I 394
Sprache: Die Problem Domain Description Language, kurz PDDL (Ghallab et al., 1998)(6), wurde als von Computern lesbare, standardisierte Syntax zur Darstellung von Planungsproblemen eingeführt und wird seit 1998 als Standardsprache für die International Planning Competition verwendet. Es gab mehrere Erweiterungen; die neueste Version, PDDL 3.0, enthält plan constraints und Präferenzen (Gerevini und Long, 2005)(7).
Teilprobleme: Die Problemzerlegung wurde erreicht, indem für jedes Teilziel ein Teilplan berechnet und die Teilpläne dann in einer bestimmten Reihenfolge aneinandergereiht wurden. Dieser Ansatz, von Sacerdoti (1975)(8) als lineare Planung bezeichnet, wurde bald als unvollständig erkannt. Es kann einige sehr einfache Probleme nicht lösen (....) Ein vollständiger Planer muss die Verschachtelung von Handlungen aus verschiedenen Teilplänen innerhalb einer einzigen Sequenz ermöglichen. Der Begriff der serializable subgoals (Korf, 1987)(9) entspricht genau dem Set von Problemen, für welche die nicht-verschachtelten Planer vollständig sind. Eine Lösung für das Verschachtelungsproblem war das goal-regression planning, eine Technik, bei der Schritte in einem vollständig geordneten Plan neu geordnet werden, um Konflikte zwischen Teilzielen zu vermeiden. Dies wurde von Waldinger (1975)(10) eingeführt und auch von Warrens (1974)(11) WARPLAN verwendet.
Partial Ordering: Die Ideen, welche dem Partial-Order Planning zugrundeliegen, umfassen die Erkennung von Konflikten (Tate, 1975a)(12) und den Schutz der erreichten Bedingungen vor Störungen (Sussman, 1975)(13). Die Konstruktion von teilweise geordneten Plänen (damals noch Task-Netzwerke genannt) wurde vom NOAH-Planer (Sacerdoti, 1975(8), 1977(14)) und von Tates (1975b(15), 1977(16)) NONLIN-System vorangetrieben. Partial-order planning dominierte die nächsten 20 Jahre der Forschung (...).
State-space planning: Das wieder auflebende Interesse an State-space planning wurde durch Drew McDermotts UNPOP-Programm (1996)(17) vorangetrieben, das als erstes die ignore-delete-list heuristic vorschlug (...). Bonet und Geffners Heuristic Search Planner (HSP) und seine späteren Derivative (Bonet und Geffner, 1999(18); Haslum et al., 2005(19); Haslum, 2006(20)) waren die ersten,
Norvig I 395
welche state-space search praktisch für große Planungsprobleme machten. Der bisher erfolgreichste state-space searcher ist FF (Hoffmann, 2001(21); Hoffmann und Nebel, 2001(22); Hoffmann, 2005(23)), Gewinner des AIPS 2000 Planungswettbewerbs. LAMA (Richter und Westphal, 2008)(24), ein Planer auf Basis von FASTDOWNWARD mit verbesserter Heuristik, gewann den Wettbewerb 2008. >Umwelt/Welt/Planung/Norvig. Siehe auch McDermot (1985)(25).



1. Fikes, R. E., Hart, P. E., and Nilsson, N. J. (1972). Learning and executing generalized robot plans. AIJ,3(4), 251-288
2. Michie, D. (1974). Machine intelligence at Edinburgh. In On Intelligence, pp. 143–155. Edinburgh
University Press.
3. McDermott, D. (1978a). Planning and acting. Cognitive Science, 2(2), 71-109.
4. Fikes, R. E. and Nilsson, N. J. (1993). STRIPS, a retrospective. AIJ, 59(1–2), 227-232.
5. Newell, A. and Simon, H. A. (1961). GPS, a program that simulates human thought. In Billing, H.
(Ed.), Lernende Automaten, pp. 109-124. R. Oldenbourg.
6. Ghallab, M., Howe, A., Knoblock, C. A., and Mc-Dermott, D. (1998). PDDL—The planning domain definition language. Tech. rep. DCS TR-1165, Yale Center for Computational Vision and Control
7. Gerevini, A. and Long, D. (2005). Plan constraints and preferences in PDDL3. Tech. rep., Dept. of Electronics for Automation, University of Brescia, Italy
8. Sacerdoti, E. D. (1975). The nonlinear nature of plans. In IJCAI-75, pp. 206-214.
9. Korf, R. E. (1987). Planning as search: A quantitative approach. AIJ, 33(1), 65-88
10. Waldinger, R. (1975). Achieving several goals simultaneously. In Elcock, E. W. and Michie, D.
(Eds.), Machine Intelligence 8, pp. 94-138. Ellis Horwood
11. Warren, D. H. D. (1974). WARPLAN: A System for Generating Plans. Department of Computational
Logic Memo 76, University of Edinburgh
12. Tate, A. (1975a). Interacting goals and their use. In IJCAI-75, pp. 215-218.
13. Sussman, G. J. (1975). A Computer Model of Skill Acquisition. Elsevier/North-Holland.
14. Sacerdoti, E. D. (1977). A Structure for Plans and Behavior. Elsevier/North-Holland.
15. Tate, A. (1975b). Using Goal Structure to Direct Search in a Problem Solver. Ph.D. thesis, University of Edinburgh.
16. Tate, A. (1977). Generating project networks. In IJCAI-77, pp. 888-893.
17. McDermott, D. (1996). A heuristic estimator for means-ends analysis in planning. In ICAPS-96, pp.
142-149.
18. Bonet, B. and Geffner, H. (1999). Planning as heuristic search: New results. In ECP-99, pp. 360-372.
19. Haslum, P., Bonet, B., and Geffner, H. (2005). New admissible heuristics for domain-independent planning. In AAAI-05.
20. Haslum, P. (2006). Improving heuristics through relaxed search – An analysis of TP4 and HSP*a in the
2004 planning competition. JAIR, 25, 233-267.
21. Hoffmann, J. (2001). FF: The fast-forward planning system. AIMag, 22(3), 57-62.
22. Hoffmann, J. and Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. JAIR, 14, 253-302.
23. Hoffmann, J. (2005). Where “ignoring delete lists” works: Local search topology in planning benchmarks. JAIR, 24, 685-758
24. Richter, S. and Westphal, M. (2008). The LAMA planner. In Proc. International Planning Competition at ICAPS.
25. McDermott, D. (1985). Reasoning about plans. In Hobbs, J. and Moore, R. (Eds.), Formal theories of the commonsense world. Intellect Books.


_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders.
Der Hinweis [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] ist eine Hinzufügung des Lexikons der Argumente.
KI-Forschung

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z