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.

• Workshop paper submission: February 15, 2013 extension to February 22, 2013
• Notification of accepted papers: March 8, 2013 March 14, 2013
• Delivery of camera-ready papers (pre-proceedings): March 16, 2013
• AAMAS-2013 Workshops: May 6, 20133

The workshop W9 “Spatial Computing” takes place the Monday Mai 6, 2013.

The workshop notes will be included in the flash drive containing the AAMAS-2013 conference proceedings distributed to AAMAS-2013 registrants in. There is no printed workshop notes.

Registration on the AAMAS web site

1 day Workshop/Tutorial	Student	Regular
Early (by March 27)	$60	$80
Late (by April 20)	$80	$100
Onsite (after April 20)	$90	$110

 

• 09:00 - 10.30 Models I
  • Engineering Confluent Computational Fields: from Functions to Rewrite Rules, Mirko Viroli
  • Declarative Multidimensional Spatial Programming, John Plaice, Jarryd P. Beck and Blanca Mancilla
  • Promoting Space-Aware Coordination: ReSpecT as a Spatial Computing Virtual Machine, Stefano Mariani and Andrea Omicini

• 10:30 - 11:00 coffee break

• 11:00 - 12:30 Algorithms I
  • Modeling Inertia in an Amorphous Computing Medium, Alyssa S. Morgan and Daniel N. Coore
  • Computing Activity in Space, Martin Potier, Antoine Spicher and Olivier Michel
  • Accelerating Approximate Consensus with Self-Organizing Overlays, Jacob Beal

• 12:30 - 1:30 lunch break

• 1:30 - 2:00 Algorithms II
  • AREA: an Automatic Runtime Evolutionary Adaptation mechanism for Creating Self-Adaptation Algorithms in Wireless Networks, Qingzhi Liu, Stefan Dulman and Martijn Warnier

• 2:00 - 3:30 Applications
  • Spatial Computing in an Orbital Environment: An Extrapolation of the Unique Constraints of this Special Case to other Spatial Computing Environments, Jeremy Straub
  • Spatial Programming for Musical Transformations and Harmonization, Louis Bigo, Jean-Louis Giavitto and Antoine Spicher
  • Application of Force-Directed Graphs on Character Positioning, Christine Talbot and G. Michael Youngblood

• 3:30 - 4:00 coffee break

• 4:00 - 5:00 Models II
  • Population Protocols on Graphs: A Hierarchy, Olivier Bournez and Jonas Lefèvre
  • Spatial Computation and Algorithmic Information content in Non-DNA based Molecular Self-Assembly, Germàn Terrazas, Leong Ting Lui and Natalio Krasnogor

• 5:00 - 6:00 Coordination
  • Teams to exploit spatial locality among agents, James Parker and Maria Gini
  • Composing gradients for a context-aware navigation of users in a smart-city, Sara Montagna and Mirko Viroli

• 6:00 - 6:30 Demonstration, Discussion, Farewell

Call for paper (PDF version) Call for paper (text version)

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
• 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

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 the standard IEEE two-column format. All manuscripts should be submitted in PDF form through the submissions system at SCW 2013 at EasyChair.

Papers will be peer reviewed on the basis of originality, readability, relevance to themes, soundness, and overall quality. Workshop pre-proceedings will be published in a bundle with the main conference proceedings. Post-proceedings publication in a journal is planed.

Questions should be addresses to scw13@spatial-computing.org.

• Michel Banatre, INRIA Rennes
• Jacob Beal, BBN Technologies
• Sven Brueckner, Jacobs Technology Inc.
• Nikolaus Correll, Dpt of Computer Science, University of Colorado at Boulder
• Ferruccio Damiani, Dipartimento di Informatica, Università di Torino
• Rene Doursat, Complex Systems Institute, Paris Ile-de-France
• Alexis Drogoul, UMI UMMISCO 209, IRD & UPMC and Can Tho University
• Matt Duckham, University of Melbourne
• Jérôme Durand-Lose, LIFO - University of Orléans
• Nazim Fates, LORIA - INRIA Nancy
• Fred Gruau, LRI U. of Paris South
• Guillaume Hutzler, Evry University
• Taras Kowaliw, ISC-PIF, CNRS
• Luidnel Maignan, LACL University Paris Est
• Olivier Michel, LACL University Paris Est
• Ulrik Schultz, University of Southern Denmark
• Susan Stepney, Dept. of Computer Science, University of York
• Christof Teuscher, Portland State University
• Kyle Usbeck, BBN Technologies
• Danny Weyns, Linnaeus University
• Eiko Yoneki, University of Cambridge Computer Laboratory
• Franco Zambonelli, University of Modena and Reggio Emilia

• Dr. Stefan Dulman (Delft Univ., the Netherlands)
• Dr. Jean-Louis Giavitto (CNRS - IRCAM - UPMC - Inria, France)
• Dr. Antoine Spicher (Univ. Paris Est, France)
• Dr. Mirko Viroli (Univ. of Bologna, Italy)

This workshop is a continuation of a series of workshops on spatial computing previously colocated with SASO. Previous editions of this workshop may be found at the following urls: SCW 2012, SCW 2011, SCW 2010, SCW 2009, SCW 2008.

ACM Transactions on Autonomous and Adaptive Systems (TAAS) Special Issue on Spatial Computing (Volume 6 Issue 2, June 2011) (open post-proceedings SCW 2008 and 2009)

The Computer Journal Special Issue on Spatial Computing (open post-proceedings SCW 2010 and 2011)