Auton Robot (2013) 34:327–346
DOI 10.1007/s10514-013-9328-1

DCOB: Action space for reinforcement learningof high DoF robots
Akihiko Yamaguchi · Jun Takamatsu ·Tsukasa Ogasawara

Received: 21 November 2011 / Accepted: 28 February 2013 / Published online: 29 March 2013
© Springer Science+Business Media New York 2013

Abstract Reinforcement learning (RL) for robot control is
an important technology for future robots since it enables us
to design a robot’s behavior using the reward function. However, RL for high degree-of-freedom robot control is still
an open issue. This paper proposes a discrete action space
DCOB which is generated from the basis functions (BFs)
given to approximate a value function. The remarkable feature is that, by reducing the number of BFs to enable therobot to learn quickly the value function, the size of DCOB
is also reduced, which improves the learning speed. In addition, a method WF-DCOB is proposed to enhance the performance, where wire-fitting is utilized to search for continuous
actions around each discrete action of DCOB. We apply the
proposed methods to motion learning tasks of a simulated
humanoid robot and a real spider robot. The experimental
results demonstrate outstanding performance.
Keywords Reinforcement learning · Action space ·Motion learning · Humanoid robot · Crawling

1 Introduction
High-DoF (degree of freedom) robots, typified by humanoid
robots, have the ability of performing a variety of motions. In
most cases, their behavior is preprogrammed by their developers. However, designing behaviors by the end-users will
Electronic supplementary material The online version of thisarticle (doi:10.1007/s10514-013-9328-1) contains supplementarymaterial, which is available to authorized users.
A. Yamaguchi (B) · J. Takamatsu · T. Ogasawara
Graduate School of Information Science, Nara Institute of Science andTechnology, 8916-5 Takayama, Ikoma, Nara 630-0192, Japane-mail: ay@akiyam.sakura.ne.jp

be essential in the future when the robots become familiar
to us. Reinforcement learning (RL) is such a technology,
with which the end-users can design a behavior by a reward
function that encodes the behavior’s objective. We treat alearning-from-scratch case of RL where the robot learns atask with no task-specific prior knowledge. In particular,
the task-specific prior knowledge consists of data comingfrom a reward function of the task, such as a value function.
RL methods for the learning-from-scratch case have wider
applicability than those that require prior knowledge. Many
researchers apply RL methods to robot control, e.g. (Zhang
and Rössler 2004; Kimura et al. 2001; Gaskett et al. 2000).
However, RL to control a high-DoF robot is still an open
problem.
A major and promising approach is using the dynamic
motor primitives with an RL method (Peters et al. 2003;
Kober and Peters 2009). A notable feature is its applicability to motion learning tasks of a high-DoF robot. This technique is based on imitation learning, i.e. the robot does notlearn from scratch; the method learns a policy represented
by a vector field initialized around the reference trajectory.
Figure 1a illustrates the vector field and the instances of the
exploration trajectory in the state space. We refer to suchkind of exploration as the trajectory-wise exploration. Meanwhile, discrete action spaces are used in some RL applications (Uchibe and Doya 2004; Takahashi and Asada 2003;
Tham and Prager 1994; Kirchner 1998). The advantages of
discrete action spaces are:(A) A graph search-like exploration is available by using anaction value function (Sutton and Barto 1998; Sedgewick
and Wayne 2011), which enables the robot to explore
widely in the possible behavior space. Figure 1b illustrates the instances of the exploration trajectory in thestate space where a discrete action space is used.

123

328

Auton Robot (2013) 34:327–346

(a)

(a)

(b)

Fig. 1 Illustration of a trajectory-wise exploration (a) and a graphsearch-like exploration (b) in the state space of a robot. In both figures, the lines denote the instances of the exploration trajectory. a The
arrows denote a vector field initialized around a reference trajectory,
and the exploration policy is assumed to be the Gaussian policy. b Eachdotted arrow denotes an action, and the exploration policy (learned fromscratch) is assumed to be the Boltzmann policy(B) In general, learning in a continuous action space is moredifficult than learning in a discrete action space (Suttonand Barto 1998).
Thus, a discrete action space is supposed to be one of the realistic solutions to the learning-from-scratch case. However,there are few general ways to design a discrete action space.
Though a typical way is dividing independently each dimension of the command space of the robot, such a method has
a practical issue: the size of the action space increases exponentially with respect to the dimensionality of the command
space. In addition, there is no discrete action space that can
prevent performance degradation caused by the discretization. Thus, conventional discrete action spaces are inefficientin RL to control a high-DoF robot.
This paper aims to develop an RL method which is efficient in the learning-from-scratch case of high-DoF robots.
First, we propose a discrete action space DCOB which is generated from the basis functions (BFs) given to approximate
a value function. DCOB works with any RL method that has
the capability to learn in a discrete action space (see Fig. 2).
Each action in DCOB is a trajectory that is directed to thecenter of a target BF, which is the origin of the name. The
remarkable feature is that, by reducing the number of BFs
to enable the robot to learn quickly the value function, thesize of DCOB is also reduced, which improves still further
the learning speed. Naturally, RL in DCOB has the stability
due to being a discrete space. Thus, DCOB has the capability to learn efficiently in the learning-from-scratch case ofhigh-DoF robots.
Though working efficiently in large domains, DCOB suffers from degradation caused by the discretization. Thus, we
extend DCOB so that the search area changes from the discrete points to continuous regions around the discrete actionsin DCOB, in order to improve the ability to acquire perfor-

123

(b)

Fig. 2 Overview of DCOB. a DCOB is a discrete action space generated from BFs. An action in DCOB selected by the RL agent is converted
into a command sequence for the robot. b Acquired motion is generated
by a sequence of the actions in DCOB

mance. This method is named WF-DCOB because of utilizing wire-fitting (Baird and Klopf 1993) to approximate thevalue function in the continuous action space. WF-DCOB
performs the graph search-like (wide) exploration in the continuous action space; this nature is inherited from DCOB.
Thus, WF-DCOB also has the capability to learn efficiently
in the learning-from-scratch case of high-DoF robots.
The most remarkable contribution of this paper is achieving the graph search-like exploration (Fig. 1b) even in large
domains by cooperating with an action value function-based
RL method. Most of the similar methods (e.g. Miyamoto et al.
2004) and state-of-the-art methods (e.g. Theodorou et al.
2010) use a simple exploration policy, such as a policy using
Gaussian noise, which may cause a narrow exploration likeFig. 1a. We consider that such a poor exploration is not suitable for the learning-from-scratch case of high-DoF robots.
The detailed discussion is given in Sect. 8.
Since having some requirements, the proposed methods
are mainly applicable to articulated robots, such as legged
robots including humanoid robots, and manipulators. The
precise requirements are given in Sect. 4.2. We apply the
proposed methods to motion learning tasks of a simulated
humanoid robot, a real spider, and a dinosaur robot. Especially in the humanoid robot experiments, we investigate theircapabilities in several DoF configurations. The experimental results demonstrate outstanding advantages of the proposed methods both in learning speed and ability to acquire
performance, compared to conventional action spaces. Furthermore, we find that the difference in performance between
DCOB and WF-DCOB depends on the conditions, such as the
DoF configuration. The experimental results provide guidelines for choosing DCOB or WF-DCOB.

Auton Robot (2013) 34:327–346

This paper is organized as follows. Section 2 introduces
RL and function approximators. Section 3 outlines the proposed methods. Section 4 describes an action converter usedin DCOB and WF-DCOB. Section 5 defines DCOB and
WF-DCOB. Section 6 introduces BF allocation methods.
Section7 demonstrates the results of the experiments. Section
8 discusses the theoretical basis of the proposed methods, its
applicability, and the related work. Section 9 concludes thispaper.

329

As an exploration policy, we introduce the Boltzmann
selection method (Sutton and Barto 1998), which has a temperature parameter τ ; letting τ = 0 gives the greedy policy. For BFs, we use Normalized Gaussian Network (NGnet)(Sato and Ishii 2000) which is a popular function approximator in RL applications, e.g. (Morimoto and Doya 2001).
In NGnet, φk (x) is given by
G x; μk , Σ k,φk (x) = (1)k  ∈K G x; μk  , Σ k This section briefly introduces an RL algorithm used in thispaper, and a linear and a nonlinear function approximator.

where G(x; μ, Σ) denotes a Gaussian function with mean μand covariance matrix Σ. In this paper, K is predefined and{μk , Σ k | k ∈ K} are treated as fixed parameters.
In the following, we refer to the linear function approximator with NGnet as LFA-NGnet.

2.1 Reinforcement learning

2.2.2 Wire-fitting

The purpose of the RL method is that a learning system(agent) whose input is an observable state xn ∈ X and areward Rn ∈ R, and whose output is an action un ∈ U,
theacquires the policy π(xn ) : X → U that maximizes

k−1 R
where
n
∈
γ
expected discounted return E ∞n+kk=1
N = {0, 1, . . . } denotes the time step and γ ∈ [0, 1) denotes
a discount factor. In this paper, X denotes a continuous state
space, U denotes a continuous action space, and A denotes
a discrete action space. In value-function-based RL methods, an action value function Q(x, u) : X × U → R islearned to represent the expected discounted return by taking an action u from an observable state x. Then, the optimal action rule is obtained from the greedy policy π(x) =arg maxu Q(x, u). We use the Peng’s Q(λ)-learning algorithm (Peng and Williams 1994), which is an on-line RL
method, i.e. the update procedure is applied after each action.

Wire-fitting (Baird and Klopf 1993) is a function approximator of Q(x, u) for a continuous state x ∈ X and a continuous action u ∈ U, which interpolates a set of control
wires W = {i|i = 1, 2, . . . }. Each control wire i ∈ W
consists of two function approximators qi (x) : X → R
and ui (x) : X → U, where qi encodes an action value,
and ui encodes an action. The notable feature of wire-fittingis that we can maximize Q(x, u) w.r.t. u by evaluating only{qi (x) | i ∈ W}; this feature is independent from the kinds offunction approximators qi (x), ui (x). In this paper, we employ
LFA-NGnet for qi (x) and a constant vector for ui (x); that is,qi (x) = θi φ(x), ui (x) = Ui . This configuration makes it
simple to design WF-DCOB as an extension of DCOB. The
detail is described in Appendix A.

2.2 Function approximators

The discrete action space DCOB is compact, has the ability to acquire high performance motions, and is therefore
applicable to RL in large domains. The proposed action space
DCOB is generated from a set of basis functions (BFs) given
to approximate a value function. DCOB enables to acquire
higher performance than a conventional discrete action spacethat has the same size as DCOB. The key technique is thatthe motion caused by each action is adjusted for the resolution of the BFs; such actions are considered to be suitable
for learning the policy with the BFs. Section 4 describes thedetails of the methods that clarify the reasons of the higher
performance. Moreover, reducing the number of BFs by BF
allocation methods reduces the size of DCOB, since DCOB
is generated from the BFs. Thus, DCOB has advantages inboth learning speed and ability to acquire performance. Naturally, a graph search-like (wide) exploration is available with
DCOB.

2 Preliminaries

Next, we describe two function approximators for the action
value functions Q(x, u). For a continuous state space X anda discrete action space A (the DCOB case), we use a linear
function approximator because of its stability. When boththe state and the action space X , U are continuous (the WFDCOB case), we employ wire-fitting.
2.2.1 Linear function approximator (LFA) with NGnet
For a continuous state x ∈ X and a discrete action a ∈A, we let Q(x, a) = θa φ(x), where φ(x) = (φ1 (x), . . . ,φ|K| (x)) denotes the output of BFs at a state x, K = {k |k = 1, 2, . . .} denotes a set of BFs, and θa ∈ R|K|×1 denotes aparameter related to an action a. In the learning-from-scratchcase, every θa is initialized by zero.

3 Overview of proposed methods

123

330

Fig. 3 Relations of the proposed methods; BFTrans, DCOB, and WFDCOB. BFTrans is an action converter from the agent’s action into
a command sequence for the robot. DCOB is a discrete action spaceobtained by discretizing the input space of BFTrans. WF-DCOB directly
learns in BFTrans, but the actions are constrained around the actions in
DCOB. Thus, WF-DCOB is regarded as an extension of DCOB.

DCOB consists of an action converter named BFTransand discretization using BFs. We assume that the parametersof each BF include a center state like a Gaussian function.
BFTrans outputs a command sequence from an input consisting of target joint angles and a motion speed. This converter
provides a continuous action space for RL; the input spaceof BFTrans is the action space in this case. The joint angle
trajectory generated by this command sequence is adjusted
for the resolution of the BFs [see Fig. 3 (BFTrans)]. The
name of this action space stands for Transition between BFs.
The input space of BFTrans is discretized by using the set of
BF centers; the obtained discrete action space is DCOB [seeFig. 3 (DCOB)]. Thus, each action in DCOB is a trajectorythat is Directed to the Center Of a target BF.
WF-DCOB explores continuous actions around each discrete action of DCOB. The aim of WF-DCOB is to acquire
higher performance than DCOB while maintaining the wide
exploration ability. In addition, WF-DCOB is designed to
be stable and speedy in the learning-from-scratch case,which is comparable to DCOB. The key ideas of WF-DCOB
are: (1) restricting the exploration in regions around thecorresponding DCOB’s actions [see Fig. 3 (DCOB) and(WF-DCOB) to compare the regions and the actions], and(2) the exploration policy selects an action from a set ofrepresentative actions in the regions. (1) makes the learning
process stable, and (2) maintains the wide exploration ability of DCOB; actually, though (1) restricts the exploration,
WF-DCOB explores a policy wider than DCOB. To accomplish these ideas, we utilize wire-fitting (Baird and Klopf
1993) as the value function approximator. Section 5 describes
how WF-DCOB achieves these ideas.
Note that only a single action is illustrated in Fig. 3. The
obtained policy by an RL method with DCOB generates apath consisting of a sequence of actions in DCOB that maximizes the return (Fig. 2b). Roughly speaking, the problem of
an RL method with DCOB is similar to a path-planning task
in a gridworld; namely, finding the best action for each state

123

Auton Robot (2013) 34:327–346

Fig. 4 Illustration of how an action in the BFTrans is executed. First,
a reference trajectory is generated, then it is abbreviated. The reference
trajectory may change the state greatly, so the obtained motion is coarse.
To make the motion fine, the trajectory is abbreviatedfrom an action set. The differences are that DCOB is used
as an action set, and NGnet is used for approximation overa continuous state space. If there is a gap on the state space
due to an obstacle or a collision, the RL method can find apath as a sequence of the DCOB actions that goes aroundthe gap. DCOB can cope with a configuration space of ageneric motion learning task such as crawling. Thus, DCOB
is applicable to generic motion learning tasks. This is also
the same as the WF-DCOB case. In the following sections,
we describe the details of the proposed methods.

4 BFTrans: action converter using basis functions
This section introduces the action converter BFTrans whichis the core system of DCOB and WF-DCOB. BFTrans converts an input action u = (g, qtrg ) into a sequence of control
commands, where g ∈ R is called the interval factor that
determines the speed of motion, and qtrg ∈ Q is the target point of a reference trajectory. A predefined low-level
controller outputs the command sequence to follow the trajectory. The key technique used here is that the commandsequence is terminated after a short period during which thestate of the robot moves into the BF nearest to the startingstate of the action. This abbreviation makes the commandsequence suitable for the resolution of the given BFs. Thus,
BFTrans provides a continuous action space for RL methods.
Let UBFTrans  R × Q denote the space.
4.1 Features
The features of BFTrans are summarized as follows:(F1) The dynamics of the actions improves learning a policy.
(F2) The actions can reflect the range of the state space, suchas joint angle limitations.

Auton Robot (2013) 34:327–346(F1) is satisfied by abbreviating the trajectory which adjusts
each action for the resolution of BFs. Let us see Fig. 4. The
original trajectory is a curve segment of two points in thestate space. On average, the length of a curve segment iscomparatively long (Fig. 4 “Reference Trajectory”). Let us
recall that a motion is generated by a sequence of BFTrans’
input actions. If a motion of the robot were represented by asequence of such long curve segments, the whole trajectoryof the motion would become coarse; namely, the trajectorywould consist of less number of actions. Increasing the number of actions makes the variety of motions wider, which
may improve the performance. In order to make a motion
fine, each curve segment is abbreviated (Fig. 4 “AbbreviatedTrajectory”).
On the other hand, making each trajectory too short may
cause a long learning time. A moderate length is the distance
between two adjacent BFs, since the representable fineness ofa policy over the state space is almost the same as the resolution of the BF set. Thus, the original trajectory is abbreviatedto the length between the starting point and the nearest BF.
About (F2), if we select a target point inside the rangeof the state space, the action rarely exceeds the range. Thisfeature is kept for discretizing the target point space by the
BF set, since in many cases, the BFs are allocated inside therange of the state space.
4.2 Assumptions
BFTrans assumes the following:

331
Table 1 Examples of BFTrans setup
No.

Observable state (x)

CP

CD

Ctrl

Class

#1

(pg , q, vg , q̇)

q

q̇

PD

MDP

#2

(q, q̇)

q

q̇

PD

POMDP

#3

(q)

q

0

P

POMDP

pg : the global position and rotation, q: the joint angles, vg : the global
linear and angular velocity, q̇: the joint angular velocities, PD/P: a
PD-/P-controller.

employ a TD(λ) method; the detailed discussion is given in
Sect. 8. Thus, there are some variations in choosing the above
assumptions. Table 1 shows the possible combinations. In#1, the whole state is observable, which satisfies the Markov
property. Meanwhile in #2, only the joint angles and the joint
angular velocities are observable; in #3, only the joint angles
are observable. The cases #2 and #3 are POMDPs. The bestpolicy may be obtained with the full-observation (#1), but
in an real robot case, sometimes it is difficult to observe
the whole state. In such case (#2 or #3), the applicability to
POMDPs is desirable. The case #1 is verified in the motion
learning tasks of a simulated humanoid robot, and the case
#3 is verified in the crawling task of a real robot.
4.3 Algorithm outline
When an action un = (g, qtrg ) is input to BFTrans at step n (attime tn ), a reference trajectory is calculated. The duration ofthis trajectory is abbreviated to a shorter period. Then the trajectory is followed by the low-level controller which outputs
the command sequence. The whole procedure is describedin Algorithm 1.

(A) Each BF k ∈ K has a fixed center μk ∈ X .
(B) The state x ∈ X is observable.
(C) Q, CP (x), and CD (x) are predefined. Q: a controllable
subspace of X where a reference trajectory is calculated. CP (x): a function that extracts q ∈ Q from astate x ∈ X by q = CP (x) : X → Q. CD (x): a function that extracts the derivative of q ∈ Q from a statex ∈ X by q̇ = CD (x).
(D) A low-level controller ũ(t) = Ctrl(x(t), qD (t + δt))is given to follow the reference trajectory qD (t) (e.g.
a PD-controller), where ũ denotes a control command,Ũ denotes a control command space, and δt denotes acontrol time-step.

Algorithm 1: Executing an action in the BFTrans
Input:Action un = (g, qtrg ) ∈ R × Q = UBFTrans ,starting state xn = x(tn )1: Estimate the time interval TF of the trajectory from g, xn , qtrg
2: Generating a reference trajectory with which the state changes
from xn to qtrg in TF : qD (tn + ta ), ta ∈ [0, TF ]3: Abbreviating the trajectory to ta ∈ [0, TN ] ⊆ [0, TF ] (TN  TF )4: Following the trajectory with the low-level controller which outputs a command sequence: ũ(tn + ta ) = Ctrl(x(tn + ta ), qD (tn +ta + δt)), ta ∈ [0, TN )5: The action un is finished; n ← n + 1

In this paper, we use NGnet which satisfies (A). Radial BFs
are an alternative to NGnet. The reason of assuming the centers to be fixed is to ensure the convergence of learning.
The assumptions (B), (C) and (D) are actually requirements on the task domain including the robot configuration.
Let us consider to apply BFTrans to a crawling task of ahumanoid robot whose objective is to move forward as far as
possible. The proposed methods are applicable to POMDPs(partially observable Markov decision processes) when we

The reference trajectory qD (tn + ta ), ta ∈ [0, TF ] isdesigned so that the state changes from the starting state
xn = x(tn ) to the target qtrg in the time interval TF . We
represent the trajectory with a cubic function. The detailed
calculation of the trajectory is described in Appendix B.
Instead of using the time interval TF , we introduce theinterval factor g into an action to represent exclusively
the speed of the action. This parameter is suitable to explore
the motion-speed space and is easily discretized. The speedof the action depends on TF , xn , and qtrg . Thus, we

123

332

Auton Robot (2013) 34:327–346

define trg g as thequotient of TF and the maximum norm ofq − CP (xn ) . Namely, we calculate TF with

5.1 Discrete action space DCOB
TF = g qtrg − CP (xn )∞A discrete action space DCOB is defined by discretizing the
input space of BFTrans. The key idea is that we can discretize
the Q space with the centers of the BFs. Though these centers
are originally distributed on the X space, the space converter
CP : X → Q can transfer them onto the Q space.
Let us recall that an action in BFTrans is denoted by u =(g, qtrg ) ∈ R × Q. The interval factor space is discretized bya small discrete set of real numbers I = {g1 , g2 , . . . }, andQ is discretized by a set of the centers of the BFs, {CP (μk ) |k ∈ K}. Let ADCOB denote DCOB: ADCOB = I × K. An
action an in DCOB selected at step n (at time tn ) is executed
as follows:(2)

where · ∞ denotes a maximum norm1 .
The reference trajectory is abbreviated by reducing theterminal time; its detail is described in the following section.
The abbreviated trajectoryis followed by the low-level con
troller as ũ(t) = Ctrl x(t), qD (t + δt) , t ∈ [tn , tn +TN ). In
the simulated small-humanoid experiments, we use a simple
PD-controller. In the real robot experiments, we use controllers embedded on each joint actuator.
4.4 Abbreviating trajectory
We abbreviate the reference trajectory as qD (tn + ta ), ta ∈[0, TN ] where 0 < TN  TF to make the action suitable
for the resolution of BFs. Here, the abbreviation cuts the
trajectory at ta = TN , where TN is a duration in which thestate changes into the BF nearest to the starting state2 .
The abbreviation is performed as follows: (1) estimate
DN (xn ) as the distance between two neighboring BFs aroundthe start state xn , (2) calculate TN from the ratio of DN (xn )and the distance between xn and qtrg . Here, we employ amaximum norm as a distance rather than the L2 -norm since
the trajectory of each joint is calculated independently.
Using the output of BFs φ(xn ), the distance DN (xn ) is
estimated by
DN (xn ) = (dN (1), dN (2), . . . , dN (|K|)) φ(xn )(3)where dN (k) denotes the distance between the center μk ofa BF k and the center of the nearest BF from k. Then, TN isdefined byFabbrv DN (xn )TF ,TN (xn , un ) = min 1, trg(4)
q − CP (xn ) ∞where Fabbrv denotes a scaling factor which typically takes
1. The detailed calculation is described in Appendix B.

5 DCOB and WF-DCOB
This section defines DCOB and WF-DCOB based on
BFTrans.
1 For a vector x = (x , . . . , x ), the maximum norm is defined as1D

x ∞ = maxm |xm |.
2 We do not abbreviate the trajectory by observing the output of BFs

since when the dynamics is a POMDP, using the BFs output to terminate
the action may complicate the dynamics more.

123

Algorithm 2: Executing an action in DCOB
Input:Action an = (g, k) ∈ I × K = ADCOB ,starting state xn = x(tn )1: un ← (g, CP (μk ))2: Execute BFTrans with un (Algorithm 1)

The size of DCOB is |I||K|. Since we use I whose number of elements is small (typically, around 3), the size of
DCOB is a few times the number of BFs. Thus, if the number of BFs is reduced by a BF allocation technique, the sizeof DCOB is also reduced.
5.2 WF-DCOB
WF-DCOB directly learns a policy in the continuous action
space BFTrans with wire-fitting. Thus, WF-DCOB has apotential to exceed performance with DCOB. However, ingeneral, learning in a continuous action space has problems
in initializing parameters and problems with learning stability. WF-DCOB tries to solve these issues by restricting the
exploration around the actions in DCOB. That is to say, eachaction in DCOB is a point in BFTrans; WF-DCOB searches
inside a region around the point. Figure 5 illustrates the comparison of DCOB and WF-DCOB in terms of qtrg .
To do this, we prepare the control wires whose number is the same as the size of DCOB; let W = {i|i =1, . . . , |ADCOB |} denote the set of control wires. Then, we
initialize each control wire i ∈ W so that Ui is equal to thecorresponding action of DCOB. During learning, each control wire is kept inside the constraint region. To define theconstraint region, a set of interval factor ranges is definedfor WF-DCOB as
IR  {(gSm , gEm ) | 0 < gSm  gEm , m = 1, 2, . . . , |I|},(5)

where gSm ∈ R and gEm ∈ R denote the boundary values of thetrg
range. For Ui = (gi , qi ), the interval factor gi is constrained
trg
inside (giS , giE ). The target point qi is constrained insidedcob
a hypersphere of radius dN (ki ) centered at CP (μk dcob ),iwhere kidcob denotes a target BF of the corresponding action

Auton Robot (2013) 34:327–346

333

6.1 Grid allocation
This method allocates BFs on a grid where each dimensionof the state-action space is divided independently. Grid allocation is widely used, e.g. (Matsubara et al. 2007), for easeof use. However, since the number of BFs increases exponentially w.r.t. the dimensionality of the state-action space,
applying this allocation method to large domains is difficult.
6.2 Spring-damper allocation

Fig. 5 Illustration of the comparison of DCOB (top) and WF-DCOB(bottom). In both methods, the trajectory is calculated in the same manner as the BFTrans. The difference is that in DCOB, the target state is
the fixed center of a selected BF, while in WF-DCOB, the target state
can change but is constrained around a corresponding BF

in DCOB. The details of the initialization and the constraints
are described in Appendix C.

5.2.1 Action selection for WF-DCOB
In order to accomplish the graph search-like (wide) exploration, we introduce an action selection method like theBoltzmann selection method for WF-DCOB. A control wire
i is assumed to be a discrete action whose action value isqi (x), and one of the control wires is chosen by the Boltzmann selection method. Then the corresponding ui (x) is theselected action. That is to say, a control wire i ∈ W is selectedby the probability
exp τ1 qi (x)π(i|x) = 1,i  ∈W exp τ qi  (x)(6)

where τ denotes a temperature parameter. As with Boltzmann
selection, letting τ = 0 gives the greedy policy.

6 Supplementary techniques: basis function allocation
Allocating BFs is a major factor of the learning performance,
especially in large domains. A set of BFs is used not only ina value function approximator, but also in DCOB and WFDCOB. This section introduces three allocation methods:
grid allocation, spring-damper allocation, and dynamicsbased allocation. Grid allocation uses an exponential number
of BFs with respect to the dimensionality of a state space,
while the others can choose the number of BFs.

This method allocates a given number of BFs so that they
spread as widely as possible within a certain boundary. Since
this method enables us to decide the number of BFs, applying
it to large domains is easier than that of grid allocation. In
spring-damper allocation, first, we allocate BFs of the given
number randomly. The covariance matrix of each BF is constrained to Σ = σ 2 1 where 1 is a unit matrix, and σ ∈ R
is a positive value shared in every BF. Each BF is regarded
as a hypersphere of radius σ centered at the BF’s mean. The
boundary is defined by a minimum and a maximum valueof each dimension of the state space; if the state consists ofjoint angles, the joint angle ranges are used as the boundary.
Then, the BFs are re-arranged so that the centers spread as
widely as possible and σ becomes as large as possible without overlapping. This calculation uses pseudo-dynamics ofa spring-damper system. Though there is no guarantee of
converging without falling into a local maxima, this method
achieved a desired allocation in the preliminary experiments.
Its complete algorithm is described in (Yamaguchi 2011).
6.3 Dynamics-based allocation
Similar to the case of spring-damper allocation, we firstchoose the number of BFs in dynamics-based allocation.
The dynamics-based method allocates BFs according to the
dynamics of the robot, while spring-damper method does notconsider the real dynamics of the robot. The required resolution of the action value function depends on a reward and the
dynamics. Thus, we consider that allocating BFs by using
the dynamics information generates a better set of BFs. Thisidea is similar to the MOSAIC model (Wolpert and Kawato
1998; Doya et al. 2002).
Since we do not require an explicit dynamics model ofthe robot, first, we generate a data set {x, ũ, v} by moving therobot randomly; here, x is a state, ũ is a command, and v is avelocity of next time step. Then, we train a dynamics model,
v=

Ak
k∈K

x
+ bk φk (x; μk , Σ k ),ũ

(7)with the data set. Here, {Ak , bk , μk , Σ k |k ∈ K} denotes theset of model parameters, and φk is a normalized Gaussian

123

334

Auton Robot (2013) 34:327–346(eq. 1). The parameters are trained by EM algorithm withunit manipulations (Sato and Ishii 2000)3 where the algorithm starts with the given number of BFs |K|. Obtained{μk , Σ k |k ∈ K} is used in RL algorithm.

7 Experiments
This section demonstrates experimental comparisons of the
proposed methods and the conventional methods. There are
two domains as benchmarks: motion learning tasks of a simulated humanoid robot, and a motion learning task of a real
spider robot. Since each action space has a different duration,
the reward functions of the following tasks are calculated ateach time step t rather than at each action, in order to compare the action spaces evenly. The reward for an action is
obtained by summing r (t) during the action.
7.1 Motion learning tasks of humanoid robot
First, we apply the proposed methods to motion learning tasks
of a small-size humanoid robot. Here, the robot learns two
motion learning tasks; the crawling task and the turning task.
The objective of each is to acquire the whole body motion.
Furthermore, several DoF configurations and BF allocations are compared in the crawling task. We employ DCOB,
WF-DCOB, a conventional discrete action space, and wirefitting.
7.1.1 Robot description
Experiments are performed in simulation using a dynamics
simulator ODE4 . Figure 6 shows the simulation model ofthe robot. Its height is 0.328 m. It weighs 1.20 kg. Each joint
torque is limited to 1.03 Nm. The dynamics simulation is
calculated with the time step δt = 0.2 ms.
7.1.2 DoF configurations and BF allocations
Here, we define a set of conditions consisting of a DoF configuration and a BF allocation. Figure 7 illustrates the DoF
configurations. The conditions are defined as the following.
Here, each condition name indicates the DoF configurationand the BF allocation. ‘Grid’ denotes grid allocation, ‘Dyn’
denotes dynamics-based allocation, and ‘SprDmp’ denotes
spring-damper allocation.
3-DoF-Grid: Each set of joint pairs {q1 , q3 , q4 , q6 },{q8 , q13 }, {q9 , q10 , q14 , q15 } is coupled, which gives a

Fig. 6 Simulation model of the humanoid robot

bilateral symmetry. The BFs are allocated on a 5 × 5 × 5grid over the reduced joint angle space. The number of
BFs is 125.
4-DoF-Grid: Each set of joint pairs {q1 , q3 }, {q4 , q6 },{q8 , q9 , q10 }, {q13 , q14 , q15 } is coupled, which results ina single DoF on each leg. The BFs are allocated on a
4 × 4 × 4 × 4 grid over the reduced joint angle space.
The number of BFs is 256.
5-DoF-Dyn: Each set of joint pairs {q1 , q4 }, {q3 , q6 },{q8 , q13 }, {q9 , q14 }, {q10 , q15 } is coupled, which gives abilateral symmetry. The BFs are allocated by dynamicsbased allocation method over the reduced state space.
Specifically, 202 BFs are allocated5 .
5-DoF-Grid: The DoF configuration is the same as
5-DoF-Dyn. The BFs are allocated on a 3 × 3 × 3 × 3 × 3
grid over the joint angle space. The number of BFs is243.
5-DoF-SprDmp: The DoF configuration is the same as
5-DoF-Dyn. The BFs are allocated by spring-damper
allocation method over the reduced joint angle space.
Specifically, 300 BFs are allocated.
6-DoF-SprDmp: A coupled joint pair {q7 , q12 } is added
to the 5-DoF, which also gives a bilateral symmetry. The BFs are allocated by spring-damper allocation
method over the reduced joint angle space. Specifically,
300 BFs are allocated.
7-DoF-SprDmp: A coupled joint pair {q2 , q5 } is added
to the 6-DoF, which also gives a bilateral symmetry. The BFs are allocated by spring-damper allocation
method over the reduced joint angle space. Specifically,
600 BFs are allocated.
Note that in each condition, the set of BFs is commonlyused in a value function approximator (LFA-NGnet and wire-

3 Actually, unit division and unit deletion are implemented.

5 We start the EM algorithm with 200 BFs, and obtain the 202 trained

4 Open Dynamics Engine: http://www.ode.org/

BFs.

123

Auton Robot (2013) 34:327–346

335

Fig. 7 DoF configurations of
the humanoid robot. Each
encircled number shows anindex of dimension; joints withthe same numberare coupled

fitting) and to generate DCOB and WF-DCOB. In ND -DoF
configuration, the command input ũ is a ND -dimensional
joint torque. The state is given as follows:
x = (c0z , qw , qx , q y , qz , q1:N,Dċ0x , ċ0y , ċ0z , ωx , ω y , ωz , q̇1:N
) ,
D

(8)

where (c0x , c0y , c0z ) denotes the position of the center-ofmass of the body link, (qw , qx , q y , qz ) denotes the rotationof the body link in quaternion, (ωx , ω y , ωz ) denotes the rotational velocity of the body link, and q1:ND denotes the joint
angle vector of the ND -DoF configuration. The reason for
the absence of c0x and c0y from state x is that a policy for the
crawling task or the turning task does not have to depend on
the global location of the robot.
In the crawling task, every condition is used. In the turning task, only 4-DoF-Grid is used since the other conditions
constrain the robot’s movement in the sagittal plane, i.e. therobot cannot turn.
7.1.3 Task description
Crawling task: The objective of the crawling task is to move
forward along the x-axis as far as possible. According to thisobjective, the reward is designed as follows:r (t) = rmv (t) − rsc (t) − rfd (t),(9)

rmv (t) = 50ċ0x (t),(10)

rsc (t) = 2 × 10−5 ũ(t) ,(11)where rmv (t) is the reward for forward movement, rsc (t) is
the step cost, rfd (t) is the penalty for falling down. rfd (t) takes
4 if the body or the head link touches the ground, otherwise
it takes 0. The penalty for falling down is given once in eachaction. Each episode begins with the initial state where therobot is standing up and stationary, and ends if t > 20s or
the sum of reward is less than −40.
Crawling task for 4-DoF: Since the robot is not symmetrically constrained only in the 4-DoF configuration, a penalty
for rotational movement should be added. Similarly, reward
for forward movement is changed. Concretely, we use thefollowing reward definition only for the 4-DoF case:(t) − rrt (t) − rsc (t) − rfd (t),r (t) = rmv(12)(t) = 50(ċ0x (t)ez1 (t) + ċ0y (t)ez2 (t)),
rmv

(13)

rrt (t) = 5|ωz (t)|,(14)

 (t) is the reward for forward movement, (e , e ,where rmv
z1 z2
ez3 ) is the z-component of the rotation matrix of the body
link6 , rrt is the penalty for rotation. The step cost rsc (t) and thefalling down penalty rfd (t) are as defined above. In the 4-DoF
configuration, each episode begins with the initial state where
the robot lies down and is stationary, and ends if t > 20s or
the sum of reward is less than −40.
Turning task: The objective of the turning task is to rotate
on the z-axis as fast as possible. According to this objective,
the reward is designed as follows:(t),r (t) = rtn (t) − rfw (t) − rsc (t) − rfd(15)

rtn (t) = 2.5ωz (t),(16)

rfw (t) = 0.5 (ċ0x , ċ0y ) ,(17)

where rtn (t) is the reward for turning, rfw (t) is the penalty for (t) is the penalty for fallingthe x-y global movement, and rfd

down. rfd (t) takes 4 if the body link touches the ground, andtakes 0.1 if the head link touches the ground; otherwise it (t) is given once in each action. The step cost
takes 0. rfd
rsc (t) is the same as that in the crawling task. Each episodebegins with the initial state where the robot lies down and is
stationary, and ends if t > 20s or the sum of reward is lessthan −40.
7.1.4 Configurations of action spaces and function
approximators
The following methods are compared.
DCOB: For each ND -DoF configuration, DCOB is configured as follows:
CP (x) = q1:ND ,(18)

CD (x) = q̇1:ND ,(19)

Ctrl(x(t), q (t + δt))
D

= KP {qD (t + δt) − CP (x(t))} − KD CD (x(t)),
I = {0.075, 0.1, 0.2},

(20)
(21)

0x (t)ez1 (t) + ċ0y (t)ez2 (t), indicates the velocity of the
body link projected into the (ez1 , ez2 , 0) direction; that is, the x–y direction from the body link to the head link.

6 The term, ċ

123

336

Auton Robot (2013) 34:327–346

Table 2 Number of BFs, actions, and control wires
DoF and BF allocation

BFs

DCOB

WF-DCOB

Grid3

WF3

Grid5

WF5

3-DoF-Grid

125

375

375

27

27

125

125

4-DoF-Grid

256

768

768

81

81

625

625

5-DoF-Dyn

202

606

606

243

243

3,125

3,125

5-DoF-Grid

243

729

729

243

243

–

–

5-DoF-SprDmp

300

900

900

243

243

–

–

6-DoF-SprDmp

300

900

900

729

729

–

–

7-DoF-SprDmp

600

1,800

1,800

2,187

2,187

–

–

BFs: number of BFs, DCOB/Grid3/Grid5: number of actions, WF-DCOB/WF3/WF5: number of control wires. Dash (—) denotes that the condition
is not used in the DoF.

Fabbrv =0.5 (ND = 4),
1 (otherwise),(22)

used, which are represented as WF3 and WF5 respectively.
An action u selected by the RL agent is converted into thetarget joint angles by

where q1:ND denotes the joint angle vector, q̇1:ND
denotes the joint angular velocities, KP = 5.0 Nm/rad, andKD = 1.6 Nms/rad. Fabbrv = 0.5 for ND = 4 is determinedthrough preliminary experiments. As a function approximator, LFA-NGnet is used.
WF-DCOB: For each ND -DoF configuration, the
WF-DCOB’s parameters CP , CD , Ctrl and Fabbrv are thesame as DCOB. The other parameter isThen, a control command is computed from qD (t) in thesame manner as grid action set. The duration of an action is
TWF = 0.1s.
Table 2 shows the number of BFs, actions, and control
wires in each DoF configuration.

IR = {(0.05, 0.1), (0.1, 0.2), (0.2, 0.3)}.

7.1.5 Configuration of RL method(23)

Wire-fitting is used as a function approximator.
Grid Action Set (Grid3, Grid5): “Grid action set” AG
is defined as an action set where the displacement of a target joint angle is discretized by a grid. For each ND -DoF
configuration, AG is defined as follows:q | q = (δq1 , . . . , δq ND ) ,
AG =

N −1
δq1,...,ND ∈ {0, ± ϕ, . . . , ± grid
ϕ}
(24)
2
where Ngrid denotes the number of divisions of each joint
angle, and ϕ = π/12 is a unit of the displacement. The sizeof AG is |AG | = (Ngrid ) ND . In the following experiments,
Ngrid = 3 and 5 are used, which are represented as Grid3 andGrid5 respectively. Each element q ∈ AG is converted to
a command sequence as follows:qD (t) = CP (x(t)) +

q

(25)

ũ(t) = KP {q (t) − CP (x(t))} − KD CD (x(t))

(26)

D

where t = tn + ta , ta ∈ [0, TG ), and TG = 0.1s denotes
a duration of an action. As a function approximator, LFANGnet is used.
Wire-fitting (WF3, WF5): This is a continuous versionof grid action set, where the action of the RL agent is thedisplacement of target joint angles. The action value function
is approximated by wire-fitting. The parameters of the control
wires {Ui |i ∈ W} are initialized by the elements of gridaction set { q} defined above. Similarly, Ngrid = 3 and 5 are

123

qD (t)  CP (x(t)) + u.

(27)

As an RL method, we use Peng’s Q(λ)-learning for every
condition. We also employ replacing trace. The parametersof the Q(λ)-learning are also consistent for every condition:
γ = 0.9, λ = 0.9. We use a decreasing step-size parameter α = α0 exp(−δα Neps ) for updating, and a decreasing
temperature parameter τ = τ0 exp(−δτ Neps ) for Boltzmann
selection where Neps denotes the episode number. These
parameters are determined through preliminary experiments:
α0 = 0.3, δα = 0.002, τ0 = 5, δτ = 0.004.
7.1.6 Results
Figure 8 shows the learning curves of the motion learning
tasks; in each graph, the mean of the return over 15 runs isplotted per episode. In all results, DCOB and WF-DCOB
acquire a motion of outstanding performance compared tothe other methods, and the learning speed of DCOB or WFDCOB is the fastest in most cases. The possible reasons are
considered as follows:(R1) BFTrans provides a suitable action space for RL methods as mentioned in Sect. 4.1.
(R2) Utilization of BFs for the action space discretization(DCOB) or for the parameter initialization and constraints (WF-DCOB) reduces the learning time or thelearning instability.

Auton Robot (2013) 34:327–346

337

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Fig. 8 Resulting learning curves of the crawling task. In every graph, each curve shows the mean of the return over 15 runs per episode

123

338

Auton Robot (2013) 34:327–346

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Fig. 9 Snapshots of acquired motions with DCOB

(R1) enables the robot to acquire higher performance; inFig. 8f, g, the sizes of DCOB and Grid3 are almost thesame, but DCOB outperforms Grid3. Similarly, in Fig. 8b,
the sizes of DCOB and Grid5 are almost the same, but DCOB
outperforms Grid5. We can verify (R2) in Fig. 8c where thenumber of BFs is reduced by dynamics-based allocation. The
size of DCOB is smaller than that of Grid5, which enables afast convergence. Still, the acquired performance of DCOB
is the highest in most cases.
Next, we compare the results of DCOB and WF-DCOB. In
lower DoFs (3, 4, and 5), DCOB and WF-DCOB are almost
the same, or DCOB acquires better performance than WFDCOB (Figs. 8b, e). In addition, DCOB learns faster thanWF-DCOB in Fig. 8b. On the other hand, in higher DoFs (6and 7), WF-DCOB is superior to DCOB; WF-DCOB learns
faster in Fig. 8f, g), WF-DCOB acquires better performancein Fig. 8g.
The following possible reason of them is considered:in higher DoFs, the number of actions in DCOB is relatively small for the DoF, which leads to a coarse exploration. WF-DCOB explores continuous actions around theactions in DCOB, which makes exploration finer. Thus, WFDCOB performed better than DCOB in the higher DoF cases.

123

Meanwhile in the lower DoFs, the number of actions in
DCOB was considered to be enough for a fine exploration. In
such cases, exploring continuous actions improves the performance minimally. Moreover, due to the instability of learning
in a continuous action space, WF-DCOB is inferior to DCOB
in some cases. This consideration can also explain the resultsof 5-DoF-Dyn, 5-DoF-Grid, and 5-DoF-SprDmp (Fig 8c–e).
In some runs, there was a period of episodes where thereturn had higher value than one at the final episode. However, because of instability of such a policy, the policy converged to a stable one that had a lower return value. For
instance, we can see this effect in Fig. 9a. The reason why
DCOB has high peak between 500 and 750 episodes is that
one of 15 runs had a much higher return value during thisperiod.
Figure 9 shows the snapshots of acquired motions with
DCOB. Though the same set of movable joints are used in
3-DoF and 5-DoF, the difference of joint-coupling or BF allocation changes the behavior of the robot (Fig. 9a, c–e). The
behavior is also changed by increasing movable joints as seenin 6 and 7-DoFs (Fig. 9f, g). The crawling behavior with 4DoF configuration shows a slight turning (Fig. 9b, h); this isbecause the joint-coupling is not symmetric. Comparing theAuton Robot (2013) 34:327–346

339

Fig. 10 King Spider (ROBOTIS Bioloid) which has 18 DoF

Fig. 11 Setup of experimental environment

crawling behavior of 4-DoF configuration with the turning
behavior of the same configuration, we can find that the difference of reward function generates the behavior (Fig. 9b,h). Please see also the accompanying video.

measures the distance from the robot to the wall. The robot
is connected to a computer7 and communicates with it using
a serial protocol. In each δt = 0.1 s, the command input ũ(the target joint angles) is sent to the robot.

7.2 Crawling task of real robot

7.2.2 Task description

As an application to real robot control, experiments of thecrawling task are demonstrated. The robot used here is
Bioloid of the King Spider model (Fig. 10), made by ROBOTIS co.

The objective of the crawling task is to move forward as far
as possible. So, the reward is designed as follows:

7.2.1 Robot and environment description
The robot has 18 joints where an actuator is attached to eachjoint. We use a 5-DoF configuration; specifically, each set of
joint pairs {q1 , q2 }, {q3 , q4 , q5 , q6 }, {q7 , q8 }, {q9 , q10 , q11 ,q12 }, {q15 , q16 } is coupled, which gives a bilateral symmetry.
The other joints are fixed to a neutral angle; q13 = q14 =q17 = q18 = 0.
The command input ũ is a 5-dimensional vector of thetarget joint angles. The observable state includes only joint
angles: x = (q1 , q3 , q7 , q9 , q15 ) . That is, it does not include
a global position and orientation. The absence of these observations may break the Markov property of the task. The
reasons for this absence are that (1) we can verify the applicability to POMDPs (Partially Observable Markov Decision
Processes), and (2) using the Bioloid product as it is makes
verification experiments easier for other researchers. We utilize NGnet whose BFs are allocated on a 3 × 3 × 3 × 3 × 3
grid over the state space, i.e. the reduced joint angle space.
Besides the joint angle sensors, we use an infrared ray (IR)sensor to observe the distance from the robot to an obstacle. This observation is used to calculate the reward. Let dIRdenote the distance (actually, dIR is processed by a low-passfilter).
The experimental environment is configured as shown in
Fig. 11. The robot is put in front of a wall; the IR sensor

r (t) = vIR (t) − 0.15,(28)

where vIR (t) denotes the velocity of the robot calculated
from dIR (t). Thus, in the summation of the reward (return),
the vIR (t) term indicates a moving distance and the constant(0.15) term denotes a penalty for elapsed time. Each episodebegins with an initial pose (q1 = −q2 = −π/9, q3,...,18 =0), and ends if t > 50s, if the robot touches the wall (determined by the operator), or if some problems arise.
7.2.3 Configurations of action spaces and function
approximators
The following methods are compared.
DCOB: DCOB is configured as follows:
CP (x) = q1:5 ,(29)

CD (x) = 0 ,(30)

I = {0.5},(31)

Fabbrv = 1,

(32)

5

where q1:5 denotes the joint angle vector, and 05 denotes the
5-dimensional zero vector. Note that the command input of
the robot is the target joint angles, thus, Ctrl is considered
to be embedded in the robot. That is, we use qD (t + δt) as acommand input. As a function approximator, LFA-NGnet isused.
7 A laptop PC: Pentium M 2GHz CPU, 512MB RAM, Debian Linux.

123

340

Fig. 12 Resulting learning curves of the crawling task of King Spider(raw data). Each curve shows the return per episode in a run. To see
the tendency of each curve, a low-pass filter with a time constant of ten
episodes is applied

Auton Robot (2013) 34:327–346

Fig. 14 Performance of the acquired motion of King Spider: the average and the ±1SD of the return over the last ten episodes

Fig. 15 Snapshots of an acquired crawling motion of King Spider(4.8, 5.4, 6.0, 7.2 s)Fig. 13 Averaged learning curves of the crawling task of King Spider.
Each curve shows the mean of the return over four runs from 0 to 77th
episodes. Error bar denotes the ±1 standard deviation. A low-pass filter
with a time constant of ten episodes is also applied

Grid action set (Grid3): Grid action set AG , defined in
Sect. 7.1, is employed. The parameters are ϕ = π/12, andTG = 0.1s. The number of divisions is set as Ngrid = 3,
which is referred to as Grid3. LFA-NGnet is also used as afunction approximator.

Fig. 16 Resulting learning curves of the crawling task of Dinosaur.
Each curve shows the return per episode in a run

7.2.4 Configuration of RL method
As the RL method, we use Peng’s Q(λ)-learning for every
method. We also employ replacing trace. The parameters of
the Q(λ)-learning are consistent for every condition: γ = 0.9,
λ = 0.9. We use a decreasing step-size parameter α =α0 exp(−δα Neps ) for updating, and a decreasing temperatureparameter τ = τ0 exp(−δτ Neps ) for Boltzmann selection
where Neps denotes the episode number. These parameters
are determined through preliminary experiments: α0 = 0.3,
δα = 0.002, τ0 = 0.1, δτ = 0.004.

and the ±1SD of four runs from 0 to 77th episodes, where
every run is performed. Figure 14 shows the mean and the±1SD in the last ten episodes. Figure 13 shows that with
DCOB, a higher return is obtained around 20–30th episodes,
which is faster than Grid3. Meanwhile, Fig. 14 indicatesthat the performance of the acquired motions with DCOB
is superior to that of Grid3. Therefore, DCOB also outperforms Grid3 both in learning speed and acquired motion performance. Figure 15 demonstrates a motion acquired with
DCOB. Please see also the accompanying video.

7.2.5 Results

7.2.6 Demonstration of Dinosaur

For each method, four runs are performed. Figure 12 shows
the obtained learning-curves. Figure 13 shows the mean

Finally, DCOB is applied to a crawling task of the Dinosaur
model of Bioloid. In this case, the task setup is almost the123Auton Robot (2013) 34:327–346

341

Fig. 17 Snapshots of an acquired crawling motion of Dinosaur(7.2, 7.6, 8.0, 8.6 s)same as the King Spider case except for the number of actuators. The differences are (1) the reward is multiplied by fivesince Dinosaur is slower than King Spider because of its
shorter legs, (2) a penalty is given when the robot falls down(the operator determines the falling down event), and (3) the
IR sensor is mounted on the head.
Figure 16 shows the resulting learning curves in three runs,
and Fig. 17 shows snapshots of an acquired crawling motion.
Learning speed is slower than that of the King Spider case.
A possible reason is that Dinosaur sometimes falls down,
which makes the task more difficult than the task with King
Spider.

control input, i.e. P(x |x, ũ), the new state transition probability depends only on the current state and the current
action: P(xn+1 |xn , un ). This is because the reference trajectory of the action in BFTrans’ input space is determinedby only xn and un , and thus, the command sequence ũ(t),t ∈ [tn , tn + TNn  ) depends only on xn and un . Therefore, if
the original task has the Markov property, the converted task
also has the Markov property.
Note that DCOB also has the same property, while this is
not the case with WF-DCOB. This is caused by the utilizationof a nonlinear function approximator (wire-fitting) in WFDCOB. As far as the authors know, there is no RL methodthat generally guarantees its convergence with a nonlinear
function approximator.
8.1.2 Computational costThis section discusses the theoretical basis of BFTrans andthe related work.

The computational cost of the generating trajectory step andthe following trajectory step is O(dim(Q)). The abbreviating
trajectory step8 requires O(|K|2 ) to compute {dN (k)|k ∈ K},
but {dN (k)} stays constant during learning with fixed BFs.
Thus, we can pre-compute {dN (k)}. Eventually, the abbreviating trajectory step requires O(|K|). Thus, the total computational cost of each BFTrans action is O(|K|) (in general,dim(Q) < |K|). Note that this cost is the same as the cost ofevaluating all BFs, which is required in each action selection.

8.1 Theoretical basis of BFTrans

8.2 Applicability

8.1.1 Markov property

The assumptions of the proposed methods are mentioned in
Sect. 4.2. These requirements and the applicability of the
RL method decide the applicability of the proposed methods. The proposed methods do not sacrifice the Markov
property of a task as discussed in the previous section.
Though the convergence of Sarsa(λ) with a linear function approximator is proven by Tsitsiklis and Roy (1997)
while that of Q(λ)-learning is not, the both algorithms practically work well in MDPs (Markov Decision Processes).
Furthermore, the TD(λ) methods work well even in POMDPs(Partially Observable MDPs); e.g. Loch and Singh are empirically studied the applicability of the table-lookup Sarsa(λ)
in POMDPs (Loch and Singh 1998). From our experience,
Q(λ)-learning with a linear function approximator also works
well in POMDPs. Thus, the proposed methods are considered
to be able to handle POMDPs practically.
Based on this discussion, let us consider the examples
of applicable robots and tasks. From our experiments, it ispossible to apply the proposed methods to learning a wholebody motion of an articulated robot, such as a humanoid
robot and a spider robot. In this case, we have some choices

8 Discussion

The convergence of some RL methods depends on theMarkov property of the task, e.g. (Tsitsiklis and Roy 1996,1997), thus, we clarify the Markov property of the task using
BFTrans.
BFTrans converts the control command space ũ ∈ Ũ to
the action space u ∈ U. The time sequence, the state transition probability, and the reward function change with thisconversion. The time sequence changes from a continuous
time to a discrete time associated with the action sequence.
The discrete time is defined by
n−1

t0 = 0, tn =TNn  ,

(33)n  =0where TNn denotes the duration of the action un at step n. We
can define the new reward function as
tn
+TNn

Rn =

r (t)dt,(34)

tn

where r (t) is the reward at time t. If the original state transition probability depends only on the current state and the

8 We assume that a simple PD-controller is used as the low-level

controller.

123

342

of the observable state. At least, we need to include the joint
angles in the observable state; on the other hand, we canomit the global position and orientation. When applying themethods to a navigation task of a omniwheel mobile robot,
we will choose the global position as the observable state.
However, since our methods require a conversion CP fromthe observable state to a controllable subspace of the state,
there are some domains to which it is difficult to apply. For
example, handling a wheeled robot (other than a omniwheel)
is not straightforward; as the state, we may choose the global
position and orientation, and the linear and angular velocities,
but we need to use a trick on the conversion CP .
8.3 Related work
The most remarkable contribution of this paper is achieving the graph search-like exploration (Fig. 1b) even in large
domains by cooperating with an action value function-based
RL method. As far as we know, there are only few researches
achieving the graph search-like exploration in large domains.
Most researches use a simple exploration policy, such asa policy using Gaussian noise, which may cause a narrow
exploration like a trajectory-wise exploration (Fig. 1a). Sucha method cannot explore enough the state-action space in alarge domain. Thus, we consider that such a poor exploration
is not suitable for the learning-from-scratch case of high-DoF
robots.
A disadvantage of the proposed methods is the assumptionof fixed BFs. Optimizing the parameters of BFs sometimes
can prevent the effects of the curse of dimensionality. For
instance, learning the nonlinear parameters of the sigmoid
functions in a neural network significantly reduces theapproximation error, more so than in the case of learning
only the linear weights of the network (Barron 1993). DCOB
assumes that the given BFs have already prevented the curseof dimensionality, but this assumption may not be always satisfied. Some RL researches reported that updating not only
the linear weights of NGnet but also the means and the covariance matrices can improve learning (Morimoto and Doya
1998; Kondo and Ito 2004).
However, though the assumption of fixed BFs is a disadvantage, this assumption makes learning stable. Under thisassumption, we can maintain the Markov property of the task.
In the rest of this section, we discuss the related work fromvarious points of view.
8.3.1 Via-point representation
Miyamoto et al. (2004) proposed an RL method with viapoint representation. Both WF-DCOB and the via-point representation are similar in that they have explicit target pointsof the state space and optimize the target points. However,the RL method with via-point representation uses a simple

123

Auton Robot (2013) 34:327–346

exploration noise. The advantage of DCOB and WF-DCOB
is the graph search-like exploration.
8.3.2 RL methods using action converter
Using an RL-compatible action space instead of the command space is a common approach in RL applications. In
such a method, an action selected by the RL policy is converted into a sequence of control commands. A typical way
is using a PD controller and training an RL agent to learn its
target value, e.g. (Morimoto and Doya 1998). Using a central pattern generator (CPG) and letting an RL agent learn its
parameters is effective in learning rhythmic motions, such as
walking (e.g. Nakamura et al. 2007). The proposed methods(DCOB and WF-DCOB) are applicable to episodic tasks,
such as jumping, that are difficult to learn with CPG.
Ijspeert et al. (2002) proposed nonlinear dynamic motor
primitives for robot control. Later, Peters et al. (2003) developed an RL method to optimize the primitives’ parameters. This framework is similar to WF-DCOB, since bothmethods use RL-compatible action spaces and employ RL
methods designed for a continuous action space. However,the primitive-based approach assumes that the parameters
are initialized through an imitation learning framework.
As we described in the introduction section, this method
leads to a trajectory-wise exploration. Meanwhile, WFDCOB provides a proper parameter initialization method forlearning-from-scratch cases, and provides a graph searchlike exploration method, which enables the robot to explore
widely in the possible behavior space.
Theodorou et al. (2010) proposed a novel RL method PI2
which is applicable to an RL problem in large domain. PI2
seems to be a promising method; actually, it was applied tolearning a jumping behavior of a 12-DoF robot dog. However, in its experiments, a Gaussian noise was also used for
exploration. In addition, the application to learning a jumping
behavior used a demonstration generated manually. Thus, it
is suspicious how the method works in the learning-fromscratch case of this paper.
8.3.3 Hierarchical RL methods
DCOB and WF-DCOB resemble hierarchical RL methods
since we can consider the action converter BFTrans as a lower
layer controller and the RL agent as a higher level controller.
Asada et al. (1996) proposed a method to construct a state
space based on actions. The advantage of this method is constructing the state space in execution time. However, if we
apply the method to a large domain, the number of segments
may become huge. In addition, if the task has a POMDP property like the spider robot case, it is suspicious that the statesegmentation converges. The proposed methods provide a
reasonable solution to such problems.

Auton Robot (2013) 34:327–346

Morimoto et al. (Morimoto and Doya 2001) proposed ahierarchical RL method for robot learning which seems to
be a realistic solution. Its disadvantage is that we need toadjust a hierarchical structure manually, which may require
a complex tuning in large domains.
Sutton et al. (1999) proposed options which are generalized actions of primitive and macro actions under the RL
framework. Our DCOB can be regarded as one kind of theoptions specialized for robot control. There is research on
finding options or subgoals automatically (Mcgovern andBarto 2001; Menache et al. 2002; Stolle 2004), however the
discovery of the optimal options is still an open problem. We
consider that DCOB is a practical solution to it.
8.3.4 Parti-game algorithm
Moore and Atkeson (1995) proposed parti-game algorithm
as an RL method for continuous state-action spaces. Thismethod assumes a local controller which moves a robot toa near state, and finds an optimal policy in partitions on thestate space where each action is a transition to a neighboring
partition. Its feature is that partitioning of the state spaceis also optimized, which is superior to DCOB, where theallocation of the given BFs is not changed.
However, the applicable tasks of parti-game algorithm arelimited; a task should have a goal state, which should be
explicitly given. It is therefore not applicable to the crawlingtask used in this paper.

9 Conclusion
This paper proposed a discrete action space DCOB for RL
methods to handle domains of higher dimensional control
input space. DCOB is generated from a set of BFs given
to approximate a value function. DCOB is a discrete space
but it has the ability to acquire high performance motions.
Moreover, using the dynamics-based BF allocation or thespring-damper BF allocation reduces the size of DCOB,
which improves the learning speed. In addition, a method
called WF-DCOB was proposed to enhance the performance,
where wire-fitting was employed to search for continuous
actions around each discrete action of DCOB. In WF-DCOB,
to relax the learning instability of wire-fitting, a parameter
initialization and a constraint method were proposed. In addition, an action selection method like Boltzmann selection was
proposed in order to accomplish a graph search-like (wide)
exploration.
The proposed methods were applied to the simulation
tasks (the crawling and the turning task of the humanoid
robot) and the real robot task (the crawling task of Bioloid).
In the simulation tasks, DCOB and WF-DCOB were compared with conventional action spaces. Moreover, in the343

humanoid’s crawling task, the methods were compared indifferent DoF configurations and different BF-allocation
methods. In every experiment, DCOB and WF-DCOB outperformed the other methods.
Furthermore, we found that the difference in performance
between DCOB and WF-DCOB depended on the conditions, such as a DoF configuration. From the results of thehumanoid’s crawling task, the guidelines for choosing DCOB
or WF-DCOB are as follows: use DCOB if a relatively sufficient number of BFs can be allocated in a state space, e.g. thelower DoF cases; use WF-DCOB if it is difficult to allocate
a sufficient number of BFs, e.g. the higher DoF cases.
Acknowledgments Part of this work was supported by a Grant-inAid for JSPS, Japan Society for the Promotion of Science, Fellows(22·9030).

Appendix
Appendix A Wire-fitting
For a continuous state x ∈ X and a continuous action u ∈ U,
wire-fitting is defined as:−1i∈W (di + ) qi (x)Q(x, u) = lim
,
(35)
−1
→0+
i∈W (di + )
di = u − ui (x) 2 + C max (qi  (x)) − qi (x) . (36)i  ∈W

Here, a pair of the functions qi (x) : X → R and ui (x) :X → U (i ∈ W) is called a control wire; wire-fitting isregarded as an interpolator of the set of control wires W.
C is the smoothing factor of the interpolation; we choose
C = 0.001 in the experiments. Any function approximatoris available for qi (x) and ui (x). For any kind of the function
approximators, one of qi (x), i ∈ W is equal to maxu Q(x, u)
and the corresponding ui (x) is the greedy action at x.
max Q(x, u) = max(qi (x)),
u
i∈W


arg max Q(x, u) = ui (x)ui=arg maxi  ∈W (qi  (x))

(37)
.

(38)

Namely, the greedy action at state x is calculated only by
evaluating qi (x) for i ∈ W.
We use NGnet for qi (x) and a constant vector for ui (x),that is, we let qi (x) = θi φ(x) and ui (x) = Ui , where φ(x)is the output vector of the NGnet. The parameter vector θ
is defined as θ  = (θ1 , U1 , θ2 , U2 , . . . , θ|W | , U|W | ), andthe gradient ∇θ Q(x, u) can be calculated analytically.
Figure 18 shows an example of wire-fitting where both ofx ∈ [−1, 1] and u ∈ [−1, 1] are a one-dimensional vector. There are two control wires (dashed lines) and threebasis functions (dotted lines). The BFs (NGnet) are locatedat x = (−1), (0), (1) respectively, and the parameters of the

123

344

Auton Robot (2013) 34:327–346

dN (k) is calculated bykN (k) = arg mink  ∈K,k  =k CP (μk  ) − CP (μk ) ∞ ,dN (k) = max CP (μkN (k) ) − CP (μk ) ∞ , dmin k ,

(41)
(42)

where dmin k ∈ R is a positive constant to adjust dN (k) when
CP (μkN (k) )−C P (μk ) ∞ is too small. For NGnet, we define
it as dmin k =QλQk where λk is the maximum eigenvalue of9
the covariance matrix Σ Q
k on the Q space . Note that we can
pre-compute {dN (k)|k ∈ K} for fixed BFs.
Using the output of BFs φ(xn ), DN (xn ) is estimated by

DN (xn ) = (dN (1), dN (2), . . . , dN (|K|)) φ(xn )Fig. 18 Example of wire-fitting(43)

Finally, TN is defined bywire-fitting are θ1 = (0.0, 0.6, 0.0) , U1 = (−0.5), θ2 =(0.0, 0.3, 0.6) , U2 = (0.5). Each control wire is plottedas (x, u1 (x), q1 (x)) and (x, u2 (x), q2 (x))
 respectively. Each
×-mark is put at (x, ui  (x), qi  (x))i  =arg max q (x) whichi ishows the greedy action at x.

TN (xn , un ) = min 1,

Fabbrv DN (xn )TF .
qtrg − CP (xn ) ∞(44)

Appendix C Initialization and constraints of WF-DCOB
Initializing wire-fitting parameters

Appendix B Calculations of BFTrans
Generating trajectory
The reference trajectory qD (tn + ta ), ta ∈ [0, TF ] is designed
so that the state changes from the starting state xn = x(tn )to the target qtrg in the time interval TF . We represent the
trajectory with a cubic function,

For a control wire i ∈ W, we use aidcob to denote the corresponding action in DCOB: aidcob = (gidcob , kidcob ). Let(giS , giE ) denote the range of the interval factor which includes
gidcob . For each control wire i ∈ W, its parameter is definedtrg
as Ui = (gi , qi ) and is initialized by
giS + giE,2
trg
qi ← CP (μk dcob ).
gi ←

(45a)
(45b)

i

qD (tn + ta ) = c0 + c1 ta + c2 ta2 + c3 ta3 ,(39)

where c0,...,3 are the coefficient vectors. These coefficientsare determined by the boundary conditions,

Constraints on wire-fitting parametersqD (tn ) = CP (xn ), qD (tn + TF ) = qtrg ,q̇D (tn + TF ) = 0, q̈D (tn + TF ) = 0,(40)

where 0 denotes a zero vector.
Abbreviating trajectory
The abbreviation is performed as follows: (1) estimate
DN (xn ) as the distance between two neighboring BFs aroundthe start state xn , (2) calculate TN from the ratio of DN (xn )and the distance between xn and qtrg .
To define DN (xn ), for each BF k, we first calculate dN (k)as the distance between its center μk and the center of thenearest BF from k. Then, we estimate DN (xn ) by interpolating {dN (k)|k ∈ K} with the output of the BFs at xn .

123

The other parameters of the control wires {θi |i ∈ W} are
initialized by zero, since, in a learning-from-scratch case, we
do not have prior knowledge of the action values.

trg

For Ui = (gi , qi ), the interval factor gi is constrained inside
trg(giS , giE ), and the target point qi is constrained inside a
dcob
hypersphere of radius dN (ki ) centered at CP (μk dcob ). Here,idN (kidcob ) denotes the distance to the nearest BF from kidcob
trg
defined by Eq. 42. Specifically, the parameter Ui = (gi , qi )of each control wire i ∈ W is constrained by
if gi < gSi then gi ← gSi ,if gi > gEi then gi ← gEi ,if diff ∞ > dN (kdcobi ) then.
9 Σ Q is calculated from the original covariance matrix Σ (on the Xkkspace) as follows. For ease of calculation, let CP (x) = ĈP x where ĈP is

a constant matrix. The converted covariance matrix is Σ Q
k = ĈP Σ k ĈP .

Auton Robot (2013) 34:327–346
trg

qi ← CP (μk dcob ) + dN (kidcob )
i

345

diff
,
diff ∞

(46)

where
trg

diff  qi − CP (μk dcob ).
i(47)

These constraints are applied after each update of an RL
algorithm.

References
Asada, M., Noda, S., & Hosoda, K. (1996). Action-based sensor space
categorization for robot learning. In The IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS ’96) (pp. 1502–
1509).
Baird, L.C., & Klopf, A.H. (1993). Reinforcement learning withhigh-dimensional, continuous actions. Technical Report WL-TR-931147, Wright Laboratory, Wright-Patterson Air Force Base.
Barron, A. (1993). Universal approximation bounds for superpositionsof a sigmoidal function. IEEE Transactions on Information Theory,39(3), 930–945. doi:10.1109/18.256500.
Doya, K., Samejima, K., Katagiri, K., & Kawato, M. (2002). Multiple
model-based reinforcement learning. Neural Computation, 14(6),1347–1369. doi:10.1162/089976602753712972.
Gaskett, C., Fletcher, L., & Zelinsky, A. (2000). Reinforcement learning for a vision based mobile robot. In The IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS’00).
Ijspeert, A., & Schaal, S. (2002). Learning attractor landscapes for learning motor primitives. In S. Becker, S. Thrun, & K. Obermayer (Eds.),
Advances in neural information processing systems (pp. 1547–1554).
Cambridge: MIT Press.
Kimura, H., Yamashita, T., & Kobayashi, S. (2001). Reinforcement
learning of walking behavior for a four-legged robot. In Proceedingsof the 40th IEEE Conference on Decision and Control. Portugal.
Kirchner, F. (1998). Q-learning of complex behaviours on a six-legged
walking machine. Robotics and Autonomous Systems, 25(3–4), 253–
262. doi:10.1016/S0921-8890(98)00054-2.
Kober, J., & Peters, J. (2009). Learning motor primitives for robotics.
In The IEEE International Conference on Robotics and Automation(ICRA’09) (pp. 2509–2515).
Kondo, T., & Ito, K. (2004). A reinforcement learning with evolutionary state recruitment strategy for autonomous mobile robots control.
Robotics and Autonomous Systems, 46(2), 111–124.
Loch, J., & Singh, S. (1998). Using eligibility traces to find thebest memoryless policy in partially observable markov decision
processes. In Proceedings of the Fifteenth International Conference
on Machine Learning. (pp. 323–331).
Matsubara, T., Morimoto, J., Nakanishi, J., Hyon, S., Hale, J.G., &Cheng, G. (2007). Learning to acquire whole-body humanoid CoM
movements to achieve dynamic tasks. In The IEEE International
Conference on Robotics and Automation (ICRA’07). (pp. 2688–
2693). doi:10.1109/ROBOT.2007.363871.
Mcgovern, A., & Barto, A.G. (2001). Automatic discovery of subgoals
in reinforcement learning using diverse density. In The EighteenthInternational Conference on Machine Learning. (pp. 361–368). San
Mateo, CA: Morgan Kaufmann.
Menache, I., Mannor, S., & Shimkin, N. (2002). Q-cut - dynamic discovery of sub-goals in reinforcement learning. In ECML ’02: Proceedings of the 13th European Conference on Machine Learning (pp.
295–306). London: Springer.
Miyamoto, H., Morimoto, J., Doya, K., & Kawato, M. (2004). Reinforcement learning with via-point representation. Neural Networks,
17(3), 299–305. doi:10.1016/j.neunet.2003.11.004.

Moore, A. W., & Atkeson, C. G. (1995). The parti-game algorithm
for variable resolution reinforcement learning in multidimensional
state-spaces. Machine Learning, 21(3), 199–233. doi:10.1023/A:
1022656217772.
Morimoto, J., & Doya, K. (1998). Reinforcement learning of dynamic
motor sequence: Learning to stand up. In The IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’98).
(pp 1721–1726).
Morimoto, J., & Doya, K. (2001). Acquisition of stand-up behavior by a real robot using hierarchical reinforcement learning.
Robotics and Autonomous Systems, 36(1), 37–51. doi:10.1016/
S0921-8890(01)00113-0.
Nakamura, Y., Mori, T., Sato, M., & Ishii, S. (2007). Reinforcement
learning for a biped robot based on a CPG-actor-critic method.
Neural Networks, 20(6), 723–735. doi:10.1016/j.neunet.2007.01.
002.
Peng, J., & Williams, R. J. (1994). Incremental multi-step Q-learning.
In International Conference on Machine Learning. (pp. 226–232).
Peters, J., Vijayakumar, S., & Schaal, S. (2003). Reinforcement learningfor humanoid robotics. In IEEE-RAS International Conference on
Humanoid Robots. Karlsruhe, Germany.
Sato, M., & Ishii, S. (2000). On-line EM algorithm for the normalized
Gaussian network. Neural Computation, 12(2), 407–432.
Sedgewick, R., & Wayne, K. (2011). Algorithms. Boston: AddisonWesley.
Stolle, M. (2004). Automated discovery of options in reinforcement
learning (Master’s thesis, McGill University).
Sutton, R., & Barto, A. (1998). Reinforcement Learning: An Introduction. Cambridge: MIT Press. Retrieved from http://citeseer.ist.psu.
edu/sutton98reinforcement.html.
Sutton, R. S., Precup, D., & Singh, S. (1999). Between mdps and semimdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112, 181–211.
Takahashi, Y., & Asada, M. (2003). Multi-layered learning systems forvision-based behavior acquisition of a real mobile robot. In Proceedings of SICE Annual Conference 2003 (pp. 2937–2942).
Tham, C. K., & Prager, R. W. (1994). A modular Q-learning architecture
for manipulator task decomposition. In The Eleventh International
Conference on Machine Learning (pp. 309–317).
Theodorou, E., Buchli, J.,& Schaal, S. (2010). Reinforcement learningof motor skills in high dimensions: A path integral approach. In
The IEEE International Conference on Robotics and Automation(ICRA’10) (pp. 2397–2403). doi:10.1109/ROBOT.2010.5509336.
Tsitsiklis, J. N., & Roy, B. V. (1996). Feature-based methods for large
scale dynamic programming. Machine Learning, 22, 59–94.
Tsitsiklis, J. N., & Roy, B. V. (1997). An analysis of temporal-difference
learning with function approximation. IEEE Transactions on Automatic Control, 42(5), 674–690.
Uchibe, E., Doya, K. (2004). Competitive-cooperative-concurrent reinforcement learning with importance sampling. In The International
Conference on Simulation of Adaptive Behavior: From Animals andAnimats (pp. 287–296).
Wolpert, D. M., & Kawato, M. (1998). Multiple paired forward
and inverse models for motor control. Neural Networks, 11(7),1317–1329.
Yamaguchi, A. (2011). Highly modularized learning system for behavior acquisition of functional robots. Ph.D. Thesis, Nara Institute of
Science and Technology, Japan.
Zhang, J., & Rössler, B. (2004). Self-valuing learning and generalization
with application in visually guided grasping of complex objects.
Robotics and Autonomous Systems, 47(2), 117–127.

123

346
Akihiko Yamaguchi received
the BE degree from the Kyoto
University, Kyoto, Japan, in
2006, and the ME and the
PhD degrees from Nara Institute of Science and Technology(NAIST), Nara, Japan, in 2008
and 2011, respectively. From
April 2010 to July in 2011, he
was with NAIST as a JSPS, Japan
Society for the Promotion of
Science, Research Fellow. From
August 2011 to present, he iswith NAIST as an Assistant Professor of the Robotics Laboratory in the Graduate School of Information Science. His research interests include motion learning of robots, reinforcement learning application to robots, machine learning, and artificial intelligence. From 2010,
he is managing the open source project of reinforcement learning, SkyAI(skyai.org).

Jun Takamatsu received the
Ph.D. degree in Computer Science from the University ofTokyo, Japan, in 2003. After
working in the Institute of Industrial Science, the University ofTokyo, he joined Nara Institute of Science and Technology (NAIST), Japan in 2008.
At present, he is an associate
professor in Graduate Schoolof Information Science, NAIST.
His research interests are in 3D
shape modeling and analysis,
physics-based vision, and robotics including learning-from-observation and task planning using feasible motion analysis.

123

Auton Robot (2013) 34:327–346
Tsukasa Ogasawara received
the BE, ME and PhD degrees
from the University of Tokyo,
Tokyo, Japan, in 1978, 1980 and
1983, respectively. From 1983
to 1998, he was with the Electorotechnical Laboratory, Ministry of International Trade andIndustry, Ibaraki, Japan. From1993 to 1994, he was with theInstitute for Real-Time Computer Systems and Robotics,
University of Karlsruhe, Karlsruhe, Germany, as a Humboldt
Research Fellow. In 1998, hejoined Nara Institute of Science and Technology, Nara, Japan, as a Professor of the Robotics Laboratory in the Graduate School of Information
Science. His research interests include human-robot interaction, dexterous manipulation and biologically inspired robotics.