\documentstyle[jair,twoside,11pt,theapa]{article}
%\input epsf %% at top of file



\jairheading{2}{1994}{111-129}{5/94}{9/94}
\ShortHeadings{On Planning while Learning}{Safra and Tennenholtz}
\firstpageno{111}


\newcommand\th{\strut^{\mbox{\tiny\underline{th}}}}



%\input{defn}
\newtheorem{THEOREM}{Theorem}[section]
\newenvironment{theorem}{\begin{THEOREM} \hspace{-.85em} {\bf :} }%
                        {\end{THEOREM}}
\newtheorem{DEFINITION}{Definition}[section]
\newenvironment{definition}{\begin{DEFINITION} \hspace{-.85em} {\bf :} \rm}%
                        {\end{DEFINITION}}
\newtheorem{LEMMA}[THEOREM]{Lemma}
\newenvironment{lemma}{\begin{LEMMA} \hspace{-.85em} {\bf :} }%
                      {\end{LEMMA}}
\newtheorem{COROLLARY}[THEOREM]{Corollary}
\newenvironment{corollary}{\begin{COROLLARY} \hspace{-.85em} {\bf :} }%
                          {\end{COROLLARY}}
\newtheorem{PROPOSITION}[THEOREM]{Proposition}
\newenvironment{proposition}{\begin{PROPOSITION} \hspace{-.85em} {\bf :} }%
                            {\end{PROPOSITION}}
%\newtheorem{DEFINITION}[THEOREM]{Definition}
%\newenvironment{definition}{\begin{DEFINITION} \hspace{-.85em} {\bf :} \rm}%
%                            {\end{DEFINITION}}
\newtheorem{EXAMPLE}[THEOREM]{Example}
\newenvironment{example}{\begin{EXAMPLE} \hspace{-.85em} {\bf :} \rm}%
                            {\end{EXAMPLE}}
\newtheorem{REMARK}[THEOREM]{Remark}
\newenvironment{remark}{\begin{REMARK} \hspace{-.85em} {\bf :} \rm}%
                            {\end{REMARK}}
%\newenvironment{proof}{\noindent {\bf Proof:} \hspace{.677em}}%
%                      {}

%theorem
\newcommand{\thm}{\begin{theorem}}
%lemma
\newcommand{\lem}{\begin{lemma}}
%proposition
\newcommand{\pro}{\begin{proposition}}
%definition
\newcommand{\dfn}{\begin{definition}}
%remark
\newcommand{\rem}{\begin{remark}}
%example
\newcommand{\xam}{\begin{example}}
%corollary
\newcommand{\cor}{\begin{corollary}}
%proof
\newcommand{\prf}{\noindent{\bf Proof:} }
%end theorem
\newcommand{\ethm}{\end{theorem}}
%end lemma
\newcommand{\elem}{\end{lemma}}
%end proposition
\newcommand{\epro}{\end{proposition}}
%end definition
\newcommand{\edfn}{\bbox\end{definition}}
%end remark
\newcommand{\erem}{\bbox\end{remark}}
%end example
\newcommand{\exam}{\bbox\end{example}}
%end corollary
\newcommand{\ecor}{\end{corollary}}
%end proof
\newcommand{\eprf}{\bbox\vspace{0.1in}}
%begin equation
\newcommand{\beqn}{\begin{equation}}
%end equation
\newcommand{\eeqn}{\end{equation}}
% white box
\newcommand{\wbox}{\mbox{$\sqcap$\llap{$\sqcup$}}}
%black box
\newcommand{\bbox}{\vrule height7pt width4pt depth1pt}
\newcommand{\qed}{\eprf}
% (not)member of
\let\member=\in
\let\notmember=\notin
% \sub will be used for subscript.
\newcommand{\sub}{_}
% \su will be used for superscript.
\def\su{^}
%right arrow
\newcommand{\rarrow}{\rightarrow}
%left arrow
\newcommand{\larrow}{\leftarrow}
%bold face lower-case letters
\newcommand{\bolda}{{\bf a}}
\newcommand{\boldb}{{\bf b}}
\newcommand{\boldc}{{\bf c}}
\newcommand{\boldd}{{\bf d}}
\newcommand{\bolde}{{\bf e}}
\newcommand{\boldf}{{\bf f}}
\newcommand{\boldg}{{\bf g}}
\newcommand{\boldh}{{\bf h}}
\newcommand{\boldi}{{\bf i}}
\newcommand{\boldj}{{\bf j}}
\newcommand{\boldk}{{\bf k}}
\newcommand{\boldl}{{\bf l}}
\newcommand{\boldm}{{\bf m}}
\newcommand{\boldn}{{\bf n}}
\newcommand{\boldo}{{\bf o}}
\newcommand{\boldp}{{\bf p}}
\newcommand{\boldq}{{\bf q}}
\newcommand{\boldr}{{\bf r}}
\newcommand{\bolds}{{\bf s}}
\newcommand{\boldt}{{\bf t}}
\newcommand{\boldu}{{\bf u}}
\newcommand{\boldv}{{\bf v}}
\newcommand{\boldw}{{\bf w}}
\newcommand{\boldx}{{\bf x}}
\newcommand{\boldy}{{\bf y}}
\newcommand{\boldz}{{\bf z}}
%bold face upper-case letters
\newcommand{\boldA}{{\bf A}}
\newcommand{\boldH}{{\bf H}}
\newcommand{\boldI}{{\bf I}}
\newcommand{\boldP}{{\bf P}}
\newcommand{\boldQ}{{\bf Q}}
\newcommand{\boldR}{{\bf R}}
\newcommand{\boldS}{{\bf S}}
\newcommand{\boldT}{{\bf T}}
\newcommand{\boldU}{{\bf U}}
\newcommand{\boldV}{{\bf V}}
%double turnstile
\newcommand{\sat}{\models}
\newcommand{\dtur}{\models}
%single turnstile
\newcommand{\infers}{\vdash}
\newcommand{\stur}{\vdash}
%fat right arrow
\newcommand{\rimp}{\Rightarrow}
%fat left arrow
\newcommand{\limp}{\Leftarrow}
%fat double arrow
\newcommand{\dimp}{\Leftrightarrow}
%big or
\newcommand{\bor}{\bigvee}
%big and
\newcommand{\band}{\bigwedge}
%union
\newcommand{\union}{\cup}
%intersection
\newcommand{\inter}{\cap}
%bold letters
\newcommand{\xx}{{\bf x}}
\newcommand{\yy}{{\bf y}}
\newcommand{\uu}{{\bf u}}
\newcommand{\vv}{{\bf v}}
\newcommand{\FF}{{\bf F}}
\newcommand{\natnum}{{\sl N}}
%\newfont{\sqi}{cmssqi8}
\newcommand{\IR}{\mbox{$I\!\!R$}}
\newcommand{\IP}{\mbox{$I\!\!P$}}
\newcommand{\IN}{\mbox{$I\!\!N$}}
\newcommand{\IC}{\mbox{$C\!\!\!\!\raisebox{.75pt}{\mbox{\sqi I}}$}}
%Use $\IC \;\;$
% multivalued arrow
\newcommand{\marrow}{\hbox{$\rightarrow$ \hskip -10pt
/                     $\rightarrow$ \hskip 3pt}}
% phi
\renewcommand{\phi}{\varphi}
%\renewcommand{\Diamond}{{\bf Large \diamond}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\all}{\forall}
\newcommand{\infinity}{\infty}
%binomial coefficient:
\newcommand{\bc}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array} \right)}
\newcommand{\cross}{\times}


% Joe's Section

\newcommand{\imp}{\Rightarrow}

%\H, \L, \O, \P and \S already taken; but we're redefining \P anyway
\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\D}{{\cal D}}
\newcommand{\E}{{\cal E}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
%\newcommand{\H}{{\cal H}}
\newcommand{\I}{{\cal I}}
\newcommand{\J}{{\cal J}}
\newcommand{\K}{{\cal K}}
%\newcommand{\L}{{\cal L}}
\newcommand{\M}{{\cal M}}
\newcommand{\N}{{\cal N}}
%\newcommand{\O}{{\cal O}}
\newcommand{\Ocal}{{\cal O}}
\newcommand{\Hcal}{{\cal H}}
\renewcommand{\P}{{\cal P}}
\newcommand{\Q}{{\cal Q}}
\newcommand{\R}{{\cal R}}
%\newcommand{\S}{{\cal S}}
\newcommand{\T}{{\cal T}}
\newcommand{\U}{{\cal U}}
\newcommand{\V}{{\cal V}}
\newcommand{\W}{{\cal W}}
\newcommand{\X}{{\cal X}}
\newcommand{\Y}{{\cal Y}}
\newcommand{\Z}{{\cal Z}}

\newcommand{\Kone}{{\cal K}_1}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\Ki}{{\cal K}_i}
\newcommand{\Kn}{{\cal K}_n}
\newcommand{\st}{\, \vert \,} %puts vertical bar with space around it
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
\newcommand{\lang}{\mbox{${\cal L}_n$}}
\newcommand{\langd}{\mbox{${\cal L}_n^D$}}

\renewcommand{\Box}{\mathbin{\vcenter{\hrule
    \hbox{\vrule \kern .6em
          \vbox to .6em{}\vrule}\hrule}}\hspace{.17ex}}
\newtheorem{nlem}{Lemma}
\newtheorem{Ob}{Observation}
\newtheorem{pps}{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{crl}{Corollary}
\newtheorem{cl}{Claim}
\newcommand{\pf}{\par\noindent{\bf Proof}~~}
\newcommand{\eg}{e.g.~}
\newcommand{\ie}{i.e.,~}
\newcommand{\vs}{vs.~}
\newcommand{\cf}{cf.~}
\newcommand{\resp}{resp.\ }
\newcommand{\respc}{resp.,\ }
\newcommand{\comment}[1]{\marginpar{\scriptsize\raggedright #1}}
\newcommand{\wrt}{with respect to~}
\newcommand{\nind}{\noindent}
\newtheorem{EXERCISE}{}[chapter]
\newenvironment{exercise}{\begin{EXERCISE}  \hspace{-.85em} {\bf .}
\rm}%
{\end{EXERCISE}}
%\newenvironment{hardex}{\begin{EXERCISE}  \hspace{-.85em} {\bf *.}
%\rm}%
%{\end{EXERCISE}}
%\newtheorem{EXERCISE}{}[chapter]
%\newenvironment{exercise}{\begin{EXERCISE}  \hspace{-.85em} {\bf .}
%\rm}%
%{\end{EXERCISE}}
\newtheorem{HARDEX}[EXERCISE]{\hspace{-.95em} * \hspace{-.25em}}
\newenvironment{hardex}{\begin{HARDEX}  \hspace{-.85em} {\bf .}
\rm}%
{\end{HARDEX}}
\newtheorem{SUPERHARD}[EXERCISE]{\hspace{-1.45em} ** \hspace{-.25em}}
\newenvironment{superhard}{\begin{SUPERHARD}  \hspace{-.85em} {\bf .}
\rm}%
{\end{SUPERHARD}}
\newcommand{\distributed}{distributed\ }
\newcommand{\bn}{\bigskip\markright{BIBLIOGRAPHIC NOTES}
\nind{\bf Bibliographic Notes:} \ }
\newcommand{\Exer}{
\bigskip\markright{EXERCISES}\nind{\bf Exercises:} \ }
\newcommand{\DG}{D_G}
\newcommand{\Sm}{{\rm S5}_m}
\newcommand{\Smc}{{\rm S5C}_m}
\newcommand{\Smi}{{\rm S5I}_m}
\newcommand{\Smic}{{\rm S5CI}_m}
\newcommand{\Martin}{Mart\'\i n\ }
\newcommand{\ol}{\setlength{\itemsep}{0pt}\begin{enumerate}}
\newcommand{\eol}{\end{enumerate}\setlength{\itemsep}{-\parsep}}
\newcommand{\ul}{\setlength{\itemsep}{0pt}\begin{itemize}}
\newcommand{\dl}{\setlength{\itemsep}{0pt}\begin{description}}
\newcommand{\edl}{\end{description}\setlength{\itemsep}{-\parsep}}
\newcommand{\eul}{\end{itemize}\setlength{\itemsep}{-\parsep}}
\newtheorem{fthm}{Theorem}
\newtheorem{flem}[fthm]{Lemma}
\newtheorem{fcor}[fthm]{Corollary}
\newcommand{\slidehead}[1]{
\eject
\Huge
\begin{center}
{\bf #1 }
\end{center}
\vspace{.5in}
\LARGE}

%chck macros
\newcommand{\subG}{_G}
\newcommand{\If}{{\bf if}}

\newcommand{\attime}{{\tt \ at\_time\ }}
\newcommand{\hatell}{\skew6\hat\ell\,}
\newcommand{\Then}{{\bf then}}
\newcommand{\Until}{{\bf until}}
\newcommand{\Else}{{\bf else}}
\newcommand{\Repeat}{{\bf repeat}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cI}{{\cal I}}
%\newcommand{\IcR}{{\cal I}_{\cal R}}
%\newcommand{\IRca}{{\cal I}_\Rca}
%\newcommand{\Rca}{{\cR_{ca}}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cS}{{\cal S}}
\newcommand{\BN}{B^{\scriptscriptstyle \cN}}
\newcommand{\BS}{B^{\scriptscriptstyle \cS}}
\newcommand{\cW}{{\cal W}}
\newcommand{\EG}{E_G}
\newcommand{\CG}{C_G}
\newcommand{\CN}{C_\cN}
\newcommand{\ES}{E_\cS}
\newcommand{\EN}{E_\cN}
\newcommand{\CS}{C_\cS}
%\newcommand{\RP}{{\cR_P}}
%\newcommand{\IRP}{{\cal I}_\RP}
%\newcommand{\RSBA}{{\cR_{\it sba}}}
%\newcommand{\IRSBA}{{\cal I}_\RSBA}
\newcommand{\attack}{\mbox{{\it attack}}}
\newcommand{\attacking}{\mbox{{\it attacking}}}
\newcommand{\delivered}{\mbox{{\it delivered}}}
\newcommand{\exist}{\mbox{{\it exist}}}
\newcommand{\decide}{\mbox{{\it decide}}}
\newcommand{\clean}{{\it clean}}
\newcommand{\diff}{{\it diff}}
\newcommand{\Failed}{{\it failed}}
\newcommand{\KF}{{\it Known\_Failed}}
%\newcommand{\RF}{\cR_{\scriptscriptstyle {\cal F}}}
%\newcommand\eqdef{\buildrel {\rm def}\over =}
\newcommand\eqdef{=_{\rm def}}

\newcommand{\DN}{D_{\cN}}
\newcommand{\DS}{D_{\cS}}
\newcommand{\IF}{\cI}
%\newcommand{\IF}{\cI_{{\it full}}}
%\newcommand{\cP}{{\cal P}}
\newcommand{\tyme}{{\it time}}
\newcommand{\fp}{f}

%chguide macros
\newcommand{\Kax}{{\rm K}_n}
\newcommand{\Kaxc}{{\rm K}_n^C}
\newcommand{\Kaxd}{{\rm K}_n^D}
\newcommand{\Tax}{{\rm T}_n}
\newcommand{\Taxc}{{\rm T}_n^C}
\newcommand{\Taxd}{{\rm T}_n^D}
\newcommand{\fourax}{{\rm S4}_n}
\newcommand{\fouraxc}{{\rm S4}_n^C}
\newcommand{\fouraxd}{{\rm S4}_n^D}
\newcommand{\fiveax}{{\rm S5}_n}
\newcommand{\fiveaxc}{{\rm S5}_n^C}
\newcommand{\fiveaxd}{{\rm S5}_n^D}
\newcommand{\Dax}{{\rm KD45}_n}
\newcommand{\Daxc}{{\rm KD45}_n^C}
\newcommand{\Daxd}{{\rm KD45}_n^D}
\newcommand{\LP}{{\cal L}_n}
\newcommand{\LCP}{{\cal L}_n^C}
\newcommand{\LDP}{{\cal L}_n^D}
\newcommand{\LCDP}{{\cal L}_n^{CD}}
\newcommand{\MP}{{\cal M}_n}
\newcommand{\MPr}{{\cal M}_n^r}
\newcommand{\MPrt}{{\cal M}_n^{rt}}
\newcommand{\MPrst}{{\cal M}_n^{rst}}
\newcommand{\MPelt}{{\cal M}_n^{elt}}
\renewcommand{\lang}{\mbox{${\cal L}_{n} (\Phi)$}}
\renewcommand{\langd}{\mbox{${\cal L}_{n}^D (\Phi)$}}
\newcommand{\fiveaxdu}{{\rm S5}_n^{DU}}
\newcommand{\LPD}{{\cal L}_n^D}
\newcommand{\fiveaxu}{{\rm S5}_n^U}
\newcommand{\fiveaxcu}{{\rm S5}_n^{CU}}
\newcommand{\LPU}{{\cal L}^{U}_n}
\newcommand{\LPCU}{{\cal L}_n^{CU}}
\newcommand{\LDPU}{{\cal L}_n^{DU}}
\newcommand{\LCPU}{{\cal L}_n^{CU}}
\newcommand{\LPDU}{{\cal L}_n^{DU}}
\newcommand{\LPCDU}{{\cal L}_n^{CDU}}
\newcommand{\Cn}{\C_n}
\newcommand{\CSn}{CS_n(\Phi)}
\newcommand{\CSAX}{CS$_{n,\Phi}$}
\newcommand{\CSAXN}{CS$_{n,\Phi}'$}
\newcommand{\untill}{U}
\newcommand{\until}{\, U \,}
\newcommand{\amp}{{\rm a.m.p.}}
\newcommand{\commentout}[1]{}
\newcommand{\msgc}[1]{ @ #1 }
\newcommand{\Camp}{{\C_n^{amp}}}











\begin{document}

 
\title{On Planning while Learning}

\author{\name Shmuel Safra \email safra@cs.huji.ac.il \\
       \addr Computer Science Department\\
       Hebrew University\\
       Jerusalem, Israel
       \AND
       \name Moshe Tennenholtz \email moshet@ie.technion.ac.il \\
       \addr Industrial Engineering and Management\\
             Technion \\
             Haifa 32000, Israel}

% For research notes, remove the comment character in the line below.
% \researchnote

\maketitle


\begin{abstract}

This paper introduces a framework for Planning while Learning where an
agent is given a goal to achieve in an environment whose behavior is
only partially known to the agent.

We discuss the tractability of various plan-design processes. We show
that for a large natural class of Planning while
Learning systems, a plan can be presented and verified in a
reasonable time. However, coming up
algorithmically with a plan, even for simple classes of systems is
apparently intractable.

We emphasize the role of off-line plan-design 
processes, and show that, in most natural cases, the verification
(projection) part can be carried out in an efficient algorithmic
manner.

\end{abstract}

\section{Introduction}

Suppose you find yourself in a complex
labyrinth, with no recollection as to what brought you there
or how to get out. You do have some knowledge as to the possible
outcomes of your actions (e.g.,  gravitation works as usual). However,
several basic characteristics of your surrounding are unknown (e.g.,
the map of the labyrinth, or where you are in it). Your goal is to
plan your way out of there while learning enough facts
about your surroundings to enable that goal.

%\subsection{The Model}

The above example is a special case of the following general setting: An
{\em agent} ${\cal P}$ operating in an {\em environment}, 
is trying to achieve a
given goal.
At each point in time,  the agent is in a specific state. The agent 
can be fully described by  a decision procedure,
which determines the next action to be taken, 
as a function of its history of  states. 
 An environment is taken to have 
%  An agent is taken to have a (physical) state% 
%\footnote{The state includes the agent observations at a particular 
%point, but not its whole local (mental) state. This is crucial for 
%having a succinct representation.}, 
% and a decision procedure,
%determining the next action (operator), while an environment is taken to have 
some {\em behavior}, determining, for
every state  and  action taken by the agent, the
next state that will be reached. 
 ${\cal P}$ is given a set of possible behaviors of
the environment, only one of which is the actual behavior of the specific
environment. We say that ${\cal P}$ has partial information on the behavior
of the environment. ${\cal P}$'s goal is given as a subset of the states. 
Reaching any of these states is considered a success.

%\subsubsection*{Planning for Success}

${\cal P}$'s goal is, of course, not necessarily achievable; it may be
the case that for one of the possible behaviors of the environment,
there does not exist a sequence of actions that would lead ${\cal P}$
to a success. Moreover, even if for every possible specific behavior of
the environment there exists a sequence of actions that leads ${\cal
P}$ to its goal, it may still be the case that ${\cal P}$ cannot
achieve its goal.
%For example, if the
%possible behaviors of the environment are $E_1$ and $E_2$, it may be
%the case that the only action $a$ that leads $A$ to its goal in the
%case that the environment follows the behavior $E_1$, leads in the
%case that the environment behaves according to $E_2$, to a state from
%which the goal is not achievable.
For example, consider an environment with two possible behaviors $E_1$ 
and $E_2$. It may be the case that the only action $a$ that leads ${\cal P}$
to its goal when the environment follows $E_1$, leads
to a state from which the goal
is not achievable if the environment behaves according to $E_2$. 

%\subsubsection*{Planning while Learning}

Nevertheless, even in the case in which ${\cal P}$'s knowledge 
 of the environment is not complete, it may sometimes be
possible for ${\cal P}$ to achieve its goal. Suppose that we change the above
example so that there exists an action $c$ that, if taken by ${\cal P}$, leads
in the case that the environment behaves according to $E_1$, to a
state which is observably different from the state that results from
the same action ($c$) taken when the environment behaves according to
$E_2$.  In addition, suppose that there exists an action $d$ that, in both
cases, reverses $c$'s effects.  In this case, ${\cal P}$ can always achieve
its goal, by following the following {\em plan}: first take $c$, and,
according to the resulting state decide whether the environment
behaves according to $E_1$ or according to $E_2$. Then, take 
action $d$ to get back to the initial state. Finally, apply the
applicable sequence of actions for either the $E_1$ or the $E_2$ case.


In general, ${\cal P}$ may perform some actions that reduce 
%*** down???
 the number of possible
behaviors of the environment (i.e., 
increase the knowledge that ${\cal P}$ has on the
environment), while avoiding actions that may lead to failure in any of the
still possible behaviors of the
environment, according to ${\cal P}$'s knowledge. 
${\cal P}$ may eventually learn enough about the behavior of the
environment to choose the applicable action that leads to success.
This process is referred to as {\em Planning while Learning}.

This paper discusses the framework of Planning while Learning, while
concentrating on the {\em tractability} of finding a satisfactory plan
(i.e., a way to achieve the goal regardless of which possible behavior of the
environment is the actual one), 
or checking that a given plan is satisfactory.  The next
section defines a basic framework where Planning while Learning can be
studied. In Section~3 we discuss the computational aspects we study in
this paper. In particular, we distinguish between three 
main types of representation, 
 and between three main
computational categories. 
% ***** Planning while Learning something....
In Sections~4--5  
we classify Planning while Learning based on
these computational categories and representation types. 
%We classify Planning while Learning based on
%these computational categories and representation types. 
%We first discuss some results implied
%by previous work, and in Sections~4 and 5 we complete the picture by
%supplying additional basic results. 
In Section~6 we discuss several
extensions to our basic framework.
%and show that our results apply to
%these extended frameworks as well.  
In Section~7 we put our framework 
and results in
the perspective of related work.
 

\section{The Basic Framework}

Consider the following examples which have motivated our study. 
The first example is taken from a medical domain. 
Consider a trauma-care system, where there 
are many%
%???????
\footnote{The term ``many'' will become more concrete when we discuss 
representation types in the following section, and will be identified 
with exponential in the actual representation size.}
 observations that can be made on a patient's state.  
 Actions taken by the 
doctor may change these observations. 
%%%% check???? 
For example, the doctor may be able to observe whether the patient's blood 
pressure is high or low, and whether the patient has 
 high or low temperature. Based 
on the observations made, the doctor may need to take an action,  
which  may in turn  lead to new observations. 
Based on these new observations, the doctor may need to choose a 
subsequent
 action, and 
so on. 
%In particular, the observations of the doctor 
% (i.e. the doctor's action may change 
%the observable state). In such a system we usually 
%have a set of atomic observations (e.g., whether the blood pressure is high or
%low) that 
%is linear in the problem's input, but the number of possible
% observations (i.e. observable states which are tuples of atomic
% observations) 
% is exponential. 
There is a list of possible injuries that the patient might suffer from, but
the exact nature of the actual injury is not known apriori. Naturally, the
effects of the action taken by the doctor may depend on the actual
%%% effect(s)?????
injury of the patient. 
 The doctor needs to devise a  plan that will
take the patient from his initial observable state to a goal
state (i.e., a ``physically stable state''). The doctor can observe the
patient at each point in time, 
%%%% about????? 
and  learn facts about the actual injury (i.e., the 
actual environment behavior) during
the execution of the plan. Hence, we get a  natural situation 
where  Planning while Learning is necessary.
%%%% critical??? 

%%% check second eample ??????
Our second example is taken from a transportation domain. Let
$G=(V,E)$ be a directed graph, where the vertices denote locations in
a hostile environment. The edges denote safe routes from one location
to another, that are taken to be one-way (two-way routes are described
as a pair of one-way routes). One-way routes in this particular domain
occur as a result of the structure of the  environment and
of the vehicle used by the agent.  Uncertainty in this
transportation domain arises from the fact that there is incomplete
information about the end-point of some routes originating from some
particular locations (i.e., the map is partially unknown). 
In some cases this incomplete information concerns
only a small number of locations and routes where the number of
possible end-points of a route is also small.%
\footnote{In the sequel, small will be identified with polynomial in the 
actual representation size. In the particular application we speak about, the 
number of uncertain routes is logarithmic, while the number of possibilities
for each such route is bounded by a small constant.}
An agent moving along these routes knows the possible
alternatives for the structure of the environment and can identify
the locations it arrives at. The objective of the agent is to reach
a given target location starting from a given initial location.

%%%%% ??????????????
The above examples  are taken from real-life situations. They are
typical situations of bounded uncertainty. Similar situations occur
whenever we have to operate a machine that works in one of several
options. In many of those cases, 
the  possible observations can be stated, and
the set of possible environment behaviors can be listed; the actual behavior, 
however, may be unknown apriori.  Illuminating results
regarding these examples are implied by our study.
Nevertheless, we first have to define our basic framework.


\begin{definition}~An {\em agent-environment system} 
$M=(Q,{\cal A},{q_0},{\Gamma_M})$
 consists of a set of {\em observable 
states} $Q$, a set of {\em possible actions} ${\cal A}$, an 
{\em initial state} ${q_0} \in Q$ and {\em an actual transition function}
$\Gamma_M\colon
 Q \times {\cal A}\to Q$  that determines for each state $q\in Q$ and
action $a\in \cal A$ the  next state $q' = \Gamma_M(q, a)$.
\end{definition}

Based on the above definition we can define what a Planning while 
Learning system is. 
Notice that we associate the informal term ``behavior'' with the term
``transition function'', where the actual behavior is the actual 
transition function. 
%\newpage
\begin{definition}~A 
{\em Planning while Learning  system} $S=(M,{\cal {\gamma}})$ 
consists of an agent-environment 
system $M=(Q,{\cal A},{q_0},{\Gamma_M})$, and a set 
of {\em possible transition functions}  ${\cal {\gamma}}
=\set{E_1, ..., E_n}$, all sharing the same set of observable states $Q$, 
where the actual transition function is one of these possible transition
functions.  
\end{definition}

Notice that we used the term {\em observable states} rather than just
states. An observable state of an agent is what the agent  perceives at a
given point (e.g., its physical location) rather than its complete
state of knowledge. We assume that an agent can always distinguish between 
different observable states. The complete state of knowledge can be defined
based on the history of actions and observable 
states of the agent.  This
history is an ordered
sequence of observable states the agent visited and actions it
performed.  For example, if an agent performed an action $a$ that led from 
an observable state $s_1$ to an observable state $s_2$, and $a$
leads to $s_2$ if and only if the environment behavior is not $b$,
then we can say that the agent {\em learned} that the environment
behavior is not $b$. The agent will know that the environment does not
behave according to $b$ in the state it reaches following this
action, but this knowledge is not implied by the observable state
$s_2$!  This enables us to obtain a succinct and natural representation
of agents.  This type of
representation has already been used in  
%is general, and it is not original to us; It is the basic
%idea behind 
Rosenschein's situated automata
\cite{Ros} and in work on 
%the powerful idea of 
reasoning about knowledge \cite{HM}. 

The observable states in the transportation domain example are the
locations, and the actual transition function corresponds to the
actual routes in the environment. In the trauma care domain, the
observable states are the possible observations of the doctor, while
the actual transition function corresponds to the effects of the doctor's 
actions given the actual injury of the
patient.  In both examples the agent may reach a state where it knows
complex facts about the environment, based on the facts it learned by
acting and observing. However, these complex states need not be
represented explicitly. Further discussion of this topic can be found
 in the situated automata \cite{Ros,RosKae} and knowledge in 
distributed systems \cite{HM,Halpern} literature.

 The reader should  not  confuse our use of automata-like
structures with other common uses of it. We don't assume that an agent
acts as if it is a finite-state machine, but only that the number of
 possible observations and possible environment
behaviors it considers is finite.  The agent's decisions will be
based on its history of observations
and actions which determine
its local  state \cite{Ros,HM} and is much more
complex than its observable state. The agent's local state is
not necessarily represented explicitly. This gives succinct and useful
representations, as the ones discussed in Discrete Event Systems (DES)
\cite{RamadgeWonham} and in work in AI that incorporates uncertainty
to control-theoretic models \cite{MTUNENT}.

The above model is fundamental and some 
extensions of it will be discussed in Section~6.
Given this model, we are now able  to  define the basic problem 
in Planning while Learning.   The problem is to find
a satisfactory plan that achieves a goal given any possible behavior of the 
environment. 
This problem is further discussed 
in the following section 
and investigated in  subsequent sections.
Similar definitions hold, and similar results can be obtained,  
if we require the agent to achieve its goal only in a fraction (e.g., 90\%) 
of the possible behaviors.


\begin{definition}~Let  
$S=(M,{\cal {\gamma}})$ be a Planning while Learning system, 
where $M=(Q,{\cal A},{q_0},{\Gamma_M})$, and  ${\cal \gamma}
=\set{E_1, ..., E_n}$.
 A {\em goal} $g$ for the agent ${\cal P}$, is a subset of the states $Q$. 
 A {\em plan} for an agent is a function from 
its history of states (in $Q$) and actions (in $\cal A$)  to 
an action (in $\cal A$).  
Given a goal $g$,
a {\em satisfactory plan} is a plan that 
guarantees that the agent will 
reach a state in $g$ starting from $q_0$, under any 
possible  transition function in $\cal \gamma$. 
A plan is called {\em efficient} if the number of actions that are executed 
in a course of it is polynomially bounded (in the representation 
of the Planning while Learning system). 
\end{definition}

%%%%%% the following sentence style????
A satisfactory plan is therefore a plan in which the agent learns 
enough about the environment behavior, in order to guarantee the 
achievement of the agent's goal.
Notice that, in general, a plan might be very complex. An agent might 
arrive, in the course of its learning process, to situations where its goal 
is no longer achievable. Hence, the agent has to find a proper 
combination of learning and acting 
phases.
%%% think what is better? maybe vertices denote...????
 A satisfactory plan can be viewed as a decision tree 
where each edge is associated with a pair of an observable state 
 and an action to 
be performed in that state. 
%%%%%% maybe too dry....??????? 
This is a general 
representation of 
 conditional plans. An efficient plan will therefore
correspond to a decision tree of polynomial depth. 
Notice, however, that the size of an efficient plan may still 
be exponential. 

%Notice that the above definition assumes that  the agent's
%actions do not affect the behavior of the environment, although of
%course affect the state transition. This is typical for many situations, 
%as the ones discussed in the above example.  We will relax this assumption in
%Section~5


\section{A Computational Study}

In the previous section we defined a basic framework of Planning while
Learning, and what a satisfactory plan for an agent ${\cal P}$ is.  In this 
section and in the 
following ones we would like to consider the complexity of
finding such a plan or checking that a given plan is satisfactory.
In order to discuss the issue of complexity we need to discuss our 
measures of complexity,  and the type of representations
of Planning while Learning systems we would like to look 
at. 


\subsection{Basic Representations} 

We will distinguish between three basic Planning while Learning 
system representations: 
 

\begin{enumerate}
\item
{\bf General Representations:} Both the number of agent's 
observable states (i.e., $|Q|$)
 and the number of possible transition functions
 may be exponential%
\footnote{We will use the term exponential and polynomial with 
their standard means (i.e., polynomial and exponential in the actual 
representation size.)} 
in the size of the actual representation. 
\item 
{\bf Quasi-Moderate Representations:} The number of agent's observable states
might be exponential in the size of the system representation, but the
number of possible transition functions is at most polynomial in that
size. This is a most appealing type of representation for systems with
bounded uncertainty \cite{HV91}.

 The trauma-care
system mentioned in Section~2 is an example of a system with a quasi-moderate
representation.  In such a system we usually have a
set of atomic observations (e.g., whether the blood pressure is high or
low). The  number of atomic observations is linear in the problem's input, 
but the number of possible
observations (i.e., observable states which are tuples of atomic
observations) is exponential. The list of possible injuries that the
patient might have is usually polynomial in the problem's
input.  Hence, we get a quasi-moderate representation of a Planning
while Learning system.


\item
{\bf Moderate Representations:} Both the number of agent's observable 
states and
the number of possible transition functions is polynomial in the
representation size. This type of representation is less general than
a quasi-moderate representation, but it is still expressive and
completely non-trivial 
 as we will later discuss. The transportation domain example of the
previous section is moderately represented by a graph-like structure, 
in cases where there are at most polynomially many alternatives for the actual
structure of that graph (e.g., in a particular application, there are 
a constant number of possibilities to a logarithmic number of routes).
\end{enumerate}

In the remainder of this paper we use the term moderate 
system (\resp quasi-moderate system)  to 
refer to a moderate representation (\resp quasi-moderate representation) 
of a Planning while Learning system. 

\subsection{Basic Computational Categories} 

Given a Planning while Learning system, there are three main
computational categories that we consider.


\begin{enumerate}
\item
{\bf Intractable:} Checking whether a plan for the agent is satisfactory
is computationally hard, and may take exponential time.


In Planning while Learning systems
 that fall into this category, even the
 problem of representing the plan and 
verifying that this supplied plan is satisfactory is 
computationally intractable (i.e., either the space needed for representation 
is exponential or the verification process takes  exponential time). 

\item
{\bf Off-Line Tractable:} A satisfactory plan for the agent ${\cal P}$ has a
short representation (i.e., polynomial in the 
representation of the problem),
%%%%% , vs. ; ?????
 and checking whether a plan 
 is satisfactory can be carried out efficiently in 
polynomial time.


Systems that fall into this category may succumb to a trial and error
process, in which an intelligent designer (i.e., a  human) suggests 
some plan for solving a problem.  The suggested plan is represented and 
verified. If it fails the verification process,  then 
the exact failure is reported, 
and the designer may try to generate a new plan. 
%%%%% generates and useful????  
This trial and error process 
 is a typical solution for design problems. 
A designer is
given a specific problem, and may use her experience in suggesting a
plan. The plan should be represented and verified efficiently. If the
plan is not satisfactory, 
the efficient verification process locates the
failures and informs the designer, who may choose to 
generate a new plan,
etc. 
This approach 
was at first made explicit in the AI literature, by the seminal 
paper of McCarthy and Hayes \cite{MH} where it is referred to as 
the Missouri program. 
This approach is indeed the one used in many practical situations, 
such as the ones mentioned in the previous section. A more detailed
demonstration of that idea and further discussion can be found in
\cite{MT4,STOFFJ}. 

%\footnote{Another attractive, frequently taken, avenue of progress, for an
%intelligent designer, is to change the specification of the problem.}

Hence, in systems that fall into this category, various plans can be tried
in an off-line design process, supported by a computerized efficient
verification procedure, which hopefully results in a satisfactory plan.

\item
{\bf On-Line Tractable:} A satisfactory plan for the agent ${\cal P}$ has a
polynomial representation, that is not only efficiently verifiable, but
can be actually computed (algorithmically) in polynomial
time.

\end{enumerate}



\subsection{Basic Results} 
We would like 
to classify Planning while Learning systems based on the above 
categories. 
The following results are simple corollaries of results proved by  
Moses and Tennenholtz 
in another context \cite{TM,MTUNENT,MosheThesis}
and their proof is omitted from the body of this paper. 


\begin{enumerate} 
\item
 Given a general representation of a Planning while Learning
system, finding a satisfactory plan is PSPACE-hard. The problem 
remains PSPACE-hard even if we consider only efficient plans.
The size of the related plan may be exponential. 
\item
If we do not restrict ourselves to efficient plans, 
then finding a satisfactory plan in quasi-moderate systems 
 is PSPACE-hard. The size of the related plan may be exponential. 
\item 
Finding an efficient
 satisfactory plan in quasi-moderate Planning while Learning
systems with only one possible transition function (i.e.,
 planning with complete
information) is NP-hard. In this case, it is enough to consider 
plans of polynomial size.  
\end{enumerate}

The above results give several restrictions as to 
what we will be able to obtain 
in our study: we can not hope that finding a satisfactory plan, either 
efficient or inefficient, 
 will be (even off-line) tractable given arbitrary representations of 
Planning while Learning systems. In addition, we can not hope that 
 Planning while Learning in quasi-moderate representations will be on-line 
tractable. We remain however with several basic questions: 

\begin{enumerate}
\item Given a 
quasi-moderate representation of a Planning while Learning system,
is the problem of finding an efficient satisfactory plan
 off-line tractable? 
\item 
Given a moderate representation of 
a Planning while Learning system, is the problem of finding an 
 either efficient or arbitrary satisfactory plan tractable (either 
off-line or on-line)? 
\end{enumerate} 


We will treat moderate representations first. 
Our results regarding quasi-moderate 
representations will be a simple modification of a result regarding moderate 
representations. We would like now to show why the problem of Planning while 
Learning, even in moderate representations, is non-trivial. 

Consider an agent ${\cal P}$ who does not have
complete information on the environment behavior, i.e., there may
be more than one possible behavior of the environment. ${\cal P}$'s plan,
instead of being a sequence of actions, becomes a decision tree. 
%This
%decision tree determines an action to be taken in each vertex of the
%tree, and where each branch originating at that vertex corresponds to
%an observably distinct state reached from the previous common state as
%a reaction of the environment, according to some possible behavior,
%to the action taken at that vertex.
${\cal P}$'s action, in this case, is a function, not only of the
observable state, 
but also of the past history of ${\cal P}$. In the example mentioned
in the introduction, where ${\cal P}$ has to first take the action $c$ to
distinguish behavior $E_1$ from behavior $E_2$, ${\cal P}$'s plan has a
different branch 
%at the root (where the action $c$ is taken) 
for the
case the environment behaves according to $E_1$ and for the case it
behaves according to $E_2$.

Note that, introducing ${\cal P}$'s memory as a parameter in its plan ---
this is essentially the difference between a sequence and a decision
tree as ${\cal P}$'s plan --- may cause an exponential blow-up in the size
of that plan, and may make intractable the task of devising or
verifying a plan, even in  moderate representations. 
This holds  even when we consider efficient plans! Hence, Planning 
while Learning even in moderate systems is completely non-trivial. 



\section{Off-Line Tractability}
\label{section-good-plan}


In this section we show that given a moderate (\resp quasi-moderate)
representation of a Planning while Learning system, whenever there is
a satisfactory plan (\resp an efficient satisfactory plan) for an
agent, there is a satisfactory plan (\resp an efficient
satisfactory plan) that can be represented in polynomial space, and 
can be checked in polynomial time. As we mentioned, this is a
non-trivial fact even for moderate systems. We prove the result for
moderate systems, and then show why it is applicable for the richer
context of quasi-moderate systems.

 
The proof of our off-line tractability result will
follow from the following lemmas.




\begin{lemma}\label{lemma-bound1}~Let $P$ be a 
satisfactory plan for achieving a goal $g$, in 
a moderate Planning while Learning system
$\cal S$
 with $s$
possible behaviors (i.e., transition functions), and 
 $t$  observable states.  
 Then, there exists a satisfactory plan $P'$ for achieving $g$
in that system, 
 where the longest path of $P'$ is bounded by $s \cdot t$.


\end{lemma} 



\noindent
{\bf Proof:} If the agent ${\cal P}$ performs along any path of $P$ more than
$t$ actions without learning  anything (i.e., along $t$ actions 
the agent does not get any new information about the actual behavior), 
then it must visit  a
particular observable state twice, 
without getting any new information about the 
actual behavior,  
and therefore we can shrink $P$ by
dropping actions which took place between these visits.  We can
perform this process until there will be no sequence of $t$ actions in
which no learning occurs.

The learning of the agent is monotonic: whenever it learned something
about the environment behavior,  future
information can just make this knowledge more concrete. Since the
number of possible  behaviors is $s$, we get that a
knowledge increase can occur at most $s$ times.

Combining the above observations leads to the desired result. 
\qed

%\newpage
\begin{lemma} \label{lemma-bound2}~Let $P$ be a 
satisfactory plan, for a moderate Planning while Learning system 
$\cal S$ with $s$ possible behaviors, and where the longest path in
$P$ is of length $t$. Then, there exists a representation of $P$ (in
size polynomial in $s$ and $t$) such that verifying that $P$ is
satisfactory can be carried out in time polynomial in $s$ and $t$.
\end{lemma}

\noindent
{\bf Proof:} The concise representation $P'$ of $P$ consists of a
table, where each entry of the table corresponds to a distinct
observable history of an interaction of the agent ${\cal P}$ with the
environment, and contains an action to be taken by ${\cal P}$ for that
specific (partial) scenario.


The number of distinct entries in the table ($P'$) can be limited to
include only the plausible distinct histories (i.e., the histories which 
can be generated) for the system
$\cal S$ and the plan $P$. The number of such distinct histories is
bounded by $s$ (the number of possible behaviors of the environment)
times $t$ (the different stages in a specific interaction).

In order to verify that a plan $P'$ which is 
represented in that manner is
satisfactory, one needs to go over all possible behaviors and for
each one of them check that $P'$ leads to ${\cal P}$'s goal.  \qed

As an immediate corollary we obtain the following:

\begin{theorem}~Finding a 
satisfactory plan for any moderate Planning while Learning system 
is off-line tractable.
\end{theorem}


Consider an agent who wishes to reach his destination in the hostile 
environment of Section~2. In principle, there might be exponentially-many 
histories of observations the  agent may encounter. Nevertheless, our result
says that it is enough to consider only polynomially-many of them in order 
to specify the appropriate plan. This is most helpful for the designer; she 
will be able to represent her suggested solution in a relatively concise way. 
If the suggested solution is not satisfactory, 
this fact will be efficiently detected, and perhaps can 
be repaired.
 The problem of navigation 
in a hostile environment we mentioned above is actually solved this way. 



Notice that Lemma~\ref{lemma-bound1}
 is quite satisfactory for moderate systems. 
However, in quasi-moderate systems this Lemma is not useful, since in that 
case $t$ might be exponential in the actual representation size. 
However, 
the properties obtained by Lemma~\ref{lemma-bound1} 
can be regained
by considering efficient plans. 
For most practical purposes, we do not lose generality by restricting our 
attention to efficient plans, since a planner 
will not be able to execute 
exponentially many actions in the course of a plan.  
Given that 
Lemma~\ref{lemma-bound2} does hold for quasi-moderate representations,  
we get:  

\begin{theorem}~Given a  quasi-moderate Planning while Learning system, 
finding an efficient satisfactory plan is off-line tractable.
\end{theorem}

This result is quite satisfactory, since quasi-moderate systems are a 
rich context. For example, some architectures such as the ones discussed 
by Brooks 
 and his colleagues \cite{Brooks} can be treated as quasi-moderate systems. 
They include a polynomial number of sensors, which correspond to an 
exponential number of possible observations, and are tested against a list 
of possible environment behaviors (i.e., 
the appropriate sensor-effector mechanism
is checked for a list of environment behaviors).  
As we mentioned before, quasi-moderate systems correspond to complex 
systems where the number of possible worlds describing the 
environment is  efficiently enumerable. These constitute a rich 
and appealing family of systems \cite{HV91}. 
Our results show, for example, that the trauma-care system 
discussed in the previous section can be  built as an expert 
system that devises  the next action to be performed based 
on the history of observations by the doctor. The problem of coming up 
with the plan may not be trivial, 
but our results show 
that a concise representation of a plan which is efficiently 
verifiable does exist whenever an efficient satisfactory plan exists. 
Therefore, the effort of generating the 
appropriate plan off-line 
is worthwhile. 
%In the trauma-care domain this is accomplished 
%via expert rules.



\section{On-Line Intractability}
\label{section-hardness}






In this section we show that it is not likely that there is a general
algorithm to come up with a satisfactory 
plan for any moderate Planning while
Learning system, since just deciding whether such a plan exists is
NP-hard. We prove the result for the basic framework of 
Section~2. A similar result holds regarding efficient satisfactory plans. 
  This will imply similar results
for the case of efficient satisfactory plans in quasi-moderate Planning 
while Learning systems, and 
for the extended frameworks discussed in the following section. 

This result together with the results 
obtained in the previous section complete the classification of Planning 
while Learning discussed in Section~3. 

\begin{theorem}~Given a 
moderate Planning while Learning system, deciding whether
there exists an (arbitrary or efficient) 
 satisfactory plan for the agent ${\cal P}$ is an NP-hard
problem.
\end{theorem}

\noindent
{\bf Proof:}
Given any 3-SAT formula $\varphi$, over variables $v_1, ..., v_n$ and
consisting of clauses $c_1, ..., c_t$, we construct, in polynomial
time, a moderate Planning while Learning system ${\cal S}_\varphi$, such
that there exists a satisfactory plan for ${\cal P}$ in ${\cal S}_\varphi$ if
and only if there exists an assignment to $v_1, ..., v_n$ that
satisfies $\varphi$. Since satisfiability of a 3-SAT formula is
NP-hard, this implies that deciding whether there exists a satisfactory
plan, even for moderate systems, is an NP-hard problem. Our reduction 
will hold for the case of efficient satisfactory plans as well. 

The set of observable states $Q$, in the system $\cal
S_\varphi$, is $\set{b, q_1, ..., q_{n+t+1}}$. The possible
behaviors of the environment are $\set{E_{1, \bar0}, ..., E_{n,
\bar0}, E_{1, \bar1}, ..., E_{n, \bar1}}$ (there are $2n$ possible
behaviors).  The initial state is $q_1$.  The set of
possible actions for ${\cal P}$ is $\set{\bar0, \bar1, a_1, ..., a_7}$.
${\cal P}$'s goal is to reach the state $q_{n+t+1}$.

The state $b$ is a {\em black-whole}, where any action that ${\cal P}$ 
takes from $b$ results back at $b$ (which is an unsuccessful state).

 From any state $q_i$, $i\in\set{1, ..., n}$, in both the cases, where
${\cal P}$ takes the action $\bar1$ and the environment behaves according to
$E_{i, \bar0}$, and  where ${\cal P}$ takes the action $\bar0$ and
the environment follows the behavior $E_{i, \bar1}$, the resulting
state is $q_{n+t+1}$ (${\cal P}$'s goal). For all other behaviors, if 
${\cal P}$
takes the actions $\bar0$ or $\bar1$ from state $q_i$, the resulting
state is $q_{i+1}$.  (Taking the actions $a_1, ..., a_7$ leads to the
state $b$).

For any clause $c_j$, with each assignment (to the variables
mentioned in $c_j$) that satisfies $c_j$, we associate one of the
actions $a_1, ..., a_7$ (a clause with 3 variables has 7 satisfying
assignments to its variables). If the observable state is 
$q_{n+j}$, and ${\cal P}$ takes the action $a_k$, which is associated with an
assignment that assigns 0 (1) to variable $v_l$, and  the 
environment behaves according to $E_{l, \bar1}$ ($E_{l, \bar0}$), the
resulting state is $b$ (hence ${\cal P}$'s goal is not achievable anymore);
taking the action $a_k$ from the state $q_{n+j}$, under other possible
behaviors, leads to state $q_{n+j+1}$.

We show now that if $\varphi$ is satisfiable then there exists a
satisfactory plan for ${\cal P}$ in ${\cal S}_\varphi$.  Let $S\colon\set{1,
..., n}\to\set{0, 1}$ be an assignment to variables $v_1, ..., v_n$,
that satisfies $\varphi$. We construct a plan $P_S$ for ${\cal P}$ as
follows: in the $i\th$ step, the agent takes the action
$\bar0$ or $\bar1$ depending on the value of $S(i)$. Then, in step
$n+j$, the agent takes action $a_k$, 
that corresponds to the restriction of $S$ to
the variables that appear in $c_j$.
% is taken by ${\cal P}$ according to the
%plan $P_S$. 
It is easy to see that $P_S$ leads to success regardless 
of the actual environment behavior.

On the other hand, given a satisfactory plan $P$ for ${\cal P}$, we show there
exists an assignment $S_P$ that satisfies $\varphi$. $S_P$ is
constructed according to the first $n$ steps of $P$ (for the
behaviors that did not reach success yet) --- which must be either
$\bar0$ or $\bar1$. $S_P$ satisfies $\varphi$, otherwise there would
be a clause $c_j$, such that any assignment that satisfies $c_j$,
contradicts the assignment of $S_P$'s value to one of the variables
$v_l$, which would cause failure, on the $(n+j)\th$ step, for either
behavior $E_{l,\bar0}$ or $E_{l,\bar1}$. \qed


\section{Extending the Framework}
\label{section-more-good-plan}

The previous sections introduced and investigated a general framework
of Planning while Learning.  A major feature of
the model discussed in the previous sections is that the agent 
does not affect the environment behavior. 
This is quite natural in many applications. 
In many cases we may wish to consider a particular set of possible worlds 
(i.e., behaviors, transition functions), and there is no reason to assume they 
 may change, given that a possible world specifies a full transition 
function.  
An interesting extension results from relaxing 
 this feature. 
For example, in the transportation domain described in Section~2, 
 one may wish to consider a case where moving along a particular 
route prevents future movements along other routes. 
This is due to the fact that movements along some routes may reveal the 
agent's 
existence to an enemy and will prevent the agent's 
movement along some routes 
that are under
the enemy's  control. 
  Another  interesting extension we would like to consider 
is the case of a multi-agent system instead of a single-agent 
one. 

Both of the above extensions are  strict generalizations of our basic 
framework. Therefore, our on-line intractability results hold in  the 
extended frameworks as well. However, questions regarding off-line tractability
should be  carefully considered. We will define these extended frameworks
and investigate the off-line tractability of the related 
problems. 



\subsection{Dynamic Behaviors}
\begin{definition}~An {\em extended Planning while Learning system}  ${S_e}=
(Q,{\cal A},{q_0},B,{b_0},\Gamma_e)$ 
consists of a set of {\em observable states} $Q$, a set of {\em possible 
actions} 
${\cal A}$, an {\em initial agent's state} ${q_0} \in Q$, a set of 
{\em environment 
behaviors}  $B$,  an {\em initial environment behavior} ${b_0} \in B$, 
and a {\em global transition function} 
${\Gamma_e}\colon
 Q \times B \times {\cal A}\to Q \times B$, that determines 
for each state $q\in Q$, behavior $b \in B$,  and
action $a\in \cal A$, the next state and behavior 
$(q',b')={\Gamma_e}(q, b, a)$.
\end{definition}

Notice that  in extended Planning while Learning systems, 
the global transition function 
may change the behavior (i.e., the actual transition function) of 
the environment. 

The definition of a goal and of a satisfactory plan will remain as in the
basic framework. More specifically, we assume that  the agent does not
initially know the identity of $b_0$, but wishes to devise a plan that
will succeed regardless of the identity of $b_0$. The agent however
knows $\Gamma_e$. These assumptions will capture Planning while
Learning in the extended framework.  A moderate (\resp quasi-moderate)
extended Planning while Learning system is a Planning while Learning
system in which the number of elements in $B$ is polynomial, and the
number of elements in $Q$ is polynomial (\resp exponential) in the
size of the actual representation. The meaning of these definitions is
as in the basic Planning while Learning framework.



Unfortunately, Lemma~\ref{lemma-bound1} 
does not hold even for moderate extended Planning while Learning systems.
However, as we mentioned in Section~4, 
the properties obtained by Lemma~\ref{lemma-bound1} 
can be regained
by considering efficient plans. 
For most practical purposes, we do not lose generality by restricting our 
attention to efficient plans, since a planner 
will not be able to execute 
exponentially many actions in the course of a plan.  
As we mentioned before, 
 blow-up in the size of satisfactory plans
may still be possible, even if we restrict ourselves to efficient plans only. 
We make no assumptions about the size of the related decision 
tree.

Fortunately, Lemma~\ref{lemma-bound2} does  hold for extended 
Planning while Learning systems. The proof of this lemma for the 
extended framework is similar to its proof in 
the basic framework.  
Combining the above we get: 

\begin{theorem}~Given a 
quasi-moderate extended Planning while Learning system, 
finding an efficient satisfactory plan 
 is off-line tractable.
\end{theorem}


\subsection{Multi-Agent Systems}
   
Another interesting extension is concerned with the case 
where  there is more than one agent in the system. 
 For ease of exposition, we
will assume that there are two agents that generate actions.%
\footnote{Our discussion and results hold for any constant number of
agents.}


An interesting feature of the multi-agent case is that  an agent might 
not be familiar with the goal and the initial state 
of the other agent. Hence,  Planning while 
 Learning refers
now to the case in which an agent tries to achieve its goal while learning 
about  the behavior of the environment,  
 and about the goals and  initial states of  other agents.

\begin{definition}~A {\em multi-agent Planning while Learning system} 
 is a tuple \\
 ${S_m}=
({Q_1},{Q_2},{\cal A},{q^1_0},{q^2_0},B,{b_0},\Gamma_m)$ 
 where $Q_i$ is a set of {\em observable
states for agent} $i$, 
${\cal A}$ is a set of {\em possible actions}, ${q^i_0} \in {Q_i}$ is the 
{\em initial state of agent} $i$, 
 $B$ is a set of {\em environment behaviors},   ${b_0} \in B$ is 
an {\em initial environment behavior}, and ${\Gamma_m}\colon
 {Q_1} \times {Q_2} \times B \times {{\cal A}}^2\to {Q_1} \times {Q_2}
 \times B$ is a {\em global transition function}
 that determines 
for each pair of states ${q_1} \in {Q_1}$,${q_2} \in {Q_2}$, 
behavior $b \in B$,  and
a joint action of the agents $({a_1},{a_2}) \in {{\cal A}^2}$,  
the next observable states of the 
agents  and the next environment behavior: 
$({q_1}',{q_2}',b')={\Gamma_m}({q_1}, {q_2}, b, {a_1}, {a_2})$.
\end{definition}

Each agent has its own goal, and its plan 
is a decision tree that refers only to that agent's observable states. 
The definitions of moderate and quasi-moderate representations 
are straightforward generalizations of their definitions for extended 
Planning while Learning systems. 
In addition, 
we assume that each agent can start in one of polynomially many initial 
observable states, and may have one of polynomially many goals it might 
be required to achieve. Nevertheless, each agent may not know what the 
exact initial state of the other agent is, and what the exact goal of the 
other agent is. We are interested in satisfactory {\em multi-agent plans}.
 Formally, we have: 

\begin{definition}~Given a multi-agent Planning while Learning system, 
a {\em multi-agent  plan} is a pair of sets of plans, one 
set for each agent. Let ${Goal}_i$ denote the set of plans for agent $i$. 
A multi-agent plan is {\em satisfactory} if for each agent $i$ and 
for each possible goal $g$ 
of agent $i$, there is a plan in ${Goal}_i$, that achieves $g$ 
 starting from 
any possible initial state, regardless of the plan (in the corresponding 
${Goal}_j$) and initial state of the 
other agent, and regardless of the  initial behavior of the 
environment. An {\em efficient satisfactory multi-agent plan}
  is a satisfactory 
multi-agent plan that consists of plans which are decision trees of polynomial 
depth. 
\end{definition}

The above definition captures  intuitive situations of Planning while 
Learning in multi-agent domains. Assume for example 
that there are two forces that have to move in the hostile 
environment of Section~2. They start moving on 5AM, and need 
to reach their destinations by 9PM. 
Nevertheless, they can not be sure about the 
exact initial location of each other and about each other's destination. 
What 
the commander attempts to do in that case,  is to devise 
 a master-plan that should 
be good for all  goals, initial locations, and environment behaviors.
 This master-plan 
is the satisfactory multi-agent plan we look for. Notice that movements 
of one agent may affect the behavior of the system and the results of other 
agents' movements. It is easy to see that similar scenarios occur in the 
trauma-care example and in many other natural systems. 

%An {\em environment} $E$ consists of a set of {\em states} $Q$, a set
%of initial states $Q_0$ and a transition function 
%$\Gamma_E\colon Q \times {\cal A}\times {\cal A}\to Q$, that
%determines,  for each state $q\in Q$ and
% {\em joint action} of the agents, the {\em next state} $q' = \Gamma(q, a)$.

%A Planning while Learning {\em multi-agent system} consists of a 
%pair of agents $A_1$ and $A_2$, a set
%of possible,  environment behaviors ${\cal E}
%=\set{E_1, ..., E_n}$ all sharing the same set of states $Q$ (however
%may differ on the transition function), and a set of equivalence 
%classes (one set for each agent) ?????? (a *set* for each agent). 

%The agent $A$'s goal???????????????????


%We assume a given set of possible goals for
%each of the agents, where the number of these possible goals is
%polynomially bounded.  A satisfactory
%multi-agent plan is a pair of plans, a plan for each agent, 
% where an agent's plan  achieves any given possible 
%goal of it, for any possible initial state and 
%environment behavior (from the 
%agent's perspective) and goal
%of the other agent.

We now show that our off-line tractability result can be extended to the 
multi-agent case as well. We will use the following two lemmas. 
 

\begin{lemma}~Given a 
quasi-moderate multi-agent Planning while Learning system,
where each agent has only one goal,  
if an efficient   satisfactory multi-agent plan 
for achieving these goals exists, 
 then there exists such an efficient satisfactory multi-agent
  plan that can be encoded in polynomial
space, and be verified in polynomial time. 
\end{lemma}

\noindent
{\bf Proof:} In this case each agent knows  the goal of the 
other agent, and hence it is clear that it might learn only facts 
about the possible initial states and behaviors. 
%If the number of states is $s$ and no fact is learned 
%by any of the agents along $s$ actions, then we can shrink the 
%plan as in Lemma~\ref{lemma-bound1}. Hence, we can look only at plans with 
%polynomial depth. 

Given that there is only a polynomial number of possible initial states 
and environment behaviors,  
and given the polynomial bound on the depth of the plans, there are only 
polynomially many sequences of observations (each of which of 
polynomial length) of each agent that 
are of interest (as in Lemma~\ref{lemma-bound2}). Hence, we can encode, 
 in polynomial 
space, a decision table for each agent  mentioning only these 
sequences, and check, in polynomial time, whether it determines a 
satisfactory multi-agent plan.
\qed
%\newpage
\begin{lemma}~Given a 
quasi-moderate multi-agent Planning while Learning system $S$, 
where each agent has $n$ possible goals (where $n$ 
is polynomially bounded in the actual representation size),
  there exists a quasi-moderate 
  multi-agent Planning while Learning system 
$S'$ (where quasi-moderate refers to the actual 
  representation size of the original system $S$),
with a unique goal for each agent, such that there exists an
(efficient) satisfactory  multi-agent plan in $S'$ if and only if there exists 
an (efficient) satisfactory multi-agent plan in $S$. 
\end{lemma}

\noindent
{\bf Proof:}
$S'$ will be built as follows. The observable states of agent $i$ in
$S'$ will be the cartesian product of the observable states of agent
$i$ in $S$ with the set of states: \\
 $\{ {{start}_i},
{{observe}_{i_1}},\ldots, {{observe}_{i_n}}, {{goal}_i} \}$. The
initial state of agent $i$ in $S'$ will be taken to be the pair
consisting of its initial state in $S$ and $start_i$, and its goal is
taken to be the set of states in which $goal_i$ is a component.  The
environment in $S'$ will be a cartesian product of the behaviors in
$B$ with two sets $G_1$ and $G_2$, where $G_i$ has $n$ distinct
elements: $\{ {{g'}_{i_1}},\ldots, {{g'}_{i_n}} \}$.

 Agent $i$ will have a distinguished action, called
${observe-goal}_i$, which he must execute in its initial state. The
state transition function will be as in $S$, but when $i$ performs
${observe-goal}_i$ its ``new component'' in the cartesian product
(and only it) will change; the change will be  to ${observe}_{i_j}$ if
and only if the projection of the initial behavior on $G_i$ is  
${g'}_{i_j}$. In
addition, assume that $\{ {{g}_{i_1}},\ldots, {{g}_{i_n}} \}$ are
the possible goals for agent $i$ in $S$, then the transition function 
in $S'$ will
change the new component of the observable state to ${goal}_i$
if and only if  the new component of the environment is in state ${g'}_{i_j}$,
and a state satisfying ${g}_{i_j}$ has been reached.

The above transformation from $S$ to $S'$ makes the identity of an agent's
goal a component of the initially unknown behavior. 
However, agent $i$ and no other agent will observe its goal 
after its first action. 
It is 
easy to see that the above
transformation keeps the system quasi-moderate, and that there exists 
a satisfactory multi-agent plan in $S$ if and only if there exists such 
a plan in $S'$, where in $S'$ each agent has only one possible goal. 
\qed 

Combining the above lemmas we get: 


\begin{theorem}~Given a 
quasi-moderate multi-agent Planning while Learning system, 
finding an efficient multi-agent satisfactory plan 
is off-line tractable.
\end{theorem}


The above proof shows that Planning while Learning is off-line tractable
in  multi-agent cases such as the ones described above. 
 Given the structure of the above
lemmas, it is easy to prove similar results for other contexts where 
there is a polynomially bounded uncertainty about a multi-agent system.
For example, if we would like to find a multi-agent plan where crash 
failures of agents might occur (in that case the faulty agent might not
achieve its goal, but we require that the other agent will still be able
to achieve its goal), then  we 
can show that this 
problem is  off-line tractable, using the above techniques. 



\section{Related Work}

Early work in the area of planning was devoted to
various cases of planning with complete information
(see~\cite{ReadPlan} for many papers on that topic).  As research in
this area progressed in various directions, several independent works
observed that the assumption that a planner has complete
information is unrealistic for many situations; the sub-area that
treats that aspect of planning is usually referred to as planning in
uncertain territories.

Examples of research in this sub-area include work
concerning knowledge and action \cite{Moore,Halpern}, 
%dealing with issues like knowledge preconditions for actions and
%reasoning about knowledge,
 work on
conditional and reactive plans \cite{DeanWellman}
 and work on interleaving planning and execution 
\cite{AmbIngStill}. The reactive approach is proposed as
a tool in the  control of robots operating in
 uncertain environments, and in the design of
real-life control architectures that would be able to react in a
satisfactory manner, given unpredicted events \cite{Brooks}.
The interleaving of planning and execution may sometimes be a useful 
alternative to conditional planning. However, in many realistic 
domains there is a need to consider a whole or large portion of a plan before 
deciding on an action. This is the case in the transportation 
domain and the trauma-care domain we discussed. Nevertheless, 
we see the interleaving of execution with Planning while Learning a 
promising direction for future research. 


Research in the direction of conditional plans 
 deals with plans in which the outcome of the agent's
action may affect the next action taken by the agent.  Theoretical
work on this issue is mainly devoted to aspects of reasoning about
knowledge and action ~\cite{Moore,Halpern,MorgensternL},  
and to the logical formulation of conditional plans \cite{Ros81}. 
  Specific
mechanisms to construct conditional plans in which observable events
and tests are explicitly declared are discussed as
well \cite{Wellman}. 
These  as well as the more classical work on conditional plans
\cite{Warren}, and work  that followed and extended it in various 
directions \cite{PeotSmith,EHWDLW}
have not concentrated on general computational aspects of Planning while 
Learning. Our work does not concentrate on specific mechanisms 
for the construction of conditional plans; Rather, it concentrates 
on general computational aspects of conditional planning. 
 Some recent work has also been concerned with  computational 
aspects of conditional plans, but concentrated on 
 several natural pruning rules that 
can be used in the construction of conditional plans \cite{GenNak}.

%
%

Our approach  crystallizes 
the notion of an agent interacting with an
environment, and having to come up with a conditional plan, which would
lead to the agent's goal in every possible behavior of the environment
(possible world). We are mainly concerned with general  computational
aspects of Planning while Learning, and classify Planning while Learning 
based on several computational categories and representation types.


Another suggested approach for planning in uncertain environments,
whose applicability aroused quite a heated discussion recently, is
referred to as universal plans \cite{Schoppers}. A universal
plan is one in which the reaction of the agent to every possible
event of the environment is specified explicitly. 
 Our results isolate  general
classes of systems in which the agent's actions can
be specified explicitly  in an efficient manner, in order to
enable automatic verification. 
Furthermore, systems that do not fall into the above classes may 
be intractable even if the agent has complete information
on the environment behavior.

%On the other hand, concerning the
%applicability (or efficiency) of such an approach for general
%settings, our result imply that these problems are in general
%infeasible. However, one has to remember that these problems are as
%infeasible as the same problems in the case where the agent has
%complete information on the environment behavior.


Other somewhat related work is concerned with planning routes where
the geography is unknown  \cite{PY,MD}. For example, one may
be interested in finding a route leading from one city to another
without access to an appropriate map. This work may be viewed as a
special case of the general framework of Planning while Learning. Work on the 
design of physical part orienters (belts, panhandlers) that accept an 
object 
in one of several possible orientations and output it in a predetermined 
orientation \cite{Natar} may also be viewed as a special case of our framework.



Our work is concerned with the off-line and on-line tractability of
Planning while Learning. This  relates it to work 
concerned with the tractability of different types of
planning~\cite{ENS,Bylander}. This work mainly concentrated on on-line 
tractability of a single-agent planning  with complete information. Our work 
concentrates on general computational aspects of planning with incomplete
information, considers also multi-agent situations, and discusses both 
on-line and off-line 
tractability. Recall that off-line design and tractability, 
although considered an attractive option 
\cite{MH}, has been almost neglected in the recent years (but 
see \cite{MT4,STOFFJ}). 

Research on inference of finite-automata \cite{RS1,RS2}
assumes an agent that tries to infer the structure of an automaton.
The agent is given a limited access to the automaton, and is expected
to gain enough information to deduce the complete structure of the
automaton. By contrast, in the framework discussed in this paper, the agent
needs only gain information that would help in reaching the given goal.
Therefore, in what is probably a most natural case, the automaton is
fairly complicated, thus learning its complete structure is 
computationally infeasible. However, being only interested in a
specific goal, one may be able to obtain the necessary information,
and succeed in that goal. 
In addition, 
work on computational learning assumes that the given automaton is
fully connected, to enable reaching any state of the automaton and
eliminating the need of avoiding states from which other states are
not reachable. This assumption --- that the automaton is fully
connected --- may very well be false in many real-life applications.


The part of our work which discusses multi-agent plans is related to
issues in distributed AI \cite{BG} and to the complexity of
multi-agent planning \cite{TM}; we investigate 
the computational difficulty that arises due to uncertainty
concerning the activities of an additional agent(s).



As far as related representations are concerned, 
the model we present is different from classical representations in
the spirit of STRIPS. It is a classical Discrete Event Systems
model \cite{RamadgeWonham}.
%  An overview of such models appears in 
The general connection between planning and control theory has been 
discussed in previous work \cite{DeanWellman}. In addition, 
Tennenholtz and Moses 
show  a reduction from
control-theoretic models as the ones we  discuss to the more
classical STRIPS-like representations \cite{TM}. They show how a 
typical STRIPS-like representation 
can be reduced  to a quasi-moderate representation. 
 However, the control-theoretic representations we considered 
are conceptually different from classical planning 
models, due to the fact that they  model explicitly the possible 
observations 
of agents and the effects of actions given different environment 
behaviors, rather than 
represent general facts  about an environment. The {\em local} (or
 {\em  mental})
state of an agent, which is the general agent's state discussed in the 
AI literature \cite{Shohamaop}, will 
not be represented explicitly in our representation and will be built 
implicitly based on the agent's actions and observations. Hence, the most 
appropriate similar model of knowledge representation in AI is the situated 
automata \cite{Ros}. 
Notice that, in general,  the number of local states an agent might reach 
is exponential in the number of its observable states. 


%Starting from the early days of
%AI, work in the field noticed the importance of learning in order to
%support successful planning \cite{Nilsson}.
%
%Work in AI (see \cite{MD}) and in theoretical computer science (see
%\cite{PY}) have been concerned with planning routes through uncertain
%territories.
%
%Planning while learning is a general computational
%framework where the related issues of goal achievement in face
%of uncertainty can be investigated.

%Some works are also concerned
%with the notion of knowledge and with reasoning about knowledge
%(\cite{Moore}, \cite{HM}). Knowledge plays a major role in planning
%while learning. In planning while learning we are interested in a
%computational study of how to
%acquire knowledge and to use it in an efficient way
% in order to enable agents to achieve their goals.

\section{Conclusions}~\label{section-discussion}
A useful planning system needs to have three essential properties.
First, it should supply a mechanism for the generation of plans.
Second, it should supply a concise way for representing plans. Third,
it should supply an efficient mechanism for the verification of plans
or for testing candidate plans.

In this paper we concentrate on planning in uncertain territory,
where the agent has only partial information on the environment
behavior. We show that it is intractable to build a useful
planning system even for moderate representations (i.e., representations in
which the number of observable states and possible behaviors is
polynomial in the actual representation size). However, our positive
results show that it is possible, in moderate and quasi-moderate 
representations (where the number of observable states might be exponential),
 to satisfy the 2nd and 3rd properties mentioned
above. Hence, off-line design becomes tractable, as discussed and
demonstrated in the paper.

%Assuming an intelligent designer that is able to come up with a plan,
%we can supply her with a concise way for representing that plan, and a
%computational mechanism to verify the plan (this enables a trial<
%and error procedure).

%On the other hand, we show that coming up with a plan, on-line, is
%apparently computationally hard. This emphasizes the importance of
%off-line design.

Notice that if we consider quasi-moderate systems and efficient plans, 
which  is a most natural situation, 
our results imply that Planning while Learning is as efficient as planning 
with complete information. Both are off-line tractable and on-line 
intractable.  However, in moderate systems, planning with 
complete information is quite trivial (this is the case of graph search 
\cite{AHU}), 
while in that case we show that Planning while Learning is NP-hard. 
More generally, we obtain a complete classification of Planning while 
Learning systems based on several representation types and computational 
categories. In addition, we discuss extensions of Planning while 
Learning,  such as Planning while Learning in multi-agent domains. 

%A possible interpretation of our results may be concerned with a fully
%automatic (on-line) plan-design process, that makes use of some
%special heuristics or hardware. Our results show that the main problem
%to be concerned with, in that framework, is the generation of plans,
%while testing candidate plans can be carried out quite efficiently.

%The positive results obtained in this paper, refer to moderate
%environments.  If one is interested in plans of polynomial length,
%then our results can be generalized in order to include non-moderate
%environments as well. The only property required of the settings to
%support this statement is that the number of 
% behaviors of the environment be moderate. In that case,
%Lemma~\ref{lemma-bound1}  holds, and we are able to prove
%Lemma~\ref{lemma-bound2} in a similar way to the one described
%above.

The framework of Planning while Learning is a general framework where
planning in uncertain territory can be studied. The introduction of
this framework, and the related (positive and negative) results,
facilitate that study.
 
\section*{Acknowledgements}
We would like to thank Dan Weld, and three anonymous reviewers, for their 
helpful comments.    


\begin{thebibliography}{}

\bibitem[\protect\BCAY{Aho, Hopcroft, \BBA\ Ullman}{Aho et~al.}{1974}]{AHU}
Aho, A.~V., Hopcroft, J.~V., \BBA\ Ullman, J. \BBOP1974\BBCP.
\newblock {\Bem {The Design and Analysis of Computer Algorithms}}.
\newblock Addison-Wesley Publishing Company.

\bibitem[\protect\BCAY{Allen, Hendler, \BBA\ Tate}{Allen
  et~al.}{1990}]{ReadPlan}
Allen, J., Hendler, J., \BBA\ Tate, A.\BEDS. \BBOP1990\BBCP.
\newblock {\Bem Readings in Planning}.
\newblock Morgan Kaufmann Publishers.

\bibitem[\protect\BCAY{Ambros-Ingerson \BBA\ Steel}{Ambros-Ingerson \BBA\
  Steel}{1988}]{AmbIngStill}
Ambros-Ingerson, J.\BBACOMMA\  \BBA\ Steel, S. \BBOP1988\BBCP.
\newblock \BBOQ {Interleaving Planning, Execution and Monitoring}\BBCQ\
\newblock In {\Bem Proceedings of AAAI-88}, \BPGS\ 83--88.

\bibitem[\protect\BCAY{Bond \BBA\ Gasser}{Bond \BBA\ Gasser}{1988}]{BG}
Bond, A.~H.\BBACOMMA\  \BBA\ Gasser, L. \BBOP1988\BBCP.
\newblock {\Bem {Readings in Distributed Artificial Intelligence}}.
\newblock Ablex Publishing Corporation.

\bibitem[\protect\BCAY{Brooks}{Brooks}{1986}]{Brooks}
Brooks, R.~A. \BBOP1986\BBCP.
\newblock \BBOQ {A Robust Layered Control System for a Mobile Robot}\BBCQ\
\newblock {\Bem IEEE Journal of Robotics and Automation}, {\Bem 2}, 14--23.

\bibitem[\protect\BCAY{Bylander}{Bylander}{1992}]{Bylander}
Bylander, T. \BBOP1992\BBCP.
\newblock \BBOQ {Complexity Results for Serial Decomposability}\BBCQ\
\newblock In {\Bem Proceedings of AAAI-92}, \BPGS\ 729--734.

\bibitem[\protect\BCAY{Dean \BBA\ Wellman}{Dean \BBA\
  Wellman}{1991}]{DeanWellman}
Dean, T.~L.\BBACOMMA\  \BBA\ Wellman, M.~P. \BBOP1991\BBCP.
\newblock {\Bem {Planning and Control}}.
\newblock Morgan Kaufmann Publishers.

\bibitem[\protect\BCAY{Erol, Nau, \BBA\ Subrahmanian}{Erol et~al.}{1992}]{ENS}
Erol, K., Nau, D., \BBA\ Subrahmanian, V. \BBOP1992\BBCP.
\newblock \BBOQ {On the Complexity of Domain-Independent Planning}\BBCQ\
\newblock In {\Bem Proceedings of AAAI-92}, \BPGS\ 381--386.

\bibitem[\protect\BCAY{Etzioni, Hanks, Weld, Draper, Lesh, \BBA\
  Williamson}{Etzioni et~al.}{1992}]{EHWDLW}
Etzioni, O., Hanks, S., Weld, D., Draper, D., Lesh, N., \BBA\ Williamson, M.
  \BBOP1992\BBCP.
\newblock \BBOQ {An Approach to Planning with Incomplete Information}\BBCQ\
\newblock In {\Bem Proceedings of the 3rd Conference on Principles of Knowledge
  Representation and Reasoning}, \BPGS\ 115--125.

\bibitem[\protect\BCAY{Genesereth \BBA\ Nourbakhsh}{Genesereth \BBA\
  Nourbakhsh}{1993}]{GenNak}
Genesereth, M.\BBACOMMA\  \BBA\ Nourbakhsh, I.~R. \BBOP1993\BBCP.
\newblock \BBOQ {Time Saving Tips for Problem Solving with Incomplete
  Information}\BBCQ\
\newblock In {\Bem Proceedings of AAAI-93}.

\bibitem[\protect\BCAY{Halpern \BBA\ Moses}{Halpern \BBA\ Moses}{1984}]{HM}
Halpern, J.\BBACOMMA\  \BBA\ Moses, Y. \BBOP1984\BBCP.
\newblock \BBOQ Knowledge and common knowledge in a distributed
  environment\BBCQ\
\newblock \BTR\ RJ 4421, IBM.

\bibitem[\protect\BCAY{Halpern}{Halpern}{1988}]{Halpern}
Halpern, J.~Y. \BBOP1988\BBCP.
\newblock \BBOQ Reasoning about knowledge: An overview\BBCQ\
\newblock In {\Bem Theoretical Aspects of Reasoning About Knowledge:
  Proceedings of the 1988 conference}, \BPGS\ 1--17.

\bibitem[\protect\BCAY{Halpern \BBA\ Vardi}{Halpern \BBA\ Vardi}{1991}]{HV91}
Halpern, J.~Y.\BBACOMMA\  \BBA\ Vardi, M.~Y. \BBOP1991\BBCP.
\newblock \BBOQ Model checking vs.~theorem proving:~a manifesto\BBCQ\
\newblock In {\Bem Principles of Knowledge Representation and Reasoning:
  Proceedings of the Second International Conference}, \BPGS\ 325--334.

\bibitem[\protect\BCAY{McCarthy \BBA\ Hayes}{McCarthy \BBA\ Hayes}{1969}]{MH}
McCarthy, J.\BBACOMMA\  \BBA\ Hayes, P. \BBOP1969\BBCP.
\newblock \BBOQ {Some Philosophical Problems from the Standpoint of Artificial
  Intelligence}\BBCQ\
\newblock {\Bem Machine Intelligence}, {\Bem 4}, 463--502.

\bibitem[\protect\BCAY{Mcdermott \BBA\ Davis}{Mcdermott \BBA\ Davis}{1984}]{MD}
Mcdermott, D.\BBACOMMA\  \BBA\ Davis, E. \BBOP1984\BBCP.
\newblock \BBOQ {Planning Routes Through Uncertain Territory}\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 22}.

\bibitem[\protect\BCAY{Moore}{Moore}{1980}]{Moore}
Moore, R.~C. \BBOP1980\BBCP.
\newblock \BBOQ {Reasoning about Knowledge and Action}\BBCQ\
\newblock \BTR\ 191, SRI International.

\bibitem[\protect\BCAY{Morgenstern}{Morgenstern}{1987}]{MorgensternL}
Morgenstern, L. \BBOP1987\BBCP.
\newblock \BBOQ {Knowledge Preconditions for Actions and Plans}\BBCQ\
\newblock In {\Bem Proceedings of the 10th International Joint Conference on Artificial
  Intelligence}, \BPGS\ 867--874.

\bibitem[\protect\BCAY{Moses \BBA\ Tennenholtz}{Moses \BBA\
  Tennenholtz}{1991}]{MTUNENT}
Moses, Y.\BBACOMMA\  \BBA\ Tennenholtz, M. \BBOP1991\BBCP.
\newblock \BBOQ {Cooperation in Uncertain Territory Using a Multi-Entity
  Model}\BBCQ\
\newblock In Bruckstein, A.\BBACOMMA\  \BBA\ Feldman, Y.\BEDS, {\Bem Artificial
  Intelligence and Computer Vision}. Elsevier Science.

\bibitem[\protect\BCAY{Moses \BBA\ Tennenholtz}{Moses \BBA\
  Tennenholtz}{1993}]{MT4}
Moses, Y.\BBACOMMA\  \BBA\ Tennenholtz, M. \BBOP1993\BBCP.
\newblock \BBOQ {Off-Line Reasoning for On-Line Efficiency}\BBCQ\
\newblock In {\Bem Proceedings of the 13th International Joint Conference on Artificial
  Intelligence}.

\bibitem[\protect\BCAY{Natarajan}{Natarajan}{1986}]{Natar}
Natarajan, K. \BBOP1986\BBCP.
\newblock \BBOQ {An Algorithmic Approach to the Automatic Design of Parts
  Orienters}\BBCQ\
\newblock In {\Bem Proceedings of the 27th IEEE Symp. on Foundations of Computer Science},
  \BPGS\ 132--142.

\bibitem[\protect\BCAY{Papadimitriou \BBA\ Yannakakis}{Papadimitriou \BBA\
  Yannakakis}{1989}]{PY}
Papadimitriou, C.\BBACOMMA\  \BBA\ Yannakakis, M. \BBOP1989\BBCP.
\newblock \BBOQ {Shortest Paths Without a Map}\BBCQ\
\newblock In {\Bem Automata, Languages and Programming. 16th International
  Colloquium Proceedings}, \BPGS\ 610--620.

\bibitem[\protect\BCAY{Peot \BBA\ Smith}{Peot \BBA\ Smith}{1992}]{PeotSmith}
Peot, M.~A.\BBACOMMA\  \BBA\ Smith, D. \BBOP1992\BBCP.
\newblock \BBOQ {Conditional Nonlinear Planning}\BBCQ\
\newblock In {\Bem Proceedings of the 1st International Conference on AI
  Planning Systems}, \BPGS\ 189--197.

\bibitem[\protect\BCAY{Ramadge \BBA\ Wonham}{Ramadge \BBA\
  Wonham}{1989}]{RamadgeWonham}
Ramadge, P.\BBACOMMA\  \BBA\ Wonham, W. \BBOP1989\BBCP.
\newblock \BBOQ {The Control of Discrete Event Systems}\BBCQ\
\newblock {\Bem Proceedings of the IEEE}, {\Bem 77\/}(1), 81--98.

\bibitem[\protect\BCAY{Rivest \BBA\ Schapire}{Rivest \BBA\
  Schapire}{1987}]{RS1}
Rivest, R.~L.\BBACOMMA\  \BBA\ Schapire, R.~E. \BBOP1987\BBCP.
\newblock \BBOQ {Diversity-Based Inference of Finite Automata}\BBCQ\
\newblock In {\Bem Proceedings of the 28th IEEE Symp. on Foundations of Computer Science},
  \BPGS\ 78--87.

\bibitem[\protect\BCAY{Rivest \BBA\ Schapire}{Rivest \BBA\
  Schapire}{1989}]{RS2}
Rivest, R.~L.\BBACOMMA\  \BBA\ Schapire, R.~E. \BBOP1989\BBCP.
\newblock \BBOQ {Inference of Finite Automata Using Homing Sequences}\BBCQ\
\newblock In {\Bem Proceedings of the 21th ACM Symp. on Theory of Computing}, \BPGS\
  411--420.

\bibitem[\protect\BCAY{Rosenschein}{Rosenschein}{1985}]{Ros}
Rosenschein, S.~J. \BBOP1985\BBCP.
\newblock \BBOQ {Formal Theories of Knowledge in AI and Robotics}\BBCQ\
\newblock {\Bem New Generation Computing}, {\Bem 3\/}(3), 345--357.

\bibitem[\protect\BCAY{Rosenschein \BBA\ Kaelbling}{Rosenschein \BBA\
  Kaelbling}{1986}]{RosKae}
Rosenschein, S.~J.\BBACOMMA\  \BBA\ Kaelbling, L.~P. \BBOP1986\BBCP.
\newblock \BBOQ {The synthesis of digital machines with provable epistemic
  properties}\BBCQ\
\newblock In {\Bem Proceedings of the Conference on Theoretical Aspects of
  Reasoning about Knowledge}, \BPGS\ 83--98.

\bibitem[\protect\BCAY{Rosenschein}{Rosenschein}{1981}]{Ros81}
Rosenschein, S. \BBOP1981\BBCP.
\newblock \BBOQ {Plan Synthesis: A logical Perspective}\BBCQ\
\newblock In {\Bem Proceedings of the  7th International Joint Conference on Artificial
  Intelligence}.

\bibitem[\protect\BCAY{Schoppers}{Schoppers}{1987}]{Schoppers}
Schoppers, M. \BBOP1987\BBCP.
\newblock \BBOQ {Universal Plans for Reactive Robots in Unpredictable
  Environments}\BBCQ\
\newblock In {\Bem Proceedings of of AAAI-87}, \BPGS\ 1039--1046.

\bibitem[\protect\BCAY{Shoham \BBA\ Tennenholtz}{Shoham \BBA\
  Tennenholtz}{1994}]{STOFFJ}
Shoham, Y.\BBACOMMA\  \BBA\ Tennenholtz, M. \BBOP1994\BBCP.
\newblock \BBOQ {Social Laws for Artificial Agent Societies: Off-line
  Design}\BBCQ\
\newblock To appear in AI journal.

\bibitem[\protect\BCAY{Shoham}{Shoham}{1990}]{Shohamaop}
Shoham, Y. \BBOP1990\BBCP.
\newblock \BBOQ {Agent Oriented Programming}\BBCQ\
\newblock \BTR\ STAN-CS-1335-90, Dept. of Computer Science, Stanford
  University.

\bibitem[\protect\BCAY{Tennenholtz}{Tennenholtz}{1991}]{MosheThesis}
Tennenholtz, M. \BBOP1991\BBCP.
\newblock {\Bem Efficient Representation and Reasoning in Multi-Agent Systems}.
\newblock Ph.D.\ thesis, Weizmann Institute, Israel.

\bibitem[\protect\BCAY{Tennenholtz \BBA\ Moses}{Tennenholtz \BBA\
  Moses}{1989}]{TM}
Tennenholtz, M.\BBACOMMA\  \BBA\ Moses, Y. \BBOP1989\BBCP.
\newblock \BBOQ {On Cooperation in a Multi-Entity Model}\BBCQ\
\newblock In {\Bem Proceedings of the 11th International Joint Conference on Artificial
  Intelligence}.

\bibitem[\protect\BCAY{Warren}{Warren}{1976}]{Warren}
Warren, D. H.~D. \BBOP1976\BBCP.
\newblock \BBOQ {Generating Conditional Plans and Programs}\BBCQ\
\newblock In {\Bem Proceedings of the Summer Conference on AI and Simulation of
  Behavior, Edinburgh}.

\bibitem[\protect\BCAY{Wellman}{Wellman}{1990}]{Wellman}
Wellman, M.~P. \BBOP1990\BBCP.
\newblock {\Bem {Formulation of Tradeoffs in Planning Under Uncertainty}}.
\newblock Pitman, London.

\end{thebibliography}

%\bibliography{bib}
%\bibliographystyle{theapa}

\end{document}


