\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 aspect which is mostly ignored,
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 important for application areas in logistics,
manufacturing, and scheduling that often are characterized by a large
amount of domain knowledge that is costly to maintain [ref to that configuration
paper]. Previous work in this direction is sparse. It 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. The
main difference between our approach and the previous work mentioned
above is that we depart from classical deterministic planning and
instead base our work on a novel planning domain representataion that
combines temporal and non-deterministic planning. This domain
representation is the focus of this paper.

The planning problems we are interested in can be illustrated by the
following scenario. A manager is in charge of a set of workers, but
also observes a set of demons that the manager is unable to
control. The manager sits behind a screen showing the current state of
the world and is connected to the workers by a telephone. Each demon
and worker is always in a state of activity executing some task. When
a worker finishes a task, the worker calls the manager. It is the
manager's responsibility to immidiately substitute the completed task
with a new task. The manager does this by taking a careful look at
the screen and observing the activities of both workers and
demons. Since the manager has a good idea about the nature of the
tasks of both demons and workers, the manager assumes that it only is
necessary to take action when the phone rings. 

We belive that the above scenario captures a wide range of 
real-world planning problems where some planning unit (the manager)
has gathered all the world information needed to plan (or at least
assumes it has done so) and relies heavily on models of the 
activities it must deal with to avoid getting overloaded by 
micro managing.

It may be claimed that the manager is facing a planning problem with
a natural representation in one of the current planning languages. To our best knowledge,
this is not the case. There are several difficulties.
\begin{enumerate}
\item The manager only has a ``good idea'' about how tasks may evolve. Exactly how they 
      evolve is uncertain leading non-determinism in both duration and
      effects. Further, there are uncontrollable activites carried out
      by demons.

\item At any time the phone rings, the manager takes a look at the screen 
      and observes the state of the world. No information is hidden by
      workers or demons even if they are in the process of changing
      this information.
\end{enumerate}
The first point requires a domain representation with durative
non-deterministic actions. However, temporal planning languages have
deterministic actions [ref ref] and non-deterministic planning
languages does not consider durative actions [ref ref]. The second
point address a general problem of argmenting first order logic with
time for temporal planning. This often leads to information ``holes''
[ref TLplan ref PDDl 2.2] due to concurrent actions hidding state information.
Such models may be efficient for planning but may be hard to maintain if we require
complete state information at any time point.

It may also be claimed that the manager has misunderstood the
situation and should decompose the tasks into start and stop event
actions. This, however, interfer with the model of control.  The
manager is not able to stop tasks. Tasks are uninteruptable macros.

To model these domains, we have developed an action representation
called Evolving Tasks (ETs). ETs are guarded acyclic directed graphs where
each vertex is an execution state of the task, and each edge is a unit
time transition between execution states. The edges are guarded, and
if several edges are enabled, one of these is non-deterministically
chosen to transition. The ET representation is general enough to model
non-determinism both in terms of the duration of the task and its
effect. They further define the value of the state variables they
effect at every time point. This solves problem mentioned in point two
above, since it allows the value of each state variable to be
determined at any time point. We consider multi-agent planning domains
where each agent is defined by a set of ETs, it can apply. We call
these Multi-agent Auto Task Domains (METDs). Like NADL [ref], METDs
explicitly model the evironment as a set of uncontrollable agents (the
demons).

In this paper, we formally define the METD representation and its
low-level unit time transition graph semantics. This transition graph
can be transformed into a non-deterministic planning domain [ref]
which allows us to define solutions to METD planning problems as
strong, strong cyclic, and weak plans. 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 METDs and a transformation of this
representation into a Boolean encoding of the corresponding
non-deterministic planning domain based on iterative squaring [ref].
A major motivation for transforming METDs into non-deterministic
planning domains is to generate fault tolerant plans for METD problems
[ref]. Fault tolerant planning is an alternative approach to
probabilistic planning where a plan with high probability of success
is expressed as a plan with high level of tolerance for failures
occuring during execution. This notion of fault tolerance is
well-known from engineering and control theory [ref], and in contrast
to probabilistic plans, fault tolerant plans bypass a complex
manipulation of transition probabilities. We show how fault tolerant
planning can be naturally expressed in METDs.

The reminder of the paper is organized as follows. In Section \ref{sec:matd},
we introduce METDs and their low-level unit time semantics. We then, in section
\ref{sec:non}, briefly define non-determinstic planning domains and show how 
to transform the unit time sematics of METD to a non-deterministic
planning domain.  The Boolean encoding of these domains is given in Section
\ref{sec:bool}. Finally, we conclude and discuss our plans for future
work in Section~\ref{sec:con}.



\section{METD Descriptions}
\label{sec:matd}
The two major design goals of the METD 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 MATD description consists of a {\em global clock} with a finite
domain of discrete integer time points, a disjoint set of system and
environment {\em state variables} with finite domains, and a
description of {\it system} and {\it environment agents}.

The state variables can be {\em metric} with integer domains, {\em
Boolean}, or {\em enumerations} with finite domains. The usual
arithmetic and relational operations can be carried out on metric
variables. The set of state variable assignments defines the state
space of the world.

An agent's description is a set of {\it tasks}. The agents change the
state of the world by executing tasks. Each agent is always in a state
of activity executing some task. The agents are asynchronous, they may
start and stop tasks at different time-points. The system agents
model the behavior of the agents controllable by the planner, while
the environment agents model the uncontrollable world. To ensure
independence of the system and environment agents, they affect a
disjoint set of state variables. Their tasks, however, may depend on
the complete state of the world.

A task has two parts: a set of {\it state variables} that the task
modifies and a set of {\it unit time transitions} that defines how the
task evolves. The task is responsible of assigning new values to the
variables it modifies. It further has exclusive access to these
variables, no other concurrent task can modify these variables as long
as it is active. Each agent is associated with a finite set of
execution states. These states are shared between the tasks of the
agent and defines the transition states of the tasks. Each set of
execution states has a special {\em idle state}. The outgoing
transitions from the idle state are taken when a task starts, the
incomming transitions to the idle state are taken when the task
stops. The remaining transitions form a directed acyclic graph on the
execution states causing all execution paths of the task to be
finite. Each transition is {\em guarded}. The guard is an expression
on the complete state. This may include the current task and execution
state of any agent as well as the current value of any state variable.
This allows rich behavior models including strong synchronization
schemes with other tasks. The effect of the transition is given as an
expression on the state variables it modifies and its execution
state. If the this expression holds for several assignments, one of
these is non-deterministically chosen. In this way, tasks are
non-deterministic both with repsect to duration and effect on modified
variables. Notice that there is no need for an explicit
precondition. The precondition of a task is the disjuntion of the
guards of outgoing transitions from the idle state.

Time advances in discrete integer time points. In each unit time step
the task of each agent performs a unit time transition. This {unit
time transition graph} will {\em block} if no transition is enabled
(its guard expression holds) for some task. An METD, however, cannot
be controlled at the unit time transition level. Control decisions can
only be made in states, where some task has terminated. In these
states, a new task must be chosen for each idle agent.
 
\begin{example} \upshape Chris and Kim are cave divers. Chris is 
initially at the cave bottom and must {\em surface} before running out
of oxygen. Kim is initially at the surface and can either {\em wait}
one minute at the surface or {\em dive} for two minutes to escort
Chris. Chris'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 Chris has
left. Figure~\ref{fig:diverSenario} shows the initial situation (a)
and the eight possible ways the world can evolve
(b). Figure~\ref{fig:diverMETD} shows the METD decription of the
problem. Chris and Kim are assumed to be controllable system agents.
the idle state is marked \texttt{I}. Notice how we can choose different
formats of the task descriptions to emphasize their meaning. As
mentioned in the introduction, this is important since ATs must be
easy to grasp and alter for human operators participating in the model
adaptation process. For Chris' surface task, we choose to show the
relation between time and oxygen consumption, while automata models
are more appropriate for the simple wait and dive tasks of Kim.
Figure~\ref{fig:diverUnit} shows the unit time transition graph of
the domain. The initial state and goal conditions is not a part of a
METD description, but we assume that ${\it ox} = 3$ in the initial
state and the goal is to reach a state where Chris reaches the surface
before running out of oxygen (${\it clock \geq 1 \wedge {\it ox} \geq
0}$). There are boxes around the goal states in the figure. There is,
however, no plan that guarantees goal achievement. Chris can only
surface, but no matter how Kim chooses to wait or dive, there is a
possibility of the goal not being achieved.
\label{ex:diverScenario}
\end{example}


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


\begin{figure}[h!]
\begin{center}
\scalebox{0.75}{\epsfbox{diverMETD.eps}}
\end{center}
  \caption{METD description of the diver example.}
\label{fig:diverMETD} 
\end{figure}





\begin{figure}[h!]
\begin{center}
\scalebox{0.75}{\epsfbox{diverUnit.eps}}
\end{center}
  \caption{Unit time transition graph of the diver example .}
\label{fig:diverUnit} 
\end{figure}


Compared to the durative action descriptions of PDDL2.1, TLplan, and
IxTET [cite], the most significant difference to METD is that tasks
are durative {\em and} non-deterministic.  None of the above domain
descriptions consider non-deterministic actions. Actually, we are not
aware of other planning domain description with temporally extended
and durative actions. Another important difference between METD and
the domaoin descriptions above is the use of state variables. This
provides metric values, but so has PDDL2.1. What is probably more
important is that our state variables maintain the characteristics of
state variables in physics and control theory [cite control book] by
being defined for every time point. When argmenting first order logic
with time, but other wise essentially keep the precondition and effect
notions from classical planning, there is no guarantee of the state of
information being known at each time point, as this information may
have been deleted at action start only to appear when the action
terminates. An important exception from this, however, are the
continous durative actions of PDDL2.1. For these actions, update functions are provided 
to define the change of metric information. This approach, however, is not as
general as TAs. 

Another challenge for durative actions in the classical
precondition-effect format is the how to handle conditional
effects. The problem is that conditional effects require information
to be transfered from the state the action is being applied to the
state the action is being terminated, but that these states may not be
adjacent in the planning domain. this can be solved implicitly by
introducing memory propositions [pddl 2.1] or immidiate effects of the
action [TLplan]. For TAs the problem is solved explicitly, since
conditional effects can be defined for each unit time transition as
shown in the diver example.

When transforming an METD to it corresponding non-deterministic planning 
domain this information is compiled away. Thus, METD intsoduces a bottom-up approach to durative actions 
as opossed to the usual top-down apprach.

An important issue to address when introducing concurrent tasks is
synergetic effects between simultaneously executing tasks
[LR98]. A common example of destructive synergetic effects
is when two or more tasks require exclusive use of a single resource
or when two tasks have inconsistent effects like ${\it pos}' = 3$
and ${\it pos}' = 2$.  

Like actions in NADL, METD methods cannot be performed concurrently in
the following two conditions: 1) they have inconsistent effects, or 2)
they constrain an overlapping set of state variables.  The first
condition is due to the fact that state knowledge is expressed in a
monotonic logic that cannot represent inconsistent knowledge. The
second condition addresses the problem of sharing resources. Consider
for example two agents trying to drink the same glass of water.  If
only the first condition defined interfering actions, both agents
could simultaneously empty the glass, as the effect ${\it
glass\_empty}$ of the two tasks would be consistent. With the second
condition added, these tasks are interfering and cannot be performed
concurrently. 

We have chosen this ressource conflict resolution, since our
experiences with this technique in NADL have been overly
positive. There are, however, several issues to address. First, we
need to show how to encode synergetic activity strong enough to solve
Gelfond's soup problem [gelfond 91, see FOX].  The problem is to lift
a soup bowl without spilling the soup. Two actions, lift left and lift
right, can be applied to the bowl.  If either is applied on its own
the soup will spill, but if they are applied simultaneously then the
bowl is raised from the table and no soup spills. The problem is that
we cannot model the state of the soup bowl in METD or NADL using just
one state variable, since two concurrent lift tasks then would be
unable to access that state variable. we can, however, represent such synergetic 
activity be letting the state of the bowl being expressed by several state variables. 
If we introduce two Boolean variables ${\it force\_left}$ and ${\it force_right}$ 
the different states of the bowl can be represented: 
\begin{eqnarray}
{\it stateBowl}({\it force\_left}$,{\it force_right}) = {\it force\_left} \,\, \mbox{XOR} \,\, {\it force_right}$


gelfond



second resolution of shared ressources


Our experience with NADL has shown that this approach to
ressource race resolution METD resolves ressource races    
   






















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.




% related work: remember to talk about that METDs do not allow zero time tasks



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