Notes - Artificial Intelligence MT24, Planning with propositional logic


Flashcards

Suppose a $T$-step plan is represented as a logical formula $\varphi _ T$. What is the idea behind planning wtih 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 (also allowed 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 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_T^\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 _ T^\text{initial}$ ensures that every ground atom occuring in the initial state is true,
  • $\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 _ T^\text{initial}$ (initial axioms): is a conjunction of
    • $F^0$ for each ground atom $F$ occuring in the initial state
    • $\lnot F^0$ for each ground atom $F$ not occuring in the initial state
  • $\varphi^\text{goal} _ T$ (goal axioms): is a conjunction of:
    • $F^T$ for each ground atom $F$ occuring 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 (also allowed 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\]

by

\[\varphi_T = \varphi_T^\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 _ T^\text{initial}$ ensures that every ground atom occuring in the initial state is true,
  • $\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

How many variables does this have?


\[T \times PA \times O^{R}\]

where:

  • $T$ is the max timestep
  • $PA$ is the number of predicates and actions
  • $O$ is the number of predicates and objects
  • $R$ is the maximal arity of a function term



Related posts