\section{Introduction}

\section{Introduction}
\label{sec:intro}
\input{sections/intro.tex}

\section{Problem Formulation}
\label{sec:problem}
\input{sections/problem.tex}

\section{Active Learning of Abstract Plan Feasibility}
\label{sec:active-learning}
\input{sections/method.tex}

\section{Implementation}
\label{sec:implementation}
\input{sections/implementation.tex}

\section{Evaluation}
\input{sections/evaluation.tex}

\section{Related Work}
\label{sec:related_work}
\input{sections/related_work}

\section{Conclusion}
\label{sec:conclusion}
\input{sections/conclusion}

\section*{Acknowledgments}
\label{sec:acknowledgements}
\input{sections/acknowledgements}

\bibliographystyle{plainnat}
\input{paper_template.bbl}

\clearpage

\subsection{Impact of Sampling Strategy}
\label{sec:eval-sequential}

Figure \ref{fig:eval-strategies} shows the task performance of models trained using the four sampling strategies described in Section \ref{sec:sampling-strategies}.
Each strategy has results aggregated from $4$ independent training runs and $50$ task evaluations per run all performed in a simulated environment. Different sets of blocks are used between training and evaluation.

Our {\sc apf}{} model performs best on the \emph{Tallest Tower} task, successfully minimizing regret after constructing only $200$ towers with the sequential{} method.
The incremental{} method also performs well, successfully minimizing regret with minimal variance across runs. The {\it complete}{} method on average performs well, but has very high variance for the more challenging tasks, \emph{Longest Overhang} and \emph{Maximum Unsupported Area}. Note that the shaded region represents the quartile distribution --- a region that extends to $1.0$ means that more than a quarter of the trials were unstable. This highlights the importance of considering the \emph{infeasible sub-sequence property} when sampling and scoring plans in the action space.
Finally, the naive {\it greedy}{} strategy performs the worst, and is only able to achieve decent performance on the \emph{Tallest Tower} task after seeing roughly $800$ training towers, likely due to the fact that it is not considering the feasibility of subtowers when searching the actions space, just greedy single-block placements.

The \emph{Maximum Unsupported Area} and \emph{Longest Overhang} tasks are more challenging for the robot because they require deep understanding of the tower stability decision boundary, while the \emph{Tallest Tower} task only requires a rough understanding of how to build stable towers with high confidence. These results show that in spite of the difficulty of the first two tasks, the active learner is able to improve its understanding of the decision boundary well enough to perform tasks with very low regret and low variance.

In Appendix \ref{sec:appendix-sim-random} we give additional results which compare against baselines that do not leverage active learning.

\begin{figure*}
    \centering
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_overhang.pdf}
        \label{fig:eval-strategies-overhang}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_contact.pdf}
        \label{fig:eval-strategies-contact}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_tallest.pdf}
    \label{fig:eval-strategies-tallest}
    \end{subfigure}
        \vspace{-10pt}
        \caption{A comparison of sampling strategies on different downstream tasks all performed in simulation. Each method evaluation consists of $4$ separate {\sc apf}{} model-learning runs, and each point is the Median Normalized Regret of $50$ individual planning runs per learned model. The shaded regions show $25\%$ and $75\%$ quantiles.}
        \label{fig:eval-strategies}
        \vspace{-12pt}
\end{figure*}

\subsection{Model Architecture and Generalization}
\label{sec:eval-graph}

We compare our {\sc tgn}{} to the other network architectures discussed in Section \ref{sec:imp-learning} and shown in Figure \ref{fig:architecture_graphic}.
For this evaluation, we report accuracy on a held-out test set of towers built with a novel set of blocks.
The test set consists of half feasible and half infeasible towers, and $1000$ towers for each tower size.
Our models were trained in simulation on towers consisting of up to $5$ blocks, but our results give model accuracy for towers ranging from $2$ to $7$ blocks, shown in Figure \ref{fig:eval-models}.

In the towers domain, it is necessary to consider the joint centers of mass for groups of blocks above support blocks.
While the {\sc lstm} architecture could remember the previous blocks as it iterates through the tower, in practice we find that it is outperformed by the graph network architectures.
We believe this is because the connectivity of the graph networks allows them to precisely compare adjacent blocks in addition to aggregating information about multiple blocks.
The weakness of the {\sc lstm} is more pronounced as the number of blocks in a tower increases.

Our {\sc tgn}{} architecture is structured to be biased towards our particular domain, so it is able to improve its predictions much faster than the other architectures.
This enables good planning time performance as seen in Section \ref{sec:eval-sequential} with similar long-term performance to the {\sc fcgn} architecture.

\begin{figure}

    \centering{\includegraphics[width=\columnwidth]{figures/architecture_comparison_2.pdf}}
    \caption{A comparison of different network architectures using the sequential{} sampling strategy, performed in simulation. The accuracy for each method is averaged over 3 separate training runs. The shading shows the minimum and maximum accuracy from these runs.}
    \label{fig:eval-models}
    \vspace{-12pt}
\end{figure}

\subsection{Real Robot Experiments}
\label{sec:eval-robot}

Finally, we give results for executing the entire active learning pipeline on a real Panda robot (see Section \ref{sec:implementation} for details of the real robot setup).
In total, the robot built $400$ towers while training over a period of $55$ hours.

For the experimentation phase, we used a fixed set of $10$ training blocks. The {\sc tgn}{} ensemble is initialized with $40$ random $2$-block towers labeled in simulation with added relative-pose noise. We generated candidate experiments using the incremental{} strategy described in Section \ref{sec:sampling-strategies}, and produced stability labels for the constructed towers by observing the outcome with the cameras.

During the evaluation phase, we test the robot's ability to use its learned {\sc apf}{} model to perform all tasks described in Section~\ref{sec:domain} with a separate set of $10$ held-out evaluation blocks.
We compare the learned {\sc apf}{} model to two baselines.
First, we compare to a hand-engineered model of plan feasibility that calculates whether a candidate tower is feasible in a noiseless world.
We also compare to a noisy simulator feasibility model, which predicts a tower is feasible only if the candidate tower is also stable to $10$ normally distributed perturbations, with a standard deviation of $5$mm, for each block placement.

\begin{table}[b]
\centering
\scriptsize
\begin{tabular}{|c||c|c||c|c||c|c|}
\hline
 & \multicolumn{2}{c||}{\textbf{Tallest}}
 & \multicolumn{2}{c||}{\textbf{Longest}}
 & \multicolumn{2}{c|} {\textbf{Max Unsupported}} \\
 & \multicolumn{2}{c||}{\textbf{Tower}}
 & \multicolumn{2}{c||}{\textbf{Overhang}}
 & \multicolumn{2}{c|} {\textbf{Area}} \\
\hline
\textbf{Model} & \textbf{Regret} & \textbf{\#Stable}& \textbf{Regret} & \textbf{\#Stable}& \textbf{Regret} & \textbf{\#Stable}\\ \hline
Analytical & 0.30 & 7/10 & 0.80 & 2/10 & 0.80 & 2/10\\
\hline
Simulation & 0.41 & 6/10 & 0.47 & 8/10 & 0.19 & 10/10\\
\hline
Learned & 0.15 & 9/10 & 0.45 & 9/10 & 0.33 & 9/10\\
\hline
\end{tabular}
\caption{\label{tab:real-results}
Real robot task performance when using different {\sc apf}{} models. The \emph{Learned} model was trained with data collected through active learning on the real Panda robot.
The \emph{Analytical} and \emph{Simulation} models calculate feasibility using the known underlying dynamics but use either no noise or simple noise models respectively.}
\vspace{-3pt}
\end{table}

For each task and model we select $5$ blocks at random from the evaluation set and plan to maximize the given objective.
If a constructed tower is unstable, it gets zero reward.
The robot constructs $10$ towers for each task and feasibility model.
In Table~\ref{tab:real-results}, we report average normalized regret, and the number of total trials that resulted in a stable tower.
Figure~\ref{fig:panda_eval_qualitative} includes images of the robot performing the \emph{Longest Overhang} task using the different models for {\sc apf}{}.

From these results, it can be seen that the \emph{Analytical} model can build towers with high reward when the tower is stable, but the towers it chooses to build are rarely stable across all three tasks.
However, the \emph{Simulation} and \emph{Learned} {\sc apf}{} models can still build towers with large overhang while considering the effects of noisy action execution on a real robot.
Our \emph{Learned} model performs competitively with the \emph{Simulation} model, and in aggregate leads to similar stability across all tasks (27 versus 24 stable towers out of 30).
However, note that the \emph{Simulation} model presents higher variability in tower stability across tasks.
This is because the model makes assumptions about the type of noise distribution (Gaussian only in the plane normal to the table) and its parameters (mean and variance), which may be more suitable for certain tasks.
The \emph{Learned} model, on the other hand, may capture other complex real-world phenomena that significantly contribute to plan feasibility in a task-agnostic setting.

\begin{figure}[t!]
    \centering{\includegraphics[width=0.48\textwidth,trim=0 0 900px 0, clip]{figures/comparison_overhang_blurred.png}}
    \caption{Towers built for the \emph{Longest Overhang} task when using different {\sc apf}{} models. Observe that some towers built using the \emph{Analytical} and \emph{Simulation} models were unstable. See the appendix for more examples.}
    \label{fig:panda_eval_qualitative}
    \vspace{-10pt}
\end{figure}

\subsection{Stacking Task}
\textbf{Stacking Domain}
Tasks that involve stacking objects in a \emph{Blocks World} have a long history in artificial intelligence.
Early works developed methods to compute the stability of block placements and construct a target configuration \cite{blum1970stability, winston1972}.
More recently, computer vision researchers have developed scene understanding algorithms that take into account known geometries and stability properties of objects within the scene \cite{GuptaEfrosHebert_ECCV10, jia_3d_2015, roberts1963machine}.
\citet{furrer2017autonomous} developed a system that can build stacks out of stones using detailed models of the objects.

Recent work has shown the ability to predict tower stability using deep learning techniques \cite{ferrari_shapestacks_2018, hamrick_relational_2018, lerer2016learning}.
However, typically these works have used passively collected datasets which include orders of magnitude more samples than required in this work --- making them infeasible to actively collect on a real robot.
An active learning approach allows the robot to explore efficiently, and learn a feasibility model under the real-world noise distribution.
In addition, vision-based systems would not be effective when the state contains non-visual properties, such as the center of mass in our stacking domain \cite{ferrari_shapestacks_2018, lerer2016learning}.

\subsection{Domain}
\label{sec:domain}

The world consists of the robot and a set of objects, $\mathcal{O}$, with which it can interact.
In this work, we consider cuboids with non-uniform mass distributions (Figure \ref{fig:panda_and_objects}).  Each object, $o \in \mathcal{O}$, is described by a tuple, $(d, c, m)$, where $d \in \mathbb{R}^3$ are the dimensions, $c \in \mathbb{R}^3$ is the offset of the center of mass from the center of geometry, and $m \in \mathbb{R}$ is the object's mass.

During the experimentation phase we use a set of 10 blocks, and all evaluations are performed with a different set of 10 blocks.
The block parameters from each set are sampled from the same uniform distribution over the dimensions of the objects and the locations of the center of mass within the objects.

The abstract actions are to place objects onto a stack;  they are specified by $a=(o, r)$ where $r \in SE(3)$ is the relative pose of $o$ with respect to the object placed in the previous action (or the table if this is the first object placement).

An abstract plan is feasible if the detailed planning and execution system can find and execute robot commands (i.e., grasp poses and motion plans) such that the objects are placed on top of one another and the resulting tower is stable.  Note that, for this property to hold, each prefix of the plan must also be feasible --- that is, each subtower is stable.

The learned {\sc apf}{} model is applied to three different objectives in the \emph{evaluation phase}:
\begin{enumerate}
    \item \emph{Tallest Tower:} The objective is to construct the tallest possible tower.
    \item \emph{Longest Overhang:} The objective is to construct the tower with the maximum distance from the center of geometry of the bottom block to the furthest vertical side of the top block.
    \item \emph{Maximum Unsupported Area:} The objective is to construct the tower where each block has as much area possible unsupported by the block below it.
\end{enumerate}

See Appendix \ref{sec:appendix-gen} for a discussion on the generalizability of our method outside of the towers domain.

\subsection{Perception, planning, and execution}

\textbf{Perception}
For the system to robustly pick up blocks and recover from unstable towers falling in unpredictable configurations, we require a perception system that can identify and localize objects at arbitrary positions. Although more advanced perception systems might be needed for arbitrary objects, vision is not the immediate focus of this work, so we pattern our objects with ArUco markers to simplify perception. To indicate identity and avoid orientation ambiguity, each object has a unique ArUco marker on each face.

Two RealSense D435 depth cameras mounted statically on a frame observe the workspace and allow for localizing the objects with minimal occlusions. If an object is not visible, it is assumed to be at its home position behind the arm. Due to the resolution of the cameras and size constraints of the tags on the blocks, we found that the pose estimates from the static cameras can have up to 1 centimeter of error. This level of error is acceptable, as rough pose estimates are refined with a third RealSense D435 camera mounted on the robot wrist. As the arm moves to a pre-grasp pose computed from the noisy object pose estimate, the wrist-mounted camera collects images closer to the the object to be grasped, allowing for a refined pose estimate and more precise grasp.

\textbf{Planning} In this domain, executing an abstract action requires a multi-step task and motion plan. For example, to place an object on a tower with an arbitrary relative pose to the block below it, regrasping may be necessary. When a tower falls over, the robot will also need to move fallen blocks out of the way to build the next tower.

To handle these scenarios, we turn to a large body of work in task and motion planning. We use PDDLStream \cite{garrett2020pddlstream}, which integrates PDDL task-level planning with lower level motion planning. The PDDL domain describes actions including picking and placing objects and moving the arm through free space, while a Bidirectional RRT \cite{kuffner2000rrt} in joint configuration space performs motion planning and collision checking with a surrogate world model implemented in PyBullet \cite{coumans2016pybullet}. In this work we make the simplifying assumption that there are dedicated positions for the base of the tower, regrasping, and storage for each of the objects.
These constraints are specified to the planner to reduce planning time by limiting the search space of possible action parameters.

\textbf{Execution} The motion plans generated by PDDLStream are executed using joint-space controllers on the robot. When constructing a tower in the experimentation phase, after each block placement the wrist camera is used to check for tower stability. If a tower was unstable, then the last manipulated block will not be near its expected pose in front of the gripper.

To improve data collection efficiency, we parallelize execution and planning. As the robot executes a motion plan to assemble or disassemble a tower, the planner produces plans to move each individual block in that tower under the assumption that all actions will be successful. This parallelism is interrupted if a tower falls over prematurely, prompting a replan to clear the fallen blocks.

If the state of the world is such that a robot is unable to find a plan to proceed with experimentation or execute an existing plan, human intervention may be required. We have provisioned for several of these cases, including blocks falling off the table, or too close to one another for the planner to find feasible grasp candidates. Once such issues are manually resolved (e.g., by putting the block back on the table), the robot can update its estimate of block poses and resume planning.

\subsection{Learning}
\label{sec:imp-learning}

As discussed in Section \ref{sec:method-apf-model}, the distribution over {\sc apf}{} model parameters is represented by an ensemble of networks.
In our implementation, the ensemble is made up of {\sc gnn}s with domain-specific connectivity.
The input to the {\sc gnn} is an abstract action sequence, $\mathbf{a}$.
Each action, or block placement $a_i$, is passed into a separate node in the graph, and each node (corresponding to a block placement in the tower) is connected to nodes above it in the tower.
This mirrors the analytical computation of tower stability, in that each subtower's combined center of mass must be within the contact patch of the block below it.
We refer to this network architecture as a {\sc tgn}{}, or {\em Towers Graph Network}.
Other network architectures which are invariant to task plan length are a \emph{Fully Connected Graph Network} ({{\sc fcgn}}) and a {\sc lstm} model.
The {{\sc fcgn}} uses the same node and edge networks as our {\sc tgn}{} model, but has edges between each node.
The {\sc lstm} model passes each block's vector representation through the network in order starting from the top of the tower, and most closely matches our {\sc tgn}{} connectivity.
A visualization of the connectivity of each architecture is given in Figure \ref{fig:architecture_graphic}.

\begin{figure}
    \centering{\includegraphics[width=\columnwidth]{figures/architecture_graphic_flat.pdf}}
    \caption{The flow of information for the model architectures compared in Section \ref{sec:eval-graph}. The {\sc tgn}{} uses domain specific connectivity, while the {\sc fcgn} assumes no prior knowledge on how the blocks should be used together to inform predicting feasibility. The {\sc lstm} simply iterates through the blocks starting with the top block.}
    \label{fig:architecture_graphic}
    \vspace{-10pt}
\end{figure}

In our experiments, $10$ networks are used in the ensemble.
Each individual network is randomly initialized and trained using the binary cross-entropy loss function with early stopping according to the loss on a validation set, which is also collected actively.

Before active experimentation, each model in the ensemble is initialized by training on the same dataset (shuffled differently for each) of $40$ randomly generated towers. For the  \emph{complete} strategy the towers are of size $2-5$, and for the \emph{sequential}, \emph{incremental}, and \emph{greedy} strategies they are of size $2$.
During the experimentation phase, at each iteration the top $10$ most informative towers are chosen and labeled by attempting to build each with the robot.
$20\%$ of the collected data is added to a validation set and the remainder is added to the training set.
We perform data augmentation by rotating each collected tower $90, 180, \text{and}, 270$ degrees about the axis normal to the table surface.

\subsection{Abstract plan feasibility model}
\label{sec:method-apf-model}

Our {\sc apf}{} model, $\Pr(\phi \mid \mathbf{a}; \Theta)$, aims to capture the uncertainty in the underlying stochastic process of predicting the feasibility of abstract action sequences.
This uncertainty can be attributed to phenomena such as the robot's motor capabilities, errors in perception, or unmodeled behaviors of the planning process, and is referred to as {\em aleatoric uncertainty}.
Our goal is to learn parameters $\Theta$ such that this uncertainty is adequately captured and our model can be leveraged, along with a low level planner, to achieve a goal.

We take a Bayesian approach to learning the model parameters, and maintain a distribution over the parameter space, $\Pr(\Theta)$.
This distribution aims to capture the uncertainty we have regarding the accuracy of our predictions, referred to as {\em epistemic uncertainty}.
In general, for complex model classes such as neural network classifiers, an explicit representation of $\Pr(\Theta \mid \mathcal{D})$ for training data $\mathcal{D}$ is difficult to construct or update with new data.
We therefore follow the strategy of \citet{beluch_power_2018} and represent this uncertainty with an ensemble of $N$ models, $(\theta_1, \ldots, \theta_N)$, where ${\theta_i} \in \mathbb{R}^{d}$.
Initial parameters are drawn independently at random and are updated to incorporate new data via gradient descent.

The design of the models in the ensemble is selected to match the underlying structure of the prediction problem.
In a naive implementation, we can directly estimate feasibility from the entire sequence of actions. We will refer to this approach as a {\it complete}{} model, denoted by $\Theta_{comp}$.
However, we observe that the \emph{infeasible sub-sequence property} provides a strong constraint on the set of feasible plans: sequence $(a_1, \ldots, a_n)$ is only feasible if all of its prefixes are also feasible. As such, the model can instead learn the probability a specific action is feasible given all previous actions were feasible. We will refer to a model that considers this property as $\Theta_{ss}$.
Under this model, the feasibility of a plan, $\mathbf{a}$, is:
\begin{equation}
\label{eq:theta-ss}
    \Pr(\Phi_{1:n} \mid \mathbf{a}, \Theta_{ss}) = \prod\limits_{i=2}^n \Pr(\Phi_i \mid a_{1:i}, \Phi_{1:i-1} = \bm1; \Theta_{ss}),
\end{equation}
where $\Phi_i$ represents whether action $a_i$ is feasible given $a_{1:i-1}$ were feasible, and we use the subscript $1:n$ to refer to a sequence of variables. In our method we assume initial actions are feasible, meaning $\Pr(\Phi_1 = 1 \mid a_1) = 1$.

The $\Theta_{comp}$ model only considers full action sequences, and therefore entire plans correspond to a single label once they are executed. On the other hand, $\Theta_{ss}$ requires labels after each action is executed.

In both of these models, the length of plans for which we require predictions varies.  Therefore, we use {\em graph neural networks} ({\sc gnn}s), which make predictions based on aggregations of local properties and relations among the input entities, and exploit parameter tying to model global properties of plans of arbitrary size using a fixed-dimensional parameterization $\Theta$.  For a detailed description of {\sc gnn}s, see the overview by \cite{zhou2018graph}.
More details about the specific architecture we use can be found in Section \ref{sec:imp-learning}.

\subsection{Entropy reduction}

Following \cite{mackay1992objective, cohn1996active}, we guide our active learning by picking a sequence of data $\mathcal{D}$ that maximally reduces the entropy of $\Pr(\Theta \mid \mathcal{D})$. The general problem of designing a sequence of experiments to minimize entropy --- or equivalently, maximize information gain --- is a difficult sequential decision-making problem.  Fortunately, due to sub-modularity of the objective, a myopic approach that considers only the next experiment to conduct can be shown to be a good approximation to the optimal experimentation strategy \cite{Nemhauser1978submodular}.

Given a model distribution $\Pr(\Theta \mid \mathcal{D})$ that depends on the data we have seen so far, $\mathcal{D}$, we choose the action sequence $\mathbf{a} \in \mathbf{A}$ that reduces the entropy of the posterior distribution as much as possible:
\begin{equation}\label{eq:theta_entropy_objective2}
\mathbf{a}^* = \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\Theta \mid \mathcal{D}) - \expect{\phi \sim \Pr(\cdot \mid \mathcal{D}, \mathbf{a})} \left[ \mathrm{H}(\Theta \mid \mathcal{D}, \mathbf{a}, \phi) \right]
\end{equation}
While the robot can select the plan, $\mathbf{a}$, to experiment with, it cannot select the outcome $\phi$, so to compute this quantity, we have to take an expectation over the outcome, using our current model distribution.

Estimating the entropy over a high-dimensional parameter space is expensive, so we follow the approach of~\citet{houlsby_bayesian_2011} to reformulate the objective in (\ref{eq:theta_entropy_objective2}) as:
\begin{align}\label{eq:y_entropy_objective2}
\mathbf{a}^* &= \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{I}(\Phi : \Theta \mid \mathcal{D}, \mathbf{a}) \\
&= \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\Phi \mid \mathcal{D}, \mathbf{a}) -
                          \expect{\Theta \sim \Pr(\cdot \mid \mathcal{D})} \left[ \mathrm{H}(\Phi \mid \mathbf{a}; \Theta) \right],
\end{align}
allowing the computation of entropies to take place in the lower-dimensional label space, $\Phi$. This is known as {\em Bayesian Active Learning by Disagreement}, or {\sc bald}{}.

The {\sc bald}{} objective invites an appealing interpretation: maximizing the first term encourages selecting an $\mathbf{a}$ that our model is overall uncertain about, and minimizing the second term encourages selecting an $\mathbf{a}$ for which the individual models in $(\theta_1, \ldots, \theta_N)$ can make confident predictions about the outcome $\phi$.  If we think of the overall uncertainty as a combination of \emph{epistemic} and \emph{aleatoric uncertainty}, then this objective seeks an experiment with high overall uncertainty and low \emph{aleatoric uncertainty}, which therefore has high \emph{epistemic uncertainty}.  Intuitively, if the various possible models in $\Pr(\Theta \mid \mathcal{D})$ are individually confident but about differing outcomes, then observing the $\phi$ value corresponding to $\mathbf{a}$ is likely to prove some of those outcomes incorrect.

Using an ensemble of equally weighted parameter vectors ($\theta_1, \ldots, \theta_N$) to represent $\Pr(\Theta \mid \mathcal{D})$ allows us to compute a global feasibility prediction,
\[
\widehat{\Pr}(\Phi = \phi \mid \mathbf{a}; \Theta) = \frac{1}{N} \sum_{i=1}^N \Pr(\Phi = \phi \mid \mathbf{a}; \theta_i)
\]
as well as find the experiment that maximizes the estimated {\sc bald}{} objective in the form: \begin{equation}\label{eq:final-criterion}
\textsc{bald}(\mathbf{a}; \Theta) = \mathrm{H}(\widehat{\Pr}(\Phi \mid \mathbf{a}; \Theta)) -
                          \frac{1}{N}\sum_{i=1}^N \mathrm{H}(\Pr(\Phi \mid \mathbf{a}; \theta_i)).
                          \end{equation}

\subsection{Sampling Strategies}
\label{sec:sampling-strategies}

Now that we have established an informational score for experiments, we consider several sampling strategies for optimizing over $\mathbf{A}$, the set of plans up to a fixed length $L$.
Maximizing the {\sc bald}{} objective over the entire set $\mathbf{A}$ is difficult because we need to consider all discrete plans up to length $L$, as well as all possible assignments to each continuous abstract action parameter.

\textbf{Complete} One strategy we consider is uniformly sampling complete plans from $\mathbf{A}$ and scoring the samples. We call this the {\it complete}{} strategy.
\begin{equation}
\argmax{\mathbf{a} \in \mathbf{A}}  \text{{\sc bald}{}}(\mathbf{a} ; \Theta_{comp})
\end{equation}

Unfortunately, to achieve a consistent sampling density, the number of required samples scales exponentially with the length of the plan. Additionally, this strategy might generate most of its samples in the infeasible part of the space.

\textbf{Greedy} Another strategy requiring fewer samples is a {\it greedy}{} approach, in which we select the next action $a_n$ which maximizes the {\sc bald}{} objective, given that we have already optimistically constructed $a_{1:n-1}$. This strategy does not take into consideration that if a plan fails early, we do not get to learn from the full plan execution.

We can leverage additional structure afforded to us by the \emph{infeasible subsequence property} when we do active learning using the $\Theta_{ss}$ model class.
In the following, we consider two possible strategies.

\textbf{Sequential} When generating a potentially informative plan for the $\Theta_{ss}$ model, we can take into account the probability a specific action will be attempted (i.e., that the plan was successful up until that action).
This allows us to find plans whose informative outcomes have a high probability of being observed.
The resulting objective is:
\begin{equation}
\argmax{a_{1:n} \in \mathbf{A}} \sum_{i=2}^n \Pr(\Phi_{1:i-1} = \bm1 \mid a_{1:i-1}; \Theta_{ss}) \text{{\sc bald}{}}(a_{1:i} ; \Theta_{ss})
\end{equation}
where the probability is calculated as in Equation \ref{eq:theta-ss}.
This equation computes the expected information gain for executing a plan, taking into account the probability that plan execution fails at any given step as predicted by the learned {\sc apf}{} model.
We refer to this as the sequential{} strategy.

We implement the sequential{} approach naively by sampling and scoring entire plans. Like  {\it complete}{}, this method requires exponentially more samples for longer plans, however, in the domain we considered, a sampling approach was acceptable as we had a relatively short plan horizon. In the future work we hope to extend this strategy to a search-based method which prunes candidate plans by their predicted feasibility.

\textbf{Incremental} We also consider a strategy where we only consider plans $(a_1, \ldots, a_n)$ for which we have already observed the prefix to be feasible. In other words, the prefix $(a_1, \ldots, a_{n-1})$ together with result $\phi_{1:n-1} = \bm1$ are in the current data set $\mathcal{D}$.  We call this the incremental{} strategy
\begin{equation}
\argmax{a_{1:n} \in \mathbf{A}} \mathbbm{1}_{(a_{1:n-1}, \phi=1) \in \mathcal{D}} \text{{\sc bald}{}}(a_{1:n} ; \Theta_{ss})
\end{equation}

Although this strategy finds more feasible plans than {\it complete}{}, it also requires the robot to reuse plan prefixes, so we do not gather novel observations when repeating a plan prefix. Constraining our experiments to build on previously feasible plans may be overly restrictive.
\subsection{Experimentation phase}

During the experimentation phase, the robot performs active learning to efficiently design, plan, and execute abstract action sequences that are informative about {\sc apf}{}.
This phase operates in a loop.
At each iteration, the robot first generates candidate action sequences that may be informative according to some \emph{sampling strategy}.
Each action sequence is then scored using the current model according to some acquisition function, $f: \mathbf{A} \rightarrow \mathbb{R}$.
The highest scoring plans are executed on the robot to obtain feasibility labels which are then used to update the model for future iterations of the active learning loop.
The effectiveness of active learning in reducing data complexity depends critically upon the choice of acquisition function and sampling strategy --- or which action sequences are considered as possible experiments.
These choices are discussed in more detail in Section~\ref{sec:active-learning}.

\subsection{Evaluation phase}

After the {\sc apf}{} model has been learned, it can be used to achieve multiple objectives.
We assume that the robot is given an objective function $V$ which maps action sequences to real values and its goal is to find the abstract action sequence, $\mathbf{a} \in \mathbf{A}$ with the highest expected value,
\begin{equation}
    \mathbf{a}^* = \argmax{\mathbf{a} \in \mathbf{A}} \mathbb{E}_{\Pr(\phi|\mathbf{a}, \Theta)}\left[ V(\mathbf{a}) \right]
\end{equation}
where the expectation takes into account the likelihood that an abstract action sequence is  feasible when executed on the real robot.
To maximize this objective, we use a Monte Carlo planner which randomly samples action sequences and selects the one with the maximum expected value.

\subsection{Real Robot Evaluations}
\label{sec:appendix-real-robot}

In this section we provide additional results for the experiments described in Section \ref{sec:eval-robot}.
Figure \ref{fig:towers-tallest} shows the towers built when performing the \emph{Tallest Tower} task with each of the analytical, simulation, and learned models.
$10$ towers were built for each task using $5$ blocks.
Towers that have fallen over or do not have $5$ blocks were infeasible plans.
Figures \ref{fig:towers-overhang} and \ref{fig:towers-unsupported} show the evaluation towers for the \emph{Longest Overhang} and \emph{Maximum Unsupported Area} tasks, respectively.

\begin{figure*}[t!]
    \centering{\includegraphics[width=0.85\linewidth]{figures/comparison_tallest_blurred.png}}
    \caption{Towers built for the \emph{Tallest} task when using different \emph{Abstract Plan Feasibility} models.}
    \label{fig:towers-tallest}
\end{figure*}

\begin{figure*}[t!]
    \centering{\includegraphics[width=0.85\linewidth]{figures/comparison_overhang_blurred.png}}
    \caption{Towers built for the \emph{Longest Overhang} task when using different \emph{Abstract Plan Feasibility} models.}
    \label{fig:towers-overhang}
\end{figure*}

\begin{figure*}[t!]
    \centering{\includegraphics[width=0.85\linewidth]{figures/comparison_contact_blurred.png}}
    \caption{Towers built for the \emph{Maximum Unsupported Area} task when using different \emph{Abstract Plan Feasibility} models.}
    \label{fig:towers-unsupported}
\end{figure*}

\subsection{Supervised vs Active Learning Comparisons}
\label{sec:appendix-sim-random}

In this section we compare the active learning methods described in this paper to supervised learning baselines which do not perform active data collection to train the {\sc apf}{} model.
Figure \ref{fig:eval-strategies-ss} compares our methods which use the $\Theta_{ss}$ model class to a \emph{random-ss} strategy.
\emph{random-ss} randomly samples action sequences and labels each subsequence. The results show that our active methods which leverage the \emph{infeasible subsequence property}, sequential{} and incremental{}, outperform \emph{random-ss}. \emph{random-ss} only outperforms {\it greedy}{}, showing that a random strategy is able to find more interesting training towers than a myopic approach which simply tries to maximize the {\sc bald}{} objective for a single block placement.

Figure \ref{fig:eval-strategies-comp} compares our method, {\it complete}{}, which uses the $\Theta_{comp}$ model class, to a \emph{random-comp} strategy. \emph{random-comp} randomly samples action sequences to train on and only labels the full sequences. As expected, training on sequences which maximize the {\sc bald}{} objective is more effective than randomly sampling action sequences.

The data used to train the \emph{random} methods is not actively collected, but we show how training on increasingly larger datasets compares to the actively collected dataset.

\begin{figure*}
    \centering
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_overhang_ss.pdf}
        \caption{}
        \label{fig:eval-strategies-overhang-ss}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_contact_ss.pdf}
        \label{fig:eval-strategies-contact-ss}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_tallest_ss.pdf}
    \label{fig:eval-strategies-tallest-ss}
    \end{subfigure}
        \caption{A comparison of sampling strategies which use the $\Theta_{ss}$ model class on different downstream tasks all performed in simulation.
        The \emph{random-ss} strategy randomly samples action sequences and thus does not use active learning.
        Each method evaluation consists of $4$ separate {\sc apf}{} model-learning runs, and each point is the Median Normalized Regret of $50$ individual planning runs per learned model. The shaded regions show $25\%$ and $75\%$ quantiles.}
        \label{fig:eval-strategies-ss}
        \vspace{-10pt}
\end{figure*}

\begin{figure*}
    \centering
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_overhang_comp.pdf}
        \label{fig:eval-strategies-overhang-comp}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_contact_comp.pdf}
        \label{fig:eval-strategies-contact-comp}
    \end{subfigure}
    \begin{subfigure}{0.32\textwidth}
        \centering
        \includegraphics[width=\textwidth, trim={.5cm 0 1.5cm 0}, clip]{figures/eval_strategies_tallest_comp.pdf}
    \label{fig:eval-strategies-tallest-comp}
    \end{subfigure}
        \caption{A comparison of sampling strategies which use the $\Theta_{comp}$ model class on different downstream tasks all performed in simulation.
        The \emph{random-comp} strategy randomly samples action sequences and thus does not use active learning.
        Each method evaluation consists of $4$ separate {\sc apf}{} model-learning runs, and each point is the Median Normalized Regret of $50$ individual planning runs per learned model. The shaded regions show $25\%$ and $75\%$ quantiles.}
        \label{fig:eval-strategies-comp}
        \vspace{-10pt}
\end{figure*}

\subsection{Method Generalizability}
\label{sec:appendix-gen}

Here, we motivate a more general class of problems for which our system applies and clarify which components of the system are specific to our chosen domain.
Our method most benefits domains where the feasibility of an action depends strongly on the preceding action sequence (e.g., adding a fifth block to a tower that already has four blocks).
Domains that include construction tasks, like ours, will commonly benefit from non-myopic information gathering and a feasibility predictor that incorporates previous actions into its predictions.
To apply our method to a new domain (e.g., consider a packing problem where many objects need to be placed in a larger container), the overall system/methodology would remain unchanged.
However, one would need to adapt the following domain-specific components:

\begin{enumerate}
    \item \emph{Abstract action definitions}. Parameterize an abstract action that is appropriate for the domain and connect it to concrete actions (e.g., object locations within the container).
    \item \emph{Experimental infrastructure}. Additional capabilities to autonomously plan and execute abstract actions in the physical world (e.g., motion and grasp planning infrastructure).

    \item \emph{Feasibility detector}. The notion of {\sc apf}{} will depend on the desired outcome of an abstract action. For a new action, we require a method to autonomously acquire the feasibility label during execution (e.g., whether the gripper will collide when placing the object or if an object will be damaged).
    \item \emph{Additional inductive bias} (optional). Additional structure to the learner can further increase data efficiency, as shown by our {\sc tgn} method. However, this is not required as we show in Figure \ref{fig:architecture_graphic} that a general purpose graph network can be used (e.g., a graph network that has connectivity between all objects).
\end{enumerate}

\subsection{Learning}

We aim to learn a model which is able to make predictions in sequential decision-making problems involving multiple objects.
Our current work is limited to classification predictions, but could be extended to handle regression.
The model, $p(\bm{y} | \bm{x} ; \bm{\theta})$, takes as input the state of the objects, $\bm{x}$, and returns a prediction $\bm{y}$, determined by the parameters of the model, $\bm{\theta}$.
We also maintain a posterior distribution over our model parameters given the data we have seen so far, $p(\bm{\theta}|D)$, by leveraging an ensemble of models, which we discuss in Section \ref{sec:bald}.
The learning process occurs in several repeating steps.

First, the robot synthesizes a pool of potential inputs, $D_{pool}$ (shown in blue in Figure \ref{fig:method_overview}).
In the case of multiple object interactions, the size of this space makes random data acquisition unlikely to succeed.
In our work we are able to handle this by only considering inputs to the model that differ from data already seen by one action.
This prevents the agent from considering full inputs that it is incapable of actually attempting.
We elaborate on this in Section \ref{sec:acquisition}.

Next, we find the inputs, $D_{BALD}$, from $D_{pool}$ that will maximally reduce the entropy over our model parameters, $H(\bm{\theta}|D)$, when labeled, by using the BALD \cite{houlsby_bayesian_2011} objective (shown in red in Figure \ref{fig:method_overview}).
This objective selects inputs which our model is uncertain about, and which result in high disagreement across our ensemble predictions.
This is discussed in more detail in Section \ref{sec:bald}.

Now that we know which inputs would most benefit our model, we need to label them (shown in orange in Figure \ref{fig:method_overview}).
Here we are able to leverage our TAMP planner by giving it our desired object states, $\bm{x}$.
The robot then executes the returned plan, and labels the input with its associated $\bm{y}$.

Finally, the model parameters can be updated given the newly received labelled data, $D_{train}$ (shown in green in Figure \ref{fig:method_overview}), and the cycle repeats.

\subsection{Evaluation}

The benefit of learning a global model is that it can be used for several downstream tasks.
To evaluate the performance of our model, we supply a task-specific objective function, $f_{task}$, and the ground truth optimal value of this function, $v_{gt}$.
We then optimize this objective function, subject to the desired constraint of the model, to find the optimal input, $\bm{x}_{opt}$ (shown in purple in Figure \ref{fig:method_overview}).
Then, we pass the desired state, $\bm{x}_{opt}$, to the TAMP planner to get an executable plan to attempt to achieve this state.
Finally, we execute the plan and determine the true value of the given state, $v_{opt}$.
The metric we use to evaluate performance is regret, or the difference between the ground truth optimal value, $v_{gt}$, and the value found when using our model, $v_{opt}$.
If we have learned a good model that is representative of the phenomena we are aiming to characterize, this value should approach the ground truth optimal value, and our regret will approach zero.
\subsection{Problem Formulation}
\label{sec:exp-design}
Our objective is to learn a model that predicts plan success, that is, to learn the parameters $\Theta$ that most accurately predict
\[
\Pr(\phi \mid \mathbf{a}; \Theta),
\]
where $\phi \in \{0, 1\}$ is the success of the plan given by action sequence $\mathbf{a} \in \mathbf{A}$. We wish to learn $\Theta$ from a sequence of data $\mathcal{D}$, and we wish to learn $\Theta$ from a minimal length sequence of $\mathcal{D}$.

\subsubsection{Entropy reduction}
Following \ref{Mackay92,Cohn96}, we can pick a sequence of data $\mathcal{D}$ that maximizes the information gain, or reduces the entropy of $\Pr(\Theta \mid \mathcal{D})$. The general problem of designing a sequence of experiments to maximize some sort of information gain is a difficult sequential decision-making problem.  In many cases, due to sub-modularity of the objective, a greedy, ``myopic'' approach that considers only the next experiment to conduct can be shown to be a good approximation to the optimal experimentation strategy~\cite{Krause?}.

Given a model distribution $\Pr(\Theta \mid \mathcal{D})$ that depends on the data we have seen so far, $\mathcal{D}$, we choose the $\mathbf{a} \in \mathbf{A}$ that reduces the entropy of the posterior distribution as much as possible: \inote{this seems to imply that we've already marginalized out $\phi$? I think we need to put that back in}
\begin{equation}\label{eq:theta_entropy_objective2}
\mathbf{a}^* = \argmin{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\Theta \mid \mathcal{D}, \mathbf{a})\;\;.
\end{equation}
While the agent can select the action sequence to experiment with, $\mathbf{a}$, it cannot select the outcome $\phi$, so to compute this quantity, we have to take an expectation over the outcome, using our current model distribution:
\[\mathrm{H}(\Theta \mid \mathcal{D}, \mathbf{a}) = \expect{\phi \sim \Pr(\cdot \mid \mathcal{D}, \mathbf{a})} \mathrm{H}(\Theta \mid \mathcal{D}, \mathbf{a}, \phi) \;\;,\]
where
\[\Pr(\phi \mid \mathcal{D}, \mathbf{a}) = \int_\theta \Pr(\phi \mid \mathbf{a}; \theta) \Pr(\theta \mid \mathcal{D})\;\;.\]

Estimating the entropy over a high-dimensional parameter space is difficult, so we follow the approach of~\citet{houlsby_bayesian_2011} to reformulate the objective in (\ref{eq:theta_entropy_objective2}) as
\begin{equation}\label{eq:y_entropy_objective2}
\mathbf{a}^* = \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\Phi \mid \mathcal{D}, \mathbf{a}) -
                          \expect{\theta \sim \Pr(\cdot \mid \mathcal{D})} \mathrm{H}(\Phi \mid \mathbf{a}; \theta)\;\;,
\end{equation}
allowing the computation of entropies to take place in the typically lower-dimensional label space. This is known as the {\sc bald}{} objective. \inote{is the switch between $\theta, \Theta$ or $\phi, \Phi$ supposed to represent a specific value vs a random variable?}

In addition to improved efficiency, the objective in (\ref{eq:y_entropy_objective2}) invites an appealing interpretation: maximizing the first term encourages selecting an $\mathbf{a}$ that our model is overall uncertain about, and minimizing the second term encourages selecting an $\mathbf{a}$ for which the individual models $\theta$ can make confident predictions about the outcome $\phi$.  If we think of the overall uncertainty as a combination of epistemic and aleatoric uncertainty, then this objective seeks an example with high overall uncertainty and low aleatoric uncertainty, which therefore has high epistemic uncertainty.  In other words, if the various possible models in $\Pr(\Theta \mid \mathcal{D})$ are individually confident but about differing outcomes, then observing the $\phi$ value corresponding to $\mathbf{a}$ is likely to prove some of those outcomes incorrect.
Using an ensemble of equally weighted parameter vectors $\theta_1, \ldots, \theta_N$ to represent $\Pr(\Theta \mid \mathcal{D})$ allows us to compute a global feasibility prediction
\[
\widehat{\Pr}(\Phi = \phi \mid \mathbf{a}; \theta) = \frac{1}{N} \sum_{i=1}^N \Pr(\Phi = \phi \mid \mathbf{a}; \theta_i)
\]
as well as find the experiment that optimizes the estimated {\sc bald}{} objective in the form \begin{equation}\label{eq:final-criterion}
\mathbf{a}^* = \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\widehat{\Pr}(\Phi \mid \mathbf{a}; \theta)) -
                          \frac{1}{N}\sum_{i=1}^N \mathrm{H}(\Pr(\Phi \mid \mathbf{a}; \theta_i))\;\;.
                          \end{equation}
\subsection{Abstract plan feasibility model}
\label{sec:method-apf-model}
The role of the {\sc apf}{} model is to predict the probability that an action sequence is feasible, $\Pr(\phi \mid \mathbf{a})$, where $\mathbf{a} = (a_1, \ldots, a_n)$ is an action sequences, $\phi$ is a Boolean random variable indicating that the action sequence can be executed feasibly, and the probability distribution represents inherent {\em aleatoric uncertainty} due to unmodeled behavior of the detailed planning process and execution of actions in the world.

\begin{figure*}
\includegraphics[width=0.95\linewidth]{figures/overview.png}
\caption{\label{fig:method_overview} The proposed system that learns \emph{Abstract Plan Feasibility} ({\sc apf}{}) operates in two phases. \textbf{Experimentation Phase} (left) First, the robot will iteratively design and execute experiments that improves its {\sc apf}{} model. (A) Using its current model, the robot selects the action sequence, $\mathbf{a^*}$ that minimizes its entropy over {\sc apf}{} models. (B) The robot computes and executes a detailed motion plan for executing the abstract action sequence. (C) After observing the true plan feasibility, $\phi$, the robot updates its {\sc apf}{} model, represented as an ensemble of neural networks. \textbf{Execution Phase} (right) Once an {\sc apf}{} model has been learned, the robot can use it to perform various tasks, such as build the tallest tower, or the tower with the largest overhang.}
\end{figure*}

Because our objective is to learn the {\sc apf}{} model from as few data samples as possible, it is critical that it be formulated in a way that makes our {\em epistemic uncertainty} about the model explicit.  We do this by representing a particular model using a parameter vector $\theta$ in the space of possible {\sc apf}{} models $\Theta$.  So the prediction of a particular model is $\Pr(\phi \mid \mathbf{a}; \theta)$ and our epistemic uncertainty can be described in terms of a distribution on the model parameter space, $\Pr(\Theta)$.

In general, for complex model classes, explicit representation and updating of $\Pr(\Theta \mid \mathcal{D})$ for training data $\mathcal{D}$ is too difficult.  We follow the strategy of~\citet{ensemble} and represent this uncertainty using an ensemble of $k$ models, whose initial parameters $(\theta_1, \ldots, \theta_k)$ are drawn independently at random and are updated to incorporate new data via gradient descent.

The design of the models in the ensemble is selected to match the underlying structure of the prediction problem.  Importantly, the length of action sequences for which we require predictions varies during both the experimentation and execution phases.  For this reason, we use {\em graph neural networks} ({\sc gnn}s), which make predictions based on aggregations of local properties and relations among the input entities, and exploit parameter tying to model global properties of collections of objects of arbitrary size using a fixed-dimensional parameterization $\Theta$.  For a detailed description of {\sc gnn}s, see the overview by \citet{Battaglia}.

We take advantage of the {\em infeasible sub-sequence} property of the {\sc apf}{} problem to design a special connectivity structure for our {\sc gnn} models.  As shown in figure~\ref{fig:graph_network}, the node corresponding to action $a_i$ is connected to each node representing $a_j$ for $1 \leq j < i$.  This encodes the structural property that the feasibility of step $i$ in the plan depends on all previous actions.  To make a prediction, an encoding of $\mathbf{a}$ is fed into the network, some number of rounds of message passing is performed on the graph using the local neural network models $\theta$, and the average activation level of each node is computed and passed through a sigmoidal transformation to obtain a prediction $\Pr(\phi \mid \mathbf{a})$.

\lpknote{We might want to put more details in here?}

\subsubsection{Domain of experimentation}
Now that we have established a strategy for selecting the best experiment from a set $\mathbf{A}$, we investigate several choices of that set.   Let $\mathcal{A}$ be a (possibly infinite) set of possible individual actions and $L$ be the maximum action-sequence length.

Most straightforwardly, we would let $\mathbf{A}$ be all possible sequences $(a_1, \ldots, a_l)$ with $a_i \in \mathcal{A}$ and $1 \leq l \leq L$.
We not be able to maximize objective (\ref{eq:final-criterion}) over the entire set and will therefore have to let $\mathbf{A}$ be a randomly generated set of samples from that space and optimize only over the samples.   We call this the {\it all sequences{}} strategy.

The all sequences{} approach might generate most of its samples in the infeasible part of the space, requiring a large sample set and causing slow computation.
We observe that the infeasible sub-sequence property provides a strong constraint on the set of actually feasible action sequences:  sequence $(a_1, \ldots, a_n)$ is only feasible if all of its prefixes are also feasible.  We can use this insight to bias our sampling to focus on action sequences that are much more likely to be feasible by only considering sequences $(a_1, \ldots, a_n)$ for which the prefix $(a_1, \ldots, a_{i-1})$ together with result $\phi = 1$ are in the current data set $\mathcal{D}$.  We call this the {\it sequential{}} strategy.

Finally, we observe that asking the robot to execute action sequences is a substantial cost and that if it has just finished successfully executing a sequence $(a_1, \ldots, a_n)$, rather than asking for a completely unrelated sequence, we have the opportunity to immediately append another action to that sequence and execute just the last step on the robot.  In this {\em incremental{}} strategy, we let $\mathbf{A}$ consist only of one-step continuations of the previous action sequence if it was feasible, and otherwise revert to the sequential{} approach.

\subsection{Integrated system}

In this section, we illustrate the integration of the active learning methodology into an overall experimentation, learning, planning, and execution system, which operates in two phases:  experimentation and execution.

Both phases depend on the ability to construct and execute detailed plans on a real robot given an abstract action sequence.  We assume that a detailed planning and execution system is available that can integrate perception, planning, and control to carry out that action sequence and observe whether or not it was successful.  In section~\ref{experimentPlanner} we describe our experimental implementation of such a system in detail.  In the following, we assume the existence of a procedure \textproc{detailedPlanEx}, which takes a sequence of abstract actions $\mathbf{a}$ and the current robot state, and performs closed-loop perception, planning, and control to execute actions $a \in \mathbf{a}$ in sequence until it determines that $\mathbf{a}$ has been successfully carried out or has become impossible.  It returns a Boolean value indicating whether it succeeded.

\subsubsection{Experimentation phase}
The experimentation phase operates, as shown in algorithm~\ref{exper_pseudocode}, as follows.  It starts by initializing $n_m$ separate parameter sets $\theta$ for the {\sc gnn}s representing the ${\sc apf}$ model.  It then iterates $n_i$ through an experimentation and training loop.  It is parametrized by an action sampling strategy (one of all sequences{}, sequential{}, or incremental{}), which it uses to generate $n_s$ sample action sequences $A_hat$ (note that the incremental{} strategy depends on the current world state and is really only sensible for $n_b = 1$).  Then, the approximate {\sc bald}{} objective is used to select the best batch of $n_b$ action sequences $A_batch$ from $A_hat$.  These action sequences are executed, yielding results $\phi_batch$, and the test sequences and results are added to the data set.  Finally, the parameters $\theta_i$ for each model in the ensemble are updated and a new iteration begins.

\begin{scriptsize}
\begin{verbatim}
    explore(n_b, n_s, n_m, n_i, A, L, sampler, world_state)
        Theta = (\theta_1, \ldots, \theta_n_m) randomly initialized GNNs
        D = {}
        for iteration in n_i
            A_hat = sampler(A, L, D, n_s, world_state)
            A_batch = top_n(bald(., Theta), A_hat, n_b)
            Phi_batch = [detailedPlanEx(a, world_state) for a in A_batch]
            D = D u zip(A_batch, Phi_batch)
            Theta = [train(theta, D) for theta in Theta]
        return Theta
\end{verbatim}
\end{scriptsize}
\lpknote{If this pseudocode is worth having, then typeset}

\subsubsection{Execution phase}

After the {\sc apf}{} model has been learned, it can be used flexibly to achieve multiple objectives.  We assume that the robot is given an objective function $V$ which maps action sequences to real values and its goal is to find an abstract action sequence
\[\mathbf{a}^*= \argmax{\{\mathbf{a} \in \mathbf{A} \mid \Pr(\phi \mid \mathbf{a}) > 1-\epsilon\}} V(\mathbf{a})\;\;,\]
which has high value subject to being $1-\epsilon$ likely to be feasibly executable.

\lpknote{Add some detail here about the Monte-carlo planner we are using to select plans at performance time.}
\subsection{Notes from meeting}

What priors are we bringing into our curiosity framework?

\begin{enumerate}
    \item Stable states (we're curious about whether the built towers fall over)
    \item Sequential building (place one block at a time)
    \item The structure of the computation (GNN)
\end{enumerate}

\subsection{Local Interactions}

We leverage a TAMP planner, PDDLStream \cite{garrett2020pddlstream}, to allow the robot to plan for interactions with individual objects.
We specify a planning model that reasons about picking and placing individual objects.
Given a state, $\bm{x}$, the planner returns a sequence of pick, place, and move actions that attempt to achieve it.
\textcolor{red}{We are planning on giving brief PDDL descriptions of the actions (pick, place, move, move-free) we use, but are open to suggestions on if that is necessary.}

\subsection{Global Dynamics}

We consider the \emph{constructability} of towers in this work, as show in Figure \ref{fig:constructability}.
This is different from stability in that towers can be stable, but impossible for a single-armed manipulator to construct.

\begin{figure}
    \centering
    \includegraphics[clip, trim={0 0cm 0 0cm}, width=0.8\columnwidth]{figures/constructability.png}
    \caption{The size and placement of the black dot on each block corresponds to the mass and center of mass, respectively. The tower shown on the left is stable but not constructable. After placing the yellow block, it would fall off of the red block preventing the robot from building any further. However, if one were to hold the yellow block in place while placing the blue block, the weight of the blue block would hold the tower stably in place. The tower on the right is both constructable and stable.}
    \label{fig:constructability}
\end{figure}

\subsection{Graph Network Connectivity}
\label{sec:gn-con}

The base model used in our ensemble of models is a Graph Neural Network.
A single graph structure is used to represent a tower, where each node corresponds to a block, and each edge corresponds to a connection between blocks.
We refer to \cite{zhou2018graph} for more details on graph networks.
In our work, the connectivity of the graph corresponds to the true underlying stability model.
When analytically determining the stability of a tower, one iteratively consider each subtower starting with the top block.
If the combined center of mass of a subtower lies within the contact patch of the surface below it, then it is stable.
If all subtowers are stable, then the tower is overall stable.
In our network, each node can be seen as representing the probability that the subtower with the block as the bottom one is stable.
We average the output of each node to get the final prediction of tower stability. The details of the graph network connectivity and output can be seen in Figure \ref{fig:graph_network}.

\begin{figure}
    \centering
    \includegraphics[clip, trim={0 0cm 0 0cm}, width=0.8\columnwidth]{figures/graph_network.png}
    \caption{(Top) The tower under consideration. (Middle) The dotted arrows on the graphs show the edges added to the graph network that correspond to the subtowers on the left. (Bottom) The output of all nodes in the graph network are averaged to get the final prediction.}
    \label{fig:graph_network}
\end{figure}

\subsection{Evaluation Tasks}
\label{sec:tasks}

We evaluate on the following downstream tasks:
\begin{enumerate}
    \item \emph{Tallest Tower:} The objective is to build the tallest possible constructable tower.
    \item \emph{Minimum Contact:} The objective is to build the tower with minimal total overlapping area between each pair of blocks.
    \item \emph{Longest Overhang:} The objective is to build the tower with the maximum distance from the center of geometry of the bottom block to the vertical side of the top block which is furthest from the bottom block.
\end{enumerate}

\subsection{BALD Acquisition with an Ensemble of Models}
\label{sec:bald}

Our objective is to learn the global dynamics $p(\bm{y} | \bm{x} ; \bm{\theta})$  with parameters $\bm{\theta}$ in as few interactions as possible.
Denoting the posterior distribution over our parameters given our observations by $p(\bm{\theta} |D)$, we formalize our ``few interactions'' objective as selecting observations which maximally reduce the uncertainty over $p(\bm{\theta} |D)$, quantified by Shannon entropy $H(\bm{\theta} | D)$. This can also be seen as selecting interactions which reduce the the size of the hypothesis space as quickly as possible.

\begin{equation}
    \underset{D}{\text{argmin}} \  H(\bm{\theta} | D)
\end{equation}

While finding the set of interactions that jointly minimize the entropy of the parameters is difficult, entropy is submodular and monotone, which means that a greedy sequential selection will be within $(1 - \frac{1}{e})$ of optimal \cite{Nemhauser1978submodular}.

\begin{equation}
    \underset{\bm{x}, \bm{y}}{\text{argmax}} \  H(\bm{\theta} | D) - H(\bm{\theta} | \bm{x}, \bm{y}, D)
\end{equation}

While the agent can put the world in an initial state $\bm{x}$, it cannot select the outcome $\bm{y}$. Fortunately, we have a prediction of $\bm{y}$ using our learned dynamics dynamics:

\begin{equation}
    \underset{\bm{x}}{\text{argmax}} \  H(\bm{\theta} | D) - \mathbb{E}_{\bm{y} \sim p(\cdot | \bm{x}, D)}  \left [ H(\bm{\theta} | \bm{x}, \bm{y}, D) \right ]
    \label{eq:theta_entropy_objective}
\end{equation}

Computing entropy is subject to the curse of dimensionality, and the parameter space is often high-dimensional. To address this, Houlsby et. al. \cite{houlsby_bayesian_2011} show that Equation \ref{eq:theta_entropy_objective} is equivalent to

\begin{equation}
    \underset{\bm{x}}{\text{argmax}} \  H(\bm{y} | \bm{x}, D) - \mathbb{E}_{\bm{\theta} \sim p(\cdot |D)}  \left [ H(\bm{y} | \bm{x}, \bm{\theta}) \right ]
    \label{eq:y_entropy_objective}
\end{equation}

 allowing the computation of entropies to take place in the typically lower-dimensional label-space. In addition to saving compute, Equation \ref{eq:y_entropy_objective} invites an appealing interpretation: the left term encourages selecting an $\bm{x}$ that our model is overall uncertain about, $\bm{y}$, and the right term encourages selecting an $\bm{x}$ where parameters sampled from the posterior are confident about different outcomes. In other words, if the various possible models in the posterior distribution over $\bm{\theta}$ are individually confident but about differing outcomes, then observing $\bm{y}$ is likely to prove some of those outcomes incorrect.

In our work, our global dynamics model is represented by an ensemble of $N$ models, each with their own parameters, $\bm{\theta_i}$.
At inference time, we make predictions by averaging over these models

\begin{equation}
    \hat{\bm{y}} = p(\bm{y} | \bm{x}, \bm{\theta}) = \frac{1}{N} \sum_{i=1}^{i=N} \hat{\bm{y}}_i
\end{equation}
\begin{equation}
    \hat{\bm{y}}_i = p(\bm{y}|\bm{x}, \bm{\theta_i})
\end{equation}

When evaluating the BALD objective in Equation \ref{eq:y_entropy_objective} with an ensemble of models, the first term represents the entropy over our ensemble's prediction.

\begin{equation}
    H(\bm{y} | \bm{x}, D) = H(\hat{\bm{y}}|\bm{x}, D, \bm{\theta})
\end{equation}

The second term represents the average entropy of our individual model predictions.

\begin{equation}
    \mathbb{E}_{\bm{\theta} \sim p(\cdot |D)}  \left [ H(\bm{y} | \bm{x}, \bm{\theta}) \right ] = \frac{1}{N} \sum_{i=1}^{i=N} H(\hat{\bm{y}}_i|\bm{x}, \bm{\theta_i})
\end{equation}

\subsection{Feasible Action Acquisition}
\label{sec:acquisition}

Active learning is a viable approach to limiting the amount of labeled data needed to learn a global dynamics model.
Typically active learning involves selecting useful data from a given pool of unlabeled inputs.
In long-horizon manipulation problems, randomly generating a pool of unlabeled data is unlikely to produce useful inputs.
Given the large search space, more work is needed to ensure that the active learner is able to generate a pool of unlabeled data that is useful.
As mentioned, the input to our model is a set of desired object states.
In our work, we leverage the fact that much of this input space is actually inaccessible to the robot.
If we naively performed a random search for sequences of actions, or object placements, we would end up considering sequences in which the robot fails to achieve the desired world state early on in the sequence.
Thus, we limit our search to sequences which differ from successful sequences in the existing labeled dataset by just one action.
Therefore the robot is not considering long sequences which it most likely cannot attempt, but rather just incrementally trying to add a single action to sequences that are feasible.
We also assume that all sequences consisting of just one action will be successful.
The details of our active learning method are given in Algorithm \ref{alg:active}.

\begin{algorithm}
\caption{Active Learning Algorithm}
\begin{algorithmic}[1]
    \Procedure{ActiveLearning}{$model, actions$}
    \State $D_{train} = \{\}$
    \Repeat
        \State $D_{pool} =  \textproc{GeneratePool}(D_{train}, actions)$
        \State $D_{BALD} = \textproc{BALD}(model, D_{pool})$
        \Comment{Eq. \ref{eq:y_entropy_objective}}
        \ForAll{$\bm{x} \in D_{BALD}$}
            \State $\bm{y} = \textproc{PlanAndExecute}(\bm{x})$
            \State $ D_{train} = D_{train} \cup {(\bm{x}, \bm{y})}$
        \EndFor
        \State $model.\textproc{Train}(D_{train})$
    \Until{}
\end{algorithmic}
\begin{algorithmic}[1]
    \Procedure{GeneratePool}{$D_{train}, actions$}
    \State $D_{pool} = \{\}$
    \ForAll{$action \in actions$}
        \State $D_{pool} = D_{pool} \cup \{action\}$
    \EndFor
    \ForAll{$(\bm{x},\bm{y}) \in D_{train}$}
        \ForAll{$action \in actions$}
            \If{$\textproc{Success}(\bm{y})$}
                \State $D_{pool} = D_{pool} \cup \{\bm{x} \cup action\}$
            \EndIf
        \EndFor
    \EndFor
\end{algorithmic}
\label{alg:active}
\end{algorithm}
\subsection{Abstract plan feasibility model}
\label{sec:method-apf-model}

Our {\sc apf}{} model, $\Pr(\phi \mid \mathbf{a}; \Theta)$, aims to capture the uncertainty in the underlying stochastic process of predicting the feasibility of abstract action sequences.
This uncertainty can be attributed to phenomena such as the robot's motor capabilities, errors in perception, or unmodeled behaviors of the planning process, and is referred to as {\em aleatoric uncertainty}.
Our goal is to learn parameters $\Theta$ such that this uncertainty is adequately captured and our model can be leveraged, along with a low level planner, to achieve a goal.

We take a Bayesian approach to learning the model parameters, and maintain a distribution over the parameter space, $\Pr(\Theta)$.
This distribution aims to capture the uncertainty we have regarding the accuracy of our predictions, and is referred to as {\em epistemic uncertainty}.
In general, for complex model classes such as our proposed neural network classifier, an explicit representation of $\Pr(\Theta \mid \mathcal{D})$ for training data $\mathcal{D}$ is difficult to construct or update with new data.
We therefore follow the strategy of \cite{beluch_power_2018} and represent this uncertainty with an ensemble of $N$ models, $\bm{\theta}=(\theta_1, \ldots, \theta_N)$, where ${\theta_i} \in \mathbb{R}^{d}$ and ${\bm\theta} \in \mathbb{R}^{Nd}$.
Initial parameters are drawn independently at random and are updated to incorporate new data via gradient descent.

The design of the models in the ensemble is selected to match the underlying structure of the prediction problem.  Importantly, the length of plans for which we require predictions varies during both the experimentation and execution phases.  For this reason, we use {\em graph neural networks} ({\sc gnn}s), which make predictions based on aggregations of local properties and relations among the input entities, and exploit parameter tying to model global properties of collections of objects of arbitrary size using a fixed-dimensional parameterization $\Theta$.  For a detailed description of {\sc gnn}s, see the overview by \cite{zhou2018graph}.
More details about the specific architecture we use can be found in Section \ref{sec:imp-learning}.

\subsection{Entropy reduction}

Following \cite{mackay1992objective, cohn1996active}, we guide our active learning by picking a sequence of data $\mathcal{D}$ that maximally reduces the entropy of $\Pr(\Theta \mid \mathcal{D})$. The general problem of designing a sequence of experiments to minimize entropy --- or equivalently, maximize information gain --- is a difficult sequential decision-making problem.  Fortunately, due to sub-modularity of the objective, a \emph{myopic} approach that considers only the next experiment to conduct can be shown to be a good approximation to the optimal experimentation strategy \cite{Nemhauser1978submodular}.

Given a model distribution $\Pr(\Theta \mid \mathcal{D})$ that depends on the data we have seen so far, $\mathcal{D}$, we choose the action sequence $\mathbf{a} \in \mathbf{A}$ that reduces the entropy of the posterior distribution as much as possible:
\begin{equation}\label{eq:theta_entropy_objective2}
\mathbf{a}^* = \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\Theta \mid \mathcal{D}) - \mathrm{H}(\Theta \mid \mathcal{D}, \mathbf{a}).
\end{equation}
While the agent can select the plan, $\mathbf{a}$, to experiment with, it cannot select the outcome $\phi$, so to compute this quantity, we have to take an expectation over the outcome, using our current model distribution:
\[\mathrm{H}(\Theta \mid \mathcal{D}, \mathbf{a}) = \expect{\phi \sim \Pr(\cdot \mid \mathcal{D}, \mathbf{a})} \left[ \mathrm{H}(\Theta \mid \mathcal{D}, \mathbf{a}, \phi) \right].\]

Estimating the entropy over a high-dimensional parameter space is expensive, so we follow the approach of~\citet{houlsby_bayesian_2011} to reformulate the objective in (\ref{eq:theta_entropy_objective2}) as
\begin{align}\label{eq:y_entropy_objective2}
\mathbf{a}^* &= \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{I}(\Phi : \Theta \mid \mathcal{D}, \mathbf{a}) \\
&= \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\Phi \mid \mathcal{D}, \mathbf{a}) -
                          \expect{\Theta \sim \Pr(\cdot \mid \mathcal{D})} \left[ \mathrm{H}(\Phi \mid \mathbf{a}; \Theta) \right],
\end{align}
allowing the computation of entropies to take place in the typically lower-dimensional label space, $\Phi$. This is known as the {\em Bayesian Active Learning by Disagreement}, or {\sc bald}{}, objective.

In addition to improved efficiency, the {\sc bald}{} objective invites an appealing interpretation: maximizing the first term encourages selecting an $\mathbf{a}$ that our model is overall uncertain about, and minimizing the second term encourages selecting an $\mathbf{a}$ for which the individual models in $\bm\theta$ can make confident predictions about the outcome $\phi$.  If we think of the overall uncertainty as a combination of \emph{epistemic} and \emph{aleatoric uncertainty}, then this objective seeks an example with high overall uncertainty and low \emph{aleatoric uncertainty}, which therefore has high \emph{epistemic uncertainty}.  In other words, if the various possible models in $\Pr(\Theta \mid \mathcal{D})$ are individually confident but about differing outcomes, then observing the $\phi$ value corresponding to $\mathbf{a}$ is likely to prove some of those outcomes incorrect.

Using an ensemble of equally weighted parameter vectors $\theta_1, \ldots, \theta_N$ to represent $\Pr(\Theta \mid \mathcal{D})$ allows us to compute a global feasibility prediction
\[
\widehat{\Pr}(\Phi = \phi \mid \mathbf{a}; \Theta) = \frac{1}{N} \sum_{i=1}^N \Pr(\Phi = \phi \mid \mathbf{a}; \theta_i)
\]
as well as find the experiment that optimizes the estimated {\sc bald}{} objective in the form \begin{equation}\label{eq:final-criterion}
\mathbf{a}^* = \argmax{\mathbf{a}\in\mathbf{A}} \mathrm{H}(\widehat{\Pr}(\Phi \mid \mathbf{a}; \Theta)) -
                          \frac{1}{N}\sum_{i=1}^N \mathrm{H}(\Pr(\Phi \mid \mathbf{a}; \theta_i)).
                          \end{equation}

\subsection{Sampling Strategies}
\label{sec:exp-design}

Now that we have established an informational score for experiments, we consider several sampling strategies for optimizing over $\mathbf{A}$, the set of plans up to a fixed length $L$.

Maximizing the {\sc bald}{} objective over the entire set $\mathbf{A}$ is difficult because we need to consider all discrete plans up to length $L$, as well as all possible assignments to each continuous abstract action parameter. Additionally, information gain is in general non-convex. One strategy we consider is uniformly sampling complete plans from $\mathbf{A}$ and scoring the samples. We call this the {\it complete}{} strategy.
\begin{equation}
\argmax{\mathbf{a} \in \mathbf{A}}  \text{{\sc bald}{}}(\mathbf{a})
\end{equation}

Unfortunately, to achieve a consistent sampling density, the number of required samples scales exponentially with the length of the plan. Additionally, this strategy might generate most of its samples in the infeasible part of the space.

We observe that the \emph{infeasible sub-sequence property} provides a strong constraint on the set of feasible plans: sequence $(a_1, \ldots, a_n)$ is only feasible if all of its prefixes are also feasible. As such, the model can learn the probability a specific action is feasible instead of the entire plan. If we denote the feasibility of each individual action as $\Phi_l$, then the probability that the plan is feasible is:
\begin{equation}
    \Pr(\Phi_{1:L}|\mathbf{a}, \Theta) = \prod\limits_{l=1}^L \Pr(\Phi_l|a_{1:l}, \Phi_{1:l-1} = \bm1; \Theta),
\end{equation}
where $\Phi_l$ represents whether action $a_l$ is feasible and we use the subscript $1:L$ to refer to a sequence of variables.

Now each plan will return multiple feasibility labels and we can select plans where multiple of these labels will be informative.
Importantly, we need to take into account the probability a specific action will be attempted (i.e., that the plan was successful up until that action).
We call this the sequential{} strategy.

\begin{equation}
\argmax{(a_1, \ldots, a_n) \in \mathbf{A}} \sum_{i=2}^n \widehat{\Pr}(\Phi_{1:i-1} = \bm1 \mid a_{1:i-1}; \Theta) \text{{\sc bald}{}}(a_i)
\end{equation}

We implement the sequential{} approach naively by sampling and scoring entire plans. Like  {\it complete}{}, this method requires exponentially more samples for longer plans, however, in the domain we considered, a sampling approach was acceptable as we had a relatively short plan horizon. In future work we hope to extend this strategy to a search-based method which prunes candidate plans by their feasibility.

We also consider a third strategy which uses the \emph{infeasible sub-sequence property} to bias our sampling towards plans that are much more likely to be feasible, and therefore informative. We only consider sequences $(a_1, \ldots, a_n)$ for which the prefix $(a_1, \ldots, a_{n-1})$ together with result $\phi = 1$ are in the current data set $\mathcal{D}$.  We call this the incremental{} strategy.

\begin{equation}
\argmax{a_n \in \mathbf{A}} \mathbbm{1}_{(a_{1:n-1}, \phi=1) \in \mathcal{D}} \text{{\sc bald}{}}(a_n)
\end{equation}

Although this strategy finds more feasible plans than {\it complete}{}, it also requires that the robot re-use plan prefixes, so we do not gather novel observations when repeating a plan prefix. Constraining our experiments to build on previously feasible plans may be overly restrictive.
One might also consider a {\it greedy}{} approach, in which we select the action $a_n$ which maximizes the {\sc bald}{} objective, given that we have already constructed $a_{1:n-1}$.