Automatic Generation of State Sets
from Domain Specifications
Diploma Thesis
of
Bernhard Wolf
10th October 2000
Advisors:
Prof. Dr. Fritz Wysotzki
Dr. Ute Schmid
Technical University of Berlin
Department of Computer Science
Institute of Applied Computer Science
Artificial Intelligence Group
Abstract
This work introduces an approach which makes it possible to create a complete and correct set of states for a predefined planning domain without having any planning problem defined. It is worked out which information comes with an initial state and how this information can be retrieved without this state. Further on, the approach is developed to a recursive procedure enabling extension of already known domain instances by adding additional objects. Eventually, it is shown under which circumstances the state space of a domain instance can also be extended when a new object is added.
Acknowledgements
I want to thank all people having accompanied the present work. First of all, I am grateful to Ute Schmid who was very engaged in advising me and encouraged me when I thought to fail. She was all ears whenever I developed a new theory or brought along one of those fascinating state space graphs. She always gave me the feeling of doing enormously important work.
I want to thank Prof. Fritz Wysotzki, who supported me all the times, not only in view of administrative problems.
My colleagues from the diploma seminar, Karin Böhnke, Martin Mühlpfordt, Marina Müller, Heike Pisch, Uwe Sinha, Janin Toussant, Ulrich Wagner and Jürgen Winkler, I want to thank for their interest, their editorial notes and, of course, for the fun we had on our restaurant excursions. Special thanks go to Marina for the invention of the word “vernudeln” – we rarely laughed that loud.
Last but not least I want to thank Susanne who never understood a word of what I was doing but always was patient and – especially in the last weeks - kept away from me all those daily problems. I’m afraid, my dog Frieda will not understand why I spent that few time with her, but I hope I can make up for it.
Contents
1 Introduction
2 Domain Analysis and Plan Construction
2.1Planning Domain Definition Languages
2.1.1 STRIPS
2.1.2PDDL
2.1.3 Other Domain Definition Languages
2.2State Based Planning
2.2.1 Admissibility of States and Universal Planning
2.2.2 State and State Space Analysis
2.3Domain Analysis
2.3.1 Balanced Atoms
2.3.2 Type Inference and State Invariants
3 Generating States from Domain Specifications
3.1Creating the Complete State Set from the Operators
3.2How to Find Complete and Correct State Descriptions
3.2.1Properties of the Adjacency Matrix
3.2.2Using the Adjacency Matrix to Build States
3.3Limits of the Approach
3.4Extending the Approach to a Recursive Procedure
4 Algorithmic Realization and Results
4.1Creating the Set of Facts
4.1.1Type Correctness
4.1.2Equality Constraints
4.1.3Verifying the Correct Set of Static Facts
4.2Creating the Set of Operations
4.2.1Conditional Effects
4.2.2Operation Enchaining
4.3Creating the Adjacency Matrix
4.4Creating the Set of States
4.5The Recursive Approach
4.5.1 Extending State Spaces
5 Conclusion and Further Work
Bibliography
A Domain Specifications
A.1 Ferry
A.2 Blocks-World
A.3 Briefcase
A.4 Rocket
A.5 Hanoi
A.6 Travel
A.7 Monkey
A.8 Life
B Realization of the Introduced Algorithms
B.1Creation of the Domain Instance
B.2Construction of the Adjacency Matrix
B.3Creation of the Set of States
B.4Varying the Set of Static Facts
B.5An Example of the Recursive Approach
C Notes on the Implementation
1
1
Chapter 1
Introduction
“...; dass ich erkenne, was die Welt im Innersten zusammenhält.“
Faust. Der Tragödie erster Teil. 1.Akt, 1.Szene
In the real world making a plan means to consider in which order which things must be done to reach a certain goal. If we make a plan we will therefore have to be sure about some properties of the world. We have to know which objects exist, for we will not be able to do something with things that are not available. It does not make sense to make a plan for riding a unicorn in a world where unicorns do not exist.
Further on, we have to know, what we can do with the existing things. Some actions make sense, some don’t and some may even be impossible. Of course, parking one’s car in the river may be possible but is not very useful, whereas parking the car in the dog kennel will in most cases be impossible. But why do people normally not sink their car in the river or damage the kennel? Well, the answer is, that they learn about it when they grow up. Somebody tells them not to do such stupid things.
In the artificial world of planning systems, we create a model of the real world, which only consists of the relevant facts and relations needed to make up a certain plan. In this model, called a planning domain, objects and actions must be defined before being able to use them for making a plan. Objects therefore have a set of possible properties and may stand in various relations to other objects. At each point in time, the properties of an object will be well defined, and so will be the relations to other objects.
As in the real world, the relation between the objects and the properties of an object change by acting in a certain way. To be able to do so, some conditions must meet. Think of driving a car from the street into the garage. To do so, we at first have to have a car, which must be in the street, and further we need an empty garage to drive the car into. These so called preconditions are specified when we define an operator, which in a planning domain enables us to drive a car into a garage. In addition, we define what happens to the involved objects (the car, the street, the garage), when applying this operator: the car is not longer in the street, but in the garage, the garage is not empty any longer, etc.
1
CHAPTER 1. INTRODUCTION1
The question that raises is, how we can prevent our car from being parked in the dog kennel by a planning program working on our domain. The planner cannot learn but only can apply the given operators. The answer is that we have to define the planning domain in a way that enables the planner to act in a reasonable way. This means that we have to make the operators acting in the way we want them to act.
At first, we have to specify which actions at all can take place in a planning domain. As an example, we would never define an operator that enables a car to be sunk in the river.
Further on, we have to ensure that certain actions can only be applied to a specific type of objects, e.g. that only cars can be driven into garages, but not streets, kennels or even garages themselves. To support such behavior, planning domains make use of typing the objects. With this solution we are able to specify that cars cannot be parked in kennels.
Having taken this considerations into account, it should be true, that only reasonable actions take place.
If we have defined an operator to drive a car from the street into the garage, aren’t we then able to infer that there must be a state of the world, where a car stands in the street, as well as there must be a state where the same car is in the garage rather than in the street, so that we can use the operator to transfer the world from the former state into the latter? There is no reason why we should not consider these states to exist. Disregarding states that we can neither change nor make true, we should be able to infer all states of a planning domain that may exist for a given set of objects, which we will prove in this work.
A section of the real world is never cut off from the rest of the world, whereas a model of the world always is a closed off generalization of this section, which shows itself in leaving away some of the details of the real world. But it is true, that regardless of whether or not we model a second car in our domain, the first car may be driven into the garage, as long as the second car does not stand in the garage at that time. So if we extended the modeled world in the way that we add objects to it, the objects of the former world should be able to have the same properties and relations as before and may have additional relations to the new objects.
In current planning research the objects of a planning problem are given with an initial state that describes the state of the world at the beginning of the planning process. Therefore this set of objects is fixed and with the given set of operators all states that may ever occur can be found from analyzing the operators. Such analysis is nowadays made to increase the efficiency of the planning process. We can often find repeated sequences of actions, for example if we drive 20 cars into 20 garages. From the definitions of the operators we may for example find, that the person driving the car may only drive one car at a time, and so on.
On the other hand, little work is done on the aspect, that a world with 20 cars is just an extension of the world with 19 cars, which eventually is an extension of a world with one car or even no car at all. And further on, a world with zero cars, a street and a garage is an extension of a world with the one and only object named street. This work will investigate in detail the relation between both the states and the state transitions of different instances of a planning domain, which mainly differ in the set of involved objects.
The diploma thesis is structured as follows. In chapter 2, actual used domain definition languages are introduced. We shed some light on particular problems of state based planning regarding to the admissibility of states and discuss solutions of other researchers. In chapter 3, we at first make the definitions needed to discuss our approach, which is then proved. The benefits and limitations are worked out and the approach will be extended to a recursive procedure. Chapter 4 introduces the used algorithms and gives some examples of the realization of our attitude. Eventually, we will discuss the conclusions in chapter 5. Appendix A contains the used domain definitions, whereas appendix B gives examples of the introduced algorithms. In appendix C we make some notes on the implementation.
Chapter 2
Domain Analysis and Plan Construction
The great majority of today’s planners are state based planners, i.e. planning is done as a search in the state space of a given problem. To do so, progression planners start with an initial state and by successively applying operations develop a partial state space until the plan reaches a state matching the goal description. Regression planners do the same, but start from the goal description and plan backwards to the initial state. The main difference between the various planning systems lies in the algorithms used to do this search. There are, of course, many reasons to support specific algorithms, as optimality of the plan or the computation time for creating a plan.
The power of planning systems not only depends on the algorithms used to search the state space (or the plan space, respectively), but is mainly restricted to the expressiveness of the used planning domain definition language.
2.1Planning Domain Definition Languages
The reason why there are at all different languages to define planning domains, is that together with the expressiveness often comes a lack of efficiency. The most expressive way of defining a planning domain is to use statements from the situation calculus [MH69]. Unluckily this results in a very clumsy use of so defined operators. For example, we would wish to disregard all objects not being involved in an operation, which is impossible in the situation calculus, where for all objects it must be stated what applies to them (frame axioms).
On the other hand, the most simple way of domain definition is to use STRIPS [FN71].
2.1.1 STRIPS
STRIPS (STanford Research Institute Problem Solver) is at the same time a planner and the definition language that comes along with it. A STRIPS operator is a 3-tuple (op,PREC,EFF) where op is the name and parameter list of the operator, whereas PREC is a set of positive
1
CHAPTER 2.DOMAIN ANALYSIS AND PLAN CONSTRUCTION1
literals (atoms)[1]. EFF is divided into two sets ADD and DEL, each consisting of atoms. Applying op to a state s is possible if there exists an instance of PREC that is a complete subset of s. In that case the operation is applied by adding the instantiated atoms (facts) of ADD and removing the instantiated atoms (facts) of DEL from s.
The expressiveness of STRIPS is very poor, although we are able to define a large number of domains with it.
For example, we cannot make use of conditional effects, which is a powerful way of increasing efficiency by doing the work of several unconditioned operators within a single one. Serializing an operator with conditional effects to a set of unconditioned operators may be of exponential effort (see [AWS98]), and it may even be impossible to do so, as Nebel proved in [N00].
The use of quantifiers is not supported by STRIPS, which makes it impossible to define as simple operators as
operator:get_wet()
precondition: rains()
effect:p.wet(p)
which models the fact that all people become wet if it rains.
2.1.2PDDL
As a compromise between the situation calculus and STRIPS, ADL was introduced by Pednault [P89]. Combining the expressiveness of the situation calculus and the easy-to-use notation of STRIPS, it has become the basis of the most important domain description language that is in use today: PDDL (Planning Domain Definition Language).
PDDL was introduced in [GH98] as the mandatory language for the AIPS’98 planning competition. It is based on the language used for the planner UCPOP (see [PW92]) and mainly supports the complete range of expressions coming along with ADL.
To support a wide range of planners, PDDL provides a set of so called requirement flags, which makes it possible for a planner to decide whether or not it is capable of the expressions used in the domain. These flags include capabilities like equality constraints, typing, use of quantifiers, disjunctive expressions, function application, domain axioms or conditional effects.
There are few planners supporting all of the possible requirements. We can mainly distinguish between two groups of planners, those capable of the :strips requirement and those supporting :adl (which is the combination of :strips, :equality, :typing, :conditional-effects, :quantified-precondition and disjunctive-precondition), or at least a relevant subset of it.
Our approach is not a planner yet, but it works on PDDL V1.2 domains and is fully capable of the :adl requirements.
2.1.3Other Domain Definition Languages
There are some other domain definition languages for special purposes. To model non-deterministic domains, there is a family of languages, e.g. A [GL93], AR [GKR97] and C [GL98]. These languages are aimed at expressing non-deterministic operators in an intuitive way and at easily representing environmental changes.
In [J99] Jensen introduced NADL (Non-deterministic Agent Domain Language), which is able to model concurrent operators based on multi-agent domain decomposition.
One of the first and most popular planners, Prodigy, uses an own language, named PDL (Prodigy’s description language), which is very similar to ADL.
2.2State Based Planning
State based planning is the search for a series of operator applications to transfer an initial state into a goal state. The fact that an operator can only be applied to a state if its precondition matches the state, restricts us to have either a complete description of an initial state or a complete description of the goal state. This is true, because we need a complete description for the admissibility check after applying an operator. If we hadn’t, it could happen that we cannot decide whether or not an operator is applicable because we do not have enough information to do so.
If we, for example, use a regression planner to find a plan from an incomplete goal description to an initial state, the initial state must be a complete description, from which we can verify the plan by forward application of the found operations. Otherwise it could happen that we create a plan from an incorrect initial state to an incorrect goal state, because within the plan we used an operator we must not have used.
2.2.1Admissibility of States and Universal Planning
Within the planning process it may happen that incorrect states are created, for example by mismatching the required types of the arguments that come along with the atoms of an operator. This leads to incorrect operations and applying them results in incorrect states.
As long as a single plan from an incomplete goal to a complete initial state is needed, this is no problem, as we mentioned above. When reaching the initial state, we can simply verify the found plan by forward application and remove all wrongly developed plans.
We get a problem when we are universally planning. Universal planning was introduced by Schoppers [Sch87] and means to find all plans from any states to a defined goal description. This is done by a breadth first search over the state space.
If an incomplete goal description leads to incorrect states while planning backwards, we have no possibility to prove this, because with universal planning we have no initial state to check the admissibility of the created plan. We even do not know, whether or not the initial state of a found plan is complete.
There are planners, needing the complete set of states of a domain instance, for example the universal regression planner DPlan [Sch99]. DPlan proves the admissibility of a reached state by looking it up in the given set of states. It further prevents itself from running into cycles, by removing an already visited state from the state set.
Our approach is able to create all correct states of a domain instance, so that admissibility of a state can easily be proved. For we create states from an adjacency matrix, we can also prove the validity of a state description without really creating the complete state set, but by searching the adjacency graph only for the given (partial or complete) state. From a partial state description we are able to create the complete set of states matching this description (or to prove that the description is invalid), so that we enable planners to plan with both incomplete initial states and goal states at the same time.
The state space may be divided into several disjoint subspaces, but such a property has no influence on our approach. We are able to create the complete set of states regardless of whether the state space is a single component graph or not.