Difference between revisions of "SRSP"

From IridiaWiki
Jump to navigationJump to search
Line 5: Line 5:
 
==Characteristics of swarm robotics==
 
==Characteristics of swarm robotics==
   
A robot swarm is a large and highly redundant group of autonomous robots that act in a self-rganized way and cooperate to accomplish a given task. Robots’ sensing and communication capabilities are local and robots do not have access to global information. The collective behavior of the robot swarm results from the interactions of each individual robot with its neighboring peers and with the environment.
+
A robot swarm is a large and highly redundant group of autonomous robots that act in a self-organized way and cooperate to accomplish a given task. Robots’ sensing and communication capabilities are local and robots do not have access to global information. The collective behavior of the robot swarm results from the interactions of each individual robot with its neighboring peers and with the environment.
   
 
==Desirable properties of swarm robotics systems==
 
==Desirable properties of swarm robotics systems==

Revision as of 16:34, 1 October 2013

Swarm robotics studies how to design a large group of robots that operate without relying on any external infrastructure and on any form of centralized control. In a robot swarm, the collective behavior of the robots results from local interactions between the robots and between the robots and the environment in which they act. The design of robot swarms is guided by swarm intelligence principles, which promote the realization of systems that are robust, scalable and flexible. Swarm robotics appears to be a promising approach when different activities must be performed concurrently, when high redundancy and the lack of a single point of failure are desired, and when it is technically unfeasible to setup an infrastructure to control the robots in a centralized way. Examples of tasks that could benefit from the application of swarm robotics are demining, search and rescue, planetary or underwater exploration, and surveillance.

Characteristics of swarm robotics

A robot swarm is a large and highly redundant group of autonomous robots that act in a self-organized way and cooperate to accomplish a given task. Robots’ sensing and communication capabilities are local and robots do not have access to global information. The collective behavior of the robot swarm results from the interactions of each individual robot with its neighboring peers and with the environment.

Desirable properties of swarm robotics systems

The characteristics of swarm robotics are deemed to promote the realization of systems that are robust, scalable and flexible.

A robot swarm is able to cope well with the failure of one or more of its individuals: the loss of individuals does not result in the failure of the whole swarm. This robustness to failures is promoted by redundancy, that is, by having many homogeneous robots, and by the lack of a leader or centralized control.

A robot swarms is also able to cope well with changes in its group size: the introduction or removal of individuals does not result in a drastic change in the performance of the swarm. Scalability is promoted by local sensing and communication and by the lack of a centralized control.

Finally, robot swarms are flexible, that is, are able to cope with a broad spectrum of different environment and tasks. Flexibility is promoted by redundancy, simplicity of the behaviors, lack of global knowledge and behavioral mechanisms as, for example, task allocation.

Potential applications of swarm robotics

The desired properties of swarm robotics systems make them appealing in several potential fields of application.


Tackling dangerous applications, such as demining, with robots is a well suited solution, as this approach eliminates or reduces the risks for humans. However, since the risk of losing robots is high, a solution that is robust to failures is necessary, making dangerous applications an ideal field of application for robot swarms.

Example of dangerous applications that can be tackled using robot swarms are: demining, search and rescue, toxic cleaning, military applications.


Other potential applications for robot swarms are those in which the dimensions of the task to tackle are difficult to estimate in advance or change with time. For instance, in case of an oil leak it is very often difficult to estimate the oil output and foreseen its development. Applications with unknown or varying dimensions must be tackled with solutions which can easily adapt. This is the case of robot swarms: robots can be added or removed to fit different requirements of the applications.

Example of applications with unknown or varying size: search and rescue, transportation of large objects, tracking, cleaning, military applications.


Applications which take place in large or unstructured environments, in which there is no pre-available communication network or global localization system, are another potential field of application for swarm robotics. Swarm robotics systems are well suited for such applications, since such systems can tackle them faster than single robots and without relying on local information and or any a priori infrastructure.

Examples of applications in unstructured and large environments are planetary or underwater exploration, military applications, surveillance, demining, cleaning, search and rescue.


Some applications take place in environments that change over time. For instance, in a post earthquake situation, buildings can collapse changing the usable paths and creating new hazards to avoid. In applications with dynamic environments it is necessary to adopt solutions which are flexible and can react fast to events. Swarm robotics principles promote the development of flexible systems, making applications in dynamic environments an ideal field of application for robot swarms.

Example of applications in dynamic environments are surveillance, disaster recovery, search and rescue, cleaning, military applications.

Scientific implications of swarm robotics

Beside engineering applications, swarm robotics is also used as a scientific tool: in particular, many models derived from the analysis of natural swarm intelligence systems have been refined and validated using robot swarms. For example, Garnier et al. (2005) validated the model of a collective decision-making behavior in cockroaches using robot swarms.

Swarm robotics has been used also to investigate the evolutionary conditions for the emergence of adaptive behaviour in groups of interacting individuals. The use of robot swarms allow the researcher to identify, in a controlled environment, the evolutionary pressures that lead to complex social behaviors, such as communication (Ampatzis et al., 2008) or collective decision-making (Francesca et al., 2012).

Current research axis

In this section, some examples of current research in swarm robotics are presented, focusing on design, modeling and collective behaviors. For a full review of the literature, see Brambilla et al. (2013).

Design

The design of a robot swarm is a difficult task: requirements are usually expressed at the collective level, but, eventually, the developer needs to define what the individual robots should do so that their interactions result in the desired collective behavior.

Approaches to the design problem in swarm robotics can be divided in two categories: manual design methods and automatic design methods.


In manual design methods, the designer follows a trial-and-error process in which he develops, tests and improves the reactive behaviors of the individual robot until the desired collective behavior is obtained.

The most common behavioral architecture used is the probabilistic finite state machine. Probabilistic finite state machines have been used to develop several collective behaviors, such as aggregation (Soysal and Sahin 2005), chain formation (Nouyan et al. 2009) and task allocation (Liu et al. 2007).

Another common approach is based on virtual physics, in which the robots and the environment interact through virtual forces. Virtual physics-based design approaches are particularly suited for spatially organizing collective behaviors, such as pattern formation (Spears er al. 2004) and collective motion (Ferrante et al., 2012).

The main limit of manual design methods is that, being bottom-up, the quality of the developed robot swarm depends completely on the ingenuity and expertise of the human designers. A systematic and general top-down design approach is still missing, even though some problem-specific approaches have been recently proposed (Hamann and Worn, 2008; Berman et al., 2011; Brambilla et al., 2012).


The main automatic design method adopted in swarm robotics is evolutionary robotics (Nolfi and Floreano, 2004). Typically, in evolutionary robotics, artificial evolution is used to configure the parameters of a neural networks that controls the behavior of the robots in the swarm (Trianni and Nolfi, 2011).

Evolutionary robotics has been applied to develop behaviors for various collective behaviors, such as aggregation (Trianni et al., 2003) and collective transport (Groß and Dorigo, 2008).

One of the main limits of evolutionary robotics is that it is often difficult to define the experimental setup and fitness function that will produce an effective collective behavior. Moreover, since collective behaviors are obtained using simulations, often they are not able to overcome the reality gap, that is, despite having good performance in simulation, they do not perform well once instantiated on robots.

TODO: remove. An alternative approach to automatically design robot swarms has been recently proposed. In this approach, probabilistic finite state machines are automatically assembled starting from pre-available modular components using an optimization algorithm (Francesca et al. 2014).

Analysis

The analysis and verification of the properties of a robot swarm are usually done by means of models.

A model of a robot swarm can be realized in two ways: by modeling the behaviors of the individual robots, what it is called, modeling the microscopic level, or by modeling the collective behavior of the swarm, what it is called, modeling the macroscopic level.

Modeling the microscopic level is a difficult task, due to the very large number of robots involved. Microscopic models in which the elements composing a system are simulated with the use of a computer are traditionally called simulations. Examples of simulators used for swarm robotics can be found in Kramer and Scheutz (2007) or in Pinciroli et al. (2012).

On the contrary, macroscopic models avoid the complexity and scalability issues of having to model each individual robots, by considering only the collective behavior of the swarm.

One of the most common macroscopic modeling approach is the use of rate or differential equations (Lerman et al. 2005). Rate equations describe the time evolution of the proportion of robots in a particular state, that is, performing a specific action or in a specific area of the environment, over the total number of robots.

Another common approach is the use of Markov chains, which allow researchers to formally verify properties of a robot swarm (Dixon et al., 2011; Massink et al., 2013).

Control theory has also been used to analyze whether a robot swarm eventually converges to a desired macroscopic state (Liu and Passino, 2004; Hsieh et al., 2008).

Finally, An alternative mesoscopic approach is the use of the Fokker-Plank and Langevin equations, which allows the researcher to model both the behavior of the individual robot, in the form of a deterministic component of the model, and the collective level of the swarm, in the form of a stochastic component of the model. Examples of such models can be found in Hamann and Worn (2008), Berman et al. (2011b) and Prorok et al. (2011).

Collective behaviors

A large part of the research efforts in swarm robotics are directed towards the study of collective behaviors. Most collective behaviors can be categorized into three main groups: spatially organizing behaviors, navigation behaviors, collective decision-making behaviors.

Spatially-organizing behaviors focus on how to organize and distribute robots and objects in space. Examples of such behaviors are: aggregation (Trianni et al., 2003), pattern formation (Spears et al. 2004), chain formation (Nouyan et al. 2009), self-assembly (O'Grady et al., 2010) and object clustering and assembling (Werfel et al., 2011).

Navigation behaviors focus on how to coordinate the movements of a robot swarm. Examples of such behaviors are: collective exploration (Ducatelle et al., 2011a), collective motion (Ferrante et al., 2012) and collective transport (Groß and Dorigo, 2009).

Collective decision-making focuses on how robots influence each other in making decisions over multiple choices. In particular collective decision-making can be used to achieve consensus, such as deciding where to aggregate (Garnier et al., 2005), or specialization, such as task allocation (Pini et al., 2009).

Other behaviors that do not fall in the previously mentioned categories are: collective fault detection (Christensen et al. 2009), group size regulation (Pinciroli et al, 2013) and human-swarm interactions (Naghsh et al. 2008).

Open issues

Swarm robotics, despite its potential to promote robustness, scalability and flexibility, have yet to be used to tackle a real-world application. There are many reasons for this lack of applications, such as, the limitations of the currently available robots or the lack of an engineering approach to swarm robotics. In particular, the lack of a general top-down methodology for the design of robot swarms, the lack of well defined metrics and testbed applications, and the lack of formal ways to verify and guarantee properties of a robot swarm are all open challenges that must be tackled before swarm robotics can be successfully applied to real-world applications.






References

C. Ampatzis, E. Tuci, V. Trianni, and M. Dorigo. Evolution of signaling in a multi-robot system: categorization and communication. Adaptive Behavior, 16(1):5–26, 2008.

S. Berman, Á. M. Halász, M. A. Hsieh, and V. Kumar. Optimized stochastic policies for task allocation in swarms of robots. IEEE Transactions on Robotics, 25(4):927–937, 2009.

S. Berman, V. Kumar, and R. Nagpal. Design of control policies for spatially inhomogeneous robot swarms with application to commercial pollination. IEEE International Conference on Robotics and Automation (ICRA), pp 378–385. 2011.

M. Brambilla, C. Pinciroli, M. Birattari, and M. Dorigo. Property-driven design for swarm robotics. In Proceedings of the AAMAS 2012, pp 139–146, 2012.

M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1):1–41, 2013.

A. L. Christensen, R. O’Grady, and M. Dorigo. From fireflies to fault-tolerant swarms of robots. IEEE Transactions on Evolutionary Computation, 13(4):754–766, 2009.

C. Dixon, A. Winfield, and M. Fisher. Towards temporal verification of emergent behaviours in swarm robotic systems. In Lecture notes in computer science: Vol. 6856. Towards autonomous robotic systems, pp. 336–347, 2011.

F. Ducatelle, G. A. Di Caro, C. Pinciroli, F. Mondada, and L. M. Gambardella. Communication assisted navigation in robotic swarms: self-organization and cooperation. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS 2011), pp. 4981–4988, 2011.

E. Ferrante, A. E. Turgut, C. Huepe, A. Stranieri, C. Pinciroli, and M. Dorigo, Self-organized flocking with a mobile robot swarm: a novel motion control method. Adaptive Behavior, 20(6):460-477, 2012.

G. Francesca, M. Brambilla, V. Trianni, M. Dorigo and, M. Birattari. Analysing an evolved robotic behaviour using a biological model of collegial decision making. In Lecture notes in computer science: Vol. 7426. Proceedings of the 12th international conference on adaptive behavior (SAB2012), pp. 381–390, 2012.

S. Garnier, C. Jost, R. Jeanson, J. Gautrais, M. Asadpour, G. Caprari, and G. Theraulaz. Aggregation behaviour as a source of collective decision in a group of cockroach-like robots. In Lecture notes in artificial intelligence: Vol. 3630. Advances in artificial life, pp. 169–178, 2005.

R. Groß and M. Dorigo. Evolution of solitary and group transport behaviors for autonomous robots capable of self-assembling. Adaptive Behavior, 16(5):285–305, 2008.

H. Hamann and H. Wörn. A framework of space-time continuous models for algorithm design in swarm robotics. Swarm Intelligence, 2(2–4):209–239, 2008.

M. A. Hsieh, Á. Halász, S. Berman and V. Kumar. Biologically inspired redistribution of a swarm of robots among multiple sites. Swarm Intelligence, 2(2–4):121–141, 2008.

J. Kramer and M. Scheutz. Development environments for autonomous mobile robots: a survey. Autonomous Robots, 22(2), 101–132, 2007.

K. Lerman, A. Martinoli, and A. Galstyan. A review of probabilistic macroscopic models for swarm robotic systems. In Lecture Notes in Computer Science: Vol. 3342. Swarm robotics, pp 143–152, 2005.

Y. Liu and K. M. Passino. Stable social foraging swarms in a noisy environment. IEEE Transactions on Automatic Control, 49(1):30–44, 2004.

W. Liu, A. F. T. Winfield, J. Sa, J. Chen, and L. Dou. Towards energy optimization: emergent task allocation in a swarm of foraging robots. Adaptive Behavior, 15(3):289–305, 2007.

M. Massink, M. Brambilla, D. Latella, M. Dorigo, and M. Birattari. On the use of bio-pepa for modelling and analysing collective behaviours in swarm robotics. Swarm Intelligence, 7(2-3):201-228, 2013.

A. Naghsh, J. Gancet, A. Tanoto, and C. Roast. Analysis and design of human-robot swarm interaction in firefighting. In Proceedings of the 17th IEEE international symposium on the robot and human interactive communication (Ro-man 2008), pp. 255–260, 2008.

S. Nolfi and D. Floreano. Evolutionary robotics: intelligent robots and autonomous agents. Cambridge: MIT Press, 2000.

S. Nouyan, R. Groß, M. Bonani, F. Mondada, and M. Dorigo. Teamwork in self-organized robot colonies. IEEE Transactions on Evolutionary Computation, 13(4):695–711, 2009.

R. O’Grady, R. Groß, A. L. Christensen, and M. Dorigo. Self-assembly strategies in a group of autonomous mobile robots. Autonomous Robots, 28(4):439–455, 2010.

C. Pinciroli, V. Trianni, R. O'Grady, G. Pini, A. Brutschy, M. Brambilla, N. Mathews, E. Ferrante, G. Di Caro, F. Ducatelle, M. Birattari, L. M. Gambardella and M. Dorigo. ARGoS: a Modular, Parallel, Multi-Engine Simulator for Multi-Robot Systems. Swarm Intelligence, 6(4):271-295, 2012.

C. Pinciroli, R. O'Grady, A. L. Christensen, M. Birattari and M. Dorigo. Parallel Formation of Differently Sized Groups in a Robotic Swarm. SICE Journal of the Society of Instrument and Control Engineers, 52(3):213-226, 2013.

G. Pini, A. Brutschy, M. Birattari, and M. Dorigo. Interference reduction through task partitioning in a robotic swarm. In IEEE international conference on neural networks: IEEE world congress on computational intelligence, 2009.

A. Prorok, N. Correll, and A. Martinoli. Multi-level spatial modeling for stochastic distributed robotic systems. The International Journal of Robotics Research, 30(5):574–589, 2011.

O. Soysal and E. Şahin. Probabilistic aggregation strategies in swarm robotic systems. In Proceedings of the IEEE swarm intelligence symposium, pp. 325–332, 2005

W. M. Spears, D. F. Spears, J. C. Hamann, and R. Heil. Distributed, physics-based control of swarms of vehicles. Autonomous Robots, 17(2–3):137–162. 2004.

V. Trianni, R. Groß, T. H. Labella, R. Şahin, and M. Dorigo. Evolving aggregation behaviors in a swarm of robots. In Lecture notes in artificial intelligence: Vol. 2801. Advances in artificial life (ECAL 2003), pp. 865–874, 2003.

V. Trianni and S. Nolfi. Engineering the evolution of self-organizing behaviors in swarm robotics: A case study. Artificial Life, 17(3):183–202, 2011.

J. Werfel, K. Petersen, and R. Nagpal. Distributed multi-robot algorithms for the TERMES 3D collective construction system. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS), 2011.

External Links