Action description language

Last updated

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. Edwin 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 [1] ) proposed this language in 1987. It is an example of an action language.

Contents

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 roughly the propositional fragment of the ADL proposed by Pednault, [2] 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. [3]

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.

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:

  1. The R represents a relation symbol
  2. τ1, ..., τn represents terms
  3. ψ represents a formula
  4. The sequence z1, ..., zk are variable symbols that appear in the terms τ1, ..., τn, but not in the parameter list of the action schema
  5. 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:

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. [4] Any ADL problem can be translated into a STRIPS instance – however, existing compilation techniques are worst-case exponential. [5] This worst case cannot be improved if we are willing to preserve the length of plans polynomially, [6] 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. [7]

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

  1. 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
  2. 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.
  3. 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
  4. In STRIPS the goals are conjunctions, e.g., (Rich ∧ Beautiful). In ADL, goals may involve conjunctions and disjunctions (Rich ∧ (Beautiful ∨ Smart)).
  5. 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
  6. The STRIPS language does not support equality. In ADL, the equality predicate (x = y) is built in.
  7. 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. [8]

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. [9] [10] 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

Related Research Articles

In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

In artificial intelligence, with implications for cognitive science, the frame problem describes an issue with using first-order logic to express facts about a robot in the world. Representing the state of a robot with traditional first-order logic requires the use of many axioms that simply imply that things in the environment do not change arbitrarily. For example, Hayes describes a "block world" with rules about stacking blocks together. In a first-order logic system, additional axioms are required to make inferences about the environment. The frame problem is the problem of finding adequate collections of axioms for a viable description of a robot environment.

Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem-specific branching heuristic.

A Bayesian network is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). It is one of several forms of causal notation. Bayesian networks are ideal for taking an event that occurred and predicting the likelihood that any one of several possible known causes was the contributing factor. For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases.

In computer science, domain relational calculus (DRC) is a calculus that was introduced by Michel Lacroix and Alain Pirotte as a declarative database query language for the relational data model.

<span class="mw-page-title-main">Referential integrity</span> Where all data references are valid

Referential integrity is a property of data stating that all its references are valid. In the context of relational databases, it requires that if a value of one attribute (column) of a relation (table) references a value of another attribute, then the referenced value must exist.

<span class="mw-page-title-main">Method of analytic tableaux</span>

In proof theory, the semantic tableau is a decision procedure for sentential and related logics, and a proof procedure for formulae of first-order logic. An analytic tableau is a tree structure computed for a logical formula, having at each node a subformula of the original formula to be proved or refuted. Computation constructs this tree and uses it to prove or refute the whole formula. The tableau method can also determine the satisfiability of finite sets of formulas of various logics. It is the most popular proof procedure for modal logics.

<span class="mw-page-title-main">Stopping time</span> Time at which a random variable stops exhibiting a behavior of interest

In probability theory, in particular in the study of stochastic processes, a stopping time is a specific type of “random time”: a random variable whose value is interpreted as the time at which a given stochastic process exhibits a certain behavior of interest. A stopping time is often defined by a stopping rule, a mechanism for deciding whether to continue or stop a process on the basis of the present position and past events, and which will almost always lead to a decision to stop at some finite time.

<span class="mw-page-title-main">Automated planning and scheduling</span> Branch of artificial intelligence

Automated planning and scheduling, sometimes denoted as simply AI planning, 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 complex and must be discovered and optimized in multidimensional space. Planning is also related to decision theory.

The Planning Domain Definition Language (PDDL) is an attempt to standardize Artificial Intelligence (AI) planning languages. It was first developed by Drew McDermott and his colleagues in 1998 mainly to make the 1998/2000 International Planning Competition (IPC) possible, and then evolved with each competition. The standardization provided by PDDL has the benefit of making research more reusable and easily comparable, though at the cost of some expressive power, compared to domain-specific systems.

The Stanford Research Institute Problem Solver, known by its acronym STRIPS, is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International. The same name was later used to refer to the formal language of the inputs to this planner. This language is the base for most of the languages for expressing automated planning problem instances in use today; such languages are commonly known as action languages. This article only describes the language, not the planner.

The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based on that introduced by Ray Reiter in 1991. It is followed by sections about McCarthy's 1986 version and a logic programming formulation.

Answer set programming (ASP) is a form of declarative programming oriented towards difficult search problems. It is based on the stable model semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates.

A "production system" is a computer program typically used to provide some form of artificial intelligence, which consists primarily of a set of rules about behavior but it also includes the mechanism necessary to follow those rules as the system responds to states of the world. Those rules, termed productions, are a basic representation found useful in automated planning, expert systems and action selection.

In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula in conjunctive normal form, that can be made true by an assignment of truth values to the variables of the formula. It is a generalization of the Boolean satisfiability problem, which asks whether there exists a truth assignment that makes all clauses true.

Ramsey sentences are formal logical reconstructions of theoretical propositions attempting to draw a line between science and metaphysics. A Ramsey sentence aims at rendering propositions containing non-observable theoretical terms clear by substituting them with observational terms.

In computer science and recursion theory the McCarthy Formalism (1963) of computer scientist John McCarthy clarifies the notion of recursive functions by use of the IF-THEN-ELSE construction common to computer science, together with four of the operators of primitive recursive functions: zero, successor, equality of numbers and composition. The conditional operator replaces both primitive recursion and the mu-operator.

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. Action languages are commonly used in the artificial intelligence and robotics domains, where they describe how actions affect the states of systems over time, and may be used for automated planning.

LOOP is a simple register language that precisely captures the primitive recursive functions. The language is derived from the counter-machine model. Like the counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer. A few arithmetic instructions operate on the registers. The only control flow instruction is 'LOOP x DO...END'. It causes the instructions within its scope to be repeated x times.

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier in the first order formula expresses that everything in the domain satisfies the property denoted by . On the other hand, the existential quantifier in the formula expresses that there exists something in the domain which satisfies that property. A formula where a quantifier takes widest scope is called a quantified formula. A quantified formula must contain a bound variable and a subformula specifying a property of the referent of that variable.

References

  1. ↑ Edwin Pednault. "IBM Research Website: Pednault" . Retrieved 29 March 2013.l
  2. ↑ Pednault. Formulating multi-agent dynamic-world problems in the classical planning framework. In Michael Georgeff and Amy Lansky, editors, Reasoning about actions and plans pages 47-82. Morgan Kaufmann, San Mateo, CA, 1987.
  3. ↑ Michael Gelfond, Vladimir Lifschitz (1998) "Action Languages Archived September 2, 2011, at the Wayback Machine ", Linköping Electronic Articles in Computer and Information Science, vol 3, nr 16.
  4. ↑ Edwin P. D. Pednault. ADL. "Exploring the Middle Ground Between STRIPS and the Situation Calculus." In Proceedings of KR-89, 324–332.
  5. ↑ Gazen, B. C. and Knoblock, C. A., "Combining the Expressivity of UCPOP with the efficiency of Graphplan." In ECP97, pp. 221233. Toulouse, France. 1997
  6. ↑ Nebel, B., "On the Compilability and Expressive Power of Propositional Planning Formalisms." Journal of Artificial Intelligence Research , 12, 271315. 2000
  7. ↑ Jorge A. Baier., "Effective Search Techniques for Non-Classical Planning via Reformulation." Ph.D. thesis, University of Toronto, 2003.
  8. ↑ Edwing P.D. Pednault. ADL and the State-Transition Model of Action
  9. ↑ H. J. Levesque and R. J. Brachman. A fundamental tradeoff in knowledge representation and reasoning. In Readings in Knowledge Representation, H. J. Levesque and R. J. Brachman, eds, pp. 42–70. Morgan Kaufmann, San Mateo, CA, 1985.
  10. ↑ Vladimir Lifschitz and Arkady Rabinov. Miracles in formal theories of actions. Artificial Intelligence, 626(3):89–116. 1986
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.