Notes - Artificial Intelligence MT24, Planning with propositional logic

Created: October 27, 2024
Updated: January 14, 2025

Flashcards

Suppose a $T$-step plan is represented as a logical formula $\varphi _ T$. What is the idea behind planning with propositional logic?
\[\text{there exists a valid }T\text{-step plan} \iff \text{there exists a valuation }v \text{ such that }v(\varphi_T) = T\]

So iterate over all $T = 1, 2, \ldots, N$ up to some reasonable upper bound $N$, and try and find a valuation.

Suppose a planning problem is formulated in STRIPS using:

  • Predicates: A set of possible predicates (relations) used in formulating the problem.
  • Constants: A set of constants (objects) used in formulating the problem.
  • States: A set of positive ground atoms describing what holds currently, in terms of these predicates and constants
    • e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Milk})\}$
  • Goal: A set of ground atoms to be made true (you are also allowed to satisfy a superset):
    • e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Drill})\}$.
  • Action: A precondition and postcondition
    • Precondition: What must be true before an action is carried out
    • Postcondition: A set of atoms to be added (appear positively) and a set of atoms to be removed (appear negatively)

Describe the technique used to convert the problem into a propositional logic formula $\varphi _ T$ such that

\[\text{there exists a valid }T\text{-step plan} \iff \text{there exists a valuation }v \text{ such that }v(\varphi_T) = T\]

.

For each $t = 1, \ldots, T$, introduce propositional variables:

  • $F^t$ for each ground atom $F$
    • $F^t$ will be true iff the ground atom $F$ is in the state at step $t$
  • $A^t$ for each ground action $A$ (i.e. not an action template in terms of variables)
    • $A^t$ will be true iff the action is taken at step $t$

Then construct

\[\varphi_T = \varphi^\text{initial} \land \varphi_T^\text{goal} \land \varphi_T^\text{succ} \land \varphi_T^\text{prec} \land \varphi_T^\text{excl}\]

where intuitively:

  • $\varphi^\text{initial}$ ensures that every ground atom occurring in the initial state is true and the ground atoms not occurring are false,
  • $\varphi _ T^\text{goal}$ ensures that every ground atom required for the goal is satisfied eventually,
  • $\varphi^\text{succ} _ T$ ensures that each ground atom is only set if an action taken that made it true, or it was already true and nothing has undone it,
  • $\varphi^\text{prec} _ T$ ensures that if an action is taken, all preconditions must be met
  • $\varphi _ T^\text{excl}$ ensures that only one action can be taken each time step

In more detail:

  • $\varphi^\text{initial}$ (initial axioms): is a conjunction of
    • $F^0$ for each ground atom $F$ occurring in the initial state
    • $\lnot F^0$ for each ground atom $F$ not occurring in the initial state
  • $\varphi^\text{goal} _ T$ (goal axioms): is a conjunction of:
    • $F^T$ for each ground atom $F$ occurring in the goal
  • $\varphi _ T^\text{succ}$ (successor-state axioms): is a conjunction of:
    • For each ground atom $F$ and each $0 \le t < T$, contains
    • $F^{t+1} \leftrightarrow \text{ActCauses}F^t \lor (F^t \land \lnot \text{ActCausesNot}F^t)$
    • Where $\text{ActCauses}F^t$ is a disjunction of all ground actions with effect $F$ for timestep $t$, and
    • where $\text{ActCausesNot}F^t$ is a disjunction of all ground actions with effect $\lnot F$.
  • $\varphi _ T^\text{prec}$ (precondition axioms): is a conjunction of:
    • For each ground action $A$ and each $0 \le t < T$,
    • $A^t \to \text{Precond}A^t$
    • where $\text{Precond}A^t$ is a conjunction of all ground preconditions of $A$.
  • $\varphi^\text{excl} _ T$ (exclusion axioms): is a conjunction of:
    • For each pair of distinct actions $A _ i$ and $A _ j$ and each $0 \le t < T$
    • $\lnot (A _ i^t \land A _ 2^t)$.

Suppose a planning problem is formulated in STRIPS using:

  • Predicates: A set of possible predicates (relations) used in formulating the problem.
  • Constants: A set of constants (objects) used in formulating the problem.
  • States: A set of positive ground atoms describing what holds currently, in terms of these predicates and constants
    • e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Milk})\}$
  • Goal: A set of ground atoms to be made true (you are also allowed to satisfy a superset):
    • e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Drill})\}$.
  • Action: A precondition and postcondition
    • Precondition: What must be true before an action is carried out
    • Postcondition: A set of atoms to be added (appear positively) and a set of atoms to be removed (appear negatively)

One approach is to convert the problem into a propositional logic formula $\varphi _ T$ such that

\[\text{there exists a valid }T\text{-step plan} \iff \text{there exists a valuation }v \text{ such that }v(\varphi_T) = T\]

where for each $t = 1, \ldots, T$, we introduce propositional variables:

  • $F^t$ for each ground atom $F$
    • $F^t$ will be true iff the ground atom $F$ is in the state at step $t$
  • $A^t$ for each ground action $A$ (i.e. not an action template in terms of variables)
    • $A^t$ will be true iff the action is taken at step $t$

Then construct

\[\varphi_T = \varphi^\text{initial} \land \varphi_T^\text{goal} \land \varphi_T^\text{succ} \land \varphi_T^\text{prec} \land \varphi_T^\text{excl}\]

where intuitively:

  • $\varphi^\text{initial}$ ensures that every ground atom occurring in the initial state is true and the ground atoms not occurring are false,
  • $\varphi _ T^\text{goal}$ ensures that every ground atom required for the goal is satisfied eventually,
  • $\varphi^\text{succ} _ T$ ensures that each ground atom is only set if an action taken that made it true, or it was already true and nothing has undone it,
  • $\varphi^\text{prec} _ T$ ensures that if an action is taken, all preconditions must be met
  • $\varphi _ T^\text{excl}$ ensures that only one action can be taken each time step

Can you give an upper bound on the number of variables this has?
\[T \times (P + A) \times O^{R}\]

where:

  • $T$ is the max timestep (each timestep needs its own set of variables)
  • $P$ is the number of predicates and $A$ is the number of actions (we introduce several propositional variables for each predicate and for each action)
  • $O$ is the number of objects and $R$ is the maximal arity of a predicate or action (each predicate or action needs arguments, this is the number of possible ways we can fill each one in)

(this disagrees with the notes slightly but I think this is correct).

Consider the following STRIPS formulation of an air cargo transport problem:

  • Predicates:
    • $\mathbf{In}(c, p)$
    • $\mathbf{At}(x, a)$
    • $\mathbf{Cargo}(c)$
    • $\mathbf{Plane}(p)$
    • $\mathbf{Airport}(a)$
  • Constants:
    • $C _ 1, C _ 2, \ldots$
    • $P _ 1, P _ 2, \ldots$
    • $\text{SFO}, \text{JFK}, \ldots$
  • Initial state:
    • $\mathbf{At}(C _ 1, \text{SFO})$
    • $\mathbf{At}(C _ 2, \text{JFK})$
    • $\mathbf{Cargo}(C _ 1)$
    • $\mathbf{Airport}(\text{SFO})$
  • Goal state:
    • $\mathbf{At}(C _ 1, \text{JFK})$
    • $\mathbf{At}(C _ 2, \text{SFO})$

with the corresponding actions:

  • $\mathbf{Load}(c, p, a)$
    • Preconditions: $\mathbf{At}(c, a), \mathbf{At}(p, a), \mathbf{Cargo}(c), \mathbf{Plane}(p), \mathbf{Airport}(a)$
    • Effects: $\mathbf{At}(c, a), \lnot \mathbf{In}(c, p)$
  • $\mathbf{Unload}(c, p, a)$
    • Preconditions: $\mathbf{In}(c, p), \mathbf{At}(p, a), \mathbf{Cargo}(c), \mathbf{Plane}(p), \mathbf{Airport}(a)$
    • Effects: $\mathbf{At}(c, a), \lnot \mathbf{In}(c, p)$
  • $\mathbf{Fly}(p, \text{from}, \text{to})$
    • Preconditions: $\mathbf{At}(p, \text{from}), \mathbf{Plane}(p), \mathbf{Airport}(\text{from}), \mathbf{Airport}(\text{to})$
    • Effects: $\lnot \mathbf{At}(p, \text{from}), \mathbf{At}(p, \text{to})$

One approach is to convert the problem into a propositional logic formula $\varphi _ T$ such that

\[\text{there exists a valid }T\text{-step plan} \iff \text{there exists a valuation }v \text{ such that }v(\varphi_T) = T\]

where for each $t = 1, \ldots, T$, we introduce propositional variables:

  • $F^t$ for each ground atom $F$
    • $F^t$ will be true iff the ground atom $F$ is in the state at step $t$
  • $A^t$ for each ground action $A$ (i.e. not an action template in terms of variables)
    • $A^t$ will be true iff the action is taken at step $t$

Then construct

\[\varphi_T = \varphi^\text{initial} \land \varphi_T^\text{goal} \land \varphi_T^\text{succ} \land \varphi_T^\text{prec} \land \varphi_T^\text{excl}\]

where intuitively:

  • $\varphi^\text{initial}$ ensures that every ground atom occurring in the initial state is true and the ground atoms not occurring are false,
  • $\varphi _ T^\text{goal}$ ensures that every ground atom required for the goal is satisfied eventually,
  • $\varphi^\text{succ} _ T$ ensures that each ground atom is only set if an action taken that made it true, or it was already true and nothing has undone it,
  • $\varphi^\text{prec} _ T$ ensures that if an action is taken, all preconditions must be met
  • $\varphi _ T^\text{excl}$ ensures that only one action can be taken each time step

In this context, what would $\varphi^\text{prec} _ 2$ look like, specifically for the $\mathbf{Fly}$ action?

For each timestep $t = 0, 1, 2$, conjunction over all the actions and their preconditions. For those involving $\mathbf{Fly}$, this would be:

  • $\mathbf{Fly}(P _ 1, \text{JFK}, \text{SFO})^t \to \mathbf{At}(P _ 1, \text{JFK})^t$
  • $\mathbf{Fly}(P _ 1, \text{JFK}, \text{SFO})^t \to \mathbf{Plane}(P _ 1)^t$
  • $\mathbf{Fly}(P _ 1, \text{JFK}, \text{SFO})^t \to \mathbf{Airport}(\text{JFK})^t$
  • $\mathbf{Fly}(P _ 1, \text{JFK}, \text{SFO})^t \to \mathbf{Airport}(\text{SFO})^t$


Related posts