Publications

The goal of this project was to develop a risk analysis meta tool--a tool that enables security analysts both to combine and analyze data from multiple other risk assessment tools on demand. Our approach was based on the innovative self-assembling software technology under development by the project team. This technology provides a mechanism for the user to specify his intentions at a very high level (e.g., equations or English-like text), and then the code self-assembles itself, taking care of the implementation details. The first version of the meta tool focused specifically in importing and analyzing data from Joint Conflict and Tactical Simulation (JCATS) force-on-force simulation. We discuss the problem, our approach, technical risk, and accomplishments on this project, and outline next steps to be addressed with follow-on funding.

Biochemical reactions taking place in living systems that map different inputs to specific outputs are intuitively recognized as performing information processing. Conventional wisdom distinguishes such proteins, whose primary function is to transfer and process information, from proteins that perform the vast majority of the construction, maintenance, and actuation tasks of the cell (assembling and disassembling macromolecular structures, producing movement, and synthesizing and degrading molecules). In this paper, we examine the computing capabilities of biological processes in the context of the formal model of computing known as the random access machine (RAM) [Dewdney AK (1993) The New Turing Omnibus. Computer Science Press, New York], which is equivalent to a Turing machine [Minsky ML (1967) Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, NJ]. When viewed from the RAM perspective, we observe that many of these dynamic self-assembly processes - synthesis, degradation, assembly, movement - do carry out computational operations. We also show that the same computing model is applicable at other hierarchical levels of biological systems (e.g., cellular or organism networks as well as molecular networks). We present stochastic simulations of idealized protein networks designed explicitly to carry out a numeric calculation. We explore the reliability of such computations and discuss error-correction strategies (algorithms) employed by living systems. Finally, we discuss some real examples of dynamic self-assembly processes that occur in living systems, and describe the RAM computer programs they implement. Thus, by viewing the processes of living systems from the RAM perspective, a far greater fraction of these processes can be understood as computing than has been previously recognized. © Springer Science+Business Media, Inc. 2006.

The brain is often identified with decision-making processes in the biological world. In fact, single cells, single macromolecules (proteins) and populations of molecules also make simple decisions. These decision processes are essential to survival and to the biological self-assembly and self-repair processes that we seek to emulate. How do these tiny systems make effective decisions? How do they make decisions in concert with a cooperative network of other molecules or cells? How can we emulate the decision-making behaviors of small-scale biological systems to program and self-assemble microsystems? This LDRD supported research to answer these questions. Our work included modeling and simulation of protein populations to help us understand, mimic, and categorize molecular decision-making mechanisms that nonequilibrium systems can exhibit. This work is an early step towards mimicking such nanoscale and microscale biomolecular decision-making processes in inorganic systems.

Intracellular molecular machines synthesize molecules, tear apart others, transport materials, transform energy into different forms, and carry out a host of other coordinated processes. Many molecular processes have been shown to work outside of cells, and the idea of harnessing these molecular machines to build nanostructures is attractive. Two examples are microtubules and motor proteins, which aid cell movement, help determine cell shape and internal structure, and transport vesicles and organelles within the cell. These molecular machines work in a stochastic, noisy fashion: microtubules switch randomly between growing and shrinking in a process known as dynamic instability; motor protein movement along microtubules is randomly interrupted by the motor proteins falling off. A common strategy in attempting to gain control over these highly dynamic, stochastic processes is to eliminate some processes (e.g., work with stabilized microtubules) in order to focus on others (interaction of microtubules with motor proteins). In this paper, we illustrate a different strategy for building nanostructures, which, rather than attempting to control or eliminate some dynamic processes, uses them to advantage in building nanostructures. Specifically, using stochastic agent-based simulations, we show how the natural dynamic instability of microtubules can be harnessed in building nanostructures, and discuss strategies for ensuring that 'unreliable' stochastic processes yield a robust outcome.

We present two ways in which dynamic self-assembly can be used to perform computation, via stochastic protein networks and self-assembling software. We describe our protein-emulating agent-based simulation infrastructure, which is used for both types of computations, and the few agent properties sufficient for dynamic self-assembly. Examples of protein-network-based computation and self-assembling software are presented. We describe some novel capabilities that are enabled by the inherently dynamic nature of the self-assembling executable code. © Springer-Verlag 2004.

We have made progress in developing a new statistical mechanics approach to designing self organizing systems that is unique to SNL. The primary application target for this ongoing research has been the development of new kinds of nanoscale components and hardware systems. However, this research also enables an out of the box connection to the field of software development. With appropriate modification, the collective behavior physics ideas for enabling simple hardware components to self organize may also provide design methods for a new class of software modules. Our current physics simulations suggest that populations of these special software components would be able to self assemble into a variety of much larger and more complex software systems. If successful, this would provide a radical (disruptive technology) path to developing complex, high reliability software unlike any known today. This high risk, high payoff opportunity does not fit well into existing SNL funding categories, as it is well outside of the mainstreams of both conventional software development practices and the nanoscience research area that spawned it. This LDRD effort was aimed at developing and extending the capabilities of self organizing/assembling software systems, and to demonstrate the unique capabilities and advantages of this radical new approach for software development.

We describe stochastic agent-based simulations of protein-emulating agents to perform computation via dynamic self-assembly. The binding and actuation properties of the types of agents required to construct a RAM machine (equivalent to a Turing machine) are described. We present an example computation and describe the molecular biology and non-equilibrium statistical mechanics, and information science properties of this system.

We are currently exploring and developing a new statistical mechanics approach to designing self organizing and self assembling systems that is unique to SNL. The primary application target for this ongoing research is the development of new kinds of nanoscale components and hardware systems. However, a surprising out of the box connection to software development is emerging from this effort. With some amount of modification, the collective behavior physics ideas for enabling simple hardware components to self organize may also provide design methods for a new class of software modules. Large numbers of these relatively small software components, if designed correctly, would be able to self assemble into a variety of much larger and more complex software systems. This self organization process would be steered to yield desired sets of system properties. If successful, this would provide a radical (disruptive technology) path to developing complex, high reliability software unlike any known today. The special work needed to evaluate this high risk, high payoff opportunity does not fit well into existing SNL funding categories, as it is well outside of the mainstreams of both conventional software development practices and the nanoscience research area that spawned it. We proposed a small LDRD effort aimed at appropriately generalizing these collective behavior physics concepts and testing their feasibility for achieving the self organization of large software systems. Our favorable results motivate an expanded effort to fully develop self-organizing software as a new technology.

We present initial results on achieving synthesis of complex software systems via a biophysics-emulating, dynamic self-assembly scheme. This approach offers novel constructs for constructing large hierarchical software systems and reusing parts of them. Sets of software building blocks actively participate in the construction and subsequent modification of the larger-scale programs of which they are a part. The building blocks interact through a software analog of selective protein-protein bonding. Self-assembly generates hierarchical modules (including both data and executables); creates software execution pathways; and concurrently executes code via the formation and release of activity triggering bonds. Hierarchical structuring is enabled through encapsulants that isolate populations of building block binding sites. The encapsulated populations act as larger-scale building blocks for the next hierarchy level. Encapsulant populations are dynamic, as their contents can move in and out. Such movement changes the populations of interacting sites and also modifies the software execution. ''External overrides'', analogous to protein phosphorylation, temporarily switch off undesired subsets of behaviors (code execution, data access/modification) of other structures. This provides a novel abstraction mechanism for code reuse. We present an implemented example of dynamic self-assembly and present several alternative strategies for specifying goals and guiding the self-assembly process.

We present a set of novel design principles to aid in the development of complex collective behaviors in fleets of mobile robots. The key elements are: the use of a graph algorithm that we have created, with certain proven properties, that guarantee scalable local communications for fleets of arbitrary size; the use of artificial forces to simplify the design of motion control; the use of certain proximity values in the graph algorithm to simplify the sharing of robust navigation and sensor information among the robots. We describe these design elements and present a computer simulation that illustrates the behaviors readily achievable with these design tools.

Abstract not provided.

We present mathematical proofs for two useful properties of the clusters generated by the visual empirical region of influence (VERI) shape. The first proof shows that, for any d-dimensional vector set with more than one distinct vector, that there exists a bounded spherical volume about each vector v which contains all of the vectors that can VERI cluster with v, and that the radius of this d-dimensional volume scales linearly with the nearest neighbor distance to v. We then prove, using only each vector's nearest neighbor as an inhibitor, that there is a single upper bound on the number of VERI clusterings for each vector in any d-dimensional vector set, provided that there are no duplicate vectors. These proofs guarantee significant improvement in VERI algorithm runtimes over the brute force O(N{sup 3}) implementation required for general d-dimensional region of influence implementations and indicate a method for improving approximate O(NlogN) VERI implementations. We also present a related region of influence shape called the VERI bow tie that has been recently used in certain swam intelligence algorithms. We prove that the VERI bow tie produces connected graphs for arbitrary d-dimensional data sets (if the bow tie boundary line is not included in the region of influence). We then prove that the VERI bow tie also produces a bounded number of clusterings for each vector in any d-dimensional vector set, provided that there are no duplicate vectors (and the bow tie boundary line is included in the region of influence).

Important factors in the application of sensing technology to space applications are low mass, small size, and low power. All of these attributes are enabled by the application of MEMS and micro-fabrication technology to micro-sensors. Two types of sensors are utilized in space applications: remotes sensing from orbit around the earth or another planetary body, and point sensing in the spacecraft or external to it. Several Sandia projects that apply microfabrication technologies to the development of new sensing capabilities having the potential for space applications will be briefly described. The Micro-Navigator is a project to develop a MEMS-based device to measure acceleration and rotation in all three axes for local area navigation. The Polychromator project is a joint project with Honeywell and MIT to develop an electrically programmable diffraction grating that can be programmed to synthesize the spectra of molecules. This grating will be used as the reference cell in a gas correlation radiometer to enable remote chemical detection of most chemical species. Another area of research where micro-fabrication is having a large impact is the development of a "lab on a chip." Sandia's efforts to develop the μChemLab™ will be described including the development of microfabricated pre-concentrators, chromatographic columns, and detectors. Smart sensors that allow the spacecraft independent decision making capabilities depend on pattern recognition. Sandia's development of a new pattern recognition methodology that can be used to interpret sensor response as well as for target recognition applications will be described.

Development of bug-free, high-surety, complex software is quite difficult using current tools. The brittle nature of the programming constructs in popular languages such as C/C++ is one root cause. Brittle commands force the designer to rigidly specify the minutiae of tasks, e.g. using ''for(index=0;index>total;index++)'', rather than specifying the goals or intent of the tasks, e.g. ''ensure that all relevant data elements have been examined''. Specification of task minutiae makes code hard to comprehend, which in turn encourages design errors/limitations and makes future modifications quite difficult. This report describes an LDRD project to seed the development of a surety computer language, for stand-alone computing environments, to be implemented using the swarm intelligence of autonomous agents. The long term vision of this project was to develop a language with the following surety capabilities: (1) Reliability -- Autonomous agents can appropriate y decide when to act and when a task is complete, provide a natural means for avoiding brittle task specifications, and can overcome many hardware glitches. (2) Safety, security -- Watchdog safety and security agents can monitor other agents to prevent unauthorized or dangerous actions. (3) An immune system -- The small chunks of agent code can have an encryption scheme to enable detection and elimination of unauthorized and corrupted agents. This report describes the progress achieved during this small 9 month project and describes lessons learned.

Optimal selection of array sensors for a chemical sensing application is a nontrivial task. It is commonly believed that "more is better" when choosing the number of sensors required to achieve good chemical selectivity. However, cost and system complexity issues point towards the choice of small arrays. A quantitative array optimization is carried out to explore the selectivity of arrays of partially-selective chemical sensors as a function of array size. It is shown that modest numbers (dozens) of target analytes are completely distinguished with a range of arrays sizes. However, the array selectivity and the robustness against sensor sensitivity variability are significantly degraded if the array size is increased above a certain number of sensors, so that relatively small arrays provide the best performance. The results also suggest that data analyses for very large arrays of partially-selective sensors will be optimized by separately anal yzing small sensor subsets.

This report describes the results of a Sandia Laboratov Directed Research & Development project to develop a technique that can identifi atoms in atomically engineered nanostructures. The report provides a detailed description of the experimental measurement techniques and subsequent image analysis procedures used in the identification process, followed by examples of the technique's successful application to several atomic surface features. Use of this technique requires the experimental measurement of both constant-current topographic and multi-bias conductance data from an atomic surface with the scanning tunneling microscope. These measurements are rendered as a collection of topographic and single-bias conductance images of the surface. Image pixels are then grouped into classes by a computed grouping algorithm, according to the shared conductance characteristics exhibited at each pixel. The image pixels are then color-coded by class to produce a false-color image of the scanned surface that chemically distinguishes surface electronic features over the entire area of the measured atomic surface.

Detecting object boundaries in the presence of cast shadows is a difficult task for machine vision systems. A new edge detector is presented which responds to shadow penumbras and abrupt object edges with distinguishable signals. The detector requires the use of spatially extended light sources and sufficient video resolution to resolve the shadow penumbras of interest. Detection of high frequency noise is suppressed without requiring image-dependent adjustment of signal thresholds. The ability of the edge operator to distinguish shadow penumbras from abrupt object boundaries while suppressing responses to high frequency noise and texture is illustrated with idealized shadow and object edge intensity profiles. Selective detection of object boundaries in a video scene with a cast shadow has also been demonstrated with this operator.

A new approach for solving two-dimensional clustering problems is presented. The method is based on an inhibitory template which is applied to each pair of dots in a data set. Direct clustering of the pair is inhibited (allowed) if another dot is present (absent), respectively, within the area of the template. The performance of the method is thus entirely determined by the shape of the template. Psychophysical experiments have been used to define the template shape for this work, so that the resulting method requires no pattern-dependent adjustment of any parameters. The novel concept of a psychophysically-defined template and the absence of adjustable parameters set this approach apart from previous work. The useful grouping performance of this approach is demonstrated with the successful grouping of a variety of dot patterns selected from the clustering literature.

A general representation approach is described which employs a hierarchy of holes and notches. A matching procedure is also described which allows non-ideal image hierarchies to be matched to class representations. The representation and matching methods are demonstrated on a set of handgun photographs. Examples of handguns which are different in detail are shown to exhibit the same class characteristics, while other similarly shaped objects are correctly distinguished from the handgun class. 6 refs., 8 figs.