Many self-organizing or self-adaptive 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.
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.”
Similarly, in reconfigurable microchip platforms, moving data between adjacent logic blocks is much faster than moving it across the chip, which in turn favors problems with spatial structure like stream processing. 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 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.
We are soliciting submissions on any aspect of spatial computing. Examples of topics of interest include, but are by no means limited to:
- 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
- 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)
We encourage authors to submit papers in one of two formats: (1) Papers that develop “unifying” principles or techniques in spatial computing – these papers should be suitable in format and quality for a conference track, but avoid incrementalism. (2) Papers that demonstrate how a technique or problem from a specific area of application can usefully be generalized – these papers should be a combination of review paper and position paper, presenting the material from one area in a form comprehensible to researchers of another area, as well as a coherent technical argument generalizing the material to other areas. Although our interests are broad, we discourage authors from submitting reviews of particular application areas unless the paper explicitly connects the material to the larger technical issues of spatial computing.
Papers should be no longer than 6 pages in standard IEEE two-column format. All manuscripts should be submitted in PDF form to firstname.lastname@example.org.
Please direct all questions to email@example.com.
Workshop proceedings will be published and archived by the IEEE.
July 4, 2011July 11, 2011: Submission deadline July 25, 2011August 6th: Acceptance notification August 18, 2011: Early registration deadline August 25, 2011: Camera ready version of accepted papers
- October 3, 2011: Workshop held at IEEE SASO in Ann Arbor, Michigan, USA.
08:30 → 09:15 Registration
09:15 → 09:30 Presentation of the workshop - Organisers
09:30 → 10:00 On the Evaluation of Space-Time Functions - Jacob Beal and Kyle Usbeck (talk)
10:00 → 10:30 Rekindling Parallelism - Frédéric Gruau and Fabien Michel (talk)
10:30 → 11:00 Spatial Computers for Emergency Management - Avgoustinos Filippoupolitis, Gokce Gorbil and Erol Gelenbe
11:00 → 11:30 Coffee break
11:30 → 12:00 Convex Hulls on Cellular Spaces: Spatial Computing on Cellular Automata - Luidnel Maignan and Frederic Gruau
12:00 → 13:00 Demos
- Stefan Dulman - ASH virtual node algorithm
- Glenn Fink - Digital ants for cyber-security
- Thomas Schmickl - Hormone robotics
- Frederic Gruau - homogenization processes
- Jean-Louis Giavitto - MGS
- Sven Breuckner - PolyAgents
- Jacob Beal - Proto BioCompiler
13:00 → 14:00 Lunch break
14:00 → 14:30 Spatial Sorting Algorithms for Parallel Computing in Networks - Max OrHai and Christof Teuscher (talk)
14:30 → 15:00 State Space Exploration of Spatially Organize Populations of Agents - Antoine Dautriche, Jean-Louis Giavitto, Hanna Klaudel and Franck Pommereau
15:30 → 16:00 Coffee break
16:00 → 16:30 Using Morphogenetic Models to Develop Spatial Structures - Jacob Beal, Jessica Lowell, Annan Mozeika and Kyle Usbeck (talk in pdf and ppt)
16:30 → 17:00 Homeostatic Architectures for Robust Spatial Computing - David H. Ackley and Lance R. Williams (talk)
17:00 → 17:30 Open discussions
- Dr. Jacob Beal (BBN Technologies, USA)
- Dr. Stefan Dulman (Delft Univ., the Netherlands)
- Prof. Olivier Michel (Univ. Paris Est, France)
- Dr. Antoine Spicher (Univ. Paris Est, France)
- Dr. Michel Banatre (Inria, France)
- Prof. Cristian Borcea (New Jersey Institute of Technology, USA)
- Dr. Sven Brueckner (Vector Research Center, USA)
- Dr. Nikolaus Correll (University of Colorado Boulder, USA)
- Prof. Shlomi Dolev (Ben-Gurion University of the Negev)
- Prof. Jerome Durand-Lose (Universite d'Orleans)
- Dr. Jean-Louis Giavitto (Institut de Recherche Coordonnée Acoustique Musique)
- Prof. Frederic Gruau (University Paris Sud)
- Prof. David Hales (University of Bologna, Italy)
- Prof. Márk Jelasity (Hungarian Academy of Sciences and University of Szeged, Hungary)
- Dr. Luidnel Maignan (INRIA Saclay, France)
- Ulrik Pagh Schultz (University of Southern Denmark)
- Prof. Christof Teuscher (Portland State University)
- Kyle Usbeck (BBN Technologies)
- Dr. Danny Weyns (K.U.Leuven, Belgium)
- Dr. Eiko Yoneki (University of Cambridge, UK)
- Prof. Franco Zambonelli (Universita di Modena)