Spatial Computing Workshop 2013
Saint Paul, Minnesota, USA, 06/05/2013
Many self-organizing or self-adaptive multiagent systems are spatial computers – collections of local computational devices distributed through a physical space, in which:
- the difficulty of moving information between any two devices is strongly dependent on the distance between them, and
- the “functional goals” of the system are generally defined in terms of the system’s spatial structure.
In multiagent systems, spatial relationships (location, region, frontier, neighborhood, obstruction, field, basin, communication, diffusion, propagation) are used to organize the interactions between agents where their location is important for the problem. Systems that can be viewed as spatial computers are abundant, both natural and man-made. For example, in wireless sensor networks and animal or robot swarms, inter-agent communication network topologies are determined by the distance between devices, while the agent collectives as a whole solve spatially-defined problems like “analyze and react to spatial temperature variance” or “surround and destroy an enemy”. In biological embryos, each developing cell’s behavior is controlled only by its local chemical and physical environment, but the eventual structure of the organism is a global property of the cellular arrangement. Moreover, a variety of successful established techniques for self-organization and self-adaptation arise from explicitly spatial metaphors, e.g., self-healing gradients.
On the other hand, not all spatially distributed systems are spatial computers. The Internet and peer-to-peer overlay networks may not in general best be considered as spatial computers, both because their communication graphs have little relation to the Euclidean geometry in which the participating devices are embedded, and because most applications for them are explicitly defined independent of network structure. Spatial computers, in contrast, tend to have more structure, with specific constraints and capabilities that can be used in the design and analysis of algorithms.
The goal of this workshop is to explicitly identify the idea of spatial computing as a theme in multi agent systems and in self-organizing and self-adaptive systems, and further to develop the study of spatial computation as a subject in its own right. We believe that progress towards identifying common principles, techniques, and research directions – and consolidating the substantial progress that is already being made – will benefit all of the fields in which spatial computing takes place. And, as the impact of spatial computing is recognized in many areas, we hope to set up frameworks to ensure portability and cross-fertilization between solutions in the various domains.
topics of interest
- Languages for programming spatial computers and describing spatial tasks and patterns
- Methods for compiling global programs to local rules that produce the desired global effect
- Relationships between agent interaction and spatial organizations
- Theoretical and practical limitations arising from spatial properties
- Characterization of spatial self-organization phenomena as algorithmic building blocks
- Characterization of error in spatial computers (e.g., error from approximating continuous space with networks of devices)
- Analysis of tradeoffs between system parameters (e.g., communication radius vs. device memory consumption)
- Studies of the relationship between time, propagation of information through the spatial computer, and computational complexity
- Application of spatial computing principles to novel areas, or generalization of area-specific techniques
- Device motion in spatial computing algorithms (e.g. the relationship between robot speed and gradient accuracy in multi-robot swarms)
- Theoretical and empirical analysis of spatial applications
hosting event
works as
origin event for publication
hosting event for talk
hosted event for
Promoting Space-Aware Coordination: ReSpecT as a Spatial-Computing Virtual Machine (paper in proceedings, 2013) — Stefano Mariani, Andrea Omicini
Promoting Space-Aware Coordination: ReSpecT as a Spatial-Computing Virtual Machine (SCW 2013@AAMAS 2013, 06/05/2013) — Stefano Mariani (Stefano Mariani, Andrea Omicini)