J Intell Robot Syst (2011) 62:467–500
DOI 10.1007/s10846-010-9465-0

Planning-Space Shift Motion Generation:
Variable-space Motion Planning Toward Flexible
Extension of Body Schema
Yuichi Kobayashi · Shigeyuki Hosoe

Received: 22 October 2009 / Accepted: 26 August 2010 / Published online: 15 September 2010
© Springer Science+Business Media B.V. 2010

Abstract To improve the flexibility of robotic learning, it is important to realize
an ability to generate a hierarchical structure. This paper proposes a learning
framework which can dynamically change the planning space depending on the
structure of tasks. Synchronous motion information is utilized to generate ’modes’
and hierarchical structure of the controller is constructed based on the modes. This
enables efficient planning and control in low-dimensional planning space, though
the dimension of the total state space is in general very high. Three types of object
manipulation tasks are tested as applications, where an object is found and used asa tool (or as a part of the body) to extend the ability of the robot. The proposed
framework is expected to be a basic learning model to account for body schema
acquisition including tool affordances.
Keywords Hierarchy generation · Motion planning · Tool affordance
1 Introduction
Among approaches for improving learning ability of robots, hierarchical learning
is an important issue. In some researches of hierarchical learning, navigation inlarge building like complex mazes [6, 11] or controlling a robotic arm with multiple
joints [20] are investigated as examples of large and complex problems. Apart fromthose high-dimensionalities, one aspect of the complexity in robot tasks is that it
involves objects whose shapes can vary depending on situations and the objects can

Y. Kobayashi (B)Tokyo University of Agriculture and Technology, 2-24-16 Naka-cho,
Koganei, Tokyo, Japane-mail: yu-koba@cc.tuat.ac.jp
S. Hosoe
RIKEN-TRI Collaboration Center for Human-Interactive Robot Research (RTC),
Nagoya University, Shimoshidami,
Anagahora, Nagoya, Japan468

J Intell Robot Syst (2011) 62:467–500

play various roles; a target to be carried, an obstacle to avoid collision, or a tool
which can be used to achieve different objectives. The existence of such objects
makes tasks diverse (various objectives and situations), complex (different dynamics
depending on contact or non-contact) and high-dimensional (configuration space).
But the tasks that involve objects have not been explicitly discussed in the researchesof hierarchical learning.
As an approach to the complex control problems, it is known that some behaviorsof the robotic system can be realized by combination of multiple modules, each ofwhich has relatively small dimension, even though the DOF of the total system isvery large. For example, subsumption architecture [5] realized flexible and adaptive
behaviors of locomotion robots with many DOFs, while individual modules in
the architecture played rather simple roles such as collision avoidance or simple
maneuver. From the viewpoint of building learning robots, such architectures realize
flexibility by focusing on just a part of the total system, where the part in focus
flexibly varies depending on the situations and objectives.
In this paper, a learning architecture that can account for such variable focus in
robotic motion learning with objects is proposed. A ‘part in focus’ is interpreted
as a space for motion planning in this research. By changing or ‘shifting’ theplanning space, the architecture can be applied to diversity of tasks. In the proposedarchitecture, variables to be controlled can be variant, differing from the multiplemodule learning model [30] where the state variables and control variables have to
be invariant.
In the researches on hierarchical motion planning and generation introduced
above [6, 11, 20], ‘abstraction’ of state space is a common idea, which means thatplanning is first done in an abstract state space, and later the total motion generationis considered with the total state space. In this paper, we consider a chain of objects
and motion of tip object of the chain. The proposed planning framework also uses
a kind of abstraction, and thus can be regarded as hierarchical, in the sense thatfirst trajectory of the tip object is calculated and later planning problem (generating
trajectory) is attributed to planning of shorter chains successively, where considering
the tip of current chain for planning can be regarded as an abstraction.
One possible application of planning-space shift learning is a problem of adaptive
tool-use. An object can be utilized to extend reachable region of a robot when
the robot can move it. That is, the robot can use the object as a tool. The abilityof tool-use has gathered attention partly because it is deeply related to the issueof affordance [10] and body schema, that are frequently discussed in the field ofdevelopmental robotics [1, 15], as well as neuropsychology and cognitive science [17].
Stoytchev proposed a behavior-based approach to realize representation of tool use[27]. They proposed to let the robot find the relation between actions while the robot
is grasping a tool and motions of an object. The tool affordances were expressed bydistance and direction of object motions for several direction of tool motions andvarious shapes of tools. Based on those experiences, the robot realized carrying theobject to desired goals. Nabeshima et al. also proposed a learning framework for tooluse [21]. They used synchronousness of visual and tactile information to extend the
body schema. A neural network architecture was implemented for integrating tactile
information and visual information related to a tool and an object by an associative
memory. By learning extended body schema, the robot realized reaching motion tothe object by grasping the tool.

J Intell Robot Syst (2011) 62:467–500

469

This paper proposes a general and bottom-up description of hierarchy generation.
In [27], actions of the robot were restricted to discrete ones, such as ‘slide arm left’.
This paper deals with continuous observation and action variables, which enables
more varied planning of motions. In [21], visual information that is useful for motion
generation (such as direction from the tip of the tool to the object and distance
between the hand and the object) is extracted by the designer. In this paper, no
specific feature extraction is introduced except observation of configuration variablesof the robot body and the objects. Moreover, in both [27] and [21], distinction of ‘tool’and ‘object’ is given in advance. On the other hand, distinction of object and tool
is not given in this paper. The robot only observes information on objects without
any prior knowledge and it learns functional relationship among object motions.
Since there is no pre-defined distinction of object and tool, an object can play arole of object to be moved toward a destination or a tool to move another object
in this paper’s framework. A disadvantage for this more bottom-up framework isthat acquisition of relations among objects requires large amount of trial motions
and increase of computational amount is also inevitable.
Another related research was conducted by Drescher [9]. He proposed a Piagetiandevelopmental approach for robot learning, where concept invention and planning ofgoal-oriented actions were designed based on schema mechanism. With a simulated
body in a microworld, an agent gradually obtained persistent external objects. In
comparison with this, our paper deals with more simple and fundamental problem
from the perspective of kinematics learning, while Drescher’s schema is based ontactile sensation, moving the view range, distinction of peripheral and foveal vision.
While the basic idea of finding relation between sensing and action is close to[9], this paper proposes to find structure of problem from less information, thatis, only with motion synchronousness and distinction by change of observation
variables. Besides, this paper deals with continuous observation variables, which ismuch closer to the real world and brings much richer and finer structure of object
behaviors.
In the research domain of manipulation planning, motion generation of robots
with objects has been discussed. For example, Siméon et al. discussed applicationof probabilistic roadmap method [14] to planning of manipulation [26]. Comparedwith those planning methods, the planning strategy presented in this paper is rather
primitive and difficult to be applied to complex cases. On the other hand, theseconventional researches never deal with ‘finding object’ or ‘finding to use an object
as a tool’, which can be discussed only by a learning framework from much lower
level, as discussed in this paper.
From the perspective of combination of continuous control and mode switching,
the framework of hybrid dynamical system control [25] is closely related to the
problem discussed in this paper. Though several frameworks have been proposed for
obtaining general solutions for this problem (e.g., [3]), unknown factors of control
problems have been rarely considered. The planning strategy proposed in this paper
can be regarded as a learning-based approach to a class of the hybrid system control
problems, where system dynamics including discrete modes and conditions for modeswitchings are unknown to the robot.
The remainder of the paper is constructed as followings. In Section 2, problem
settings for the proposed learning architecture is described. The learning architecture
is proposed in Section 3, followed by evaluations by simulation in Section 4.

470

J Intell Robot Syst (2011) 62:467–500

2 Problem Description
For simplicity, it is assumed that all motions of the robot and the objects are quasistatic.1 Let N be the number of joints of the robot arm and M the number of theobjects, which move only through contacting with the robot hand or other objects,
i.e., they do not move by themselves.2 The state variables of the system are thefollowings:––

Variables which express the configuration of the robot; θ ∈  ⊂ R N
Variables which express the configuration of the objects; q1 ∈ RN1 , · · · ,q M ∈ R NM

The objective of the robot task is to move an object to a certain desired configuration.
Which object should be moved and its desired configuration are given on-line. The
agent can observe the following variables in addition to the configuration of therobot θ:––Position of the robot hand (end effector) h(θ)
Configuration variables of the objects measured from image information

These variables are presented to the agent as the observation vector y ∈ Y ⊂ R Lo .
Initially, the number of the objects or DOFs of motions of them are unknown. The ith component of observation variable y is denoted by yi , i = 1, · · · , Lo . The agent
does not know the correspondence between the elements of y and the observed
position of the robot hand, nor the functional relationships among the elements of y(including the kinematics of the arm).
An example of a robot task is depicted in Fig. 1. The configuration of the robot isexpressed by its two joint angles, θ = [θ1 , θ2 ]T . Configuration variables of two objects
are given by q1 = [q1 , q2 , q3 ]T for the square object and q2 = [q4 , q5 ]T for the circular
object, where posture is omitted for the circular object. The position of the robot
hand is denoted by [y1 , y2 ]T , which corresponds to h(θ1 , θ2 ). The other observation
variables are given by [y3 , y4 , y5 ]T = q1 and [y6 , y7 ]T = q2 , respectively.
At each time step, the robot can change its configuration variables. That is, u =θ is the control input to the system. The following scenario is assumed about the
task:
–
–
–

–

At the initial state, the robot hand and all of the objects are still and separately
located.3
The robot hand begins moving when input u is given.
A still object begins moving when it comes in contact with the robot hand orother objects in motion. It is assumed that the coupled system of the robot hand
and the objects makes a chain form structure by supposing that contact between
objects happens only at the endmost moving object in the chain.
The movement of an object contained in the chain is assumed to be affected onlyby the one of the neighboring object that is positioned to the robot hand side.

1 By this, velocity components can be omitted from state variables.
2 It is assumed that the robot contacts with an object only at its hand.
3 This assumption is needed so that the robot can distinguish objects only by the information of

motion synchronousness.

J Intell Robot Syst (2011) 62:467–500
Fig. 1 An exemplar problem
setting with two objects

471

object 2
manipulator[ q4 , q5 ]T= [ y6 , y7 ]Tθ2[ y1 , y2 ]T

θ1

hand

[ q1 , q2 , q3 ]T= [ y3 , y4 , y5 ]Tobject 1

Therefore the effect of the object motions is transmitted from the robot hand to
the endmost object in unidirectional way.
The third assumption of forming a chain might restrict the generality of the proposed
framework, because generally there can be various types of contacts, such as loops
and trees. From the perspective of tool use, however, we believe that the case thatthe body and tools form a chain will be very common.

3 Learning Structure
The learning structure proposed in this paper is constituted by the four basic functional components. An overview will first be presented in the following subsection
and following to this the detail of the algorithm will be described.
3.1 Basic Idea of Planning-Space Shift
The agent repeats trial motions while resetting the configurations of the robot arm
and the objects (the reset is done after a certain numbers of motions). The agent
initially yields random action controls (random joint velocities), observes y andcollects them together with control input u. An example with Lo = 5 is shown in
Figs. 2 and 3. Figure 2 shows that by detecting synchronous movements in theobserved variables of y initially, variables y3 , y4 and y5 are observed to change inaccordance with the change of θ. Also it indicates that y3 , y4 , y5 take values in set
Y 1 ⊂ R3 . This corresponds to a situation where the end effector of the robot can be
expressed by three dimensional vector with two dimensional vector for the position
and a scalar for the posture for planar motions. In this situation, only robot handmoves while all objects are remaining still. And Fig. 3 shows that after the movementof Fig. 2 variables y1 and y2 are also observed moving (, where Y 2 ⊂ R2 denotes
the value set taken by y1 and y2 ). Suppose there is a circular object on the plane
whose configuration can be expressed by two dimensional vector, [y1 , y2 ]. This casecorresponds, from the scenario stated above, to the situation where the robot handcontacted with the circular object and both are moving by keeping the contact. In
the following, to designate the set of varying observation variables including theoccurrence relationships we will use the terminology ‘mode’. For instance, the case472

J Intell Robot Syst (2011) 62:467–500

Fig. 2 Mode 1: generation ofcommand u from Y 1

planning in

y2

y1

y3

y4

1

y5

y
desired trajectory
as commandθrobot body &environmentu = Δθ

where only variables y1 , y2 , y3 change while y4 , y5 are still is called mode 1 andthe case where y4 , y5 also change following y1 , y2 , y3 is called mode 2. If y1 , y2 , y3
begin changing first and later y4 , y5 follow, then a different mode number will beassigned.
By collecting the data of θ and y3 , y4 , y5 for some time period in the situation ofFig. 2, one can obtain a functional relationship between θ and y3 , y4 , y5 represented
as a mapping from  to Y 1 and the inverse mapping from Y 1 to  (expressed by anarrow in the figure). Similarly to the case of mode 1, the mapping from Y 1 to Y 2 isregarded as a forward mapping and the inverse mapping from Y 2 to Y 1 is acquired.
Note that it requires fair amount of trial motions to explore mode 2 with simple
random motions, because the system easily goes back to mode 1. One idea to reduce

Fig. 3 Mode 2: generation of
trajectory in Y 1 from one in Y 2

desired trajectory
as command

y1
y

y2

y3

planning in

y4 y5

2

θ
robot body &environmentu = Δθ

J Intell Robot Syst (2011) 62:467–500

473

the amount is to improve controller to avoid mode transitions while the exploration,
which is described later in Section 3.4.
The constructed mappings can be used when a task is given to the robot system.
For instance, let a desired configuration for {y1 , y2 } is given as a cross depicted
in Fig. 4. First, a total trajectory with mode transitions is planned as shown as a
succession of arrows in the right part of the figure. Up to point p12 indicated in Fig. 4,
the trajectory has to be retained in mode 1, i.e., only variables y3 , y4 , y5 can change
but y1 , y2 must be constant. For this, we can use the constructed mapping from Y 1 to
U . After transition to mode 2, the mapping from Y 2 to Y 1 is used while maintaining
mode 2. Note that in the case of mode 2, the trajectory is first planned in space Y 2 .
Then a trajectory in Y 1 that realizes the trajectory in Y 2 is generated. In other words,
the planning space ‘shifts’ to Y 1 . This is the basic idea of ‘shifting’ the planning space.
From the perspective of hierarchical structure, control variables in U ‘obeys’ thetrajectory defined by observation variables in Y 1 in mode 1 (Fig. 2). Next in mode
2, the trajectory in Y 1 is dominated by the trajectory defined in Y 2 (Fig. 3). Thus,
different relations of dependence among groups of variables can be seen in eachmode, where one group of variables in the upper layer dominates the behavior ofanother group of variables in the lower layer. In this sense, the proposed architecture
can be regarded to generate hierarchy autonomously.
This architecture brings two advantages:––

The motion-planning space is not pre-defined. The planning framework can be
flexibly applied to various tasks with different objects and different number ofobjects.
The exploration space is divided into lower dimensional spaces (Y 1 and Y 2 in thepresent example) and this makes the exploration more efficient.
The proposed learning structure has the following functional components:

1. Mode generation by motion synchronousness:
Modes are generated by grouping observation variables based on motion synchronousness. Observation variables are stored for estimating the boundary
between modes.
2. Acquisition of motion mappings with mode keeping and mode transition controls:
Mapping representing a functional relationship between the observed variables
corresponding to objects moving in contact is estimated. This mapping is used toFig. 4 Planning-space shift
among different modes2

2
1

desired configurationumode 2
1umode 1mode transition

p12

current configuration
1

474

J Intell Robot Syst (2011) 62:467–500

plan motion of the ‘causal’ object when a desired motion of the ‘resultant’ object
is given. Within each mode, there can be two strategies for control;(a) to keep the same mode without any occurrence of mode transition, and(b) to make mode transition to a certain target mode.
3. Exploration and estimation of reachable region:
Using the motion mappings mentioned above, each mode is explored. Duringexploration, observation variables are stored to estimate reachable regions.
4. Planning and control via multiple modes:
Once a desired configuration of a certain object is given to the robot, the total
trajectory is planned by finding via points on the boundaries among modes ( p12
in Fig. 4). Parameterization of boundaries is used for this.
These processes can be conducted simultaneously, but we execute and evaluate eachprocess one by one, for simplicity. The following subsections give the details of thecomponents.
3.2 Mode Generation Using Motion Synchronousness
Recall that vector y = [y1 , · · · , y Lo ]T ∈ Y ⊂ R Lo is the observation vector. y(t)denotes the observed value of y at time t. In order to detect synchronousness amongobservation variables, time differences of observation variables are defined as
ya (t) = ya (t) − ya (t − 1),

a = 1, · · · , Lo .

(3.1)

With ya (t), its indicator set IC is defined as4
IC (t) = {a|ya (t)  = 0}.

(3.2)

Based on this, the notion of ‘mode’ is introduced as follows. ‘Mode 1’ specifies theinitial stage of each trial where only the robot hand moves and all the objects arestill. This is characterized by the set value taken by IC (t), which is constant up to themoment when the robot hand touches an object (let it be t1 ). Let us represent thisset as(3.3)
IC(1) = i11 , i12 , · · · , i1n1 = IC (t), 0 ≤ t < t1 .
The corresponding observed variables (changing components of y describing the
movement of the robot hand) are represented by the vector


(3.4)
y(1) = [yi11 , · · · , yi1n ]T , i11 , · · · , i1n1 = IC(1) .
1Continuing the trial, we come to a new stage denoted as mode 2, which represents
that the robot hand contacts with an object and both the robot hand and the object
move together. This new mode is characterized by the indicator setIC(2) = i11 , i12 , · · · , i1n1 , i21 , i22 , · · · , i2n2 = IC (t), t1 ≤ t < t2 ,(3.5)

4 This condition of nonzero change is not applicable to problems with noise. An approach to thisproblem is to set a range of values to judge whether they are still. This point is discussed later in
Section 5.

J Intell Robot Syst (2011) 62:467–500

475

where t2 denotes the time moment the object in mode 1 meets another object and n2
the dimension of the vector composed of the observed variables


(3.6)
y(2) = [yi21 , · · · , yi2n ]T , i21 , · · · , i2n2 = IC(2) − IC(1) ,2corresponding to the new object. Continuing further in this way, at every moment
when a mode that has never been encountered is experienced, we define a newmode by assigning it a new numbering, its corresponding indicator set and the vector
expressing the new variation components of y.5 The index of the tip object of thechain corresponding to mode i is denoted by T(i) as a function of i. Furthermore let
us denote the vector space spanned by observed vector y(k) for object Ok6 as Y k .
Using these notations, the set of all the observed variables for Ok throughout trials
is defined as


(3.7)
O(k) = y(k) (t) ∈ Y k .
Note that the increase of the total number of objects causes (potentially) exponential
growth of modes. In the application, however, we do not suppose modes with large
number of objects, because standard applications for tool use do not require large
number of objects.
3.3 Estimation of Mode Boundaries Using SVM
The boundaries among different modes can be estimated by collecting observed
values on Y at the moment of the mode changes. Specifically, let us consider( j)
the boundary between mode i and j, where it is assumed that IC(i) ⊂ IC and let
k = T(i) and  = T( j). We collect all the observed data y1 (t), y2 (t) just before andy1 (t + 1), y2 (t + 1) just after the contact between objects Ok and O , respectively.
Let us arrange all such data in the following way.
TBi,0 j = y1 (t)T , y2 (t)T , | y1 (t), ∈ O(k) , y2 (t), ∈ O() ,TBi,1 j = y1 (t + 1)T , y2 (t + 1)T | y1 (t + 1) ∈ O(k) , y2 (t + 1) ∈ O() ,Bi, j = Bi,0 j ∪ Bi,1 j = {a1 , a2 , · · · , ams },(3.8)

where ms denotes the number of the observed data. To get the boundary equations
between modes i and j, non-linear Support Vector Machine (SVM), which is known
as a non-linear classifier with kernel functions [29], is applied.7 For this, let us denoteby x = [ y1T , y2T ]T an arbitrary variable vector. In non-linear SVM with Gaussian
kernel, by introducing kernel function K asx − ac 2
K(x, ac ) = exp −
,
(3.9)
σs2

5 Suppose there are two objects A and B. Then generally there can be five modes corresponding to

the chains of the robot and the objects, hand, hand-A, hand-B, hand-A-B and hand-B-A.
6 Hereafter, we suppose that the term ‘object’ includes the robot hand. And we let observation

variables y(k) correspond to object k, denoted by Ok .

7 Among various classification methods, we selected SVM because of its usability for parameterizing

mode boundaries in the later section using discrimination function F(x) given by SVM.

476

J Intell Robot Syst (2011) 62:467–500

where σs denotes a width parameter for the Gaussian kernel, the separation surface
between two classes is expressed as
F(x) ≡ms

dc wc K (x, ac ) = 0,

(3.10)

c=1

where dc = 1 (respectively −1) if ac corresponds to mode i (respectively mode j) and
w is the solution of the following optimization problem:min

1 T
w Qw − eT w , e = [1, · · · , 1]T ∈ Rns .
2(3.11)Q=

1+ H HT ,ν

(3.12)w

Q is given by
H = D[A , −e],ν > 0,

where D = diag[d1 , · · · , dms ], A = [a1 , · · · , ams ]T and ν is a parameter for the optimization problem. For implementation of optimization in Eq. 3.11, Lagrangian SVM[16] is applied.
The boundary information obtained by SVM is used for (1) generation of mode
keeping (and mode transition) motion controller and (2) trajectory planning using via
points on the boundaries with parameterization. In the following, the discrimination
function between mode i and j is denoted by Fi, j(x).
3.4 Mode-Transition and Mode-Keeping Motion Mapping
In this section we consider contact-keeping motions of objects. For this, it is supposedthat object Ok is contacting with object O in a chain of objects (including the robothand) and Ok is located at the nearer side to the robot hand. Therefore motion ofO is affected by Ok . In the following, a mapping will be described to determine
necessary displacement of Ok when the desired displacement of O is specified. Notehere that in general there can be redundancy in the mapping between Y k and Y  .8 To
derive the mapping, all the motion data expressing the contacted motion of objects
Ok and O are to be collected and stored throughout all random explorations. Let
such data set be obtained as{ ya(k) , ya() }, a = 1, · · · , ng ,(3.13)

where ng denotes the number of the samples. Now assume that at time t we haveobserved y(k) (t) and y() (t) on the observation variables for Ok and O respectively
and that desired displacement  y() for O is specified. With these data set we wish tofind  y(k) which realizes the desired displacement. This situation is depicted in Fig. 5
as motion transformation Gk, from Y  to Y k . Motion transformation Gk, receives

8 One example is the redundancy of the kinematics of the manipulator itself. When the manipulator

has 3 DOF in planar motion and observation variables for the hand are only x-y configuration
variables (excluding posture), there can be infinite motions of the joint angles that realize a desired
2D displacement of the hand. Another example is shown in Fig. 6 with Ok (circle) and O (ellipsoid).
In the figure, three different displacements of y(k) can cause the same motion of y() . To determine y(k) uniquely in such cases, we will pose a constraint to choose the smallest displacement of y(k) .

J Intell Robot Syst (2011) 62:467–500
Fig. 5 Motion transformation
between Y k and Y 

477

motion transformation

Δ y (l )Δ y (k )

Gk ,l
(k )

motion of ywhich realizes desired motion

desired motion
(l )
of y

 y() as an input and gives  y(k) as an output. As a result, it can generate a small
motion of y(k) so as to realize given (desired) small motions of y() .
Such a transformation can be constructed by an extension of sample-based
function approximation techniques (e.g. [2, 28]). Displacement  y(k) that realizes y() can be expressed as y(k) =ngw̃a ya(k) − y(k) (t),(3.14)

a=1

where w̃a , a = 1, · · · , ng denotes a weighting coefficient. w̃a is normalized as w̃a =wa / b wb , where wa is given as2y(t) − ya(k).
(3.15)
wa = ωa g sω , exp −2σ12
ωa and sω are given asωa = exp −y() (t) +  y() − ya()and function g(s, β) is defined as

2σ22

2


,

sω =

ng


ωa

(3.16)a=11g(s, β) = β + (1 − β) 1 −,exp(−ζ (s − ξ )) + 1(3.17)

where ζ, ξ > 0 are parameters for shaping the function. The shape of g is shownin Fig. 7. Observe from Eq. 3.16 that sω becomes large when there are sufficientnumber of samples that are close to y() (t) +  y() . Therefore when sω is large we canFig. 6 Redundant mapping
between groups of observation
variablesy(k) (t)Δy (k)Δ y (l)478
Fig. 7 Outline of g(s, β)

J Intell Robot Syst (2011) 62:467–500

1g(s,β)

β0sutilize generally more sufficient (possibly redundant) samples to determine  y() . In
such case, weighting coefficient wa is calculated using both information of ya(k) andya() , and finally  y(k) is decided based on both ya(k) and ya() . (note that g(s, β)β in Eq. 3.15 because sω is large. Then wa is decided by the product of the term
including ya() and the term including ya(k) ). If sω is small, contrarily, there are notsufficient samples. In such case, wa is decided only by considering the weight of ya()(note that g(s, β) 1 in Eq. 3.15 because sω is small. Then wa reflects only the term
including ya() ). Function g(s, β) is defined in Eq. 3.17 as a continuous curve in orderto smoothly connect the both cases.
Here we have to address a scalability problem of the proposed method, i.e., thenumber of samples needed for constructing mappings between motions become ingeneral very large according to the increase of dimensions of input and output
spaces, since the whole spaces have to be covered with samples. We will face thesame problem also for estimation and parameterization of boundaries. A key idea toreduce this problem is to effectively use already obtained knowledge, which is also
related to generalization of approximation, as can be seen in an example of ellipsoidal
estimation of reachable region described in Section 3.6.2. The issue of scalability willbe also discussed in Section 5.
To accumulate motion data to construct the transformation mapping throughrandom explorations and also to apply the mapping for motion generation, the mode
has to be kept unchanged, i.e., it has to stay in the same mode. In the following, byassuming that the current mode is i and k = T(i), an algorithm will be presented to
avoid mode changes from mode i to any other modes. For this, consider an arbitrary
mode h ( = i) and let m = T(h). Recall that the boundary between modes i and his given by Fi,h (x) = 0 (see Eq. 3.10), where Fi,h (x) > 0 (respectively Fi,h (x) < 0)
for mode i (respectively h). Define a potential function by i,h (x) = {Fi,h (x)}2 . The
following algorithm can be used to generate random displacement of  y(k) for the
exploration in mode i. In case of the motion generation based on Eq. 3.14, rand() instep 2 should simply be replaced by  y(k) by Eq. 3.14.

J Intell Robot Syst (2011) 62:467–500

479

Algorithm 1 Motion generation with mode keeping
1. Set f ound ← f alse
2. While f ound = f alse repeat:(k)(a) Set  ytmp
← rand()(k) T(k), y(m) (t)]T ) > εb , then f ound ← true(a) If Fi,h ([ y (t)T +  ytmp(c) Else repeat the followings for no times:∂ i,h∂ y(k)(k) T(k)Tii If Fi,h ([ y (t) +  ytmp , y(m) (t)T ]T ) > εb , then f ound ← true and
break
(k)
(k)
←  ytmp−ηi Set  ytmp(k)
3. Output  y(k) with  y(k) =  ytmp

Here, ‘rand()’ denotes a random vector generator, η a parameter to adjust themodification of the displacement of y(k) and εb a threshold value to judge thecloseness to the boundary of modes i and h.
3.5 Parameterization of Mode Boundary
Parameterization of boundaries between modes will be needed to determine a point
for transition on the boundary for the total planning accompanying mode transitions.
It can be also used to estimate reachable set based on the parametric approximation of the reachable set. In this section, a boundary parameterization method
is presented based on the expression of mode boundary presented in Section 3.3.
The potential function (x)(= F(x)2 ) which is defined by the SVM discrimination
function is used to utilize the boundary information.
Let us consider parameterization of boundary between mode i and mode j, wherek = T(i) and  = T( j). The parameterization is done for each discretized value
()
()
y()
as shown in Fig. 8. In this paper, it is supposed for simplicityd(1) , · · · , yd(n ) of ythat boundaries are one-dimensional manifolds in two-dimensional space.9 Thus,boundary is estimated by a curve on a plane of Y k ⊂ R2 . The idea employed here
for curve fitting is similar to the active contour models (e.g. [19, 31]) that weredeveloped for edge detection in image processing. The curve model requires aneasy computation for the parameterization and the model presented here meets therequirement because it applies fully segmented representation of the curve.
The curve model consists of multiple segments that are specified by nodes. Now
let qc ∈ R2 denote a node on the boundary between mode i and mode j which we callhereafter c-th node and L denote the number of nodes.10 A curve from c-th node

9 One dimensional boundary corresponds to the case with objects and circular hand expressed in 2D

space.
10 Here we discuss the case with fixed number of nodes and the number of nodes is appropriately

specified. It is also possible to adaptively change L based on the resultant shape of the estimatedcurve.

480

J Intell Robot Syst (2011) 62:467–500

Fig. 8 Parameterization ofboundary by nodesy (l )(k)y2mode j(k )y1mode imode boundaryto (c + 1)-th node, which is defined as c-th segment of the curve, is defined using
following equation as shown in Fig. 9.
z(c) ( p ) = qc + v 1c p + v 2c p 2 ,(3.18)

where v 1c , v 2c ∈ R are coefficient vectors that give the shape of c-th segment of
the curve. This curve is designed so that changing parameter p from zero to one
corresponds to the change on the curve from qc to qc+1 . By differentiating Eq. 3.18
(c)by p , ∂∂zp ( p ) = v 1c + 2v 2c p is obtained. This gives a tangential vector of the curve.
By considering the continuity of positions of the curve at the both edge of the curve
segment, that is, by letting z(c) (1) = z(c+1) (0),2

qc + v 1c + v 2c = qc+1 ,Fig. 9 A curve model
constructed by nodes

c = 0, · · · , L − 1(3.19)(k)y2p' = 1qa+1p' = 0z (a ) ('p)

qa
y1(k)

J Intell Robot Syst (2011) 62:467–500

481

is obtained as the condition for position continuity. Similarly, the condition for
(c)
(c+1)
continuity of tangential vector is given by ∂∂zp (1) = ∂ z∂ p (0), that is,v 1c + 2v 2c = v 1c+1 ,c = 0, · · · , L − 2.

The above-mentioned conditions can be expressed in matrix form as


 
Q1
A1
,Q≡
,
AV = Q, A ≡A2
O2(L−1)×1
where matrices are defined as⎡⎢⎢
A1 = ⎢
⎣

I2 I2

O
I2 I2
..
.

O

(3.20)(3.21)⎤⎥⎥⎥ ∈ R2L×4L ,⎦(3.22)

I2 I2⎤
I2 2I2 −I2O⎥⎢
I2 2I2 −I2⎥⎢
A2 = ⎢⎥ ∈ R2(L−1)×4L
.
..
⎦
⎣
O
I2 2I2 −I2 O2(3.23)⎤v 10⎡⎤⎢ v 20 ⎥q1 − q0
⎥
⎢
⎢
⎥
⎥
⎢
..
2L
V = ⎢ ... ⎥ ∈ R4L , Q1 = ⎣
⎦∈R .
.
⎥
⎢
⎣v 1L−1 ⎦q L − q L−1
v 2L−1(3.24)⎡

and⎡When the positions of nodes are given, the minimum-norm solution V for Eq. 3.21
can be calculated using the pseudo-inverse as V = AT (A AT )−1 Q ≡ A† Q. By connecting all segments, a one-dimensional submanifold z(s) can be defined as follows:z(s) ≡ z(c) ( p ),c ≤ s < c + 1, p = s − c, c ∈ Z.

(3.25)The positions of the nodes need to be modified if curves z(s) lie close to theboundary. By assuming that the boundary is smooth, this is realized by anincremental procedure to reduce energy defined on the curve, where energyfunction of the curve is defined with coefficient αext and αint as
E = αext Eext + αint Eint .

(3.26)

An internal energy for the curve is defined as L 2
2∂ z(s)
ds.
Eint =∂s2
0(3.27)

Using Eq. 3.18, Eint can be expressed as
Eint =L  1

∂ 2 z(c)
∂p 2
c=1 0

2

dp = 4Lc=1

v 2c 2 .

(3.28)

482

J Intell Robot Syst (2011) 62:467–500

Eext is defined so that the curve coincides with the boundary when Eext is minimized.
By using the potential function i, j, it can be defined as
Eext =L() T TTi, j ([qc , y(d) ] ),(3.29)c=1()where y()(d) denotes discretized value of y . By iterating the following gradientdescent updateq c ← q c − ηn

∂E
,
∂qc

c = 1, · · · , L,

(3.30)

the positions of nodes 1, · · · , L are modified so that the curve lies more closely
to the boundary while keeping the smoothness of the curve. The positions of theend nodes 1 and L have to be updated so that they expand up to the furthest (in
(L−1)
(1)
the direction of ∂ z∂ p (1) and − ∂∂zp (0) from the positions of 1st and L-th nodes,
respectively) observed data in Bi, j. After convergence of the iteration of Eq. 3.30,
any point on the boundary can be expressed by parameter s.
In the following sections, parameterization of boundary between mode i and j will
be presented as zi, j(s) to identify modes.
3.6 Expression for Reachable Region
For planning trajectories to realize the desired configurations of objects, it is required
to identify where the object can reach (reachable region). In this section, a describing
method is given for the reachable region for observation variable y() (corresponding
to O ). Before this, let us consider the pushing task of a triangular object as an
example (see Fig. 10). When the hand is touching the object at the left (, respectively right) leg, the reachable region of the object is restricted to the right-hand(, respectively left-hand) space of the current object position. This shows that thereachable region of an object changes according to at which part of object- (hand-)surface the contact takes place. In the general case, the reachable region (, say ofobject O ) is characterized by the following factors:(i) Set of objects forming a chain whose tip object is O and their arranging order(ii) Initial locations of the the objects in the chain(iii) Contact positions of any two mutually connected objects in the chain(i) is reflected in the observation on mode transitions since each mode corresponds
to a chain. (ii) can be expressed by the observation variables that start moving at the
instant of mode changes. (iii) can be specified by the boundary parameters recorded
when each contact between two objects happened. Since positions of objects andtheir contact positions take continuous values, the reachable regions of objects
depend on these continuous variables and therefore are characterized in general
by infinitely many parameters. Here to get an explicit description of the reachable
regions, we will introduce a finite number approximation for them by discretizing
continuous variables. The left hand of Fig. 11 shows the conceptual diagram for thediscretization, where the black small circles on the vertical axis of y() indicates thediscretization of observation variable y() and the black small circles on the curves

J Intell Robot Syst (2011) 62:467–500
Fig. 10 Different reachable
region depending on contact
point and object configuration

483

manipulator

reachable region
hand
object(that designates a boundary between two modes) indicates the discretization of aparameter for the mode boundary.11
Now, let us consider the reachable region of object Oc . We assume that Oc is thetip object of mode ic (c = T(ic )) and mode transitions have occurred as i1 → i2 →· · · → ic . This sequence of mode transitions is expressed by τ = [i1 , · · · , ic ]T ∈ Nc
and it contains the information corresponding to (i). Let i and j be any two adjacentmode transition in τ and let Ok and O be the contacting objects corresponding
to them, i.e., k = T(i),  = T( j). It is supposed that Ok is located to the nearer
position to the robot hand. Discretized values of observation variables for O , which()
corresponds to (ii), is defined as Y D= { y()(1) , · · · , y(n()) }, where n() denotes thenumber of discretization of the observation variable. This is shown in the left hand of
Fig. 11, where the horizontal plane indicates Y k and the curves in the planes denotethe boundary sets between modes i and j. In the figure, space of y() (vertical axis)
is discretized with equal distances as shown by the small circles on the axis. Recall
that s is the parameter on the boundary defined in Eq. 3.25 and corresponding to thecondition (iii) about contact, the discretization of boundary parameters (between(i, j)(i, j),1(i, j),n(i, j)
mode i and j) is introduced as S D(b ) = {s(b ) , · · · , s(b )}, b = 1, · · · , n(), where(i, j),as(b )denotes a discretized parameter on the boundary of mode transition from ito j when the discretized observation variable takes value y()(b ) and n(i, j) denotes
the number of discretization of the boundary. The right hand of Fig. 11 indicatesthe conceptional picture of reachable regions. Each ellipse represents the reachable
region of object O caused by the contact between objects Ok and O where the(i, j),acontact initiated at y() = y()(b ) and the boundary parameter was s(b ) . The horizontal
plane indicates the space Y  (, here for drawing purpose it is assumed to be twodimensional whereas it was represented by one-dimensional space in the left handfigure).
(i, j)

Based on the above-mentioned notation of Y D
and S D(b ) , estimation of reachable
region is given. Let T denote the set of experienced mode transition sequences. T is
updated whenever a new mode transition τ is experienced, i.e.,

T ← T ∪ {τ } if τ ∈/ T ∧ IC(i1 ) ⊂ IC(i2 ) ⊂ · · · ⊂ IC(ic ) .

(3.31)The second condition stands for that new mode sequence is memorized only when
the total number of objects in the chain increases. By this, mode transitions withseparation between objects are omitted. Identification of mode transition for mode

11 Note that the idea of discretization is same as shown in Fig. 8, though the objective of discretizationin Section 3.5 was to parameterize the boundary by multiple segments of curves.

484

J Intell Robot Syst (2011) 62:467–500

Fig. 11 Discretization of modeboundary and observation
variable and extrapolation
with parameter on boundaryy (l )ys((bi ,)j ),as((bi ,)j ),a

(l )
(b )

s((bi ,)j ),5s((bi ,)j ),1y((1l))y2( k )

s((bi ,)j ),1y2(l )

mode j(k )1mode iymode boundaryy1(l )

transition parameter s(i, j) and observation variable y() can be given as gτ = {s̄τ , ȳτ },
where
(2 )
(e )
(e )
c)
ȳτ = [ y(b, · · · , y(, e = T(ie ), e = 2, · · · , c (3.32)(b c ) ], b e = arg min  y(b ) − y
2)
b

and
(i ,i ),a1,2s̄τ = [s(b1) 2(i,i ),ac−1,c T

c, · · · , s(bc−1)] , b = b e+1 ,(i ,i ),aae,e+1 = arg min s(be ) e+1 − s(ie ,ie+1 ),a , e = 1, · · · , c − 1, .
a

(3.33)

Note here that gτ contains discrete expression of (i), (ii) and (iii). Let Dτ (gτ ) denotethe set of all observed y() where mode transitions specified by τ and gτ have takenplace (here we let  = c for simplicity of notation), which will be used as a data basefor estimating the reachable regions. When y() (t) is observed during exploration,Dτ (gτ ) is updated asDτ (gτ ) ← Dτ (gτ ) ∪ { y() (t)} if  y() (t) − ya()  > Rr , ∀ ya() ∈ Dτ() (gτ )(3.34)

where Rr > 0 denotes a threshold value and ya() denotes a-th element in Dτ (gτ ).
3.6.1 Estimation of Reachable Region with Raw Samples
A straightforward approach to estimate reachable region is to sum up hyperspheres
whose centers are observed samples as shown in the left hand of Fig. 12. Based on
this idea, reachable region of O via mode transition τ and gτ can be expressed as()Rτ (gτ ) = { y() ∈ Y  |∃ y()− y()m ∈ Dτ (gτ ),  ym  ≤ Rr },which will be used in motion planning described in Section 3.7.

Fig. 12 Estimation ofreachable region by two ways:
directly approximating byobserved samples andapproximating withparameterized geometrical
model

l

l

observed
sample(3.35)

J Intell Robot Syst (2011) 62:467–500

485

3.6.2 Estimation of Reachable Region with Parameterized Smooth Function
Another approach to estimate reachable region is to apply parameterized geometrical models as indicated in the right hand of Fig. 12. This model is suitable to be used
when the number of available observation samples are not enough. Let us consider acase in the right hand of Fig. 11, where we do not have sufficient number of observed(i, j),a(i, j),5
samples for s(5) . In this case, it is possible to estimate the reachable region for s(b )(i, j),aby extrapolating parameters of reachable regions for s(b ) , a = 1, · · · , 4 as can beseen in the figure (a yellow ellipsoid).
Now we consider again the case where mode ic has been reached by modetransition τ = [i1 , · · · , ic ]T , where  = T(ic ). Assume that the mode transition is
specified by gτ = {s̄τ , ȳτ }, where(i ,i ),a1,2ȳτ = [ y(b 2 ) , · · · , y(b c ) ], s̄τ = [s(b1) 2(i,i ),ac−1,c T

c, · · · , s(bc−1)] .

(3.36)

Among these parameters for the mode transitions, we are interested in the boundary
parameter of the latest mode transition of ic−1 → ic , that is, where Ok , k = T(ic−1 )touched with O . So we rewrite gτ as(i ,ic ),ac−1,c T, ȳτ .
gτ = s̄0τ T , s(bc−1(3.37))
That is, s̄0τ denotes discretized parameters on the mode transition boundaries except
for the latest transition ic−1 → ic . Then we wish to get an approximation for the(i ,ic ),areachable region for O (denoted by Rτ ,s̄0 , ȳ (s(bc−1)) realized via mode transition
)
τ
τ


(ic−1 ,ic ),a0 T (ic−1 ,ic ),aand ȳτ . Rτ ,s̄0 , ȳ (s(b )s̄τ , s(b )) is in the formττ

(ic−1 ,ic ),aRτ ,s̄0 , ȳ (s(b) = { y ∈ Rn |Fφ ( y) ≤ 0},)ττ(3.38)

where Fφ ( y) denotes a quadratic form with parameters φ = [λ1 , · · · λn , ψ T , d T ]T
described by
⎡ 2
⎤
λ1
⎢
⎥
Fφ ( y) = ( y − d)T R(ψ)T ⎣ . . .
⎦ R(ψ)( y − d) − 1, λ1 , · · · , λn > 0, (3.39)
λ2nwhere R(ψ) ∈ Rn ×n denotes the rotation matrix with parameter ψ ∈ Rn (n −1)/2 .
(i ,ic ),aParameter φ is determined so that Rτ ,s̄0 , ȳ (s(bc−1) contains all of the observation
)
τ

τ

(i

,i ),ac) minimal. Therevariables in Dτ (gτ ) while making the volume of Rτ ,s̄0 , ȳ (s(bc−1)ττ
fore, parameter vector φ is decided by minimizing the following cost function:

∀ ()

d y, subject to Fφ ( y()(3.40)
J(φ) =m ) ≤ 0, ym ∈ Dτ (gτ ).
(i,i ),aR 0

τ ,s̄τ , ȳτ(s(bc−1
)

c

)

(i

,i ),ac,a =This estimation is processed for each discretized boundary of s(bc−1
)
 

12


1, · · · , n(ic−1 , ic ) which satisfies Dτ (gτ ) ≥ Nd , where Nd denotes a threshold for

12 |S| denotes the number of elements in set S.

486

J Intell Robot Syst (2011) 62:467–500

Fig. 13 Interpolation usingparameter vectorsφs((bi ,)j ),aφy1(l )( y) ≤ 0y2(l )…

s((bi ,)j ),1s((bi ,)j ),as((bi ,)j ),n (ic−1 ,ic )the number of observed samples. Let a1 , · · · , and denote the discretization indicesof the boundary that meet the above condition for the number of samples, wherend ≤ n(ic−1 , ic ) denotes the number of discretized boundaries that have sufficientnumbers of samples.
Next step is to find an approximation of the parameter vector φ(s) as a functionof boundary parameter s based on φ b , as shown in the right hand of Fig. 13. A linear
polynomial approximation model can be expressed byφ(s) = φ 1 s + φ 0 ,s ∈ R, φ 0 , φ 1 ∈ Rn p ,(3.41)

where φ 0 and φ 1 are coefficient vectors. The least square approximation of coefficient(ipre ,i),and(i ,i),a1, · · · , s(b )and φ̂ a1 , · · · , φ̂ an are given are calcuvectors {φ 0 , φ} when s(bpre)dlated by⎡ (ipre ,i),a1
⎡ T ⎤
⎤
s(b )
1
φ̂ a
⎢
⎢ .1 ⎥
.. ⎥
T
†
⎢
⎢
⎥
⎥
(3.42)[φ̄ 1 φ̄ 0 ] = S Aφ , S = ⎣. ⎦ , Aφ = ⎣ .. ⎦ ,T(ipre ,i),andφ̂ an ,s(b )1dwhere φ̂ a denotes the solution for the optimization problem of Eq. 3.40. Using theobtained approximation of φ̄(s) = φ̄ 1 s + φ̄ 0 , estimation of the reachable region is
given asR̄τ ,s̄0 , ȳ (s) = { y ∈ Rn |Fφ̄(s) ( y) ≤ 0},ττ(3.43)

which gives the interpolation and the extrapolation mentioned in the example.
3.7 Trajectory Generation and Control with Mode Transitions
Planning with mode transitions described in this section corresponds to the dynamical shift of planning space, because different observation variables are usedin planning within each mode. The total algorithm of trajectory generation andcontrol is given in Algorithm 2. A task is given to the robot system as a target
configuration of a certain object.13 Let the target object be Ok∗ and assume its target
configuration y∗(k∗ ) ∈ Y k∗ is given. The robot interprets the given information as atarget mode (step 2. in Algorithm 2). Using mode transition and reachable region

13 Here it is assumed that configurations of other objects and the robot arm are not specified as atask.

J Intell Robot Syst (2011) 62:467–500

487

database, the robot finds an appropriate transition sequence of modes and pair ofmode transition parameters and observation variable at mode transition (steps 3. and4.). At step 5., the robot starts control of its body to realize mode transition sequenceof τ † with transition parameter g†τ † . At each mode, the robot aims at a target(subgoal) point on the mode transition boundary which is specified by discretizedparameter of boundary curve (b). Once a subgoal is determined, the robot repeats
small movements toward the subgoal while trying to keep current mode. For mode(i)keeping, Algorithm 1 can be used by replacing  y(i)given in (c)-i. The
tmp by  y(i)desired motion  y is realized by transformations of motions as shown in Fig. 14.
Algorithm 2 Trajectory generation and control
Given: target object k∗ and its configuration y∗(k∗ )Find target mode i∗ that satisfies k∗ = T(i∗ )Find τ † ∈ T s.t. (∃ a ∈ N s.t. i∗ = τa† )Find g†τ † = {s̄†τ , ȳ†τ } s.t. y∗(k∗ ) ∈ Rkτ ∗† (g†τ † ) ∧ ȳ†τ † = [ y(b 2 ) , · · · , y(b c ) ]T ,e)(e )(0), e = T(ie ), e = 2, · · · , cwhere b e = arg minb  y((b ) − y5. Set current mode as i = 1 and current tip of the chain as k = 1. Repeat following trajectory generation and control procedures until target configurationis achieved, i.e.  y(k∗ ) (t) − y∗(k∗ )  < εd holds:
1.
2.
3.
4.

(a) If i  = i∗ , find next mode as j = τι† where ι = κ + 1, τκ† = i. Let  = T( j) and(i, j),a†set subgoal on mode boundary by y†(k) = zi, j s(b 0 ), where s̄†τ † =(i, j),a†()[· · · , s(b 0 ) , · · · ]T , b 0 = arg minb  y()(b ) − y (t)(b) If i = i∗ , set target observation variable as y†(k) = y∗(k∗ )(c) Repeat small movement of  y(k) until target point is reached (i.e.  y(k) (t) −y†(k)  ≤ εd )(k)=γi Calculate displacement  y(k) by modifying  ytmp(k)
( y(k)† − y (t))(k)
 y(k)† − y (t))

with

Algorithm 1
ii Calculate  y(km ) using  y(k) ,  y(km−1 ) using  y(km ) , · · · ,  y(k0 ) using
 y(k1 ) with Eq. 3.14, where {k0 , k1 , · · · , km , k} denotes the sequence ofthe chain of objects in mode i (k = T(i), k0 = 1).
(d) Set i ← j
In 5(c)-i and 5(c)-ii, displacements  y(k) ,  y(km ) , · · · are calculated so that thetransition to irrelevant modes and the transition to the desired mode at undesired
point on the boundary are avoided. We introduce a threshold value ε p and replace
conditions of 2(a) and 2(b)-ii in Algorithm 1 by(k) TFi,h ([ y(k) (t)T +  ytmp
, y(m) (t)T ]T ) > εb ∧
(k) T
(k)
(Fi, j([ y(k) (t)T +  ytmp
, y() (t)T ]T ) > εb ∨  y(k) +  ytmp
− y†(k)  > ε p ),(3.44)

where h denotes irrelevant mode (h  = j) in this application. By this, mode transition
to j at undesired point on the boundary that is not close to y†(k) can be avoided.
Step 4. in the algorithm is based on the direct memory-based estimation of
the reachable region described in Section 3.6.1. An alternative approach is to use

488

J Intell Robot Syst (2011) 62:467–500

Fig. 14 Planning with modetransition(zi , j s((bi ,0 j)),k)y*( k* )(1)y ( 0)(i )y (t )Δy ( j )targetΔy (1)Δy (i )
mode jmode imode 1Δy (i )umode i*the estimation by the parameterization-based estimation described in Section 3.6.2,
where the procedure will be replaced by the following.



∗)
T † T
, ȳ†τ s.t. y(k∈ Rkτ ∗† ,s̄0† , ȳ (s† ) ∧4 . Find g†τ † = s̄0†
∗
τ ,s
τ†

τ†

e)
(e )
ȳ†τ † = [ y(b 2 ) , · · · , y(b c ) ]T , b e = arg minb  y((0), e = T(ie ), e = 2, · · · , c.
(b ) − y

4 Simulation
The proposed mode generation and trajectory generation algorithms are implemented and evaluated in three types of settings by simulations. In the first setting,the manipulator moves in a vertical plane and the objects are restricted to move ona line (floor) as indicated in the left hand of Fig. 15. Thus motions of objects areconstrained in a one-dimensional line because of the contact with the floor as long as
the objects keep the same posture and do not rotate. In the second setting, the objects
and the hand move on a plane (2D space) without any constraint as depicted in theright hand of Fig. 15. Planning and motion generation are more complicated in thesecond case because of the two-dimensional motions of the object. The proposed
planning framework is evaluated in the first case with multiple objects including
approximation of the boundary with SVM. In the second case, motion generation on
a 2D plane with redundant mapping between groups of the observation variables andapproximation of reachable region are evaluated. In the third setting, L-shaped toolis utilized to move the object close to the robot itself. It is shown that the proposed
framework is applicable to a similar problem setting to learning tool affordance [27].
4.1 Case 1: Multiple Objects with One-dimensional Constraint
The robot manipulator has two joints and there are two objects, rectangular andcircular objects as shown in the left hand of Fig. 15. The end effector of the robot

Fig. 15 Simulation settings:
robot hand and objects

hand[ y1 , y2 ]T

1.5
1

θ2

1

0.5
0
-0.5
-0.5

0

q1
0.5

0

q2
1

Case 1

1.5

2

θ2

object 1

0.5

object 1 object 2
θ1

hand[ y1 , y2 ]T

1.5

2.5

-0.5
-0.5

θ1

0

[ q1 , q2 ]T

0.5

1

Case 2

1.5

2

2.5

J Intell Robot Syst (2011) 62:467–500

489

hand is also circularly shaped. The state variables are the joint angles of the manipulator θ ∈ R2 and positions of two objects q1 , q2 ∈ R. The observation variables are theposition of the robot hand (center of circle) [y1 , y2 ]T , the position of the rectangular
object (object 1) y3 (= q1 ) and the position of the circular object (object 2) y4 (= q2 ).
Initial position of object 1 is randomly chosen in 0.6 ≤ q1 ≤ 0.9, while position of
object 2 is fixed at q2 = 1.6. The manipulator and the objects are initialized every
100 steps.
Exploration and learning are done by the followings:
1. Move the arm randomly for 3,000 steps, including the initializations per 100 steps.
2. Build mapping between [θ1 , θ2 ]T and [y1 , y2 ]T , estimate boundary between mode
1 and mode 2,14 and generate parameterization on the boundary.
3. Explore mode 2 using the motion generator which keeps mode 2 for 200 steps.
4. Build mapping between q1 and q2 , estimate boundary between mode 2 and mode
3 (, where object 2 is moving).
5. Explore modes 2 and 3 using mode keeping motion generator described in
Section 3.4 for 200 steps to estimate reachable region.
Explorations in procedure 3 and 5 are initialized when the robot fails to keep mode
2 or 3 in addition to initializations per 100 steps. For the estimation of the reachable
region at procedure 5, direct memory-based approximation described in Section
3.6.1 is used. It is expected that while procedure 1, contact between the hand andobject 1 happens frequently enough to estimate boundary. Similarly it is expectedthat sufficient motion information of object 2 is obtainable to finally estimate thereachable region. The mapping and boundary building in 4. is formally done but
actually not so important because motions of object 1 and 2 are restricted on a line
and the boundary of mode switching is just a point.
After the total exploration, three tasks are given to the robot system:–––

Task 1: Move the end effector to [y1 , y2 ]T = [1.3, 0.6]T .
Task 2: Move object 1 to q1 = 0.5.
Task 3: Move object 2 to q2 = 1.9.

First, the robot acquired the relation between its joint angles and the hand position
by randomly changing the joint angles (procedure 1). The first group of observation
variables was built as [y1 , y2 ]T ∈ Y 1 . When the hand contacted object 1, the second
group of observation variable was constructed as y3 ∈ Y 2 . While the hand keeps
contact with the object 1, the object moved together with the hand. When moving
object 1 contacted with object 2, object 2 began to move and the third group wasconstructed as y4 ∈ Y 3 . While collecting mapping data by the random motion, therobot also collected boundary information between mode 1 and mode 2. In this casediscrimination function F1,2 (x) of SVM was defined in three-dimensional space, thatis, x = [y1 , y2 , y3 ]T . Figure 16a and b show boundaries of two modes where 0.55 ≤q1 < 0.65 for (a) and 0.65 ≤ q1 < 0.75 for (b). Circles in the figure denote variables
in mode 1, crosses denote mode 2 and curves denote boundaries of F1,2 (x) = 0.

14 They correspond respectively to the movement of the robot hand and the movement of therectangular object by contacting with the robot hand. Mode 3 corresponds to the movement of object
2 caused by the contact with object 1.

490
Fig. 16 Estimated boundaries
between mode 1 and 2

J Intell Robot Syst (2011) 62:467–500
0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1
0

0.1
0.4

0.6

0.8

1

1.2

1.4

1.6

0

0.4

(a) 0.55 ≤ q1 < 0.65

0.6

0.8

1

1.2

1.4

1.6

(b) 0.65 ≤ q1 < 0.75

The discrimination function F1,2 (x) was utilized for parameterization on theboundary explained in Section 3.5. Figure 17a and b are resultant node distributions
with L = 9 after 100 iterations of node movements, where nodes were initiallylocated around the center of the boundary. It can be seen that nodes are distributed
along the contour of F1,2 (x) = 0. Both end nodes are constrained to the nearest
observed data, which can be understood by comparing Fig. 16 with Fig. 17.
Figure 18 shows the trajectory of task 1, where a cross in the figure denotes thetarget configuration. This motion was realized by using the mapping between Y 1
and Y 2 , which can be regarded as inverse kinematics learning. In the case of task 2,
first reachable region of y3 was checked by Algorithm 2. A cross in Fig. 19 denotes
the destination on the boundary between mode 1 and 2. First the robot hand aimed
at the destination on the boundary, and then kept contact to realize the desiredconfiguration of y3 . In the case of task 3, first reachable region of y4 was checked.
The lower cross in Fig. 20 indicates the destination on boundary between mode 2
and 3, while the upper cross indicates the destination on boundary between mode 1
and 2. After realizing contact between the hand and object 1, the robot kept contact
to move object 1 to the right direction and to realize contact between object 1 andobject 2. It can be seen that finally the robot realized the desired configuration of
y4 = 1.9 by extending its body by using object 1.
4.2 Case 2: Pushing Manipulation on a Plane
The manipulator used for this setting is the same as case 1. In this case, it is assumed
that only one object exist (, the simplest case) but it can move in the 2D space bycontacting with the robot hand (Fig. 21). The kinematics of the object motion isapproximately given as follows: The position of the hand is updated every discrete
time step based on the updated values of the joint angles in the simulation. Wheninterference between the hand and the circular object occurs, the position of theFig. 17 Parameterization on
boundary with nodes

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0
0.4

0.6

0.8

1

1.2

(a) 0.55 ≤ q < 0.65
1

1.4

1.6

0

0.4

0.6

0.8

1

1.2

(b) 0.65 ≤ q < 0.75
1

1.4

1.6

J Intell Robot Syst (2011) 62:467–500
Fig. 18 Trajectory of task 1

491

1.5

1

0.5

0

-0.5
-0.5

0

0.5

1

1.5

2

object is modified so as to resolve the interference with minimal displacement fromthe original position.
Since there is only one object, there are only mode 1 and 2, where mode 2 denotesthat the object is moving with the hand. Exploration and learning are done by thefollowings:
1. Move randomly for 3,000 steps (within mode 1), including the initializations per
100 steps.
2. Build mapping between [θ1 , θ2 ]T and [y1 , y2 ]T , estimate boundary between mode
1 and mode 2, and generate parameterization on the boundary between modes 1
and 2.
3. Choose a target subgoal on the boundary randomly and navigate the hand
toward the subgoal in mode 1. When the hand contacts with the object, explore
mode 2 randomly while trying to keep mode 2. Totally 1,000 steps are performed
for this reachable region exploration while the positions of the hand and theobject is reset every 50 steps.

Fig. 19 Trajectory of task 2

1.5

1

0.5

0

-0.5
-0.5

0

0.5

1

1.5

2

492

J Intell Robot Syst (2011) 62:467–500

Fig. 20 Trajectory of task 3

1.5

1

0.5

0

-0.5
-0.5

0

0.5

1

1.5

2

In the estimation of the reachable region, approximation with parameterized function described in Section 3.6.2 is applied. A two-dimensional ellipsoid with parameterset of φ = [λ1 , λ2 , ψ, d T ]T ∈ R5 is used for the reachable region approximation:
 2 
λFφ ( y) = ( y − d)T R(ψ)T 1 2 R(ψ)( y − d) − 1, λ1 , λ2 > 0,
(4.1)
λ2
where R(ψ) ∈ R2×2 denotes the rotation matrix with rotation angle ψ. Using thisparameter set, the square measure of the ellipsoid can be expressed byJ(φ) =

1
.
λ1 λ2

(4.2)

There are two tasks given to the robot:––

Task 1: Move the end effector to [y1 , y2 ]T = [1.4, 0.4]T .
Task 2: Move object 1 to [q1 , q2 ]T = [0.86, 0.04]T .

Grouping of hand-related observation variables [y1 , y2 ]T ∈ Y 1 and learning of
kinematics of the manipulator are the same as the first setting. After that, the second

Fig. 21 Problem setting with
one object

1.5

1

0.5

0

-0.5
-0.5

0

0.5

1

1.5

2

2.5

J Intell Robot Syst (2011) 62:467–500

493

Fig. 22 Parameterizedboundary
1

0.8

0.6

0.4

0.2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

group of observation variables are grouped as [y3 , y4 ]T ∈ Y 2 when they change bycontact with the object. Thus, modes are created as mode 1 for free motion of themanipulator and mode 2 for motion of the object by the contact.
The parameterized boundary between mode 1 and 2 is shown in Fig. 22. 8 nodes
are applied for the parameterization. Estimation of reachable regions is done foreach discretized parameter on the boundary. In Fig. 23, three estimated ellipsoids
with discretized parameters of b = 2, 3, 4 are shown. It can be seen that each ellipsoidcontains all of the observed samples while keeping the size of the ellipsoid small.
The optimization of Eq. 3.40 was solved with Nelder-Mead method [22]. Figures 24
and 25 show the result of interpolation of ellipsoidal parameters obtained by theleast-square approximation of Eq. 3.42 from different views. Cross in Fig. 24 indicates
the target position of the object.
Figure 26 shows the trajectory for task 1. In this case, initial configuration of thearm is given as θ = [ 57 π, − 58 π ]T . The hand moved toward the target position while
avoiding contact with the object. This was achieved by the mechanism of mode
keeping, where contact with the object causes the mode transition from mode 1 tomode 2 and keeping mode 1 corresponds to avoiding contact with the object.
Figure 27 shows the trajectory for task 2, where the initial configuration of the7
arm is given as θ = [ 37 π, − 16
π ]T . First the robot checked if the target position of

1.5

1.5

1.5

1

1

1

0.5

0.5

0.5

0

0

0

-0.5
-0.5

0

0.5

1

b=2

1.5

2

2.5

-0.5
-0.5

0

0.5

1

b=3

Fig. 23 Ellipsoids for reachable region estimation

1.5

2

2.5

-0.5
-0.5

0

0.5

1

b=4

1.5

2

2.5

494

J Intell Robot Syst (2011) 62:467–500

Fig. 24 Ellipsoid parametersinterpolation (1)

0.6
0.5
0.4
0.3
0.2
0.1
0
-0.1
-0.2
-0.3
-0.4
0.4

0.6

0.8

1

1.2

the object is included in the approximated reachable region in mode 2 (step 4 in
Algorithm 2). The target (indicated as a cross in the figure) is not included in anyof the approximated ellipsoids. Interpolation proposed in Section 3.6.2, however, enabled to recognize that the target position is included in the approximated reachable
region with parameter s† = 0.5. The destination on the boundary that corresponds toz1,2 (s† ) is indicated as a ‘+’ in the figure. First the hand moved toward the destination

Fig. 25 Ellipsoid parametersinterpolation (2)

0.5
0.4
0.3
0.2
0.1
0
0.6
0.4
0.2
0
-0.2
-0.4

0.4

0.6

0.8

1

1.2

J Intell Robot Syst (2011) 62:467–500
Fig. 26 Trajectory of task 1:
reaching of the hand while
avoiding contact with theobject

495

1.5

1

0.5

0

-0.5
-0.5

Fig. 27 Trajectory of task 2:
pushing of the object toward
the target position

0

0.5

1

1.5

2

2.5

0

0.5

1

1.5

2

2.5

1.5

1

0.5

0

-0.5
-0.5

Fig. 28 Simulation settingwith L-shaped and circular
objects

1.5

θ2
1[ y1 , y2 ]Tobject 1[q1 , q2 , q3 ]Tarm

object 2

0.5

θ1[q4 , q5 ]T

0

-0.5
-0.5

0

0.5

1

1.5

2

2.5

496
Fig. 29 Trajectory for task 1

J Intell Robot Syst (2011) 62:467–500
1.5

1

0.5

0

-0.5
-0.5

0

0.5

1

1.5

2

2.5

on the boundary while avoiding to contact the object at different point from z1,2 (s† ),by the effect of Eq. 3.44. After mode transition from 1 to 2, the hand pushed theobject toward the target position using the redundant mapping between [y1 , y2 ]Tand [y3 , y4 ]T with Eq. 3.14. It can be seen that the realized trajectory of the robot issmooth, while the trajectory of the hand is zigzag.
4.3 Case 3: Using L-shaped Tool for Manipulation
In the third problem setting, the link length of the manipulator is the same as case 1
and 2, whereas the circular end effector is omitted (Fig. 28). There are two objects,
L-shaped object (object 1) and a circular object (object 2). When the end of themanipulator contacts with the L-shaped object, the hand sticks to the object and they
move together thereafter. The relative posture of the object is fixed when the handcontacts with the object.
There are three modes in this problem. In mode 2, L-shaped object is moving withthe hand. In mode 3, the circular object is moving by the contact with the L-shaped
object. Exploration and learning are done by the followings:
1. Move randomly for 3,000 steps (within mode 1), including the initializations per
100 steps.
2. Build mapping between [θ1 , θ2 ]T and [y1 , y2 ]T , estimate boundary between mode
1 and mode 2, and generate parameterization on the boundary between modes 1
and 2. h
3. Choose a target subgoal on the boundary between mode 1 and 2. Go to theboundary and then explore mode 2. Totally 3,000 steps are spent for this
exploration including initializations per 100 steps.15
4. Build mapping between [y1 , y2 ]T and [y3 , y4 , y5 ]T , estimate boundary between
mode 2 and mode 3, and generate parameterization on the boundary between
modes 1 and 2.

15 For mode 2, explicit mode keeping controller is not required because once the hand contacts with
the L-shaped object, they keep contact until the initialization.

J Intell Robot Syst (2011) 62:467–500
Fig. 30 Trajectory for task 2

497

1.5

1

0.5

0

-0.5
-0.5

0

0.5

1

1.5

2

2.5

5. Choose target subgoals on the boundaries between mode 1 and 2 and between
mode 2 and 3. The robot first aims the first subgoal (toward mode 2) and thenthe second subgoal (toward mode 3). After reaching mode 3, explore mode 3
randomly while trying to keep mode 3. Totally 6,000 steps are performed for this
exploration while all of the configurations are initialized per 100 steps.
6. Build mapping between [y3 , y4 , y5 ]T and [y6 , y7 ]T .
Since the initial positions of the L-shaped object and the circular object are fixed,
parameterization of the mode boundaries are done only for the specific configuration
decided by the initial configuration. Target subgoals on the mode boundaries wereselected by calculating the mean of the total length of the boundary (for example,
if a boundary is parameterized from 0 to 5, subgoal is decided by specifying theparameter as 2.5).
There are two tasks given to the robot:––

Task 1: Move object 2 to [q4 , q5 ]T = [1.2, 0.2]T .
Task 2: Move object 2 to [q4 , q5 ]T = [1.5, 0.1]T .

Learning of kinematics of the manipulator are the same as the first and thesecond setting. After that, the second group of observation variables are groupedas [y3 , y4 , y5 ]T ∈ Y 3 when they change by contact with the object.16 Thus, modes are
created as mode 1 for free motion of the manipulator and mode 2 for motion of the
L-shaped object. Later, mode 3 is found for motion of the circular object. In the bothcases in Figs. 29 and 30, the L-shaped object was utilized to move the circular object
to the desired position.

16 At the moment of contact, interference between the arm and the L-shaped object is resolved byrotating the object around the tip (closer to the arm). The configuration of the L-shaped object
is specified by its position of its corner, thus three configuration variables changes at a time whencontact occurs.

498

J Intell Robot Syst (2011) 62:467–500

5 Discussion
In the simulation, it was shown that the proposed learning architecture enables
various task execution (including pushing manipulation and obstacle avoidance) byfinding relations among variables and using the relations for planning with various
observation variables.
Motor babbling [7] has been discussed as human learning of motor coordination.
While the first stage of mapping learning for the arm in the proposed method can beequivalent to inverse-kinematics learning (e.g. [23] for learning with neural networks
and [8] for imitation learning for analyzing development of infants), the totalframework deals with wider problem of finding relations among various observation
variables. The proposal of this paper can be regarded as an construction method ofbody scheme [32], where ‘self’ is identified through the criterion of ‘what can be controlled’ and ‘what cannot be controlled’. Speaking more concretely, the distinction
between ‘what can be controlled’ and ‘what cannot be controlled’ is obtained throughthe grouping of the observation variables. The indicator sets of IC(i) , i = 1, · · · , jgive the observation variables that can be controlled and the remaining indicators
denote that those observation variables are impossible to control so far. The ‘senseof agency’ (e.g. [4]) is expressed as potentially controllable variables of y(1) , · · · , y(k)in this framework.
The proposed learning architecture includes a criterion for autonomous exploration (e.g.[24]), which is based on the structure of the task. Exploration in the
proposed learning method is done while keeping a mode or aiming at different
modes, which helps building an exploration strategy.
On the other hand, the applications presented in the simulation is rather simple
and easy. The proposed architecture is applicable to more complex and highdimensional problems, but to apply the framework to higher-dimensional problems, it is required to consider parameterization of high-dimensional sub-manifolds(boundaries between modes). Other possible extensions are the followings:
–

–

–

–
–

The influence of noise should be taken into account in order to implement the
proposed framework in the real world. One possible way to deal with noise
in motion synchronousness detection is to approximate the effect of noise by
preceding measurement. It would be more useful if online approximation ofstochastic model of the motion and observation could be implemented.
Observation variables directly correspond to configuration variables in thispaper. Extraction of observation variables from various image feature vectors
should be taken into consideration.
The proposed framework does not include integration of multi-modal sensor
information. E.g., tactile information is of great importance to generate therepresentation of the object [18]. Generation of modes can be done more
efficiently with integration of other sensor information.
A control strategy that utilizes a partial information of state variable is known as‘backstepping’ in nonlinear control research fields [12].
Normally we human ‘grasp’ an object when we intend to use the object as atool. To fix the relative positions between the hand and the object, mechanicalstructures such as fingers or grips have to be implemented. We avoided suchmechanisms in the robot for simplicity, but grasping behavior of the robot handshould be discussed in the future.

J Intell Robot Syst (2011) 62:467–500

–

–

499

For the discussion of motor development of human body, control of force
through musculo-skeletal system is an important issue [13]. The idea of planningspace shift might be applied also to the different levels of motor control.
From the viewpoint of widening applicability of the proposed framework, development of generalization ability will be one of the most important issues.
The simulation results were realized based on many off-line trials. It will be
preferable to decrease the number of trials when the robot learns to manipulatedifferent objects based on the obtained knowledge. The interpolation of theestimated reachable region based on the parameterization of the mode boundaryis an attempt to decrease the number of trials by effectively utilizing existentsampled data.

6 Conclusion
In this paper, an approach to hierarchy generation is proposed as planning-spaceshift learning. The learning framework consists of generation of modes based on
motion synchronousness, estimation of boundaries between modes, and planning via
multiple modes with estimated reachable regions. In simulation, three examples wereshown to evaluate the proposed motion generation scheme. In the first example, anobject was utilized as a tool to move another object in a simple one-dimensionalmotion. In the second example, an obstacle avoidance behavior and a pushingmanipulation, normally realized by different control schemes with different statevariables, were realized with the unified control architecture of hierarchical learning.
In the third example, an L-shaped object was utilized as a tool to move a circular
object to a destination with planar motion. In all of these examples, different
hierarchies (different dependencies of groups of observation variables) were realized
by the proposed framework. The proposed scheme is expected to be a fundamentalbuilding block for generation of complex motions of robots. In the future work, we
consider executing experiments using real data. For this the influence of noise should
be taken into account in order to implement the proposed framework in the realworld.
The proposed architecture does not utilize any explicit representation of ‘tool’and it uses just the information of motion synchronousness. An advantage of thisapproach is that the designer does not have to model tools, while in other researches‘objects’ and ‘tools’ must be fixed and modeled in advance. For example, the robot
may use an object as a tool that has not been supposed by the designer. On the other
hand, this approach requires more trial of the robot to find objects and their motional
properties. To extend and improve the proposed architecture, effective explorationand effective approximation of the motional properties will play an important role.

References
1. Asada, M., MacDorman, K., Ishiguro, H., Kuniyoshi, Y.: Cognitive developmental robotics as a
new paradigm for the design of humanoid robots. Robot. Auton. Syst. 37, 185–193 (2001)
2. Atkeson, C.G., Moore, A.W., Schall, S.: Locally weighted learning. Artif. Intell. Rev. 11, 11–73(1997)

500

J Intell Robot Syst (2011) 62:467–500

3. Bemporad, A., Morari, M., Dua, V., Pistikopoulos, E.: The explicit linear quadratic regulator forconstrained systems. Automatica 38(1), 3–20 (2002)
4. Blakemore, S.J., Wolpert, D.M., Frith, C.D.: Abnormalities in the awareness of action. Trends
Cogn. Sci. 6(6), 237–242 (2002)
5. Brooks, R.A.: A robust layered control system for a mobile robot. IEEE J. Robot. Autom. RA-2,
253–262 (1986)
6. Dayan, P., Hinton, G.E.: Feudal reinforcement learning. In: Giles, C.L., Hanson, S.J., Cowan,
J.D. (eds.) Advances in Neural Information Processing Systems, vol. 5, pp. 271–278 (1993)
7. Demiris, Y., Dearden, A.: From motor babbling to hierarchical learning by imitation: a robot
developmental pathway. In: Berthouse, L., et al. (eds.) Proc. of the Fifth Int. Workshop on
Epigenetic Robotics, pp. 31–37. Japan (2005)
8. Demiris, Y., Meltzoff, A.: The robot in the crib: a developmental analysis of imitation skills in
infants and robots. Infant Child Dev. 17, 43–53 (2008)
9. Drescher, G.L.: Made-Up Minds: A Constructivist Approach to Artificial Intelligence. MIT(1991)
10. Gibson, J.J.: The theory of affordances. In: Perceiving, Acting, and Knowing: Toward EcologicalPsychology, pp. 62–82. Lawrence Erlbaum, NJ (1977)
11. Hauskrecht, M., Meuleau, N., Boutilier, C., Kaelbling, L.P., Dean, T.: Hierarchical solutionof markov decision processes using macro-actions. In: Proc. of 14th Annual Conference on
Uncertainty in Artificial Intelligence, pp. 220–222 (1998)
12. Khalil, H.K. (ed): Nonlinear Systems. Prentice Hall (2001)
13. Kuniyoshi, Y., Sangawa, S.: Early motor development from partially ordered neural-body dynamics: experiments with a cortico-spinal musculo-skeletal model. Biol. Cybern. 95, 589–605(2006)
14. Lavalle, S.M.: Planning Algorithms. Cambridge University Press (2006)
15. Lungarella, M., Metta, G., Pfeifer, R., Sandini, G.: Developmental robotics: a survey. Connect.
Sci. 15(4), 151–190 (2003)
16. Mangasarian, O.L., Musicant, D.R.: Lagrangian support vector machines. J. Mach. Learn. Res.
1, 161–177 (2001)
17. Maravita, A., Iriki, A.: Tools for the body (schema). Trends Cogn. Sci. 8(2), 79–86 (2004)
18. Metta, G., Fitzpatrick, P.: Early integration of vision and manipulation. Adapt. Behav. 11(2),109–128 (2003)
19. Michael Kass, A.W., Terzopoulos, D.: Snakes: active contour models. Int. J. Comput. Vis. 1(4),321–331 (1988)
20. Miyamoto, H., Morimoto, J., Doya, K., Kawato, M.: Reinforcement learning with via-point
representation. Neural Netw. 17, 299–305 (2004)
21. Nabeshima, C., Kuniyoshi, Y., Lungarella, M.: Adaptive body schema for robotic tool use. Adv.
Robot. 20(10), 1105–1126 (2006)
22. Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7, 308–313(1965)
23. Oyama, E., Agah, A., MacDorman, K.F., Maeda, T., Tachi, S.: A modular neural networkarchitecture for inverse kinematics model learning. Neurocomputing 38–40, 797–805 (2001)
24. Ratitch B., Precup D.: Using MDP Characteristics to Guide Exploration in Reinforcement
Learning. Springer, Berlin (2003)
25. van der Schaft, A., Schumacher, H.: An Introduction to Hybrid Dynamical Systems. Springer(2000)
26. Siméon, T., Laumond, J.P., Cortés, J., Sahbani, A.: Manipulation planning with probabilistic
roadmaps. Int. J. Rob. Res. 23(7–8), 729–746 (2004)
27. Stoytchev, A.: Behavior-grounded representation of tool affordances. In: Proc. of IEEE Int.
Conf. on Robotics and Automation, pp. 3071–3076. Barcelona, Spain (2005)
28. Stoytchev, A.: Toward video-guided robot behaviors. In: Proc. of the Seventh International
Conference on Epigenetic Robotics, pp. 165–172. Rutgers University, NJ (2007)
29. Vapnik, V.N.: The Nature of Statictical Learning Theory. Springer (1995)
30. Wolpert, D.M., Kawato, M.: Multiple paired forward and inverse models for motor control.
Neural Netw. 11, 1317–1329 (1998)
31. Xu, C., Prince, J.L.: Snakes, shapes, and gradient vector flow. IEEE Trans. Image Process. 7(3),359–369 (1998)
32. Yoshikawa, Y., Hosoda, K., Asada, M.: Does the invariance in multi-modalities represent the
body scheme?—A case study with vision and proprioception—. In: Proc. of the 2nd Int. Symp.
on Adaptive Motion of Animals and Machines, vol. SaP-II-1 (2003)