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