# 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\]
.

- e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Milk})\}$

- e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Drill})\}$.

- 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)

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?

- e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Milk})\}$

- e.g. $\{\text{At}(\textit{Home}), \text{Have}(\textit{Drill})\}$.

- 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)

\[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