\documentclass[twoside,11pt]{article}
\usepackage{times}
\usepackage{jair}
\usepackage{graphicx}
\usepackage{rpl}
\usepackage{pst-node,pstricks}
\usepackage{amssymb,amsmath}
\usepackage{theapa}
\usepackage{latexsym}
\usepackage{ha}
\usepackage[scaled=0.90]{helvet}

% \documentclass[jair,11pt]{article}
% \usepackage{theapa}
% \usepackage{times,graphicx,rpl}
% \usepackage{pstricks,pst-node,ha}
% \usepackage{amssymb,amsmath,latexsym}

\newcommand{\dtc}{{$dt_{clock}$}}
\newcommand{\dtcm}{{dt_{clock}}}
\newcommand{\xypos}[2]{(#1,#2)}
\newcommand{\Pm}[1]{$#1$}
\newcommand{\Po}[1]{{\sc $#1$}}
\newcommand{\bm}[1]{\mathbf{\boldsymbol{#1}}}
\newcommand{\rc}[1]{\textit{#1}}
\newcommand{\term}[1]{\textsf{\textsc{#1}}}
\newcommand{\nonterm}[1]{\textit{\textrm{#1}}}
\newcommand{\pos}[2]{$\langle$#1,#2$\rangle$}
\newcommand{\loc}[2]{$\langle$#1,#2$\rangle$}
\newcommand{\predicate}[2]{\textsf{\textsc{#1}(#2)}}
\newcommand{\src}{\textsc{src}}
\newcommand{\crp}{\textsc{crp}}
\newcommand{\ppsd}{\textsc{ppsd}}
\newcommand{\pham}{\textsc{pham}}
\newcommand{\rpl}{\textsc{rpl}}
\newcommand{\rhino}{\textsc{rhino}}
\newcommand{\xfrm}{\textsc{xfrm}}
\newcommand{\myem}[1]{\textbf{\textit{#1}}}
\newcommand{\mathloc}[2]{\langle #1,#2 \rangle}

\def\algkey#1{\mbox{\textit{\textsf{\underline{#1}}}\ }}

\renewcommand{\myem}[1]{\textit{\textbf{#1}}}

\newtheorem{Lemma}{Lemma}
\newtheorem{Theorem}{Theorem}
\newtheorem{Def}{Definition}

\newcommand{\da}{{\downarrow}}
\newcommand{\ua}{{\uparrow}}
\newcommand{\gdw}{{$\Longleftrightarrow$}}
\newcommand{\eprule}[4]{{$#1/#2$$\stackrel{#3}{\rightarrow}$$#4$}}

\newcommand{\todo}[1]{\begin{center} \textbf{\fbox{todo: #1}} \end{center}}
\newcommand{\pprule}[2]{
  {($#1\ \mbox{\cl{p<-p}}\ #2$)}}

\newcommand{\perule}[3]{{$#1$$\stackrel{#2}{\rightarrow}$$#3$}}

\newcommand{\non}[1]{
  {\overline{#1}}}

\newcommand{\xfrmrule}[2]{
  {\noindent {\bf Regel #1:} #2
    \label{rule:#1}
    }}

\newenvironment{code-example}[1]%
{\begin{center}
  \begin{minipage}{#1}
    \begin{footnotesize}
      \begin{sf}
        \begin{tabbing}}%
{\end{tabbing}
      \end{sf}
    \end{footnotesize}
  \end{minipage}
\end{center}}

\makeatletter

\jairheading{24}{2005}{799-849}{08/04}{12/05}
\ShortHeadings{Probabilistic Hybrid Action Models}
{Beetz \& Grosskreutz}
\firstpageno{799}

\begin{document}

\title{Probabilistic Hybrid Action Models \\
  for Predicting Concurrent Percept-driven Robot Behavior}

\author{\name Michael Beetz \email beetz@in.tum.de \\
  \addr Department of Computer Science IX, Technische Universit\"at
  M\"unchen, \\ 
  Boltzmannstr.\ 3, D-81667 Garching, Germany, \\
  \name Henrik Grosskreutz \email grosskreutz@cs.rwth-aachen.de\\
  \addr Department of Computer Science, Aachen University of Technology\\
  D-52056 Aachen, Germany}

\maketitle

\begin{abstract}
  This article develops \myem{Probabilistic Hybrid Action Models
    (\pham s)}, a realistic causal model for predicting the behavior
  generated by modern percept-driven robot plans.  \pham s represent
  aspects of robot behavior that cannot be represented by most action
  models used in AI planning: the temporal structure of continuous
  control processes, their non-deterministic effects, several modes of
  their interferences, and the achievement of triggering conditions in
  closed-loop robot plans.

  The main contributions of this article are: (1)~\pham s, a model of
  concurrent percept-driven behavior, its formalization, and proofs
  that the model generates probably, qualitatively accurate
  predictions; and (2)~a resource-efficient inference method for \pham
  s based on sampling projections from probabilistic action models and
  state descriptions. We show how \pham s can be applied to planning
  the course of action of an autonomous robot office courier based on
  analytical and experimental results.
\end{abstract}

\bibliographystyle{theapa}


\section{Introduction}
\label{sec:intro}

Most autonomous robots are equipped with restricted, unreliable, and
inaccurate sensors and effectors and operate in complex and dynamic
environments.  A successful approach to deal with the resulting
uncertainty is the use of controllers that prescribe the robots'
behavior in terms of \textit{concurrent reactive plans (CRPs)} ---
plans that specify how the robots are to react to sensory input in
order to accomplish their jobs reliably
\cite<e.g.,>{McD92Rob,Bee99Str}.  Reactive plans are successfully used
to produce situation specific behavior, to detect problems and recover
from them automatically, and to recognize and exploit opportunities
(Beetz et al., \citeyearR{Bee01Int}).  These kinds of behaviors are
particularly important for autonomous robots that have only uncertain
information about the world, act in dynamically changing environments,
and are to accomplish complex tasks efficiently.

Besides reliability and flexibility, foresight is another important capability
of competent autonomous robots \cite{McD92Rob}.  Temporal projection, the
computational process of predicting what will happen when a robot executes its
plan, is essential for the robots to plan their intended courses of action
successfully. To be able to project their plans, robots must have causal
models that represent the effects of their actions. Most robot action planners
use representations that include discrete action models and plans that define
partial orders on actions. Therefore, they cannot automatically generate,
reason about, and revise modern reactive plans. This has two important
drawbacks. First, the planners cannot accurately predict and diagnose the
behavior generated by their plans because they abstract away from important
aspects of reactive plans.  Second, the planners cannot exploit the control
structures provided by reactive plan languages to make plans more flexible and
reliable.

In this article we develop \myem{\pham s} (Probabilistic Hybrid Action
Models), action models that have the expressiveness for the accurate
prediction of behavior generated by concurrent reactive plans.  To the
best of our knowledge, \pham s are the only action representation used
in action planning that provides programmers with means for describing
the interference of simultaneous, concurrent effects, probabilistic
state and action models, as well as exogenous events. \pham s have
been successfully applied by an autonomous robot office courier and a
museum tour-guide robot to make predictions of full-size robot plans
during the execution of these plans \cite{Bee01Str}.

This article makes several important contributions to the area of
decision-theoretic robot action planning. First, we describe \pham s,
formal action models that allow for the prediction of the qualitative
behavior generated by concurrent reactive plans. Second, we show how
\pham s can be implemented in a resource efficient way such that
predictions based on \pham s can be performed by robots while
executing their plans. Third, we apply the plan projection method to
probabilistic prediction-based schedule debugging and analyze it in
the context of a robot office courier \cite{Bee01Str}.

Before starting with the technical part of the article we would like
to make several remarks. In this article we restrict ourselves to
navigation actions and model them exactly as they are implemented in
one of the most successful autonomous robot navigation systems
\shortcite{Bur00Exp}. The reason is that we want to close the gap
between action models used in AI planning systems and the control
programs that are used by autonomous robots and the behavior they
produce. The control programs that we model have proven themselves to
achieve reliable, high performance navigation behavior. In the Minerva
experiment, they controlled the navigation in a crowded museum for
more than 93~hours.  During their execution, the navigation plans have
been revised by a planning module about 3200~times without causing any
deadlocks between interacting, concurrent control processes
\cite{Bee02Pla,Bee01Int}. In robot office courier experiments, we have
applied plan revision methods that enabled the robot to plan ahead for
about 15-25 minutes. We consider this to be a time scale sufficient
for improving the robot's performance through planning.  However, the
performance gains that can in principle be achieved through navigation
planning are often small compared to those that can be achieved by
planning manipulation tasks.

Although we use navigation as our only example, the same modeling
techniques apply to other mechanisms of autonomous robots, such as
vision \shortcite{Bee98Tra}, communication \cite{Bee98Str}, and
manipulation \cite{Bee00Con} equally well. The reasons that we do not
cover these kinds of actions in this article are that they require
additional reasoning capabilities and at the moment these models can
only be validated with respect to robot simulations. The additional
robot capabilities that would have to be modeled include symbol
grounding/object recognition \cite{Bee00Con}, changing states of
objects, and more thorough models of the belief states of robots
\shortcite{Schmitt02CPS}.  Addressing these issues is well beyond the
scope of this article.

In the remainder of the article we introduce the basic
conceptualization underlying \pham s and describe two realizations of
them: one for studying their formal properties and another one
targeted at their efficient implementation.  We also show how \pham s
are employed in the context of transformational robot planning.

The article is organized as follows.  Section~\ref{sec:example-plans}
describes everyday activity as our primary class of application
problems. We introduce concurrent reactive plans (CRPs) as means for
producing characteristic patterns of everyday activity and identify
technical problems in the prediction of the physical robot behavior
that CRPs generate.  Section~3 explains how the execution of CRPs and
the physical and computational effects of plan execution can be
modeled using \pham s. \pham s describe the behavior of the robot as a
sequence of control modes where in each mode the continuous behavior
is specified by a control law. Mode transitions are triggered by the
controlled system satisfying specified mode transition conditions. We
then introduce a set of predicates that we use to represent our
conceptualization formally.  Section~4 and 5 describe two different
approaches to predicting the behavior produced by concurrent reactive
plans in the context of \pham s.  In the first one the behavior is
approximated by discretizing time into a sequence of clock ticks that
can be made arbitrarily dense. This model is used to derive formal
properties for the projection of concurrent reactive plans.  The
second approach, described in Section~5, describes a much more
efficient approach to the projection of CRPs.  In this approach only
those time ticks are explicitly considered and represented where
discrete events may occur. At all other time instances the system
state can be inferred through interpolation using the control laws of
the respective modes.  This is the projection mechanism that is used
at execution time on board the robots. We show how this implementation
of \pham s is employed for prediction-based tour scheduling for an
autonomous robot office courier.  We conclude with an evaluation and a
discussion of related work.


\section{Structured Reactive Controllers and the Projection of Delivery
  Tour Plans}
\label{sec:example-plans}

Plan-based robot control has been successfully applied to tasks such
as the control of space probes \shortcite{Mus98Rem}, disaster
management and surveillance \shortcite{doherty00witas}, and the
control of mobile robots for office delivery
\shortcite{Sim97Mod,Bee01Int} and tourguide scenarios
\shortcite{Ala00Aro,Thr00Prob}. A class of tasks that has received
little attention is the plan-based robot control for everyday activity
in human living and working environments, tasks that people are
usually very good at.

To get a better intuition of the activity patterns to be produced in
everyday activity, let us consider the chores of a hypothetical
household robot.  Household chores entail complex routine jobs such
as cooking dinner, cleaning the kitchen, loading the dish washer, etc.
The routine jobs are typically performed in parallel. A household
robot might have to clean up the living room while the soup is cooking
on the stove. While cleaning up, the phone might ring and the robot
has to interrupt cleaning in order to go and answer the phone.  After
having completed the telephone call the robot has to continue cleaning
right where it stopped. Thus, the robot's activity must be concurrent,
percept-driven, interruptible, flexible, and robust, and it requires
foresight.

The fact that people manage and execute their daily tasks effectively
suggests, in our view, that the nature of everyday activity should
permit agents to make assumptions that simplify the computational
tasks required for competent activity. As \citeA{Hor96Int} puts it,
everyday life must provide us with some loopholes, structures and
constraints that make activity tractable.

We believe that in many applications of robotic agents that are to
perform everyday activities, the following assumptions are valid and
allow us to simplify the computational problems of controlling a robot
competently:

\begin{enumerate}

\item Robotic agents are familiar with the activities for satisfying
  individual tasks and the situations that typically occur while performing
  them. They carry out everyday activities over and over again and are
  confronted with the same kinds of situations many times. As a consequence,
  conducting individual everyday activities can be learned from experience and
  is simple in the sense that it does not require a lot of plan generation
  from first principles.

\item Appropriate plans for satisfying multiple, possibly interfering, tasks
  can be determined in a greedy manner. The robot can first determine a
  default plan performing the individual tasks concurrently with some
  additional ordering constraints through simple and fast heuristic plan
  combination methods. The robot can then avoid the remaining interferences
  between its sub-activities by predicting and forestalling them.

\item Robotic agents can monitor the execution of their activities and thereby
  detect situations in which their intended course of action might fail to
  produce the desired effects. If such situations are detected, the robots can
  adapt their intended course of action to the specific situations they
  encounter, if necessary based on foresight.

\end{enumerate}

%% The working hypothesis underlying this research is that robotic agents can
%% competently accomplish complex and dynamically changing everyday tasks in
%% human working environments if they use general, flexible \textit{routine
%%   plans}, \textit{recognize} problems, opportunities, and interactions between
%% sub-activities, and \textit{adapt} their activity if necessary.

In our previous research we have proposed Structured Reactive
Controllers (\src s) as a computational model for the plan-based
control of everyday activity. \src s are collections of concurrent
reactive control routines that adapt themselves to changing
circumstances during their execution by means of planning.  \src s are
based upon the following computational principles:

\begin{enumerate}
\item \src s are equipped with a library of plan schemata for routine tasks in
  common situations. These plan schemata are --- for now --- provided by
  programmers and designed to have high expected utility at the cost of not
  having to deal with all conceivable problems. We know from our AI courses
  that plans that check the tailpipes every time before starting a car have
  typically lower expected utility than the ones that do not check them, even
  though having no bananas stuck in the tailpipe is a necessary precondition
  for starting a car successfully.

%%   Fast heuristic methods that are again specified by programmers put plans
%%   together from routine plan schemata.

%%   The plan schemata are designed to deal with common situations and to be
%%   robust, flexible, concurrent and percept-driven behavior specifications.

  The robustness, flexibility, and reactivity of plan schemata is
  achieved by implementing them as \textit{concurrent percept-driven}
  plans --- even at the highest level of abstraction. The plans employ
  control structures including conditionals, loops, program variables,
  processes, and sub-routines.  They also make use of high-level
  constructs (interrupts, monitors) to synchronize parallel actions
  and make plans reactive and robust by incorporating sensing and
  monitoring actions and reactions triggered by observed events. Goals
  of sub-plans are represented explicitly as annotations such that
  planning algorithms can infer the purpose of sub-plans
  automatically.

\item \src s have fast heuristic methods for putting plans together
  from routine activities. They are able to predict problems that are
  likely to occur and revise their course of action to avoid them.
  Predictive plan debugging requires the \src\ to reason through, and
  predict the effects of, highly conditional and flexible plans ---
  the subject of this article.

\item \src s perform execution time plan management. They run
  processes that monitor the beliefs of the robot and are triggered by
  certain belief changes. These processes revise plans while they are
  executed.

\end{enumerate}

Structured reactive controllers work as follows.  When given a set of
requests, structured reactive controllers retrieve routine plans for
individual requests and execute the plans concurrently.  These routine
plans are general and flexible --- they work for standard situations
and when executed concurrently with other routine plans.  Routine
plans can cope well with partly unknown and changing environments, run
concurrently, handle interrupts, and control robots without assistance
over extended periods.  For standard situations, the execution of
these routine plans causes the robot to exhibit an appropriate
behavior in achieving their purpose.  While they execute routine
plans, the robot controllers also try to determine whether their
routines might interfere with each other and watch out for exceptional
situations.  If they encounter exceptional situations they will try to
anticipate and forestall behavior flaws by predicting how their
routine plans might work in this kind of situation. If necessary, they
revise their routines to make them robust for the respective kinds of
situations.  Finally, they integrate the proposed revisions smoothly
into their ongoing course of actions.

%% SRCs are equipped with a library of plans for routine tasks in standard
%% situations.  The agenda for the day is generated by ``gluing'' together the
%% routine plans for the individual tasks using heuristic plan generation rules.
%% Again these heuristic rules are specified by programmers and designed to have
%% high expected utility.

%% There are implications of using routine plans.  Routine plans that produce
%% good performance do often not work in every situation.  Everyday activity is
%% done using routine plans that have high expected utility at the cost of
%% dealing with all eventualities. Thus when using routine plans, the robot
%% should always monitor the execution of its activities and detect situations in
%% which their intended course of action might fail to produce the desired
%% effects. If such situations are detected, the robot should adapt its intended
%% course of action to the specific situation at hand.

%% To achieve this we equip the robots general, flexible, and percept-driven
%% \textit{routine} plans.  Such plan schemata must include local program
%% variables that are set and updated by the routines and sophisticated control
%% structures for concurrent reactive plan execution. The necessary activity
%% patterns also include the flexible interleaving of different jobs and the
%% exploitation of unplanned situations and opportunities.

%% The implementation of a plan-based controller for a household robot entails a
%% number of unsolved computational problems including object recognition and
%% manipulation and reasoning about common sense physics necessary for reasoning
%% about the effects of household actions. Therefore, we use office delivery as
%% our running example; a control task that is well within the capabilities of
%% today's autonomous mobile robots.


\subsection{Plan-based Control for a Robot Office Courier}
\label{sec:example}

Before we describe our approach to predicting concurrent
percept-driven robot behavior we first give a comprehensive example of
a plan-based robot office courier performing a delivery tour and
exhibiting aspects of everyday activity. The description of the
example includes the presentation of key plan schemata used by the
robot, a sketch of the heuristic plan combination method, the
prediction of behavior flaws, and the revision of delivery plans. This
example run has been performed with the mobile robot \rhino\ acting as
a robot office courier \cite{Bee01Str,Bee99Pro}.


\subsubsection{Plans and Plan Schemata of the Robot Courier}

The robot courier is equipped with a library of plan schemata for its standard
tasks including delivering items, picking up items, and navigating from one
place to another.  The presentation of the plans and plan schemata proceeds
bottom up. We start with the low-level plans for navigation and end with the
comprehensive object delivery plans.

%% To get better intuitions of the issues involved in realistically
%% projecting navigation behavior, we start with a description of the
%% \textit{low-level navigation plans} used by an autonomous robot that has
%% been successfully deployed as a museum tour-guide robot
%% \cite{Thr00Prob} and performed office delivery tasks \cite{Bee01Str}.

A low-level navigation plan specifies how the robot is to navigate from one
location in its environment, typically its current position, to another one,
its destination.  Figure~\ref{fig:low-level-plan-graphics} depicts such a
low-level navigation plan for going from a location in room A-117 to the
location~5 in room A-111.  The plan consists of two components: a sequence of
intermediate target points (the locations indexed by the numbers 1 to 5 in
Figure~\ref{fig:low-level-plan-graphics}) to be sequentially visited by the
robot and a specification of when and how the robot is to adapt its travel
modes as it follows the navigation path.  In many environments it is
advantageous to adapt the travel mode to the surroundings: to drive carefully
(and therefore slowly) within offices because offices are cluttered, to switch
off the sonars when driving through doorways (to avoid sonar crosstalk), and
to drive quickly in the hallways.  The second part of the plan is depicted
through regions with different textures for the different travel modes
``office'', ``hallway,'' and ``doorway.''  Whenever the robot crosses the
boundaries between regions it adapts the parameterization of the navigation
system. Thus, low-level navigation plans start and terminate navigation
processes and change the parameterization of the navigation system through
control mode switches (\textsc{set-navigation-mode}) and adding and deleting
intermediate target points (\textsc{move-to}).

\begin{figure}[htb]

\vspace{-2ex}

  \begin{center}
    \begin{tabular}{cc}
      \begin{minipage}{0.55\textwidth}
        \mbox{\includegraphics[width=0.95\textwidth]{PICS/topmap2.eps}}
      \end{minipage} &
      \begin{minipage}{0.38\textwidth}
        \begin{tabular}{|cc|l|}
          \hline
          \multicolumn{3}{|c|}{Legend} \\
          \hline
          \psframebox[fillstyle=crosshatch,framesep=8pt]{$~~~$}
          & &
          doorway travelmode \\
          \hline
          \psframebox[fillstyle=hlines*,hatchangle=0,framesep=8pt]{$~~~$} &
          & office travelmode \\
          \hline
          \psframebox[fillstyle=vlines,framesep=8pt]{$~~~$} &
          & hallway travelmode \\
          \hline
        \end{tabular}

        \vspace{2.5ex}

        \begin{tabular}{|c|l|}
          \hline
          \multicolumn{2}{|c|}{Navigation Plan} \\
          \hline
          waypoint & waypoint coordinates \\
          \hline
          1 & $\langle 2300,800\rangle$ \\
          2 & $\langle 2300,900\rangle$ \\
          3 & $\langle 1200,1100\rangle$ \\
          4 & $\langle 1200,1200\rangle$ \\
          5 & $\langle 1250,1400\rangle$ \\
          \hline
        \end{tabular}
      \end{minipage}
      \\
    \end{tabular}
  \end{center}

  \vspace{-1ex}

  \caption{Graphical representation of a
    navigation plan. Topological navigation plan for navigating from
    room A-117 to A-111 with regions indicating different travel modes
    and small black circles indicating additional navigation path
    constraints. \label{fig:low-level-plan-graphics}}

\vspace{-2ex}

\end{figure}

We specify reactive plans in \rpl\ \cite{McD91Rea,Bee92Dec}, a plan
language that provides high-level control structures for specifying
concurrent, event-driven robot behavior. The pseudo code in
Figure~\ref{fig:rpl-plan} sketches the initial part of the plan
depicted in Figure~1. The plan for leaving an office consists of two
concurrent sub-plans: one for following the (initial part of the)
prescribed path and one for adapting the travel mode.  The second
sub-plan adapts the navigation mode of the robot dynamically.
Initially, the navigation mode is set to ``office''.  Upon entering
and leaving the doorway the navigation mode is adapted.  The plan uses
\myem{fluents}, conditions that are updated asynchronously based on
new sensor readings. Fluents can trigger (\algkey{whenever}) and
terminate (\algkey{wait for}) plan steps.

\begin{figure}[htb]

  \begin{small}
    \begin{tabbing}
      \hspace*{4ex}\=\hspace{4ex}\=\hspace{4ex}\=\kill
      \algkey{execute concurrently} \\
      \> \algkey{execute-in-order}\\
      \> \> \textsc{move-to} \mbox{\textit{\textbf{(1)}}};
      \algkey{wait for} (\textbf{\textit{go-to-completed?}}); \\
      \> \> \textsc{move-to} \mbox{\textit{\textbf{(2)}}};
      \algkey{wait for} (\textbf{\textit{go-to-completed?}}); \\
      \> \algkey{with local fluents}
      \= \textbf{\textit{distance-to-doorway}} \\
      \> \> \hspace{3ex} $\leftarrow$ \= \textbf{\textit{fluent-network}}
      ($\mid \langle x,y \rangle - \langle x_{dw},y_{dw} \rangle
      \mid$) \\
      \> \> \textbf{\textit{entering-dw?-fl}} $\leftarrow$
      \textbf{\textit{distance-to-doorway}} $<$ 1m \\
      \> \> \=\textbf{\textit{entering-hw?-fl}} $\leftarrow$
      \textbf{\textit{distance-to-doorway}} $>$ 1m \\
      \> \hspace{6ex} \algkey{execute-in-order}\\
      \> \hspace{9ex} \= \textsc{set-navigation-mode}\mbox{(office)};
      \algkey{wait for}(\textbf{\textit{entering-dw?-fl}}); \\
      \> \> \textsc{set-navigation-mode}\mbox{(doorway)};
      \algkey{wait for}(\textbf{\textit{entering-hw?-fl}}); \\
      \> \> \textsc{set-navigation-mode}\mbox{(hallway)}
    \end{tabbing}
  \end{small}

  \vspace*{-2ex}

  \caption{The plan sketches the specification of a navigation
    process for leaving an office. The two components following the
    prescribed path and adapting the travel mode are implemented as
    concurrent sub-plans.  The second component uses a fluent to
    measure the distance to the center of the doorway and two
    dependent fluents that signal the robot's entering and leaving
    the doorway. Initially, the travel mode is set to ``office''.
    Upon entering and leaving the doorway the travel mode is
    adapted.}
  \label{fig:rpl-plan}

\end{figure}

The low-level navigation plan instances are used by higher-level navigation
plans that make the navigation processes flexible, robust, and embeddable into
concurrent task contexts. The higher-level plans generate the low-level plans
based on the robot's map of its environment (\textsc{generate-nav-plan}). A
slightly simplified version of this high-level plan is listed below.

\begin{minipage}{\textwidth}
  \begin{algorithm}{highlevel-plan}{\textbf{achieve}}{loc(rhino, \langle
          x,y \rangle)}
        \begin{EVAPPROTECT}{\CALL{abort-navigation-process}}
        \begin{WITHVALVE}{\VALVE{wheels}}
        \begin{REPEAT}{0}
          \begin{TRYALL}
            \WAITFOR{\FLUENT{navigation-interrupted?}} \\
            \begin{WITHLOCALVARS}{\algconst{nav-plan} \=
                \CALL{generate-nav-plan}\mbox{(c,d)}}
              \SWAPPLAN{\algconst{nav-plan}}{\algconst{nav-step}} \\
              \begin{NAMEDSUBPLAN}{\algconst{nav-step}}
                \CALL{dummy}
              \end{NAMEDSUBPLAN}
            \end{WITHLOCALVARS}
          \end{TRYALL}
        \end{REPEAT} \CALL{is-close?} (\langle x,y \rangle)
        \end{WITHVALVE}
        \end{EVAPPROTECT}
  \end{algorithm}
\end{minipage}

We explain the plan going from the inner parts, which generate the robot
behavior, to the outer ones, which modify the behavior.  Lines 6 to 8 make the
navigation plan independent of its starting position and thereby more general:
given a destination \textit{d}, the plan piece computes a low-level navigation
plan from the robot's current location \textit{c} to \textit{d} using the map
of the environment and executes it \cite{Bee96RTP}.

In order to run navigation plans in less constrained task contexts we must
prevent other --- concurrent --- routines from directing the robot to
different locations while the navigation plan is executed. We accomplish this
by using semaphores or ``valves'', which can be requested and released.  Any
plan asking the robot to move or stand still must request the valve
\textit{wheels}, perform its actions only after it has received
\textit{wheels}, and release \textit{wheels} after it is done. This is
accomplished by the statement \algkey{with valve} in line~2.

In many cases processes with higher priorities must move the robot
urgently.  In this case, blocked valves are simply pre-empted.  To
make our plan \textit{interruptible}, robust against such interrupts,
the plan has to do two things.  First, it has to detect when it gets
interrupted and second, it has to handle such interrupts
appropriately. This is done by a loop that generates and executes
navigation plans for the navigation task until the robot is at its
destination.  We make the routine cognizant of interrupts by using the
fluent \textbf{\textit{navigation-interrupted?}}.  Interrupts are
handled by terminating the current iteration of the loop and starting
the next iteration, in which a new navigation plan starting from the
robot's new position is generated and executed.  Thus, the lines 3-5
make the plan interruptible.

To make the navigation plan \textit{transparent} we name the routine plan
\rc{\textbf{\textsc{achieve}}(loc(rhino,$\langle$x,y$\rangle$))} and thereby
enable the planning system to infer the purpose of the sub-plan syntactically.
Interruptible and embeddable plans can be used in task contexts with higher
priority concurrent sub-plans. For instance, a monitoring plan used by our
controller estimates the opening angles of doors whenever the robot passes
one. Another monitoring plan localizes the robot actively whenever it has lost
track of its position.

%% \vspace{2mm}

%% \begin{rpltext}
%%   \begin{WITHPOLICY}{%
%%       \begin{WHENEVER}{\FLUENT{pos-uncertainty} > 0.8}
%%         \CALL{activate(active-localization)} \\
%%         \WAITFOR{\FLUENT{pos-uncertainty} \leq 0.8}
%%       \end{WHENEVER}}
%%     \mbox{\fbox{active-primaries}}
%%   \end{WITHPOLICY}
%% \end{rpltext}

To facilitate online rescheduling we have modularized the plans with
respect to the locations where sub-plans are to be executed using the
\algkey{at location} plan schema.  The \algkey{at location}
  $\langle$\textit{x,y}$\rangle$ \textit{p} plan schema specifies
that plan \textit{p} is to be performed at location \loc{x}{y}.  Here
is a simplified version of the plan schema for \algkey{at location}.

\begin{minipage}{\textwidth}
  \begin{rpltext}
    \begin{NAMEDSUBPLAN}{\noindent \VALVE{N$_i$}}
      \begin{REDUCE}{\algkey{at location}
          \makebox[2ex]{$~$} \mathloc{x}{y} \indent
          \textit{p}} \indent \algkey{by} \\
        \begin{WITHVALVE}{\VALVE{wheels}}
          \begin{WITHLOCALVARS}{\algconst{done?} \= \algconst{false}}
            \begin{LOOP}{XXX}
              \begin{TRYALL}
                \WAITFOR \FLUENT{Task-Interrupted?(\VALVE{N$_i$})} \\
                \begin{SEQ}
                  \CALL{Navigate-To} \mathloc{x}{y} \\
                  \textit{p} \\
                  \algconst{done?} \= \algconst{true}
                \end{SEQ}
              \end{TRYALL}
            \end{LOOP} \algconst{done?} = \algconst{true}
          \end{WITHLOCALVARS}
        \end{WITHVALVE}
      \end{REDUCE}
    \end{NAMEDSUBPLAN}
  \end{rpltext}
\end{minipage}

The plan schema accomplishes the performance of plan \textit{p} at
location \loc{x}{y} by navigating to the location \loc{x}{y},
performing sub-plan \textit{p}, and signalling that \textit{p} has
been completed (the inner sequence). The {\small \algkey{with valve}}
statement obtains the semaphore \textit{wheels} that must be owned by
any process changing the location of the robot. The loop makes the
execution of \textit{p} at \loc{x}{y} robust against interrupts from
higher priority processes. Finally, the {\small \algkey{named
    sub-plan}} statement gives the sub-plan a symbolic name that can
be used for addressing the sub-plan for scheduling purposes and in
plan revisions.  Using the {\small \algkey{at location}} plan schema,
a plan for delivering an object \textit{o} from location \textit{p} to
location \textit{d} can be roughly specified as a plan that carries
out \textit{pickup(o)} at location \textit{p} and \textit{put-down(o)}
at location \textit{d} with the additional constraint that
\textit{pickup(o)} is to be carried out before \textit{putdown(o)}.
If every sub-plan \textit{p} that is to be performed at a particular
location \textit{l} has the form {\small \algkey{at location}
  $\langle$\textit{x,y}$\rangle$ \textit{p}}, then a scheduler can
traverse the plan recursively and collect the {\small \algkey{at
    location}} sub-plans and install additional ordering constraints
on these sub-plans to maximize the plan's expected utility.

To allow for smooth integration of revisions into ongoing scheduled
activities, we designed the plans such that each sub-plan keeps a
record of its execution state and, if started anew, skips those parts
of the plan that no longer have to be executed \cite{Bee96RTP}.  We
made the plans for single deliveries restartable by equipping the plan
\textit{p} with a variable storing the execution state of \textit{p}
that is used as a guard to determine whether or not a sub-plan is to
be executed. The variable has three possible values:
\textit{to-be-acquired} denoting that the object must still be
acquired; \textit{loaded} denoting that the object is loaded; and
\textit{delivered} denoting that the delivery is completed. The plan
schema for the delivery of a single object consists of two fairly
independent plan steps: the pick-up and the put-down step.

\vspace{1ex}

\begin{rpltext}
  \begin{IF}{\CALL{execution-state}{(p,\mbox{\textit{to-be-acquired}})}}
    \CALL{At-Location} \indent \algconst{L} \indent
    \CALL{pick-up}{(o)}
  \end{IF} \\
  \begin{IF}{\CALL{execution-state}{(p,loaded)}}
    \CALL{At-Location} \indent \algconst{D} \indent
    \CALL{put-down}{(o)}
  \end{IF}
\end{rpltext}


\subsubsection{Generating Default Delivery Plans}

The heuristic plan generator for delivery tours is simple: it inserts
the pick-up and put-down sub-plans of all delivery requests into the
overall plan and determines an appropriate order on the {\small
  \algkey{at location}} sub-plans. The ordering is determined by a
heuristic that performs a simple topological sort on the sub-plans
based on the locations where the sub-plans are to be executed. The
heuristic considers additional constraints such as executing pick-up
steps always before the respective put-down plan-steps.


\subsubsection{Prediction-based Plan Debugging by the Robot Office Courier}

Let us now contemplate a specific scenario in which the robot office courier
\rhino\ performs an office delivery that requires the prediction and
forestalling of plan failures at execution time. Consider the following
situation in the environment pictured in Figure~\ref{fig:scenario1}. A robot
office courier is to deliver a letter in a yellow envelope from room A-111 to
A-117 (\textit{cmd-1}) and another letter for which the envelope's color is
unknown from A-113 to A-120 (\textit{cmd-2}).  The robot has already tried to
accomplish \textit{cmd-2} but because it has recognized room A-113 as closed
(using its range sensors) it revises its intended course of action into
achieving \textit{cmd-2} opportunistically. That is, if it later detects that
A-113 is open it will interrupt its current activity and reconsider its
intended course of action under the premise that the steps for accomplishing
\textit{cmd-2} are executable.

To perform its tasks quickly the robot schedules the pick-up and
delivery actions to minimize execution time and assure that letters
are picked up before they are delivered. To ensure that the schedules
will work, the robot has to take into account how its own state and
the world changes as it carries out the scheduled activities.  Aspects
of states that the robot has to consider when scheduling its
activities are the locations of the letters.  Constraints on the state
variables that schedules have to satisfy are that they only ask the
robot to pick up letters that are currently at the robot's location
and that the robot does not carry two letters in envelopes with the
same color.

\begin{figure}[htbp]

  \begin{center}
    \begin{tabular}{c}
      \includegraphics[width=0.55\textwidth]{PICS/opp1.ps}  \\
    \end{tabular}
  \end{center}

  \caption[A possible projected scenario for the initial plan.]%
  {A possible projected execution scenario for the initial plan. The
  opportunity of loading the letter of the unknown color is ignored.}
  \label{fig:scenario1}

\end{figure}

Suppose our robot is standing in front of room A-117.  The belief
state of the robot contains probabilities for the colors of letters on
the desk in A-113.  The robot also has received some evidence that
A-113 has been opened in the meantime. Therefore its belief state
assigns probability \textit{p} for the value \textsf{true} of random
variable \textsf{open-A113}.

This update of the belief state requires the robot to reevaluate its
options for accomplishing its jobs with respect to its changed belief
state. Executing its current plan without modifications might yield
mix ups because the robot might carry two letters in envelopes with
the same color. The different options are: (1)~to skip the
opportunity, (2)~to ask immediately for the letter from A-113 to be
put into an envelope that is not yellow (to exclude mix ups when
taking the opportunity later); (3)~to constrain later parts of the
schedule such that no two yellow letters will be carried even when the
letter in A-113 turns out to be yellow; and (4)~to keep picking up the
letter in A-113 as an opportunistic sub-plan. Which option the robot
should take depends on its belief state with respect to the states of
doors and locations of letters.  To find out which schedules will
probably work, in particular, which ones might result in mixing up
letters, the robot must apply a model of the world dynamics to the
state variables.

With respect to this belief state, different scenarios are possible. The first
one, in which A-113 is closed, is pictured in Figure~\ref{fig:scenario1}.
Points on the trajectories represent predicted events. The events without
labels are actions in which the robot changes its heading (on an approximated
trajectory) or events representing sensor updates generated by passive sensing
processes.  For example, a passive sensor update event is generated when the
robot passes a door.  In this scenario no intervention by prediction-based
debugging is necessary and no flaw is projected.

\begin{figure}[htbp]

  \begin{center}
    \begin{tabular}{cc}
      \includegraphics[width=0.45\textwidth]{PICS/opp3.ps} &
      \includegraphics[width=0.45\textwidth]{PICS/opp2.ps} \\
      (a) & (b) \\
    \end{tabular}
  \end{center}

  \vspace{-1ex}

  \caption[Two possible predicted scenarios for the opportunity being taken.]
  {Two possible predicted scenarios for the opportunity being taken. In
    scenario~(a) the letter turns out to have the same color as the one that
    is to be loaded afterwards. Therefore, the second loading fails.  In
    scenario~(b) the letter turns out to have a different color than the one
    that is to be loaded afterwards. Therefore, the second loading succeeds.}
  \label{fig:scenarios}

\end{figure}

\begin{figure}[htbp]

  \begin{center}
    \begin{tabular}{c}
      \includegraphics[width=0.55\textwidth]{PICS/opp5.ps}  \\
    \end{tabular}
  \end{center}

  \vspace{-1ex}

  \caption[Projected scenario for a plan suggested by the plan debugger.]%
  {Projected scenario for a plan suggested by the plan debugger. The letter
    with the unknown color is picked up and also delivered first. This plan is
    a little less efficient but avoids the risk of not being able to load the
    second letter.}
  \label{fig:scenario-revised}

\end{figure}

In the scenarios in which office A-113 is open the controller is
projected to recognize the opportunity and to reschedule its enabled
plan steps as described above.\footnote{Another category of scenarios
  is characterized by A-113 becoming open after the robot has left
  A-111. This may also result in an execution failure if the letter
  loaded in A-113 is yellow, but is not discussed here any further.}
The resulting schedule asks the robot to enter A-113 first, and pickup
the letter for \emph{cmd-2}, then enter A-111 and pick up the letter
for \emph{cmd-1}, then deliver the letter for \emph{cmd-2} in A-120,
and the last one in A-117. This category of scenarios can be further
divided into two categories. In the first sub-category shown in
Figure~\ref{fig:scenarios}(a) the letter to be picked up is yellow.
Performing the pickup thus would result in the robot carrying two
yellow letters and therefore an execution failure is signalled. In the
second sub-category shown in Figure~\ref{fig:scenarios}(b) the letter
has a different color and therefore the robot is projected to succeed
by taking the same course of action for all these scenarios.  Note
that the possible flaw is introduced by the reactive rescheduling
because the rescheduler does not consider how the state of the robot
will change in the course of action, in particular that a state may be
caused in which the robot is to carry two letters with the same color.

In this case, the plan-based controller will probably detect the flaw
if it is likely with respect to the robot's belief state. This
enables the debugger to forestall the flaw, for instance, by
introducing an additional ordering constraint, or by sending an email
that increases the probability that the letter will be put into a
particular envelope.  These are the revision rules introduced in the
last section.  Figure~\ref{fig:scenario-revised} shows a projection of
a plan that has been revised by adding the ordering constraint that
the letter for A-120 is delivered before entering A-111.

Figure~\ref{fig:real-trajectory}(a) shows the event trace generated by
the initial plan and \emph{executed} with the \rhino\ control system
\shortcite{Thr98Map} for the critical scenario without prediction
based schedule debugging; Figure~\ref{fig:real-trajectory}(b) shows
the one with the debugger adding the additional ordering constraint.
This scenario shows that reasoning about the future execution of plans
enables the robot to improve its behavior.

\begin{figure}[htbp]

  \begin{center}
    \begin{tabular}{cc}
      \includegraphics[width=0.45\textwidth]%
      {PICS/new-fail-episode-1.ps} &
      \includegraphics[width=0.45\textwidth]%
      {PICS/sc-new-episode-1.ps} \\
      (a) & (b) \\
    \end{tabular}
  \end{center}

  \vspace{-1ex}

  \caption[Possible physical behaviors of the robot with and without \ppsd.]%
  {The trajectory without prediction-based plan revision (Sub-figure~(a)) fails
    because the courier did not foresee the possible complications with
    loading the second letter.  Sub-figure~(b) shows a trajectory where the
    possible flaw is forestalled by the planning mechanism.}
  \label{fig:real-trajectory}

\end{figure}

In this article, we describe the probabilistic models of reactive robot
behavior that are necessary to predict scenarios such as the one described
above for the purpose of prediction-based plan debugging.


\subsection{The Projection of Low-level Navigation Plans}
\label{sec:nav-plan-projection}

Now that we know what the robot plans look like we can turn to the question of
how to predict the effects of executing a delivery plan. The input data for
plan projection are the probabilistic beliefs of the robot with respect to the
current state of the world, probabilistic models of exogenous events that are
assumed to be Poisson distributed, probabilistic models of low-level plans,
and probabilistic rules for guessing missing pieces of information. The output
of the projection process is a sequence of dated events along with the
estimated state at the time of each event.

Plan projection is identical to plan execution with two exceptions.  First,
whenever the plan projector interprets a {\small \algkey{wait for}} or
{\small \algkey{whenever}} it records the corresponding fluents as active
triggering conditions. This way, the plan projection mechanism can
automatically generate percepts when continuous control processes or exogenous
events make the triggering conditions true. For example, when the navigation
plan is waiting for the robot to enter the hallway the plan projector
probabilistically guesses when the robot motion causes the respective
triggering condition to become true. For this time instant, the plan projector
generates a sensor input event with the corresponding sensor reading.

Plan projection also differs from plan interpretation in that whenever
the robot interacts with the real world, the projected robot must
interact with the symbolic representations of the world. The places
where this happens are the low-level plans.  Thus instead of executing
a low-level plan the projector guesses the results of executing these
plans and asserts their effects in the form of propositions to the
timeline.  There are three kinds of effects that are generated by the
interpretation of low-level plans: (1)~physical changes, such as the
robot changing its position, (2)~the low-level plan changing the
dynamical state of the robot, such as the direction the robot is
heading to, and (3)~computational effects, such as changing the values
of program variables or signalling the success and failure of control
routines.  Thus the model of a low-level plan used for plan projection
is a probability distribution over the sequence of events that it
generates and the delays between the subsequent events.

Thinking procedurally, the plan projector works as follows. It iteratively
infers the occurrence of the next event until the given plan is completely
interpreted. The next event can either be the next event that the low-level
plan generates if the computational state of the controller does not change,
or a sensor input event if an active triggering condition is predicted to
become true, or an exogenous event if one is predicted to occur. The next
predicted event is the earliest of these events.

%% (2)~percepts, such as the sensor data corresponding to the robot entering the
%% hallway, a fluent that the low-level navigation is waiting for,


%% Since the main purpose of low-level plans is
%% the activation and deactivation of behavior modules, let us recall the most
%% salient features of behavior modules. Behavior modules can be activated and
%% deactivated; they signal their successful \rc{(FINISH {\it VALUES})} or
%% unsuccessful \rc{(FAIL {\it DESCRIP})} completion.  While running they cause
%% changes in the computational state of the robot controller (by setting
%% fluents) and changes in the environment and the physical state of the robot.

%% At a certain level of abstraction, robot action planning systems
%% consider plan steps as black boxes that generate behavior. The robot
%% must have causal models of these plans that enable its planning system
%% to predict what will happen when these steps get executed. We call
%% these plan steps \textit{low-level plans}.

We will now consider a particular instance of low-level plans: the
low-level navigation plans used in the example of the previous
section.  Navigation is a key action of autonomous mobile robots.
While predicting the path that a robot will take it is necessary to
predict \textit{where} the robot will be, which is a prerequisite for
predicting \textit{what} the robot will be able to perceive.  For
example, whether the robot will perceive that a door is open depends
on the robot taking a path that passes by the door, executing the door
angle estimation routine while passing the door and the door being
within sensor range. Passing the door is perceived based on the
robot's position estimate and the environment map. Consequently, if
the robot executes a plan step only if a door is open, then in the end
the execution of this plan step depends on the actual path the robot
will take.  This implies that an action planning process must be
capable of predicting the trajectory accurately enough to predict the
global course of action correctly.

Navigation actions are representative for a large subset of physical
robot actions: they are movements controlled by motors.  Physical
movements have a number of typical characteristics. First, they are
often inaccurate and unreliable.  Second, they cause continuous (and
sometimes discontinuous) change of the respective part of the robot's
state. Third, the interference of concurrent movements can often be
described as the superposition of the individual movements.

To discuss the issues raised by the projection of concurrent reactive plans,
we sketch a delivery tour plan that specifies how a robot is to deliver mail
to the rooms A-113, A-111, and A-120 in Figure~1 \cite{Bee01Str}. The mail for
room A-120 has to be delivered by 10:30 (a strict deadline).  Initially, the
planner asks the robot to perform the deliveries in the order A-113, A-111,
and A-120.  As the room A-113 is closed the corresponding delivery cannot be
completed.  Therefore, the planning system revises the overall plan such that
the robot is to accomplish the delivery for A-113 as an opportunity.  In other
words, the robot will interrupt its current delivery to deliver the mail to
A-113 (see Figure~\ref{fig:office-delivery-plan}) if the delivery can be
completed.

\begin{figure}[htb]

  \begin{center}
    \parbox{5cm}{%
      \begin{it}
        \begin{tabbing}
          \algkey{with policy} \= \algkey{as long as}
          \textbf{\textit{in-hallway?}}\\
          \> \hspace{3ex} \= \algkey{whenever}
          \textbf{\textit{passing-a-door?}} \\
          \>  \> \hspace{3ex} \textsc{estimate-door-angle}() \\
          \hspace{3ex} \= \algkey{with policy}
          \algkey{seq} \= \algkey{wait for}
          \textbf{\textit{open?(A-113)}} $~~$ \\
          \> \> \textsc{deliver-mail-to(Dieter)} \\
          \> \hspace{3ex} \= 1. \textsc{go-to(A-111)} \\
          \> \> 2. \textsc{go-to(A-120)} \algkey{before} 10:30
        \end{tabbing}
      \end{it}}
  \end{center}
  \vspace*{-3ex}

  \caption[Delivery tour plan with opportunistic steps.]%
  {Delivery tour plan with a concurrent monitoring process triggered by the
    continuous effects of a navigation plan (passing a door) and an
    opportunistic step. This concurrent reactive plans serve as an example
    for discussing the requirements that the causal models must satisfy.}
  \label{fig:office-delivery-plan}
\end{figure}

The plan contains constraining sub-plans such as ``whenever the robot
passes a door it estimates the opening angle of the door using its
laser range finders'' and opportunities such as ``complete the
delivery to room A-113 as soon as you learn the office is open''.
These sub-plans are triggered or completed by the continuous effects
of the navigation plans. For example, the event passing a door occurs
when the robot traverses a rectangular region in front of the door.
We call these events \emph{endogenous events}.

\begin{figure}[htb]
  \begin{center}

    \includegraphics[width=0.8\textwidth]{PICS/test.ps}

    \caption[Visualization of a projected execution scenario.]%
    {Visualization of a projected execution scenario. The following
      types of events are depicted by specific symbols: change travel
      mode event by rhombuses, start/stop passing doorway by small
      circles, start/stop low-level navigation plan by double circles,
      and entering doorway/hallway by boxes.}
  \label{fig:projected-scenario}
  \end{center}
\end{figure}

Figure~\ref{fig:projected-scenario} shows a projected execution
scenario for a low-level navigation plan embedded in the plan depicted
in Figure~\ref{fig:office-delivery-plan}.  The behavior generated by
low-level navigation plans is modeled as a sequence of events that
either cause qualitative behavior changes (e.g.\ adaptations of the
travel mode) or trigger conditions that the plan is reacting to (e.g.\
entering the hallway or passing a door).  The events depicted by
rhomboids denote events where the CRP changes the direction and the
target velocity of the robot.  The squares denote the events entering
and leaving offices. The small circles denote the events
\textit{starting} and \textit{finishing passing a door}, which are
predicted because a concurrent monitoring process estimates the
opening angles of doors \emph{while} the robot is passing them.

Such projected execution scenarios have been used for prediction-based
debugging of delivery tours of an autonomous robot office courier.
\citeA{Bee99Pro} have shown that a controller employing predictive
plan scheduling using the causal models described in this article can
perform better than it possibly could without predictive capabilities
(see also Section~6.1).


\subsection{Peculiarities of Projecting Concurrent Reactive Plans}
\label{sec:characteristics}

There are several peculiarities in the projection of concurrent reactive
plans that we want to point out here.

\noindent \textbf{Continuous Change.}
Concurrent reactive plans activate and deactivate control processes and
thereby cause continuous change of states such as the robot's position.
Continuous change must be represented explicitly because CRPs employ sensing
processes that continually measure relevant states (for example, the robot's
position) and promptly react to conditions caused by the continuous effects
(for example, entering an office).

\noindent \textbf{Reactive Control Processes.}  Because of the
reactive nature of robot plans, the events that have to be predicted
for a continuous navigation process depend not only on the process
itself but also on the monitoring processes that are simultaneously
active and wait for conditions that the continuous effects of the
navigation process might cause.  Suppose the robot controller is
running a monitoring process that stops the robot as soon as it passes
an open door.  In this case the planner must predict ``robot passes
door'' events for each door the robot passes during a continuous
navigation action.  These events then trigger a sensing action that
estimates the door angle, and if the predicted percept is an ``open
door detected'' then the navigation process is deactivated.  Other
discrete events that might have to be predicted based on the
continuous effects of navigation include entering and leaving a room,
having come within one meter of the destination, etc.

\noindent \textbf{Interference between continuous effects.}
For the control processes that set voltages for the robot's motors, the
possible modes of interference between control processes are limited. If they
generate signals for the same motors the combined effects are determined by
the so-called \textit{task arbitration scheme} \cite{Ark98Beh}.  The most
common task arbitration schemes are (1)~behavior blending (where the motor
signal is a weighted sum of the current input signals) \cite{Kon97Sap};
(2)~prioritized control signals (where the motor signal is the signal of the
process with the highest priority) \cite{Bro86Rob}; and (3)~exclusion of
concurrent control signals through the use of semaphores.  In our plans, we
exclude multiple control signals to the same motors but they can be easily
incorporated in the prediction mechanism.  Thus the only remaining type of
interference is the superposition of movements such as turning the camera
while moving.

\noindent \textbf{Uncertainty.}
There are various kinds of uncertainty and non-determinism in the
robot's actions that a causal model should represent. It is often
necessary to specify a probability distribution over the average speed
and the displacements of points on the paths to enable models to
predict the range of spatio-temporal behavior that a navigation plan
can generate.  Another important issue is to model probability
distributions over the occurrence of exogenous events. In most dynamic
environments exogenous events such as opening and closing doors might
occur at any time.


\section{Modeling Reactive Control Processes and Continuous Change}
\label{sec:hybrid-automata}

Let us now conceptualize the behavior generated by modern robot plans
and the interaction between behavior and the interpretation of
reactive plans.  We base our conceptualization on the vocabulary of
\textit{hybrid systems}. Hybrid systems have been developed to design,
implement, and verify embedded systems, collections of computer
programs that interact with each other and an analog environment
\cite{Alu97Sym,Alu96Aut}.

The advantage of a hybrid system based conceptualization over
state-based ones is that hybrid systems are designed to represent
concurrent processes with interfering continuous effects. They also
allow for discrete changes in process parameterization, which we need
to model the activation, deactivation, and reparameterization of
control processes through reactive plans. In addition, hybrid system
based conceptualizations can model the procedural meaning of
\algkey{wait for} and \algkey{whenever} statements.

As pictured in Figure~\ref{fig:dynamic-system}, we consider the robot
and its operating environment as two interacting processes: the
environment including the robot hardware, which is also called the
controlled process, and the concurrent reactive plan, which is the
controlling process. The state of the environment is represented by
state variables including the variables \textit{x} and \textit{y}, the
robot's real position and \textit{door-angle$_i$} representing the
opening angle of door~\textit{i}.  The robot controller uses fluents
to store the robot's measurements of these state variables
(\rc{robot-x}, \rc{robot-y}, \rc{door-a120}, etc.).  The fluents are
continually updated by the self-localization process and a model-based
estimator for estimating the opening angles of doors. The control
inputs of the plan for the environment process is a vector that
includes the \textit{travel mode}, the parameterization of the
navigation processes and the current target point to be reached by the
robot.

\begin{figure}[htb]
  \begin{center}
    \includegraphics[width=0.85\textwidth]{PICS/dynamic-system-2.eps}
  \end{center}
  \caption[Conceptualization of the dynamic system model for projection.]%
  {The figure shows our conceptualization of the execution of navigation
  plans. The relevant state variables are the x and y coordinates of the
  robot's position and opening angles of the doors. The fluents that estimate
  these state variables are \rc{robot-x}, \rc{robot-y}, and \rc{door-a120}.}
  \label{fig:dynamic-system}
\end{figure}


\subsection{A Hybrid System Model for Reactive Robot Behavior}
\label{sec:hybrid-system-model}

We will now model the controlled process as a hybrid system
\cite{Alu97Sym,Alu96Aut}.  Hybrid systems are continuous variable,
continuous time systems with a phased operation.  Within each phase,
called \textit{control mode}, the system evolves continuously
according to the dynamical law of that mode, called \textit{continuous
  flow}. Thus the state of the hybrid system can be thought of as a
pair --- the control mode and the continuous state. The control mode
identifies a flow, and the continuous flow identifies a position in
it. Also associated with each control mode are so-called \textit{jump
  conditions}, specifying the conditions that the discrete state and
the continuous state together must satisfy to enable a transition to
another control mode. The transitions can cause abrupt changes of the
discrete as well as the continuous state. The \textit{jump relation}
specifies the valid settings of the system variables that might occur
during a jump. Then, until the next transition, the continuous state
evolves according to the flow identified by the new control mode.

When considering the interpretation of concurrent reactive plans as a
hybrid system the control mode is determined by the set of active
control processes and their parameterization. The continuous state is
characterized by the system variables \textit{x}, \textit{y}, and
\textit{o} that represent the robot's position and orientation. The
continuous flow describes how these state variables change as a result
of the active control processes.  This change is represented by the
component velocities $\dot{x}$, $\dot{y}$, and $\dot{o}$.  Thus for
each control mode the robot's velocity is constant.  Linear flow
conditions are sufficient because the robot's paths can be
approximated accurately enough using polylines \cite{Bee98Cau}. They
are also computationally much easier and faster to handle. The jump
conditions are the conditions that are monitored by constraining
control processes which activate and deactivate other control
processes.

Thus the interpretation of a navigation plan according to the hybrid systems
model works as follows.  The hybrid system starts at some initial state
$\langle cm_0, x_0 \rangle$. The state trajectory evolves with the control
mode remaining constant and the continuous state $x$ evolving according to the
flow condition of $cm$. When the (estimated) continuous state satisfies the
transition condition of an edge from mode $cm$ to a mode $cm'$ a jump must be
made to mode $cm'$, where the mode might be chosen probabilistically. During
the jump the continuous state may get initialized to a new value $x'$. The new
state is the pair $\langle cm', x' \rangle$. The continuous state $x'$ evolves
according to the flow condition of $cm'$.

\begin{figure}[htb]

  \begin{center}
    \automaton
  \end{center}

  \vspace{-2ex}


%%   \begin{center}
%%     \includegraphics[width=0.8\textwidth]%
%%     {PICS/ha.ps}
%%   \end{center}

  \caption[Hybrid automaton for the interpretation of a navigation
  plan.]%
  {The figure shows the hybrid automaton for the interpretation of the
    navigation plan in Figure~\ref{fig:rpl-plan}. The possible control
    modes with the continuous flow equations are depicted as nodes and
    the mode transitions as edges. The edges are labeled with jump
    conditions: entering doorway ($e_1$, $e_6$), leaving doorway
    ($e_3$), reaching first waypoint ($e_2$, $e_4$), and reaching
    second waypoint ($e_5$).}
  \label{fig:hybrid-automaton}

\end{figure}

The construction of the hybrid system for a given concurrent plan is
straightforward. We start at the current plan execution state. For every
concurrent active statement of the form \algkey{wait for} \textit{cond} and
\algkey{whenever} \textit{cond} we add \textit{cond} as a jump condition to
the current control mode. In addition we have one additional jump condition
for the completion of the plan step.

Figure~\ref{fig:hybrid-automaton} depicts the interpretation of the
first part of the navigation plan shown in Figure~\ref{fig:rpl-plan}.
The interpretation is represented as a tree where the nodes represent
the control modes of the corresponding hybrid system and the node
labels the continuous flow. The edges are the control mode transitions
labeled with the jump conditions.  The robot starts executing the plan
in room A-117. The initial control mode of the hybrid system is the
root of the state tree depicted in Figure~\ref{fig:hybrid-automaton}.
The initial state represents the state of computation where the first
control processes of the two parallel branches are active, that is the
processes for going to the intermediate target point~\textbf{1} and
maintaining the ``office mode'' as the robot's travel mode. The flow
specifies that while the robot is in the initial control mode the
absolute value of the derivative of the robot's position is a function
of the robot's navigation mode (office, doorway, or hallway) and the
next intermediate target point.  The hybrid system makes a transition
into one of the subsequent states when either the first target point
is reached or when the distance to the doorway becomes less than one
meter.  The transition condition for the upper edge is that the robot
has come sufficiently close to the doorway, for the lower edge that it
has reached the first target point. For the lower edge, the hybrid
system goes into the state where the robot goes to the target
point~\textbf{2} while still keeping the office mode as its current
travel mode. In the other transition the robot changes its travel mode
to doorway and keeps approaching the first target point.  The only
variables that are changed through the control mode transitions are
the velocity of the robot and its orientation.  Both settings are
implied by the flow condition of the respective successor states.

There is one issue that we have not yet addressed in our conceptualization:
uncertainty.  We model uncertainty with respect to the continuous effects and
the achievement of jump conditions using multiple alternative successor modes
with varying flows and jump conditions. We associate a probability of
occurrence with each mode transition. This way we can, for example, represent
rotational inaccuracies of navigation actions that are typical for mobile
robots.


\subsection{Representation of the Hybrid System Model}
\label{sec:hybrid-system-representation}

Let us now formalize our hybrid system conceptualization using a
logical notation.  To do so, we are going to use the following
predicates to describe the evolution of the system states:
\textit{jumpCondition(cm,e,c)},
\textit{jumpSuccessor(e,cm',probRange)}, \textit{jumpRelation(cm',}
\textit{$\vec{vals}$,$\vec{flows}$)}, and \textit{prob\-Range(e,max)}.
\textit{jumpCondition(cm,e,c)} represents mode \textit{cm} being left
along edge \textit{e} when condition \textit{c} becomes true.
\textit{jumpSuccessor(e,cm',probRange)} defines the non-deterministic
successor states \emph{cm'} and the probability \emph{ProbRange} with
which they are entered if the system makes a transition along
\emph{e}. \textit{jumpRelation(cm',}
\textit{$\vec{vals}$,$\vec{flows}$)} defines the initial values of the
state variables and the flow conditions upon entering state
\emph{cm'}.  A jump \textit{e} causes the automaton to transit
probabilistically into a successor mode.

% To represent that the transitions are mutually exclusive we specify
% the probabilities through non-overlapping probability ranges.

For each possible successor we define a probability range \textit{probRange}.
For reasons that are explained below we represent the probability ranges such
that they are non-overlapping, their relative sizes are proportional to the
probability they represent (the sum of the ranges is 1) and that their
boundaries have the form $\frac{i}{2^n}$, where \textit{i} and \textit{n} are
integers. The predicate \textit{probRange(e,$2^n$)} defines the sum of the
ranges.  A possible transition with a probability range
[$\frac{i}{2^n},\frac{j}{2^n}$] is represented as
\textit{jumpSuccessor(e,cm',[i,j])}. The predicate
\textit{jumpRelation(cm',$\vec{vals},\vec{flows}$)} means that upon entering
control mode \textit{cm'} the system variables and flows are initialized as
specified by $\vec{vals}$ and $\vec{flows}$.

Using the predicates introduced above, we can state a probabilistic hybrid
automaton (Figure~\ref{fig:hybrid-automaton}) for the interpretation of our
navigation plan using the following facts.

\begin{quote}
  \textit{jumpRelation(cm$_0$,$\langle$2400,600$\rangle$,
    $\langle f_1(\mbox{\textit{office}},\mathloc{2300}{800}),
    f_2(\mbox{\textit{office}},\mathloc{2300}{800}) \rangle$)} \\
  \textit{jumpCondition(cm$_0$,e$_1$,$\mbox{dist}(\langle x,y
          \rangle,\langle x_{dw},y_{dw} \rangle) < 100$)} \\
  \textit{jumpCondition(cm$_0$,e$_2$,$x = 2300 \wedge y = 800$)} \\[2mm]
  \textit{jumpSuccessor(e$_1$,cm$_1$,[1,1])}\\
  \textit{probRange(e$_1$,1)} \\[2mm]
  \textit{jumpRelation(cm$_1$,$\langle$
  $\rangle$,$\langle f_1(\mbox{\textit{doorway}},\mathloc{2300}{800}),
  f_2(\mbox{\textit{doorway}},\mathloc{2300}{800}) \rangle$)} \\
  \textit{jumpRelation(cm$_2$,$\langle$
  $\rangle$,$\langle f_1(\mbox{\textit{office}},\mathloc{2300}{900}),
  f_2(\mbox{\textit{office}},\mathloc{2300}{900}) \rangle$)} \\
  ...
\end{quote}

%% \begin{quote}
%%   \textit{jumpRelation(cm$_0$,$\langle$2400,800$\rangle$,$\langle$30,80$\rangle$)} \\
%%   \textit{jumpCondition(cm$_0$,e$_1$,y$\geq$900)} \\[2mm]
%%   \textit{jumpSuccessor(e$_1$,cm$_1$,[1,12])}\\
%%   \textit{jumpSuccessor(e$_1$,cm$_2$,),[13,16])}\\
%%   \textit{probRange(e$_1$,16)} \\[2mm]
%%   \textit{jumpRelation(cm$_1$,$\langle$
%%   $\rangle$,$\langle$30,80$\rangle$)} \\
%%   \textit{jumpRelation(cm$_2$,$\langle$
%%   $\rangle$,$\langle$40,76$\rangle$)} \\
%%   ...
%% \end{quote}

The robot starts at position $\langle 2400,600\rangle$ in control mode
\textit{cm$_0$} in which the robot leaves the lower office on the
right. In this control mode the robot moves with $\langle
f_1(\mbox{\textit{office}},\mathloc{2300}{800}),$
$f_2(\mbox{\textit{office}},\mathloc{2300}{800}) \rangle$. The
navigation system leaves control mode \textit{cm$_0$} when coming
close to the door ($\mbox{dist}(\langle x,y \rangle,\langle
x_{dw},y_{dw} \rangle) < 100$) by performing the transition
\textit{e$_1$}.  If the system performs the transition $e_1$ then the
control flow changes because the low-level navigation plan switches
into the navigation mode \textit{doorway}. In our example, this
transition is deterministic.

To account for uncertainty in control we make these transitions
probabilistically. Thus we can substitute the control mode
\textit{cm$_1$} by multiple control modes, say \textit{cm$_1'$} and
\textit{cm$_1''$} where the control flows of the modes are sampled
from a probability distribution. We can then state for example that
with a probability of 75\% ($\frac{12}{16}$) the system transits into
control mode \textit{cm$_1'$} and with 25\% ($\frac{4}{16}$) into the
mode \textit{cm$_1''$} by defining the effects of the transition $e_1$
as follows:

\begin{quote}
  \textit{jumpCondition(cm$_0$,e$_1$,$\mbox{dist}(\langle x,y
    \rangle,\langle x_{dw},y_{dw} \rangle) < 100$)} \\
  \textit{jumpSuccessor(e$_1$,cm$_1'$,[1,12])}\\
  \textit{jumpSuccessor(e$_1$,cm$_1''$,),[13,16])}\\
  \textit{probRange(e$_1$,16)}
\end{quote}


To represent the state of a hybrid automaton we use the predicates
\textit{mode(cm)} and \textit{startTime(cm,t)} to represent that the
current control mode is \textit{cm} and that \textit{cm} started at
time \textit{t}. We use \textit{flow($\vec{\textit{flow}}$)} and
\textit{valuesAt($t_i$,$\vec{val_i}$)} to assert the flows and values
of system variables for given time points. Further, the values of
system variables can be inferred for arbitrary time points through
interpolation on the basis of the current flow and the last instances
of \textit{valuesAt($t_i$,$\vec{val_i}$)}. This is done using the
predicate \textit{stateVarsVals}:

\begin{tabbing}
        \quad \= \quad \= \kill
\textit{stateVarVals($\vec{vals}$)} $\equiv$
valuesAt(t$_0$,$\vec{vals_0}$) $\land$ \textit{now(t)}\\
\> $\land flow(\vec{\mbox{\textit{flow}}}) \land \vec{vals} = \vec{vals_0} + (t-t_0) \vec{\mbox{\textit{flow}}}$
\end{tabbing}

\noindent where \textit{now(t)} specifies that \textit{t} is the
current time. Note, in this conceptualization we represent the
discrete state changes explicitly and the states within a mode using
the mode's initial state and its flow. A particular state within a
mode can be derived on demand using the predicate
\textit{stateVarVals}. Interferences between different movements of
the robot issued in different control threads are modeled through the
mode's flow.

% The plan projection process takes the current world model, a
% concurrent reactive plan, rules for generating exogenous events, and a
% probabilistic causal models of the basic control routines, and
% generates \textit{execution scenarios} of the plan.

Figure~\ref{fig:timeline} depicts an execution scenario, a possible
evolution of the hybrid system representing how the execution of a
robot controller might go. An execution scenario is a consistent set
of jumps and values from the hybrid model over time. From this we can
extract event histories that can be used to simulate plan execution
and look for flaws.

An execution scenario consists of a \textit{timeline}, a linear sequence of
events and their results.  Timelines represent the effects of plan execution
in terms of \textit{time instants}, {\it occasions}, and \textit{co-occurring
  events}. This implies that several events can occur at the same time instant
but only one of them, the primary one, changes the state of the world.
\textit{Time instants} are points in time at which the world changes due to an
action of the robot or an exogenous event.  Each time instant has a {\it date}
which holds the time on the global clock at which the time instant occurred.
An \textit{occasion} is a stretch of time over which a world state \textit{P}
holds and is specified by a proposition, which describes \textit{P}, and the
time interval for which the proposition is true.

\begin{figure}[htb]
  \begin{center}
    \includegraphics[width=0.8\textwidth]{PICS/timeline-new.eps}
  \end{center}
  \caption[Visualization of a projected timeline.]%
  {Part of a timeline that represents a projected execution
    scenario for a low-level navigation plan. Time instants are depicted as
    circles, events as rectangles, and occasions as rectangles with round
    corners.}
  \label{fig:timeline}
\end{figure}

We deal with other kinds of uncertainty by representing our model using
McDermott's rule language for probabilistic, totally-ordered temporal
projection \cite{McD94Alg}. Using this language we can represent Poisson
distributed exogenous events, probability distributions over the current world
state, and probabilistic sensor and action models in a way that is consistent
with our model presented so far.


\subsection{Discussion of the Model}
\label{sec:model-discussion}

Let us now discuss how our hybrid system model addresses the issues
raised in Section~2.3.  There are two inference tasks concerning the
issue of continuous change caused by concurrent reactive plans that
are supported by our model. The first one is inferring the state at a
particular time instant.  For example, if the projection mechanism
predicts the occurrence of an exogenous event, such as an object
falling out of the robot's gripper, then the projection mechanism has
to infer where the robot is at this time instant to assert the
position of the object after falling down. This can be done using the
initial state and the flow condition of the active control mode. The
second important inference task is the prediction of control mode
jumps caused by the continuous effects of low-level plans, such as the
robot entering the hallway. This can be inferred using the jump
conditions of the active control mode in addition to the initial state
and the flow condition.

The second issue that we have raised in Section~2.3 is the prediction
of the robot's reactions to instantaneous events, such as dropping an
object. Typically, a reactive plan for carrying an object contains
sub-plans that ask the robot to stop and pick up the object again as
soon as the sensed force in the gripper drops. These kinds of
reactions are handled by checking all active jump conditions
immediately after an instantaneous event has occurred.

The third issue in projecting concurrent reactive plans is the
interference between simultaneous continuous effects. In our model,
interference is modelled by describing the effects of control mode
jumps on the flow condition of the subsequent control mode. The
programmer must specify rules describing the physics of the domain for
specifying the flow condition of the next mode. Thus, when a sub-plan
for moving the robot's arm is started while the robot is moving, then
the rule describing the effects of the corresponding control mode jump
asserts the flow condition specifying that the world coordinates of
the gripper are determined by the gripper position at the mode jump
and the transposition of the two motions in the successor mode.

Our last issue is that of uncertainty. One aspect of uncertainty that our
model supports are inaccuracies in the physical behavior of the robot.  This
is modelled by specifying probability distributions over the successor modes
when a control mode jump occurs. Other aspects of uncertainty including
probabilistic sensor models, uncertainty of instantaneous physical effects,
uncertainty about the state of the world, and Poisson distributed exogenous
events are handled by the rule language that we describe in the next section.
In particular, we will give examples of exogenous events and passive sensors
in Section~\ref{sec:passive-sensors} and a detailed probabilistic model of a
complex sensing action in Section~\ref{sec:action-models}.

Our approach does not explicitly reason about the belief state. We
assume that the belief state is computed by probabilistic state
estimators \shortcite{Thr00Prob}. Such state estimators not only
return the most likely state but also infer additional properties of
the belief state such as its ambiguity and the expected accuracy of
its global maximum. The plan-based controller interrupts delivery
tours as soon as the position estimate is ambiguous or too inaccurate.
Details of this mechanism as well as motivations for it can be found
in the work of \citeA{Bee98Int}.


\section{Probabilistic, Totally-Ordered Temporal Projection}
\label{sec:ptotp}

In the last section we have seen how hybrid systems and execution scenarios
are represented. In this section, we will see how we can predict execution
scenarios from the specification of a hybrid system.  For this purpose we use
McDermott's rule language for probabilistic, totally-ordered temporal
projection \cite{McD94Alg}.  This rule language has the expressiveness needed
for our purpose: we can specify the probabilities of event effects depending
on the respective situation, Poisson distributed events, and probability
distributions over the delays between subsequent plan generated events.
Uncertainty about the current state of the world can be specified in the form
of probabilistic effect rules of the distinct start event.

This rule language is an excellent basis for formalizing our model introduced
in the last section. A set of rules that satisfies certain conditions implies
a unique distribution of dated event sequences that satisfies the
probabilistic conditions of the individual rules (see
Definition~\ref{def:prob} in Section~\ref{sec:rule-language}). Thus if we give
probabilistic formalizations of the behavior within control modes and mode
jumps in McDermott's rule language then we define a unique probability
distribution over the state trajectories of the hybrid automaton that
satisfies our probabilistic constraints. Moreover, McDermott has developed a
provably correct projection algorithm that samples dated event sequences from
this unique distribution.

In the remainder of this section we will proceed as follows. We start by
presenting McDermott's rule language for probabilistic, totally-ordered
temporal projection and summarize the main properties of this language. We
will then represent our hybrid system model using this rule language. Based on
this representation we can, loosely speaking, show that when applying
McDermott's projection algorithm to the representation of the hybrid system,
the algorithm returns dated event sequences drawn from the unique distribution
implied by our rules with arbitrarily high probability.

Note, to obtain these results we will use a discretized model of time with
clock tick events that can be spaced arbitrarily close together resulting in
higher accuracy of the projection algorithm. This makes the use of this
representation infeasible in practice. Therefore, we eliminate the need for
clock tick events in Section~\ref{sec:monte-carlo} by making use of
McDermott's \algkey{persist} effects.


\subsection{McDermott's Rule Language for Probabilistic, Totally-ordered
Temporal Projection}
\label{sec:rule-language}

The different kinds of rules provided by this language are projection rules,
effect rules, and exogenous event rules.  Projection rules specify the
sequence of dated events caused by low-level plans, effect rules specify
causal models of sensing processes and actions, and exogenous event rules
are used to specify the occurrence of events not under the control of the
robot.  We will describe these kinds of rules below.

\vspace{-2ex}

\begin{itemize}

\item \myem{Projection rules} can be used to specify the sequence of
  events caused by the interpretation of a low-level plan. Projection
  rules have the form

  \begin{it}
    \begin{tabbing}
      \hspace{20ex} \= \algkey{project rule} \textit{name}(args) \\
      \> \algkey{if} cond \\
      \> \algkey{with a delay  of} $\delta_1$
      \algkey{occurs} ev$_1$ \\
      \> ... \\
      \> \algkey{with a delay  of} $\delta_n$
      \algkey{occurs} ev$_n$
    \end{tabbing}
  \end{it}

  \noindent and specify that if low-level plan \textit{name(args)}
  is executed and condition \textit{cond} holds then the low-level plan
  generates the events $ev_1$, ..., $ev_n$ with relative delays
  $\delta_1$, ..., $\delta_n$, respectively. Thus, projection rules
  generate a sequence of dated events.

  Uncertain models can be represented by sampling the $\delta_i$ from
  a probability distribution over durations and by specifying
  conditions that are satisfied only with a certain probability.

\item \myem{Effect rules} are used to specify conditional probabilistic
  effects of events. They have the form

  \vspace{1ex}

  \begin{tabbing}
    \hspace{12ex} \= \algkey{e$\rightarrow$p rule} \textit{name} \\
    \> \algkey{if} \textit{cond} \\
    \> \algkey{then} \= \algkey{with probability} $\theta$
    \algkey{event} \textit{ev} \algkey{causes} \textit{effs}
  \end{tabbing}

  \vspace{1ex}

  \noindent and specify that whenever event \textit{ev} occurs and
  \textit{cond} holds, then with probability $\theta$ create and clip states
  as specified in \textit{effs}. The effects of the \algkey{e$\rightarrow$p
    rule} rules have the form \textit{A}, causing the occasion \textit{A} to
  hold, \algkey{clip} \textit{A}, causing \textit{A} to cease to hold, and
  \algkey{persist} \textit{t A}, causing \textit{A} to hold for {\it t} time
  units.

\item \myem{Exogenous event rules} are used to specify the conditional
  occurrence of exogenous events. The rule

  \vspace{1ex}

  \begin{tabbing}
    \hspace{12ex} \= \algkey{p$\rightarrow$e rule} \textit{name} \\
    \> \algkey{while} \= \textit{cond}
    \algkey{with an avg spacing of} $\tau$  \algkey{occurs}
    \textit{ev}
  \end{tabbing}

  \vspace{1ex}

  \noindent specifies that over any interval in which \textit{cond} is
  true, exogenous events \textit{ev} are generated
  Poisson-distributed with an average spacing of $\tau$ time units.
\end{itemize}

% A consistent set of probabilistic rules together with a set of dated
% plan generated events define a probability distribution over execution
% scenarios. An execution scenario describes how the execution of a
% robot controller might go, that is, how the environment changes as the
% plan gets executed. It is represented as a {\it timeline}, a linear
% sequence of \textit{occurrences} where an occurrence is a dated
% \textit{event}.  The events of occurrences cause new \textit{world
%   states} that are characterized by the set of propositions that hold
% in them.  Actions are events that are caused by the robot.

% In this section we will introduce McDermott's probabilistic rule
% language \cite{McD94Alg} as a means for representing probabilistic
% effects of robot actions and nondeterministic exogenous events.
% McDermott \cite{McD94Alg} gives a formal semantics for the rule
% language introduced above, shows that a consistent set of rules has a
% unique model, and proves the algorithms for building and retrieving
% from the timeline to be correct.


% In McDermott's rule language causal models are represented by
% \begin{center}
% %  \begin{footnotesize}
%     \begin{tabular}{|p{0.43\columnwidth}|p{0.43\columnwidth}|}
%       \hline
%  \\
%       \hline
%     \end{tabular}
% %  \end{footnotesize}
% \end{center}

% \textbf{Exogenous event rules} (\textit{p$\rightarrow$e}) generate
% over any interval in which {\it cond} is true, random
% ``Poisson-distributed'' events \textit{ev} with an average spacing of
% $\tau$ time units (see \cite{McD94Alg}). \textbf{Effect rules}
% (\textit{e$\rightarrow$p} rules) specify that whenever event {\it ev}
% occurs and {\it cond} holds, then with probability $\theta$ the
% effects of {\it ev} are specified by {\it effs}. The effects have the
% form {\it p}, causing the proposition {\it p} to hold in the resulting
% world state and {\small \algkey{clip} {\it p}}, terminating the
% persistence of {\it p}.

Before proving properties of our model we must first introduce
McDermott's semantics of possible worlds. To do so, we define the key
notions of the underlying conceptualization in
Definition~\ref{def:world-of-d}. The evolution of the world is
described as a sequence of dated instantaneous events where an
occurrence \textit{e@t} specifies that event \textit{e} occurs at time
instant \textit{t}. In addition, we have a function mapping time
instants into world states. More precisely these notions are defined
as follows \cite<see>{McD94Alg}.

\begin{Def}
  A \myem{world state} is a function from propositions to
  \{T,F,$\perp$\} and is extended to boolean formulas in the usual
  way. An \myem{occurrence} e@t is a pair $c=(e,t)$, where $e$ is an
  event and $t$ a time ($t \in \Re_+$).  An \myem{occurrence sequence}
  is a finite sequence of occurrences, ordered by date.  Its duration
  is the date of the last occurrence.  A \myem{world of duration L},
  where $L \in \Re_+$, is a complete history of duration $L$, that is,
  it is a pair $(C,H)$, where $C$ is an occurrence sequence with
  duration $\leq L$, and $H$ is a function from $[0,L]$ to world
  states. In $H(0)$ all propositions are mapped to F, and if $t1 < t2$
  and $H(t1) \neq H(t2)$ then there must be an occurrence e@t with
  t1$\leq$t$\leq$t2.
  \label{def:world-of-d}

\end{Def}

We use the following abbreviations: $(A \downarrow t)(W)$, ``A after t
in execution scenario W'', to mean that there is some $\delta > 0$
such that $\forall t': t<t'<t+\delta \Rightarrow H(t')(A) = T$. $(A
\uparrow t)(W)$, ``A before t in W'' is similarly defined, but the
upper bound for $t'$ includes t.

% $A \uparrow c$ and $A \downarrow c$ refer to the date of the occurrence $c$.

After we have described how we represent the change in the world, we state the
conditions under which worlds of duration are consistent with a given set of
event effects and exogenous event rules. To do so, we have to state the
constraints that the rules, the local probabilistic models, impose on state
evolution. For this definition we take the plan generated events that are
typically specified through project rules, as given.

\begin{Def}
  \label{def:prob}
  If $T$ is a set of rules as defined above, $Exog$ is an occurrence
  sequence\footnote{\textit{Exog} is an occurrence sequence, which
    represents the events generated by the interpretation of the
    robot's plan and modeled using projection rules.}, $P$ is the set
  of propositions, and L is a real number $\geq duration(Exog)$, then
  an \myem{L-Model of T and Exog} is a pair $(U,M)$, where $U$ is a
  set of worlds of duration $L$ such that $\forall (C,H) \in U: Exog
  \subset C$, and $M$ is a probability measure on $U$ that obeys the
  following restrictions: $(A \da t)$, $(A \ua t)$ and $e@t$ are
  considered as random variables.  $\non{A}$ is the ``annihilation''
  of a conjunction $A$, that is the conjunction of the negations of
  the conjuncts of $A$.

  \begin{enumerate}
  \item \myem{Initial blank state:} $\forall A \in P : M(A \uparrow 0) = 0$.
    \label{clause:init}

  \item \myem{Event-effect rules:} If $T$ contains a rule instance

    \begin{center}
      \mbox{\algkey{e$\rightarrow$p rule} \textit{name} \algkey{if}
        \textit{A} \algkey{then} \algkey{with probability} $r$
        \algkey{event} \textit{e} \algkey{causes} \textit{B},}
    \end{center}
    then for every date $t$, require that, for all nonempty
    conjunctions C of literals from B: \\
    $M(C \da t | e@t \wedge A \ua t \wedge \non{B} \ua t) = r.$
    \label{clause:ep-active}

  \item \myem{Event-effect rules when the events don't occur:} Suppose
    B is an atomic formula, and let $R = \{R_i\}$ be the set of all
    instances of \algkey{e$\rightarrow$p} rules whose consequents
    contain $B$ or $\neg B$. If \mbox{\algkey{e$\rightarrow$p rule}
      $R_i = $ \algkey{if} $A_i$} \mbox{\algkey{then} \algkey{with
        probability} $p_i$} \mbox{\algkey{event} $E_i$ \algkey{causes}
      $C_i$,} then let $D_i = A_i \wedge \non{C_i}$, Then $M(B \da t |
    B \ua t \wedge N) = 1$ and $M(B \da t | \neg B \ua t \wedge N) =
    0$ where $N = ( \neg E_1@t \vee \neg D_1) \wedge ( \neg E_2@t \vee
    \neg D_2) \wedge ...$.
    \label{clause:ep-passive}

  \item \myem{Event-occurrence rules:} For every time point $t$ such that no
    occurrence with date $t$ is in $Exog$ and every event $E$, such that there
    is exactly one instance

    \begin{center}
      \algkey{p$\rightarrow$e rule} \textit{name} \algkey{while}
      \textit{A} \algkey{with an avg spacing of} $d$
      \algkey{occurs} \textit{E}
    \end{center}

    with $M(a \ua t) > 0$ require

    \[ lim_{dt \rightarrow 0} \frac{M(\mbox{occ.~of class E
        between t and t+dt} | A \ua t)}{dt} = 1/d \]

    \[ lim_{dt \rightarrow 0} \frac{M(\mbox{occ.~of class E
        between t and t+dt} | \neg A \ua t)}{dt} = 0 \]

    if there exists no so such rule, require

    \[ lim_{dt \rightarrow 0} \frac{M(\mbox{occ.~of class E
        between t and t+dt})}{dt} = 0 \]

  \item \myem{Conditional independence:} If one of the previous
    clauses defines a conditional probability $M(\alpha | \beta)$,
    which mentions times $t$, then $\alpha$ is conditionally
    independent, given $\beta$, of all other random variables
    mentioning times on or before $t$. That is, for arbitrary $\gamma$
    mentioning times on or before $t$, $M(\alpha | \beta) = M(\alpha |
    \beta \wedge \gamma)$.
  \end{enumerate}

\end{Def}

\begin{sloppypar}
  \noindent \mbox{\citeA{McD94Alg} shows that this definition yields a
    unique probability distribution~$M$.} He also gives a proof that his
  projection algorithm draws random execution scenarios sampled from
  this unique probability distribution implied by the given
  probabilistic models.
\end{sloppypar}


\subsection{Probabilistic Temporal Rules for PHAMs}
\label{sec:rules}

% Let us now discuss our approach to predicting the changes of the
% control mode of the automaton over time. The complication with the
% prediction of control mode is that the hybrid automaton defines
% mutually exclusive control mode transitions that occur with different
% probabilities. In the light of definition~2 this means that the
% distribution over execution scenarios of duration \textit{L} must
% reflect the probability distributions over control mode transitions.

In order to predict the evolution of a hybrid system, we specify rules
in McDermott's rule language that, given the state of the system and a
time \textit{t}, predict the successor state at \textit{t}. To predict
the successor state, we must distinguish three cases: first, a control
mode transition occurs; second, an exogenous event occurs; and third,
the system changes according to the flow of the current mode.

We will start with the rules for predicting control mode jumps. To ensure
that mode transitions are generated as specified by the probability
distributions over the successor modes, we will use the predicate
\textit{randomlySampledSuccessorMode(e,cm)} and realize a random number
generator using McDermott's rule language.

% As a means of formulating the rules that represent control mode
% transitions we will use the predicate
% \textit{randomlySampledSuccessorMode(e,cm)}:

\begin{tabbing}
  \textit{randomlySampledSuccessorMode(e,cm)} $\equiv$  \\
  \hspace{3ex} \= $probRange(e,max) \land randomNumber(n,max) $\\
  \> $ \land jumpSuccessor(e,cm,range) \land n \in range$
\end{tabbing}

In order to sample values from probability distributions we have to
axiomatize a random number generator that asserts instances of the
predicate \textit{randomNumber(n,max)} used above
\cite<see>{Bee00Pro}.  We do this by formalizing a \textit{randomize}
event.  \citeA{McD94Alg} discusses the usefulness of, and the
difficulties in, realizing nondeterministic exclusive outcomes.
Therefore in his implementation he escapes to Lisp and uses a function
that returns a random element.

\begin{Lemma}
 \label{Lemma:randomNumber}

 At any time point randomNumber has exactly one extension
 randomNumber(r,max) where r is an unbiased random between $0$ and
 $max$.

\end{Lemma}

\noindent \underline{Proof:} Let \textit{max$^*$} be  the largest
  \textit{probRange} extension and \textit{randomBit(i,value)} the
  i-th random bit.  The start event that causes the initial state
  timeline causes \textit{randomBit(i,0)} $\forall 0 \leq i \leq
  \log{max^*}$. Thereafter, a $randomize$ event is used to sample
  their value:

%  \begin{small}
    \begin{it}
      \begin{tabbing}
        \algkey{e$\rightarrow$p rule} \textsc{randomize} \\
      \algkey{if} \= \textit{randomBit(i,val)}
      $\land$ \textit{negation(val,neg)} \\
      \algkey{then} \= \algkey{with probability} \textit{0.5} \\
      \> \algkey{event} \textit{randomize} \\
      \> \algkey{causes} \= \textit{randomBit(i,neg)}
      $\land$ \algkey{clip}
      \textit{randomBit(i,val)}
    \end{tabbing}
  \end{it}
% \end{small}

% Using the rule language described above and the predicates introduced
% in the last section, we will now specify the causal model of \crp s.
% As the semantics of McDermott's algorithm is not full first-order, we
% treat the following rules as schemata standing for all their ground
% instances.

% In order to represent the hybrid automaton in McDermott's rule
% language we spercify rules for the occurrence and effects of mode
% transitions and the progress of time. In addition we list rules for
% the occurrence and effects of exogenous events.

Rule \textsc{Mode-Jump} causes a control mode transition as soon as
the jump condition \textit{cond} becomes true. The rule says that in
any interval in which \textit{cm} is the current control mode and in
which the jump condition \textit{cond} for leaving \textit{cm}
following edge \textit{edge} a jump along \textit{edge} will occur
with an average delay of $\tau$ time units.

\begin{it}
  \begin{tabbing}
    \algkey{p$\rightarrow$e rule} \textsc{Mode-Jump} \\
    \algkey{while} \= \textit{mode(cm)} $\land$
    \textit{jumpCondition(cm,cond,edge)} \\
    \> \hspace{2ex} $\land$ \textit{stateVarsVal($\vec{\mbox{vals}}$)} $\land$
    \textit{satisfies(vals,cond)} \\
    \algkey{with an average spacing of} $\tau$ \textit{time units} \\
    \algkey{occurs} \textit{jump(edge)}
  \end{tabbing}
\end{it}

Rule \textsc{Jump-Effects} specifies the effects of an jump event on
the control mode, system variables, and the flow. If \textit{cm} is a
control mode randomly sampled from the probability distribution over
successor nodes for jumps along \textit{edge} then the jump along
\textit{edge} has the following effects. The values of the state
variables and the flow condition of the previous control mode
\textit{cm$_{old}$} are retracted and the ones for the new control
mode \textit{cm} are asserted.

\begin{it}
  \begin{tabbing}
    \algkey{e$\rightarrow$p rule} \textsc{Jump-Effects} \\
    \algkey{if} \= \textit{randomlySampledSuccessorMode(edge,cm)} \\
    \> \hspace{2ex} \= $\land$ \textit{initialValues(cm,$\vec{val}$)} $\land$
    \textit{flowCond(cm,$\vec{\mbox{\textit{flow}}}$)} $\land$ \textit{now(t)} \\
    \> \>  $\land$ \textit{mode(cm$_{old}$)} $\land$
    \textit{flow(flow$_{old}$)}  $\land$
    \textit{valuesAt(t$_{old}$,val$_{old}$)} \\
    \algkey{then} \= \algkey{with probability} \textit{1.0} \\
    \> \algkey{event} \textit{jump(edge)} \\
    \> \algkey{causes} \= \textit{mode(cm)} $\land$
    \textit{flow($\vec{\mbox{\textit{flow}}}$)} $\land$
    \textit{valuesAt(transTime,$\vec{val}$)} \\
    \> \> \hspace{2ex} \= $\land$ \algkey{clip}
    \textit{mode(cm$_{old}$)} $\land$ \algkey{clip}
    \textit{flow(flow$_{old}$)}  $\land$
    \algkey{clip} \textit{valuesAt(t$_{old}$,val$_{old}$)}
  \end{tabbing}
\end{it}

Time is advanced using \textit{clock-tick} events.  With every
\term{Clock-Tick(\nonterm{?t})} event the \textit{now} predicate is
updated by clipping the previous time and asserting the new one. Note,
the time differs at most \dtc time units from the actual time.

\begin{it}
  \begin{tabbing}
    \algkey{e$\rightarrow$p rule} \textsc{Clock-Rule} \\
    \algkey{if} \= \textit{now(t$_o$)}\\
    \algkey{then} \= \algkey{with probability} \textit{1.0} \\
    \> \algkey{event} \textit{clock-tick(t)} \\
    \> \algkey{causes} \= \textit{now(t)} $\land$ \algkey{clip}
    \textit{now(t$_o$)}
  \end{tabbing}
\end{it}

Exogenous events are modeled using rules of the following structure.
When the navigation process is in the control mode \textit{cm} and the
values $\vec{\mbox{\textit{vals}}}$ of the state variables satisfy the
condition for the occurrence of the exogenous event \textit{ev}, then
the event \textit{ev} occurs with average spacing of $\tau$ time
units.

\begin{it}
  \begin{tabbing}
    \algkey{p$\rightarrow$e rule} \textsc{Cause-Exo-Event} \\
    \algkey{while} \= \textit{mode(cm)} $\land$
    \textit{exoEventCond(cm,cond,ev)} \\
    \> \hspace{2ex} $\land$ \textit{stateVarsVal($\vec{\mbox{vals}}$)} $\land$
    \textit{satisfies(vals,cond)} \\
    \algkey{with an average spacing of} $\tau$ \textit{time units} \\
    \algkey{occurs} \textit{exoEvent(ev)}
  \end{tabbing}
\end{it}

The effects of exogenous event rules are specified by rules of the
following form. The exogenous event \textit{exoEvent(ev)} with effect
specification \textit{exoEffect(ev,$\vec{val}$))} causes the values
of the state variables to change from $\vec{val_o}$ to $\vec{val}$.

\begin{it}
  \begin{tabbing}
    \algkey{e$\rightarrow$p rule} \textsc{Exo-Event-Effect} \\
    \algkey{if} \= \textit{exoEffect(ev,$\vec{val}$))}
    $\land$ \textit{valuesAt(t$_o$,val$_o$)} $\land$
    \textit{now(t)} \\
    \algkey{then} \= \algkey{with probability} \textit{1.0} \\
    \> \algkey{event} \textit{exoEvent(ev)} \\
    \> \algkey{causes} \= \textit{valuesAt(t,$\vec{val}$)}
    $\land$ \algkey{clip}
    \textit{valuesAt(t$_o$,$\vec{val_o}$)}
  \end{tabbing}
\end{it}


\subsection{Properties of PHAMs}
\label{sec:properties}

We have seen in the last section that a \pham\ consists of the rules
above and a set of facts that constitute the hybrid automata
representation of a given \crp.  In this section we investigate
whether \pham s make the ``right'' predictions.

There are essentially three properties of predicted execution
scenarios that we want to ensure. First, predicted control mode
sequences are consistent with the specified hybrid system. Second,
mode jumps are predicted according to the specified probability
distribution over successor modes. Third, between two successive
events, the behavior is predicted according to the flow of the
respective control mode.

As McDermott's formalism does not allow for modeling instantaneous
state transitions we can only show that control mode sequences in
execution scenarios are probably approximately accurate.  In our view,
this is a low price for the expressiveness we gain through the
availability of Poisson distributed exogenous events.

% In this section we show that if we represent the interpretation of
% \crp s using the rules listed in the last section then the control
% mode sequences in execution scenarios are legal with respect to the
% hybrid automaton, the probability distribution over control mode
% sequences in execution scenarios corresponds to the probability
% distributions over mode transitions that are defined by the automaton,
% and continuous states of the system are interpolated accurately.

The subsequent Lemma~\ref{Lemma:transition} states that control mode
jumps can be predicted with arbitrary accuracy and arbitrarily high
probability by decreasing the time between successive clock ticks.

\begin{Lemma}
  \label{Lemma:transition}

  For each probability $\epsilon$ and delay $\delta$, there exists a
  $\tau$ (average delay of the occurrence of an event after the
  triggering condition has become true) and a \dtc\ (time between two
  subsequent clock ticks) such that whenever a jump condition becomes
  satisfied, then with probability $\geq 1-\epsilon$ a jump event will
  occur within $\delta$ time units.

\end{Lemma}

\begin{sl}
  \noindent
  \underline{\textbf{Proof:}} Let $t$ be the time where the jump condition is
  fulfilled.  If $\tau \leq \delta/(2 \log(1/\epsilon))$ and \dtc $\leq
  \delta/2$ then at most $\delta/2$ time units after $t$ the antecedent of
  rule \textsc{Mode-Jump} is fulfilled. The probability that no event of class
  $jump(cm')$ occurs between $t+\delta/2$ and $t + \delta$ is $\leq
  e^{-\delta/(2 \tau)} = e^{-log(1/\epsilon)} = \epsilon$, so with probability
  $ \geq 1-\epsilon$ such an event will occur at most $\delta$ time units
  after $t$.

  \begin{flushright}
    $\square$
  \end{flushright}
\end{sl}

This implies that there is always a non-zero chance that control mode
sequences are predicted incorrectly. It happens only when two jump
conditions become true and the jump triggered by the later condition
occurred before the other one. However, the probability of such
incorrect predictions can be made arbitrarily small by the choice of
$\tau$ and \dtc.

The basic framework of hybrid systems does not take the possibility of
exogenous events into account and thereby allows for proving strong system
properties such as the reachability of goal states from arbitrary initial
conditions or safety conditions for the system behavior
\cite{Alu97Sym,Alu96Aut}. For the prediction of robot behavior in dynamic
environments these assumptions, however, are unrealistic. Therefore, we only
have a weaker property, namely the correspondence between the predicted
behavior and the flows specified by the hybrid system between immediate
subsequent events.

\begin{Lemma}
 \label{Lemma:}

 Let $W$ be an execution scenario, $e_1@t_1$ and $e_2@t_2$ be two
 immediate subsequent events of type \textsl{jump} or
 \textsl{exoEvent}, and \textsl{cm} be the control mode after $t_1$ in
 $W$. Then, for every occurrence e@t with $t_1 < t \leq t_2$
 \textsl{W(t)(stateVarVals($\vec{vals}$))} is unique. Further,
 $\vec{vals} = \vec{vals_1}$ + (t - $t_1$) * \textsl{flow(cm)}, where
 $\vec{vals_1}$ are the values of the state variables at $t_1$.

\end{Lemma}

\begin{sl}
  \noindent
  \underline{\textbf{Proof:}} There are only two classes of rules that
  affect the value of \textit{valuesAt} and \textit{flow}: rule
  \textsc{jump-Effects}, and rule \textsc{Exo-Event-Effect}. These
  rules always clip and set exactly one extension of the predicates,
  thus together with the fact that the initial event asserts exactly
  one such predicate, the determined value is unique.

  During the interval between $t_1$ and $t_2$ the extension of
  \textit{stateVarVals} evolves according to the flow condition of mode $cm$
  due to the fact that \textit{flow} is not changed by rule
  \textsc{Exo-Event-Effect}.  Thus it remains as initially set by rule
  \textsc{jump-Effects}, which asserts exactly the \textit{flow} corresponding
  to \textit{cm}.  The proposition then follows from the assumption of a
  correct axiomatization of addition and scalar-vector multiplication.

  \begin{flushright}
    $\square$
  \end{flushright}

\end{sl}

Another important property of our representation is that jumps are
predicted according to the probability distributions specified for the
hybrid automaton.

\begin{Lemma}

  Whenever a jump along an edge $e$ occurs, the successor state is
  chosen according to the probability distribution implied by
  \textsl{probRange} and \textsl{jumpSuccessor}.
\end{Lemma}

\begin{sl}
  \noindent
  \underline{\textbf{Proof:}} This follows from the properties of the
  \textit{randomize} event and Rule~\textit{Jump-Effects}.

  \begin{flushright}
    $\square$
  \end{flushright}

\end{sl}

Using the lemmata we can state and show the central properties of \pham s:
(1)~the predicted control mode transitions correspond to those specified by
the hybrid automaton; and (2)~the same holds for the continuous predicted
behavior between exogenous events; (3)~Exogenous events are generated
according to their probabilities over a continuous domain
\cite<this is shown in>{McD94Alg}.

\begin{Theorem}

  Every sequence of $mode(cm)$ occasions follows a branch
  $(cm_i),...,(cm_j)$ of the hybrid automaton.

\end{Theorem}

\begin{sl}
  \noindent
  \underline{\textbf{Proof:}} Each occasion \textit{mode(cm)} must be
  asserted by rule \textsc{Jump-Effects}. Therefore there must have
  been a \textit{jump(e)} event. Consequently, there must have been a
  \textit{jumpCondition} from the previous control mode to
  \textit{cm}.

  \begin{flushright}
    $\square$
  \end{flushright}

\end{sl}

Because jump events are modeled as Poisson distributed events there is
always the chance of predicting control mode sequences that are not
valid with respect to the original hybrid system. So next we will
bound the probability of predicting such mode sequences by choosing
the parameterization of the jump event and clock tick event rules
appropriately.

\begin{Theorem}
  For every probability $\epsilon$ there exists an average delay of a mode
  jump event $\tau$ and a delay \dtc\ with which the satisfaction of jump
  conditions is realized such that with probability $\geq 1-\epsilon$ the
  $\vec{vals}$ of \textit{stateVarVals} occasions between two immediate
  subsequent exogenous events follow a state trajectory of the hybrid
  automaton.
\end{Theorem}

\begin{sl}
  \noindent
  \underline{\textbf{Proof:}} The proof is based on the property that
  jumps occur in their correct order with an arbitrarily high
  probability. In particular, we can choose $\delta$ as a function of
  the minimal delay between jump conditions becoming true.  Then, the
  jumps to successor modes occur with arbitrarily high probability
  (Lemma~2). Finally, according to Lemma~3 the trajectory of
  \textit{stateVarVals} between transitions is accurate.

  \begin{flushright}
    $\square$
  \end{flushright}

\end{sl}



\section{The Implementation of PHAMs}
\label{sec:monte-carlo}

We have now shown that \pham s define probability distributions over
possible execution scenarios with respect to a given belief state. The
problem of using \pham s is obvious.  Nontrivial CRPs for controlling
robots reliably require hundreds of lines of code. There are typically
several control processes active, many more are dormant, waiting for
conditions that trigger their execution. The hybrid automata for such
CRPs are huge, the branching factors for mode transitions are immense.
Let alone the distribution of execution scenarios that they might
generate.  The accurate computation of this probability distribution
is prohibitively expensive in terms of computational resources.

There is a second source of inefficiency in the realization of \pham
s.  In \pham s we have used clock tick rules, Poisson distributed
events, that generate clock ticks with an average spacing of $\tau$
time units. We have done so, in order to formalize the operation of
CRPs in a single concise framework. The problem with this approach is
that in order to predict control mode jumps accurately we must choose
$\tau$ to be very small. This, however, increases the number of clock
tick events drastically and makes the approach infeasible for all
but the most simple scenarios.

In order to draw sample execution scenarios from the distribution
implied by the causal model and the initial state description we use
an extension of the \xfrm\ projector \cite{McD92Tra} that employs the
\rpl\ interpreter \cite{McD91Rea} together with McDermott's algorithm
for probabilistic temporal projection \cite{McD94Alg}. The projector
takes as its input a \crp, rules for generating exogenous events, a
set of probabilistic rules describing the effects of events and
actions, and a (probabilistic) initial state description. To predict
the effects of low-level plans the projector samples effects from the
probabilistic causal models of the low-level plans and asserts them as
propositions to the timeline. Similarly, when the plan activates a
sensor, the projector makes use of a model of the sensor and the state
of the world as described by the timeline to predict the sensor
reading.

In this section we investigate how we can make effective and informative
predictions on the basis of \pham s that can be performed at a speed
sufficient for prediction-based online plan revision.  To achieve
effectiveness we use two means. First, we realize weaker inference mechanisms
that are based on sampling execution scenarios from the distribution implied
by the causal models and the initial state description. Second, we replace the
clock tick event mechanism with a different mechanism that infers the
occurrence of control mode jumps and uses the \algkey{persist} effect to
generate the respective delay. We will detail these two mechanisms in the
remainder of this section.


\subsection{Projection with Adaptive Causal Models}
\label{sec:adaptive-models}

Let us first turn to the issue of eliminating the inefficiencies caused
by the clock tick mechanism. We will do so by replacing clock tick
rules with a mechanism for tailoring causal models on the fly and
using the \algkey{persist} effects of the probabilistic rule language.

For efficiency reasons the process of projecting a continuous process
{\it p} is divided into two phases. The first phase estimates a
schedule for endogenous events caused by {\it p} while considering
possible effects of {\it p} on other processes but not the effects of
the other processes on {\it p}.  This schedule is transformed into a
context-specific causal model tailored for the plan which is to be
projected.  The second phase projects the plan {\it p} using the model
of endogenous events constructed in the first phase.  This phase takes
into account the interferences with concurrent events and revises the
causal model if situations arise in which the assumptions of the
precomputed schedule are violated.

The projection module uses a model of the dynamic system that
specifies for each continuous control process the state variables it
changes and for each state variable the fluents that measure that
state variable.  For example, consider the low-level navigation plans that
steadily change the robot's position (that is the variables \rc{x} and
\rc{y}).  The estimated position of the robot is stored in the fluents
\rc{robot-x} and \rc{robot-y}:

\begin{it}
  \begin{tabbing}
    changes(low-level-navigation-plan, x) \\
    changes(low-level-navigation-plan, y) \\
    measures(robot-x, x) \\
    measures(robot-y, y)
  \end{tabbing}
\end{it}

\noindent \textbf{Extracting relevant conditions.}
When the projector starts projecting a low-level navigation plan it
computes the set of pending conditions that depend on \rc{robot-x}
and \rc{robot-y}, which are the fluents that measure the state
variables of the dynamic system and are changed by the low-level navigation
plan. These conditions are implemented as fluent networks.

\begin{figure}[htb]
  \begin{center}

  \begin{center}
    \includegraphics[width=0.7\textwidth]%
    {PICS/fluent-net.eps}
  \end{center}

  \caption{Fluent network for being in room A-120. The robot believes
    it is in room A-120 if its estimated x-coordinate is between 860
    and 1265 and the y-coordinate is smaller than 817, where the
    hallway begins.}
  \label{fig:fluent-net}
  \end{center}
\end{figure}

Fluent networks are digital circuits where the components of the circuit are
fluents. Figure~\ref{fig:fluent-net} shows a fluent network where the output
fluent is true, if and only if the robot is in room A-120. The inputs of the
circuit are the fluents \rc{robot-x} and \rc{robot-y} and the circuit is
updated whenever \rc{robot-x} and \rc{robot-y} change.

Our reactive plans are set up such that the fluent networks that compute
conditions for which the plan is waiting can be determined automatically using
({\sc Prolog}-like) relational queries:

\begin{it}
  \begin{tabbing}
    \algkey{setof} \= ?fl-net ( \= fluent(?fl) $\wedge$ status(?fl,pending) \\
    \> \> $\wedge$ changes(low-level-nav-plan, ?state-var) \\
    \> \> $\wedge$ measures(?state-var-fl, ?state-var) \\
    \> \> $\wedge$ depends-on(?fl, ?state-var-fl) \\
    \> \> $\wedge$ fluent-network(?fl, ?fl-net) ) \\
    \> ?pending-fl-nets
  \end{tabbing}
\end{it}

\noindent This query determines \rc{?pending-fl-nets}, the set of
fluent networks \rc{?fl-net} such that \rc{?fl-net} is a network with
output fluent \rc{?fl}. \rc{?fl} causes a plan thread to pend and
depends on a fluent measuring a state variable \rc{?state-var} changed
by the low-level navigation plan. The extraction of these conditions
is done automatically. The automatic extraction requires the
conditions be in a particular form and the effects of low-level plans
on state variables and the sensing of state variables to be
represented explicitly.

To predict when the fluent IN-A-120? will become true or false, we
have to compute the region in the state space that corresponds to the
fluent and compute the intersections of the robot's state trajectories
with this region.

\noindent \textbf{Endogenous event schedules.}  For each class of
continuous processes we have to provide an {\it endogenous event
  scheduler} that takes the initial conditions and the
parameterization of the process, and the fluent networks that might be
triggered and computes the endogenous event schedule.  The endogenous
event scheduler for the low-level navigation plans is described in the
next section. Given the kind of process (e.g., low-level navigation
plan), the process parameters (e.g., the destination of the robot),
and the pending fluent networks, the scheduler returns a sequence of
composite endogenous events. Composite events are represented as
triples of the form \rc{($\Delta$t, $\langle$sv$_{1}$, ...,
  sv$_{n}\rangle$, \{ev$_1$, ..., ev$_m$\})}. $\Delta$t is the delay
between the {\it i}th and the {\it i+1}st event in the schedule,
\rc{$\langle$sv$_{1}$, ..., sv$_{n}\rangle$} the values of the state
variables, and \rc{\{ev$_1$, ..., ev$_m$\}} the atomic events that are
to take place.

If a state for which the plan is waiting, becomes true at a time
instance {\it t}, then at {\it t} a \rc{passive-sensor-update} event
is triggered.  \rc{passive-sensor-update} is an event model that takes
a set of fluents as its parameters, retrieves the values of the state
variables measured by these fluents, applies the sensor model to these
values, and then sets the fluents accordingly.

\noindent \textbf{A causal model of low-level navigation plans.}
Projecting the initiation of the execution of a navigation plan causes two
events: the start event and a hypothetical completion event after an infinite
number of time units. This is shown in the following projection rule.

\begin{minipage}{\textwidth}
  \begin{it}
    \begin{tabbing}
      \algkey{project rule} \textsc{low-level-navigation-plan} \\
      \algkey{if} true \\
      \algkey{with a delay  of} 0 \\
      \algkey{occurs} begin(low-level-nav-plan(?dest-descr, ?id, ?fluent) \\
      \algkey{with a delay  of} $\infty$ \\
      \algkey{occurs} end(low-level-nav-plan(?dest-descr, ?id, ?fluent) \\
    \end{tabbing}
  \end{it}
\end{minipage}

The effect rule of the start event of the low-level navigation plan
computes the endogenous event schedule and asserts the next endogenous
navigation event into the timeline.

\begin{it}
  \begin{tabbing}
    \algkey{e$\rightarrow$p rule} \textsc{endogenous-events} \\
    \algkey{if} \= \textit{endogenous-event-schedule}(low-level-nav-plan(?dest-descr, ?schedule)) \\
    \algkey{then} \= \algkey{with probability} \textit{1.0} \\
    \> \algkey{event}
    \textit{begin(low-level-nav-plan(?dest-descr, ?id, ?fluent))} \\
    \> \algkey{causes} \= \textit{predicted-events(?id, ?schedule)} \\
    \> \> $\land$ \textit{running(robot-goto(?descr, ?id))} \\
    \> \> $\land$ \textit{next-nav-event(?id))}
  \end{tabbing}
\end{it}

The occasion \rc{next-nav-event(?id)} triggers the next endogenous
event \rc{begin(follow-path(?here $\langle$?x,?y$\rangle$) ?dt
  ?id))}. The remaining two conditions determine the parameters of the
\rc{follow-path} event: the next scheduled event and the robot's
position.

\begin{it}
  \begin{tabbing}
    \algkey{p$\rightarrow$e rule} \textsc{Cause-Exo-Event} \\
    \algkey{while} \= next-nav-event(?id) \\
    \> $\land$ predicted-events(?id, ((?dt $\langle$?x,?y$\rangle$ ?evs)
    !?remaining-evs) \\
    \> $\land$ robot-loc(?here) \\
    \algkey{with an average spacing of} 0.0001 \\
    \algkey{occurs} begin(follow-path(?here, $\langle$?x,?y$\rangle$,
    ?dt, ?id))
  \end{tabbing}
\end{it}

The effect rule of the \rc{begin(follow-path (...))} event specifies
among other things that the next endogenous event will occur after
\rc{?dt} time units \rc{(\algkey{persist} ?dt sleeping(?id))}.

\begin{it}
  \begin{tabbing}
    \algkey{e$\rightarrow$p rule} \textsc{follow-path} \\
    \algkey{if} \= robot-loc(?coords) \\
    \algkey{then} \= \algkey{with probability} \textit{1.0} \\
    \> \algkey{event}
    begin(follow-path(?from, ?to, ?dt, ?id)) \\
    \> \algkey{causes} \= running(follow-path(?from, ?to, ?dt, ?id)) \\
    \> \> $\land$ \algkey{clip} robot-loc(?coords) \\
    \> \> $\land$  \algkey{clip} next-nav-event(?id) \\
    \> \> $\land$ \algkey{persist}  ?dt sleeping(?id)
  \end{tabbing}
\end{it}

If a running \textit{follow path} event has finished sleeping the \rc{end
  (follow-path (...))} event occurs.

\begin{it}
  \begin{tabbing}
    \algkey{p$\rightarrow$e rule} \textsc{Terminate-Follow-Path} \\
    \algkey{while} \= \algkey{not} sleeping(?id) \\
    \> $\land$ running(follow-path(?from, ?to, ?time, ?id)) \\
    \algkey{with an average spacing of} 0.0001 \\
    \algkey{occurs} end(follow-path(?from, ?to, ?time, ?id))
  \end{tabbing}
\end{it}

Our model of low-level navigation plan presented so far suffices as long as
nothing important happens while carrying out the plan. However, suppose that
an exogenous event that causes an object to slip out of the robot's hand is
projected at time instant {\it t} while the robot is in motion. To predict the
new location of the object the projector predicts the location {\it l} of the
robot at the time {\it t} using the control flow and asserts it in the
timeline.

Qualitative changes in the behavior of the robot caused by adaptations
of the travel mode are described through
\protect\algkey{e$\rightarrow$p}-rules.  The following
\protect\algkey{e$\rightarrow$p}-rule describes the effects of the
event \protect\rc{nav-event(set-travel-mode(?n))}, which represents the
low-level navigation plan resetting the travel mode:

\begin{it}
  \begin{tabbing}
    \algkey{e$\rightarrow$p rule} \textsc{set-doorway-mode} \\
    \algkey{if} \= travel-mode(?m) \\
    \algkey{then} \= \algkey{with probability} \textit{1.0} \\
    \> \algkey{event} nav-event(set-travel-mode(doorway)) \\
    \> \algkey{causes} \=  \algkey{clip} travel-mode(?m) \\
    \> \> $\land$ \algkey{clip} obstacle-avoidance-with(sonar) \\
    \> \> $\land$ travel-mode(doorway)
  \end{tabbing}
\end{it}

The rule specifies that if at a time instant at which an event
\rc{nav-event(set-travel-mode(?n))} occurs the state \rc{travel-mode(?m)}
holds for some \rc{?m}, then the states \rc{travel-mode(?m)} and
\rc{obstacle-avoidance-with(sonar)} will (with a probability of \rc{1.0}) not
persist after the event has occurred, i.e., they are clipped by the event. The
event causes the state \rc{travel-mode(doorway)} to hold until it is adapted
next time.

The rules listed above are hand-coded and plan-specific. An
investigation of whether the plans can be coded such that the rule
specification can be automated is on our agenda for future research.


\subsection{Endogenous Event Scheduler}

We have just shown how events are projected from a given endogenous
event schedule, but we have not shown how the schedule is constructed.
Thus, this section describes the endogenous event scheduler for
low-level navigation plans. The scheduler predicts the effects of the
low-level navigation plan on the state variables \rc{x} and \rc{y}.
The endogenous event scheduler assumes the robot is following a
straight path between locations \rc{1} to \rc{5}. As we have pointed
out earlier, there are two kinds of events that need to be predicted:
the ones causing {\it qualitative physical change} and the ones
causing the {\it trigger conditions} that the plan is waiting for.

The qualitative events caused by the low-level navigation plan pictured in
Figure~13 are the ones that occur when the robot arrives at the locations
\rc{1}, \rc{2}, \rc{3}, \rc{4}, and \rc{5} in which the robot either changes
its travel mode or arrives at its destination.  For each of these time
instants the occurrence of a \rc{set-travel-mode}-event is predicted.

The scheduler for triggering events works in two phases: (1)~it
transforms the fluent network into a condition that it is able to
predict and (2)~it applies an algorithm for computing when these
events occur.  The conditions that are caused by the low-level
navigation plan can be represented as regions in the environment such
that the condition is true if and only if the robot is within this
region. The elementary conditions are numeric constraints on the
robot's position or the distance of the robot to a given target point.
The scheduler assumes that \rc{robot-x} and \rc{robot-y} are the only
fluents in these networks that change their value during the execution
of the plan.  More complex networks can be constructed as conjunctions
and disjunctions of the elementary conditions.

\begin{figure}[htb]
  \begin{center}

  \begin{center}
    \includegraphics[width=0.7\textwidth]%
    {PICS/prediction1.eps}
  \end{center}

  \caption{Initially predicted endogenous events.}
  \label{fig:prediction1}
  \end{center}
\end{figure}

% The endogenous event scheduler approximates the regions by rectangular
% areas in order to apply faster computation methods. Consequently,
% circles, that is regions specified by a maximal distance to a given
% point, are approximated as the surrounding squares. Thus, the step
% performed by the endogenous event scheduler is to transform the given
% fluent network into a union or intersection of rectangles.

In the next step the endogenous event scheduler overlays the
straight line path through the intermediate goal points of the
topological navigation path (see Figure~\ref{fig:office-delivery-plan})
with the regions computed in the previous step.  It then computes a
schedule for the endogenous events by following the navigation path
and collecting the intersections with the regions (see
Figure~\ref{fig:prediction1}). The result of the scheduling step is a
sequence of triples of the form \rc{($\Delta$t$_i$, $\langle$x$_{i}$,
  y$_{i}\rangle$, \{ev$_1$, ..., ev$_n$\})}.

\begin{figure}[htb]
  \begin{center}

  \begin{center}
    \includegraphics[width=0.7\textwidth]%
    {PICS/prediction2.eps}
  \end{center}

  \caption{Modified endogenous event schedule.}
  \label{fig:prediction2}
  \end{center}
\end{figure}

\noindent {\bf Rescheduling endogenous events.}
One problem that our temporal projector has to deal with is that a
\algkey{wait for} step might be executed while a low-level navigation plan is
projected. For example, when the robot enters the hallway, the policy
that looks for the opening angles of doors when passing them is
triggered. Therefore, the causal model that was computed by the
endogenous event scheduler is no longer sufficient.  It fails to
predict the ``passing a door'' events.

These problems are handled by modifying the endogenous event schedule:
whenever the robot starts waiting for a condition that is a function
of the robot's position, it interrupts the projection of the low-level
navigation plan, adapts the causal model of the low-level navigation
plan, and continues with the projection. In the case of entering the
hallway, a new endogenous event schedule that contains endogenous
events for passing doorways is computed. This updated schedule of
endogenous events is pictured in Figure~\ref{fig:prediction2}.


\subsection{Projecting Exogenous Events, Passive Sensors and
  Obstacle Avoidance}
\label{sec:passive-sensors}

One type of exogenous event is an event for which we have additional
information about its time of occurrence, such as the event that
Dieter will be back from lunch around \rc{12:25}. These kinds of
events are represented by a \algkey{p$\rightarrow$e} rule together
with an \algkey{e$\rightarrow$p} rule. The \algkey{e$\rightarrow$p}
rule specifies that the \rc{start} event causes the state
\rc{before-dieters-door-opens()} to hold and persist for \rc{?time}
time units. The event \rc{dieters-door-opens()} is triggered as soon
as \rc{before-the-door-opens()} no longer holds.

\begin{it}
  \begin{tabbing}
    \algkey{e$\rightarrow$p rule} \textsc{Back-from-Lunch} \\
    \algkey{if} \= about(?time, 12:25) $\wedge$
    difference(?time, *now*, ?wait-for)) \\
    \algkey{then} \= \algkey{with probability} \textit{1.0} \\
    \> \algkey{event}
    \textit{start} \\
    \> \algkey{causes} \algkey{persist} ?wait-for before-the-door-opens
  \end{tabbing}
\end{it}

\begin{it}
  \begin{tabbing}
    \algkey{p$\rightarrow$e rule} \textsc{Door-Opens} \\
    \algkey{while} \= \algkey{thnot} before-the-door-opens \\
    \algkey{with an average spacing of} 0.0001 \\
    \algkey{occurs} dieters-door-is-opened
  \end{tabbing}
\end{it}

In order to predict the occurrence of exogenous events, the plan projector
does the following. It first computes the time when the robot will cause the
next event $e_{next}$. Let us assume that this event occurs $t$ time units
after the last event $e_{last}$ and that \textit{c} is the strongest condition
that holds from $e_{last}$ until $e_{next}$.\footnote{The cases where enabling
  conditions of exogenous events are caused by the continuous effects between
  $e_{last}$ and $e_{next}$ are handled analogously to the achievement of
  triggering conditions.} The following algorithm predicts the occurrence of
the next exogenous event accurately. First, for every \algkey{p$\rightarrow$e}
rule $r_i$ whose enabling condition is satisfied by \textit{c} randomly decide
whether $e_i$ will occur between $e_{last}$ and $e_{next}$ based on the
average temporal spacing of $e_i$ events in situations where $c$ holds. If
$e_i$ is predicted to occur, select its occurrence time by randomly selecting a
time instant in the time interval between $e_{last}$ and $e_{next}$ (the
exogenous events are Poisson distributed). Select the exogenous event that is
predicted to occur the earliest, assert it to the timeline, and continue the
projection after the occurrence of this event.

%Another type of event is the Poisson distributed event. As an example,
%the following event states that if the localization module is running
%on a computer where the load average exceeds a certain threshold then
%the robot loses track of its position on average once in ten minutes.

%\begin{code-example}{10cm}
%  (\textbf{P-$>$E} \= (\textbf{AND} \= (RUNS LOCALIZE ?COMPUTER) \\
%  \> \> (LOAD-AVERAGE ?COMPUTER ?LOAD-AVG) \\
%  \> \> ($>$ ?LOAD-AVG {\it TRESHOLD})) \\
%  \> 600 (LOSING-TRACK-OF-POS))
%\end{code-example}

The last two components we need to describe are passive sensors, which are
steadily updated and do not change the configuration of the robot and the
behavior of the collision avoidance routines.

Readings of passive sensors only need to be projected if the measured
state variables change significantly or if the state variables
traverse values that satisfy conditions for which the robot is
waiting. For each of these situations there is an
\rc{update-passive-sensors} event.

Collision avoidance is not modeled except in situations in which the
robot is told about objects that are moved around. In this case the
endogenous event scheduler adds a region corresponding to the object.
If the region blocks the way to the destination --- that is the robot
cannot move around the region --- then a \rc{possible-bump-event} is
generated. The effect rule for a possible bump event specifies that,
if the robot has activated sensors that can detect the object, the
low-level navigation plan fails with a failure description ``path
blocked.'' Otherwise a bump event is generated. For example, since
sonar sensors are the only sensors placed at table height, the
collision avoidance module can avoid a collision with a table only if
the sonar sensors are active. Thus, to predict a bump, the projector
has to determine how long the sonar sensors have been switched off
before the possible bump event occurs.


\subsection{Models of Complex Sensing Actions}
\label{sec:action-models}

To understand how other types of uncertainty can be modeled and how
the causal models interact with the plan interpretation let us look at
a more complex sensing action realized through a low-level plan
\textit{look-for}.  The sub-plan is called with a visual description
(\textit{?pl}) of objects it is supposed to look for.

Typically, in order to model a low-level plan we need a set of projection
rules that probabilistically describe the possible event sequences and
outcomes when activating a behavior module. In each situation exactly one
projection rule is applied (although the decision about which one might be
probabilistic).

One of these projection rules for \textit{look-for} is listed below. The model
consists of three parts.  The first part (line 1 to 7) specifies the condition
under which this rule predicts the behavior of the \textit{look-for}
correctly. The second part (lines 8 to 11) lists the events that
\textit{look-for} will cause if this rule is applicable. Finally, the last
line specifies how the low-level plan signals the completion of its
interpretation. In our case, the low-level plan succeeds and returns a list of
object descriptions (\textit{?desigs}) as its value.


\begin{figure}[htb]

  \begin{it}
    \begin{tabbing}
      \hspace{6ex} \= ( \hspace{2ex}  \= $\wedge$ \algkey{setof} \= \hspace{2ex}
      \= e \hspace{25ex} \= \kill
      \> \algkey{project rule} look-for(?pl, ?cam) \\
      {\bf {\em (1)}} \> \algkey{if} \> ( loc(robot, \pos{?x}{?y}) \\
      {\bf {\em (2)}} \> \> $\wedge$ normal-look-for-behavior(?cam, ?loc) \\
      {\bf {\em (3)}} \> \> $\wedge$ \algkey{setof} ?ob loc(?ob, \pos{?x}{?y})
      ?obs-here  \\
      {\bf {\em (4)}} \> \> $\wedge$ sensor-model(?cam, ?sensor-model) \\
      {\bf {\em (5)}} \> \> $\wedge$ features(?pl,?features) \\
      {\bf {\em (6)}} \> \> $\wedge$ \algkey{setof} ?desig  \\
      \> \> \> ( member(?ob,?obs-here) \\
      \> \> \> \hspace{2ex} \= $\wedge$ obj-seen(?ob, ?sensor-model) \\
      \> \> \> \> $\wedge$ perceived-properties(?ob, ?features,
      ?sensor-model, ?pl) \\
      \> \> \> \> $\wedge$ local-desig(?desig,?ob,?pl,?x,?y)) \\
      \> \> \> ?desigs \\
      {\bf {\em (7)}} \> \> $\wedge$ look-time(\pos{?x}{?y}, ?features, ?dt)) \\
      {\bf {\em (8)}} \> \algkey{with a delay  of} 0 \algkey{occurs}
      \algkey{mode transition} begin(look-for(?pl, ?cam)) \\
      {\bf {\em (9)}}\> \algkey{with a delay  of} ?dt \algkey{occurs}
      \algkey{mode transition} end(look-for(?pl, ?cam)) \\
      {\bf {\em (10)}} \> \algkey{with a delay  of} 0 \algkey{occurs}
      \algkey{trigger fluent} visual-inputs-fluent(?cam) \\
      {\bf {\em (11)}} \> \algkey{with a delay  of} 0 \algkey{occurs}
       \algkey{set fluent} obs-pos-fluent $\leftarrow$ ?seen) \\
      {\bf {\em (12)}} \>  \algkey{with a delay  of} 0 \algkey{occurs}
      \algkey{succeed} ?desigs
    \end{tabbing}
  \end{it}

  \caption{A projection rule describing the behavior module
    \protect\textit{look-for}.}
  \label{fig:look-for}

\end{figure}

The condition of the projection rule determines where the robot is {\bf {\em
    (1)}}, probabilistically decides whether the \textit{look-for} is
``normal'' based on the camera used and the specifics of the location {\bf
  {\em (2)}}, and infers what objects are located there {\bf {\em (3)}}. This
inference is performed based on the robot's probabilistic belief about the
state of the world and the predicted exogenous events. The condition then uses
the sensor model for the camera in order to decide probabilistically how the
robot perceives each object. For each object that is perceived as matching the
perceptual description \textit{?pl} a local designator \textit{?desig} is
created and collected in the variable \textit{desigs}. The last condition {\bf
  {\em (7)}} estimates the time \textit{?dt} after which the \textit{look-for}
behavior completes.  Upon completion of the \textit{look-for} behavior the
projected interpretation process sends a success signal with the return value
\textit{?desigs} as its argument. The projected behavior consists of three
events: two that change the world \textit{begin(look-for(?pl, ?cam))} and
\textit{end(look-for(?pl, ?cam))}, which occurs \textit{?dt} later. The third
event changes the computational state of the structured reactive controller
after passing \textit{?dt} time units.  This event pulses the fluent
\textit{visual-inputs-fluent(?cam)} and sets the fluent
\textit{obs-pos-fluent(?cam)}.

Besides asserting the events that take place during the execution of a plan we
have to specify how these events change the world. This is done by using {\it
  effect rules}. One of them is shown in Figure!~\ref{fig:e-to-p-rule}. The
rule specifies that if at a time instant at which an event
\textit{end(look-for(?pl, ?cam))} occurs the state
\textit{visual-track(?desig, ?ob)} holds for some \textit{?desig} and
\textit{?ob}, then the states \textit{visual-track(?desig, ?ob)} will not
(with a probability of \textit{1.0}) persist after the event has occurred,
i.e., they are clipped by the event.

\begin{figure}[htb]

  \begin{it}
    \begin{tabbing}
      \algkey{e$\rightarrow$p rule} \textsc{visual-tracking} \\
      \algkey{if} \= visual-track(?desig, ?ob) \\
      \algkey{then} \= \algkey{with probability} \textit{0.9} \\
      \> \algkey{event} end(look-for(?pl, ?cam)) \\
      \> \algkey{causes} \= \algkey{clip} visual-track(?desig, ?ob))
    \end{tabbing}
  \end{it}

  \caption[An \protect\rc{E-$>$P}-rule describing the effects of
  an event.]{An \protect\algkey{e$\rightarrow$p} rule describing the effects
    of the event \protect\textit{end(look-for(?pl, ?cam))}.}
  \label{fig:e-to-p-rule}

\end{figure}


\subsection{Probabilistic Sampling-based Projection}
\label{sec:sampling}

So far we have looked at the issue of efficiently predicting an
individual execution scenario. We will now investigate the issue of
drawing inferences that are useful for planning based on sampled
execution scenarios.

Recently, probabilistic sampling-based inference methods have been
proposed to infer information from complex distributions quickly and
with bounded risk \cite{Fox99Mon,Thr99Mon}.  We will now discuss how
we can use sampling-based projection for anticipating likely flaws
with high probability.

% For the sample-based projection of complex \crp s we do not need to
% represent the complete hybrid automaton for a \crp\ in advance. Rather
% our plan projector extends the \xfrm\ projector so that it generates
% the parts of the \pham\ that are needed to project a sample scenario
% on the fly (see section~\ref{sec:adaptive-models} for details).  To do
% so, the projector extracts the jump conditions from the conditions the
% interpreter is waiting for (for example, the {\footnotesize
%   \algkey{wait for}} statements in the \crp\ shown in
% figure~\ref{fig:rpl-plan}). It also signals predicted control mode
% jumps to and thereby tells the interpreter component of the projector
% to continue with the projection of the subsequent plan steps.

% \textit{jumpRelation} and \textit{jumpSuccessor} are generated using
% probabilistic models of low level control processes and their physical
% effects.

% The projector probabilistically samples from the probability
% distributions defined for the initial state, exogenous events,
% probabilistic effects, and probabilistic control mode transitions.

Advantages of applying probabilistic sampling-based projection to the
prediction of the effects of \crp s are that it works independently of the
branching factor of the modes of the hybrid automaton and that it only
constructs a small part of the complete \pham.

But what kinds of prediction-based inferences can be drawn from
samples of projected execution scenarios?  The inference that we found
most valuable for online revisions of robot plans is: do projected
execution scenarios drawn from this distribution satisfy a given
property $p$ with a probability greater than $\theta$? A robot action
planner can use this type of inference to decide whether or not it
should revise a plan to eliminate a particular kind of flaw: it should
revise the plan if it believes that the flaw's likelihood exceeds some
threshold and ignore it otherwise. Of course, such inferences can be
drawn based on samples only with a certain risk of being wrong.
Suppose we want the planner to classify any flaw with probability
greater than $\theta$ as to be eliminated and to ignore any flaw less
likely than $\tau$.  We assume that flaws with probability between
$\tau$ and $\theta$ have no large impact on the robot's performance.
How many execution scenarios should the plan revision module project
in order to classify flaws correctly with a probability greater than
95\%?

%To start our discussion let us assume that we have a function \mt{rse}
%that maps the belief state of the agent into a possible execution
%scenario that is randomly drawn from the probability distribution over
%execution scenarios implied by the belief state of the agent. Further
%we assume a second function \mt{fail$_i$}\textit{(es)} that returns a
%failure \mt{ft} if the execution scenario es contains a failure event
%of type \textit{i}. Now, \mt{fail$_i$(res(bs))} can be considered as a
%detector that detects flaws of failure type \textit{i} that are
%possible with respect to the belief state \textit{bs}.

%This detector function is not reliable. It guesses the existence of a
%schedule flaw. If the belief state of the agent implies a probability
%distribution on possible execution scenarios where $\psi$ is the
%percentage of possible execution scenarios that contain a failure of
%type \textit{i} then the detector function will detect the flaw with
%probability $\psi$.

A main factor that determines the performance of sample-based
predictive flaw detection is the \emph{flaw detector}. A flaw detector
classifies a flaw as to be eliminated if the probability of the flaw
with respect to the robot's belief state is greater than a given
threshold probability $\theta$. A flaw detector classifies a flaw as
hallucinated if the probability of the flaw with respect to the
robot's belief state is smaller than a given threshold $\tau$. So far
we do not consider the severity of flaws, which is an obvious
extension.  Typically, we choose $\theta$ starting at 50\% and $\tau$
smaller than 5\%.

Specific flaw detectors can be realized that differ with respect to
(1)~the time resources they require; (2)~the reliability with which
they detect flaws that should be eliminated; and (3)~the probability
that they hallucinate flaws. That is, they signal a flaw that is so
unlikely that eliminating the flaw would decrease the expected
utility.

% \[ X_i(f) = \left\{ \begin{array}{r@{\quad:\quad}l}
%                       1 & f \mbox{occurs in the \textit{i}th
%                       projection} \\
%                       0 & \mbox{otherwise }
%                     \end{array} \right.
% \]

To be more precise consider a flaw \textit{f} that occurs in the
distribution of execution scenarios of a given scheduled plan with
respect to the agent's belief state with probability p. Further, let
\textit{X$_i$(f)} represent the event that behavior flaw \textit{f}
occurs in the \textit{i}th execution scenario: $X_i(f) = 1$, if $f$
occurs in the \textit{i}th projection and $0$ otherwise.

The random variable \textit{Y(f,n) = $\sum_{i=1}^n$X$_i$(f)}
represents the number of occurrences of the flaw \textit{f} in
\textit{n} execution scenarios.  Define a probable schedule flaw
detector \textit{\textsc{Det}} such that \textit{\textsc{Det}(f,n,k) =
  true iff Y(f,n) $\geq$ k}, which means that the detector classifies
a flaw \textit{f} as to be eliminated if and only if \textit{f} occurs
in at least \textit{k} of \textit{n} randomly sampled execution
scenarios. Thus \textit{\textsc{Det}(f,n,k)} works as follows. It
first projects \textit{n} execution scenarios. Then it counts the
number of occurrences of the flaw \textit{f} in the \textit{n}
execution scenarios.  If it is greater or equal to \textit{k} then the
\textit{\textsc{Det}(f,n,k)} returns true, false otherwise.

Now that we have defined the schedule flaw detector, we can
characterize it.  Since the occurrence of schedule flaws in randomly
sampled execution scenarios are independent from each other, the value
of \textit{Y(f)} can be described by the binomial distribution
\textit{b(n,p)}.  Using \textit{b(n,p)} we can compute the likelihood
of overlooking a probable schedule flaw \textit{f} with probability
\textit{p} in \textit{n} execution scenarios:

% \vspace{-5ex}

\[ P(Y(f)<j) = \sum^{j-1}_{k=0} \left( \begin{array}{c}
                                          n \\ k
                                        \end{array}
                                      \right) * p^k * (1-p)^{n-k}
\]

% \vspace{-3ex}

Figure~\ref{fig:performance-table} shows the probability that the flaw
detector \textit{\textsc{Det}(f,n,2)} for \textit{n} = 3,...,5 will
detect a schedule flaw with probability $\bm{\theta}$. The probability
that the detectors classify flaws less likely than $\tau$ as to be
eliminated is smaller than 2.3\% (for all \textit{n}$\leq$5).

\begin{figure}[tb]
  \begin{center}
    \begin{tabular}{|l|l|l|l|l|l|}
      \hline
      & \multicolumn{5}{|c|}{Prob.\ of Flaw $\bm{\theta}$} \\
      & 50\% & 60\% & 70\% & 80\% & 90\% \\
      \hline
      \textit{\textsc{Det}(f,3,2)} & 50.0 & 64.8 & 78.4 & 89.6 & 97.2  \\
      \hline
      \textit{\textsc{Det}(f,4,2)} & 68.8 & 81.2 & 91.6 & 97.3 & 99.6 \\
      \hline
      \textit{\textsc{Det}(f,5,2)} & 81.2 & 91.3 & 96.9 & 99.3 & 99.9 \\
      \hline
    \end{tabular}
  \end{center}
  \caption{The table shows the probability of the flaw detectors
        \textit{\textsc{Det}(f,i,2)} detecting flaws that have the probability
        $\bm{\theta}$ = 50\%, 60\%, 70\%, 80\%, and 90\%.}
  \label{fig:performance-table}
\end{figure}

When using the prediction-based scheduling as a component in the controller of
the robot office courier we typically use \textit{\textsc{Det}(f,3,2)},
\textit{\textsc{Det}(f,4,2)}, and \textit{\textsc{Det}(f,5,2)} for the
different experiments, which means a detected flaw is classified as probable if
it occurs at least twice in three, four, or five detection readings.

% Taking a single reading takes about three to eight seconds depending
% on the complexity of the plan and the number of probabilistically
% occurring exogenous events. This enables the robot to perform a
% schedule debugging step in less than thirty seconds (on average).

Figure~\ref{fig:performance-table2} shows the number of necessary
projections to achieve $\beta=95\%$ accuracy. For a detailed
discussion see the work of \citeA{Bee99Pro}.

% Given that in $n$ randomly sampled execution scenarios are $m$
% scenarios that satisfy property $p$, is the probability of scenarios
% satisfying $p$ is smaller than $\tau$?

\begin{figure}[htbp]

  \begin{center}
    \begin{tabular}{|l|c|c|c|c|c|c|}
      \hline
      & \multicolumn{6}{|c|}{$\bm{\theta}$} \\
      & 1\% & 10\% & 20\% & 40\% & 60\% & 80\% \\
      \hline
      $\bm{\tau=} .1\%$ &1331 & 100 &44 & 17 & 8 & 3\\
      \hline
      $\bm{\tau=} 1\%$ & $\perp$ & 121 & 49 & 17 & 8 & 3\\
      \hline
      $\bm{\tau=} 5\%$ & $\perp$ & 392 & 78 & 22 & 9 & 3\\
      \hline
    \end{tabular}
  \end{center}

  \caption{The table lists the number of randomly sampled projections
    needed to differentiate failures with an occurrence probability
    lower than $\bm{\tau}$ from those that have a probability higher
    than $\bm{\theta}$ with an accuracy of 95\%.}
  \label{fig:performance-table2}

\end{figure}

The probabilistic sampling-based projection mechanism becomes extremely useful
for improving robot plans during their execution once the execution scenarios
can be sampled fast enough. At the moment a projection takes a couple of
seconds. The overhead is mainly caused by recording the interpretation of
\rpl\ plans in a manner that is far too detailed for our purposes.  Through a
simplification of the models we expect an immediate speed up of up to one
order of magnitude. It seems that with a projection frequency of about 100~Hz
one could start tackling a number of realistic problems that occur at
execution time continually.



\section{Evaluation}
\label{sec:evaluation}

We have validated our causal model of low-level navigation plans and their
role in office delivery plans with respect to computational resources and
qualitative prediction results in a series of experiments.


\subsection{Generality}

\pham s are capable of predicting the behavior generated by flexible
plans written in plan execution languages such as RAP \cite{Fir87RAP}
and PRS \cite{Mye96Pro}. To do so, we code the control structures
provided by these languages as \rpl\ macros. To the best of our
knowledge \pham s are the first realistic symbolic models of the
sequencing layer of 3T architectures, the most commonly used software
architectures for controlling intelligent autonomous robots
\shortcite{Bon97TTT}. These architectures run planning and execution
at different software layers and different time scales where a
sequencing layer synchronizes between both layers. Each layer uses a
different form of plan or behavior specification language. The
planning layer typically uses a problem space plan, the execution
layer employs feedback control routines that can be activated and
deactivated.  The intermediate layer typically uses a reactive plan
language. The use of \pham s enables 3T planning systems to make more
realistic predictions of the robot behavior that is generated from
their abstract plans.  \pham s are also capable of modeling different
arbitration schemes and superpositions of the effects of concurrent
control processes.

The causal models proposed here complement those introduced by
\citeA{Bee00Con}.  He describes sophisticated models of object
recognition and manipulation that allow for the prediction of plan
failures including those that are caused by the robot overlooking or
confusing objects, objects changing their location and appearance, and
faulty operation of effectors.  These models, however, were given for
a simulated robot acting in a grid world. In this article, we have
restricted ourselves to the prediction of behavior generated by modern
autonomous robot controllers. Unfortunately, object recognition and
manipulation skills of current autonomous service robots are not
advanced enough for action planning. On the other hand, it is clear
that action planning capabilities pay off much better if robots
manipulate their environments and there is a risk of manipulating the
wrong objects.


\subsection{Assumptions and Restrictions}

The control problem for autonomous robots is to generate effective and
goal-directed control signals for the robot's perceptual and effector
apparatus within a feedback loop. Plan-based robot control is a
specialization of this control problem, in which the robot generates
the control signals by maintaining and executing a plan that is
effective and has a high expected utility with respect to the robot's
dynamically changing belief state.  This problem is so general that we
cannot hope to solve it in this form.

In Computer Science it is common to characterize the computational problems a
program can solve through the language in which the input for the program is
specified.  For example, we distinguish compilers for regular and context-free
programming languages. The same is true for plan-based control of agents.
Typically, planning problems are described in terms of an initial state
description, a description of the actions available for the agents, their
applicability conditions and effects, and a description of the goal state.

The three components of planning problems are typically expressed in some
formal language. The problem solving power of the planning systems is
characterized by the expressiveness of the languages for the three inputs.
Some classes of planning problems are entirely formulated in propositional
logic while others are formulated in first order logic. We further classify
the planning problems with respect to the expressiveness of the action
representations that they use; whether they allow for disjunctive
preconditions, conditional effects, quantified effects, and model resource
consumption. Some planning systems even solve planning problems that involve
different kinds of uncertainty.

In contrast, \src s use methods that make strong assumptions about plans to
simplify the computational problems. As a consequence, \src s can apply
reliable and fast algorithms for the construction and installment of
sub-plans, the diagnosis of plan failures, and for editing sub-plans during
their execution.  Making assumptions about plans is attractive because
planning algorithms construct and revise the plans and can thereby enforce
that the assumptions hold.

In a nutshell, the set of plans that an \src\ generates is the reflexive,
transitive closure of the routine plans with respect to the application of
plan revision rules.  Thus, to enforce that all plans have a property
\textit{Q} it is sufficient that the routine plans satisfy \textit{Q} and that
the revision rules preserve \textit{Q}.  These properties make it particularly
easy to reason about the plans while the plans can still specify the same
range of concurrent percept-driven behavior that \rpl\ can. The properties of
plans that play an important role in this article are their generality,
flexibility, and reliability. These properties are achieved through careful
design and hand-coding. As a consequence plan generation and revision can be
performed by programmed heuristic rules. We believe, however, that such plans
and rules can be learned from experience.

We make two other important assumptions. First, we assume that the
tasks and the environment is benign and therefore behavior flaws do
not result in disasters. This is important, because robots must make
errors in order to learn the competent performance of tasks from
experience. And only if the planner is allowed occasionally to propose
worse plans we can apply fast planning methods based on Monte Carlo
methods to improve the average performance of the robot.

Another design decision is that we do not explicitly represent the
belief state of the robot, that is the probability distributions over
the values of the state variables. This, however, does not need to
imply that we cannot reason about inaccuracies and uncertainties of
the robot's estimate of the world state. \citeA{Bee98Int} describe how
to couple plan-based high-level control with probabilistic state
estimation. In this article the state estimator automatically computes
and signals properties of the belief state such as the ambiguity and
inaccuracy of state estimates to the plan-based controller. The
plan-based controller, on the other hand, uses these signals in order
to decide when to interrupt its missions to re-localize the robot.


\subsection{Scaling Up}

The causal models that we have described in Section~\ref{sec:monte-carlo} have
been used for execution time planning for a robot office courier. The plans
that have been projected were the original plans for this application and
typically several hundreds of code lines long. The projected execution
scenarios contained hundreds of events. Because the projection of single
execution scenarios can cost up to a second, robots must revise plans based on
very few samples. Thus, the robot can only detect probable flaws with high
reliability.

The computational resources are mainly consumed by bookkeeping
mechanisms that record the computational state of the robot at any
time instant represented in the execution scenario and not by the
mechanisms proposed in this article. The recorded computational state
is used by the planning mechanisms in order to diagnose behavior flaws
that are caused by discrepancies between the computational state of
the robot and the state of the environment. The ability to reconstruct
regularly updated fluent values is computationally very costly. We
intend to provide programming constructs that let programmers declare
the parts of the computational state that are irrelevant for planning
and do not need to be recorded.

Even with this severe limitation we were able to show that with this
preliminary implementation the robot can outperform controllers that lack
predictive capabilities. The main source of inefficiency is the bookkeeping
needed to reconstruct the entire computational state of the plan for any
predicted time instant, an issue that we have not addressed in this article.
Using a more parsimonious representation of the computational state we expect
drastic performance gains.


\subsection{Qualitatively Accurate Predictions}

Projecting the plan listed in Figure~\ref{fig:office-delivery-plan}
generates a timeline that is about 300 events long. Many of these
events are generated through rescheduling the endogenous events
(21~times).  Figure~\ref{fig:experiment} shows the predicted
endogenous events (denoted by the numbered circles) and the behavior
generated by the navigation plan in 50 runs using the robot simulator
(we assume that the execution is interrupted in room A-111 because the
robot realizes that the deadline can not be achieved).  The
qualitative predictions of behavior relevant for plan debugging are
perfect. The projector predicts correctly that the robot will exploit
the opportunity to go to location 5 while going from location~1 to 9.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=0.65\textwidth]{PICS/aij.eps}
  \end{center}
  \caption[Comparison of projected and simulated navigation behavior.]%
  {The figure shows the trajectories of multiple executions of the navigation
    plan and the events that are predicted by the symbolic plan projector.}
  \label{fig:experiment}
\end{figure}

% The projector was also able to predict perfectly the relevant qualitative
% aspects of the other introductory example: whether or not the robot bumps into
% tables in front of door A-111.


% Again, this treatment is based on the introductory example.
% This time the robot receives no external evidence that the door to
% a-113 might be open. Instead, the controller periodically projects its
% intended course of action in the light of its current belief state. If
% the projection predicts an execution failure, the controller search
% for an alternative, which gets executed. The task of searching for a
% new plan is beyond the scope of this paper - we just assume that the
% controller will determine a new plan in a given time.

% Let us return to the example: upon passing a-113, the robot notices that the
% door is open, and projects it's current remaining plan under the premise that
% a-113 is open\footnote{In order to avoid restarting at the initial position,
%   the controller would have to memorize which letters are already loaded.}.
% Figure~\ref{fig:expproj} pictures the projected course of action, which
% lead's to a violation of the deadline for letter to A-120.

% \begin{figure}[htbp]
%   \begin{center}
%     \includegraphics[width=0.85\textwidth]{PICS/expproj.ps}
%   \end{center}
%   \caption[A projected trajectory.]
%   {The figure shows an example projection of the plan discussed in this
%     section.}
%   \label{fig:expproj}
% \end{figure}

% Upon realizing that the current plan will result in a flaw, the
% controller starts searching for a better plan. This task has to be
% achieved quickly in order to enable the robot to react in time to
% achieve its tasks in time. As mentioned, we don't study this part of
% the robot's architecture. Instead, we determine the magnitude of the
% number of projection which might be generated to guide the search
% under real-time conditions.


% \subsection{The Effect of Fast Projection on Navigation Performance}

% In the next experiment, we investigate the importance of fast
% projections in order to yield an effective improvement of the robot's
% behavior. The robot navigates along the hallway and notices an open
% door that might constitute an opportunity. Through predictions the
% robot infers that it should better ignore the opportunity.
% Figure~\ref{fig:exp5} shows the resulting trajectory if the robot
% makes use of 5 and 10 projections in order to determine a better plan
% (in these examples, the improved behavior essentially postpones the
% opportunity). In case it takes 10 projections to react, the resulting
% behavior is very inefficient: the robot wastes time by navigating back
% and forth.

% \begin{figure}[htb]

%   \begin{center}
%     \begin{tabular}{cc}
%       \includegraphics[width=0.48\textwidth]%
%       {PICS/exp5a.ps} &
%       \includegraphics[width=0.48\textwidth]%
%       {PICS/exp5c.ps} \\
%       (a) & (b)
%     \end{tabular}


%   \end{center}

%   \caption[Effect of spending more time for more reliable predictions.]
%   {The figure shows the effects spending more time to obtain more reliable
%     predictions. Subfigure~(a) shows the behavior of the robot when revising
%     its plan after making one and subfigure~(b) after making five
%     projections.}
%   \label{fig:exp5}
% \end{figure}


\subsection{Prediction-based Plan Debugging}
\label{sec:planning}

Beetz (\citeyearR{Bee02Pla} and
\citeyearR{Bee00Con}) describes experiments showing that
prediction-based plan debugging can improve the performance of robot
controllers substantially.

\section{Related Work}
\label{sec:related-work}

\pham s represent external events, probabilistic action models, action
models with rich temporal structure, concurrent interacting actions,
and sensing actions in the domain of autonomous mobile robot control.
There are many research efforts that formalize and analyze extended
action representations and develop prediction and planning techniques
for them. We know, however, only of approaches that address subsets of
the aspects addressed by our representation.  Related work comprises
research on reasoning about action and change, probabilistic planning,
numerical simulation, and qualitative reasoning.

\paragraph*{Reasoning about action and change.}
\citeA{All94Act} give an excellent and detailed discussion of
important issues in the representation of temporally complex and
concurrent actions and events. One important point that they make is
that if actions have interfering effects then, in the worst case,
causal models for all possible combinations of actions must be
provided. In this paper, we have restricted ourselves to one kind of
interference between actions: the transposition of movements which is
the dominant kind of interference in physical robot behavior.  In
their article they do not address the issues of reasoning under
uncertainty and efficiency with respect to computational resources.

A substantial amount of work has been done to extend the situation
calculus \cite{McC63Sit} to deal with time and continuous change
\cite{Pin94Tem,Gro00ccg}, exogenous (natural) actions \cite{Rei96Nat},
complex robot actions (plans) \shortcite{Lev97GOL,Gia97Rea} using
sensing to determine which action to execute next
\cite{Lev96Wha,Lak99CAT} as well as probabilistic state descriptions
and probabilistic action outcomes \cite{Bac99Noi,Gro00Tur}.  The main
difference to our work is that their representation is more limited
with respect to the kinds of events and interactions between
concurrent actions they allow. In particular, we know of no effort to
integrate all of these aspects.

Some of the most advanced approaches in this area are formalizations
of various variants of the high-level robot control language
\textsc{Golog}, in particular \textsc{ConGolog} \cite{Gia97Rea}.
\citeA{Bou00Dec} have applied decision theoretic means for optimally
completing a partially specified \textsc{Golog} program.  A key
difference is that in the \textsc{Golog} approach the formalization
includes the operation of the plan language whereas in our approach a
procedural semantics realized through the high-level projector is
used.

\citeA{Han95Pro} present a very interesting and expressive framework
for representing probabilistic information, and exogenous and
endogenous events for medical prediction problems.  Because of their
application domain they do not have to address issues of sophisticated
percept-driven behavior as is done in this article.

\paragraph*{Extensions to Classical Action Planning Systems.}
Planning algorithms, such as {\sc snlp} \cite{McA91Sys}, have been
extended in various ways to handle more expressive action models and
different kinds of uncertainty (about the initial state and the
occurrence and outcome of events) \cite{Kus95Alg,Dra94Pro,Han90Pra}.
These planning algorithms compute bounds for the probabilities of plan
outcomes and are computationally very expensive.  In addition,
decision-theoretic action planning systems \cite<see>[for a
comprehensive overview]{Bly99Dec}
have been proposed in order to determine plans
with the highest, or at least, sufficiently high expected utility
\cite{Had90Pla,Had92Rep,Wil94Uti}. These approaches abstract away from
the rich temporal structure of events by assuming discrete atomic
actions and ignore various kinds of uncertainty.

Planning with action models that have rich temporal structure has also
been investigated intensively \cite{All90Rea,Dea88Hie}. IxTeT
\cite{Gha94Rep} is a planning system that has been applied to robot
control and reasons about the temporal structure of plans to identify
interferences between plan steps and resource conflicts. The
planner/scheduler of the Remote Agent \shortcite{Mus98Rem} plans space
maneuvers and experiments based on rich temporal causal models
\shortcite{Mus98Iss,Pel97Rob}. A good overview of the integration of
action planning and scheduling technology can be found in an overview
article by \citeA{Smi00Bri}. So far they have considered uncertainty
only with respect to the durations of actions.

\citeA{Kab97Pla} model actions and behaviors as state transition
systems and synthesize control rules for reactive robots from these
descriptions. Their approach can be used to generate plans that
satisfy complex time, safety, and liveness constraints. These
approaches too are limited with respect to the temporal structure of
the (primitive) actions being modeled and the kinds of interferences
between concurrent actions that can be considered.

\paragraph*{MDP-based planning approaches.}
In recent years \textsc{mdp} (Markov decision process) planning has
become a very active research field \cite{Bou98Dec,Kae96Act}.  In the
\textsc{mdp} approach robot behavior is modeled as a finite state
automaton in which discrete actions cause stochastic state
transitions. The robot is rewarded for reaching its goals quickly and
reliably.  A solution for such problems is a \textit{policy}, a
mapping from discretized robot states into, often fine-grained,
actions.

\textsc{mdp}s form an attractive framework for action planning because
they use a uniform mechanism for action selection and a parsimonious
problem encoding.  The action policies computed by \textsc{mdp}s aim
at robustness and optimizing the average performance. A number of
researchers have successfully considered navigation as an instance of
Markov decision problems (\textsc{mdp}s)
\shortcite{Bur00Exp,Kae96Act}.

One of the main problems in the application of \textsc{mdp} planning
techniques is to keep the problem encoding small enough so that the
\textsc{mdp}s are still solvable.  A number of techniques for
complexity reduction can be found in the article written by
\shortciteA{Bou98Dec}.  Yet, it is still very difficult to solve big
planning problems in the \textsc{mdp} framework unless the state and
action spaces are well structured.

Besides reducing the complexity of specifying models for, and solving
\textsc{mdp} problems, extending the expressiveness of \textsc{mdp}
formalisms is a very active research area. Semi Markov decision
problems \cite{Bra95Rei,Sut99Bet} add a notion of continuous time to
the discrete model of change used in \textsc{mdp}s: transitions from
one state to another one no longer occur immediately, but according
to a probability distribution.  Others investigate mechanisms for
hierarchically structuring \textsc{mdp}s \cite{Par98Rei}, decomposing
\textsc{mdp}s into loosely coupled sub-problems \cite{Par98Fle}, and
making them programmable \cite{And01Pro}.  \citeA{Roh01Dec} propose an
approach for extending \textsc{mdp}-based planning to concurrent
temporally extended actions. All these efforts are steps towards the
kind of functionality provided in the \pham\ framework. Another
relationship between the research reported here and the \textsc{mdp}
research is that the navigation routines that are modeled with \pham s
are implemented on top of \textsc{mdp} navigation planning.
\citeA{Bel02Lea} use the \textsc{mdp} framework to learn action
models for the improved execution of navigation plans.

The application of \textsc{mdp} based planning to reasoning about
concurrent reactive plans is complicated by the fact that, in general,
any activation and termination of a concurrent sub-plan might require
a respective modification of the state and action space of the
\textsc{mdp}.

Weaver \cite{Bly95Ext,Bly96Dec} is another probabilistic plan debugger capable
of reasoning about exogenous events. Weaver uses Markov decision processes as
its underlying model of planning. Weaver provides much of the expressiveness
of \pham s. Unlike Weaver, \pham s are designed for reasoning about the
physical behavior of autonomous mobile robots. Therefore, \pham s add to
Weaver's expressiveness in that they extensively support reasoning about
concurrent reactive plans. For example, \pham s can predict when the
continuous effects of actions will trigger a concurrent monitoring process.
\pham s have built-in capabilities to infer the combined effects of two
continuous motions of the robot.

% \textsc{(po)mdp} planners
% aim at precomputing the best decisions under uncertainty for all
% situations that an agent might face. So far, this approach has been
% feasible only for small or at least well-structured state spaces and
% has difficulties in handling concurrent and continuous actions with
% interfering effects.  Related approaches aim at the anytime synthesis
% of plans that are increasingly robust \cite{Dea93Pla,Dru90Any}. Others
% look at hierarchically structuring

% However, this feature cannot be used so
% significantly reduce the state space needed to represent problems like those
% discussed in this paper.


\paragraph*{Qualitative reasoning about physical processes.}
Work in qualitative reasoning has researched issues in the
quantization of continuous processes and focussed among other things
on quantizations that are relevant to the kind of reasoning performed.
\citeA{Hen73Mod} points out the limitations of discrete event
representations and introduces a very limited notion of continuous
process as a representation of change. He does not consider the
influence of multiple processes on state variables.  \citeA{Hay85Phy}
represents events as \textit{histories}, spatially bounded, but
temporally extended, pieces in time space, and proposes that histories
which do not intersect do not interact. In Forbus' Qualitative Process
Theory \cite{For84QPT} a technique called limit analysis is applied to
predict qualitative state transitions caused by continuous events.
Also, work on simulation often addresses the adequacy of causal models
for a given range of prediction queries, an issue that is neglected in
most models used for AI planning.  Planners that predict qualitative
state transitions caused by continuous events include
\textsc{excalibur} \cite{Dra93Exc}.


\paragraph*{Planning as model checking.}
Planning as model checking \cite{Ber01Pla,Cim00Con} represents domains
as finite-state systems.  Planning problems are solved by searching
through the state space, checking for the existence of a plan that
satisfies the goals.  Goals are formalized as logical requirements
about the desired behavior for plans. Unlike planning as model
checking we consider continuous control processes, plan interpretation
as well as the physical effects of actions, and concurrency. This
extended representational power comes at the cost of probably finding
behavior flaws rather than proving their absence.


\paragraph*{Design and verification of embedded systems based on hybrid
  automata.} The formalization of embedded software systems
\cite{Alu97Sym,Alu96Aut} using hybrid automata aims at proving critical
aspects of the software rather than the physical effects of running this
software. In our approach we have used the ideas of this research field as the
basis of our conceptualization but added additional mechanisms to model the
effects of actions and sensing mechanisms. Again, the additional complexity
of our model is compensated by solving more restrictive inference problems:
the detection of probable behavior flaws with high probability rather than
safety of the system and the reachability of goals.


\section{Conclusion}
\label{sec:conclusion}

The successful application of AI planning to autonomous mobile robot
control requires the planning systems to have more realistic models of
the operation of modern robot control systems and the physical effects
caused by their execution.  In this article we have presented
\emph{probabilistic hybrid action models (\pham s)}, which are capable
of representing the temporal structure of continuous feedback control
processes, their non-deterministic effects, several modes of their
interferences, and exogenous events. We have shown that \pham s allow
for predictions that are, with high probability, qualitatively
correct. We have also shown that powerful prediction-based inferences
such as deciding whether a plan is likely to cause a flaw with a
probability exceeding a given threshold can be drawn fast and with
bounded risk.

We believe that equipping autonomous robot controllers with concurrent
reactive plans and prediction-based online plan revision based on \pham s is a
promising way to improve the performance of autonomous service robots through
AI planning both significantly and substantially.

The rules that we have used for projecting navigation behavior were hand-coded
and plan and possibly even environment specific. On our research agenda is the
development of transformational mechanisms for learning high performance and
task specific plans. After having learned the plans the robot should then
learn the projection rules by applying data mining techniques to the plan
execution traces. To enable this approach we must invent novel
representational mechanisms for the plans that allow for the automatic
extraction of the rules. Initial steps into this direction can be found in
the work of \citeA{Bel02Lea,Bee00Env,Bee02Rep}.


\bibliography{/home/beetz/OLD-TEXTS/BIB/defs,/home/beetz/OLD-TEXTS/BIB/michael,%
  /home/beetz/OLD-TEXTS/BIB/bibliography}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
