CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> Flocking is the ability of a group of robots to follow a leader or head whenever it moves in a plane (two dimensional Cartesian space). In this paper we propose and prove correct an architecture for a selforganizing and stabilizing flocking system. Contrary to the existing work on this topic our flocking architecture does not rely on the existence of a specific leader a priori known to every robot in the network. In our approach robots are uniform, start in an arbitrary configuration and the head of the group is elected via algorithmic tools. ::: ::: Our contribution is threefold. First, we propose novel probabilistic solutions for leader election in asynchronous settings under bounded schedulers. Additionally, we prove the impossibility of deterministic leader election when robots have no common coordinates and start in an arbitrary configuration. Secondly, we propose a collision free deterministic algorithm for circle formation designed for asynchronous networks. Thirdly, we propose a deterministic flocking algorithm totally independent of the existence of an a priori known leader. The proposed algorithm also works in asynchronous networks. <s> BIB001 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> This paper proposes a distributed algorithm for circle formation by a system of mobile robots. Each robot observes the positions of other robots and moves to a new position. Eventually they form a circle. The robots do not store past actions. They are anonymous and cannot be distinguished by their appearance and do not have a common coordinate system (origin and axis) and chirality (common handedness). Most of the earlier works assume the robots to be dimensionless (points). In this paper a robot is represented as a unit disc (fat robot). The robots are assumed to be transparent in order to achieve full visibility. However, a robot is considered as a physical obstacle for another robot. The robots execute the algorithm asynchronously. <s> BIB002 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> We study the computational power of distributed systems consisting of simple autonomous robots moving on the plane. The robots are endowed with visual perception, allowing them to see each other, but they do not have any means of explicit communication with each other. Further the robots are oblivious, meaning that they always act based on their current perception of the environment, and they have no memory of the past. Such system of simple robots have been studied extensively with the objective of achieving coordinated tasks e.g. arranging the robots in a line or a circle. In fact it has been shown that obliviousness is not a limiting factor to form a single geometric pattern, however arbitrary. This paper aims to understand the computational limits imposed by the obliviousness of the robots by studying the formation of a series of geometric patterns instead of a single pattern. If such a series of patterns could be formed this would create some form of memory in an otherwise memory-less system. We show that, under particular conditions, oblivious robot systems can indeed form a given series of geometric patterns starting from any arbitrary configuration. More precisely, we characterize the series of patterns that can be formed by oblivious robot systems under various additional restrictions such as anonymity, asynchrony and lack of common orientation. These results provide strong indications that oblivious solutions may be obtained also for tasks that intuitively seem to require memory. <s> BIB003 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> We present a randomized pattern formation algorithm for asynchronous oblivious (i.e., memory-less) mobile robots that enables formation of any target pattern. As for deterministic pattern formation algorithms, the class of patterns formable from an initial configuration I is characterized by the symmetricity (i.e., the order of rotational symmetry) of I, and in particular, every pattern is formable from I if its symmetricity is 1. The randomized pattern formation algorithm ψ PF we present in this paper consists of two phases: The first phase transforms a given initial configuration I into a configuration I′ such that its symmetricity is 1, and the second phase invokes a deterministic pattern formation algorithm ψ CWM by Fujinaga et al. (DISC 2012) for asynchronous oblivious mobile robots to finally form the target pattern. <s> BIB004 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> We investigate pattern formation, i.e., self-organization, by a swarm of mobile robots, which is closely related with the agreement problem in distributed computing. Consider a system of anonymous mobile robots in a 2-dimensional Euclidean space in which each robot repeatedly executes a “Look-Compute-Move” cycle, to observe the positions of all the robots, to compute a route to the next position using an algorithm, and then to trace the route, where the algorithm is common to all robots. The robots are said to be fully synchronous if their Look-Compute-Move cycles are completely synchronized, and the $i$th Look, Compute, and Move of all robots start and end simultaneously. They are said to be asynchronous if no assumptions are made on their synchrony. The robots are said to be oblivious if they have no memory to memorize the execution history and hence behave based only on the robots' positions observed during the immediately preceding Look. We show that the set of geometric patterns formable by oblivious... <s> BIB005 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> This paper addresses gathering, a fundamental coordination problem for multi-robot systems, for n ? 2 asynchronous, oblivious mobile robots in the presence of f faulty robots. Earlier work has reported that the asynchronous robots cannot gather at a point without having some assumptions on multiplicity detection or total agreement in coordinate axis or constant amount of persistent memory bits. This paper shows that gathering is possible by agreeing only on one axis. Traditionally the robots have been assumed to be transparent. This work proves that gathering is achievable under one axis agreement even if the robots have obstructed visibility. In both the cases, deterministic fault-tolerant algorithms have been presented, for any initial static configuration of the robots. This paper is the first attempt at studying the gathering problem under the combination of three realistic model specifications (i) agreement in one axis (ii) obstructed visibility (iii) arbitrary number of faulty robots. <s> BIB006 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> We propose a new self-stabilizing flocking algorithm for oblivious robot networks, and prove its correctness. With this algorithm, a flock head emerges from a uniform flock of robots, and the algorithm allows those robots to follow the head, whatever its direction on the plane. Robots are oblivious in that they do not recall the result of their previous computations and do not share a common coordinate system. <s> BIB007 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> The paper studies the gathering problem on grid and tree networks. A team of robots placed at different nodes of the input graph, has to meet at some node and remain there. Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move toward one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids and trees. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.In this paper, we provide a full characterization about gatherable configurations for grids and trees. In particular, we show that on these topologies, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of structures like grids and trees that allow to overcome the multiplicity detection with respect to the ring case. <s> BIB008 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> Consider a set of $n$ simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular $n$-gon not fixed in advance (Uniform Circle Formation). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the Uniform Circle Formation problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant. <s> BIB009 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> Abstract A largely studied version of the gathering problem asks to move a set of robots initially placed at different vertices of an anonymous graph toward a common vertex, and to let them remain at such a vertex. Asynchronous robots move based on the so-called Look–Compute–Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move toward one of its neighbors (Compute), and then it performs the computed move (Move), eventually. So far, the main goal has been to detect the minimal assumptions that allow to accomplish the task, without taking care of any cost measure. In this paper, we are interested in optimal algorithms in terms of total number of moves. We consider infinite grids, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm. <s> BIB010 </s> CPS-Based Smart Warehouse for Industry 4.0: A Survey of the Underlying Technologies <s> Local Coordination in Multi-Robot Systems <s> Recent advances in robotics technology have made it practical to deploy a large number of inexpensive robots in a wide range of application domains. In many of those applications, a group of autonomous robots is required to form a predefined geometric shape such as a line or a circle. This problem, namely pattern formation problem, is one of the most important coordination problems in multi-robot systems. A particular pattern extensively studied in literature is the uniform circle, and the corresponding problem is called uniform circle formation. In uniform circle formation, a set of simple mobile robots (asynchronous, autonomous), starting from arbitrary positions on the plane, have to arrange themselves on the vertices of a regular polygon eventually. Towards addressing the problem, existing works usually make conveniently strong assumptions, i.e., the robots are regarded as mass points and have unlimited sensing and communication range. The question of whether the robots with actual size and limited sensing and communication range could form a uniform circle, to our knowledge, has remained open. In this paper, we propose a new approach towards addressing this issue. Three phases, consensus on the circle, circle formation, and uniform transformation, constitute our approach. Inside our approach, there are some new distributed algorithms such as convex hull construction and cardinality estimation. Simulation result, theoretical analysis, and successful deployment have shown the effectiveness and practicability of our approach. <s> BIB011
Local Coordination is critical for multi-robot applications. It is also a research hotspot in the field of distributed computing. In literature, the researchers have established various theoretical models for MRS. Based on those models, the fundamental coordination problems are studied. Specifically, the theoretical models are divided into fully-synchronous, semi-synchronous, and asynchronous  and fundamental coordination problems include gathering BIB006 , pattern formation  BIB005 , flocking BIB007 , and so on. We categorize the local coordination in MRS according to three criteria, namely, system model, and robot ability, the problem as shown in Figure 3 . Concerning coordination in MRS, a single robot is often modeled as a loop to perform the three stages of the Look-Compute-Move  . In the phase of "Look", the robot acquires data from itself, surrounding robots and the environment. In the "Compute" phase, the robot runs a deterministic program designed to calculate the action to be taken with the data collected in the "Sense phase. Finally, in the "Move" phase, the robot performs the actions generated by the "Look" phase. Based on the model of "Look-Compute-Move", there are three theoretical models, namely fully-synchronous, semi-synchronous and asynchronous. For a fully-synchronous multi-robot system, all robots must be in the same phase at the same time. In other words, if there is a robot in the "Compute" phase, then it can be asserted that all other robots are in the "Compute" phase. For a semi-synchronous multi-robot system, all robots that are active must be in the same phase. For an asynchronous multi-robot system, the robots do not have any relationship concerning the phases. The research community always wants to achieve local coordination with the weakest robot ability. By saying robot ability, it includes visibility, memory, geometric agreement, and so on. Concerning visibility, the robots can have unlimited or limited visibility range and can be solid or transparent. With unlimited visibility range, all the robots can see each other while the system always employs unit disk graph as the visibility graph when limited visibility range is considered. The robots are solid if the robots cannot be looked through while transparent robots can. Concerning memory, three models are considered, namely oblivious, unbounded memory, and finite-state. In the oblivious model, the robots forget everything once a cycle is finished. In the unbounded memory model, the robots can memorize all the past information and computation for usage while finite-state model means that the robots have a constant persistent memory. As for the ability of geometric agreement, three models consistent compass, chirality, and disorientation are often considered. In the model of consistent compass, all the robots share the same coordinate system; in the model of chirality, the robots agree on only the direction of one axis; and, in the model of disorientation, the robots have no common sense on the coordinate system. The gathering problem refers to congregating a set of robots, which are initially placed at arbitrary positions, to a single location within a finite time. The gathering problem is the first problem studied in multi-robot coordination and is still a research hotspot. In addition, it has been studied in fully synchronous, semi-synchronous and asynchronous models BIB010 BIB008 . The pattern formation problem refers to arrange a set of robots to form a given pattern. In literature, some research works are focusing on some specific patterns, such as circular BIB002 , regular polygonal BIB009 BIB011 , etc. In addition, some research works are focusing on arbitrary patterns BIB003 BIB004 . The flocking problem is a more complicated task than pattern formation. It studies how a group of robots move while maintaining a given pattern. In nature, the flocking behavior exhibits in many living beings such as fish and birds. According to whether there are leaders (such as the bellwethers in a group of wild geese), the flocking problem is divided into guided flocking  and homogeneous flocking BIB001 .