Localization
Finding One Right Place Among a Million Just Like It
With every move it makes, the tiny, sub-millimeter modular catom confronts the question of where it is located among thousands to millions of other catoms in the claytronics ensemble.
Awareness of location - or localization -- is important because an individual catom needs to make moves in relation to other catoms in order to support the shifting shape of the ensemble. It is also important because, from its position, the catom provides a distinctive detail in the larger representation to which the ensemble gives a dynamic shape.
The localization of any individual catom in relation to all other catoms thus enables the ensemble accurately to enact the choreography of its motions. From its location, each particle moves with the omni-directional roll of one sphere against another to create the malleable reshaping of the ensemble, a fine-grain motion of millions of particles in a continuous shifting that reshapes the form.
In the rolling mass of thousands to millions of robotic modules, how does an individual catom know where to fit its shape and motion? In turn, how does the ensemble locate the position of the individual catom in the dynamic mass of all its particles? This is the essence of localization.
Alignment of Two Perspectives
One perspective is the global shape that the ensemble of millions of catoms forms at any moment. That perspective always presents a dynamic condition - of the ensemble reshaping its representation of an original object.
The other perspective is that of the individual catom, whose rotations adjust the ensemble's shape in one very specific site (with thousands of other catoms also rotating) to enable the form to continue to present a dynamic, 3-dimensional reality. While limited to its immediate neighbors in the ensemble, the perspective of a specific catom encompasses the essential work that shapes the ensemble. Between the two pespectives, it provides the focus for localization.
In other types of computing networks, detailed instructions are sent to each node, which possesses a unique address to identify its location for receiving and sending data. The address determines the path of delivery and the relationship of all parallel computation occurring in a network of related nodes. This typical network relationship, however, is virtual rather than physical. It does not matter where the nodes of computing are located as long as the data relationships shared between separate nodes maintain the proper alignment in time.
In contrast, a catom always functions in direct physical contact with other catoms. It is an independent, ever-shifting node with no distinct identification other than that derived from contact with its nearest neighbors. Among a catom's neighbors and neighbors’ neighbors throughout the ensemble, parallel computation distributes a constantly changing state of physical relationships between catoms. Operating within a mass of millions of other similarly indistinct modules, a catom's condition always reflects the result of parallel processing, which also changes the state of every other individual computing node.
Thus, the output of each catom is most often a state of motion. In this way, localization represents a function that integrates the motion from all parallel processing by all catoms. The result presents the dynamism of the 3-dimensional object that the ensemble represents. To achieve this result, each individual device depends upon a clear definition of its location to fit its motion into the overall shape of the ensemble's dynamic self-construction.
Like Birds in a Flock
This paradigm of relatedness within a shifting mass of nodes thus forces the individual catom to localize its position in relation to two general circumstances. In the clearer circumstance, the catom finds itself surrounded by other catoms from all points of view. In the more uncertain circumstance, the catom finds itself surrounded by fewer and fewer catoms with which it can localize its position. In both circumstances, the individual catom might be compared to a bird that flies within a very large flock whose shape similarly places all birds in circumstances where they can sometimes see all birds around them -- and sometimes not.
As feathered friends pitch and roll in patterns that can blacken the sky, an individual bird has no clear picture of the flock's overall migratory motion. Nonetheless, the flight of each bird sustains a position that keeps the flock intact. There is not only motion but also biological energy that binds the flock. Yet it is not all encompassing. It radiates from the activity of each bird and builds its noisy crackling force across the flock toward the horizon that draws the formation, balanced to bind the bird to the common instinctive motion but insufficient to overwhelm any individual need for release from the common direction.
If a hawk swoops upon the flock, the pattern breaks. Then the shifting form must reclaim synergy among scattered birds by remerging again into the prior unison. No universal intelligence orchestrates these recovery motions. Rather, each bird cues its motion to the behavior of close neighbors. Thus, a shift in the relative position of one bird propagates through the flock.
These flight patterns might be categorized in two general types. Birds flock together in close, tight formations. They maintain precise local relationships by direct observation and other signals such as calls from neighboring birds. Yet variations occur within the overall pattern of organized behavior. Birds that fly alongside boundaries, such as an outside edge or around voids in the midst of the flock, refer to nearest neighbors for location. When birds cannot sense uniform distances to other birds around them, they exchange more information to redefine their locations in the avian cloud.
Algorithms for Flocks of Catoms
A catom in an ensemble doesn't carry the heritage of a bird's embedded biological instincts. Nonetheless, its process of identifying its position can be managed with an algorithm that addresses changes in conditions that affect its sense of location. When catoms remain close together, the task of localization remains straightforward. To test the condition of general uniformity within the ensemble, each catom localizes its position by initial identification of its relative relationship to neighboring catoms with which it has direct contact. Through such direct contacts, an individual catom may be able to localize its position in relation to as many as 12 other catoms, a context of high density and more probable accuracy. However, a need for additional steps to interpret location arises when the catom senses emptiness in the spaces near it.
When Catoms Don't See Eye to Eye
Even in the regions of the ensemble where there is uniformity in distances between catoms, there may be some imprecision in localization due to slight misalignments of the sensors of one catom with those of another. However, because it is drawn from many nearby devices, the data can be averaged to achieve a high level of accuracy. This precaution to smooth data within localized groups is very important. Even slight errors magnify as the process of localization radiates through the ensemble and other catom groups rely upon prior reference points to identify their locations.
The greater challenge to localization arises along boundaries around voids. Because a deficit of neighbors for reference exists in those regions, localization errors become more likely. To deal with this common condition in ensemble structure, the algorithm of localization follows several steps to complete its analysis. First, it catalogs the relationship of dense and less dense regions. Then, by a series of cross-cuts in the statistical structure of the ensemble, the algorithm assigns segments of boundaries around voids to their nearest anchor points in more densely populated regions.
This step requires a skillful use of heuristics. Patches of irregular or poorly defined landscape often cannot be mapped with precision. There are no catoms inside the void to mark locations. Yet the boundary around the void must be defined. As a consequence, catoms forming this boundary must map a relationship to a denser area of the ensemble by a more probabilistic analysis to align a location around empty space.
In effect, the algorithm of localization subdivides a grouping of catoms near a void and refers the location of its newly identified segments to the region nearby that has greater density. For catoms in boundaries along voids, reallocation of reference points to nearest neighboring regions of density enables the individual node to localize its position with greater accuracy.
Cutting the Ensemble into Pieces
Localization thus occurs in a multi-step process that interprets the position of individual catoms in relation to nearest neighbors. Then statistical analysis addresses the density of regions in order to relate catoms located in less dense regions to neighboring regions of greater density. In regions of the ensemble where catoms are most densely concentrated, they are easier to localize. Regions of higher density provide bases to which to reorient nearby sections of harder-to-localize boundary areas. In this realignment, a segment of boundary area gains more points of reference from the region of heavier catom concentration to which it becomes attached.
In effect, regions of greater density serve as anchor points to smaller strings of catoms that otherwise have a harder time localizing their positions in relation to voids. As the survey of locations continues, the algorithm reassembles the regions that have been dissected in this process. This analytical process distributes the density of the ensemble into more accurately related regions that can then be fitted back together with more evenly distributed reference points. In final localization, the regions of heavier catom concentration again provide interfaces that make it easier to reassemble a complete map of catom locations throughout the ensemble.
Putting It Back Together Again
Much like birds that generate more complex calls to recapture bearings after a rift in the flock, the algorithm that assesses the location of catoms generates additional routines to realign catoms that have the fewest neighbors with regions of the ensemble that have greater density. This realignment moves from a view of the ensemble divided between dense and less dense regions to an analysis that further subdivides less dense regions and relates their pieces to regions of denser concentrations. The cuts continue until the distribution optimizes the probability of accurate localization.
Simulation of this process can be seen here.
This hierarchical segmentation thus attaches portions of the voids (and their difficult-to-localize boundary catoms) to regions that are easier to map. As smaller segments of larger pieces, difficult-to-localize areas can be more easily oriented in a final step. Realignment occurs when the algorithm reassembles its analysis of the regions with a natural fit for pieces of boundary that surround voids. Like a puzzle fitted together by bulkier pieces, subtle lines in the overall image suddenly appear. Formerly undefined background appears complete. Voids in the picture that could not be seen clearly in the pieces fall naturally into place.
In effect, the algorithm subdivides locations of greatest uncertainty and distributes them to regions of most accurate localization to which they have the nearest physical relationship. The algorithm employs the certainty gained from larger segments of accurate localization to minimize the amount of survey required to localize catoms holding positions of greater uncertainty. Then recursive testing of the result improves the solution.
Publications and Documents
The following sources provide more information about Localization:
