This page in Downloads Danksagung Literaturverzeichnis Wer ist Wer in der Planung Verschiedenes
Automatische Generierung von Zustandsmengen aus Domainspezifikationen

Beim zustandsbasierten Planen wird davon ausgegangen, dass die Vorwärtsanwendung eines Operators auf einen gültigen Zustand wiederum einen gültigen Zustand erzeugt. Diese Eigenschaft wird ausgenutzt, um bei unsicherer Anwendung eines Operators, z.B. bei der Rückwärtsplanung oder beim Planen mit unvollständigen Zustandsbeschreibungen, die Gültigkeit von Zuständen eines Plans dadurch zu prüfen, dass von einem vorgegebenen korrekten Anfangszustand durch Vorwärtsanwendung der gefundenen Operationen der Plan verifiziert wird. Dieses Vorgehen bedarf aber immer mindestens einer vollständigen Zustandsbeschreibung. Im Vortrag wird ein Verfahren vorgestellt, das es ermöglicht, allein anhand der Operatoren und einer vorgegebenen Menge von Objekten (Konstanten) die vollständige und korrekte Menge von Zuständen einer Planungsdomäne zu erzeugen. Darauf aufbauend wird ein rekursives Verfahren entwickelt, mit dessen Hilfe eine bereits existierende Zustandsmenge durch Hinzufügen weiterer Objekte erweitert werden kann. Schließlich wird untersucht, unter welchen Umständen es möglich ist, nicht nur die Zustandsmenge, sondern auch den Zustandsraum rekursiv zu expandieren und somit auch die Expansion von Plänen zu ermöglichen.

Downloads

Danksagung

Dr. Ute Schmid war eine Spitzenbetreuung. Sie hatte immer ein offenes Ohr, wenn ich Unterstützung brauchte und teilte immer etwas meiner Begeisterung. Danke Ute.
Prof. Dr. F.Wysotzki unterstützte mich stets unbürokratiasch, wann immer das nötig war.
Meine Kollegen vom Diplomanden-Kolloquium halfen mir stets in Diskussionen, durch Korrekturlesen und mit jeder Menge Spaß. Diejengen, deren Abgabetermin vor meinem lag möchte ich für ihre Diplomarbeiten danken, die mir als Vorlage dienten.
In alphabetischer Reihenfolge: Karin Böhnke, Martin Mühlpfordt, Marina Müller, Heike Pisch, Uwe Sinha, Janin Toussant, Ulrich Wagner, Jürgen Winkler.
(Man werfe einen Blick auf ihre Arbeit.) Je länger ich an der Diplomarbeit arbeitete und je näher der Abgabetermin rückte, desto chaotischer wurde es rund um meinen Schreibtisch. Mein Hund Frieda langweilte sich den ganzen Tag und sah mich vorwurfsvoll an (ihr wisst sicherlich, dass nur Hunde so vorwurfsvoll gucken können!). Susanne tröstete sie und hielt auch all die täglichen Probleme von mir fern. Ich denke, ich liebe sie noch mehr als ich es in den letzten 15 Jahren getan habe.

Literaturverzeichnis

Dies ist das vollständige Literaturverzeichnis meiner Diplomarbeit. Einträge, die mit einer Lupe markiert sind, beschäftigen sich mit verwandten Themen.
Aho, A.V., and J.D.Ullman. Informatik: Datenstrukturen und Konzepte der Abstraktion. International Thomson Publishing.1996
Anderson, C., D.Weld and D.Smith. Conditional Effects in Graphplan. In: Proceedings of the 4th International Conference Artificial Intelligence, 1998
Bryant, R.E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams. CMU-CS-92-160, Carnegie Mellon University, 1992
Blum, A., and M. Furst. Fast Planning Through Planning Graph Analysis. In: Artificial Intelligence, 90:281-300, 1997
Bonet, B., and H. Geffner. HSP: Heuristic Search Planner. Entry at the AIPS-98 Planning Competition, Pittsburgh, 1998
Bonet, B., and H. Geffner. Planning as Heuristic Search: New Results. In: Proceedings of ECP-99, Springer, 1999.
Bonet, B., and H. Geffner. Planning with Incomplete Information as Heuristic Search in Belief Space. In: Proceedings of the 5th Int. Conference on AI Planning and Scheduling (AIPS 2000), AAAI Press, pp 52-61, 2000
Bron, C., and J. Kerbosch. Finding All Cliques of an undirected Graph. In: Collected Algorithms from CACM, Alg.457, 1971
Edelkamp, S., and M. Helmert. Exhibiting Knowledge in Planning Problems to Minimize State Encoding Length. ECP, Durham, pp 135-147, LNAI, Springer, 1999
Fink, E. Automatic Representation Changes in Problem Solving. Doctoral Thesis, CMU-CS-99-150, Carnegie Mellon University, 1999
Ghallab, M., A. Howe et.al. PDDL - The Planning Domain Definition Language, Version 1.2. Technical Report CVC TR-98-003/DCS TR-1165. Yale Center for Computational Vision and Control, 1998
Fox, M., and D.P. Long. The Automatic Inference of State Invariants in TIM. In: Journal of Artificial Intelligence Research, 9:376-421, 1998
Fox, M., and D.P. Long. The Efficient Implementation of the plan-graph in STAN. In: Journal of Artificial Intelligence Research, 10:87-115, 1999
Fox, M., and D.P. Long. The Detection and Exploitation of Symmetry in Planning Domains. Technical Report 1/99, Durham University, 1999
Fikes, R., and N. Nilsson. Strips: A New Approach to the Application of Theorem Proving and Problem Solving. In: Artificial Intelligence, 2:189-208, 1971
Giunchiglia, E., G.N. Kartha and V. Lifschitz. Representing action: Indeterminacy and Ramifications. In: Artificial Intelligence, 95(2):409-438, 1997
Gelfond, M., and V. Lifschitz. Representing Actions and Change by Logic Programs. In: The Journal of Logic Programming, 17:301-322, 1993
Giunchiglia, E., and V. Lifschitz. An action language based on causal explanation: Preliminary Report. In: Proceedings of the 15th National Conference on Artificial Intelligence (AAAI'98), pp 623-630, 1998
Jensen, R.M., OBDD-based Universal Planning in Multi-Agent, Non-Deterministic Domains. Master's Thesis, University of Denmark, 1999
Kautz, H., and B. Selman. Unifying SAT-based and Graph-based Planning. In: Proceedings of the IJCAI '99, Stockholm, 1999
McCarthy, J., and P.J. Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence. In: D.Mitchie. Machine Intelligence 4. American Elsevier, New York, 1969
Nebel, B. On the Compilability and Expressive Power of Propositional Planning Formalisms. In: Journal of Artificial Intelligence Research, 12:271-315, 2000
Pednault, E. ADL: Exploring the Middle Ground Between STRIPS and the Situation Calculus. In: Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning, pp 324-332, 1989
Pardalos, P.M. An Algorithm for Finding the Maximum Clique on an Arbitrary Graph. University of Florida, 1997
Penberthy, J., and D. Weld. UCPOP: A Sound, Complete, Partial-Order Planner. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning, University of Washington, 1992
Pardalos, P.M., and J. Xue. The Maximum Clique Problem. In: Journal of Global Optimization, 4:301-328, 1994.
Schoppers, M.J. Universal Plans for Reactive Robots in Unpredictable Environments. In: IJCAI '87, pp 1039-1046, 1987
Schmid, U. Iterative Macro-Operators Revisited: Applying Program Synthesis to Learning in Planning. Technical Report CMU-CS-99-114, Carnegie Mellon University, 1999
Schmid, U. and Wysotzki, F. Applying Inductive Program Synthesis to Learning Domain-Dependent Control Knowledge - Transforming Plans into Programs. Technical Report CMU-CS-00-143, Carnegie Mellon University 2000

Who Is Who in Planning

Dies ist eine kurze (und natürlich unvollständige) Liste von Menschen, die Forschung im Bereich der Planung betreiben. Ich entschuldige mich bei allen Leuten, die nicht genannt werden.

A.Blum, Carnegie Mellon University, Pittsburgh
B.Bonet, Universidad Simon Bolivar, Caracas
S.Edelkamp, Universität Freiburg
M.Fox, University of Durham
M. Furst, Carnegie Mellon University, Pittsburgh
H.Geffner, Universidad Simon Bolivar, Caracas
H.Kautz, University of Washington
J.Köhler, Universität Freiburg
D.P.Long, University of Durham
D.McDermott, Yale University, New Haven
B.Nebel, Universität Freiburg
U.Schmid, TU Berlin
B.Selman, Cornell University, Ithaca
D.Weld, University of Washington
F.Wysotzki, TU Berlin

Verschiedenes

DPlan - ein universeller Rückwärtsplaner.
AIPS 2000 Planungswettbewerb