4. Deductive Planning (Classical Planning)

History of the Situation Calculus

• introducedby McCarthy (1963)

• used for plan construction by resolution, Green (1969)

• further developments in the context of the event calculus (Kowalski, 1968) and fluent calculus (Thielscher, 2000)

Features of Situation Calculus

• States: described by logical formulas

• Operators: described by logical axioms

• Plans: computed by theorem provers

—> SC does not use the Closed-World-Assumption

(= if something is not explicitly stated to be true, it’s not false either in SC)

Situations and Fluents

• Predicates that change over time get an additional argument (captures change)

• Additional argument represents current situation

• Predicates are called fluents

—> keeps track of all actions that happened (everything can be deduced)

• Situations are terms. They’re either:

  • Atomic Situations (constants) like S1 or

  • Complex Situations (created from atomic situations using operators)

Effect Axioms

—> describe preconditions and effects of operators

Frame Axioms

Frame Problem in Situation Calculus:

we don’t only need axioms describing the effect of actions, but also axioms describing what remains unchanged

Frame Axioms

—> describe what relations remain unaffected by actions

—> describe properties of previous situations that remain true

Planning Problems using the Situation Calculus

• When operators have been described, planning problems can be solved by

  1. Defining Initial State (logical atoms)

  2. Defining Goal State (goals is to prove a theorem)

  3. Applying Theorem Prover

Planning Problems in Situation Calculus

Qualification Problem:

—> Preconditions in Effect Axioms can solve it

Frame Problem:

—> Frame Axioms can solve it

Ramification Problem:

—> Additional Axioms can solve it (“if an object is attached to another object and one of it is moved, the other moves too.“)

In practice, however, it’s difficult to guarantee that all cases are covered, and runtime may suffer

Planning with Golog

Golog combines

• Logical Programming

• Situation Calculus

Situation Calculus (example of Deductive Planning)

• States are represented by sets of Fluents (logical atoms)

  • predicates with an extra term which describes the situation

• Operators and their Effects are described by Logical Axioms

• Planning can be reduced to Theorem Proving

• Deductive Reasoning ability comes for free

  (because all the time we have knowledge of the past steps, and we can deduce to initial state or to further states)

• Verification and Computational Performance can be a problem

  (expensive in memory, running time, computation)