What kinds of big jobs could lots of little robots do by working together?
What do we mean when we say "working together"? What would the robots have to know about "working together"? Would they have to be able to see each other? Talk with each other? How would each robot know what to do? How could we make sure that the robots would actually help each other, and wouldn't just get in each others' way?
How would we tell a whole lot of robots to do a specific job? When they were done, how would we tell whether they had done the job right? Would we be able to keep track of what they were all doing while they were doing it? How? Would we be able to stop them if they went wrong? How?
Of course, these pages will forever be under construction -- the content is almost all there, but the html still needs some cleaning up, and there are a few goodies yet to be added.
Navigation Sensor Abstractions
Nature provides a number of animal models for sensor-based navigation which differ greatly from the "go to coordinate x,y" model used in industrial manipulators and in many human navigation tasks. The sensors which support these navigational processes are diverse, not only in the physics (or chemistry) of the sensed phenomena, but also in the fundamental types of information provided to the navigational process.
Simulation: Condensation Behavior
A simulation is presented of a robust distributed algorithm that allows numerous robots to "condense" into a compact group without a beacon or central control of any sort. The algorithm requires only that each element be able to sense the relative bearing of (enough of) the other elements. An interesting (and potentially useful?) behavioral artifact is induced by the time-step nature of the simulation.
Target Detection Sensor Abstractions
A target detection sensor's performance as a function of closest approach can be modeled by a "lateral range curve". Search theoretical analyses often use an approximation of the sensor that provides guaranteed detection within a specified range (a "definite range law", or "cookie cutter" model). Our analysis hinges on using a more sophisticated (but still idealized) model of detection -- a specified probability of detection which is strictly less than one and is uniform over a specified range ("imperfect sensor").
Models for Coordinated and Random Searches
Analytical models are established -- employing "imperfect sensors" -- for the performance of two alternative canonical search processes -- a completely coordinated search (like a lawnmower) and a completely random search (uncorrelated point sampling).
Measuring Search Effectiveness for Many-Target and Single-Target Searches
The search performance of a many-searcher system can be factored into components dependent on (1) the characteristics of the target detection sensor, (2) the number and range of the robots, and (3) the efficiency of the search strategy (search "gain"). If costs can be assigned to various levels of performance of these system components, then tradeoffs can be performed in a multi-dimensional system design space. What the cost optimal system will look like depends sensitively on component cost/performance (especially for target detection sensor performance and search gain), and also on the relative values assigned to finding targets versus identifying target-free space. The poorer the target detection sensor, the more the tradeoff will favor random search.
Randomized Search Strategies
While the analytical model of a "random" search is uncorrelated point sampling, physical robots follow continuous tracks in which successively sampled points are strongly correlated. We would like to have a "randomized" search strategy whose coverage of an area is as uniform as possible, without waiting for the asymptotic limit (i.e., searching forever) that search theorists use as their benchmark. We propose a fairly obvious generalization of a strategy previously proven to provide asymptoptically uniform coverage over a circular disk, and present some simulation results.
Modeling Lack of Sweep Independence and Search Performance Validation
Some targets will be intrinsically less detectable than others, and this can be explicitly included in modeling and simulation. Data to support this in real world applications should come from statistically sophisticated (but operationally simple) evaluations of actual mine detection sensor performance in the field.
The Motivating Nightmare Scenario
As we move in scale from a system of 5 hand-crafted units to a first production run of 1000, we will likely encounter behaviors that didn't appear in our simulations. We will need communications in order to find out what the offending robots "think" they are doing, and to reprogram them -- even if we know that the operational system we ultimately deploy will need have no communication capability.
Communication Channels, Protocols, and Cueing
Classical "bits is bits" communication a la Shannon is only one end of a spectrum of possible coordination mechanisms -- a robot's behavior can be driven by any sensory input, including observations of its neighbors' behaviors. Biological systems, too, tend to make use of cueing mechanisms which only sometimes involve intentionality on the part of the transmitter of the cue. The line between what is and what is not "communications" is not a distinct one.
The Command Channel: "SLEEP"
A single broadcast channel can allow the user or developer to command or manage an arbitrarily large number of robots through the use of "situational addressing". The specific scheme proposed is termed "SLEEP", for "Simplified LISP-like Expression Evaluation Paradigm".
Command Channel Management
Clever exploitation of command channel statistics allows a SLEEP system user to initiate a one-to-one session with one of a situationally addressed group of nodes, and to discover approximately how many members are actually in the group, which can be arbitrarily large.
Other Coordination Mechanisms
The SLEEP command channel can be supplemented by other coordination mechanisms. A small number of LEDs or other means of displaying a few bits of state can be used both for coordination with neighboring robots, and for reporting specified elements of robot state to the user. A modulated laser "flashlight" could allow a user to designate specific robots ("hey, you... yes, you!"). A means of activating and deactivating large numbers of robots will be required both for deploying operational systems and for supporting the development process.
SLEEP Operation, Functions, and Variables
A LISP-like processing system is proposed in which (1) variables include memory-mapped sensor inputs and actuator outputs, and (2) standard arithmetic, boolean, and LISP special forms are augmented with randomization funtions. An initial exploratory version of SLEEP has been implemented in C. An illustrative example outlines how SLEEP could be mapped to a specific application (Hoskins' "emergent Braitenberg Vehicle").
Factors in Cost-Optimal System Design
Even at the grossest level (e.g., many very simple and cheap robots vs. fewer more complex and expensive robots), cost-optimal many-robot system design is sensitive to component subsystem price and performance, to the details of explicit mission-specific goals, and to the details of implicit user policies.
Reconciling Design Flexibility and Efficiency
An efficient and flexible robotic system integration architecture will be required to resolve the serious conflict between (1) the fact that cost-optimality considerations will dictate widely varying system approaches to satisfy the requirements of different applications, and (2) the fact that minimum production costs will require tight physical integration of a robot's component functional subsystems.
The Evolution of Products and Marketplace
The first commercially successful many-robot systems may well be adapted from other mass market products (e.g., toys). Large companies with the resources to aggressively minimize production costs will become key players once it becomes clear that there is a commercially viable mass market for a given class of many-robot products.
Please address all questions and comments to: robo-web@spawar.navy.mil
Last update: 23 December 1998.
Back to Robotics home page