Misplaced Pages

#952047

61-416: PDDL is a human-readable format for problems in automated planning that gives a description of the possible states of the world, a description of the set of possible actions, a specific initial state of the world, and a specific set of desired goals. Action descriptions include the prerequisites of the action and the effects of the action. PDDL separates the model of the planning problem into two major parts: (1)

122-405: A b l e ) , t ) {\displaystyle HoldsAt(on(box,table),t)} means that the box is actually on the table at time t {\displaystyle t} , where the predicate H o l d s A t {\displaystyle HoldsAt} is the one that tells when fluents are true. This representation of fluents is used in the event calculus , in

183-421: A control function , which is also part of the plan. OPT ( O ntology with P olymorphic T ypes) was a profound extension of PDDL2.1 by Drew McDermott from around 2003–2005 (with some similarities to PDDL+). It was an attempt to create a general-purpose notation for creating ontologies , defined as formalized conceptual frameworks for planning domains about which planning applications are to reason. Its syntax

244-482: A fluent is a condition that can change over time. In logical approaches to reasoning about actions, fluents can be represented in first-order logic by predicates having an argument that depends on time. For example, the condition "the box is on the table", if it can change over time, cannot be represented by O n ( b o x , t a b l e ) {\displaystyle \mathrm {On} (\mathrm {box} ,\mathrm {table} )} ;

305-431: A problem-name definition, the definition of the related domain-name , the definition of all the possible objects (atoms in the logical universe), initial conditions (the initial state of the planning environment, a conjunction of true/false facts), and the definition of goal-states (a logical expression over facts that should be true/false in a goal-state of the planning environment). Thus eventually PDDL1.2 captured

366-403: A search problem where the set of possible partial-order plans is the search space. The initial state would be the plan with the open preconditions equal to the goal conditions. The final state would be any plan with no open preconditions, i.e. a solution. The initial state is the starting conditions, and can be thought of as the preconditions to the task at hand. For a task of setting the table,

427-440: A certain task, the creator needs to take into account how much energy is needed. Though a partial-order plan may be quicker it may not be worth the energy cost for the robot. The creator must be aware of and weigh these two options to build an efficient robot. This artificial intelligence -related article is a stub . You can help Misplaced Pages by expanding it . Fluent (artificial intelligence) In artificial intelligence ,

488-417: A domain description of those elements that are present in every problem of the problem domain, and (2) the problem description which determines the specific planning problem. The problem description includes the initial state and the goals to be accomplished. The example below gives a domain definition and a problem description instance for the automated planning of a robot with two gripper arms. PDDL becomes

549-465: A goal, a partial-order plan specifies all actions that must be taken, but specifies an ordering between actions only where needed. Consider the following situation: a person must travel from the start to the end of an obstacle course. The course is composed of a bridge, a see-saw, and a swing-set. The bridge must be traversed before the see-saw and swing-set are reachable. Once reachable, the see-saw and swing-set can be traversed in any order, after which

610-415: A partial ordering between actions and only commits ordering between actions when forced to, that is, ordering of actions is partial. Also this planning doesn't specify which action will come out first when two actions are processed. By contrast, total-order planning maintains a total ordering between all actions at every stage of planning. Given a problem in which some sequence of actions is needed to achieve

671-472: A simple mechanism for the inheritance and polymorphism of actions, goals and metrics was also introduced in MA-PDDL (assuming :typing is declared). Since PDDL3.1 assumes that the environment is deterministic and fully observable, the same holds for MA-PDDL, i.e. every agent can access the value of every state fluent at every time-instant and observe every previously executed action of each agent, and also

SECTION 10

#1732790613953

732-421: A solution, given that a solution does in fact exist. Partial-order planning is the opposite of total-order planning , in which actions are sequenced all at once and for the entirety of the task at hand. The question arises when one has two competing processes, which one is better? Anthony Barret and Daniel Weld have argued in their 1993 book, that partial-order planning is superior to total-order planning , as it

793-479: A subgoal trivially or laboriously serializable is the search space of different plans. They found that partial-order planning is more adept at finding the quickest path, and is therefore the more efficient of these two main types of planning. Partial-order plans are known to easily and optimally solve the Sussman anomaly . Using this type of incremental planning system solves this problem quickly and efficiently. This

854-510: A syntactically seemingly small, but semantically quite significant change in expressiveness. The latest version of the language is PDDL3.1 . The BNF (Backus–Naur Form) syntax definition of PDDL3.1 can be found among the resources of the IPC-2011 homepage or the IPC-2014 homepage . This extension of PDDL2.1 from around 2002–2006 provides a more flexible model of continuous change through

915-430: A third argument is necessary to the predicate O n {\displaystyle \mathrm {On} } to specify the time: O n ( b o x , t a b l e , t ) {\displaystyle \mathrm {On} (\mathrm {box} ,\mathrm {table} ,t)} means that the box is on the table at time t {\displaystyle t} . This representation of fluents

976-400: Is a function and not a predicate. In first-order logic, converting predicates to functions is called reification ; for this reason, fluents represented by functions are said to be reified. When using reified fluents, a separate predicate is necessary to tell when a fluent is actually true or not. For example, H o l d s A t ( o n ( b o x , t

1037-407: Is a plan which specifies all actions that must be taken, but only specifies the order between actions when needed. It is the result of a partial-order planner. A partial-order plan consists of four components: To keep the possible orders of the actions as open as possible, the set of order conditions and causal links must be as small as possible. A plan is a solution if the set of open preconditions

1098-434: Is empty. A linearization of a partial order plan is a total order plan derived from the particular partial order plan; in other words, both order plans consist of the same actions, with the order in the linearization being a linear extension of the partial order in the original partial order plan. For example, a plan for baking a cake might start: This is a partial plan because the order for finding eggs, flour and milk

1159-513: Is faster and thus more efficient. They tested this theory using Korf’s taxonomy of subgoal collections , in which they found that partial-order planning performs better because it produces more trivial serializability than total-order planning . Trivial serializability facilitates a planner’s ability to perform quickly when dealing with goals that contain subgoals. Planners perform more slowly when dealing with laboriously serializable or nonserializable subgoals . The determining factor that makes

1220-423: Is modified in the situation calculus by using the sequence of the past actions in place of the current time. A fluent can also be represented by a function, dropping the time argument. For example, that the box is on the table can be represented by o n ( b o x , t a b l e ) {\displaystyle on(box,table)} , where o n {\displaystyle on}

1281-619: Is more expressive than PPDDL1.0. MA-PDDL ( M ulti A gent PDDL ) is a minimalistic, modular extension of PDDL3.1 introduced in 2012 (i.e. a new :multi-agent requirement) that allows planning by and for multiple agents. The addition is compatible with all the features of PDDL3.1 and addresses most of the issues of MAPL . It adds the possibility to distinguish between the possibly different actions of different agents (i.e. different capabilities). Similarly different agents may have different goals and/or metrics . The preconditions of actions now may directly refer to concurrent actions (e.g.

SECTION 20

#1732790613953

1342-432: Is not specified, the agent can wander around the store reactively accumulating all the items on its shopping list until the list is complete. A partial-order planner is an algorithm or program which will construct a partial-order plan and search for a solution. The input is the problem description, consisting of descriptions of the initial state , the goal and possible actions . The problem can be interpreted as

1403-413: Is realized through speech act based communication among agents. This assumption may be artificial, since agents executing concurrent plans shouldn't necessarily communicate to be able to function in a multi-agent environment. Finally, MAPL introduces events (endogenous and exogenous) for the sake of handling concurrency of actions. Thus events become part of plans explicitly, and are assigned to agents by

1464-497: Is referred to as the start-process-stop model . Distinctions are made between logical and numeric states: transitions between logical states are assumed to be instantaneous whilst occupation of a given logical state can endure over time. Thus in PDDL+ continuous update expressions are restricted to occur only in process effects. Actions and events, which are instantaneous, are restricted to the expression of discrete change. This introduces

1525-512: Is that the precondition to the start of the algorithm will be unsatisfied as the table will no longer be clear. Thus, constraints exist that must be added to the algorithm that force Actions 2, 3, and 4 to come after Action 1. Once these steps are completed, the algorithm will finish and the goal will have been completed. As seen in the algorithm presented above, partial-order planning can encounter certain threats, meaning orderings that threaten to break connected actions, thus potentially destroying

1586-415: Is to describe a process model not with mathematical equations but with natural language. That means an action is not only determined by its trajectory, but with a symbolic model, very similar to a text adventure. Naive physics stands in opposition to a numerical physics engine and has the obligation to predict the outcome of actions. The fluent realizes the common sense grounding between the robot's motion and

1647-537: The Action description language (ADL), among others. The PDDL language uses principles from knowledge representation languages which are used to author ontologies , an example is the Web Ontology Language (OWL). Ontologies are a formal way to describe taxonomies and classification networks, essentially defining the structure of knowledge for various domains: the nouns representing classes of objects and

1708-494: The fluent calculus , and in the features and fluents logics . Some fluents can be represented as functions in a different way. For example, the position of a box can be represented by a function o n ( b o x , t ) {\displaystyle on(box,t)} whose value is the object the box is standing on at time t {\displaystyle t} . Conditions that can be represented in this way are called functional fluents . Statements about

1769-583: The "physics" of a deterministic single-agent discrete fully accessible planning environment. This was the official language of the 3rd IPC in 2002. It introduced numeric fluents (e.g. to model non-binary resources such as fuel-level, time, energy, distance, weight, ...), plan-metrics (to allow quantitative evaluation of plans, and not just goal-driven, but utility-driven planning, i.e. optimization, metric-minimization/maximization), and durative/continuous actions (which could have variable, non-discrete length, conditions and effects). Eventually PDDL2.1 allowed

1830-488: The actions of other agents) and thus actions with interacting effects can be represented in a general, flexible way (e.g. suppose that at least 2 agents are needed to execute a lift action to lift a heavy table into the air, or otherwise the table would remain on the ground (this is an example of constructive synergy, but destructive synergy can be also easily represented in MA-PDDL)). Moreover, as kind of syntactic sugar,

1891-402: The before mentioned 3-part modelling of periods of continuous change: (1) an action or event starts a period of continuous change on a numeric variable expressed by means of a process; (2) the process realizes the continuous change of the numeric variable; (3) an action or event finally stops the execution of the process and terminates its effect on the numeric variable. Comment: the goals of

Planning Domain Definition Language - Misplaced Pages Continue

1952-405: The concurrent actions of agents unambiguously determine the next state of the environment. This was improved later by the addition of partial-observability and probabilistic effects (again, in form of two new modular requirements, :partial-observability and :probabilistic-effects , respectively, the latter being inspired by PPDDL1.0 , and both being compatible with all the previous features of

2013-417: The end is reachable. In a partial-order plan, ordering between these obstacles is specified only when needed. The bridge must be traversed first. Second, either the see-saw or swing-set can be traversed. Third, the remaining obstacle can be traversed. Then the end can be traversed. Partial-order planning relies upon the principle of least commitment for its efficiency. A partial-order plan or partial plan

2074-405: The entire plan. There are two ways to resolve threats: Promotion orders the possible threat after the connection it threatens. Demotion orders the possible threat before the connection it threatens. Partial-order planning algorithms are known for being both sound and complete, with sound being defined as the total ordering of the algorithm, and complete being defined as the capability to find

2135-483: The generic mapping) could be defined with variables, which could have an even higher level type ( level 2 type ) not to speak of that the mappings could be arbitrary, i.e. the domain or range of a function (e.g. predicate, numeric fluent) could be any level 0/1/2 type. For example, functions could map from arbitrary functions to arbitrary functions...). OPT was basically intended to be (almost) upwardly compatible with PDDL2.1. The notation for processes and durative actions

2196-404: The given planning problem) and preferences (soft-constraints in form of logical expressions, similar to hard-constraints, but their satisfaction wasn't necessary, although it could be incorporated into the plan-metric e.g. to maximize the number of satisfied preferences, or to just measure the quality of a plan) to enable preference-based planning . Eventually PDDL3.0 updated the expressiveness of

2257-427: The initial state and finishes when all parts of the goal have been achieved. In the setting a table example, two types of actions exist that must be addressed: the put-out and lay operators. Four unsolved operators also exist: Action 1, lay-tablecloth, Action 2, Put-out (plates), Action 3, Put-out (silverware), and Action 4, Put-out (glasses). However, a threat arises if Action 2, 3, or 4 comes before Action 1. This threat

2318-442: The initial state could be a clear table. The goal is simply the final action that needs to be accomplished, for example setting the table. The operators of the algorithm are the actions by which the task is accomplished. For this example there may be two operators: lay (tablecloth), and place (glasses, plates, and silverware). The plan space of the algorithm is constrained between its start and finish. The algorithm starts, producing

2379-503: The input to planner software, which is usually a domain-independent Artificial Intelligence (AI) planner. PDDL does not describe the output of the planner software, but the output is usually a totally or partially ordered plan , which is a sequence of actions, some of which may be executed in parallel. The PDDL language was inspired by the Stanford Research Institute Problem Solver (STRIPS) and

2440-414: The language to be able to cope with recent, important developments in planning. This was the official language of the deterministic track of the 6th and 7th IPC in 2008 and 2011 respectively. It introduced object-fluents (i.e. functions' range now could be not only numerical (integer or real), but it could be any object-type also). Thus PDDL3.1 adapted the language even more to modern expectations with

2501-406: The language with a few important elements, but wasn't a radical evolution compared to PDDL2.1 after PDDL1.2. This was the official language of the deterministic track of the 5th IPC in 2006. It introduced state-trajectory constraints (hard-constraints in form of modal-logic expressions, which should be true for the state-trajectory produced during the execution of a plan, which is a solution of

Planning Domain Definition Language - Misplaced Pages Continue

2562-416: The language, including :multi-agent ). This is the domain definition of a STRIPS instance for the automated planning of a robot with two gripper arms. And this is the problem definition that instantiates the previous domain definition with a concrete environment with two rooms and two balls. Partial-order planning Partial-order planning is an approach to automated planning that maintains

2623-416: The mentioned differences planning and execution of plans (e.g. during critical space missions) may be more robust when using NDDL, but the correspondence to standard planning-problem representations other than PDDL may be much less intuitive than in case of PDDL. MAPL ( M ulti- A gent P lanning L anguage, pronounced "maple") is an extension of PDDL2.1 from around 2003. It is a quite serious modification of

2684-547: The original language. It introduces non-propositional state-variables (which may be n-ary: true, false, unknown, or anything else). It introduces a temporal model given with modal operators (before, after, etc.). Nonetheless, in PDDL3.0 a more thorough temporal model was given, which is also compatible with the original PDDL syntax (and it is just an optional addition). MAPL also introduces actions whose duration will be determined in runtime and explicit plan synchronization which

2745-644: The plan might be achieved before an active process is stopped. NDDL ( N ew D omain D efinition L anguage) is NASA 's response to PDDL from around 2002. Its representation differs from PDDL in several respects: 1) it uses a variable/value representation (timelines/activities) rather than a propositional / first-order logic , and 2) there is no concept of states or actions, only of intervals (activities) and constraints between those activities . In this respect, models in NDDL look more like schemas for SAT encodings of planning problems rather than PDDL models. Because of

2806-408: The planner is not specified by PDDL, but it is usually a totally or partially ordered plan (a sequence of actions, some of which may be executed even in parallel sometimes). Now lets take a look at the contents of a PDDL1.2 domain and problem description in general... (1) The domain description consisted of a domain-name definition, definition of requirements (to declare those model-elements to

2867-737: The planner which the PDDL-model is actually using), definition of object-type hierarchy (just like a class-hierarchy in OOP ), definition of constant objects (which are present in every problem in the domain), definition of predicates (templates for logical facts), and also the definition of possible actions (operator-schemas with parameters, which should be grounded/instantiated during execution). Actions had parameters (variables that may be instantiated with objects), preconditions and effects . The effects of actions could be also conditional (when-effects) . (2) The problem description consisted of

2928-466: The probabilistic track of the 4th and 5th IPC in 2004 and 2006 respectively. It extended PDDL2.1 with probabilistic effects (discrete, general probability distributions over possible effects of an action), reward fluents (for incrementing or decrementing the total reward of a plan in the effects of the actions), goal rewards (for rewarding a state-trajectory, which incorporates at least one goal-state), and goal-achieved fluents (which were true, if

2989-432: The related problem description . Such a division of the model allows for an intuitive separation of those elements, which are (1) present in every specific problem of the problem-domain (these elements are contained in the domain-description), and those elements, which (2) determine the specific planning-problem (these elements are contained in the problem-description). Thus several problem-descriptions may be connected to

3050-532: The representation and solution of many more real-world problems than the original version of the language. This was the official language of the deterministic track of the 4th IPC in 2004. It introduced derived predicates (to model the dependency of given facts from other facts, e.g. if A is reachable from B, and B is reachable from C, then A is reachable from C (transitivity)), and timed initial literals (to model exogenous events occurring at given time independently from plan-execution). Eventually PDDL2.2 extended

3111-509: The same domain-description (just as several instances may exist of a class in OOP (Object Oriented Programming) or in OWL (Web Ontology Language) for example). Thus a domain and a connecting problem description forms the PDDL-model of a planning-problem, and eventually this is the input of a planner (usually domain-independent AI planner) software, which aims to solve the given planning-problem via some appropriate planning algorithm. The output of

SECTION 50

#1732790613953

3172-475: The state-trajectory incorporated at least one goal-state). Eventually these changes allowed PPDDL1.0 to realize Markov Decision Process (MDP) planning, where there may be uncertainty in the state-transitions, but the environment is fully observable for the planner/agent. APPL ( A bstract P lan P reparation L anguage) is a newer variant of NDDL from 2006, which is more abstract than most existing planning languages such as PDDL or NDDL. The goal of this language

3233-490: The task description in natural language. From a technical perspective, a fluent is equal to a parameter that is parsed by the naive physics engine. The parser converts between natural language fluents and numerical values measured by sensors. As a consequence, the human-machine interaction is improved. This artificial intelligence -related article is a stub . You can help Misplaced Pages by expanding it . This programming language theory or type theory -related article

3294-420: The use of autonomous processes and events . The key this extension provides is the ability to model the interaction between the agent's behaviour and changes that are initiated by the agent's environment. Processes run over time and have a continuous effect on numeric values. They are initiated and terminated either by the direct action of the agent or by events triggered in the environment. This 3-part structure

3355-406: The values of such functions can be given in first-order logic with equality using literals such as o n ( b o x , t ) = t a b l e {\displaystyle on(box,t)=table} . Some fluents are represented this way in the situation calculus . From a historical point of view, fluents were introduced in the context of qualitative reasoning. The idea

3416-424: The verbs representing relations between the objects. The latest version of PDDL is described in a BNF (Backus–Naur Form) syntax definition of PDDL 3.1. Several online resources of how to use PDDL are available, and also a book. This was the official language of the 1st and 2nd IPC in 1998 and 2000 respectively. It separated the model of the planning problem in two major parts: (1) domain description and (2)

3477-406: Was a result of partial-order planning that solidified its place as an efficient planning system. One drawback of this type of planning system is that it requires a lot more computational power for each node. This higher per-node cost occurs because the algorithm for partial-order planning is more complex than others. This has important artificial intelligence implications. When coding a robot to do

3538-450: Was based on PDDL, but it had a much more elaborate type system , which allowed users to make use of higher-order constructs such as explicit λ-expressions allowing for efficient type inference (i.e. not only domain objects had types ( level 0 types ), but also the functions/fluents defined above these objects had types in the form of arbitrary mappings ( level 1 types ), which could be generic, so their parameters (the domain and range of

3599-413: Was borrowed mainly from PDDL+ and PDDL2.1, but beyond that OPT offered many other significant extensions (e.g. data-structures , non-Boolean fluents , return-values for actions, links between actions, hierarchical action expansion , hierarchy of domain definitions , the use of namespaces for compatibility with the semantic web ). PPDDL ( P robabilistic PDDL ) 1.0 was the official language of

3660-741: Was the official language of the uncertainty track of the 7th IPC in 2011. Conceptually it is based on PPDDL1.0 and PDDL3.0, but practically it is a completely different language both syntactically and semantically. The introduction of partial observability is one of the most important changes in RDDL compared to PPDDL1.0. It allows efficient description of Markov Decision Processes (MDPs) and Partially Observable Markov Decision Processes (POMDPs) by representing everything (state-fluents, observations, actions, ...) with variables. This way RDDL departs from PDDL significantly. Grounded RDDL corresponds to Dynamic Bayesian Networks (DBNs) similarly to PPDDL1.0, but RDDL

3721-476: Was to simplify the formal analysis and specification of planning problems that are intended for safety-critical applications such as power management or automated rendezvous in future manned spacecraft. APPL used the same concepts as NDDL with the extension of actions , and also some other concepts, but still its expressive power is much less than PDDL's (in hope of staying robust and formally verifiable). RDDL ( R elational D ynamic influence D iagram L anguage)

SECTION 60

#1732790613953
#952047