Difference between revisions of "SRSP"

From IridiaWiki
Jump to navigationJump to search
Line 1: Line 1:
'''Swarm robotics''' studies how to design large groups 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 fault tolerant, scalable and flexible.
+
'''Swarm robotics''' studies how to design large groups 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. Such principles promote the realization of systems that are fault tolerant, 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
 
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 be profitably tackled using swarm robotics are demining, search and rescue, planetary or underwater exploration, and surveillance.
 
it is technically unfeasible to setup an infrastructure to control the robots in a centralized way. Examples of tasks that could be profitably tackled using swarm robotics are demining, search and rescue, planetary or underwater exploration, and surveillance.
  +
  +
==Origins==
  +
  +
Swarm robotics has its origins in [[swarm intelligence]] and, in fact, could be defined as "embodied swarm intelligence". Initially, the main focus of swarm robotics research was to study and validate biological research (Beni, 2005). Collaboration between roboticists and biologists was vital to make swarm robotics a relevant research field. However, in recent years the focus of swarm robotics has been shifting: from a bio-inspired field of robotics, swarm robotics is becoming more and more an engineering field whose focus is on the development of tools and methods to solve real problems (Brambilla et al., 2013).
   
 
==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-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.
+
A robot swarm is a type of multi-robot system characterized by being a highly redundant group of autonomous robots that act in a [[Self-organization|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 emerges from the interactions of each individual robot with its neighboring peers and with the environment. Typically, a robot swarm is composed of homogeneous robots, but examples of heterogeneous robot swarms exist (Dorigo et al., 2013).
   
 
==Desirable properties of swarm robotics systems==
 
==Desirable properties of swarm robotics systems==
Line 13: Line 17:
 
Swarm robotics promotes the development of systems that are able to cope well with the failure of one or more of its individuals: the loss of individuals does not imply the failure of the whole swarm. Fault tolerance is enabled by the high redundancy of the swarm: the swarm does not rely on any centralized control entity, leaders, or any individual robot playing a predefined role.
 
Swarm robotics promotes the development of systems that are able to cope well with the failure of one or more of its individuals: the loss of individuals does not imply the failure of the whole swarm. Fault tolerance is enabled by the high redundancy of the swarm: the swarm does not rely on any centralized control entity, leaders, or any individual robot playing a predefined role.
   
Swarm robotics promotes also the development of systems that are able to cope well with changes in their group size: the introduction or removal of individuals does not cause a drastic change in the performance of the swarm. Scalability is enabled by local sensing and communication: provided that the introduction and removal of robots does not dramatically modify the density of the robots, each individual robot will keep interacting with approximately the same number of peers, those that are in its sensing and communication range.
+
Swarm robotics promotes also the development of systems that are able to cope well with changes in their group size: ideally, the introduction or removal of individuals does not cause a drastic change in the performance of the swarm. Scalability is enabled by local sensing and communication: provided that the introduction and removal of robots does not dramatically modify the density of the robots, each individual robot will keep interacting with approximately the same number of peers, those that are in its sensing and communication range.
   
 
Finally, swarm robotics promotes the development of systems that are able to deal with a broad spectrum of environments and operating conditions. Flexibility is enabled by the distributed and self-organized nature of a robot swarm: in a swarm, robots dynamically allocate themselves to different tasks to match the requirements of the specific environment and operating conditions; moreover, robots operate on the basis of local sensing and communication without the need of pre-existing infrastructures and of global information on the environment.
 
Finally, swarm robotics promotes the development of systems that are able to deal with a broad spectrum of environments and operating conditions. Flexibility is enabled by the distributed and self-organized nature of a robot swarm: in a swarm, robots dynamically allocate themselves to different tasks to match the requirements of the specific environment and operating conditions; moreover, robots operate on the basis of local sensing and communication without the need of pre-existing infrastructures and of global information on the environment.
Line 21: Line 25:
 
The properties of swarm robotics systems make them appealing in several potential fields of application.
 
The properties of swarm robotics systems make them appealing in several potential fields of application.
   
 
The use of robots for tackling dangerous tasks is clearly appealing as it eliminates or reduces risks for humans. The dangerous nature of these tasks implies a high risk of losing robots. Therefore, a fault-tolerant approach is required, making dangerous tasks an ideal field of application for robot swarms. Example of dangerous tasks that could be tackled using robot swarms are demining, search and rescue, and toxic cleaning.
<!-- ====Dangerous applications==== -->
 
The use of robots for tackling dangerous tasks is clearly appealing as it eliminates or reduces risks for humans. The dangerous nature of these tasks implies a high risk of losing robots. Therefore, a solution that is fault tolerant is necessary, making dangerous tasks an ideal field of application for robot swarms. Example of dangerous tasks that could be tackled using robot swarms are demining, search and rescue, and toxic cleaning.
 
   
<!-- ====Applications with unknown or varying size==== -->
 
 
Other potential applications for robot swarms are those in which it is difficult or even impossible to estimate in advance the resources needed to accomplish the task. For instance, allocating resources to manage an oil leak can be very hard because it is often difficult to estimate the oil output and to foresee its development. In these cases, a solution is needed that is scalable and flexible. A robot swarm could be an appealing solution: robots can be added or removed in time to provide the appropriate amount of resources and meet the requirements of the specific task. Example of tasks that might require an ''a priori'' unknown amount of resources are search and rescue, transportation of large objects, tracking, and cleaning.
 
Other potential applications for robot swarms are those in which it is difficult or even impossible to estimate in advance the resources needed to accomplish the task. For instance, allocating resources to manage an oil leak can be very hard because it is often difficult to estimate the oil output and to foresee its development. In these cases, a solution is needed that is scalable and flexible. A robot swarm could be an appealing solution: robots can be added or removed in time to provide the appropriate amount of resources and meet the requirements of the specific task. Example of tasks that might require an ''a priori'' unknown amount of resources are search and rescue, transportation of large objects, tracking, and cleaning.
   
<!-- ====Applications in large and unstructured environments==== -->
 
 
Another potential field of application for swarm robotics are tasks that have to be accomplished in large or unstructured environments, in which there is no available infrastructure that can be used to control the robots - e.g., no available communication network or global localization system. Robot swarms could be employed for such applications because they are able to act autonomously without the need of any infrastructure or any form of external coordination. Examples of tasks in unstructured and large environments are planetary or underwater exploration, surveillance, demining, cleaning, and search and rescue.
 
Another potential field of application for swarm robotics are tasks that have to be accomplished in large or unstructured environments, in which there is no available infrastructure that can be used to control the robots - e.g., no available communication network or global localization system. Robot swarms could be employed for such applications because they are able to act autonomously without the need of any infrastructure or any form of external coordination. Examples of tasks in unstructured and large environments are planetary or underwater exploration, surveillance, demining, cleaning, and search and rescue.
   
<!-- ====Applications in dynamic environments==== -->
 
 
Some environments might change rapidly over time. For instance, in a post earthquake situation, buildings might collapse changing the layout of the environment and creating new hazards. In these cases, it is necessary to adopt solutions that are flexible and can react fast to events. Swarm robotics could be used to develop flexible systems that can rapidly adapt to new operating conditions. Example of tasks in environments that change over time are patrolling, disaster recovery, search and rescue, cleaning.
 
Some environments might change rapidly over time. For instance, in a post earthquake situation, buildings might collapse changing the layout of the environment and creating new hazards. In these cases, it is necessary to adopt solutions that are flexible and can react fast to events. Swarm robotics could be used to develop flexible systems that can rapidly adapt to new operating conditions. Example of tasks in environments that change over time are patrolling, disaster recovery, search and rescue, cleaning.
   
Line 41: Line 41:
 
==Current research axes==
 
==Current research axes==
   
In this section, we present the main research axes of the current research in swarm robotics. For a comprehensive review of the literature, see Brambilla et al. (2013).
+
In this section, we present the main research axes of the current research in swarm robotics. We follow the taxonomy presented in Brambilla et al. (2013).
   
 
====Design====
 
====Design====
Line 48: Line 48:
 
Approaches to the design problem in swarm robotics can be divided in two categories: manual design and automatic design.
 
Approaches to the design problem in swarm robotics can be divided in two categories: manual design and automatic design.
   
In '''manual design''', the designer follows a trial-and-error process in which the behaviors of the individual robot are developed, tested and improved until the desired collective behavior is obtained. The software architecture that is most commonly adopted in swarm robotics is the ''probabilistic finite state machine''. Probabilistic finite state machines have been used to obtain several collective behaviors, including 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 this approach, robots and environment interact through virtual forces. This approach is particularly suited for spatially organizing collective behaviors, such as pattern formation (Spears et al. 2004) and collective motion (Ferrante et al., 2012). Currently, the main limit of manual design is that it completely relies on the ingenuity and expertise of the human designer: designing a robot swarm is more of an art than a science. A systematic and general way to design robot swarms is still missing, even though a few preliminary proposals have been made (Hamann and Worn, 2008; Berman et al., 2011; Brambilla et al., 2012).
+
In '''manual design''', the designer follows a trial-and-error process in which the behaviors of the individual robot are developed, tested and improved until the desired collective behavior is obtained. The software architecture that is most commonly adopted in swarm robotics is the ''probabilistic finite state machine''. Probabilistic finite state machines have been used to obtain several collective behaviors, including aggregation (Soysal and Sahin, 2005), chain formation (Nouyan et al., 2009), and task allocation (Liu and Winfield, 2010). Another common approach is based on ''virtual physics''. In this approach, robots and environment interact through virtual forces. This approach is particularly suited for spatially organizing collective behaviors, such as pattern formation (Spears et al. 2004) and collective motion (Ferrante et al., 2012). Currently, the main limit of manual design is that it completely relies on the ingenuity and expertise of the human designer: designing a robot swarm is more of an art than a science. A systematic and general way to design robot swarms is still missing, even though a few preliminary proposals have been made (Hamann and Worn, 2008; Berman et al., 2011; Brambilla et al., 2012).
   
In swarm robotics, '''automatic design''' has been mostly performed using the evolutionary robotics approach (Nolfi and Floreano, 2004). Typically, individual robots are controlled by a neural network whose parameters are obtained via artificial evolution (Trianni and Nolfi, 2011). Evolutionary robotics has been used to develop several collective behaviors including collective transport (Groß and Dorigo, 2008) and development of communication networks (Huaert et al., 2008). One of the main limits of evolutionary robotics is that it is often difficult to define all the elements of the evolutionary process that will produce control software that allows the robot swarm to effectively accomplish the given task.
+
In swarm robotics, '''automatic design''' has been mostly performed using the evolutionary robotics approach (Nolfi and Floreano, 2004). Typically, individual robots are controlled by a neural network whose parameters are obtained via [[Genetic algorithms|artificial evolution]] (Trianni and Nolfi, 2011). Evolutionary robotics has been used to develop several collective behaviors including collective transport (Groß and Dorigo, 2008) and development of communication networks (Huaert et al., 2008). One of the main limits of evolutionary robotics is that it is often difficult to define all the elements of the evolutionary process that will produce control software that allows the robot swarm to effectively accomplish the given task.
   
 
====Analysis====
 
====Analysis====
 
The analysis of a robot swarm usually relies on models. A model of a robot swarm can be realized at two levels: the microscopic level, that is modeling the behaviors of the individual robots; or the macroscopic level, that is modeling the collective behavior of the swarm.
 
The analysis of a robot swarm usually relies on models. A model of a robot swarm can be realized at two levels: the microscopic level, that is modeling the behaviors of the individual robots; or the macroscopic level, that is modeling the collective behavior of the swarm.
   
Modeling the microscopic level allows one to represent in a detailed way the actions of all the individual robots composing the swarm. Unfortunately, microscopic modeling is problematic due to the very large number of robots involved. Often, microscopic modeling relies on computer-based simulations (Kramer and Scheutz, 2007; Pinciroli et al., 2012).
+
Modeling the microscopic level allows one to represent in a detailed way the actions of all the individual robots composing the swarm. Unfortunately, microscopic modeling is problematic due to the large number of robots involved. Often, microscopic modeling relies on computer-based simulations (Kramer and Scheutz, 2007; Pinciroli et al., 2012).
   
Macroscopic models avoid the complexity and scalability issues of having to model each individual robot by considering only the collective behavior of the swarm. One of the most common macroscopic modeling approaches is the use of ''rate'' or ''differential equations'' (Martinoli et al., 2004; Lerman et al., 2005). Rate equations describe the time evolution of the ratio of robots in a particular state, that is, of robots that are performing a specific action or are in a specific area of the environment. Another common approach is the use of ''Markov chains'', which allow researchers to formally verify properties of a robot swarm (Dixon et al., 2011; Konur et al., 2012; 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).
+
Macroscopic models avoid the complexity and scalability issues of having to model each individual robot by considering only the collective behavior of the swarm. One of the most common macroscopic modeling approaches is the use of ''rate'' or ''differential equations'' (Martinoli et al., 2004; Lerman et al., 2005). Rate equations describe the time evolution of the ratio of robots in a particular state, that is, of robots that are performing a specific action or are in a specific area of the environment. Rate equations have been used to model many collective behaviors, including object clustering (Martinoli et al., 1999) and adaptive foraging (Liu and Winfield, 2010). Another common approach is the use of ''Markov chains'', which allow researchers to formally verify properties of a robot swarm (Dixon et al., 2011; Konur et al., 2012; 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).
   
 
A hybrid way of modeling robot swarms is based on ''Fokker-Plank'' and ''Langevin'' equations (Hamann and Worn, 2008; Berman et al., 2009; Prorok et al., 2011). Using these equations, one can 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.
 
A hybrid way of modeling robot swarms is based on ''Fokker-Plank'' and ''Langevin'' equations (Hamann and Worn, 2008; Berman et al., 2009; Prorok et al., 2011). Using these equations, one can 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.
Line 63: Line 63:
 
====Collective behaviors====
 
====Collective behaviors====
 
A large part of the research effort in swarm robotics is directed towards the study of collective behaviors.
 
A large part of the research effort in swarm robotics is directed towards the study of collective behaviors.
Collective behaviors can be categorized into four main groups: spatially organizing behaviors, navigation behaviors, collective decision-making behaviors, and other behaviors.
+
Collective behaviors can be categorized into five main groups: spatially organizing behaviors, navigation behaviors, decision-making behaviors, human interaction behaviors, and other behaviors.
   
<!-- =====Spatially-organizing behaviors===== -->
 
 
Spatially-organizing behaviors focus on how to organize and distribute robots and objects in space.
 
Spatially-organizing behaviors focus on how to organize and distribute robots and objects in space.
 
Examples of such behaviors are aggregation (Soysal and á¹¢ahin, 2005), pattern formation (Spears et al. 2004), chain formation (Nouyan et al. 2009), self-assembly (O'Grady et al., 2010), and object clustering/assembling (Werfel et al., 2011).
 
Examples of such behaviors are aggregation (Soysal and á¹¢ahin, 2005), pattern formation (Spears et al. 2004), chain formation (Nouyan et al. 2009), self-assembly (O'Grady et al., 2010), and object clustering/assembling (Werfel et al., 2011).
   
<!-- =====Navigation behaviors===== -->
 
 
Navigation behaviors focus on how to coordinate the movement of a robot swarm.
 
Navigation behaviors focus on how to coordinate the movement of a robot swarm.
 
Examples of such behaviors are collective exploration (Ducatelle et al., 2014), collective motion (Turgut et al., 2008), and collective transport (Baldassarre et al., 2006).
 
Examples of such behaviors are collective exploration (Ducatelle et al., 2014), collective motion (Turgut et al., 2008), and collective transport (Baldassarre et al., 2006).
   
<!-- =====Collective decision-making===== -->
 
 
Collective decision-making focuses on how robots influence each other in making decisions.
 
Collective decision-making focuses on how robots influence each other in making decisions.
 
In particular, collective decision-making can be used to achieve consensus on a single alternative (Garnier et al., 2005; Campo et al. 2011) or allocation to different alternatives (Pini et al., 2011).
 
In particular, collective decision-making can be used to achieve consensus on a single alternative (Garnier et al., 2005; Campo et al. 2011) or allocation to different alternatives (Pini et al., 2011).
   
  +
Human-swarm interaction focus on how a human operator can control a swarm and receive feedback information from it. For example, robots can distributedly recognize the gestures of human operator (Giusti et al., 2012) or form groups based on visual and vocal inputs (Pourmehr et al., 2013).
<!-- =====Other===== -->
 
  +
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 interaction (Naghsh et al. 2008).
+
Other behaviors that do not fall in the previously mentioned categories are collective fault detection (Christensen et al. 2009) and group size regulation (Pinciroli et al, 2013).
   
 
==Open issues==
 
==Open issues==
   
Despite its potential to promote robustness, scalability and flexibility, swarm robotics has yet to be adopted for solving real-world problems. This is possibly due to the hardware limitations of the currently available robots and to the lack of an engineering approach for swarm robotics. In particular, the main open issues are the lack of a general methodology for designing robot swarms, the lack of well defined metrics and testbed to assess their performance, and the lack of formal ways to verify and guarantee their properties.
+
Despite its potential to promote robustness, scalability and flexibility, swarm robotics has yet to be adopted for solving real-world problems. This is possibly due to the hardware limitations of the currently available robots, to the lack of effective ways to let a human operator interact with a robot swarm and to the lack of an engineering approach for swarm robotics. A further issue is the lack of any compelling demonstrators for outdoor swarm robotic systems (e.g., waste collection), and the lack of any business case or business model that demonstrates that the swarm robotics approach would be more cost effective than other approaches. In particular, the main open issues are the lack of a general methodology for designing robot swarms, the lack of well defined metrics and testbed to assess their performance, and the lack of formal ways to verify and guarantee their properties.
  +
__AUTOLINKER{0}
 
 
== References ==
 
== References ==
   
 
G. Baldassarre, D. Parisi, and S. Nolfi. Distributed coordination of simulated robots based on self-organization. ''Artificial Life'', 12(3):289–311, 2006.
 
G. Baldassarre, D. Parisi, and S. Nolfi. Distributed coordination of simulated robots based on self-organization. ''Artificial Life'', 12(3):289–311, 2006.
  +
  +
G. Beni. From swarm intelligence to swarm robotics. In ''Swarm Robotics'', LNCS 3342, pp. 1-9, 2005. Springer.
   
 
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, Á. 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.
Line 100: Line 100:
 
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.
 
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 ''Towards Autonomous Robotic Systems'', LNCS 6856, pp. 336–347, 2011. Springer.
+
C. Dixon, A. F. T. Winfield, M. Fisher, and C. Zheng. Towards Temporal Verification of Swarm Robotic Systems. ''Robotics and Autonomous Systems'', 60(11):1429-1441, 2012.
  +
  +
M. Dorigo, D. Floreano, L. M. Gambardella, F. Mondada, S. Nolfi, T. Baaboura, M. Birattari, M. Bonani, M. Brambilla, A. Brutschy, D. Burnier, A. Campo, A. L. Christensen, A. Decugniere, G. Di Caro, F. Ducatelle, E. Ferrante, A. Forster, J. Martinez Gonzales, J. Guzzi, V. Longchamp, S. Magnenat, N. Mathews, M. Montes de Oca, R. O'Grady, C. Pinciroli, G. Pini, P. Retornaz, J. Roberts, V. Sperati, T. Stirling, A. Stranieri, T. Stutzle, V. Trianni, E. Tuci, A.E. Turgut, F. Vaussard. Swarmanoid: A Novel Concept for the Study of Heterogeneous Robotic Swarms. ''IEEE Robotics & Automation Magazine'', 20(4):60-71, 2013.
   
 
F. Ducatelle, G. A. Di Caro, C. Pinciroli, F. Mondada, and L. M. Gambardella. Cooperative navigation in robotic swarms. ''Swarm Intelligence'', 8(1):in press, 2014.
 
F. Ducatelle, G. A. Di Caro, C. Pinciroli, F. Mondada, and L. M. Gambardella. Cooperative navigation in robotic swarms. ''Swarm Intelligence'', 8(1):in press, 2014.
Line 107: Line 109:
   
 
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 ''Advances in Artificial Life'', LNAI 3630, pp. 169–178, 2005. Springer.
 
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 ''Advances in Artificial Life'', LNAI 3630, pp. 169–178, 2005. Springer.
  +
  +
A. Giusti, J. Nagi, L. Gambardella, S. Bonardi, and G. A. Di Caro. Human-Swarm Interaction through Distributed Cooperative Gesture Recognition. 7th ACM/IEEE International Conference on Human-Robot Interaction (Video Session), 2012.
   
 
J. Halloy, G. Sempo, G. Caprari, C. Rivault, M. Asadpour, F. Tâche, I. Said, V. Durier, S. Canonge, J.M. Amé, C. Detrain, N. Correll, A. Martinoli, F. Mondada, R. Siegwart, J.-L. Deneubourg. Social integration of robots into groups of cockroaches to control self-organized choices. ''Science'', 318(5853):1155–1158, 2007.
 
J. Halloy, G. Sempo, G. Caprari, C. Rivault, M. Asadpour, F. Tâche, I. Said, V. Durier, S. Canonge, J.M. Amé, C. Detrain, N. Correll, A. Martinoli, F. Mondada, R. Siegwart, J.-L. Deneubourg. Social integration of robots into groups of cockroaches to control self-organized choices. ''Science'', 318(5853):1155–1158, 2007.
Line 124: Line 128:
 
Y. Liu and K. M. Passino. Stable social foraging swarms in a noisy environment. ''IEEE Transactions on Automatic Control'', 49(1):30–44, 2004.
 
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.
+
W. Liu, A. F. T. Winfield. A Macroscopic Probabilistic Model for Collective Foraging with Adaptation. ''International Journal of Robotics Research'', 29(14):1743-1760, 2010.
   
 
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.
 
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. Martinoli, A. J. Ijspeert, and F. Mondada. Understanding collective aggregation mechanisms: from
  +
probabilistic modelling to experiments with real robots. ''Robotics and Autonomous Systems'', 29(1):51–
  +
63, 1999.
   
 
A. Martinoli, K. Easton, and W. Agassounon. Modeling swarm robotic systems: a case study in collaborative distributed manipulation. ''The International Journal of Robotics Research'', 23(4–5):415–436, 2004.
 
A. Martinoli, K. Easton, and W. Agassounon. Modeling swarm robotic systems: a case study in collaborative distributed manipulation. ''The International Journal of Robotics Research'', 23(4–5):415–436, 2004.
Line 145: Line 153:
   
 
G. Pini, A. Brutschy, M. Frison, A. Roli, M. Dorigo, and M. Birattari. Task partitioning in swarms of robots: An adaptive method for strategy selection. ''Swarm Intelligence'', 5(3-4):283-304, 2011.
 
G. Pini, A. Brutschy, M. Frison, A. Roli, M. Dorigo, and M. Birattari. Task partitioning in swarms of robots: An adaptive method for strategy selection. ''Swarm Intelligence'', 5(3-4):283-304, 2011.
  +
  +
S. Pourmehr, V. M. Monajjemi, R. T. Vaughan, and G. Mori. "You two! Take off!": Creating, modifying and commanding groups of robots using face engagement and indirect speech in voice commands. In'' Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS)'', 2013. IEEE press.
   
 
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.
 
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.
Line 158: Line 168:
 
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. IEEE press.
 
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. IEEE press.
   
== External Links ==
+
== External links ==
   
 
* [http://www.springer.com/11721 Swarm Intelligence]: The main journal in the field.
 
* [http://www.springer.com/11721 Swarm Intelligence]: The main journal in the field.
Line 171: Line 181:
 
* [http://www.e-swarm.org/ E-Swarm]: research project 2010-2015
 
* [http://www.e-swarm.org/ E-Swarm]: research project 2010-2015
 
* [http://www.eecs.harvard.edu/ssr/projects/progSA/kilobot.html Kilobots]: a low-cost robot for swarm robotics
 
* [http://www.eecs.harvard.edu/ssr/projects/progSA/kilobot.html Kilobots]: a low-cost robot for swarm robotics
  +
  +
  +
  +
[[Category:Artificial Life]]
  +
[[Category:Robotics]]
  +
[[Category:Computational intelligence]]

Revision as of 15:08, 9 January 2014

Swarm robotics studies how to design large groups 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. Such principles promote the realization of systems that are fault tolerant, 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 be profitably tackled using swarm robotics are demining, search and rescue, planetary or underwater exploration, and surveillance.

Origins

Swarm robotics has its origins in swarm intelligence and, in fact, could be defined as "embodied swarm intelligence". Initially, the main focus of swarm robotics research was to study and validate biological research (Beni, 2005). Collaboration between roboticists and biologists was vital to make swarm robotics a relevant research field. However, in recent years the focus of swarm robotics has been shifting: from a bio-inspired field of robotics, swarm robotics is becoming more and more an engineering field whose focus is on the development of tools and methods to solve real problems (Brambilla et al., 2013).

Characteristics of swarm robotics

A robot swarm is a type of multi-robot system characterized by being a 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 emerges from the interactions of each individual robot with its neighboring peers and with the environment. Typically, a robot swarm is composed of homogeneous robots, but examples of heterogeneous robot swarms exist (Dorigo et al., 2013).

Desirable properties of swarm robotics systems

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

Swarm robotics promotes the development of systems that are able to cope well with the failure of one or more of its individuals: the loss of individuals does not imply the failure of the whole swarm. Fault tolerance is enabled by the high redundancy of the swarm: the swarm does not rely on any centralized control entity, leaders, or any individual robot playing a predefined role.

Swarm robotics promotes also the development of systems that are able to cope well with changes in their group size: ideally, the introduction or removal of individuals does not cause a drastic change in the performance of the swarm. Scalability is enabled by local sensing and communication: provided that the introduction and removal of robots does not dramatically modify the density of the robots, each individual robot will keep interacting with approximately the same number of peers, those that are in its sensing and communication range.

Finally, swarm robotics promotes the development of systems that are able to deal with a broad spectrum of environments and operating conditions. Flexibility is enabled by the distributed and self-organized nature of a robot swarm: in a swarm, robots dynamically allocate themselves to different tasks to match the requirements of the specific environment and operating conditions; moreover, robots operate on the basis of local sensing and communication without the need of pre-existing infrastructures and of global information on the environment.

Potential applications of swarm robotics

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

The use of robots for tackling dangerous tasks is clearly appealing as it eliminates or reduces risks for humans. The dangerous nature of these tasks implies a high risk of losing robots. Therefore, a fault-tolerant approach is required, making dangerous tasks an ideal field of application for robot swarms. Example of dangerous tasks that could be tackled using robot swarms are demining, search and rescue, and toxic cleaning.

Other potential applications for robot swarms are those in which it is difficult or even impossible to estimate in advance the resources needed to accomplish the task. For instance, allocating resources to manage an oil leak can be very hard because it is often difficult to estimate the oil output and to foresee its development. In these cases, a solution is needed that is scalable and flexible. A robot swarm could be an appealing solution: robots can be added or removed in time to provide the appropriate amount of resources and meet the requirements of the specific task. Example of tasks that might require an a priori unknown amount of resources are search and rescue, transportation of large objects, tracking, and cleaning.

Another potential field of application for swarm robotics are tasks that have to be accomplished in large or unstructured environments, in which there is no available infrastructure that can be used to control the robots - e.g., no available communication network or global localization system. Robot swarms could be employed for such applications because they are able to act autonomously without the need of any infrastructure or any form of external coordination. Examples of tasks in unstructured and large environments are planetary or underwater exploration, surveillance, demining, cleaning, and search and rescue.

Some environments might change rapidly over time. For instance, in a post earthquake situation, buildings might collapse changing the layout of the environment and creating new hazards. In these cases, it is necessary to adopt solutions that are flexible and can react fast to events. Swarm robotics could be used to develop flexible systems that can rapidly adapt to new operating conditions. Example of tasks in environments that change over time are patrolling, disaster recovery, search and rescue, cleaning.

Scientific implications of swarm robotics

Beside being relevant to engineering applications, swarm robotics is also a valuable scientific tool. Indeed, several models 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 also been used to investigate, via controlled experiments, the conditions under which some complex social behaviors might result out of an evolutionary process. For example, robot swarms have been used to study the evolution of communication (Mitri et al., 2009) and collective decision making (Halloy et al., 2007).

Current research axes

In this section, we present the main research axes of the current research in swarm robotics. We follow the taxonomy presented in Brambilla et al. (2013).

Design

The design of a robot swarm is a difficult endeavor: requirements are usually expressed at the collective level, but, eventually, the designer 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 and automatic design.

In manual design, the designer follows a trial-and-error process in which the behaviors of the individual robot are developed, tested and improved until the desired collective behavior is obtained. The software architecture that is most commonly adopted in swarm robotics is the probabilistic finite state machine. Probabilistic finite state machines have been used to obtain several collective behaviors, including aggregation (Soysal and Sahin, 2005), chain formation (Nouyan et al., 2009), and task allocation (Liu and Winfield, 2010). Another common approach is based on virtual physics. In this approach, robots and environment interact through virtual forces. This approach is particularly suited for spatially organizing collective behaviors, such as pattern formation (Spears et al. 2004) and collective motion (Ferrante et al., 2012). Currently, the main limit of manual design is that it completely relies on the ingenuity and expertise of the human designer: designing a robot swarm is more of an art than a science. A systematic and general way to design robot swarms is still missing, even though a few preliminary proposals have been made (Hamann and Worn, 2008; Berman et al., 2011; Brambilla et al., 2012).

In swarm robotics, automatic design has been mostly performed using the evolutionary robotics approach (Nolfi and Floreano, 2004). Typically, individual robots are controlled by a neural network whose parameters are obtained via artificial evolution (Trianni and Nolfi, 2011). Evolutionary robotics has been used to develop several collective behaviors including collective transport (Groß and Dorigo, 2008) and development of communication networks (Huaert et al., 2008). One of the main limits of evolutionary robotics is that it is often difficult to define all the elements of the evolutionary process that will produce control software that allows the robot swarm to effectively accomplish the given task.

Analysis

The analysis of a robot swarm usually relies on models. A model of a robot swarm can be realized at two levels: the microscopic level, that is modeling the behaviors of the individual robots; or the macroscopic level, that is modeling the collective behavior of the swarm.

Modeling the microscopic level allows one to represent in a detailed way the actions of all the individual robots composing the swarm. Unfortunately, microscopic modeling is problematic due to the large number of robots involved. Often, microscopic modeling relies on computer-based simulations (Kramer and Scheutz, 2007; Pinciroli et al., 2012).

Macroscopic models avoid the complexity and scalability issues of having to model each individual robot by considering only the collective behavior of the swarm. One of the most common macroscopic modeling approaches is the use of rate or differential equations (Martinoli et al., 2004; Lerman et al., 2005). Rate equations describe the time evolution of the ratio of robots in a particular state, that is, of robots that are performing a specific action or are in a specific area of the environment. Rate equations have been used to model many collective behaviors, including object clustering (Martinoli et al., 1999) and adaptive foraging (Liu and Winfield, 2010). Another common approach is the use of Markov chains, which allow researchers to formally verify properties of a robot swarm (Dixon et al., 2011; Konur et al., 2012; 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).

A hybrid way of modeling robot swarms is based on Fokker-Plank and Langevin equations (Hamann and Worn, 2008; Berman et al., 2009; Prorok et al., 2011). Using these equations, one can 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.

Collective behaviors

A large part of the research effort in swarm robotics is directed towards the study of collective behaviors. Collective behaviors can be categorized into five main groups: spatially organizing behaviors, navigation behaviors, decision-making behaviors, human interaction behaviors, and other behaviors.

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

Navigation behaviors focus on how to coordinate the movement of a robot swarm. Examples of such behaviors are collective exploration (Ducatelle et al., 2014), collective motion (Turgut et al., 2008), and collective transport (Baldassarre et al., 2006).

Collective decision-making focuses on how robots influence each other in making decisions. In particular, collective decision-making can be used to achieve consensus on a single alternative (Garnier et al., 2005; Campo et al. 2011) or allocation to different alternatives (Pini et al., 2011).

Human-swarm interaction focus on how a human operator can control a swarm and receive feedback information from it. For example, robots can distributedly recognize the gestures of human operator (Giusti et al., 2012) or form groups based on visual and vocal inputs (Pourmehr et al., 2013).

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

Open issues

Despite its potential to promote robustness, scalability and flexibility, swarm robotics has yet to be adopted for solving real-world problems. This is possibly due to the hardware limitations of the currently available robots, to the lack of effective ways to let a human operator interact with a robot swarm and to the lack of an engineering approach for swarm robotics. A further issue is the lack of any compelling demonstrators for outdoor swarm robotic systems (e.g., waste collection), and the lack of any business case or business model that demonstrates that the swarm robotics approach would be more cost effective than other approaches. In particular, the main open issues are the lack of a general methodology for designing robot swarms, the lack of well defined metrics and testbed to assess their performance, and the lack of formal ways to verify and guarantee their properties. __AUTOLINKER{0}

References

G. Baldassarre, D. Parisi, and S. Nolfi. Distributed coordination of simulated robots based on self-organization. Artificial Life, 12(3):289–311, 2006.

G. Beni. From swarm intelligence to swarm robotics. In Swarm Robotics, LNCS 3342, pp. 1-9, 2005. Springer.

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. IEEE press.

M. Brambilla, C. Pinciroli, M. Birattari, and M. Dorigo. Property-driven design for swarm robotics. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp 139–146, 2012. IFAAMAS press.

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. Campo, S. Garnier, O. Dédriche, M. Zekkri & M. Dorigo (2011). Self-organized discrimination of resources. PLOS One, 6(5): e19888.

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. F. T. Winfield, M. Fisher, and C. Zheng. Towards Temporal Verification of Swarm Robotic Systems. Robotics and Autonomous Systems, 60(11):1429-1441, 2012.

M. Dorigo, D. Floreano, L. M. Gambardella, F. Mondada, S. Nolfi, T. Baaboura, M. Birattari, M. Bonani, M. Brambilla, A. Brutschy, D. Burnier, A. Campo, A. L. Christensen, A. Decugniere, G. Di Caro, F. Ducatelle, E. Ferrante, A. Forster, J. Martinez Gonzales, J. Guzzi, V. Longchamp, S. Magnenat, N. Mathews, M. Montes de Oca, R. O'Grady, C. Pinciroli, G. Pini, P. Retornaz, J. Roberts, V. Sperati, T. Stirling, A. Stranieri, T. Stutzle, V. Trianni, E. Tuci, A.E. Turgut, F. Vaussard. Swarmanoid: A Novel Concept for the Study of Heterogeneous Robotic Swarms. IEEE Robotics & Automation Magazine, 20(4):60-71, 2013.

F. Ducatelle, G. A. Di Caro, C. Pinciroli, F. Mondada, and L. M. Gambardella. Cooperative navigation in robotic swarms. Swarm Intelligence, 8(1):in press, 2014.

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.

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 Advances in Artificial Life, LNAI 3630, pp. 169–178, 2005. Springer.

A. Giusti, J. Nagi, L. Gambardella, S. Bonardi, and G. A. Di Caro. Human-Swarm Interaction through Distributed Cooperative Gesture Recognition. 7th ACM/IEEE International Conference on Human-Robot Interaction (Video Session), 2012.

J. Halloy, G. Sempo, G. Caprari, C. Rivault, M. Asadpour, F. Tâche, I. Said, V. Durier, S. Canonge, J.M. Amé, C. Detrain, N. Correll, A. Martinoli, F. Mondada, R. Siegwart, J.-L. Deneubourg. Social integration of robots into groups of cockroaches to control self-organized choices. Science, 318(5853):1155–1158, 2007.

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.

S. Hauert, J.-C. Zufferey, and D. Floreano. Evolved swarming without positioning information: an application in aerial communication relay. Autonomous Robots, 26(1):21–32, 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.

S. Konur, C. Dixon, and M. Fisher. Analysing robot swarm behaviour via probabilistic model checking. Robotics and Autonomous Systems, 60(2):199–213, 2012.

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 Swarm Robotics, LNCS 3342, pp 143–152, 2005. Springer.

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. A Macroscopic Probabilistic Model for Collective Foraging with Adaptation. International Journal of Robotics Research, 29(14):1743-1760, 2010.

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. Martinoli, A. J. Ijspeert, and F. Mondada. Understanding collective aggregation mechanisms: from probabilistic modelling to experiments with real robots. Robotics and Autonomous Systems, 29(1):51– 63, 1999.

A. Martinoli, K. Easton, and W. Agassounon. Modeling swarm robotic systems: a case study in collaborative distributed manipulation. The International Journal of Robotics Research, 23(4–5):415–436, 2004.

S. Mitri, D. Floreano, and L. Keller. The evolution of information suppression in communicating robots with conflicting interests. PNAS, 106(37):15786-15790, 2009.

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), pp. 255–260, 2008. IEEE press.

S. Nolfi and D. Floreano. Evolutionary robotics: intelligent robots and autonomous agents. 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. A. 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. Frison, A. Roli, M. Dorigo, and M. Birattari. Task partitioning in swarms of robots: An adaptive method for strategy selection. Swarm Intelligence, 5(3-4):283-304, 2011.

S. Pourmehr, V. M. Monajjemi, R. T. Vaughan, and G. Mori. "You two! Take off!": Creating, modifying and commanding groups of robots using face engagement and indirect speech in voice commands. In Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), 2013. IEEE press.

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 (SIS), pp. 325–332, 2005. IEEE press.

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 and S. Nolfi. Engineering the evolution of self-organizing behaviors in swarm robotics: A case study. Artificial Life, 17(3):183–202, 2011.

A. E. Turgut, H. Çelikkanat, F. Gökçe, and E. Ṣahin. Self-organized flocking in mobile robot swarms. Swarm Intelligence, 2(2–4): 97–120, 2008.

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. IEEE press.

External links