Cogsys.uni-bamberg.de
Automatic Generation of State Sets
from Domain Specifications
Diploma Thesis
of
Bernhard Wolf
wolf@cs.tu-berlin.de
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 1
2 Domain Analysis and Plan Construction 4
2.1 Planning Domain Definition Languages 4
2.1.1 STRIPS 4
2.1.2 PDDL 5
2.1.3 Other Domain Definition Languages 6
2.2 State Based Planning 6
2.2.1 Admissibility of States and Universal Planning 6
2.2.2 State and State Space Analysis 7
2.3 Domain Analysis 8
2.3.1 Balanced Atoms 9
2.3.2 Type Inference and State Invariants 9
3 Generating States from Domain Specifications 12
3.1 Creating the Complete State Set from the Operators 17
3.2 How to Find Complete and Correct State Descriptions 20
3.2.1 Properties of the Adjacency Matrix 22
3.2.2 Using the Adjacency Matrix to Build States 26
3.3 Limits of the Approach 33
3.4 Extending the Approach to a Recursive Procedure 35
4 Algorithmic Realization and Results 41
4.1 Creating the Set of Facts 41
4.1.1 Type Correctness 42
4.1.2 Equality Constraints 45
4.1.3 Verifying the Correct Set of Static Facts 47
4.2 Creating the Set of Operations 48
4.2.1 Conditional Effects 49
4.2.2 Operation Enchaining 55
4.3 Creating the Adjacency Matrix 55
4.4 Creating the Set of States 57
4.5 The Recursive Approach 62
4.5.1 Extending State Spaces 66
5 Conclusion and Further Work 74
Bibliography 77
A Domain Specifications 80
A.1 Ferry 80
A.2 Blocks-World 81
A.3 Briefcase 82
A.4 Rocket 83
A.5 Hanoi 83
A.6 Travel 84
A.7 Monkey 85
A.8 Life 86
B Realization of the Introduced Algorithms 87
B.1 Creation of the Domain Instance 87
B.2 Construction of the Adjacency Matrix 91
B.3 Creation of the Set of States 97
B.4 Varying the Set of Static Facts 98
B.5 An Example of the Recursive Approach 99
C Notes on the Implementation 108
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.
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.1 Planning 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
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.2 PDDL
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.3 Other 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 State 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.1 Admissibility 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.
2.2.2 State and State Space Analysis
Some research has been done on analyzing the states and the state space involved in a planning problem. Although we are (yet) not planning with our approach, we can find some similarities between these strategies and our way of generating state descriptions.
Bonet and Geffner introduced a heuristic search in the state space [BG98]. The forward application of operators of the planner HSP is directed by a heuristic, which calculates the costs of adding facts to states. This approach has been developed to a heuristic search over the regression space, i.e. HSPr searches the state space by backward application of operators [BG99]. HSPr relies on the reversibility of operations, which our approach also does (see definition 3.8). Our strategy of creating complete state descriptions also is to add facts by combining operator effects.
HSPr increases the efficiency of the heuristic by exploring mutexes, which are pairs of facts that cannot be combined in a single state. In our approach, this idea has been developed to a more general classification of the compatibility of pairs of facts. We do not restrict to mutexes, but also deal with some kind of semi-mutexes, which are pairs of facts that can be combined only in one direction. Think of the pair ((on a b), (on b c)). This pair is a semi-mutex: it can be combined, but only in the way that (on a b) is added to (on b c), but not vice versa.
In opposite to HSP and HSPr, our approach does not deal with predefined states, but uses the compatibility of facts to create complete and correct state descriptions. The reversibility of operators (which we demand) enables us to use the DEL set of an operator as if it was the ADD set of a reverse operator. The information on the compatibility of facts can be used to direct the search in the same way as it is provided by HSP and HSPr, and enables us to deal with incomplete information while operator application, which Bonet and Geffner discuss in [BG00].
Another interesting connection to our approach comes with the planner STAN [FL99a]. Fox and Long introduced the detection of symmetry in planning problems [FL99b]. These symmetries come along with objects of the same type, playing the same role in the initial state as well as in the goal description. For example, if in a planning problem of the ferry domain, 10 cars shall be shipped from one shore a to another shore b, STAN is able to explore that the partial plan to transfer one of the cars from a to b, is symmetric to the partial plans for transferring the other cars, which results in the decision that it is irrelevant which of the cars to transfer first. This causes a dramatic reduction of the effort needed to construct a complete plan, because otherwise 10! possible combinations of shipping the cars will all result in similar plans.
In our approach to extend the state space of a planning domain instance by adding new objects, we make use of a similar idea. Due to the fact, that two objects of the same type may play the same role, we are able to duplicate state spaces by exchanging objects, i.e. by exchanging the constants within the facts (see chapter 4.5.1). This corresponds with the duplication of partial plans.
3 Domain Analysis
Domain analysis is done to support correct behavior of planners and to increase the efficiency of the planning process. It mainly deals with two aspects, the correct instantiation of atoms and their meaningful combination. While the first aspect is in the first case a matter of typification, the second one analyzes in which way the operators of a domain change the properties and relations of the objects of a state description. State invariants can be inferred telling us something about the compatibility of certain facts.
2.3.1 Balanced Atoms
In [EH99], Edelkamp and Helmert introduce the use of the property of atoms to be balanced for efficiently representing state descriptions in OBDD (Ordered Binary Decision Diagram, see [B92]). An atom is said to be balanced if, regarding to a certain variable of the parameter list, a fixed number of instances occurs in a state description. For example, this applies to (atferry ?x) of the ferry domain, where in a single state description only one instance of the atom (i.e. one substitution of the variable ?x ) occurs. This is represented by the equation
#atferry1() = 1.
The property of being balanced is found from the fact that whenever an instance of the atom is deleted another instance of the same atom is added, where the relevant variable has a different substitution. The sail operator of the ferry domain adds (atferry ?y) and deletes (atferry ?x) (while demanding different instantiations of ?x and ?y).
The number of instances within one state is inferred from the initial state. The fact that an initial state of a planning problem of the ferry domain places the ferry at only one position, together with the fact that any operator involving atferry keeps the number constant, leads to the conclusion that #atferry1() = 1.
In our approach the lack of an initial state leads to the fact that we cannot deal with balanced atoms, if the number of objects for a single variable is greater than one. This means, if the ferry would in all states have to be at two or more positions, we would not be able to infer this property. We think that in most cases this is not a limitation for us, because we hardly find examples of balanced atoms with a balance number greater than 1. Balanced atoms mainly belong to location (or other ordering) properties, which almost always are restricted to uniqueness.
If the initial state description is incomplete the balance property cannot be inferred anyway.
2.3.2 Type Inference and State Invariants
Fox and Long introduced a domain-independent system for inferring object types and state invariants, called TIM (Type Inference Module) [FL98].
Inferring types in untyped domains prevents us from creating invalid facts. Besides the possibility of using typed atoms (as provided by PDDL), a common way of typing is to use type attributes, like (location ?x). Unluckily, type attributes increase the size of the state descriptions, which becomes the more unpractical the more objects exist.
The types TIM is able to infer are not identical to the types in the normal sense but are also distinguished with respect to the role the objects may have in a particular situation. For example, TIM makes a distinction between the intact wheel and the flattened one in the tyre-world domain.
Our approach is only able to infer those types provided by type attributes (or a generic type object), which is simply done by using the predicate of a static unary atom as type for its one and only argument. With this procedure we can of course not handle all the domains TIM is able to deal with. On the other hand, our procedure for creating states is independent from static facts, so we will not suffer from loss of efficiency when the number of static facts increases. After inferring the types we remove all static facts from the operators but typify the variables instead. For this reason we can dispense with the type attributes in the state descriptions, but need them in the descriptions of the operators.
TIM is able to infer four kinds of state invariants. In [FL98] the following examples are given from the rocket domain (1-3) and the gripper domain (4):
1. Identity invariant (x: Tk.(y.(z.( at(x, y) ( at(x, z) ( y = z)[2]
2. State membership invariant (x: Tk.( (y: Tn.at(x, y) ( (y: Tm.in(x, y) )
3. Uniqueness invariant (x: Tk.(( ( y: Tn.at(x, y) ( (y: Tm.in(x, y) )
4. Fixed resource invariant | { x: at_robot( x ) } | = 1
The first invariant means that a thing x cannot be at more than one place at a time, which is a special case of the third invariant, which tells us that a thing x cannot be at a place and in the rocket at the same time. The state membership invariant eventually tells us that a thing x must either be at a place or in the rocket. The fourth invariant from the gripper domain restricts the robot to be at most at one place.
For pairs of facts (i.e. pairs of instantiated positive literals), our approach is able to implicitly find the first three kinds of invariants by a single procedure.
In our algorithm, the compatibility of a pair of facts is defined in the way that a pair (p, q) is compatible, if p can be added to a set of facts, from which q is an element. The pair ((at rocket a), (at rocket b)) is incompatible in that sense. For the reverse pair ((at rocket b), (at rocket a)) is of course also incompatible, the proof of these two incompatibilities (with some restriction) corresponds with the first state invariant of TIM. In the same way we can prove that ((at package a), (in package rocket)) is incompatible as well as ((in package rocket), (at package a)), which corresponds with the third state invariant.
Working with ground literals rather than with facts we discover a state to be a maximum set of compatible literals. For pairs of ground literals we can, for example, prove that (((at package a), (in package rocket)) and (((in package rocket), (at package a)) are compatible, because the literals of the first pair occur together in the effect of a load operation, and the facts of the second pair occur together in an unload operation.
Finally, we find that all states we are able to create, contain exactly one of the two positive literals (at package a) and (in package rocket), which corresponds to the second state invariant discovered by TIM.
Our approach is not able to handle the fourth invariant, because we work without having an initial state, which we would need to infer the balance property of an atom. This also restricts our solution of finding the first and third state invariant to the case where | { x: at(x, y) } | =
| { x: in(x, y) } | = 1, because the incompatibilities of the pairs ((at rocket a), (at rocket b)) and ((at rocket b), (at rocket a)) is not equivalent to the expression (at rocket a) ( ((at rocket b).
Fox and Long suggest to generalize the identity invariant to deal with multi-mutex relations rather than with binary mutex relations. This kind of generalization corresponds to the possibility to extend our approach by checking the compatibility of n-tuples instead of pairs of facts (see chapter 3.3).
Chapter 3
Generating States from Domain Specifications
In order to introduce our approach we have to say what a domain specification really is. Domain specifications define operators that are used to transfer one state into another. This is done by manipulating facts which in a specific combination make up a description of the states being transferred. The facts themselves are instances of predefined atoms, where the variables of the atoms are substituted by members of a given set of objects.
For our approach mainly deals with the facts of a domain instance we are going to make some definitions taking this need into account.
Definition 3.1 (Operator) An operator ( = ((0, (0), ..., ((n, (n) is a list of pairs, each consisting of two formulas given in first order logic. These formulas are restricted as follows.
1) (i is a valid expression if (i is an atom. In addition, if (i,1, ..., (i,m are valid expressions, the following expressions are valid, too.
a. ((i,1
b. (i,1 ( (i,m
c. (i,1 ( (i,m
d. (X.(i,1, where X is a set of variables
e. (X.(i,1, where X is a set of variables
f. (i,1 ( (i,2
2) (i is a valid expression if (i is a literal. In addition, if (i,1, ..., (i,m are valid expressions, the following expressions are valid, too.
a. (i,1 ( (i,m
b. (X.(i,1, where X is a set of variables
(0 is called the primary precondition of ( and (0 is called the primary effect of (. The operator is called unconditioned if n = 0. Otherwise the operator is said to have conditional effects.
As we can see, the effect(s) of an operator is/are restricted in the way that it is impossible to have disjunctive expressions. This is necessary to avoid non-deterministic operator effects.
We can now define a domain specification as follows.
Definition 3.2 (Planning Domain Specification) A planning domain specification is a pair
( = (OPS, A). OPS = {(1, ..., (k } is a set of operators and A ={ a1, ..., an } is the set of atoms that are used to build the formulas of (1, ..., (k.
This kind of definition of a planning domain provides an easy way of accessing the atoms of the domain which is useful for us when creating the set of states. But before we can build states we need a set of objects to instantiate the variables of the domain atoms. Instantiating a variable with an object is called a substitution.
Definition 3.3 (Substitution) Given a set of objects O and a set of variables X, a function
( : X ( O is called a substitution (( = { o1/x1, ..., on/xn } ).
The operators we use are able to deal with the almost complete range of possible formulas of first order logic, i.e. the expressions used in the preconditions (and in a restricted way in the effects) may contain conjunctions and disjunctions as well as quantifiers and implications. On the other hand, states are simple sets of ground literals, and we want the instantiated operators also to be defined by such sets so that we easily can transfer states by applying operations to them. Therefore we have to give a very special kind of instance definition.
Definition 3.4 (Instance / Set of Instances) Given an expression E and a substitution (i = {o1/x1, ..., on/xn }, (i(E) = { (i,1(E), ..., ( i,m(E) } is called the set of instances of E w. r. t. substitution (i, where all xj (1 ( j ( n) are substituted by oj. ((E) =(1(E) ( ... ( (k(E) is the set of instances of E and is defined as follows.
( (i=1..k { fi }, if E is an atom. fi is a ground atom built from E with (i.
(i=1..k { e1 ( e2 | e1 ( (i(E1), e2 ( (i(E2) }, if E = E1 ( E2.
(i=1..k [ { e1 ( e2 | e1 ( (i(E1), e2 ( (i(E2) } (
{ e1 ( e2 | e1 ( (i(E1), e2 ( (i((E2) } (
{ e1 ( e2 | e1 ( (i((E1), e2 ( (i(E2) } ], if E = E1 ( E2.
{ e1 ( e2 | e1 ( (1(E’), e2 ( (((E) \ (1(E)) }, if E = (E’
2(i(E’) \ ( , i=1..k, if E = (E’
((E) = ( (i=1..k {( fi }, if E = (E’ and E’ is an atom. fi is a ground atom built from
E’ with (i.
(((E1 ( (E2), if E = ((E1 ( E2)
(((E1 ( (E2), if E = ((E1 ( E2)
((((E’), if E = ((E’
((((E’), if E = ((E’
(( E’ ), if E = ((E’
(( (E1 ( E2), if E = E1 ( E2
( (( E1 ( (E2 ), if E = ((E1 ( E2)
This definition allows us to refer to an instance of an operator in a simple way.
Definition 3.5 (Operator Instance / Operation[3]) Let ( = ((0, (0), ..., ((n, (n) be an operator. For a given substitution ( = { o1/x1, ..., om/xm } the instantiation of one of the ((i, (i) of ( is defined as
(( ((i, (i) ) = (j=1..k ((j((i), (j((i))
We define PRECj,i = (j((i) and EFFj,i = (j((i). With two countable sets
P = 2PRECj,i = { p0, ..., px } and
E = 2EFFj,i = { e0, ..., ex }
the set of operator instances is then defined as
(( ( ) = (j=1..k { (PREC, EFF) | PREC = PRECj,0 ( pi, EFF = EFFj,0 ( ei, i=1..x }
A single instance op ( (( ( ) is called an operation, and with op = (PRECop, EFFop) we define
ADDop = { l | l ( EFFop and l is a positive ground literal }
DELop = { l | (l ( EFFop }
We can now say that op = (PRECop, EFFop) = (PRECop, ADDop, DELop).
Eventually we can define a domain instance.
Definition 3.6 (Planning Domain Instance / Set of Facts) Given a set of objects
O = { o1, ..., om } the instance of a planning domain ( = (OPS, A) is defined as (( (, O ) = (OPOPS,O , FA,O, ŜA,O) with the following properties.
1) OPOPS,O = ( i=1..k (( (i ) with (i ( OPS
2) FA,O = ( i=1..n { f | f = (( an ), an ( A ( [ (op ( OP. an ( EFFop ] }
3) ŜA,O = ( i=1..n { f | f = (( an ), an ( A ( [ (op ( OP. an ( EFFop ] }
FA,O is called the set of non-static facts, whereas ŜA,O is called the set of static facts.
As mentioned, a domain defines operators to manipulate states. States are points in time and in all states the objects of a world have specific properties and stand in specific relations to each other. In the close world of a planning domain these properties and relations are finite and are expressed by the ground literals that can be built from the set of facts of a domain instance.
Definition 3.7 (State Description / State Set) In a domain instance (( (, O ) = (OP, F, Ŝ) with ( = (OPS, A) a description of the properties and relations of the objects of O is called a state description. A state description is a set of ground literals, where positive literals describe properties or relations that hold, and negative ones describe those that do not hold.[4] A state description is said to be complete, if the properties and relations of all objects are given. To a (complete) state description s it applies that s ( 2F(Ŝ. A state description s is called valid if the properties and relations of the objects described in s are consistent regarding to the real world that is modeled. We define S as the set of complete and valid state descriptions. For the set A of atoms and the set O of objects are finite, the set S of states is finite, too.[5]
To change the state, the world of a planning domain instance actually is in, we have to apply an operation to this state. It is clear that not all operations may be applied to all states.
Definition 3.8 (Operator Application / State Transition) Let (( (, O ) = (OP,F,Ŝ) be a planning domain instance with a set of facts F and a set of operations OP. Let S be the set of states of (( (, O ). With si ( S an operation opij ( OP with opij = (PRECop, ADDop, DELop) is applicable to si iff it applies to si that
a. PRECop ( si
b. si ( ADDop = (
c. DELop ( si
The resulting state sj is defined as sj = si ( ADDop \ DELop. We call sj = opij( si ) a state transition from si to sj by applying opij.
We say that the application of opij to si is reversible, because op -1( op( si ) ) = si.
Normally, operations do not have to be reversible, so condition b. and c. would not be demanded. Our approach needs to apply operations forwards and/or backwards and must therefore rely on the assumption that backward application of an operation is the reverse operation of the forward application. Successively applying operations leads us to
Definition 3.9 (State Transition Path) A sequence op01( s0 ), ..., op(n-1)n( sn-1 ) is called a state transition path from s0 to sn. We also write sn = op(n-1)n( ... op01( s0 )...) or
sn = ( s0, [op01, ..., op(n-1)n]).
The complete set of states together with the complete set of operations between these states makes up the state space of a planning domain instance.
Definition 3.10 (State Space) A signed directed graph ( = (S,E) is called a state space (state space graph) if the following properties apply to it.
1) The set S of vertices of ( is the complete set of states of a planning domain instance (( (, O ) = (OP,F,Ŝ).
2) The set E of signed edges of ( is the complete set of tuples (si, sj, opij) with si,sj ( S, opij ( OP and sj = opij( si ).
We now have the definitions needed to introduce our approach. To create the complete state set from the domain description alone makes it necessary to deal with mainly two questions: whether an initial state or goal description[6] is really not needed and how to find states without having any starting point to do so.
Normally, the objects needed to be assigned to the variables of the domain description are implicitly given with the initial state. From this point of view an initial state cannot be omitted. But assuming the objects to be given separately, is there any further functionality of an initial state regarding to the aim of creating the complete and correct state set? Well, there is - in introducing a set of static facts. Think of the travel domain, where some persons and vehicles may only be moved between cities which are connected by roads or bridges. As one can imagine, roads and bridges may differ from one planning problem to another. On the other hand there is no restriction in defining them[7], so the set of these so called statics cannot be inferred from the domain description alone.
We will now show that except from objects and statics no state description is necessary to build the complete and correct set of states of a domain.
1 Creating the Complete State Set from the Operators
Using definition 3.8 we always have a unique reverse operation for all possible operations because it applies to them that ADDop = DELop-1 and DELop = ADDop-1. Therefore, in a single component state space graph we can always give a path from any state si to any other state sj by repeatedly applying forward or backward operations to si, even if one or more edges of this path are of opposite direction. The graph always behaves as if it was undirected and it has been proved that for any pair of nodes there exists at least one path between them where all nodes are mutual exclusive (see for example [AU96]).
We can represent a state s0 ( S as the state transition path from any other state si ( S to s0. As an example we use the state space graph ( from figure 3.1. It applies to s0 that
a. s0 = op10( s1 ) = op01-1
b. s0 = op20( s2 ) = op02-1
c. s0 = op03( op23( s2 ) ) = op03( op32-1( s2 ) )
d. s0 = op20( op32( s3 ) ) = op02-1( op32( s3 ) )
e. s0 = op30( s3 )
As we can see, although we have no operator to get from s1 or s2 to s0, we are able to give a path between these states because of the reversibility of the operations.
It’s important to see that we can find more than one path to get from s3 to s0 as well as from s2 to s0. Doing so we are able to make use of all operations that ever occur in a state transition. This property makes it easier for us to prove that we can create all states from the operators alone. However, it would nevertheless be sufficient to have one path, as we will see later on.
Figure 3.1 Example state space graph ( = ( { s0, s1, s2, s3 },
{ (s0, s1, op01), (s0, s2, op02), (s3, s2, op32), (s3,s0, op30) } )
On the set operation level we can rewrite the above equations and get
a. s0 = s1 ( DEL01 \ ADD01
b. s0 = s2 ( DEL02 \ ADD02
c. s0 = (s2 ( DEL32 \ ADD32) ( ADD03 \ DEL03
d. s0 = (s3 ( ADD32 \ DEL32) ( DEL02 \ ADD02
e. s0 = s3 ( ADD30 \ DEL30[8]
Generalizing these equations, we can now prove the irrelevance of having a complete state given to create the other states, provided that objects and static facts are known.
Fact 3.1 (States as Combination of Operator Effects) Given the set of objects O and the set of static facts ŜA,O there is no need of having predefined a complete state description si ( S to create the complete and correct state set of the single component state space graph ( = (S,E).
Proof.
Let S = { s0, s1, ..., sn }. Without loss of universality we choose s0 as the state to create. As we know, s0 can be represented as a state transition path from all states si, i=1..n.
s0 = ( s1, [op1j, ..., opk0] ) = ... = ( sn, [opnp, ..., opq0] ) (1)
where opij is either a forward operation or the backward operation of opji.
Let f ( s0. To any state transition path ( si, P ) with P = [(PRECi,1, ADDi,1, DEL i,1), ..., (PRECi,m, ADDi,m, DELi,,m)] one of the following conditions applies.
1) m = 0. In this case f ( si holds.
2) m > 0. In this case f ( DELi,,m holds. We distinguish two cases.
a. f ( ADDi,m.
b. f ( ADDi,m.
In this case we prove P’ = [(PRECi,1, ADDi,1, DELi,1), ..., (PRECi,m-1, ADDi,m-1, DELi,m-1)] in s0 = ( si, P’ ) ( ADDi,m \ DELi,m.
We know that f ( si or f ( ADDi,j but not both at the same time because of definition 3.8.
We can now distinguish two cases:
1. (ADDi,j.f ( ADDi,m, j = 1...m, i = 1...n.
In this case it applies to f that(si, i=1..n. f ( si. This means that f is an element of all states and therefore is a static facts per definition. We can remove f from all states because f ( Ŝ holds and Ŝ is given and will be added to all states at last.
2. (ADDi,j.f ( ADDi,j, j = 1...m, i = 1...n.
In this case we can make use of the set property that to two sets M and N it applies that [ M = N ] ( [ (M ( N) = M = N = (N ( M) ]. Therefore we can derive (1) to a single equation
s0 = ( s1, [op1j, ..., opk0] ) ( ... ( ( sn, [opnp, ..., opq0] ) (2)
f is element of one of the ADD sets and will therefore be added from there. Because of this, it is irrelevant whether or not f occurs in any state si and we can remove f from all of these states. Doing this for all fi, all states eventually become empty.
We have shown that all facts that are not static must occur in at least one ADD set of a forward or backward operation. Removing the states (and with them the preconditions of the applied operations) from (1) and adding the static facts we get
s0 = Ŝ ( ( (, [(ADD1j, DEL1j), ..., (ADDk0, DELk0)] )
( ...
( ( (, [(ADDnp, DELnp), ..., (ADDq0, DELq0)] ) (3)
which we can rewrite to
s0 = Ŝ ( [(...(ADD1j \ DEL1j) ( ... ) ( ADDk0 \ DELk0) ]
( ...
( [ (...(ADDnp \ DELnp) ( ... ) ( ADDq0 \ DELq0) ] (4)
We have seen that there is no further functionality in having a state given to create the others but that it is only necessary to predefine the frame of objects and statics for a planning problem. A state has been proved to be a combination of operation effects (except from the static facts which apply to all states). What we have to find out now is, in which order operation effects may be combined.
2 How to Find Complete and Correct State Descriptions
Equation (4) from fact 3.1 shows that for creating a state description the starting point to apply operations to is the empty set. From this starting point we can successively apply operations to create states. What we have to decide then is, which operation may be applied and whether a resulting set of facts is a complete state. The problem is that we do not know whether an operation can be applied to a subset of a state because we may not have all information to decide it. Figure 3.2 gives an example of such a problematic situation. It is taken from a monkey domain instance. The first operation go-to models that the monkey goes from place p1 to another place p2. go-to can only be applied if the monkey is on the floor which is expressed by the predicate on-floor.
The second operation grab-bananas models that the monkey grabs the bananas what she can do if she has a knife and stands on the box which must be at the same place as the bananas, namely at p2.
Figure 3.2 Two operations from a monkey domain instance
When starting with the effect from go-to(p1 p2) we have an initial substate s0’ = { (at the-monkey p2), ((at the-monkey p1), (on-floor) }. On the literal level this substate does not contradict the precondition of the second operation and applying that operation we get a substate s0’ = { (at the-monkey p2), ((at the-monkey p1), (on-floor), (has-knife), (has-bananas), (at-bananas p2), (on-box p2) }. On the level of meaning this of course a contradiction because (on-floor) and (on-box p2) are mutual exclusive: standing on the box while being on the floor is impossible not only for monkeys. If we knew which pairs of facts can be combined we would also know this for the operator effects. We will therefore answer the question of combining effects by answering the question of compatibility of facts. If all facts of a (sub-)state s are compatible with those an operation opij = (PRECij, ADDij, DELij) demands, this operation must be applicable. This is true because we can in that case create a superset s’ of s with s’ = s ( PRECij ( DELij \ ADDij which trivially may be applied by opij.
This approach corresponds with the one from Bonet and Geffner [BG99], who define a mutex in the way that, if adding a fact p to a state s with q ( s is impossible, as well as adding q to a state with p ( s, the facts p and q are mutual exclusive. Our approach is somewhat more specific and distinguishes between adding p to q and vice versa. We are not only interested in mutexes, but also in semi-mutex pairs. What does that mean? There are cases where adding a fact p to a fact q is allowed but adding q to p isn’t. Think of the blocks-world domain. The fact (on a b) can be added to a set of facts where (on b c) is true by applying the operation (put a b). Nevertheless, it is impossible to add (on b c) when (on a b) is valid, because b cannot be put onto c if a already stands on b.
Considering that, we prove the compatibility of two facts as follows.
Fact 3.2 (Compatibility of Facts) Let s be a set of facts. If a fact p is added to s, a second fact q cannot be an element of s ( {p} iff to all operations opij = (PRECij, ADDij, DELij) one of the following propositions applies.
(q ( DELij) (1)
(q ( DELij) ( (q ( PRECij) ( (( t.[(t ( PRECij) ( (t ( DELij)] ( (t ( (q)) (2)
Proof.
(
We show by contradiction that if p cannot be added to a set s with q ( s, (1) or (2) applies to p and q for all operations. Therefore we assume that there exists an operation op = (PREC, ADD, DEL) applicable to s with p( ADD and in the way that both (1) and (2) do not apply to op. Let RES = s ( PREC ( ADD \ DEL. We get
(q ( DEL) (3)
(q ( DEL) ( (q ( PREC) ( (( t.[(t ( PREC) ( (t ( DEL)] ( (t ( (q)) (4)
We can reduce these equations to a single one.
(q ( DEL) ( [(q ( PREC) ( (( t.[(t ( PREC) ( (t ( DEL)] ( (t ( (q))] (5)
From q ( DEL follows that q ( RES. For p ( ADD, we get { p, q } ( RES which is a contradiction to our assumption.
(
We show by contradiction that if (1) or (2) applies to all operations, p cannot be added to a set s with q ( s. Therefore we assume that p can be added to s although one of (1) or (2) applies to all operations. Let op = (PREC, ADD, DEL) be an operation applicable to s with p ( ADD. Let RES = s ( PREC ( ADD \ DEL.
If (1) holds, then q ( RES, which would not fulfil our assumption. Therefore (2) must hold. If (1) is wrong the first subclause of (2) is true, so all we have to prove is that the second and third subclause of (2) also hold. To make the proposition valid we must assume q not to be an element of the precondition and eventually have to check out the correctness of
(( t.[(t ( PREC) ( (t ( DEL)] ( (t ( (q)) (6)
By assumption, op is applicable to s. In that case from (t ( PREC) ( (t ( DEL) follows that t ( s by definition 3.8 and therefore {t, q} ( s. With t ( (q = ((t ( (q) this is a contradiction.
Proving the compatibility of all pairs of facts, we are able to make up an adjacency matrix holding this information.
Definition 3.11 (Adjacency Matrix of Fact Compatibility) For a list of facts F = f1, f2, ..., fn a (n,n)-matrix (F is an adjacency matrix for the compatibility of the facts of F, if to all cells aij of (F it applies that
1, if fi is compatible with fj in the sense of fact 3.2
aij =
0, else
It is clear that all pairs (f,f) will have a zero in the corresponding cell of the adjacency matrix, because from definition 3.8 follows that f cannot be added to a (sub-)state where f is already valid.
Before we can use the information of the adjacency matrix we have to work out some problems with the creation of the matrix because unluckily this is not as easy at it seems.
1 Properties of the Adjacency Matrix
Condition (2) of fact 3.2 makes it necessary for the adjacency matrix to be created by iteration. The proposition (t ( (q) cannot be verified unless the adjacency matrix has made at least some decisions to check the relation between t and q. In most cases we will not be able to verify the compatibility of all pairs of facts within one turn. Think of a fact p that cannot be added to q because for all operations adding p, t is part of the precondition. We can only decide the incompatibility of p and q if the incompatibility of t and q is already known, but it depends on the order of facts which of the decision will be made first. If the incompatibility of p and q is checked first, it cannot be decided and therefore (after finding the incompatibility of t and q) we need a second turn to do so.[9]
Nevertheless, there arise three major problems with the iterative construction of the matrix which we will discuss now.
Interpretation of the Implication
The correct interpretation of the expression (t ( (q) is that the presence of t demands the absence of q and that the presence of q demands the absence of t. Additionally, both t and q may be absent. This holds because (t ( (q) = ((t ( (q).
It is of course clear, that an operation that has t in its precondition cannot be applied to states where q is valid. Unluckily, the adjacency matrix cannot give us this information. The only thing the matrix is able to tell us, is that t cannot be added to q and that q cannot be added to t. That means that there is no operation that is able to combine the two facts, but it does not mean that there cannot be any state where both occur. None of the operations demanding t or q in its precondition could be applied to such a state, but there may be other operations which could.
The reason why we decide that (t ( (q) holds whenever the adjacency matrix contains a zero for both (t, q) and (q, t), is that it is very unlikely that there exist facts in a way that they cannot be combined but which despite from that occur together in one state. If they do so, a couple of operations cannot be applied, and all the others do neither add (or delete) t nor q.
As an example, take the facts (at bmw a) and (on-ferry bmw) from an instance of the ferry domain (see figure 3.3). We are able to prove that (at bmw a) cannot be added to (on-ferry bmw) and vice versa. But that doesn’t mean that they mustn’t occur in one state. If they do, the operation sail(a b) is still applicable. Nevertheless, it is very unlikely to assume the two facts to be compatible and from the point of meaning it really is senseless. Therefore we think that it is a good heuristic for our approach to behave in the described way.
Figure 3.3 Three operations from a ferry domain instance
Weakness of the Domain Operators
In some few cases we can find domains having operators with very weak preconditions in a way that it would be able to work on planning problems that are not intended by the user. The blocks-world domain is such a domain and we will explain the problem using this domain. Therefore have a look at figure 3.4. It shows a puttable operation, where a block b is put from a second block a onto the table. The intention of the blocks-world domain is that blocks can stand on a table or on another block. A block can at most stand on one other block and therefore can also be at most under one block.[10] Despite from this the puttable operator allows a block to stand on more than one other block. A state s with three blocks a, b and c, where b stands on a as well as on c, would be represented by the set s = { (ct b) (on b a) (on b c) }. As we can see, the precondition of the puttable operator matches this state.
Figure 3.4. Three operations from an instance of the blocks-world domain
Our approach therefore allows (on b a) to be added to (on b c) because the backward operation of puttable(b) allows us to do so.
In this domain specification we are able to discover this incorrect behavior. For the puttable operator only takes one argument, namely the block to be put onto the table, it becomes non-deterministic if we allow the block to stand on more than one other block, because we would not know from which of them we should take it away.[11]
We are able to define the domain in a way, that it makes it possible for our approach to create the correct set of states. This definition disables the application of operations to states, where a block stands on more than one block, by extending the preconditions of the operators from the weak blocks-world domain. Both domain specifications are given in appendix A.2.
Mutual Dependencies of Fact Compatibility
Corresponding to fact 3.2 any algorithm to create the adjacency matrix has to decide one of two things for each pair of facts: either if there exists an operation that allows to add the first to the second or if none of the operations does so. Normally we will try to find an operation allowing the combination because if it exists we can immediately stop verifying. But independent from the strategy we get a problem if a pair cannot be decided.
Let (p,q) be the pair to be decided. Think of an operation op1 that adds p. If q is not part of any of the sets of op1, we have to find out whether there is a fact in the precondition of op1 which demands the absence of q. If for a fact t of the precondition the compatibility of, for example, (t,q) is yet unknown, we cannot decide (p,q). In that case we have to verify (t,q) first, but it might be possible that the decision on (t,q) depends on an operation op2, adding t but not saying anything about q. We would then have to check q against the precondition of op2, but what happens if p is part of that precondition? We would have to verify (p,q) and (q,p) to decide on (t,q)! We have found that (p,q) and (t,q) depend on each other and that none of them can be decided without deciding the other. If the former is allowed, the latter is, too, and if the former is forbidden, so is the latter.
Again, the blocks-world domain is an example of such a problematic situation. Have again a look at figure 3.4. We have three operations. The first one puts b onto the table taking it down from a. The second one puts c onto a, taking c away from b. The third one takes b from d and puts it on a. The question whether (ct a) may be added to (on c a) cannot be decided by the operation puttable(b) as long as it is unknown whether (on b a) implies ((on c a). Why that? As we can see, (ct a) is added by puttable(b). (on c a) does not at all occur in this operation. Therefore we have to check (on c a) against the precondition of the operation, that is against (ct b) and against (on b a). While we can easily prove the compatibility of (ct b) and (on c a) (et vice versa) from the put(c a) operation (both are added here), we have a problem in deciding it for (on b a) and (on c a). In the operation put(b a) - which adds (on b a) - nothing is said about (on c a). Checking (on c a) against the precondition of put(b a) raises the question of whether (ct a) implies ((on c a) - which we originally tried to find out.
We found that when it is allowed to add (ct a) to (on c a) it must also be allowed to add (on b a) to (on c a) or if the former is forbidden the latter is, too, which, as we know, is the case.
Mutual dependencies need not be restricted to two pairs of facts, but may also be chains of the form (p,q), (q,t), ..., (u,p), (p,q), where two neighbored pairs have a fact in common. It’s also possible that two or more pairs depend on one single other pair, e.g. (p,q) and (t,q), both depending on (q,u), which itself depends on one of the former pairs. Eventually, it is possible to have more than one set of mutual dependant pairs within one domain.
This is the main problem with automatic generation of the state set from the domain description. There is a useful heuristic, which is in some cases very powerful. It is able to keep the problem as small as possible.[12] We will discuss it in chapter 4.2.
Unluckily we have not found any complete solution to the problem, so we need to interact with the user to retrieve answers to the undecided questions, which we will discuss in chapter 4.3.
2 Using the Adjacency Matrix to Build States
With the information from the adjacency matrix we are able to decide which operation can be applied to an incomplete state. In the example from the monkey domain (see figure 3.2) we are now able to decide that grab-bananas cannot be applied to the substate we created from the go-to operation, because from the adjacency matrix we know that the fact (onbox p2) cannot be added to a set having (on-floor) as one of its elements.
Depending on our aim, we can either create the state set or the state space. We will now introduce both. We will at first assume the state space to be a single component graph, but later on we will show that our approach can also be used with a multiple component state space.
Creating the State Set
Regarding to fact 3.1 we can say that all facts of a state are collected by successively adding them by operation application. On the fact level, we can therefore say that a fact can be added to a set of facts if it is compatible with all of the elements of the latter. This means, that we can simply start with a single fact, add a second one, that is compatible with the first, then add a third one which is compatible with the first and the second, and so on. This procedure is equivalent to searching a complete subgraph (clique) in the adjacency graph that is represented by the matrix. The only thing we have to find out is, in which cases the created set of facts is a complete state. If for example
a. { (intact fridge), (attached backplane fridge) (fridge-on fridge) }
b. { (intact fridge), (attached backplane fridge) }
both represent correct and complete states, it is impossible to decide that the second one is already complete. It may also happen that the maximum subgraph we found is a partial state only, because the order of adding the ground literals doesn’t enable us to create the complete set. We will come back to this later.
We could get rid of the problem if we were able to say that a complete state always is the maximum set that can be created by adding facts. This does of course not apply to our example. But we can use a little trick. If the adjacency matrix would not be made from the facts but from the ground literals created from the facts, then we would get
a. { (intact fridge), (attached backplane fridge) (fridge-on fridge), ... }
b. { (intact fridge), (attached backplane fridge) ((fridge-on fridge), ... }
where both states possibly have some more negative ground literals. The effect is that now all states have the same number of ground literals because for all facts it is true that they are either element of a state or not. Now we have a criterion to terminate the addition of facts, namely the size of the so far created set, which must be equal to the size of the set of facts, if the created set is a complete state. This is equivalent to searching a maximum clique within the adjacency graph. We therefore define a new adjacency matrix that depends on fact 3.3.
Fact 3.3 (Compatibility of Ground Literals) Let s be a set of ground literals. If a literal p is added to s, a second literal q cannot be an element of s ( {p} iff to all operations opij = (PRECij, ADDi, DELi) = (PRECij, EFFij) at least one of the following propositions applies.
((q ( EFFij) (1)
((q ( EFFij) ( (q ( PRECij) ( (( t.[(t ( PRECij) ( ((t ( EFFij)] ( (t ( (q)) (2)
Proof.
Let
RES = { l | (l is a positive ground literal and l ( PREC and l ( DEL) (
(l is a negative ground literal and l ( PREC and (l ( ADD) (
(l ( PREC and l ( EFF) }
(
We show by contradiction that if p cannot be added to a set s with q ( s, (1) or (2) applies to p and q for all operations. Therefore we assume that there exists an operation op = (PREC, ADD, DEL) = (PREC,EFF) applicable to s with p( EFF and in the way that both (1) and (2) do not apply to op. We get
((q ( EFF) (3)
((q ( EFF) ( (q ( PREC) ( (( t.[(t ( PREC) ( ((t ( EFF)] ( (t ( (q)) (4)
We can reduce these equations to a single one.
((q ( EFF) ( [(q ( PREC) ( (( t.[(t ( PREC) ( ((t ( EFF)] ( (t ( (q))] (5)
From (q ( EFF follows that q ( RES. For p ( EFF, we get { p, q } ( RES which is a contradiction to our assumption.
(
We show by contradiction that if (1) or (2) applies to all operations, p cannot be added to a set s with q ( s. Therefore we assume that p can be added to s although one of (1) or (2) applies to all operations. Let op = (PREC, ADD, DEL) = (PREC, EFF) be an operation applicable to s with p( EFF.
If (1) holds, then (q ( RES, from which follows that q ( RES, which would not fulfil our assumption. Therefore (2) must hold. If (1) is wrong the first subclause of (2) is true, so all we have to prove is that the second and third subclause of (2) also hold. To make the proposition valid we must assume q not to be an element of the precondition and eventually have to check out the correctness of
(( t.[(t ( PREC) ( ((t ( EFF)] ( (t ( (q)) (6)
By assumption, op is applicable to s. In that case from (t ( PREC) ( ((t ( EFF) follows that t( s by definition 3.8 and therefore {t, q} ( s. With t ( (q = ((t ( (q) this is a contradiction.
Regarding to fact 3.3 we define the extended adjacency matrix.
Definition 3.12 (Adjacency Matrix of Ground Literal Compatibility) For a list of facts
F = f1, f2, ..., fn a (2n,2n)-matrix (L is an adjacency matrix for the compatibility of the ground literals built from the facts of F, if to all cells aij, a(i+1)j, ai(j+1), a(i+1)(j+1) of (L (i,j=1...n) it applies that
1, if fi is compatible with fj in the sense of fact 3.3
aij =
0, else
1, if (fi is compatible with fj in the sense of fact 3.3
a(i+1)j =
0, else
1, if fi is compatible with (fj in the sense of fact 3.3
ai(j+1) =
0, else
1, if (fi is compatible with (fj in the sense of fact 3.3
a(i+1)(j+1) =
0, else
In this adjacency matrix all pairs (f,(f) and ((f,f) will of course be incompatible. The additional effort to create this extended matrix is very little, because once the pair (p,q) is decided we immediately can decide ((p,q) because of the reversibility of the operations. For the same reason we can decide (p,(q) whenever we have a decision for ((p,(q).
The most interesting property of the extended adjacency matrix is that we do not need to apply operations at all to create the state set, but just have to search the matrix.
In most domains it is unnecessary to create the states from the extended matrix but can be found using the simple one because for each fact there exist another fact being mutual exclusive to the first. For example, in the ferry domain with one car c1 (see figure 3.3), the fact (atferry a) is mutual exclusive to (atferry b) and to c1 it applies that it is exclusively (at c1 a), (at c1 b) or (on-ferry c1). The remaining fact (empty) is mutual exclusive with (on-ferry c1). Therefore all states of this ferry domain instance have the maximum number of facts that can occur together in one state.[13] Unluckily we cannot know that from the beginning or must do some effort to find it out.
The described way of creating states has some considerable disadvantages. If it applies to two ground literals p and q that (p,q) is compatible as well as (q,p), we will create two identical subtrees during the traversal of the matrix, one beginning with p and adding q in the second step, and the other beginning with q and adding p in the second step. If the tree is deep, this will be very inefficient.[14] To avoid this, we have to keep in mind which subsets of facts we ever created, so that we are able to stop further development of a subtree for already known sets of facts. Doing so, we will need lots of resources to hold such information, but there is another disadvantage that is even worse.
If with a planning problem a partial description is given as initial state or goal description (which often is the case), we would like to start searching the adjacency matrix with an already non-empty subset of ground literals, namely the given description. Besides this, we can make another consideration. If we leave singular states[15] out of consideration we can say that for all states there exists an operation that can be applied either forward or backward. Because of this, there exists at least one precondition or result set for all states, which is a subset of that state. Considering that we would like to start searching the adjacency matrix with one of the preconditions or result sets as initial set of facts. In our example from the ferry domain, the precondition of the operation debark(c a) already is a complete state and we will therefore not find any additional compatible fact.
But the problem is that the adjacency matrix represents a directed graph, and therefore it is impossible to guarantee, that we will be able to create all states having a predefined set of facts as subset to start with.
Figure 3.5 A state, the corresponding adjacency matrix and graph
Take a look at the state given in figure 3.5. To create this state it is necessary to add p1 first, then p2 before adding p3 and eventually add p4. In fact, this is the only possibility to create s. If we now predefine an initial subset F = { p2, p3 }, s cannot be created. The reason is that p1 must be added before adding p2 or p3. This is very unfortunate, because finding all possible states matching a given set of facts would be a useful application for the adjacency matrix. What we need is an algorithm, so that it is irrelevant in which order the facts are combined.
Figure 3.6. Adjacency graph of the blocks-world domain instance with 3 blocks
If the graph represented by the adjacency matrix was undirected, there would be an easy way of creating states from given initial sets, namely any of the well-investigated algorithms to find maximum cliques in undirected graphs (see [BK71], [P97], [PX94]). Unluckily not all maximum cliques found by these algorithms are correct states, for the step from directed to undirected edges leads to a loss of information and therefore to incorrect decisions. We already mentioned that the blocks-world domain is a good example for this behavior. Figure 3.6 shows the adjacency graph for the domain instance with three blocks.
If the edges were undirected, { (on a b), (on b c), (on c a) } would for example be a maximum clique, but is actually not representing a correct state. To identify such incorrect cliques we can make a simple recursive test on it. The found set of facts must at least have one fact that can be added to all the others. If it has, to the rest of the facts it again applies, that one of them can be added from the remaining ones. If this test is recursively true for all nodes, the tested clique really is a correct state. The above clique would already fail in the first step of the test.
In chapter 4.4 we will give some examples of creating the state set from the adjacency matrix.
Creating the State Space
The normal way of creating the state space of a domain instance is to start with an initial state and to recursively apply all possible operations, i.e. creating the state space is done by a breadth first search. Planners will stop this procedure if they at some time reach a state matching the goal description, but if the complete state space is needed, we simply go on until no further state can be created.
In our approach there is no initial state, but we are able to create it. We can do this from the adjacency matrix as we described in the above section. With the help of the adjacency matrix we are also able to deal with partial descriptions of an initial state, for we can create all initial states matching this description by searching the matrix beginning with this subset (if it is at all valid). With the so found state (or set of states) we can build the state space in the normal way or search for a plan to reach a state matching a given goal description.
Although not necessary, we can also create a complete state by collecting ground literals while successively applying operations and due to the fact that all complete states must have the same number of literals, namely as much as the number of facts, we know that immediately after applying an operation that produces a resulting set consisting of the maximum number of literals, we have a complete state. We can then build the state space beginning from this state.
This additional effort of building the first complete state is the cost that raises from a missing initial state. To keep the costs as low as possible, we can try to mainly apply operations that increase the number of known literals whenever this is possible. This number increases the faster the smaller the intersection between the so far built substate and the DEL set of the to-be-applied operation is, while at the same time there are as much yet unknown literals as possible in the PREC and ADD set of the operation. This is also a demanded criterion to avoid getting into endless cycles.
As an example we again take the graph from figure 3.1. We may start with op10. It is irrelevant whether the starting operation is applied in forward or backward direction. Here op10 is a backward operation. In figure 3.7 a sample path
p = op03( op23( op02( op10( Ŝ )))) = op03( op32-1( op02( op01-1( Ŝ ))))
is given. After applying op03 the path ends up in a complete state s0[16] which therefore can be identified as
s0 = ((((Ŝ ( DEL01 \ ADD01) ( ADD02 \ DEL02) ( DEL32 \ ADD32) ( ADD03 \ DEL03)
Although we know from fact 3.1 that all facts can be found in the ADD and DEL sets of the operations, we have to take the preconditions into account to check whether an operation is applicable. We can also describe s0 as
s0 = ((((Ŝ ( RES01 ( DEL01 \ ADD01) ( PREC02 ( ADD02 \ DEL02) ( RES32 ( DEL32 \ ADD32) ( PREC03 ( ADD03 \ DEL03)
Figure 3.7 A path to create the state space of ( = ( {s0, s1, s2, s3}, {(s0, s1), (s0, s2), (s3, s2)} )
where RESij = PRECij ( ADDij \ DELij. Note, that all facts of a precondition that are element of s0 will occur in at least one of the ADD sets. What we do here, is to use the information of the preconditions to decide the applicability.
To create the rest of the states and the state transitions we can now continue with applying operations. In chapter 4.4 we will introduce an example from the blocks-world domain.
Multiple Component State Space Graphs
The considerations we have made so far applied to single component state space graphs. But it is not very difficult to transfer the approach to multiple component graphs. As one can see, the representability of a state as a state transition path applies to each of the components of a graph. Therefore the act of creating the state space is identical for each of them. The only problem that arises is to know how many components exist.
Even to a multiple component state space graph it applies that the static facts are part of all states, regardless of the component a state belongs to. Therefore there must be at least one non-static fact (or a combination of facts) that determines to which component a state belongs. For this fact is part of at least one operation, we are able to decide whether we have to create another component or not. After creating the partial state space of one component, we may take a look at the operations that have been used so far. If there exists an operation that has never been used, this operation must belong to a further component which we may create by building a new initial state starting with the unused operation.
3 Limits of the Approach
Besides the restriction of reversibility of the operations (definition 3.8) and the inaccuracy of how the implication of fact 3.2 is interpreted the introduced approach has a general limit that cannot be altered except from rewriting the domain in a suitable way.
So far we have assumed that the question of compatibility of two facts is the same in all cases. This is mostly true, but there are domains where the compatibility of a pair of facts (p,q) depends on the existence of a third fact t. Therefore have a look at the instance from the life domain[17] given in figure 3.8.
In the life domain instance lucy grows up, earns money and can spend this money for some desired aims. She can buy a house, have some luxurious cars or found a family. The interesting thing is that the domain restricts lucy to have at most two of the things money can buy, because after spending her money for the second thing lucy runs out of money.
If we want to decide whether (have family) can be added to (has-money lucy) we have a problem. If lucy already has one of the other things (i.e. if (have house) or (have cars) hold) we have to decide negative, because having two things does not allow (has-money lucy) to stay in the resulting state. But if lucy has neither house nor cars yet, we have to decide positive. We must say that the compatibility of the pair ((have family), (has-money lucy)) depends on the validity of (have house) and (have cars).
Figure 3.8. An operation from the life domain
This dependency may not be restricted to three facts. We can also think of a life domain where one my have three, four or 27 things, before money runs empty.
For the else-case of the operation allows the two facts to be combined, our approach would decide that the facts are compatible. This applies to (have family) as well as to (have house) and (have cars), they all are compatible to (has-money lucy). For the (have ?x) instances are mutual compatible, too (they occur together in the result state of the then-case of the spend-money operator), all these combinations will have a one in the adjacency matrix and our algorithm will, for example, create a state where { (has-money lucy), (have family), (have house) } is a legal subset, which is wrong.
There is no practicable solution to this problem. Surely, we can solve the life problem by inventing new operators. If we have an operator to spend money for the first thing, and a second operator to spend it for the second thing, we have no problem. But this is, of course, far from being efficient, not to mention intuition.
What we could do is to make up an (2n,2n,2n)-adjacency matrix using triples of ground literals instead of pairs. This would lead us to a matrix making decisions as shown in table 3.1. The different decisions for the pair ((have family), (has-money lucy)) according to the presence of (have house) can be found in the first two rows of the table.
The problem with this solution is that we do not know whether we have to check pairs of literals or triples or even larger n-tuples. For the matrix grows exponentially with its rank this becomes inefficient very soon. In the end it would mean to build the powerset over the set of literals and make up a matrix where a one stands for a legal state. The question is whether in that case decisions can at all be made.
Table 3.1 Decisions for triples of literals of a life domain planning problem
|literal to be added |literals that already hold |decision |
|(have family) |((have house) | |(has-money lucy) |1 |
|(have family) |(have house) | |(has-money lucy) |0 |
|(have family) |((have house) | |((has-money lucy) |0 |
|(have family) |(have house) | |((has-money lucy) |0 |
|((have family) |((have house) | |(has-money lucy) |0[18] |
|((have family) |(have house) | |(has-money lucy) |0 |
|((have family) |((have house) | |((has-money lucy) |0 |
|((have family) |(have house) | |((has-money lucy) |0 |
|(have family) |((have cars) | |(has-money lucy) |1 |
| (have family) |... |... |... |... |
|... |... |... |... |... |
For we did not have this problem with any of the investigated domains but had to invent the life domain to explain the problem, we will disregard it in our further examinations.
4 Extending the Approach to a Recursive Procedure
We have seen that the state set mainly depends on the compatibility of facts. Facts represent properties of objects or relations between objects. If for a set of objects we can give a set of facts, these facts will also be legal if we extend the set of objects. What happens is that the set of facts will grow, which corresponds with the fact that the new objects may have particular properties and may stand in relation to the already existing objects. In a close world like a planning domain new objects will never bring other than the domain defined properties or relations with them and if an object of a specific type may have a particular property, another object of the same type may as well have it. In the ferry domain the ferry may stand in relation to a place a, represented by the fact (atferry a). If there exists a second place b it will not change this possibility. It is also clear that if the ferry may be at a, it may be at b, too, because a and b are of the same type and there is no further distinction between the two places.
We assume the compatibility of two facts (or literals) to be independent from other facts (or literals). Therefore we know that the compatibility of a pair of facts will not change even if the set of facts grows. So, if we know the compatibility of the facts of, say, the ferry domain instance with one car, we can use this information to find out the compatibility of the facts of the instance with two cars, for the adjacency matrix of the latter will contain all of the information of the former and, in addition, the information about the new facts, too. Figure 3.9 points out the connection between the two domain instances.
The ferry domain instance with one car may be defined as
(( ferry, O1 ) = (OPOPS,O1, FA,O1, () with ferry = (OPS,A) and O1 = { a, b, c1 }
Figure 3.9. The figure shows the connection between the adjacency matrices of a domain instance
(( ( , O ) and a second one (( (’, O’ ) which is an extension of (( (, O ) with some more objects.
The dotted area represents the matrix of the original instance (( ( ), the white area represents
those cells of (( (’, O’ ) where the information of the compatibility of the additional facts is held.
The set of facts is in this case defined as
FA,O1 = { (empty), (atferry a), (atferry b), (at c1 a), (at c1 b), (on-ferry c1) }
With two cars the instance would then be
(( ferry, O2 ) = (OPOPS,O2, FA,O2, () with O2 = { a , b, c1 , c2 }
and the corresponding set of facts is
FA,O2 = {(empty), (atferry a), (atferry b), (at c1 a), (at c1 b), (on-ferry c1),
(at c2 a), (at c2 b), (on-ferry c2) }
It can immediately be seen that
FA,O2 = FA,O1 ( { (at c2 a), (at c2 b), (on-ferry c2) }
Therefore the adjacency matrix for FA,O2 is an extension of the one for FA,O1.
We can of course not only add cars but could instead add a third place c. In that case the ferry would not only be able to sail from a to b but also to c or from b to c and vice versa.[19]
Instead of adding objects to (( ferry, O1 ), we can take away one object after the other. We will then at some step reach the empty set of objects. The ferry domain we use here only has one ferry which is implicitly used without having an object for it. Therefore, if the set of objects is empty, we still have a ferry, and the only instantiated atom is (empty). This is also correct in meaning, because there is no car to board and there is no shore to be at or to sail to.
In general we can recursively define a set of facts as
Definition 3.13 (Recursively Defined Set of Facts) Let O = { o1, ..., om } be a set of objects. Let ( = (OPS, A) be a planning domain where A = { a1, ..., an } is the set of atoms with
ai: Xi ( ... ( Xi ( bool, where Xi ( X and X is the set of variables used in A.
A set of facts FA,O can in that case be recursively defined as follows.
1) If O = (, then FA,O = { (( ai ) | ai: ( bool, ai ( A }
2) If O = { o1, ..., om }, then with O’ = { o1, ..., om-1 }
FA,O = FA,O’ ( { (( ai ) | ai: Xi ( ... ( Xi ( bool and ((om/x). x ( Xi, ai ( A }[20]
If we consider Sm to be the set of states of a domain instance (( (, Om ) = (OPOPS,Om, FA,Om, ŜA,Om) with m = |Om|, and if we further define Lm as the set of ground literals that can be built from FA,Om, we know that all states si ( Sm are subsets of Lm. Therefore with
Lm+1 = Lm ( L’
where L’ is the set of ground literals that can be built from the one additional object, we can say that
(si ( Sm. si ( Lm+1
But we can do better. We can prove that
(si ( Sm.(sj ( Sm+n. si ( sj
What does that mean? All states of a set Sm will be substates of the state set Sm+n of the domain instance (( (, Om+n ) that is built from (( (, Om ) by adding n objects to Om.
Fact 3.4 (Subset Property of States) If a state si is an element of the state set of a domain instance (( (, Om ) with m objects, it is a subset of at least one state sj of all domain instances
(( (, Om+n ) having the m objects of (( (, Om ) and, in addition, n new objects.
Proof.
Let Fm+n be the set of facts of (( (, Om+n ) and Fm be the set of facts of (( (, Om ).
Let Lm+n be the set of ground literals built from the facts of Fm+n, and let Lm be the set of ground literals built from the facts of Fm.
Let ALm+n be the adjacency matrix for the compatibility of the literals from Lm+n. Let without loss of universality be the cells ordered in the way that to the first 2m rows and columns it applies that with i=0...m-1 and fi ( Fm
a2i,2j holds the information of the compatibility of (fi, fj) (1)
a2i+1,2j holds the information of the compatibility of ((fi, fj) (2)
a2i,2j+1 holds the information of the compatibility of (fi, (fj) (3)
a2i+1,2j+1 holds the information of the compatibility of ((fi, (fj) (4)
In this case the sub-matrix of the first 2m rows and columns of ALm+n is equal to ALm. As shown in chapter 3.2.2, we build the state set of a domain instance by successively adding those literals to a subset s, that are compatible with all literals from s. We further have shown that we can start with any literal we want.
If we start from the literal with the smallest index we have yet not been started with, and successively adding those compatible literals that have the smallest possible index, we will in the first (m-1) steps add literals from the (2m,2m)-sub-matrix, building substates that completely consist of literals from Lm. For the compatibility of a pair of facts does not depend on other facts, these substates must be complete states of (( (, Om ), because they do not depend on the additional literals from Lm+n. Further on, we add another n literals to these substates to build the states of (( (, Om+n ).
This property is of course very powerful and can save us a lot of costs when creating the state set of a domain instance if this world is an extension of a world we already know. The more objects a known instance has, the more efficiently we can compute the larger one, because the number of additional facts becomes smaller in relation to the total number of facts, the larger the domain instance is. In a blocks-world domain instance with 20 blocks we have 400 facts, i.e. 800 ground literals. If we know the compatibility of these literals, stepping to the instance with 21 blocks brings us 41 new facts (82 literals), which is just 10% of the literals we would have to check if we start from the beginning.
But we can even do better. Think again of the ferry domain. Adding a second car c2 to a ferry, two shores a and b and a first car c1 will bring us three new facts:
FA,O2’ = { (at c2 a), (at c2 b), (on-ferry c2) }
These three new facts must be checked against six already existing facts:
FA,O1 = { (empty), (atferry a), (atferry b), (at c1 a) (at c1 b) (on-ferry c1) }
so that we would have to check 42 pairs of facts: each of FA,O2’ with each of FA,O1 in both directions (3x6x2=36) and the three new facts against each other (2x3). But we needn’t! We have already checked an object of type car against the other types place and (the implicit) ferry. What can be applied to c1 must be applicable to c2, too. Therefore we can simply transfer this knowledge. Eventually, we just have to check the relation between two cars, for this is the only combination of objects that did not occur so far. This reduces the unknown pairs to the number of five: ((at c2 a) (at c1 a)), ((at c2 a) (at c1 b)), ((at c2 a) (on-ferry c1)), ((on-ferry c2) (at c1 a)) and ((on-ferry c1) (on-ferry c2)). All other pairs are either known already or isomorphic to the five pairs mentioned.
Eventually, adding a third car does not raise any new questions, but simply is a repetition of already known pairs of facts.
It is important to note that this recursive approach works even if the set of static facts of the smaller world is different from the one of the larger world. For static facts do not occur in the adjacency matrices, they have no influence on the created (sub-)states. Therefore we can add any set of static facts we want. We are not restricted to the one that was valid in the smaller problem. This is true because of the assumption that the compatibility of a pair of facts does not depend on a third fact, especially not on a static one. Changing the set of static facts will only change the number and kind of edges that occur in the state space, as we will see in chapter 4.5.1.
What can we say about the state spaces of two domain instances from which the first is the extension of the second? If we assume the set Ŝ of static facts not to change we can make some interesting considerations.
The states sn,i of a domain instance (( (, On ) are substates of some states sn+m,i from an instance (( (, On+m ). Under which circumstances will sn+m,i match the same preconditions as sn,i? Well, as long as a precondition contains no quantified expressions[21], it will be matched by both whenever it is matched by the smaller one, i.e if sn,i matches a precondition, so does sn+m,i. This holds because
(PREC ( sn,i) ( (sn,i ( sn+m,i) ( (PREC ( sn+m,i)
Because of this property we can prove the following fact.
Fact 3.5 (Subgraph Property of State Spaces) If a domain can be represented without the use of quantifiers, all instances of this domain are mutual dependent in the way that either the state space of the first is a subgraph of the state space of the second or both state spaces are subgraphs of the state space of a third instance.
Proof.
Let (( (, O1 ) = (OPOPS,O1, FA,O1, Ŝ) and (( (, O2 ) = (OPOPS,O2, FA,O2, Ŝ) be instances of the domain ( = (OPS, A). Let S1 and S2 be the set of states of (( (, O1 ) and (( (, O2 ) and (1 and (2 the corresponding state spaces. Without loss of universality we assume |O2| ( |O1|. We have to distinguish two cases.
Case 1:
O1 ( O2. In this case (( (, O2 ) is an extension of (( (, O1 ) in the sense of definition 3.13. From this follows that fact 3.4 holds. By assumption, ( does not make use of quantifiers and therefore all operations opij ( OPOPS,O1 occur in OPOPS,O2. To states s1,i ( S1 and s2,i ( S2 it applies that
(PRECij ( s1,i) ( (s1,i ( s2,i) ( (PRECij ( s2,i) (1)
Therefore (1 is a subgraph of (2, because they share all nodes and edges of (1.
Case 2:
O1 ( O2. In this case there exists an instance (( (, O3 ) = (OPOPS,O3, FA,O3, Ŝ) with O3 = O1 ( O2. From O3 ( O1 follows that (( (, O1 ) is an extension of (( (, O3 ) and from O3 ( O2 follows that (( (, O2 ) is an extension of (( (, O3 ) by definition 3.13. Let S3 be the set of states of (( (, O3 ) and (3 the state space of (( (, O3 ). To states s1,i ( S1, s2,i ( S2 and s3,i ( S3 it applies that
(PRECij ( s3,i) ( (s3,i ( s1,i) ( (PRECij ( s1,i) (2)
(PRECij ( s3,i) ( (s3,i ( s2,i) ( (PRECij ( s2,i) (3)
Therefore (( (, O3 ) is a subgraph of (( (, O1 ) as well as of (( (, O2 ), because the latter share all nodes and edges of (( (, O3 ).
It can be seen that this property also holds for positive existential quantification and negated universal quantification respectively, because this means that, if such a precondition holds for a given state, there is at least one literal representing a special property. For the existence of only one such literal in a set is enough to make the operation applicable, it will also be applicable to all supersets of that state.
Chapter 4
Algorithmic Realization and Results
We now know that to create the set of states we need the set of facts in order to initialize the adjacency matrix and the set of operations to fill the matrix with the correct information. In addition, to create the state space we need the operations to find the state transitions. As we have said, we assume the set of objects and the set of static facts to be retrieved from the user.
As mentioned in definition 3.7, a state description is a set of facts. But it is clear that the set S of states is just a subset of the potential set of FA,O and that it is hardly ever true that S = 2FA,O.
In addition, not all instantiations of the set of atoms are correct. Therefore we have to find a way to create the complete and correct set of facts FA,O before we can build the adjacency matrix.
1 Creating the Set of Facts
From a domain description it is possible to retrieve all atoms needed to create FA,O. A relevant atom will occur in at least one operator, so what we have to do is to build the union of all atoms of all operators.[22] It would of course be possible to have further atoms being mentioned only in the problem description but they wouldn’t have any effect on the planning problem and would therefore be redundant.
Of course, these atoms will not be ground atoms in most cases. For the set FA,O is the set of instances of the atoms of A we need to know which objects occur in a domain instance, i.e. we have to know the set O. Because objects are not part of the planning domain itself, O must be given by the user. It is clear that the objects must meet some conditions, e.g. that they only are of types provided by the domain.
A complete and correct set A does not ensure us to create a correct set of facts. We need to know which variables may be replaced by which objects. There are two things to take care of: type correctness and equality constraints.
1 Type Correctness
To illustrate the problem we will take a look at the atom (on-ferry ?x) from the ferry domain. Assuming two shores a and b and a car c1, we may instantiate the atom and get a (partial) set of facts
F{(on-ferry ?x)},{a,b,c1}’ = { (on-ferry a), (on-ferry b), (on-ferry c1) }
Two of the three facts are, of course, complete nonsense. Meaning “being boarded” the only appropriate instance of the atom is (on-ferry c1), because boarding a shore doesn’t make sense. How can we solve this problem?
We need not worry about type correctness if the domain description language provides typing of variables and constants. Using PDDL, a simple way of facing the question of type correctness is to make use of the :typing feature. In this case all variables and constants are typed and can therefore be instantiated correctly. If :typing is provided, the set of objects being given from the user can be constrained to the used types. In our example we could use the types place and car. Declaring the typed atom (on-ferry ?x – car) will constrain the variable ?x to be instantiated with objects of type car which will lead to a correct set of facts.
If typing is not provided by the description language (or if the actual PDDL domain does not support the :typing requirement) we need to infer the types of the variables. This is possible because a planning domain must prevent the creation of incorrect facts which is done by using so called type attributes. In the ferry domain we have the operator board( ?x ?y ) which is defined as given in figure 4.1.
Figure 4.1. The board operator from the ferry domain using type attributes
Here the variable ?x from the atom (on-ferry ?x) is constrained by the type attribute (car ?x). If it wasn’t it would be able to identify ?x with an object of another type, e.g. place a, which would create an incorrect fact (on-ferry a). This would soon lead to inconsistencies.[23] Because the type attributes have the same functionality as if the variables were typed directly, we can assume that the expressions ((car ?x) ( (on-ferry ?x)) and (on-ferry ?x – car) are equivalent in meaning. But how can type attributes be recognized?
Type attributes always have an arity of 1. The only argument of the attribute is the variable (or constant) that is said to have the property named by the predicate. Like the type of a variable (or constant) does not change over time the type attribute will be valid in the complete state space. Therefore, a type attribute is not part of the effect of any operator.
Definition 4.1 (Type attribute). A type attribute a ( A of a planning domain ( = (OPS, A) is an atom having the following properties.
1) a: X ( bool.
(a has an arity of 1.)
2) (( ( OPS. ( = ((, () and a ( (.
(a occurs in the precondition of at least one operator of (.)
3) ((i ( OPS. (i = ((i, (i) and a ( (i.
(a does not occur in the effect of any operator of (.)
According to this, we can bind variables (and constants) to type attributes. But it is not always necessary to constrain variables (or constants) to types. For example, in the blocks-world domain all objects are of the same type and therefore need not have a specific type. To avoid partiality of typing we can assume a generic type object, which applies to all objects not bound to type attributes.[24]
Sometimes it is useful to have the same predicate for objects of different type. In the instances of the briefcase domain we (normally) have an object b of type briefcase and some other objects oi of type thing.
(:action put-in
:parameters (?x - thing ?b – briefcase ?y - location)
:precondition (and (at ?x ?y) (at ?b ?y))
:effect (and (not (at ?x ?y)) (in ?b ?x)))
Figure 4.2. The put-in operator from the briefcase domain
If there wouldn’t be any distinction between the briefcase and the things being moved with it the operator put-in (given in figure 4.2) would allow the briefcase to be put into itself. This problem is similar to the one from the ferry domain we discussed above. On the other hand, only one predicate at is used to describe at which place both the things and the briefcase are. This is possible by declaring the predicate with an argument of a third type that functions as the supertype of the types briefcase and thing. What we get is a type hierarchy.
Definition 4.2 (Type Hierarchy of a Planning Domain). Each planning domain ( provides a type hierarchy which is a tree and is recursively defined as follows.
For any object o of type (n it is true that
a. If n = 0 then (n = object.
b. If n > 0 then (n is a subtype of (n-1 to which it applies that (i=0..n-1.(n ( (i.
It applies to o that it is at the same time of type (n,...,(0.
We could assume the atom (at ?x – object ?y – location) to create facts for the briefcase and the other things, because object is the most general type and therefore is the supertype of briefcase as well as of thing. The problem is that we would then be able to create a fact (at home office) where both home and office are of type location, because location is a subtype of object, too. To avoid this we invent another type dynobj as supertype of briefcase and thing, but not of location. We then define the atom (at ?x – dynobj ?y – location). The resulting type hierarchy of the briefcase domain is shown in figure 4.3.
Figure 4.3 Type Hierarchy of the briefcase domain
It is hardly possible to infer type hierarchies. If a variable (or constant) of an atom is given different type attributes within different occurrences of the atom, we do not know whether one of the inferred types is the subtype of the other or both are subtypes of a third one. The only thing we can find out is whether a predicate is able to have variables of different types at one position. We can then assume these types to be the subtype of a generic type object.
Figure 4.4 shows two operators from the travel domain using type attributes. From the precondition of the operator board we can infer that the first argument of the predicate mobile may be of type person as well as of type vehicle. We can also infer from the operator cross that this argument may be of type dynobj. Unluckily there is no possibility to recognize dynobj as supertype of person and vehicle rather than a third type of the same hierarchy level.[25]
Figure 4.4 Two operators from the travel domain using type attributes
Type Conversion
There hardly is a difference between type attributes and normal unary atoms. In the trains domain we have an atom (bananas ?b) which is a type attribute and an atom (oranges ?o) which is not. The only difference is that in this domain oranges can be made into orange juice by an operator make-oj. We can consider this a type conversion because by making juice from ?o the atom (oj ?o) becomes valid and (oranges ?o) becomes invalid. But because both (oranges ?o) and (oj ?o) occur in the effect of make-oj, they are not type attributes per definition 4.1. Instead of that, ?o is of type object and may have one of the properties to be oranges or orange juice.
2 Equality Constraints
Let us again take a look at an example, this time from the typed version of the ferry domain. The domain provides an operator sail (see figure 4.5) which enables the ferry to move from one shore to another. This action makes of course sense only if the shore the ferry starts from is not the same as the one it sails to. Therefore an equality constraint is provided by the operator. Equality constraints may occur in preconditions of operators and may demand two variables to have different instantiations (or the same one). In the case of sail the precondition has an equality constraint (not (= ?x ?y)).
Figure 4.5. The sail operator of the typed ferry domain
In this example sailing from a shore to the same shore would normally not be problematic except for the lack of efficiency[26], but there are domains where violating an equality constraint leads to wrong states. The blocks-world domain is a very good example for that. One can see in figure 4.6. that if the put operator would not constrain the variables ?x and ?y
to have different instantiations it would be able to put a block onto itself. The problem with that would be, that the atoms (ct ?x) and (ct ?y) would be instantiated to the same fact and would be deleted from the effect. The block would stand on itself and there would be no possibility to take it away from there because the puttable operator demands the property (ct ?x) for the upper block to be able to be put onto the table.
Figure 4.6. The blocks-world domain
Simulating Equality Constraints
Some planning languages like STRIPS do not support equality constraints.[27] To simulate them planners like Blackbox 3.4 [KS99] or DPlan 1.0 [Sch99] assume that different variable names require different objects. In many cases this works, so for ferry, blocks-world and most of the transportation domains. It does not work if it is all the same whether or not two variables instantiate to the same object (which holds if the predicate is reflexive). Think of a predicate loves( ?x ?y ) where it is possible for an individual ulysses to love penelope as well as to love himself. Therefore both loves( ulysses, penelope) and loves( ulysses, ulysses ) are correct.
3 Verifying the Correct Set of Static Facts
If the domain provides static atoms, we will have to verify which of the instances should be valid for the processed planning problem. In the travel domain we have the following set of atoms:
A = { (at ?x – dynobj ?y – city) (driving ?p – person ?v - vehicle)
(mobile ?x – dynobj) (road ?x ?y – city) (bridge ?x ?y – city) }
The subset of the static atoms is
A’ = { (road ?x ?y – city) (bridge ?x ?y – city) } ( A
Given two cities c1 and c2, we are able to instantiate the following set of static facts.
ŜA,O = { (road c1 c2), (road c2 c1), (bridge c1 c2), (bridge c2 c1) }[28]
It is clear that depending on the domain instance not all of these possible facts will be valid. On the contrary, the purpose of static facts is exactly to restrict the sphere of influence of the operators (see 4.5 for examples). Therefore the set of static facts varies from one domain instance to another. On the other hand, it is of course possible to have all these facts being valid. Depending on the implementation the subset of valid statics can be predefined or can be retrieved by interacting with the user.
What is the effect that comes along with invalid static facts? What happens is that preconditions containing such a fact will not match any state. In other planning approaches this is no problem because it will not lead to incorrect states, because the invalid facts are not elements of the states. In our case, where building the states is done by applying operations we have to take care of skipping operations with invalid static facts because if we did not, we would add these facts and create invalid states.[29] This directly raises the problem of creating the set of operations.
2 Creating the Set of Operations
On the first sight, instantiating operators seems to be a simple procedure. In chapter 4.1 we have shown how to typify the atoms of a domain. Given a set of typed objects, we simply have to match the variables, that occur in the atoms of the operator specification, to this set. With simple (i. e. STRIPS-like) operators this is true, as we can see from the ferry domain example in figure 4.7. These operators are unconditioned and define preconditions and effects as a conjunction of literals, so that a precondition of that kind leads to one single instance for each possible substitution (see definition 3.4).
The ferry domain instance of figure 4.7 provides a set OP of six operations. As we can see there is no problem with the operators board and debark, where all possible instances are correct. In contrast to this, the sail operator is restricted by an equality constraint. Two instances are invalid (sail(a a) and sail(b b)) and therefore not elements of OP. We can simply prove that such an operator instance is invalid because it applies to all facts occuring in a valid operation to be elements of the set of facts F. With respect to 4.1.2, sail(a a) and sail(b b) are both not elements of FA,O.
Creating operations is problematic, if the operators become more complex. This is the case in allowing additional features of some domain specification languages, namely conditional effects and quantification.[30] In our definition of an operator we have taken these extensions into account. Within the instantiation process we transfer quantified expressions into formulas being in conjunctive normal form (CNF)[31], so that we will not have to face any problems with them. So what we have to handle here are the conditional effects.
Figure 4.7. The set of operations of the ferry domain instance with one car
1 Conditional Effects
Using conditional effects provides a powerful and efficient way of specifying a planning domain. It has been shown that all STRIPS-like operators using conditional effects can be rewritten to a set of unconditioned operators (see [ASW98]), and transferring quantified expressions into CNF (i.e. into STRIPS-like representation) we are able to create a set of completely unconditioned operations.
As with the facts, we have the problem that not all operations, that can be built, are valid. Besides the ones with equality constraints we have problems with conditioned operators. As defined in definition 3.5, to create all instances of an conditioned operator, we combine the secondary preconditions in a way that we build the powerset of these conditions. The preconditions of each of the resulting sets are unified in a new precondition, and together with the effect that is built by combining all of the participating effects, unconditioned operations are created.
The problem is that we normally have a complete and correct state from which is proved whether the instance of a conditioned operator may be applied. The rule is that the primary precondition must match the state to make the operation applicable, and that for each of the additionally matching secondary preconditions the corresponding effect takes place, too. Having a state given, we can easily prove, which of the secondary preconditions match.
Without having a state we probably cannot decide which of the secondary preconditions at all can be combined. Have a look at the operator from figure 4.8. It models the marriage of a man and a woman.
Figure 4.8. An operator to enable marriage of two adults
As we can see the operator has two secondary preconditions and the powerset of them is
2PRECmarry = { (, (female ?x), (male ?x), (female ?x) ( (male ?x) }
which for two persons ulysses and penelope result in the operations given in figure 4.9.[32]
The sets of the first operation are subsets of those of the second and third operation, whereas the sets of the latter are subsets of the sets from the fourth operation. When we for example try to verify the compatibility of the pair ((husband ulysses penelope) (husband penelope ulysses) ) we get a problem, because both facts occur in the effect of the fourth operation
which would mean that this pair is compatible. This is, of course, wrong. What we disregarded is the fact that (female ?x) and (male ?x) must not be combined in a single
precondition which is the case in the fourth operation. For any legal state, one of the two atoms will not match, but unluckily we are not able to know that at this point, because exactly this is what we are going to find out by examining the operations.
Figure 4.9. Instances of the marry operator from figure 4.8
The only way we can handle this problem is to define operators in a way that preconditions that cannot be combined are able to be detected. We can for example decide two preconditions to be mutual exclusive, if the first contains a fact p whereas the second contains (p. It is unequivocal that such preconditions cannot be combined so that we can prevent these instances from being added to the set of operations. To solve the problem with the marry operator we could for example define it as given in figure 4.10.
Figure 4.10. The derived marry operator
An algorithm to create the set of unconditioned operations from a conditioned operator is given in figure 4.11.
Figure 4.11. An algorithm to create the set of unconditioned operations from a conditioned operator
As an example of the instantiation of conditioned operators we will take a look at the blocks-world domain again. The complete domain is given in figure 4.6 and for four blocks a, b, c and d we build the operations for one variable substitution as given in figure 4.12. It is important to see that the single atom in the secondary precondition of the put operator must be read as if it was existentially quantified.
Figure 4.12. Creating the instances of the put operator for a specific variable substitution
The number of three operations corresponds with the possibilities where a block a can reside before it is put on a block b in a world with four blocks a, b, c and d. a may have been on block c or d or on the table. In general, the number of operations that can be built from an operator mainly depends on two things: the number of objects being involved and the number of secondary preconditions, because we have an exponential number of possible combinations for each possible instance of the primary precondition. Table 4.1 gives examples for the number of operations with well-known domains.
Table 4.1 Number of operations for some domain instances
|Domain |Objects |Operator |# Operations |
|blocks-world |2 |puttable |2 |
| | |put |2 |
| |3 |puttable |6 |
| | |put |12 |
| |4 |puttable |24 |
| | |put |72 |
| |5 |puttable |120 |
| | |put |480 |
|ferry |2 places |board |2 |
| |1 car | | |
| | |sail |2 |
| | |debark |2 |
| |2 places |board |4 |
| |2 cars | | |
| | |sail |2 |
| | |debark |4 |
| |2 places |board |6 |
| |3 cars | | |
| | |sail |2 |
| | |debark |6 |
|briefcase |2 places |put-in |2 |
| |1 briefcase | | |
| |1 thing | | |
| | |take-out |2 |
| | |move |2 |
| |2 places |put-in |4 |
| |1 briefcase | | |
| |2 things | | |
| | |take-out |4 |
| | |move |2 |
| |2 places |put-in |6 |
| |1 briefcase | | |
| |3 things | | |
| | |take-out |6 |
| | |move |2 |
|monkey |1 monkey |go-to |- |
| |1 box | | |
| |1 knife | | |
| |1 bananas | | |
| |1 place | | |
| | |climb |1 |
| | |get-knife |1 |
| | |grab-bananas |1 |
| | |push-box |- |
| |1 monkey |go-to |2 |
| |1 box | | |
| |1 knife | | |
| |1 bananas | | |
| |2 places | | |
| | |climb |2 |
| | |get-knife |1[33] |
| | |grab-bananas |1 |
| | |push-box |2 |
| |1 monkey |go-to |6 |
| |1 box | | |
| |1 knife | | |
| |1 bananas | | |
| |3 places | | |
| | |climb |3 |
| | |get-knife |1 |
| | |grab-bananas |1 |
| | |push-box |6 |
2 Operation Enchaining
We often can find domain instances, where some pairs of facts are compatible, but will never
occur together in the sets of an operation. This happens due to the fact that operations often manipulate a however structured periphery of the object space of the domain instance. Think of the blocks-world domain, where both operators work on the top of the towers built from the blocks but never manipulate the inner blocks. A fact (on c a) is compatible with a second fact (on a b), but due to the fact that it is irrelevant for putting a block c on a block a, whether a is on the table or already standing on a block b, the put operator does not give us any information on this question. But have a look at the first (put a b) operation from figure 4.12. The resulting set after applying this operation is s = { (ct a), (on a b), ((ct b), ((on a c), (ct c) }. It can easily be seen that this set matches the put operator again. For example, put(c a) is applicable, which has a primary precondition PREC0 = { (ct c), (ct a) } and a primary effect EFF0 = { (on c a), ((ct b) }.
What we can see now is, that adding (on c a) is done by this operation and that the precondition matches a (sub-)state containing (on a b), so that we can state that the pair of facts ((on c a), (on a b)) is compatible in the sense of fact 3.2.
We found this compatibility by enchaining the application of two operations. We can, of course, enchain more than two operations and possibly are able to combine both the proof of compatibility (see chapter 3.2 and 4.3) and the creation of the state space (see chapter 3.2.2
and 4.4) in a way that makes it much more simple to fill the adjacency matrix. This enables us to build the adjacency matrix of the blocks-world domain instances without interacting with the user.
We have not further investigated this possibility and can therefore not give any detailed information.
3 Creating the Adjacency Matrix
Having the domain instance (( (, O ) = (OP, F, Ŝ) we can start filling the adjacency matrix which we create as a (2n,2n)-matrix with all cells initialized with a value other than zero or one to sign them as undecided. For all pairs (p,q) of facts we then decide whether they are compatible in the sense of fact 3.2 by applying the algorithm given in figure 4.13.
The algorithm provides a series of tests, each of them made whenever the former test failed. So, for a fact (p,q) we first check, whether it has already been decided. If this is not the case, we check whether p is equal to q. In that case the corresponding cell of the adjacency matrix will be set to zero. Otherwise we make the next test, and so on.
If in this procedure a pair cannot be decided, it is skipped and having run through the complete matrix, we either or not made some decisions. If we did and if there are some of the pairs yet not decided, we repeat the complete procedure for all undecided pairs.
We stop, if either all pairs have been decided, or in one loop no further decisions have been made. In the case of having undecided pairs we will now have to interact with the user, asking him to decide one of the remaining pairs. Having this new information we again start the loop and try to decide some more pairs. We repeat this procedure until the complete matrix is filled.
Figure 4.13. Algorithm to fill the adjacency matrix of a domain instance
As one can imagine the number of pairs that have to be decided by the user depends on the question how independent the objects of the domain instance can act. For example, a car of a ferry domain instance can be at a shore completely independent from any other cars. Due to this fact, the only question the user has to answer for a ferry domain instance is, whether a car may be at the same place a while another car c2 is at place a already. The pair that is to be decided by the user for the ferry domain instance with two cars is ((at c1 b), (at c2 b)).
The complete example for creating the adjacency matrix for the travel domain instance with one person, one bulldozer and two cities is given in appendix B.2.
If there are at all undecided pairs, their number increases as long as there are combinations of objects, which have yet not occurred and therefore are unknown. Normally, if a certain number of objects has been reached, only repetitions (i.e. isomorphic instances) of already known pairs of facts can be built. For example, the unique undecided pairs in the ferry domain never exceed the number of 1. See table 4.2 for more details.
Table 4.2 Number of questions for some domain instances
|Domain |Objects |# of questions |
|blocks-world |3...n |0 |
|ferry |2 places, 1 car |0 |
| |2 places, 2...n cars |1 |
|hanoi |n pegs, m disks |0 |
|briefcase |2 places, 1 thing |0 |
| |2 places, 2...n things |1 |
|travel |1 person, 1 bulldozer, 2 cities |1 |
| |1 person, 1 bulldozer, 3...n cities |4 |
|monkey |1 monkey, 1 box, 1 knife, 1 bananas, 2..n places |11 |
It is conspicuous that the monkey domain raises much more questions than the other domains. This is explicable by the large number of types and operators that come along with the monkey domain.
4 Creating the Set of States
In chapter 3.2.2 we have introduced two ways of creating the set of states from the adjacency matrix. Now we will introduce the corresponding algorithms.
The first algorithm (Algorithm 1) starts with an empty set of literals. In a loop we run over the complete set of literals, once starting with each of them. To this initial literal we add a second compatible one, and so on, until we cannot add any further literal. After adding a literal we check, whether we ever before created the same resulting set of literals. In that case we skip this set and start with the next literal. When no further literal can be added, we have to prove, whether the resulting set is a complete state by simply checking its size. We can then add this set of literals to the set of complete states. Algorithm 1 is given in figure 4.14.
Figure 4.14. Algorithm 1 to create the set of states from the adjacency matrix of a domain instance
As an example we may have a look at the simple adjacency matrix (i.e. built from the facts rather than from the ground literals) of the ferry domain instance with one car. It is given in figure 4.15 together with the corresponding adjacency graph.
Figure 4.15. Adjacency matrix and graph of the ferry domain with one car
In the adjacency graph there is an edge from node x to node y, if fact x is compatible to fact y, i.e. fact x can be added to a set of facts where y is an element.
We may for example start with the fact (atferry a), then adding (empty) which is compatible to (atferry a). The next fact we can add is (at bmw a), which is compatible to both (atferry a) and (empty). Having done so, we can decide that
s = { (atferry a), (empty), (at bmw a) }
is a complete state, because at that point we cannot add any further fact. We can find all states by this procedure. The complete resulting forest is given in figure 4.16.
As we can see from the forest, we will create all states twice or more times[34], what makes up the disadvantage of this algorithm (see the discussion in chapter 3.2.2). The only paths we need to traverse in order to create all states are the ones marked by bold lines. The problem becomes worse the more facts are needed to build a complete state description. Think, for example, of the ferry domain instance with 10 cars. It is completely irrelevant, in which order the facts (at c1 a) to (at c10 a) are combined in the state s = { (atferry a), (empty),
Figure 4.16. Forest of trees traversed by algorithm 1 for the ferry domain with one car
(at c1 a), ..., (at c10 a) }. Nevertheless, Algorithm 1 will search all paths.[35]
As an alternative we introduce Algorithm 2 which makes use of one of the well-known algorithms for finding maximum cliques in an undirected graph. In our implementation we
use the algorithm introduced by [BK71].[36] This algorithm needs to regard a pair of nodes (f, f) as connected. In a first step we therefore have to vary the main diagonal of the adjacency matrix. Disregarding the directions of the edges of the adjacency graph leads to wrong cliques as we have shown in figure 3.6. We therefore have to post-process the found cliques by a recursive function to detect incorrect sets of facts. Algorithm 2 is given in figure 4.17.
Figure 4.17. Algorithm 2 to create the set of states from the adjacency matrix of a domain instance
As we mentioned in chapter 3.2.2, the second algorithm has some useful advantages. If we, for example, have a partial description of an initial state, we can simply step into the clique algorithm of Algorithm 2 with the already pre-initialized set of facts. Another benefit of the second algorithm raises from the subset property of states (see fact 3.4) which we will discuss in chapter 4.5.
An Example of Building a State by Operation Application
We showed that it is not necessary to apply operations to build states but that we simply can do this from the adjacency matrix. But we can of course do the former, because for the fact that all non-static facts occur in the effect of at least one operation, we can be sure to have them collected in a complete state description after a finite number of operations.[37]
As an example we create a complete state description in the blocks-world domain instance with three blocks. We apply six operations:
1. puttable(a) = ( { (ct a), (on a b) }, { (ct b), ((on a b) } )
( s = { (ct a), (ct b), ((on a b) }
2. put(b a) = ( { (ct a), (ct b), (on b c) }, { (on b a), (ct c), ((ct a), ((on b c) } )
( s = { ((ct a), (ct b), (ct c), ((on a b), (on b a), ((on b c) }
3. puttable(b) = ( { (ct b), (on b a) }, { (ct a), ((on b a) } )
( s = { (ct a), (ct b), (ct c), ((on a b), ((on b a), ((on b c) }
4. put(c a) = ( { (ct c), (ct a), ((on c b) }, { (on c a), ((ct a) } )
( s = { ((ct a), (ct b), (ct c), ((on a b), ((on b a), ((on b c), (on c a), ((on c b) }
5. put(c b) = ( { (ct c), (ct b), (on c a) }, { (on c b), (ct a), ((ct b), ((on c a) } )
( s = { (ct a), ((ct b), (ct c), ((on a b), ((on b a), ((on b c), ((on c a), (on c b) }
6. put(a c) = ( { (ct a), (ct c), ((on a b) }, { (on a c), ((ct c) } )
( s = { (ct a), ((ct b), ((ct c), ((on a b), (on a c), ((on b a), ((on b c), ((on c a),
(on c b) }
How can we know which operations to use in order to create a complete state from an optimal number of operations? Whenever we have the chance to apply more than one operation, we can, of course, choose the one with the maximum new information for us, i.e. the one where the resulting set has as much literals of yet unknown facts as possible. As it can easily be seen in the above example, it would have been more efficient to skip at all operation 1 but to start with operation 2. The only information of operation 1, that is not given by operation 2, is ((on a b). But we can see that ((on a b) is part of the precondition of operation 6. So if we start with operation 2, we will come to a complete state within 5 operations. Taking the amount of information into account, we would find, that it is always most efficient to start with a put operation, namely one where the secondary precondition does not match, because in that case the negated secondary precondition leads to a lot of information, above all when the number of blocks is large.
In our example, we were two times not able to get new information about unknown facts, namely when applying operation 3. and 5. This is a lack of efficiency, which comes with the special properties of the blocks-world domain. Regarding to this creating the state from the adjacency matrix seems to be more practicable.
5 The Recursive Approach
The recursive approach of extending domain instances by successively adding objects is highly supported by Algorithm 2 from chapter 4.4. We proved that all states of a domain instance (( (, Om ) are substates of states of an instance (( (, Om+n ) if Om ( Om+n. That means that with Algorithm 2 we can use this property to build the maximum cliques of literals of (( (, Om+n ) by starting the clique algorithm with the states of (( (, Om ) instead of starting with single facts from Fm which will save us the more effort the larger the instance becomes. What we have to do in addition is to build the remaining maximum cliques starting from the new literals. Table 4.3 shows the relation between the total number of facts and the number of new facts that come with an added object. The underlying domains are given in appendix A.
Table 4.3 Relation between total number of facts and number of new facts
|Domain |Objects |# facts |# additional facts |
|blocks-world |n |n2 |2n – 1 |
|ferry |k places, n cars |(k+1)(n+1) |Increasing k: n+1 |
| | | |Increasing n: k+1 |
|briefcase |k places, n things, b briefcases |k(b+n)+bn |Increasing k: b+n |
| | | |Increasing n: b+k |
| | | |Increasing b: k+n |
|hanoi |p pegs, d disks |d(p+d-1)[38] |Increasing p: d |
| | | |Increasing d: p+d-1 |
|monkey |k places, 1 monkey, 1 box, |5k+3[39] |5 |
| |1 knife, 1 bananas | | |
Whereas the total number of facts mainly grows polynomial, the number of additional facts grows linear.
A second benefit comes with the fact that if the object being added has a type that is the same as the one of an already known object, we can save the effort needed to explore the compatibility between the additional facts and those belonging to the objects of other types. Have a look at figure 4.18. It shows a diagram illustrating the relation between added objects and objects already existing in ferry domain instances. Depending on the types of the
Figure 4.18. Diagram of the different prototypes of pairs of facts of the ferry domain.
objects different sets of additional facts are created. The column defines the type of the added object, whereas the row defines the types of the already existing objects of the domain instance that is to be extended.
Each of the pattern may be seen as an equivalence class, representing pairs of facts that have to be proved when adding the object. With each of these classes, a fix number of objects is needed to instantiate the pairs. Which objects may be used is restricted by the list of types that is predefined by the class and that are given in square brackets.[40]
For example, adding a place b to a ferry and another place a raises three kinds of new pairs of facts, that are to be proved. First of all, atoms that can be fully instantiated alone from the new place are represented by the light gray pattern ( i.e. the pair ((atferry b), (atferry b))). The middle gray pattern represents those pair of atoms that can be instantiated from one ferry and one place ( i.e. ((empty), (atferry b)) and ((atferry b), (empty))) whereas eventually the dark gray pattern represents those pairs, that can be instantiated from both place a and b (i.e. ((atferry a), (atferry b)) and ((atferry b), (atferry a))). There is no possibility to instantiate pairs of atoms that take a ferry and two different places, and therefore no corresponding class exists.
It is clear that due to the fact, that the set of atoms is finite, the number of possible combinations of objects used to instantiate pairs of atoms is finite, so that we will in all cases come to the point where adding an object leads to a set of facts, that is completely isomorphic to one we already proved.
In the ferry domain we never need more than one object of the same type to instantiate all possible facts (provided the objects of the other types are given as far as needed). We then need two objects to check the compatibility of a pair of different instances of the same atom (e.g. ((atferry a), (atferry b))). In the blocks-world domain we have a predicate that takes two objects of the same type, namely (on ?x ?y). Therefore, to check a pair of instances of the predicate on, we need up to four objects to get all combinations of objects in that predicate. For example, we need two blocks to verify ((on a b), (on a b)) and ((on a b), (on b a)), three blocks to verify ((on a b), (on a c)) and ((on a b), (on c b)), and eventually four blocks to verify ((on a b), (on c d)).
There may be domains where atoms taking two objects of the same type allow these atoms to be instantiated by one single object of the demanded type (see the example with the loves predicate in 4.1.2). We have to take this property into consideration if we divide the possible pairs of facts into classes.
Building pairs over the atoms of a domain results in a set of pairs that can be divided into classes due to the number and types of the objects that are necessary to completely instantiate the involved atoms. We call each of these classes a prototype.
Definition 4.3 (Prototype) In a domain instance (( (, O ) = (OP, F, Ŝ) a prototype is a tuple
( = ((, P, C, ( ) with the following properties.
1) ( = [(1, ..., (m] is a list of types provided by (.
2) P = p1, ..., pn is a list of pairs of facts. It applies to two facts fi, fj ( F that (fi, fj) ( P iff
a. The number of objects involved in (fi, fj) is m.
b. To all objects ok involved in (fi, fj) it applies that if (k is the type of ok, then (k ( (.
3) C = c1, ..., cn is a bit vector and to a bit ci it applies that
a. ci = 1, if it applies to pi = (fi, fj) that fi is compatible with fj in the sense of fact 3.2.
b. ci = 0, else.
4) (: F ( F ( C is a prototype selector function which is defined as follows.
ck, if it applies to any pk ( P that pk is isomorphic to (fi, fj)
(( (fi, fj) ) =
-1, else
Two pairs of facts p1 and p2 are isomorphic, if there exists a bijective substitution so that each object of p1 can be replaced by an object of p2 of the same type.
In figure 4.18 each pattern represents a different prototype. It can be seen that depending on the already existing objects and the object being added, a different set of prototypes is needed to decide on the compatibility of the new built pairs of facts. Nevertheless it is clear that the set of prototypes is always finite, because of the finite set of atoms that are used to build the pairs of facts.
Assuming that we have an existing adjacency matrix where the already proved pairs have been used to build the corresponding subset of possible prototypes, we can use this prototypes to decide the compatibility of facts that raise when the adjacency matrix is extended by adding a new object. Figure 4.19. gives the algorithm to do so.
Figure 4.19 Algorithm to create the adjacency matrix by recursively adding objects
4.5.1 Extending State Spaces
When we extend a domain instance (( (, On ) by adding a new object, we know that the states of the former instance occur as substates in (( (, On+1 ). In chapter 3.4 we also discussed under which circumstances the state space (n of the smaller instance occurs as a subgraph in the state space (n+1 of the extended instance. We now want to investigate the question whether it is possible to simply extend (n to (n+1.
As an example we are going to extend an instance of the briefcase domain, where we have one briefcase, one thing and two places, to the instance where we have two things. We will therefore define
(1 = (( briefcase, { b – briefcase, p – thing, home, office – place } )
(2 = (( briefcase, { b – briefcase, p, d – thing, home, office – place } )
The facts of these two instances are
F1 = { (at b home), (at b office), (at p home), (at p office), (in p b) }
F2 = { (at b home), (at b office), (at p home), (at p office), (in p b), (at d home),
(at d office), (in d b) }
The state space of (1 is
(1 = ( { { (at b home), (at p office) }, { (at b office), (at p office) },
{ (at b office), (in p b) }, { (at b home), (in p b) },
{ (at b home), (at p home) }, { (at b office), (at p home) }
} = { s1, s2, s3, s4, s5, s6 },
{ (s1,s2,move(b,office)), (s2,s1,move(b,home)), (s2,s3,put-in(p,b,office)),
(s3,s2,take-out(p,b,office)), (s3,s4, move(b,home)), (s4,s3, move(b,office)),
(s4,s5,take-out(p,b,home)), (s5,s4,put-in(p,b,home)), (s5,s6,move(b,office)),
(s6,s5,move(b,home))
}
)
and the state space graph is given in figure 4.20. With the set of additional facts
F’ = { (at d office), (at d home), (in d b) }
we have to prove the compatibility of 36 pairs of facts (which we do not list here). The compatibility check will result in the fact that the new facts are mutual exclusive but are compatible to all of the old facts and vice versa. This makes it easy for us to illustrate how we can extend (1 to (2.
Figure 4.20 State space of the briefcase domain instance with one thing
When we create the states of (2 from the corresponding adjacency matrix (i.e. its maximum cliques), we at first begin with the already known states from (1 as initial cliques. For each state from (1 we find that we can add exactly one of the additional facts. If we, for example add the fact (at d office), we can create six states of (2 with the same state transitions as in (1 (due to fact 3.5). Similarly, if we add the fact (at d home) to the states of (1, we get another six states of (2. Eventually, if we add the third fact (in d b) to the states of (1, we get six further states of (2. These states are illustrated in figure 4.21. For the three new facts are compatible to all the old facts (and vice versa) and are mutual exclusive to each other, there will not be any further states, so that (2 consists of 18 states.
Figure 4.20 The partial state space of the briefcase domain instance with two things
Some edges (i.e. state transitions) are missing yet. What we have disregarded yet is the fact, that p and d are of the same type. Therefore in each of the three subgraphs of figure 4.20 we can exchange the two things and get the new subgraphs of figure 4.21. These new subgraphs cannot contain any new states but instead have other edges. In figure 4.21 we kept the numbers of the states as they are given in figure 4.20.
Figure 4.21 The partial state spaces of figure 4.20 after exchanging p and d
We can now combine the subgraphs to the complete state space (2, which is given in figure 4.22. How can we be sure that (2 is complete now? Well, we know that there are no more states (we have proved that from the adjacency matrix). With exchanging the two things p and d in the state descriptions and keeping the edges of the graph we implicitly exchanged p and d in the operations, too. There are no operators, that never have been instantiated (there is no operator, which at the same time involves two things), so that we cannot create new operations, from which follows that the state space has to be complete.[41]
As we mentioned, in addition to extending the states from the smaller instance, we have to build the cliques beginning from the new facts, possibly resulting in further states. But if adding a new object only brings up facts, that are isomorphic to already known ones, the cliques being built beginning from the new facts will be isomorphic to some of the extended states. Therefore we can skip building the additional states, because exchanging the objects in the second step of our procedure exactly means to build the isomorphic states.
Figure 4.22 The state space of the briefcase domain instance
with 2 things (numbers given from figure 4.20)
We can illustrate this with the blocks-world domain, where we can create additional states that do not have one of the states of the smaller world as substates. For example, the state
s = { (ct a), (on a c), (on c b) }
does not contain any state of the blocks-world domain instance with two blocks a and b.
Figure 4.23 The partial state space of the blocks-world
domain instance with three blocks.
Nevertheless we are able to create all states, because s is isomorphic to
s’ = { (ct a), (on a b), (on b c) }
which is an extension of
s’’ = { (ct a), (on a b) }
We again start with extending the states from the smaller instance, which is shown in figure 4.23. We observe that the new facts (on c a) and (on c b) cannot be added to any of the states from the 2-blocks instance. But (on c a) is isomorphic to (on a c), so with exchanging objects in the second step, we nevertheless create all possible states, as we can see in figure 4.24.
Figure 4.24. The partial state space of figure 4.23 after exchanging c with a or b
So far, everything is alright. We really were able to create all the states of the new instance, although not building the additional cliques. But we now have to face another problem. If we combine the resulting subgraphs of figure 4.24 in order to build the single state space of the blocks-world domain instance with three blocks, we find that not all state transitions occur, as illustrated in figure 4.25.
Figure 4.25 State space of the blocks-world domain instance with three blocks
(numbers given from figure 4.24)
The stressed edges of the state space are missing. This happens due to the fact that in the blocks-world domain instance with two blocks the secondary precondition of the put operator cannot be instantiated, so that the corresponding operations do not occur there. Therefore they are also missing in the extended instance with three blocks.
What we have to do now is to check whether or not we can instantiate any additional operators (similar to checking whether we can build additional non-isomorphic states). If we do so, we would find that, having three blocks, the secondary precondition of the put operator can be instantiated. We find the corresponding edges by applying these new operations to the states.[42]
If the set of new facts is not a complete isomorphic subset of the already known facts, things become different. In that case we possibly get some additional new states. We could extend the state space as shown, disregarding the additional states. Afterwards we would have to check the operations that can be applied to those states to connect them to the newly created partial state space. See appendix B.5 for an example from the travel domain.
In general, we can state that in domains with STRIPS-like operators we are able to create the state space of a domain instance by extending the state space of another instance that has one object less. Two problems may come with this procedure. At first, it may be that we can create states, that are not superstates of the states of the smaller instance, so that we have to check how these states are connected to the rest of the state space. The second problem would be that we are able to instantiate additional non-isomorphic operations, so that we will get new state transitions (i.e. edges in the state space graph). In other words, the first problem is, that we have states from which we do not know the corresponding edges, and the second problem is that we have edges from which we do not know, which states they are connecting. Nevertheless it holds, that from a certain collection of objects on, neither the first, nor the second problem will occur anymore, so that we will always be able to extend an existing state space.
Figure 4.26 gives the complete algorithm for extending states spaces.
The Role of Static Facts
We discussed in chapter 4.1.3 that the static facts do not have any influence on the set of states. This is clear, because taking away the static facts from all states of a domain instance, does not cause any two states to be united to one single state, which would be the only way to decrease the number of states. The number of states will also not increase if static facts are added, because we would have to add the static facts to all states (per definition of a static fact). Therefore the number of states will always be the same, regardless of the subset of valid static facts.
This property has the effect that we can extend a set of states by adding a new object, and afterwards change the set of static facts in the new states. But this is, of course, not true for the state space. Static facts enable or disable state transitions and therefore changing the set of static facts will cause a change in the set of edges of the state space graph.
To change the set of static facts after extending the state space of a domain instance, we will have to prove whether or not an edge of the extended state space graph keeps valid. Assuming the set of non-static facts F1 and the set of valid static facts Ŝ1 of the smaller instance and the set of valid static facts Ŝ2 of the extended instance, we can say that an edge (si,sj,opij) with opij = (PREC,EFF) is valid in the smaller instance if PREC ( (F1 ( Ŝ1) and that it keeps valid if PREC ( (F1 ( Ŝ2). An example can be found in appendix B.5.
Figure 4.26. Algorithm to extend an existing state space to the state space with an additional object
Chapter 5
Conclusion and Further Work
We introduced an approach that - with some restrictions – enables us to create a complete state set in relation to a given domain and a set of objects on an exclusively syntactic level. One may contest the idea of creating the state set of a domain instance, because the state set alone does in most cases not help us in planning. There are few systems like DPlan needing a complete state set. In universal planning we may find useful applications, too.
There are some advantages in having an adjacency matrix of fact (or ground literal) compatibility. We are able to check the admissibility of states by reconstructing them from the adjacency graph. Another useful application is that we are able to enrich incomplete state descriptions in the way that we create the set of states containing the given subset. This enables us to plan with incomplete initial states and goal descriptions.
The approach makes some restrictions to the domains which may not always be desirable. While reversibility of operations nearly always is feasible, we may have serious problems with the assumption, that balanced atoms do not occur with more than one instance in a single state (see chapter 3.2.1). Normally we have initial states given with a planning problem and from this state we can find the number of instances of a single balanced atom of a state. Perhaps it is possible to use this knowledge for a correct interpretation of the implication that comes along with fact 3.2.
The restriction of checking the compatibility only of pairs of facts, corresponds with the capability of exploring mutexes, coming along with the Graphplan approach [BF97]. As shown, we could extend the approach to check triple (or n-tuples) of facts, and it may be useful to investigate in the question whether it can be decided from the domain description, how large the tuples have to be to come to correct results.
It is a disadvantage that it is necessary to interact with the user, for this is a source of mistakes, and an erroneous adjacency matrix leads of course to wrong states. It would be desirable to find a solution to the fact that the decisions made on the compatibility of pairs of facts depend on each other. The possibility of enchaining operations to enrich the preconditions (which we introduced in chapter 4.2.2) seems to be a step into the right
direction. But it would be necessary to research whether the effort that comes along with the enchaining of operations is justified by the wish to avoid interaction with the user.
The introduced recursive approach enables us not to confine to state sets but also to deal with the state space. As we have shown, we are able to extend already known state sets and spacesby adding objects. Creating a state space as an extension of another state space saves us a lot of the effort needed to create both state spaces on their own.
It seems to be possible to generalize from extending a specific state space by adding one object to a generic algorithm that is able to build the state space of any extension of a given domain instance.
We believe that some work should be done on the question whether it is possible to extend plans in a similar way as extending state spaces. If we create new states and operations by adding facts to the description of the states and operations, we can do that on a plan in the same way. It is clear that a plan for moving a car from one shore to another is similar to the one that is needed to move any other car in the same way. But this is not what we mean. What we mean is, that in the same way we add facts to states in the state set of a domain instance, we can add these facts to the states of an existing plan. This means that we can extend plans of a planning world to plans of the extended planning world. To do so, we need not create the complete state set, and having all possible prototypes of a domain (see chapter 4.5), we even do not have to create the additional operations needed to extend the adjacency matrix, because in that case extending the adjacency matrix is unnecessary, too.
On the semantic level, it is reasonable that in the ferry domain a plan for moving a car across the river keeps the same, regardless of how much other cars are at one of the shores. It is of course clear, that when we add a second car to such a plan, we mustn’t put it on the ferry. But we will not do so, because we cannot do so. How that? In the original plan, the ferry is empty, as long as the first car is not boarded (and also after debarking). Therefore we cannot put the second car on the ferry, because (on-ferry c2) is incompatible to (empty). The same applies to the states of the plan where the first car is on the ferry, because (on-ferry c2) is also incompatible to (on-ferry c1). This results in the fact that we only can extend the plan in a reasonable way, i.e. putting the second car at one of the shores.
Another interesting field for future work are static facts. As statics do not have any influence on the set of states, their role lies in defining the structure of the state space and therefore they are very important for planning. It can be proved that the travel domain instance with one person, one bulldozer and two cities has a similar set of states as the ferry domain instance with one ferry, one car and two shores. In fact, the person corresponds with the ferry, the bulldozer corresponds with the car and the two cities correspond with the two shores. The only difference between the two domains is that in the travel domain we have some static facts, defining which of the cities are connected. Here the static facts play the role of restricting the freedom of action.
We think that investigating the effects of defining static facts, we are able to find some kind of domain hierarchy, based on the data type that is provided by the objects being involved in a domain instance. For example, we consider a state of a ferry domain instance to be based on a set of sets, namely a set of shores, each containing a set of cars. Corresponding to this point of view, the states of a hanoi domain instance also provide a set of sets: a set of pegs, each containing a set of disks. It applies to both domains, that each object can be at each place (i.e. each element can be in any set), but the hanoi domain restricts the movement of the discs by a static fact (smaller ?d1 ?d2). Therefore hanoi and ferry are derivations of the same domain set-of-sets.
What the researchers from the university of Durham call enablers is a class of facts, that in addition to the statics consists of facts, that play the same role. For example, the predicate fuelled of the rocket domain restricts the freedom of movement in the same way as a static fact, whereas the predicate empty of the ferry domain restricts the number of cars that can be on the ferry. If we leave away the predicate empty, the ferry domain becomes isomorphic to the briefcase domain, and so does the rocket domain, if we leave away fuelled. This leads us to the fact that both ferry and rocket are derivations of the briefcase domain, which in turn is a derivation of a pure set-of-sets domain. We are able to find even more connections between different domains, all depending on static facts and other enablers.
Bibliography
|[AU96] |Aho, A.V., and J.D.Ullman. Informatik: Datenstrukturen und Konzepte der Abstraktion. International Thomson |
| |Publishing.1996 |
| | |
|[AWS98] |Anderson, C., D.Weld and D.Smith. Conditional Effects in Graphplan. In: Proceedings of the 4th International |
| |Conference Artificial Intelligence, 1998 |
| | |
|[B92] |Bryant, R.E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams. CMU-CS-92-160, Carnegie Mellon |
| |University, 1992 |
| | |
|[BF97] |Blum, A., and M. Furst. Fast Planning Through Planning Graph Analysis. In: Artificial Intelligence, 90:281-300, 1997 |
| | |
|[BG98] |Bonet, B., and H. Geffner. HSP: Heuristic Search Planner. Entry at the AIPS-98 Planning Competition, Pittsburgh, 1998 |
| | |
|[BG99] |Bonet, G., and H. Geffner. Planning as Heuristic Search: New Results. In: Proceedings of ECP-99, Springer, 1999. |
| | |
|[BG00] |Bonet, G., 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 |
| | |
|[BK71] |Bron, C., and J. Kerbosch. Finding All Cliques of an undirected Graph. In: Collected Algorithms from CACM, Alg.457, |
| |1971 |
| | |
|[EH99] |Edelkamp, S., and M. Helmert. Exhibiting Knowledge in Planning Problems to Minimize State Encoding Length. ECP, |
| |Durham, pp 135-147, LNAI, Springer, 1999 |
| | |
|[F99] |Fink, E. Automatic Representation Changes in Problem Solving. Doctoral Thesis, CMU-CS-99-150, Carnegie Mellon |
| |University, 1999 |
|[GH98] |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 |
|[FL98] |Fox, M., and D.P. Long. The Automatic Inference of State Invariants in TIM. In: Journal of Artificial Intelligence |
| |Research, 9:376-421, 1998 |
| | |
|[FL99a] |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 |
| | |
|[FL99b] |Fox, M., and D.P. Long. The Detection and Exploitation of Symmetry in Planning Domains. Technical Report 1/99, Durham |
| |University, 1999 |
| | |
|[FN71] |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 |
| | |
|[GKR97] |Giunchiglia, E., G.N. Kartha and V. Lifschitz. Representing action: Indeterminacy and Ramifications. Artificial |
| |Intelligence, 95(2):409-438, 1997 |
| | |
|[GL93] |Gelfond, M., and V. Lifschitz. Representing Actions and Change by Logic Programs. In: The Journal of Logic |
| |Programming, 17:301-322, 1993 |
| | |
|[GL98] |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 |
| | |
|[J99] |Jensen, R.M., OBDD-based Universal Planning in Multi-Agent, Non-Deterministic Domains. Master’s Thesis, University of |
| |Denmark, 1999 |
| | |
|[KS99] |Kautz, H., and B. Selman. Unifying SAT-based and Graph-based Planning. In: Proceedings of the IJCAI ’99, Stockholm, |
| |1999 |
| | |
|[MH69] |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 |
| | |
|[N00] |Nebel, B. On the Compilability and Expressive Power of Propositional Planning Formalisms. In: Journal of Artificial |
| |Intelligence Research, 12:271-315, 2000 |
| | |
|[P89] |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 |
| | |
|[P97] |Pardalos, P.M. An Algorithm for Finding the Maximum Clique on an Arbitrary Graph. University of Florida, 1997 |
| | |
| | |
|[PW92] |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 |
| | |
|[PX94] |Pardalos, P.M., and J. Xue. The Maximum Clique Problem. In: Journal of Global Optimization, 4:301-328, 1994. |
| | |
|[Sch87] |Schoppers, M.J. Universal Plans for Reactive Robots in Unpredictable Environments. In: IJCAI ’87, pp 1039-1046, 1987 |
| | |
|[Sch99] |Schmid, U. Iterative Macro-Operators Revisited: Applying Program Synthesis to Learning in Planning. Technical Report |
| |CMU-CS-99-114, Carnegie Mellon University, 1999 |
| | |
|[SW00] |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 |
| | |
| | |
Appendix A
Domain Specifications
We give a couple of domain specifications as we used them for our research. All domains are defined in PDDL and are mainly taken from the AIPS ’98 planning competition.
A.1 Ferry
The ferry domain is one of the most simple domains where all operators are STRIPS-like, i.e. they do not have any quantifiers, disjunctions or conditional effects. The ferry domain was originally introduced 1993 by T. Barrett from the University of Washington and was one of the domains from the AIPS ’98 planning competition. We used the typed version of the domain and manipulated it in the way that we minimized it by removing the domain constant the-ferry and using the ferry implicitly instead.
(define (domain ferry-minimal)
(:requirements :strips :equality :typing)
(:types car place)
(:predicates
(atferry ?l - place)
(at ?x - car ?y - place)
(on-ferry ?x - car)
(empty))
(:action board
:parameters (?x - car ?y - place)
:precondition (and (at ?x ?y) (atferry ?y) (empty))
:effect (and (on-ferry ?x) (not (at ?x ?y)) (not (empty))))
(:action sail
:parameters (?x ?y - place)
:precondition (and (atferry ?x) (not (= ?x ?y)))
:effect (and (atferry ?y) (not (atferry ?x))))
(:action debark
:parameters (?x - car ?y - place)
:precondition (and (on-ferry ?x) (atferry ?y))
:effect (and (at ?x ?y) (empty) (not (on-ferry ?x)))))
We additionally wrote a quantified version of the original ferry domain by removing the predicate (empty) and using the expression (forall (?z - auto) (not (on ?z the-ferry))) instead.
(define (domain ferry-quantified)
(:requirements :equality :typing :quantified-preconditions)
(:types car place ferry)
(:constants the-ferry - ferry)
(:predicates
(atferry ?l - place)
(at ?x - car ?y - place)
(on-ferry ?x - car ?f - ferry))
(:action board
:parameters (?x - car ?y - place)
:precondition (and (at ?x ?y)(atferry ?y)
(forall (?z - car) (not (on ?z the-ferry))))
:effect (and (on-ferry ?x the-ferry) (not (at ?x ?y))))
(:action sail
:parameters (?x ?y - place)
:precondition (and (atferry ?x) (not (= ?x ?y)))
:effect (and (atferry ?y) (not (atferry ?x))))
(:action debark
:parameters (?x - car ?y - place)
:precondition (and (on-ferry ?x the-ferry) (atferry ?y))
:effect (and (at ?x ?y) (not (on ?x the-ferry)))))
A.2 Blocks-World
The blocks-world domain is one of the most investigated domains ever. We use a simple version which we compiled to PDDL from a proprietary version we found in [Sch99].
(define (domain blocks)
(:requirements :strips :equality)
(:predicates (on ?x ?y) (ct ?x))
(:action PutTable
:parameters (?x)
:vars (?y)
:precondition (and (on ?x ?y) (ct ?x) (not (= ?x ?y)))
:effect (and (ct ?y) (not (on ?x ?y))))
(:action Put
:parameters (?x ?y)
:vars (?z)
:precondition (and (ct ?x) (ct ?y) (not (= ?x ?y)))
:effect (and (on ?x ?y) (not (ct ?y))
(when (and (on ?x ?z) (not (= ?x ?z)) (not (= ?y ?z)))
(and (not (on ?x ?z)) (ct ?z))))))
As discussed in chapter 3.2.1, this domain specification leads to a state set, that does not correspond with the blocks-world (set-of-lists), but is the one of a set-of-trees domain. A varied definition, which results in the correct set of the blocks-world domain is the following one.
(define (domain blocks-deterministic)
(:requirements :adl)
(:predicates (on ?x ?y) (ct ?x))
(:action PutTable
:parameters (?x)
:vars (?y)
:precondition (and (ct ?x) (on ?x ?y) (not (= ?x ?y))
(forall (?z)
(or (and (= ?z ?y) (on ?x ?z))
(and (not (= ?z ?y)) (not (on ?x ?z))))))
:effect (and (ct ?y) (not (on ?x ?y))))
(:action Put
:parameters (?x ?y)
:vars (?z)
:precondition (and (ct ?x) (ct ?y) (not (= ?x ?y))
(or (forall (?w) (not (on ?x ?w)))
(and (on ?x ?z) (not (= ?x ?z))
(forall (?v) (or (and (= ?v ?z) (on ?x ?v))
(and (not (= ?v ?z))
(not (on ?x ?v))))))))
:effect (and (on ?x ?y) (not (ct ?y))
(when (and (on ?x ?z) (not (= ?x ?z)) (not (= ?y ?z)))
(and (not (on ?x ?z)) (ct ?z))))))
A.3 Briefcase
We took the simple strips version of the briefcase domain from the AIPS ’98 planning competition, which only knows a single briefcase, given by the domain constant b.
(define (domain briefcase-strips)
(:requirements :strips :equality)
(:constants B)
(:predicates
(at ?x ?y)
(in ?x ?y))
(:action move-briefcase
:parameters (?m ?l)
:precondition (and (at B ?m) (not (= ?m ?l)))
:effect (and (not (at B ?m))(at B ?l)))
(:action take-out
:parameters (?x ?y)
:precondition (and (at B ?y) (in ?x B) (not (= ?x B)))
:effect (and (not (in ?x B))(at ?x ?y)))
(:action put-in
:parameters (?x ?y)
:precondition (and (at ?x ?y) (at B ?y) (not (= ?x B)))
:effect (and (not (at ?x ?y)) (in ?x B))))
A.4 Rocket
The rocket domain is a domain where the state space graph is divided into two components.
(define (domain rocket)
(:requirements :strips :equality :typing)
(:types thing location)
(:predicates
(at ?x - thing ?l - location)
(atR ?l - location)
(inR ?x - thing)
(fuelled))
(:action moveR
:parameters (?l1 ?l2 - location)
:precondition (and (fuelled) (atR ?l1) (not (= ?l1 ?l2)))
:effect (and (not (fuelled))(not (atR ?l1)) (atR ?l2)))
(:action load
:parameters (?x - thing)
:vars (?l - location)
:precondition (and (atR ?l) (at ?x ?l))
:effect (and (inR ?x) (not (at ?x ?l))))
(:action unload
:parameters (?x - thing)
:vars (?l - location)
:precondition (and (atR ?l) (inR ?x))
:effect (and (not (inR ?x)) (at ?x ?l))))
A.5 Hanoi
We used a hanoi domain introduced by Fink in [F99], which provides exactly three pegs, given as domain constants, and three implicit disks.
(define (domain hanoi-3-disks)
(:requirements :strips :equality)
(:predicates (small-on ?x) (medium-on ?x) (large-on ?x))
(:constants PEG1 PEG2 PEG3)
(:action move-small
:parameters (?x ?y)
:precondition (and (small-on ?x) (not (= ?x ?y)))
:effect (and (small-on ?y) (not (small-on ?x))))
(:action move-medium
:parameters (?x ?y)
:precondition (and (medium-on ?x) (not (small-on ?x))
(not (small-on ?y)) (not (= ?x ?y)))
:effect (and (medium-on ?y) (not (medium-on ?x))))
(:action move-large
:parameters (?x ?y)
:precondition (and (large-on ?x) (not (small-on ?x))
(not (small-on ?y)) (not (medium-on ?x))
(not (medium-on ?y)) (not (= ?x ?y)))
:effect (and (large-on ?y) (not (large-on ?x)))))
In addition to that we wrote a quantified version of the domain with a random number of pegs and disks.
(define (domain hanoi)
(:requirements :adl :typing)
(:types disk peg)
(:predicates (on ?x - disk ?p - peg) (smaller ?x ?y - disk))
(:action move-on
:parameters (?d1 ?d2 - disk ?p1 ?p2 - peg)
:precondition (and (smaller ?d1 ?d2) (on ?d1 ?p1)
(on ?d2 ?p2) (not (= ?d1 ?d2)) (not (= ?p1 ?p2)))
:effect (and (on ?d1 ?p2) (not (on ?d1 ?p1))))
(:action move
:parameters (?d1 - disk ?p1 ?p2 - peg)
:precondition (and (on ?d1 ?p1)
(forall (?d2 - disk) (not (on ?d2 ?p2))))
:effect (and (on ?d1 ?p2) (not (on ?d1 ?p1)))))
A.6 Travel
The travel domain also took part in the AIPS ’98 planning competition.
(define (domain travel)
(:requirements :strips :equality :typing)
(:types city physobj - object person vehicle - physobj)
(:predicates
(road ?x ?y - city)
(bridge ?x ?y - city)
(at ?x - physobj ?p - city)
(mobile ?x - physobj)
(driving ?p - person ?v - vehicle))
(:action Drive
:parameters (?x - physobj ?p1 ?p2 - city)
:precondition (and (road ?p1 ?p2) (at ?x ?p1) (mobile ?x)
(not (= ?p1 ?p2)))
:effect (and (at ?x ?p2) (not (at ?x ?p1))))
(:action Cross
:parameters (?x - physobj ?p1 ?p2 - city)
:precondition (and (bridge ?p1 ?p2) (at ?x ?p1) (mobile ?x)
(not (= ?p1 ?p2)))
:effect (and (at ?x ?p2) (not (at ?x ?p1))))
(:action Board
:parameters (?p - person ?l - city ?v - vehicle)
:precondition (and (at ?p ?l) (at ?v ?l) (mobile ?p))
:effect (and (driving ?p ?v) (mobile ?v) (not (at ?p ?l))
(not (mobile ?p))))
(:action Disembark
:parameters (?p - person ?l - city ?v - vehicle)
:precondition (and (driving ?p ?v) (at ?v ?l) (mobile ?v))
:effect (and (at ?p ?l) (mobile ?p) (not (driving ?p ?v))
(not (mobile ?v)))))
A.7 Monkey
The monkey domain we used is a light version of the one originally introduced by Barrett in 1993. We skipped the water problem. We also invented a static predicate (fix-at ?x – fixobj ?y – location). This predicate is used to specify where the knife and the bananas are. We could have done this by the predicate at, but in that case our algorithm would create the states of all components of the state space graph, with each possible position of the knife as well as the bananas. Using the static predicate causes the creation of one component only.
(define (domain monkey)
(:requirements :strips :equality :typing)
(:types fixobj dynobj location - object)
(:predicates
(on-floor)
(at ?m - dynobj ?x - location)
(hasknife)
(onbox ?x - location)
(hasbananas)
(fix-at ?x - fixobj ?y - location))
(:constants the-monkey the-box - dynobj knife bananas - fixobj)
(:action go-to
:parameters (?x ?y - location)
:precondition (and (not (= ?y ?x)) (on-floor)
(at the-monkey ?x))
:effect (and (at the-monkey ?y) (not (at the-monkey ?x))))
(:action climb
:parameters (?x - location)
:precondition (and (on-floor) (at the-box ?x)
(at the-monkey ?x))
:effect (and (onbox ?x) (not (on-floor))))
(:action push-box
:parameters (?x ?y - location)
:precondition (and (not (= ?y ?x)) (at the-box ?x)
(at the-monkey ?x) (on-floor))
:effect (and (at the-monkey ?y) (not (at the-monkey ?x))
(at the-box ?y) (not (at the-box ?x))))
(:action get-knife
:parameters (?y - location)
:precondition (and (fix-at knife ?y) (at the-monkey ?y)
(on-floor))
:effect (hasknife))
(:action grab-bananas
:parameters (?y - location)
:precondition (and (hasknife) (fix-at bananas ?y) (onbox ?y))
:effect (hasbananas)))
A.8 Life
The life domain is an invention of the author to illustrate the problem that the compatibility of pairs of facts may not be decided on its own, but may depend on a third fact. This problem raises from the spend-money operator.
(define (domain life)
(:requirements :equality :typing)
(:types person thing)
(:predicates
(child ?p – person)
(adult ?p – person)
(has-money ?p - person)
(have ?x – thing ?p - person))
(:action grow-up
:parameters (?p - person)
:precondition (child ?p)
:effect (and (adult ?p) (not (child ?p))))
(:action earn-money
:parameters (?p - person)
:precondition (and (adult ?p)(not(exist (?x - thing)(have ?x))))
:effect (has-money ?p))
(:action spend-money
:parameters (?p – person ?x – thing)
:vars (?y)
:precondition (and (has-money ?p) (not (have ?x)))
:effect (have ?x)
(when (and (have ?y) (not (= ?y ?x)))(not (has-money ?p)))))
Appendix B
Realization of the Introduced Algorithms
To give an example of the algorithms of chapter 4, we will introduce in detail the creation of the state set and state space of the travel domain instance with one person, one bulldozer and two cities. To simplify the example we will assume the cities to be connected in all directions by roads except from appendix B.4 where we want to show the effects of changing the set of static facts.
B.1 Creation of the Domain Instance
We want to create the instance (( travel, O ), where the travel domain is defined as in appendix A.6 and O = { jack - person, bulldozer - vehicle, c1 - city, c2 - city }.
Creating the set of facts
We can retrieve the set of atoms from the :predicates field of the domain. We get
A = { (road ?x ?y - city), (bridge ?x ?y - city), (at ?x - physobj ?p - city),
(mobile ?x - physobj), (driving ?p - person ?v - vehicle) }
We can prove that the predicates road and bridge are statics, for they do not occur in any operator effect. Therefore we can split A into two subsets
A = Â ( A’
where the subsets are defined as
 = { (road ?x ?y - city), (bridge ?x ?y - city) }
A’ = { (at ?x - physobj ?p - city), (mobile ?x - physobj),
(driving ?p - person ?v - vehicle) }
For both atoms of  we get a set of valid substitutions[43]
( = { (1, (2 } with
(1 = { c1/?x, c2/?y }
(2 = { c2/?x, c1/?y }
With these substitutions we get a set of static facts
Ŝ = { (1( (road ?x ?y) ), (2( (road ?x ?y) ), (1( (bridge ?x ?y), (2( (bridge ?x ?y) }
= { (road c1 c2), (road c2 c1), (bridge c1 c2), (bridge c2 c1) }
As mentioned, we will for simplicity reasons assume all of these static facts to be valid.
For the instantiation of the predicate at we can find the substitutions
( = { (1, (2, (3, (4 } with
(1 = { jack/?x, c1/?p }
(2 = { jack/?x, c2/?p }
(3 = { bulldozer/?x, c1/?p }
(4 = { bulldozer/?x, c2/?p }
which leads to a set of facts
F1 = { (1( (at ?x ?p) ), (2( (at ?x ?p) ), (3( (at ?x ?p) ), (4( (at ?x ?p) ) }
= { (at jack c1), (at jack c2), (at bulldozer c1), (at bulldozer c2) }
Similarly, for the predicate mobile we find the substitutions
( = { (1, (2 } with
(1 = { jack/?x }
(2 = { bulldozer/?x }
and create the facts
F2 = { (1( (mobile ?x) ), (2( (mobile ?x) ) }
= { (mobile jack), (mobile bulldozer) }
Eventually, the predicate driving raises the substitutions
( = { (1 } with
(1 = { jack/?p, bulldozer/?v }
which results in the set of facts
F3 = { (1( (driving ?p ?v ) ) }
= { (driving jack bulldozer) }
The complete set of non-static facts of the domain instance is then given as
F = F1 ( F2 ( F3
= { (at jack c1), (at jack c2), (at bulldozer c1), (at bulldozer c2),
(mobile jack), (mobile bulldozer), (driving jack bulldozer) }
Creating the set of operations
The operators are instantiated in the same way as the atoms, namely by finding substitutions for the variables. We will again assume the equality constraints to be held.
For the drive operation
(:action drive
:parameters (?x - physobj ?p1 ?p2 - city)
:precondition (and (road ?p1 ?p2) (at ?x ?p1) (mobile ?x) (not (= ?p1 ?p2)))
:effect (and (at ?x ?p2) (not (at ?x ?p1))))
we get a set of substitutions
( = { (1, (2, (3, (4 } with
(1 = { jack/?x, c1/?p1, c2/?p2 }
(2 = { jack/?x, c2/?p1, c1/?p2 }
(3 = { bulldozer/?x, c1/?p1, c2/?p2 }
(4 = { bulldozer/?x, c2/?p1, c1/?p2 }
From these substitutions we get a set of instances of the operator drive which is given as
OP1 = (( drive ) = (1( drive ) ( (2( drive ) ( (3( drive ) ( (4( drive )
= { ((1( (0 ), (1( (0 )) } ( { ((2( (0 ), (2( (0 )) } ( { ((3( (0 ), (3( (0 )) } (
{ ((4( (0 ), (4( (0 )) }
= { (PREC1,0, EFF1,0) } ( { (PREC2,0, EFF2,0) } ( { (PREC3,0, EFF3,0) } (
{ (PREC4,0, EFF4,0) }
= { (PREC1,0, EFF1,0), (PREC2,0, EFF2,0), (PREC3,0, EFF3,0), (PREC4,0, EFF4,0) }
= { ({(road c1 c2), (at jack c1), (mobile jack)}, {(at jack c2), ((at jack c1)}),
({(road c2 c1), (at jack c2), (mobile jack)}, {(at jack c1), ((at jack c2)}),
({(road c1 c2), (at bulldozer c1), (mobile bulldozer)},
{(at bulldozer c2), ((at bulldozer c1)}),
({(road c2 c1), (at bulldozer c2), (mobile bulldozer)},
{(at bulldozer c1), ((at bulldozer c2)}) }
For the cross operator is identical to the drive operator except from the static atom bridge, which is used with the cross operator instead of the static atom road, we will skip the instantiation of the cross operator but only give the resulting set of operations
OP2 = { ({(bridge c1 c2), (at jack c1), (mobile jack)},
{(at jack c2),((at jack c1)}),
({(bridge c2 c1), (at jack c2), (mobile jack)},
{(at jack c1), ((at jack c2)}),
({(bridge c1 c2), (at bulldozer c1), (mobile bulldozer)},
{(at bulldozer c2), ((at bulldozer c1)}),
({(bridge c2 c1), (at bulldozer c2), (mobile bulldozer)},
{(at bulldozer c1), ((at bulldozer c2)}) }
The board operator
(:action board
:parameters (?p - person ?l - city ?v - vehicle)
:precondition (and (at ?p ?l) (at ?v ?l) (mobile ?p))
:effect (and (driving ?p ?v) (mobile ?v) (not (at ?p ?l)) (not (mobile ?p))))
comes along with two substitutions
( = { (1, (2 } with
(1 = { jack/?p, c1/?l, bulldozer/?v }
(2 = { jack/?p, c2/?l, bulldozer/?v }
The operations can then be found as
OP3 = (( board ) = (1( board ) ( (2( board )
= { ((1( (0 ), (1( (0 )) } ( { ((2( (0 ), (2( (0 )) }
= { (PREC1,0, EFF1,0) } ( { (PREC2,0, EFF2,0) }
= { (PREC1,0, EFF1,0), (PREC2,0, EFF2,0) }
= { ({(at jack c1), (at bulldozer c1), (mobile jack)},
{(driving jack bulldozer), (mobile bulldozer), ((at jack c1),
((mobile jack)}),
({(at jack c2), (at bulldozer c2), (mobile jack)},
{(driving jack bulldozer), (mobile bulldozer), ((at jack c2),
((mobile jack)}) }
debark, which is the reverse operator of board is given as
(:action disembark
:parameters (?p - person ?l - city ?v - vehicle)
:precondition (and (driving ?p ?v) (at ?v ?l) (mobile ?v))
:effect (and (at ?p ?l) (mobile ?p) (not (driving ?p ?v)) (not (mobile ?v))))
Therefore, it also has two substitutions which are
( = { (1, (2 } with
(1 = { jack/?p, c1/?l, bulldozer/?v }
(2 = { jack/?p, c2/?l, bulldozer/?v }
and lead to the operations
OP4 = (( debark ) = (1( debark ) ( (2( debark )
= { ((1( (0 ), (1( (0 )) } ( { ((2( (0 ), (2( (0 )) }
= { (PREC1,0, EFF1,0) } ( { (PREC2,0, EFF2,0) }
= { (PREC1,0, EFF1,0), (PREC2,0, EFF2,0) }
= { ({(driving jack bulldozer), (at bulldozer c1), (mobile bulldozer)},
{(at jack c1), (mobile jack), ((driving jack bulldozer),
((mobile bulldozer)}),
({(driving jack bulldozer), (at bulldozer c2), (mobile bulldozer)},
{(at jack c2), (mobile jack), ((driving jack bulldozer),
((mobile bulldozer)}) }
The complete set of operations of the domain instance is then given as
OP = OP1 ( OP2 ( OP3 ( OP4
and finally, the domain instance is
(( travel, O ) = (OP, F, Ŝ)
B.2 Construction of the Adjacency Matrix
The set of non-static facts of the travel domain instance we constructed in appendix B.1, consists of seven facts. We therefore create a (7,7)-matrix AF which we initialize by ?, except from the main diagonal which we initialize by zero. The initial matrix is given in figure B.1.
Figure B.1 Initial adjacency matrix of a travel domain instance
We use the simple version of the adjacency matrix, i.e. we prove pairs of facts rather than pairs of ground literals, because there is no need to use the latter with the travel domain.
To keep the example simple, we additionally do not make use of the reverse operations. Normally, we would have to do so, but in the travel domain all operators have a reverse operator defined in the domain. For the fact that drive and cross are symmetric, the reverse operation of a drive or cross operation is again a drive or cross operation, i.e.
drive( ?x, ?p1, ?p2 )-1 = drive( ?x, ?p2, ?p1 ) and
cross( ?x, ?p1, ?p2 )-1 = cross( ?x, ?p2, ?p1 )
To the other operators it applies that board is the reverse operator of debark, meaning that
board( ?p, ?l, ?v )-1 = debark( ?p, ?l, ?v ) and
debark( ?p, ?l, ?v )-1 = board( ?p, ?l, ?v )
We will often have to refer to the operations, so we will number them as given in table B.1.
|No. |Name |Precondition |Effect |
|1 |drive |(road c1 c2), (at jack c1), (mobile jack) |(at jack c2), ((at jack c1) |
|2 | |(road c2 c1), (at jack c2), (mobile jack) |{ (at jack c1), ((at jack c2) |
|3 | |(road c1 c2), (at bulldozer c1), |(at bulldozer c2), |
| | |(mobile bulldozer) |((at bulldozer c1) |
|4 | |(road c2 c1), (at bulldozer c2), |(at bulldozer c1), |
| | |(mobile bulldozer) |((at bulldozer c2) |
|5 |cross |(bridge c1 c2), (at jack c1), (mobile jack) |(at jack c2), ((at jack c1) |
|6 | |(bridge c2 c1), (at jack c2), (mobile jack) |{ (at jack c1), ((at jack c2) |
|7 | |(bridge c1 c2), (at bulldozer c1), |(at bulldozer c2), |
| | |(mobile bulldozer) |((at bulldozer c1) |
|8 | |(bridge c2 c1), (at bulldozer c2), |(at bulldozer c1), |
| | |(mobile bulldozer) |((at bulldozer c2) |
|9 |board |(at jack c1), (at bulldozer c1), (mobile jack) |(driving jack bulldozer), |
| | | |(mobile bulldozer), |
| | | |((at jack c1), ((mobile jack) |
|10 | |(at jack c2), (at bulldozer c2), (mobile jack) |(driving jack bulldozer), |
| | | |(mobile bulldozer), |
| | | |((at jack c2), ((mobile jack) |
|11 |debark |(driving jack bulldozer), (at bulldozer c1), |(at jack c1), (mobile jack), |
| | |(mobile bulldozer) |((driving jack bulldozer), |
| | | |((mobile bulldozer) |
|12 | |(driving jack bulldozer), (at bulldozer c2), |(at jack c2), (mobile jack), |
| | |(mobile bulldozer) |((driving jack bulldozer), |
| | | |((mobile bulldozer) |
Table B.1 The operations of the travel domain instance with one person, one bulldozer and two cities
We will now check the compatibility of each pair aij against the operations. To do so we use the algorithm of figure 4.13.
The results of this procedure is given in table B.2. If the compatibility cannot be decided, the column comp contains a question mark. The column op contains the index of the operation, which causes the decision (or -, if the pair is incompatible), whereas the column step gives the corresponding step of the algorithm. For each pair (i.e. each table row) the decision so far made are taken into account (the former table rows).
Table B.2 Decisions made in the 1st turn of the algorithm of figure 4.13
|pair |comp |op |step |
|a11 |0 |- |2.a.ii |
|a12 |? |11 |2.a.vi.7.b |
|a13 |1 |11 |2.a.vi.4 |
|a14 |? |2 |2.a.vi.7.b |
|a15 |1 |11 |2.a.vi.2 |
|a16 |? |2 |2.a.vi.7.b |
|a17 |? |2 |2.a.vi.7.b |
|a21 |? |12 |2.a.iv |
|a22 |0 |- |2.a.ii |
|a23 |? |1 |2.a.vi.7.b |
|a24 |1 |12 |2.a.iv |
|a25 |1 |12 |2.a.iv |
|a26 |? |1 |2.a.vi.7.b |
|a27 |? |1 |2.a.vi.7.b |
|a31 |? |4 |2.a.vi.7.b |
|a32 |? |4 |2.a.vi.7.b |
|a33 |0 |- |2.a.ii |
|pair |comp |op |step |
|a34 |0 |- |2.a.v |
|a35 |? |4 |2.a.vi.7.b |
|a36 |1 |4 |2.a.vi.4 |
|a37 |? |4 |2.a.vi.7.b |
|a41 |? |3 |2.a.vi.7.b |
|a42 |? |3 |2.a.vi.7.b |
|a43 |0 |- |2.a.iv |
|a44 |0 |- |2.a.ii |
|a45 |? |3 |2.a.vi.7.b |
|a46 |1 |3 |2.a.iv |
|a47 |? |3 |2.a.vi.7.b |
|a51 |1 |11 |2.a.vi.2 |
|a52 |1 |12 |2.a.iv |
|a53 |1 |11 |2.a.vi.4 |
|a54 |1 |12 |2.a.iv |
|a55 |0 |- |2.a.ii |
|a56 |0 |- |2.a.v |
|pair |comp |op |step |
|a57 |0 |- |2.a.v |
|a61 |? |10 |2.a.vi.7.b |
|a62 |? |9 |2.a.vi.7.b |
|a63 |1 |9 |2.a.vi.4 |
|a64 |1 |10 |2.a.iv |
|a65 |0 |- |2.a.v |
|a66 |0 |- |2.a.ii |
|a67 |1 |9 |2.a.vi.2 |
|a71 |? |10 |2.a.vi.7.b |
|a72 |? |9 |2.a.iv |
|a73 |1 |9 |2.a.vi.4 |
|a74 |1 |10 |2.a.iv |
|a75 |0 |- |2.a.v |
|a76 |1 |9 |2.a.vi.2 |
|a77 |0 |- |2.a.ii |
The resulting adjacency matrix is given in figure B.2.
Figure B.2 Adjacency matrix of a travel domain instance after the 1st turn
We now have to do a second turn in order to decide the yet undecided pairs. The results of the second turn is given in table B.3
Table B.3 Decisions made in the 2nd turn of the algorithm of figure 4.13
|pair |comp |op |step |
|a12 |? |11 |2.a.vi.7.b |
|a14 |1 |2 |2.a.vi |
|a16 |0 |- |2.a.vi.7.a |
|a17 |0 |- |2.a.vi.7.a |
|a21 |? |12 |2.a.iv |
|a23 |1 |1 |2.a.iv |
|a26 |0 |- |2.a.vi.7.a |
|pair |comp |op |step |
|a27 |0 |- |2.a.iv |
|a31 |? |4 |2.a.vi.7.b |
|a32 |? |4 |2.a.vi.7.b |
|a35 |0 |- |2.a.vi.7.a |
|a37 |1 |4 |2.a.vi. |
|a41 |? |3 |2.a.iv |
|a42 |? |3 |2.a.iv |
|pair |comp |op |step |
|a45 |0 |- |2.a.iv |
|a47 |1 |3 |2.a.iv |
|a61 |? |10 |2.a.vi.7.b |
|a62 |? |9 |2.a.iv |
|a71 |? |10 |2.a.vi.7.b |
|a72 |? |9 |2.a.iv |
Again, the adjacency matrix has varied (see figure B.3).
Figure B.3 Adjacency matrix of a travel domain instance after the 2nd turn
The third turn brings any new information, so that we are now forced to interact with the user.
Our implementation always saves the last undecided pair and offers it to the user. In our case the user would have to decide on the pair a72 = ((driving jack bulldozer), (at jack c2)), which is forbidden, because (driving jack bulldozer) is added, when jack enters the bulldozer, represented by the operator board. In that case jack isn’t any longer at some place.
With the new information we can start the fourth turn, which ends up in the new decisions given in table B.4
Table B.4 Decisions made in the 4th turn of the algorithm of figure 4.13
|pair |comp |op |step |
|a12 |0 |- |2.a.vi.7.a |
|a21 |0 |- |2.a.iv |
|a31 |? |4 |2.a.vi.7.b |
|a32 |? |4 |2.a.vi.7.b |
|pair |comp |op |step |
|a41 |? |3 |2.a.iv |
|a42 |? |3 |2.a.iv |
|a61 |0 |- |2.a.vi.7.a |
|a62 |0 |- |2.a.iv |
|pair |comp |op |step |
|a71 |0 |- |2.a.iv |
|a72 |0 |- |2.b |
The adjacency matrix after the fourth turn is given in figure B.4.
Figure B.4 Adjacency matrix of the travel domain instance after the 4th turn
The fifth turn decides on the last four pairs. The decisions are given in table B.5. The complete and fully initialized adjacency matrix of the travel domain with one person, one bulldozer and two cities is given in figure B.5.
Table B.5 Decisions made in the 4th turn of the algorithm of figure 4.13
|pair |comp |op |step |
|a41 |0 |- |2.a.iv |
|a42 |0 |- |2.a.iv |
|pair |comp |op |step |
|a31 |0 |- |2.a.v |
|a32 |0 |- |2.a.v |
Figure B.5 Adjacency matrix of the travel domain instance
B.3 Creation of the Set of States
The adjacency matrix of figure B.5 represents the adjacency graph given in figure B.6.
Figure B.6 Adjacency graph of the travel domain instance
Expanding each node leads to the following set of nodes. To illustrate the creation of the sets, we keep the order of the facts as it is when the facts are added to the set.
1. { 1, 5 } ( 3., 9.
2. { 2, 5 } ( 3., 9.
3. { 3, 1, 5 }
4. { 3, 2, 5 }
5. { 3, 5, 1 } = 3.
6. { 3, 5, 2 } = 4.
7. { 3, 6, 7 }
8. { 3, 7, 6 } = 7.
9. { 4, 1, 5 }
10. { 4, 2, 5 }
11. { 4, 5, 1 } = 9.
12. { 4, 5, 2 } = 10.
13. { 4, 6, 7 }
14. { 4, 7, 6 } = 13.
15. { 5, 1 } = 1.
16. { 5, 2 } = 2.
17. { 6, 3, 7 } = 7.
18. { 6, 4, 7 } = 13.
19. { 6, 7 } ( 7., 13.
20. { 7, 6 } ( 7., 13
The resulting set of states is
1. { 1, 3, 5 } = {(at jack c1), (at bulldozer c1), (mobile jack)}
2. { 1, 4, 5 } = {(at jack c1), (at bulldozer c2), (mobile jack)}
3. { 2, 3, 5 } = {(at jack c2), (at bulldozer c1), (mobile jack)}
4. { 2, 4, 5 } = {(at jack c2), (at bulldozer c2), (mobile jack)}
5. { 3, 6, 7 } = {(at bulldozer c1), (mobile bulldozer), (driving jack bulldozer)}
6. { 4, 6, 7 } = {(at bulldozer c2), (mobile bulldozer), (driving jack bulldozer)}
These states must be completed by the set of valid static facts, which we assumed to be
Ŝ = { (road c1 c2), (road c2 c1), (bridge c1 c2), (bridge c2 c1) }
= { fs,1, fs,2, fs,3, fs,4 }
B.4 Varying the Set of Static Facts
The adjacency matrix has been built without the static facts. From the matrix we created the states and afterwards added the set of static facts. This means that the set of states is always the same when we disregard the statics.
To simplify the example, we will now assume that the static facts built from the predicate bridge are all invalid. Therefore there is no valid cross operation.
Table B.6 gives all possible states spaces of the travel domain instance with one person j, one bulldozer b and two cities (left and right column), which are connected by roads, but not by bridges. In the right column of table B.6 both the valid and the invalid operations are given, depending on the set of valid static facts, given in the second column. The indices of the operations are taken from table B.1.
Table B.6 State spaces of the travel domain instances with two cities depending on the valid statics
|State Space | |Statics |Operations |
|b |Valid |{ fs,1, fs,2 } |{ 1, 2, 3, 4, 9, 10, 11, 12 } |
| | | | |
| | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
| |Invalid |{ fs,3, fs,4 } |{ 5, 6, 7, 8 } |
| |Valid |{ fs,1 } |{ 1, 3, 9, 10, 11, 12 } |
|b | | | |
| | | | |
|( | | | |
|b | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|( | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|b | | | |
|( | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
| |Invalid |{ fs,2, fs,3, fs,4 } |{ 2, 4, 5, 6, 7, 8 } |
| |Valid |{ fs,2 } |{ 2, 4, 9, 10, 11, 12 } |
|b | | | |
| | | | |
|( | | | |
|b | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|( | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|b | | | |
|( | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
| |Invalid |{ fs,1, fs,3, fs,4 } |{ 1, 3, 5, 6, 7, 8 } |
| |Valid |( |{ 9, 10, 11, 12 } |
|b | | | |
| | | | |
| | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
| | | | |
|b | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
| | | | |
| | | | |
|bj | | | |
| | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
|j | | | |
| | | | |
| | | | |
| |Invalid |{ fs,1, fs,2, fs,3, |{ 1, 2, 3, 4, 5, 6, 7, 8 } |
| | |fs,4 } | |
B.5 An Example of the Recursive Approach
We want to build the travel domain instance of chapter B.1 by recursively adding all the objects of that instance. We will begin with the domain instance without any objects. It is defined as
(( travel, ( ) = ( (, (, ()
Without objects we cannot instantiate any atom, so that both the set of non-static facts and the set of static facts is empty. This leads to an empty set of states. Without fact we cannot instantiate any of the operators, so that the set of operations is also empty. Therefore the state space of the travel domain instance without objects is
(0 = ((, ()
We now add one of the objects. It is irrelevant which object to add, so we choose the person jack. Doing so, we get a set of objects
O1 = { jack – person }
and a domain instance
(( travel, O1 ) = ((, FA,O1, ()
with a set of non-static facts
FA,O1 = { (mobile jack) }
The trivial adjacency matrix A1 of this instance has one cell, which contains a zero, corresponding to step 2.a.ii of the algorithm given in figure 4.13.
A single person enables us to create the first prototype of pairs which take one object of type person. This prototype is defined as
(1 = ( (1, P1, C1, (1 )
(1 = [person]
P1 = [ ((mobile jack), (mobile jack)) ]
C1 = [0]
The set of prototypes is therefore
( = { (1 }
Extending the one and only fact (mobile jack) leads to the state
s0 = { (mobile jack) }
which is the only state of the instance, resulting in a state space
(1 = ( { s0 }, ( )
We now want to add a city.
O2 = O1 ( { c1 – city } = { jack – person, c1 – city }
The extension of the domain instance (( travel, O1 ) is
(( travel, O2 ) = ((, FA,O2, ()
with a set of facts
FA,O2 = FA,O1 ( { (at jack c1) } = { (mobile jack), (at jack c1) }
We have found one new fact, so that we extend the adjacency matrix A1 to A2 by adding a single column and row. Although we cannot fully instantiate an operation, we can decide from the effect of the debark operator, that a12 = a21 = 1, whereas a22 = 0 according to step 2.a.ii of the algorithm. The extended matrix is
| |j |1 |2 |
|i | |(mobi|(at |
| | |le |jack |
| | |jack)|c1) |
|1 |(mobile jack) |0 |1 |
|2 |(at jack c1) |1 |0 |
We are able to create another prototype of pairs which take one object of type person and one of type city. This prototype is defined as
(2 = ( (2, P2, C2, (2 )
(2 = [person, city]
P2 = [ ((at jack c1), (at jack c1)),
((mobile jack), (at jack c1)), ((at jack c1), (mobile jack)) ]
C2 = [011]
Note, that we cannot find a prototype for a city only, because the travel domain does not provide any atoms, that just take an object of type city. The set of prototypes is therefore
( = { (1, (2 }
If we now build the states of the new instance we begin with extending the states of the former instance. The only state of the former instance trivially consists of only one fact, so that we get the state
s0 = { 1, 2 } = { (mobile jack), (at jack c1) }
For we have been able to instantiate facts that are not isomorphic to those we already had, we have to build states beginning with these new facts, namely with (at jack c1). But doing so does not result in further states, so that the new set of states is
S = { s0 }
We yet have no operations, so the state space of the new instance is
(2 = ( { s0 }, ( )
Adding a second city results in the set of objects
O3 = O2 ( { c2 – city } = { jack – person, c1 – city, c2 – city }
The domain instance raising from the new set of objects is
(( travel, O3 ) = (OP3, FA,O3, ŜA,O3)
with
FA,O3 = FA,O2 ( { (at jack c2) } = { (mobile jack), (at jack c1), (at jack c2) }
ŜA,O3 = { (road c1 c2), (road c2 c1), (bridge c1 c2), (bridge c2 c1) }
OP3 = { op1, op2, op5, op6 }
where the indices of the operations are taken from table B.1. According to the instance of chapter B.1, we define all static facts to be valid.
For the new non-static fact (at jack c2) we can make use of the prototype (2 to decide on the cells a13, a31 and a33.
a13 = (2( ((mobile jack), (at jack c2)) ) = 1
a31 = (2( ((at jack c2), (mobile jack)) ) = 1
a33 = (2( ((at jack c2), (at jack c2)) ) = 0
For the remaining pairs we can create a third prototype, which is defined as
(3 = ( (3, P3, C3, (3 )
(3 = [person, city, city]
P3 = [ ((at jack c1), (at jack c2)) ]
C3 = [0]
There is no prototype for two cities, because the travel domain does not provide any such atoms. The set of prototypes is therefore
( = { (1, (2, (3 }
We prove the incompatibility of (at jack c1) and (at jack c2) from the fact that all operations of OP3 that add (at jack c1) delete (at jack c2). The same applies to the reverse pairing. Therefore, the adjacency matrix A3 which we extended from A2 by adding a single column and row, is given as
| |j |1 |2 |3 |
|i | |(mobi|(at |(at |
| | |le |jack |jack |
| | |jack)|c1) |c2) |
|1 |(mobile jack) |0 |1 |1 |
|2 |(at jack c1) |1 |0 |0 |
|3 |(at jack c2) |1 |0 |0 |
In order to build the states of the new instance, we find that we cannot extend the state s0 of the former instance, because the only new fact is incompatible to (at jack c1), what means that s0 is also a state of the new instance[44], but must be enriched by the static facts:
s0 = { (mobile jack), (at jack c1) } ( Ŝ
We know that all new non-static facts are isomorphic to already known facts, so that we need not create additional states by expanding the new facts, but can build them by exchanging the objects of the same type in the description of s0. This means to exchange c1 and c2 which leads to the new state
s1 = { (mobile jack), (at jack c2) } ( Ŝ
resulting in a new set of states
S = { s0, s1 }
According to chapter 4.5.1, we would also exchange the objects in the operations of the smaller instance. But the smaller instance has no operations, so that we have nothing to do here. But we can instantiate new operations, and checking their applicability results in the new state space
(3 = ( { s0, s1 }, { (s0,s1,op1), (s1,s0,op2), (s0,s1,op5), (s1,s0,op6) ) } )
with a state space graph given in figure B.8.
Figure B.8 State space of the travel domain with one person and two cities
Finally, we add the bulldozer.
O4 = O3 ( { bulldozer – vehicle }
= { jack – person, c1 – city, c2 – city, bulldozer - vehicle }
We get a domain instance
(( travel, O4 ) = (OP4, FA,O4, ŜA,O4)
with
FA,O4 = FA,O3 ( { (at bulldozer c1), (at bulldozer c2), (mobile bulldozer),
(driving jack bulldozer) } =
{ (mobile jack), (at jack c1), (at jack c2), (at bulldozer c1),
(at bulldozer c2), (mobile bulldozer), (driving jack bulldozer) }
ŜA,O4 = ŜA,O3
OP4 = { op1, op2, op3, op4, op5, op6, op7, op8, op9, op10, op11, op12 }
The new facts raise six new prototypes.
(4 = ((4, P4, C4, (4)
(4 = [vehicle]
P4 = [ ((mobile bulldozer), (mobile bulldozer)) ]
C4 = [0]
(5 = ((5, P5, C5, (5)
(5 = [vehicle, city]
P5 = [ ((at bulldozer c1), (at bulldozer c1)),
((mobile bulldozer), (at bulldozer c1)),
((at bulldozer c1), (mobile bulldozer)) ]
C5 = [011]
(6 = ((6, P6, C6, (6)
(6 = [vehicle, city, city]
P6 = [ ((at bulldozer c1), (at bulldozer c2)) ]
C6 = [0]
(7 = ((7, P7, C7, (7)
(7 = [vehicle, person]
P7 = [ ((driving jack bulldozer), (driving jack bulldozer)),
((mobile jack), (mobile bulldozer)), ((mobile bulldozer), (mobile jack)),
((mobile jack), (driving jack bulldozer)),
((driving jack bulldozer), (mobile jack)),
((mobile bulldozer), (driving jack bulldozer)),
((driving jack bulldozer), (mobile bulldozer)) ]
C7 = [0000011]
(8 = ((8, P8, C8, (8)
(8 = [vehicle, city, person]
P8 = [ ((mobile bulldozer), (at jack c1)), ((at jack c1), (mobile bulldozer)),
((mobile jack), (at bulldozer c1)), ((at bulldozer c1), (mobile jack)),
((at bulldozer c1), (at jack c1)), ((at jack c1), (at bulldozer c1)),
((driving jack bulldozer), (at bulldozer c1)),
((at bulldozer c1), (driving jack bulldozer)),
((driving jack bulldozer), (at jack c1)),
((at jack c1), (driving jack bulldozer)) ]
C8 = [0010011100]
(9 = ((9, P9, C9, (9)
(9 = [vehicle, city, person, city]
P9 = [ ((at jack c1), (at bulldozer c2)), ((at bulldozer c1), (at jack c2)) ]
C9 = [10]
The compatibility checks of the new pairs of facts result in the extended adjacency matrix
j1234567i(mobile jack)(at jack c1)(at jack c2)(mobile bulldozer)(at bulldozer c1)(at bulldozer c2)(driving jack bulldozer)1(mobile jack)01101102(at jack c1)10001103(at jack c2)10001104(mobile bulldozer)00000015(at bulldozer c1)10010016(at bulldozer c2)10010017(driving jack bulldozer)0001110
The check of a a44 results in (4, while the check of the cells a55, a45 and a54 lead to (5. With (5 we can check the compatibility of a66, a46 and a64.
The cell a56 is used to build the prototype (6, which afterwards can be used to check the compatibility of a65.
(7 is built from the compatibility check of the cells a14, a41, a17, a71, a47, a74 and a77.
From the check of the cells a24, a42, a15, a51, a25, a52, a57, a75, a27 and a72 the prototype (8 is built. (8 can then be used to check the compatibility of the cells a34, a43, a16, a61, a36, a63, a67, a76, a37 and a73.
Eventually, a26 and a62 cause the prototype (9, which is used to check a35 and a53.
Building new states by extending the old ones leads to
s0 = { 1, 2, 5 } = { (mobile jack), (at jack c1), (at bulldozer c1) } ( Ŝ
s1 = { 1, 2, 6 } = { (mobile jack), (at jack c1), (at bulldozer c2) } ( Ŝ
s2 = { 1, 3, 5 } = { (mobile jack), (at jack c2), (at bulldozer c1) } ( Ŝ
s3 = { 1, 3, 6 } = { (mobile jack), (at jack c2), (at bulldozer c2) } ( Ŝ
For the operation between the states of the smaller instance keep the same, their extension ends up in two partial state spaces, given in figure B.9.
Figure B.9 Partial state spaces of the travel domain
Building further states beginning from the new facts results in two additional states
s4 = { 5, 4, 7 } ( Ŝ
= { (at bulldozer c1), (mobile bulldozer), (driving jack bulldozer) } ( Ŝ
s5 = { 6, 4, 7 } ( Ŝ
= { (at bulldozer c2), (mobile bulldozer), (driving jack bulldozer) } ( Ŝ
The new set of facts enables eight new operations to be instantiated: op3, op4, op7, op8, op9, op10, op11 and op12. Applying the new operations to the new states raises the eight new edges (s4, s5, op3), (s5, s4, op4), (s4, s5, op7), (s5, s4, op8), (s0, s4, op9), (s4, s0, op11), (s3, s5, op10) and (s5, s3, op12). This finally leads to the state space as it is given in figure B.10.
Figure B.10 State space of the travel domain instance
In our example we have assumed all static facts to be valid in the smaller instance as well as in the extended instance. If we want the set of valid static facts to change from one instance to the next, e.g. from (( travel, O3 ) to (( travel, O4 ), we can do so by simply varying that set. What we have to take into account is that the set of operations will change. In our case, we may for example invalidate the facts (road c2 c1) and (bridge c2 c1). This would lead to invalidation of operations that were valid before extension, namely op2 and op6. In addition, after extension, the operation op4 and op8 will not be instantiated as valid operations. These four invalid operations must be removed from the set of operations, to get a correct state space.
Appendix C
Notes on the Implementation
The program realizing the introduced (non-recursive) approach to create the state set of a domain instance is written in Common Lisp. It works on PDDL V1.2 and is capable of the following requirements.
:strips
:equality
:typing
:conditional-effects
:universal-preconditions
:existential-preconditions
:quantified-preconditions (= 5. + 6.)
:disjunctive-preconditions
:adl (= 1. + 2. + 3. + 4. + 5. + 6. + 8.)
Domain extension (keyword :extends) is not supported.
Within the Lisp interpreter the program may be started by the call
(load ‘updom.lsp)
To load a domain file call
(loadPDDLFile ‘ferry.lsp)
where ferry.lsp is the name of the PDDL file containing the domain to be loaded. The program supports to have more than one domain in a single file and offers them all by listing them up.
Available domains:
FERRY-QUANTIFIED
FERRY-TYPED
FERRY-MINIMAL
Use (loadDomainNo ) or (loadDomain ) to load a domain.
If the loaded file only contains a single domain, this step is skipped but the domain is loaded directly. Otherwise, there are two ways of loading one of the offered domains. The first is to call
(loadDomainNo 2)
which loads the domain with index 2, the other possibility is to call
(loadDomain ‘ferry-typed)
Having loaded the domain it is first checked whether all requirements are supported. If some requirements do not meet, an corresponding error message is printed. Otherwise the types of the domain are inferred, either by scanning the :types field (if :typing is used) or by analyzing the operators. The resulting type hierarchy is printed.
Domain FERRY-TYPED loaded.
The domain uses the following types:
OBJECT
|--AUTO
|--PLACE
|--FERRY
The user is now asked for objects of each provided type. Doing so, for each type the given domain constants are listed in brackets. The user is also asked for objects of all supertypes. The input of the user is to be a list of objects separated by spaces. If the list of objects is given in parentheses or even is a nested list, the lists are flattened and each atomic constant is treated as an object. The consistency of the given object lists are not proved. If the user gives the same object (i.e. the same constant) for more than one type, the program may fail to work properly. For the ferry domain instance with one car and two shores the user input may look like
Enter objects of type FERRY (THE-FERRY):
Enter objects of type PLACE (NO CONSTANTS): A B
Enter objects of type AUTO (NO CONSTANTS): BMW ROVER
Enter any additional objects of type OBJECT (NO CONSTANTS):
where the-ferry is a domain constant. The objects are listed in the variable ‘objects, where each object is a pair ( ).
Afterwards the operations are created which is reported by the output
Create Actions...
The operations are held in the variable ‘actions. For the program makes use of reverse operations, an element of the ‘actions list has the following structure.
a = ( )
This structure supports access to the reverse operation by the Lisp call (reverse a).
After creating the operations the program begins to construct the adjacency matrix
Create (6,6)-adjacency matrix...
In some cases after one turn over the complete matrix, not all pairs of facts have been decided. The user is in that case asked to decide on one of these pairs, which looks like
(AT ROVER B) - (AT BMW B) ? (y/n)
This shorthand output represents the question
“Can (AT rover b) be added to a set of facts containing (AT bmw B), in the way that it is not necessary to remove (at bmw b) from that set?”
The answer in this case is ‘y’(es). With this information the initialization of the adjacency matrix can be finished and the creation of the states is started, reported by
Build states...
Eventually, the adjacency matrix is output, together with the number of states and the time needed to create the states.
ADJACENCY MATRIX:
#2A(#*100111111
#*010111100
#*001110011
#*111101111
#*111011111
#*100011011
#*100100111
#*100011110
#*100101101
)
16 states created.
Real time: 0.18 sec.
Run time: 0.050072 sec.
Space: 5020 Bytes
The states themselves are held as bit vectors in the variable ‘states, whereas the matrix is given by ‘matrix, which is a two-dimensional array of bits with rank (n,n). The function call (printStates) lists up the states as sets of facts rather than as bit vectors.
On one view the creation of the states may look like this:
3. Break [5]> (loadPDDLFile 'ferry.lsp)
Available domains:
1. FERRY-QUANTIFIED
2. FERRY-TYPED
3. FERRY-MINIMAL
Use (loadDomainNo ) or (loadDomain ) to load a domain.
NIL
3. Break [5]> (loadDomainNo 3)
Domain FERRY-MINIMAL loaded.
The domain uses the following types:
OBJECT
|--AUTO
|--PLACE
Enter objects of type PLACE (NO CONSTANTS): A B
Enter objects of type AUTO (NO CONSTANTS): BMW ROVER FIAT VOLVO FORD
Enter any additional objects of type OBJECT (NO CONSTANTS):
Create Actions...
Construct (18,18)-adjacency matrix...
(AT FORD B) - (AT VOLVO B) ? (y/n) y
Build states...
ADJACENCY MATRIX:
#2A(#*100000111111111111
#*010000111111111100
#*001000111111110011
#*000100111111001111
#*000010111100111111
#*000001110011111111
#*111111101111111111
#*111111011111111111
#*100000011011111111
#*100000100111111111
#*100000011110111111
#*100000101101111111
#*100000011111101111
#*100000101111011111
#*100000011111111011
#*100000101111110111
#*100000011111111110
#*100000101111111101
)
224 states created.
Real time: 1.672 sec.
Run time: 1.2317712 sec.
Space: 34792 Bytes
If the domain provides static facts the user is asked to decide which possible instances of the facts should be valid. In the travel domain with three cities this looks like
1. (ROAD C3 C3) 2. (ROAD C3 C2) 3. (ROAD C3 C1)
4. (ROAD C2 C3) 5. (ROAD C2 C2) 6. (ROAD C2 C1)
7. (ROAD C1 C3) 8. (ROAD C1 C2) 9. (ROAD C1 C1)
10. (BRIDGE C3 C3) 11. (BRIDGE C3 C2) 12. (BRIDGE C3 C1)
13. (BRIDGE C2 C3) 14. (BRIDGE C2 C2) 15. (BRIDGE C2 C1)
16. (BRIDGE C1 C3) 17. (BRIDGE C1 C2) 18. (BRIDGE C1 C1)
Enter the indices of all valid statics: 17 2
The user may then input the indices of the valid static facts. For the travel domain, a complete run of the program looks like
3. Break [5]> (loadPDDLFile 'travel.lsp)
Domain TRAVEL loaded.
The domain uses the following types:
OBJECT
|--PLACE
|--PHYSOBJ
| |--PERSON
| |--VEHICLE
Enter objects of type PERSON (NO CONSTANTS): JACK
Enter objects of type VEHICLE (NO CONSTANTS): BULLDOZER
Enter any additional objects of type PHYSOBJ (NO CONSTANTS):
Enter objects of type PLACE (NO CONSTANTS): C1 C2 C3
Enter any additional objects of type OBJECT (NO CONSTANTS):
1. (ROAD C3 C3) 2. (ROAD C3 C2) 3. (ROAD C3 C1)
4. (ROAD C2 C3) 5. (ROAD C2 C2) 6. (ROAD C2 C1)
7. (ROAD C1 C3) 8. (ROAD C1 C2) 9. (ROAD C1 C1)
10. (BRIDGE C3 C3) 11. (BRIDGE C3 C2) 12. (BRIDGE C3 C1)
13. (BRIDGE C2 C3) 14. (BRIDGE C2 C2) 15. (BRIDGE C2 C1)
16. (BRIDGE C1 C3) 17. (BRIDGE C1 C2) 18. (BRIDGE C1 C1)
Enter the indices of all valid statics: 17 2
Statics are: ((ROAD C3 C2) (BRIDGE C1 C2))
Create Actions...
Construct (9,9)-adjacency matrix...
(DRIVING JACK BULLDOZER) - (AT JACK C2) ? (y/n) n
Build states...
ADJACENCY MATRIX:
#2A(#*101000111
#*010111111
#*101000111
#*010100111
#*010010111
#*010001111
#*101000100
#*101000010
#*101000001
)
12 states created.
Real time: 0.201 sec.
Run time: 0.0400576 sec.
Space: 4640 Bytes
For all operations and states are held in memory, the program may soon reach the limits of the memory space. Therefore it would be highly recommended to use OBDDs for both the operations as well as the states, which would also increase the computation time.
-----------------------
[1] We use the notation of [AU96] to refer to logic entities. An atom or atomic formula is a predicate with a number of parameters, which may be constants or variables. If the list of parameters only consists of constants, we talk about a ground atom or fact. A literal is an atom or its negation, whereas a ground literal is a fact or its negation.
[2] In the original paper, the conclusion of the implication is given as x = z, which we assume to be a printing error.
[3] Operations are sometimes called actions. We will not use this term because :action is a keyword of PDDL to introduce an operator specification.
[4] We make the closed-world assumption, i.e. we assume a property or relation to be false, if it is not given in a state description that is known to be complete.
[5] We skip domains using function application, which produce infinite state sets if the function domain is an infinite set.
[6] In the following, whenever we mention an initial state, we as well mean a goal description. The functional difference between initial state and goal description is irrelevant for our approach, for we are just creating state sets or state spaces, but are in the first case not planning. What we want to show is that we do not need the information an initial state or goal description provides, which in the first case is used for admissibility checks.
[7] Of course, we could define a domain, where roads must be built first before being able to use them. But in such a domain, the road and bridge predicates would not longer be static.
[8] We assume precedence of ( over \.
[9] This raises the question if we at all can find incompatible pairs of facts that fulfil the direct condition (1) of fact 3.2. The answer is that this is always true because if it wasn’t, everything would be allowed. If there is no pair of facts being mutual exclusive, condition (2) could neither become true for any pair of facts because of its implication. In that case all facts are mutual compatible and could be combined in one single state which would make it senseless to have any preconditions at all. But even then the adjacency matrix would be correct because it would contain a one in all cells then.
[10] As Schmid shows in [SW00], the blocks-world domain represents the data type set of lists. It is clear that elements of a list have at most one predecessor and one successor.
[11] This property of the blocks-world domain enables us to prove that the underlying data type is derived from a set of trees rather than from a set of lists and that therefore a set of lists only applies if a list is interpreted as a restricted tree having at most one child.
[12] For example, it is possible to completely decide all uncertainties of the blocks-world domain.
[13] This property does not mean that all states have the same number of facts. For example s0 = { (on-ferry c1) (atferry a) } is a legal state as well as s1 = { (at c1 a) (atferry a) (empty) } which has more facts than s0. But to both states it applies that there is no fact that can be added to one of them without making it invalid.
[14] For example, the blocks-world domain with 5 blocks has 501 unique states. By traversing the adjacency matrix, 23520 states are created, i.e. each state is approximately created 47 times.
[15] Singular states are states that can neither be reached by an operation nor be left by one, i.e. have no edge to any other state in a state space graph.
[16] In this example, due to equation (4) of fact 3.1 the created subset must be the complete state s0, because all operations have been used in the path to s0. Therefore we need not deal with literals here.
[17] The life domain is an invention of the author. The complete domain description can be found in appendix A.8.
[18] The domain does not provide any operator which makes it possible not to have a thing that one ever got.
[19] In the ferry domain that we introduced there is only one (implicit) ferry. Using the slightly different atoms (atferry ?f - ferry ?p - place), (empty ?f - ferry) and (on-ferry ?f - ferry ?c - car) we are also able to have more than one ferry.
[20] We have not introduced typed variables and objects yet (which we will do in chapter 4.1.1). therefore it is possible to produce incorrect facts. We ignore the problem at this point and assume the set of facts FA,O to contain only the correct facts.
[21] This applies to all domains that can be represented in STRIPS, for STRIPS does not know quantified expressions.
[22] PDDL domains provide a section :predicates where all atoms of a domain are listed. This section is optional, but if mentioned it is a simple way to get the set of atoms.
[23] After boarding the shore a we could of course sail to shore b and debark shore a there. We would then have a fact (at a b).
[24] PDDL knows a generic type object, which is used together with the :typing feature for objects that have no special type. Whenever a variable (or constant) has no type given it is assumed to be of type object.
[25] In fact, the problem leads to a flat type hierarchy with at most two levels. There is a simple but not very pretty solution to this problem. Instead of building a type hierarchy for person, vehicle and dynobj we simply add the atoms three times to A, each with a different type for the first variable. What we have to do then is to add all objects of type person as person as well as as dynobj. As set of objects may then look like O = { (jack – person), (bulldozer– vehicle), (jack – dynobj), (bulldozer – dynobj), (c1 – city), (c2 – city) }. This corresponds with the property of the type tree that an object of a specific type also is an object of all supertypes. Instantiating the atoms with these objects will lead to a correct set of facts because of the set properties of FA,O.
[26] It would be problematic if application of the operator first adds positive literals from the effect and afterwards deletes the negative ones because set operations are in most cases not commutative: M ( N \ X rarely is the same as M \ X ( N.
[27] PDDL supports it but has a requirement flag for it to enable planners to use PDDL even if not supporting equality constraints.
[28] Obeying the equality constraints discussed in 4.1.2 we are able to prevent (road c1 c1), (road c2 c2), (bridge c1 c1) and (bridge c2 c2) from being added to the set of statics.
[29] This applies to building the state space, because in that case we add the facts from the precondition when applying an operation. For all other facts are compatible to static facts, the statics have no influence on the applicability of an operation in the sense of fact 3.2. But the operation itself is invalid, so we will create incorrect state transitions.
[30] PDDL provides these features by adding the requirement flags :conditional-effects and :quantified-preconditions.
[31] This can be done, because being instantiated, a quantified expression becomes finite.
[32] We skip the symmetric operations marry( penelope ulysses ), because their body is completely identical to the given ones. The facts (female penelope) and (male ulysses) would normally be given as static facts. This would make our example improper, so we assume the facts not to be static.
[33] get-knife and grab-bananas always have only one operation because knife and bananas do not move.
[34] In fact, the forest has 26 leafs, which means that we create 26 states, whereas the domain instance only provides six states.
[35] This behaviour has an interesting connection to the planning problem, where the 10 cars shall be transported from shore a to shore b. There, it is also irrelevant in which order the cars are transported. Adding the fact (at c1 a) happens when applying the debark operation which of course has exactly the semantics that comes along with the planning problem.
[36] The implementation of this algorithm has to decide that two nodes p and q are connected, if the directed adjacency graph has at least one of the edges (p,q) or (q,p).
[37] In a single component graph there is at least one path over all nodes and all edges (see [AU96]). This path may walk over some nodes twice or more times.
[38] The number of non-static facts is pd, the number of valid static facts is d(d-1).
[39] As long as the monkey does not take the knife, the knife is at a fix position. This position may be at any of the given k places. Therefore the state space is divided into k components, because once the knife has been taken, it cannot be put at another place. The same applies to the bananas. Therefore, using the same predicate to define the position of the monkey, the box, the knife and the bananas, the complete set of states for all components are created. The number of facts correspond with this behavior. Using a static fact to define the position of the knife and the bananas, the number of facts would be 3k + 5, and the number of additional facts when increasing the number of places would be 3.
[40] We use sets of facts to simplify the diagram and the illustration of the problem. The following definition and algorithm can at any case be extended to work on literals rather than on facts.
[41] We can say that we have enabled the new object d to have all the properties and relations, the old object p could have had. Therefore, none of the objects of (2 can have any further property or relation to another object.
[42] The problem would also have occurred in the briefcase domain, if we extended the instance without thing to the one with one thing, because the put-in and the take-out operator cannot be instantiated in the instance without a thing.
[43] We would normally also instantiate the facts (road c1 c1), (road c2 c2), (bridge c1 c1) and (bridge c2 c2), which we would then recognize as invalid, because of the equality constraints of the operators (see chapter 4.1.2.).
[44] If we dealt with literals rather than with facts, we would have extended the state by adding ((at jack c2).
-----------------------
|op32 |
| |
|op02 |
| |
|op01 |
| |
|s3 |
| |
|s2 |
| |
|s1 |
| |
|s0 |
| |
|op03 |
| |
|(:act|
|ion |
|go-to|
|:para|
|meter|
|s (p1|
|p2) |
|:prec|
|ondit|
|ion |
|(and |
|(on-f|
|loor)|
|(at |
|the-m|
|onkey|
|p1)) |
|:effe|
|ct |
|(and |
|(at |
|the-m|
|onkey|
|p2) |
|(not |
|(at |
|the-m|
|onkey|
|p1)))|
|) |
| |
|(:act|
|ion |
|grab-|
|banan|
|as |
|:para|
|meter|
|s |
|(p2) |
|:prec|
|ondit|
|ion |
|(and |
|(has-|
|knife|
|) (at|
|banan|
|as |
|p2) |
|(on-b|
|ox |
|p2)) |
|:effe|
|ct |
|(has-|
|banan|
|as) )|
| |
|(:act|
|ion |
|board|
|:para|
|meter|
|s (?p|
|?x |
|?v) |
|:prec|
|ondit|
|ion |
|(and |
|(pers|
|on |
|?p) |
|(vehi|
|cle |
|?v) |
|(city|
|?x) |
|(at |
|?p |
|?x) |
|(at |
|?v |
|?x) |
|(not |
|(= ?p|
|?v)))|
|:effe|
|ct |
|(and |
|(driv|
|ing |
|?p |
|?v) |
|(mobi|
|le |
|?v) |
|(not |
|(at |
|?p |
|?x)) |
|(not |
|(mobi|
|le |
|?p)))|
|) |
| |
|(:act|
|ion |
|cross|
|:para|
|meter|
|s (?t|
|?x |
|?y) |
|:prec|
|ondit|
|ion |
|(and |
|(mobi|
|le |
|?t) |
|(dyno|
|bj |
|?t) |
|(city|
|?x) |
|(city|
|?y) |
|(brid|
|ge ?x|
|?y) |
|(at |
|?t |
|?x) |
|(not |
|(= ?x|
|?y)))|
|:effe|
|ct |
|(and |
|(at |
|?t |
|?y) |
|(not |
|(at |
|?t |
|?x)))|
|) |
| |
| |
|brief|
|case |
| |
|thing|
| |
|dynob|
|j |
| |
|locat|
|ion |
| |
|objec|
|t |
| |
|{ |
| |
|(:act|
|ion |
|board|
|:para|
|meter|
|s |
|(bmw |
|a) |
|:prec|
|ondit|
|ion |
|(and |
|(atfe|
|rry |
|a) |
|(at |
|bmw |
|a) |
|(empt|
|y)) |
|:effe|
|ct |
|(and |
|(on-f|
|erry |
|bmw) |
|(not |
|(at |
|bmw |
|a)) |
|(not |
|(empt|
|y))))|
| |
|(:act|
|ion |
|debar|
|k |
|:para|
|meter|
|s |
|(bmw |
|a) |
|:prec|
|ondit|
|ion |
|(and |
|(atfe|
|rry |
|a) |
|(on-f|
|erry |
|bmw))|
|:effe|
|ct |
|(and |
|(at |
|bmw |
|a) |
|(empt|
|y) |
|(not |
|(on-f|
|erry |
|bmw))|
|) |
| |
|(:act|
|ion |
|sail |
|:para|
|meter|
|s (a |
|b) |
|:prec|
|ondit|
|ion |
|(atfe|
|rry |
|a) |
|:effe|
|ct |
|(and |
|(atfe|
|rry |
|b) |
|(not |
|(atfe|
|rry |
|a))))|
| |
| |
|(:act|
|ion |
|putta|
|ble |
|:para|
|meter|
|s (b)|
|:prec|
|ondit|
|ion |
|(and |
|(ct |
|b) |
|(on b|
|a)) |
|:effe|
|ct |
|(and |
|(ct |
|a) |
|(not |
|(on b|
|a))))|
| |
|(:act|
|ion |
|put |
|:para|
|meter|
|s (c |
|a) |
|:prec|
|ondit|
|ion |
|(and |
|(ct |
|a) |
|(ct |
|c) |
|(on c|
|b)) |
|:effe|
|ct |
|(and |
|(on c|
|a) |
|(ct |
|b) |
|(not |
|(on c|
|b)) |
|(not |
|(ct |
|a))))|
| |
|(:act|
|ion |
|put |
|:para|
|meter|
|s (b |
|a) |
|:prec|
|ondit|
|ion |
|(and |
|(ct |
|b) |
|(ct |
|a) |
|(on b|
|d)) |
|:effe|
|ct |
|(and |
|(on b|
|a) |
|(ct |
|d) |
|(not |
|(on b|
|d)) |
|(not |
|(ct |
|a))))|
| |
| |
|6 |
| |
|s3 |
| |
|4 |
| |
|op03 |
| |
|3 |
| |
|op32 |
| |
|5 |
| |
|2 |
| |
|op02 |
| |
|s0 |
| |
|s2 |
| |
|7 |
| |
|8 |
| |
|{ |
| |
|op01 |
| |
|1 |
| |
|s1 |
| |
|addit|
|ional|
|cells|
|of |
|the |
|(n+m,|
|n+m)-|
|matri|
|x |
|of an|
|exten|
|sion |
|(( |
|(’, |
|O’ ) |
|of ((|
|(, O |
|) |
| |
|(n,n)|
|-matr|
|ix of|
|the |
|domai|
|n |
|insta|
|nce |
|(( (,|
|O ) |
| |
|(:act|
|ion |
|spend|
|-mone|
|y |
|:para|
|meter|
|s |
|(lucy|
|famil|
|y) |
|:prec|
|ondit|
|ion |
|(and |
|(has-|
|money|
|lucy)|
|(not |
|(have|
|famil|
|y))) |
|:effe|
|ct |
|(and |
|(have|
|famil|
|y) |
|(when|
|(or |
|(have|
|house|
|) |
|(have|
|cars)|
|) |
|(not |
|(has-|
|money|
|lucy)|
|)))) |
| |
|{ |
| |
|{ |
| |
|{ |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
(:action board
:parameters (?x ?y)
:precondition (and (place ?y) (car ?x) (at ?x ?y) (atferry ?y) (empty-ferry))
:effect (and (on-ferry ?x) (not (at ?x ?y)) (not (empty-ferry))))
(:action sail
:parameters (?x ?y - place)
:precondition (and (atferry ?x) (not (= ?x ?y)))
:effect (and (atferry ?y) (not (atferry ?x))))
OPS = {
(:action put
:parameters (?x ?y)
:vars (?z)
:precondition (and (ct ?x) (ct ?y) (not (= ?x ?y)))
:effect (and (on ?x ?y) (not (ct ?y))
(when (and (on ?x ?z) (not (= ?x ?z)) (not (= ?y ?z)))
(and (not (on ?x ?z)) (ct ?z)))))
(:action puttable
:parameters (?x)
:vars (?y)
:precondition (and (on ?x ?y) (ct ?x) (not (= ?x ?y)))
:effect (and (ct ?y) (not (on ?x ?y))))
}
A = { (ct ?x – object), (on ?x ?y – object) }
(define (domain ferry)
(:requirements :strips :equality :typing)
(:types car place)
(:predicates (atferry ?l - place) (at ?x - car ?y - place) (on-ferry ?x - car) (empty))
(:action board :parameters (?x - car ?y - place)
:precondition (and (at ?x ?y) (atferry ?y) (empty))
:effect (and (on-ferry ?x) (not (at ?x ?y)) (not (empty))))
(:action sail :parameters (?x ?y - place)
:precondition (and (atferry ?x) (not (= ?x ?y)))
:effect (and (atferry ?y) (not (atferry ?x))))
(:action debark :parameters (?x - car ?y - place)
:precondition (and (on-ferry ?x) (atferry ?y))
:effect (and (at ?x ?y) (empty) (not (on-ferry ?x)))))
A = { (atferry ?l - place), (at ?x - car ?y - place), (on-ferry ?x - car), (empty) }
O = { (a – place), (b – place), (c1 – car) }
FA,O = {(atferry a),(atferry b),(at c1 a),(at c1 b),(on-ferry c1),(empty)}
\[pic]A,O = (
OP = { (board(c1ŜA,O = (
OP = { (board(c1, a) :precondition (and (at c1 a) (atferry a) (empty))
:effect (and (on-ferry c1) (not (at c1 a)) (not (empty))))
(board(c1, b) :precondition (and (at c1 b) (atferry b) (empty))
:effect (and (on-ferry c1) (not (at c1 b)) (not (empty))))
(sail(a, b) :precondition (and (atferry a) (not (= a b)))
:effect (and (atferry b) (not (at-ferry a))))
(sail(b, a) :precondition (and (atferry b) (not (= b a)))
:effect (and (atferry a) (not (at-ferry b))))
(debark(c1, a) :precondition (and (on-ferry c1) (atferry a))
:effect (and (at c1 a) (empty) (not (on-ferry c1))))
(debark(c1, b) :precondition (and (on-ferry c1) (atferry b))
:effect (and (at c1 b) (empty) (not (on-ferry c1))))
}
(:action marry
:parameters (?x ?y - person)
:precondition (and (adult ?x) (adult ?y) (not (= ?x ?y))
(not (married ?x)) (not (married ?y)))
:effect (and (married ?x) (married ?y)
(when (female ?x) (and (wife ?x ?y) (husband ?y ?x)))
(when (male ?x) (and (husband ?x ?y) (wife ?y ?x)))))
OP = {
(marry(ulysses, penelope)
:precondition (and (adult ulysses) (adult penelope) (not (married ulysses)) (not (married penelope)))
:effect (and (married ulysses) (married penelope)))
(marry(ulysses, penelope)
:precondition (and (adult ulysses) (adult penelope) (not (married ulysses)) (not (married penelope))
(female ulysses))
:effect (and (married ulysses) (married penelope)
(wife ulysses penelope) (husband penelope ulysses)))
(marry(ulysses, penelope)
:precondition (and (adult ulysses) (adult penelope) (not (married ulysses)) (not (married penelope))
(male ulysses))
:effect (and (married ulysses) (married penelope)
(husband ulysses penelope) (wife penelope ulysses)))
(marry(ulysses, penelope)
:precondition (and (adult ulysses) (adult penelope) (not (married ulysses)) (not (married penelope))
(male ulysses) (female ulysses))
:effect (and (married ulysses) (married penelope)
(husband ulysses penelope) (wife penelope ulysses)
(wife ulysses penelope) (husband penelope ulysses)))
}
(:action marry
:parameters (?x ?y - person)
:precondition (and (adult ?x) (adult ?y) (not (= ?x ?y))
(not (married ?x)) (not (married ?y)))
:effect (and (married ?x) (married ?y)
(when (and (not (male ?x)) (female ?x))
(and (wife ?x ?y) (husband ?y ?x)))
(when (male ?x) (and (husband ?x ?y) (wife ?y ?x)))))
For operator ( = ((0, (0), ..., ((n, (n) build the set of operations OP for one single variable substitution ( = { o1/x1, ..., om/xm } as follows.
1. Initialize the set of primary preconditions PREC0 = { PREC0,j | PREC0,j = (j( (0 ) }
2. Initialize the set of primary effects EFF0 = { EFF0,j | EFF0,j = (j ( (0 ) }.
3. For each instantiated primary precondition PREC0,j ( PREC0 do
a. Initialize PREC = PREC0,j and EFF = EFF0,j.
b. For each secondary precondition (i do
i. Initialize PRECi = (( (i ) and EFFi = (( (i ).
ii. For each PRECi,k continue at 3.b with PREC = PREC ( PRECi,k and
EFF = EFF ( EFFi,k, if for all p ( PRECi,k it applies that (p ( PREC
iii. Initalize NPRECi = (j( ((i ).
iv. For each NPREC i,k continue at 3.b with PREC = PREC ( NPRECi,k and EFF, if for all p ( NPRECi,k it applies that (p ( PREC
c. Add (PREC,EFF) to OP.
d.
put = ( (ct ?x) ( (ct ?y) ( ((= ?x, ?y), (on ?x, ?y) ( ((ct ?y) ), ( (?z.(on ?x ?z), ((on ?x ?z) ( (ct ?z) )
With ( = { a/?x, b/?y, c/?z1, d/?z2 } we build the set of operations as follows. ?z1 and ?z2 arise from ?z when the existential quantifier is instantiated.
1. PREC0 = { { (ct a), (ct b) } }. There is just one instance of the primary precondition, because it does not contain disjunctions.
2. EFF0 = { (on a, b), ((ct b) }
3. With the only element PREC0,0 = { (ct a), (ct b) } ( PREC0 we do
a. PREC = PREC0,1, EFF = EFF0.
b. With the only secondary precondition (1 = (?z.(on ?x ?z) we do:
i. PREC1 = { { (on a, c) }, { (on a, d) } },
EFF1 = { { ((on a, c), (ct c) }, {((on a d), (ct d) } }
ii. With PREC1,0 = { (on a, c) } and EFF1,0 = { ((on a, c), (ct c) } we get
PREC = PREC ( PREC1,0 = { (ct a), (ct b), (on a, c) } and EFF = EFF ( EFF1,0 = { (on a, b), ((ct b), ((on a, c), (ct c) }. We cannot further recur, so we add (PREC, EFF) to OP.
With PREC1,1 = { (on a, d) } and EFF1,1 = { ((on a, d), (ct d) } we get
PREC = PREC ( PREC1,1 = { (ct a), (ct b), (on a, d) } and EFF = EFF ( EFF1,1 = { (on a, b), ((ct b), ((on a, d), (ct d) }. We cannot further recur, so we add (PREC, EFF) to OP.
iii. NPREC1 = (( ((?z.(on ?x ?z) ) = (( (?z.((on ?x ?z) ) = (( ((on a, c) ( ((on a, d) ) = { { ((on a, c), ((on a, d) } }
iv. With the only element NPREC1,0 = { ((on a, c), ((on a, d) } we get
PREC = PREC ( NPREC1,0 = {(ct a), (ct b), ((on a, c), ((on a, d)} and EFF = { (on a, b), ((ct b) }. We cannot further recur, so we add (PREC, EFF) to OP.
OP = { ( { (ct a), (ct b), (on a, c) }, { (on a, b), ((ct b), ((on a, c), (ct c) } ),
( { (ct a), (ct b), (on a, d) }, { (on a, b), ((ct b), ((on a, d), (ct d) } ),
{ (ct a), (ct b), ((on a, c), ((on a, d) }, { (on a, b), ((ct b) } ) }
= { (put(a, b) :precondition (and (ct a) (ct b) (on a c))
:effect (and (on a b) (not (ct b)) (not (on a c)) (ct c)))
(put(a, b) :precondition (and (ct a) (ct b) (on a d))
:effect (and (on a b) (not (ct b)) (not (on a d)) (ct d)))
(put(a, b) :precondition (and (ct a) (ct b) (not (on a c)) (not (on a d)))
:effect (and (on a b) (not (ct b)))) }
s = { p1, p2, p3, p4 }
| |p1 |p2 |p3 |p4 |
|p1 |0 |1 |1 |1 |
|p2 |0 |0 |1 |1 |
|p3 |0 |0 |0 |1 |
|p4 |0 |0 |0 |0 |
p1
p2
p3
p4
1 (ct a) 4 (on a b) 7 (on b c)
2 (ct b) 5 (on a c) 8 (on c a)
3 (ct c) 6 (on b a) 9 (on c b)
5
6
4
7
3
8
2
9
1
For a domain instance (( (, O ) = (OP, F, Ŝ) and a set of literals L = { l1, ..., l2n } being built from the set of facts F = { f1, ..., fn } we build the adjacency matrix AL by applying the following algorithm.
1. Create AL as an (2n,2n)-matrix. Initialize all cells with –1.
2. Repeat
a. Repeat
For all pairs (li, lj) of L do
i. If aij ( -1 then continue with 2.a.
ii. If li = lj then aij = 0. Continue with 2.a.
iii. If li = (lj then aij = 0. Continue with 2.a.
iv. If there exists an already decided pair (lp, lq), where lp and li are isomorphic instances of the same literal, and lq and lj are isomorphic instances of the same literal, too, then aij = apq. Continue with 2.a.
v. Set aij = 0.
vi. With all operations op ( OP do
1. If li ( EFFop, then continue with 2.a.vi.
2. If lj ( EFFop, then aij = 1. Continue with 2.a.
3. If (lj ( EFFop, then continue with 2.a.vi.
4. If lj ( PRECop, then aij = 1. Continue with 2.a.
5. If (lj ( PRECop, then continue with 2.a.vi.
6. d = 1.
7. With all literals lk ( PRECop do
a. If ajk = 0 and akj = 0 then continue with 2.a.vi.
b. If ajk ( 1 and akj ( 1 d = -1.
8. aij = d.
until no further decisions have been made.
b. If any pair (li, lj) is undecided, ask the user to decide it. Set aij to the user’s decision.
until all pairs have been decided.
To create the complete set of states S from the adjacency matrix AL giving the compatibility information of the set of literals L = { l1, ..., l2n }, apply the following algorithm.
1. Initialize an empty set of states S = ( and an empty set of substates S’ = (.
2. Initialize an empty state s = (.
3. With s do
a. If s ( S’ then return.
b. For all literals li ( L do
i. If to all lj ( s it applies that aij = 1 then
1. s = s ( { li }
2. Continue at step 3.
3. s = s \ { li }.
c. If |s| = n then
i. S = S ( { s }.
ii. S’ = S’ ( { s }.
iii.
| |(empt|(atfe|(atfe|(at |(at |(on-f|
| |y) |rry |rry |bmw |bmw |erry |
| | |a) |b) |a) |b) |bmw) |
|(empty) |0 |1 |1 |1 |1 |0 |
|(atferry a) |1 |0 |0 |1 |1 |1 |
|(atferry b) |1 |0 |0 |1 |1 |1 |
|(at bmw a) |1 |1 |1 |0 |0 |0 |
|(at bmw b) |1 |1 |1 |0 |0 |0 |
|(on-ferry bmw) |0 |1 |1 |0 |0 |0 |
1 (empty) 4 (at bmw a)
2 (atferry a) 5 (at bmw b)
3 (atferry b) 6 (on-ferry bmw)
1
2
3
4
5
6
(at bmw a)
(empty) (atferry a) (atferry b)
(atferry a) (atferry b) (empty)
(on-ferry bmw)
(atferry a) (atferry b)
(atferry b)
(empty) (at bmw a) (at bmw b) (on-ferry bmw)
(at bmw a) (at bmw b) (empty)
(atferry a)
(empty) (at bmw a) (at bmw b) (on-ferry bmw)
(at bmw a) (at bmw b) (empty)
(empty)
(atferry a) (atferry b) (at bmw a) (at bmw b)
(at bmw a) (at bmw b) (at bmw a) (atferry a) (atferry b) (atferry a)
(at bmw b)
(empty) (atferry a) (atferry b)
(atferry a) (atferry b) (empty)
To create the complete set of states S from the adjacency matrix AL giving the compatibility information of the set of literals L = { l1, ..., l2n }, apply the following algorithm.
1. For i = 1..2n do aii = 1.
2. With the clique algorithm given in [BK71] create all maximum cliques.
3. With each clique c = { l1, ..., lm } do
a. Initialize c’ = c.
b. For i = m downto 1 do
i. Find an lj ( c’ with ajk = 1 for all lk ( c’.
ii. If lj exists then c’ = c’ \ { lj }. Continue at step 3.b.
iii. Else fail. Continue with a new clique at step 3.
c. S = S ( { c }.
|add |place |car |
|to | | |
|(ferry) | | |
| | | |
|(ferry) | | |
|+ | | |
|place | | |
| | | |
| | | |
| | | |
|(ferry) | | |
|+ | | |
|car | | |
| | | |
| | | |
| | | |
|(ferry) | | |
|+ | | |
|place | | |
|+ | | |
|car | | |
| | | |
| | | |
| | | |
| | | |
| | | |
|place | | |
|+ | | |
|place | | |
|+ | | |
|car | | |
| | | |
| | | |
| | | |
| | | |
| | | |
{
[ (ferry) ]: [ ((empty), (empty)) ]
[ place ]:
[ ((atferry a), (atferry a)) ]
[ car ]:
[ ((on-ferry c1), (on-ferry c1)) ]
[ (ferry) + place ]:
[ ((empty), (atferry a)), ((atferry a), (empty)) ]
[ (ferry) + car ]:
[ ((empty), (on-ferry c1)), ((on-ferry c1), (empty)) ]
[ place + place ]:
[ ((atferry a), (atferry b)) ]
[ place + car ]:
[ ((at c1 a), (at c1 a)), ((atferry a), (at c1 a)),
((at c1 a), (atferry a)), ((atferry a), (on-ferry c1)),
((on-ferry c1), (atferry a)), ((at c1 a), (on-ferry c1)) ]
[ car + car ]:
[ ((on-ferry c1), (on-ferry c2)) ]
[ (ferry) + place + car ]:
[ ((empty), (at c1 a)), ((at c1 a), (empty)),
((empty), (at c1 b)), ((at c1 b), (empty)) ]
[ place + place + car ]:
[ ((atferry a), (at c1 b)), ((at c1 b), (atferry a)), ((at c1 a), (at c1 b)), ((at c1 b), (at c1 a)) ]
[ place + car + car ]:
[ ((on-ferry c1), (at c2 a)), ((at c2 a), (on-ferry c1)), ((on-ferry c2), (at c1 a)),
((at c1 a), (on-ferry c2)), ((at c1 a), (at c2 a)), ((at c2 a), (at c1 a)) ]
[ place + place + car + car ]:
[ ((at c1 a), (at c2 b)), ((at c2 a), (at c1, b)) ]
To extend an existing (n,n)-matrix AF to an (n+m,n+m)-matrix AF’ by adding a new object o use the following algorithm. Let ( = (1, ..., (k be the set of prototypes provided by the facts of AF.
1. Create the additional set of facts F+ = { f1+, ..., fm+ }.
2. Create AF’ by adding to AF
a. m uninitialized columns [a1(n+1), ..., an(n+1)], ..., [a1(n+m), ..., an(n+m)]
b. m uninitialized rows [a(n+1)1, ..., a(n+1)(m+n)], ..., [a(n+m)1, ..., a(n+m)(n+m) ]
3. With all pairs (fi+, fj+) do
a. If there exists a prototype (k = ((, P,C,() for (fi+, fj+) with (( (fi+, fj+) ) ( -1, then a(n+i)(n+j) = (( (fi+, fj+) ).
b. Else
i. Decide a(n+i)(n+j) by the algorithm given in figure 4.13.
ii. ( = ( ( { ( [(x, ..., (x+y], [ (fi+, fj+) ], [a(n+i)(n+j) ], ( ) } where (x, ..., (x+y is the list of types occurring in (fi+, fj+).
left column: office, right column: home, b and p in one cell: in(p b)
| |p | |
| | |b |
| |p | |
| |b | |
| | | |
| |bp | |
| | |p |
| |b | |
| | |p |
| | |b |
| | | |
| | |bp |
Adding { (at d office) }
Adding { (at d home) }
Adding { (in d b) }
| |d |p |
| |b | |
| |d |p |
| | |b |
| |d | |
| | |bp |
| |d | |
| |bp | |
| |pd | |
| |b | |
| |pd | |
| | |b |
| | |pd |
| |b | |
| | |pd |
| | |b |
| | |d |
| | |bp |
| | |d |
| |bp | |
| |p |d |
| |b | |
| |p |d |
| | |b |
| | |p |
| |bd | |
| | |p |
| | |bd |
| | | |
| | |bdp |
| | | |
| |bdp | |
| |p | |
| |bd | |
| |p | |
| | |bd |
1 2 3 4 5 6
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
4 3 15 16 10 9
5 6 18 17 11 12
1 2 14 13 7 8
| | |d |
| |bp | |
| | |d |
| | |bp |
| | | |
| | |bpd |
| | | |
| |bpd | |
| |d | |
| |bp | |
| |d | |
| | |bp |
| | |dp |
| |b | |
| | |dp |
| | |b |
| | |p |
| | |bd |
| | |p |
| |bd | |
| |d |p |
| |b | |
| |d |p |
| | |b |
| |p |d |
| |b | |
| |p |d |
| | |b |
| |p | |
| | |bd |
| |p | |
| |bd | |
| |dp | |
| |b | |
| |dp | |
| | |b |
15
16
17
10
1
2
3
14
13
7
8
11 3
| | | | |
| | | |b |
| | |c |a |
| |j |1 |2 |3 |4 |5 |6 |7 |
|i |to |(at |(at |(at |(at |(mobi|(mobi|(driv|
| | |jack |jack |bulld|bulld|le |le |ing |
| | |c1) |c2) |ozer |ozer |jack)|bulld|jack |
| | | | |c1) |c2) | |ozer)|bulld|
| | | | | | | | |ozer)|
| |add | | | | | | | |
|1 |(at jack c1) |0 |? |? |? |? |? |? |
|2 |(at jack c2) |? |0 |? |? |? |? |? |
|3 |(at bulldozer c1) |? |? |0 |? |? |? |? |
|4 |(at bulldozer c2) |? |? |? |0 |? |? |? |
|5 |(mobile jack) |? |? |? |? |0 |? |? |
|6 |(mobile bulldozer) |? |? |? |? |? |0 |? |
|7 |(driving jack bulldozer) |? |? |? |? |? |? |0 |
| | | |c |
| | | |b |
| | | |a |
9
11
12
4
5
6
18
9 10
| | | | |
| | |c | |
| | |a |b |
| | | |b |
| | | |c |
| | | |a |
| |j |1 |2 |3 |4 |5 |6 |7 |
|i |to |(at |(at |(at |(at |(mobi|(mobi|(driv|
| | |jack |jack |bulld|bulld|le |le |ing |
| | |c1) |c2) |ozer |ozer |jack)|bulld|jack |
| | | | |c1) |c2) | |ozer)|bulld|
| | | | | | | | |ozer)|
| |add | | | | | | | |
|1 |(at jack c1) |0 |? |1 |? |1 |? |? |
|2 |(at jack c2) |? |0 |? |1 |1 |? |? |
|3 |(at bulldozer c1) |? |? |0 |0 |? |1 |? |
|4 |(at bulldozer c2) |? |? |0 |0 |? |1 |? |
|5 |(mobile jack) |1 |1 |1 |1 |0 |0 |0 |
|6 |(mobile bulldozer) |? |? |1 |1 |0 |0 |1 |
|7 |(driving jack bulldozer) |? |? |1 |1 |0 |1 |0 |
8 2 7
| | | | |
| | | | |
| |a |c |b |
| | | | |
| | | |b |
| | |a |c |
| | | | |
| | | |c |
| | |a |b |
Exchanging c and a
Exchanging c and b
6 7
| | | |a |
| | | |b |
| | | |c |
| |j |1 |2 |3 |4 |5 |6 |7 |
|i |to |(at |(at |(at |(at |(mobi|(mobi|(driv|
| | |jack |jack |bulld|bulld|le |le |ing |
| | |c1) |c2) |ozer |ozer |jack)|bulld|jack |
| | | | |c1) |c2) | |ozer)|bulld|
| | | | | | | | |ozer)|
| |add | | | | | | | |
|1 |(at jack c1) |0 |? |1 |1 |1 |0 |0 |
|2 |(at jack c2) |? |0 |1 |1 |1 |0 |0 |
|3 |(at bulldozer c1) |? |? |0 |0 |0 |1 |1 |
|4 |(at bulldozer c2) |? |? |0 |0 |0 |1 |1 |
|5 |(mobile jack) |1 |1 |1 |1 |0 |0 |0 |
|6 |(mobile bulldozer) |? |? |1 |1 |0 |0 |1 |
|7 |(driving jack bulldozer) |? |? |1 |1 |0 |1 |0 |
| | | | |
| | | |b |
| | |a |c |
| | | | |
| | |a | |
| | |c |b |
| |j |1 |2 |3 |4 |5 |6 |7 |
|i |to |(at |(at |(at |(at |(mobi|(mobi|(driv|
| | |jack |jack |bulld|bulld|le |le |ing |
| | |c1) |c2) |ozer |ozer |jack)|bulld|jack |
| | | | |c1) |c2) | |ozer)|bulld|
| | | | | | | | |ozer)|
| |add | | | | | | | |
|1 |(at jack c1) |0 |0 |1 |1 |1 |0 |0 |
|2 |(at jack c2) |0 |0 |1 |1 |1 |0 |0 |
|3 |(at bulldozer c1) |? |? |0 |0 |0 |1 |1 |
|4 |(at bulldozer c2) |? |? |0 |0 |0 |1 |1 |
|5 |(mobile jack) |1 |1 |1 |1 |0 |0 |0 |
|6 |(mobile bulldozer) |0 |0 |1 |1 |0 |0 |1 |
|7 |(driving jack bulldozer) |0 |0 |1 |1 |0 |1 |0 |
| | | |b |
| | | |a |
| | | |c |
4 5
| | | | |
| | | |a |
| | |c |b |
| | | | |
| | | | |
| |c |a |b |
| | | | |
| | | |b |
| | |c |a |
1 2 3
Adding { (ct c) }
Adding { (on a c) }
Adding { (on b c) }
13 8
| | | | |
| | | |c |
| | |a |b |
To extend an existing state space (1 = (S1, E1) of a certain domain instance to the state space (2 = (S2, E2) of an instance with an additional object, apply the following algorithm. Let F = { f1, ..., fn } be the set of additional facts and OP the additional set of operations.
1. Initialize an empty set of partial state spaces, G = (.
2. If all fi ( F are isomorphic to already known facts do
a. (1’ = (1.
b. With all states sx of (1’ do repeat
i. Extend sx by F’ ( F to a new state of (2.
ii. With all other states sy of (1’ do
1. If sy ( F’ is a legal state extend sy by F’ and keep its edges.
2. Else delete sy and all its edges from (1’.
3. G = G ( (1’.
until all extensions of sx have been processed.
c. With G = { (S1’,E1’), ..., (Sk’,Ek’) }do
i. S’ = (i=1..kSi’
ii. E’ = (i=1..kEi’
iii. (’ = (S’, OP’)
d. If all operations opj ( OP are isomorphic to already known operations, then (2 = (’
e. Else
i. E = { (sx’,sy’,opxy) | sx’,sy’ ( S’, opxy ( OP and opxy is not isomorphic to any operation of the edges in E1.
ii. (2 = (S’,OP’ ( E)
3. Else if building states from the non-isomorphic facts does not lead to states without having states from S1 as subset, process step 2.a. to 2.e.
4. Else
a. Apply step 2.a to 2.e. to create a partial state space (2’ = (S2’,E2’).
b. Create the set of states S’’ by building cliques beginning from the additional facts.
c. Delete from S’’ all states that are isomorphic to states from S2’.
d. E’’ = { (sx’’,sy’’,opxy) | sx’’,sy’’ ( (S’’ ( S2’), opxy ( OP.
e. (2 = (S’’ ( S2’, E2’ ( E’’)
| | | |a |
| | | |c |
| | | |b |
1 12
| | | | |
| | |a | |
| | |b |c |
| | | |c |
| | | |a |
| | | |b |
4 2 9
| | | | |
| | | | |
| |b |a |c |
| | | | |
| | | |c |
| | |b |a |
| | | | |
| | | |a |
| | |b |c |
12
| |j |1 |2 |3 |4 |5 |6 |7 |
|i |to |(at |(at |(at |(at |(mobi|(mobi|(driv|
| | |jack |jack |bulld|bulld|le |le |ing |
| | |c1) |c2) |ozer |ozer |jack)|bulld|jack |
| | | | |c1) |c2) | |ozer)|bulld|
| | | | | | | | |ozer)|
| |add | | | | | | | |
|1 |(at jack c1) |0 |0 |1 |1 |1 |0 |0 |
|2 |(at jack c2) |0 |0 |1 |1 |1 |0 |0 |
|3 |(at bulldozer c1) |0 |0 |0 |0 |0 |1 |1 |
|4 |(at bulldozer c2) |0 |0 |0 |0 |0 |1 |1 |
|5 |(mobile jack) |1 |1 |1 |1 |0 |0 |0 |
|6 |(mobile bulldozer) |0 |0 |1 |1 |0 |0 |1 |
|7 |(driving jack bulldozer) |0 |0 |1 |1 |0 |1 |0 |
5
4
1
7
6
11
3
10
9
8
2
13
1
2
3
4
5
6
7
1 (at jack c1) 5 (mobile jack)
2 (at jack c2) 6 (mobile bulldozer)
3 (at bulldozer c1) 7 (driving jack bulldozer)
4 (at bulldozer c2)
| |j | | | |j |
left column: c1, right column: c2
| |b | | |b | |
| |j | | | |j |
| | |b | | |b |
| |j | | | |j |
s0
s2
s1
s3
s1 s3 s5 s4 s0 s2
| | | |
| |bj | |
| | | |
| | |bj |
| | |b |
| | |j |
| | |b |
| |j | |
| |b | |
| |j | |
| |b | |
| | |j |
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
Related searches
- qs uni ranking 2020
- globo de noticias de hoje
- ultimas noticias de estados unidos de america
- noticias de portugal de hoje
- mapa de estados de mexico
- noticias de esportes de hoje
- jornal de angola de hoje
- jornal canal de mocambique de hoje
- agendamento de carteira de trabalho
- uni toll pass
- uni high school irvine
- uni epass