David W. Payton

Self-organized criticality (SOC) is a phenomenon observed in certain complex systems of multiple interacting components, e.g., neural networks, forest fires, and power grids, that produce power-law distributed avalanche sizes. Here, we report the surprising result that the avalanches from an SOC process can be used to solve non-convex optimization problems. To generate avalanches, we use the Abelian sandpile model on a graph that mirrors the graph of the optimization problem. For optimization, we map the avalanche areas onto search patterns for optimization, while the SOC process receives no feedback from the optimization itself. The resulting method can be applied without parameter tuning to a wide range of optimization problems, as demonstrated on three problems: finding the ground-state of an Ising spin glass, graph coloring, and image segmentation. We find that SOC search is more efficient compared to other random search methods, including simulated annealing, and unlike annealing, it is parameter free, thereby eliminating the time-consuming requirement to tune an annealing temperature schedule.

We describe techniques for coordinating the actions of large numbers of small-scale robots to achieve useful large-scale results in surveillance, reconnaissance, hazard detection, and path finding. Inspired by the chemical markers used by insects for communication and coordination, we exploit the notion of a “virtual pheromone,” implemented using simple beacons and directional sensors mounted on each robot. Virtual pheromones facilitate simple communication and coordination and require little on-board processing. Our virtual pheromone technique enables a robot collective to become a distributed computing mesh embedded within the environment, while simultaneously acting as a physical embodiment of the user interface. This leads to notions of world embedded computation and world embedded interfaces that provide new ways to think about robot colonies.

Much of the recent interest in active vision has focussed on the development of novel methods for controlling fast pan/tilt camera mounts, called eye-head systems. Simple real-time processing of input images coupled with fast control has enabled interesting system behaviors. This paper describes the ongoing development of behavior-based control methods for a miniature eye-head system. We first describe the eye-head hardware and image processing system. We then define and present approaches for behavior-based control of the eye-head system. Finally, we discuss results from the use of simple behaviors for verging two cameras on moving objects.