Distributed Autonomous Robotic Systems 8

Distributed Autonomous Robotic Systems 8

Hajime Asama, Haruhisa Kurokawa,

Jun Ota, Kosuke Sekiyama (Eds.)

Distributed Autonomous

Robotic Systems 8

ABC

Hajime Asama

RACE (Research into Artifacts,

Center for Engineering)

The University of Tokyo

Kashiwanoha 5-1-5

Kashiwa-shi, Chiba 277-8568

Japan

E-mail: [email protected]

Haruhisa Kurokawa

Distributed System Design

Research Group

National Institute of Advanced

Industrial Science and Technology

(AIST)

1-2-1 Namiki, Tsukuba

Ibaraki 305-8564

Japan

E-mail: [email protected]

Jun Ota

The University of Tokyo

Graduate School of Engineering

7-3-1 Hongo, Bunkyo-Ku

Tokyo 113-8656

Japan

E-mail: [email protected]

Kosuke Sekiyama

Department of Micro-Nano Systems

Engineering

Nagoya University

Nagoya 464-8603

Japan

E-mail: [email protected]

ISBN 978-3-642-00643-2 e-ISBN 978-3-642-00644-9

DOI 10.1007/978-3-642-00644-9

Library of Congress Control Number: 2009922104

c 2009 Springer-Verlag Berlin Heidelberg

This work is subject to copyright. All rights are reserved, whether the whole or part of the mate￾rial is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,

broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Dupli￾cation of this publication or parts thereof is permitted only under the provisions of the German

Copyright Law of September 9, 1965, in its current version, and permission for use must always

be obtained from Springer. Violations are liable to prosecution under the German Copyright Law.

The use of general descriptive names, registered names, trademarks, etc. in this publication does

not imply, even in the absence of a specific statement, that such names are exempt from the relevant

protective laws and regulations and therefore free for general use.

Typeset and Cover Design: Scientific Publishing Services Pvt. Ltd., Chennai, India.

Printed in acid-free paper

987654321

springer.com

Preface

The International Symposia on Distributed Autonomous Robotic Systems (DARS)

started at Riken, Japan in 1992. Since then, the DARS symposia have been held

every two years: in 1994 and 1996 in Japan (Riken, Wako), in 1998 in Germany

(Karlsruhe), in 2000 in the USA (Knoxville, TN), in 2002 in Japan (Fukuoka), in

2004 in France (Toulouse), and in 2006 in the USA (Minneapolis, MN).

The 9th DARS symposium, which was held during November 17–19 in Tsu￾kuba, Japan, hosted 84 participants from 13 countries. The 48 papers presented

there were selected through rigorous peer review with a 50% acceptance ratio.

Along with three invited talks, they addressed the spreading research fields of

DARS, which are classifiable along two streams: theoretical and standard studies

of DARS, and interdisciplinary studies using DARS concepts. The former stream

includes multi-robot cooperation (task assignment methodology among multiple

robots, multi-robot localization, etc.), swarm intelligence, and modular robots. The

latter includes distributed sensing, mobiligence, ambient intelligence, and multi￾agent systems interaction with human beings.

This book not only offers readers the latest research results related to DARS

from theoretical studies to application-oriented ones; it also describes the present

trends of this field. With the diversity and depth revealed herein, we expect that

DARS technologies will flourish soon.

We thank everyone involved with the organization of DARS 2008. The mem￾bers of the program committee organized sessions, reviewed papers, and contrib￾uted to enhancement of the quality of the program. We thank Prof. Alan Winfield

(University of the West of England), Prof. Katsuhiro Nishinari (The University of

Tokyo), and Prof. Gregory S. Chirikjian (The Johns Hopkins University) for their

plenary and keynote talks. We truly appreciate co-sponsorship by the Mobiligence

program of MEXT, and technical co-sponsorship by other organizations (IEEE

RAS, SICE, RSJ, and JSME), and grants from the Inoue Foundation for Science

and from the Suzuki Foundation. Kind assistance extended by the Tsukuba Con￾vention Bureau was indispensable for us.

We would like also to thank Dr. Kuniaki Kawabata, Dr. Masao Sugi, and Dr.

Kohji Tomita for their invaluable help with local arrangements, conference web￾site, and document edition.

January 2009 Hajime Asama

Haruhisa Kurokawa

Jun Ota

Kosuke Sekiyama

Contents

Part I: Distributed Sensing

Multi-Robot Uniform Frequency Coverage of Significant

Locations in the Environment ............................... 3

Marco Baglietto, Giorgio Cannata, Francesco Capezio,

Antonio Sgorbissa

Measuring the Accuracy of Distributed Algorithms

on Multi-robot Systems with Dynamic Network

Topologies ................................................... 15

James McLurkin

Network Topology Reconfiguration Based on Risk

Management ................................................. 27

Kosuke Sekiyama, Hirohisa Araki

Energy-Efficient Distributed Target Tracking Using

Wireless Relay Robots ....................................... 39

Chia Ching Ooi, Christian Schindelhauer

Cooperative Object Tracking with Mobile Robotic Sensor

Network ..................................................... 51

Junji Takahashi, Kosuke Sekiyama, Toshio Fukuda

Deployment and Management of Wireless Sensor Network

Using Mobile Robots for Gathering Environmental

Information.................................................. 63

Tsuyoshi Suzuki, Ryuji Sugizaki, Kuniaki Kawabata, Yasushi Hada,

Yoshito Tobe

VIII Contents

Global Pose Estimation of Multiple Cameras with Particle

Filters ....................................................... 73

Ryuichi Ueda, Stefanos Nikolaidis, Akinobu Hayashi, Tamio Arai

Part II: Mobiligence

Motion Control of Dense Robot Colony Using

Thermodynamics ............................................ 85

Antonio D’Angelo, Tetsuro Funato, Enrico Pagello

Modeling of Self-organized Competition Hierarchy with

Body Weight Development in Larval Cricket, Gryllus

bimaculatus ................................................. 97

Shiro Yano, Yusuke Ikemoto, Hitoshi Aonuma, Takashi Nagao,

Hajime Asama

Intelligent Mobility Playing the Role of Impulse

Absorption .................................................. 109

Jae Heon Chung, Byung-Ju Yi, Chang Soo Han

Part III: Ambient Intelligence

Cognitive Ontology: A Concept Structure for Dynamic

Event Interpretation and Description from Visual Scene ..... 123

Yuki Wakuda, Kosuke Sekiyama, Toshio Fukuda

Subjective Timing Control in Synchronized Motion of

Humans: A Basic Study for Human-Robot Interaction ....... 135

Mitsuharu Nojima, Hiroaki Shimo, Yoshihiro Miyake

Robot Software Framework Using Object and Aspect

Oriented Programming Paradigm ............................ 149

Fumio Ozaki, Jun’ichiro Ooga, Kunikatsu Takase

Distributed Context Assessment for Robots in Intelligent

Environments ................................................ 161

Fulvio Mastrogiovanni, Antonio Sgorbissa, Renato Zaccaria

Part IV: Swarm Intelligence

Jamology: Physics of Self-driven Particles and Toward

Solution of All Jams ......................................... 175

Katsuhiro Nishinari

Contents IX

Towards an Engineering Science of Robot Foraging .......... 185

Alan F.T. Winfield

A Modular Robot Driven by Protoplasmic Streaming ....... 193

Takuya Umedachi, Taichi Kitamura, Koichi Takeda,

Toshiyuki Nakagaki, Ryo Kobayashi, Akio Ishiguro

A Distributed Scalable Approach to Formation Control in

Multi-robot Systems ......................................... 203

I˜naki Navarro, Jim Pugh, Alcherio Martinoli, Fernando Mat´ıa

Guiding a Robot Flock via Informed Robots ................. 215

Hande C¸ elikkanat, Ali Emre Turgut, Erol S¸ahin

Theoretical and Empirical Study of Pedestrian Outflow

through an Exit ............................................. 227

Daichi Yanagisawa, Ayako Kimura, Ryosuke Nishi,

Akiyasu Tomoeda, Katsuhiro Nishinari

Understanding the Potential Impact of Multiple Robots in

Odor Source Localization .................................... 239

Thomas Lochmatter, Alcherio Martinoli

Analyzing Multi-agent Activity Logs Using Process Mining

Techniques .................................................. 251

Anne Rozinat, Stefan Zickler, Manuela Veloso,

Wil M.P. van der Aalst, Colin McMillen

Altruistic Relationships for Optimizing Task Fulfillment in

Robot Communities ......................................... 261

Christopher M. Clark, Ryan Morton, George A. Bekey

Part V: Multi-robot Cooperation

Robotic Self-replication, Self-diagnosis, and Self-repair:

Probabilistic Considerations ................................. 273

Gregory S. Chirikjian

Analysis of Multi-robot Play Effectiveness and of

Distributed Incidental Play Recognition ..................... 283

Colin McMillen, Manuela Veloso

Sparsing of Information Matrix for Practical Application

of SLAM for Autonomous Robots ........................... 295

Haiwei Dong, Zhiwei Luo

X Contents

Trajectory Generation for Multiple Robots of a Car

Transportation System ...................................... 305

Mitsuru Endo, Kenji Hirose, Yusuke Sugahara, Yasuhisa Hirata,

Kazuhiro Kosuge, Takashi Kanbayashi, Mitsukazu Oomoto,

Koki Suzuki, Kazunori Murakami, Kenichi Nakamura

Distributed Control and Coordination of Cooperative

Mobile Manipulator Systems ................................ 315

Enrico Simetti, Alessio Turetta, Giuseppe Casalino

Rearrangement Task by Multiple Robots Using a

Territorial Approach......................................... 325

Norisuke Fujii, Reiko Inoue, Jun Ota

A Task Planner for an Autonomous Social Robot ............ 335

Samir Alili, Rachid Alami, Vincent Montreuil

A Stochastic Clustering Auction (SCA) for Centralized

and Distributed Task Allocation in Multi-agent Teams ....... 345

Kai Zhang, Emmanuel G. Collins Jr., Dongqing Shi, Xiuwen Liu,

Oscar Chuy Jr.

Corridors for Robot Team Navigation ....................... 355

Zack Butler, Carlos Bribiescas

Part VI: Practical Control of Modular Robots

Efficient Distributed Reinforcement Learning through

Agreement .................................................. 367

Paulina Varshavskaya, Leslie Pack Kaelbling, Daniela Rus

Morphology Independent Learning in Modular Robots ...... 379

David Johan Christensen, Mirko Bordignon, Ulrik Pagh Schultz,

Danish Shaikh, Kasper Stoy

Reconfigurable Modular Robots Adaptively Transforming

a Mechanical Structure (Numerical Expression of

Transformation Criteria of “CHOBIE II” and Motion

Experiments) ................................................ 393

Yosuke Suzuki, Norio Inou, Michihiko Koseki, Hitoshi Kimura

Toward Flexible and Scalable Self-reconfiguration of

M-TRAN .................................................... 405

Haruhisa Kurokawa, Kohji Tomita, Akiya Kamimura,

Satoshi Murata

Contents XI

Reconfigurable Teams: Cooperative Goal Seeking with

Self-Reconfigurable Robots .................................. 417

Zack Butler, Eric Fabricant

“Deformable Wheel”-A Self-recovering Modular Rolling

Track ........................................................ 429

Harris Chi Ho Chiu, Michael Rubenstein, Wei-Min Shen

Exploit Morphology to Simplify Docking of

Self-reconfigurable Robots ................................... 441

Kasper Stoy, David Johan Christensen, David Brandt,

Mirko Bordignon, Ulrik Pagh Schultz

Reconfigurable Modular Universal Unit (MUU) for Mobile

Robots ...................................................... 453

Shugen Ma, Changlong Ye, Bin Li, Yuechao Wang

Part VII: Multi-robot Systems

Design and Analysis for AGV Systems Using Competitive

Co-evolution ................................................. 465

Ryosuke Chiba, Tamio Arai, Jun Ota

Cooperative Control of Multi-robot Nonholonomic Systems

with Dynamics Uncertainties and Control Time-Delays ...... 477

Junjie Zhang, Suhada Jayasuriya

Guaranteed-Performance Multi-robot Routing under

Limited Communication Range .............................. 491

Alejandro R. Mosteo, Luis Montano, Michail G. Lagoudakis

Pipeless Batch Plant with Operating Robots for a

Multiproduct Production System ............................ 503

Satoshi Hoshino, Hiroya Seki, Yuji Naka

Control Methodology of Transfer Crane with Look-Ahead

Rule in Harbor Transportation System ...................... 513

Hisato Hino, Satoshi Hoshino, Tomoharu Fujisawa,

Shigehisa Maruyama, Jun Ota

A Novel Marsupial Robot Society: Towards Long-Term

Autonomy ................................................... 523

Marek Matusiak, Janne Paanaj¨arvi, Pekka Appelqvist,

Mikko Elomaa, Mika Vainio, Tomi Ylikorpi, Aarne Halme

XII Contents

Predicting the Movements of Robot Teams Using

Generative Models .......................................... 533

Simon Butler, Yiannis Demiris

Interactive Mobile Robotic Drinking Glasses ................ 543

Fran¸cois Rey, Michele Leidi, Francesco Mondada

Part VIII: Human-Robot Interaction

Adaptive Supervisory Control of a Communication Robot

That Approaches Visitors .................................... 555

Masahiro Shiomi, Takayuki Kanda, Kenta Nohara, Hiroshi Ishiguro,

Norihiro Hagita

Behavior Design of a Human-Interactive Robot through

Parallel Tasks Optimization.................................. 565

Yuichi Kobayashi, Masaki Onishi, Shigeyuki Hosoe, Zhiwei Luo

Tracking and Following People and Robots in Crowded

Environment by a Mobile Robot with SOKUIKI Sensor ..... 575

Akira Ohshima, Shin’ichi Yuta

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585

Part I

Distributed Sensing

Multi-Robot Uniform Frequency Coverage of

Significant Locations in the Environment

Marco Baglietto, Giorgio Cannata, Francesco Capezio, and Antonio Sgorbissa

Abstract. The article shows that the Random Walk and Edge Counting algorithms

allow to solve – under some constraints – the Multi-Robot Uniform Frequency Cov￾erage problem, i.e., the problem of repeatedly visiting a set of locations in the envi￾ronment with uniform frequency. Both algorithms have extremely low requirements

in terms of computational power and memory storage, and do not require inter-robot

communication. Their properties are described in details and formally demonstrated.

1 Introduction

This article considers a swarm of robots which are required to repeatedly visit a set

of specific locations, a problem which is particularly relevant for surveillance and

patrolling, continuous cleaning of crowded areas (e.g., malls, convention centers,

restaurants), serving food or beverages (e.g., in hospitals or in a banquet), etc. As

stated by a recent survey [20], the problem of Multi-Robot Uniform Frequency Cov￾erage has received only a limited attention in literature. Traditional approaches rely

on the idea of decomposing the space into subregions, and to consider each region

separately in order to reduce complexity [21][1]. More recent approaches assume

that robots are equipped with an ideal “sweeping tool”, and divide the area into a

grid: the minimum spanning tree over the grid is built, and robots move along the

Hamiltonian cycle that follows the tree around, therefore guaranteeing that each cell

in the grid is visited repeatedly at the same optimal frequency [18][19].

The work described in this article1 has the additional constraints of finding solu￾tions that are technologically plausible, with the purpose of designing robot swarms

able to operate in the real-world here and now, not in a future when technology will

Marco Baglietto, Giorgio Cannata, Francesco Capezio, and Antonio Sgorbissa

DIST – University of Genova, Via Opera Pia 13, 16145, Genova, Italy

e-mail: [email protected],[email protected],

[email protected], [email protected]

1 The research leading to these results has received funding from the European Communitys

Sixth Framework Programme under contract n 045255 - project ROBOSWARM.

4 M. Baglietto et al.

be – hopefully – available. Robots must be cheap, with low computational power

and memory storage, and able to function even when wireless communication is

not available or degraded, thus being unreliable for multi-robot coordination. To￾wards this end, one of the core technologies considered are passive RFID tags: these

are low-cost, short-range, energetically self-sustained transponders that can be dis￾tributed in the environment and can store a limited amount of information. The use

of RFIDs and other deployable sensor networks in robotics have been recently in￾vestigated, both to solve general robotic problems (i.e., navigation and localization

[13][15][12]), as well as for specific applications (e.g., cleaning [10][11], explo￾ration [8][9][2], or rescue applications in large scale disasters [16][14]). Both in the

case that RFIDs are “manually” distributed during a setup phase which precedes ex￾ecution, and in the case that robots themselves distribute RFIDs in the environment,

they have been proven to provide a significant aid in different kinds of robotic tasks.

In this work, it is assumed that RFIDs are distributed in the environment prior to

robot operation, and used to build a “navigation graph”: each RFID stores navigation

directions to neighboring RFIDs, thus allowing robots to safely execute paths from

and to different locations. As a consequence of the technological constraints, we are

interested in distributed, real-time search algorithms (either biologically inspired or

not [7][6][3][4][5][2]), able to deal with situations in which a global representation

of the environment, as well as global communication capabilities, are absent.

Sections 2 shows that Random Walk and Edge Counting belong to a class of

algorithms with common properties that allow, under some constraints, to solve the

patrolling problem, and gives formal proofs of statistical completeness. Section 3

compares Edge Counting with Node Count (to our knowledge, the simpler algorithm

for which formal proofs have been given [4]). Conclusions follow.

2 Multi-Robot Uniform Frequency Coverage

2.1 General Problem

The MRUFC problem is defined as follows. Given that:

• GN is a planar, non-oriented graph of arbitrary order, possibly containing cycles,

which represents the topology of the free space, referred to as the Navigation

Graph. As usual, the latter is better represented through an oriented graph GˆN,

derived from GN by doubling all its edges and assigning them opposite directions.

• S = {si} denotes the finite set of N vertices in GˆN. Each vertex si is associated

with a location in the workspace.

• Ai = {ai j} = 0 is the finite, nonempty set of (directed) edges that leave vertex si ∈

S. Each edge ai j is defined through a couple of indices (i, j), which respectively

identify the corresponding start and end vertices. |Ai| is the dimension of the set,

i.e., the number of edges departing from si.

• R = {ri} is a set of M robots. Robots are allowed to move in the workspace from

si to sj in GˆN only if ai j ∈ Ai, i.e., if the two vertices are adjacent.

Multi-Robot Uniform Frequency Coverage of Significant Locations 5

• Λ = [λ1,··· ,λN] is a vector which describes the average robot arrival rate to each

vertex si ∈ S, expressed as number of robots divided by time (∀i,λi ∈ ℜ).

The following objective must be achieved:

the M robots must guarantee continuous coverage of GˆN in such a way that

∀si, λi = ¯

λ, where ¯

λ is the same for all vertices.

This means that all vertices in GˆN are visited with the same frequency as time

passes. For a real-world implementation, it is assumed that robots are equipped with

proper algorithms for vertex-to-vertex navigation, as well as obstacle avoidance and

localization. In particular, it is assumed that every vertex is linked to an adjacent

vertex sj through ai j whenever it is possible to reach sj starting from si through a

“simple motion”, e.g., moving on a straight line2. The following additional imple￾mentation constraints are taken into account, which restrict the spectrum of possible

solutions to the domain of the distributed and real-time search algorithms:

• The algorithm which solves MRUFC must be executable in parallel on very sim￾ple robots with limited memory and computational power. This is achieved by

assuming that robots do not know GˆN, neither in advance nor during navigation:

GˆN is neither stored in robots memory, nor in a central repository. Instead, all

the information concerning a generic vertex, as well as the edges departing from

it, is stored into a smart node opportunely located in the environment 3. To help

robots to physically navigate in the workspace, every smart node stores naviga￾tion directions to reach neighboring smart nodes.

• Robots and smart nodes have a very short communication range. Robots can

directly communicate with smart nodes, and can indirectly communicate with

other robots by writing to/reading from smart nodes. In no case, it is possible for

a robot to directly communicate with another robot, for a smart node to directly

communicate with another smart node, or for a robot to communicate with two

smart nodes at the same time.

In the following, starting from the experience acquired in previous work [17],

two real-time search algorithms are described that are able to solve MRUFC (under

restrictive conditions). Both algorithms, namely Random Walk and Edge Counting,

assume that the M robots execute in parallel a particular instance of Algorithm 1,

by properly implementing a strategy to choose the next vertex to be visited which

varies depending on the particular algorithm considered.

Algorithm 1 itself is straighforward. Line 1 chooses an arbitrary start vertex

sstart , that can be different for different robots. When in vertex sc, the operator

2 The notion of “simple motion” varies depending on the robot kinematics, localization

skills, etc.

3 Smart nodes can be implemented, for example, as active or passive RFID tags, or similar

devices with local communication capabilities and a very limited memory storage.