Action description language
Encyclopedia
In artificial intelligence
, Action description language (ADL) is an automated planning and scheduling
system in particular for robots. It is considered an advancement of STRIPS
. Pednault (a specialist in the field of Data abstraction and modelling who has been an IBM Research Staff Member in the Data Abstraction Research Group since 1996) proposed this language in 1987. It is an example of an action language
.
The sense of a planning language is to represent certain conditions in the environment and, based on these, automatically generate a chain of actions which lead to a desired goal. A goal is a certain partially specified condition. Before an action can be executed its preconditions must be fulfilled; after the execution the action yields effects, by which the environment changes. The environment is described by means of certain predicates, which are either fulfilled or not.
Contrary to STRIPS, the principle of the open world
applies with ADL: everything not occurring in the conditions is
unknown (Instead of being assumed false). In addition, whereas in STRIPS only positive literals
and conjunctions
are permitted, ADL allows negative literals and disjunctions
as well.
The Precond group is a list of formulae that define the preconditions for the execution of an action. If the set is empty the value "TRUE" is inserted into the group and the preconditions are always evaluated as holding conditions.
The Add and Delete conditions are specified by the Add and Delete groups, respectively. Each group consists of a set of clauses of the forms shown in the left-hand column of the figure 1:
The Update groups are used to specify the update conditions to change the values of function symbols. An Update group consists of a set of clauses of the forms shown in the left column of the figure 2:
The second constraint is that actions in ADL must be deterministic. If (s, t1) and (s, t2) are current-state/next-state pairs of action ∃, then it must be the case that t1 = t2.
The third constraint incorporated into ADL is that the functions introduced above must be representable as first-order formulas. For every n-ary relation symbol R, there must exist a formula ΦaR x1,... ,xn) with free variables x2,...,xn such that faR(s) is given by:
t(R) = faR(s) = (d1,... , dn) ∈ Dom(s)n | s[d1/x1,...,dn/xn ⊧ ΦaR(x1,xn)]
Consequently, F(n1,...,xn) = y will be true after performing action |= if and only if ΦaR (x1,... ,xn,y) was true beforehand. Note that this representability requirement relies on the first constraint ( Domain of f should be equal to domain of s).
The fourth and final constraint incorporated into ADL is that set of states in which an action is executable must also be representable as a formula. For every action α that can be represented in ADL, there must exist a formula Πa with the property that s |= Πa if and only if there is some state t for which (s, t ) ∈ α (i.e. action α is executable in state s)
ADL planning is still a PSPACE-complete problem. Most of the algorithms polynomial space even if the preconditions and effects are complex formulae.
Most of the top-performing approaches to classical planning internally utilize a STRIPS like representation. In fact most of the planners (FF, LPG, Fast-Downward, SGPLAN5 and LAMA) first translate the ADL instance into one that is essentially a STRIPS one (without conditional or quantified effects or goals).
The expressiveness of the STRIPS language is constrained by the types of transformations on sets of formulas that can be described in the language. Transformations on sets of formulas using STRIPS operators are accomplished by removing some formulas from the set to be transformed and adding new additional formulas. For a given STRIPS operator the formulas to be added and deleted are fixed for all sets of formulas to be transformed. Consequently, STRIPS operators cannot adequately model actions whose effects depend on the situations in which they are performed. Consider a rocket which is going to be fired for a certain amount of time. The trajectory may vary not only because of the burn duration but also because of the velocity, mass and orientation of the rocket. It cannot be modelled by means of a STRIPS operator because the formulas that would have to be added and deleted would depend on the set of formulas to be transformed.
Although an efficient reasoning is possible when the STRIPS language is being used it is generally recognized that the expressiveness of STRIPS is not suitable for modeling actions in many real world applications. This inadequacy motivated the development of the ADL language. ADL expressiveness and complexity lies between the STRIPS language and the situation calculus. Its expressive power is sufficient to allow the rocket example described above to be represented yet, at the same time, it is restrictive enough to allow efficient reasoning algorithms to be developed.
As an example in a more complex version of the blocks world: It could be that block A is twice as big as blocks B and C, so the action xMoveOnto(B,A) might only have the effect of negating Clear(A) if On(A,C) is already true, or creating the conditional effect depending on the size of the blocks. This kind of conditional effects would be hard to express in STRIPS notation without the conditional effects.
The necessary actions would be loading, unloading and flying; over the
descriptors one could express In(c, p) and At(x, a) whether a freight C is in an airplane p and whether an object x is at an airport A.
The actions could be defined then as follows:
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, Action description language (ADL) is an automated planning and scheduling
Automated planning and scheduling
Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...
system in particular for robots. It is considered an advancement of STRIPS
STRIPS
In artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...
. Pednault (a specialist in the field of Data abstraction and modelling who has been an IBM Research Staff Member in the Data Abstraction Research Group since 1996) proposed this language in 1987. It is an example of an action language
Action language
In computer science, an action language is a language for specifying state transition systems, and is commonly used to create formal models of the effects of actions on the world...
.
Origins
Pednault observed that the expressive power of STRIPS was susceptible to being improved by allowing the effects of an operator to be conditional. This is the main idea of ADL-A, which is basically the propositional fragment of the ADL proposed by Pednault, with ADL-B an extension of -A. In the -B extension actions can be described with indirect effects by the introduction of a new kind of propositions: ”static laws". A third variation of ADL is ADL-C which is similar to -B, in the sense that its propositions can be classified into static and dynamic laws, but with some more particularities.The sense of a planning language is to represent certain conditions in the environment and, based on these, automatically generate a chain of actions which lead to a desired goal. A goal is a certain partially specified condition. Before an action can be executed its preconditions must be fulfilled; after the execution the action yields effects, by which the environment changes. The environment is described by means of certain predicates, which are either fulfilled or not.
Contrary to STRIPS, the principle of the open world
Open World Assumption
In formal logic, the open world assumption is the assumption that the truth-value of a statement is independent of whether or not it is known by any single observer or agent to be true. It is the opposite of the closed world assumption, which holds that any statement that is not known to be true is...
applies with ADL: everything not occurring in the conditions is
unknown (Instead of being assumed false). In addition, whereas in STRIPS only positive literals
Literal (mathematical logic)
In mathematical logic, a literal is an atomic formula or its negation.The definition mostly appears in proof theory , e.g...
and conjunctions
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
are permitted, ADL allows negative literals and disjunctions
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
as well.
Syntax of ADL
An ADL schema consists of an action name, an optional parameter list and four optional groups of clauses labeled Precond, Add, Delete and Update.The Precond group is a list of formulae that define the preconditions for the execution of an action. If the set is empty the value "TRUE" is inserted into the group and the preconditions are always evaluated as holding conditions.
The Add and Delete conditions are specified by the Add and Delete groups, respectively. Each group consists of a set of clauses of the forms shown in the left-hand column of the figure 1:
- The R represents a relation symbol
- τ1,...,τn represents terms
- ψ represents a formula
- The sequence z1,...,zk are variable symbols that appear in the terms τ1,...,τn, but not in the parameter list of the action schema
- x1,...,xn are variable symbols that are different from the variables z1,...,zn and do not appear in τ1,...,τn, ψ , or the parameter list of the action schema
The Update groups are used to specify the update conditions to change the values of function symbols. An Update group consists of a set of clauses of the forms shown in the left column of the figure 2:
Semantics of ADL
The formal semantic of ADL is defined by 4 constraints. The first constraint is that actions may not change the set of objects that exist in the world; this means that for every action α and every current-state/next-state pair (s, t) ∈ a, it must be the case that the domain of t should be equal to the domain of s.The second constraint is that actions in ADL must be deterministic. If (s, t1) and (s, t2) are current-state/next-state pairs of action ∃, then it must be the case that t1 = t2.
The third constraint incorporated into ADL is that the functions introduced above must be representable as first-order formulas. For every n-ary relation symbol R, there must exist a formula ΦaR x1,... ,xn) with free variables x2,...,xn such that faR(s) is given by:
t(R) = faR(s) = (d1,... , dn) ∈ Dom(s)n | s[d1/x1,...,dn/xn ⊧ ΦaR(x1,xn)]
Consequently, F(n1,...,xn) = y will be true after performing action |= if and only if ΦaR (x1,... ,xn,y) was true beforehand. Note that this representability requirement relies on the first constraint ( Domain of f should be equal to domain of s).
The fourth and final constraint incorporated into ADL is that set of states in which an action is executable must also be representable as a formula. For every action α that can be represented in ADL, there must exist a formula Πa with the property that s |= Πa if and only if there is some state t for which (s, t ) ∈ α (i.e. action α is executable in state s)
Complexity of planning
In terms of computational efficiency, ADL can be located between STRIPS and the Situation Calculus. Any ADL problem can be translated into a STRIPS instance – however, existing compilation techniques are worst-case exponential. This worst case cannot be improved if we are willing to preserve the length of plans polynomially, and thus ADL is strictly more brief than STRIPS.ADL planning is still a PSPACE-complete problem. Most of the algorithms polynomial space even if the preconditions and effects are complex formulae.
Most of the top-performing approaches to classical planning internally utilize a STRIPS like representation. In fact most of the planners (FF, LPG, Fast-Downward, SGPLAN5 and LAMA) first translate the ADL instance into one that is essentially a STRIPS one (without conditional or quantified effects or goals).
Comparison between STRIPS and ADL
- The STRIPS language only allows positive literals in the states, while ADL can support both positive and negative literals. For example, a valid sentence in STRIPS could be Rich ^ Beautiful. The same sentence could be expressed in ADL as ¬Poor ∧ ¬Ugly
- In STRIPS the unmentioned literals are false. This is called the Closed World Assumption. In ADL the unmentioned literals are unknown. This is known as the Open World Assumption.
- In STRIPS we only can find ground literals in goals. For instance, Rich ∧ Beautiful. In ADL we can find quantified variables in goals. For example, ∃x At (P1, x) ∧ At(P2, x) is the goal of having P1 and P2 in the same place in the example of the blocks
- In STRIPS the goals are conjunctions (Rich ^ Beautiful ). In ADL the goals allow conjunction and disjunction (Rich ∧ Beautiful ¬Smart).
- In STRIPS the effects are conjunctions, but in ADL conditional effects are allowed: when P:E means E is an effect only if P is satisfied
- The STRIPS language does not support equality. In ADL , the equality predicate (x = y ) is built in.
- STRIPS does not have support for types, while in ADL it is supported (for example, the variable p : Person).
The expressiveness of the STRIPS language is constrained by the types of transformations on sets of formulas that can be described in the language. Transformations on sets of formulas using STRIPS operators are accomplished by removing some formulas from the set to be transformed and adding new additional formulas. For a given STRIPS operator the formulas to be added and deleted are fixed for all sets of formulas to be transformed. Consequently, STRIPS operators cannot adequately model actions whose effects depend on the situations in which they are performed. Consider a rocket which is going to be fired for a certain amount of time. The trajectory may vary not only because of the burn duration but also because of the velocity, mass and orientation of the rocket. It cannot be modelled by means of a STRIPS operator because the formulas that would have to be added and deleted would depend on the set of formulas to be transformed.
Although an efficient reasoning is possible when the STRIPS language is being used it is generally recognized that the expressiveness of STRIPS is not suitable for modeling actions in many real world applications. This inadequacy motivated the development of the ADL language. ADL expressiveness and complexity lies between the STRIPS language and the situation calculus. Its expressive power is sufficient to allow the rocket example described above to be represented yet, at the same time, it is restrictive enough to allow efficient reasoning algorithms to be developed.
As an example in a more complex version of the blocks world: It could be that block A is twice as big as blocks B and C, so the action xMoveOnto(B,A) might only have the effect of negating Clear(A) if On(A,C) is already true, or creating the conditional effect depending on the size of the blocks. This kind of conditional effects would be hard to express in STRIPS notation without the conditional effects.
Example
Consider the problem of air freight transport, where certain goods must be transported from an airport to another airport by plane and where airplanes need to be loaded and unloaded.The necessary actions would be loading, unloading and flying; over the
descriptors one could express In(c, p) and At(x, a) whether a freight C is in an airplane p and whether an object x is at an airport A.
The actions could be defined then as follows:
Action (
Load (c: Freight, p: Airplane, A: Airport)
Precondition: At(c, A) ^ At(p, A)
Effect: ¬At(c, A) ^ In(c, p)
)
Action (
Unload (c: Freight, p: Airplane, A: Airport)
Precondition: In(c, p) ^ At(p, A)
Effect: At(c, A) ^ ¬In(c, p)
)
Action (
Fly (p: Airplane, from: Airport, to: Airport)
Precondition: At(p, from)
Effect: ¬At(p, from) ^ At(p, to)
)
See also
- Action languageAction languageIn computer science, an action language is a language for specifying state transition systems, and is commonly used to create formal models of the effects of actions on the world...
- Automated planning
- Hierarchical task networkHierarchical task networkIn artificial intelligence, the hierarchical task network, or HTN, is an approach to automated planning in which the dependency among actions can be given in the form of networks....
- Planning Domain Definition LanguagePlanning Domain Definition LanguageThe Planning Domain Definition Language is an attempt to standardize planning domain and problem description languages. It was developed mainly to make the 1998/2000 International Planning Competitions possible....
(PDDL) - STRIPSSTRIPSIn artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...