Robot Swarm Design Patterns

Information Storage

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 depositing information into their environments and retrieving it, for example to drop, update and read RFID tags (Drogoul and Ferber, 1993; Hrolenok et al., 2010), deposit and sense chemicals (Mayet et al., 2010; Fujisawa et al., 2014), or store and read "virtual pheromone" maintained by stationary robots (Hoff et al., 2010; Ducatelle et al., 2011) or by an external server (Sugawara et al., 2004; Kazama et al., 2005).

Solution:

A robot scouts for worksites in the environment. Additionally, it can adopt information about a worksite if it finds a data storage device containing information ("Worksite data ext."), and if a boolean adoption function, a, returns true. Once a robot discovers information about a worksite either as a result of scouting or when finding a data storage device, it begins work. The robot’s internal data structure is used and updated with information stored in the environment while the robot works, based on a. An informed robot deposits information about its worksite into data storage device(s) when appropriate.

BDRML representation of the Information Storage design pattern.

Feedback Loops:

Depositing information in the environment acts as a positive feedback loop that can be regulated via the pattern’s parameters. Additionally, a negative feedback loop can be created by applying the update relation to "Worksite data ext.".

Parameters:

• Deposit function, d: A boolean function that determines whether a robot deposits information into an external data structure. For example, a robot might deposit a chemical trail any time it is traveling between a worksite and the base (Mayet et al., 2010; Fujisawa et al., 2014). In other cases, a robot might decide to drop an RFID tag into the environment based on a perceived density of RFID tags nearby (Hrolenok et al., 2010).
• Adoption function, a: A boolean function that determines whether a robot copies information that it finds in a data storage device into its own internal data structure. For example, a robot might only adopt external data when it does not have any worksite information, or when the external data is more up-to-date (Hecker and Moses, 2015).
• Decay function, y: A function according to which information in the data storage device(s) is updated. For example, if "Worksite data ext." stores a vector towards a worksite location, y can determine how up-to-date the information is (Hecker and Moses, 2015). On the other hand, if ‘Worksite data ext." is a real number, as is often the case in pheromone-inspired algorithms, y can define how the real value "evaporates" over time (Hrolenok et al., 2010; Fujisawa et al., 2014).
• Detection range: A range at which a robot can find storage devices.

Forces:

• The decay function affects how long the information about worksites remains available in each storage device, i.e., the life span of the stored information. The function therefore must consider dynamics of the environment. An information life span that is too long causes robots to get recruited to depleted worksites and incur high misinformation cost, while a very short information life span prevents robots from utilising the stored information (Drogoul and Ferber, 1993; Garnier et al., 2007).

Consequences:

• Information about worksites is more easily accessible to uninformed robots. Information gain rate depends on the probability of robots to detect the information storage devices, but not on the probability of robots to meet each other (Pitonakova et al., 2018).
• Causes robots to incur displacement and misinformation costs, as a result of recruitment to worksites. The extent of these costs increases with an increasing robot density as a result of congestion (Drogoul and Ferber, 1993; Parker, 1995; Hoff et al., 2010).
• Can lead to the spread of erroneous information through the swarm, e.g., when a depositing robot’s worksite information is incorrect due to sensory-motor noise (Hecker et al., 2012).

Known Uses:

Often used for studying ant-inspired central-place foraging behaviour (Beekman et al., 2001), where "pheromone" trails are formed between the robot base and worksites, helping the robots to navigate an unknown environment (Drogoul and Ferber, 1993; Sugawara et al., 2004; Kazama et al., 2005; Hoff et al., 2010; Hrolenok et al., 2010; Mayet et al., 2010; Ducatelle et al., 2011; Fujisawa et al., 2014). Has also been used for robot recruitment in a cooperative transportation task (Amato et al., 2015).

Related Patterns:

Depending on the type of storage device used, the pattern can either be combined with the Information Exchange Anywhere pattern, in order to form pheromone trails made of RFID tags (Drogoul and Ferber, 1993; Hrolenok et al., 2010), chemicals (Mayet et al., 2010; Fujisawa et al., 2014) or by other means (Sugawara et al., 2004; Kazama et al., 2005; Hoff et al., 2010; Ducatelle et al., 2011), or with the Information Exchange Centre pattern, in order to store information about worksites in the robot base (Alers et al., 2011; Amato et al., 2015; Hecker and Moses, 2015).

Other related patterns include "Evaporation" (Gardelli et al., 2007; Fernandez-Marquez et al., 2013), "Diffusion" (Gardelli et al., 2007), "Gradient", "Digital pheromone" and "Ant foraging" (Fernandez-Marquez et al., 2013)