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) \land Clean(𝑅_2)$
    • PDDL: negative literals are allowed (e.g., $¬Clean(𝑅_1) \land Clean(𝑅_2)$)
    • Literals are called sub-goals
  • No disjunctions $Clean(𝑅_1) \lor Clean(𝑅_2)$
  • 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

Exam questions

2020 02 13 Q4.1

To put the air conditioning to work one has to press the START button when the ON-OFF switch is ON and the air conditioning is not already working. Initially, the ON-OFF switch is OFF and the air conditioning is not working. The goal is to put the air conditioning to work.

Use PDDL to represent the problem. List all the problem-dependent symbols that you introduce and briefly explain the meaning of each of them. (Be careful to introduce the smallest possible set of symbols.) Then specify the initial state, the goal, and the action schemes that are strictly necessary to solve the problem.

Solution

Predicates:

  • $On$ the switch is ON
  • $Working$ the air conditioner is working

Initial state: $\lnot On \land \lnot Working$

Goal state: $Working$ Actions:

  • switchOn()
    • Precond: $\lnot On$
    • Eff: $On$
  • start()
    • Precond: $On \land \lnot Working$
    • Eff: $Working$
Back to top