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

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

\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{ASET: Representing Indeterminate Durative 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,\hspace{1mm} Manuela M. Veloso, \and Sergey Shchukin \\
Computer Science Department, Carnegie Mellon University,\\
Pittsburgh, PA 15213-3891, USA}




\begin{document}
\maketitle

\begin{abstract}
In this paper, we introduce a novel planning domain representation
called ASynchronous Evolving Tasks (ASET). The main contribution of
ASET is a representation of temporally extended tasks that may be
non-deterministic both with respect to duration and effects. Like
NADL, ASET represents metric domain knowledge as state variables and
explicitly models the environment as a set of uncontrollable agents.
We formally define ASET descriptions and their transformation to a
non-deterministic planning domain. Using a Boolean encoding of this
transformation, ASET planning problems can be solved efficiently using
state-of-the-art symbolic non-deterministic planning systems. In
particular, we show how to augment an ASET description to generate fault tolerant
plans via the strong planning algorithm.
\end{abstract}

\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, and we need rich domain
representations to capture the multifaceted nature of real
scenarios. There is also, however, 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 \cite{GL86,FIR89,RS94}. 
The focus in this work has been on reacting to unexpected events
while overall acting deliberatively. Another aspect 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 \cite{DR98}. Previous work in
this direction is sparse, but includes the prodigy project \cite{WA94,YG92} and 
Haigh's work on the Xavier robot \cite{HV98}.

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 representation that
combines temporal and non-deterministic planning. This domain
representation is the focus of the present 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 customers 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
customer 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 then the manager's responsibility to give the worker a new task. The
manager does this by taking a careful look at the screen and observing
the activities of both workers and customers. Since the manager has a
good idea about the nature of the tasks of both customers and workers,
the manager assumes that it only is necessary to take action when the
phone rings.

We believe that this scenario captures a wide range of real-world planning
problems where some planning unit (the manager) has gathered all world
information necessary to plan successfully (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 and leads to non-determinism both with respect to duration and
      effects. Further, there are uncontrollable activities carried out
      by customers.

\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 customers 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 e.g. \cite{FL03,BA01,LGH98} and
non-deterministic planning languages do not consider durative actions
e.g. \cite{PBCGGRS02,GK97,JV00A}. The second point addresses a general
problem of augmenting first order logic with time for temporal
planning. This often leads to information ``holes'' \cite{BA01,FL03}
caused by concurrent actions hiding the state of domain knowledge they
are currently changing.

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, conflicts with the model of control.  The
manager is not able to stop tasks in the middle of their
execution. A task is uninteruptable.

To model these domains, we have developed an action representation
called Evolving Tasks (ETs). ETs are, as far as we know, the first
action representation that can represent temporally extended
activities which are non-deterministic both with respect to duration
and effect. ETs are represented by unit time transition systems. They
further define the value of the state variables they effect at every
time point. This solves the problem mentioned under point two
above. The explicit representation of time and intermediate states of
ETs also address another requirement to our task representation: it
must be easy to access for humans participating in the model
adaptation process. To this end ETs can be represented visually as
graphs.

We consider multi-agent planning domains where each agent is defined
by a set of ETs, it can apply. We call these Asynchronous Evolving Tasks
(ASET). Like NADL \cite{JV00A}, ASET explicitly model the
environment as a set of uncontrollable agents (the customers).

In this paper, we formally define an ASET description and its
low-level semantics ({\em unit time transition graph}) and high-level
semantics ({\em decision graph}). The decision graph is a
non-deterministic planning domain which allows us to define solutions
to ASET planning problems as strong, strong cyclic, and weak plans
\cite{CPRT01}. These plans can be efficiently generated by
state-of-the-art symbolic non-deterministic planning systems
\cite{CPRT01,JVB03A}. To this end, we define a Boolean encoding of the
unit time transition graph and a transformation of this representation
into a Boolean encoding of the decision graph based on iterative
squaring \ref{BCM90}.

A major motivation for transforming an ASET description into a
non-deterministic planning domain is to generate fault tolerant plans
for ASET planning problems \cite{JVB04A}. 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 occurring during execution. This notion of fault
tolerance is well-known from engineering and control theory and
in contrast to probabilistic plans, fault tolerant plans bypass a
complex manipulation of transition probabilities. We show how to
augment an ASET description to obtain a fault tolerant planning domain
such that fault tolerant plans can be generated via the strong
planning algorithm.

The remainder of the paper is organized as follows. We first define
ASET descriptions and discuss how they relate to other planning domain
representations. We then present the unit time decision graph of an
ASET description and its Boolean encoding and show how to transform
the unit time transition graph into a decision graph which is a
non-deterministic planning domain. The following section briefly
reminds about the definition of strong non-deterministic plans and
shows how to represent fault tolerant planning domains in
ASET. Finally, we conclude and discuss plans for future work.


\section{ASET Descriptions} 
An ASET 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 finite 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. Intuitively, the task is responsible of assigning new
values to the variables it modifies. It further has exclusive access
to the modified 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 define the transition states of the tasks. Each
set of execution states has a special {\em idle state}. A task is a transition system where each 
transition has unit time duration. The outgoing
transitions from the idle state are taken when a task starts. The
incoming transitions to the idle state are taken when the task
stops. The remaining transitions of a task 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. The transition is only enabled if the guard expression
is satisfied.  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 this expression holds for several assignments,
one of these is non-deterministically chosen as the effect of the
transition. In this way, tasks are non-deterministic both with respect to
duration and effect on modified variables. Notice that there is no
need for an explicit precondition. The precondition of a task is the
disjunction of the guards of outgoing transitions from the idle state.

Time advances in discrete integer time points. In each unit time step,
the currently active tasks performs a unit time transition. Variables not
modified by any task maintain their value. The resulting {unit
time transition graph} will {\em block} if no transition is enabled
for some task. 
 
\begin{example} \upshape Chris and Kim are cave divers. Chris is 
initially at the cave bottom at a depth of 20 yards with three units
of oxygen 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. The cave has a
difficult passage at a depth of 10 yards. Chris' surface swim is
non-deterministic, both with respect to time and amount of oxygen
consumed. It may either take one or two minutes. If no problems are
encountered, it takes one minute and two gallons of oxygen is
consumed. Otherwise, it takes two minutes, and two gallons of oxygen
is consumed in the first minute and either one or two gallons is
consumed in the second minute. The Initial situation is shown in  
Figure~\ref{fig:diverSenario}(a).

\begin{figure}[h!]
\begin{center}
\scalebox{0.90}{\epsfbox{diverScenario.eps}}
\end{center}
  \caption{Initial situation (a) and ASET description (b) of the diver domain.}
\label{fig:diverSenario} 
\end{figure}

An ASET description of this scenario is shown in
Figure~\ref{fig:diverSenario}(b). The domain of the clock is
$\{0,\ldots,2\}$ and there is a single state variable ${\it ox }$ with
domain $\{-1,0,\ldots,3\}$ representing the amount of oxygen Chris has
left. To simplify the presentation, we do not include state variables
representing the position of Chris and Kim, but it is straight forward
to extend the example to include these. Chris and Kim are assumed to
be controllable system agents. The execution states associated with
Chris and Kim are $\{I,p\}$ and $\{I,q\}$, respectively. The idle
state is marked \texttt{I}. The guard and effect expression of a
transition is written above and below the transition arrow,
respectively. To represent conditional effects, primed variables refer
to the current state of the transition while unprimed variables refer
to the next state. As for the surface task, it may be helpful to use
several copies of the idle state, but each of these copies represents
the same idle state.

Notice that different formats of the task descriptions are used to
emphasize their meaning. For Chris' surface task, we choose to show
the relation between traveled distance and oxygen consumption, while
automata models are more appropriate for Kim's simple wait and dive
tasks. 

Figure~\ref{fig:timePlot} shows the eight different ways the scenario
can evolve from the initial state. It can be seen, however, that no
matter how tasks are chosen for Chris and Kim, it cannot be guaranteed
that Chris has oxygen left when reaching the surface. In non-deterministic planning
terms, we say that there is no {\em strong} plan for reaching the
goal. This will be clarified in the following sections. \endex
\label{ex:diverScenario}
\end{example}

\begin{figure}[h!]
\begin{center}
\scalebox{0.90}{\epsfbox{timePlot.eps}}
\end{center}
  \caption{Eight possible evolutions of the diver scenario.}
\label{fig:timePlot} 
\end{figure}

\noindent
Formally, a ASET description is defined as follows. 
\begin{definition}[ASET Description] 
An ASET 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$ {\em system state variables} and $n^e$ {\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}

Compared with the durative action descriptions of PDDL2.1, TLplan, and
IxTeT \cite{FL03,BA01,LGH98}, the most significant difference of ASET
descriptions 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 any planning
language with temporally extended and non-deterministic
actions. Another important difference between ASET and the domain
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 are defined at every time point like state
variables in physics and control theory \cite{CL299}. When augmenting
first order logic with time and preserving the precondition and effect
notions from classical planning, domain knowledge may only exist at
certain time points. An important exception from this, however, are
the continuous 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 ETs.

Another challenge for durative actions in the classical
precondition-effect format is how to handle conditional
effects. The problem is that conditional effects require information
to be transfered from the state the action is being applied in, to the
state the action is completed in. These states, however, may not be
adjacent in the planning domain. The problem can be solved by
introducing memory propositions \cite{FL03} or instantaneous effects of
actions \cite{BA01}. For ETs the problem is solved explicitly, since
conditional effects can be defined for each unit time transition as
shown in the diver example.

An important issue to address when introducing concurrent tasks is
synergetic effects between simultaneously executing tasks
\cite{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, ASET tasks cannot be performed concurrently in
the following two conditions: 1) they have inconsistent effects, or 2)
they modify 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 tasks, 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 definition of task interference due to our
positive experience with it in NADL. 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 \cite{GLR91}.  
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 ASET 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 by
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 by
\begin{eqnarray*}
{\it onGround} & = & \neg{\it force\_left} \andd \ \neg{\it force_right}, \\
{\it spill} & = &    {\it force\_left} \,\, \mbox{\tiny XOR} \,\, {\it force_right}, \\
{\it lift} & = & {\it force\_left} \andd \ {\it force_right}. \\
\end{eqnarray*}

Second, we need to address how to handle state variables that
represent shared resources.  In \cite{BA01} an example of a gas station
with 6 refueling bays is given. If this resource is represented by a
single state variable in ASET, we once more face the problem of at
most one task accessing the resource. Again, we can solve the problem
by using several state variables (e.g., a Boolean variable for each
refueling bay).


\section{ASET Unit Time Transition Graphs}
\label{sec:uttg}
In order to transform an ASET description into a non-deterministic
planning domain, we first compute its {\em unit time transition
graph}. The unit time transition graph is a transition system that
represents the combined effect of active tasks. As the name suggests,
each transition in the unit time transition graph advances the clock 
one time unit. There is, however, not necessarily a planning decision
associated with each transition. It is only when one or more tasks of
controllable system agents terminate that there is a choice of the
planner of which new tasks to start. We call such states 
{\em decision states}.

\begin{example} \upshape Consider again the diver domain described in
Example~\ref{ex:diverScenario}. The initial state and goal states is
not a part of a ASET 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. Figure~\ref{fig:diverUnit}
shows the part of the unit time transition graph that can be reached
from the initial state. Each state is represented by a triple and a
pair $({\it ox},e_{{\it Chris}},t_{{\it Chris}})$ and $(e_{{\it
Kim}},t_{{\it Kim}})$, where ${{\it ox}}$ is the value of the ${{\it
ox}}$ state variable, and $e$ and $t$ are the execution state and
current task of Chris and Kim. In the initial state, we choose {\em
surface} and {\em wait} as dummy idle tasks. There are boxes around
the goal states (i.e. states where Chris has surfaced successfully). 
Each of these are decision states. Additional
decision states are marked by ellipses. Each path in the graph
corresponds to one of the eight scenarios shown in
Figure~\ref{fig:timePlot}. \endex
\label{ex:diverUnit}
\end{example}

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


For an ASET description $\M = \(C,V,E,T\)$, let $\mbox{NC}$ denote
non-conflicting tasks of system and environment agents.  We have,
$\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 \}$. We can now define
the unit time transition graph of an ASET description as follows.

\begin{definition}[Unit Time Transition Graph] A unit time
transition graph of an ASET description $\M = \(C,V,E,T\)$ is a transition system  
$\T = \( S_{\T} , R_{\T} \)$, where
\label{def:unittime}
\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} \times S_{\T}$. \\

\end{tabular}
\vspace{4mm}

\noindent
For
\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*}

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

\vspace{3mm}
\begin{enumerate}

\item Running tasks transition,
      $$
      \( 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,
      $$
      where  $M^x_t = \{ p(1),\ldots,p(n^x_t)  \}$.
      

\item Non-idle tasks continue,
      $$
      (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.
      $$

\item Unmodified variables maintain their value, and
      $$
      v'^x_i = v^x_i \,\, \mbox{for} \,\, x \in \{s,e\} \,\, \mbox{and} \,\, i \in \{1,\ldots,m^x\} \Minus M, 
      $$
      where $M = \bigcup_{j = 1}^{m^x} M^x_{t'^x_j}$.

\item Time advances.
      $$	
      c' = c + 1.
      $$
 
\end{enumerate}


In order to use symbolic non-deterministic planners to solve ASET
planning problems, we need a Boolean encoding of unit time transition
graphs. This is achieved by defining the {\em characteristic} function
of the set of state pairs in $R_{\T}$ of the unit time transition
graph. Let $\vec{s}$ and $\vec{s}'$ be two vectors of Boolean
variables representing the current and next state of a unit time
transition graph, where
\begin{eqnarray*}
 \vec{s}   & = & \(\vec{c}, \vec{v}^s_{1..n^s}, \vec{v}^e_{1..n^e}, \vec{e}^s_{1..m^s}, \vec{e}^e_{1..m^e}, \vec{t}^s_{1..m^s}, \vec{t}^e_{1..m^e} \),         \\
 \vec{s}'  & = & \(\vec{c}',\vec{v}'^s_{1..n^s}, \vec{v}'^e_{1..n^e}, \vec{e}'^s_{1..m^s}, \vec{e}'^e_{1..m^e}, \vec{t}'^s_{1..m^s}, \vec{t}'^e_{1..m^e} \).        
\end{eqnarray*}
Our goal is to define a Boolean
function $R_{\T}(\vec{s},\vec{s}')$ that is true iff the variables of
$\vec{s}$ and $\vec{s}'$ are assigned values corresponding to a
transition in $R_{\T}$. For an ASET description $\M = \(C,V,E,T\)$, let
$r_i$ represent requirement $i$ of Definition~\ref{def:unittime}
\begin{eqnarray*}
r_1^x &  = & \bigwedge_{i=1}^{m^x} \bigwedge_{t \in T_i^x} \Big[ (\vec{t}'^x_i = t) \Imp R^x_t(\vec{s},\vec{v}'^x_{p(1)..p(n^x_t)},\vec{e}'^x_i) \Big],\\
r_2^x &  = & \bigwedge_{i=1}^{m^x} \Big[ (\vec{e}^x_i \not= \Idle) \Imp (\vec{t}'^x_i = \vec{t}^x_i) \Big],\\
r_3^x &  = & \bigwedge_{i=1}^{n^x} \big[ (\bigwedge_{j=1}^{m^x} \bigwedge_{t \in T^x_j(i)} \vec{t}'^x_j \not= t) \Imp (\vec{v}'^x_i = \vec{v}^x_i) \big], \\
r_4   &  = & \vec{t}' = \vec{t} + 1, \\
\end{eqnarray*}
where $M^x_t = \{ p(1),\ldots,p(n^x_t) \}$,
$R^x_t(\vec{s},\vec{v}'^x_{p(1)..p(n^x_t)},\vec{e}'^x_i)$ is the
characteristic function of the set of tuples in $R^x_t$, and $T^x_j(i) = \{ t \in T^x_j \Bar i \in M^x_t \}$.\\

\noindent
Further, let ${\it NC}$denote the non-conflicting tasks
$$
{\it NC}^x = \bigwedge_{\begin{array}{c} i \in D_1  \\ j \in D_2 \end{array}} 
             \bigwedge_{\begin{array}{c} t_1 \in T^x_i \\ t_2 \in T^x_j \end{array}} 
             \Big[ \begin{array}{l}  D^x_{t_1} \cap D^x_{t_2} = \Empty \Imp \\ \vspace{2mm} \neg (\vec{t}^x_i = t_1 \wedge \vec{t}^x_j = t_2) \end{array} \Big].  
$$
where $D_1 = \{1,\ldots,m^x\}$ and $D_2 = \{1,\ldots,m^x\} \Minus \{i\}$.\\

\noindent
We then have
$$
R_{\T}(\vec{s},\vec{s}') = r_4 \wedge \bigwedge_{x \in \{s,e\}} r^x_1 \wedge r^x_2 \wedge r^x_3 \wedge {\it NC}^x.
$$


\section{ASET Decision Graphs}
\label{sec:dg}
We now consider how to transform the unit time transition graph of a
ASET description into a non-deterministic planning domain that we can
solve efficiently with a state-of-the-art symbolic non-deterministic
planning system. The non-deterministic planning
domains used by these systems are a generalization of classical
deterministic planning domains where the effect of an action applied
in some state is modeled by a non-deterministic choice from a
set of possible next states. 

\begin{definition}[Non-Deterministic Planning Domain]
A non-deterministic planning domain is a tuple 
$\(S, A, R \)$ where $S$ is a 
finite set of states, $A$ is a finite set of actions, and 
$R \subseteq S \times A \times S$ 
is a non-deterministic transition relation of action effects.
\end{definition}

A unit time transition graph is transformed into a non-deterministic
planning domain by removing states where no planning decision can be
made. As mentioned in previous section, a planning decision can be
made in states where the task of one or more controllable agents is
idle. Let $D_{\T}$ denote these {\em decision states} of a unit time
transition graph $\T = \( S_{\T} , R_{\T} \)$. We have $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 non-deterministic planning domain of an ASET description, however,
also needs to include {\em blocking states} where some task is unable
to transition. Without including these states we may get an incorrect
model that hides the fact that some decision may lead to a dead end
(e.g., causing two tasks to ``wait'' on each other).  Let $B_{\T}$
denote the blocking states of a unit time transition graph $\T = \(
S_{\T} , R_{\T} \)$. We have $B_{\T} = \{ s \in S_{\T}
\Bar \(s,s'\) \notin R_{\T}$ for all $s' \in S_{\T} \}$.
  
The non-deterministic planing domain associated with an ASET
description is called a {\em decision graph}. Each transition in the
decision graph corresponds to a path between decision states and
blocking states in the unit time transition graph. For a set of states
$Q$ and a transition relation $U \Subeq Q \times Q$ a {\em path} of
{\em length} $k$ from $v$ to $w$ is a sequence of states $q_0 q_1
\cdots q_k$ such that $(q_i,q_{i+1}) \in U$ for $i = 0,\ldots,k-1$ and
$v = s_0$ and $w = s_k$. We can now define the decision graph as
follows.

\begin{definition}[ASET Decision Graph] Given an ASET 
description $\M = \(C,V,E,T\)$ and a unit time transition graph $\T =
\( S_{\T} , R_{\T} \)$ of $\M$, an ASET decision graph of $\M$ 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}

\noindent
For
\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*}

\noindent
We have $\(s,a,s'\) \in R$ iff

\vspace{3mm}
\begin{itemize}

\item there exists a path $s_0 \cdots s_k$ in $R_{\T}$ between $s = s_0$ and $s' = s_k$ not visiting 
      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}

If $\(s,a,s'\)$ is a transition in a decision graph, the current state
$s$ is a decision state and the next state $s'$ is the first decision
state or blocking state reached by some path from $s$ when
starting the tasks defined by $a$ in the current state $s$.


\begin{example} \upshape Figure~\ref{fig:diverDec} shows the decision graph of the unit time
transition graph of the diver domain shown in
Figure~\ref{fig:diverUnit}. Again, we only consider the subset of
transitions reachable from the initial state. The decision graph has
only one state less than the unit time transition graph. The reason is
that the diver example for sake of presentation only has tasks with short
duration.  For more realistic domains, where most tasks will have
longer duration, a much larger fraction of states will be abstracted
away. 

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{diverDec.eps}}
\end{center}
  \caption{Decision graph of the diver domain.}
\label{fig:diverDec} 
\end{figure}


The diver domain does not have any blocking states. We can introduce
one by changing the {\em surface} task to the one depicted in
Figure~\ref{fig:blockSurface}. The difference is that the two top
right transitions are guarded by Kim executing the {\em dive} task and
being in execution state $q$. This results in a blocking state if Kim
decides to {\em wait}. Figure~\ref{fig:diverBlockUnit} shows the unit
time transition graph of the domain. the blocking state is indicated
by a sharp edged box. Figure~\ref{fig:diverBlockDec} shows the
corresponding decision graph. \endex
\end{example}


\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{blockSurface.eps}}
\end{center}
  \caption{The blocking {\em surface} task.}
\label{fig:blockSurface} 
\end{figure}

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{diverBlockUnit.eps}}
\end{center}
  \caption{The unit time transition graph of the diver example with the {\em surface}
           task shown in Figure~\ref{fig:blockSurface}.}
\label{fig:diverBlockUnit} 
\end{figure}

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{diverBlockDec.eps}}
\end{center}
  \caption{The decision graph of the unit time transition 
           graph shown in Figure~\ref{fig:diverBlockUnit}.}
\label{fig:diverBlockDec} 
\end{figure}

It is not obvious how to compute the decision graph, since it is
defined in terms of paths in the unit time transition graph. For
symbolic non-deterministic planning, on the other hand, the decision
graph can be efficiently computed using {\em iterative squaring}
\cite{BCM90}.

\noindent
Let 
\begin{eqnarray*}
B(\vec{s}) & = & \neg \big[ \exists \vec{s}' \, . \, R_{\T}(\vec{s},\vec{s}') \big], \, \mbox{and}\\
D(\vec{s}) & = & \bigvee_{i=1}^{m^s} \vec{t}^s_i = \Idle
\end{eqnarray*}
denote the characteristic functions for the set of blocking
states and decision states of a unit time transition graph with Boolean encoding 
$R_{\T}(\vec{s},\vec{s}')$. Further, let $R^i(\vec{s},\vec{s}')$ be defined recursively
by
\begin{eqnarray*}
R^0_{\T}(\vec{s},\vec{s}') & = & R_{\T}(\vec{s},\vec{s}'), \\
R^i_{\T}(\vec{s},\vec{s}') & = & R^{i-1}_{\T}(\vec{s},\vec{s}') \, \vee \Big(\exists \vec{s}' \, . \, R^{i-1}_{\T}(\vec{s},\vec{s}') \wedge \\
                           &   & \neg ( D(\vec{s}' ) \vee B(\vec{s}')) \wedge R^{i-1}_{\T}(\vec{s}',\vec{s}'') \Big)[\vec{s}'' / \vec{s}'], \\
                           &   & \mbox{for} \,\, i > 0. \\
\end{eqnarray*}
The operator $e[\vec{s}'' / \vec{s}']$ renames double primed variables
to single primed variables in the expression $e$. $R^0_{\T}$ encodes
the transition relation of the unit time transition graph. $R^1_{\T}$
includes the transitions of $R^0$, but adds a transition
$\(s,s''\)$ for every path $s s' s''$ where $s'$ neither is a
blocking state or decision state. Similarly $R^2$ adds
transitions that may bypass two such states, and $R^3$ adds
transitions that may bypass four etc.. In this way, we can define a Boolean
encoding of the decision graph as
\begin{eqnarray*}
R(\vec{s},\vec{s}') & = & R^{\lceil \log d \rceil}_{\T}(\vec{s},\vec{s}') \wedge (D(\vec{s}) \vee B(\vec{s})) \wedge \\
                    &   & (D(\vec{s}') \vee B(\vec{s}'))
\end{eqnarray*}
where $d$ is the maximal duration of any task. Iterative squaring is
known to be computationally complex. In our case, though, we only need
to iterate to ``compress'' paths of length $d$, which often will be
much less than the diameter of the transition graph. In addition,
iterative squaring has been shown to be fairly efficient for
transition systems dominated by clock counting \ref{GCLQ97}. 

\section{Solving ASET Planning Problems}
\label{sec:np}
The transformation of an ASET description to a non-deterministic
planning domain and the Boolean encoding of the decision graph, allows
us to use efficient symbolic non-deterministic planning algorithms
\cite{CPRT01,JV00A} including heuristic symbolic search algorithms \cite{JVB03A} to solve
ASET planning problems. In the remainder of this section, we apply the
machinery developed for non-deterministic symbolic planning 
to define ASET planning problems and solutions.

\begin{definition}[Non-Deterministic Planning Problem] A non-deterministic 
planning problem is a tuple $\(\D,s_0,G\)$ where $\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}

For a non-deterministic planning domain $\D = \(S, A, R \)$, the 
set of possible next states of an action $a$ applied in state $s$
is given by $\Next(s,a) \defeq \{ s' \Bar \(s,a,s'\) \in R \}$.
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  $\App(s) \defeq \{ a \Bar \Next(s,a) \not= \emptyset \}$.
A non-deterministic plan is a set of {\em state-action pairs} (SAs). 

\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 $\{ \(s,a\) \Bar 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. 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.  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. We are particularly interested in strong plans that guarantee
goal achievement in a finite number of steps. Following
\cite{DTV99,CPRT01}, we define strong plans formally by as a CTL
formula that must hold on a Kripke structure representing the execution
behavior of the plan.

A set of states {\em covered} by a plan $\pi$ is 
$\States(\pi) \defeq \{  s \Bar \exists a \, . \, \( s,a \) \in \pi \}$.
The set of actions in a plan $\pi$ associated with a state $s$ is
$\Actions(\pi,s) \defeq \{  a \Bar \( s,a \) \in \pi \}$.
The {\em closure} of a plan $\pi$ is the set of possible end states 
$\Closure(\pi) \defeq \{ s' \not\in \States(\pi) \Bar \exists \(s,a\) \in \pi \, . \, s' \in \Next(s,a) \, \}$.

\begin{definition}[Execution Model]
An execution model with respect to a non-deterministic plan $\pi$ for
the domain $\D = \(S,A,R\)$ is a Kripke structure
$\M(\pi) = \(Q,U\)$ where
\begin{itemize}
\item $Q = \Closure(\pi) \Cup  \States(\pi) \Cup  G$,
\item $\(s,s'\) \in U$ iff $\,\,s \not\in G,\,\,\exists a \Dot \( s,a \) \in \pi$ and $\(s,a,s'\) \in R$, 
      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, 
strong plans are defined by the CTL formula below.
\begin{definition}[Strong Plans]
\label{def:strong}
Given a non-deterministic planning problem $\P = \(\D,s_0,G \)$ and
a plan $\pi$ for $\D$, $\pi$ is a strong plan iff $\M(\pi),s_0 \models \AF G$.
\end{definition}    
The expression $\M(\pi),s_0 \models \AF G$ is true if all execution
paths in lead to a goal state in a finite number of steps.

\begin{example} \upshape There exists three non-deterministic plans for the 
decision graph of the diver problem shown in Figure~\ref{fig:diverDec}.
\small
\begin{eqnarray*} 
p_1 & = &  \{\((3,I,S)(I,W),\{S,D\}\)\} \\ 
p_2 & = &  \{\((3,I,S)(I,W),\{S,W\}\), \((1,p,S)(I,W),\{D\}\) \} \\
p_3 & = &  \{\((3,I,S)(I,W),\{S,W\}\), \((1,p,S)(I,W),\{W\}\) \} \\
\end{eqnarray*} 
\normalsize
None of these, however, are guaranteed to reach a goal state. Thus, as
mentioned earlier, there does not exist a strong plan for the diver
problem. \endex
\end{example}

\subsection{Fault Tolerance}

A weakness of strong plans is that they can be very conservative. In
real-world domains most actions may fail. If fault behavior is
modeled by non-determinism, a strong plan only exists if the worst
case behavior of the plan, where all actions fail, still leads to a
goal state. This is seldom the case. Instead it is natural to suggest
a weaker requirement, which is to guarantee goal achievement only if
no more than $n$ actions fail during execution. Such plans are called
$n$-fault tolerant plans \cite{JVB03W1}. Fault tolerant plans can be computed
via strong plans by adding fault counters to the domain. This is also
possible for ASET domains. 

We define a failure of a task as a unit time transition leading to the
idle state. In order to generate $n$-fault tolerant plans, we add a
special fault counter state variable $f_i$ for each controllable agent
$i$. For each task of agent $i$ that can fail, we extend the guard and
effect of each unit time transition denoting failure with the
expression $n > \sum_{i = 1}^{m_s} f_i$ and $f_i' = f_i + 1$,
respectively. For the remaining transitions of the task, we maintain
the value of $f_i$ by extending the effect with $f_i' = f_i$. Finally,
the initial state is extended with $f_i = 0$ for $i = 1 \ldots m^s$ and the goal states are extended
with $n \geq \sum_{i = 1}^{m_s} f_i$.

In this way failures can only happen in the fault extended problem if
less than $n$ failures have occurred so far. This is precisely the
assumption of $n$-fault tolerant plans and ensures that a strong plan
of the fault extended problem is a valid $n$-fault tolerant plan.

\begin{example} \upshape Consider a fault extended version of the diver
problem for generating 1-fault tolerant plans via strong planning. In
this domain, we assume that the top-most unit transition of the {\em
surface} task is due to an unlikely equipment failure. The new task is shown in 
Figure~\ref{fig:faultSurface}. Since Kim's
{\em wait} and {\em dive} tasks are successful, it is sufficient just
to add a single fault counter $f$ for Chris. The initial state is
extended with $f = 0$ and the goals states are extended with $1 \geq
f$.

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{faultSurface.eps}}
\end{center}
  \caption{The surface task of the fault extended diver problem.}
\label{fig:faultSurface} 
\end{figure}

The decision graph of the fault extend problem is shown in
Figure~\ref{fig:diverFaultDec}. The value of $f$ has been added to the
front of the first state tuple. Since the structure of the fault
extended decision graph is identical to the decision graph of the
original problem shown in Figure~\ref{fig:diverDec}, there does not
exist a strong plan and thus no 1-fault tolerant plan for this
problem. Consider, however, that the initial state is a state on an
execution path where one failure has already  happened. Since the fault transition of the 
{\em surface} task now can be assumed not to happen, we get the new decision graph shown
in Figure~\ref{fig:diverFaultDec2}. The non-deterministic plan $\{\((1,3,I,S)(I,W),\{S,D\}\)$       
is one of several strong plans for this problem. Thus, under these assumptions, there exists
a 1-fault tolerant plan. \endex
\end{example}



\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{diverFaultDec.eps}}
\end{center}
  \caption{Decision graph of the fault extended diver problem.}
\label{fig:diverFaultDec} 
\end{figure}


\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{diverFaultDec2.eps}}
\end{center}
  \caption{Decision graph of the fault extended diver problem assuming
  that one fault already has occurred.}
\label{fig:diverFaultDec2} 
\end{figure}



\subsection{Model Adaptation}

ASET descriptions support model adaptation learning algorithms by
providing a low-level definition of task behavior. Adapting the
behavior of tasks to a real-world domain is a structural learning
problem, where transitions are added or removed from tasks. In addition,
guard and effect expressions can be modified and task descriptions split.
The idea is to make a system more controllable by getting rid of
non-determinism. 

\begin{example} \upshape Assume that it has been learned that Kim always help Chris when
choosing to dive. In this case, at most one unit of oxygen  is consumed in
the second time unit of the {\em surface} task. The learned surface
task is shown in Figure~\ref{fig:learnSurface} and the corresponding
decision graph is shown in Figure~\ref{fig:learnDec}. It is now
possible always to safe Chris if Kim decides to {\em dive} (e.g.,
$\{\((1,3,I,S)(I,W),\{S,D\}\)$ is a strong plan for the
problem). \endex
\end{example}

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{learnSurface.eps}}
\end{center}
  \caption{The learned surface task.}
\label{fig:learnSurface} 
\end{figure}

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{learnDec.eps}}
\end{center}
  \caption{The decision graph of the diver problem with the
           learned surface task.}
\label{fig:learnDec} 
\end{figure}


\section{Conclusion}
\label{sec:con}
In this paper, we have introduced a new multi-agent planning domain
representation called ASET. The main contribution of ASET is Evolving
Tasks (ETs). ETs are, as far as we know, the first action
representation that can represent temporally extended activities which
are non-deterministic both with respect to duration and effect. ETs
are represented as unit time transition systems that in a natural way
solves the problem of representing conditional effects and
intermediate effects of durative actions.  In addition, ETs are
explicit and structural representations that are easy to access for
humans and suitable for domain knowledge learning algorithms.

We have formally defined ASET descriptions and shown how they can be
transformed into non-deterministic planning domains. Using a Boolean
encoding of these domains, efficient symbolic non-deterministic
planning algorithms can be applied to ASET planning problems.

The ASET representation is currently being integrated as the basic
building block in a closed loop planning, execution, and learning
framework. Our goal is to develop algorithms that adapt ASET
descriptions to real-world domains by learning new domain knowledge
from execution failures.


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