Skip to main content

Classical Planning

Classical planning is defined as the task of finding a sequence of actions to accomplish a goal in a discrete, deterministic, static, fully observable environment.

We have seen two approaches to this task: the problem-solving agent and the hybrid propositional logical agent. Both share two limitations:

  1. They both require ad hoc heuristics for each new domain: a heuristic evaluation function for search, and hand-written code for the hybrid wumpus agent.
  2. They both need to explicitly represent an exponentially large state space.

In response to these limitations, planning researchers have invested in a factored representation using a family of languages called PDDL, the Planning Domain Definition Language.

PDDL

Basic PDDL can handle classical planning domains, and extensions can handle non-classical domains that are continuous, partially observable, concurrent, and multi-agent.

In PDDL, a state is represented as a conjunction of ground atomic fluents. Recall that “ground” means no variables, “fluent” means an aspect of the world that changes over time, and “ground atomic” means there is a single predicate, and if there are any arguments, they must be constants.

Assumptions

  • Unique Name Assumption (UNA): different constants always denote different objects
  • Domain Closure Assumption (DCA): the environment includes only those objects that are denoted by a constant
  • Closed World Assumption (CWA): all literals that are not explicitly mentioned in the description of the state are assumed to be false (i.e., their negation is assumed to be true)

Actions and action schemas

An action schema represents a family of ground actions.

The schema consists of the action name, a list of all the variables used in the schema, a precondition and an effect. The precondition and the effect are each conjunctions of literals (positive or negated atomic sentences). We can choose constants to instantiate the variables, yielding a ground (variable-free) action.

A ground action a is applicable in state s if s entails the precondition of a; that is, if every positive literal in s the precondition is in and every negated literal is not.

The result of executing applicable action a in state s is defined as a state which is represented by the set of fluents formed by starting with s, removing the fluents that appear as negative literals in the action’s effects (what we call the delete list or DEL(a)), and adding the fluents that are positive literals in the action’s effects (what we call the add list or ADD(a))

Goals

  • Conjunction of literals, Clean(𝑅1) Ù Clean(𝑅2)
    • PDDL: negative literals are allowed (e.g., ¬Clean(𝑅")ÙClean(𝑅2))
    • Literals are called sub-goals
  • No disjunctions
  • A goal 𝐺 is satisfied in a state 𝑆 when all the positive literals of 𝐺 are contained in the representation of 𝑆 and all the negative literals of 𝐺 are not contained in 𝑆
  • Goals can contain variables
Back to top