Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> From the Preface (See Front Matter for full Preface) ::: ::: Man has within a single generation found himself sharing the world with a strange new species: the computers and computer-like machines. Neither history, nor philosophy, nor common sense will tell us how these machines will affect us, for they do not do "work" as did machines of the Industrial Revolution. Instead of dealing with materials or energy, we are told that they handle "control" and "information" and even "intellectual processes." There are very few individuals today who doubt that the computer and its relatives are developing rapidly in capability and complexity, and that these machines are destined to play important (though not as yet fully understood) roles in society's future. Though only some of us deal directly with computers, all of us are falling under the shadow of their ever-growing sphere of influence, and thus we all need to understand their capabilities and their limitations. ::: ::: It would indeed be reassuring to have a book that categorically and systematically described what all these machines can do and what they cannot do, giving sound theoretical or practical grounds for each judgment. However, although some books have purported to do this, it cannot be done for the following reasons: a) Computer-like devices are utterly unlike anything which science has ever considered---we still lack the tools necessary to fully analyze, synthesize, or even think about them; and b) The methods discovered so far are effective in certain areas, but are developing much too rapidly to allow a useful interpretation and interpolation of results. The abstract theory---as described in this book---tells us in no uncertain terms that the machines' potential range is enormous, and that its theoretical limitations are of the subtlest and most elusive sort. There is no reason to suppose machines have any limitations not shared by man. <s> BIB001 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> Models of collective behavior are developed for situations where actors have two alternatives and the costs and/or benefits of each depend on how many other actors choose which alternative. The key concept is that of "threshold": the number or proportion of others who must make one decision before a given actor does so; this is the point where net benefits begin to exceed net costs for that particular actor. Beginning with a frequency distribution of thresholds, the models allow calculation of the ultimate or "equilibrium" number making each decision. The stability of equilibrium results against various possible changes in threshold distributions is considered. Stress is placed on the importance of exact distributions distributions for outcomes. Groups with similar average preferences may generate very different results; hence it is hazardous to infer individual dispositions from aggregate outcomes or to assume that behavior was directed by ultimately agreed-upon norms. Suggested applications are to riot ... <s> BIB002 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> This paper presents a unique real-time obstacle avoidance approach for manipulators and mobile robots based on the "artificial potential field" concept. In this approach, collision avoidance, traditionally considered a high level planning problem, can be effectively distributed between different levels of control, allowing real-time robot operations in a complex environment. We have applied this obstacle avoidance scheme to robot arm using a new approach to the general problem of real-time manipulator control. We reformulated the manipulator control problem as direct control of manipulator motion in operational space-the space in which the task is originally described-rather than as control of the task's corresponding joint space motion obtained only after geometric and kinematic transformation. This method has been implemented in the COSMOS system for a PUMA 560 robot. Using visual sensing, real-time collision avoidance demonstrations on moving obstacles have been performed. <s> BIB003 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> Social insects provide us with a powerful metaphor to create decentralized systems of simple interacting, and often mobile, agents. The emergent collective intelligence of social insects---swarm intelligence---resides not in complex individual abilities but rather in networks of interactions that exist among individuals and between individuals and their environment. In particular, a recently proposed model of division of labor in a colony of primitively eusocial wasps, based on a simple reinforcement of response thresholds, can be transformed into a decentralized adaptive algorithm of task allocation. An application of such an algorithm is proposed in the context of a mail company, but virtually any type of flexible task allocation can be described within the same framework. <s> BIB004 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> Abstract A Very Large Scale Robotic (VLSR) system may consist of from hundreds to perhaps tens of thousands or more autonomous robots. The costs of robots are going down, and the robots are getting more compact, more capable, and more flexible. Hence, in the near future, we expect to see many industrial and military applications of VLSR systems in tasks such as assembling, transporting, hazardous inspection, patrolling, guarding and attacking. In this paper, we propose a new approach for distributed autonomous control of VLSR systems. We define simple artificial force laws between pairs of robots or robot groups. The force laws are inverse-power force laws, incorporating both attraction and repulsion. The force laws can be distinct and to some degree they reflect the ‘social relations’ among robots. Therefore we call our method social potential fields. An individual robot's motion is controlled by the resultant artificial force imposed by other robots and other components of the system. The approach is distributed in that the force calculations and motion control can be done in an asynchronous and distributed manner. We also extend the social potential fields model to use spring laws as force laws. This paper presents the first and a preliminary study on applying potential fields to distributed autonomous multi-robot control. We describe the genetic framework of our social potential fields method. We show with computer simulations that the method can yield interesting and useful behaviors among robots, and we give examples of possible industrial and military applications. We also identify theoretical problems for future studies. <s> BIB005 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> In this paper we study the stability of the collective behavior of social foraging swarms, i.e., swarms moving in a profile of nutrient/toxic substances (an attractant/repellent profile) and extend our previous results. In particular, we consider a plane profile and also extend our results for the quadratic, Gaussian, and multi-modal Gaussian profiles. Moreover, we analyze the ultimate behavior of the individuals in the social foraging swarm. The paper closes with new simulation studies that give insights into swarm dynamics. <s> BIB006 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> We introduce a framework, called “physicomimetics,” that provides distributed control of large collections of mobile physical agents in sensor networks. The agents sense and react to virtual forces, which are motivated by natural physics laws. Thus, physicomimetics is founded upon solid scientific principles. Furthermore, this framework provides an effective basis for self-organization, fault-tolerance, and self-repair. Three primary factors distinguish our framework from others that are related: an emphasis on minimality (e.g., cost effectiveness of large numbers of agents implies a need for expendable platforms with few sensors), ease of implementation, and run-time efficiency. Examples are shown of how this framework has been applied to construct various regular geometric lattice configurations (distributed sensing grids), as well as dynamic behavior for perimeter defense and surveillance. Analyses are provided that facilitate system understanding and predictability, including both qualitative and quantitative analyses of potential energy and a system phase transition. Physicomimetics has been implemented both in simulation and on a team of seven mobile robots. Specifics of the robotic embodiment are presented in the paper. <s> BIB007 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> Amorphous computing considers the problem of controlling millions of spatially distributed unreliable devices which communicate only with nearby neighbors. To program such a system, we need a high-level description language for desired global behaviors, and a system to compile such descriptions into locally executing code which robustly creates and maintains the desired global behavior. I survey existing amorphous computing primitives and give desiderata for a language describing computation on an amorphous computer. I then bring these together in Amorphous Medium Language, which computes on an amorphous computer as though it were a space-filling computational medium. <s> BIB008 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> We present two swarm intelligence control mechanisms used for distributed robot path formation. In the first, the robots form linear chains. We study three variants of robot chains, which vary in the degree of motion allowed to the chain structure. The second mechanism is called vectorfield. In this case, the robots form a pattern that globally indicates the direction towards a goal or home location. <s> BIB009 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> Traditionally, two alternative design approaches have been available to engineers: top-down and bottom-up. In the top-down approach, the design process starts with specifying the global system state and assuming that each component has global knowledge of the system, as in a centralized approach. The solution is then decentralized by replacing global knowledge with communication. In the bottom-up approach, on the other hand, the design starts with specifying requirements and capabilities of individual components, and the global behavior is said to emerge out of interactions among constituent components and between components and the environment. In this paper we present a comparative study of both approaches with particular emphasis on applications to multi-agent system engineering and robotics. We outline the generic characteristics of both approaches from the MAS perspective, and identify three elements that we believe should serve as criteria for how and when to apply either of the approaches. We demonstrate our analysis on a specific example of load balancing problem in robotics. We also show that under certain assumptions on the communication and the external environment, both bottom-up and top-down methodologies produce very similar solutions. <s> BIB010 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> Programmability is an increasingly important barrier to the deployment of multi-robot systems, as no prior approach allows routine composition and reuse of general aggregate behaviors. The Proto spatial computing language, however, already provides this sort of aggregate behavior programming for non-mobile systems using an abstraction of the network as a continuous-space-filling device. We extend this abstraction to mobile systems and show that Proto can be applied to multi-robot systems with an actuator that turns a vector field into device motion. Proto programs operate on fields of values over an abstract device called the amorphous medium and can be joined together using functional composition. These programs are then automatically transformed for execution by individual devices, producing an approximation of the specified continuous-space behavior. We are thus able to build up a library of simple swarm behaviors, and to compose them together into highly succinct programs that predictably produce the desired complex swarm behaviors, as demonstrated in simulation and on a group of 40 iRobot SwarmBots. <s> BIB011 </s> Swarm robotics: a review from the swarm engineering perspective <s> Behavior-based design methods <s> In this paper, we propose a novel top-down design method for the development of collective behaviors of swarm robotics systems called property-driven design. Swarm robotics systems are usually designed and developed using a code-and-fix approach, that is, the developer devises, tests and modifies the individual robot behaviors until a desired collective behavior is obtained. The code-and-fix approach can be very time consuming and relies completely on the ingenuity and expertise of the designer. The idea of property-driven design is that a swarm robotics system can be described by specifying formally a set of desired properties. In an iterative process similar to test-driven development, the developer produces a model of the system that satisfies the desired properties. Subsequently, the system is implemented in simulation and using real robots. Property-driven design helps to minimize the risk of developing a system that does not satisfy the required properties, and to promote the reuse of hardware independent models. In this paper, we start by giving a general description of the method. We then present a possible way to apply it by using Discrete Time Markov Chains (DTMC) and Probabilistic Computation Tree Logic* (PCTL*). Finally, we conclude by presenting the application of the proposed method to the design and development of a swarm robotics system performing aggregation. <s> BIB012
In swarm robotics, the most commonly used design method involve developing, by hand, the individual behaviors of the robots which results in the collective behavior of the swarm. Designing a behavior for a swarm robotics system is usually a trial and error process: individual behaviors are iteratively adjusted and tuned until the resulting collective behavior is obtained. For this reason, behavior-based design is, typically, a bottom-up process BIB010 ) even though some top-down methods have been recently proposed (see Sect. 2.1.1). We divide the literature on behavior-based design methods into three main categories: probabilistic finite state machine design, virtual physics-based design and other design methods. Probabilistic finite state machine design Generally, in swarm robotics, an individual robot does not plan its future actions, but it takes decisions only on the basis of its sensory inputs and/or its internal memory  . One of the most adopted design methods to obtain such behaviors is the use of a particular class of finite state machine BIB001 : probabilistic finite state machines (PFSMs). In PFSMs, the transition probability between states can be fixed or can change over time. The transition probability is fixed when a single probability value is defined and used throughout the execution of the collective behavior. An example can be found in the work of Soysal andŞahin (2005) . The transition probability is not fixed when it is defined through a mathematical function of one or more parameters of the system. One of the most widely used function is the response threshold function developed by BIB002 (see also BIB004 . The response threshold function, depicted in Fig. 2 , has been used to study the collective behavior of social insects , and has been introduced in swarm robotics by  to study collective decision-making and task allocation. In the response threshold function, the probability to switch to a new state is usually related to the current state of the robot. PFSMs have been used to develop several collective behaviors, such as aggregation (Soysal andŞahin 2005) , chain formation BIB009 ) and task allocation  . These behaviors will be explained in more detail in Sect. 3.1.1, Sect. 3.1.2 and Sect. 3.3.2, respectively. Fig. 3 The Lennard-Jones potential function. The potential v depends on the current distance d between two robots. σ is the desired distance between the robots and corresponds to the depth of the potential function. In this example, σ = 0.3 and = 2.5 Virtual physics-based design The virtual physics-based design method draws inspiration from physics. Each robot is considered as a virtual particle that exerts virtual forces on other robots. One of the first works using virtual physics-based design was by BIB003 , who used the concept of artificial potential field. In this and in some following works, the robots are subject to repulsive virtual forces originating from the environment: the goal is associated with an attractive force and the obstacles with repulsive forces. The social potential fields framework BIB005 considers also robots as associated to virtual forces. Later, BIB007 proposed a virtual physics-based design method called physicomimetics framework. Since we believe this is the most general framework, it will be used to describe the method. In describing virtual physics-based design, we will follow the most common used terminology, which uses, sometimes in an inaccurate way, a vocabulary borrowed from physics. Virtual physics-based design assumes that the robots are able to perceive and distinguish neighboring robots and obstacles, and to estimate their distance and relative position. Each robot computes a virtual force vector , where θ i and d i are the direction and the distance of the ith perceived obstacle or robot and the function f i (d i ) is derived from an artificial potential function. The most commonly used artificial potential is the LennardJones potential, depicted in Fig. 3 . The main advantages of virtual physics-based design methods are: (i) a single mathematical rule smoothly translates the entire sensory inputs space into the actuators output space without the need for multiple rules or behaviors; (ii) the obtained behaviors can be combined using vectorial operations; (iii) some properties (such as robustness, stability, etc.) can be proved using theoretical tools from physics, control theory or graph theory BIB006 . The virtual physics-based method is often used to design collective behaviors that require a robot formation. Examples of such behaviors are pattern formation (Sect. 3.1.2), collective exploration (Sect. 3.2.1) and coordinated motion (Sect. 3.2.2). Other behavior-based design methods In this section, we outline other works using behavior-based design that do not fit in the previous sections. BIB011 proposed a scripting language called Protoswarm based on the amorphous computational medium BIB008 . The amorphous computational medium considers the environment as filled with individuals able both to perform computations and to communicate with their neighbors. Using Protoswarm it is possible to define behaviors for an individual by writing scripts at the collective level. Several collective-level primitives exist in the scripting language, both related to space and time. These primitives are translated into individual behaviors by exploiting the underlying local communication. This language, even though it cannot be considered a standalone design method, can significantly ease the design process thanks to its collective-level primitives. This approach is particularly suited for sensor networks, where the great number of individuals guarantees that the system is able to cover the entire environment with a single communication network. BIB012 proposed a top-down method to design swarm robotics systems. Their idea is to define the desired system using a set of properties. These properties are logic formulas which need to hold true in the final system. The authors propose an iterative process composed of four steps. In the first step, the properties are defined. In the second step, a macroscopic model is produced. A model checker is then used to verify that the properties hold true in the produced model. In the third step, the macroscopic model is used to guide the process of implementing the system using a simulator. Finally, in the fourth the system is tested using real robots. This approach can guide the design process from the desired system to the actual implementation. Moreover, the process helps to formally verify that the final system satisfies the desired properties.