\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: a Multi-Agent Planning Language with Nondeterministic Durative Tasks for
BDD-Based Fault Tolerant Planning\thanks{This 
research is sponsored by BBNT Solutions LLC under its prime contract 
number FA8760-04-C-0002 with the U.S. Air Force and DARPA.
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

\begin{abstract}
In this paper, we introduce a multi-agent planning language called
ASynchronous Evolving Tasks (ASET). The main contribution of ASET is a
novel explicit representation of temporally extended tasks that may be
nondeterministic both with respect to duration and effects. Moreover,
ASET explicitly models the environment as a set of uncontrollable
agents. We formally define ASET descriptions and their transformation
to a nondeterministic planning domain. Using a Boolean encoding, fault
tolerant planning problems specified in ASET can be solved efficiently
with state-of-the-art BDD-based planning systems. Our preliminary
experimental results show that the transformation of ASET domains to
nondeterministic planning domains is computationally efficient even
for ASET descriptions with a high level of temporal detail.
\end{abstract}

\section{Introduction}
The most important obstacle for widespread application of automated
planning is lack of scalability. Since the complexity of planning
grows with the representational power of the planning language, a good
strategy for solving a planning problem efficiently is to use a
planning language that is sufficient for representing the problem at
hand but among such languages has least representational power.

For this reason, the goal for planning language developers is to
expose the representational power of the language by providing
intuitive and explicit ways to state abstract real-world phenomena.
In addition, well designed high-level languages makes it possible to
write short and elegant descriptions of a domain. They further improve
the ability of planning systems to exploit structure in domains.

Today powerful planners exist for the STRIPS planning language e.g.,
\cite{HN01}. But STRIPS assumes a single agent executing instantaneous
and deterministic actions, while most real domains involve multiple
asynchronous agents executing temporally extended stochastic
actions. There is no simple way of modeling stochastic behavior of
actions and multi-agent domains in STRIPS. Its representational power
is too low.

A wide range of planning languages have been developed to address the
deficiencies of STRIPS including temporal languages e.g.,
\cite{FL03,BA01,LGH98}, nondeterministic languages e.g.,
\cite{PBCGGRS02,GK97,JV00A} and probabilistic languages e.g.,
\cite{Y03}. None of them, however, have simple explicit ways of describing domains 
that combine all the aspects of real-world domains mentioned
above. In particular, we are not aware of any planning language with a
single unified construct to define actions that are nondeterministic
both with respect to effect and duration. Temporal planning languages
have deterministic actions and nondeterministic planning languages do
not consider durative actions.

The representational power of some of these languages e.g.,
\cite{Y03,MDS93} and classical representations like discrete event
systems, timed automata, and Markov Decision Processes (MDPs) is
strong enough to model such domains. But it is often tedious and error
prone to define domains in these formalisms due to the
implicit representation of abstract phenomena. Furthermore, the
representational power may be so high that the planning problems
become unnecessarily hard to solve.

The research reported in this paper investigates how low we can go in
representational power and still be able to define a language in which
stochastic durative actions and multi-agent domains can be
stated in a unified, intuitive, and explicit way. More specifically, we
consider a language with the representation power of a
nondeterministic planning domain (i.e., an MDP with no transition
probabilities). Our motivation is that stationary policies for
nondeterministic planning problems can be synthesized efficiently 
\cite{CPRT01,JVB03A} using techniques developed in formal verification based on Binary
Decision Diagrams (BDDs) \cite{B86,BCM90}.

Continuous time and probabilistic models are attractive, but come with
a high computational fee. It is well-known that continuous time
verification of asynchronous circuits is much harder than discrete
time verification of synchronized circuits, and even though efficient
symbolic techniques exist for solving MDPs \cite{HZ01}, it is our
experience that nonprobabilistic versions of these problems have orders
of magnitude lower complexity.

We are interested in high-level planing problems where the goal is to
coordinate low-level activities and manage shared resources. Such
domains are often combinatorial and discrete in nature. Imagine an
automated job shop floor with robots moving objects between machines
and storage buffers. Commands to machines and robots are high-level,
but fairly accurate models exist of the behavior they trigger. The
main problem is to deliver and remove objects from machines in a
temporally coordinated manner and share resources such as space. 

Our language is based on an action representation called Evolving
Tasks (ETs). ETs are Directed Acyclic Graphs (DAGs) of guarded unit
time transitions that define the temporal behavior of the task. They
can represent temporally extended activities which are
nondeterministic both with respect to duration and effect. We consider
multi-agent planning domains where each agent is defined by the set of
ETs it can execute. The resulting language is called ASynchronous
Evolving Tasks (ASET). Like NADL \cite{JV00A}, ASET explicitly model
the environment as a set of uncontrollable agents.

The low-level semantics of an ASET domain is a {\em unit time
transition graph}. The domain, however, is not controllable at this
level since tasks are uninterruptible. A {\em decision graph} is
derived from the unit time transition graph by adding transitions
between all states where some task is idle and removing all other states
from the unit time transition graph. This can be done efficiently using a technique
called {\em iterative squaring} \cite{BCM90}.  The decision graph is a
nondeterministic planning domain that 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 nondeterministic planning systems
\cite{CPRT01,JVB03A}.

Using this bottom-up approach, it is easy to define low-level temporal
properties of the activities, but plan in a more abstract
space. PDDL2.1 and other temporal languages extending STRIPS are based
on a top-down approach where many features are used to define the
temporal properties of actions. The result is less general languages
with temporal semantics of actions that can be hard to understand. The
unit time semantics of ETs further solve a general problem of
augmenting first order logic with time for temporal planning
\cite{BA01,FL03}. This often leads to information ``holes'' caused by
concurrent actions hiding the state of domain knowledge they are
currently changing. This makes it hard to write domains with mutually
dependent asynchronous activities.

The main limitation of ASET is the lack of transition
probabilities. Often, however, stochastic behavior is caused by
infrequent system failures. This allows us to avoid full-blown
probabilistic planning and instead consider nondeterministic plans
robust to a limited number of system failures \cite{JVB04A}.  
Another limitation is that ASET assumes full
observability. But this is a reasonable assumption for systems that
are engineered to be highly controllable. 

We have implemented a BDD-based planning system for ASET. Preliminary
experimental results show that a unit time transition graph can be
efficiently transformed into decision graph even when the duration of
tasks is in the order of 500 time units. This level of temporal
granularity is more than sufficient for most applications.

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 transition graph of an
ASET description and its Boolean encoding and show how to transform
the unit time transition graph into a decision graph. The following
section briefly reminds about the definition of strong
nondeterministic plans and shows how to represent a fault tolerant
planning domain in ASET. We then present our experimental results
and finally draw conclusions and discuss plans for future work.


\section{ASET Descriptions} 
An ASET description consists of 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 for 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}. Each
transition of a task 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 DAG 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 tasks of other agents. 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 nondeterministically chosen as the effect of the transition. In
this way, tasks are nondeterministic 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 perform 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. 
 
As an example consider the simple job shop domain shown in 
Figure~\ref{fig:dom}. The domain has four locations $a$, $b$, $c$, and $d$ connected
with corridors ${\it ab}$, ${\it bd}$, ${\it cd}$, and ${\it ac}$. The goal is to paint 
the object (O). It can be carried by the robot (R) to the painting machine (P).
The robot spends time navigating between corridors and may have to backtrack to its source 
location. The robot and painting machine are controllable, but there is also an uncontrollable 
human operator (H). For security reasons, the robot is not allowed to load and unload the object
when the human is at the same location. 

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{dom.eps}}
\end{center}
  \caption{The job shop domain.}
\label{fig:dom} 
\end{figure}

Figure~\ref{fig:aset} shows an ASET description of the job shop
domain. Each task is a DAG where vertices are execution states and
edges are unit time transitions. The idle execution state is marked by
a double circle.  Execution states are labeled by numbers (by
convention idle states are labeled by zero, but these labels have been
omitted to enhance readability). The guard expression or precondition
of a unit time transition is shown above the associated edge. The
effect of the transition is shown below the edge. The ASET description
has two controllable system agents the robot (R) and the painting
machine (P). It also has a single uncontrollable environment agent
which is the human operator (H). The tasks of the robot are ${\it
move}(x,y)$\footnote{The figure shows ${\it move}(a,b)$, but there are
7 other move tasks.}, ${\it take}$, ${\it put}$, and ${\it
wait}$. During the move task, the robot navigates between the
locations via the corridors. It may succeed after 2 time units and
reach its destination, or fail after 3 time units in which case, it
returns to the source location. The take and put tasks loads and
unloads the object on the robot. They take one time unit and are
conditioned by the human being at another location. The wait task also
takes one time unit. It does not change any state variables, but only
advances time to coordinate the robots activities with other
agents. The tasks of the painter are ${\it paint}$ and ${\it
wait}$. The paint task takes either 3 or 4 time units and requires
that the object is at location $b$ and is unpainted. Moreover, the
robot must avoid location $b$ when the actual painting happens. The
wait task of the painter is identical to the wait task of the
robot. The human has move tasks similar to the robot except that
they are deterministic and have a duration of 4 time units. Since
there is no wait task, the human must continuously move between
locations. This guarantees that the robot eventually can load and
unload the object.

\begin{figure}[t!]
 \centering \input{aset.eepic}
 \caption{\label{fig:aset} An ASET description of the job shop domain.}
\end{figure}




\newpage
\noindent
Formally, an ASET description is defined as follows. 
\begin{definition}[ASET Description] 
An ASET description is a triple $\M = \(V,E,T\)$, where
\end{definition}
\begin{tabular}{lp{7.5cm}}

$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 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}
nondeterministic. None of the above domain descriptions consider
nondeterministic actions. Actually, we are not aware of any planning
language with temporally extended and nondeterministic
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 job shop 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  eat the same ice cream.  If
only the first condition defined interfering tasks, both agents
could simultaneously eat the ice cream, as the effect ${\it iceCreamEaten}$ 
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 at a time. 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 nondeterministic
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. 

Consider again the job shop domain shown in Figure~\ref{fig:aset}.
Assume that all agents are in an idle execution state in the situation
depicted at the top of the figure. Suppose that the tasks ${\it
move(a,c)}$ and ${\it paint}$ are chosen for the robot and painter,
and that the human happens to choose ${\it move(d,c)}$.\footnote{The 
result would have been the same for any of its move tasks.} 
Figure~\ref{fig:unitTime} shows the reachable states in the unit time
transition graph from this state until some agents are idle
again. Each state is labeled with a vector showing the execution state
of the robot, painter, and human respectively.

\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{unitTime.eps}}
\end{center}
  \caption{A subset of the unit time transition graph of the job shop domain.}
\label{fig:unitTime} 
\end{figure}

For an ASET description $\M = \(V,E,T\)$, let $\mbox{NC}$ denote
nonconflicting 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 = \(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} = 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   & = & \(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'  & = & \(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}$.
 
\end{enumerate}


In order to use symbolic nondeterministic 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{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{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 = \(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]\\
      &    & \mathrm{where} \,\, M^x_t = \{ p(1),\ldots,p(n^x_t) \} \,\, \mathrm{and}    \\
      &    & R^x_t(\vec{s},\vec{v}'^x_{p(1)..p(n^x_t)},\vec{e}'^x_i) \,\, \mathrm{is} \,\, \mathrm{the} \,\, \mathrm{characteristic} \\
      &    & \mathrm{function} \,\, \mathrm{of} \,\, \mathrm{the} \,\, \mathrm{set}\,\, \mathrm{of} \,\, \mathrm{tuples} \,\, \mathrm{in} \,\, R^x_t,  \\
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] \\
      &    & \mathrm{where} \,\, T^x_j(i) = \{ t \in T^x_j \Bar i \in M^x_t \}.\\
\end{eqnarray*}

\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}} 
             \left[ \begin{array}{l}  D^x_{t_1} \cap D^x_{t_2} = \Empty \Imp \\ 
                   \neg (\vec{t}^x_i = t_1 \wedge \vec{t}^x_j = t_2) \\ 
                   \wedge \neg(\vec{t}'^x_i = t_1 \wedge \vec{t}'^x_j = t_2) \end{array} \right].  
$$
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}') = \bigwedge_{x \in \{s,e\}} r^x_1 \wedge r^x_2 \wedge r^x_3 \wedge {\it NC}^x.\footnote{Since the finite domains of 
ASET variables are embedded in a binary encoding, there may exist assignments to the Boolean variables that do not correspond to valid domain values. 
Conjoining an expression that removes these assignments from the Boolean transition relation has been omitted in the definition to simplify the presentation.}
$$

\section{ASET Decision Graphs}
\label{sec:dg}
We now consider how to transform the unit time transition graph of an
ASET description into a nondeterministic planning domain that we can
solve efficiently with a state-of-the-art BDD-based nondeterministic
planning system. The nondeterministic 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 nondeterministic choice from a
set of possible next states. 

\begin{definition}[Nondeterministic Planning Domain]
A nondeterministic 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 nondeterministic transition relation of action effects.
\end{definition}

A unit time transition graph is transformed into a nondeterministic
planning domain by removing states where no planning decision can be
made. A planning decision can be made in states where the task of one
or more controllable agents is idle. We call such states {\em decision
states}. For unit time transition graph of the job shop domain shown in
Figure~\ref{fig:unitTime}, all unfilled circles (the end states) are decision
states. 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 nondeterministic 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). In the job shop
domain, any state where the robot is at location $b$ and the painter
is in execution state $1$ of its paint task is a blocking state since
the paint task is unable to transition due to the guard ${\it posR}
\neq b$. 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 nondeterministic 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 = \(V,E,T\)$ and a unit time transition graph $\T =
\( S_{\T} , R_{\T} \)$ of $\M$, an ASET decision graph of $\M$ is a
nondeterministic 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   & = & \(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'  & = & \(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$.

It is nontrivial to compute the decision graph, since it is
defined in terms of paths in the unit time transition graph. For
symbolic nondeterministic planning, though, the decision
graph can be efficiently computed using {\em iterative squaring}
\cite{BCM90}. Iterative squaring of a transition relation introduces 
transitions between all states connected by a path. The operation is
defined recursively. $R^0$ is the original transition relation.  $R^1$
includes all the transition in $R^0$, but in addition has transitions
between all states in $R^0$ connected by a path of length 2. $R^2$
includes all transitions in $R^1$, but in addition has transitions
between all states in $R^1$ connected by a path of length 2. Since
$R^1$ includes $R^0$ this means that $R^2$ includes all the
transitions in $R^0$, but in addition has transitions between all
states in $R^0$ connected by a path of length 2,3, or 4. Thus, for
each squaring of the transition relation the length of the paths for
which transitions are added doubles. 

Consider squaring the unit time transition graph of the
job shop domain shown in Figure~\ref{fig:unitTime}. 
Figure~\ref{fig:square} shows the transitions in $R^2$.
\begin{figure}[h!]
\begin{center}
\scalebox{1.0}{\epsfbox{square.eps}}
\end{center}
  \caption{Squaring the unit time transition graph shown in Figure~\ref{fig:unitTime}. 
           Transitions in $R^j$ for $j \leq i$ are labeled $i$.}
\label{fig:square} 
\end{figure}

We use a special version of the algorithm that ensures that all intermediate 
states on paths for which transitions are introduced are neither decision states nor
blocking states.

\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{e}^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}$ is
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 up to 3 such states, and $R^3$ adds
transitions that may bypass 7 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. 

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

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 digital
systems dominated by clock counting \cite{GCLQ97}. We may expect ASET
domains where tasks have long duration to be structurally similar to
this kind of circuits.


\section{Solving ASET Planning Problems}
\label{sec:np}
The transformation of an ASET description to a nondeterministic
planning domain and the Boolean encoding of the decision graph, allows
us to use efficient symbolic nondeterministic 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 nondeterministic symbolic planning 
to define ASET planning problems and solutions.

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

For a nondeterministic 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 nondeterministic plan is a set of {\em state-action pairs} (SAs). 

\begin{definition}[Nondeterministic Plan] 
Let $\D$ be a nondeterministic planning domain. A nondeterministic 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 nondeterministic 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 nondeterministic 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{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 nondeterministic 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 state 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 nondeterministic 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 lead to a goal state in a finite number of steps.


\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
via nondeterminism, 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. We would like to be able to state a
weaker kind of plans that do not have to cover the most unlikely
execution paths.  As mentioned in the introduction,
going all the way to probabilistic planning is not a solution due to
the high computational cost. But we can rephrase a plan
with high probability of success as a plan with high tolerance for
failures encountered during execution. Such plans can be defined fully
within the framework of nondeterministic planning. Plans that guarantee 
goal achievement if no more than $n$ actions fail during execution are called
$n$-fault tolerant plans \cite{JVB04A}. Fault tolerant plans can be
computed via strong plans by adding fault counters to the
domain.\footnote{While this approach is conceptually easy to
understand, much better performance can be achieved in real-world
domains by distinguishing semantically between failure effects and
successful effects and use specialized planning algorithms \cite{JVB04A}.}
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.


\section{Experimental Evaluation}

We have implemented a planning system in C++/STL using the BuDDy BDD package \cite{L99}.
Given a textual ASET description, it computes two BDDs representing the transition
relation of the unit time transition graph and its associated decision graph.

The experiment reported in this section investigates how fast the
computational complexity of synthesizing the decision graph grows with
the temporal granularity of the unit time decision graph. We consider
a parameterized version of the job shop domain where each task is
extended with extra unit time transitions such that the overall structure of the
task is maintained. For instance, unit time transitions are added on both the
left and right side of the early termination of the painter's paint
task and the robot's move task. Since the number of possible ways 
that tasks can be temporally aligned grows polynomially with their duration, computing 
the decision graph could potentially be hard.

We conducted the experiments on a 3GHz Pentium 4 with 1024KB L2 cache
and 2GB RAM~\footnote{The experiments, however, were limited to 500MB RAM.}
running Linux kernel 2.4.25. Figure~\ref{fig:dg} shows the computation time 
of the unit time transition graph and the decision graph.  
\begin{figure}[h!]
\begin{center}
\scalebox{0.6}{\epsfbox{gnuplot/dg.eps}}
\end{center}
  \caption{CPU time for synthesizing the unit time transition graph (UTG) and the decision graph (DG) as a function of maximum task duration.}
\label{fig:dg} 
\end{figure}
As depicted, the CPU time for computing the unit time transition graph
is very low for all versions of the domain. Despite the much longer
time needed to compute the decision graph, the asymptotic complexity
of this operation is low. Notice the jumps in
computation time when the iterative squaring involves computing a new
intermediate transition relation. Fortunately the distance between
these jumps grows exponentially with the maximum task duration.

Figure~\ref{fig:bdd} shows how the BDD size of the unit time transition
graph and the decision graph grows as a function of the maximum task
duration.
\begin{figure}[h!]
\begin{center}
\scalebox{0.6}{\epsfbox{gnuplot/bdd.eps}}
\end{center}
  \caption{BDD size of the unit time transition graph (UTG) and the decision graph (DG) as a function of maximum task duration.}
\label{fig:bdd} 
\end{figure}
As depicted, the BDD size of the decision graph grows approximately
linearly with the computation time of the decision graph. It may be
surprising that the BDD of the decision graph is larger than the BDD
of the unit time transition graph. Since BDDs represent
transitions implicitly, there is no simple relation between the size
of a BDD and the number of transitions it represent. That the BDD
representing the decision graph is large merely indicates that the
subspace of transitions in the decision graph is less structured than
that of the unit time decision graph. The question is to what extend
this will impair BDD based planning based on the decision graph. 
Future experiments will address this issue.


\section{Conclusion}
\label{sec:con}
In this paper, we have introduced a new multi-agent planning language
called ASET. The main contribution of ASET is Evolving Tasks
(ETs). ETs are, as far as we know, the first action description that
in an explicit and intuitive way can represent temporally
extended activities which are nondeterministic both with respect to
duration and effect. ETs are represented as directed acyclic graphs 
that in a natural way solves the problem of representing
conditional effects and intermediate effects of durative actions.

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

ASET shows that it is possible to model essential aspects of time and
stochastic behavior in a language with a representational power as low
as a nondeterministic finite automata. This is encouraging since the
main challenge of automated planning is to scale to the size of
real-world domains, and since dense time and probabilistic models come
with a high computational fee.

Preliminary results show that the decision graph of ASET domains can
be generated efficiently even for domains with a high level of
temporal detail. Future work includes further experiments
investigating BDD-based planning based on ASET decision graphs and
developing more efficient ways of generating and representing decision
graphs (e.g., by using transition relation partitioning \cite{BC91}).


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