Philosophie Lexikon der Argumente

Home

Screenshot Tabelle Begriffe

Autor/Titel Begriff Zusammenfassung Metadaten
Norvig I 401
Umwelt/Planung/reale Welt/Repräsentation/Künstliche Intelligenz/Norvig / Russell: Algorithmen für die Planung (...) erweitern sowohl die Repräsentationssprache als auch die Art und Weise, wie der Planer mit der Umwelt interagiert. >Planung/Norvig, >Agenten/Norvig.
Neu: [wir haben jetzt] a) Handlungen mit Dauer und b) Pläne, die hierarchisch organisiert sind.
Hierarchie: Die Hierarchie eignet sich auch für eine effiziente Plankonstruktion, da der Planer ein Problem auf einer abstrakten Ebene lösen kann, bevor er sich mit Details beschäftigt.
1. Ansatz: "Zuerst planen, dann schedulen": (...) Wir teilen das Gesamtproblem in eine Planungsphase, in der Handlungen mit einigen ordering constraints ausgewählt werden, um die Ziele des Problems zu erreichen, und eine spätere Schedulingphase, in der dem Plan zeitliche Informationen hinzugefügt werden, um sicherzustellen, dass er die Ressourcen- und Deadline-Constraints erfüllt.
Norvig I 404
Kritischer Pfad (critical path): Mathematisch gesehen sind Critical-Path-Probleme leicht zu lösen, da sie als eine Konjunktion linearer Ungleichungen auf der Start- und Endzeit definiert sind. Wenn wir resource constraints einführen, werden die daraus resultierenden Constraints der Start- und Endzeiten komplizierter.
Norvig I 405
Scheduling: Der "cannot overlap"-Constraint ist eine Disjunktion von zwei linearen Ungleichungen, eine für jede mögliche Ordnung. Die Einführung von Disjunktionen führt dazu, dass die Planung mit resource constraints NP-schwer wird. >NP-Probleme.
Nicht überlappend: [Wenn wir von Nichtüberlappung ausgehen,] kann jedes Scheduling-Problem durch eine nicht überlappende Sequenz gelöst werden, die alle Ressourcenkonflikte vermeidet, vorausgesetzt, dass jede Handlung für sich allein durchführbar ist. Wenn sich ein Scheduling-Problem jedoch als sehr schwierig erweist, ist es vielleicht keine gute Idee, es auf diese Weise zu lösen - es kann besser sein, die Handlungen und Einschränkungen zu überdenken, falls dies zu einem viel einfacheren Scheduling-Problem führt. Daher ist es sinnvoll, Planung und Scheduling unter Berücksichtigung von Laufzeiten und Überschneidungen bei der Erstellung eines partial-order plan zu integrieren.
Heuristiken: partial-order planners können Verletzungen von resource constraints auf ähnliche Weise erkennen wie Konflikte mit kausalen Zusammenhängen. Heuristiken können entwickelt werden, um die insgesamt benötigt Zeit zur Ausführung eines Plans abzuschätzen. Dies ist derzeit ein aktives Forschungsgebiet (siehe unten).
Norvig I 406
Planung in der Praxis: KI-Systeme werden wahrscheinlich das tun müssen, was der Mensch zu tun scheint: auf höheren Abstraktionsebenen planen. Ein vernünftiger Plan für den Hawaii-Urlaub könnte sein: "Fahre zum Flughafen San Francisco (...)" ((n), der in einer anderen Richtung liegen könnte). (...) Planung kann sowohl vor als auch während der Ausführung des Plans erfolgen (...).
Lösung: hierarchische Zerlegung: hierarchische Aufgabennetzwerke (hierarchical task networks - HTN).
Norvig I 407
Ein hochrangiger Plan erreicht das Ziel aus einem gegebenen Zustand heraus, wenn mindestens eine seiner Implementierungen das Ziel aus diesem Zustand erreicht. Der "mindestens eine" in dieser Definition ist entscheidend - nicht alle Implementierungen müssen das Ziel erreichen, denn der Agent kann
Norvig I 408
entscheiden, welche Implementierungen er ausführen wird. So ist die Menge der möglichen Implementierungen in der HTN-Planung - von denen jede ein anderes Ergebnis haben kann - nicht die gleiche wie die Menge der möglichen Ergebnisse in der nicht-deterministischen Planung. Es kann gezeigt werden, dass die richtige Sammlung von HLAs (high level actions) dazu führen kann, dass die zeitliche Komplexität der blinden Suche von exponentiell in der Lösungstiefe auf linear in der Lösungstiefe sinkt, obwohl die Entwicklung einer solchen Sammlung von HLAs in sich eine nicht-triviale Aufgabe sein kann.
Norvig I 409
Plan-Bibliothek: Der Schlüssel zur HTN-Planung ist daher der Aufbau einer Planbibliothek mit bekannten Methoden zur Umsetzung komplexer, hochrangiger Maßnahmen. Eine Methode zum Aufbau der Bibliothek besteht darin, die Methoden aus der Erfahrung der Problemlösung zu lernen. (Repräsentation/KI-Forschung, >Lernen/KI-Forschung).
Lernen/AI: Auf diese Weise kann der Agent im Laufe der Zeit immer kompetenter werden, da neue Methoden auf alten Methoden aufbauen. Ein wichtiger Aspekt dieses Lernprozesses ist die Fähigkeit, die konstruierten Methoden zu verallgemeinern und Details zu eliminieren, die spezifisch für die Probleminstanz sind (....).
Norvig I 410
Nichtdeterministisches Handeln: Problem: Die Verfeinerung nach unten ist viel zu konservativ für eine reale Umgebung. Siehe >Terminologie/Norvig für "dämonischen Nichtdeterminismus" (demonic nondeterminism) und "engelhaften Nichtdeterminismus"(angelic nondeterminism).
Norvig I 411
Erreichbare Sets: Die Grundidee ist, dass der Agent wählen kann, in welchem Teil des erreichbaren Sets er endet, wenn er die HLA ausführt; somit ist eine HLA mit mehreren Verfeinerungen "mächtiger" als die gleiche HLA mit weniger Verfeinerungen. Der Begriff der erreichbaren Sets ergibt einen einfachen Algorithmus: Suche unter high level plans und schaue nach einem, dessen erreichbares Set sich mit dem Ziel überschneidet; sobald das passiert, kann sich der Algorithmus auf diesen abstrakten Plan festlegen, in dem Wissen, dass er funktioniert, und sich auf die weitere Verfeinerung des Plans konzentrieren.
Norvig I 415
Unbekannte Umgebung / Planung / nichtdeterministische Bereiche: [Probleme sind hier] sensorlose Planung (auch bekannt als konforme Planung) für Umgebungen ohne Beobachtungen; Notfallplanung für teilweise beobachtbare und nichtdeterministische Umgebungen; und Online-Planung und Neuplanung für unbekannte Umgebungen.
Norvig I 417
Sensorlose Planung: In der klassischen Planung, in der die Closed world assumption getroffen wird, würden wir davon ausgehen, dass jeder Fluent, der nicht in einem Zustand erwähnt wird, falsch ist, aber in der sensorlosen (und teilweise beobachtbaren) Planung müssen wir zu einer Open world assumption wechseln, in der Zustände sowohl positive als auch negative Worte enthalten, und wenn ein Fluent nicht erscheint, ist sein Wert unbekannt. So entspricht der Belief State genau dem Satz möglicher Welten, die die Formel erfüllen.
Norvig I 423
Online-Neuplanung: Der Online-Agent hat die Wahl, wie sorgfältig er die Umgebung überwacht. Wir unterscheiden drei Ebenen: a) Handlungsüberwachung: Vor der Ausführung einer Handlung überprüft der Agent, ob alle Voraussetzungen noch erfüllt sind, b) Planüberwachung: Vor der Ausführung einer Handlung überprüft der Agent, ob der verbleibende Plan noch erfolgreich ist, c) Zielüberwachung: Vor der Ausführung einer Handlung überprüft der Agent, ob es ein besseres Set von Zielen gibt, den er zu erreichen versuchen könnte.
Norvig I 425
Multi-Agenten-Planung: Ein Mehrkörpersystem ist nach wie vor ein "standardmäßiges" Einzelkörperproblem, solange die von jedem Körper gesammelten relevanten Sensorinformationen - entweder zentral oder innerhalb jedes Körpers - zu einer gemeinsamen Schätzung des Weltzustands zusammengefasst werden können, die dann die Ausführung des Gesamtplans bestimmt; in diesem Fall agieren die Mehrkörper als ein Einzelkörper. Wenn Kommunikations-Constraints dies unmöglich machen, haben wir
Norvig I 426
ein so genanntes dezentrales Planungsproblem: (...) Der für jeden Körper erstellte Teilplan muss möglicherweise explizite kommunikative Handlungen mit anderen Körpern beinhalten.
Norvig I 429
Konvention: Eine Konvention ist jede Einschränkung bei der Auswahl gemeinsamer Pläne.
Kommunikation: In Ermangelung einer Konvention können die Agenten die Kommunikation nutzen, um gemeinsame Kenntnisse über einen durchführbaren gemeinsamen Plan zu erlangen.
Planerkennung: Funktioniert, wenn eine einzelne Handlung (oder eine kurze Folge von Handlungen) ausreicht, um einen gemeinsamen Plan eindeutig festzulegen. Beachten Sie, dass die Kommunikation sowohl mit konkurrierenden Agenten als auch mit kooperativen Agenten funktionieren kann.
Norvig I 430
Die schwierigsten Mehragentenprobleme betreffen sowohl die Zusammenarbeit mit Mitgliedern des eigenen Teams als auch den Wettbewerb mit Mitgliedern gegnerischer Teams, alles ohne zentrale Kontrolle.
Norvig I 431
Zeitliche Constraints in Plänen: Die Planung mit Zeitvorgaben wurde zunächst von DEVISER durchgeführt (Vere, 1983(1)). Die Darstellung von Zeit in Plänen wurde von Allen (1984(2)) und von Dean et al. (1990)(3) im FORBIN-System behandelt. NONLIN+ (Tate and Whiter, 1984)(4) und SIPE (Wilkins, 1988(5), 1990(6)) konnten die Aufteilung der begrenzten Ressourcen auf verschiedene Planschritte erörtern.
Vorwärts-Zustandsraumsuche: Die beiden Planer SAPA (Do und Kambhampati, 2001)(7) und T4 (Haslum und Geffner, 2001)(8) nutzten beide die Vorwärts-Zustandsraumsuche mit ausgefeilter Heuristik, um Handlungen mit Dauer und Ressourcen zu handhaben.
Menschliche Heuristiken: Eine Alternative besteht darin, sehr ausdrucksstarke Handlungssprachen zu verwenden, sie aber durch von Menschen geschriebene domänenspezifische Heuristiken zu leiten, wie es bei ASPEN (Fukunaga et al., 1997)(9), HSTS (Jonsson et al., 2000)(10) und IxTeT (Ghallab and Laruelle, 1994)(11) geschieht.
Norvig I 432
Hybride Planungs- und Schedulingsysteme: ISIS (Fox et al., 1982(12); Fox, 1990(13)) wurde für die Arbeitsplanung bei Westinghouse verwendet, GARI (Descotte und Latombe, 1985)(14) plante die machinelle Bearbeitung und Konstruktion von mechanischen Teilen, FORBIN wurde für die Werkskontrolle und NONLIN+ für die Marinelogistikplanung verwendet. Wir haben uns dafür entschieden, Planung und Scheduling als zwei getrennte Probleme darzustellen; (Cushing et al., 2007)(15) zeigen, dass dies bei bestimmten Problemen zu Unvollständigkeit führen kann.
Scheduling: Die Literatur zu Scheduling wird in einem klassischen Überblicksartikel (Lawler et al., 1993)(16), einem aktuellen Buch (Pinedo, 2008)(17) und einem überarbeiteten Handbuch (Blazewicz et al., 2007)(18) vorgestellt.
Abstraktionshierarchie: Das ABSTRIPS-System (Sacerdoti, 1974)(19) führte die Idee einer Abstraktionshierarchie ein, wonach die Planung auf höheren Ebenen untergeordnete Handlungsvoraussetzungen ignorieren durfte, um die allgemeine Struktur eines Arbeitsplans abzuleiten. Austin Tates Doktorarbeit (1975b) und die Arbeit von Earl Sacerdoti (1977)(20) entwickelten die Grundgedanken der HTN-Planung in ihrer modernen Form. Viele praktische Planer, darunter O-PLAN und SIPE, sind HTN-Planer. Yang (1990)(21) diskutiert die Eigenschaften von Handlungen, die die HTN-Planung effizient machen. Erol, Hendler und Nau (1994(22), 1996(23)) präsentieren einen kompletten hierarchischen Zerlegungsplaner sowie eine Reihe von Komplexitätsergebnissen für reine HTN-Planer. Unsere Präsentation von HLAs und angelischer Semantik (angelic semantics) ist auf Marthi et al. zurückzuführen (2007(24), 2008(25)). Kambhampati et al. (1998)(26) haben einen Ansatz vorgeschlagen, bei dem Zerlegungen nur eine weitere Form der Planverfeinerung sind, ähnlich den Verfeinerungen für nicht-hierarchisches partial-order planning.
Erklärungsbasiertes Lernen: Die Technik des erklärungsbasierten Lernens (...) wurde in mehreren Systemen als Mittel zur Verallgemeinerung zuvor berechneter Pläne angewendet, darunter SOAR (Laird et al., 1986)(27) und PRODIGY (Carbonell et al., 1989)(28).
Fallbasierte Planung: Ein alternativer Ansatz besteht darin, zuvor berechnete Pläne in ihrer ursprünglichen Form zu speichern und sie dann wiederzuverwenden, um neue, ähnliche Probleme analog zum ursprünglichen Problem zu lösen. Dies ist der Ansatz des Forschungsbereichs Fallbasierte Planung (Carbonell, 1983(29); Alterman, 1988(30); Hammond, 1989(31)). Kambhampati (1994)(32) argumentiert, dass die fallbezogene Planung als eine Form der Verfeinerungsplanung analysiert werden sollte und bietet eine formale Grundlage für fallbezogenes partial-order planning.
Norvig I 433
Konforme Planung: Goldman und Boddy (1996)(33) führten den Begriff konforme Planung ein und stellten fest, dass sensorlose Pläne oft effektiv sind, selbst wenn der Agent Sensoren hat. Der erste mäßig effiziente konforme Planer war Smith and Weld's (1998)(34) Conformant Graphplan oder CGP. Ferraris und Giunchiglia (2000)(35) und Rintanen (1999)(36) entwickelten unabhängig voneinander SATPLAN-basierte konforme Planer. Bonet und Geffner (2000)(37) beschreiben einen konformen Planer, der auf heuristischer Suche im Raum der >Belief States (...) basiert.
Norvig I 434
Reaktive Planung: Mitte der 80er Jahre führte der Pessimismus über die langsamen Laufzeiten von Planungssystemen zum Vorschlag von Reflexagenten, die als reaktive Planungssysteme bezeichnet werden (Brooks, 1986(38); Agre and Chapman, 1987)(39). PENGI (Agre and Chapman, 1987)(39) konnte ein (vollständig beobachtbares) Videospiel spielen, indem es Boolesche Schaltkreise in Kombination mit einer "visuellen" Repräsentation aktueller Ziele und des internen Zustands des Agenten verwendete.
Richtlinien: "Universelle Pläne" (Schoppers, 1987(40), 1989(41)) wurden als eine Methode der Lookup-Tabellen für die reaktive Planung entwickelt, erwiesen sich aber als Wiederentdeckung der Idee von Richtlinien, die lange Zeit in Markovs Entscheidungsprozessen verwendet wurden (...). >Open Universe/KI-Forschung).



1. Vere, S. A. (1983). Planning in time: Windows and durations for activities and goals. PAMI, 5, 246-267.
2. Allen, J. F. (1984). Towards a general theory of action and time. AIJ, 23, 123-154.
3. Dean, T., Kanazawa, K., and Shewchuk, J. (1990). Prediction, observation and estimation in planning and control. In 5th IEEE International Symposium on Intelligent Control, Vol. 2, pp. 645-650.
4. Tate, A. and Whiter, A. M. (1984). Planning with multiple resource constraints and an application to a naval planning problem. In Proc. First Conference on AI Applications, pp. 410-416.
5. Wilkins, D. E. (1988). Practical Planning: Extending the AI Planning Paradigm. Morgan Kaufmann.
6. Wilkins, D. E. (1990). Can AI planners solve practical problems? Computational Intelligence, 6(4), 232-246.
7. Do, M. B. and Kambhampati, S. (2003). Planning as constraint satisfaction: solving the planning graph by compiling it into CSP. AIJ, 132(2), 151-182.
8. Haslum, P. and Geffner, H. (2001). Heuristic planning with time and resources. In Proc. IJCAI-01 Workshop on Planning with Resources.
9. Fukunaga, A. S., Rabideau, G., Chien, S., and Yan, D. (1997). ASPEN: A framework for automated planning and scheduling of spacecraft control and operations. In Proc. International Symposium on AI,
Robotics and Automation in Space, pp. 181-187.
10. Jonsson, A., Morris, P., Muscettola, N., Rajan, K., and Smith, B. (2000). Planning in interplanetary space: Theory and practice. In AIPS-00, pp. 177-186.
11. Ghallab, M. and Laruelle, H. (1994). Representation and control in IxTeT, a temporal planner. In AIPS-94, pp. 61-67.
12. Fox, M. S., Allen, B., and Strohm, G. (1982). Job shop scheduling: An investigation in constraint directed reasoning. In AAAI-82, pp. 155-158.
13. Fox, M. S. (1990). Constraint-guided scheduling: A short history of research at CMU. Computers in
Industry, 14(1–3), 79-88
14. Descotte, Y. and Latombe, J.-C. (1985). Making compromises among antagonist constraints in a planner. AIJ, 27, 183–217.
15. Cushing,W., Kambhampati, S.,Mausam, and Weld, D. S. (2007). When is temporal planning really temporal? In IJCAI-07.
16. Lawler, E. L., Lenstra, J. K., Kan, A., and Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. In Graves, S. C., Zipkin, P. H., and Kan, A. H. G. R. (Eds.), Logistics of Production and Inventory: Handbooks in Operations Research and Management Science, Volume 4, pp. 445 - 522. North-Holland.
17. Pinedo, M. (2008). Scheduling: Theory, Algorithms, and Systems. Springer Verlag.
18. Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., and Weglarz, J. (2007). Handbook on Scheduling: Models and Methods for Advanced Planning (International Handbooks on Information Systems). Springer-Verlag New York, Inc.
19. Sacerdoti, E. D. (1974). Planning in a hierarchy of abstraction spaces. AIJ, 5(2), 115–135.
20. Sacerdoti, E. D. (1977). A Structure for Plans and Behavior. Elsevier/North-Holland
21. Yang, Q. (1990). Formalizing planning knowledge for hierarchical planning. Computational Intelligence, 6, 12–24.
22. Erol, K., Hendler, J., and Nau, D. S. (1994). HTN planning: Complexity and expressivity. In AAAI-94,
pp. 1123–1128.
23. Erol, K., Hendler, J., and Nau, D. S. (1996). Complexity results for HTN planning. AIJ, 18(1), 69–93.
24. Marthi, B., Russell, S. J., and Wolfe, J. (2007). Angelic semantics for high-level actions. In ICAPS-07.
25. Marthi, B., Russell, S. J., and Wolfe, J. (2008). Angelic hierarchical planning: Optimal and online algorithms. In ICAPS-08.
26. Kambhampati, S., Mali, A. D., and Srivastava, B. (1998). Hybrid planning for partially hierarchical domains. In AAAI-98, pp. 882–888.
27. Laird, J., Rosenbloom, P. S., and Newell, A. (1986). Chunking in Soar: The anatomy of a general learning mechanism. Machine Learning, 1, 11–46.
28. Carbonell, J. G., Knoblock, C. A., and Minton, S. (1989). PRODIGY: An integrated architecture for planning and learning. Technical report CMU-CS- 89-189, Computer Science Department, Carnegie-
Mellon University.
29. Carbonell, J. G. (1983). Derivational analogy and its role in problem solving. In AAAI-83, pp. 64–69.
30. Alterman, R. (1988). Adaptive planning. Cognitive Science, 12, 393–422.
31. Hammond, K. (1989). Case-Based Planning: Viewing Planning as a Memory Task. Academic Press.
32. Kambhampati, S. (1994). Exploiting causal structure to control retrieval and refitting during plan reuse. Computational Intelligence, 10, 213–244
33. Goldman, R. and Boddy, M. (1996). Expressive planning and explicit knowledge. In AIPS-96, pp. 110–117.
34. Goldman, R. and Boddy, M. (1996). Expressive planning and explicit knowledge. In AIPS-96, pp. 110–117.
35. Smith, D. E. and Weld, D. S. (1998). Conformant Graphplan. In AAAI-98, pp. 889–896.
36. Rintanen, J. (1999). Improvements to the evaluation of quantified Boolean formulae. In IJCAI-99,
pp. 1192–1197.
37. Bonet, B. and Geffner, H. (2005). An algorithm better than AO∗? In AAAI-05.
38. Brooks, R. A. (1986). A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation, 2, 14–23.
39. Agre, P. E. and Chapman, D. (1987). Pengi: an implementation of a theory of activity. In IJCAI-87, pp. 268–272.
40. Schoppers, M. J. (1987). Universal plans for reactive robots in unpredictable environments. In IJCAI-
87, pp. 1039–1046.
41. Schoppers, M. J. (1989). In defense of reaction plans as caches. AIMag, 10(4), 51–60.


_____________
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