\documentclass{scrartcl}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[ngerman]{babel}
\usepackage{amsmath}

\input{macros}




\title{Decompositions in PANDA3}
\author{Gregor Behnke}
\date{\today}

\begin{document}
\maketitle



\section{Prerequesits}
Please read the Geiers and Berchers IJCAI 2011 paper.
We use the same formalism.

\subsection{Additional definitions}
\begin{definition}[TTG - Task transition Graph]
Let $\mathcal P$ be a planning problem.
Then the (directed) stask transition graph $G_{TTG} = (V,E)$ is defined by
\begin{align*}
    V &= C \cup O\\
    E &= \{(c_1,c_2) \mid c_1 \in C, (c_1,\tn) \in M, t \in T(\tn), \alpha(t(c_2))\}
\end{align*}
Further, the task transition relation $\ttr$ is the transitive hull of $E$.
\end{definition}


\section{Decomposition-Modifications for Open-Precondition Flaws}
We start by defining which proposition symbols are generated by applying a decomposition method to an abstract task.

In addition to their definition, we assume that $\Eff(c)$ contains the effects of a primitive task a list of literals, i.e.
\[\Eff(c) = \Add(c) \cup \{\neg p \mid p \in \Del(c)\}\]

\begin{definition}[Generated Proposition Symbols]
Let $c$ be a compound task and $m = (c,\tn)$ a matching method.
Then we define the set $\Gamma(c,m)$ of literals which can be generated from applying $m$ to $c$ by
\[
\Gamma(c,m) = \bigcup \{ \Add( \alpha(t)) \mid \tn(c) \decompose{\alpha(\tn)^{-1}(c)}{m} \tn_1 \leqd \tn_2, t \in T(\tn_2), \alpha(t) \in O\}
\]
The simple generation function $\Gamma(c)$, which ignores the decomposition method applied is defined by
\[
\Gamma(c) = \bigcup_{m=(c,\tn)\in M} \Gamma(c,m)
\]
\end{definition}


When trying to resolve an open-precondition flaw, decomposing an abstract task is clearly a viable modification, as it can produce new tasks containing the needed effect.
In order to keep the search-space as small as possible, only decompositions possibly leading to the needed literal should be considered.
However, contrary to standart POCL, applying this modification does not always solve the flaw, but only enables it to be solved later on.
E.g. imagine a situation in which two consecutive decompositions are necessary to obtain the task producing the required conidition.

We propose a technique to solve this problem (at least partially).
Instead of applying only a single decomposition, a set of decompositions could be applied s.t. the task generating the effect is obtained and a causal link can be added immediately.
Unfortuanetly, there are cases where this is not possible, as the set of all possible decompositions is not finite.

\begin{definition}[Directed Decomposition]
Let $\tn$ be a task network and $p$ be a proposition symbol.
Then the set $\Delta(\tn,p)$ of all task networks which can be obtained from $\tn$ by decomposing it directed to $p$ is defined by
\[\Delta(\tn,p) = \{\tn' \mid t \in T(\tn), m=(\alpha(t),\tn_p) \in M, p \in \Gamma(\alpha(t),m), \tn \decompose{\alpha(t)}{m} \tn' \}\]
Further we define $\Delta^*(\tn,p)$ as the set of all task networks which can be obtained by repated directed decomposition
\begin{align*}
\Delta^*(\tn,p) = \{\tn' \mid &\tn = \tn_1 \decompose{t_1}{m_1} \tn_2 \decompose{t_2}{m_2} \dots \decompose{t_{l-2}}{m_{l-2}} \tn_{l-1} \decompose{t_{l-1}}{m_{l-1}} \tn_l = \tn', \\
& \forall i \in [l-1]: \tn_{i+1} \in \Delta_p(\tn_i,p) \text{ and iff } i\neq 1: t_i \in T(\tn_i) \setminus T(\tn{i-1})\}
\end{align*}
\end{definition}

Next, we can define the set of all decompositions (i.e. task networks), which could be used, as they make the predicate $p$ true.
\begin{definition}[$p$-probiding task networks]
Let $c$ be a compound task and $p$ a proposition symbol.
Then the set $\Pi(c,p)$ of all directly decomposable task networks, which probide $p$ is defined as:
\[\Pi(c,p) = \{\tn \mid \tn \in \Delta^*(tn(c),p), t \in T(\tn), p \in \Add(\alpha(t))\}\]
\end{definition}

In theory we would like to regard every task network in $\Pi(c,p)$ as a possible decomposition of $c$ to obtain $p$.
As mentioned earlier this set might be infinetly large.
We used the TTD to ''prune'' these infinite parts of the set while keeping finite ones.

\begin{definition}[Non-recursive $p$-probiding task networks]
Let $\tn$ be a task network and $p$ be a proposition symbol.
We define the non-recursive restriction of $\Delta^*(\tn,p)$ as $\Delta_f^*(\tn,p)$ by
\begin{align*}
\Delta^*_f(\tn,p) = \{\tn' \mid &\tn = \tn_1 \decompose{t_1}{m_1} \tn_2 \decompose{t_2}{m_2} \dots \decompose{t_{l-2}}{m_{l-2}} \tn_{l-1} \decompose{t_{l-1}}{m_{l-1}} \tn_l = \tn', \\
& \forall i \in [l-1]: \tn_{i+1} \in \Delta_p(\tn_i), \text{ and iff } i\neq 1: t_i \in T(\tn_i) \setminus T(\tn_{i-1})\\
& \forall 1 \leq j < i: \alpha(\tn_i)(t_i) \neq \alpha(\tn_j)(t_j) \}
\end{align*}
Further, let $c$ be a compound task and $p$ a proposition symbol.
Then the set $\Pi_f(c,p)$ of all non-recursively directly decomposable task networks, which probide $p$ is defined as:
\[\Pi(c,p) = \{\tn \mid \tn \in \Delta_f^*(tn(c),p)\text{ with } t \in T(\tn), p \in \Add(\alpha(t)) \text { or } \not\exists \tn' \in \Delta_f^*(tn(c),p) : \tn \leqd \tn'\}\]

\end{definition}




\end{document}