\documentclass[letterpaper]{article}
\usepackage{aaai}
\usepackage{times}	
\usepackage{helvet}
\usepackage{courier}

\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{epic,eepic,epsfig}


% 
% \begin{figure}[h!]
% \begin{center}
% \scalebox{0.9}{\epsfbox{weakIt.eps}}
% \end{center}
%   \caption{The search tree of an execution example of {\sc WeakGuided}. The numbers in the search
% nodes are the $h$-values of the states. Shaded nodes are covered by the plan.}
% \label{fig:weakEx} 
% \end{figure}
% 
% 
% \begin{figure}[h!]
%  \centering \input{exampleDomainC.eepic} \caption{The example problem with a heuristic 
% function estimating the sum of the horizontal and vertical distance to the initial state.}
% \label{fig:exampleDomC} 
% \end{figure}
% 



\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}

\def\({\langle}
\def\){\rangle}
\def\andd{\wedge}
\def\orr{\vee}
\def\True{{\it true}}
\def\False{{\it false}}
\def\Proof{\vspace{-3mm}\noindent{\em Proof}. }
\def\qed{\hfill$\Box$}
\def\endex{\hfill$\Diamond$}
\def\defeq{\equiv} 
\def\Cap{\, \cap \,}
\def\Cup{\, \cup \,}
\def\Minus{\, \setminus \,}
\def\Subeq{\, \subseteq \,}
\def\Supeq{\, \supseteq \,}
\def\Sub{\, \subset \,}
\def\Sup{\, \supset \,}
\def\Empty{\, \emptyset \,}
\def\Bar{\, : \,}
\def\Dot{\, . \,}
\def\DotDot{\, . \, . \,}
\def\Imp{\Rightarrow}
\def\BiImp{\Leftrightarrow}
\def\Max{{\it max}}
\def\Min{{\it min}}
\def\Idle{\mbox{idle}}
\def\Act{{\it Act}}
\def\States{\mbox{{\sc States}}}
\def\Statess{\mbox{{\sc States}}_s}
\def\Statese{\mbox{{\sc States}}_e}
\def\Actions{\mbox{{\sc Act}}}
\def\Closure{\mbox{{\sc Closure}}}
\def\Next{\mbox{{\sc Next}}}
\def\Nexts{\mbox{{\sc Next}}_s}
\def\Nexte{\mbox{{\sc Next}}_e}
\def\App{\mbox{{\sc App}}}
\def\SA{{\it SA}}
\def\EF{\mathtt{EF}\,}
\def\AGEF{\mathtt{AGEF}\,}
\def\AF{\mathtt{AF}\,}
\def\AG{\mathtt{AG}\,}
\def\D{\mathcal{D}}
\def\P{\mathcal{P}}
\def\S{\mathcal{S}}
\def\U{\mathcal{U}}
\def\M{\mathcal{M}}
\def\T{\mathcal{T}}
\def\nadl{\mbox{{\it N\hspace{-.57mm}A\hspace{-.3mm}D\hspace{-.4mm}L }}}
\def\nadlnospace{\mbox{{\it N\hspace{-.57mm}A\hspace{-.3mm}D\hspace{-.4mm}L}}}

\title{Encoding Temporally Extended Non-Deterministic Tasks for
Symbolic Fault Tolerant Planning in Multi-Agent Domains\thanks{This research is sponsored by
BBNT Solutions, LLC under contract no.  FA8760-04-C-0002 with the US
Air Force. The views and conclusions contained herein are those of the
authors and should not be interpreted as necessarily representing the
official policies or endorsements, either expressed or implied, of the
sponsoring institutions, the U.S. Government or any other entity.}}

\author{Rune M. Jensen \and Manuela M. Veloso \\
Computer Science Department, Carnegie Mellon University,\\
Pittsburgh, PA 15213-3891, USA}

\begin{document}
\maketitle

\section{Introduction}

Real-world planning is often considered a two dimensional challenge:
we need powerful planning algorithms to scale to the massive problems
frequently encountered in practice [ref pop,graph, satplan, ff], and
we need rich domain representations to capture the multifaceted nature
of real scenarios [prob,non-det,conditional, partial obs.]. There is,
however, also a third dimension which is to {\em integrate planning
and execution}. This problem has been addressed by execution languages
for autonomous agents like robots with limited world state knowledge
and short perceptual horizons [PSR, RAP, TCA]. The focus in this work
has been on reacting to unexpected events while overall acting
deliberatively. Another important aspect, however, is to use the
planning and execution cycle to {\em learn} domain knowledge and {\em
adapt} the planning domain to the execution environment. This is
relevant for autonomous agents, but seems particularly suitable for
application areas in logistics, manufacturing, and scheduling that
often are characterized by a large amount of domain knowledge that is
costly to maintain. Previous work in this direction is sparse, but
includes the prodigy project [ref] that focused on domain knowledge
learning and Haigh's work on the Xavier robot [ref].

The goal of our research is to investigate {\em domain model
adaptation} in a closed-loop planning and execution
framework. Compared to previous work we depart from classical  planning 
and consider learning in multi-agent planning domains with non-deterministic 
temporally extended actions.

In this paper, we lay the foundation for this work and introduce a
novel domain representation called Multi-agent Task Domains (MTDs). An
MTD is a multi-agent planning domain description. Like NADL [ref] it
defines a set system agents and environement agents. The environment
agents {\em explicitly} models uncontrollable activity in the domain,
i.e., actions of environment agents cannot be a part of the plan.

(etc.)

We formally define the MTD representation and its low-level unit time
transition graph semantics. This transition graph can be transformed
into a non-deterministic planning domain which allows us to define
solutions to MTD planning problems as strong, strong cyclic, and weak
plans. In addition it is possible to represent fault tolerant planning
domains. These plans can be efficiently generated by state-of-the-art
symbolic non-deterministic planning systems [mbp,umop,bifrost]. To
this end, we define a Boolean encoding of the low-level semantics of
MTDs and a transformation of this representation into a Boolean
encoding of the corresponding non-deterministic planning domain based
on iterative squaring [ref].  We further show how to use MTDs to [ref]
that can be solved with the strong planning algorithm



% reminder
In this paper, we introduce MTDs and show how to transform an
MTD into a non-deterministic planning domain [ref]. Via In particular, we
present a boolean encoding based on iterative squaring [ref] that can
be used to solve MTD planning problems efficiently with of-the-shelf symbolic
non-deterministic planning systems [ref bifrost, umop, mbp]. Finally,
we demonstrate how to encode and solve fault tolerant planning domains
for MTDs.




\section{MTD Description}

The two major design goals of the MTD representation are to facilitate
domain model adaptation and capture the main characteristics of the
domains we are interested in. With respect to the former, action
representations must be rich enough to accomodate fine tuning of the
domain model (e.g. in the later stages of a converging learning
process). Futher, the representation must be easy to access for humans
operators that may adjust models manualy. With respect to the latter,
the domains that we investigate have the following characteristics
\begin{enumerate}
\item Planning goals are temporally extended and activities
      are coordinated at explicit time points.

\item Most state information is metric and may represent shared ressources.

\item Actions are concurrent, durative and uncertain both with respect to their effects and temporal extend. 

\item The domains are dynamic with controllable as well as uncontrollable activity.

\item Domains are inherently multi-agent.
\end{enumerate}

An MTD description consists of a set of controllable system agents and
a set of uncontrollable environment agents.  


\begin{example} \upshape Alice and Bob are divers. Alice is 
initially at the reef bottom and must {\em surface} before
running out of oxygen. Bob is initially at the surface and can either
{\em wait} one minute at the surface or {\em dive} for two minutes to
escort Alice. Alice's surface swim is non-deterministic, both with respect to
time and amount of oxygen consumed. It may either take one or
two minutes. If it takes one minute, two gallons of oxygen is consumed. If it takes 
two minutes, two gallons of oxygen is consumed in the first minute and
either one or two gallons is consumed in the second minute.
Let ${\it ox}$ the mount of oxygen Alice has left. 
Figure~\ref{fig:diverSenario} shows the initial situation (a)
and the eight possible scenarios (b).  \endex
\label{ex:diverScenario}
\end{example}


\begin{figure}[h!]
\begin{center}
\scalebox{0.75}{\epsfbox{diverScenario.eps}}
\end{center}
  \caption{Initial situation (a), Eight possible scenarios (b).}
\label{fig:weakEx} 
\end{figure}








Figure~\ref{fig:diverScene}.

\begin{example}



\end{example}



\begin{definition}[MTM Description] 
An MTM description is a tuple $\M = \(C,V,E,T\)$, where
\end{definition}
\begin{tabular}{lp{7.5cm}}

$C$ & is a finite domain of a {\em global clock} $C = \{0,1,\ldots,c_{\Max}\}$, \\

$V$ & is a finite domain of $n^s > 0$ {\em system state variables} and $n^e \geq 0$ {\em environment state variables}  
      $V = V^s \times V^e$ where $V^x = \prod_{i=1}^{n^x} V^x_i$ for $x \in \{s,e\}$,\\

$E$ & is a finite {\em execution space} of $m^s > 0$ {\em system agents} and $m^e \geq 0$ {\em environment agents} each associated 
      with a set of execution states
      $E = E^s \times E^e$ where $E^x = \prod_{i=1}^{m^x} E^x_i$ for $x \in \{s,e\}$. Each set of execution
      states includes a special idle state $E^x_i \Supeq \{ \Idle \}$ for $x \in \{s,e\}$ and $i = 1 \DotDot m^x$, and \\
       
$T$ & is a finite {\em task space} of a non-empty set of tasks associated with each agent
      $T = \prod_{i=1}^{m^s} T^s_i \times \prod_{i=1}^{m^e} T^e_i$. Each task 
      $t \in T^x_k$ is a pair $\( M^x_t, R^x_t \)$, where \\

\end{tabular}

\begin{tabular}{clp{6.5cm}}

 & $M^x_t$ & is a set of indices of state variables modified by the task
             $M^x_t \Subeq \{1,\ldots,n^x\}$, and  \\ 

 & $R^x_t$ & is a set of guarded unit time execution transitions of the task defining
             how modified variables are changed while the task is active 
             $R^x_t \Subeq C \times V \times E \times T \times \prod_{i \in M^x_t} V^x_i \times E^x_k$. \\

\end{tabular}
\vspace{4mm}



Let $\mbox{NC} = \mbox{NC}^s \times \mbox{NC}^e$, where 
$\mbox{NC}^x = \{ \( t_1, \ldots, t_{m_x} \) \in T^x \Bar M^x_{t_i} \Cap M^x_{t_j} = \Empty \,\, \mbox{for} \,\, i \not= j \}$
for $x \in \{s,e\}$.  

\begin{definition}[MTM Transition Graph] A 
transition graph of an MTM description $\M = \(C,V,E,T\)$ is a unit time transition system  
$\T = \( S_{\T} , R_{\T} \)$, where
\end{definition}
\begin{tabular}{lp{7.5cm}}

$S_{\T}$ & is a finite set of states 
                    $S_{\T} = C \times V \times E \times NC$, and \\

$R_{\T}$ & is a transition relation 
                    $R_{\T} \Subeq S_{\T}^2$. \\

\end{tabular}
\vspace{4mm}

Let
\begin{eqnarray*}
 s  & = & \(c, v^s_{1..n^s}, v^e_{1..n^e},e^s_{1..m^s}, e^e_{1..m^e},t^s_{1..m^s}, t^e_{1..m^e} \)        \\
 s'  & = & \(c', v'^s_{1..n^s}, v'^e_{1..n^e},e'^s_{1..m^s}, e'^e_{1..m^e},t'^s_{1..m^s}, t'^e_{1..m^e} \)        \\
\end{eqnarray*}

$\(s,s'\) \in R_{\T}$ iff

\begin{itemize}

\item running tasks transition,
      \begin{eqnarray*}
      \( s,v'^x_{p(1)..p(n^x_{t'^x_i})},e'^x_i \) \in R^x_{t'^x_i} \,\, \mbox{for} \,\, x \in \{s,e\}, i = 1 \DotDot m^x, \,\, \mbox{and} \\
      M^x_{t'^x_i} = \{ p(1),\ldots,p(n^x_{t'^x_i})  \} \hspace{45mm} 
      \end{eqnarray*}

\item non-idle tasks continue,
      \begin{eqnarray*}
      (e^x_i \not= \Idle) \Imp (t'^x_i = t^x_i)  \,\, \mbox{for} \,\, x \in \{s,e\} \,\, \mbox{and} \,\,  i = 1 \DotDot m^x
      \end{eqnarray*}

\item unmodified variables maintain their value, and
      \begin{eqnarray*}
      v'^x_i = v^x_i \,\, \mbox{for} \,\, x \in \{s,e\} \,\, \mbox{and} \,\, i \in \{1,\ldots,m^x\} \Minus (\bigcup_{j = 1}^{m^x} M^x_{t'^x_i})
      \end{eqnarray*}
     

\item time advances.
      \begin{eqnarray*}
      c' = c + 1
      \end{eqnarray*}
 
\end{itemize}

Let $\T = \( S_{\T} , R_{\T} \)$ be an MTM transition graph of an MTM
description $\M = \(C,V,E,T\)$. The set of {\em decision} states $D_{\T}$ 
of $\T$ is the subset of states where some task is idle 
$D_{\T} = \{ \(\ldots,e^s_{1..m^s},\ldots\) \in S_{\T} \Bar e^s_i = \Idle$ for 
some $1 \leq i \leq m^s\}$. 

The set of {\em blocking} states $B_{\T}$ of $\T$ 
is the subset of states with no successor states 
$B_{\T} = \{ s \in S_{\T} \Bar \(s,s'\) \notin R_{\T}(s,s')$ for 
all $s' \in S_{\T} \}$.
  

For a set of states $S$ and a transition relation $R \Subeq S \times S$ a
{\em path} of {\em length} $k$ from $p$ to $q$ is a sequence of states
$s_0 s_1 \cdots s_k$ such that $(s_i,s_{i+1}) \in R$ for $i = 0
\DotDot k-1$ and $p = s_0$ and $q = s_k$.

\begin{definition}[MTM Decision Graph] Given an MTM 
description $\M = \(C,V,E,T\)$ and transition graph $\T = \( S_{\T} , R_{\T} \)$
of $\M$, an MTM decision graph is a non-deterministic planning 
domain $\mathcal{D} = \(S,A,R\)$, where
\end{definition}
\begin{tabular}{lp{7.5cm}}

$S$ & is the union of the decision and blocking states $S = D_{\T} \Cup B_{\T}$, \\

$A$ & is a finite set of actions $A = 2^{T^s}$, and \\
 
$R$ & is a transition relation $R \Subeq S \times A \times S$. \\

\end{tabular}
\vspace{4mm}

Let
\begin{eqnarray*}
 s  & = & \(\cdots,e^s_{1..m^s},\cdots \)        \\
 s'  & = & \(\cdots,t'^s_{1..m^s},\cdots \)        
\end{eqnarray*}

$\(s,a,s'\) \in R$ iff

\begin{itemize}

\item there exists a path $s_0 \cdots s_k$ in $R_{\T}$ between $s = s_0$ and $s' = s_k$ not visting 
      other states in $S$ ($s_i \notin S \,\, \mbox{for} \,\, i = 1,\ldots,k-1$), and  

\item the action $a$ is the set of system tasks started in $s$ ($a = \bigcup_{e^s_i = \Idle} \{t'^s_i\}$). 
 
\end{itemize}













\section{Non-Deterministic Planning}

A deterministic action can lead to at most one possible next state.  A
more general model is to assume that the outcome actions is uncertain 
such that actions may lead to one of several possible next states. 
 Non-determinism can model a wide range of dynamic systems
\cite{AMP94}. Common to all of them is that an active environment
interact with the actions. The environment can for instance cause
otherwise deterministic actions to fail, or it can control a subset of
the actions. In the latter case these uncontrollable actions may
either be interleaved or simultaneous with controllable actions. 
In both cases, it can be modeled by non-deterministic controllable 
actions.

\begin{definition}[Non-Deterministic Planning Domain]
A non-deterministic planning domain is a tuple 
$\(S, \Act,\rightarrow \)$ where $S$ is a 
finite set of states, $\Act$ is a finite set of actions, and 
$\rightarrow \, \subseteq S \times {\it Act} \times S$ 
is a non-deterministic transition relation of action effects.
Instead of $(s,a,s') \in \, \rightarrow$, we write
$s \stackrel{a}{\rightarrow} s'$.
\end{definition}
The set of next states of an action $a$ applied in state $s$
is given by
\begin{eqnarray}
\Next(s,a) & \defeq & \{ s' \Bar s \stackrel{a}{\rightarrow} s' \}.
\end{eqnarray}
An action $a$ is called {\em applicable} in state $s$ iff 
$\Next(s,a) \not= \emptyset$. The set of applicable 
actions in a state $s$ is given by  
\begin{eqnarray}
\App(s) & \defeq & \{ a \Bar \Next(s,a) \not= \emptyset \}.
\end{eqnarray}

\begin{definition}[Non-Deterministic Planning Problem] A non-deterministic 
planning problem is a tuple $\(\mathcal{D},s_0,G\)$ where $\mathcal{D}$ is a non-deterministic 
planning domain, $s_0$ is an initial state, and $G \Subeq S$ is a set of goal states.
\end{definition}

we define a non-deterministic plan
to be a set of {\em state-action pairs} defined below. 
\begin{definition}[State-action pair (SA)] 
Let $\D$ be a non-deterministic planning domain. A state-action pair 
$\(s,a\)$ of $\D$ is a state $s \in S$ associated with an applicable action 
$a \in \App(s)$.
\end{definition}
The set of SAs define a function from states to sets of actions relevant to 
apply in order to reach a goal state. This definition is identical to the state-action table 
definition used in \cite{CR98a,CR98b,DTV99,CPRT01} and is similar to universal plans
\cite{S87}, policies in reinforcement learning (e.g.,\cite{M97}), and strategies 
in concurrent reachability games \cite{DHK98}.
 
\begin{definition}[Non-Deterministic Plan] 
Let $\D$ be a non-deterministic planning domain. A non-deterministic plan for $\D$
is set of state-action pairs of $\D$.
\end{definition}
States are assumed to be fully observable. An execution of a non-deterministic 
plan is an alternation between observing the current state and choosing
an action to apply from the set of actions associated with the state. Similar to
policies in game theory, we call a non-deterministic plan {\em static} if there 
is at most a single action associated with each state. Otherwise, we call it {\em dynamic},
since an agent executing the plan may change its preference about which action to apply.

\noindent The set of states {\em covered} by a plan $\pi$ is
\begin{eqnarray} 
\States(\pi) & \defeq & \{  s \Bar \exists a \, . \, \( s,a \) \in \pi \}.
\end{eqnarray}
The set of actions in a plan $\pi$ associated with a state $s$ is
\begin{eqnarray} 
\Actions(\pi,s) & \defeq & \{  a \Bar \( s,a \) \in \pi \}.
\end{eqnarray}
The {\em closure} of a plan $\pi$ is the set of possible end states 
\begin{eqnarray} 
\Closure(\pi) & \defeq & \{ s' \not\in \States(\pi) \Bar \exists \(s,a\) \in \pi \, . \, s' \in \Next(s,a) \, \}.
\end{eqnarray}
A plan $\pi$ is said to be {\em total} iff $\Closure(\pi) \subseteq G$.

Notice that the definition of a non-deterministic plan does not give
any guarantees about goal achievement. The reason is that, in contrast
to deterministic plans, it is natural to define a range of 
solutions classes. There currently exists three classes of
non-deterministic plans called weak, strong cyclic, and strong
\cite{CR98a,CR98b}. Following \cite{DTV99,CPRT01}, we use CTL to
define these solutions. First, we need to define a Kripke structure to
represent the execution behavior of a plan.
\begin{definition}[Execution Model]
An execution model with respect to a non-deterministic plan $\pi$ for
the domain $\D = \(S,\Act,\rightarrow\)$ is a Kripke structure
$\M(\pi) = \(S,R\)$ where
\begin{itemize}
\item $S = \Closure(\pi) \Cup  \States(\pi) \Cup  G$,
\item $\(s,s'\) \in R$ iff $\,\,s \not\in G,\,\,\exists a \Dot \( s,a \) \in \pi$ and $s \stackrel{a}{\rightarrow} s'$, 
      or $s = s'$ and $s \in \Closure(\pi) \Cup  G$.
\end{itemize}
\end{definition}    

Notice that all execution paths are infinite which is required in
order to define solutions in CTL. If a state is reached that is not
covered by the plan (e.g., a goal state or a dead end), the postfix of
the execution path from this states is an infinite repetition of
it. Given a Kripke structure defining the execution of a plan,  weak, 
strong cyclic, and strong plans are defined by the CTL formulas below.
\begin{definition}[Weak, Strong Cyclic, and Strong Plans]
\label{def:weakStrongCStrong}
Given a non-deterministic planning problem $\P = \(\D,s_0,G \)$ and
a plan $\pi$ for $\D$
\begin{itemize}
\item $\pi$ is a weak solution iff $\M(\pi),s_0 \models \EF G$,
\item $\pi$ is a strong cyclic solution iff $\M(\pi),s_0 \models \AGEF G$,
\item $\pi$ is a strong solution iff $\M(\pi),s_0 \models \AF G$.
\end{itemize}
\end{definition}    
An execution of a strong plan is guaranteed to reach states covered by the
plan until a goal state after a finite number of steps is reached. An
execution of a strong cyclic plan is also guaranteed to reach states covered
by the plan or a goal state. However, due to cycles, it may never reach a goal 
state. An execution of a weak plan may reach states not covered by
the plan, it only guarantees that some execution exists that reaches
the goal from the initial state.


\bibliographystyle{aaai}
\bibliography{/usr0/home/runej/research/bibtex/all}
\end{document}
