Robot Swarm Design Patterns

 

Design Pattern Catalogue


Broadcaster

Category:

Information Transmitter pattern

Problem:


Robots need to find and exploit worksites as quickly as possible, but the task characteristics (e.g., robot or worksite density) make it difficult for robots to discover worksites.

Applicability:


Robots are capable of directly communicating with each other (as in, e.g., Wawerla and Vaughan, 2010; Ducatelle et al., 2014; Pitonakova et al., 2018).

Solution:


A robot scouts for worksites in the environment. A successful scout stores information about its worksite, such as its location, in an internal data structure ("Worksite data int."), and begins work. The data structure may be updated and used periodically while the robot works. A robot that is engaged in the "Work" behaviour may send information about its worksite to another robot, provided that a boolean recruitment function, r, returns true. When a robot receives worksite data in this way, it stores it in its own internal data structure and transitions from the "Scout" to the "Work" behaviour, provided that a boolean adoption function, a, returns true.

BDRML representation of the Broadcaster design pattern.BDRML representation of the Broadcaster design pattern.

Feedback Loops:


Sharing of worksite information represents a positive feedback loop that can be regulated via the pattern’s parameters.

Parameters:


  • Recruitment function, r: A boolean function that determines whether the robot decides to recruit another robot. For example, a robot might decide to recruit with a certain probability every time it encounters another robot.
  • Adoption function, a: A boolean function that determines whether a scout transitions to the "Work" behaviour after receiving worksite information. For example, a robot might prefer worksites from a certain area only.
  • Robot communication range: A range at which robots can communicate with one another


Forces:


  • A sufficient communication range must be available in order for recruitment to take place, depending on the worksite and robot density (Sugawara and Watanabe, 2002).
  • A larger communication range causes a higher information gain rate, but can also increase displacement and misinformation costs incurred by recruited robots, consequently decreasing the swarm performance (Sugawara and Watanabe, 2002; Valdastri et al., 2006; Rybski et al., 2007; Pitonakova et al., 2016a).


Consequences:


  • Information about worksites is more easily accessible to uninformed robots (Sugawara and Watanabe, 2002; Rybski et al., 2007; Sarker and Dahl, 2011)
  • Information is carried and transmitted by robots, meaning that the information gain rate depends on the probability of robots meeting each other, i.e., on their movement algorithm and on the structure of the environment (Pitonakova et al., 2018)
  • Causes the robots to incur displacement cost, associated with traveling to worksites after being recruited (Pitonakova et al., 2018)
  • Increases the probability of incurring misinformation cost, as a result of outdated information potentially being spread across the swarm (Gardelli et al., 2007; Fernandez-Marquez et al., 2013; Pitonakova et al., 2018)
  • Can lead to the spread of erroneous information among robots, e.g., when a recruiter’s worksite information is incorrect due to sensory-motor noise (Pitonakova et al., 2014)


Known Uses:


Often used to implement local communication of robot state (Balch and Arkin, 1994; Parker, 1995; Dahl, 2002; Sugawara and Watanabe, 2002; Rybski et al., 2007), worksite location (Balch and Arkin, 1994; Parker, 1995; Valdastri et al., 2006; Wawerla and Vaughan, 2010; Sarker and Dahl, 2011; Amato et al., 2015; Pitonakova et al., 2018) and worksite urgency (Sarker and Dahl, 2011). It has been used in tasks like general (Balch and Arkin, 1994; Pitonakova et al., 2018) and central-place (Parker, 1995; Valdastri et al., 2006; Rybski et al., 2007; Pitonakova et al., 2018) foraging, cooperative transportation (Sugawara and Watanabe, 2002; Amato et al., 2015), package delivery (Wawerla and Vaughan, 2010) and task allocation (Sarker and Dahl, 2011).

Related Patterns:


The pattern can be combined with the Information Exchange Anywhere pattern to make robots exchange information at any time they meet in the foraging arena (Gutiérrez et al., 2010; Fraga et al., 2011). When combined with Information Exchange near Worksites pattern, a behaviour similar to that of sheep (Michelena et al., 2010) and fish (Lachlan et al., 1998) is obtained, where robots that are currently obtaining reward from worksites attract nearby robots, effectively increasing the worksite detection range (e.g., as in Wawerla and Vaughan, 2010; Ducatelle et al., 2014; Pitonakova et al., 2018). Finally, bee-inspired recruitment (Seeley et al., 1991), that involves communication in the base, can be obtained by combining the Broadcaster and the Information Exchange Centre pattern (e.g., as in Parker, 1995; Krieger and Billeter, 2000; Pitonakova et al., 2018).

Other related patterns include "Diffusion" (Gardelli et al., 2007) and "Spreading" (Fernandez-Marquez et al., 2013).