Many important science and engineering applications require interpreting data and designing controls for spatially distributed systems. For example, in order to predict the weather, meteorologists utilize massive amounts of pressure, temperature, and wind velocity data collected from spatially distributed sensors. Similarly, in designing aircraft with minimal drag, engineers study wind tunnel and simulation data specifying airflow over a body at many points and over many instants of time. Recent advances in the fabrication of low-cost, large-scale arrays of microelectromechanical systems (MEMS) have enabled the construction of "smart matter" systems that integrate sensing, computation, and actuation at a fine grain.

Interpretation and control tasks for distributed physical systems encounter a number of challenges. Spatial properties (e.g. variations in material property and boundary conditions) make it hard to apply analytic methods to determine closed-form solutions. Data interpretation can be challenged by the massive amount of data, either collected from arrays of sensors or produced by simulations running on fine-grained discretizations. Local methods must aggregate distributed sensor information; global objectives must be achieved by local actuators. In order to overcome these challenges, applications must utilize physical properties such as continuity and locality, which give rise to regions of uniformity in spatially distributed data. The Spatial Aggregation Language (SAL) allows researchers to specify and utilize relevant physical knowledge to uncover abstract descriptions of spatial data. As illustrated above, SAL transforms a numerical input field (such as temperature throughout a room or wind velocity vectors sampled across the country) to successively higher-level descriptions by applying a small set of operators to each layer, given appropriate metrics, neighborhood relations, and equivalence relations. SAL is applicable to a wide range of other problem domains; following are some examples.

Decentralized control design
	Applications such as controlling the temperature distribution over a semiconductor wafer and controlling the noise of a photocopy machine require designing decentralized controllers that achieve a global control objective via local sensing and actuation. For example, in a "local warming" approach to thermal regulation, a set of distributed point heat sources must work together to control the global temperature distribution over a piece of material, but each heat source only affects some local region. We have developed a novel approach to decentralized control design, called influence-based model decomposition, and applied it in the context of thermal regulation. Influence-based model decomposition uses a decentralized model, called an influence graph, as a key data abstraction representing influences of controls on distributed physical fields (e.g. the figure shows the effect of one point heat sources on the thermal field for a P-shaped piece of material). The influence graph serves as the basis for novel algorithms for control placement and parameter design for systems with large numbers of coupled variables. These algorithms exploit physical knowledge of locality, linear superposability, and continuity, encapsulated in influence graphs. [Bailey-Kellogg and Zhao]
Weather data interpretation
	In analyzing spatial data sets such as weather data experts often perceive and reason about these physical fields in terms of abstract spatial objects, also called features or patterns, that evolve and interact with each other. For example, meteorologists identify and explicitly label aggregate weather features such as high/low pressure centers, pressure troughs, thermal packings, fronts, and jet streams. The experts then use weather rules to correlate these features and establish prediction patterns. A SAL approach to weather data interpretation extracts features such as troughs using a multi-level approach. First, the algorithm extracts salient iso-bar segments using an iterative thresholding technique. It builds a neighborhood structure for the segments from a Delaunay triangulation of iso-points. It then classifies the neighborhood relations and uses the strong adjacencies to extract the linear structures among the segments to obtain troughs. [Huang and Zhao]
Diffusion-reaction morphogenesis
	A number of physical, chemical, and biological phenomena can be modeled by diffusion-reaction systems (e.g. the Gray-Scott model of glycolysis). It is important to identify and track coherent structures in spatio-temporal fields for such systems; the study may shed light on how nature constructs and evolves structures that exhibit a high degree of regularity. A SAL approach adaptively samples a spatial field using a particle system, aggregates the sampling particles into a neighborhood graph, classifies the structure into coherent regions, and tracks the regions over time to produce a qualitative description of the temporal evolution of the field. Because the adaptive sampling grid varies smoothly with the temporal evolution of the underlying field, the algorithm is able to efficiently track the corresponding objects over successive time frames by minimally updating the grid. [Ordóñez and Zhao]
Dynamical system analysis
	Spatial Aggregation generalizes KAM [Yip 1991], MAPS [Zhao 1994], and a number of other programs for analyzing nonlinear dynamical systems. According to modern dynamical systems theory, the qualitative behaviors of a nonlinear dynamical system can be described by the geometric features in phase space. Once the appropriate metrics and equivalence relations are defined, SAL can naturally express the operations in analyzing dynamics in phase space, as the trajectory interpretation example has already illustrated. [Zhao]

The C++ version of SAL has grown a bit stale. We are currently porting versions of the code to Java and Matlab. Please contact me (CBK) if you are interested.

• Naren Ramakrishnan (computer science, Virginia Tech)
• Feng Zhao (embedded collaborative computing area, PARC)