View All Pages

Module2 - mtrl - Task Planning

Much of the material on this page comes from the lecture by Jonas Kvarnström and the exercises and labs from him from the last course round of the autonomous systems course. 

Intended learning outcomes

  • General feeling for what automated planning is, how planners work, when they can be applied
  • Learn how to specify general planning problems and apply existing planners

 

Overview of AI planning

There are different forms of planning. You might already have gone through the material on Motion Planning, if not it will come. In this part of the course we will look at planners which address planning problems at a higher level. Some of the actions in these plans could then involve motion planning for example. The picture below gives a simplified view of AI planning.

 

Central idea: Think before you act. 

  • Usually generate a complete solution in advance (not just a limited-horizon lookahead)
  • Particularly suitable when:
    • We want to optimize plan quality
    • Predicting the long-term consequences of an action is difficult (will this action help or hinder us, 40 steps from now?)
    • We have absolute objectives to achieve (not only a "quality scale")

 

For another classical example take a quick glance at the video of the robot Shakey Links to an external site..

Now go through the slides from Jonas Kvarnström ( Download planning-jonas-kvarnstrom-20160908.pdf

).

 

The classical planning framework is universal, domain independent, but the cost for that is performance of the algorithms. They will pretty much always do worse than algorithms tailored for a particular explicit problem description taking into account the knowledge about the domain. You — a user — also do not need to work directly with the state space, you work with a high-level description and the rest is taken care of by the framework. Most industry problems can be solved more efficiently by modeling them less abstractly and casting them as a discrete optimization problem and running a solver such as "Gurobi Links to an external site.".

PDDL

To be able to describe a planning problem, most planners make use of a language. Most such languages are based on STRIPS (Stanford Research Institute Problem Solver). One such language is PPDL.

PDDL, the Planning Domain Definition Language, was developed with the aim of generating a standard to replace or augment a variety of existing planning domain and problem description languages. It was created mainly to make a series of International Planning Competitions (IPC) possible. The base concepts used in PDDL mainly coincide with the concepts that were introduced in the WASP  planning lecture, but the surface syntax is somewhat different in order to cleanly support a number of extensions.

PDDL supports the full expressivity of earlier languages such as STRIPS and ADL (Action Description Language), as well as a large set of extensions of varying complexity. Providing full support for all aspects of PDDL is a very complex task. In fact, many planners support only the smaller STRIPS subset, possibly with a few extensions. Limiting the expressivity in this way allows the use of planning algorithms that use the limiting assumptions to improve performance. This is similar to how one can find special algorithms for linear programming in order to solve such problems faster than using more general algorithms supporting non-linear programming.

We will now give a brief introduction to PDDL. A PDDL definition consists of two parts: The domain definition and the problem definition. Although not required by the PDDL standard, many planners require that the two parts are in separate files.

Comments in a PDDL file start with a semicolon (";") and last to the end of the line.

Because PDDL is a very general language and most planners support only a subset, domains may declare requirements. The most commonly used requirements are:

:strips
The most basic subset of PDDL, consisting of STRIPS only.
:equality
The domain uses the predicate =, interpreted as equality.
:typing
The domain uses types (see typing Links to an external site. below).
:adl
The domain uses some or all of ADL (i.e. disjunctions and quantifiers in preconditions and goals, quantified and conditional effects).

Unfortunately, most planners' parsers are quite simple and often written under the assumption that you already know which parts of PDDL the planner supports. They often ignore the :requirements clause – if you use a feature of PDDL they don't support, they give you a parse error without further information. Nevertheless, you should declare the correct requirements in any domain you write.

Domain definition

The domain definition contains the domain predicates and operators (called actions in PDDL). It may also contain types (see below), constants, static facts and many other things, but these are not supported by the majority of planners.

The format of a (simple) domain definition is:

(define (domain DOMAIN_NAME)
  (:requirements [:strips] [:equality] [:typing] [:adl] ...)
  (:predicates (PREDICATE_1_NAME [?A1 ?A2 ... ?AN])
               (PREDICATE_2_NAME [?A1 ?A2 ... ?AN])
	       ...)

  (:action ACTION_1_NAME
    [:parameters (?P1 ?P2 ... ?PN)]
    [:precondition PRECOND_FORMULA]
    [:effect EFFECT_FORMULA]
   )

  (:action ACTION_2_NAME
    ...)

  ...)

Elements in []'s are optional, for those not familiar with formal grammars.

Names (of domains, predicates, actions, etc.) can usually contain alphanumeric characters, hyphens ("-") and underscores ("_"). There may be planners that allow less. Some planners use the same namespace for different items, so that you cannot (for example) use the same name for a domain and for a type.

Parameters of predicates and actions are distinguished by beginning with a question mark ("?").

For untyped domains, the parameters used in predicate declarations (the :predicates part) have no other function than to specify the number of arguments that the predicate should have, i.e. the parameter names do not matter (as long as they are distinct). Predicates can have zero parameters, but the predicate name still has to be written within parentheses.

Action Definitions

All parts of an action definition except the name are, according to the spec, optional (although, of couse, an action without effects is pretty useless). However, for an action that has no preconditions some planners may require an "empty" precondition, on the form :precondition (). Some planners may also require an empty :parameter list for actions without parameters.

Note: Some planners require that the arguments to an action are all different, i.e.the same object may not be used to instantiate two parameters. This ensures that the planner never tries pointless actions such as move(robot,locA,locA) which would move a robot from a location to the same location. At the same time there are cases where one does want the same argument to be used. For example, if we represent coordinates in a grid as the objects p1,p2,p3,p4,..., the planner should (but might not) allow actions such as move-to(p2,p2).

This may cause some difficulties (e.g. problems becoming unsolvable) if one is not aware of it. See the domain definition slidetile.pddl Links to an external site. and the two problem definitions eight01.pddl Links to an external site. and eight01x.pddl Links to an external site. for an example of this problem and how to fix it. (For an explanation of the corresponding problems see this video Links to an external site.)

Actions: Precondition Formulas

In a STRIPS domain, a precondition formula may be:

  • An atomic formula:
    (PREDICATE_NAME ARG1 ... ARG_N)
    The predicate arguments must be parameters of the action (or constants declared in the domain, if the domain has constants).
  • A conjunction of atomic formulas:
    (and ATOM1 ... ATOM_N)

If the domain uses :equality, an atomic formula may also be of the form (= ARG1 ARG2). Many planners that support equality also allow negated equality, which is written (not (= ARG1 ARG2)), even if they do not allow negation in any other part of the definition.

In an ADL domain, a precondition may in addition be:

  • A general negation, conjunction or disjunction:
    (not CONDITION_FORMULA)
    (and CONDITION_FORMULA1 ... CONDITION_FORMULA_N)
    (or CONDITION_FORMULA1 ... CONDITION_FORMULA_N)
  • A quantified formula:
    (forall (?V1 ?V2 ...) CONDITION_FORMULA)
    (exists (?V1 ?V2 ...) CONDITION_FORMULA)

Actions: Effect Formulas

In PDDL, the effects of an action are not explicitly divided into "adds" and "deletes". Instead, negative effects (deletes) are denoted by negation.

In a STRIPS domain, an effect formula may consist of:

  • An added atom:
    (PREDICATE_NAME ARG1 ... ARG_N)
    The predicate arguments must be parameters of the action (or constants declared in the domain, if the domain has constants).
  • A deleted atom:
    (not (PREDICATE_NAME ARG1 ... ARG_N))
  • A conjunction of atomic effects:
    (and ATOM1 ... ATOM_N)

The equality predicate (=) can of course not occur in an effect formula; no action can make two identical objects be not identical or vice versa!

Note that you can't use "exists" in action effects, since that would correspond to non-deterministic effects.

In an ADL domain, an effect formula may in addition contain:

  • A conditional effect:
    (when CONDITION_FORMULA EFFECT_FORMULA)
    The interpretation is that the specified effect takes place only if the specified condition formula is true in the state where the action is executed. Conditional effects are usually placed within quantifiers.
  • A universally quantified formula:
    (forall (?V1 ?V2 ...) EFFECT_FORMULA)

Note that nested use of "when" and "and" will confuse some planners. In general, it is good practice not to nest conditions more than necessary, and to keep expressions simple and readable. Most operators can be written using a single list of effects with a single level of nesting: "(and (p1) (p2) (when (p3) (p4)) (p5) (p6))".

Problem definition

The problem definition contains the objects present in the problem instance, the initial state description, and the goal.

The format of a (simple) problem definition is:

 

(define (problem PROBLEM_NAME)
  (:domain DOMAIN_NAME)
  (:objects OBJ1 OBJ2 ... OBJ_N)
  (:init ATOM1 ATOM2 ... ATOM_N)
  (:goal CONDITION_FORMULA)
  )

The initial state description (the :init section) is simply a list of all the ground atoms that are true in the initial state. All other atoms are by definition false.

The goal description is a formula of the same form as an action precondition. All predicates used in the initial state and goal description should naturally be declared in the corresponding domain. Goals are generally specified as a single conjunction: (and (something) (somethingelse) ...).

In difference to action preconditions, the initial state and goal descriptions should be ground, meaning that all predicate arguments should be object or constant names rather than parameters. (An exception is quantified goals in ADL domains, where of course the quantified variables may be used within the scope of the quantifier. However, even some planners that claim to support ADL do not allow quantifiers in goals.)

 

Typing

PDDL has a (very) special syntax for declaring parameter and object types. If types are to be used in a domain, the domain should first of all declare the requirement :typing.

Second, the type names have to be declared before they are used (which usually means before the :predicates declaration). This is done with the declaration

  (:types NAME1 ... NAME_N)

Then, to declare the type of a parameter of a predicate or action one writes ?X - TYPE_OF_X. A list of parameters of the same type can be abbreviated to ?X ?Y ?Z - TYPE_OF_XYZ. Note that the hyphen between parameter and type name has to be "free-standing", i.e. surrounded by whitespace.

The syntax is the same for declaring types of objects in the problem definition.

Fast Downward planner

To get some hands on experience we make some tests with the so called Fast Downward planner.

Installing Fast Downward

sudo apt-get install cmake g++ g++-multilib mercurial make python flex bison
cd ~/software
hg clone http://hg.fast-downward.org downward
cd downward
./build.py
cd ~/software/downward
git clone https://github.com/KCL-Planning/VAL.git
    

Links to an external site.
cd VAL
make clean
make validate parser
export PATH=$PATH:/home/wasp/software/downward/VAL
You might want to put the export statement into you ~/.bashrc file so that VAL is always in your path, otherwise you need to execute that in every terminal you want to validate a plan in.

Testing Fast Downward

Start by testing the Fast Downward planner on one of the examples from the International Planning Contest (IPC) from 2011. You find the PDDL files that define the problem here
  • ~/software/downward/misc/tests/benchmarks/gripper/domain.pddl
  • ~/software/downward/misc/tests/benchmarks/gripper/prob01.pddl
Make sure that you understand them.
When writing PPDL it is very useful to be able to check that your files are written correctly. You can use the parser from VAL to do this. Test
cd ~/software/downward
VAL/parser misc/tests/benchmarks/gripper/domain.pddl
VAL/parser misc/tests/benchmarks/gripper/domain.pddl misc/tests/benchmarks/gripper/prob01.pddl

Then run the planner with
cd ~/software/downward
./fast-downward.py --validate --alias seq-sat-lama-2011 misc/tests/benchmarks/gripper/prob01.pddl
Take a look at the solution which is found in the file sas_plan.1
more sas_plan.1

Combining motion planning and PDDL

This video shows motion planning + PDDL integratedhttps://www.youtube.com/watch?v=kb79tR5bmlE Links to an external site.

Extra

If you want more details, the International Planning Competition web pages contain a list of papers related to PDDL, including definitions of PDDL 1.2, 2.1, 2.2, and 3.0.

Several examples of PDDL domain and problem definitions may be found, using either the STRIPS subset of PDDL Links to an external site. or using object types and some extended ADL features Links to an external site.. There are also several variants of the Satellite domain Links to an external site. (used in IPC 2002), which illustrate the extended features of PDDL 2.1.