Mechanisms for environments in multi-agent systems: Survey and opportunities <s> Overlay data structures <s> Pervasive computing calls for suitable middleware and programming models to deal with large software systems dived in dynamic mobile network environments. Here we present the programming model of TOTA ("tuples on the air"), a middleware for supporting adaptive context-aware activities in pervasive computing scenarios. The key idea in TOTA is to rely on spatially distributed tuples, propagated across a network on the basis of application-specific rules, for both representing contextual information and supporting uncoupled interactions between application components. As shown with the help of a case study scenario, TOTA promotes a simple programming model and can effectively facilitate access to distributed information, navigation in complex networks, and achievement of complex coordination tasks in a fully distributed and adaptive way. <s> BIB001 </s> Mechanisms for environments in multi-agent systems: Survey and opportunities <s> Overlay data structures <s> One of the parade examples of agent coordination through a shared environment is the use of chemical markers, or pheromones, for path planning in insect colonies. We have developed a digital analog of this mechanism that is well suited to problems such as the control of unmanned robotic vehicles, and extended it in novel ways to provide a rich set of tools for robotic control. We introduce the approach, describe the mechanisms we have developed, and summarize the technology's performance in a series of scenarios reflecting military command and control. <s> BIB002
Name: Overlay data structures. Motivations: Need for efficient, expressive contextual information. Constituent atoms: Multiplicity of data spaces to store the overlay data. Creation and maintenance: Protocols to deploy overlay data structure, maintain their intended distribution, and maintain data consistency. Usage: Agents access the overlay data structure to get contextual information. Examples: TOTA BIB001 , UAVs BIB002 , Swarm Linda  Another important class of mechanisms aims at describing the operational context of agents, i.e. the resources and contextual data available for exploitation by agents. Overlay data structures are distributed data structures encoding specific aspects of the operational environment of agents (e.g. resources such as databases available on a grid infrastructure). These overlays are propagated across a network in order to be easily accessible by the agents and to provide context information. They can be accessed piecewise as the application agents visit different places of the distributed environment. That is overlays let agents access the right information at the right location. It is worth mentioning that overlay data structures can also be dynamically spread by an agent in order to represent and 'communicate' its own activities. Two representative examples in this category are pheromone-based and field-based data structures. -Pheromones are overlay data structures that can be deployed across a distributed infrastructure by moving agents. In particular, as agents move across the infrastructure they can store specific data in the place (i.e. part of the distributed infrastructure) in which they are actually located. Following this approach, the overlay is deployed according to the agents motion patterns. -Fields are overlay data structures that can be deployed across a networked distributed infrastructure. Agents can instantiate fields that propagate over the topology of the environment. Fields can embed specific propagation rules prescribing how they should spread. Following this approach, the overlay is deployed according to the field propagation rules. While pheromones are constrained to the agent motion pattern, fields can propagate independently. Both mechanisms allow agents to enrich their environment with information that can be used to gather context information or to coordinate with each other. Stigmergic systems exemplify such coordination cases  . The constituent atoms consist of multiple data repositories to store information in a decentralized way. Creation and maintenance refer to the deployment of data in the repositories and maintenance algorithms to keep the data consistent and updated. The usage is the access by agents to the repositories depending on their activities. Interesting examples of this mechanism are those relying on distributed data structures implementing pheromone approaches  BIB002 . Agents perceive pheromones produced and deposited by others in the environment. The pheromones belong to an overlay data structure providing contextual information and pointing to specific resources. For example, applications to the simulation of unmanned vehicles show how artificial agents can automatically recognize team members, threats, and mission targets depending on the type of pheromones spread over the overlay data structure. An example of mechanism for the field approach is the TOTA middleware BIB001 . The key idea in TOTA is to rely on spatially distributed tuples, propagated across a network to implement gradient fields on the basis of application-specific rules for representing contextual information. In TOTA, there is no notion of centralized shared tuple space. Instead, tuples can be 'injected' into the network from any node and can propagate and diffuse according to tuple-specific propagation patterns. Agents can sense the distributed tuples and decide how to react. For example, TOTA tuples are used to create fields as data structures to let the agents coordinate their movements by following the gradient of those fields.