In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, an action language is a language for specifying
state transition system
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled wit ...
s, 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
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machine
A machine is a physical system using Power (physics), power to apply Force, forces and control Motion, moveme ...
and
robotics
Robotics is an interdisciplinarity, interdisciplinary branch of computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist human ...
domains, where they describe how actions affect the states of systems over time, and may be used for
automated planning.
Action languages fall into two classes:
action description languages and action query languages. Examples of the former include
STRIPS,
PDDL, Language A (a generalization of STRIPS; the propositional part of Pednault's
ADL
Adl ( ar, عدل, ) is an Arabic word meaning 'justice', and is also one of the names of God in Islam. It is equal to the concept of ''Insaf'' انصاف (lit. sense of justice) in the Baháʼí Faith.
Adil ( ar, عادل, ), and Adeel ( ar, � ...
), Language B (an extension of A adding ''indirect effects'', distinguishing static and dynamic laws) and Language C (which adds indirect effects also, and does not assume that every fluent is automatically "inertial"). There are also the Action Query Languages P, Q and R. Several different algorithms exist for converting action languages, and in particular, action language C, to
answer set program
Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduce ...
s.
Since modern answer-set solvers make use of
boolean SAT
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 satisfie ...
algorithms to very rapidly ascertain
satisfiability
In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...
, this implies that action languages can also enjoy the progress being made in the domain of boolean SAT solving.
Formal definition
All action languages supplement the definition of a
state transition system
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled wit ...
with a set ''F'' of ''
fluents'', a set ''V'' of values that fluents may take, and a function mapping ''S'' × ''F'' to ''V'', where ''S'' is the set of states of a state transition system.
See also
*
Linear temporal logic In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths, e.g., a condition will eventually be true, a condition will ...
*
GOLOG
*
Fluent calculus The fluent calculus is a formalism for expressing dynamical domains in first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in ma ...
*
Situation calculus
*
Event calculus
References
{{DEFAULTSORT:Action Language
Programming language classification
Automated planning and scheduling
Transition systems