目次
1. モジュール型学習機構における例示の理解に基づいた自律的なタスク分解,
高橋 泰岳 [1][2], 西 智樹 [1], 浅田 稔 [1][2] (1 大阪大学, 2 阪大 FRC)

. . . . . . . . . . . . . . . . .

1

2. モジュール型学習機構を用いたマルチエージェント環境における競合行動の同時学習,
高橋 泰岳 [1][2], 枝澤 一寛 [1], 野間 健太郎 [1], 浅田 稔 [1][2] (1 大阪大学, 2 阪大 FRC) . . . . . . .

9

3. 自律移動ロボットにおける強化学習による軌道生成法の検討,
清水 昌樹, 藤田 誠, 宮本 弘之 (九州工業大学大学院) . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4. スクリプト言語 Lua を用いたロボカップ四足ロボットリーグシミュレータ,小林 隼人 [1]，井上 淳 [1]，石野 明 [2]，篠原 歩 [3] (1 九州大学大学院システム情報科学府，

2 九州大学大学評価情報室，3 東北大学大学院情報科学研究科) . . . . . . . . . . . . . . . . . . . . 20
5. 統合シミュレーションのためのデータのバージョン管理の形式的考察,
野田 五十樹 ((独) 産業技術総合研究所) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

6. 照明変動に頑健な ID 認識とロボットの姿勢検出,
永橋 知行，清水 彰一，藤吉 弘亘 (中部大学工学部情報工学科) . . . . . . . . . . . . . . . . . . . . 32

7. 小型 (F180) リーグのためのイメージモザイクによるグローバルビジョンシステム,
林 裕司, 遠山 聖司, 藤吉 弘亘 (中部大学工学部情報工学科) . . . . . . . . . . . . . . . . . . . . . . . 38

8. 行動による通信 B-MODEM,
西野 順二, 戸田 英治 (電気通信大学システム工学科) . . . . . . . . . . . . . . . . . . . . . . . . . . 44

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-1 (5/24)

モジュール型学習機構における例示の理解に基づいた自律的なタスク分解
Self Task Decomposition for Modular Learning System through Interpretation of Instruction byCoach高橋 泰岳 1,2 , 西 智樹 1 , 浅田 稔 1,2
Yasutake Takahashi ,Tomoki Nishi and Minoru Asada
1
1

阪大 ,2 阪大 FRC

2Osaka University , HANDAI Frontier Research Center

Abstract

Fortunately, a long time-scale behavior might often
be decomposed into a sequence of simple behaviors ingeneral, and therefore, the search space can be divided
into smaller ones. In the existing studies, however, task
decomposition and behavior switching procedures are
given by the designers (ex. [3, 9, 10]). Others adopt
the heuristics or the assumption that are not realisticfrom the view point of real robot application (ex. [4, 5,
7, 8]). Doya et al. [6] have proposed MOdular Selection
And Identification for Control (MOSAIC), which is a
modular RL architecture for non-linear, non-stationary
control tasks. This method decomposes a whole state
space to a number of areas so that each expert module can produce good performance in the assigned area,
however, all learning modules share the one state spacethat consists of a few variables.
When we develop a real robot that learns various behaviors in its life, it seems reasonable that a human instructs or shows some example behaviors to the robot toaccelerate the learning before it starts to learn (ex. [12,1]). This idea was applied to a monolithic learning module. To cope with more complicated tasks, this idea canbe extended to a multi-module learning system. That is,
the instruction will help a learner to find useful subtasks.
In this paper, we introduce an idea that the capability of a learning module defines the size of subtasks.
We assume that each module can maintain a few number of state variables and this assumption is reasonable
for real robot applications. Then, the system decomposes a long-term task into short-term subtasks with selfinterpretation of coach instructions so that one learning module with limited computational resources can acquire a purposive behavior for one of these subtasks. We
show experimental results with much more sensors suchas normal and omni-vision systems and 8 directions infrared range sensors.

One of the most formidable issues of RL application to real robot tasks is how to find a suitable state space, and this has been much more
serious since recent robots tends to have moresensors and the environment including otherrobots becomes more complicated. In order
to cope with the issue, this paper presents amethod of self task decomposition for modular
learning system based on self-interpretation of
instructions given by a coach. Unlike the conventional approaches, the system decomposesa long-term task into short-term subtasks sothat one learning module with limited computational resources can acquire a purposive behavior for one of these subtasks. Since instructions are given from a viewpoint of coach who
has no idea how the system learns, they are interpreted by the learner to find the candidates
for subgoals. Finally, top layer of the hierarchical RL system coordinates the lower learning
modules to accomplish the whole task. The
method is applied to a simple soccer situationin the context of RoboCup.

1

Introduction

Reinforcement learning (hereafter, RL) is an attractive
method for robot behavior acquisition with little or noa priori knowledge and higher capability of reactive
and adaptive behaviors [3, 2]. However, a simple andstraightforward application of RL methods to real robot
tasks is difficult because of the enormous time for exploration that scales exponentially with the size of thestate/action space. The recent robots tend to have manykinds of sensors like normal and omni-vision systems,
touch sensors, infrared range sensors, and so on. They
can receive a variety of information from these sensors,
especially vision sensors. This fact indicates that thedifficulty of RL application to real robot tasks becomes
more serious.

2

Basic Idea

There are a learner and a coach in a simple soccer situation (Fig. 1). The coach has a priori knowledge of atask to be played by the learner while s/he does not have
any idea about the system of the learner. On the other1Instructionx2
x3

SubgoalCandidatex1

x4
State Space Decompositionx5

Goal State

x4
xn

x2

Gtask
xn

x3

x1

x1

xn-1
x2

x2

Module Available Area

New Subgoal
Candidate

Module Available Area
SubgoalCandidate

x3

x1

x4
State Space Decompositionx3

x5

Subgoal Gsub

x2

x4

xn

xn
x1

x2
x1

New Subgoal
Candidate

Module Avairable Area

Module Available Area
SubgoalCandidate

x2
x3

x1

x4
x5
xn

Figure 3: Rough sketch of the idea of task decomposition procedure

2

xn-1

1. find module unavailable areas in the instructions
and regard them as unknown subtask.
2. assign a new learning module.
(a) list up subgoal candidates for the unknown subtasks on the whole state space.
(b) decompose the state space into subspaces thatconsist of a few state variables.
(c) check all subspaces and select one in which thesubgoal candidates reach a certain area best
(Gsub in Fig. 3).
(d) generate another leanring module with the selected subspace as a state space and the certain
area as the goal state.

Figure 1: A coach gives instructions to a learner

Figure 2: The learner follows the instructions and finds
basic behaviors by itself

3. check the areas where the assigned modules areavailable.
4. exit if the generated modules cover all segments of
instructed behaviors. Else goto 1.
We will explain the details of the implementations ofabove capabilities from 5 to 7.

3

hand, the learner just follows the instructions without
any knowledge of the task. After some instructions given
by a coach, the learner decomposes the whole task into
a sequence of subtasks, acquires a behavior for each subtask, and coordinates these behaviors to accomplish thetask by itself . In Fig. 1, the coach instructs an shooting
a ball into a yellow goal with obstacle avoidance. Fig.
2 shows an example that the system decomposes thistask into three subtasks and assigns them to three modules that maintain state spaces consist of ball variables,
opponent and goal ones, and goal ones, respectively.

Robot, Tasks, and assumption

Figure 4: A real robot

Figure 5: Captured camera images
Fig. 3 show a rough sketch of the idea of the task
decomposition procedure. The top of the Fig. 3 showsa monolithic state space that consists of all state variables (x1 , x2 , · · · , xn ). The red lines indicate sequencesof state value during the given instructions. As we assume beforehand, the system cannot have such a hugestate space, then, decomposes the state space into subspaces that consist of a few state variables. The system
regards that the ends of the instructions represent goalstates of the given task. It checks all subspaces and selects one in which the most ends of the instruction reacha certain area (Gtask in Fig. 3). The system regards thisarea as the subgoal state of a subtask which is a part of
the given long-term task. The steps of the procedure areas follows:

Fig. 4 shows a mobile robot we have designed andbuilt. The robot has a normal camera in front of body,an omni-directional camera on the top, and infra red distance sensors around the body. Fig. 5 show the imagesof both cameras. A simple color image processing is applied to detect the ball, the goal, and an opponent in
the image in real-time (every 33ms). Table 1 shows 39
candidates for state variables. The mobile platform is anomni-directional vehicle (any translation and rotation on
the plane). The tasks for this robot are chasing a ball,navigating on the field, shooting a ball into the goal,and so on. We assume that the given task has someabsorbing goals, that is, the tasks are accomplished if
the robot reaches to certain situations. We also assume

3

Table 1: The candidates of state variables
state variablefeatureNormal camera
Xpb
Ball X
Ypb
Ball Y
Dpb
Ball DistanceApb
Ball Area
Xpm g
Own Goal X
Ypm g
Own Goal Y
Dpmg
Own Goal DistanceApmg
Own Goal Area
Xpog
Opponent Goal X
Ypog
Opponent Goal Y
Dpog
Opponent Goal Distance
Apog
Opponent Goal Area
Omni vision camera
Xob
Ball X
Yob
Ball Y
Dob
Ball Distance
Aob
Ball AreaθobBall Angle
Xomg
Own Goal X
Yomg
Own Goal Y
Domg
Own Goal Distance
Aomg
Own Goal Area

θomg
Xoog
Yoog
Doog
Aoog
θoog
θbmg
θbog
Dbmg
Dbog

IRn
IRne
IRe
IRse
IRs
IRsn
IRw
IRnw

that a long time-scale task can be decomposed into asequence of simple sub-tasks and the state space of eachsimple sub-task consists of a few state variables.

Own Goal Angle
Opponent Goal X
Opponent Goal Y
Opponent Goal DistanceOpponent Goal Area
Opponent Goal Angle
Relative Angle
between ball and own goal
Relative Angle
between ball and opponent goal
Relative distance
between ball and own goal
Relative distance
between ball and opponent goal
IR sensor
IR north
IR north east
IR eastIR south east
IR south
IR south west
IR westIR north west

given byQ(s, a)

=

X
s0

4

V (s)

Hierarchical Multi-Module Learning
System

=

i
h
0 0
a
a
, (1)
P̂ss
0 R̂ss0 + γ max Q(s , a )0amax Q(s, a) ,
a

(2)

a
a
where P̂ss
0 and R̂ss0 are the state-transition probabilities
and expected rewards, respectively, and γ is a discountrate.

The architecture of multi-module learning system is thesame one in [11]. We briefly review it here. The robot
prepares learning modules of one kind, makes a layer
with these modules, and constructs a hierarchy between
the layers. The hierarchy of the learning module’s layers
can be regarded as a role of task decomposition. Each
module has a forward model (predictor) which represents the state transition model, and a behavior learner(policy planner) which estimates the state-action valuefunction based on the forward model in an RL manner(Fig. 6(b)). The state and the action are constructedusing sensory information and motor commands, respectively at the bottom level.
The input to and output from the higher level are thegoal state activation and the behavior command, respectively, as shown in Fig. 6. The goal state activation g isa normalized state value, and g = 1 when the situation is
the goal state. When the module receives the behavior
command b from the higher modules, it calculates the
optimal policy for its own goal, and sends action commands to the lower module. The action command at thebottom level is translated to an actual motor command,then the robot takes an action in the environment.
An approximated action value function Q(s, a) for astate action pair (s, a) and state value function V (s) are

5

Availability Evaluation

The learner needs to check the availability of learned
behaviors that help to accomplish the task by itself because the coach neither knows what kind of behavior thelearner has already acquired nor shows perfect example behaviors from the learner’s viewpoint. The learnershould suppose a module as valid if it accomplishes thesubtask even if the greedy policy seems different fromthe example behavior. Now, we introduce AE in orderto evaluate how suitable the module’s policy is to thesubtask:AE(s, ae ) =Q(s, ae ) − mina0 Q(s, a0 ),maxa0 Q(s, a0 ) − mina0 Q(s, a0 )(3)

where ae indicates the action taken in the instructed example behavior. AE becomes larger if ae leads to thegoal state of the module while it becomes smaller if aeleaves from the goal state (see Fig. 7). Then, we prepare a threshold AEth , and the learner evaluates themodule as valid for a period if AE > AEth . If there
are modules whose AE exceeds the threshold AEth , thelearner selects the module which keeps AE > AEth for4Learning
Moduleupper layer
state

actiong 1 ... gn

b 1 ... bn

Learning
Module 1

Learning
Module n(s 11, ... ,s1m )lower layer(s n1, ... ,snm )1nstate 1state nactionFigure 7: Sketch of state value function and action value
an existing learning module is available

sensormotor

new learning modules are neededWorld(a) A whole system

AE
Goal State Activation

AEth

Behavior Command

PlannerignoreaPss’ R st

Predictor

State

Figure 8: Availability identification during the given sample behavior

Action(b) A moduleis that many instructed data reach to the same region
if the instructed behaviors contains shared subtasks andthe more sensitive state variable tends to be better forcontrol. Each state variable is quantized into a numberof blocks beforehand. The system takes histograms of
the end points of the unassigned periods on the all statevariables (Fig. 10). It regards the highest scored region
on each state variable xi as the goal region GRi . Then,the system selects one state variable that maximizes thefollowing evaluation measure Ci :Figure 6: A multi-layered learning systemlongest period among the modules (see Fig. 8). In Fig.
3, ”Module Available Area” indecates the one in which
AE > AEth .

6

New Learning Module Assignment

If there is no module which has AE > AEth for a period,
the learner creates a new module which will be assigned
to the subtask (see procedure 2 in ??). To assign a newmodule to such a subtask, the learner identifies the state
space and the goal state. The system follow the two
steps to select an appropriate state space and the goalstate for the subtask:

Ci =

X

li,k ,kwhere i and li,k are indices of the state variables xi andthe transition length on the state variables xi of the kth segmented data of which end points are on the goal
region GRi , respectively. Ci describes that how many
segmented data reach to the goal region candidate GRi
and how the state variable is sensitive during the segmented sequences.

• selection of one state variable that specifies the goalstate, and• construction of a state space including the selectedstate variable.
In order to find one state variable that specifies the goalstate best, the system lines up the candidates for a goal
region in term of state variables. On the other hand, inorder to select another state variable, the system evaluates performance of Q value estimation.
Fig. 9 shows that the system regards the end pointsof the periods where no module is assigned as candidates for the goal state of the unknown task. In Fig. 3,”Subgoal Candidate” indicate the end point. The idea

The system constructs a state space including the selected state variable. It start from a state space withthe one state variable. If the performance of the learned
behavior for the subtask is bad (the success rate does
not exceed a pre-determined threshold), it adds anotherstate variables with which the accuracy of action value
Q estimation improves. It is important to estimate the
Q value correctly in order to acquire an appropriate behavior. We introduce an adequacy measure QE defined5New module
Assignment

AE ( s , a e )

g

3

1

start

LM 3

LM 1
0

2

Figure 9: Subgoal candidate pointg

2 Goal Region

Instructions

LM 2

1

GR1

x3

g

t

3

goal

SubgoalCandidate

Figure 11: An example state transition on upper layer
state space

Selected state variable

x1
l1,k

state space based on their goal state activations (say g1 ,g2 , and g3 ). Fig. 11 shows an example state transitionon the upper layer state space. At the initial situation,
all lower modules activate low. The system sends a command to the module LM1 , then the goal state activationof LM1 , that is g1 , goes up. After LM1 finishes its own
task, the upper module sends a command to the module
LM2 , and accomplishes the whole task by finally activating LM3 at last.

x2
x2

GR3

x1

x3
1

: Subgoal Candidate

l3,kFigure 10: Specification of goal region and its
state variable for a subgoal

8

as equations (4), (5), and (6) :
QE

=

1

P

∀ a∈A,∀ s∈Se(s, a) =Pe(s, a).

p
P (1 − P ) .
0= P (V (s ) > V (s)|s, a) .

(4)
(5)
(6)

P (V (s0 ) > V (s)|s, a) indicates that the probability of thecase in which the next state value V (s0 ) is greater thanthe current state value V (s) when the robot takes action
a at the state s and goes to the next state s0 . The reason
not to use just an error of state value estimation is that
it is too sensitive to evaluate the state space with thestate value estimation error because the state transition
is often probabilistic. We expect that the rough criterion
such as it distinguish the state value goes up or down isenough and robust to evaluate the state space.
Even if we got a module with a proper policy based on
the state transition model and the reward model, there
is no assurance that the module has acquired sufficientperformance for the subtask. Before the system adds a
new module to the available module database, it checks
the success rate of the module. If the success rate is low,
the system discards the module.

7

Experiments

Figure 12: Examples of Instructed behaviors
We have instructed the robot from a simple behavior (ball chasing) to a complicated one (shooting a ballwith obstacle avoidance) in [11], however, the there is a
criticism that the step-by-step instruction implies task
decomposition to the robot. Therefore we adopt onlyshooting behavior for the task decomposition and thecoordination. Fig. 12 shows four examples of the behaviors instructed by the coach. The total number of
instruction is 21 for this experiment.
According to the learning procedure, the system produced four modules for the instructed behaviors. The
modules are LM1 (Apb , Xpb ), LM2 (θog ), LM3 (Yob , Xob ),Learning behavior coordination

After the procedures mentioned above, necessary andsufficient modules are built at the lower layer. Then,the learning system needs to put a new learning module
at the upper layer (top of the Fig.6(a)) which learns tocoordinate the lower modules. The upper module has astate space constructed with the goal state activations of
the lower modules. A set of actions consists of commands
to the lower modules.
For example, suppose three modules at the lower level(say LM1 , LM2 , and LM3 ), then the upper module has a

6

LM4
LM3
LM2
LM1

goal state activation

AE

1

0.5

0
1

0.5

0
0

50

100

150

200

250

300

350

Step

Figure 13: Sequences of the selected module, availability evaluations and goal state activations of modules
through an instruction
Figure 15: Acquired behaviors for shooting task
[2] M. Asada, S. Noda, S. Tawaratumida, andK. Hosoda. Purposive behavior acquisition for areal robot by vision-based reinforcement learning.
Machine Learning, Vol. 23, pp. 279–303, 1996.
Figure 14: Acquired hierarchy for the shooting behavior[3] Jonalthan H. Connell and Sridhar Mahadevan.
ROBOT LEARNING. Kluwer Academic Publishers, 1993.

and LM4 (Aob , θob ). For example LM1 (Apb , Xpb ) indicates that the modules has a state space that consists of
the area of ball on the normal camera image (Ao b) andthe x position of the ball on the normal camera image(Xpb ). Fig. 13 shows sequences of the selected module, availability evaluations and goal state activations ofmodules through an instruction.
Fig. 15 shows the learned behaviors. The start positions of the behaviors are the same ones of the instructions for comparison. The trajectories of learned behaviors are different from the instructed behaviors. This
fact indicates that the learner recognizes the subtasks
based on its own modules, understands the objectives ofthe subtasks, and executes appropriate actions for them.

9[4] Bruce L. Digney. Emergent hierarchical control
structures: Learning reactive/hierarchical relationships in reinforcement environments. In Pattie
Maes, Maja J. Mataric, Jean-Arcady Meyer, Jordan Pollack, and Stewart W. Wilson, editors, Fromanimals to animats 4: Proceedings of The fourth
conference on the Simulation of Adaptive Behavior:
SAB 96, pp. 363–372. The MIT Press, 1996.
[5] Bruce L. Digney. Learning hierarchical control
structures for multiple tasks and changing environments. In Rolf Pfeifer, Bruce Blumberg, JeanArcady Meyer, and Stewart W. Wilson, editors,
From animals to animats 5: Proceedings of The fifth
conference on the Simulation of Adaptive Behavior:
SAB 98, pp. 321–330. The MIT Press, 1998.

Conclusion

We proposed a hierarchical multi-module learning system based on self-interpretation of instructions given bya coach. We applied the proposed method to our robot
and showed results for a simple soccer situation in thecontext of RoboCup.

[6] Kenji Doya, Kazuyuki Samejima, Ken ichi Katagiri, and Mitsuo Kawato. Multiple model-based reinforcement learning. Technical report, Kawato Dynamic Brain Project Technical Report, KDB-TR08, Japan Science and Technology Corporatio, June
2000.

References[7] Bernhard Hengst. Generating hierarchical structure
in reinforcement learning from state variables. In
Riichiro Mizoguchi and John K. Slaney, editors, 6thPacific Rim International Conference on Artificial
Intelligence (PRICAI 2000), Vol. 1886 of Lecture
Notes in Computer Science. Springer, 2000.

[1] M. Asada, S. Noda, S. Tawaratsumida, andK. Hosoda. Vision-based reinforcement learning for
purposive behavior acquisition. In Proc. of IEEE
Int. Conf. on Robotics and Automation, pp. 146–
153, 1995.

7

[8] Bernhard Hengst. Discovering hierarchy in reinforcement learning with HEXQ. In Proceedingsof the Nineteenth International Conference on Machine Learning (ICML02), pp. 243–250, 2002.
[9] Peter Stone and Mamuela Veloso. Layered approachto learning client behaviors in the robocup soccer
server. Applied Artificial Intelligence, Vol. 12, No.
2-3, 1998.
[10] Peter Stone and Manuela Veloso. Team-partitioned,
opaque-transition reinforcement learning.
In
M. Asada and H. Kitano, editors, RoboCup-98:
Robo Soccer World Cup II, pp. 261–272. Springer
Verlag, Berlin, 1999.
[11] Yasutake Takahashi, Koichi Hikita, and Minoru
Asada. Incremental purposive behavior acquisition
based on self-interpretation of instructions by coach.
In Proceedings of the 2003 IEEE/RSJ International
Conference on Intelligent Robots and Systems, pp.
686–693, Oct 2003.
[12] Steven D. Whitehead. Complexity and cooperationin q-learning. In Proceedings Eighth International
Workshop on Machine Learning (ML91), pp. 363–
367, 1991.

8

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-2 (5/24)

モジュール型学習機構を用いたマルチエージェント環境における競合行動の同時学習
Simultaneous Learning to Acquire Competitive Behaviors
in Multi-Agent System based on Modular Learning System

高橋泰岳 枝澤一寛 野間健太郎 浅田稔
Yasutake Takahashi, Kazuhiro Edazawa, Kentarou Noma and Minoru Asada
Dept. of Adaptive Machine Systems, Graduate School of Engineering, andHandai Frontier Research Center, Osaka University

yasutake,eda,noma,asada@er.ams.eng.osaka-u.ac.jp
Abstract

Stone [8] have applied a reinforcement learning systemwith function approximater to the keep-away problem
in the situation of RoboCup simulation league. In theirwork, only the passer learns his policy to keep the ballaway from the opponents. The other agents, receivers
and opponents, follow fixed policies given by the designer
beforehand.
Asada et al. [2] proposed a method that sets a global
learning schedule in which only one agent is specified as alearner and the rest of agents have fixed policies. Therefore, the method cannot handle the alternation of the
opponents policies. Ikenoue et al. [3] showed simultaneous cooperative behavior acquisition by fixing learners’
policies for a certain period during the learning. Thesestudies suggest that it is enable to acquire a reasonablebehavior in a multi-agent environment if the learner can
see the environment including the other agents almost
fixed because the others keep their policies for a certain
time. In the case of cooperative behavior acquisition,
both agents do not have any reason to change their policies while they successfully acquire positive rewards withthe result of the cooperative behavior for each other. The
agents tend to update their policies gradually so that thestate transition probabilities seem almost fixed from theview point of the other learning agents.
In case of competitive behavior acquisition in a multiagent environment, however, it is unlikely that the agent
tends to select the action that causes positive rewards forthe opponents and a negative reward for itself. The punished agent tends to change drastically its policy so thatit can acquire a positive reward by which it gives a negative reward to the opponents. This policy alternation
causes dynamic changes in the state transition probabilities from the viewpoint of the learning agent therefore it
seems difficult to directly apply the reinforcement learning method to a multiagent system.
A modular learning approach would provide one solution to this problem. If we can assign multiple learning
modules to different situations, respectively, in each ofwhich the state transition probabilities can be regarded
as constant, then the system could show a reasonable
performance. Jacobs and Jordan [7] proposed the mix-

The existing reinforcement learning approaches
have been suffering from the policy alternationof others in multiagent dynamic environments.
A typical example is a case of RoboCup competitions since other agent behaviors may cause
sudden changes in state transition probabilitiesof which constancy is needed for the learning
to converge. The keys for simultaneous learning to acquire competitive behaviors in such anenvironment are• a modular learning system for adaptation to
the policy alternation of others, and• an introduction of macro actions for simultaneous learning to reduce the search space.
This paper presents a method of modular learning in a multiagent environment, by which thelearning agents can simultaneously learn their
behaviors and adapt themselves to the situations as consequences of the others’ behaviors.

1

Introduction

There have been an increasing number of approaches torobot behavior acquisition based on reinforcement learning methods [1, 4]. The conventional approaches need anassumption that the state transition is caused by an action of a learning agent so that the learning agent canregard the state transition probabilities as constant during its learning. Therefore, it seems difficult to directly
apply the reinforcement learning method to a multiagent
system because a policy alteration of other agents may
occur, which dynamically changes the state transition
probabilities from the viewpoint of the learning agent.
RoboCup provides such a typical situation, that is, ahighly dynamic, hostile environment, in which agents
must obtain purposive behaviors.
There are a number of studies on reinforcement learning systems in a multiagent environment. Kuhlmann and9Receiver 1
Intercepter

Receiver 2

PasserFigure 1: Task : 3 on 1

Figure 3: Viewer of simulator

Figure 2: A real robot
Figure 4: Adaptive behavior selection based on Multimodule learning system

ture of experts, in which a set of the expert modules learn
and the gating system weights the output of the each expert module for the final system output. This idea is very
general and has a wide range of applications (ex. [11, 9,
14, 13, 5]).
We adopt the basic idea of the mixture of experts into
an architecture of behavior acquisition in the multi-agent
environment. Takahashi et al. [12] have shown preliminary experimental results of behavior acquisition in themulti-agent environment, however, the learning modules
were assigned by the human designer. In this paper, first,
we show how it is difficult to directly introduce a multimodule learning system for even single agent learning
in a multi-agent environment because of its complexity
and introduce a simple learning scheduling which makes
it relatively easy to assign modules automatically. Second, we introduce macro actions to realize simultaneous
learning in multiagent environment by which the eachagent does not need to fix its policy according to somelearning schedule. Elfwing et al. [6] introduced macro
actions to acquire a cooperative behavior with two realrodent robots. The exploration space with macro actions
becomes much smaller than the one with primitive actions, then, the macro action increases the possibility tomeet cooperative experiences and leads the two agents tofind a reasonable solution in realistic learning time. We
show the introduction of macro actions enable the agentsto learn competitive behaviors simultaneously. We haveapplied the proposed multi-module learning system tosoccer robots which participate in RoboCup competitionand show experimental results on computer simulation
and real robot implementation.

2

there are one opponent and other three players. The
player nearest to a ball becomes to a passer and passes
the ball to one of the teammates (receivers) while theopponent tries to intercept it.
Fig. 2 shows a mobile robot we have designed andbuilt. Fig. 3 shows the viewer of our simulator for ourrobots and the environment. The robot has an omnidirectional camera system. A simple color image processing is applied to detect the ball, the intercepter, andthe receivers on the image in real-time (every 33ms).
The left of Fig. 3 shows a situation in which the agent
can encounter and the right images show the simulated
ones of the normal and omni vision systems. The mobile
platform is an omni-directional vehicle (any translation
and rotation on the plane).

3

Multi-Module Learning System

3.1

Basic Idea

The basic idea is that the learning agent could assign one
behavior learning module to one situation which reflects
other agent’s behavior and the learning module would
acquire a purposive behavior under the situation if theagent can distinguish a number of situations in each ofwhich the state transition probabilities are almost constant. We introduce a modular learning approach to realize this idea (Fig. 4). A module consists of a learningcomponent that models the world and a action planner. The whole system follows these procedures:• select a model which represents the best estimation
among the modules,

Tasks and assumption

Fig.1 shows a situation which the learning agents aresupposed to encounter. The game is like a three on one;

• update the model, and10• calculate action values to accomplish a given task
based on dynamic programming.

3.2.3 Module Selection for Action Selection
The reliability of the module becomes larger if themodule does better state transition prediction during acertain period, else it becomes smaller. We assume thatthe module which does the best state transition prediction has the best policy against the current situation because the planner of the module is based on the model
which describes the situation best. In the proposed architecture, the reliability is used for gating the action
outputs from modules. We calculate an execution-time
reliability exec gi of the module i as follows:

As an experimental task, we suppose ball passing withpossibility of being intercepted by the opponent (Figs. 1
and 3). The problem for the passer (intercepter) here isto select one model which can most accurately describe
the intercepter’s (passer’s) behavior from the viewpointof the agent and to take an action based on the policy
which is planned with the estimated model.
3.2

Architecture

exec g =

Gate

i

0
Y

t

eλpi

t=−T +1ssPlannerawhere pi is an occurrence probability of the state transition from the previous (t − 1) state to the current (t)one according to the model i, and λ is a scaling factor.
The T indicate a period (step) to evaluate the reliabilityof the module and we set T as 5 in the following experiments. The agent continues to use the module for acertain period, for example 5 step or 1 second, after itchanges the module in order to avoid oscillation of thepolicies.

Environments Predictor

Figure 5: A multi-module learning system
Fig. 5 shows a basic architecture of the proposedsystem, that is, a multi-module reinforcement learning
system. Each module has a forward model (predictor)
which represents the state transition model, and a behavior learner (action planner) which estimates the stateaction value function based on the forward model in a reinforcement learning manner. This idea of combinationof a forward model and a reinforcement learning system
is similar to the H-DYNA architecture [10] or MOSAIC[5]. The system selects one module which has the best
estimation of a state transition sequence by activating agate signal corresponding to a module while deactivating the gate signals of other modules, and the selected
module sends action commands based on its policy.

3.2.4

Module Selection for Updating Models
We use an update-time reliability update g of the modiule for updating modules. The calculation of this reliability contains the future state transition probabilities:
update g =i(1)R̂ass0 = E{rt+1 |st = s, at = a, st+1 = s0 }

(2)

4

.

Behaviors Acquisition under
SchedulingAs we mentioned in 1, first, we show how it is difficult
to directly introduce the proposed multi-module learning
system in the multi-agent system. We introduce a simple
learning scheduling in order to make it relatively easy toassign modules automatically.
4.1

Configuration

The state space is constructed in terms of the centroidof the ball on the image, the angle between the ball andthe intercepter, and the angles between the ball and thereceivers (see Figs. 10 (a) and (b)). We quantized theball position space 11 by 11 as shown in Fig. 10 (a) andthe each angle into 8. As a result, the number of states
becomes 112 × 8 × 8 × 8 = 61952. The action space isconstructed in terms of desired three velocity values (xd ,yd , wd ) to be sent to the motor controller (Fig. 7). Eachvalue is quantized into three, then the number of actionis 33 = 27. The robot has a pinball like kick device,
and it automatically kicks the ball whenever the ballcomes to the region to be kicked. It tries to estimate themapping from sensory information to appropriate motor
commands by the proposed method.
The initial positions of the ball, the passer, the intercepter, and receivers are shown in Fig. 1. The opponent

Each module has a reward model R̂ass0 , too:We simply store all experiences (sequences of stateaction-next state and reward) to estimate these models.
3.2.2 Planner
Now we have the estimated state transition probabilaaities P̂ss
0 and the expected rewards R̂ss0 , then, an approximated state-action value function Q(s, a) for a state
action pair s and a is given by
h
i
X
a
a
0 0
Q(s, a) =
P̂ss
, (3)
0 R̂ss0 + γ max Q(s , a )
0
s0

t

eλpi

t=t−T

3.2.1 Predictor
Each learning module has its own state transition
model. This model estimates the state transition proba
ability P̂ss
0 for the triplet of state s, action a, and next
0state s :a0P̂ss
0 = P r{st+1 = s |st = s, at = a}

t+T
Y

a

where γ is a discount rate.

11

first stage (250 trials), however, it goes down at the second stage because the obtained policy is biased against
ball
ball
the experiences at the fist stage and cannot follow thepolicy change of the opponent. Since the opponent takes
teammate2
one of the policies at random at the third stage, thelearning agent obtains about 50% of success rate. “withteammate1
out scheduling” means that we do not applied learningscheduling and the opponent changes its policy at ran(a) state variables (position) (b) state variables (angle) dom from the start. Somehow the performance of themonolithic module system without learning scheduling
Figure 6: State variables
is getting worse after the 200 trials. The multi-module
system without learning schedule shows the worst perwd
formance in our experiments. This result indicates that
it is very difficult to recognize the situation at the earlystage of the learning because the modules has too few exyd
periences to evaluate their fitness, then the system tends
to select the module without any consistency. As a rexd
sult, the system cannot acquires any valid policies at all.
opponent

Figure 7: Action variables
R block and L block

withoutscheduling
R block

schedulinghas two kinds of behaviors; it defend the left side, orright side. The passer agent has to estimate which direction the intercepter will defend and go to the positionin order to kick the ball to the direction the intercepter
does not defend. From a viewpoint of the multi-module
learning system, the passer will estimate which situationof the module is going on, select the most appropriate
module to behave. The passer acquires a positive reward
when it approach to the ball and kicks it to one of thereceivers.

L block

R block and L block1
multi module(scheduling)

success rate

0.8

0.6
mono. module(scheduling)
0.4
mono. module(without scheduling)

0.2

multi module(without scheduling)00

100 200 300 400 500 600 700 800 900 1000
trials4.2

Learning Scheduling
Figure 8: Success rate during the learning

We prepare a learning schedule composed of three stages
to show its validity. The opponent fixes its defending
policy as right side block at the first stage. After 250
trials, the opponent changes the policy to block the left
side at the second stage and continues this for another
250 trials. Then, the opponent changes the defending
policy randomly after one trial.
4.3

5

Simultaneous Learning with Macro
Actions

We introduce macro actions to realize simultaneous
learning in multiagent environment by which the eachagent does not need to fix its policy according to somelearning schedule. In this experiment, the passer andthe intercepter learn their behaviors simultaneously. The
passer learns behaviors for different situations which arecaused by the alternation of the intercepter’s policies,that is, blocking left side or right one. The intercepter
also learns behaviors for different situations which arecaused by the alternation of the passer’s policies, thatis, passing a ball to left receiver or right one.

Simulation Result

We have applied the method to a learning agent andcompared it with only one learning module. We havealso compared the performances between the methods
with and without the learning scheduling. Fig. 8 shows
the success rates of those during the learning. The success indicates that the learning agent successfully kickthe ball without interception by the opponent. The success rate indicates the number of successes in the last
50 trials. The “mono. module” in the figure indicates“monolithic module” system and it tries to acquire abehavior for both policies of the opponent. The multimodule system with scheduling shows a better performance than the one-module system. The monolithic
module with scheduling means that we applied learningscheduling mentioned in 4.2 even though the system has
only one learning module. The performance of this system is similar with multi-module system until the end of

5.1

Macro Actions and State Spaces

Fig. 9 shows the macro actions of the passer and theintercepter. The macro actions for the intercepter areblocking the pass way to the left receiver and right one.
On the other hand, the macroaction for the passer are
turning left, turning right around the ball, and approaching to the ball to kick it. A ball gazing control is embedded to the both learners. The number of the actions

12

ginning of learning, the passer is getting to acquire theappropriate behaviors corresponding to the intercepter’s
behaviors, and the both agents have almost equal successrate at the end of learning stage. The sum of the both
success rates is not 1 because the both player sometimes
failed to pass or intercept simultaneously.
In order to check if the both learners acquire appropriate behaviors against the opponent’s behaviors, we fixed
one agent’s policy and check that the other can selectan appropriate behavior and its success rate. Table 1
shows this results. The both players have two modules
and assign them to appropriate situations by themselves.
LM and the digit number right after the LM indicate
Learning Module and index number of the module, respectively. For example, the passer uses both LM0 and
LM1 and the intercepter use only LM0, then the passer’s
success rate, intercepter’s success rate, and draw rate are
59.0 %, 23.0%, and 18.0%, respectively. Apparently, theplayer switching multi-modules achieves higher successrate than the opponent using only one module. These results show that the multi-module learning system works
well for both.

intercepter
receiver1

receiver2

passerFigure 9: Macro actions
RCUUGT
DCNN
ǰ

T

ǰ
ǰ

TGEGKXGTTGEGKXGT(a) passer(b) intercepter

Figure 10: State variables
1

success_rate

0.8
0.6
0.4
0.2
0

passerintercepter
0

200

400

600

800 1000 1200 1400 1600
trialsFigure 11: Sequence of success rates during simultaneous
learning

reduced from 27 (see 4.1) primitives to 2 or 3 macro actions. The state space for the passer is constructed interms of the y position of the ball on the normal image,and the angle between the ball and the centers of intercepter, the ones between the balls and the two receiverson the image of omni-directional vision. The numberof the states reduced from 61952 (see 4.1 ) to 3773 because the set of macro actions enable us to select smaller
number of state variables and coarser quantization. The
state space for the intercepter is constructed in terms of
the y position of the passer on the image of normal visionsystem, and the angle between the ball and the passer
and the ones between the ball and the two receivers on
the image of omni-directional vision. The number of thestates is 2695.
5.2

Figure 12: A sequence of a behavior of passing a ballto the right receiver while the intercepter blocks the leftside
We have applied the same architecture to the realrobots. Fig. 12 shows the one example behaviors byreal robots. First, the intercepter tried to block the left
side, then the passer approached the ball with intention
to pass it to the right receiver. The intercepter foundthat it tried to block the wrong side and change to block
the other side (right side), but, it is too late to intercept
the ball and the passer successfully pass the ball to theright receiver.

6

Experimental Resutls

We have checked how the simultaneous learning of thepasser and intercepter works on our computer simulation. Both agents start to learn their behaviors fromscratch and have 1500 trials without any scheduling. Fig.
11 show the success rates during the simultaneous learning of the passer and the intercepter. This figure showsthat the intercepter has higher success rate at the be-Conclusion

In this paper, we proposed a method by which multiple
modules are assigned to different situations which arecaused by the alternation of the other agent policy andlearn purposive behaviors for the specified situations asconsequences of the other agent’s behaviors.
We introduced macro actions to realize simultaneous
learning of competitive behaviors in a multi-agent sys-

13

passer
LM0,LM1
LM0,LM1LM0
LM1
LM0,LM1

Table 1: Success rates for passer and receiver in different casesintercepter passer’s success rate[%] intercepter’s success rate [%]
LM0
59.0
23.0
LM1
52.7
34.3
LM0,LM1
25.6
55.0
LM0,LM1
26.0
59.3
LM,LM1
37.6
37.3

draw rate[%]
18.0
13.0
19.4
14.7
25.1

[9] Satinder P. Singh. The effeicient learnig of multiple
task sequences. In Neural Information Processing
Systems 4, pages 251–258, 1992.

tem. We have shown results of a soccer situation andthe importance of the learning scheduling in case of nonesimultaneous learning without macro actions and the validity of the macro actions in case of simultaneous learning in the multi-agent system.

[10] Satinder P. Singh. Reinforcement learning with ahierarchy of abstract models. In National Conference on Artificial Intelligence, pages 202–207, 1992.

References[11] Satinder Pal Singh. Transfer of learning by composing solutions of elemental sequential tasks. Machine
Learning, 8:323–339, 1992.

[1] M. Asada, S. Noda, S. Tawaratumida, andK. Hosoda. Purposive behavior acquisition for areal robot by vision-based reinforcement learning.
Machine Learning, 23:279–303, 1996.

[12] Yasutake Takahashi, Kazuhiro Edazawa, and Minoru Asada. Multi-module learning system for behavior acquisition in multi-agent environment. In
Proceedings of 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages
CD–ROM 927–931, October 2002.

[2] M. Asada, E. Uchibe, and K. Hosoda. Cooperative behavior acquisition for mobile robots in dynamically changing real worlds via vision-based reinforcement learning and development. Artificial
Intelligence, 110:275–292, 1999.
[3] Shoichi Ikenoue Minoru Asada and Koh Hosoda.
Cooperative behavior acquisition by asynchronous
policy renewal that enables simultaneous learning in
multiagent environment. In Proceedings of the 2002
IEEE/RSJ Intl. Conference on Intelligent Robots
and Systems, pages 2728–2734, 2002.

[13] J. Tani and S. Nolfi. Self-organization of modules and their hierarchy in robot learning problems: A dynamical systems approach. Technicalreport, Sony CSL Technical Report, SCSL-TR-97008, 1997.
[14] Jun Tani and Stefano Nolfi. Self-organization ofmodules and their hierarchy in robot learning problems: A dynamical systems approach. Technicalreport, Technical Report: SCSL-TR-97-008, 1997.

[4] Jonalthan H. Connell and Sridhar Mahadevan.
ROBOT LEARNING. Kluwer Academic Publishers, 1993.
[5] Kenji Doya, Kazuyuki Samejima, Ken ichi Katagiri, and Mitsuo Kawato. Multiple model-based reinforcement learning. Technical report, Kawato Dynamic Brain Project Technical Report, KDB-TR08, Japan Science and Technology Corporatio, June
2000.
[6] Stefan Elfwing, Eiji Uchibe, Kenji Doya, and Henrik I. Christensen1. Multi-agent reinforcement
learning: Using macro actions to learn a matingtask. In Proceedings of 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages CD–ROM, Sep 2004.
[7] R. Jacobs, M. Jordan, Nowlan S, and G. Hinton.
Adaptive mixture of local experts. Neural Computation, (3):79–87, 1991.
[8] Gregory Kuhlmann and Peter Stone. Progress inlearning 3 vs. 2 keepaway. In Daniel Polani, BrettBrowning, Andrea Bonarini, and Kazuo Yoshida,
editors, RoboCup-2003: Robot Soccer World Cup
VII. Springer Verlag, Berlin, 2004.

14

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-3 (5/24)

自律移動ロボットにおける強化学習による軌道生成法の検討
Trajectory Generation for a Mobile Robot by Reinforcement Learning

清水 昌樹, 藤田 誠, 宮本 弘之
Masaki Shimizu, Makoto Fujita, Hiroyuki Miyamoto

九州工業大学大学院
Kyushu Institute of Technology, Kitakyushu

shimizu-masaki@edu.brain.kyutech.ac.jp

Abstract

提案されている [3][4]。さらに階層型強化学習によって巨大な状態行動空間を解く研究も提案されている [5][6]。

強化学習はロボットに自律的に行動を生成させる

本論分では上記の問題を解くため２つのシンプルな方ための非常に有効な方法である。強化学習の中の法を提案する。最初の方法は本来未知な学習の初期値をQ-learning は比較的簡単なな方法であるが、タスクが複雑になるに従い学習時間が長くなる。さらに離散的に状態と行動空間を分割するため、ロ設計者が設定することである。少ない知識を与えること

ボットはスムーズな行動を得ることができない。

エージェントは全く間違った方向を探索しなくても良い。

これら問題を解決するため、我々は二つの方法を

２つめの方法は、状態と行動を等間隔で分割しないことで提案する。我々の方法の有効性を確かめるため、ある。移動ロボットの場合、従来は設定した数に従って状

我々はロボットサッカーのような動的環境におけ態と行動を等間隔に分割していた。しかし様々なターゲッ

る Ball-To-Goal タスクの軌道生成に Q-learning

トへ向かう行動を獲得するタスクでは、このような分割を適用するシミュレーションを行った。

は便利ではない。従って我々はターゲット周辺方向の行動によってエージェントは設計者の意図を理解し学習を始める。設計者が与えた初期値が最適な行動計画に近ければ、空間を細かく分割し、その他の行動空間を荒く分割した。

1

本論文では、これら２つの方法を使った１つの学習モ

緒言

ジュールだけで Ball-To-Goal タスクの行動軌道を２輪移

人間の仕事の一部をロボットに分担させたり、人間にとっ動ロボットに獲得させることを目的とする。またロボットて作業が困難な環境や危険な環境におけるロボットの活躍は単純な Ball-To-Goal タスクだけでなく攻撃や守備のよが望まれている。その分野において近年、自律移動ロボッ

うな状況に応じた高いレベルのタスクの複雑な行動軌道

トに関する研究が盛んである。ロボットが直面するタスも獲得させる。提案した方法の有効性を調べるためシミュクに対して人間が設計した行動計画は優れた性能を示す。

レーションにより実験を行った。

しかし設計者の能力以上の複雑なタスクでは行動計画の

2

設計者にかかる負担は大きくなる。
設計者の負担を軽減させるために強化学習を使いタス

プルトイ法

クの最適な行動計画を自律的に生成させることでロボット

Ball-To-Goal タスクはターゲットに向かうという意味から To-Ball タスクと To-Goal タスクに分けることができに行動を獲得させる。行動の指針を与える必要のある教る。そこでこの節では、まずロボットに Ball-To-Goal タ

師あり学習とは異なり、強化学習は環境の観測と可能な行

スクを学習させる前に人の手によって設計した理想的な動から自律的に学習が可能である。
ない。さらに Q-learning での状態や行動は不連続である。

To-Ball タスクでの運動制御法を提案する。従来、我々が用いていた運動制御法では、前進や回転の速度を加えたものがモータに与えられる。この方法だとロボットは常にこれらの問題のため、エージェントと呼ばれる学習者は前進指令を受けていた。しかしこれではロボットの進行

実環境や連続空間に対して正確に反応することが難しい。

方向とボールの進行方向が大きく異なっていたとき、す

最近、この問題を解くため多くの研究がなされている。例

ばやくボールにアプローチできていなかった。これまで

えば Q-learning に連続空間を使うためいくつかの研究がの運動制御法はロボットからボールまでの距離と角度かもし観測可能な状態と行動が多すぎると学習は収束し

15

Figure 2: Comparison of Pulltoy and Thruster trajectory. Blue is Pulltoy. Yellow is Thruster. Ball is moving

Figure 1: A new approach ”Pulltoy”

from left below to right.Pulltoy approach is acquiring theball at t=2.5. Thruster is acquiring it at t=3.0.

ら以下のように計算される。

(

Vr
Vl

= Vc + A × L= Vc − A × L(1)

ここで Vr は各ホイールの速度、A は角速度に関するパラ
メータ、L は左右のタイヤの間隔、Vc はロボットの基準速度である。式（１）による方法を便宜上、スラスター法

(

Vr
Vl

= Vmax= Vmax (cos(φf ) − sin(φf ))(0 ≤ φf < π2 )

(

Vr
Vl

= −Vmax (cos(φf ) − sin(φf ))= −Vmax( π2 ≤ φf ≤ π)

と呼ぶ。

(2)

（もし Φf がマイナスの場合、r と l が逆転する）ここで Φ式（１）はスムーズに行動を生成するが、ボールがロ

f はロボット先端からボールまでの角度、Vmax はロボッ

ボットの後方にあるときでさえ、前進に回転指令を加えボールにアプローチしていた。ロボットサッカーにおいてトの最大速度である。式（２）は非常に単純な方法であは、ボールにどれだけ早くアプローチできるかが非常にる。さらに Φf はボールだけでなく他のターゲットに対重要になる。従って我々は人が行うように状況に応じて前しても使える。
我々は次にスラスター法とプルトイ法の軌道を比較し進より回転を優先させる新しい運動制御法を提案する。

た（図 2）。

人はボールが自身の後ろにある場合、まずボールに向き、その後ボールへアプローチする。このようなアプロー

図のようにロボットの背後にボールがある状況では特チがロボットには有効だと考える。しかし人間の行うアに効果的であることがわかった。さらにロボットからボー

プローチを正確に解析し設計するのは難しい。従って新ルへの初期角度、距離を変え比較実験を行った（図 3）。

しいアプローチが必要になる。この論文ではボールにス

縦軸はボールを得るまでの時間差でスラスター法からプムーズにアプローチする人の方法を簡略化した方法を提ルトイ法を引いている。横軸はロボットからボールまで案する（図 1）。新しい方法は式の中にロボットの先端かの下図が初期角度、上図が初期距離である。これらの図か

らボールへの角度を使う。この角度が大きくなると図中のらほとんどの条件においてスラスター法よりプルトイ法

矢印の方向に引っ張られすばやく回転する。我々はこの新が効果的だといえる。もし初期角度が大きく、初期距離がしいアプローチをプルトイ法1 と呼ぶ。

小さい場合、その傾向は顕著になる。

しかしロボットの先端から引っ張られるだけでは最適

3な行動を設計することはできないので、図 1 のようにロ

強化学習

ボットの後方とボールを結んだ角度も使用する。これは引強化学習において学習エージェントは環境から状態を観張る力ではなく押す力になる。図 1 の Φb は式を最適化す

測した後、ポリシーから行動を選択する。その後エージェ

ると省略できる。従ってプルトイ法は式（２）になる。

ントは変化した環境を観測することで報酬を得る。最終
的にエージェントは受け取った報酬に従いポリシーを修

1 プルトイとは子供が小さな木馬や車の先端に結ばれた紐を引っ張っ正する。エージェントはこれを繰り返し学習する。我々はて遊ぶおもちゃである。

16

25

"compare.dat"

20

Time Difference

15

10

5

0

-5

-10

-150

-100

-50

0

Initial Angle(deg.)

50

30

100

150

"compare.dat"

25

Time Difference

20

15

Figure 4: Trajectory of the robot for Ball-To-Goal taskthat generated by RL setting initial value

105では前節で提案した To-Target タスクでのプルトイ法を0Ball-To-Goal タスクでの強化学習法の初期値として使用

-5

-10

した。
0

50

100

150

200

250

Initial Distance(cm)

300

350

400

450

4

状況に応じた戦略の獲得

Figure 3: Graph of varying initial angle and distance.
Upside in each graph represent that the Pulltoy approach

我々はエージェントに単なる Ball-To-Goal タスクだけでcould get the ball before the Thruster approach.

る。ハイレベルなタスクではエージェントとボール、ゴー

なく状況に応じたハイレベルなタスクでの軌道も獲得させ
ルだけでなく複雑な環境の下でのタスクを考えた場合、通常の直接的なアプローチより、守備や攻撃などロボットの強化学習の１つである Watkins el al. によって提案された役割やターゲットの種類、敵ロボットの有無によってター

Q-learning を使う。Q-learning は行動価値関数 Q(s,a) と呼ばれる関数を持ち、ポリシーπにおける状態 s での行動

ゲットへのアプローチの仕方を変える方がより効果的であるといえる。例えば相手に攻められ守備をしなければa を得るときの価値を計算する。この関数は式（３）で定義され更新される。

ならない場合、エージェントは自分のゴールとボールの間に入りながらアプローチする方が得点の危険性を考慮

Q(st , at ) ← Q(st , at )+α[rt+1 +γmaxa Q(st+1 , a)−Q(st , at )] すると効果的である。
(3)5

ここで r は報酬、γ は学習率、st+1 は t + 1 での状態、αは一定のステップサイズパラメータである。

シュミレーション実験

エージェントは探索行動をしなければならない。エージェ

Q-learning は一般的に観測可能な状態とエージェントの取りうる行動を空間的に分割する。本実験においても状態と行動の分割を使用した。状態にはロボットからボール

ントは手本を使わず無知な状態から探索を開始する。そおよびゴールへの角度と距離、ボールの速度を使用した。

のため報酬を学習初期の段階で獲得することは難しく、良ボールへの角度の分割数は１２、距離は４、ゴールへの角い行動を獲得するには時間がかかる。我々はこの問題を度は１２、距離は４、ボール速度は５とした。移動ロボッ

解くため行動を選択するためのポリシーに最適な初期値

トの場合、一般的にエージェントの行動はロボットの周囲を前もって設定する。人の手によって比較的設計が簡単なまたは取りうる行動をほぼ等間隔に分割する。しかしロ

学習開始時において正しい行動価値関数が未知なためタスクでは初期値を設定できる。設定された初期値から

ボットサッカーでの Ball-To-Goal タスクの場合、行動空

探索を開始することによって効率的な学習が期待できる。

間は等間隔に分割すると効率が悪い。よって我々はター

この考え方は人にも言えることで、あるタスクを人に教ゲット周辺の行動空間を密に分割し、他の行動空間を荒える場合、まず手本を見せることが重要である。本論文

く分割した。

17

Figure 6: Generated trajectory for defense task

Figure 5: Generated trajectory for offense task
本論文ではシミュレータを使い Ball-To-Goal タスクにした軌道である。

おいて軌道を生成させる以下の実験を行った。

攻撃や守備等の役割を与えられた場合、プルトイ法や良い初期軌道を与えたときの学習

他の運動制御法では満足な結果が得られない。報酬関数

5.1は複雑になるが人の手では設計が難しいタスクでは強化ロボットの軌道は強化学習でのポリシーの初期値に２節でのプルトイ法を使い生成した。この結果を図 4 に示す。

学習法が有効である。

この時の報酬はボールをゴールへ入れた場合、1 を与えて6いる。
プルトイ法やスラスター法などのように設計が簡単で結言

我々は実験結果から To-Ball タスクや To-Goal タスクの一般的な方法では To-Ball や To-Goal としてターゲット

ような To-Target タスクにおいてスラスター法よりプルを変えなければならない。しかし本論文で提案した方法

トイ法が有効なことを示した。もしロボットが小さいサイを使った強化学習を使用することで初期位置からボール

ズ、または強化学習や他の方法ではメモリが足りないよを獲得し、得点するまでを１つの軌道として生成するこ

うな場合、プルトイ法は簡単なため非常に有効だといえとができる。また状態にボールの速度を含んでいるためる。ロボットは強化学習によって Ball-To-Goal タスクでボールの速度に対応した適切な行動を選択し軌道を生成の軌道を自律的に生成することができた。強化学習を実ロできる。

ボットへの適用を考慮した場合、学習の効率化、高速化がしかし実験のような比較的簡単なタスクの場合、良い求められる。この問題は初期値の設定により解決できた。

初期軌道を与えると学習後に生成される軌道は与えた軌

しかし学習後の軌道は人の手による良い初期軌道とほと

道とほとんど変わらない。つまり今回与えた初期軌道でんど同様の軌道が得られた。このことから単純なタスクあるプルトイ法は学習の手を借りずとも良好な手法であに限れば両手法とも有効であることがわかった。

るといえる。

強化学習法において状態空間が大きくなりすぎると学

5.2

高度なタスクにおける軌道生成

習が収束しなくなる。さらに状況に応じた戦略軌道を設

図 5,6 は単にボールにアプローチするだけでなく役割を与計することは人の手においても難しい。良い初期軌道とえられた戦略下での高度なタスクでの軌道生成の結果をして用いたプルトイ法であっても戦略に応じた軌道を生示す。報酬は役割に応じた方向を向きボールをキャッチし成することはできない。これら問題にも我々の比較的単た場合、1 を与えた。さらにその状態からボールをゴール

純な方法で対応できた。また攻撃や守備のような難しいへ入れた場合、さらに 1 を与えた。

戦略に従ってボールにアプローチする軌道も生成できた。
今後は複雑になった報酬を簡素化する方法の検討および

図 5 で示した攻撃行動は両チームのロボット共ボール

実ロボットへの適用を目指す。

に触れていない場合に使用される。ロボットがボールを獲得したときすでにゴールの方向を向いているポリシーを獲得している。相手ロボットがボールを持ちゴールに

参考文献

向かっている場合、守備の戦略が最適である。この戦略で[1] R.S.Sutton, A.Barto, ”Reinforcement Learning:An

はゴールとボール間の軌道上に自身を移動させ、その後ボールへアプローチする。図 6 は守備戦略の場合、生成Introduction”, MIT Press,1998.

18

[2] J.Peng,

R.J.Williams, ”Incremental Multi-Step
Q-Learning”, Machine Learning, Vol.22,pp283290,1996.

[3] A.Sherstov, P.Stone, ”On Continuous-Action QLearning via Tile Coding Function Approximation”,
In Under Review., June 2004.
[4] S.Hagen, B.Kröse, ”Neural Q-learning”, In Neural Computing & Applications, 12(2), pages 81-88,
November 2003.
[5] A.Barto, S.Mahadevan, ”Recent Advances in Hierarchical Reinforcement Learning”, Discrete Event
Dynamic Systems:Theory and Applications, 13,4177,2003.
[6] Y.Takahashi, M.Asada, ”Multi-Layered Learning
Systems for Vision-Based Behavior Acquision of A
Real Mobile Robot”, Proceedings of SICE Annual
Conference 2003 in Fukui, Vol.CD-ROM, pp.29372942, 2003.

19

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-4 (5/24)

スクリプト言語 Lua を用いたロボカップ四足ロボットリーグシミュレータ
A Simulator of Four-Legged Robot League in RoboCup using an Scripting Language Lua

小林隼人 1 ，井上淳 1 ，石野明 2 ，篠原歩 3
Hayato KOBAYASHI1 , Jun INOUE1 , Akira ISHINO2 , and Ayumi SHINOHARA3
1

九州大学大学院システム情報科学府，2 九州大学大学評価情報室，3 東北大学大学院情報科学研究科
1

Graduate School of Information Science and Electrical Engineering, Kyushu University
2

Oﬃce for Information of University Evaluation, Kyushu University
3

Graduate School of Information Sciences, Tohoku University{h-koba, j-inoue, ishino}@i.kyushu-u.ac.jp and ayumi@ecei.tohoku.ac.jp
Abstract

3. 実行ファイルをメモリスティックにコピーする．
4. メモリスティックを AIBO に挿入する．

In RoboCup four-legged robot league, no modiﬁcations or additions to the robot hardware are

5. AIBO の電源を入れて AIBO を起動させる．
6. AIBO を動かして，プログラムの動作の確認をする．

allowed; hence, there is no diﬀerence between
teams without software. For optimum results,

7. AIBO の電源を切り，メモリスティックを抜く．
8. 手順 1 へと戻る．

to improve the software development process iscritical. In this paper, we introduce a method

手順 2 のコンパイルでは数分から数十分を必要とし，手of using the scripting language Lua in soccer
robots, and we show the soccer simulator, in

順 5 の AIBO の起動には約一分程度を必要とする．さらwhich Lua scripts are executed as in robots.
Using the scripts in both the environments has

強制終了してしまった場合，復帰に数分程度かかること

made it easy to develop soccer robots.

時間は，プログラムの作成はもちろんのこと細かなパラに，手順 7 の AIBO の終了では，プログラムの不具合でがある．プログラムの作成とは直接関係のないこれらのメータの調整をするにあたって大きな弊害となっている．

1

上記の問題を解決するために，本稿では AIBO 上と同

はじめにじスクリプトプログラムの実行を可能とするシミュレー
ロボカップ四足ロボットリーグは，四足のエンターテイン
メントロボット AIBO (ERS-210, ERS-7) [1]による 4 対

タを示す．これによって，上記の手順 2 から 7 すべてをシ

4 のロボットサッカーリーグである．四足ロボットリーグ
では，ロボットは完全な自律型であり，ロボット同士での向上する．

ミュレータ上で行うことが可能となり，開発効率は格段に通信と審判からの指示を除いては，外部の人間による操四足ロボットリーグのシミュレータに関しては，これま
でに ARAIBO [2] や，ASURA [5] や，GermanTeam[9]作はもちろん，計算機による制御も許されていない．さらや，UChile1 [12] チームのシミュレータが報告されている．

に，ロボットの改造も許されておらず，プログラムの優劣がサッカーの勝敗を大きく左右するリーグであるといえる．したがって，開発効率の向上は四足ロボットリーグにおける重要な課題のひとつであると言える．
四足ロボットリーグで用いている AIBO ERS-7 は 64bit

RISC プロセッサーを CPU とし，64MB のメインメモリーと無線 LAN を持ち，OS を含むプログラムはメモリス
ティックにより供給される．したがって，AIBO を動かすプログラムの開発は，通常以下のようなサイクルで行われる．

1. PC 上で C++ プログラムを作成する．

特に GermanTeam は，戦略の記述に XML 形式で振る舞いを記述する XABSL [7]という独自の言語を用いたシュミレータを示している．しかし，XABSL は細やかな動作の記述を行うことができず，シミュレーションの範囲も戦術面の調整にとどまっている．
本稿では，スクリプト言語 Lua を使用したシミュレー
タを示す．汎用のスクリプト言語 Lua を用いることで，戦略の記述のみならず，細かな動作までもが記述可能である．また，この言語は組み込みが容易であるため，Jolly

Pochie フレームワークに組み込むことで，シミュレータ
上だけではなく，AIBO 上でも実行できる．

2. PC 上のクロスコンパイラでコンパイルする．

スクリプト言語の組み込みに関しては，MicroPerl の組

20

Figure 1: Jolly Pochie のフレームワークの概要．

Figure 2: 組み込みの考え方．

み込み [6] が紹介されているが，MicroPerl は十分に大きクラスを用いて各モジュールを記述することを可能としな言語であり，わずかなメモリしか持たない AIBO にはている．個々のモジュールが OPEN-R の関数を直接呼び向いていないと考えられる．

出すことはない．

本稿の構成は以下のとおりである．まず，第 2 節で Jolly

各モジュールは基底となるモジュールクラスを継承すPochie フレームワークおよび Lua の組み込みについて述べる．次に，第 3 節でシミュレータの設計，実装について述べることによって作成され，フレームワークが受け取った

OObject としてのイベントを，それを処理すべき各モジる．最後に，第 4 節で全体のまとめと OPEN-R TECHNO

ュールの呼び出しへと翻訳することによって実行される．

FORUM 2004 の結果を述べ，今後の課題について述べる．

基底となるモジュールには，カメラの画像処理を担当するカメラモジュール，動作時の関節角度を計算するア

Lua の組み込み2

Lua は C 言語への組み込みを前提として開発されたスク
リプト言語である．そのため，組み込みが容易であるのはもちろんのこと，実行エンジンが小さく，簡潔で明瞭な文法規則を持つといった特徴がある．Lua が組み込まれるプログラムはホストと呼ばれ，ホストは Lua の関数を呼び出したり，Lua の変数を読み書きしたり，C/C++ の関数を登録したりすることが出来る．通常それらの処理には，Lua が提供する C の API を用いて仮想スタック
を操作することが必要だが，本稿ではそれを自動化する
Luabind [8] ライブラリを用いてその処理を実現する．

2.1

Jolly Pochie フレームワーク

我々Jolly Pochie チームでは，独自のフレームワークを開発し，様々な機能を個々のモジュールとして作成し，それらを組み合わせてひとつの AIBO プログラムとすることを可能としている [4]．このフレームワークを採用するこクションモジュール，各センサーから送られてくる情報を処理するセンサーモジュール，サッカーにおける適切な戦略を作り出すマインドモジュールなどがある．
この中でも特に，マインドモジュールはすべてのモジュー
ルを制御して AIBO を動作させるモジュールであるため，

AIBO のプログラムの中核を担っている．したがって，Luaの組み込みは主にマインドモジュールに対して行う．
マインドモジュールは，40ms ごとにコアプログラムから呼ばれる mindNotify という特殊な関数を持っている．
この関数の中でサッカーにおける戦略が記述される．例えば，カメラモジュール，センサーモジュールから情報を受け取り，アクションモジュールで AIBO を動かすといった処理を記述する．また，マインドモジュールには状態遷移モデルが導入されているため，mindNotify は状態に対応した関数を呼び出す事になっている．

2.2

実装

とにより，各プログラマーはそれぞれの担当部分に集中しLua を組み込む際の基本的な考え方を図 2 に示す．マインドモジュールが Lua スクリプトを呼び出し，Lua スクて開発を進めることができる．図 1 に Jolly Pochie のフリプトが他のモジュールを呼び出すようにすることで，戦レームワークの概要を示す．

略の変更に関しては再コンパイルの必要をなくすることがフレームワークの基本部分は OPEN-R 1 の OObject であり，OPEN-R 特有の型や関数を隠蔽し標準的な C++の1 SONY が提供する AIBO 用プログラム開発のための API．

出来る．これを実現するには，C++ の関数から Lua の関数を呼び出し，その Lua の関数内で C++ の関数を呼び出せるようにすればよい．

21

Lua の関数の呼び出しは，Luabind ライブラリを用いることで容易に実現することが出来る．例えば，引数，戻1. PC 上で Lua プログラムを作成する．
2. Lua プログラムを FTP で AIBO に送信する．

り値のない Lua の関数 swingStart を呼び出すためには
以下のように書く．JPLua::L は Lua の状態を保持する

3. AIBO に Lua プログラムの再読み込み命令を送る．
4. AIBO を動かしてプログラムの動作確認をする．

構造体のポインタである．

5. プログラムを修正して手順 2 へ戻る．

luabind::call_function<void>(JPLua::L,"swingSt

原理的には Lua スクリプトであらゆることを記述する

art");

ことが可能であるが，我々は Lua スクリプトでは，前進

一方，Lua の関数内で C++ の関数を呼び出すこともする，ボールを見るといった抽象度の高い振る舞いを記

Luabind ライブラリを用いることで容易に実現すること

述することにした．歩行の関節角の計算や，画像処理のよが出来る．例えば，基本動作を実行するモジュール Basic-

うな計算時間がかかるが試行錯誤は行われない処理にはMotionJPM のメンバ関数 swingHead は，モジュールクラスとそのメンバ関数およびモジュールクラスのインス

C++で記述されたモジュールを用い，抽象度の高い振る

タンスを登録するだけである．具体的には以下のようにサッカーの戦略の作成に集中することが出来る．

書く．

同 じ く ス ク リ プ ト 言 語 (MicroPerl) を 組 み 込 ん だ
UPENNALIZERS [3] のソースコードと比較すると，Luamodule(JPLua::L) [class_<BasicMotionJPM>("BasicMotionJPM")

舞いだけを Lua で記述することによって，プログラマはの組み込みの方が遥かに簡単であることが分かる．また，スクリプトを比較しても，Perl は感覚的なコーディング.def("swingHead",&BasicMotionJPM::swingHead)];が出来る半面，初心者には分かりづらいソースとなるが，get_globals(JPLua::L)["basicMotion"] = this;Lua は Pascal に似た文法を持つため初心者にやさしい可
読性のあるコードとなっている．

最 後 の 行 の イ ン ス タ ン ス の 登 録 は ，Lua の 変 数"basicMotion" に BasicMotionJPM の this ポインタを代入している．登録が済むと，Lua では以下のような記述で関数を呼び出すことが出来る．

basicMotion:swingHead(0, 0, 0)
先に述べたように Jolly Pochie では，AIBO プログラム

シミュレータ3

前節では，サッカーの戦略を Lua スクリプトだけで作成できることを示した．しかし，作成した Lua スクリプトのテストには依然として実機によるテストが必要であり，
このことが多大な試行錯誤を必要とする開発の妨げとなっは多数のモジュールを組み合わせることによって構成されている．そこで，本節では，その Lua スクリプトを一切書る．その際，これらの Lua への C++関数の登録はモジュー

き換えることなく実行できるシミュレータを示す．シミュ

ルごとに行われるため，モジュールの構成の違いによってレータを用いることによって実機を使わずに開発を行う

C++プログラムや Lua スクリプトを変更する必要はない．
例えば BasicMotionJPM モジュールと互換性を持った新ことができ，これにより開発効率は飛躍的に改善する．

たなモジュール AdvancedBasicMotionJPM を作成したと疑似受動的モジュールの 3 つに分けて考える．図 3 に，現しても，Lua への登録を AdvancedBasicMotionJPM の中実の環境とシミュレータ環境の対応関係を示した．

で記述するだけで他は全く変更することはない．

2.3

考察

まず，シミュレータを疑似環境，疑似能動的モジュール，

3.1

疑似環境

疑似環境は，フィールドや AIBO やボールといった実世

上述の通りマインドモジュールから Lua を通して，自由界の環境をシミュレーションする部分である．疑似環境で自在に他のモジュールを呼び出せるようになった．すなわ

は，それぞれの物体を三次元モデルで表現することによっち，今まで数分から数十分を要していたコンパイル時間て，例えば鼻先に搭載された AIBO のカメラからボールが不要となり，開発効率が大幅に向上した．さらに，今まで使ってきた C++ の戦略プログラムも，単純に Lua のが見えているかどうかを視覚的にも確認できるようにしている．これを VPython [11]という Python の三次元グ構文規則にしたがって変換（中括弧をなくして end を付

ラフィックスモジュールを用い実現した．
疑似能動的モジュールは，Lua スクリプトを呼び出す

ける等）することで使用することが出来る．
また，スクリプトは AIBO の再起動なしに再読み込みをすることが出来るため，FTP 経由でスクリプトを送信

Jolly Pochie のフレームワークに属するモジュールをシ
ミュレーションする部分である．具体的にはマインドモ

するなどすれば，AIBO の再起動に伴う数十秒から数分

ジュール，UDP 通信モジュール，アクションモジュールの無駄な時間もなくすことが出来る．したがって，一連のなどをシミュレーションするプログラムからなる．区別す

開発手順も以下のように簡単なものとなった．

るため，これらのモジュールを能動的モジュールと呼び，

22

Figure 4: フィールドのモデル．

Figure 3: 現実の環境とシミュレータ環境の対応関係．

他のモジュールを受動的モジュールと呼ぶことにする．能動的モジュールが受動的モジュールと違うのは、一定時間ごとに，あるいはイベントごとに呼ばれる関数を持ってFigure 5: ボールのモデル． Figure 6: AIBO のモデル．

いる点である．
マインドモジュールは 40ms ごとに Lua スクリプトを呼び，アクションモジュールは 8ms ごとに関節の角度を

尾はシミュレーションする必要はなく，歩行に関しても天指定する．また，UDP 通信モジュールはメッセージを受

井カメラから計測した一歩の歩幅が設定ファイルとして信した時に，Lua スクリプトのある関数を呼ぶことになっ保存してあるので，足の動き自体をシミュレーションするている．疑似能動的モジュールは、C++で実装される．

必要はない．頭部に関しては，視覚的に AIBO からボー

疑似受動的モジュールは，Lua スクリプトから呼び出

ルが見えているかを判断するために，AIBO の仕様書をされるような，受動的モジュールをシミュレーションする

元に首関節の長さや接合部の位置まで正確に実装した．

部分である．例えば，歩行やシュートといった AIBO に

これらのモデルの表示ルーチンは，マインドモジュール

動作をさせるものや，画像認識の結果からボールの位置に同期させることにする．つまり，表示ルーチンは 40msを計算するものがこれにあたる．本来なら受動的モジューごとに呼ばれ，同時にマインドモジュールも呼ばれるこルの関数は Luabind で登録されて Lua スクリプトから呼とになる．

び出されるが，シミュレータでは画像処理や自己位置同定などの計算をする必要がないため，単に Lua 側でダミー

3.3

疑似能動的モジュールの実装

関数を定義することにする．ただし，シミュレータにも使

本稿で実装した能動的モジュールは，マインドモジュール，える OPEN-R に依存しないライブラリは，再利用のためアクションモジュール，UDP 通信モジュールの 3 つである．

に登録することもできる．例えば，３つの首関節の角度とこれらのモジュールは C++ で実装され疑似環境から呼ばカメラの XYZ 座標の相互変換を行う HeadKinema ライ

れる．Python から C++ を呼び出すためには，ラッパ関数

ブラリなどがこれにあたる．

を自動生成する SWIG(Simpliﬁed Wrapper and Interface
Generator) [10] というツールを使った．

3.2

疑似環境の実装

疑似マインドモジュールは，Lua の組み込みでの実装

VPython を用いて，三次元空間上にサッカーフィールド，と同様に Lua スクリプトの関数を呼び出すようにすればボール，AIBO を表示して疑似環境を作る．サッカーフィー

よい．40ms ごとに mindNotify 関数を呼び出す処理は，

ルドとボールに関しては，VPython の基本的なオブジェ

疑似環境が提供する．

クト（球，円柱，箱など）を組み合わせて簡単に表現出来る（図 4, 5）．

疑似アクションモジュールは，8ms ごとに呼び出すことはせず，処理を単純にするために疑似マインドモジュー

一方，AIBO は複雑で円みを帯びた形状をしているたルに同期させて 40ms ごとに呼び出すことにする．首のめ，基本的なオブジェクトを組み合わせても正確に表現す

動作に関しては，1 フレーム（8ms 区間）で動かせる制ることは難しい．よって，AIBO のモデルは簡略化して胴限角度が決まっているので，疑似アクションモジュールで部と頭部だけの簡単なものとした（図 6）．実際，耳や尻は一度呼ばれるごとに 5 フレーム分の角度を送り込むこ23

soundPlayer = {}function soundPlayer:playSoundOnce()endfunction soundPlayer:playSoundStop()
end
Figure 8: ダミー関数の一部．

Figure 7: 前方歩行の歩幅と歩行距離のグラフ．

とにする．また，歩行動作に関しては 12 個の関節角度を計算する必要はなく，一歩の歩行距離が保存されたファイ
ルさえあれば直接 AIBO を動かすことができる．
歩行距離は天井カメラから得た情報を元に計測する．天井カメラによる距離の計測方法については，青山ら [13]を参照されたい．歩幅に対する歩行距離は，床との摩擦や，モータの性質から線形的に変化することはない．したがって，まず歩幅を 10 段階に変化させて歩行距離の計測

Figure 9: シミュレーターの実行の様子．

値を出し，この計測値から線形補完したグラフを元に歩行距離の近似値を出す．図 7 に，前方歩行の歩行距離を実際に線形補完したグラフを示す．
また，疑似アクションモジュールは 5 フレームごとにLua でダミー関数を定義する（図 8）．一方，シミュレー
タ用に新たに実装しなければならないモジュールとして，

AIBO を移動させるため，1 歩にかかるフレーム数が必要となる．これは，既存の歩行パラメータから抽出する

ボールの位置を計算するモジュールや，自己位置を計算ことにする．シミュレータ上で一度に移動する距離は，1

ミュレータが常にすべての物体（AIBO，ボール，ゴール

歩の歩行距離を 1 歩のフレーム数で割り，それを 5 倍しなど）のグローバル座標を保持しているため，複雑な画像たものとなる．最後の端数フレー厶に関しては，1 フレー

処理をしなくても取得することが出来る．ただし，AIBO

ムの歩行距離を端数倍したものを送る．

の鼻先のカメラからボールまでの相対距離や角度を出すた

するモジュールなどが挙げられる．これらに関しては，シ

疑似 UDP 通信モジュールは単なる UDP サーバーでめには，複雑な幾何計算が必要となるため，その計算をすあるが，同一ポートでは 2 つの UDP サーバーを立ち上るために作られた C++ の自作ライブラリ HeadKinema

げることができない．したがって UDP サーバーの実体を Lua に登録することにした．

は 1 つとして，受け取った情報を複数の疑似 AIBO プロ
グラムに渡す仕組みを作った．したがって，実際の試合と

3.5

考察

同じようにゲームコントーラの情報を受け取り試合を始

図 9 にシミュレータの実行の様子を示す．シミュレータ

めることも可能である．

内の AIBO の動作は理想的な環境下でのものなので，実世界が理想的な環境に近ければ実世界の AIBO とほぼ同

3.4

疑似受動的モジュールの実装

じ動作をする．

疑似受動的モジュールは，そのほとんどはダミー関数を作実機で動くスクリプトをシミュレータ上で動かせるよるだけで事足りる．なぜなら，各種センサー用のモジュー

うにしたことで，実機を使用せずにスクリプトの開発，動ルや音声出力モジュールなどのモジュールはシミュレータ

作確認が行えるようになった．したがって，シミュレータ

では実装しないからである．よって，これらのモジュール上での作業手順は以下のような更に簡単なものとなる．たの関数については C++ で新たに実装し登録するようなだし，ある程度シミュレータ上で動作確認が出来たら，最ことはせず，単にスクリプトがエラーを出さないように後に実機で動作確認や微調整をする必要がある．

24

1. PC 上で Lua スクリプトを作成する．
2. PC 上のシミュレータで動作の確認をする．

[3] D. Cohen, Y. H. Ooi, P. Vernaza, and D. D.
Lee. The University of Pennsylvania Robocup 2003
Legged Soccer Team. Technical report, UPENNAL-

3. プログラムを修正して手順 2 へ戻る．

IZERS, 2003.
シミュレータの最大の利点は実機を使わずにプログラ
ムの開発が出来ることである．これにより，実世界における複雑さに惑わされることなく開発作業に集中する事が[4] J. Inoue, H. Aoyama, A. Ishino, and A. Shinohara.
Jolly Pochie 2004 in the Four Legged Robot League.
Technical report, Jolly Pochie, 2004.

出来る．特に複数の AIBO を使って動作確認を行いたい
場合には有効である．また，今まではすべてのモジュール[5] T. Ishimura, T. Kato, K. Oda, and T. Ohashi. Anが揃わなければ，サッカーの戦略部分のプログラムを開発することが出来なかったが，シミュレータではダミー関Open Robot Simulator Environment. In RoboCup
2003, Vol. 3020 of LNAI, pp. 621–627. Springer,数を作って簡単に動作確認まですることが出来る．これ2004.

は AIBO の制御プログラムのように，大規模なプログラ
ムを複数人で開発する際には大きな効果をもたらす．
シミュレータの欠点は，実世界を完全にシミュレート
できないことである．例えば，障害物と衝突した場合や，[6] T. Jenness and S. Cozens. Extending and Embedding Perl. Linux Journal, 2003:15, July 2003.
[7] F. Lötzsch,

ボールが完全に見えていない場合の処理をシミュレート
レータに採り入れることも考えられるが，最終的には実andguage XABSL. In 7th International Workshop on
RoboCup 2003, LNAI. Springer, 2004.

機での動作確認をすることが必要となるだろう．

おわりに

H.-D. Burkhard,

M. Jüngel.
Designing Agent Behavior with
the Extensible Agent Behavior Speciﬁcation Lan-

するのは非常に難しい．実世界での誤差を計測してシミュ

4

J. Bach,[8] Luabind. http://luabind.sourceforge.net/.

本稿では，まずスクリプト言語 Lua をプログラムに組み[9] T. Röfer. German team robocup 2004 technical re-

込むことで，プログラム作成とは直接関係のないコンパ

port. Technical report, German Team, 2004.

イル時間を不要にした．さらに，AIBO 上と全く同じスク
リプトプログラムの実行を可能とするシミュレータを示した．このことで，実機を使わずに動作確認が出来るようになり，プログラムの開発効率が大幅に向上した．
また，我々は本稿の技術を生かして，SONY が主催する

OPEN-R TECHNO FORUM 2004 in Japan (2004/12/4)の競技種目に出場した．結果，シュート技術を競う PK 競

[10] Simpliﬁed Wrapper and Interface Generator. http://www.swig.org/.
[11] VPython. http://vpython.org/.
[12] J. C. Zagal and J. R. del Solar. UCHILSIM: A Dynamically and Visually Realistic Simulator for the
RoboCup Four Legged League. In 8th International

技，歩行技術を競うレース競技において優勝することがWorkshop on RoboCup 2004, LNAI. Springer, 2004.

出来た．
今後の課題としては，シュートにより移動するボールの方向や距離，視覚によるボールの位置情報などに誤差[13] 青山, 井上, 坂井, 石野, 篠原. 遺伝的アルゴリズムによる四足歩行ロボットの高速歩行の実現. 火の国情報シンポジウム論文集, March 2005.

を加えることが挙げられる．そうすることで，シミュレー
タの環境が実世界に近付き，より実世界に適応するロバストな戦略の作成が出来るようになる．

参考文献[1] AIBO SDE Homepage. http://openr.aibo.com/
openr/jpn/index.php4.
[2] K. Asanuma, K. Umeda, R. Ueda, and T. Arai. Development of a Simulator of Environment and Measurement for Autonomous Mobile Robots Considering Camera Characteristics. In Robot Soccer World
Cup VII, pp. 446–457, 2004.

25

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-5 (5/24)

統合シミュレーションのためのデータのバージョン管理の形式的考察
Consistency Management Framework for Database used in Integrated Simulations

野田五十樹
NODA, Itsuki(独) 産業技術総合研究所
National Institute of Advanced Industrial Science and Technology

i.noda@aist.go.jp

Abstract

2

In this article, I show a mathematical formalization of version control that manage consistency
among data that are used in integrated simulation system. When we apply integrated simulations
to real-time evaluation of complex social phenomena like disaster and rescue, keeping consistencyof data is an important issue for validate result,because multiple and delayed information are reported to the database continuously in such applications. The proposed formalization gives fundamental background of consistency and validityof database and simulation. I also investigate anddiscuss about cost of the management in several
implementation style.

要件

以下では、災害救助シミュレーションを例題として、統合シミュレーションの際のデータ管理に求められる要件を、いくつかのケースの形であげておく。

2.1

ケース 1:センシングにおけるノイズ

現場におけるシミュレーションの利用を考える場合、センサーから得られるデータがかならずしも真ではないことを前提としなければならない。特に同じ事象を観測する
複数のセンサーがあった場合、それらが異なるデータを報告することは普通に起こり得る。例えば、先の中越地
震では、気象庁の web サイトにおいて、同一地点の同一
時刻の震度として 5 と 7 が繰り返し報告されていた。こ

1

はじめに

のような場合、震度 5 でシミュレーションすべきか、震度 7 を採用すべきか、あるいは間をとって 6 をとるのか、災害など複雑な現象を計算機で扱う手法として、統合シ
ミュレーションの構築が進められている[2, 1]。これら統

さらには 6 ± 1 といった幅や分布を伴ったデータをシミュ
レーションの入力として採用するのか、管理する方法が合シミュレーションの特徴は、関連ある事象の変化を各々必要となる。

予測するシミュレータと結合し、相互に計算結果を反映しながら全体としての現象をシミュレーションする点で

2.2

ある。

ケース 2:報告の遅延

このようなシミュレーションを具体的な問題に提供す

広域に広がる対象を扱う場合、実際の対象の状態を計測る場合、誤差を含む膨大な量のデータを扱い、それらのするセンサーはデータベースから遠いところに存在する。

間の依存関係を適切に管理する必要がある。また、シミュ

よって、そのデータは必ずしもリアルタイムで入ってく

レーションを現場で利用、すなわち災害救助の例では災るとは限らず、場合によってはシミュレーション開始後に害が実際に発生した直後に被害想定や救助計画立案のた入ってくる場合もある。例えば中越地震においても、通信

めにシミュレーションを用いる場合、災害現場のセンサー

や電力のトラブルのために山古志村のデータが 2 日間もデータの報告に遅延が生じることを考慮する必要がある。

遅延して報告された事は記憶に新しい。

このような条件をふまえた上で、シミュレーションに対し一方、現場で利用されるシミュレーションではそのようて整合性のある初期データを提供する枠組みが必要となな遅延のある報告をいちいち待っていられない事が多い。

る。本報告では、このようなデータの整合性を形式的に定

よって、それら報告の遅延も厳密に管理し、シミュレー

義し、統合シミュレーションへの入出力を担うデータベー

ションに利用されたデータとの整合性をチェックできる機スに求められる機能を整理することを目的とする。

構が必要になる。

26

2.3

ケース 3:シミュレーションの依存関係

データ: データ dθ,t,s は、センサーあるいはシミュレー

複数のシミュレーション結果が別のシミュレーションへの

ション s によって観測・推定された事象 hθ, ti の値であ入力となる場合、元となるデータの整合性が重要となってる。観測や推定にはノイズや前提条件の違いがあるので、くる。例えば、建物倒壊シミュレーションを震度 7、道路

同じ事象に対し異なるデータがあり得る。s はセンサーの閉塞シミュレーションを震度 5 を前提として行い、それら同定子あるいはシミュレーションのセッションに対応するを合わせて避難シミュレーションを行うことは、整合性がバージョン (次節参照) に対応する。

あるとは言いにくい。1 よって、シミュレーション結果をまた、データがデータベースに報告された時刻を明記

あわせる場合には、それらのシミュレーションの依存関係

する場合は、dθ,t,s;τ ような記述を用いる。ただし、τ はをたどって整合性をチェックできる枠組みが必要となる。
実際、災害救助シミュレーション[2, 1] では、10 以上のデータベースにこのデータが報告された時刻である。

サブシミュレータが相互に依存して計算を行う。また、こに渡って報告されるものを含む) 全データの集合である。

れらが扱うデータは膨大であるため、整合性チェックは軽データベース: データベース DB = {dθ,t,s;τ } は (将来

また、DB(0,T ) = {dθ,t,s;τ ∈ DB|τ < T } は、ある時刻

量でスケーラブルな枠組みである必要がある。

T におけるデータベースのスナップショット、すなわち、

2.4

ある時刻 T までに報告されたデータの集合を表す。

要件のまとめ

上記の要件をまとめると、統合シミュレーションのための

3.2

データベースに求められる機能は次のようになる。

シミュレーション とは、データベース DB と以下のよう• ある事象の観測あるいは推定として、複数あり得る値のどれをシミュレーションの初期値として用いたかを管理する手法。
• 複数のシミュレーション結果を統合する際に、そのデータの整合性をチェックできる機能。
• 遅延して報告された値に対し、報告以前に行われたシミュレーションとの整合性をチェックする機能。

3に入出力を行うものとして定義する。

1. ある事象の集合 E ground = {ei |i} に関するデータの集合 D ground を、ある時刻 Tbegin (一般にシミュレー
ション開始時刻) にデータベース DB から取得する。
2. 別の事象の集合 E target = {ei |i} についてのデータ
D target を推定する。
3. 推定されたデータ D target を時刻 Tend (一般にシミュ
レーションの完了時刻) にデータベース DB に書き込む。

形式的定義と定理以上の要件や機能を形式的に議論するため、いくつかの概念と定理を整理する。

3.1

バージョン

このシミュレーションの入出力に用いられるデータの集
合 (D ground , D target ) につけられた名前を バージョンとDatabase と Snapshot

呼ぶ。よって、シミュレーションはあるバージョンのデー

ここではデータベースを、データ の集まりとみなす。まタ集合をデータベースから受け取り、別のバージョンのた データ とはある時刻のある 事物 について観測あるい

データ集合を作成してデータベースへ登録する処理とみは推定された個々の値とする。データベースは動的であなされる。

るとする。すなわち、データベースへはシミュレーション

前節で述べているように、統合シミュレーションではいなどとは非同期にデータが書き加えられるものとする。

くつかのシミュレーション結果を合わせて別のシミュレー

以下に形式的定義を述べる。

ションの入力として用いることが生じる。この際に、それ: 事物 θ は、個々の物体やその属性、現象などの同定子である。例えば、“建物 X”、“車 Y の速度”、“地らのシミュレーション結果が合わせて用いてもよいものか

点 Z の震度” などは事物である。事物同士には包含関係ために、バージョン間の整合性というものを定義する。

事物

どうかを区別する必要がある。ここではこの区別を行う

や上位下位関係があっても良い。

バージョン: バージョン v は hE, T , D, Gi という対で: 事象 e は、事物 θ と時刻 t の対である。よって、定義される。ここで、 E = {ei |i} は事象の集合、D は

事象 e は hθ, ti とも記述される。例えば、“時刻 t におけそのバージョンに属するデータ集合、T はデータベース

る人 X の負傷度” “時刻 t における車 Y の速度” “時刻 tDB を操作 (入出力) した時刻、G = {ui |i} は D が直接における道 Z の閉塞度” は事物 である。

依存するバージョンの集合を表す。これらの対の要素は以事象

下の条件を満たさなければならない。

1 このようなシミュレーションを行った場合、(震度 7 で) 建物倒壊で多くの被災者が出ているところに、(震度 5 で) あまり閉塞していない
道路を使って救助隊が迅速に対応してしまうシミュレーションが怒ってしまうことが考えられる。

D ⊂ DB(0,T ) /E = {dθ,t,s;τ | hθ, ti ∈ E, τ < T }27

バージョンの生成: 新しいバージョンが生成されるに

ただし、u = hE u , Tu , D u , Gu i、v = hE v , Tv , D v , Gv i では、発生、抽出、算出、合同の 4 種類の方法がある。

ある。

DB からセンサーにより直接観測されたデータのみを集めて新しいバージョン v をつくる場合、そのバージョ
ンを 発生 するという。発生させられたバージョンは v =hE, T , D, φi のような対で表される。ここで、E は関連する事象、D はセンサーから直接得られたデータからなる集合、T は D を DB から集めた時刻である。
既存のバージョン u = hE u , Tu , D u , Gu i からいくつかのデータを取捨選択してバージョン v を作成する場
合、そのバージョンを抽出するという。抽出された v は
hE v , Tv , D v , {u}i という対で表される。ただし、Tv は抽

2 つのバージョン u, v が 無矛盾 (u ∼ v) であるとは、以下の条件を満たすときである。
∀u0 Â∗ u, ∀v 0 Â∗ v : u0 ∼v
˙ 0
2 つのバージョンの合同 u ⊕ v をつくる場合、u と v は無矛盾である必要がある。
また、v ∼ v が成り立つ場合、バージョン v が 自己無
矛盾 であるという。

3.3

出の時刻であり、また、D v ⊆ D u および E v = {e|dθ,t,s ∈D v , e = hθ, ti} が満たされるものとする。

世界線

データの定義で述べたように、ある事象に対して複数のデータがデータベースに登録されていることがあり得る。

あるバージョン u を入力としてシミュレーションした

一方、事象の解析やシミュレーションでは、それらのデー

結果をバージョン v として得る場合、そのバージョンをタを全て真として扱うとは限らず、目的に応じて取捨選択算出 するといい、u ¤ v と記述する。算出されたバージョされた一部のデータを真して解析などの入力とする。こンは以下の対で表される。

こでは、一連のシミュレーションにおいて真として扱われたデータの集合を世界線と呼ぶ。

u ¤ v ⇔ v = hE v , Tv , D v , {u}i

もちろんシミュレーションでは少しずつ異なる初期値
ここで E v 、D v 、T は各々シミュレーションの対象事象、を入力として解析を行うことがある得るので、世界線も複結果、完了時刻である2 。

数、並行して存在し得る。このような場合、異なる初期値

2 つのバージョン u、v の 合同 (u ⊕ v) とは、2 つのバー
ジョンに含まれるデータを合わせたものを表すバージョンである。合同バージョンは仮想的なバージョンであり、事象集合やデータ集合は空集合として扱われる。すなわち、
u と v の合同バージョンは以下の対で表される。

を用いていることから、それらの世界線は相互に矛盾していることになる。一方、一つの世界線の中では、それに含まれる全てのデータは相互に無矛盾である必要がある。
ここで無矛盾とは「各々のデータが相互に矛盾しない条件
あるいはデータに基づいて求められたものである」という状態をさす。以下ではこれらの概念を形式的に定義する。

u ⊕ v = hφ, T , φ, {u, v}i: 世界線 w はデータベース DB の任意の部分集合である。すなわち w ⊆ DB である。世界線 w が同じ事象 e に対し複数のデータを含んでいる場合はモンテ
カルロ的に解釈され、その複数のデータは e の値の分布
世界線

ただし、T は合同の操作を行った時刻である。
バージョン v がバージョン u を直接根拠とする (u Â vと記述) とは、v が u から合同あるいは算出されている場合をさす。上で定義されているように、v とその直接根拠

u には u Â v ⇔ u ∈ Gv という関係が成り立つ。ただし、
v = hE v , Tv , D v , Gv i である。
∗
バージョン u がバージョン v の根拠である (u Âv) とに準じていると見なす。一方、世界線がある事象について
データを含んでいないときは、その事象については考慮しない (‘don’t-care’) ものとして扱う。
データベースから世界線を選びだす時に制約は存在しは、u と v の間に再帰的に直接根拠の関係のパスがあるない。よって、世界線の全集合はデータベースの巾集合
2DB である。

ことをさす。すなわち、u Â∗ v ⇔ (u = v もしくは u Â u0 , u0 Â∗ v)

世界線はデータベースの時間変化とは独立である。すなわち、データベースに新たなデータが登録されても、世である。また、バージョン v の根拠の集合を v の軌跡

界線は変化しないものとする。

(Tr(v) = {u|u Â∗ v}) と呼ぶ。
整合性

: 世界線 w のうち、ある時刻 t に関する
事象のデータのみを集めたものを時刻 t における世界線

世界線の射影: 2 つのバージョン u, v が 1 次的に無矛盾 (u∼v)˙

であるとは、以下の条件を満たすときである。

w の射影、あるいはタイムスライスと呼び、w/t と表す。
すなわち、w/t = {dθ,t0 ,s;τ ∈ w|t0 = t} である。

∀e ∈ E u ∩ E v : D u /e = D v /e

また世界線 w のうち、ある事物 θ に関するデータのみ

2 ここでは、シミュレーションの結果はすぐさまデータベースに記録を集めたものを事物 θ における世界線 w の射影 と呼び、されると仮定している。

28

w/θ で表す。すなわち、w/θ = {dθ0 ,t,s;τ ∈ w|θ0 = θ} である。
同様に世界線 w のうち、ある事象 e に関するデータのみを集めたものを事象 e における世界線 w の射影 と呼び、w/e で表す。すなわち、w/e = {de0 ,s;τ ∈ w|e0 = e}である。

である。しかしこれはバージョン v の自己無矛盾性の定義に反する。
よって、根拠 u は w に支持される。
この補題より、次の定理が導き出される。
定理 1. バージョン v が自己無矛盾である場合、それを支持する無矛盾な世界線 w が存在する。

: 以下の条件を満たした場合、またそのときに限り世界線 w がバージョン v を支持すると呼び、w ` v と記述する。
世界線の無矛盾性∀v : v is self-consistent → ∃w : w is consistent, w ` v
証明 (定理 1). 次のような世界線 w を考える。

∀u = hE u , Tu , D u i Â∗ v, ∀e ∈ E u : w/e = D u /ew = {d|u = hE u , Tu , D u , Gu i Â∗ v, d ∈ D u }また、以下の条件を満たした場合、またそのときに限り、世界線 w が 無矛盾であると呼ぶ。

補題 1 より世界線 w はバージョン v の任意の根拠を∀dθ,t,s;τ ∈ w : s is a sensor id or w ` s

支持する。一方、任意のシミュレーションされたデータ

言い換えれば、世界線を構成するデータのうちシミュレー

dθ,t,s;τ ∈ w に対して、3 そのデータが属するバージョンs は v の軌跡に含まれる。よって、s は世界線 w に支持される。

ションにより求められたものは、それが属するバージョンの根拠が全て世界線に含まれている場合に限り、世界線は

よって、無矛盾であり、かつ、v を支持する世界線 w

無矛盾となる。

は存在する。

一般にシミュレーションは世界線を伸ばしていく作業と言える。ここで重要なのは、世界線が無矛盾性を維持す

この定理により、シミュレーションが意味あるものとす

るようにシミュレーションを行わなくてはならないことでる、すなわち、シミュレーションの結果が無矛盾な世界線ある。もし世界線が無矛盾に保てないとすると、そのシの一部となるためには、そのシミュレーションが出力する

ミュレーションは異なる相互に相容れない根拠に基づいてデータのバージョンの自己無矛盾性にのみ配慮すれば良計算を行っていることになり、全体としては意味のない計いことになる。
この定理を元に、以下ではバージョンの生成に関する算を行うことになる。

3.4

定理を導き出す。

無矛盾性に関する定理

定理 2. 発生させられたバージョンは自己無矛盾であり、

ここでは、世界線およびバージョンの無矛盾性の維持にそれを支持する無矛盾な世界線が存在する。

関していくつかの定理を与える。
補題 1. バージョン v が自己無矛盾であり、かつ、世界証明 (定理 2). 定義により、発生させられたバージョンに線 w が v の軌跡に属する全てのデータから構成されて含まれるデータは全てセンサーから直接きたものであり、いる場合、v の任意の根拠 u は世界線 w に支持される。

他のバージョンとの依存関係はない。よって、自己無矛盾

すなわち、以下の式が成り立つ。

である。

∀v

:

よって、定理 1 より、発生バージョンを支持する無矛

v is self-consistent,

盾な世界線が存在する。

w = {d|u = hE u , Tu , D u , Gu i Â∗ v, d ∈ D u }定理 3. 自己無矛盾なバージョン u からバージョン v を→ ∀u Â∗ v : w ` u

抽出する場合、以下の条件を満たす場合に限り、v は自証明 (補題 1). バージョン v の根拠の 1 つ u が世界線 w

己無矛盾であり、それを支持する無矛盾な世界線が存在に支持されていないとする。すなわち、する。

∃u = {E u , Tu , D u , Gu } Â∗ v, ∃e ∈ E : w/e 6= D u /e.

∀v :u ⊃ v,とする。定義より、w は D u の上位集合である。よって、∃d ∈ w/e, d ∈/ D u /e が満たされる限り w/e 6= D u /e が成り立つ。これは、

v is self-consistent ↔ ∀e ∈ E v : D u /e = D v /e
た だ し 、u、v

は 各々hE u , Tu , D u , Gu i

および

hE v , Tv , D v , Gv i である。

∃u0 {E u0 , Tu0 , D u0 , Gu0 } ∈ Tr(v) : u0 6= u,

3 センサーから得られたデータは根拠を持たないので、無矛盾性には抵触しないため、考慮しない。

d ∈ D u029

4

証明 (定理 3). もし上記の条件が満たされている場合、uand v は無矛盾である。また、u は自己無矛盾であることから、v もまた自己無矛盾である。
逆に、条件 ∀e ∈ E v : D u /e = D v /e が満たされない場
合、v に含まれるある事象 e が存在して、かつ、D u /e 6=
D v /e を満たすものが存在する。よって、u と v は矛盾することになり、v は自己無矛盾でなくなる
よって、v の自己無矛盾性と上記の条件は等価であり、定理 1 より、抽出バージョンを支持する無矛盾な世界線が存在する。
定理 4. バージョン u が自己無矛盾である場合、それから算出されたバージョン v は自己無矛盾であり、v を支持する無矛盾な世界線が存在する。すなわち、∀u : self-consistent →∀v : u ¤ v→

v is self-consistent,∃w : w is consistent, w ` v

バージョン管理のコスト

前節で議論した無矛盾性を保ちつつ統合シミュレーションを行うためには、データベースに以下のような機能を追加する必要がある。

• バージョンに関する情報 hE, T , D, Gi を記録する機能。特に、D は多数に上ることを前提に扱われることが必要。
• 既存のバージョンの無矛盾性を保ちつつ、新しいデー
タを登録する機能。特に、シミュレーション開始後にそのシミュレーションに関係するデータが挿入された場合、関係するバージョンの無矛盾性を管理する
方法が必要。
• 2 つのバージョンの無矛盾性をチェックする機能。前節の定理にあるように、バージョンの合同を行う場
合、その無矛盾性を高速にチェックする機能が必要。
以下ではこれらの機能を実装する方法として、D の記

ただし、ここではシミュレーションは入力されたものと録方法に着目し、正記法 と 負記法 の 2 つの方法とその同じ事象に関するデータを出力しないものとする。

計算コストについて考察する。

証明 (定理 4). 定義により、Tr(v) is {v} + Tr(u) が成り4.1

立つ。また、E u ∩ E v = φ であることから、u の任意の正記法あるバージョンに関する D の最も単純な記録方法は、そ根拠は v と無矛盾である。よって、バージョン v は自己れに含まれるデータを列挙する方法である。これを 正記

無矛盾である。

法 と呼ぶ。

よって、定理 1 から、抽出バージョンを支持する無矛
盾な世界線が存在する。

4.1.1

必要記憶容量定理 5. 2 つのバージョン v 、u が自己無矛盾でありかつ当たり前ではあるが、正記法ではデータの数に比例し相互に無矛盾であるとする。この場合、この 2 つのバー

た記憶容量 (O(|D|)) が必要となる。これは、災害救助のジョンの合同バージョンは自己無矛盾であり、それを支持ような大規模なシミュレーションではかなりのコストにする無矛盾な世界線が存在する。すなわち、なる。

∀u, v : self-consistent, u ∼ v →4.1.2

データの登録コストu ⊕ v is self-consistent,

新しいデータを DB にいれる場合、その新しいデータ∃w : w is consistent, w ` u ⊕ v

はこれまで生成されたバージョンには全く含まれないため、正記法では特に余計なコストは生じない。

証明 (定理 5). 定義より、

4.1.3

Tr(u ⊕ v) = {u ⊕ v} + Tr(u) + Tr(v)

無矛盾性チェックのコスト

前節の定理で述べているように、シミュレーションにである。x と y を Tr(u ⊕ v) に含まれる 2 つのバージョ

おいて成長する世界線を無矛盾に保つためには、バージョンとする。もし x と y が共に Tr(u) に含まれている場
合、u が自己無矛盾であるため、x と y は無矛盾である。

x と y が共に Tr(v) に含まれている場合も同様である。
x ∈ Tr(u) 、y ∈ Tr(v) かつ、x ∈/ Tr(v) 、y ∈/ Tr(u)ンの合同を行う際の無矛盾性の確保が一番問題となる。

2 つのバージョン u と v の無矛盾性をチェックするためには以下の操作が必要である。

である場合、u と v は相互に無矛盾であるので、x と y∀u0 ∈ Tr(u), ∀v 0 ∈ Tr(v), ∀e ∈ (E u0 ∩ E v0 ) :は相互に無矛盾である。

x と y のいずれかが u ⊕ v と一致する場合、u ⊕ v が事象を含まないことから、x と y は 1 次的似無矛盾である。
よって、合同バージョン u ⊕ v は自己無矛盾であり、定理 1 よりそれを支持する無矛盾な世界線が存在する。

30

check D u0 /e = D v0 /e
た だ し 、 u0

= hE u0 , Tu0 , D u0 , Gu0 i お よ び v 0 =P
hE v0 , Tv0 , D v0 , Gv0 i である。この操作は O( |D u0 | +P|D v0 |) の計算量を必要とする。

4.2

5

負記法

D のもう一つの記録方法として、そのバージョンが関係している事象 E のなかで使われなかったデータを記録する方法が考えられる。これを 負記法 と呼ぶ。
一般に、使われなかったデータは以下の場合に生じる。
• 1 つの事象に対し異なる値が報告されており、その一方を真、他方と偽として扱ってシミュレーションを行う場合。
• あるシミュレーションが時刻 T に開始され、その後、補足的な議論正記法と負記法のどちらが効率がよいかは一般に決めることはできない。しかし大規模シミュレーションでは多くの場合、データの数は非常に多くなるため、前節の考察では負記法の方が記憶容量の点で有利と思われる。
また、4 節では射影の操作 (例えば DB(Tu0 ,Tv0 ) /e) を無視している。これは、一般的な RDB を用いた場合、これ
らの操作は log N 程度の高速な手法が用意されていることを前提としているためである。
また、事象集合 E の管理コストも上記の議論では無視

そのシミュレーションに関係する事象のデータが報している。これは、シミュレーションに関係する事象と告された場合。

いうのは、一般に機械的に指定されることを前提として
負記法では以下のデータ集合を記録することになる。

D̄ v =

Xいる。例えば災害シミュレーションでは、入力としては指定された領域の特定の種類の地物 (「建物」や「道路」、(DB(0,Tv ) /e − D v )「震度分布」など) という形で与えられる。これらをリスe∈E v

トアップすることも可能だが、汎用的なデータベースを

ここで注意しておかなければならないのは、上の式で DB用いていれば、必要に応じて検索により求めていてもその変わりに DB(0,Tv ) を用いていることである。つまり D̄ v
は時刻 Tv において使われなかったデータのみを記録する。

れほどコストは生じないと考えられる。
この他、以下のような問題が形式化の上で残っている。

これ以降に入ってきたデータについては、そのデータのタイムスタンプ T とこのバージョンのタイムスタンプ Tv
を比較することで D v に含まれるかどうかが判定できる。

4.2.1

必要記録容量¯ ¯
負記法による記録容量は O(¯D̄ ¯) である。一般に関連参考文献

する事象で使われないデータは、使われるデータより少[1] Satoshi Tadokoro. Japan government special project:

ないため、正記法よりは効率が良いと考えられる。

4.2.2

development of advanced robots and information systems for disaster response (daidaitoku) — for earthquake disaster mitigation in urban areas —. In Proc.
of IEEE Workshop on Safety Security and Rescue
Robotics (SSRR03), 2003.

データの登録コスト

新しく登録されるデータは既存のバージョンでは使われなかったデータであるので、負記法では本来ならばい
ちいち D̄ v に追加する必要がある。しかし上で述べているように、データが記録された時刻とバージョンのタイ[2] Satoshi Tadokoro. An overview of japan national spe-

ムスタンプの比較を行うことで D v に含まれているかど

cial project daidaitoku (ddt) for earthquake disastermitigation in urban areas. In Proc. of IEEE International Symposium on Computational Intelligence in
Robotics and Automation (CIRA2003) Workshop on
Advanced Robots and Information Systems for Dis-

うかを容易に判定できるため、実際には余計なコストは
生じない。

4.2.3

無矛盾性チェックのコスト

2 つのバージョン u と v の無矛盾性をチェックするた

aster Response, 2003.

めには以下の操作が必要である。

∀u0 ∈ Tr(u), ∀v 0 ∈ Tr(v), ∀e ∈ (E u0 ∩ E v0 ) :check D̄ 0 /e − D̄ 0 /e = DB 0 0 /e if T 0 < T 0vu(Tu ,Tv )uv
check D̄ 0 /e − D̄ 0 /e = DB 0 0 /e if T 0 < T 0u

た だ し 、u0v

(Tv ,Tu )v

hE u0 , Tu0 , D u0 , Gu0 i お よ び v 0

=

u

=

hE , T , D , G i であり、DB(Tx ,Ty ) は時刻 Tx から 時
v0

v0

v0

v0

刻 Ty の間に記録されたデータの集合である。この操作の計
¯ P¯
¯ P¯
¯
P¯
算コストは、O( ¯DB(T 0 ,T 0 ) /E ¯ + ¯D̄ u0 ¯ + ¯D̄ v0 ¯)v• バージョンの抽出に関する計算コスト。
• 統計的処理の合同や、モンテカルロシミュレーションの結果の解析に対するバージョンの考え方。

u

である。

31

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-6 (5/24)

照明変動に頑健な ID 認識とロボットの姿勢検出
Robust Under Varying Light Condition and Accurate Detection of Object Orientation and ID

永橋知行，清水彰一，藤吉弘亘
Tomoyuki NAGAHASHI , Shoichi SHIMIZU , Hironobu FUJIYOSHI

中部大学 工学部情報工学科
Dept. of Computer Science, Chubu University, Japankida@vision.cs.chubu.ac.jp, shiyou@vision.cs.chubu.ac.jp, hf@cs.chubu.ac.jp
http://www.vision.cs.chubu.ac.jp/
Abstract

本稿では，このような問題を解決する手法として，サブマーカの色識別を必要としない ID 認識とロボットの向This paper describes a novel approach to detecting orientation and identity of robots without color segmentation. The continuous DP
matching calculates the similarity between the

きを連続 DP マッチングを利用した計算手法について提案する．本手法は，ロボット上部のマーカの色変化パター
ンを連続 DP によりパターンマッチングし，その最小累積距離を ID 認識に，バックトレースによる最適パスの対reference pattern and the input pattern bymatching the intensity changes of the robot
markers. After the continuous DP matching, asimilarity value is used for object identification,

応からロボットの向きを同時に計算する．

and correspondences of the optimal route obtained by back tracing are used for estimating
the robot’s orientation. This method archives
orientation estimation of less than 1 degree and2ロボットのマーカと従来法

2.1

従来法

ロボカップ小型リーグでは，直径 50 mm の青色または黄色の円をメインマーカとしてロボット上部につける．また，
サブマーカとしてロボットの上部にオレンジ色 (ボールに使用)，黄色，青色以外の 3 色のパッチを追加して，ID 認

robustness with respect to varying light condition.

識や向きの検出に使用可能である．現在多くのチームで使用されているパッチの配置例を Figure 1 に示す．

1

はじめに

より正確にロボットをビジュアルフィードバックで制御するには，ロバストなビジョンアルゴリズムが必要である．
特に，ロボカップ小型リーグでは，照明変化に対してロボットの姿勢 (向き) や ID を正確に認識する必要がある．
一般的なグローバルビジョンシステムでは，画像の色変換

Figure 1: 従来の ID プレート後，色識別，ID 認識，ロボットの姿勢 (向き) の流れとなる．ロボットの向きを得るには，最小 2 乗法[Murakami,
いる．このような姿勢推定の結果は，前処理である色識別(a)white bar は，白いバーと背景の黒とのエッジ点から最小 2 乗法やモーメント法[Ball, 2004]により角度を求める．また，ID はバー以外のサブマーカの配置から認識する．このような手法では，ロボットの方向と ID 認識のの結果に依存する．色識別として，CMVision というライ
ブラリが提供されており[Bruce, 2000]，多くのチームで使2 つのプロセスを必要とする．また，ロボットの台数が増えた場合，サブマーカに色を用いる必要がある．

2003]やモーメント法[Ball, 2004]による手法が提案されて用されている．また，照明変動に対して頑健な色識別のための色校正法[Egorova, 2004]が提案されている．しかし，(b)butterfly はバタフライ型と呼ばれ，マーカの対称性

一般に色校正には多くの時間が必要である．また，校正時からロボットの回転角度を求め，高精度に ID 識別が可能であることが報告されている[Bruce, 2003]．

の照明環境下以外では，その色識別精度は低下するとい(c)pie slice-based は，ロボットの中心から円形に走査して，2 色以上の色配置を検出し，ID と角度を認識する

う問題がある．

32

立つ．

(xc − xi )2 + (yc − yi )2(xc − xj )2 + (yc − yj )2(xc − xk )2 + (yc − yk )2

=
=

(1)

式 (1) は連立一次方程式となるため，ガウスの消去法を用いて円の中心位置 (xc , yc ) を解くことができる．以下に 3

Figure 2: ID パターン例 (提案手法)

点推測による円の検出手順を示す．

手法である[Hibino, 2002]．しかし，pie slice-based は円

Step1 入力画像よりメインマーカの輪郭点を抽出する．

上のデータ数が 40 個であるため，向きの解像度は 8 度とStep2 輪郭点からランダムに 3 点選び，式 (1) を用いて円中心を求める．

低い．
上記に示したマーカによる従来法は，色識別の結果をStep3 求めた円中心座標に重みをつけて投票する．

利用しているため，影領域等での ID 誤認識や向きの推定
精度の低下を招くという問題がある．

2.2

Step4 Step2∼3 の処理を n 回繰り返す．

提案手法のマーカ

最終的に投票数が最大の画素を中心座標 (xc , yc ) とする．

本稿では，色識別を行わずに円周上の輝度パターンを直3.2

接マッチングする手法を提案する．本手法では，Figure 2

円周パターンの 1 次元化

3.1 で求めた中心から半径 r(本稿では 10 pixel) の円周上の YUV 成分を Figure 4 に示すように，1 度間隔で 360 点取得する．角度 θ における円周上の座標 (x, y) は次式となる．

に示すように，適当なサブマーカをメインマーカの周りに自由に設置すれば良い．そのため，設置する上での手間を大幅に削減できる．さらに，サブマーカの色配置から IDを識別することから，多くの ID を容易に作成することが可能である．また，認識時には，ID 毎のルールを決定す

x = r cos θ + xc ,y = r sin θ + yc

(2)

る必要はない．
実際には，半径 10 pixel の円周上の点は 76 点であり，360

DP マッチングによる物体識別3点の分解能がない．そこで，座標 (x, y) の座標点における輝度値 I(x, y) を，Figure 5(a) に示すように 4 近傍の輝度

カメラ画像から得られたロボット上部の円周上の輝度パ値からバイリニア補間により求める．

ターンと予め登録したパターンとの DP マッチングを行う．

I(x, y)DP マッチング後，その最小累積距離を ID 認識に，バックトレース後の対応からロボットの向き推定に利用する．

= (1 − n)((1 − m)I(0, 0) + mI(1, 0))+ n((1 − m)I(0, 1) + mI(1, 1))

その処理の流れを Figure 3 に示す．

(3)バイリニア補間による Y 成分の抽出結果を Figure 5(b)1. 色変換 (RGB to YUV)
2. メインマーカの抽出
3. 円周上の輝度パターンの作成 (1 次元化)に示す．バイリニア補間を行うことで，ロボット向き検出時

4. 連続 DP マッチングによる ID 認識
5. バックトレースによる向き推定

4(b) に 1 次元化した円周上のデータ (YUV) を示し，各角度 θ に対する輝度値関数を次式のように定義する．

3.1

におけるサブピクセル推定が可能となる．最後に，補間した I(x, y) の Y 成分を，0∼255 の値に正規化する．Figure

メインマーカの中心位置検出

I(θj ) = I(r cos θj , r sin θj )j = 0, · · · , 359(4)

メインマーカを中心とする円周上の色成分を基に ID の認
連続 DP マッチングによる ID 認識

識，及びロボットの向きの算出を行うため，メインマーカ

3.3の中心位置を予め正確に求める必要がある．以下に，円周各ロボット上部のパターンから，予めメインマーカの中

上の 3 点を用いた円中心位置の高精度検出法について述心からある半径 r を持つ円周上の輝度パターンを登録しべる．

ておく．この作業は，画面上からロボットの正面 (0 度) とメインマーカの円周上の 3 点が与えられると，その 3なる位置をユーザがマウスクリックにより与える. このよ

点から円を表すパラメータを推測することが可能である．

うに，本提案手法は従来法で用いた ID 認識のためのルー

中心座標を (xc , yc ) とし，メインマーカ円周上の 3 点をル設定を必要とせず，短い時間で簡易に ID の設定が可能(xi , yi ), (xj , yj ), (xk , yk ) とすると，式 (1) の関係が成り

である．

33

Figure 3: 連続 DP マッチングによる ID 認識と向きの推定

Figure 4: 1 次元データの作成法

3.3.1

連続 DP マッチング

DP マッチングは，異なる二つの時系列信号の類似度と最適な対応を求める手法であり，音声認識等の，さまざまな分野で利用されている．DP マッチングは非線形の伸縮により，長さの異なるパターンの類似度を計算することができる[Sakoe, 1978]．

Figure 5: バイリニア補間
たパスに対応したラベル (a), (b), (c) をバックトレースの提案手法では，データの始点を固定しない連続 DP マッ際に用いるために記憶しておく．

チングを行い，更に，入力パターンを２周分用意すること

ローカルディスタンス ld(i, j) は式 (7) より求める．

で始点の対応位置に関する問題を解決する．以下に，用いる連続 DP マッチングの適用法について示す．

ld(i, j) = (It (θi ) − It−1 (θj ))2

DP マッチングにおける始端領域においては，式 (5) に示すような初期値を設定する．
g(i, 0) = 0 (i = 0, 1, . . ., I)(5)g(0, j) = ∞ (j = 1, 2 . . . , J)

(7)

格子点 (i, j) までに選択された経路の長さを式 (8) より求める．

 c(i − 1, j − 2) + 3
c(i, j) =c(i − 1, j − 1) + 2c(i − 2, j − 1) + 3

連続 DP マッチングに用いる DP パスを Figure 6(a) に示

if(a)
if(b)
if(c)

(8)

す．各格子点 (i, j) における累積距離 g(i, j) を次式より求以上の操作を各格子点にて行い，式 (9) より累積距離をそめる．

れまで辿った経路の長さで正規化する.

g(i, j)=g(i − 1, j − 2) + 2 · ld(i, j − 1)g(i − 1, j − 1) + ld(i, j)ming(i − 2, j − 1) + 2 · ld(i − 1, j)

: (a)
: (b)
: (c)



+ ld(i, j)

G(i) =(6)
3.3.2

g(i, J)c(i, J)

(9)

ID 認識

式 (6) は，Figure 6(a) に示す対照的な３つのパスから

マウスクリックにより各ロボットに対して，ロボットの最も特徴が似ているパスを選択する．このとき，選択され正面を 0 度とした 360 度までの 1 次元化したパターンを

34

Figure 7: バックトレーシング

Figure 6: 対称型 DP パス

登録パターンとする．カメラ画像からメインマーカを検以上より，バックトレースにより得られる最適パス上出し，入力パターンと全登録パターンとの DP マッチンの対応からロボットの向きを推定することが可能となる．

グを行う．そして，累積距離が最小となる登録パターンのFigure 8 に，同一 ID を持つロボットのバックトレース例

ID を入力パターンの ID と決定する．

を示す．DP マッチングにより得られた最適パスが示す対応が正確であることがわかる．

3.4

バックトレースによる向きの検出

ロボットの向き検出するには，3.3 で述べた DP マッチン
グの際にラベル付けされた DP パスを用いて，バックト
レースすることで入力パターンと登録パターンの局所的な対応を求める．その処理を以下に示す．

1. 選択したパスの記憶
各格子点 (i, j) において，最小累積距離を求める際に，式 (6) により選択されたパスをラベル (a)，(b)，(c) として記憶する．
2. 開始点の決定
正規化累積距離を J/2 ≤ i ≤ 2I の区間で求め，最小となる i フレームを以下の式より求める．

i = argmin(J/2≤i≤2I )G(i, J)

Figure 8: バックトレース例

実験

4

(10)

本手法の有効性を評価するために，ロボットの向き推定

3. バックトレースと照度変化に対する ID 認識を，シミュレーションと実画

i フレームを開始点とし，バックトレースを行う．Figure 7 に示すように，各格子点においてラベル付けされた (a)，(b)，(c) のどれかのパスを参照してバックトレースすることで最適ルートを求める．(a) のパスは像を用いた実験を行う．

脱落を意味し，(c) のパスは挿入を意味する．(b) のパ

ロボット姿勢推定実験結果

4.1.1

シミュレーション実験

0∼359 度の間を 1 度間隔で回転した ID パターンを擬

スは，入力パターンの i フレームと登録パターンの j似的に生成し，これを入力画像として回転角度である向フレームが 1 対 1 に対応していることを意味する．そきを求める．ID パターンには 11 種類用意し，計 3960 パ

こで，(b) のパスが選択された場合のみ，登録パター

ターンに対して向きの推定実験を行った．推定した角度のンのフレームナンバー θj を入力フレーム θi から引い平均誤差を Table 1 に示す．Table 1 の “最小 2 乗法” は，た値 θ をロボットの向きを表す角度とする．この処理を，バックトレースが j = 0 となる始点まで行う．

θ = θi − θj

4.1

(11)

白いバーのエッジを最小 2 乗法により求めた結果であり，“2 次モーメント” も同様に白いバー領域を 2 次モーメン
ト法により求めた結果である．また，実画像を用いた場
合，メインマーカ領域を正確に求められるとは限らないた

4. バックトレースの終了(b) のパスが選択された場合に求めた角度 θ の平均をTable 1 より，本手法の精度は 1.0 度未満であることがわ

求め，これをロボットの最終的な向きとする．

かる．また中心ずれとは，中心位置からの誤差を表し，中め，提案手法では中心位置のずれに対した実験を行った．

35

セル (14 mm) ずれたとすると，メインマーカの端に近い

Table 1: 方向算出結果の平均誤差 [度]

位置となり，色の変化パターンを含むように 1 次元デー
タを生成できないからである．

中心ずれ

提案手法

従来法

SSD

DP

最小 2 乗法

2 次モーメント

0

0.30

0.76

0.85

1.08

1

1.71

1.10

-

-

2

4.20

1.75

-

-

Table 2: 方向算出結果の平均誤差 [度]提案手法

最小 2 乗法

2 次モーメント

白いバー

0.85

1.17

0.96

ID パターン

0.95-

Figure 9: ID 認識実験結果

心位置から 8 近傍にずれた場合を “中心ずれ 1” ，さらに

16 近傍の外側の画素を “中心ずれ 2” とする．中心位置がずれた場合，SSD の結果に比べ DP の方が，より精度良く求めることが可能である．これは，中心位置がずれるこ

4.2.2

実画像における照明変動に対する評価実験を行う．照明を 100 lux から 2,900 lux まで 100 刻みで変化させた際とで生じる長さの伸縮を, DP マッチングが吸収して対応のロボット上部の画像を Figure 10 に示す．また，11 種を求めることができるからである．

4.1.2

実画像を用いた実験類の ID を 100 lux から 3,000 lux まで変化させた 330 パ
ターンの画像に対して ID 認識実験を行った結果を Figure

実画像を用いた実験の方向の算出実験を行う．マーカを 1 度づつ回転させたと11 に示す．従来法では，600 lux から 1,000 lux の画像に対して認識率を 100%になるように色識別の閾値処理を手きの真値との平均誤差を Table 2 に示す．実画像を用いた動で設定した．一方，提案手法は 1,000 lux で撮影した１

実験においても，シミュレーション実験と同様に，提案手パターンを登録パターンとして実験に用いた．Figure 11

法は従来法と同等以上の精度を得ることができた．また，より提案手法は，色識別を行う従来法と比べて照明変動に

Figure 1(b) のパターンである白いバーに対して，提案手頑健であることがわかる．これは，提案手法が色識別を行法で方向を推定した結果，平均誤差 0.85 度となった．こわず，ロボットの中心から一定の半径で走査して得られたのように，提案手法は，バタフライ型や白いバーを用いた

輝度パターンの変化をマッチングに利用するからである．

ID マーカの向きを正確に求めることが可能である．これは，敵チームの正面向きからパスの方向を推定すること

5

実際のカメラを高さ 4,000 mm の位置に設置し，マーカに利用できるため，インターセプト等の戦略への応用が提案手法のメリットを以下に挙げる．

期待できる．

4.2
4.2.1

考察

ID の認識実験結果
シミュレーション実験

照明変動に対する頑健性を評価するために，擬似的に照度を変化させた画像を作成しシミュレーション実験を行う．CG における光源の照度を 0.1 から 1.1 まで 0.1 刻みに変化させることによって，擬似的に照明変動を作り出す. 評価実験には，1 度刻みで 360 度回転したものに照明を変化させた計 43560 パターンを使用する. Figure 9 に認識結果を示す．本手法は中心ずれが 8 近傍以内であれ
ば，照明変動に対して安定して ID 認識が可能であることがわかる．しかし，中心位置が 2 ピクセルずれた際，ID

Figure 10: 100 lux から 2900 lux までの実画像認識率は低下している．これは，縦横それぞれに 2 ピク36

本手法では，円周パターンの 1 次元化を行っている．そのため，円の中心が正確に求まっていなければ，正確に 1
次元化を行うことが困難になる．また，ID 認識及び向きを正確に行うには，中心位置の誤差を約 2 画素以内 (14 mm)に抑える必要がある．ID 認識を行う際，1 つのパターンに対し全ての登録パターンとマッチングをとらなければならない．よって，ロボットの数が増えるとその計算量が多くなる．

6
Figure 11: 照度変化に対する認識率

まとめ

本稿では，登録パターンと入力パターンの 1 次元データ
を DP マッチングにより，ID 認識とロボット方向を同時に求める手法について提案した．提案手法のロボット方• ID の初期登録の簡便性
ID の初期登録は，ID の中央 (メインマーカの中心)とロボットの向いている方向をマウスクリックにより指定するだけで，各 ID の 1 次元データに変換し，率を得ることができ，照明変動に対して頑健であること

これを登録パターンとして記憶する．このように各を確認した．また，提案手法はルールベースを必要としID 毎にサブマーカの配置からルールを作成する必要がない．

ないので，敵ロボットの ID 並びに向きを知ることができ

向を約 1 度未満の誤差であり，従来法と同精度であることを示した．また，ID 認識では，実画像における実験よ
り，300 lux から 3,000 lux の照度変化に対し高い ID 認識

る．そのため，敵ロボット間のパスのインターセプト等の• 多くの ID を作成することが可能
従来法では，サブマーカより向きを求める手法があり，マーカの配置を予め考慮する必要がある．また，白いバーを用いた場合は，サブマーカを配置するス
ペースが狭くなるため，ID の種類を多く用意することができない．しかし，提案手法では，サブマーカの配置や大きさ等の配慮が必要なく，無作為に取り戦術幅を広げることができると考えられる．

参考文献[Murakami, 2003] K.Murakami,
S.Hibino,
Y.Kodama,
T.Iida, K.Kato, S.Kondo, and T.Naruse: “Cooperative
Soccer Play by Real Small-Size Robot”, RoboCup 2003:
Robot Soccer World Cup VII, Springer, pp. 410-421,
2003.
[Ball, 2004] Ball D., Wyeth G., Nuske S: “A Global Vision
System for a Robot Soccer Team”, Proceedings of the2004 Australasian Conference on Robotics and Automation (ACRA), 2004.

付けるだけで，ID を作成することができる．そのため，容易に複数の ID パターンを作成することが可能
である．

[Bruce, 2000] J. Bruce, T. Balch, M. Veloso: “Fast andInexpensive Color Image Segmentation for Interactive
Robots”, In Proceedings of IROS-2000, Japan, 2000.

• 照明変動にロバストな ID 認識提案手法では，YUV の Y を正規化した 1 次元デー
タから DP マッチングを用いて ID を認識する．そのため，従来法では必要とするサブマーカの色識別と，その閾値を決定するための色校正を必要としない．

[Egorova, 2004] A.Egorova, M.Simon, F.Wiesel, A.Gloye,
and R.Rojas: “Plug & Play: Fast Automatic Geometry
and Color Calibration for Cameras Tracking Robots”,
Proceedings of ROBOCUP2004 SYMPOSIUM, 2004.
[Bruce, 2003] J.Bruce, M.Veloso:“Fast and Accurate
Vision-Based Pattern Detection and Identification”,
Proceedings of ICRA-03, the 2003 IEEE International
Conference on Robotics and Automation (ICRA’03),
May, 2003.

• 対戦相手のロボットの向きを取得可能
バタフライ型の ID は，実験で使用したパターンと同種であると考えられるため，初期登録さえしておけば，敵ロボットの ID とロボットの角度を求めること[Hibino, 2002] S.Hibino,
Y.Kodama,
Y.Nagasaka,
T.Takahashi, K.Murakami and T.Naruse: “Fast Image
Processing and Flexible Path Generation System for
RoboCup Small Size League”, RoboCup 2002: Robot
Soccer World Cup VI, Springer, pp. 53-64, 2002.

が可能である．また，白いバーを用いたマーカについても，角度を求めることができることを実験で示した．これにより，対戦相手のロボットの方向も知ることができるため，パスのインターセプト等，戦略[Sakoe, 1978] H. Sakoe, S. Chiba: “Dynamic Programming
Algorithm Optimization for Spoken Word Recognition”,
IEEE Trans. Acoust., Speech, and Signal Process.,
Vol.ASSP-26, pp. 43-49, 1978.

の幅が広くなる．
以上に挙げたメリットに対して，提案手法のデメリットを以下に述べる．

37

社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-7 (5/24)

小型  リーグのためのイメージモザイクによるグローバルビジョンシステム

         
林裕司 遠山聖司 藤吉弘亘

      
中部大学 工学部

情報工学科!"#  $"  $  %& '"             


 



イク画像では，高さを持つオブジェクト +ロボット等- が

画像の重なり領域で二重に見え，認識が困難となる問題         

              

が生じる．そこで，我々は認識対象オブジェクトのフィー
ルド面からの高さを考慮したイメージモザイクによるグ

ローバルビジョンシステムを提案する．本システムでは，  !  "  

自由な高さでのモザイク画像を生成することが可能であ   ! !  #    %るため，高精度なロボットの位置推定が可能である．

$   #   #  

台のカメラによる重なり領域での
識の問題

#

  #    認      !  # 

*$    &+./3 %1- で撮影するには，       !  '      





  !    ..

ラ * がカバーするように配置する必要がある．画像の一部

   #(    のように画像の一部を重ね合わせて，左半分をカメラ ，右半分をカメ         

台 の カ メ ラ を 用 い て ，フィー ル ド 全 体 を 高 解 像 度を重ねることにより，認識結果の統合処理が必要になる．

 #

統合処理には以下の手法が考えられる．

) * +, ) -(# 最新フレームのカメラ結果を優先 台のカメラ間が )  *

非同期の場合，常に最新フレームの認識結果を用いる．


# 境界による判定統合 台のカメラの重なり領域内にお

はじめに

*

ロボカップ小型リーグでは，*) 年のルール変更に伴い

いて，境界を予め決定する．各カメラ画像において

フィールドサイズが .. × ) に広くなった．こ

境界から内側のみ認識対象とする．

ローバルビジョンでは認識精度の低下を招くため，複数台$# トラッキング結果による統合 重なり領域においては，のカメラを用いる手法が主流になりつつある/0 *)1#

前フレームでトラッキングが成功したカメラの処理/0 *)1．* 台のカメラを用いた場合，各カメラ画像

結果を使用．

れにより，従来用いられてきた 台の広角カメラによるグ!# 重み付き統合 各カメラ画像の認識結果を重み付けしにおいてロボットの位置推定や 2 認識等のビジョン処理の後，* 枚の画像が重なる領域において認識結果の統合処て共通の座標に統合して使用．

理が必要である/0 *)1．

例えば，  

このような複雑な統合処理を回避する一手法として，*枚の画像からにおいてカメラ の画像上のロボット *枚のモザイク画像を生成し，ビジョン処

は， 2 用マーカーの一部が切れているため 4，，2 でではボー

はロボット との識別が不可能である．また，0 では，カルやロボット等の高さが異なるオブジェクトが複数存在す

メラを取り付ける位置が変わる度に，ロボット上部の 2るため，フィールド面上の対応点を用いて生成したモザ

用マーカが切れない場所に境界を再設定する必要がある．

理を施すことが考えられる．しかし，

38

camera1

camera2

Camera position
Robot1

Robot2  *, フィールド面での射影変換行列の算出)#* フィールド面のモザイク画像の生成  * にフィールド面と各カメラ画像間の関係を示す．

カメラ

における座標/    1

8 /   1と世界座標  8に対応したモザイク画像座標  ¼ 8 /   1から平面射影行列  を求める．平面射影行列は，9#Camera1 image
 

Camera2 image  と呼ばれ，5 次元空間の各平面毎に異なる値を持つ．

また，* 枚の画像間における ) 点以上の対応点から求ま, カメラを * 台使用時の設置例

り，5 × 5 の 6 要素，自由度は の行列となる．同様にカメラ * の画像座標  からモザイク画像への平面射影行列
 を求める．これらの関係は次式で表現される．

これらの手法では，認識後に統合処理を行うため，画像端での誤認などが起こる．そこで，認識処理前の画像 * 枚をイメージモザイク処理により枚の高解像度画像を生成¼

する．これにより認識前に統合処理を行い誤認を防ぐ．



8









   





¼

8

 

+*-

8



+5-

+ -

   



¼* 台のカメラから取得した各画像を平面射影変換により，枚のモザイク画像を生成する．処理画像を 枚にすることで，画像端での 2 の誤認や各カメラからの認識結果の統合処理を省くことができる．しかし，平面射影変換では対応を求めた基準平面上に存在しない物体は，モザイク
画像上において，二重に見えるなどの問題が生じる．そこで，本システムでは，ボール，味方ロボット，敵ロボッ
トの高さに対応した平面における 5 枚のモザイク画像を生成する．その後，各モザイク画像に色識別， 2 認識等の処理を施す．本システムでは，カメラキャリブレーショ
ン/$
8  


6 71により求めた外部・内部パラメータから擬似的に対応点を生成し，対象とする高さにおけるモザイ
ク画像を生成するため，ロボット等の高さを考慮した位  5, レンズ歪み補正

置推定が可能となる．

39)#*#* レンズ歪み補正
カメラから取得した画像には，レンズ特有の歪みが含まれる．歪みを含んだ画像座標における対応点から平面
射影行列  を求めると誤差が生じ精度が低下する．そこ
で，カメラキャリブレーションから求めたレンズ歪み係数，  を用いて補正を行う．歪みを含んだ画像座標 +  から歪みの含まない座標点 +    - への変換を式 +.- に示す．+   - は画像座標の中心， は画像中心からの距
離， はせん断係数である．
 8 

 



8

 +



8

+

 8 


:



:

:

:



  ), カメラ画像







+)-

-

+.-

レンズ歪み補正後の対応点から，平面射影行列を求める
ことで，より正確な平面射影変換，即ち位置推定が可能となる．   5 に，レンズ歪み補正後の画像を示す．歪み補正することにより，画像端における湾曲していたラインが直線に補正されていることがわかる．

)#*#+ モザイク画像座標と世界座標の対応
平面射影変換で用いる座標系として，どちらか一方の画像座標系に他の画像座標系を変換する考え方 +相対座標系  ., フィールド面でのモザイク画像と，どちらの画像を新しい座標系，例えば世界座標に座標変換する考え方 +絶対座標系- の * つがある．本手法では，モザイク後の画像座標から，世界座標を直接求めること

", 求めた  と  によりモザイク画像を生成す


ができる後者を用いる．このとき，分解能を .3 %る．その際に，モザイク画像上の重なり領域ではブレンとなるように世界座標系を設定すると，フィールドサイ

ディング処理を施す．

ズは .. × ) であるため，モザイク画像の解像度は  ×  画素となる．しかし，実際のカメラ画像の解像度は . .3 % であるため，モザイク処理の際に，値が存在しない画素が生じる．このような画素は最近
隣内挿により補間する．そのため，ビジョン処理により求めたモザイク画像上の座標から世界座標を式 +;- により求めることが可能となる．
世界座標  /1 8./ %1

 モザイク画像の座標  / %1 +;¼)#*#) フィールド面のモザイキング
フィールド面のモザイク画像の生成過程を以下に示す．
"* カメラ の画像上で位置が確認できるフィー+ -ルド面の特徴点  を選定し，その世界座標  +    とカメラの画像座標

  ;, 二重に見える原因+  - を計測する．

"+ 式 より世界座標  をモザイク画像座標 に変換する．
") モザイク画像座標  とカメラ の画像座標+;-¼

  ) に各カメラからの画像を，   . にフィー¼

ルド面で生成したモザイク画像を示す．フィールド面上のの ) 点以上の対応点群から平面射影行列  を求める．カ

ボールは，継ぎ目がないモザイク画像が生成できているメラ *+*- も同様の方法で平面射影行列  を求める．

ことがわかる．しかし，フィールド面から高さを持つロ40

ボット上部の 2 マーカが二重に見えるという問題が発生している．これは，   ; に示すように，フィールド面実験

高さを考慮したモザイク画像を用いたロボットの位置推から高さを持つ世界座標  +     - は，カメラ では世界座標  へ射影され，誤差  が生じる．同様にカメラ  * では  に射影され，誤差  が生じるためである．

定実験を行う．

)#+ 高さを考慮した仮想平面上のモザイク画像の生成

フィールド面上の )6 × 5) の領域 +重なり領域,#* 実験概要
本実験では，* 台のカメラを高さ約 5，それぞれ
5- が視野に入るように設置する．カメラキャリブ

レーションには . の正方形が描かれたキャリブレー

フィールド面上の特徴点から求めた平面射影行列は，フィーションシートを床に敷き，正方形の頂点をランドマーク点

ルド面と高さの異なるロボット上面での対応を取ること+カメラはできない．高さを考慮したモザイク画像を生成するたは ) 点，カメラ * は ) 点- として用いた．ロ

ボットの位置推定実験として，高さを考慮したモザイク

めには，求めたい高さを持つ平面上の特徴点を求め，平面

画像とフィールド面のモザイク画像の各 ; 点の画像座標

射影行列を計算する．しかし，特定の高さを持つ平面上にから世界座標を求めた．

存在する特徴点を実際に設置し測定するのは非常に困難,#+ 実験結果である．そこで，   7 に示すようにフィールド面の特徴点から求めたい高さの平面上 +仮想平面- の画像座標を$

擬似的に生成し，仮想平面上での平面射影行列を求める．

"* カメラ の画像上で位置が確認できる特徴
"+ フィールド面での世界座標  を  軸方向に生にフィールド面でのモザイク画像と仮想面 +高さ.- でのモザイク画像から計算した世界座標と実測値の誤差を示す．仮想面でモザイクすることにより位置推+ -点  +    - を選定する．

定精度が向上することがわかる．仮想面でのモザイク画
像を用いた位置推定では，平均誤差が約 ) であり，実成したい仮想面の高さ + の高さ- を持つ世界

際のカメラ画像の解像度 +. .3 %- より小さいこと

座標 +     - を求める．

から，高精度な位置推定を実現しているといえる．  ") 世界座標  から外部・内部パラメータを用い

6 に各位置における誤差分布を示す．フィールド面のモザ  6+- に示すように，高さをもつオブて以下に逆投影を行う式を示す．逆投影により画像座標

イク画像では +   - を求める． は回転行列， は平行移動ベクトル， は焦点距離， はせん断係数である．

ジェクトが光軸中心から離れる程その誤差は増大していることがわかる．一方，仮想平面でのモザイクした場合は，全体的に推定誤差が小さいことがわかる．









 














,#) 処理時間   

本グローバルビジョンシステムのハードウェア構成を $* に示す．モザイク画像を生成する際，毎フレームごとに", 世界座標  から仮想平面 高さ  のモザ+

 を用いて座標変換すると計算コストが高くなる．そこ-

イク画像座標 ¼ に変換し，¼ と  の関係から平面射影
行列  ¼ を求める．カメラ *+*- も同様の方法で画像座標

¼ を求める．
求めた  ¼ と ¼ より仮想平面でのモザイク画
像を生成する．その際に，モザイク画像上の重なり領域ではブレンディングを施す．

"-

 

に，ロボットの高さを. とした際のモザイク画像を示す．フィールド上のボールはモザイク画像上にずれが生じるが，高さを持つロボット上部のマーカは継ぎ目がなく生成されていることがわかる．イメージモザ
イクによるグローバルビジョンでは，認識対象オブジェク
トの高さにおけるモザイク画像を生成するため 2 の誤認
識や統合処理を必要としない．また，モザイク画像には，従来のビジュアルアルゴリズムが適用できるというメリッ  7, 仮想平面の算出

トがある．

41

  6, 位置推定誤差

$

高さ

 

平均誤差
方向

 方向

方向

 方向

フィールド面

 

 



 





仮想面













方向

$ *, 実験環境



5 枚のモザイク画像の生成に要する時間は +フィールド面カメラ

イク- 約 56，色識別に約 5 ， 2 認識に約 )，合*! - ある． *!  のフレームレートでは高速なビジュアルフィードバック処理を実現できないため，
過去フレームで求めたオブジェクトの座標周囲 5 %+約.- のみ処理を施すことにより，モザイク画像生成に約 . .，色識別に約 . .， 2 認識に     用モザイク，味方  用モザイク，敵  用のモザ

*

最大誤差

, 仮想平面でのモザイク画像

&< $+<$- を作成する．作成した <$ による

+約

標準偏差

 方向

で，モザイク画像座標は，予めカメラ画像と対応を表す

計, 位置推定誤差 /1

，合計

+ *! - の高速化が実現できている．

42

!


"#$

ズームレンズ% &  "#$広角レンズ' %&"()*$キャプチャーカード+& !"サイバーテック社$



まとめ

/&66)1 

 

本稿では，イメージモザイキンクによるグローバルビジョ&,

 ! ンシステムを提案した．提案したシステムは，* 台のカメ  ! # CCC @& A

))#.5

/9 **1  9 G &

ラ画像を仮想平面上でイメージモザイキングすることに 4 #
66)

E G#より，画像の重なり領域での 2 誤認を軽減し，モザイク  >& $ $& E 画像に対して従来のビジョンアルゴリズムを適用できる

D &  $ > ,というメリットがある．また，ロボットの高さを考慮した 

モザイク画像を生成するため，高精度な位置推定を評価することを実験により示した．今後の課題として，さらな   .5#;) **/0  *1 = 0  $ & 0  D 

る処理速度の向上を目指す予定である．

A , 

 !

参考文献

%  

 ! (#* =  ( */0 **1  0 = 2  = 2, 4    4   # !  *  >4 *577

*7.#*  **  

/0 *)1 2 0 ? @   > &,

4 ? A  !   # $

B !  *) 4 

!    4  +44- 4  *)/C *)1
4 C 4% ?   ?&&
4  D  !  ' D& 
( $  @,  *) 

<# *)    

   $ 2  *) 

 /E *)1 > 0 E,  & *) *)        $ 2 #
/0 *)1 20?

@,

 *),? 



<F
*)

       $ 2 
*)/$

6 71 

G$,

4   # $H  ! 9#4  52 D A# D < (I# ! $A   CCC =  !   4 # A 4#5 >  )5*5#5))

6 7/J *1 J J,4 K%  H  ! 

CCC $  B

4  D



**+ B#

% B ?  !

-, 55#55) *43 # B社団法人 人工知能学会
Japanese Society for
Artificial Intelligence

人工知能学会研究資料
JSAI Technical Report
SIG-Challenge-0521-8 (5/24)

行動に よ る 通信 B-MODEM
The B-MODEM

西野順二、 戸田英 治
Junji NISHINO, Eiji TODA

電気 通信大学 システム 工学科
Dept. of systems engineering,
The University of Electro-Communications

nishino@se.uec.ac.jp
メ ッセー ジを 送る こ と を 定式化す る も の で あ る 。 よ り 効

Abstract率の 良い 行動に よ る 通信の あ り か た を 考え 、 目的行動とThis paper presents a novel communication
method B-MODEM using actions for carrier instead of wireless communication medium. Behavior modulation is a kind of selection from

通信の 混合方式の 例を い く つ か 示す 。
以 下で は 、 B-MODEM の 実用上の 背景、 数理的な原理、実装例と そ の 方法を 説明し、 RoboCup シミ ュ レ ー ショ ン
サッカー [Pet99]で の 実験を 通じ て 有効性を 示す 。

action sequences leading given goal situations.
The proposed method shows effectiveness withan experimental result on scenario communications.

1

2

B-MODEM の 位 置付け

エー ジェン トの 行動は 位 置の 物理変化で あ り 、 実際の ロ
ボ ットなど で は 遠隔 か ら 光学的に 観 測で き る 。 こ の 光学
的 (視覚 的) な情報を 用い て メ ッセー ジ通信を 行う こ と がは じ め に可能で あ る 。 B-MODEM(Behavior Modulation and DE-

素で あ る 。 しか し、 多対多の 通信環 境で の 電波無線通信やModulation) は 、 本来そ の エー ジェン トに 必要な目的行
動、 サッカー の 例で は ドリ ブ ル に よ る ボ ー ル 運 び など 、 を行い つ つ そ の 上に メ ッセー ジを 載せ る も の で あ る 。 例え ば

音声通信は 混信や 外乱に よ る 不到達など 通信の 失敗の 発

自動車運 転で は 左折の 前に そ れ を 示す た め 左路側に 幅寄生が 頻繁で あ り 、 協調行動の 実現に 悪 影 響を 与え て い る こ

せ す る こ と が 推奨さ れ て お り 、 こ れ も 目的行動を メ ッセーと が 少なく ない 。 特に RoboCup サッカー 実機 部門の よ う

ジに よ っ て 変調した 例で あ る 。

マ ル チエー ジェン トシステム の 協調作業に お い て 、 相互の 通信は 意 志疎通を 行い 行動の 同期 を 実現す る 重要な要な多数の ロ ボ ットが 開か れ た 環 境で 動作す る た め に は 電

エー ジェン トの 行動に よ っ て メ ッセー ジ通信を 行う こ と波の 管 理が 必須で あ り 、 技術的に も 、 ま た 行政上で も 大きに つ い て 、 従来か ら ジェスチャ ー や ボ ディ ラ ン ゲー ジなどな課題と なっ て い る 。

を 対象に 、 ノ ン バ ー バ ル コミ ュ ニケー ショ ン と して 研究 がなさ れ て い る [黒川 94, 岡 98, 山中 03, 西田 03]。 しか し、

本稿で は 、 無線、 音声に 頼ら ない 多対多の 通信手段として 、 エー ジェン トの 行動と そ の 視覚 的観 測に よ る 手法、
B-MODEM を 提案 す る 。 物理的な意 味で エー ジェン トの行動と は す なわ ち 位 置、 配置の 変更で あ り 、 こ れ ら は 他のエー ジェン トか ら 光学的に 観 測す る こ と が で き る 。 行動のジェスチャ ー や 手話は 、 通信の た め だ け に 動作を 行う こ と中に 協調の た め の メ ッセー ジを 混入す る こ と が で き れ ば 、

メ ッセー ジを 扱 う も の で あ り 、 目的の 行動と 同時に 表出さ

電波や 音声に 頼ら ない 通信が 可能と なる 。 こ の よ う な行

れ る も の の 積極的な通信手段で は ない 。

に 関 す る も の で あ り 、 目的の 行動を 行い なが ら 同時に メ ッ
セー ジを 送る こ と に つ い て は 扱 わ れ て い ない 。 さ ら に 、 狭い 意 味で の ボ ディ ラ ン ゲー ジは 人間 が 無意 識に 表出す る

動に よ る 通信は 、 ジェスチャ ー や ボ ディ ラ ン ゲー ジと してい っ ぽ う 、 意 図的に 、 目的行動と 同時に メ ッセー ジを 行

実用に あ る 。 しか し、 い わ ゆ る ジェスチャ ー は 、 本来目的

動で 送り 受信す る と い う 、 よ り 一 般的で 実用的な枠組は こと す る 行動を い っ た ん 止め た う え で 通信の た め だ け の 動

れ ま で あ ま り 顧みら れ て こ なか っ た 。 実際に は B-MODEM

作を 行う も の で あ り 、 時間 効率の 面で は 時間 的な制約がが 提案 す る 通信モ デル に は 、 ジェスチャ ー や 手話も 含 ま れ

あ る なか で の 通信と して は 不満で あ る 。 本稿で 提案 す るて い る 。 本稿で は と く に 目的行動と メ ッセー ジを 意 図的

B-MODEM は 、 目的と す る 行動を 微小に 変調す る こ と でに 効率良く 混合す る こ と を 扱 う 。

44

3

行動に よ る 通信の 原理

3.1

通信路と して の 行動

こ こ で 、 ami に は い く つ か の 実現方法が あ る 。 任意 の
ai と mi と が 加法性を 持つ なら ば 、 ami = ai + mi と 与
え て 、

一 連の 動作に よ り 実現さ れ る 目的を 持っ た 動き を エー ジェ

A + M = (a1 + m1 , a2 + m2 , … al + ml , … an )ン トの 行動 A と 呼ぶ 。 動作は 物理的な運 動す なわ ち ア ク
チュ エー タの 稼働に よ り 引 き 起 こ さ れ る 行動の 基 本要素(3)の よ う に 表す こ と が で き る 。 こ の と き 全体の ステップ 数

で あ る 。 と く に エー ジェン トに 対して 与え ら れ た タスク

は n で あ り 、 標準と なる 目的行動と 同等の 効率を 実現でを 遂行す る た め の 一 連の 動作列を 、 目的行動と 呼ぶ こ と

き る 。

に す る 。

ま た 動作相互に 干 渉が 無く 、 時刻に も 依 存せ ず 、 順序のタスクの 遂行は 、 現在の 状態 S か ら 目標状態 G へ 遷

みで 行動が 定ま る なら タイ ム シェア リ ン グを 行っ て 、

移 す る こ と で あ り 、 動作列 A = (a1 a2 · · · an ) で 表す こ とが で き る 。 一 般に S か ら G ま で の 状態遷移 ル ー トと そ の

A + M = (a1 , m1 , a2 , m2 , … al , ml , … an )た め の 動作列に は 複数の 代替案 Aj が あ り 、 こ の た め 目的

(4)と 表せ る 。 た だ し、 こ の 場合は 総ステップ 数が l+n ステッ

行動は 動作列の 集合 B = {A1 , A2 , · · · , Am } と なる 。

プ に 拡大して い る た め 、 効率は 必ず 下が っ て しま う 。 目的

行動を 変調して 通信メ ッセー ジを 載せ る こ と は 、 あ る

行動に 時間 的な変移 の 耐性が あ る と す る と 、目的に 適合した 目的行動集合 B の 中か ら 、 一 つ の 行動 Ai
を 選び 出す こ と で あ る 。 こ の た め 現状態か ら ゴー ル へ 到達

A + M = (m1 , m2 , … ml , a1 , a2 , … an ) = (M, A)

す る 動作列の 代替案 が 一 つ に 制限さ れ る 場合は 、 行動に 変(5)

調を 加え る こ と が で き ない こ と に なる 。 た だ し実用上はと 並び 変え る こ と が で き る 。 こ れ は メ ッセー ジ行動と 目

目的行動が 一 つ に 制限さ れ る こ と は ま れ で あ る 。 通信メ ッ的行動を 逐次的に 行う 意 味と なり 、 い わ ゆ る ジェスチャ ー

セー ジの 復調で は 、 観 測した 動作列の 推測値 (a01 a02 · · · a0n )に よ る メ ッセー ジ通信そ の も の で あ る 。

と B と の 照合処理を 行う こ と で メ ッセー ジと して の 行動

形式的に は 時間 で 混合す る こ と が 可能だ が 、 こ の と き

Aj を 抽出す る 。 こ の と き 行動 Ai の 番号 i が 入力ア ル フ ァ
ベ ットで あ り 、 抽出さ れ た 行動 Aj の 番号 j が 出力ア ル フ ァ
ベ ットで あ る 。
一 般に 動作の 遂行や 観 測に は ゆ ら ぎ が 伴う 。 入力 i が 与生成した 動作列が 適切に 遂行さ れ ゴー ル 状態へ 到達で きる 保証は なく 、 目的行動と なっ て い ない 場合が あ る 。 こ のた め 、 そ れ ぞ れ の 目的行動と メ ッセー ジの 相互依 存関 係の 度合に よ り 、 混合方法を 選択す る 必要が あ る 。 動作の 相

え ら れ て 出力 j を 観 測す る 確 率を pij と お く と 、 行動に よ互依 存関 係に つ い て は 、 １) パ ラ メ ー タ加算に よ る 状態遷る 通信を 行う と き そ の 通信路行列は

移 へ の 非線形効果： 増幅に よ る 行動失敗、 ２ ) 並行実行動
作の 相互干 渉： 同時に 実行す る こ と に よ る 歪み、 ３ ) 時間

T = [pij ](1)

ず れ に よ る 無効化： コン ビ ネー ショ ン 効果の 減衰、 など があ る 。

で 与え ら れ る 。

3.2

4

変調と 復調メ ッセー ジ発信側の エー ジェン トを S 、 受信側を R とサッカー に お け る 実装例

RoboCup サッカー シミ ュ レ ー ショ ン は 、 11 対 11 の 人工
エー ジェン トに よ る 試合を 行う 、 マ ル チエー ジェン ト協調の 標準問題で あ る 。
動作と して 、 Dash、 Turn、 Kick、 TurnNeck を 行う こ

し、 S は 、 時刻 T に お い て メ ッセー ジ M と 目的行動 Aを 持つ と す る 。 R は 、 時刻 T 以 降 S の 行動 A0 を 観 測
す る 。
目的行動 A と は 、 現在の S の 状態を 目的の 状態 G に 変と が で き る 。 エー ジェン トの 状態に は 、 (x, y, dx, dy, r)

更す る 動作列で あ る 。 A を 表す 動作列で は 多く の 場合に

位 置、 速度、 方角が あ る 。 ボ ー ル の 状態は (x, y, dx, dy)

動作の 組合せ は 複数存在し、 そ の す べ て を 毎度網羅す る

位 置と 速度が あ る 。 エー ジェン トと ボ ー ル の 状態は 動的で

こ と は 不可能で あ る 。 そ こ で 、 発信側が メ ッセー ジを 行動

あ り 、 現在の 速度に よ っ て 次ステップ の 位 置が 更新さ れ 、に 混合し通信を 行う と き 、 標準と なる 行動列 A を 随時変

ま た 速度は 摩擦に よ る 一 定の 減衰を 受け る 。 動作 Dash(n)

更しメ ッセー ジを 含 ん だ 行動列を 生成す る も の と す る 。

に よ り エー ジェン トの 速度は 加速度パ ラ メ ー タ n に 応じ

変調す なわ ち 動作列の 書き 換 え は つ ぎ の よ う に 行わ れて 増加す る 。 動作 Turn(n) に よ り エー ジェン トの 方角はる 。 メ ッセー ジを M = (m1 , m2 , … , ml ) と い う 一 連の 動

トル クパ ラ メ ー タ n に 応じ て 変化す る 。 エー ジェン ト近

作列で 表現す る と 、 目的行動と メ ッセー ジの 混合は 、傍に 存在す る ボ ー ル の 速度は 、 動作 Kick(n,d) に よ り 加速

A + M = (am1 , am2 , · · · , aml , · · · , an )度パ ラ メ ー タベ クトル n (d は 相対方向) に 応じ て 変化す(2)る 。 動作 TurnNeck(n) に よ り エー ジェン トの 視線方向はの よ う に 表さ れ る 。

トル クパ ラ メ ー タ n に 応じ て 変化す る 。

45

0.6
0.5

40m 60m
agent speed(t+1)

20m

Dash
Not Dash

A
B

0.4
0.3
0.2
0.1

C

0

D

Table 1: 動作の 加算可能性
D+D ○ パ ラ メ ー タ加算可能
D+T
× 同時実行不可能
D+K
×
D+N◎ 並行実行可能

○

1.5

2

2.5

3

渉が あ る 。 と く に Kick は 実行不可能なと き が あ る 。

4.2

K+K
K+N
N+N

1

Figure 2: Dashgle only in D○

0.5

difference of position

Figure 1: Range of agent visual cognition area. All in
A; Team, Distance and Angle in B other stochastic; Distance and Angle in C other stochastic; Distance and An-

T+T
T+K
T+N

0

復調と 解釈ダッシュ を 行っ た あ と の 、 速度と 位 置の 変移 を 図 2 に 示
す 。 意 図的に ダッシュ 行動を せ ず と も そ れ ま で の 慣 性で 運動が 続く た め 、 速度と 位 置の 変移 だ け の 観 測で は ダッシュを した か ど う か を 、 完 全に 弁別す る こ と は で き ない こ とが 分か る 。
い っ ぽ う ター ン 後の 角度変化の 頻度か ら 、 角度変化に×

よ っ て ター ン の 有無を 容易 に 判断で き る こ と が 分か る 。

◎

4.3

通信の 同期◎
行動は つ ね に 行う も の で あ り 一 方通信は そ の う ち の 一 部○

で あ る 。 こ の た め 通信の 開始と 終了を 知ら せ る 通信の 同期は 重要で あ る 。 RoboCup サッカー シミ ュ レ ー ショ ン で は観 測に は 図 1 に 示した 距離に よ る 歪みが あ る が 、 対象

視線の 方向か ら 読み取っ た ア イ コン タクトに よ っ て 同期 を物す なわ ち 発信者の 位 置と 方向は 読み取る こ と が で き る 。

と る こ と が で き る 。 こ れ は TurnNeck 動作に よ り 、 通信をた だ し、 そ の 値に は 確 率的なノ イ ズが 重積して い る 。

4.1

した い エー ジェン トの 方角に 視線を 向け る こ と で 実現する 。 受信側は 、 自身を 直視す る エー ジェン トが あ れ ば 、 しサッカー 行動の 変調

ば ら く 停止して ア イ コン タクトを 成立さ せ て 同期 を 取る 。

サッカー システム で 実施可能な 4 種類の 動作、 Dash, Turn,

Kick, TurnNeck を そ れ ぞ れ 、 D, T, K, N と 呼ぶ こ と に

5

実験

す る 。 こ こ で の メ ッセー ジは こ れ ら の 5 つ の 行動の 列として 、 た と え ば (D D T K D) の よ う に 表す こ と が で き

RoboCup サッカー シミ ュ レ ー ショ ン システム を も ち い てる 。 こ れ ら の 動作の 順序組合せ に よ る 特性は 次の と お り

実験を 行い B-MODEM 通信の 効果を 検証す る 。 メ ッセー

で あ る 。

ジの 変調方法と して 、 予め メ ッセー ジを 送る ジェスチャ ー

連接に は 次の 特性が あ る 。 二つ の 動作の 間 に 他の 動作法と 、 混合方式を 実装し、 比較 す る 。 効率の 計測は 伝達所(O) を 追加した と き の 状態遷移 と 比べ た と き の 効果で あ る 。

用時間 に も と づ い て 行う 。 比較 の た め 、 音声通信 (Say プ(D,D) 非線形 (増強効果)、 (D,T) 非線形 (打消効果)、

ロ トコル ) に よ る 伝達を 用い た 場合も 実施す る 。 ま た メ ッ(D,K) ボ ー ル と の 位 置変化に 応じ て 効力が 変化す る 非線
形効果が あ る (増強・ 打消両方)、 (D,N) 干 渉なし、 (T,*)
干 渉なし、 (K,*) 干 渉なし、 (N,*) 干 渉なし。

セー ジ行動の 系列を ２ 種類用意 して こ れ ら の 比較 も 行う 。

5.1

場面設定

以 上を ま と め る と 、 TurnNeck は つ ね に 他の 動作と 加法

実験に 用い た 環 境と して 図 3,4,5 に 示した 3 つ の シナリ オ

的に も 、 時間 連結で も 混合可能で あ る 。 加算的混合で は 、を 用意 した 。 同一 の スター ト状態か ら 一 つ を 選び コミ ュ ニDash, Turn, Kick は 相互干 渉が 強く 、 連接に お い て も 干

ケー ショ ン に よ り 行動の 同期 を は か る 。

46

P2

P2

a
dribleaPassdrible

P1

Pass

Pass

P1
b
P3

b
P3

Pass

Figure 3: Scenario 1

Figure 5: Scenario 3

Table 2: 目的行動を 混合した 伝達の 結果
変調 シナ 受信成功率 (%)
伝達
P2

drible

方式
Pass

a
Pass

1

P1
b
P3
Pass

2

Figure 4: Scenario 2

リ オ

P2

P3

成功率 (%)

1
2
3
1

58
52
68
100

32
81
22
100

22
50
20
100

2
3

100
100

100
100

100
100

2. そ れ 自体ノ イ ズ源と なる 無線機 器 を ロ ボ ットに 搭載
す る 必要が 無い 。

実験結果

5.2

3. 視覚 観 測に よ る 通信で は 視線方向の 指向性が 高く 、各条件ご と に 150 回の 試行を 行っ た 結果を 、 表 2 と 図 6 にメ ッセー ジと して の 行動を 観 測した 時点で 、 能動的

ま と め る 。

に 通信相手が 明ら か に なる 。

図 6 か ら 、 ジェスチャ ー 方式す なわ ち メ ッセー ジ伝送
を あ ら か じ め 終了して か ら 目的行動を 行う 場合に は 平均

一 方で 、 以 下の よ う な問題点が 明ら か に なっ た 。

21.8 ステップ を 必要す る こ と が 分か る 。 こ れ は 目的行動の みの 16.0 と 比較 して 1.36 倍の 時間 消費で あ る 。

1. 多対多の 環 境で は 、 無線で は 発信者、 受信者の 確 認の コストが 高く なる行動系列冒頭の ア イ コン タクトは 、 メ ッセー ジ伝送の主客 を 伝え る と と も に 、 メ ッセー ジの 開始の 同期 を 伝え る

2. 視覚 に よ り 観 測さ れ る 物理情報と メ ッセー ジと して発行した 動作と の ギャ ップ が あ り 、 推定が １００％ とは なら ない

働き が あ る 。 目的行動と メ ッセー ジに 共通部分 (D) が あ
る た め 、 こ の 同期 を 取る こ と で 解釈が よ り 容易 に なっ て
い る 。

3. 視覚 セン サの 負担が 大き い

い っ ぽ う メ ッセー ジ混合方式の 場合に は 、 メ ッセー ジの一 部を ア イ コン タクトお よ び 移 動と 重ね あ わ せ 、 平均ス

4. 指向性が 高い た め 、 視野外の エー ジェン トか ら の メ ッ
セー ジを 受け 取れ ない

テップ 数は 16.1 〜 17.5 に なり ジェスチャ ー 方式と 比較 して 大幅な短縮が で き て い る 。

5. 行動系列の 認識が 難しい 。

6

B-MODEM の 効果
7

本稿で 提案 した 手法は 、 物理的な運 動と 視覚 認識を 応用

ま と め と 今後の 課題

従来、 音声や 電波無線に よ っ て 担わ れ て い た 通信路を 、 行

した 通信を 実現して お り 、 以 下の よ う な利点が あ る 。

動に よ る 発信と 視覚 的な受信に 置き 換 え 、 混信の 無い コ
ミ ュ ニケー ショ ン を 実現す る B-MODEM を 提案 した 。

1. 混信に 対して 強い 耐性を 持っ て い る 。

47

Say

移

動 (16.0)

16.0

アイコンタクト
ジェスチャー
アイコンタクトあり(1.7) メッセージ送信 (4)移

動 (16.1)

21.8

アイコンタクト +移動
混合
メッセージ送信 +移動 (8)(2.2)
アイコンタクトあり(シナリオ 1)
アイコンタクト +移動(シナリオ 2) (1.9)

メッセージ送信 +移動 (8)移

動 (7.3)17.5

移動 (7.5)17.4

移動 (5.9)10

12

アイコンタクト +移動(シナリオ 3) (2.2)
0メッセージ送信 +移動 (8)
2

4

6

8

16.1
14

16

18

20

22 (step)

Figure 6: Mean time for execute a scenario
RoboCup サッカー シミ ュ レ ー ショ ン を も ち い た 実験を行い 、 ター ン と い う 認識性の 高い 行動を 、 通信の 主体と す
る こ と で 、 通信確 度を 高く す る こ と が で き る こ と を 明ら
か に し、 マ ル チエー ジェン ト環 境に お け る 提案 手法の 有
効性を 示した 。
行動を 通信路と みなす と き 、 行動が 慣 性の 法則など 物
理法則に した が っ て い る た め 、 実際に は 状態を 持つ 通信路と して 扱 う 必要が あ る 。 こ の と き の 、 通信路と して の 相
互情報量と 通信容量の 定式化や 、 よ り 使い 勝手の 良い 変調方式を 検討す る こ と が 、 今後の 課題で あ る 。

参考文献[Pet99]Peter, S., V. Manuela, and P. Riley: RoboCup98: Robot Soccer World Cup II, Vol. 1604 of
Lecture Notes in Artificial Intelligence, chapter
Champion Teams: The CMUnited-98 Champion Simulator Team, pp. 61–76, Springer,
1999.

[岡 98]岡, 武田, 西田： 人の 集団と ロ ボ ットと の ノ ン バ ー
バ ル コミ ュ ニケー ショ ン の 実現法の 提案 , 第 16回日本ロ ボ ット学会学術講演 会予稿集, pp. 397–

398, 1998.
[黒川 94] 黒川： ヒ ュ ー マ ン コミ ュ ニケー ショ ン 工学シリ ー
ズ ノ ン バ ー バ ル イ ン ター フ ェー ス, オー ム 社,

1994.
[山中 03] 山中, 岡本, 中西, 石田： 非言語的合図に 基 づ いて 仮想都市を 案 内す る 対話エー ジェン ト, 情報処理学研究 報告 グル ー プ ウ ェア と ネットワ ー ク
サー ビ ス, Vol. 47, No. 16, pp. 89–94, 2003.

[西田 03] 西田： 人間 と ロ ボ ットの 意 思疎通, 情報処理,
Vol. 44, No. 12, 2003.

48

c 2005

Special Interest Group on AI Challenges
Japanese Society for Artificial Intelligence
社団法人 人工知能学会 AI チャレンジ研究会〒 162 東京都新宿区津久戸町 4-7 OS ビル 402 号室 03-5261-3401 Fax: 03-5261-3402(本研究会についてのお問い合わせは下記にお願いします.)AI チャレンジ研究会
主査
奥乃 博
京都大学大学院 情報学研究科
知能情報学専攻 音声メディア分野〒 606-8501 京都市左京区吉田本町
Tel: 075-753-5376
Fax: 075-753-5977
okuno@nue.org

Executive Committee
Chair
Hiroshi G. Okuno
Dept. of Intelligence Science andTechnology, Graduate School ofInformatics, Kyoto University
Yoshida-honmachi Sakyo-ku,
Kyoto, 606-8501, JAPAN

担当幹事
浅田 稔
大阪大学大学院 工学研究科
知能・機能創成工学専攻 創発ロボット工学講座〒 565-0871 大阪府吹田市山田丘 2-1
Tel: 06-6879-7349
Fax: 06-6879-7348
asada@ams.eng.osaka-u.ac.jp

Secretary in Charge
Minoru Asada
Dept. of Adaptive Machine Systems
Graduate School of Engineering
Osaka University
2-1 Yamada-oka, Suita,
Osaka 565-0871, JAPAN

担当幹事
光永 法明
株式会社国際電気通信基礎技術研究所
知能ロボティクス研究所〒 619-0288 京都府「けいはんな学研都市」
光台 2-2-2
Tel: 0774-95-1401
Fax: 0774-95-1408
mitunaga@atr.jp

Secretary in Charge
Noriaki Mitsunaga
Dept. of Intelligent Robotics andCommunication Laboratories
Advanced Telecommunications
Research Institute International
2-2-2 Hikaridai, Keihanna Science
City, Kyoto 619-0288, JAPANSIG-AI-Challenges web page; http://winnie.kuis.kyoto-u.ac.jp/SIG-Challenge/