During the past decade, systems of autonomous mobile robots have been gathering attention as distributed systems that are expected effective for activity in deep sea or outer space, where robots have to act autonomously. The system consisting of a large number of simple robots is expected to be effective to work with fault-tolerance. Hence minimal setting for robots which cope with this kind of difficult environment is worth studying from the practical and also theoretical points of view. In particular, increasing more research has been focusing on the coordination and self-organization of autonomous mobile robot systems in involving multiple simple robots working together, rather than a single high-complex one. This view is motivated by a variety of reasons, including reduced manufacturing costs, increased fault resilience, improved overall maneuverability or simply better polyvalence of the system. This tutorial focuses on the theoretical aspects of systems of autonomous mobile robots. The talks in the tutorial include introduction of theoretical models of autonomous mobile robots originated by Profs. Ichiro Suzuki and Masafumi Yamashita (called SYm) and Prof. Giuseppe Prencipe (called CORDA) and their variant models dealing with some practical issues such as fault tolerance and inaccuracy of robots sensors and recent results obtained in the models and algorithms for solving geometric problems and/or graph theoretic problems. This tutorial also aims to make the theoretical model of autonomous mobile robots more rigid in the sense that researchers in this field have consensus about the model.
Koichi Wada (Nagoya Institute of Technology, Japan)
Xavier Defago(JAIST Japan)
As robotic systems are getting cheaper and easier to produce in mass, more and more applications envision future systems in which groups of simple robots are expected to self-organize and cooperate to perform complex tasks.
While earlier developments have mostly emphasized an empiric approach, observing the emergence of collective behavior under given circumstances, there has been a call for a more formal approach based on rigorous problem definitions, formally stated algorithms, and detailed proofs of correctness.
The rigorous definition of a system model for cooperative mobile robots is a necessary foundation for a formal study of algorithms and their proofs. The first definition of such a model, proposed by Suzuki and Yamashita and called SYm, appeared for the first time in a journal publication a decade ago. A weaker model, called CORDA, with full asynchrony between robots has been later defined by Prencipe et al.
In this tutorial, we will introduce the two main system models, namely SYm and CORDA, as well as many of the variants that have been considered in the literature. We will discuss some of the tradeoffs and illustrate the difference between the two main system models through the example of the gathering problem. The attendant will have a good grasp of the main issues and the terminology used in this area of research.
Yoshiaki Katayama(NIT Japan)
The autonomous mobile robots system is one of the distributed systems such that communications between robots are done by observations of all the other robots' locations and state transitions are done by changing their locations on two-dimensional space or graphs etc. Recent years, this system has attracted a lot of researchers in distributed systems and some kind of fundamental problems like pattern forming, flocking, or graph exploring etc. have been concerned. One of the main objectives in this research area is to reveal relationship between the system models and its solvability of the problems. The system model consists of wide variety of abilities such as observation, mobility, multiplicity, synchronicity, memory, and so on. Differences of these factors sensitively influence the problem solvability; it is very similar to conventional distributed systems. In this talk, the relationship between faulty robot models and their solvability of the rendezvous problem is focused on. The faulty robot model means that, for example, an observation mechanism equipped with each robot returns inaccurate coordinates of other robots' locations. The rendezvous problem is one of the agreement problem and to make all robots meet or gradually converge at a single point which is not predefined. To investigate the relationship between faulty models and the solvability of the rendezvous problem is fundamental and interesting for theoretical point of view on the autonomous mobile robot system. Especially, I will pick up inaccurate compasses (observation mechanism) and Byzantine fault robot model as faulty models, and present the relationships between them and solvability of the rendezvous problem through introducing recent works.
Franck Petit(INRIA/Universite de Lyon France)
In a given environment, the ability for the swarm of robots to succeed in the accomplishment of the assigned task greatly depends on global properties assigned to the swarm, and individual capabilities each robot has. Examples of such global properties are the ability to distinguish among themselves at least one (or, more) robots (leader), to agree on a common global direction (sense of direction), or to agree on a common handedness (chirality). The individual capacities of each robot are its moving capabilities and its sensory organs.
To deal with cost, flexibility, resilience to dysfunction, and autonomy, many problems arise for handling the distributed coordination of swarms of robots in a deterministic manner. This issue is motivated by the minimal level of ability that the robots are required to have in the accomplishment of basic cooperative tasks. In other words, the feasibility of some given tasks is addressed assuming swarm of autonomous robots either devoid or not of capabilities like (observable) identifiers, direct means of communication, means of storing previous observations, sense of direction, chirality, etc.
Leader election and arbitrary pattern formation are fundamental tasks for a set of autonomous mobile robots. The former consists in moving the system from an initial configuration were all entities are in the same state into a final configuration were all entities are in the same state, except one, the leader. The latter consists in the design of protocols allowing autonomous mobile robots to form any (arbitrary) geometric pattern. The solvability of both these tasks turns out to be necessary in order to achieve more complex tasks.
During this tutorial, we address both problems. We first consider the deterministic solvability of the pattern formation problem assuming swarms of anonymous robots. Next, under the same assumptions, we provide a complete characterization (necessary and sufficient conditions) on the robots positions to deterministically elect a leader. Finally, we show that Leader Election and Pattern Formation are two equivalent problems in the precise sense that, the former is solvable if and only if the latter problem is solvable.
Yuichi Asahiro(Kyushu Sangyo University Japan)
We propose a decentralized motion planning algorithm for a group of autonomous robots in an obstacle-free workspace. The task of the robots is to transport a polygonal object (which may be an imaginary one in marching), where each robot holds the object at the corner. Given the current and the goal positions of the robots, each robot independently computes a next position in a memoryless manner that the computation is fully independent of the past history of their motions. Then each robot tries to move the new position for a unit of time, and repeats this cycle until it reaches the goal position. The objective of our research is to develop a motion planning algorithm which simultaneously guarantees self-stability and smoothness of motion; each robot finally reaches its goal position under an assumption that finite number of transient and sensor errors occur, and the formation of the robots is maintained so as to be reasonably similar to that of the goal position. In this talk, we demonstrate the proposed algorithm by simulations.
Arquimedes Canedo (IBM Research - Tokyo)
In a world dominated by register (i.e. CISC, RISC) and stack machines (i.e. Java), don't be surprised if you have never heard of Queue machines. Nevertheless, queue-based processors offer high instruction-level parallelism, a compact instruction set, simple hardware, and low power consumption. Queue machines are the “parallel siblings” of stack machines. The register file is organized as a first-in first-out (FIFO) queue that decouples reads and writes in benefit of program parallelism and hardware simplicity. Instructions read their source operands from the head of the queue and write their destination operand through the tail of the queue. Given this configuration, novel compilation techniques were needed and we implemented them in the Queue Compiler Infrastructure. During this tutorial, I will guide you from the basic principles of queue computing to the advanced compilation techniques. We will present experimental data that highlights the good characteristics of queue machines as a competitive computer architecture for general purpose computing, embedded systems, streaming applications, and software virtual machines. This tutorial aims at informing the community about a viable alternative for future computer systems based on queue-machines.
Shinichi Yamagiwa (Kochi University of Technology)
Graphics Processing Units (GPUs) has been applied to graphics applications to implement realistic perspectives of virtual scenes especially in entertainment market. Due to the demands from the market for creating super high definition scenes with high frame rate that simulates physics phenomenon naturally in visualization applications, the last decade promoted drastic performance improvement of GPUs. Obtaining the growth rate more than the Moore’s law, in the very near future, performance of GPUs will reach 10TFLOPS due to concurrent execution of mutithreads on its multicore/manycore architecture. Researchers from the high performance computing field focus on the incredible high performance, and recently they are going to apply the GPU horse power to general purpose applications. This field is called the General Purpose computing on GPUs (GPGPU). When we program any application in a GPGPU environment, it is hard to extract the potential performance of GPUs because originally it is designed to process graphics applications. Therefore, to grab the best performance, the programmer needs to master the hardware architectural and the processing conceptual aspects of GPUs. This tutorial will begin to focus on such aspects of GPGPU environment, and will introduce the recent methodologies of advanced programming at GPGPU environment. The tutorial will also discuss performance impacts presenting recent research results from Caravela Projects led by the speaker.