text:
\section{Introduction}
Current observational data[1] on neutrino oscillations indicates a clear departure
 from the tri-bimaximal mixings or Harrison-Perkins-Scott (HPS) mixing pattern[2].
The most recent SNO experimental determination[3] of solar angle gives
$\tan^2\theta_{12}=0.45^{+0.09}_{-0.08}$ compared with  $\tan^2\theta_{12}=0.50$ in
HPS scheme. There is no  strong claim for a substantial departure from the maximal
atmospheric mixing
 ($\tan^2\theta_{23}=1$),  and also from the zero reactor angle ($\sin\theta_{13}=0$).
Only upper bound for  $\sin\theta_{13}$ is known at the moment and
future measurements may possibly give  a very small value so small that we can
 approximate it by zero[4]. This does  not yet contradict with the  non-observation of
Dirac CP phase angle. There are discussions[5] on the experimental requirements for mass
 hierarchy measurements for $\theta_{13}=0$.

Conditions of maximal atmospheric mixing $(\theta_{23}=\pi/4)$
 and exact zero of reactor angle $(\theta_{13}=0)$, are in fact
necessary and sufficient conditions[4-9] for the leptonic mixing matrix obtained
from the diagonalization of the left-handed Majorana neutrino mass
 matrix having a 2-3 symmetry. Here the  2-3 symmetry simply implies an invariance
under the simultaneous permutation of the second and third rows as well as
the second and third columns[4]. In the basis where charged lepton mass matrix
is diagonal, a 2-3 symmetry can be generally realised in three degenerate
 models,
and two inverted hierarchical models of neutrino mass patterns[10].
 However, normal hierarchical model
generally does not possess a  2-3 symmetry and hence it does not predict maximal atmospheric
mixing as well as exact zero reactor angle[11]. The degenerate models on the other hand
give either very small ($\tan^2\theta_{12}\approx 0.27$) or maximal solar mixings[10].
 Further constraints such as zero determinant[12,13,4]
 or zero trace[14] of the neutrino mass matrix, which lead to other interesting
properties, are not considered in the present analysis.
This freedom  allows us to consider  larger value of   non-zero mass eigenvalue $m_3$
 within the framework of  inverted
hierarchical model.

A general form of inverted hierarchical  mass matrix $m_{LL}$ having 2-3 symmetry,
 can be written as[4],
 \begin{equation}
m_{LL}=
\left(\begin{array}{ccc}
m_{11} & m_{12} & m_{12} \\
m_{12} & m_{22} & m_{23} \\
m_{12} & m_{23} & m_{22}
\end{array}\right)
\end{equation}
which is  diagonalised by the relation $ m_{LL}=UDU^{\dag}$ where $U$ is given by
\begin{equation}
U=
\left(\begin{array}{ccc}
c_{12} & -s_{12} & 0 \\
\frac{s_{12}}{\sqrt{2}} & \frac{c_{12}}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\
\frac{s_{12}}{\sqrt{2}} & \frac{c_{12}}{\sqrt{2}} & \frac{1}{\sqrt{2}}
\end{array}\right).
\end{equation}
Here we have  $c_{12}=\cos\theta_{12}$ and $s_{12}=\sin\theta_{12}$;
and $\theta_{23}=\pi/4$ and $\theta_{13}=0$.
In the basis where charged lepton mass matrix  is  diagonal, $U$ in eq.(2)
is identified as the MNS mixing
matrix $U_{MNS}$[15] where the solar mixing angle $\theta_{12}$ is arbitrary, atmospheric
mixing angle $\theta_{23}$ is maximal and reactor angle $\theta_{13}$ is exactly zero.
For bimaximal mixings, we choose  $c_{12}=1/\sqrt 2$ and $s_{12}=1/\sqrt 2$, leading to
$\tan^2\theta_{12}=1.0$, whereas for tri-bimaximal mixings[2], we have
$c_{12}=\sqrt {\frac{2}{3}}$ and $s_{12}=1/\sqrt 3$, leading to
$\tan^2\theta_{12}=0.5$.

We are now interested in the present analysis to investigate the condition for
fixing the arbritary  solar mixing angle
to its tri-bimaximal value[2] and also for a possible  gradual departure from this
tri-bimaximal  value, without sacrificing maximal atmospheric mixing  and exact
zero value of reactor angle. We  calculate here  three neutrino mass eigenvalues
 consistent with the present observational  data[1].

 We  confine our analysis in  inverted hierarchical neutrino
mass model having a 2-3 symmetry in eq.(1). We organise the paper as follows.
 In section 2 we present an analytic solution for the inverted hierarchical model
 and find out condition
for lowering the solar mixing angle. This is followed by  a crossing over from
 Type-IHA to Type-IHB inverted hierarchical models.
Numerical results  are presented in  section 3. We conclude in section 4 with a summary and discussions.

\section{Analysis of Inverted hierarchical model}
We have in general two  types[16,10,11] of inverted hierarchical models based on
the relative sign of the first
two mass  eigenvalues $m_1$ and $ m_2$ : Type-IHA for same CP parity $(m_1, m_2, m_3)$ and Type-IHB
 for opposite CP parity  $(m_1, - m_2, m_3)$. Type-IHB is considered to be more  stable under
 radiative corrections in MSSM [17-19],  whereas Type-IHA is found to be more stable under the presence
of left-handed
Higgs triplet term in type-II seesaw mechanism[20]. For our present  analysis we will not
address the issue
of stability of neutrino mass model.  Instead, we explore the properties of these two types
of inverted hierarchical mass matrices and their interconnection.

\subsection{Inverted hierarchy of Type-IHA}
 We start with a specific form[10] of Type-IHA mass matrix having 2-3 symmetry (1) as,
  \begin{equation}
M_{IHA}=
\left(\begin{array}{ccc}
1-2\epsilon & -\epsilon & -\epsilon \\
-\epsilon & \frac{1}{2} & \frac{1}{2}-\eta \\
-\epsilon & \frac{1}{2}-\eta & \frac{1}{2}
\end{array}\right)m_0,
\end{equation}
where the symmetry breaking parameters are $\epsilon,\eta << 1$
and $m_{0}=0.05$eV as imput value[10]. Such left-handed Majorana mass matrix
can be realised in the canonical seesaw formula using a generalised diagonal form of
Dirac mass matrix $m_{LR}$ and non-diagonal form of right-handed Majorana mass matrix $M_{RR}$
 given by[10]
\begin{equation}
m_{LR}=
\left(\begin{array}{ccc}
\lambda^m & 0  & 0 \\
0 & \lambda^n & 0 \\
0 & 0 & 1
\end{array}\right)m_f,
\end{equation}
 and
\begin{equation}
M_{RR}=
\left(\begin{array}{ccc}
(1+2\epsilon)\lambda^{2m} & \epsilon\lambda^{m+n} & \epsilon\lambda^{m} \\
\epsilon\lambda^{m+n} & \frac{1}{2\eta}\lambda^{2n} &(1-\frac{1}{2\eta})\lambda^n \\
\epsilon\lambda^{m} & (1-\frac{1}{2\eta})\lambda^n & \frac{1}{2\eta}
\end{array}\right)v_0,
\end{equation}
where $m_{0}=m_f^2/v_{0}$. The pair of $(m,n)$ can take different sets of values which can represent
 mass matrices belonging to up-quark, down-quark, charged-lepton or any diagonal form of Dirac neutrino.

$M_{IHA}$ in eq.(3) can be   reduced to  the zeroth order texture[16] when  $\epsilon=\eta=0$,
\begin{equation}
M^0_{IHA}=
\left(\begin{array}{ccc}
1 & 0  & 0 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & \frac{1}{2} & \frac{1}{2}
\end{array}\right)m_0,
\end{equation}
This has a degeneracy in the first two  mass eigenvalues, $(1, 1, 0)m_0$, and
such degeneracy makes the solar mixing angle $\theta_{12}$  arbitrary, and may have infinite  values
lying  between $0$ and $\frac{\pi}{4}$.
Once the degeneracy is removed as in eq.(3), the solar angle is then fixed at a particular value.
 Such freedom
in fixing the solar angle does not destroy 2-3 symmetry of the mass matrix, and it
depends absolutely on the  choice of input values of $\eta$ and $\epsilon$,
without disturbing the predictions on  atmospheric angle $\theta_{23}=\frac{\pi}{4}$ and
reactor angle $\theta_{13}=0$. Diagonalizing (3) we obtain  the three  mass eigenvalues,
\begin{equation}
m_1=(2 - 2\epsilon - \eta - y)\frac{m_0}{2},\ \ \
 m_2=(2 - 2\epsilon - \eta + y)\frac{m_0}{2},\ \ \
 m_3= \eta m_0
\end{equation}
where
\begin{equation}
y^2= 12 \epsilon^2 -4 \epsilon \eta + \eta^2.
\end{equation}
The solar mixing is now fixed by the relation[7],
\begin{equation}
\tan 2\theta_{12}= \frac{2\sqrt{2}}{2-\frac{\eta}{\epsilon}}
\end{equation}
As long as $(2-\frac{\eta}{\epsilon})\leq 1$, we have tri-bimaximal (or HPS) mixing  and its
possible deviation to lower values. For tri-bimaximal mixing, we find
 two sulutions of eq.(7), for  $\eta/\epsilon$ at  $1$ and $3$ respectively.
Similarly, for deviation from tri-biimaximal solar mixing to lower values, we have the
 corresponding  values of this
ratios as  $\eta/\epsilon <1$ and  $\eta/\epsilon > 3$. Once the solar angle is fixed, then the range
of $\eta$ or $\epsilon$ can be solved through a search programme. Table-1 represents a
summary of our results.

\subsection{Crossing over from Type-IHA to Type-IHB}
 One particular observation for the  solution of eq.(3) in  the range  $\epsilon > 0.5$, is the crossing
over from inverted hierarchical model  with same CP parity (Type-IHA) to inverted hierarchical model
 with opposite
CP parity (Type-IHB). To demonstrate this interconnection, we start with the most general form
of mass matrix[8] belonging to  Type-IHB,
 \begin{equation}
M_{IHB}=
\left(\begin{array}{ccc}
\delta_1 & 1 & 1 \\
1 & \delta_{2} & \delta_{3} \\
1 & \delta_{3} & \delta_{2}
\end{array}\right) m'_{0}.
\end{equation}
The zeroth order mass matrix of eq.(10) has the form[16]
 \begin{equation}
 M^0_{IHB}=
\left(\begin{array}{ccc}
0  & 1 & 1 \\
1 & 0  & 0  \\
1 & 0  & 0
\end{array}\right)m'_{0},
\end{equation}
which has non-degenerate eigenvalues $(1, -1, 0)m'_{0}$ compared to that of
 eq.(6).
In addition, the solar mixing
is now fixed at  the maximal value ($\theta_{12}=\pi/4$)  unlike eq.(4) where it can have any arbitrary   value.
The diagonalization of (10) leads to the following mass eigenvalues,
\begin{equation}
m_1=(\delta_1 + \delta_2 + \delta_3 + x)\frac{m'_0}{2},\ \ \
m_2=(\delta_1 + \delta_2 + \delta_3 - x)\frac{m'_0}{2},\ \ \
 m_3=(\delta_2 - \delta_3)m'_0
\end{equation}
where
\begin{equation}
x^2=8+(\delta_1^2+\delta_2^2+\delta_3^2)-2\delta_1\delta_2-2\delta_1\delta_3+2\delta_2\delta_3;
\end{equation}
and the  solar mixing,
\begin{equation}
\tan 2\theta_{12}= \frac{2\sqrt{2}}{(\delta_1-\delta_2-\delta_3)}.
\end{equation}
Type-IHB in (10) generally predicts nearly maximal solar mixing and it has been  considered
almost impossible to tone down the solar angle without corrections from charged
lepton mass matrix[21]. Here we wish to show that this notion is not completely true  and
can be avoided through the following transformation,
\begin{equation}
\delta_1=2(1-\frac{1}{2\epsilon}), \ \ \
\delta_2=-\frac{1}{2\epsilon}, \ \ \
\delta_3=(\frac{\eta}{\epsilon}-\frac{1}{2\epsilon}), \ \ \
m'_{0}=m_{0}(-\epsilon)
\end{equation}
where the three parameters $\delta_1, \delta_2,  \delta_3$ are now replaced by only
two parameters $\eta,  \epsilon$.
From eq.(15) it is easy to see that  inverted
hierarchical model (Type-IHB)  in eq.(10) is now equivalent to Type-IHA in eq.(3), and
their expressions for   eigenvalues and
 solar angle  in eqs.(7)-(9) and eqs.(12) - (14) respectively, are also equivalent.
 As emphasised earlier,
such cross-over will take place only when the value of  $\epsilon > 0.5$ and this is shown in Table-1.
\section{Numerical calculations and results}
We follow two important steps for carrying out numerical estimations.
 In the first step, we choose a specific value of solar mixing
$\tan^2\theta_{12}$ via eq.(9) or (14), and then solve for possible values of the ratio $\eta/\epsilon$.
In the second step we take up  a particular value of this ratio $\eta/\epsilon$,
and find out the ranges
of either $\eta$ or $\epsilon$ for the given  ranges of $\bigtriangleup m^2_{21}$ and
$\bigtriangleup m^2_{23}$ which are consistent with observational data[1].

For a demonstration, we present here the   numerical estimations for the value of
solar mixing $\tan^2\theta_{12}=0.45$
which in turn corresponds to two values of $r=\eta/\epsilon$  at $r=0.840498455$ and $r=3.1594955$
derived  from eq.(9). The first value leads to   two ranges of $\eta$ as
(A): $0.00398619\leq \eta\leq 0.00527107$ and (B):$0.586525 \leq\eta\leq 0.58781$,
 whereas second one has only one range
of $\eta$ as (C): $-0.0193327 \leq\eta\leq -0.0147069$. As discussed before, case (B)
belongs to inverted hierarchy
(Type-IHB) and cases (A,C) belong to Type-IHA. However the expressions for eigenvalues and solar
mixing angle are the same. We use standard procedure to estimate neutrino masses and mixings[10,11].

{\bf Case (A): Type-IHA where mass eigenvalues are of the form $(m_1, m_2, m_3)$.}\\
 Using  the best value $\eta=0.00462863$ and $\epsilon=0.0055071$, we have
 \begin{equation}
m_{LL}= M_{IHA}=
\left(\begin{array}{ccc}
0.0494493  & -0.000275351 & -0.000275351 \\
-0.000275351 & 0.025  & 0.0247686  \\
-0.000275351 & 0.0247686  & 0.026
\end{array}\right)
\end{equation}
Diagonalising the above mass matrix we have three  mass eigenvalues,
$$ m_i= (0.0491881, 0.0500298, 000231432)eV, \ \ \ i=1, 2, 3.$$
 leading  to $\Delta m^2_{21}=8.35\times 10^{-5}eV^2$ and $\Delta m^2_{23}=2.5\times 10^{-3}eV^2$.
The MNS mixing matrix is extracted as ,
\begin{equation}
U_{MNS}=
\left(\begin{array}{ccc}
0.830455  & 0.557086 & -2.5\times 10^{-18} \\
0.393919 & -0.58722  & -0.707107  \\
0.393919 & -0.58722  & 0.70717
\end{array}\right)
\end{equation}
 which gives $\tan^2\theta_{12}=0.45$, $\tan^2\theta_{23}=1$ and $\sin\theta_{13}=0$.

{\bf Case (B):Type-IHB where the mass eigenvalues are of the form $(-m_1, m_2, m_3)$.}\\
For the best input value $\eta=0.5871675$ and $\epsilon=0.6985945$ we have
 \begin{equation}
m_{LL}= M_{IHB}=
\left(\begin{array}{ccc}
-0.0198595  & -0.0349297 & -0.0349297 \\
-0.0349297 & 0.025  & -0.00435837  \\
-0.0349297 & -0.00435837  & 0.026
\end{array}\right),
\end{equation}
Diagonalising the above mass matrix we have three  mass eigenvalues,
$$ m_i= (-0.0529967, 0.0537789, 0.0293584)eV, \ \ \ i=1, 2, 3.$$
 leading to $\Delta m^2_{21}=8.35\times 10^{-5}eV^2$ and $\Delta m^2_{23}=2.03\times 10^{-3}eV^2$.
 The model is quite  different from degenerate model where
the overall magnitude of neutrino masses, is of the order of $0.4$eV.
The MNS mixing matrix is extracted as ,
\begin{equation}
U_{MNS}=
\left(\begin{array}{ccc}
-0.830455  & 0.557086 & -4.4\times 10^{-17} \\
-0.393919 & -0.58722  & -0.707107  \\
-0.393919 & -0.58722  & 0.70717
\end{array}\right),
\end{equation}
 which gives $\tan^2\theta_{12}=0.45$, $\tan^2\theta_{23}=1$ and $\sin\theta_{13}=0$.

{\bf Case (C):Type-IHA where the mass eigenvalues are of the form $(m_1, m_2, -m_3)$.}\\
For the best input value  $\eta=-0.0170198$ and $\epsilon=-0.005386865$ we have,
 \begin{equation}
m_{LL}= M_{IHA}=
\left(\begin{array}{ccc}
0.0505387  & 0.000269343 & 0.000269343 \\
0.000269343 & 0.025  & 0.025851  \\
0.000269343 & 0.025851  & 0.025
\end{array}\right)
\end{equation}
Diagonalising the above mass matrix we have three  mass eigenvalues
$$ m_i= (0.0502832, 0.0511065, -0.00085099)eV, \ \ \ i=1, 2, 3.$$
 leading to $\Delta m^2_{21}=8.3\times 10^{-5}eV^2$ and $\Delta m^2_{23}=2.6\times 10^{-3}eV^2$.
The MNS mixing matrix is extracted as ,
\begin{equation}
U_{MNS}=
\left(\begin{array}{ccc}
0.830455  & -0.557086 & -1.5\times 10^{-18} \\
-0.393919 & -0.58722  & -0.707107  \\
-0.393919 & -0.58722  & 0.70717
\end{array}\right)
\end{equation}
 which gives $\tan^2\theta_{12}=0.45$, $\tan^2\theta_{23}=1$ and $\sin\theta_{13}=0$.

We present our calculations in Table-1 for all possible ranges of $\eta$ and $\epsilon$
leading to different values of solar mixing $\tan^2\theta_{12}$ at $0.5$ for tri-bimaximal
mixing,  and then
 $0.45$ and $0.35$ as possible deviations from tri-bimaximal mixing.
The present analysis shows  enormous  provision for  lowering  the solar mixing angle
without sacrificing predictions on  $\tan^2\theta_{23}=1$ and $\sin\theta_{13}=0$. It is interesting
to note   that only two parameters $\eta$ and $\epsilon$ play the key roles in the  whole analysis.
For each value of $\tan^2\theta_{12}$ we have three  solutions  corresponding to two values of  $\eta/\epsilon$,
 and every solution has a particular range of $\eta$. These values  satisfy  observed ranges of
 $\Delta m^2_{21}$ and $\Delta m^2_{23}$.

As a representative example, we present in Fig.1 the graphical solution of the ratio $\eta/\epsilon$ corresponding to
$\tan^2\theta_{12}=0.45$. In Figs. 2-4 we  summarise all the  results of the calculation corresponding to
$\tan^2\theta_{12}=0.45$ case.  In  particular, Fig.2  presents a graphical  summary of the predictions on
$\Delta m^2_{21}$ and   $\Delta m^2_{23}$, and  a corresponding   correlation graph between them for the valid  range
 $0.003986 \leq \eta \leq 0.005271$. Similarly, Figs. 3 and 4 for $0.586525 \leq \eta \leq 0.58781$ and
 $-0.019333 \leq \eta \leq -0.014707$ ranges, respectively.

\section{Summary and discussions}
We summarise the main points in this work. The inverted hierarchical neutrino mass matrix having 2-3 symmetry,
has great potential to give  tri-bimaximal mixings and also possible deviations of solar mixing
angle, without sacrificing predictions on maximal atmospheric mixing angle and zero reactor angle.
We do not take  corrections from charged lepton mass matrix and this helps to maintain 2-3 symmetry of the neutrino mass matrix.
Such  neutrino mass matrices are generated from seesaw formula
using  diagonal form of Dirac mass matrix and non-diagonal form of right
handed Majorana mass matrix. Two types of inverted hierarchical models
 are found
to be crossed over at  a particular range of input parameters.
The present analysis though phenomenological,  may have important
implications in
model buildings[22] on tri-bimaximal mixings
and its possible deviations,  based on various discrete symmetries  as well as
non-Abelian gauge groups, and also on the experimental requirements for mass hierarchy
measurements at zero reactor angle[5].

{\bf Table-1: }
Prediction of the solar mixing angle and its deviation from tri-bimaximal
mixings,  along with the predictions on solar and atmospheric mass-squared differences.

\begin{tabular}{lllll}\\ \hline
$\tan^2\theta_{12}$ & $\eta/\epsilon$ & range of $\eta$ &
      $\bigtriangleup m^2_{21}(10^{-5}eV^2)$ & $\bigtriangleup m^2_{23}(10^{-3}eV^2)$ \\ \hline
$0.5$ & $1.0$  &  $0.004835-0.006395$ & $7.20-9.50$ & $2.50-2.50$ \\
$0.5$ & $1.0$ &  $0.66072-0.66183$      & $9.50-7.20$ & $1.41-1.41$ \\
$0.5$ & $3.0$  &   $-0.01871 - -0.01423$ & $ 9.41-7.20$ & $2.63-2.60$ \\ \hline
$0.45$ & $0.84049$  &  $0.003986-0.005271$ & $7.17-9.50$ & $2.5-2.5$ \\
$0.45$ & $0.84049$ &  $0.586525-0.58781$      & $9.5-7.2$ & $2.03-2.03$ \\
$0.45$ & $3.15949$  &   $-0.019333 - -0.014707$ & $ 9.41-7.20$ & $2.63-2.60$ \\ \hline
$0.35$ & $0.44620$  &  $0.002002-0.0026463$ & $7.20-9.50$ & $2.51-2.51$ \\
$0.35$ & $0.44620$ &  $0.36217-0.362811$      & $9.5-7.2$ & $4.01-4.01$ \\
$0.35$ & $3.55380$  &   $-0.020592 - -0.015666$ & $ 9.41-7.20$ & $2.63-2.60$ \\ \hline
\end{tabular}

\section*{Acknowledgements}
One of the authors(NNS) is thankful to organisers of the IX Workshop on High Energy Physics
Phenomenology (WHEPP-9) held at Institute of physics, Bhubaneswar, India, January 3-14, 2006,
where the present work  was initiated. Useful interactions with Prof.G. Altarelli and  Prof.Ernest Ma
during the workshop are highly acknowledged.


text:
\section{Introduction}
\label{section:introduction}

Automated robotic assembly requires the ability to plan
\emph{pick-and-place} motions\,: pick an object from a given
configuration (position and orientation) and place it in a desired
configuration, possibly with a desired grasp. A grasp refers to a
relative transformation between the gripper and the object. When none
of the possible grasps for picking up the object at its initial
configuration is compatible with subsequent operations, the robot
needs to change its grasp, possibly several times, until the desired
grasp can be attained. Unlike multi-fingered hands, parallel grippers
(which are the most common and robust grippers in the industry) cannot
realize in-hand manipulations. To change a grasp with a parallel
gripper, the robot must \emph{transfer} the object to some
intermediate stable placement, then \emph{transit} to a new
grasp. Those operations are collectively termed
``regrasping''~\cite{TP87icra}.

Since a manipulation planning problem involves both the robot and the
object configurations, searching for a sequence of transit and
transfer paths, so-called a \emph{manipulation path}, has to be done
in the \emph{composite configuration space} $\mc{C}$~\cite{SimX04ijrr},
which is the Cartesian product of the robot configuration space
$\mc[robot]{C}$ and the object configuration space $\mc[object]{C}$. A
transit path, along which the robot moves alone while the object
remains at a stable placement, lies in $\mc{P}$, the subset of
$\mc{C}$ corresponding to stable placements of the object. Similarly, a
transfer path, along which the robot moves while grasping the object
with a valid grasp, lies in $\mc{G}$, the subset of $\mc{C}$
corresponding to valid grasps. The subset $\mathcal{G}\cap\mathcal{P}$ is central in solving
manipulation planning problems since it is the place where transitions
between transit and transfer paths may
occur~\cite{ALS94wafr},~\cite{SimX04ijrr}. Manipulation planners
differ mainly in the way they explore and capture the connectivity of
$\mathcal{G}\cap\mathcal{P}$.

For a parallel gripper grasping a polyhedral object, all the valid
grasps and stable placements can be categorized into a finite number
of classes. A grasp class corresponds to e.g. a pair of object
surfaces the fingers are touching. A placement class corresponds to
e.g. a surface (of the object or of its convex hull) in contact with
the table. Each grasp and placement class may be further parameterized
by a set of continuously varying parameters.

In a pioneering work, Tournassoud \textit{et~al.}~\cite{TP87icra} started by
discretizing $\mathcal{G}\cap\mathcal{P}$\footnote{The notion of composite configuration
  space was not introduced at the time. However, their idea of grasp
  and placement spaces bears a close resemblance to the formulation
  presented in~\cite{SimX04ijrr}.}  and then searched for a feasible
regrasping sequence by backward chaining from the goal grasp. However,
because of the high dimensionality of $\mc{C}$ and the complexity
arising from the discretization, the authors had to constrain each
grasp and placement class to have only single varying parameter. Their
method is therefore limited and much dependent on the particular
choice of the parameters. Nevertheless, they did introduce the
important notion of \emph{Grasp-Placement Table}, which captures part
of the connectivity of $\mathcal{G}\cap\mathcal{P}$. This Grasp-Placement Table can be seen
as an instance of a Manipulation Graph~\cite{ALS94wafr} that is
particularly adapted for polyhedral objects. The Grasp-Placement Table
is a grid where each vertical line represents a placement class while
each horizontal line represents a grasp class. Intersections of
vertical lines with horizontal lines then correspond to subsets of
$\mathcal{G}\cap\mathcal{P}$. A transfer path appears as a connection between intersections
on the same horizontal line, whereas a transit path appears as a
connection between intersections on the same vertical line.

Here we propose a method to construct a \emph{high-level}
Grasp-Placement Table (or graph). In contrast with~\cite{TP87icra},
our graph does not require any discretization or heavy
pre-processing. Moreover, it is specific only to the movable object,
and not to the environment or to the robot\,: it does not therefore
require to be re-computed when the environment changes. At the query
phase, the graph is used as a high-level task planner to guide the
manipulation planner in exploring $\mc{C}$.

Specifically, the edges of the graph are generated by ignoring all the
robot kinematics. Verification of kinematic feasibility along each
edge of the graph is postponed to the planning phase. In doing so, our
method enables handling the full parameterization of $\mathcal{G}\cap\mathcal{P}$. Although
the idea of delaying IK computation has been independently explored in
a recent work~\cite{WanX15icra} to construct a manipulation graph, the
authors' graph still requires discretizing grasp and placement
classes, entailing the same problem of heavy pre-processing.

By constructing and using a high-level Grasp-Placement Table, we
decouple a pick-and-place manipulation planning problem into two
layers of planning. The \emph{high-level} task planning layer consists
in finding a sequence of $\mathcal{G}\cap\mathcal{P}$ configurations that answers the query,
while the \emph{low-level} motion planning layer consists in finding
\emph{actual} motions between the $\mathcal{G}\cap\mathcal{P}$ configurations. Since the
emphasis of this paper is on the high-level planning, {\textit{i.e.}}, how we
construct and use a high-level Grasp-Placement Table to help solve a
manipulation query, addressing uncertainty, which takes place at the
second layer, is beyond the scope of this paper.

Note also that we focus here on industrial assembly, where
parallel-jaw grippers are pervasive owing to their cost-effectiveness
and ease of integration. We first specifically consider the case when
movable objects are either boxes or composed of boxes. These
properties enables an efficient parameterizations of grasps and
placements. We discuss extension to broader types of objects in
Section~\ref{subsection:extension}.

The rest of this paper is organized as follows. In
Section~\ref{section:related_lit}, we briefly review related
literature. In Section~\ref{section:notation}, we present definitions
and conventions that will be used in the
sequel. Section~\ref{section:graph} introduces the high-level
Grasp-Placement Table, its construction, and its use in
planning. Comparisons between the proposed planner and other
manipulation planners are presented in
Section~\ref{section:results}. Finally,
Section~\ref{section:discussion} offers a brief discussion and
sketches future research directions.

\section{Related Literature}
\label{section:related_lit}

\subsection{Manipulation Planning}
Manipulation planners can be seen as a generalization of motion
planners where the robot is allowed to displace specific objects,
called movable objects, in its environment via specific interactions,
e.g., pushing or grasping. Early work considered pick-and-place
manipulation planning as a \emph{regrasping
  problem}~\cite{TP87icra},~\cite{RW97icra},~\cite{StoX99icra}. The
authors discretized $\mathcal{G}\cap\mathcal{P}$ and checked at each discretized point
whether the placement was stable and the grasp was feasible. They then
executed a deterministic search of a regrasping sequence on the set of
feasible placements and grasps. Evaluation of object placements based
on minimum tipping energy was proposed in~\cite{RW97icra}.

A recent work on regrasping algorithms~\cite{WanX15icra} also utilized
a discretization of $\mathcal{G}\cap\mathcal{P}$ to construct a regrasp graph, which
represents connectivity of $\mathcal{G}\cap\mathcal{P}$ connected components, to analyze
workcell utility. The authors improved efficiency of their algorithm
by delaying IK computation in the graph construction until it is
necessary. However, the discretization cost still remains considerable
compared to our method of construction.

Most later work is based on the notion of Manipulation
Graph~\cite{ALS94wafr} and composite configuration
space~\cite{SimX04ijrr}. Initially the planners usually assumed
discrete sets of grasps and
placements~\cite{ALS94wafr},~\cite{KL94icra},~\cite{NK00iros}. Later
work extended the approach to handle continuous
representation~\cite{SimX04ijrr}. The approach has also been extended
to facilitate bimanual manipulation planning~\cite{HarX14icra}. Apart
from permitting only two \emph{modes} of motions, transit and
transfer, there is also work on generalization that permitting finding
solution paths with multiple modes of
motions~\cite{HN11ijrr},~\cite{BarX13er}.

Although a majority of manipulation planners are sampling-based, there
also exist deterministic manipulation
planners~\cite{CCL10icra},~\cite{CCL13ijrr}. These planners construct
a lattice graph representing a discretized configuration space and
then use heuristic searches to find solution paths. However, these
planners are currently capable of planning only single-mode motions
such as reach-to-grasp motions or motions once the robot has already
grasped an object.

\subsection{Object Rearrangement}
Another problem related to manipulation planning is object
rearrangement problem~\cite{StiX07icra},~\cite{KB15rss}. The problem
consists in finding a rearrangement path such that all movable objects
are moved by the robot to their goal poses. Generally the problem can
be decomposed into two subproblems. The first problem is finding a
sequence of object rearrangements and the second one is finding
manipulation paths connecting adjacent rearrangements. Here
pick-and-place planners can serve as local planners to connect nodes
of object rearrangements.

\subsection{Task and Motion Planning}
Planning pick-and-place motions can also be considered in a framework
of task and motion planning~\cite{CAG09ijrr}, \cite{PK14iros},
\cite{SriX14icra}, \cite{GPK15afr}. A planning problem is solved
through two layers of planning\,: high-level task planning and
low-level motion planning. A task planner executes symbolic searches
for high-level actions such as \emph{pick}, \emph{move}, and
\emph{place}, not considering geometries nor kinematics. A motion
planner then computes actual commands to follow the strategy---a
sequence of actions---given by the task planner.

From the perspective of task and motion planning, instead of planning
tasks by a symbolic task planner, we generate task plans by using
information provided by our high-level Grasp-Placement Table. A grasp
search algorithm is used to extract task plans, which will then inform
the manipulation planner about how to make transitions between $\mathcal{G}\cap\mathcal{P}$
connected components. This makes the overall planner less likely to
generate solutions with redundant grasp and ungrasp operations.

\section{Definitions and Convention}
\label{section:notation}

In this section, we present the definitions and conventions involved
in manipulation planning. The terminology introduced here will
facilitate the discussions in the sequel.

\subsection{Mathematical Definitions}
\label{subsection:definitions}
We represent a composite configuration with a couple $(\bm{q},
\bm{T})$, where $\bm{q} \in \mc[robot]{C} \subseteq \mathbf{R}^{n}$ is
a robot configuration, $n$ is the degrees-of-freedom (DOF) of the
robot, and $\bm{T} \in SE(3)$\footnote{$SE(3)$ is the special
  Euclidean group of rigid body transformations.} is a homogeneous
transformation matrix of the object. For a composite configuration in
$\mc{G}$ we define a grasp as a vector of parameters describing the
relative transformation of the gripper and the object. Therefore, a
grasp can generally be described by a vector of $7$ parameters of
quaternion and translation, which can be uniquely identified from
$\bm{q}$ and $\bm{T}$. The number of parameters, however, can be
reduced via grasp parameterization. An example of grasp
parameterization can be found in~\cite{YN10robio}.

A \textbf{single-mode path} is defined as a continuous function $P$
from the unit interval $[0, 1]$ to a level set of $\mc{G}$ or
$\mc{P}$. There are two types of single-mode paths\,: transit and
transfer. A \textbf{transit path} maps the unit interval into a level
set of $\mc{P}$, {\textit{i.e.}}, for any two configurations $(\bm{q}_{1},
\bm{T}_{1})$ and $(\bm{q}_{2}, \bm{T}_{2})$ on the path, $\bm{T}_{1} =
\bm{T}_{2}$. A \textbf{transfer path} maps the unit interval into a
level set of $\mc{G}$, {\textit{i.e.}}, a grasp remains constant along the path.

Next, we define a binary operation called \textbf{composition}
operation. First of all, the composition of two single-mode paths
$P_{1}$ and $P_{2}$ is defined as
\begin{equation*}
  (P_{1} \ast P_{2})(s) = \left\{
    \begin{matrix}
      P_{1}(2s/t) & 0 \leq s \leq t/2,\\
      P_{2}(2s/t - 1) & t/2 \leq s \leq t,
    \end{matrix}
  \right.
\end{equation*}
where $t = 1$ if both paths are of the same type and $t = 2$
otherwise. Note that the composition operation is only defined when
$P_{1}(1) = P_{2}(0)$. From the above definition, when $P_{1}$ and
$P_{2}$ have the same type, $M = P_{1} \ast P_{2}$ is also a
single-mode path. We use $|M|$ to denote the \textbf{parameterization
  domain length} or \textbf{domain length} of $M$. Note that all
single-mode paths have unit domain length.

Let $\prod_{i = a}^{b}P_{i} = P_{a} \ast P_{a + 1} \ast \ldots \ast
P_{b}$, where $b \geq a$. We can define the composition of $k$
single-mode paths as
\begin{equation*}
  \left( \prod_{i = 1}^{k} P_{i} \right)(s)
  = \left\{
    \begin{matrix}
      (P_{1} \ast P_{2})(s) & 0 \leq s \leq t_{2}\\
      M_{2}(s - t_{2}) & t_{2} \leq s \leq |M_{2}| + t_{2}
    \end{matrix}
  \right.
\end{equation*}
\begin{equation*}
  = \left\{
    \begin{matrix}
      M_{1}(s) & 0 \leq s \leq |M_{1}|\\
      (P_{k - 1} \ast P_{k})(s - |M_{1}|) & |M_{1}| \leq s \leq
      |M_{1}| + t_{1},
    \end{matrix}
  \right.
\end{equation*}
where $M_{1} = \prod_{i = 1}^{k - 2}P_{i}$, $M_{2} = \prod_{i =
  3}^{k}P_{i}$, and $t_{1}$ and $t_{2}$ are one if both single-mode
paths are of the same type and two otherwise. Notice that the
composition operation is associative but not commutative.

According to the above definition of the composition operation, we can
now define a \textbf{manipulation path} as a composition of
single-mode paths. A manipulation path is \textbf{irreducible} if no
two consecutive single-mode paths are of the same type, {\textit{i.e.}}, it is an
alternating composition of transit and transfer paths. Any composition
$\prod_{i = 1}^{k}P_{i}$ can always be written it as an irreducible
manipulation path $\prod_{i = 1}^{l}P_{i}'$ with $l \leq k$. For an
irreducible manipulation path $M$, we have that the number of
\textbf{transitions} (between transit and transfer paths or vice
versa) is $|M| - 1$.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node at (0, 0) {\includegraphics[width = 0.1\textwidth] {gripper}};
    \node [scale=0.8] at ( 1.4, 0.4) {lateral};
    \node [scale=0.8] at (-1.4, 0.4) {sliding};
    \node [scale=0.8] at ( 0, 1.2) {approaching};
  \end{tikzpicture}
  \caption{The parallel gripper used in this paper with its local
    frame. The lateral direction is orthogonal to both finger
    surfaces. The sliding direction is parallel to both finger
    surfaces and is defined such that the approaching direction is
    pointing out of the gripper.}
  \label{figure:gripper}
\end{figure}

\subsection{Placement Classes and Grasp Classes}
The sets $\mc{P}$ and $\mc{G}$ can be partitioned into finite disjoint
classes called placement classes and grasp classes, respectively. A
class groups together composite configurations with similar
properties. Each placement class indicates how an object is placed on
a table, and thus normally refers to a surface of the object's convex
hull being in contact with the table. Similarly, each grasp class
indicates how the object is grasped by the gripper. In our case, with
an assignment of the gripper's local frame as shown in
Fig.~\ref{figure:gripper}, each grasp class refers to the relative
direction of the gripper's approaching direction with respect to the
object.

Consider a gripper grasping a box. We say that the approaching
direction is $+x$ if the positive direction of the gripper's
approaching axis is aligned with $+x$-direction of the box's local
frame. Therefore, there are $6$ possible directions along which the
gripper can approach the box\footnote{This means the approaching axis
  of the gripper must be perpendicular to a surface of the box. A
  configuration that the approaching direction is not perpendicular to
  any surface can then be achieve by rotating the gripper about the
  sliding axis.}. For convenience, we will use integers $1$ to $6$ to
denote approaching directions $+x, +y, +z, -x, -y, -z$,
respectively. Now consider the case when the object is composed of $m$
boxes. Suppose we index those boxes with integers from $1$ to
$m$. There will be in total $6m$ possible grasp classes. When the
gripper is approaching the object in the direction $i$ of the box $j$,
the grasp class index is $i + 6(j - 1)$. For example, in the grasp
class $7$, the gripper is grasping box $2$ and the approaching axis is
aligned with $+x$-axis of the box.

\section{Manipulation Planning Using High-Level Grasp-Placement Table}
\label{section:graph}

\subsection{High-Level Grasp-Placement Table}

\subsubsection{Overview}
\label{subsubsection:graph_overview}
A high-level Grasp-Placement Table (or graph) is an undirected,
unweighted graph whose nodes represent different subsets of
$\mathcal{G}\cap\mathcal{P}$. According to the partitioning of $\mc{G}$ and $\mc{P}$, the set
$\mathcal{G}\cap\mathcal{P}$ is then partitioned into finite disjoint subsets. Each subset of
$\mathcal{G}\cap\mathcal{P}$ is the intersection between a particular pair of placement and
grasp classes. Therefore, a node in the graph can be represented by a
pair of integers, a placement class index and a grasp class index. We
visualize a high-level Grasp-Placement Table in the similar way as the
authors of~\cite{TP87icra} did for their Grasp-Placement Table. Our
Table is plotted on a two-dimensional grid. Each vertical line
corresponds to a placement class whereas each horizontal line
corresponds to a grasp class. Intersections of vertical with
horizontal lines then represent subsets of $\mathcal{G}\cap\mathcal{P}$.

If there were no collision avoidance constraints and kinematic
reachability constraints, any combination of an object contact surface
and a gripper's approaching direction would have been possible. Any
pair of nodes on the same vertical or horizontal line will be
connected. Imposing those constraints makes some nodes and edges
infeasible. However, verifying all constraints at the graph
construction phase entails costly computations. Also, by checking
kinematic reachability, the graph will become robot- and
environment-dependent\,: it will need to be re-computed when the
environment changes. Therefore, we propose to construct the graph by
verifying only collision avoidance constraints (between the gripper
and the table). Robot kinematic reachability constraint verification
(IK computation) is postponed until the planning phase.

\subsubsection{Graph Construction}
\label{subsubsection:graph_construction}
In the first step, we check for feasibility of graph nodes. For each
placement class, we place the object at a nominal location on the
table. Then for each box composing the object, we check whether the
gripper can approach the box from any of the $6$ directions, {\textit{i.e.}},
$+x$-, $+y$-, $+z$-, $-x$-, $-y$-, and $-z$-directions, of the box's
local frame, without colliding with the table. If there is no
collision, we add a node that represents the respective placement and
grasp classes into the graph. We continue this procedure for all
placement classes. Since we do not consider the robot kinematics here,
the actual location of the object on the table, {\textit{i.e.}}, how far the
object is from the robot, does not affect the resulting graph.

After we obtain all feasible nodes in the first step, we display them
on a grid. Then we connect every pair of nodes on the same vertical or
horizontal line. These edges represent \emph{potential} connections
between nodes. An edge connecting a pair of nodes on the same vertical
line represents \emph{transit} paths while an edge connecting a pair
of nodes on the same horizontal line represents \emph{transfer}
paths. Every node also has two self-loops. One loop corresponds to a
transit path; the other loop corresponds to a transfer
path. Fig.~\ref{figure:graph_box} shows an example of a high-level
Grasp-Placement Table for a box of dimension $28.0$ cm. $\times$ $4.9$
cm. $\times$ $2.5$ cm. For simplicity, we do not show self-loops in
the plot.

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=0.5]
    \def\np{6
    \def\ng{6
    \def0.2{0.3}

    \draw[ystep = 0.2 cm, gray, ultra thin](0, 0) grid
    (\np + 0.8, \ng*0.2 + 0.8*0.2);

    \draw[->] (-0.5, 0) -- (\np + 1, 0);
    \draw[->] (0, -0.5) -- (0, \ng*0.2 + 0.2);

    \node [align=left, right, scale=0.8] at (\np + 1, 0) {placement\\
      class};

    \foreach \x in {1, ..., \np}{
      \draw (\x, -0.1) -- (\x, 0.1);
      \node [below, scale=0.8] at (\x, 0) {$\x$};
    }

    \node [align=left, above, scale=0.8] at (0, \ng*0.2 + 0.2)
    {grasp class};

    \foreach \y in {2, 4, ..., \ng}{
      \draw (-0.1, \y*0.2) -- (0.1, \y*0.2);
      \node [left, scale=0.8] at (0, \y*0.2) {$\y$};
    }

    \draw[very thick, teal] (1, 1*0.2) -- (1, 6*0.2);
    \draw[very thick, teal] (4, 2*0.2) -- (4, 6*0.2);

    \draw[very thick, teal] (1, 2*0.2) -- (4, 2*0.2);
    \draw[very thick, teal] (1, 3*0.2) -- (4, 3*0.2);
    \draw[very thick, teal] (1, 5*0.2) -- (5, 5*0.2);
    \draw[very thick, teal] (1, 6*0.2) -- (6, 6*0.2);

    \foreach \x/\y in
    { 1/1, 1/2, 1/3, 1/5, 1/6,
      2/2,
      3/3,
      4/2, 4/3, 4/4, 4/5, 4/6,
      5/5,
      6/6 }{
      \filldraw (\x, \y*0.2) circle [radius=0.08cm, fill=black];
    }

    \draw [decorate, decoration={brace, amplitude=3pt}, xshift=-4pt,
    yshift=0pt] (-1, 0.7*0.2 + 6*0.2 - 6*0.2) --
      (-1, 0.3*0.2 + 6*0.2)
    node [black, midway, xshift=-0.8cm] {\footnotesize box $1$};

  \end{tikzpicture}
  \caption{An example of a high-level Grasp-Placement Table for a box
    of dimension $28.0$ cm. $\times$ $4.9$ cm. $\times$ $2.5$ cm. For
    clarity, self-loops are not depicted. Note that every node on the
    same line is connected to all other nodes although we do not draw
    separate lines for them. For example, node $(1, 6)$ is
    reachable from $(6, 1)$ in one step.}
  \label{figure:graph_box}
\end{figure}

The construction can be generalized to handle start and goal
configurations in $\mc{G}$ and/or $\mc{P}$ by adding special nodes
into the graph. To handle configurations in $\mc{P}$, we can add a
grasp class index $0$ to the graph. For example, in the above example
of the box, we will obtain $6$ new nodes, $(1, 0), (2, 0), \ldots, (6,
0)$. These nodes are connected to all other nodes with the same
placement class. Note, however, that there are no horizontal edges
between them since it is not possible to travel directly from one
placement class to another in $\mc{P}$. To handle configurations in
$\mc{G}$, we can add a placement class index $0$, similarly to the
previous case.

\subsubsection{Guiding a Manipulation Planner via Task Plans}
\label{subsubsection:extractingplans}
One of quality measures of manipulation paths is the number of
transitions (as defined in
Section~\ref{subsection:definitions}). Fewer transitions means fewer
grasp/ungrasp operations and fewer single-mode paths. This may
therefore lead to a shorter overall execution time.

From the constructed graph we can extract \emph{task plans} of a
specific length\footnote{A task plan of length $k$ has $k - 1$
  transitions} which serve as a guide for the planner about how to
travel between different subsets of $\mathcal{G}\cap\mathcal{P}$. The planner, instead of
exploring randomly how to go from one subset of $\mathcal{G}\cap\mathcal{P}$ to another, will
follow those plans to search for a manipulation path of a specific
number of transitions. Here a \textbf{task plan} is a sequence of
graph nodes connected by graph edges. For example, from
Fig.~\ref{figure:graph_box} a task plan of length $3$ to travel from
$(6, 6)$ to $(2, 2)$ is given by $(6, 6) \rightarrow (4, 6)
\rightarrow (4, 2) \rightarrow (2, 2)$.

The task plans extracted from the graph only provide high-level
information on how to pick and place the object. Exact parameter
values for each grasp and placement classes will be assigned by the
planner, {\textit{i.e.}}, via random sampling, in the planning phase (see
Section~\ref{subsection:algorithm}).

\subsection{Manipulation Planning Algorithm}

\subsubsection{Algorithm Details}
\label{subsection:algorithm}
Our pick-and-place manipulation planner proceeds in two phases\,:
pre-processing phase and planning phase. In the pre-processing phase,
it constructs a high-level Grasp-Placement Table based on the models
of the object and of the gripper (the latter is needed for collision
checking). Note that neither the kinematic model of the robot nor the
environment is needed at this phase. Then this high-level
Grasp-Placement Table is used in the planning phase to guide a
bidirectional tree-based planner, similar to~\cite{LK00citeseer}, to
search for a manipulation path. The main algorithm is listed in
Algorithm~\ref{algo:main}.

\begin{algorithm}[h]
\caption{Main algorithm}
\label{algo:main}
\Indm
{\renewcommand{\nl}{\let\nl\oldnl}{\func{Main}($\mc{R}, \mc{M}, \q{start}, \T{start}, \q{goal},
    \T{goal}, t_{\textrm{max}}$):}}\;
\Indp
$G \leftarrow$ \func{Preprocess}($\mc{R}, \mc{M}$)\;
$v_{\textrm{start}} \leftarrow$ \func{Vertex}($\q{start}, \T{start}$)\;
$v_{\textrm{goal}} \leftarrow$ \func{Vertex}($\q{goal}, \T{goal}$)\;
$l \leftarrow$
\func{FindShortestPathLength}($G, v_{\textrm{start}}, v_{\textrm{goal}}$)\;
\label{line:findshortestlength}
$t \leftarrow 0, k \leftarrow l$,
found $\leftarrow$ \kw{False}\;
$\Delta \leftarrow$ \func{ChoosePathLengthIncrement}$(v_{\textrm{start}}, v_{\textrm{goal}})$\;
\While{\upshape ($t < t_{\textrm{max}}$) \kw{and} (\kw{not} found)}{
  $t_{\textrm{s}} \leftarrow$ \func{GetTime}()\;
  $\Pi \leftarrow$ \func{FindPlansOfGivenLength}($k, v_{\textrm{start}},v_{\textrm{goal}}$)\;
  \label{line:findplansofgivenlength}
  $Q \leftarrow$ \func{CreateDirectedGraph}($\Pi$)\;
  \{found, $\pi$\} $\leftarrow$ \func{PlanPath}($Q, \mc{R}, \mc{M}, v_{\textrm{start}},
  v_{\textrm{goal}}, t_{\textrm{max}} - t$)\;
  $t_{\textrm{e}} \leftarrow$ \func{GetTime}()\;
  $t \leftarrow t + (t_{\textrm{e}} - t_{\textrm{s}})$\;
  \If{\upshape found}{
    \KwRet{$\pi$}
  }
  $k \leftarrow k + \Delta$\;
}
\KwRet{\upshape \kw{None}}\;
\end{algorithm}

The main algorithm takes as its input a robot model $\mc{R}$; an
object model $\mc{M}$; start and goal robot configurations $\q{start}$
and $\q{goal}$; start and goal object transformations $\T{start}$ and
$\T{goal}$; and a maximum running time for the planner
$t_{\textrm{max}}$. Details of functions in Algorithm~\ref{algo:main}
are listed below\,:

\begin{itemize}[leftmargin=*]

\item \func{Preprocess} gathers geometric information of the gripper
  and the object to construct a high-level Grasp-Placement Table $G$,
  as described in Section~\ref{subsubsection:graph_construction}.

\item \func{Vertex} initializes a new tree vertex to store information
  of a composite configuration. Note that this function also examines
  $G$ to find the graph node to which the input composite
  configuration belongs.

\item \func{FindShortestPathLength} finds the length $l$ of the
  shortest task plan(s) to go from the graph node $c_{\textrm{start}}$ to the
  graph node $c_{\textrm{goal}}$. Here $l - 1$ serves as the lower bound of
  the number of transitions of manipulation paths connecting
  $(\q{start}, \T{start})$ and $(\q{goal}, \T{goal})$.

\item \func{ChoosePathLengthIncrement} chooses the suitable value of
  $\Delta$ for the query. If either $(\q{start}, \T{start})$ or
  $(\q{goal}, \T{goal})$ is in $\mathcal{G}\cap\mathcal{P}$, $\Delta$ can be $1$. Otherwise,
  $\Delta$ has to be $2$ in order to keep the resulting manipulation
  path irreducible.

\item \func{CreateDirectedGraph} creates a directed graph $Q$ from
  task plans in $\Pi$. A node of $Q$ is encoded as a couple $(d_{i},
  c_{i})$, where $c_{i}$ is the corresponding node of $G$ and $d_{i}$
  indicates the number of steps $c_{i}$ is away from
  $c_{\textrm{start}}$\footnote{We need to encode the level $d_{i}$ of $c_{i}$
    into each node of $Q$ since the node $c_{i}$ may appear at
    different steps in different task plans. This helps the planner
    not to get lost when many task plans contain the same node
    $c_{i}$.}.

\item \func{PlanPath}, which acts as a motion planner, searches for a
  manipulation path according to information provided by
  $Q$. \func{PlanPath} is listed in Algorithm~\ref{algo:planpath}.
\end{itemize}

\vspace{-5pt}
\begin{algorithm}[h]
\caption{Planning phase}
\label{algo:planpath}
\Indm
{\renewcommand{\nl}{\let\nl\oldnl}{\func{PlanPath}($Q, \mc{R}, \mc{M}, v_{\textrm{start}}, v_{\textrm{goal}},
    t_{\textrm{max}}$):}}\;
\Indp
$\mc[FW]{T} \leftarrow$ \func{Tree}($v_{\textrm{start}}$),
$\mc[BW]{T} \leftarrow$ \func{Tree}($v_{\textrm{goal}}$)\;
$\mc[a]{T} \leftarrow \mc[FW]{T}$,
$\mc[b]{T} \leftarrow \mc[BW]{T}$\; $t \leftarrow 0$\;
\While{\upshape $t < t_{\textrm{max}}$ \kw{or} $Q$.haspath}{
  $t_{\textrm{s}} \leftarrow$ \func{GetTime}()\;
  $v \leftarrow$ \func{SampleTree}($\mc[a]{T}$)\;
  $Q \leftarrow$ \func{RemoveInfeasibleEdges}($Q$)\;
  result $\leftarrow$ \func{ExtendFrom}($v, Q$)\;
  \If{\upshape result == \kw{REACHED}}{
    $\pi \leftarrow$ \func{ExtractPath}($\mc[FW]{T}, \mc[BW]{T}$)\;
    \KwRet{\upshape\{\kw{True}, $\pi$\}}
  }
  $t_{\textrm{e}} \leftarrow$ \func{GetTime}()\;
  $t \leftarrow t + (t_{\textrm{e}} - t_{\textrm{s}})$\;
  \func{Swap}($\mc[a]{T}, \mc[b]{T}$)\;
}
\KwRet{\upshape\{\kw{False}, \kw{None}\}}
\end{algorithm}
\vspace{-5pt}

\begin{itemize}[leftmargin=*]
\item \func{ExtendFrom} first randomly samples a new composite
  configuration in the grasp and placement classes suggested by
  $Q$. Then it will attempt to connect the composite configuration
  contained in $v$ with the newly sampled one. The function returns
  \kw{True} if the attempt is successful.

\item \func{RemoveInfeasibleEdges} removes edges in $Q$ which lead to
  more than $N$ failed attempts by \func{ExtendFrom}, where $N$ is a
  threshold value set by the user.
\end{itemize}

\subsubsection{Example}
\label{subsubsection:example}
Consider the task of moving the box, whose high-level Grasp-Placement
Table is shown in Fig.~\ref{figure:graph_box}, from the placement and
grasp $c_{\textrm{start}} = (6, 6)$ to $c_{\textrm{goal}} = (2, 2)$. In the first
planning loop in Algorithm~\ref{algo:main}, the algorithm will try to
find a manipulation path of length $k = 3$. The set $\Pi$ will store
two task plans\,: $(6, 6) \rightarrow (4, 6) \rightarrow (4, 2)
\rightarrow (2, 2)$ and $(6, 6) \rightarrow (1, 6) \rightarrow (1, 2)
\rightarrow (2, 2)$. The directed graph $Q$, constructed from $\Pi$,
will serve as a guidance for the planner as follows.

In each while loop in Algorithm~\ref{algo:planpath}, the planner will
randomly pick an existing vertex $v_{\tr{sample}}$ on a tree. Suppose
$v_{\tr{sample}}$ contains a composite configuration in placement and
grasp classes $(4, 6)$. From $Q$, the planner then knows that the next
extension should be attempted towards a composite configuration in the
placement and grasp classes $(4, 2)$. \func{ExtendFrom} will then
sample a composite configuration in that subset of $\mathcal{G}\cap\mathcal{P}$ and call a
local planner, e.g., a bidirectional RRT planner~\cite{LK00citeseer},
to attempt the connection.

\subsection{Remarks}
\begin{remark}
  The high-level Grasp-Placement Table $G$, and hence $Q$, is
  constructed without considering kinematic constraints. Failed
  attempts by \func{ExtendFrom} are likely due to kinematic
  infeasibility. Therefore, we need to set a threshold $N$ to prevent
  the planner from repetitively attempting infeasible connections.

  This threshold also affects the running time of our planner. If we
  set $N$ too low, feasible edges of $Q$ can also be removed due to
  false negative reports of kinematic infeasibility. This will lead to
  obtaining solutions with redundant transitions. On the other hand,
  if the threshold is set too high, it will take longer time for the
  planner to declare an infeasible edge and hence longer overall
  running time.
\end{remark}

\begin{remark}
  We can tailor the sampling of vertices from a tree, done in
  \func{SampleTree}, by putting different sampling weight on different
  vertices. For example, we can use weights proportional to the level
  of $c_{\tr{sample}}$ in $Q$, {\textit{i.e.}}, $d_{\tr{sample}}$. In this way,
  vertices farther away from the root will be more likely to be
  selected.
\end{remark}

\begin{remark}
  Our planner tends to work better in a less constrained
  environment. In a very constrained environment\footnote{This may be
    seen as a narrow passage in $\mc{C}$. An example of such cases is
    the problem considered in~\cite{SimX04ijrr} where the robot needs
    to pull a bar out of a tight cage mounted on the floor.} in which
  the robot needs to grasp and ungrasp the object a number of times
  before it can move the object to the final transformation, our
  planner will spend a considerable amount of time verifying
  infeasible edges. However, in actual industrial settings, although
  the environment might be cluttered, it is usually not tightly
  constrained.
\end{remark}

\section{Results and Comparisons with Other Manipulation Planners}
\label{section:results}

In this section, we present details of comparisons between our planner
and two other planners\,: Primitive Manipulation Planner
(Section~\ref{subsubsection:pmp}) and Discretization-Based
Manipulation Planner (Section~\ref{subsubsection:dbmp}). We
implemented all planners in Python and used OpenRAVE~\cite{Dia10these}
as a simulation environment. The local planner employed in all
manipulation planners was the OpenRAVE built-in bidirectional RRT. The
robot was a $6$-DOF industrial manipulator Denso VS-$060$ equipped
with a $2$-finger Robotiq gripper $85$. All simulations were run on a
$3.2$ GHz Intel\textsuperscript{\circledR} Core\texttrademark desktop
with $3.8$ GB RAM.

\subsection{Task Details}
The planners had to plan pick-and-place motions for three objects\,: a
box, an L-shaped object, and a small chair. The robot was to move from
\kw{Home}, {\textit{i.e.}}, $\bm{q} = \bm{0}$, pick up the object at a given
object transformation, place it at another given transformation, and
finally return to \kw{Home}. Snapshots of all three settings are shown
in Fig.~\ref{figure:scenes}. The Grasp-Placement Tables of the
L-shaped object and the chair are shown in Fig.~\ref{figure:graph_L}
and Fig.~\ref{figure:graph_chair}, respectively. (The Grasp-Placement
Table of the box is similar to the one in
Fig.~\ref{figure:graph_box}.)  These tasks are useful especially for
assembly operations, such as furniture assembly where the robot needs
to grasp a furniture part at some placement and move it to some
desired transformation to attach the part to other parts. We set chose
start and goal object transformations such that the robot needed to
perform regrasp operations at least once in order to complete the
tasks.

\begin{figure}
  \centering
  \subfloat[]{\includegraphics[width=0.13\textwidth]{scene_exp1}}
  \hspace{10pt}
  \subfloat[]{\includegraphics[width=0.13\textwidth]{scene_exp2}}
  \hspace{10pt}
  \subfloat[]{\includegraphics[width=0.13\textwidth]{scene_exp3}}
  \caption{Scenes used in our experiments. There are two identical
    (movable) objects shown in each figure. The objects on the left
    are at the initial transformations. The objects on the right are at
    the final transformations.}
  \label{figure:scenes}
\end{figure}

\captionsetup[subfigure]{position=b}
\begin{figure}
  \centering
  \subfloat[The high-level Grasp-Placement Table for an L-shaped object]{
    \begin{tikzpicture}[scale=0.7]
      \def\np{5
      \def\ng{12
      \def0.2{0.2}

      \draw[ystep = 0.2 cm, gray, ultra thin](0, 0) grid
      (\np + 0.8, \ng*0.2 + 0.8*0.2);

      \draw[->] (-0.5, 0) -- (\np + 1, 0);
      \draw[->] (0, -0.5) -- (0, \ng*0.2 + 0.2);

      \node [align=left, right, scale=0.8] at (\np + 1, 0) {placement\\
        class};

      \foreach \x in {1, ..., \np}{
        \draw (\x, -0.1) -- (\x, 0.1);
        \node [below, scale=0.8] at (\x, 0) {$\x$};
      }

      \node [align=left, above, scale=0.8] at (0, \ng*0.2 + 0.2)
      {grasp class};

      \foreach \y in {3, 6, ..., \ng}{
        \draw (-0.1, \y*0.2) -- (0.1, \y*0.2);
        \node [left, scale=0.8] at (0, \y*0.2) {$\y$};
      }

      \draw[very thick, teal] (1, 3*0.2) -- (1, 9*0.2);
      \draw[very thick, teal] (2, 1*0.2) -- (2, 7*0.2);
      \draw[very thick, teal] (3, 2*0.2) -- (3, 12*0.2);
      \draw[very thick, teal] (4, 5*0.2) -- (4, 12*0.2);
      \draw[very thick, teal] (5, 6*0.2) -- (5, 12*0.2);

      \draw[very thick, teal] (2, 2*0.2) -- (3, 2*0.2);
      \draw[very thick, teal] (1, 3*0.2) -- (3, 3*0.2);
      \draw[very thick, teal] (2, 5*0.2) -- (4, 5*0.2);
      \draw[very thick, teal] (2, 6*0.2) -- (5, 6*0.2);
      \draw[very thick, teal] (2, 7*0.2) -- (4, 7*0.2);
      \draw[very thick, teal] (1, 9*0.2) -- (4, 9*0.2);
      \draw[very thick, teal] (3, 10*0.2) -- (4, 10*0.2);
      \draw[very thick, teal] (3, 12*0.2) -- (5, 12*0.2);

      \foreach \x/\y in
      { 1/3, 1/9,
        2/1, 2/2, 2/3, 2/5, 2/6, 2/7,
        3/2, 3/3, 3/4, 3/6, 3/8, 3/9, 3/10, 3/12,
        4/5, 4/7, 4/9, 4/10, 4/11, 4/12,
        5/6, 5/12
      }{
        \filldraw (\x, \y*0.2) circle [radius=0.06cm, fill=black];
      }

      \foreach \k in {1, 2}{
        \draw [decorate, decoration={brace, amplitude=3pt}, xshift=-4pt,
        yshift=0pt] (-1, 0.7*0.2 + 6*\k*0.2 - 6*0.2) --
        (-1, 0.3*0.2 + 6*\k*0.2)
        node [black, midway, xshift=-0.8cm] {\footnotesize box $\k$};
      }
    \end{tikzpicture}
    \label{figure:graph_L}
  }

  \subfloat[The high-level Grasp-Placement Table for a small chair]{
    \begin{tikzpicture}[scale=0.7]
      \def\np{6
      \def\ng{48
      \def0.2{0.2}

      \draw[ystep = 0.2 cm, gray, ultra thin](0, 0) grid
      (\np + 0.8, \ng*0.2 + 0.8*0.2);

      \draw[->] (-0.5, 0) -- (\np + 1, 0);
      \draw[->] (0, -0.5) -- (0, \ng*0.2 + 0.2);

      \node [align=left, right, scale=0.8] at (\np + 1, 0) {placement\\
        class};

      \foreach \x in {1, ..., \np}{
        \draw (\x, -0.1) -- (\x, 0.1);
        \node [below, scale=0.8] at (\x, 0) {$\x$};
      }

      \node [align=left, above, scale=0.8] at (0, \ng*0.2 + 0.2)
      {grasp class};

      \foreach \y in {6, 12, ..., \ng}{
        \draw (-0.1, \y*0.2) -- (0.1, \y*0.2);
        \node [left, scale=0.8] at (0, \y*0.2) {$\y$};
      }

      \foreach \x/\y/\z in {
        1/1/48, 2/2/40, 3/1/48, 4/1/48, 5/1/48, 6/1/38
      }{
        \draw[very thick, teal] (\x, \y*0.2) -- (\x, \z*0.2);
      }

      \foreach \x/\y/\z in {
        1/1/6, 2/1/6, 4/1/5, 5/2/6,
        9/2/6, 10/2/5, 11/2/6,
        13/3/6, 15/3/6, 17/3/6,
        19/1/6, 20/1/6, 21/1/6,
        26/1/6, 27/1/6, 28/1/4,
        31/3/6, 34/2/5, 35/3/6, 36/3/5,
        37/1/6, 38/1/6, 40/1/4, 42/1/4,
        44/1/4, 47/3/5, 48/1/5
      }{
        \draw[very thick, teal] (\y, \x*0.2) -- (\z, \x*0.2);
      }

      \def0.06{0.06}

      \foreach \y in {
        1, 2, 4, 19, 20, 21, 25, 26, 27, 28, 37, 38, 40, 42, 44, 48
      }
      {\filldraw (1, \y*0.2) circle [radius=0.06 cm, fill=black];}

      \foreach \y in {
        2, 4, 5, 8, 9, 10, 11, 22, 26, 27, 28, 34, 40
      }
      {\filldraw (2, \y*0.2) circle [radius=0.06 cm, fill=black];}

      \foreach \y in {
        1, 2, 5, 13, 15, 17, 19, 20, 21, 23, 31, 35, 36, 37, 38, 42, 44, 47, 48
      }
      {\filldraw (3, \y*0.2) circle [radius=0.06 cm, fill=black];}

      \foreach \y in {
        1, 2, 4, 5, 10, 11, 13, 17, 19, 20, 26, 28, 31, 34, 35, 36, 37,
        38, 40, 42, 44, 47, 48
      }
      {\filldraw (4, \y*0.2) circle [radius=0.06 cm, fill=black];}

      \foreach \y in {
        1, 4, 5, 9, 10, 11, 13, 15, 17, 31, 34, 35, 36, 47, 48
      }
      {\filldraw (5, \y*0.2) circle [radius=0.06 cm, fill=black];}

      \foreach \y in {
        1, 2, 5, 9, 11, 13, 15, 17, 19, 20, 21, 26, 27, 31, 35, 37, 38
      }
      {\filldraw (6, \y*0.2) circle [radius=0.06 cm, fill=black];}

      brackets
      \foreach \k in {1, 2, ..., 8}{
        \draw [decorate, decoration={brace, amplitude=3pt}, xshift=0pt,
        yshift=0pt] (-1, 0.7*0.2 + 6*\k*0.2 - 6*0.2) --
        (-1, 0.3*0.2 + 6*\k*0.2)
        node [black, midway, xshift=-0.6cm] {\footnotesize box $\k$};
      }
    \end{tikzpicture}
    \label{figure:graph_chair}
  }
  \caption{High-level Grasp-Placement Tables of objects used in our
    simulations.}
\end{figure}

\begin{table*}
  \centering
  \caption{Pre-Processing time, planning time, and numbers of transitions from
    three problems averaged over $100$ runs.}
  \label{table:results}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabularx}{1.00\textwidth}
    {
      @{\extracolsep{\fill}}|
      >{\setlength\hsize{0.2\hsize}\centering}X||
      >{\setlength\hsize{0.32\hsize}\centering}X|
      >{\setlength\hsize{0.32\hsize}\centering}X|
      >{\setlength\hsize{0.28\hsize}\centering}X|
      >{\setlength\hsize{0.23\hsize}\centering}X||
      >{\setlength\hsize{0.32\hsize}\centering}X|
      >{\setlength\hsize{0.32\hsize}\centering}X|
      >{\setlength\hsize{0.28\hsize}\centering}X|
      >{\setlength\hsize{0.23\hsize}\centering}X||
      >{\setlength\hsize{0.32\hsize}\centering}X|
      >{\setlength\hsize{0.32\hsize}\centering}X|
      >{\setlength\hsize{0.28\hsize}\centering}X|
      >{\setlength\hsize{0.23\hsize}\centering}X|
    }
    \cline{2-13}
    \multicolumn{1}{c|}{}
    & \multicolumn{4}{c||}{Problem $1$ (Box)}
    & \multicolumn{4}{c||}{Problem $2$ (L-shaped object)}
    & \multicolumn{4}{c|}{Problem $3$ (Small chair)}
    \tabularnewline
    \cline{2-13}
    \multicolumn{1}{c|}{}
    & prep. time (s.) & plan. time (s.) & \# transitions &
    success rate
    & prep. time (s.) & plan. time (s.) & \# transitions &
    success rate
    & prep. time (s.) & plan. time (s.) & \# transitions &
    success rate
    \tabularnewline
    \hline
    \multicolumn{1}{|m{0.09\linewidth}|}{Our planner}
    & {$0.24$} & {$12.18$} & {$4.0$} & {$100 \%$}
    & {$0.50$} & {$15.32$} & {$4.0$} & {$100 \%$}
    & {$1.95$} & {$29.19$} & {$4.0$} & {$100 \%$}
    \tabularnewline
    \hline
    \multicolumn{1}{|m{0.09\linewidth}|}{PMP}
    & {--} & {$32.02$} & {$5.52$} & {$100 \%$}
    & {--} & {$46.83$} & {$5.07$} & {$73 \%$}
    & {--} & {$68.82$} & {$5.88$} & {$50 \%$}
    \tabularnewline
    \hline
    \multicolumn{1}{|m{0.09\linewidth}|}{DBMP}
    & {$35.53$} & {$17.99$} & {$4.0$} & {$72 \%$}
    & {$55.18$} & {$39.76$} & {$4.0$} & {$53 \%$}
    & {$102.38$} & {$37.08$} & {$4.0$} & {$46 \%$}
    \tabularnewline
    \hline
  \end{tabularx}
  \vspace{-10pt}
\end{table*}

\subsection{Descriptions of Alternative Manipulation Planners}

We implemented two alternative manipulation planners, each of which
lies on opposite ends of the spectrum of Manipulation Graph
construction. The first planner does not explicitly construct the
graph while the second constructs the graph by means of
discretization. Our planner lies midway between the two.

\subsubsection{Primitive Manipulation Planner (PMP)}
\label{subsubsection:pmp}

PMP has minimal knowledge of the structure of $\mc{C}$ as it has no
pre-processing stage. It explores $\mc{C}$ according to the transition
diagram, similar to~\cite{LM15hal}, shown in
Fig.~\ref{figure:transition}.

We implemented PMP as a bidirectional tree-based planner. It grows one
tree rooted at $(\q{start}, \T{start})$, the other rooted at
$(\q{goal}, \T{goal})$. In each iteration, it samples a new composite
configuration and tries to connect it with existing vertices on a
tree. For example, if the newly sampled configuration is in $\mathcal{G}\cap\mathcal{P}$ and
is to be connected with a configuration in $\mc{P}$ on a tree, then
the local planner will try connecting them with a transit path. For
the distance metric used in our implementation, we defined a distance
$d$ between two configurations $(\bm{q}_1, \bm{T}_1)$ and $(\bm{q}_2,
\bm{T}_2)$ as a weighted sum of the Euclidean distance between the
robot configurations and a distance between the object
transformations, {\textit{i.e.}}, $d = \alpha\Vert \bm{q}_2 - \bm{q}_1 \Vert^2 +
(1 - \alpha) w(\bm{T}_1, \bm{T}_2)$, where $0 \leq \alpha \leq 1$ and
$w(\bm{T}_1, \bm{T}_2)$ is a weighted sum of the minimal geodesic
distance between two rotations (see~\cite{PR97tg} for more detail) and
the Euclidean distance between two displacements.

\begin{figure}
  \centering
  \begin{tikzpicture}[>=stealth', shorten >=1pt, node distance=2cm,
    auto, bend angle=40, every loop/.style={min
      distance=3mm, in=-20, out=20, looseness=5}, scale=0.8,
    inner sep=1pt, minimum size=1pt]
    \node[state] (p) {\small$\mc{P}$};
    \node[state] (gp) [right = of p]{\small$\mathcal{G}\cap\mathcal{P}$};

    \path[->]
    (p) edge [bend left] node [anchor=south, scale=0.8] {transit} (gp)
    (gp) edge [bend left] node [anchor=south, scale=0.8] {transit} (p)
    (gp) edge [loop right] node [anchor=west, scale=0.8, align=left]
    {transit $\rightarrow$ transfer or \\ transfer $\rightarrow$ transit} (gp);
  \end{tikzpicture}
  \caption{A transition diagram used in Primitive Manipulation Planner.}
  \label{figure:transition}
\end{figure}

\subsubsection{Discretization-Based Manipulation Planner (DBMP)}
\label{subsubsection:dbmp}
In contrast with PMP, DBMP constructs its variant of Manipulation
Graph, \emph{two-layer regrasp graph}~\cite{WanX15icra}, by
discretizing placements and grasps

We implemented DBMP following~\cite{WanX15icra}. The planner starts by
constructing the set of possible grasps by means of sampling. Then it
builds a two-layer regrasp graph\,: the first layer composes of
placements and the second layer composes of grasps. Two placements in
the first layer are connected together if they share at least one
common valid grasp. To solve a query, DBMP first searches for
placement sequences that connect the start and goal placements. Then
it examines each placement sequence and searches for feasible grasps
associated with it.

However, since all the searches are deterministic and proceed in a
depth-first fashion, the time-complexity of DBMP is significantly
large. Instead of having three varying parameters for each placement
class\,: two parameters for a location on the table and one parameter
for the rotation about an axis normal to the table's surface, we
constrained each placement class to have only a single varying
parameter, the rotation. The same was also done implicitly
in~\cite{WanX15icra}. Furthermore, the deterministic search is also
much sensitive to indexing of grasps and placements. To reduce this
effect we shuffled grasp and placement indices before each run.

Note that our implementation of grasp set computation was different
from the method used in~\cite{WanX15icra}, which was basically a
discretization. Therefore, the pre-processing time put in
Table~\ref{table:results} is intended only for reference. The numbers
of total grasps computed in the cases of a box, an L-shaped object,
and a chair are $124$, $242$, and $331$, respectively.

\subsection{Simulation Results and Comparisons}

For each object, we ran each of the three planners $100$ times. The
data collected are pre-processing time, planning time, numbers of
transitions, and success rate. (If no solution was found in $100$ s.,
then the run was considered failed.) Data were averaged over
successful runs and reported in Table~\ref{table:results}.

\subsubsection{Comparison with Primitive Manipulation Planner}
From the data reported in Table~\ref{table:results}, we can see that
by exploiting more information about the connectivity of subsets of
$\mathcal{G}\cap\mathcal{P}$, {\textit{i.e.}}, by constructing high-level Grasp-Placement Tables, our
planner was able to search for manipulation paths more systematically
and efficiently, as reflected through the running time and the path
quality achieved by our planner. As PMP had no information about the
connectivity, much planning time was spent attempting infeasible
connections between $\mathcal{G}\cap\mathcal{P}$ configurations. Furthermore, when the object
was composed of more boxes, connection attempts were even more prone
to failure since from any subset of $\mathcal{G}\cap\mathcal{P}$, the ratio of the number of
reachable $\mathcal{G}\cap\mathcal{P}$ subsets to the number of all the subsets decreased.

\subsubsection{Comparison with Discretization-Based Manipulation
  Planner}
In fact, the two-layer regrasp graph~\cite{WanX15icra} is similar to
ours. One major difference is that they did not exploit any grasp
parameterization in building the graph. Therefore, in their case, each
grasp class contains exactly one grasp, hence numerous grasp
classes. Also, the deterministic search employed in DBMP makes its
capability relatively limited. Firstly, all placements have to be
constrained to only one location on the table, or at most a few, due
to time complexity of the search. Second, a significant amount of time
is spent on exploring infeasible placement and grasp sequences due to
the depth-first fashion of the search. This makes the success rate of
DBMP in the given time much lower than the other planners.

\subsection{Hardware Experiment}
Besides simulations, we also conducted a hardware experiment. In this
experiment, the robot must pick up the leg of a stool, which we
approximated by three boxes, and hold it with a given grasp to
facilitate a subsequent screwing operation (to be performed by another
robot; not included in this experiment). Snapshots of the start and
goal configurations are shown in Fig.~\ref{figure:realexp}. One can
see that the initial pose of the object does not allow grasping with
the desired grasp. Thus, the robot needs to regrasp the object several
times. A video of the robot performing the task can be found at
{\tt{https://youtu.be/tLouwj0wITQ}}.

\captionsetup*[subfigure]{position = bottom}
\begin{figure*}
  \centering
  \subfloat[{}]{\includegraphics[height=0.13\textwidth]{exp_1}}
  \hspace{3pt}
  \subfloat[{}]{\includegraphics[height=0.13\textwidth]{exp_2}}
  \hspace{3pt}
  \subfloat[{}]{\includegraphics[height=0.13\textwidth]{exp_3}}
  \hspace{3pt}
  \subfloat[{}]{\includegraphics[height=0.13\textwidth]{exp_4}}
  \hspace{3pt}
  \subfloat[{}]{\includegraphics[height=0.13\textwidth]{exp_5}}
  \hspace{3pt}
  \subfloat[{}]{\includegraphics[height=0.13\textwidth]{exp_6}}
  \hspace{3pt}
  \subfloat[{}]{\includegraphics[height=0.13\textwidth]{exp_7}}
  \caption{Snapshots from the experiment on the real robot. (a) The
    start configuration. (b)--(f) The robot performed pick-and-place
    motions to move the object to a stable placement which allowed
    grasping with the desired final grasp. (g) The goal
    configuration. The video can be found at
    \tt{https://youtu.be/tLouwj0wITQ}.}
  \label{figure:realexp}
  \vspace{-15pt}
\end{figure*}

\section{Discussion and Conclusion}
\label{section:discussion}

\subsection{Extension to Broader Classes of Object Models}
\label{subsection:extension}
Our method for constructing the high-level Grasp-Placement Table is
mainly based on parameterizations of grasp and placement
classes. Parameterization enables categorizing infinitely many grasps
and placements into a finite number of grasp and placement
\emph{classes}. This enables us to effectively capture the
connectivity of $\mathcal{G}\cap\mathcal{P}$ subsets and encode it into a high-level
Grasp-Placement Table without using any discretization.

Our method can generalize to models for which it is possible to find
efficient placement and grasp parameterizations. In general, it is not
difficult to find \emph{placement classes} of a general object as one
can compute the convex hull of the object and then test which surfaces
of the hull result in stable placements. Therefore, the main
requirement is that the object is \emph{grasp-parameterizable}.

A wide variety of objects can indeed be grasp-parameterized, including
many daily-life objects. For example, for a bottle, one can categorize
grasps into three classes, see Fig.~\ref{figure:bottle}. For highly
irregular objects with no efficient grasp parameterization, one may
have to resort to grasp discretization. In such a case, our high-level
Grasp-Placement Table will be similar to the regrasp graph
of~\cite{WanX15icra}.

\begin{figure}
  \centering
  \subfloat[]{\includegraphics[width=0.1\textwidth]{bottle_01}}
  \hspace{18pt}
  \subfloat[]{\includegraphics[width=0.1\textwidth]{bottle_02}}
  \hspace{18pt}
  \subfloat[]{\includegraphics[width=0.1\textwidth]{bottle_03}}
  \caption{Three possible grasp classes for a parallel gripper
    grasping a bottle. Arrows show gripper motions that result in
    grasps contained in the same class.}
  \label{figure:bottle}
\end{figure}

\subsection{Conclusion}
We have presented a manipulation planner to tackle pick-and-place
planning problems. We first proposed a method to construct a
high-level Grasp-Placement Table based on the models of the robot, the
object, and the environment, without resorting to discretization of
$\mathcal{G}\cap\mathcal{P}$, the fundamental set of configurations where transition between
transit and transfer paths may occur. Our construction is therefore
associated with a full parameterization of $\mathcal{G}\cap\mathcal{P}$, in contrast to
previously proposed methods. The Table then serves as a guide for the
planner to explore the composite configuration space.

Our method to construct the Grasp-Placement Table readily applies to
movable objects that are boxes or composed of boxes. In such cases,
assuming that the gripper can exert large enough forces with its
fingers, all grasp classes considered here are also force-closure. We
also discussed extension of the method to handle broader classes of
objects.

The experimental results presented in Section~\ref{section:results}
confirmed that the high-level Grasp-Placement Table helps improve both
running time and manipulation path quality as compared to existing
manipulation planners.

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv