Pheromone Robotics Assignment PDF
9 Pages7134 Words120 Views
Added on 2021-06-15
Pheromone Robotics Assignment PDF
Added on 2021-06-15
ShareRelated Documents
Copyright © 2001, HRL Laboratories, LLC. All Rights Reserved Pheromone Robotics David Payton1, Mike Daily1, Bruce Hoff2, Mike Howard1, Craig Lee11 HRL Laboratories, LLC 3011 Malibu Canyon Road, Malibu CA 90265 2BioDiscovery, Inc. 11150 West Olympic Blvd., Los Angeles, CA 90064 {payton, mjdaily, mhoward, lee@hrl.com}, hoff@biodiscovery.com ABSTRACTWe 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. We exploit the biologically inspired notion of a “virtual pheromone,” implemented using simple beacons and directional sensors mounted atop each robot. Unlike the chemical markers used by insect colonies for communication and coordination, our virtual pheromones are symbolic messages tied to the robots themselves rather than to fixed locations in the environment. This enables our 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 displays that provide different ways to think about robot colonies and the types of distributed computations that such colonies might perform. Keywordsrobot swarm, emergent behavior, distributed control, multi-agent systems. 1. INTRODUCTION Consider a scenario in which a rescue team enters an unfamiliar building after a disaster, and needs to quickly locate any survivors. At the building’s entrance, they empty a container of thousands of tiny robots onto the floor (Figure 1a). Using simple attraction/repulsion behaviors, these robots quickly disperse throughout the building, maintaining communications contact with only their nearest neighbors (Figure 1b). Upon detection of a survivor, a robot emits a “virtual pheromone” message signaling the discovery. This message is diffused throughout the distributed mesh of robots, propagating only along unobstructed paths. Ultimately, the message makes its way back to the rescue team, signaling that someone has been found. Since each robot remembers the direction from which it received the message, the robots now collectively serve as a distributed array of guideposts (Figure 1c). Using an augmented reality display, members of the rescue team can then view the robot mesh as a world-embedded display, showing the local gradient that leads to the survivor. Following this gradient will provide the team with the shortest unobstructed path to the survivor. Emerging technologies in micro machining and MEMs hold the promise of someday enabling the creation of extremely small robots, with fully self-contained sensors, actuators, computation, and power, that could make the above scenario a reality. Such robots operating alone would most likely have very limited ability to perform useful tasks. However, thousands of tiny robots, operating as a coordinated swarm, could conceivably accomplish a wide range of significant tasks [12],[13],[20],[22],[28]. Ultimately, swarms of small-scale robots should be able to achieve large-scale results in tasks such as surveillance, reconnaissance, hazard detection, path finding, payload conveyance, and small-scale actuation. The challenges to reaching this goal lie as much in the technology for controlling and coordinating the actions of thousands of entities as it does in the technologies for miniaturization. Coordinating and interacting with a large collective of tiny robots involves many issues that are not encountered when dealing with one or a few robots [4],[5],[14],[15],[24]. Even something as trivial as turning them all on at the same time can be an awesome job for someone dealing with many thousands of robots. Coordination schemes that require unique identities for each robot, explicit routing of point-to-point communication between robots, or centralized representations of the state of an entire swarm can be overwhelmed when dealing with extremely large numbers of robots. We address these issues of coordination and control by borrowing from techniques used by ants and termites. Inspired by the chemical markers used by these insects for communication and coordination, we introduce a type of “virtual pheromone,” implemented using simple beacons and directional sensors mounted on each robot. Like their chemical counterparts, our virtual pheromones facilitate simple communication and emergent coordinated movement between robots while requiring minimal on-board processing. Unlike chemical pheromones, virtual pheromones also transform a robot swarm into a distributed computation grid embedded in the world. This grid can be used to compute non-local information about the environment such as shortest paths and choke points in ways that are foreign to insect colonies. Our goal is to apply these techniques in a manner that is applicable to future robots with extremely small form factors and is scaleable to large, heterogeneous groups of robots as well.
Copyright © 2001, HRL Laboratories, LLC. All Rights Reserved 2. VIRTUAL PHEROMONES In nature, pheromones and pheromone gradients are used extensively by insects to produce sophisticated organized group activity that emerges out of the simple interactions between individuals [2],[9],[16]. In the field of swarm intelligence [8], emergent properties of this type are considered extensively in both natural and artificial systems. In the case of artificial systems, the ant colony analogy is often transferred from a physical embodiment to a symbolic one where agents move about through graph representations, and pheromone trails are manifested as numerical quantities. In such instances, it is possible to go beyond the pure modeling of insect behavior to solving complex optimization problems [11], using methods inspired by, but only vaguely resembling true insect behavior. In the case of physically embodied artificial systems such as robot swarms, the primary emphasis has been to emulate behaviors of natural systems such as ant foraging, sorting, or cooperative transport [7],[17],[19]. In some cases, robots have even been designed to leave trails that emulate the chemical pheromones used by insects [27]. Our work in pheromone robotics differs from this past work because we too seek to go beyond the pure modeling of insect behavior. We have done so by using a symbolic message-based analogy to a pheromone, or virtual pheromone, in the context of a physical system. The unique differences between chemical pheromones and our virtual pheromones allow our robots to exhibit forms of distributed computation not found in nature, while retaining many of the emergent self-organization properties of insect colonies. In implementing a mechanism for virtual pheromones, we had to be mindful of some of the essential properties of natural pheromones that make them effective in facilitating group organization. First, the sender of a pheromone message need not be concerned with the identity of the recipient, nor does the sender need any guarantee that the message has even been received. This makes pheromones ideal for communication within large populations of simple entities where the implementation of complex protocols or the coding of unique identities might be impractical. Pheromones provide important navigational cues to members of a group by way of the directional intensity gradients created from diffusion. Diffusion gradients also encode useful information about barriers in the environment since physical obstacles can block pheromone propagation. Another essential property of pheromones is their tendency to decay over time if not replenished. This prevents cluttering the environment with obsolete or irrelevant information. To arrive at properties similar to chemical pheromones, we have developed an implementation of virtual pheromones that uses transmitted signals from each robot that are sustained in a relay-type fashion. Atop each robot is a set of radially-oriented directional infrared receivers and transmitters as shown in Figure 2. Infrared was chosen as the preferred medium of transmission because it is directional, it propagates by line of sight, it is easily modulated, and it loses intensity with increased distance from the source. Directionality is needed to encode pheromone gradients, line-of-sight propagation is needed to assure that pheromone gradients do not pass through walls, modulation is needed to encode pheromone type and other data, and distance drop-off is needed to allow robots to estimate their distance to the sender. Virtual pheromones are encoded through discrete modulated messages consisting of a type field, a hop-count field, and a data field. Upon receipt of a virtual pheromone message, a robot decrements the hop-count field and re-transmits the message in some or all directions. The robot also retains, for internal use, the direction from which the pheromone signal was received. If a robot receives the same type of pheromone from multiple directions, the robot selects the message with the highest hop-count value for re-transmission. Any pheromone messages of the same type received with hop-count values equal to or less than the hop-count already transmitted are ignored. These propagation rules are illustrated with a team of six robots in Figure 3. To deal with message collisions, when virtual pheromones from multiple TTT(a)(b)(c)Figure 1: Robots disperse through a building to become an embedded computing grid and an embedded display for finding the shortest path to a survivor. IR Digital Receiversmodified to provide signalstrength outputIR TransmitBeacons(under each receiver)CommunicationsPICFigure 2:Transceiver for virtual pheromones
Copyright © 2001, HRL Laboratories, LLC. All Rights Reserved robots are received from the same direction, messages are encoded with a checksum byte that allows detection of corrupted data. Unlike the chemical markers used by insect colonies for communication and coordination, our virtual pheromones are tied to the robots themselves rather than to fixed locations in the environment. This means that as robots move, they immediately alter the pheromone gradient. In addition, since virtual pheromones are propagated as symbolic messages, pheromone gradients may be altered without the need for physical movement of the robots. Despite the fact that a robot’s virtual pheromone transmissions are received only by nearby neighbors, the relay mechanism allows any single message to propagate quickly throughout an entire swarm of robots. If an originating source for a virtual pheromone moves, the gradient will adjust quickly, without the persistence of chemical pheromones. We can even envision implementing various ant algorithms using the messaging system alone, without any need for the robots to move. In this sense, our robot collective can truly become a distributed computing grid with each node providing local sensing, and connectivity between nodes revealing information about the topology of traversable paths. These properties are very important for enabling world-embedded computation, as will be described in a later section. 3. ROBOT MOVEMENT PRIMITIVES Our primary robot behavior primitives are centered on notions of repulsion and attraction, using virtual pheromones as the basis for determining proximity between neighboring robots. Repulsion is needed to assure that robots do not collide with obstacles and other robots. It is also used to ensure that robots will spread out and achieve maximal coverage of a space. In some cases, we may even want robots to be repulsed by a locally broadcast message so that one robot can block others from coming near. Meanwhile, attraction is needed to assure that robots do not spread out so much that they lose contact with one another. Attraction may also be used to allow robots to follow a terrain feature, or to follow a pheromone gradient toward its source. These attraction and repulsion forces can be viewed as a simple form of social potential fields [26] Appropriately combining the elemental attraction and repulsion behaviors can produce a variety of emergent group behaviors [3]. Two important emergent behaviors that are central to our world-embedded computation approach are the “gas expansion” model and the “guided growth” model. The gas expansion model is intended to cause robots to emulate gas particles filling a vacuum, arriving at a uniform density of robots throughout a closed environment, starting with a compact collection of robots. This model is based on a competition between attraction and repulsion behaviors that depend on inter-robot distance. These behaviors use the intensity of pheromone beacons from neighboring robots as an indicator of proximity. Using a set of discrete ranges, as shown in Figure 4, the attraction and repulsion behaviors can be tuned to maintain a medium-range distance from other robots. If a robot is in the short-range region of another robot it will be repulsed, if it is in the long-range region it will be attracted. These simple behaviors allow a robot swarm to expand from a tight grouping into a maximal dispersion that maintains communications between each robot and its nearest neighbors as shown in Figure 5. In many cases, a space may be too large relative to the number of available robots to allow the use of the gas expansion model alone. In this case, we use methods that allow robots to partially fill a space in a controlled manner. We refer to these methods as “guided growth” methods. The most basic of these is to use the gas expansion model in conjunction with user-designated “barrier” robots, which emit barrier pheromones that prevent other robots from coming near. The user can designate one or more robots to perform such a role via remote tagging using a laser designator or a command with a unique ID. A more advanced example of guided growth is the “bud growth” model, inspired by analogies to plant growth. One robot is designated as a “bud,” and this bud starts expanding away from the robot swarm (Figure 6a). As it moves away, other robots expand to fill the space (Figure 6b) to maintain communications Figure 3:Virtual pheromones are relayed with a lower hop-count by each subsequent robot. short_rangemedium_rangelong_rangeoutofrangeFigure 4: Decrease of pheromone beacon intensity with distance provides a basis for robot attraction and repulsion.
End of preview
Want to access all the pages? Upload your documents or become a member.