Diese Seite auf Downloads Acknowledgements References Who Is Who in Planning Miscellaneous
Automatic Generation of State Sets from Domain Specifications

In state based planning, it is assumed that forward application of an operator to a valid state results in a valid state again. This property is used to verify the admissibility of states of a plan that has been created by uncertain planning, e.g. in regression planning or by planning with incomplete state descriptions. This verification is done by forward application of the found operations beginning from a complete and correct predefined initial state. Therefore at least one complete state description is necessary.
The diploma thesis introduces an approach to create the complete and correct state set of a planning domain only from the operators and a given set of objects (constants). Additionally, a recursive procedure for extending an existing state set by adding new objects is introduced.
Eventually, it is discussed, under which circumstances it is possible not only to recursively extend the state set but also the state space, and therfore to enable expansion of plans.



Dr. Ute Schmid was a super advisor. She was all ears whenever I needed support and often shared with me some of my enthusiasm. Thank's, Ute.
Prof. Dr. F.Wysotzki unbureaucratically supported me where needed.
My colleques from the diploma seminar helped me in discussions, with editorial notes and with lots of fun. Those having had an earlier deadline than me I want to thank for their diploma thesis' functioning as models for mine.
In alphabetical order: Karin Böhnke, Martin Mühlpfordt, Marina Müller, Heike Pisch, Uwe Sinha, Janin Toussant, Ulrich Wagner, Jürgen Winkler.
(Have a look at their work).
The more I worked on the diploma thesis and the nearer the deadline came, the more chaotic it looked around my desk. My dog Frieda was bored all day and looked reproachfully at me (you certainly know, that only dogs can look that reproachful!). Susanne solaced her and also kept away from me all the other problems a student suffers from ;-). Well, I think I love her even more than I did for the last 15 years.


This is the complete reference of my diploma thesis. Entries having a magnifying glass beside them are papers on related work.
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

This is a short (and of course incomplete) list of people doing research in planning. Sorry to all the people not mentioned.

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


DPlan - a universal regression planner.
AIPS 2000 Planning Competition