Several approaches have been proposed recently for building shapes with swarms of self-assembling robots. However, there is a dearth of information about the performance of each approach, and how to compare them. This paper considers the active self-assembly scheme introduced by Arbuckle and Requicha, and investigates its performance through extensive simulations. The difficulties encountered in the evaluation of self-assembly schemes are discussed. Empirical simulation data are presented that show that the time for completion of the boundary of a polygon by the active self-assembly scheme is approximately linear in the size of the polygon, for the range of parameters investigated.

Nanomanipulation with atomic force microscopes (AFMs) for nanoparticles with overall sizes on the order of 10 nm has been hampered in the past by the large spatial uncertainties encountered in tip positioning. This paper addresses the compensation of nonlinear effects of creep and hysteresis on the piezo scanners which drive most AFMs. Creep and hysteresis are modeled as the superposition of fundamental operators, and their inverse model is obtained by using the inversion properties of the Prandtl-Ishlinskii operator. Identification of the parameters in the forward model is achieved by a novel method that uses the topography of the sample and does not require position sensors. The identified parameters are used to compute the inverse model, which in turn serves to drive the AFM in an open-loop, feedforward scheme. Experimental results show that this approach effectively reduces the spatial uncertainties associated with creep and hysteresis, and supports automated, computer-controlled manipulation operations that otherwise would fail.

Automation has long been recognized as an important goal in AFM (atomic force microscope) nanomanipulation research. For the precise manipulation of small particles with sizes on the order of 10 nm, however, automation has remained an elusive goal, primarily because of the spatial uncertainties associated with the positioning mechanisms of the AFM and with the manipulation process itself. Extensive user intervention has been necessary for the construction of desired nanostructures with the AFM, resulting in very low throughput, and severely limiting the complexity of structures that could be built with a reasonable amount of time and labor. This paper describes a fully automatic system for building arbitrary planar patterns of nanoparticles by AFM manipulation. Given an initial, random distribution of particles on a substrate surface and a desired pattern to be formed with them, a planner determines the paths required to perform the manipulation operations. The output of the planner is a sequence of primitive commands for positioning and pushing operations involving motion along line segments. The primitive commands are executed through software that compensates for thermal drift, creep and hysteresis. Experimental results presented here show that the system can build in minutes a pattern that normally would take an experienced user a whole day to construct interactively.

Manipulation of nanoparticles with atomic force microscopes (AFMs) has been under development for a decade and is now well established as a technique for prototyping nanodevices and for other applications. Until now, the manipulation process for particles with sizes of a few nanometers has been very labor intensive. This severely limits the complexity of the structures that can be built. Particle sizes on the order of 10 nm are comparable to the spatial uncertainties associated with AFM operation, and a user in the loop has been needed to compensate for these uncertainties. This paper addresses thermal drift, which is the major cause of errors for AFMs operating in ambient conditions. It is shown that drift can be estimated efficiently by using Kalman filtering techniques. This approach has firm theoretical foundations and is validated by the experimental results presented in this paper. Manipulation of groups of 15-nm particles is demonstrated under program control, without human intervention over a long period of time, in ambient air and at room temperature. Coupled with existing methods for high-level motion planning, the manipulation capabilities introduced here will permit assembling, from the bottom up, nanostructures that are more complex than those being built today with AFMs. Note to Practitioners-Nanomanipulation with scanning probe microscopes (SPMs) has potential applications in nanodevice and system prototyping, or in small-batch production if multitip arrays are used instead of single tips. However, SPM nanomanipulation is still being used primarily in research labs. A major obstacle to its wider use is the labor and time involved in the process. These are largely due to spatial uncertainty in the position of the tip (which is analogous to a robot's end effector) relative to the sample being manipulated. Today, a skilled user is needed to determine where the tip is and to correct manipulation errors due to inaccurate positional estimates. The major cause of this spatial uncertainty is thermal drift between the tip and the sample. At the time scales relevant to manipulation, the drift can reach values comparable to the size of the objects, especially if these are below /spl sim/10 nm. The techniques discussed in this paper compensate for the drift and enable automated manipulation, with associated savings in time and labor, and increased complexity of the resulting structures.

Self-assembly is expected to become a dominant fabrication technique for the nanodevices and systems of the future. Traditional, or passive, self-assembly techniques have great difficulty in producing the asymmetric structures needed by the applications. This work discusses self-assembly methods that use active assembly agents (robots). It shows that swarms of such robots that communicate only by very simple messages can be programmed to form either wholly or partially specified structures, with the construction process possibly involving sacrificial components or scaffolds. The assembly agents have small memory and communication requirements, and interact only when they are in contact. They are good models for future nanorobots, which are likely to communicate chemically.

Locating gradient sources and tracking them over time has important applications to environmental monitoring and studies of the ecosystem. We present an approach, inspired by bacterial chemotaxis, for robots to navigate to sources using gradient measurements and a simple actuation strategy (biasing a random walk). Extensive simulations show the efficacy of the approach in varied conditions including multiple sources, dissipative sources, and noisy sensors and actuators. We also show how such an approach could be used for boundary finding. We validate our approach by testing it on a small robot (the robomote) in a phototaxis experiment. A comparison of our approach with gradient descent shows that while gradient descent is faster, our approach is better suited for boundary coverage, and performs better in the presence of multiple and dissipative sources.

Manipulation of nanoparticles with atomic force microscopes (AFM) has been under development for a decade, and is now well established as a technique for prototyping nanodevices and for other applications. The manipulation process tends to be labor-intensive because a user is needed in the loop to compensate for the numerous uncertainties associated with AFM operation. This work addresses thermal drift, which is the major cause of errors for AFM operated in ambient conditions. It is shown that drift can be estimated efficiently by using Kalman filtering techniques. Preliminary results indicate that drift compensation enables manipulation of groups of particles under program control, without human intervention, in ambient air and at room temperature. This is a first step towards fully automatic nanomanipulation, which would permit assembling, from the bottom up, nanostructures much more complex than those being built today with AFM.

We describe the design and construction of an underwater sensor actuator network to detect extreme temperature gradients. We are motivated by the fact that regions of sharp temperature change (thermoclines) are a breeding ground for certain marine microorganisms. We present a distributed algorithm using local communication based on binary search to find a thermocline by using a mobile sensor network. Simulations and experiments using a mote test bed demonstrate the validity of this approach. We also discuss the improvement in energy efficiency using a submarine robot as a data mule. Comparisons between experimental data with and without the data mule show that there are considerable energy savings in the sensor network due to the data mule.

The research discussed in this paper is focused on algorithmic issues that arise in highly-distributed robotics systems at the nanoscale. The fundamental problem to be addressed is how to program large numbers of limited-capability robots so that they assemble themselves into complex nanostructures with specified shapes. Unexpected connections between geometric modeling and distributed robotics emerge from this work. Nanorobots have dimensions comparable to those of biological cells, and are expected to have remarkable applications in health care and environmental monitoring. For example, they might serve as programmable artificial cells for early detection and destruction of pathogens. The motivation for this project, however, does not stem from environmental or biomedical applications, but rather from the need to build nanostructures efficiently. Assembly of nanoscale components with scanning probe microscopes (SPMs), which is used extensively today, is inherently a sequential process, ill-suited to mass production. Passive self-assembly, that is, the autonomous assembly of building blocks driven by natural phenomena such as thermal agitation or surface tension, is an efficient, massively parallel process, but typically cannot produce the asymmetric structures needed by many applications. Active self-assembly, the approach proposed here, uses nanorobots as building blocks, and programs them through simple local rules to generate specified global shapes. Once the desired configuration is achieved, the constituent robots themselves become the structure. Active self-assembly is a massively parallel process that does not appear to have the drawbacks of its passive counterpart. Individual nanorobots of the future are expected to have limited capabilities: small memories and processors, few sensors, and communications primarily based on chemical interactions, which require contact between robots. A robot per se will not do much, but large teams of such robots may achieve complex behaviors. In the work reported in this paper nanorobots teams are modeled as swarms of robots in which each robot has a simple shape, is controlled by a small finite-state machine, and is capable of moving autonomously and exchanging a small number of messages with other robots only when they are in contact. The results to be presented show that it is possible to use such models to build wires (or, equivalently, to plan collision-free paths) between given locations, as well as to construct various shapes. The ultimate goal of the project is to demonstrate that essentially arbitrary nanostructures can be built by programming such robot swarms.

Nanorobotics encompasses the design, fabrication, and programming of robots with overall dimensions below a few micrometers, and the programmable assembly of nanoscale objects. Nanorobots are quintessential nanoelectromechanical systems (NEMS) and raise all the important issues that must be addressed in NEMS design: sensing, actuation, control, communications, power, and interfacing across spatial scales and between the organic/inorganic and biotic/abiotic realms. Nanorobots are expected to have revolutionary applications in such areas as environmental monitoring and health care. This paper begins by discussing nanorobot construction, which is still at an embryonic stage. The emphasis is on nanomachines, an area which has seen a spate of rapid progress over the last few years. Nanoactuators will be essential components of future NEMS. The paper's focus then changes to nanoassembly by manipulation with scanning probe microscopes (SPMs), which is a relatively well established process for prototyping nanosystems. Prototyping of nanodevices and systems is important for design validation, parameter optimization and sensitivity studies. Nanomanipulation also has applications in repair and modification of nanostructures built by other means. High-throughput SPM manipulation may be achieved by using multitip arrays. Experimental results are presented which show that interactive SPM manipulation can be used to accurately and reliably position molecular-sized components. These can then be linked by chemical or physical means to form subassemblies, which in turn can be further manipulated. Applications in building wires, single-electron transistors, and nanowaveguides are presented.

NEMS (nanoelectromechanical systems) loom beyond the MEMS horizon as the new frontier in miniaturization. Nanorobots and other NEMS are expected to find revolutionary applications in science, engineering and everyday life. Until now, nanostructures have been built primarily in 2D, because of the difficulties of 3D fabrication. This paper describes a promising approach to the construction of 3D nanostructures by working in successive layers, much like the rapid prototyping techniques used in the macroscopic world. Each object nanolayer is built by nanomanipulation, or possibly by programmed self-assembly, and then surrounded by a sacrificial layer that planarizes the sample and serves as a substrate for the deposition of the next object nanolayer. Initial experimental results which show that the approach is feasible are presented.

Path planning is a crucial step in automatic programming of coordinate measuring machines(CMMs). The goal is to generate an efficient and collision-free path for the CMM to inspect a collection of points. Previous research concentrates on path planning between two points, or sequencing the points without regard to obstacles and collisions. In this paper we propose a practical path planner that considers both sequencing and collision avoidance. The main idea is to create a roadmap of free-space, where the measurement points are nodes in the network. Once all the measurement points are in a single connected component of the roadmap, then a tour of the points is found by solving the appropriate traveling salesperson problem. CMM heuristics are used to construct the roadmap in an efficient and robust manner. The planner has been implemented and tested on real-world mechanical parts.

Analyzing the accessibility of an object's surface to probes or tools is important for many planning and programming tasks that involve spatial reasoning and arise in robotics and automation. The paper presents novel and efficient algorithms for computing accessible directions for tactile probes used in 3D digitization with Coordinate Measuring Machines. The algorithms are executed in standard computer graphics hardware. They are a nonobvious application of rendering hardware to scientific and technological areas beyond computer graphics.

Assembly of nanometer-scale objects by scanning probe microscope (SPM) as a promising approach for the fabrication of nanoelectromechanical systems (NEMS). This paper describes several techniques for positioning nanoparticles, linking them to form subassemblies, and moving entire subassemblies. These are first steps towards the hierarchical construction of complex nanoassemblies. Results of experiments conducted in ambient air and in liquid environments are presented. Nanomanipulation in liquids opens new research directions involving interactions with single biomolecules, and fine control of forces between tips, particles and surface substrates.

Computer-controlled dimensional inspection is typically performed with coordinate measuring machines (CMMs), which are very precise Cartesian robots that use touch probes to measure the coordinates of points on a workpiece's surfaces. Automatic planning and programming of inspection tasks with a CMM involve spatial reasoning, to determine how to orient the part on the CMM, which probes to use, how to orient the probes, and so on. This paper introduces the notions of accessibility and approachability, which are important for inspection planning, and describes two sets of implemented algorithms for computing accessibility information. One of these sets of algorithms performs exact computations on polyhedral objects and is relatively slow, whereas the other uses discrete approximations and achieves high speed by exploiting standard computer graphics hardware. The discretized algorithm has been tested on real-world parts, and is sufficiently fast for industrial applications.

Precise control of the structure of matter at the nanometer scale will have revolutionary implications for science and technology. Nanoelectromechanical systems (NEMS) will be extremely small and fast, and have applications that range from cell repair to ultrastrong materials. This paper describes the first steps towards the construction of NEMS by assembling nanometer-scale objects using a scanning probe microscope as a robot. Our research takes an interdisciplinary approach that combines knowledge of macrorobotics and computer science with the chemistry and physics of phenomena at the nanoscale. We present experimental results that show how to construct arbitrary patterns of gold nanoparticles on a mica or silicon substrate, and describe the underlying technology. We also discuss the next steps in our research, which are aimed at producing connected structures in the plane, and eventually three-dimensional nanostructures.

Solid modelers and other CAD/CAM subsystems are moving to distributed heterogeneous computing environments, so as to support design and manufacturing processes that are temporally and spatially distributed. Communication and collaboration among the software components of such distributed systems require protocols for accessing remote objects. This paper discusses an approach that provides transparent access to diverse solid modelers in a distributed environment. A solid modeler is augmented with a software wrapper, called an adaptor, so as to provide a uniform application programming interface (API). Applications interact with the uniform API and need not concern themselves with the specifics of the modeling systems used. API calls are implemented in a client-server architecture, in which a modeler and its adaptor function as a geometry server, and various applications communicate with the server through remote procedure calls (RPCs). A few adaptors have been implemented at the University of Southern California's Programmable Automation Laboratory, and have been used routinely for several years. This paper discusses adaptor design problems and our approach to their solutions. It illustrates the application of our methods through an example that involves the incremental recognition of machinable features in a distributed environment. This environment includes a geometry server, a simple feature-based design system, a state-of-the-art feature recognizer, and a graphics renderer, all running as separate processes in different machines. To our knowledge, this is the first documented effort in which a complex application such as feature recognition is capable of running, unmodified, on top of modelers based on constructive solid geometry or on boundary representations, which are fundamentally different.

A fixture is an arrangement of fixturing modules that locate and hold a workpart during a manufacturing operation. In this work we consider fixtures with frictionless point contacts and present a method for placement of contact points on a non-prismatic 3D workpart. It is a nondeterministic, potential field algorithm for contact point placement. The method provides a basic framework for the integration of heterogeneous high-level fixturing agents through an interface based on zones of attraction and repulsion on the workpart boundary. The algorithm may produce redundant fixtures, and can augment partial solutions to complete form closure fixtures.

This paper describes modeler independent application programming interfaces called adaptors. A solid modeler is augmented with an adaptor so as to provide a standard procedural interface to applications and function as a geometric server. Adaptors give the applications portability and free the application programmers from the details of specific modelers. Adaptors have been developed at USC for two different modelers, PADL-2 (a Constructive Solid Geometry system) and Parasolid (a boundary modeler). The issues raised in adaptor development and their solutions are discussed. Adaptors are routinely used at USC in a distributed environment where a solid modeler augmented with an adaptor, an application, and a renderer run as separate processes and communicate with one another through local area networks.

This paper discusses a planner that generates automatically high-level programs (or plans) for inspecting mechanical parts with coordinate measuring machines. The system's input is a solid model of a toleranced part, and the output a collection of setups, probes and probe orientations associated with the surface features to be inspected. The problem is formulated as state space search. The state contains a collection of inspection plans, represented as a set of 4-tuples of the form (setup, probe, probe direction, surface feature). The initial plans may be invalid, or unnecessarily expensive. The state evolves through the application of operators, which impose geometric and optimization constraints so as to produce a valid and nearly optimal plan. The paper discusses the planner architecture and implementation, and presents experimental results.>

Abstract Geometric modelers are becoming faster and more powerful, but they still suffer from reliability problems because of floating point errors. Previous work in the field of robust geometric modeling tends to be problem specific and has proven hard to generalize. The approach described here is a general paradigm for handling the accuracy problem for a large set of geometric algorithms. This approach brings together ideas and techniques from interval arithmetic, constraint management, randomization, and algebraic geometry. It acknowledges that input values have tolerances, that objects within tolerance are equivalent, and that certain geometric singularities must be maintained because they reflect design intent or the laws of geometry. Our approach is systematic, and can be applied almost mechanically to the large domain of problems that can be solved by algorithms using the operations +, −, * and /. The required theory and algorithms have been developed, and the viability of the concepts has been demonstrated by an experimental implementation involving linear half‐spaces in Euclidean 2‐dimensional space. The implementation focuses on algorithms for computing the boundaries of objects defined by Constructive Solid Geometry (CSG) trees.

Discusses an automatic feature recognizer that decomposes the total volume to be machined into volumetric features that satisfy stringent conditions for manufacturability, and correspond to operations typically performed in 3-axis machining centers. Unlike most of the previous research, the approach is based on general techniques for dealing with features with intersecting volumes. Feature interactions are represented explicitly in the recognizer's output, to facilitate spatial reasoning in subsequent planning stages. A generate-and-test strategy is used. OPS-5 production rules generate hints or clues for the existence of features, and post them on a blackboard. The clues are assessed, and those judged promising are processed to ensure that they correspond to actual features, and to gather information for process planning. Computational geometry techniques are used to produce the largest volumetric feature compatible with the available data. The feature's accessibility, and its interactions with others are analyzed. The validity tests ensure that the proposed features are accessible, do not intrude into the desired part, and satisfy other machinability conditions. The process continues until it produces a complete decomposition of the volume to be machined into fully-specified features.>

An overall strategy for inspection planning is discussed, and attention is focused on local and global accessibility cones and on algorithms for computing and clustering them. The direction-cone clusters serve to generate a minimal set of directions for inspecting a part. The algorithms are based primarily on the computation on Gaussian images and Minkowski (or sweeping) operations. Applications to computer vision and automatic machining are briefly presented.>

Tolerancing and surface finish data are essential for automatically planning the manufacture, inspection, and robotic assembly of mechanical components. A scheme for representing surface features in a solid modeler based on constructive solid geometry (CSG) and for associating tolerances and other attributes with such features. It shows conclusively that commonly-held beliefs on CSG's inability to deal with surface features and tolerances are unfounded. The scheme has been implemented in the PADL-2 modeling system and is being used to support research on high-level languages for programming numerically controlled (NC) machine tools.

Solid modeling plays a key role in electromechanical CAD/CAM, three-dimensional computer graphics, computer vision, robotics, and other disciplines and activities that deal with spatial phenomena. Almost all contemporary solid modeling systems support Boolean operations akin to set intersection, union, and difference on solids. Boundary representations (face/edge/vertex structures) for solids defined through Boolean operations are generated in these modelers by using so-called boundary evaluation and boundary merging procedures. These are the most complex and delicate software modules in a solid modeler. This paper describes boundary evaluation algorithms used by the PADL solid modeling systems developed at the University of Rochester, and discusses other known approaches in terms of concepts that emerged from the PADL work, notably set membership classification and neighborhood manipulation.

PADL (Part and Assembly Description Language) is a language for defining solid objects via constructive solid geometry, i.e. as (regularized) set-theoretical compositions of primitive solid “building blocks”. The current processor for Version 1.0 of the language accepts PADL statements either in batch or in keyboard-interactive mode and produces line drawings of objects on CRT's and plotting devices. A variety of drawing styles is available: dimensioned orthographics, perspectives, section views, interference drawings, etc.

The computation of expected values of functions of quantized random variables is treated by sampling theory methods, as an extension of Widrow's work on the statistical theory of quantization. It is shown that such expected values can often be evaluated readily when conditions analogous to Nyquist sampling constraints are satisfied. An example-computation of the autocorrelation of a phase-quantized angle-modulated signal-is provided to illustrate the use of the theory. Other potential areas of application are suggested.

Two algorithms are proposed for recovering signals subjected to bandpass clipping and related types of nonlinear transformations. Both are based on contraction mapping principles and both seem to work experimentally, but neither has been validated formally. The conditions on signal determinism suggested by the algorithms have interesting practical implications.

Band-limited (BL) random-real-zero (RRZ) signals are a class of stationary stochastic processes whose zero crossings are the randomly perturbed zeros of a sinusoid. They are the only nontrivial examples known to date of band-limited signals whose correlation function and power spectrum can be computed exactly from a probabilistic description of their zeros. Such signals have optimal correlation characteristics, in the sense that their correlation function exhibits the maximum peak to sidelobe ratio attainable under a fixed bandwidth constraint.