\batchmode
\documentclass[11pt,twoside]{article}
\makeatletter
\usepackage{named,jair}
\usepackage{epsfig,colortbl}


















\newlength{\picwidth}
\setlength{\picwidth}{\textwidth}






































\title{Markov Localization for Mobile Robots \\ in Dynamic Environments}


\author{\name Dieter Fox \email dfox@cs.cmu.edu\\ 
  \addr Computer Science Department and Robotics
  Institute\\  Carnegie Mellon University\\  Pittsburgh, PA 15213-3891 \\ 
  \AND Wolfram Burgard \email burgard@informatik.uni-freiburg.de\\ 
  \addr Department of Computer Science\\  University of Freiburg\\ 
  D-79110 Freiburg, Germany\\ 
  \AND Sebastian Thrun \email thrun@cs.cmu.edu \\ 
  \addr Computer Science Department and Robotics
  Institute\\  Carnegie Mellon University\\  Pittsburgh, PA 15213-3891 \\ 
  }


\newcommand {\ddd}[1]{\texttt{#1}}

\newcommand {\secRef}[1]{Section~\ref{#1}}

\newcommand {\eqRef}[1]{Equation~(\ref{#1})}

\newcommand {\tabRef}[1]{Table~\ref{#1}}

\newcommand {\rect}[3]{$#1 \times #2$#3$^2$}

\newcommand {\figRef}[1]{Figure~\ref{#1}}

\newcommand {\figDRef}[2]{Figure~\ref{#1}(#2)}

\newcommand {\figDoubleRef}[3]{Figures~\ref{#1}~(#2) and (#3)}

\newcommand {\plusminus}[2]{$ #1 $ ~ {\footnotesize $\pm \; #2 $}}

\newcommand {\plusm}[2]{$ #1 ${$\pm #2 $}}

\newcommand {\todo}[1]{\begin{center}\bf [#1]\end{center}}

\newcommand {\fig}[6]{
  \begin{figure}[htb]
    \leavevmode
    \begin{center}
      \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}}
    \end{center}
    \refstepcounter{figure}
    \hspace*{\fill}
    \begin{center}
      \parbox[t]{\picwidth}
      {\vspace{-#5ex}\center{\emph{Fig.~\thefigure. #3}}}\label{#1}
    \end{center}
    \hspace*{\fill}
    \vspace{-#6ex}
  \end{figure}}

\newcommand {\figPut}[7]{
  \begin{figure}[htb]
    \leavevmode
    \begin{center}
      \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}
        \unitlength1mm #7}\end{center}
    \refstepcounter{figure}
    \hspace*{\fill}
    \begin{center}
      \parbox[t]{\picwidth}
      {\vspace{-#5ex}{\emph{Fig.~\thefigure. #3}}}\label{#1}
    \end{center}
    \hspace*{\fill}
    \vspace{-#6ex}
  \end{figure}}

\newcommand {\figPutCenter}[7]{
  \begin{figure}[htb]
    \leavevmode
    \begin{center}
      \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}
        \unitlength1mm #7}\end{center}
    \refstepcounter{figure}
    \hspace*{\fill}
    \begin{center}
      \parbox[t]{\picwidth}
      {\vspace{-#5ex}\center{\emph{Fig.~\thefigure. #3}}}\label{#1}
    \end{center}
    \hspace*{\fill}
    \vspace{-#6ex}
  \end{figure}}

\newcommand {\doubleFig}[9] {
  \begin{figure}[htb]
    \leavevmode
    \hspace*{\fill}
    \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#6,width=#8\picwidth,clip=}}
    \hspace*{\fill} \vspace{2ex}
    \begin{trivlist}
    \item[]
      \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{#4\picwidth}
      {\vspace{-6ex}\center{\emph{Fig.~\thefigure. #3}}}\label{#1}
      \hspace*{\fill} \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{#8\picwidth}
      {\vspace{-6ex}\center{\emph{Fig.~\thefigure. #7}}}\label{#5}
      \hspace*{\fill}
    \end{trivlist}
    \vspace{-#9ex}
  \end{figure}
  }

\newcommand {\doubleFigOneTitle}[9] {
    \begin{figure}[t]
    \leavevmode
    \hspace*{\fill}
    \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}
      \put(#8,#9){\footnotesize \textbf{(a)}}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#5,width=#6\picwidth,clip=}
      \put(#8,#9){\footnotesize \textbf{(b)}}}
    \hspace*{\fill} \vspace{2ex}
    \begin{trivlist}
    \item[]
      \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{\picwidth}
      {\vspace{-6ex}\center{\small{Fig.~\thefigure. #3}}}\label{#1}
      \hspace*{\fill} \hspace*{\fill}
    \end{trivlist}
    \vspace{-#7ex}
  \end{figure}
  }

\newcommand {\doubleFigOneTitleStar}[9] {
    \begin{figure}[htb]
    \leavevmode
    \hspace*{\fill}
    \epsfig{file=#2,height=#4cm,clip=}
    \put(#8,#9){\footnotesize \emph{(a)}}\hspace*{\fill}\hspace*{\fill}
    \epsfig{file=#5,height=#4cm,clip=}
    \put(#8,#9){\footnotesize \emph{(b)}}\hspace*{\fill} \vspace{2ex}
    \begin{trivlist}
    \item[]
      \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{\picwidth}
      {\vspace{-6ex}\center{\emph{Fig.~\thefigure. #3}}}\label{#1}
      \hspace*{\fill} \hspace*{\fill}
    \end{trivlist}
    \vspace{-#7ex}
  \end{figure}
  }

\newcommand {\doubleFigOneTitleLeft}[9] {
    \begin{figure}[htb]
    \leavevmode
    \hspace*{\fill}
    \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(a)}}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#5,width=#6\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(b)}}}
    \hspace*{\fill} \vspace{2ex}
    \begin{trivlist}
    \item[]
      \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{\picwidth}
      {\vspace{-4ex}{\emph{Fig.~\thefigure. #3}}}\label{#1}
      \hspace*{\fill} \hspace*{\fill}
    \end{trivlist}
    \vspace{-#7ex}
  \end{figure}
  }

\newcommand {\doubleFigOneTitleNoFrame}[9] {
    \begin{figure}[htb]
    \leavevmode
    \hspace*{\fill}
    \epsfig{file=#2,width=#4\picwidth,clip=}
    \put(#8,#9){\footnotesize \emph{(a)}}\hspace*{\fill}\hspace*{\fill}
    \epsfig{file=#5,width=#6\picwidth,clip=}
    \put(#8,#9){\footnotesize \emph{(b)}}\hspace*{\fill} \vspace{2ex}
    \begin{trivlist}
    \item[]
      \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{\picwidth}
      {\vspace{-7ex}\center{\emph{Fig.~\thefigure. #3}}}\label{#1}
      \hspace*{\fill} \hspace*{\fill}
    \end{trivlist}
    \vspace{-#7ex}
  \end{figure}
  }

\newcommand {\doubleFigStack}[9] {
    \begin{figure}[htb]
    \leavevmode
    \hspace*{\fill}
    \fbox{\epsfig{file=#3,width=#7\picwidth,clip=}
      \put(-12,2){\footnotesize \emph{(a)}}}
    \hspace*{\fill}
    \fbox{\epsfig{file=#4,width=#7\picwidth,clip=}
      \put(-12,2){\footnotesize \emph{(b)}}}
    \hspace*{\fill}\\ [1.5ex]
    \hspace*{\fill}
    \fbox{\epsfig{file=#5,width=#7\picwidth,clip=}
      \put(-12,2){\footnotesize \emph{(c)}}}
    \hspace*{\fill}
    \fbox{\epsfig{file=#6,width=#7\picwidth,clip=}
      \put(-12,2){\footnotesize \emph{(d)}}}
    \hspace*{\fill}
    \begin{trivlist}
    \item[]
      \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{\picwidth}
      {\vspace{-#8ex}{\emph{Fig.~\thefigure. #2}}}\label{#1}
      \hspace*{\fill} \hspace*{\fill}
    \end{trivlist}
    \vspace{-#9ex}
  \end{figure}
  }

\newcommand {\doubleFigOneTitlePut}[9] {
  \begin{figure}[htb]
    \leavevmode
    \hspace*{\fill}
    \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}
      \put(#8){\footnotesize \emph{(a)}}\unitlength1mm #9}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#5,width=#6\picwidth,clip=}
      \put(#8){\footnotesize \emph{(b)}}}
    \hspace*{\fill} \vspace{2ex}
    \begin{trivlist}
    \item[]
      \hspace*{\fill}
      \refstepcounter{figure}
      \parbox[t]{\picwidth}
      {\vspace{-4ex}{\emph{Fig.~\thefigure. #3}}}\label{#1}
      \hspace*{\fill} \hspace*{\fill}
    \end{trivlist}
    \vspace{-#7ex}
  \end{figure}
  }

\newcommand {\tripleFig}[9] {
  \begin{figure}
    \leavevmode \hspace*{\fill}
    \fbox{\epsfig{file=#2,width=0.29\picwidth,clip=}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#5,width=0.29\picwidth,clip=}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#8,width=0.29\picwidth,clip=}}
    \hspace*{\fill} \vspace{3ex}
    \begin{trivlist}
    \item[] \refstepcounter{figure}
      \parbox[t]{0.33\picwidth}
      {\vspace{-5ex}\center{\emph{Fig.~\thefigure. #3}}}\label{#1}
      \refstepcounter{figure}
      \parbox[t]{0.33\picwidth}
      {\vspace{-5ex}\center{\emph{Fig.~\thefigure. #6}}}\label{#4}
      \refstepcounter{figure}
      \parbox[t]{0.33\picwidth}
      {\vspace{-5ex}\center{\emph{Fig.~\thefigure. #9}}}\label{#7}
    \end{trivlist}
    \vspace{-3ex}
  \end{figure}
  }

\newcommand {\tripleFigOneTitle}[9] {
  \begin{figure*}[htb]
    \leavevmode \hspace*{\fill}
    \fbox{\epsfig{file=#2,width=0.29\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(a)}}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#3,width=0.29\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(b)}}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#4,width=0.29\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(c)}}}
    \refstepcounter{figure}
    \hspace*{\fill}
    \begin{center}
      \parbox[t]{\picwidth}
      {\vspace{-#6ex}{\emph{Fig.~\thefigure. #5}}}\label{#1}
    \end{center}
    \hspace*{\fill}
    \vspace{-#7ex}
  \end{figure*}
  }

\newcommand {\tripleFigOneTitleSpec}[7] {
  \begin{figure*}[htb]
    \leavevmode \hspace*{\fill}
    \fbox{\epsfig{file=#2,width=0.35\picwidth,clip=}
      \put(4,2){\footnotesize \emph{(a)}}}
    \hspace*{\fill}\hspace*{\fill}
\epsfig{file=#3,width=0.26\picwidth,clip=}
      \put(-16,5){\footnotesize \emph{(b)}}\hspace*{\fill}\hspace*{\fill}
\epsfig{file=#4,width=0.26\picwidth,clip=}
      \put(-14,5){\footnotesize \emph{(c)}}\refstepcounter{figure}
    \hspace*{\fill}
    \begin{center}
      \parbox[t]{\picwidth}
      {\vspace{-#6ex}{\emph{Fig.~\thefigure. #5}}}\label{#1}
    \end{center}
    \hspace*{\fill}
    \vspace{-#7ex}
  \end{figure*}
  }

\newcommand {\quatrupleFig}[9] {
  \begin{figure*}[htb]
    \leavevmode \hspace*{\fill}
    \fbox{\epsfig{file=#3,width=0.2\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(a)}}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#4,width=0.2\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(b)}}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#5,width=0.2\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(c)}}}
    \hspace*{\fill}\hspace*{\fill}
    \fbox{\epsfig{file=#6,width=0.2\picwidth,clip=}
      \put(#8,#9){\footnotesize \emph{(d)}}}
    \hspace*{\fill} \vspace{3ex}
    \refstepcounter{figure}
    \begin{center}
      \parbox[t]{\picwidth}
      {\vspace{-8ex}\center{\emph{Fig.~\thefigure. #2}}}\label{#1}
    \end{center}
    \hspace*{\fill}
    \vspace{-#7ex}
  \end{figure*}
  }

\newcommand {\wrapFig}[6]{
  \begin{wrapfigure}{#6}{#5\picwidth}
    \begin{center}
      \fbox{\epsfig{file=#2,width=#4\picwidth,clip=}}
    \end{center}
    \refstepcounter{figure}
    \begin{center}
      \parbox[t]{#4\picwidth}
      {\vspace{-6ex}\center{\emph{Fig.~\thefigure: #3}}}\label{#1}
    \end{center}
    \hspace*{\fill}
    \vspace{-10ex}
  \end{wrapfigure}
  }

\newcommand {\pubInfo}[3]{\vspace*{#2cm} \noindent {\small \mbox{#1}} \\ [-2mm]
  \rule{\textwidth}{.2mm}\vspace*{#3cm}}

\renewcommand {\labelenumi}{\alph{enumi}.)}

\renewcommand {\labelenumii}{\arabic{enumii}.)}

\renewcommand {\arraystretch}{1.5}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1035
[htb]
\leavevmode
\hspace*{\fill}
\epsfig{file= pics/museum-tour.eps,height=6cm,clip=}
\put(6,2){\footnotesize \emph{(a)}}\hspace*{\fill}\hspace*{\fill}
\epsfig{file=pics/minerva1.eps,height=6cm,clip=}
\put(6,2){\footnotesize \emph{(b)}}\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-6ex}\center{\emph{Fig.~\thefigure. The mobile
  robots Rhino (a) and Minerva (b) acting as interactive museum
  tour-guides.}}}\label{fig:robots}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-8ex}
\end{figure}
}

\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1062
[htb]
\leavevmode
\begin{center}
\fbox{\epsfig{file=pics/local/markov-example.eps,width=0.5\picwidth,clip=}}
\end{center}
\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-9ex}\center{\emph{Fig.~\thefigure. The basic idea
  of Markov localization: A mobile robot during global
  localization.}}}\label{fig:markov-example}
\end{center}
\hspace*{\fill}
\vspace{-12ex}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{eqnarray}d&=&\{d_0,d_1,\ldots,d_T\}
\end{eqnarray}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{eqnarray}P(L_T=l\mid d) &=& P(L_T=l\mid d_0,\ldots,d_T).
\label{eqML1}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}P(d_{t+1},d_{t+2},\ldots \mid  L_t=l, d_{0},\ldots,d_{t}) &=& 
P(d_{t+1},d_{t+2},\ldots \mid  L_t=l) \;\;\forall t
\label{eqMarkov}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}P(L_T=l\mid d) &=& P(L_T=l\mid d_0,\ldots,d_{T-1},s_T).
\label{eqML1.5}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\frac{P(s_T\mid d_0,\ldots,d_{T-1}, L_T=l)\;
P(L_T=l\mid d_0,\ldots,d_{T-1})}{
P(s_T\mid d_0,\ldots,d_{T-1})},
\label{eqML2}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\frac{P(s_T\mid  L_T=l)\;
P(L_T=l\mid d_0,\ldots,d_{T-1})}{
P(s_T\mid d_0,\ldots,d_{T-1})}.
\label{eqML3}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}P(L_T=l\mid d) &=& \alpha_T \;P(s_T\mid  L_T=l)\;
P(L_T=l\mid d_0,\ldots,d_{T-1}).
\label{eqML4}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}Bel(L_T=l) &=& P(L_T=l\mid d_0,\ldots,d_T),
\label{eqML5}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}Bel(L_T=l) &=& \alpha_T \;P(s_T\mid  l)\; Bel(L_{T-1}=l).
\label{eqML6}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}P(L_T=l\mid d) &=& \int P(L_T=l\mid d, L_{T-1}=l')\;
P(L_{T-1}=l'\mid d)\; dl'.
\label{eqML10}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}P(L_T=l\mid d, L_{T-1}=l')
&=&
P(L_T=l\mid d_0,\ldots,d_{T-1},a_T, L_{T-1}=l')\\ 
&=&
P(L_T=l\mid a_T, L_{T-1}=l')
\label{eqML11}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}P(L_{T-1}=l'\mid d)  &=& P(L_{T-1}=l'\mid d_0,\ldots,d_{T-1},a_T)
\\ 
&=&P(L_{T-1}=l'\mid d_0,\ldots,d_{T-1})
\label{eqML12}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}P(L_T=l\mid d) &=& \int P(L_T=l\mid a_T, L_{T-1}=l')\;
P(L_{T-1}=l'\mid d_0,\ldots,d_{T-1} )\; dl'.
\label{eqML13}
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}Bel(L_T=l) &=& \int P(l\mid a_T, l')\;  Bel(L_{T-1}=l')\; dl'.
\label{eqML14}
\end{eqnarray}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure*}% latex2html id marker 530
[htb]
    \refstepcounter{table}
    \begin{center}
      \fbox{ \parbox{0.9\textwidth}{
          
          \textbf{for each} location $l$ \textbf{do} \hfill /* \textit{initialize} the belief */
          \begin{eqnarray}
            \label{eq:markov-algorithm-initialization}
            \hspace*{-19.5ex}Bel(L_0 = l) & \longleftarrow & P(L_0 = l)
          \end{eqnarray}
\textbf{end for}\\ [4ex]
          \textbf{forever do} \hfill\\ [1ex]
          \hspace*{3ex}\textbf{if} new sensory input $s_T$ is
          received \textbf{do}\\ [2ex]
          \hspace*{6ex}$\alpha_T \longleftarrow 0$\\ [1ex]
          \hspace*{6ex}\textbf{for each} location $l$ \textbf{do}
          \hfill /* apply the \emph{perception model} */
          \begin{eqnarray}
            \label{eq:markov-algorithm-sensing}
            \hspace*{-5ex}\widehat{Bel}(L_T = l) & \longleftarrow &
            P(s_T \mid l) \cdot Bel(L_{T-1} = l)\\ [2ex]
            \alpha_T & \longleftarrow &  \alpha_T + \widehat{Bel}(L_T = l)
          \end{eqnarray}
\hspace*{6ex}\textbf{end for}\\ [1ex]
          \hspace*{6ex}\textbf{for each} location $l$ \textbf{do}
          \hspace*{9ex}\hfill /* \emph{normalize} the belief */
          \begin{eqnarray}
            \label{eq:markov-algorithm-normalization}
            \hspace*{-11.5ex}Bel(L_T = l) & \longleftarrow &
            {\alpha_T}^{-1} \cdot \widehat{Bel}(L_T = l)
          \end{eqnarray} \hspace*{6ex}\textbf{end for}\\ [1ex]
\hspace*{3ex}\textbf{end if}\\ [1ex]
          
          \hspace*{3ex}\textbf{if} an odometry reading $a_T$ is received \textbf{do}\\ [2ex]
          \hspace*{6ex}\textbf{for each} location $l$ \textbf{do}
          \hfill /* apply the \emph{motion model} */
          \begin{eqnarray}
            \label{eq:markov-motion}
            \hspace*{5ex}Bel(L_{T} = l) & \longleftarrow &  \int{
              P( l \mid  l', a_T) \cdot Bel(L_{T-1} = l') \;dl'}
          \end{eqnarray}\hspace*{6ex}\textbf{end for}\\ 
\hspace*{3ex}\textbf{end if}\\ 
\textbf{end forever}
          }}
      \parbox[t]{0.9\textwidth}
      {\vspace{-1ex}\center{Tab.~\thetable. The Markov localization
          algorithm}}      
    \end{center}
    \label{tab:markov-algorithm}
  \end{figure*}
}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1088
[t]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file=pics/banana1.ps,width=0.3\picwidth,clip=}
\put(6,2){\footnotesize \textbf{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=pics/banana2.ps,width=0.3\picwidth,clip=}
\put(6,2){\footnotesize \textbf{(b)}}}
\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-6ex}\center{\small{Fig.~\thefigure. Typical
``banana-shaped'' distributions resulting from different motion
actions.}}}\label{fig:motion}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-7ex}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:local-gauss-distribution} P_m( d \mid l) & = &
  \frac{1}{\sigma \sqrt{ 2 \pi}} e^{- \frac{(d-o_l)^2}{2 \sigma^2}}
  \end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1118
[htb]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file=pics/local/gauss.eps,width=0.4\picwidth,clip=}
\put(-12,0){\footnotesize \emph{(a)}}\unitlength1mm {\scriptsize
        \put(-31,33){$o_l$}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=pics/local/exponential.eps,width=0.4\picwidth,clip=}
\put(-12,0){\footnotesize \emph{(b)}}}
\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-4ex}{\emph{Fig.~\thefigure. 
      Probability of measuring a distance $d_i$ (a) if obstacle in
      distance $o_l$ is detected and (b) due to unknown
      obstacles.}}}\label{fig:local-gauss-exponential}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-4ex}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:local-geometric-distribution}
      P_u( d_i) & = & \left \{
        \begin{array}{ll} 0 &  i = 0\\ [1ex]
        c_r (1 - \sum_{j<i} P_u( d_j)) & \mbox{otherwise}.
        \end{array}\right.
    \end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:a1}
      a_1 = 1 - \sum_{j<i} P_u( d_j),
    \end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:a2}
      a_2 =  c_d \; P_m( d_i \mid l)
    \end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}b_1 =  1 - \sum_{j<i} P( d_j \mid l)
    \end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:b2}
      b_2 = c_r.
    \end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:proximity-1}
  P( d_i \mid l) & = &  \;\;\;\; p \Big( \;\;\;\;\; ( a_1 \wedge a_2 ) \;\;\; \vee \;\;\;\;\; ( b_1 \wedge b_2 ) \;\; \Big) \\ 
  \label{eq:proximity-1-1}
  & = &  \;\; \neg p \Big( \;\; \neg ( a_1 \wedge a_2 ) \;\;\; \wedge \;\;\; \neg ( b_1
  \wedge b_2 ) \;\; \Big) \\ 
  \label{eq:proximity-2}
  & = & 1 - \Big( [ 1 - P(a_1 a_2)] \; \cdot \; [1 - P(b_1 b_2)] \Big) \\ 
  \label{eq:proximity-3}
  & = & 1 - \Big( 1 -  ( 1 - \sum_{j<i} P_u( d_j)) \; c_d \; P_m( d_i \mid l) )) \cdot ( 1 - 
  (1 - \sum_{j<i} P( d_j)) \; c_r \Big)
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:proximity-maxrange}
  P( d_n \mid l) & = &  1 - \sum_{j<n} P( d_j \mid l)
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1152
[htb]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file=pics/local/sonar-1D.eps,width=0.4\picwidth,clip=}
\put(-12,0){\footnotesize \emph{(a)}}\unitlength1mm {\scriptsize
    \put(-31,23){$o_l$}\put(45,25){$o_l$}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=
  pics/local/laser-1D.eps,width=0.4\picwidth,clip=}
\put(-12,0){\footnotesize \emph{(b)}}}
\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-4ex}{\emph{Fig.~\thefigure. 
  Measured and approximated probabilities of (a) sonar and (b) laser
  measurements given the distance $o_l$ to the closest obstacle along
  the sensing direction.}}}\label{fig:local-sonar-merged-1D}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-4ex}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1189
[htb]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file= pics/local/sonar-measured-2D.eps,width=0.4\picwidth,clip=}
\put(-12,2){\footnotesize \emph{(a)}}}
\hspace*{\fill}
\fbox{\epsfig{file=
  pics/local/sonar-approximated-2D.eps,width=0.4\picwidth,clip=}
\put(-12,2){\footnotesize \emph{(b)}}}
\hspace*{\fill}\\  [1.5ex]
\hspace*{\fill}
\fbox{\epsfig{file=
  pics/local/laser-measured-2D.eps,width=0.4\picwidth,clip=}
\put(-12,2){\footnotesize \emph{(c)}}}
\hspace*{\fill}
\fbox{\epsfig{file=
  pics/local/laser-approximated-2D.eps,width=0.4\picwidth,clip=}
\put(-12,2){\footnotesize \emph{(d)}}}
\hspace*{\fill}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-3ex}{\emph{Fig.~\thefigure. Measured and approximated
  probability of sonar (a,b) and laser (c,d) measurements,
  respectively.  Each table contains the probabilities of distance
  measurements given the expected distance $o_l$ extracted from a map
  of the environment.}}}\label{fig:prob-table}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-4ex}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 773
[t]
  \leavevmode
  \hspace*{\fill}
  \fbox{\epsfig{file=pics/selection/find-rhino.eps,width=0.35\picwidth,clip=}
    \put(6,2){\footnotesize \textbf{(a)}}}
  \hspace*{\fill}\hspace*{\fill}
  \fbox{\epsfig{file=pics/selection/Kids-Fest1.eps,width=0.42\picwidth,clip=}
    \put(6,2){\footnotesize \textbf{(b)}}}
  \hspace*{\fill} \vspace{2ex}
  \begin{trivlist}
  \item[] \hspace*{\fill} \refstepcounter{figure}
    \parbox[t]{\picwidth}
    {\vspace{-6ex}\center{\small{Fig.~\thefigure. Rhino surrounded by
          visitors in the \emph{Deutsches Museum
            Bonn}.}}}\label{fig:selection-find-rhino} \hspace*{\fill}
    \hspace*{\fill}
  \end{trivlist}
  \vspace{-2ex}
  \leavevmode
  \hspace*{\fill}
  \epsfig{file=pics/selection/selection-important-gyro.eps,width=0.35\picwidth,clip=}
  \put(6,2){\footnotesize \textbf{(a)}}\hspace*{\fill}\hspace*{\fill}
  \epsfig{file=pics/selection/selection-important-wall.eps,width=0.35\picwidth,clip=}
  \put(6,2){\footnotesize \textbf{(b)}}\hspace*{\fill} \vspace{2ex}
  \begin{trivlist}
  \item[] \hspace*{\fill} \refstepcounter{figure}
    \parbox[t]{\picwidth}
    {\vspace{-7ex}\center{\small{Fig.~\thefigure. Typical laser scans
          obtained when Rhino is surrounded by
          visitors.}}}\label{fig:selection-important} \hspace*{\fill}
    \hspace*{\fill}
  \end{trivlist}
  \vspace{-8ex}
\end{figure}
}

\stepcounter{subsubsection}
{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:entropy}
  H(L) & = & -\sum_{l} Bel(L = l) \; \log Bel(L = l)
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:delta-entropy}
  \Delta H(L \mid s) &:=& H(L \mid s) -  H(L) 
\end{eqnarray}
}

\stepcounter{subsubsection}
{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:selection-unexpected}
  P_{\mbox{\tiny short}}( d_i \mid l) & = &  \sum_{j > i} P_m( d_j
  \mid l).
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1231
[htb]
\leavevmode
\begin{center}
\fbox{\epsfig{file=pics/selection/laser-merge.eps,width=0.478\picwidth,clip=}
\unitlength1mm  {\scriptsize \rm \put(-27,42.3){$P_{\mbox{\tiny
          short}}(d_i \mid l)$}\put(-27,39){$P_m(d_i \mid
      l)$}\put(-35,37){$o_l$}}}\end{center}
\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-7ex}{\emph{Fig.~\thefigure. 
  Probability $P_m( d_i \mid l)$ of expected measurement and
  probability $P_{\mbox{\tiny short}} ( d_i \mid l)$ that a distance
  $d_i$ is shorter than the expected measurement given the location
  $l$.}}}\label{fig:unexpected-filter}
\end{center}
\hspace*{\fill}
\vspace{-7ex}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:selection-unexpected-average}
  P_{\mbox{\tiny short}}( d_i) & = & \sum_{l} P_{\mbox{\tiny short}}( d_i
\mid l) Bel(L = l)
\end{eqnarray}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 876
[hbt]
  \begin{center}
    \leavevmode
    {
\begin{picture}(0,0)\epsfig{file=pstex/grid.pstex}\end{picture}\setlength{\unitlength}{3947sp}\begingroup\makeatletter\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{\reset@font\fontsize{#1}{#2pt}\fontfamily{#3}\fontseries{#4}\fontshape{#5}\selectfont}\fi\endgroup\begin{picture}(3522,3645)(91,-2773)
\put(586,704){\makebox(0,0)[lb]{\smash{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}$Bel(L_t = l)$}}}
\put(1171,-1636){\makebox(0,0)[lb]{\smash{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}$x$}}}
\put(2746,-1276){\makebox(0,0)[lb]{\smash{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}$y$}}}
\put(226,-1456){\makebox(0,0)[lb]{\smash{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}$\theta$}}}
\put( 91,-2716){\makebox(0,0)[lb]{\smash{\SetFigFont{14}{16.8}{\familydefault}{\mddefault}{\updefault}$(0,0,0)$}}}
\end{picture}
}
  \end{center}\vspace*{-2ex}
  \refstepcounter{figure}
  \center{\small{ Fig.~\thefigure. Grid-based
      representation of the state space}}\label{fig:grid}
\end{figure}
}

\stepcounter{subsubsection}
\stepcounter{subsubsection}
{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:p-tilde}
  \widetilde{P}(s_t) = \sum_l P(s_t \mid l) \; P(l)
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:selective_update_1}
  Bel(L_t = l) & \longleftarrow & \left\{ \begin{array}{ll}
      \alpha_t \cdot P(s_t \mid l) \cdot Bel(L_{t-1} = l) &
      \mbox{if\ } Bel(L_{t-1} = l) > \varepsilon \\ [1ex]
      \alpha_t \cdot \;\; \tilde{P}(s_t) \;\; \cdot Bel(L_{t-1} = l) & \mbox{otherwise} 
    \end{array}\right.
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{eq:selective_update_2}
  Bel(L_t = l) & \longleftarrow & \left\{ \begin{array}{ll}
      \tilde{\alpha}_t \cdot \frac{P(s_t \mid l) }{\widetilde{P}(s_t)} \cdot
      Bel(L_{t-1} = l) &
\mbox{if\ } Bel(L_{t-1} = l) > \varepsilon \\ [1ex]
\tilde{\alpha}_t \quad  \;\; \cdot \quad \;\;\;  Bel(L_{t-1} = l) & \mbox{otherwise} 
    \end{array}\right.
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1680
[htb]
\leavevmode
\begin{center}
\fbox{\epsfig{file=
  pics/local/laser-sonar-div.eps,width=0.45\picwidth,clip=}
\unitlength1mm {\scriptsize
    \put(-40,45){$o_l$}}}\end{center}
\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-9ex}\center{\emph{Fig.~\thefigure. Ratio $\frac{P(d_i \mid
    l)}{\tilde{P}(d_i)}$ for sonar and laser measurements for expected
  distance $o_l$ of 230cm.}}}\label{fig:local-sonar-laser-divided}
\end{center}
\hspace*{\fill}
\vspace{-11ex}
\end{figure}
}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1704
[htb]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file=
pics/selection/sunday-path-merge.eps,width=0.35\picwidth,clip=}
\put(6,0){\footnotesize \emph{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=pics/smithpath.eps,width=0.415\picwidth,clip=}
\put(6,0){\footnotesize \emph{(b)}}}
\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-4ex}{\emph{Fig.~\thefigure. Typical trajectories of (a)
Rhino in the \emph{Deutsches Museum Bonn} and (b) Minerva in the
\emph{National Museum of American
History}.}}}\label{fig:museum-path}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-5ex}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1736
[htb]
\leavevmode
\begin{center}
\fbox{\epsfig{file=pics/selection/noise-ratio.eps,width=0.4\picwidth,clip=}}
\end{center}
\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-9ex}\center{\emph{Fig.~\thefigure. Percentage of noisy
  sensor measurements averaged over time intervals of five
  minutes.}}}\label{fig:noise-ratio}
\end{center}
\hspace*{\fill}
\vspace{-11ex}
\end{figure}
}

\stepcounter{subsubsection}
{\newpage
\clearpage
\samepage \begin{figure*}% latex2html id marker 1763
[htb]
\leavevmode \hspace*{\fill}
\fbox{\epsfig{file=pics/selection/rand-endpoints.eps,width=0.29\picwidth,clip=}
\put(-12,4){\footnotesize \emph{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=
  pics/selection/ent-endpoints.eps,width=0.29\picwidth,clip=}
\put(-12,4){\footnotesize \emph{(b)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=pics/selection/unex-endpoints.eps,width=0.29\picwidth,clip=}
\put(-12,4){\footnotesize \emph{(c)}}}
\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-3ex}{\emph{Fig.~\thefigure. Estimated
  and real paths of the robot along with endpoints of incorporated
  sensor measurements using (a) no filter, (b) entropy filter, and (c)
  distance filter.}}}\label{fig:rand-endpoints}
\end{center}
\hspace*{\fill}
\vspace{-5ex}
\end{figure*}
}

\stepcounter{subsubsection}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure*}% latex2html id marker 1813
[htb]
\leavevmode \hspace*{\fill}
\fbox{\epsfig{file=pics/selection/floor-outline.eps,width=0.35\picwidth,clip=}
\put(4,2){\footnotesize \emph{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\epsfig{file=
  pics/selection/floor-filter-2.eps,width=0.26\picwidth,clip=}
\put(-16,5){\footnotesize \emph{(b)}}\hspace*{\fill}\hspace*{\fill}
\epsfig{file=
  pics/selection/floor-filter-3.eps,width=0.26\picwidth,clip=}
\put(-14,5){\footnotesize \emph{(c)}}\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-2ex}{\emph{Fig.~\thefigure. (a) Outline of the office environment
  and (b,c) examples of filtered (grey) and incorporated (black)
  sensor readings using the distance filter.}}}\label{fig:floor-filtered}
\end{center}
\hspace*{\fill}
\vspace{-4ex}
\end{figure*}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1843
[htb]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file=log/aaaigreyscale.eps,width=0.45\picwidth,clip=}
\put(-12,2){\footnotesize \emph{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=log/path.eps,width=0.48\picwidth,clip=}
\put(-12,2){\footnotesize \emph{(b)}}}
\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-4ex}{\emph{Fig.~\thefigure. (a) Occupancy
  grid map of the 1994 AAAI mobile robot competition arena. (b)
  Trajectory of the robot and ultrasound measurements used to globally
  localize the robot in this
  map.}}}\label{fig:aaai-map}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-6ex}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure*}% latex2html id marker 1873
[htb]
\leavevmode \hspace*{\fill}
\fbox{\epsfig{file=log/newplots/scan5light.eps,width=0.29\picwidth,clip=}
\put(-14,0){\footnotesize \emph{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=
  log/newplots/scan18light.eps,width=0.29\picwidth,clip=}
\put(-14,0){\footnotesize \emph{(b)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=log/newplots/scan24linlight.eps,width=0.29\picwidth,clip=}
\put(-14,0){\footnotesize \emph{(c)}}}
\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-2ex}{\emph{Fig.~\thefigure. Density
  plots after incorporating 5, 18, and 24 sonar scans (darker
  positions are more likely).}}}\label{fig:belief-states}
\end{center}
\hspace*{\fill}
\vspace{-2ex}
\end{figure*}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1906
[t]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file=log/newplots/odolightrle.eps,width=0.35\picwidth,clip=}
\put(8,2){\footnotesize \textbf{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=log/newplots/pathlightrle.eps
  ,width=0.35\picwidth,clip=}
\put(8,2){\footnotesize \textbf{(b)}}}
\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-6ex}\center{\small{Fig.~\thefigure. Odometry
  information and corrected path of the
  robot.}}}\label{fig:path}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-8ex}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1934
[htb]
\leavevmode
\begin{center}
\fbox{\epsfig{file=pics/reference.eps,width=0.6\picwidth,clip=}}
\end{center}
\refstepcounter{figure}
\hspace*{\fill}
\begin{center}
\parbox[t]{\picwidth}
{\vspace{-9ex}\center{\emph{Fig.~\thefigure. Path of the robot and
    reference positions}}}\label{fig:reference}
\end{center}
\hspace*{\fill}
\vspace{-10ex}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}% latex2html id marker 1952
[htb]
\leavevmode
\hspace*{\fill}
\fbox{\epsfig{file=pics/plot.ps,width=0.4\picwidth,clip=}
\put(6,2){\footnotesize \emph{(a)}}}
\hspace*{\fill}\hspace*{\fill}
\fbox{\epsfig{file=time/plot.ps,width=0.4\picwidth,clip=}
\put(6,2){\footnotesize \emph{(b)}}}
\hspace*{\fill} \vspace{2ex}
\begin{trivlist}
\item[]
\hspace*{\fill}
\refstepcounter{figure}
\parbox[t]{\picwidth}
{\vspace{-4ex}{\emph{Fig.~\thefigure. (a) Average
  localization error and (b) average CPU-time needed for global
  localization time both for ultrasound sensors and laser range-finder
  depending on the grid resolution.}}}\label{fig:runtime-accuracy}
\hspace*{\fill} \hspace*{\fill}
\end{trivlist}
\vspace{-6ex}
\end{figure}
}

\stepcounter{section}
\stepcounter{section}
\stepcounter{section}

\end{document}
