proposal-summary.tex

\chapter[Summary of Proposed Work]{Summary of\\Proposed Work}
\label{chap:proposed}

\section{Research Questions}
\label{sec:research-questions}

I propose to address the following eight research questions
in this thesis.
This section discusses each question in turn.
See Table~\ref{table:proposed-timeline} for a timeline.

\begin{center}
{\setlength{\tabcolsep}{3pt}
\begin{tabular}{llc}
\toprule
   \multicolumn{2}{l}{Research Question}
      & Sec. \\
\midrule
   \ref{ques:choosing-lambda}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \vspace{0.05in}
      \begin{spacing}{0.7}
      \nameref{ques:choosing-lambda}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:e8} \\[20pt]
   \ref{ques:incremental-search}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \begin{spacing}{0.7}
      \nameref{ques:incremental-search}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:e8} \\[12pt]
   \ref{ques:e8-comparisons}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \begin{spacing}{0.7}
      \nameref{ques:e8-comparisons}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:e8} \\[12pt]
   \ref{ques:batching}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \begin{spacing}{0.7}
      \nameref{ques:batching}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:graphs-in-continuous} \\[12pt]
   \ref{ques:evalpath}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \begin{spacing}{0.7}
      \nameref{ques:evalpath}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:graphs-in-continuous} \\[12pt]
   \ref{ques:multi-set-suited}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \begin{spacing}{0.7}
      \nameref{ques:multi-set-suited}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:multi-set-prm} \\[12pt]
   \ref{ques:how-sequence}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \begin{spacing}{0.7}
      \nameref{ques:how-sequence}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:task-planning} \\[12pt]
   \ref{ques:proteus-compare}
      &
      \begin{minipage}[c]{0.83\columnwidth}%
      \begin{spacing}{0.7}
      \nameref{ques:proteus-compare}
      \end{spacing}%
      \vspace{0in}
      \end{minipage}%
      & \ref{chap:task-planning} \\[12pt]
\bottomrule
\end{tabular}
}%tabcolsep
\end{center}

{
%\renewcommand\thesubsection{\thesection.Q\arabic{subsection}}
\renewcommand\thesubsection{Q\arabic{subsection}}

\subsection{How should the $\lambda$ parameter mediating
   between planning and execution cost in the E$^8$
   search algorithm be chosen?}
\label{ques:choosing-lambda}

See Section~\ref{chap:e8}.

The E$^8$ algorithm's objective,
from (\ref{eqn:general-objective-explicit}),
trades off between planning and execution effort,
mediated by the parameter $\lambda \in [0,1]$.
Loosely,
adjusting $\lambda$ varies the behavior between
\emph{feasibility} (finding paths quickly)
and \emph{optimality} (of execution).

With $\lambda=0$,
E$^8$ focuses solely on minimizing execution effort.
This is similar to the LazyPRM algorithm.
On the other hand,
with $\lambda=0$,
it focuses solely on minimizing planning effort,
similarly to the RRT algorithm.
We discuss these comparisons to existing continuous-space planners
in Section~\ref{chap:graphs-in-continuous}.

If our ensemble effort model $\mathcal{M}$
specifies effort estimates in the same units
(e.g. time or energy),
$\lambda=\frac{1}{2}$ is a natural choice.
However,
due to the optimistic nature of the E$^8$ algorithm,
a different value of $\lambda$ may perform better in practice.

Minimizing total time in a greedy fashion implies $\lambda = 0.5$.
For later steps in a multi-step plan,
we might have an estimate of the probability $P_e$ that the given query will
actually be executed.
We can then pose our optimistic objective as total planning and execution
time in expection;
this induces the following parameter choice:
\begin{equation}
   \lambda = \frac{1}{1 + P_e} .
\end{equation}
For example, $P_e=1$ induces $\lambda = 0.5$;
as $P_e \rightarrow 0$, $\lambda \rightarrow 1$.
In other words,
as the estimated probability of executing the path goes down,
the planner becomes greedier w.r.t. planning effort at the expense of
costlier solution paths.

This is all one-step greedy;
it returns the optimal path optimistically,
assuming it will be collision-free.
If we have some estimate of the proportion $P_u$ of evaluated edges
which will be part of the final path,
we can then choose a cost function which downweights the planning time.

\subsection{How can incremental graph search ideas (e.g. LPA*)
   be used to efficiently implement the E$^8$ algorithm?}
\label{ques:incremental-search}

The E$^8$ algorithm (Algorithm~\ref{alg:e8}) from Section~\ref{chap:e8}
is currently executing a fully bidirectional Dijkstra's search
during each iteration.
The algorithm is clearly making multiple graph search queries
over a fixed graph with only a few edge costs changing between queries.
While, for small graphs, graph search time is small,
for larger graphs,
it will become significant.
How can we efficiently implement LPA* \cite{koenig2004lpastar}
to improve planning efficiency on large graphs?

\subsection{How does the explicit graph approach of E$^8$ compare to
   weighted and anytime implicit algorithms?}
\label{ques:e8-comparisons}

This question addresses the empirical performance of
the E$^8$ algorithm when compared to baseline algorithms
on implicit and explicit graphs with expensive edge evaluations.
We will use metrics of measured planning and execution effort
expended both on 2D graphs and on fixed lattice and RGG
graphs in \textsc{Herb}'s configuration space.

\subsection{How should discrete graphs be constructed in continuous
   $\mathcal{C}$-spaces with spatially correlated execution costs?}
\label{ques:batching}

Chapter~\ref{chap:graphs-in-continuous}
discusses how to embed roadmaps in $\mathcal{C}$
so that they can be searched by E$^8$.

The problem with na\"{\i}vly running E$^8$ on a
dense roadmap in $\mathcal{C}$
is that it tends to bunch up in local minima.
This is because reducing the continuous planning problem
to a graph search ignores the spatial correlation
inherent in $\mathcal{C}_{\mbox{\scriptsize free}}$.

One way to capture this is to maintain a probabalistic model
of $\mathcal{C}_{\mbox{\scriptsize free}}$,
and then optimize in expectation.
In particular,
instead of greedily choosing the best path based on
optimistic estimates of one-time planning and execution cost:
\begin{equation}
   f(\pi) = \lambda \hat{f}_p(\pi) + (1-\lambda) \hat{f}_x(\pi),
\end{equation}
we instead reason over the total \emph{expected} remaining cost:
\begin{align}
   f(\pi)
      &= E \left[ \lambda f_p(\pi) + (1-\lambda) f_x(\pi) \right] \\
   &= P_{\mbox{\scriptsize free}}(\pi)
      \left[ \lambda \hat{f}_p(\pi) + (1-\lambda) \hat{f}_x(\pi) \right]
      + (1-P_{\mbox{\scriptsize free}}(\pi))
      \left[ \lambda F_p + (1-\lambda) F_x \right]
\end{align}

Consider the the problem from Figure~\ref{fig:example-in-expectation}.
There are an infinite number of paths to the goal,
each consisting of walking along the sidewalk,
followed by crossing the street perpendicuarly at a particular
position $x$.
The sidewalk is known to be collision-free,
whereas each position on the street must be tested for collision
with obstacles with planning validation cost $\hat{f}_p(\pi)$
independent of $x$.
Execution cost $f_x(\pi)$ is given by $|x|+c$.

Suppose we first test walking straight across the street $\pi_0$
(knowing nothing, this is clearly the optimistically cheapest path)
and this is deemed in collision.
Which path should we consider next (e.g $\pi_a$ or $\pi_b$)?

What is our model for $P_{\mbox{\scriptsize free}}(\pi)$?
Relate to GPs for classification\cite{rasmussen2006gpml}.

We are operating under assumptions:
\begin{itemize}
\item Single-shot greedy (won't choose \emph{sets} of paths
   which minimize remaining effort)
\item Operates over \emph{paths} instead of configurations
   or edges (won't probe points, no explicit exploration)
\end{itemize}

\begin{figure}
   \begin{center}
   \includegraphics{build/example-in-expectation}
   \end{center}
   \caption{Simple example problem to illustrate optimizing
      remaining ensemble cost in expectation.}
   \label{fig:example-in-expectation}
\end{figure}

\subsection{What path evaluation strategy performs best
   across manipulation tasks?}
\label{ques:evalpath}

Because the E$^8$ and E$^8$-PRM algorithms
operate over explicit graphs and roadmaps,
they have the freedom to evaluate edges in any order.
In contrast, search algorithms over implicit graphs
must evaluate vertices via e.g. the graph's \textsc{Successors($v$)}
function.
This freedom may allow intelligent alternating or bisection approaches
to reduce average-case planning cost.

Since E$^8$ operates on graphs,
it is constrained to evaluating entire edges,
one at a time.
On the other hand,
the E$^8$-PRM roadmap algorithm
has the luxury of evaluating individual configurations at any
point on the path;
the Lazy PRM algorithm, for example,
reported promising results by performing a bisection collision
check on the entire path.

This question serves to identify
the best-performing path evaluation strategies during
testing on \textsc{Herb} and \textsc{Chimp} manipuation tasks.

\subsection{How does the extent of disclosed multi-set structure
   affect planner performance on multi-step problems?}
\label{ques:multi-set-suited}

The preliminary \textsc{Herb} experimental results reported in
Table~\ref{tab:testherb} evaluate the Multi-Set PRM's performance
with different combinations of multi-set structure is provided
to the planner.
The purpose of this question is to extend this analysis to a broader
set of manipulation tasks
which exploit other types of multi-set structure,
such as those listed in Section~\ref{chap:multi-set}
in order to identify particular types of structure which yield
the most promising performance.

\subsection{How does the amount of inter-step coupling
   affect the merit of interleaving planning and execution?}
\label{ques:how-sequence}

As discussed in the introduction,
a large amount of coupling between tasks
-- what we loosely define as the extent to which early choices
affect the performance of later portions of the task --
motivates longer planning horizons.
The importance of considering this coupling is motivated by the
performance of the planning system used on the \textsc{Chimp} robot
at the DRC Trials competition \cite{dellin2014drc},
which often failed to find solutions to multi-step tasks because
it committed too early.

We hypothesize that highly coupled tasks will favor approaches
such as \textsc{Proteus} (Chapter~\ref{chap:task-planning})
that wait to find a full task plan
before beginning execution,
while less coupled tasks will favor interleaved approaches
such as Hierarchical Task and Motion Planning in the Now
\cite{kaelbling2011inthenow}.
The purpose of this question is to validate this hypothesis
through experimental evaluation on \textsc{Herb} and \textsc{Chimp}.

\subsection{How does the \textsc{Proteus} task planner
   compare experimentally to baseline approaches
   on \textsc{HERB} and \textsc{CHIMP}?}
\label{ques:proteus-compare}

This question serves to evaluate the full task performance of the
proposed approach
in comparison to state-of-the-art baseline approaches.
In order to evaluate the efficacy of the approach,
this chapter details a set of experiments on multiple robot systems
both in simulation and on real hardware.

Here, we describe the test platforms, software,
metrics, control variables,
and baseline approaches that are used in the experimental
evaluation.

\textbf{HERB: The Home Exploring Robot Butler.}
The HERB robot \citep{srinivasa2012herb20}
is human-scale mobile manipulator designed to assist in home
environments.
It has two seven-degree-of-freedom Barrett WAM arms mounted
on a Segway RMP base.
It includes a BLAH KWh battery and has three onboard rack-mount
computers.

\textbf{CHIMP: the CMU Highly Intelligent Mobile Platform.}
CHIMP \citep{stentz2014chimp}
is a disaster response robot built by NREC at CMU
for the Darpa Robotics Challenge.
It is a tracked mobile manipulation robot consisting of
four limbs comprising 26 limb degrees of freedom.
It has Robotiq adaptive 3-finger grippers.
%\cdnote{I want to run my planner on the DRC Trials data
%and show significant improvement.}

\textbf{OpenRAVE Simulation Environment.}
We use the OpenRAVE \citep{diankov2010openrave} simulation environment
for planning and collision checking.
It implements kinematics, robot models,
and interfaces to several collision checkers.
When reporting planning effort,
we present both total time and energy used,
as well as number of collision checks performed
for comparison to other checkers.
See the section on metrics below.

\textbf{Open Motion Planning Library.}
We use the Open Motion Planning Library (OMPL)
planning framework \citep{sucan2012ompl}
to implement our planners
and for baseline approaches which we compare against.

\textbf{Metrics.}
Our primary metric is \emph{total task effort} exerted to accomplish
the task.
For each run of our algorithms,
we record this effort as measured in
(a) time, in seconds,
and (b) energy, in Joules.
In order to present these data as fairly as possible,
we record the split between planning and execution effort
for each plan.
We also report the difference between expected and actual
execution effort for the solution path
that may result from an approximate execution effort model
(see Chapter~\ref{chap:graphs-in-continuous}).

To enable comparisons to other robots and collision checkers,
we also report number of collision checks as a proxy for collision
checking effort.
We also report the number of triangles in each collision model.

While our approach terminates automatically
given an the input $\lambda$ parameter between planning and execution
effort,
we also compare against anytime approaches that return multiple
improving solutions over time.
We present plots of all of these results for comparison,
and also report the data points that result from several
a-priori time budgets.

\textbf{Baseline Approaches.}
We propose to test our task planner against a suite of
state-of-the-art approaches,
including:
\begin{itemize}
\item Hierarchical task and motion planning in the now
   \citep{kaelbling2011inthenow}.
   Note that we compare against HPN both
   interleaved and non-interleaved.
\item The seqeutial task planner used by by the CMU team
   at the Darpa Robotics Challenge
   \citep{dellin2014drc},
   based on the Constrained Bi-Directional RRT
   \cite{berenson2009manifolds}.
\item Other hybrid symbolic/geometric planners.
   %\cdnote{Talk to Evan.}
\end{itemize}
For a fair comparison,
we also select parameters for other approaches using a set of testing
problems.

}%for custom Q1 subsection numbering

\section{Timeline}

See Table~\ref{table:proposed-timeline} for the timeline.
%It's currently very aggressive.

I'm not sure if integration of my OMPL planner
is in the best interests of the DRC project.
Will know more about this after the March 2015 DRC testbed meeting.
In any case, I'd like to test against Trials data
(and perhaps Finals data if it's available).

\begin{table*}
   \begin{widepage}
   \centering
   {
   \renewcommand{\arraystretch}{1.5}
   \begin{tabular}{lccl}
   \toprule
   {\bf Topic} & {\bf Section} & {\bf Questions} & {\bf Deadline} \\
   \midrule
   Guided Manipulation Planning at the DRC Trials \citep{dellin2014drc}
      & %\ref{chap:formulation}
      &
      & February 2014 (ISER) (completed) \\
   Comprehensive Multi-Root Planning \citep{dellin2015cmr}
      & \ref{chap:cmr}
      &
      & October 2014 (ICRA) (completed) \\
   Reduce, Reuse, Recycle: Multi-Set Planning \citep{dellin2015multiset}
      & \ref{chap:multi-set}, \ref{chap:multi-set-prm}
      & \ref{ques:choosing-lambda}, \ref{ques:incremental-search}
      & January 2015 (RSS) (in submission) \\
   \midrule
   Proposal
      & & & March 2015 \\
%   ??
%      & 
%      & 
%      & March 2015 (ISRR) \\
   %DRC Integration (presuming project alignment)
   %   & & & April-May 2015 \\
   Multi-Set Planning for the DRC
      & \ref{chap:multi-set-prm}, \ref{chap:task-planning}
      & \ref{ques:evalpath}, \ref{ques:how-sequence},
        \ref{ques:proteus-compare}
      & June 2015 (Humanoids) \\
   HERB Experiments
      & \ref{chap:multi-set-prm}, \ref{chap:task-planning}
      & \ref{ques:evalpath}, \ref{ques:multi-set-suited},
        \ref{ques:proteus-compare}
      & July-August 2015 \\
   The E$^8$-PRM: Optimizing Total Task Cost
      & \ref{chap:e8}, \ref{chap:graphs-in-continuous}
      & \ref{ques:choosing-lambda}, \ref{ques:e8-comparisons},
        \ref{ques:batching}
      & September 2015 (AAAI) \\
   Thesis Writing
      & & & September-November 2015 \\
   Bored Robots: Hypothesized Conservative Volumes
      & & & October 2015 (ICRA) \\
   Defense
      & & & December 2015 \\
   \bottomrule
   \end{tabular}
   } %arraystretch
   \end{widepage}
   \caption[][0.2in]{Proposed Timeline.
      %\cdnote{This is quite agressive.}
   }
   \label{table:proposed-timeline}
\end{table*}

\section{Open-Source Software}

I propose to release the following open-source software packages
as part of my thesis deliverables:
\begin{itemize}
\item The E$^8$-PRM (OMPL).
\item The multi-set decomposer (OpenRAVE+OMPL).
\item The \textsc{Proteus} task planner.
\end{itemize}