2008 IEEE/RSJ International Conference on Intelligent Robots and Systems
Acropolis Convention Center
Nice, France, Sept, 22-26, 2008

Learning Meaningful Interactions from Repetitious Motion Patterns
Koichi Ogawara and Yasufumi Tanabe and Ryo Kurazume and Tsutomu Hasegawa

Abstract— In this paper, we propose a method for estimating
meaningful actions from long-term observation of everyday
manipulation tasks without prior knowledge as part of an action
understanding framework for life support robotic systems. The
target task is defined as a sequence of interactions between
objects. An interaction that appears many times is assumed
to be meaningful and repetitious relative motion patterns
are detected from trajectories of multiple objects. The main
contribution is that the problem is formulated as a combinatorial optimization problem with two parameters, target object
labels and correspondences on similar motion patterns, and issolved using local and global Dynamic Programming (DP) in
polynomial time O(N log N ), where N is a total amount ofdata. The proposed method is evaluated against manipulation
tasks using everyday objects such as a cup and a tea-pot.

I. INTRODUCTION
The applicable areas of robotics technology have been
rapidly expanding and “supporting our life in everyday
environment” is becoming one of the key applications.
To determine what robotic behavior is appropriate in acertain situation, the system should understand what a humanis doing at the moment. A common approach to understandhuman behavior is to design a set of necessary and sufficienttask-dependent recognizers that detect significant actions
and capture the necessary parameters to describe the tasks[1], [2], [3], [4], [5]. Various tasks are tackled in thisapproach: including assembly planning [1], [2], soft object
manipulation [3], whole body motion generation [4], [5],etc. However, unlike in the well-organized environment suchas a factory, the variety of human behavior in everyday
environment is infinite, thus it is not practical to prepare
recognizers to cover all the possible daily activities.
For this reason, the desirable system should have a mechanism to obtain and accumulate new knowledge, i.e. newcausal relationship, incrementally from observation. As abootstrap process to realize this mechanism, we are interested
in finding structured information in observations that can beextracted without prior knowledge about the presented task.
The basic idea is if a particular motion pattern appears manytimes in observations, this pattern must be meaningful to thedemonstrator or to the task. When the system detects some
repetitious motion patterns such as preparation for breakfast
or reading a news paper while observing daily activities for along period time, e.g., several days, these patterns are marked
as meaningful actions and the causal relationship between
K. Ogawara is with Faculty of Engineering, Kyushu University, Fukuoka,
JAPAN ogawara@is.kyushu-u.ac.jp
Y. Tanabe is with Department of Electrical Engineering and Computer
Science, Kyushu University, Fukuoka, JAPANR. Kurazume and T. Hasegawa are with Faculty of Information Scienceand Electrical Engineering, Kyushu University, Fukuoka, JAPAN

978-1-4244-2058-2/08/$25.00 ©2008 IEEE.

T

Input: object trajectories
Trajectory

Output 1: Pour from A to B

Object A

T

Object B

T

Object C

T
Output 2: Pour from C to B

Fig. 1.

Target Problem

meaningful actions can be used to predict the next action ofa user that can be supported in some ways by the robotic
system, e.g., bringing a news paper.
In the scope of this paper, we assume that daily activities
are composed of a sequence of interactions between two
manipulated objects, and we propose a method for detecting
repetitious interactions observed from motion trajectories ofmultiple environmental objects.
The problem is formulated as a combinatorial optimization
problem with two parameters, target object labels and correspondences on similar motions, and is solved using local
and global Dynamic Programming (DP) in polynomial time.
The contribution of the proposed method is two fold. The
first contribution is to find repetitious motion patterns in
temporal data streams without a reference pattern in polynomial time O(N log N ), where N is a total amount of data,
while most of the previous methods require O(N 2 ) time ora reference pattern which is not practical in our applications
where we have to deal with long-term observation without
prior knowledge about the task. The second contribution
is that it can estimate which two objects among many
candidates constitute each meaningful interaction, while mostof the previous methods assume a single object or a single
trajectory.
This paper is organized as follows. In Section II, the target
problem is explained and the related research as well as theoverview of the proposed algorithm is presented. In Section
III, the details of the proposed method is described. The
experimental results and evaluation are shown in Section IV
and we conclude the paper in Section V.
II. L EARNING M EANINGFUL I NTERACTIONSIn this section, the problem of finding meaningful interactions between two objects from trajectories of multiple
objects is examined. Here, we assume that an interaction that3350

appears many times in observations is meaningful, thus the
problem becomes to find repetitious relative motion patterns
between two particular objects.
Fig.1 shows an example of the target problem. There arethree objects in the scene and the input to the algorithm is thethree trajectories corresponding to each object. In this case,the desired output would be the two types of interactions:(1) “Pour from A to B” which appears three times and(2) “Pour from C to B” which appears two times. In bothinteractions, a set of segments are detected in which all the
relative trajectories are quite similar to each other.

Relave trajectory between Object A and Object B
Similar MooncandidateMoon of Interestt = T1

t = T3t = T2

O(t )

O(t )

O(t )

(2) Evaluaon is small(3) Evaluaon is smallO(T1 )(1) Evaluaon is highFig. 2.
Evaluation of Repetitious Motion Pattern. There is a single
trajectory, but some parts are omitted to better visualize it.

A. Related Research
There are roughly two approaches to detect repetitious motion patterns. One is a recognition approach where repetitious
motion patterns are spotted by a set of recognizers. The otheris a pattern matching approach where Dynamic Programmingis typically used to detect similar patterns.
1) Recognition Approach: Mori et al. proposed a hierarchical recognition framework where multiple HMM-based
recognizers for different action types and different abstraction levels run in parallel and inconsistencies in the result
are resolved by the relationship in the action hierarchy[6].
However, the labelled training data must be provided for therecognizers and it cannot deal with new actions.
Zhao et al. proposed a structured representation of the
motion primitives that satisfies MDL and recognized ballet
sequence[7]. However, the typical motion patterns encoded ineach recognizer are quite short and it is difficult to spot a longand complex interactions between objects in this approach.
2) Pattern Matching Approach: Bobic et al. represented a
set of training trajectories of gestures as a sequence of states
and recognized an input gesture using Dynamic Programming under a state transition framework[8]. However, thismethod requires manually segmented and labelled training
data for each gesture.
To relax the requirement for pre-segmentation, Ogawara
et al. proposed a method for detecting a set of repetitious
motion patterns from multiple observations of the same taskusing multi dimensional Dynamic Programming[9]. However, multiple demonstrations should be provided in that thesame types of motion patterns appears in the same order.
To overcome this problem, Uchida et al. proposed amethod for detecting a set of repetitious motion patterns
from a single observation using logical DP matching[10].
However, the computational complexity is O(N 2 ) and it
cannot deal with multiple objects.
Ogawara proposed a method for detecting a set of repetitious motion patterns from a single observation[11]. It candeal with multiple objects, however it solves a combinatorial
optimization problem by a stochastic method, Markov-Chain
Monte Calro (MCMC), and the computational efficiency becomes dramatically degraded as the amount of data increases.
B. Proposed Method Overview
In this paper, a deterministic method for detecting repetitious motion patterns from a single observation is proposed.

Fig.2 shows the 2D slice of a relative trajectory O(t)between two objects. If a motion pattern of interest ataround time t has the similar motion patterns at other timeframes on the same trajectory, this pattern can be considered
as meaningful since this particular pattern appear multiple
times. Because we take a relative trajectory between objects
as input, the similarity can be evaluated by the degree ofoverlap between their trajectories in the eucledian space.
Fig.2 shows the three typical cases. In case (1), the motion
pattern of interest at around t = T1 has multiple similar
motion pattern candidates in the neighborhood, thus theevaluation that the interaction between object A and B ataround t is meaningful becomes high. In case (2), there
is no similar motion pattern candidates at around t = T2 ,thus the evaluation becomes small. In case (3), there are
multiple motion pattern candidates in the neighborhood ataround t = T3 , however the shape of them are completely
different, thus the evaluation also becomes small.
The proposed algorithm evaluates the above mentioned
criteria for each data point along the entire relative trajectoryand integrate the evaluation in a globally consistent way.
The computational complexity of the proposed methodis O(N log N ), where N is a total amount of data. Thisis achieved by efficiently constraining the search space forfinding the similar motion patterns within the neighborhoodof each data point using kd-tree search algorithm.
Also, the proposed method can estimate which two objects
among multiple object candidates constitute a repetitious motion pattern of interest. This is achieved by formulating the
problem as a label assignment problem. This combinatorial
optimization problem can be solved by Dynamic Programming which naturally solves the determination problem of
the target object in the scene.
III. D ETECTION OF R EPETITIOUS M OTION PATTERNS
A. Problem Formulation
The problem is formulated as a combinatorial optimization
problem regarding to two parameters X, Y . Given observation O, these two parameters are solved for each object Objm
in the scene using Maximum-A-Posteriori(MAP) estimateof the probability function P (X, Y |O). Fig.3 shows theoverview of the formulation.
S
The target object label X = { xt |xt ∈ {A, B, · · · , N }}indicates the target object in the scene with which Objm

3351

L

Objm = A

Objm = A

Target Object Label X

otA
Target Object Label X

li

e1,t

r

e1,t

(Similar mo!on pa"ern)y1,tCorrespondent point Y

s1,t

Scope
range1,t : s1,t ≤ y1,t ≤ e1,ts 2 ,te2s 2 ,trange 2,t : s2,t ≤ y2,t ≤ e2,tT’path 2





O(t )

range k ,t : sk ,t ≤ yk ,t ≤ ek ,tFig. 4.
Fig. 3.

Label Assignment Problem with Hidden Parametersinteracts at time t. If Objm does not interact with any object
at time t, label N is assigned to xt .
S
The correspondence parameter Y = { yk,t |sk,t ≤ yk,t ≤ek,t }} indicates the time frame whose data point O(yk,t ) lies
on a similar motion pattern and corresponds to the data point
O(t) at time t. Fig.3 shows an typical example in the middleof estimation process where target label B is assigned to xt
and the relative trajectory between object Objm = A and B
is of interest at around time t. The range of yk,t is limited
within rangek,t (sk,t ≤ yk,t ≤ ek,t ) which is calculated
beforehand as described in Section III-B.
The MAP estimation of the probability function
P (X, Y |O) is re-written as in eq.(1) using Bayes’s theorem.
argmax P (X, Y |O) ∝ argmax P (O|X, Y )P (Y |X)P (X)X,Yrange1,ts1,tCorrespondent point Y

Rela!ve trajectory between Object A and Object B

range 2,t

N N N B B B B B B B N N N N C C C C N N

path iT

N N N B B B B B B B N N N N C C C C N N

range1,t(Segment of interest)tTrajectory of A

X,Y

(1)
P (O|X, Y ) is an observation likelihood term given X
and Y . P (Y |X) is a frequency term which favors large
number of similar motion patterns. P (X) is a prior term, ora smoothness term, which penalizes the difference between
consecutive target labels.
To realize MAP estimation, we employ an iterative framework as follows.
1) Initialization
2) Estimation of Y using local DP matching (X is fixed)
3) Estimation of X using global DP (Y is fixed)
4) Go to 2) until convergence
In the remainder of this section, the above mentioned
procedure is explained in details.
B. Initialization
As mentioned in the previous section, rangek,t (the rangeof yk,t ) is calculated as follows.
First of all, Kd-tree, a binary tree, is constructed on
observed 6 D.O.F. relative trajectory space: 3 D.O.F for
relative position and 3 D.O.F. for relative orientation. The
entire observation data is recursively divided by a hyperplane perpendicular to the axis along which the variance ofthe remaining data points becomes maximum. One Kd-treee2,tpath 3 range1,t path 4

Estimation of Correspondences Y using Local DP Matchingis built for each relative trajectory. The computational costfor Kd-tree construction is O(N log N ).
To determine rangek,t , Kd-tree is searched and the set ofdata points Ct whose distance to O(t) is less than r is foundas in eq.(2).
[Ct = { O(j)| k O(j) − O(t) k< r, 0 ≤ j ≤ T }(2)

Then, the data points in Ct are sorted along time domain
and the consecutive data points are grouped so as to define
the rangek,t , from sk,t to ek,t , of the correspondent point toO(t). As for the case in Fig.3, two range are found.
This process is applied to all the data points O(t){1 ≤t ≤ T } and rangek,t is determined for all the time frame t.
The total computational cost is O(N log N ). This cost is thebottle neck of the proposed algorithm.
Lastly, X is initialized so that no-interaction label N is
assigned to all xt .
C. Estimation of Y using Local DP Matching1) Estimation of Initial Y using Local DP Matching:
Given target object label X, X can be divided into segments
where all xt in each segment have the same label. Fig.4
shows an example where label B happens to be assigned tothe segment at around t during the estimation process.
Here, we try to find similar motion patterns by estimating
the correspondences Y on them using local DP matching.
As shown in Fig.4, we already have rangek,t on thissegment. The range of the correspondent time frame yk,tis limited within rangek,t . This means, the similar motion
patterns must go through each of rangek,t as shown in redlines in the figure.
Under this constraints, the optimal paths are calculatedusing Dynamic Programming. Here, we define the allowable
step size in DP ranges from 0 to 2, so that li takes value
between 0 and 2L. Eq.(3) shows the recurrence equation of
DP.

3352




g(t − 1, t′ − 2)g(t, t′ ) = s(t, t′ ) + min  g(t − 1, t′ − 1) g(t − 1, t′ )(3)

Objm = A

Then, we can get the non-redundant paths as shown in“after” region in Fig.5.
3) Definition of Probability Function: Finally, the probability function P (O|X, Y ), P (Y |X) and P (X) are defined
as in eq.(6), eq.(9) and eq.(11).

tTarget Object Label X

N N N B B B B B B B N N N N C C C C N N

Correspondent point Y
1

U range

hole

hole
2

k ,t

3
5

hole

4

T’
beforea er

P (ot |xt ) = 1 − exp(−α · velocityt )Topological Reduction of Paths

where s(t, t′ ) means the similarity in pose, i.e. 3 D.O.F
position and 3 D.O.F. orientation, at t and at t′ on therelative trajectory between Objm and Object B. g(t, t′ )means accumulated cost along the path.
For each rangek,t , the longest and minimum cost path iscalculated using Dynamic Programming where the cost isaccumulated from the both terminal to rangek,t . The total
number of calculated path is equal to the number of rangek,tincluded in that segment. However, most of the paths are
identical to each other in general and four distinct paths are
finally found in the case of Fig.4.
Then, two parameters are calculated for each detected
pathi . One is the ratio between the length of the segment
at time t and the length of the corresponding similar motion
pattern as shown in Fig.4 and is defined as in eq.(4). The
other is the similarity between the segment and the similar
motion pattern and is defined as a function of the average
cost of DP matching dp costi along pathi and is defined asin eq.(5).
d Lii (di ≤ Li )li = Li(4) di (Li ≤ di )simt,i = exp(−β · dp costi )(6)

P (ot |xt ) means a velocity term that penalizes a static
object and is defined as in eq.(7).

Remove path of thesame topology

6Fig. 5.

P (O|X, Y ) = ΠP (ot |xt )P (O|xt , yt )
hole

(5)

2) Topological Reduction: Most of the detected paths in
the previous section are redundant as shown in Fig.5. There
are six paths found in “before” region that is the direct resultof the local DP matching. Also, we can see that there are
two holes in the region. This situation typically occurs whena user presents a similar motion several, in this case three,times without sufficient intervals.
Among six paths, the 2nd and 5th path are not importantbecause they are apparently shorter compared with the 4th
or 6th path. And the 3rd and 4th path are redundant and oneof them should be selected.
Thus, we apply the following two operations to the candidates.
1) If a path starts or ends at a hole, remove it2) If two paths can be completely overlap without goingover the holes, remove one with lower evaluation(7)

where velocityt is the velocity of Objm at time t.
P (O|xt , yt ) means a similarity term that penalizes different motion patterns and is defined as in eq.(8).
Σli exp(−β · similarityi )(8)Σliwhere li and similarityi are defined in the previous section
III-C.1.
P (O|xt , yt ) =P (Y |X) = ΠP (yt |xt )(9)P (yt |xt ) means a frequency term that penalizes if thenumber of similar motion patterns is small and is defined
as in eq.(10).
P (yt |xt ) = 1 − exp(−γ · Σli )(10)

P (x) = ΠP (xt , xt+1 )(11)

P (xt , xt+1 ) is a smoothing term that penalizes the difference between consecutive target labels and is defined as ineq.(12).
P (xt , xt+1 ) = T (xt 6= xt+1 ) · K(12)where K is a constant and T (s) = 1 iff s = true, T (s) =0 otherwise.
Lastly, the probability function where xt = N is defined
as follows.
P (O|xt = N, yt )=P (yt |xt = N )=ΣP (O|xt 6= N, yt )· NL (13)#P (O|xt 6= N, yt )ΣP (yt |xt 6= N )
· NL
(14)
#P (yt |xt 6= N )where NL is noise level.
D. Estimation of X using Global DP
Target Label X can be solved analytically via global DP
matching.
As shown in Fig.6, a directional graph is constructed.
−logP (O|xt , yt )−logP (yt |xt ) is assigned as a node weightand −logP (xt , xt+1 ) is assigned as an arc weight. Then, theminimum cost path is calculated in Dynamic Programmingmanner and the result represents the target object label X.
The computational cost of this process is O(N M ) where
M is the number of objects in the scene.

3353

Objm = AI

Trajectory of AA

ot

Target Object Label X

t

II

III

IV

V

VI

T

B





B



B





I: Pour from A to B
II move A to B
III Spoon up with D in A
IV Put material into B with D
V Mix inside B with D
VI Pour from C to B





C





C











Find shortest PATH



N















− log P(O | xt , yt ) − log P( yt | xt )Fig. 6.

− log P( xt , xt +1 )Estimation of X using Global DP

C

Fig. 8.

Six primitive Actions in the Scenario

D
B

A
Fig. 7.

Four Object used in the ExperimentIV. E XPERIMENTAL R ESULT

Fig. 9.

Visualized Input Trajectory in Data-set 4 [16386 frames]

A. Experimental Setup
Four different manipulation tasks were performed by asubject and were used to evaluate the proposed method.
There were four objects in the scene and an electromagnetic
motion tracking system (Polhemus FASTRAK) was used toobserve the trajectory of each object during demonstrations.
Fig. 7 shows the objects used in this experiment.
As shown in Fig.8, six actions are defined. A subject
was instructed to perform a task along a scenario madeby combining six actions. To emulate the change in theenvironment during long-term observation, the subject was
instructed to relocate the objects on the table several times
so that the relative relationship between static objects waschanged.
Fig.9 shows one of the visualized trajectory data set.
B. Evaluation
The proposed method is compared with the method proposed in [11]. In [11], the combinatorial optimization problem is solved by efficiently sampling the solution space via
Markov Chain Monte Calro (MCMC) algorithm.
TableI, II, III, IV shows the presented scenario and theresult of detecting repetitious motion patterns using two
different methods.
As an error measure, Precision and Recall are calculated
from True Positive (TP), False Positive (FP) and False
Negative (FN) as defined in eq.(15).

Precision =TP
TP, Recall =TP + FPTP + FN(15)

C. Discussion
Since the data set used in the experiment were relatively
short, a clear difference was not found between two methods.
However, there was a tendency that the proposed method
results in the lower False Positive rate.
The MCMC method becomes drastically slow if theamount of data increases. Even if the amount of data ismoderate, it is sometimes difficult to decide when we should
end the algorithm. On the other hand, the proposed method
outputs the result in deterministic way and we do not haveto worry about the termination of the algorithm.
Several constant parameters in the probability function are
defined ad-hoc and they should be adjusted to achieve better
error ratio.
V. C ONCLUSION
This paper presents a method for detecting repetitious
relative motion patterns among multiple trajectories in polynomial time.
The problem is formulated as a combinatorial optimization
problem with two parameters and is solved using local

3354

TABLE I
E VALUATION FOR DATA - SET 1 [1788 FRAMES ]ActionNumber
MCMC Method [11]Proposed Method

III
3
0
0

IV
0
0
0

V
0
0
1

TP
0
1

FN
9
8

FP
6
0

Precision
0.0
1.00

Recall0.0
0.11

TABLE IIE VALUATION FOR DATA - SET 2 [3819 FRAMES ]ActionNumber
MCMC Method [11]Proposed Method

I
6
5
5

V
6
6
6

VI
6
6
4

TP
17
15

FN
1
3

FP
8
0

Precision
0.68
1.00

Recall0.94
0.83

TABLE IIIE VALUATION FOR DATA - SET 3 [5176 FRAMES ]ActionNumber
MCMC Method [11]Proposed Method

II
6
6
5

III
6
0
0

IV
6
6
2

V
5
0
0

VI
7
7
2

TP
19
9

FN
11
21

FP
7
4

Precision
0.73
0.69

Recall0.63
0.3

Precision
0.53
0.87

Recall0.45
0.68

TABLE IVE VALUATION FOR DATA - SET 4 [16386 FRAMES ]ActionNumber
MCMC Method [11]Proposed Method

II
16
2
11

III
24
11
12

IV
24
11
13

V
12
0
11

and global Dynamic Programming (DP) in polynomial timeO(N log N ), where N is a total amount of data.
The proposed method is not applicable to real-time applications because Kd-tree must be built on the entire observation. However, it still offers a powerful tool to off-line
applications since a non-Markovian combinatorial optimization problem is solved in polynomial time due to the efficientcomputation algorithm.
The notion of meaningfulness is highly context-dependentand it is not practical to tackle it by the system alone. Future
work should be to bring a user into the action understanding
framework in interactive way, so that the system can naturally
incorporate the knowledge of the users.
VI. ACKNOWLEDGMENTS
This study was supported by Program for Improvement ofResearch Environment for Young Researchers from Special
Coordination Funds for Promoting Science and Technology(SCF) commissioned by the Ministry of Education, Culture,
Sports, Science and Technology (MEXT) of Japan.
R EFERENCES[1] K. Ikeuchi and T. Suehiro, “Toward an assembly plan from observation
part i: Task recognition with polyhedral objects,” IEEE Trans. Robotics
and Automation, vol. 10, no. 3, pp. 368–384, 1994.

VI
20
19
20

TP
43
67

FN
53
32

FP
38
10

[2] Y. Kuniyoshi, M. Inaba, and H. Inoue, “Learning by watching,” IEEE
Trans. Robotics and Automation, vol. 10, no. 6, pp. 799–822, 1994.
[3] J. Takamatsu, T. Morita, K. Ogawara, H. Kimura, and K. Ikeuchi,“Representation for knot-tying tasks,” IEEE Transactions on Robotics,
vol. 22, no. 1, pp. 65–78, 2006.
[4] S. Nakaoka, A. Nakazawa, K. Yokoi, and K. Ikeuchi, “Leg motion
primitives for a dancing humanoid robot,” in Int. conf. on Robotics
and Automation, 2004, pp. 610–615.
[5] T. Inamura, Y. Nakamura, and I. Toshima, “Embodied symbol emergence based on mimesis theory,” Int. Journal of Robotics Research,
vol. 23, no. 4, pp. 363–377, 2004.
[6] T. Mori, Y. Nejigane, M. Shimosaka, Y. Segawa, T. Harada, and
T. Sato, “Online recognition and segmentation for time-series motion
with hmm and conceptual relation of actions,” in Int. conf. onIntelligent Robots and Systems, 2005, pp. 2569–2574.
[7] T. Zhao, T. Wang, and H. Shum, “Learning a highly structured motion
model for 3d human tracking,” in Proc. of Asian Conference ofComputer Vision, 2002.
[8] A. Boick and A. Wilson, “A state-based approach to the representation
and recognition of gesture,” IEEE Transactions on Pattern Analysis
and Machine Intelligence, vol. 19, no. 12, pp. 1325–1337, 1997.
[9] K. Ogawara, J. Takamatsu, H. Kimura, and K. Ikeuchi, “Extractionof essential interactinos through multiple observations of humandemonstrations,” IEEE Transactions on Industrial Electronics, vol. 50,
no. 4, pp. 667–675, 2003.
[10] S. Uchida, A. Mori, R. Kurazume, R. ichiro Taniguchi, andT. Hasegawa, “Logical dp matching for detecting similar subsequence,” in Proc. of Asian Conference of Computer Vision, 2007.
[11] K. Ogawara, “Learning meaningful interactions from observation by
repetitious motion analysis,” in The Third Joint Workshop on Machine
Perception and Robotics, 2007, pp. OS2–3.

3355