As technologies for electrical, biological, and chemical devices progress, new notions of computation and computing devices are emerging, for example, computation by swarms of robots, autonomy in mobile agents, dynamics in populations, self-assembly like DNA tiling, and chemical reaction circuits. These fields share the concept of self-organization of swarm of robotic entities in common.
The goal of the workshop on WSSR 2018 is to gather researchers and students working in distributed computing, robotics, optmization, biological systems, chemical reaction networks, and any related fields, and enhance the connection between these fields. The workshop aims at sharing new advances and work in progress, and discussing future directions to foster novel collaborations.
This year, WSSR is held as a joint workshop with the JST SICORP project, "Realization of Sustainable Autonomous Self-Organizing Systems by Low-Functional Robots in Environmental Disaster Recovery."
Program
Session 1. Toward Autonomous Self-Organizing Systems for Mobile Robots
(9:30-11:00) Chair: Yoshiaki Katayama
Introduction: JST SICORP project
"Realization of Sustainable Autonomous Self-Organizing Systems by Low-Functional Robots in Environmental Disaster Recovery"
Shlomi Dolev:
Mobile Robots Communicating, Computing and Acting
Fukuhito Ooshita:
Computational Power of Myopic Robots on Graphs
Koichi Wada:
Rendezvous on asynchronous mobile robots with lights
-Relationship between power of lights and synchrony-
Coffee break (11:00-11:15)
Session 2. Optimization (11:15-12:45) Chair: Yukiko Yamauchi
Akitoshi Kawamura:
Optimization in multi-agent patrolling on graphs
Shantanu Das:
Explorations with energy-constrained mobile robots
Leszek A. Gasieniec:
Patrolling Problem and Relatives
Lunch break (12:45-14:15)
Session 3. Mobile robots (14:15-15:35) Chair: Paola Flocchini
Giovanni Viglietta:
TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility
Sébastien Tixeuil:
Mitigating faults and attacks in mobile robotic systems
Doan Thi Thu Ha:
Model Checking of Mobile Robot Algorithms*
Coffee break (15:35-16:00)
Session 4. Programmable Matter (16:00-17:30) Chair: Giovanni Viglietta
Joshua Daymude:
Self-Organizing Particle Systems: an Algorithmic Approach to Programmable Matter
Michail Theofilatos:
Network Constructors and the Crystal Structure Prediction Problem*
Yonghwan Kim:
An Autonomous Distributed System Consisting of Pair-Robots: Model and Basic Algorithms*
Yuichi Sudo:
An Introduction to Leader Election in the Population Protocol Model*
Invited Speakers
Shlomi Dolev (Ben-Gurion University of the Negev, Israel)
Mobile Robots Communicating, Computing and Acting
Mobile robots that collaborate on a mission need to communicate and coordinate actions.
Distributed algorithms used by a swarm of robots will be overviewed, including:
--The virtual infrastructure and the virtual node,
--Explicit and implicit communication, the sound of silence, movements for encoding bit transmission, the use of random walk
--Empire of colonies
--Direction election in flocking swarms
--Nanorobots for cancer treatment
Fukuhito Ooshita (Nara Institute of Science and Technology, Japan)
Computational Power of Myopic Robots on Graphs
The Look-Compute-Move (LCM) model is commonly used as a fundamental model
of weak autonomous mobile robots. Nevertheless, most works assume that
each robot observes all other robots, and this powerful ability somewhat
contradicts the principle of weak robots. For this reason, recent studies
consider the more realistic case of myopic robots. A myopic robot has
limited visibility, i.e., it can see robots only within a certain fixed
distance. In this talk, I will present several results on computational
power of myopic robots on graphs.
Koichi Wada (Hosei University, Japan)
Rendezvous on asynchronous mobile robots with lights
-Relationship between power of lights and synchrony-
In recent years, cooperation of a large number of autonomous mobile robots has received much attention. We consider algorithmic issues of autonomous mobile robots and its computational power on a theoretical model. In the model, each robot is modeled as a point in a plane and its capability is quite weak. Robots are usually oblivious, anonymous and uniform and each robot implicitly communicates with other robots by observing the environment including the positions of other robots. In the basic common model, most tasks cannot be solved without some additional assumptions.
In this talk, we consider visible lights as an additional assumption and reveal the power of lights for autonomous mobile robots in asynchronous settings. In particular, we show some relationship between lights and other assumptions such as synchrony and restriction of robots moving and reveal boundary between solvability and insolvability for rendezvous in which 2 robots must meet in finite time at a point that is not predefined.
Akitoshi Kawamura (Kyushu University, Japan)
Optimization in multi-agent patrolling on graphs
In patrolling problems, several mobile agents move around in a given
region and try to cooperate so that every point in the region is
(perpetually) visited sufficiently often. Problems of this kind are
studied with various motivations and in various forms: the agents may
have the same or different speeds; the terrain may be a line, a cycle,
or more general graphs; the points to be visited may be the whole or a
(finite) part of the terrain. Finding an optimal patrolling strategy is
not straightforward, even in the simplest settings. I will introduce
recent results and open questions about properties of and algorithms for
optimal patrolling and related scheduling problems. This talk is partly
based on joint work with Hideaki Noshiro and Makoto Soejima.
Shantanu Das (Aix-Marseille University, France)
Explorations with energy-constrained mobile robots
We consider a team of mobile robots moving on graph where each robot has a constraint on its energy consumption which limits the number of edges it can traverse. Under this constraint we look at the problem of graph exploration. Since any single robot may not completely explore the graph, the robots need to collaborate so that each node is visited by some robot. We consider three different optimization criteria: the size of the team, the energy budget per robot, and finally the number of nodes visited. We present efficient algorithms and prove lower bounds on these different measures of optimization. We also show a separation result between exploration with return and exploration without return.
Leszek A Gasieniec (University of Liverpool, UK)
Patrolling Problem and Relatives
We consider computing environment represented as geometric space or
a graph populated by simple mobile entities, very often referred to
as robots (or agents). The robots can move freely in the inhabited
environment or they mobility can be restricted by their intrinsic
properties, direction or temporal availability of edges, obstacles,
and others. Robots can move with different speeds and operate on
various levels of interaction with other robots and the environment.
In the patrolling problem one or more robots are asked to visit and
monitor perpetually selected parts or the whole environment.
The main goal is to minimise the time between any two successive
visits at each point that needs to be monitored. We present several
variants of the patrolling problem including the main results and
open problems.
Giovanni Viglietta (Japan Advanced Institute of Science and Technology, Japan)
TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility
In this talk we investigate the computational power of a set of punctiform, memoryless, asynchronous and non-rigid mobile robots with limited visibility continuously moving in the Euclidean space R^m. We show that despite their strong limitations, it is possible to arrange 3m+3k of these weak entities in R^m to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number.
Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation with limited visibility. Incidentally, these investigations imply that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.
Sébastien Tixeuil (Sorbonne Université, France)
Mitigating faults and attacks in mobile robotic systems
Most of the literature that considers mobile robotic entities that operate in the look-compute move model expects perfect behavior from all participants. However, as actual hardware is subject to faults and attacks, countermeasures should be deployed is theoretical algorithms are to be deployed in practise.
This talk will survey existing approaches to handle crash failures, Byzantine failures, and transient failures in the context of robot network algorithms, and highlight open research directions is this domain.
Doan Thi Thu Ha (Japan Advanced Institute of Science and Technology, Japan)
Model Checking of Mobile Robot Algorithms
Autonomous mobile robots denote entities that self-organize and cooperate in order to achieve a global goal. We come up with formal specification and model checking based on rewriting logic for mobile robot algorithms. We have conducted a case study in which we specify a mobile robot exploration algorithm on ring and model check that the system enjoys some desired properties. Furthermore, we have proposed a formal model for mobile robot algorithms on an anonymous ring shape network under multiplicity and asynchrony assumptions. Maude LTL model checker is used to model check an algorithm for robot gathering problem on ring enjoys some desired properties. We refute by model checking that the algorithm enjoys the desired properties. We detect the sources of some unforeseen design errors. Mobile robot algorithms have many special characteristics, among which are the ring topology of networks and the anonymity of robots. These characteristics make us take into account non-trivial case analysis and thus make their specifications very complicated when specifying them in existing specification languages, such as Maude and DVE. We, therefore, develop a specification environment in which the systems can be concisely and naturally specified. The environment is built on top of Maude and meta-programming makes it possible to do so.
Joshua Daymude (Arizona State University, USA)
Self-Organizing Particle Systems: an Algorithmic Approach to Programmable Matter
In order for programmable matter to live up to the dream of being an all-purpose "bucket of stuff" deployable for any task at any scale, we need a rich toolbox of algorithmic primitives upon which we can program more complex behaviors. Although the eventual vision is to control a whole mass of programmable matter as a single entity, our toolbox of primitives should be defined at the level of individual "atoms" of programmable matter to enable arbitrary scalability. Thus, we must take a distributed computing approach to defining micro-scale behaviors that collectively induce macro-scale phenomena. Towards this goal, self-organizing particle systems abstractly envision programmable matter as an ensemble of tiny computational units called "particles". These particles are assumed to be very simple: they have very limited memory, no sense of orientation or direction, and only local movement and communication capabilities. Our formal model for these particle systems is the amoebot model. In this talk, I will review the amoebot model before describing the behaviors and primitives developed so far including leader election, shape formation, object coating/enclosure, compression, and separation. Time permitting, I will conclude with a preview of current work-in-progress and open problems.
Michail Theofilatos (University of Liverpool, UK)
(Co-authored by Othon Michail and Paul Spirakis)
Network Constructors and the Crystal Structure Prediction Problem
Several theoretical models for programmable matter that operate in a dynamic environment have been proposed recently. In the models that we present, the agents are passively mobile and their interactions are scheduled by a fair (or uniform random) scheduler, in the spirit of Population Protocols. We first discuss the basic Network Constructors model, in which all devices are finite automata, begin from the same initial state, execute the same protocol, and can only interact in pairs. The agents are allowed to form connections between them (on/off), while the protocol defines the way that their states and connections are updated after each pairwise interaction. The goal of such protocols is to eventually construct a desired stable network, induced by the edges that are on. A more applied version of this model, enriched with geometric constraints, has also been examined. We also discuss the Mediated Population Protocol model, which allows the edges of the interaction graph to have more than two states. We present some interesting open problems related to such protocols, for example models that take other real physical considerations into account, e.g., weight, strength of bonds and so on. Finally, we explore connections of these models with the Crystal Structure Prediction (CSP) problem. CSP can be considered as the problem of finding the most stable arrangement of atoms, by minimizing the total energy. The total energy is calculated by summing up the pairwise energies of all atoms, while the pairwise energies depend on the types of the interacting atoms and the distance between them. It is believed that these models can be used as crystal formation models, where the edge states can represent energies or distances between the atoms, and the goal is again to construct a desired stable network.
Yonghwan Kim (Nagoya Institute of Technology, Japan)
An Autonomous Distributed System Consisting of Pair-Robots: Model and Basic Algorithms
Programmable matter consisting of many self-organized computational entities which are autonomous and cooperative each other to achieve the goal has been widely studied in the various fields, e.g. robotics or mobile agents, theoretically and practically.
In the computer science field, programmable matter can be modeled as the system consisting of simple robots which have very limited computational resources, and many theoretical researches are studied in this model, especially the solvability of problems depends on the considered model or the design of the algorithms.
We propose a new programmable matter named Pair-Robots Model which consists of distributed autonomous robots where every (predetermined) two robots operate as one pair. These two robots share some information but cannot be separated over limited distance. Pair-Robots repeat separating and gathering: these operations are similar to expanding and contracting respectively which are introduced in existing research, named Amoebot, however, each robot has no memory, cannot communicate each other, and has limited visibility (can see only neighboring nodes) in our model.
In our model, we consider a triangular grid plane and we assume that each grid can be occupied by at most two robots. Moreover, we introduce some simple algorithms in our proposed model.
Yuichi Sudo (Osaka University, Japan)
An Introduction to Leader Election in the Population Protocol Model
The population protocol model, introduced by Angluin et al. in 2004, is a theoretical
model for wireless and mobile sensor networks. A network consists of a large number of
finite-state automata, called agents. Agents often make interactions (communication) in
pairs, by which they update theirs states. They cannot distinguish their neighbors with
the same states. This simple model has attracted a lot of attention and has been
studied by
many researchers. In this short talk, I will give a brief introduction to studies on
leader election, one of the most fundamental problems, in the population protocol
model. The state-of-the-art leader election protocols with and without fault tolerance
in the literature are introduced.